分散式SnowFlaakeID(雪花ID)の原理と改善最適化

最近は分布の枠組みの構成要素と全体の設計の考え方を研究しています.すべての問題は分布の難しさに触れると幾何倍にもなります.最も一般的なIDの生成を含めても、単独の場合は、データベースの自己増加ID、UUIDを使用するのは簡単です.
しかし、分散型の環境下では、同じ業務展開の複数セット以降、IDが重複することを考慮する必要がある.データベースを使用すると、データベースがボトルネックになりやすく、UUIDを使用すると順序がなく、データベース統合はまたステップアップなどの問題が発生します.最後に、データベース(redisも使用可能)セグメントジェネレータとsnowFlaakeは、現在の分布ID生成器の主流となっている.
ほとんどのインターネット会社の分布ID生成器は、ネットワークサービスまたはクラスタであり、個々に配置されていることを知っています.他のアプリケーションは、ネットワークを介して分散されたグローバル一意IDを取得する.ネットワークサービスを利用する方法は、利点が明らかであり、集中管理が容易であり、ジェネレータの設計に問題がない限り、基本IDは全体の傾向が増加することを保証することができる.デメリットは、取得効率が著しく低下していることです.
また、弊社にとっては、プロジェクトの性質上、分布ID生成器を採用しておりますので、開発とオンライン展開及び後期の運行維持には、一定の迷惑がかかります.オンラインした後、プロジェクトの管理権は私達の手元にないので、分散ID生成器の安定性を確保するために、分布ID生成センターの戦略をできるだけ取らないようにします.そこで、私に残された選択はSnowFlaakeID(雪花ID)だけを残しました.
SnowFlaakeIDとは?
SnowFlaakeは、twitter社内の分散プロジェクトに採用されたID生成アルゴリズムであり、オープン後は国内の大手メーカーから好評を得ています.このようなアルゴリズムで生成されたIDは、SnowFlaakeIDといいます.
SnowFlaakeIDの最大の特性は天然脱中心化であり、タイムスタンプ、ワークマシン番号の二つの変数によって構成された後、SnowFlaakeアルゴリズムによって唯一のインクリメントIDが生成される.どのマシンでも、作業マシンの番号が違っていれば、生成されたIDが一意であり、全体の傾向が増加することが確認されます.
Snowflakeの構造は以下の通りです.

0 - 0000000000 0000000000 0000000000 0000000000 0 - 0000000000 - 000000000000

第一段1位は未使用で、永遠に0に固定します.
第二段41位はミリ秒時間(41位の長さは69年まで使用可能)
第三段10位はウォーカーIdである(10桁の長さは最大1024個のノードの展開をサポートする)
第3のセグメント12ビットはミリ秒以内のカウント(12ビットのカウント順番号は、各ノードがミリ秒ごとに4096個のID番号を生成することをサポートする)
1024の満期ノード(1つのノードが1つの展開サービスである)によって計算された場合、1ミリ秒当たりに生成できるID番号は1024＊4096＝4194304個であり、現在の大多数のトラフィック状況を満たすには十分である.
アルゴリズムの核心は以下の通りです.

 ((     -     ) << timestampLeftShift) 
        | (  ID << workerIdShift) 
        | sequence;

サービス時間とは、サービスの開発時間、すなわち最初の正式IDが生成される時間のことです.SnowFlaakeIDが最長で69年利用可能です.(41 bitしかないので、41 bitの最大値を大人に換算すると69年です.)したがって、サービス時間がオンライン時間に近いほど、アルゴリズムの利用時間は長くなります.ここでsequenceはインクリメントシーケンスであり、現在のタイムスタンプが前のIDとタイムスタンプが一致すると、sequenceは4096まで1ずつ増加します.
SnowFlaakeには何か問題がありますか?
SnowFlaakeはいいです.分布式、中心化、第三者依存はありません.しかし、完全ではありません.SnowFlaakeはタイムスタンプに強く依存していますので、時間の変動によってSnowFlakeのアルゴリズムにエラーが発生します.
クロックコール:最も一般的な問題は、クロックコールによるID重複問題であり、SnowFlaakeアルゴリズムには効果的な解決法はなく、例外をスローするだけである.クロックコールは、2つの場合①インスタンス停止→クロックコール→インスタンス再起動→計算ID②実行中→クロックコール→計算ID
手動構成:もう一つはワーカーId(マシンID)は配備が必要な時に手動で構成され、ワーカーIdは重複しません.いくつかの例は大丈夫です.一度インスタンスが一定のレベルに達したら、ワーカーIdを管理するのは複雑な作業になります.
どのように最適化しますか
クロックバックラッシュ改善回避
IDジェネレータが利用できなくなると、すべてのデータベース関連の新規サービスが利用できなくなり、影響が大きすぎるので、クロックコールの問題は解決しなければなりません.
時計のコールバックの原因は様々です.うるう秒リターンかもしれません.NTP同期かもしれません.サーバー時間の手動調整かもしれません.つまり時間が過去に戻りました.キャンセル時間の多少については、様々な戦略が可能です.通常は以下のようないくつかの案があります.

少量のサーバ展開IDジェネレータの例では、NTPサーバをオフにして、サーバを厳重に管理しています.この方式はコードレベルから解決する必要がなく、完全に人治されます.

は、キャンセル時間が切れた場合、うるう秒コールが1秒だけ戻ると、コードレベルで一定時間の間、IDジェネレータが一時停止したと判断して使用することができます.利用可能時間が数秒足りないが、通常のクロックを押すと、トラフィックは正常に戻ります.

if (refusedSeconds <= 5) {
    try {
    //        5ms，       
        wait(refusedSeconds << 1);//wait
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
    currentSecond = getCurrentSecond();
}else {//      
    //           
}

例の起動後、メモリ生成時間に変更します.これはbaiduのオープンソースのUidGeneratorに使用されるスキームです.起動後、時間がサーバから取得されなくなりますので、システム時間

の代わりに、サーバクロックがどのようにコールされてもSnowFlaakeの実行に影響がありません.以下のコードのlastSecond変数はAtomicLongタイプです.

 List uidList = uidProvider.provide(lastSecond.incrementAndGet());

以上の2、3は解決クロック → → IDの場合である. → → → IDの場合、インスタンスを介して起動するときは、使用したことのないウォーカーIdを採用しても良い.ワーカーIdと以前にIDを生成したウォーカーIdが一致しない限り、タイムスタンプが間違っていても、生成したIDは重複しない.UidGeneratorはこの方式を採用しているが、またこの方式に依存しなければならない.一つの記憶センターは、redis、mysql、zookeeperであれ、これまで使ってきたウォーカーIdを記憶していなければならないので、重複してはいけません.特に、分布式にId生成器を配置する場合は、一つの記憶センターを使って問題を解決するように注意してください.

UidGeneratorコードはGiに行くことができます.thubhttps://github.com/zer0Black/uid-generatorを参照してください
手動設定を自動にするにはどうすればいいですか?
実際には、本明細書のシナリオとクロックコールバックの第4のシナリオは一致しています.例を再起動するたびに、自動的にウォーカーIdを探して使用します.手動構成に依存しないです.そして、自動検索のウォーカーIdは重複しません.管理が便利です.
参考文献

UidGenerator文書

一気に9種類の分布IDの生成方式を言い出して、面接官は少し愚かになりました.

Leaf-美団コメント分布ID生成システム