0

我需要生成一个 10 个字符的唯一 ID（SIP/VOIP 人员需要知道它用于 P-Charging-Vector 标头中的参数 icid 值）。每个字符应为 26 个 ASCII 字母之一（区分大小写）、10 个 ASCII 数字之一或连字符减号。

它必须是“全球唯一（在生成 id 的机器之外）”和足够“本地唯一（在生成 id 的机器内）”，所有这些都需要打包成 10 个字符，唷！

这是我的看法。我首先将“必须”编码为base-63（它是一个无符号长整数，编码后将占用1-6个字符），然后尽可能多地编码当前时间戳（它的一个 time_t/long long int 编码后将占用 9-4 个字符，具体取决于编码后的 ip 地址首先占用多少空间）。

我还在时间戳中添加了循环计数“i”以保持唯一性，以防在一秒钟内多次调用该函数。

这是否足以成为全球和本地独特的，还是有另一种更好的方法？

高拉夫

#include <stdio.h>
#include <string.h>
#include <sys/time.h>

//base-63 character set
static char set[]="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-";

// b63() returns the next vacant location in char array x
int b63(long long longlong,char *x,int index){
    if(index > 9)
        return index+1;

    //printf("index=%d,longlong=%lld,longlong%63=%lld\n",index,longlong,longlong%63);
    if(longlong < 63){
        x[index] = set[longlong];
        return index+1;
    }  

    x[index] = set[longlong%63];
    return b63(longlong/63,x,index+1);
}

int main(){
    char x[11],y[11] = {0}; /* '\0' is taken care of here */

    //let's generate 10 million ids
    for(int i=0; i<10000000; i++){

        /*  add i to timestamp to take care of sub-second function calls,
            3770168404(is a sample ip address in n/w byte order) =                84.52.184.224 */
        b63((long long)time(NULL)+i,x,b63((long long)3770168404,x,0));

        // reverse the char array to get proper base-63 output
        for(int j=0,k=9; j<10; j++,k--)
            y[j] = x[k];

        printf("%s\n",y);
    }

    return 0;
}
4

7 回答 7

5

它必须是“全球唯一（在生成 id 的机器之外）”和足够“本地唯一（在生成 id 的机器内）”，所有这些都需要打包成 10 个字符，唷！

您是否可以控制所有生成 id 的软件？你是在发身份证吗？如果不...

我对 SIP 一无所知，但是您对规范肯定有误解（或者规范一定是错误的）。如果另一位开发人员尝试使用与您编写的算法不同的算法来构建 id，您将与他们的 id 发生冲突，这意味着他们将知道在该系统中不再是全局唯一的。

我会回到 SIP 文档，看看是否有一个带有生成这些 id 的算法的附录。或者也许比我更聪明的 SO 用户可以回答生成这些 id 的 SIP 算法是什么。

于 2009-12-05T20:21:12.810 回答
2

我会认真看一下描述 128 位 GUID 生成的 RFC 4122。有几种不同的生成算法，其中一些可能适合（想到基于 MAC 地址的算法）。这是一个比你的 2^128 = 3.4 * 10^38 比 63^10 = 9.8 * 10^17 更大的数字空间，所以你可能不得不在唯一性上做出一些妥协。考虑生成 ID 的频率等因素。

然而在 RFC 中，他们考虑了一些实际问题，例如通过预先分配 ID 块来有效生成大量唯一值的能力。

于 2009-12-05T21:55:14.047 回答
1

你不能只有一个分布式 ID 表吗？

于 2009-12-05T20:20:03.093 回答
1

NAT'ed LAN 上的机器通常具有小范围的 IP，并且并非所有 32 位值都是有效的（想想多播等）。机器也可能会抓取相同的时间戳，尤其是在粒度较大（例如秒）的情况下；请记住，年份通常是相同的，因此较低的位会给您带来最大的“独特性”。

您可能想要获取各种值，使用加密散列对它们进行散列，并将其转换为您允许使用的字符，截断为 10 个字符。

但是您正在处理一个小于 60 位的值；您需要仔细考虑碰撞的影响。您可能以错误的方式处理问题...

于 2009-12-05T20:20:04.607 回答
1

好吧，如果我抛开我认为这是一个坏主意的事实，并专注于解决您的问题，这就是我要做的：

您的 id 范围为 10^63，大约对应 60 位。您希望它既“全局”又“本地”独特。让我们生成前 N 位是全局唯一的，其余的是本地唯一的。两者的串联将具有您正在寻找的属性。

首先，全球唯一性：IP 不起作用，尤其是本地的，它们的熵很小。我会使用 MAC 地址，它们是为全球唯一而设计的。它们覆盖的范围为 256^6，因此最多使用 6*8 = 48 位。

现在，对于本地唯一的：为什么不使用进程 ID？我假设唯一性是每个进程的，如果不是，你将不得不考虑别的东西。在 Linux 上，进程 ID 为 32 位。如果我们想挑剔，最重要的 2 个字节可能只有很少的熵，因为它们在大多数机器上都是 0。因此，如果您知道自己在做什么，请丢弃它们。

所以现在你会发现你有一个问题，因为它会使用多达 70 位来生成一个体面的（但不是防弹的）全局和本地唯一 ID（无论如何使用我的技术）。而且由于我还建议输入一个随机数（至少 8 位长）以防万一，它肯定不适合。因此，如果我是你，我会将生成的 ~78 位散列为 SHA1（例如），并将生成的散列的前 60 位转换为你的 ID 格式。为此，请注意您有 63 个字符范围可供选择，因此几乎是 6 位的全部范围。因此，将散列分成 6 位块，并使用前 10 块从 63 个字符范围中选择您 ID 的 10 个字符。显然，6 位的范围是 64 个可能的值（您只需要 63），所以如果您有一个等于 63 的 6 位块，要么将其设为 62，要么假设模 63 并选择 0。

因此，这应该可以为您提供一个体面的全球和本地伪唯一 ID。

最后几点：根据生日悖论，您将在生成约 1.42 亿个 ID 后获得约 1% 的碰撞几率，在生成 30 亿个 ID 后有 99% 的几率发生碰撞。因此，如果您取得了巨大的商业成功并生成了数百万个 ID，请获得更大的 ID。

最后，我认为我为您的问题提供了一个“比更差”的解决方案，但我不禁认为您以错误的方式解决了这个问题，并且可能正如其他人提到的那样，误读了规范。因此，如果没有其他更“防弹”的方法（集中式 ID 提供程序，更长的 ID ...），请使用此方法。

编辑：我重新阅读了你的问题，你说你可能每秒调用这个函数很多次。我假设这是用作某种应用程序 ID，在您的应用程序启动时生成一次，并且在退出之前从未更改过。由于不是这种情况，因此您绝对应该添加一个随机数，如果您生成大量 ID，请使其至少为 32 位数字。并阅读并重新阅读我在上面链接的生日悖论。并将您的数字生成器设置为高熵值，例如当前时间戳的 usec 值。甚至可以从 /dev/urandom 获取随机值。老实说，我对您的努力的看法是 60 位可能还不够……

于 2009-12-05T21:24:14.103 回答
0

@Doug T. 不，我无法控制所有生成 ID 的软件。我同意如果没有标准化算法，可能会发生冲突，我已经在相应的邮件列表中提出了这个问题。

@Florian 从你的回复中得到提示。我决定将 /dev/urandom PRNG 用于 32 位随机数作为 id 的空间唯一组件。我假设每台机器都有自己的噪声特征，并且可以假设它在瞬间在空间中是安全的全球唯一的。我之前使用的唯一时间组件保持不变。

生成这些唯一 ID 是为了整理从不同网络功能收集的所有计费信息，这些网络功能在呼叫处理期间独立生成特定呼叫的计费信息。

下面是更新后的代码：

高拉夫

 #include <stdio.h>
 #include <string.h>
 #include <time.h>

 //base-63 character set
 static char set[]="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-";

 // b63() returns the next vacant location in char array x
 int b63(long long longlong, char *x, int index){
     if(index > 9)
         return index+1;

     if(longlong < 63){
         x[index] = set[longlong];
         return index+1;
     }  

     x[index] = set[longlong%63];
     return b63(longlong/63, x, index+1);
 }

 int main(){
     unsigned int number;
     char x[11], y[11] = {0};

     FILE *urandom = fopen("/dev/urandom", "r");
     if(!urandom)
         return -1;

     //let's generate a 1 billion ids
     for(int i=0; i<1000000000; i++){

         fread(&number, 1, sizeof(number), urandom);

         // add i to timestamp to take care of sub-second function calls, 
         b63((long long)time(NULL)+i, x, b63((long long)number, x, 0));

         // reverse the char array to get proper base-63 output
         for(int j=0, k=9; j<10; j++, k--)
             y[j] = x[k];

         printf("%s\n", y);
     }

     if(urandom)
     fclose(urandom);

     return 0;
 }
于 2009-12-07T09:30:01.423 回答
0

嗯，使用系统时钟可能是一个弱点……如果有人把时钟调回来怎么办？您可能会再次重新生成相同的 ID。但是如果你打算使用时钟，你可以调用 gettimeofday() 而不是 time(); 至少这样你会得到比一秒更好的分辨率。

于 2009-12-05T20:21:41.383 回答