全球和本地唯一的10個字符的編號

Question

我需要生成一個10個字符的唯一編號（SIP/VOIP人們需要知道它是用於P-Charging-Vector標題中的參數icid值）。每個字符應該是26個ASCII字母之一（區分大小寫），10個ASCII字符之一或連字符減號。

它必須是「全球唯一的（產生id的機器之外的）'並且足夠'本地唯一的（在產生id的機器內）'，並且所有需要被打包成10個字符，phew！

這是我的承擔。我首先編碼'必須'被編碼爲全局唯一的本地IP地址到base-63（它是一個無符號的long int，它將在編碼後佔用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[]="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-"; 

// 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; 
} 

Answer 1

你就不能有一個分佈式的ID表？

Answer 2

NAT在局域網上的機器通常會有一個小範圍的IP，並不是所有的32位值都是有效的（比如多播等）。機器也可以獲取相同的時間戳，尤其是粒度較大時（如秒）;請記住，今年經常會是一樣的，所以它的低位會給你最多的「獨特性」。

您可能希望採用各種值，使用加密哈希對它們進行哈希處理，然後將其轉換爲允許使用的字符，截斷爲10個字符。

但是你正在處理一個小於60位的值;你需要仔細考慮碰撞的影響。你可能會接近問題的錯誤的方式...

Answer 3

它必須是「全球唯一的（外機產生的ID ）」和 足夠的「本地唯一（內 機器生成的ID） '，並且 所有需要打包成10 的字符，phew！

您是否控制了所有軟件生成ID？你是否在出示ID？如果沒有...

我對SIP一竅不通，但是對規格（或規格必須錯誤）有誤解。如果另一個開發人員嘗試使用與您熟悉的算法不同的算法來構建一個id，那麼您將與他們的id發生衝突，這意味着他們將在該系統中具有更長的全局唯一性。

我會回到SIP文檔，看看是否有附錄中的算法來生成這些ID。或者，也許一個聰明的SO用戶比我可以回答用於生成這些ID的SIP算法是什麼。

Answer 4

嗯，使用系統時鐘可能是一個弱點...如果有人設置時鐘呢？您可能會再次生成相同的ID。但是如果你打算使用時鐘，你可以調用gettimeofday（）而不是time（）;至少這樣你會得到比一秒更好的分辨率。

Answer 5

好吧，如果我唾棄的事實，我認爲這是一個壞主意，集中精力解決您的問題，這裏就是我會做：

你有10^63的編號範圍，這對應於大約60位。你希望它既是「全球」又是「本地」的獨特。讓我們生成前N位爲全局唯一，其餘爲局部唯一。兩者的連接將具有您正在查找的屬性。首先，全球唯一性：IP不會工作，尤其是本地的，他們擁有的熵很小。我會去MAC地址，他們被認爲是全球獨一無二的。它們覆蓋256^6的範圍，因此使用了6 * 8 = 48位。

現在，對於本地唯一：爲什麼不使用進程ID？我假設唯一性是每個過程，如果不是，你必須考慮其他的東西。在Linux上，進程ID是32位。如果我們想要挑選，那麼最重要的兩個字節可能只有很少的熵，因爲它們在大多數機器上都是0。所以如果你知道你在做什麼，就放棄它們。

所以現在你會看到你有一個問題，因爲它會使用多達70位來生成一個體面的（但不是防彈的）全局和本地唯一ID（無論如何使用我的技術）。而且由於我還建議放入一個隨機數（至少8位長）以防萬一，它絕對不適合。所以，如果我是你，我會將生成的〜78位散列到SHA1（例如），並將結果散列的前60位轉換爲你的ID格式。要做到這一點，請注意，您有63個字符範圍可供選擇，因此差不多有6位的全部範圍。因此，將散列分成6個部分，並使用前10個部分從63個字符範圍中選擇您的ID的10個字符。很明顯，6位的範圍是64個可能的值（你只需要63），所以如果你有一個6位的塊等於63，或者將其設置爲62或者假設爲63並且選擇0.它將稍微偏向分佈，但它不是太糟糕。

那麼，那應該讓你有一個像樣的全球和本地僞唯一ID。

最後幾點：根據Birthday paradox，在生成大約1.42億個ID後，您將有大約1％的碰撞機率，並且在生成30億個ID之後有99％的機會。因此，如果您取得了巨大的商業成功，並且生成了數百萬個ID，則可以獲得更大的ID。最後，我想我提供了一個「更好更糟糕」的解決方案來解決你的問題，但我不禁想到你用錯誤的方式攻擊這個問題，也可能像其他人提到的那樣，誤讀了眼鏡。因此，如果沒有其他更「防彈」的方式（集中式ID提供者，更長的ID ......），請使用此方法。

編輯：我重新讀你的問題，你說你可能多次調用這個函數。我假設這是作爲某種應用程序ID，在您的應用程序開始時生成一次，之後從未更改，直到它退出。由於情況並非如此，您應該添加一個隨機數，並且如果您生成很多ID，請至少使用32位數字。並閱讀並重讀與上面鏈接的生日悖論。並將您的數字生成器設置爲高度熵值，例如當前時間戳的usec值。甚至可以從/ dev/urandom中獲取隨機值。 非常誠實地說，我認爲你的努力是60位可能是不夠的...

Answer 6

我會仔細看看RFC 4122，它描述了128位GUID的生成。有幾種不同的生成算法，其中一些可能適合（基於MAC地址的一個思路）。與63^10 = 9.8 * 10^17相比，這是一個比您的2^128 = 3.4 * 10^38更大的數字空間，所以您可能必須對唯一性做出一些妥協。考慮諸如ID生成頻率的因素。

但是在RFC中，他們已經考慮了一些實際問題，比如通過預分配ID塊來有效生成大量唯一值的能力。

Answer 7

@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[]="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-"; 

// 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; 
}