スノーフレークアルゴリズムでは、どのような状況で ID の競合が発生しますか?

[[423697]]

分散システムでは、グローバルに一意の ID が必要になるシナリオがいくつかあります。この場合、36 ビットの UUID を使用して ID の競合を防ぐことができます。ただし、UUID にはいくつかの欠点があります。まず、比較的長いです。また、UUID は一般に順序付けされていません。

場合によっては、より単純な ID を使用し、ID が時間順に生成されることを期待することがあります。

スノーフレークアルゴリズムとは何ですか?

スノーフレークは中国語で雪片を意味するため、スノーフレークアルゴリズムと呼ばれることもあります。これは、Twitter のオープンソースの分散 ID 生成アルゴリズムです。

Twitter スノーフレーク アルゴリズムは、タイムスタンプを含み、基本的に自動インクリメント プロパティを維持する 64 ビットの長い値を生成します。

SnowFlakeアルゴリズムの利点:

高性能と高可用性: 生成はデータベースに依存せず、完全にメモリ内で生成されます。

高スループット: 1秒間に数百万の自動増分IDを生成可能

ID自動増分：データベースに保存され、インデックス作成効率が高い

SnowFlake アルゴリズムの欠点:

システム時間との整合性に依存します。システム時間がコールバックまたは変更されると、ID の競合や重複が発生する可能性があります。

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

スノーフレーク構造は次の図に示されています。

4つのコンポーネントが含まれています

未使用: 1 ビット、最上位ビットは符号ビット、0 は正、1 は負、0 に固定

タイムスタンプ: 41 ビット、ミリ秒タイムスタンプ (41 ビットは 69 年間使用できます)

識別ビット: 5 ビットのデータセンター ID、5 ビットの作業マシン ID。2 つの識別ビットの組み合わせにより、最大 1024 個のノードの展開をサポートできます。

シーケンス番号: 12 ビットの増分シーケンス番号。ノードが数ミリ秒以内に重複を生成し、シーケンス番号が一意性を表すことを示します。12 ビットでは、1 ミリ秒あたり 4096 個の ID を生成できます。

シリアル番号を通じて 1 ミリ秒で 4096 個の固有 ID を生成できるため、1 秒間に 4096 * 1000 = 409w 個の ID を生成できます。

デフォルトのスノーフレーク アルゴリズムは 64 ビットですが、特定の長さを設定できます。より長く実行したい場合は、タイムスタンプの桁数を増やします。より多くのノードの展開をサポートする必要がある場合は、識別桁の長さを増やします。同時実行性が高い場合は、シーケンス番号の数を増やします。

要約: スノーフレークアルゴリズムは静的ではなく、システム内の特定のシナリオに応じてカスタマイズできます。

スノーフレークアルゴリズムの適用可能なシナリオ

スノーフレークアルゴリズムは順序付けされ、自己増分されるため、MySQLのB+ツリーインデックス構造の挿入パフォーマンスが高くなります。

したがって、日常のビジネスでの使用では、スノーフレーク アルゴリズムは、データベースの主キー ID やビジネス関連の主キーでよく使用されます。

スノーフレークアルゴリズムはID重複問題を引き起こす

仮定: 注文マイクロサービスはスノーフレークアルゴリズムを使用してIDを生成し、3つのノードを展開し、同じIDを持つ

この時点で、同時接続は 200 あり、3 つのノードに均等に分散されています。3 つのノードが同じミリ秒で同じシーケンス番号で ID を生成すると、重複した ID が生成されます。

上記の仮説シナリオを通じて、スノーフレーク アルゴリズムが ID 競合を生成するには特定の前提条件があることがわかります。

サービスはクラスターにデプロイされており、一部のマシンは同じ ID を持っています。

ビジネスにはある程度の同時実行性があります。同時実行性がなければ、重複の問題は発生しません。

IDを生成するタイミング: シリアル番号は同じミリ秒内で同じです

フラグビットの定義方法

識別ビットが重複しないことが保証される場合、スノーフレーク ID も重複しません。

上記の事例を通じて、ID 重複に必要な条件がわかります。サービス内でIDの重複を避けたい場合は、記事を識別位置から移動する必要があります。

まず、オープンソース フレームワークのスノーフレーク アルゴリズムを使用して識別ビットを定義する方法を見てみましょう。

Mybatis-Plus v3.4.2 スノーフレークアルゴリズム実装クラス Sequence は、2 つの構築方法を提供します。パラメータなしの構築では、dataCenterId と workerId が自動的に生成されます。パラメータ構築では、Sequence を作成するときに識別ビットを明示的に指定します。

Hutool v5.7.9はMybatis-PlusのdataCenterIdとworkerIdの生成スキームを参照し、デフォルトの実装を提供します。

シーケンス作成のデフォルトのパラメータなし構造と、dataCenterIdとworkerIdの生成方法を見てみましょう。

公共 静的long getDataCenterId(long maxDatacenterId) {
    ロングID = 1L;
    最終バイト[] mac = NetUtil.getLocalHardwareAddress();
    （ヌル！= mac）の場合{
        id = ((0x000000FF & (long) mac[mac.length - 2])
                | (0x0000FF00 & (((long) mac[mac.length - 1]) << 8))) >> 6;
        id = id % (maxDatacenterId + 1);
    } 
 
 IDを返します。
 }

入力パラメータ maxDatacenterId は固定値で、データセンター ID の最大値を表します。デフォルト値は 31 です。

なぜ最大値は 31 なのでしょうか? 5 ビットの 2 進数の最大値は 11111 で、これはちょうど 31 だからです。

dataCenterId を取得する場合、2 つの状況があります。1 つは、ネットワーク インターフェイスが空で、デフォルトで 1L が取得される場合です。もう 1 つは、ネットワーク インターフェイスが空でなく、Mac アドレスを通じて dataCenterId が取得される場合です。

dataCenterIdの値はMacアドレスに関連していることがわかります。

次にworkerIdを見てみましょう

公共 静的long getWorkerId(long datacenterId, long maxWorkerId) {
    最終的なStringBuilder mpid = 新しいStringBuilder();
    mpid.append(データセンターID);
    試す {
        mpid.append(RuntimeUtil.getPid());
    } catch (UtilException ignore) {
        //無視する 
    }
 (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1)を返します。
 }

入力パラメータ maxWorkderId も固定値であり、ワーカー マシン ID の最大値を表します (デフォルト値は 31)。datacenterId は上記の getDatacenterId メソッドから取得されます。

名前変数の値はPID@IPなので、名前を@で分割し、添え字0を取得してPIDを取得する必要があります。

MAC + PIDのハッシュコードから下位16ビットを取得し、計算を実行して、最終的にworkerIdを取得します。

識別ビットを割り当てる

Mybatis-Plusフラグは、MacアドレスとプロセスPIDに依存して取得されます。これは最小限に抑えることができますが、それでもわずかな可能性はあります。

識別ビットが重複しないように定義するにはどうすればよいでしょうか? 事前割り当てと動的割り当ての 2 つの解決策があります。

事前割り当て

アプリケーションがオンラインになる前に、現在サービス中のノードの数を数え、手動で識別を申請します。

このソリューションはコード開発を必要とせず、サービスノードが固定されている場合やプロジェクトが少ない場合に使用できますが、サービスノードの動的スケーラビリティの問題を解決することはできません。

動的割り当て

Redis、Zookeeper、MySQLなどのミドルウェアにフラグを保存しておくと、サービスの開始時にフラグが要求されます。要求後、フラグは次の利用可能なものに更新されます。

識別ビットを保存すると、スノーフレーク アルゴリズムの ID はサービス内で一意か、それともグローバルに一意かという疑問が生じます。

Redis を例にとると、サービス内で一意にしたい場合は、独自のプロジェクト内の Redis ノードを使用して識別ビットを保存できます。グローバルに一意にしたい場合は、スノーフレーク アルゴリズムを使用するすべてのアプリケーションで同じ Redis ノードを使用する必要があります。

2 つの唯一の違いは、異なるサービスが Redis を共有するかどうかです。グローバルな一意性が必要ない場合は、IDをサービス内で一意にすることが最善です。これにより、単一ポイントの問題を回避できます。

サービスノードの数が1024を超える場合は、追加の拡張が必要です。10ビットの識別ビットを拡張するか、オープンソースの分散IDフレームワークを選択できます。

動的割り当ての実装

Redisはハッシュ構造キーを格納します。このキーには、dataCenterIdとworkerIdという2つのキーと値のペアが含まれます。

アプリケーションの起動時に、Lua スクリプトを使用して Redis から識別ビットを取得します。 Luaスクリプト内でdataCenterIdとworkerIdの取得と増分が完了し、呼び出し後に利用可能なマーキング位置が返される。

具体的な Lua スクリプトのロジックは次のとおりです。

最初のサービス ノードが取得されたとき、Redis には snowflake_work_id_key のハッシュがない可能性があります。まずハッシュが存在するかどうかを確認する必要があります。存在しない場合は、ハッシュを初期化し、dataCenterId と workerId を 0 に初期化します。

ハッシュがすでに存在する場合は、dataCenterIdとworkerIdが最大値31に等しいかどうかを判断します。条件が満たされた場合は、dataCenterIdとworkerIdを0に初期化して返します。

dataCenterId と workerId の組み合わせの総数は 1024 です。割り当てる場合は、最初に workerId を割り当てます。

workerId != 31 かどうかを判断します。条件が true の場合は、workerId を増分して戻ります。workerId = 31 の場合は、dataCenterId を増分して、workerId を 0 に設定します。

dataCenterId と workerId は常に下方にプッシュされ、全体としてリングを形成します。 Lua スクリプトのアトミック性により、1024 ノード以下のスノーフレーク アルゴリズムの生成が繰り返されないことが保証されます。フラグが 1024 に等しい場合、ループは最初から続行されます。

オープンソースの分散IDフレームワーク

Leaf と Uid はどちらもスノーフレーク アルゴリズムを実装しています。Leaf はさらに、ID を生成するためのセグメント モードも提供します。

美団リーフ: https://github.com/Meituan-Dianping/Leaf

Baidu ユーザID: https://github.com/baidu/uid-generator

スノーフレーク アルゴリズムはほとんどのシナリオに対応できます。必要がない場合は、システムの複雑さを増すオープン ソース ソリューションを導入することはお勧めしません。

レビューの概要

この記事では、スノーフレーク アルゴリズムとは何か、スノーフレーク アルゴリズムによって生成される ID 競合の問題をどのように解決するかを読者が理解できるように、画像とテキストを使用しています。

スノー リング アルゴリズムによって生成される ID 競合問題に関して、この記事では、識別ビットを割り当てるという解決策を示しています。スノーフレーク アルゴリズムのコンポーネント識別ビットを割り当てることで、デフォルトの 1024 ノードでの ID 生成が一意になります。

スノーフレーク アルゴリズムをより深く理解するために、Hutool または Mybatis-Plus のスノーフレーク アルゴリズムの具体的な実装を確認することができます。

スノーフレーク アルゴリズムは万能薬ではなく、すべてのシナリオに適用できるわけではありません。 IDにグローバルな一意性が求められ、サービスノードの数が1024ノードを超える場合は、アルゴリズム自体の構成を変更するか、識別ビットを拡張するか、オープンソースソリューション（LEAF、UID）を選択することができます。