分散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 ツイート /s、つまり 10 万 +/ 秒）
サービス全体に単一障害点がないことが望ましい

タイムスタンプ#

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

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

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

Redis の原子操作を利用#

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

注意:

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

UUID/GUID を利用#

基本概念#

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

長所と短所#

長所:

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

Twitter Snowflake#

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

ID 生成プロセス#

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