スノーフレークID生成器 - ユニークな分散IDを作成

Snowflake IDジェネレーターとは？

Snowflake IDジェネレーターは、タイムスタンプ、マシン識別子、シーケンス番号から一意な64ビット整数を生成します。この形式は2010年にTwitterが作成しました。多数のサーバーが同時に各ツイートの識別子を生成でき、互いに「この番号はもう使われているか」と確認する必要がないようにするためです。このツールは入力値から1つのSnowflake IDを生成し、それらの値が64ビットをどのように埋めるかを示します。

このSnowflake IDジェネレーターの仕組み

ジェネレーターは4つの入力値を受け取ります。

• タイムスタンプ：ミリ秒単位のUnixタイムスタンプ。空欄にすると現在時刻が使われます。
• マシンID：0から31までの整数（5ビット）。これはTwitterが最初に用いた「ワーカーID」です。
• データセンターID：0から31までの整数（5ビット）。
• シーケンス番号：0から4095までの整数（12ビット）。同じミリ秒に生成されたIDを区別するために使われます。

このツールは4つの値を1つの64ビットIDに結合します。次に、結果を二進数で表示し、タイムスタンプ、データセンター、マシン、シーケンスの各部分に分割します。

タイムスタンプは、Twitterエポックと呼ばれる固定の開始点、すなわち2010年11月4日、1:42:54.657 UTCからの経過時間で表されます。これはUnixエポックから1,288,834,974,657ミリ秒後に当たります。このジェネレーターでは、その開始点を変更できません。生成されるすべてのIDは、この1つの固定日付を基準に計算されます。

Snowflake IDの構造

Snowflake IDは4つの部分に分割された64ビット整数で、最上位ビットから順に読み取ります。

先頭ビットは常に0なので、Snowflake IDは常に正の数です。41ビットのタイムスタンプフィールドと12ビットのシーケンスフィールドが、Snowflake IDを並べ替えに適したものにする2つの部分です。後に作られたIDほどタイムスタンプ部分の値が大きいため、先に作られたIDの後に並びます。

Snowflake IDの計算式

ジェネレーターは次の式でIDを生成します。

$d = t - 1288834974657$

$I = (d << 22) \mathbin{|} (c << 17) \mathbin{|} (m << 12) \mathbin{|} s$

ここで、dは差分、tは入力されたミリ秒単位のタイムスタンプ、Iは完成したID、cはデータセンターID、mはマシンID、sはシーケンス番号です。

<<は左ビットシフトです。数値を22ビット左にシフトすることは、2²²、つまり4,194,304を掛けることと同じです。シフト量（22、17、12）は各フィールドの幅から直接決まります。シーケンスフィールドの幅は12ビットなので、マシンIDは12ビット上に配置されます。マシンフィールドの幅は5ビットなので、データセンターIDは17ビット上に配置されます（12 + 5）。以下も同様です。

Snowflake IDの計算方法：計算例

たとえば、次の値を入力したとします。

• タイムスタンプ：1,288,834,975,657（Twitterエポックからちょうど1,000ミリ秒後）
• データセンターID：1
• マシンID：1
• シーケンス番号：0

手順1 — 差分を求める。 タイムスタンプからエポックを引きます。1,288,834,975,657 − 1,288,834,974,657 = 1,000。

手順2 — 各フィールドを所定の位置にシフトする。

• タイムスタンプ：1,000 << 22 = 4,194,304,000
• データセンターID：1 << 17 = 131,072
• マシンID：1 << 12 = 4,096
• シーケンス：0

手順3 — ビット単位のORで結合する。 シフトしたフィールドは重ならないため、加算してもOR演算しても結果は同じです。

4,194,304,000 + 131,072 + 4,096 + 0 = 4,194,439,168

これがこの入力値に対するSnowflake IDです。ツールの結果表示では、同じ64ビットの二進文字列を、41ビットのタイムスタンプブロック、5ビットのデータセンターブロック、5ビットのマシンブロック、12ビットのシーケンスブロックに分割して再表示します。そのため、数値の構成が確認できます。

Snowflake IDの用途

Twitterは、多数のデータベースマシンにまたがるツイートに対して、中央カウンターをすべてのサーバーが確認しなくても、一意でおおむね時系列に並ぶIDを割り当てるためにこの形式を作りました。後にDiscordやInstagramも、メッセージや投稿向けに同様の64ビットID設計を採用しました。同じ考え方は、データベースのシャーディング、ECシステムの注文ID、分散アプリケーションのイベントログにも見られます。多数のマシンが独立してIDを発行しながら、おおむね時刻順に並べる必要がある環境に適しています。

Snowflake IDの制限

本番環境のSnowflakeジェネレーターは通常、独自の稼働クロックを保持します。同じミリ秒に生成するIDごとにシーケンス番号を増やし、シーケンスが4,095に達すると次のミリ秒まで待機します。このツールは計算間で状態を保持しません。入力された値から1つのIDを生成するため、形式の検証には便利ですが、稼働中の本番サービスとは異なります。

この設計には、実装するサービスにかかわらず、次の固定された制限があります。

• 固定エポック：このジェネレーターが受け付けるのは2010年11月4日（Twitterエポック）以降のタイムスタンプだけです。それより前の日付はエンコードできません。
• タイムスタンプの上限：41ビットのタイムスタンプフィールドは、2080年七月ごろに上限に達します。その後は、エポックからの差分が41ビットに収まりません。
• シーケンスの上限：同じミリ秒に1台のマシンが発行できる異なるIDは4,096個（0–4095）だけで、それを超えると値が繰り返されます。
• マシン空間：マシンIDとデータセンターIDにそれぞれ5ビットを使うため、1つの展開で衝突なく割り当てられる異なるマシン識別子は1,024個です（32 × 32）。
• ローカルな順序であり、グローバルな順序ではない：IDが互いに正しく並ぶのは、同期されたクロックを持つマシンから生成された場合だけです。マシン間のクロックのずれによって、厳密な時系列順が崩れることがあります。

Snowflake IDの歴史

Twitterは2010年、単純な自動増分データベースIDに代わるものとしてSnowflake ID形式を発表しました。自動増分IDは、多数の独立したデータベースサーバーにまたがる規模には対応できません。この名前は、実際の雪の結晶と同じように、生成されたIDに同一のものが2つないという発想に由来します。その後、この設計はオープンソース化され、多数のマシンが同時に生成する一意で並べ替え可能なIDを必要とする他の大規模プラットフォームにも、変更を加えた形で採用されました。

よくある質問

Snowflake IDとは何ですか？ Snowflake IDは、タイムスタンプ、マシン識別子、シーケンス番号で構成される64ビットの数値で、多数のマシンが互いに調整せずに一意なIDを生成できるよう設計されています。

Snowflake IDの計算式は何ですか？ id = ((timestamp − epoch) << 22) | (dataCenterId << 17) | (machineId << 12) | sequenceです。ここでエポックは固定された開始日であり、<<は左ビットシフトを表します。

このジェネレーターでエポックを変更できますか？ いいえ。このツールは常に固定されたTwitterエポック、2010年11月4日からタイムスタンプを計算します。別の開始日を設定する項目はありません。

このツールは既存のSnowflake IDをデコードしますか？ いいえ。入力されたタイムスタンプ、マシンID、データセンターID、シーケンス番号から新しいIDを生成し、その新しいIDのビット構成を表示するだけです。

1台のマシンが1ミリ秒に生成できるSnowflake IDの数はいくつですか？ 最大4,096個です。シーケンスフィールドの幅が12ビットで、値は0から4,095までだからです。

このジェネレーターは何年まで有効なタイムスタンプを生成できますか？ 2080年七月ごろまでです。41ビットのタイムスタンプフィールドが保持できるのは、固定された2010年のエポックから測って最大約69.7年で、その後はフィールドがオーバーフローします。

参考文献

1. 「Snowflakeの発表」Twitter Engineering Blog、2010年。
2. "Snowflake ID." Wikipedia、https://en.wikipedia.org/wiki/Snowflake_ID