スノーフレークアルゴリズムの実装原理を理解する

前提

Snowflake は、Twitter のオープンソースの高性能 ID 生成アルゴリズム (サービス) です。

上の画像は、Snowflake の Github リポジトリです。マスターブランチの REAEMDE ファイルを見ると、最初のバージョンが 2010 年にリリースされたことがわかります。Apache Thrift をベースにしており、Finagle (ここでの Finagle は、Twitter の RPC サービス用の構築モジュール) よりも前のものです。Twitter が内部的に使用している Snowflake は、完全に書き直されたプログラムであり、実行には Twitter の既存のインフラストラクチャに大きく依存しています。

2010 年にリリースされた Snowflake ソースコードの最初のバージョンは Scala で記述され、scala_28 ブランチにアーカイブされました。つまり、現在誰もが使用しているスノーフレークアルゴリズムのオリジナル版または改良版は、10年前（現在2020年）の製品であり、このアルゴリズムは確かに非常に強力であると言わざるを得ません。アルゴリズムの動機と要件は scala_28 ブランチで紹介されており、以下に簡単な抜粋を示します。

モチベーション：

Cassandra には連続 ID を生成するツールがありません。Twitter が MySQL から Cassandra に切り替えたとき、ID を生成するための新しい方法が必要でした (アーキテクチャは設計されているのではなく、ビジネスシナリオに基づいて反復されていることを証明しています)。

必要とする：

高性能: 各プロセスは 1 秒あたり少なくとも 10K 個の ID を生成し、応答速度はネットワーク遅延を含めて 2 ミリ秒以内である必要があります。
連続性: 時間に応じて自己増加する傾向があり、直接並べ替えることができます。
コンパクト性: 生成される ID の長さを 64 ビット以下に抑えます。
高可用性: ID 生成ソリューションは、ストレージサービスと同様に高可用性である必要があります。
次に、Snowflakeのソースコードに基づいて、Snowflakeの実装原理を分析します。

スノーフレークソリューションの概要

Snowflake の初期の設計は次のとおりです。

時間: 長さ 41 ビット、ミリ秒の精度、カスタムエポックを使用すると、約 69 年になります。
設定可能なマシン ID: 長さ 10 ビット、1024 台のマシンに対応できます。
シーケンス番号: 長さは 12 ビットで、4096 個の数値からランダムに値を選択できるため、単一のマシンが 1 ミリ秒以内に重複するシーケンス番号を生成することを防ぎます。

ただし、実際のソースコードの実装では、Snowflake は 10 ビットの構成可能なマシン ID を 5 ビットのワーカー ID (元のマシン ID として理解できます) と 5 ビットのデータセンター ID (データセンター ID) に分割します。詳細については、IdWorker.scala を参照してください。

つまり、最大 32 個のマシン ID と最大 32 個のデータセンター ID の構成をサポートします。

このアルゴリズムは JVM に依存する言語である Scala で記述されているため、返される ID 値は Long 型、つまり 64 ビットの整数です。元のアルゴリズムでは、生成されたシーケンスで 63 ビットの長さのみが使用され、返される数値は符号なし数値であるため、上位ビットに 0 が追加され (1 ビットを占有)、ID の合計長は 64 ビットになります。

で：

41 ビットのミリ秒タイムスタンプの値の範囲は、[0, 2^41 - 1] => 0 ~ 2199023255551、合計 2199023255552 個の数値です。
5 ビットのマシン ID の値の範囲は、[0, 2^5 - 1] => 0 ~ 31、合計 32 桁です。
5 ビットのデータセンター ID の値の範囲は、[0, 2^5 - 1] => 0 ~ 31、合計 32 個の数字です。
12 ビットのシリアル番号の値の範囲は、[0, 2^12 - 1] => 0 ~ 4095 で、合計 4096 個の数値になります。

すると理論的には、2199023255552 * 32 * 32 * 4096 個の完全に異なる ID 値を生成できます。

Snowflake アルゴリズムには、システムクロックに依存するというもう 1 つの明らかな特徴があります。 41 ビットのミリ秒時間はシステムタイムスタンプから導出されるため、システム時間は前進する必要があり、クロックのロールバックは発生しません (一般的に、複数の同一のタイムスタンプを同時に生成したり、過去のタイムスタンプを生成したりすることはできません)。時計を戻すと、Snowflake は次の ID の生成を拒否します。

ビット演算の補足知識

スノーフレークアルゴリズムでは多くのビット操作が使用されます。整数の補数はコンピュータ内での格納形式であるため、Java や Scala における整数はすべて補数コードで表現されます。ここで、元のコードと補数コードに関する知識について簡単に触れておきます。

読み取りには元のコードを使用し、計算には補数コードを使用します。
正の数の補数は、元のコードと同じです。
負の数の補数は、最上位ビットを除くすべてのビットを反転し、1 を加算します (補数に 1 を加算)。負の数の補数も同様に元のコードに復元されます。
+0 の元のコードは 0000 0000 で、-0 の元のコードは 1000 0000 です。補数コードには 0 の値が 1 つだけあり、0000 0000 で表されます。これは非常に重要です。補数コードの 0 は明確です。

簡単に言えば、次のようになります。

 * [+ 11] 元のコード = [0000 1011] 補足コード = [0000 1011]
 * [- 11] 元のコード = [1000 1011] 補足コード = [1111 0101] 
 
 * [-11]の補数の計算手順:
        オリジナルコード 1000 1011
        最上位ビット1111 0100を除くすべてのビットを反転する
        1 1111 0101 を加える（補数）

元のコードや逆コードを使用して計算した場合に得られる値は必ずしも正確ではない可能性がありますが、補完コードを使用すると計算結果は正確になります。この結論だけを覚えておいてください。ここでは例は示しません。 Snowflake の ID 生成方式では、最上位ビットを除いて、他の 4 つの部分は符号なし整数であるため、整数の 4 つの部分に補数コードを使用したビット操作の効率が高くなり、この方法でのみ Snowflake の高性能設計の本来の意図を満たすことができます。 Snowflake アルゴリズムでは、XOR (^)、ビット AND (&)、ビット OR (|)、符号付き左シフト (<<) など、いくつかのビット演算が使用されます。

排他的論理和

XOR 演算規則は、0^0=0 0^1=1 1^0=1 1^1=0 です。つまり、ビットが異なる場合は結果は 1 になり、ビットが同じ場合は結果は 0 になります。主な機能は次のとおりです。

特定のビット反転、つまり、ある数値と N ビットがすべて 1 である数値に対して XOR 演算を実行すると、対応する N ビットが反転されます。たとえば、0100 と 1111 の場合、結果は 1011 になります。
0 との XOR を実行すると、結果は元の値と同じになります。
2 つの数値の値は相互作用します: a=a^bb=b^aa=a^b。これら 3 つの演算が完了すると、a と b の値が交換されます。

最後はこちらです:

 * [+ 11] 元のコード = [0000 1011] 補足コード = [0000 1011] a
 * [- 11] 元のコード = [1000 1011] 補完コード = [1111 0101] b 
 
 a=a^b 0000 1011
               1111 0101
 ---------^  
               1111 1110
 1111 0101 1111 0101 1111 0101 1111 0111 1 ...
 ---------^  
               0000 1011（10進数：11）b
 a=a^b 1111 1110
 ---------^  
               1111 0101 (10進数: -11) a

ビットAND

ビット単位の AND 演算規則は、0^0=0 0^1=0 1^0=0 1^1=1 です。対応するビットがすべて 1 の場合にのみ計算結果は 1 になり、それ以外の場合は計算結果は 0 になります。主な機能は次のとおりです。

ゼロにクリアします。数値をゼロにクリアしたい場合は、ビットが 0 であるすべての数値に対してビット単位の AND 演算を実行するだけです。
数値内の指定されたビットを取得するには、たとえば、X の下位 4 ビットを取得するには、zzzz...1111 とのビット単位の AND 演算を実行します。たとえば、1111 の下位 4 ビットを取得するには、0110、11110110 & 00001111 を実行すると、00000110 になります。

ビットOR

ビット単位の AND 演算規則は、0^0=0 0^1=1 1^0=1 1^1=1 です。いずれかのビットが 1 であれば、計算結果は 1 になります。計算結果が 0 になるのは、両方のビットが同時に 0 の場合のみです。主な機能は次のとおりです。

数値の一部のビットに 1 の値を割り当てるには、対応するビットがすべて 0 である数値とビット単位の OR 演算を実行するだけです。たとえば、1011 0000 の下位 4 ビットすべてに 1 を割り当てる場合、10110000 | 00001111 は 1011 1111 になります。

符号付き左シフト

符号付き左シフトの演算子は << であり、一般的な形式は M << n です。効果は以下のとおりです。

M の 2 進数 (補数) を n 桁左にシフトしたもの。
左側（高い位置）にシフトアウトされた部分はそのまま破棄され、右側（低い位置）にシフトインされた部分は 0 で埋められます。
シフト結果: M に 2 の n 乗を掛けた値に相当し、0、正の数、負の数に適用できます。
移動したビット数が型の最大ビット数を超える場合、コンパイラは移動したビット数の係数を取ります。たとえば、int が 33 ビットシフトされた場合、実際に移動するのは 33%2 = 1 ビットのみです。

演繹プロセスは次のようになります（n = 2 と仮定）。

 * [+ 11] 元のコード = [0000 1011] 補足コード = [0000 1011]
 * [- 11] 元のコード = [1000 1011] 補足コード = [1111 0101] 
 
 * [+ 11 << 2]の計算過程
      2の補数 0000 1011
      2ビット左シフト 0000 1011
      高いものをあきらめて、低いものを補う 0010 1100
      10進数 2^2 + 2^3 + 2^5 = 44 
 
 * [- 11 << 2]の計算過程
      2の補数 1111 0101
      2ビット左シフト 1111 0101
      高いものをあきらめて、低いものを補う 1101 0100
      元のコード 1010 1100 (補数コード: 最上位ビットを除くすべてのビットを反転し、1 を加算)
      10進数 - (2^2 + 2^3 + 2^5) = -44

これを検証するための main メソッドを記述できます。

公共 静的void main(String[] args) {
      システム.out.println (-11 << 2); // -44
      システム.out.println (11 << 2); // 44
 }

組み合わせテクニック

上記の 3 つのビット演算子を使用すると、それらを組み合わせることでいくつかの効率的な計算スキームを実現できます。

n ビットが表すことができる最大値を計算します。

Snowflake アルゴリズムには次のようなコードがあります。

 // マシンIDのビット長
プライベートvalworkerIdBits = 5L;
 // 最大マシン ID -> 31
プライベートval maxWorkerId = -1L ^ (-1L << workerIdBits);

ここでの演算子は -1L ^ (-1L << 5L) です。演算子を並べ替えると、64 ビットの 2 進数を使用した計算プロセスは次のようになります。

 * [-1] の２の補数 111111111 11111111 11111111 11111111 11111111 11111111 1111111
  5ビット左シフト 111111111 11111111 11111111 11111111 11111111 11100000
  [-1]の補数 11111111 11111111 11111111 11111111 11111111 11111111 1111111
  XOR ------------------------------------------------------------------- ^  
  結果の2の補数は00000000 000000000 000000000 000000000 00000000 00011111 (10進数 2^0 + 2^1 + 2^2 + 2^3 + 2^4 = 31) です。

このようにして、5 ビットで表現できる最大値 n を計算できます。ここで、n は整数であり、0 <= n <= 31、つまり 0、1、2、3...31 です。この組み合わせを使用して、ワーカー ID とデータセンター ID 部分の最大値が計算されます。

オーバーフローを回避するには、固定ビットの最大値をマスクとして使用します。

Snowflake アルゴリズムには次のようなコードがあります。

 varシーケンス= 0L
 ......
プライベートvalシーケンスビット = 12L
 //シーケンスの最大値は 4095 です。
プライベートvalシーケンスマスク = -1L ^ (-1L << シーケンスビット)
 ......
シーケンス= (シーケンス+ 1) & シーケンスマスク

最後の演算子は、実際にはシーケンス = (シーケンス + 1) & 4095 です。シーケンスの現在の値が 4095 であると仮定すると、計算プロセスは次のようになります。

 * [4095] の2の補数 00000000 000000000 000000000 00000000 00000000 00000111 11111111
  [シーケンス+ 1]の 2 の補数00000000 00000000 00000000 00000000 00000000 00001000 000000000
  ビットAND ---------------------------------------------------------------------------------- &  
  計算結果 00000000 00000000 00000000 000000000 00000000 00000000 00000000 （10進数：0）

これを検証するための main メソッドを記述できます。

公共 静的void main(String[] args) {
整数マスク = 4095;
    System.out.println (0 & マスク); // 0
    System.out.println (1 & マスク); // 1
    System.out.println (2 & マスク); // 2
    システム.out.println (4095 & mask); // 4095
    System.out.println (4096 & マスク); // 0
    System.out.println (4097 & マスク); // 1
 }

つまり、x = (x + 1) & (-1L ^ (-1L << N)) は、x の最終値が N を超えないことを保証できます。これは、ビット単位の AND の「指定されたビットを取得する」機能によるものです。

スノーフレークアルゴリズム実装ソースコード分析

Snowflake は Scala で書かれていますが、構文は Java に似ています。Java コードとして読み取ることができます。以下のコードを読むと、一部のログ記録とメトリックロジックがスキップされます。まずIdWorker.scalaのプロパティ値を見てみましょう。

 // ベース エポック値を定義します。この値は北京時間で 2010-11-04 09:42:54 です。これはおそらく、2010 年にコードの最初のバージョンが送信されたときに定義されたタイムスタンプです。
 val twepoch = 1288834974657L 
 
 // シーケンス番号を0に初期化する
varシーケンス= 0L //2.8以降ではこれをデフォルト付きのコンストラクタパラメータにする  0の
 
 // マシンIDの最大長は5です
プライベートvalworkerIdBits = 5L 
 
 // データセンターIDの最大長は5です
プライベート値データセンターIdBits = 5L 
 
 // マシンIDの最大値、10進数は31
プライベートval maxWorkerId = -1L ^ (-1L << workerIdBits) 
 
 // データセンター ID の最大値、10 進数は 31
プライベート val maxDatacenterId = -1L ^ (-1L << datacenterIdBits) 
 
 // シリアル番号の最大長は12です
プライベートvalシーケンスビット = 12L 
 
 // マシンIDを左にシフトする必要があるビット数は12です
プライベートvalworkerIdShift = シーケンスビット
 
 // データセンター ID を左にシフトする必要があるビット数 = 12 + 5
プライベート val datacenterIdShift = シーケンスビット + ワーカーIdビット
 
 // タイムスタンプを左にシフトする必要があるビット数 = 12 + 5 + 5
プライベート val timestampLeftShift = シーケンスビット + ワーカー ID ビット + データセンター ID ビット
 
 // シリアル番号マスク、10進数は4095
プライベートvalシーケンスマスク = -1L ^ (-1L << シーケンスビット) 
 
 // 最後のタイムスタンプのスナップショット値を -1 に初期化します
プライベート変数 lastTimestamp = -1L 
 
 // 次のコードブロックはパラメータ検証と初期化ログ出力用であり、ここでは分析しません
ワーカーID > 最大ワーカーID || ワーカーID < 0 の場合 {
例外カウンタ.incr(1)
 throw new IllegalArgumentException( "ワーカー ID は %d より大きく、0 より小さくすることはできません" .format(maxWorkerId))
 } 
 
データセンターID > 最大データセンターID || データセンターID < 0 の場合 {
例外カウンタ.incr(1)
新しい IllegalArgumentException をスローします ( "データセンター ID は %d より大きく、0 より小さくすることはできません" .format(maxDatacenterId))
 } 
 
 log.info( "ワーカーが開始しました。タイムスタンプ左シフト %d、データセンター ID ビット %d、ワーカー ID ビット %d、シーケンス ビット %d、ワーカー ID %d" 、
 timestampLeftShift、データセンターIdBits、ワーカーIdBits、シーケンスBits、ワーカーId)

次に、アルゴリズムのコアコードロジックを見てみましょう。

 // 同期メソッドは実際には protected synchronized long nextId(){ ...... }
保護された[スノーフレーク] def nextId(): Long = synchronized {
    // システムタイムスタンプ（ミリ秒）を取得します
    varタイムスタンプ= timeGen()
    // 同時実行性の高いシナリオでは、同じミリ秒内に複数の ID が生成されます
    最後のタイムスタンプ ==タイムスタンプの場合
        //シーケンス+ 1 がオーバーフローしないことを確認し、最大値は 4095 です。これにより、実際には 1 ミリ秒以内に最大 4096 個の ID 値が生成されることが保証されます。
シーケンス= (シーケンス+ 1) & シーケンスマスク
        //シーケンスがオーバーフローすると 0 になり、1 ミリ秒以内に同時に生成される ID の数が 4096 を超えることを示します。このとき、同じミリ秒内に生成される 4097 番目の ID は次のミリ秒まで待機する必要があります。
        シーケンス== 0 の場合
            // lastTimestamp より大きくなるまで次のミリ秒値を待つ無限ループ
タイムスタンプ= tilNextMillis(lastTimestamp)
        }
    }それ以外{
        // 同時実行性が低いシナリオでは、異なるミリ秒でIDを生成します
        // 異なるミリ秒の場合、外側のメソッドはタイムスタンプが lastTimestamp より大きいか小さいかを保証するため、lastTimestamp より小さい場合は時計が戻され、以下の例外がスローされるため、考慮しないでください。
        // つまり、考慮する必要があるのは 1 つの状況だけです: timestamp > lastTimestamp、つまり現在生成された ID のミリ秒が前の ID より大きい場合
        // タイムスタンプ部分が増えれば整数値も確実に増えると判断できるので、シーケンス番号を計算する必要はなく、ここでは直接0が割り当てられます
シーケンス= 0
    }
    // 取得したタイムスタンプは最後に保存したタイムスタンプよりも小さいため、時計が戻されていることを示しています。この場合、例外が直接スローされ、ID 生成は拒否されます。
    // 個人的には、このメソッドはコードvar timestamp = timeGen() の後に置くべきだと思います。
    if (タイムスタンプ< lastTimestamp) {
      例外カウンタ.incr(1)
      log.error( "時計が逆方向に進んでいます。%d までリクエストを拒否します。" , lastTimestamp);
      throw new InvalidSystemClock( "時計が逆方向に進みました。%d ミリ秒間 ID の生成を拒否しています" .format(lastTimestamp - timestamp ));
    }
    // lastTimestamp は、次回メソッドが呼び出されたときに、現在のタイムスタンプを前のタイムスタンプのスナップショットとして保存します。
    lastTimestamp =タイムスタンプ 
    // メトリック統計、生成されたIDカウンターは1ずつ増加します
    genCounter.incr()
    // X = (システムタイムスタンプ - カスタムエポック値)、次に 22 ビット左にシフトします
    // Y = (データセンター ID を 17 ビット左にシフト)
    // Z = (マシン ID を 12 ビット左にシフト)
    // 最終 ID = X | Y | Z | 計算されたシーケンス番号シーケンス 
    ((タイムスタンプ- twepoch) << timestampLeftShift) |
      (データセンター ID << データセンター ID シフト) |
      (ワーカーID << ワーカーIDシフト) |
順序 
 } 
 
 // 補助メソッド: 現在のシステムタイムスタンプ (ミリ秒) を取得します
保護された def timeGen(): Long = System.currentTimeMillis() 
 
 // 補助メソッド: システムの現在のタイムスタンプ (ミリ秒) を取得し、無限ループを使用して、渡された lastTimestamp よりも大きいことを確認します。つまり、lastTimestamp よりも大きい次のミリ秒を取得します。
保護された def tilNextMillis(lastTimestamp: Long): Long = {
    varタイムスタンプ= timeGen()
    while (タイムスタンプ<= lastTimestamp) {
タイムスタンプ= timeGen()
    }
タイムスタンプ 
 }

ロジックの最後の段落には多くのビット演算がありますが、ビット演算子の使用に精通していれば、ロジックは複雑ではありません。これを推測するための図を以下に示します。

整数の 4 つの部分が左にシフトされた後、空いている下位ビットは 0 で埋められます。ビット単位の OR の特性に基づいて、すべての下位ビットに 1 がある限り、対応するビットは 1 で埋められます。4 つの部分のビットは境界を越えて割り当てられないため、ここでの本質は、4 つの部分が左にシフトされた後、最終的な数字が追加されることです。

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

スノーフレークアルゴリズムにはいくつかの大きな問題があります。

同時実行性の低いシナリオでは、システムクロックが常に次のミリ秒値に移動し、シーケンス番号が 0 にリセットされるため、連続した偶数が生成されます。
システムクロックによっては、時計ダイヤルが新しい ID の生成を拒否します (直接例外をスローします)。
ワーカー ID とデータセンター ID の管理は非常に面倒です。特に、同じサービスの異なるクラスターノードの場合は、各ノードのワーカー ID とデータセンター ID の組み合わせが一意であることを確認する必要があります。

Meituan のオープンソース Leaf は、これら 3 つの問題に対するソリューションを提供します。次の図は、com.sankuai.inf.leaf.snowflake.SnowflakeIDGenImpl から抜粋したものです。

対応する解決策は次のとおりです (詳細なソースコード分析はありませんが、興味がある場合は、次の Leaf ソースコードを読むことができます)。

シーケンス番号生成にランダムソースを追加すると、同じミリ秒内に生成できる ID の最大数がわずかに減少します。
時計を戻すと、一定の待機期間が発生します。
Zookeeper を使用して、ワーカー ID とデータセンター ID をキャッシュして管理します。

ワーカー ID とデータセンター ID の構成は非常に重要です。同じサービス (決済サービスなど) クラスター内の複数のノードでは、異なるマシン ID とデータセンター ID、または同じデータセンター ID と異なるマシン ID を構成する必要があります (つまり、ワーカー ID とデータセンター ID の組み合わせがグローバルに一意であることを保証するため)。そうしないと、同時実行性の高いシナリオでシステムクロックが一貫している場合、複数のノードで同じ ID 値が生成されやすくなります。したがって、一般的な展開アーキテクチャは次のようになります。

これら 2 つの ID を管理する方法は多数あります。Leaf などのオープンソースフレームワークを使用して、分散キャッシュを導入して管理することができます。たとえば、私が勤務する小規模なスタートアップチームでは、運用サービスが比較的少ないため、サービス起動スクリプトに Worker ID と Data Center ID をハードコードし、すべてのサービスで使用される Worker ID と Data Center ID をチームの内部ナレッジベースに登録しています。

スノーフレークの簡易版を独自実装

パフォーマンスをまったく考慮せず、クロックロールバックやシリアル番号生成などの問題を考慮しない場合は、実際には Snowflake のすべてのビット操作と例外処理部分を削除し、Long.toBinaryString() メソッドを使用して、Snowflake アルゴリズムに従って文字列を結合して 64 ビットの 2 進数を抽出し、Long.parseLong() メソッドを介して Long 型に変換することができます。次のようにメインメソッドを記述します。

パブリッククラスMain { 
 
    プライベート静的最終文字列 HIGH = "0" ; 
 
    /**
     * 2020-08-01 00:00:00
     */
    プライベート静的最終長いEPOCH = 1596211200000L; 
 
公共 静的void main(String[] args) {
        長いワーカーID = 1L;
        長いデータセンターID = 1L;
        長いシーケンス = 4095;
        文字列 timestampString = leftPadding(Long.toBinaryString(System.currentTimeMillis() - EPOCH), 41);
        文字列workerIdString = leftPadding(Long.toBinaryString(workerId), 5);
        文字列 dataCenterIdString = leftPadding(Long.toBinaryString(dataCenterId), 5);
        文字列 seqString = leftPadding(Long.toBinaryString(seq), 12);
        文字列値 = HIGH + timestampString + workerIdString + dataCenterIdString + seqString;
        long num = Long.parseLong(値、2);
        System.out.println (num); // ある瞬間の出力は3125927076831231です
    } 
 
    プライベート静的文字列leftPadding(文字列値、 int maxLength) {
 int diff = maxLength - value.length();
        StringBuilder ビルダー = new StringBuilder();
 ( int i = 0; i < diff; i++) {
            ビルダー.append( "0" );
        }
        ビルダー.append(値);
 builder.toString()を返します。
    }
 }

次に、コードを標準化し、Snowflake アルゴリズム実装エンジニアリングコードの簡略化されたバージョンを記述します。

 // 主キージェネレーターインターフェース
パブリックインターフェースPrimaryKeyGenerator { 
 
    長い生成();
 } 
 
 // シンプルなスノーフレークの実装
パブリッククラスSimpleSnowflakeはPrimaryKeyGeneratorを実装します{ 
 
    プライベート静的最終文字列 HIGH = "0" ;
    プライベート静的最終long MAX_WORKER_ID = 31;
    プライベート静的最終long MIN_WORKER_ID = 0; 
 
    プライベート静的最終long MAX_DC_ID = 31;
    プライベート静的最終long MIN_DC_ID = 0; 
 
    プライベート静的最終long MAX_SEQUENCE = 4095; 
 
    /**
     * マシンID
     */
    プライベート最終長いワーカー ID; 
 
    /**
     * データセンターID
     */
    プライベート最終長いデータセンターId; 
 
    /**
     * ベースエポック値
     */
    プライベートファイナルロングエポック; 
 
    プライベートロングシーケンス= 0L;
    プライベートロングlastTimestamp = -1L; 
 
パブリックSimpleSnowflake(longワーカーID、longデータセンターID、longエポック) {
        this.workerId = ワーカーId;
        this.dataCenterId = データセンターId;
        エポック
        チェック引数();
    } 
 
    プライベートvoid checkArgs() {
        （！（MIN_WORKER_ID <= ワーカーID && ワーカーID <= MAX_WORKER_ID））の場合{
            throw new IllegalArgumentException( "ワーカーIDは[0,31]の範囲内である必要があります" );
        }
        if (!(MIN_DC_ID <= データセンターID && データセンターID <= MAX_DC_ID)) {
            throw new IllegalArgumentException( "データセンターIDは[0,31]の範囲内である必要があります" );
        }
    } 
 
    @オーバーライド
パブリック同期された長い生成() {
        長いタイムスタンプ= System.currentTimeMillis();
        // 時計を戻す
        if (タイムスタンプ< lastTimestamp) {
            新しい IllegalStateException をスローします ( "時計が逆方向に動きました" );
        }
        // 同じミリ秒内の同時実行
        最後のタイムスタンプ ==タイムスタンプの場合
シーケンス=シーケンス+ 1;
            シーケンス== MAX_SEQUENCE の場合
タイムスタンプ= untilNextMillis(lastTimestamp);
シーケンス= 0L;
            }
        }それ以外{
            // 次のミリ秒でシーケンスを 0 にリセットします
シーケンス= 0L;
        }
        lastTimestamp =タイムスタンプ;
        // 41桁のタイムスタンプ文字列。桁数が足りない場合は左側に「0」を入力してください 
        文字列 timestampString = leftPadding(Long.toBinaryString( timestamp - epoch), 41);
        // 5桁のマシンID文字列。数が足りない場合は、左側に「0」を追加します。  
        文字列workerIdString = leftPadding(Long.toBinaryString(workerId), 5);
        // 5桁のデータセンターID文字列。桁数が足りない場合は、左に「0」を追加します。  
        文字列 dataCenterIdString = leftPadding(Long.toBinaryString(dataCenterId), 5);
        // 12桁のシリアル番号文字列。数が足りない場合は、左側に「0」を追加します。  
        文字列 seqString = leftPadding(Long.toBinaryString(シーケンス), 12);
        文字列値 = HIGH + timestampString + workerIdString + dataCenterIdString + seqString;
 Long.parseLong(値、2)を返します。
    } 
 
    プライベートlong untilNextMillis(long lastTimestamp) {
        長いタイムスタンプ;
        する {
タイムスタンプ= System.currentTimeMillis();
        } while (タイムスタンプ<= lastTimestamp );
戻る タイムスタンプ;
    } 
 
    プライベート静的文字列leftPadding(文字列値、 int maxLength) {
 int diff = maxLength - value.length();
        StringBuilder ビルダー = new StringBuilder();
 ( int i = 0; i < diff; i++) {
            ビルダー.append( "0" );
        }
        ビルダー.append(値);
 builder.toString()を返します。
    } 
 
公共 静的void main(String[] args) {
        ロングエポック = LocalDateTime.of ( 1970, 1, 1, 0, 0, 0, 0)
                .toInstant(ZoneOffset.of ( " +8" )).toEpochMilli();
        PrimaryKeyGenerator ジェネレーター = new SimpleSnowflake(1L, 1L, epoch);
 ( int i = 0; i < 5; i++) {
            System.out.println (String.format( "%s によって生成された ID: %d" 、i + 1、generator.generate()));
        }
    }
 } 
 
 // ある瞬間の出力は次のようになります
最初に生成された ID: 6698247966366502912
 2 番目に生成された ID: 6698248027448152064
 3番目に生成されたID: 6698248032162549760
 4 番目に生成された ID: 6698248033076908032
 5番目に生成されたID: 6698248033827688448

文字列連結方式は実行効率が低いですが、可読性は高くなります。エンジニアリングされたコードは、インスタンス化時にワーカーIDやデータセンターIDなどの値を直接指定できます。また、このシンプルなSnowflake実装にはサードパーティのライブラリ依存関係がなく、コピー後すぐに実行できます。上記の方法では文字列の連結が使用されていますが、これは少し低レベルに思えます。実際、ビットごとの OR の最後の部分は完全に加算に変換できます。

パブリッククラスMain { 
     
    /**
     * 2020-08-01 00:00:00
     */
    プライベート静的最終長いEPOCH = 1596211200000L; 
 
公共 静的void main(String[] args) {
        長いワーカーID = 1L;
        長いデータセンターID = 1L;
        長いシーケンス = 4095;
        長いタイムスタンプDiff = System.currentTimeMillis() - EPOCH;
        long num = (long) (timestampDiff * Math.pow(2, 22)) + (long) (dataCenterId * Math.pow(2, 17)) + (long) (workerId * Math.pow(2, 12)) + seq;
        System.out.println (num); // ある瞬間の出力は3248473482862591です
    }
 }

これにより、アルゴリズム全体は単純に見えますが、指数演算と加算演算が含まれるため、効率は比較的低くなります。

まとめ

Snowflake アルゴリズムは、高性能を主な目標とするアルゴリズムです。この目標に基づいて、多数のビット操作を巧みに使用します。この記事では、Snowflake で使用されるビット操作と具体的なソースコードの実装を徹底的に分析しました。最終的に、Twitter の公式 Snowflake アルゴリズムソースコードに基づいて Java 実装バージョンが改訂され、前述の改善方法が適用され、同時実行性の低いシナリオで偶数しか生成されない問題が修正されました。これは、しばらく前から実稼働環境で使用されています。コードリポジトリは次のとおりです (コードはサードパーティのライブラリに依存せず、コピー後すぐに使用できます)。

Github: https://github.com/zjcscut/framework-mesh/tree/master/java-snowflake

<<: 「ドメイン外」テキストは不要、Microsoft: NLP はターゲットを絞った方法で事前トレーニングする必要がある

>>: AIが光子の時間を3D画像に変換し、時間の経過による世界を視覚化する