0

10 文字の一意の ID を生成する必要があります (SIP/VOIP 関係者は、それが P-Charging-Vector ヘッダーの param icid-value であることを知っておく必要があります)。各文字は、26 個の ASCII 文字 (大文字と小文字を区別) の 1 つ、10 桁の ASCII 数字の 1 つ、またはハイフンマイナスである必要があります。

それは「グローバルに一意 (ID を生成するマシンの外部)」であり、十分に「ローカルに一意 (ID を生成するマシン内)」でなければならず、すべてを 10 文字に詰め込む必要があります。

これが私の見解です。私は最初に「MUST」をグローバルに一意のローカル IP アドレスを base-63 (エンコード後に 1 ～ 6 文字を占める unsigned long int) にエンコードし、次に現在のタイムスタンプ (そのエンコードされた IP アドレスが最初に占めるスペースの量に応じて、エンコード後に 9 ～ 4 文字を占める time_t/long long int)。

また、関数が 1 秒間に複数回呼び出された場合に一意性を維持するために、ループ カウント '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

2

128 ビット GUID の生成について説明している RFC 4122 を真剣に検討します。いくつかの異なる生成アルゴリズムがあり、そのうちのいくつかは適合する可能性があります (MAC アドレスベースのアルゴリズムが思い浮かびます)。これは、63^10 = 9.8 * 10^17 と比較して、2^128 = 3.4 * 10^38 よりも大きな数値空間であるため、一意性について妥協する必要がある場合があります。ID が生成される頻度などの要因を考慮してください。

ただし、RFC では、ID のブロックを事前に割り当てることによって多数の一意の値を効率的に生成する機能など、いくつかの実際的な問題が考慮されています。

于 2009-12-05T21:55:14.047 に答える
1

さて、これは悪い考えだと思うという事実を脇に置いて、問題の解決策に集中するとしたら、次のようにします。

id の範囲は 10^63 で、これはおよそ 60 ビットに相当します。「グローバル」と「ローカル」の両方で一意にする必要があります。最初の N ビットを生成してグローバルに一意にし、残りをローカルに一意にします。2 つを連結すると、探しているプロパティが得られます。

まず、グローバルな一意性: 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 億 4,200 万個の ID を生成した後は 1% の確率で衝突が発生し、30 億個の ID を生成した後は 99% の確率で衝突が発生します。したがって、商業的に大きな成功を収め、何百万もの ID が生成されている場合は、より大きな ID を取得してください。

最後に、私はあなたの問題に対して「悪いよりも良い」解決策を提供したと思いますが、この問題を間違った方法で攻撃していると思わずにはいられません。したがって、より「防弾」となる方法が他にない場合は、これを使用してください (集中型 ID プロバイダー、はるかに長い ID ... )。

編集：あなたの質問を読み直しましたが、この関数をおそらく1秒間に何度も呼び出すと言います。これは、アプリケーションの開始時に一度生成され、終了するまで変更されない、ある種のアプリケーション ID として機能すると想定していました。そうではないので、必ず乱数を追加し、大量の ID を生成する場合は少なくとも 32 ビットの数値にする必要があります。そして、上でリンクした誕生日のパラドックスを読んで、もう一度読んでください。そして、たとえば現在のタイムスタンプの usec 値のように、数値ジェネレータを非常にエントロピーな値にシードします。または、 /dev/urandom からランダムな値を取得することさえできます。正直なところ、あなたの努力に対する私の見解は、60ビットではおそらく十分ではないということです...

于 2009-12-05T21:24:14.103 に答える
0

@Doug T.いいえ、IDを生成するすべてのソフトウェアを制御しているわけではありません。標準化されたアルゴリズムがないと、衝突が発生する可能性があることに同意します。この問題は、適切なメーリング リストで取り上げました。

@Florian返信からヒントを得ています。ID の空間固有コンポーネントとして、32 ビットの乱数に /dev/urandom PRNG を使用することにしました。すべてのマシンには独自のノイズ シグネチャがあり、特定の瞬間に空間内で安全にグローバルに一意であると想定できます。以前に使用したタイム ユニーク コンポーネントはそのままです。

これらの一意の 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 に答える