分散ID生成

分散型 ID 生成方案#

内容来自

那些惊艳的算法们（四）—— 唯一 ID 生成器 snowflake

分散型 ID 生成器解决方案

高并发情况下分散型全局 ID

問題の説明#

単一システム（例えば MySQL インスタンス）では、ユニーク ID の生成は非常に簡単で、MySQL に備わっている自動増分 ID 機能を直接利用することができます。

しかし、複数のシャードが存在する分散システム（例えば、複数の MySQL インスタンスで構成されるクラスターでデータを挿入する場合）では、この問題は複雑になり、生成されるグローバルユニーク ID は以下の要件を満たす必要があります。

生成される ID がグローバルにユニークであることを保証する
将来的にデータが複数のシャード間で移動する際に、ID 生成方式に制約を受けないこと
生成される ID には時間情報を含めることが望ましく、例えば ID の最初の k ビットがタイムスタンプであると、ID の最初の k ビットのソートによってデータを時間順にソートできる
生成される ID は 64 ビットを超えないことが望ましい
ID 生成の速度に要件がある。例えば、高スループットのシナリオでは、毎秒数万の ID を生成する必要がある（Twitter の最新のピークは 143,199 ツイート / 秒、つまり 10 万 +/ 秒）
サービス全体に単一障害点がないことが望ましい

タイムスタンプ#

時間を使ってユニーク ID を生成することは、並行性が高いまたは分散環境では基本的に不可能で、統一された時間で生成された ID は重複し、グローバルユニークを満たさない。

データベースの自動増分を利用#

依然としてデータベースを利用して自動増分 ID を生成し、ユニーク性を保証します。しかし、注意が必要なのは、データベースの分割やテーブルの分割がない場合、固定数のデータベーステーブルを専用に使用して自動増分 ID を生成し、ビジネスとは無関係で、以降はテーブルを分割しないことです。
利点は実装が簡単で理解しやすいことです。不足点は ID 生成速度がデータベースの性能やデータベースへの接続ネットワークに影響されることです。

Redis の原子操作を利用#

データベースに依存せず、柔軟で便利で、性能はデータベースより優れています。
数字 ID は自然にソートされ、ページングやソートが必要な結果に非常に役立ちます。

注意:

Redis クラスターの場合、異なる増分ステップを設定する必要があります。
生成された ID が自動増分を超える場合、プレフィックス + 自動増分 + 有効期限を設定することができます。

UUID/GUID を利用#

基本概念#

UUID は、一台のマシン上で生成された数字で、同じ時空間にあるすべてのマシンに対してユニークであることを保証します。
UUID の構成要素：現在の日付と時間 + クロックシーケンス + ランダム数 + グローバルユニークな IEEE マシン識別番号

利点と欠点#

利点:

簡単で、コードが便利
ID 生成性能が非常に良く、基本的に性能問題はありません
グローバルユニークで、データ移行、システムデータの統合、またはデータベースの変更などの状況においても対応できます
欠点:
ソートがなく、トレンドの増加を保証できません
UUID は通常文字列で保存され、クエリの効率が比較的低いです
ストレージスペースが比較的大きく、膨大なデータベースの場合、ストレージ量の問題を考慮する必要があります。
長すぎて、128 ビットで、データベースの主キーとしては適していません。

Twitter Snowflake#

snowflake は Twitter がオープンソースの分散 ID 生成アルゴリズムで、結果は long 型の ID です。
その核心思想は：高位ランダム + ミリ秒数 + マシンコード（データセンター + マシン ID） + 10 桁のシーケンス番号

ID 生成プロセス#

10 ビットのマシン番号は、ID 割り当てワーカーが起動する際に、Zookeeper クラスターから取得します（すべてのワーカーが重複したマシン番号を持たないことを保証します）
41 ビットのタイムスタンプ：新しい ID を生成する必要があるたびに、現在のタイムスタンプを取得し、次の 2 つの状況でシーケンス番号を生成します：
1. 現在のタイムスタンプが前に生成された ID のタイムスタンプと同じ場合（同じミリ秒内）、前の ID のシーケンス番号 + 1 を新しいシーケンス番号（12 ビット）として使用します；このミリ秒内のすべての ID が使用された場合、次のミリ秒まで待機します（この待機中に新しい ID を割り当てることはできません）。
2. 現在のタイムスタンプが前の ID のタイムスタンプより大きい場合、初期シーケンス番号（12 ビット）をランダムに生成し、このミリ秒内の最初のシーケンス番号とします。全体のプロセスでは、ワーカーが起動する際に外部に依存することがあり（Zookeeper からワーカー番号を取得する必要があります）、その後は独立して動作でき、去中心化を実現しました。