スノーフレークアルゴリズムを学ぶのに役立つ記事

[[419666]]

序文

みなさんこんにちは、パンパンです！

これまでは rand と srand を使用して疑似乱数を生成していました。疑似乱数のシーケンスは固定されています。今日は、真の乱数を生成する方法を学びます。

エントロピープール

/dev/urandom は乱数値を生成するために使用できます。/dev/urandom は Linux のエントロピープールです。いわゆるエントロピープールは、現在のシステムにおける環境ノイズであり、システムのカオスの度合いを表します。環境ノイズは、メモリ使用量、ファイル使用量、さまざまな種類のプロセスの数など、いくつかの側面で構成されます。

 #include <stdio.h>
 #include <fcntl.h> 
 
 intメイン()
 {
整数randNum = 0;
整数fd = 0; 
 
 ( int i=0;i<5;i++ )の場合
    {
      fd = open ( "/dev/urandom" 、 O_RDONLY);
読み取り(fd, ( char *)&randNum, sizeof( int ));
閉じる（fd）;
      printf( "randNumは%dです\n" , randNum);
    } 
 
 0を返します。
 }

操作結果:

 mapan@mapan-仮想マシン:~/c++$ ./a.out   
 randNumは94961710です
randNumは-523780773です
randNumは1542169420です
randNumは-1632410867です

毎回印刷される 5 つの乱数は異なるため、実際のところ、そのランダム性はそれほど高くありません。スノーフレークアルゴリズムによって生成される数字は非常にランダムであり、通常は分散システムで一意の ID を生成するために使用されます。

スノーフレークアルゴリズム

SnowFlake アルゴリズムによって生成される ID は、次の構造を持つ 64 ビットの整数です (各部分は「-」記号で区切られます)。

0 - 0000000000 00000000000 00000000000 0000000000 0 - 00000 - 00000 - 00000 - 0000000000

1 ビットの識別部分。Java では、long の最上位ビットが符号ビットであるため、正の数は 0、負の数は 1 です。通常、生成される ID は正の数であるため、0 になります。

41 ビットのタイムスタンプ部分はミリ秒単位です。通常、現在のタイムスタンプは保存されませんが、タイムスタンプの差 (現在の時刻 - 固定開始時刻) が保存されるため、生成された ID はより小さい値から開始できます。41 ビットのタイムスタンプは 69 年間使用できます (1L << 41) / (1000L 60 60 24 365) = 69 年。

10 ビットのノード部分では、Twitter は最初の 5 ビットをデータセンター識別子として使用し、最後の 5 ビットをマシン識別子として使用するため、1024 個のノードを展開できます。

12 ビットのシリアル番号部分は、同じミリ秒内に同じノードに対して 4096 個の ID を生成することをサポートします。

 /*
    スノーフレーク
 
    ID生成戦略
    41 ビットのミリ秒時間 + 10 ビットのマシン ID + 12 ビットのミリ秒内のシーケンス。
    0 41 51 64 + -----------+------+------+ |時間 |pc |inc | +-----------+------+------+  
    最初の 41 ビットはマイクロ秒単位のタイムスタンプです。
    次の 10 ビットは、事前に構成されたマシン ID です。
    最後の 12 ビットは累積カウンターです。
    マシン ID (10 ビット) は、最大 1024 台のマシンが同時に ID を生成できることを示し、シーケンス番号 (12 ビット) は、マシンが 1 ミリ秒で最大 4096 個の ID を生成できることも示します。
      ビットシフトが使用されるため、64 ビットのオペレーティング システムが必要であることに注意してください。そうでない場合、生成される ID が正しくなくなる可能性があります。
 */ 
 
 #include <stdio.h>
 #include <pthread.h>
 #include <unistd.h>
 #include <stdlib.h>
 #include <sched.h>
 #include <linux/unistd.h>
 #include <sys/syscall.h>
 #include <errno.h>
 #include <linux/types.h>
 #include<時間.h>
 #include <stdint.h>
 #include <sys/ time.h > 
 
構造体地球儀
{
グローバル_int :12;
    uint64_t 最後のスタンプ;
作業ID ;
整数シーケンスID;
 }; 
 
 void set_workid( intワークID);
 pid_t gettid(void);
 uint64_t get_curr_ms();
 uint64_t wait_next_ms(uint64_t lastStamp);
 int atomic_incr( int id );
 uint64_t ユニークIDを取得します。

 #include "スノーフレーク.h"   
 
構造体グローバルg_info; 
 
 #define sequenceMask (-1L ^ (-1L << 12L)) //L は long 型 4095 を示します
 
 void set_workid( int作業ID)
 {
 g_info.workid = 作業ID;
 } 
 
 pid_t gettid( void ) //スレッドIDを取得する
{
システムコール(__NR_gettid)を返します。
 } 
 
 uint64_t get_curr_ms() //ミリ秒を取得
{
  構造体timevaltime_now;
  gettimeofday(&time_now, NULL );
  uint64_t ms_time = time_now.tv_sec*1000+time_now.tv_usec/1000;
 ms_timeを返します。
 } 
 
 uint64_t wait_next_ms(uint64_t 最後のスタンプ)
 {
  uint64_t カーソル = 0;
  する {
    cur は、 get_curr_ms を返します。
  } while (cur <= lastStamp);
 curを返します。
 } 
 
 int atomic_incr( int id) // 累積
{
  __sync_add_and_fetch(&id, 1);
 IDを返します。
 } 
 
 uint64_t ユニークIDを取得する()
 {
  uint64_t ユニークID = 0;
  uint64_t nowtime = get_curr_ms(); //現在のミリ秒を取得
 
  uniqueId = nowtime << 22; //タイムスタンプ部分を入力します
 
  //0x3ff 1023、2進数は11 1111 1111に相当
  // 100 を 2 進数で表すと: 0000 0000 0000 0000 0000 0000 0110 0100
  //まずシフトを実行する
  uniqueId |= (g_info.workid & 0x3ff) << 12; //ノード部分を入力します
 
  (現在時刻 < g_info.last_stamp) の場合
  {
    perror( "エラー" );
    終了(-1);
  } 
 
  (現在時刻 == g_info.last_stamp) の場合
  {
    //4095 バイナリ 0000 1111 1111 1111 [long 型]
    g_info.seqid = atomic_incr(g_info.seqid) & シーケンスマスク;
    if (g_info.seqid == 0) //seqid=0 競合を防ぎ、時間を変更する
    {
      nowtime = wait_next_ms(g_info.last_stamp); //現在の時刻より大きい時刻を取得します 
    }
  }
それ以外 
  {
    g_info.seqid = 0;
  }
  g_info.last_stamp = 現在時刻; 
 
  uniqueId |= g_info.seqid; //シリアル番号部分を入力します
uniqueIdを返します。
 } 
 
 intメイン()
 {
  ワークIDを100に設定します。
整数i;
 (i=0;i<10;i++)の場合
  {
    uint64_t ユニーク = get_unique_id();
    printf( "pthread_id:%u, id [%llu]\n" ,gettid(),unquie);
  } 
 
戻る;
 }

操作結果:

 mapan@mapan-仮想マシン:~/c++$ ./a.out   
 pthread_id:4970、ID [6595660141600063488]
 pthread_id:4970、ID [6595660141600063489]
 pthread_id:4970、ID [6595660141600063490]
 pthread_id:4970、ID [6595660141600063491]
 pthread_id:4970、ID [6595660141600063492]