一意なID生成システムの設計：Snowflake、UUIDv7、ULIDの比較

注文サービスは長年、Postgres の BIGSERIAL キーを使ってきました。そこで orders テーブルを4つのシャードに分けると、各シャードのシーケンスが注文 10452 を発行し、サポートは1つの注文番号に2人の顧客が結びついていることに気づきます。あるいは、モバイルアプリがサーバーに到達する前にIDを必要とします。

IDを作る機械が複数になると、IDはもはや無料ではありません。選択肢は、サイズ、ソート順、ID ごとの調整、そして B-tree インデックスへの優しさのトレードオフです。この記事ではシーケンス、チケットサーバー、UUIDv4、UUIDv7、ULID、Snowflake型のIDを比較し、そのうえで Snowflake 型ジェネレーターを設計します。扱うのはビット配分、worker ID のリース、時計の飛び、衝突の計算です。

分散IDの要件

• 永久に一意であること。 シャード、リージョン、再起動をまたいでも。
• おおよそ時刻順であること。 WHERE id > ? によるページネーションや時刻順のインデックスが機能するためです。Twitter の初代 Snowflake は、マシン間でも1秒以内の順序を保証していました。
• コンパクトであること。 64 ビットなら BIGINT に収まります。128 ビットだとすべてのキーが2倍になります。
• IDごとの調整が不要であること。 Snowflake の目標は、1プロセスあたり毎秒 10,000 個以上のIDを、それぞれ 2 ms 以内に発行することでした。
• 公開しても安全であること。 意図した以上の情報を漏らしません。

IDを生成する6つの方法

データベースのシーケンスは、1つのデータベースがすべての行を書き込む間は適切ですが、複数のデータベースがIDの空間を共有すると破綻します。nextval はロールバックされないため欠番が生じ、PostgreSQL では 1 より大きい CACHE を指定すると、値は重複しないもののセッション間で順序が乱れます。連番の注文番号は、注文量も明らかにしてしまいます。

チケットサーバーはシーケンスを集中化します。Flickr の MySQL チケットサーバーは2台構成で、1台が奇数、もう1台が偶数を発行し、クライアントは交互に使いました。IDのブロックをリースすれば、URL 短縮サービスの設計のように、IDごとの呼び出しをなくせます。

UUIDv7、ULID、Snowflake はタイムスタンプを先頭に置くので、同時に作られたIDは並んでソートされます。64 ビットに収まるのは Snowflake だけで、その代償として worker ID とクロックへの依存が生じます。

Snowflake のビット配分

Twitter の 2010 年のリリースは、2010 年 11 月をエポックとしてこの配分を使ったため、IDは 2080 年 7 月に尽きます。Unix エポックから数えると 41 ビットは 2039 年 9 月に尽きるので、エポックはサービスの開始時期に近い日付にします。各インスタンスは最後のミリ秒とカウンターを保持します。

// Next is called with g.mu held.
func (g *Generator) Next() (int64, error) {
	if time.Now().After(g.leaseDeadline) {
		return 0, ErrLeaseLost // another instance may own this worker ID now
	}
	now := time.Now().UnixMilli()
	if now < g.lastMs {
		if g.lastMs-now > 5 {
			return 0, ErrClockMovedBack
		}
		now = g.waitUntil(g.lastMs) // small step back: wait it out
	}
	if now == g.lastMs {
		g.seq = (g.seq + 1) & 0xFFF // 12 bits
		if g.seq == 0 {             // 4,096 IDs used in this millisecond
			now = g.waitUntil(g.lastMs + 1)
		}
	} else {
		g.seq = 0
	}
	g.lastMs = now
	return (now-epochMs)<<22 | g.workerID<<12 | g.seq, nil
}

1つの worker は毎秒最大 410 万個のIDを発行できます。実際の限界はその周りの RPC なので、クライアントにはIDをバッチで取得させます。IDはエポックから約 25 日で 2^53 を超え、JavaScript の Number.MAX_SAFE_INTEGER を上回るため、X や Discord の API と同様に JSON の文字列として送ります。

この配分は予算です。Discord は時刻に 42 ビットを使い、ノードのビットを worker とプロセスに分けています。Instagram は 13 ビットのシャードIDを使い、各 PostgreSQL シャードの中でIDを生成しました。これはデータベースをシャーディングするときに役立ちます。Sonyflake は 10 ms 単位で数えて 174 年もたせ、インスタンスあたり 10 ms に 256 個のIDを発行します。

worker ID の割り当て

Snowflake に必要なのは、IDごとではなくプロセスごとの調整だけです。同じ worker ID を持つ稼働中のジェネレーターが2つあると、同じIDを発行しかねません。

1. 静的な設定。 各ホストに WORKER_ID を割り当てます。台数が固定のフリートには十分ですが、設定ファイルを1つコピーすると重複が生じます。
2. StatefulSet のオーディナル。 Kubernetes は StatefulSet の Pod に 0 から番号を振り、それぞれに apps.kubernetes.io/pod-index ラベルを付けます（v1.32 から stable）。これは downward API で渡せます。オーディナルが一意なのは、1つのクラスター内の1つの StatefulSet の中だけで、Pod を強制削除すると同じオーディナルの Pod が2つ残ることがあります。
3. etcd または ZooKeeper のリース。 起動時にインスタンスは、/idgen/workers/17 のような空いている最小のキーを、キーが存在しない場合にだけ成功するトランザクションで確保します。リースは 10 秒で、3 秒ごとに更新します。インスタンスが落ちると、キーは失効します。Twitter の 2010 年の Snowflake は ZooKeeper の ephemeral ノードを使い、時計がピアの平均から 10 秒以上ずれていると起動を拒否しました。

env:
  - name: WORKER_ID
    valueFrom:
      fieldRef:
        fieldPath: metadata.labels['apps.kubernetes.io/pod-index']

リースには2つのルールが必要です。1つ目は、最後に成功した keepalive が、付与された TTL からマージンを引いた時間より古くなったらIDの発行を止めることです。これで、一時停止したりネットワークから切り離されたりしたインスタンスは、別のインスタンスがそのIDを確保する前に止まります。2つ目は high-water mark を保存することです。数秒ごとに、時計より少し先のタイムスタンプを別のキーに保存し、それを超えるIDは発行せず、次の保持者には自分の時計がそれを超えるまで待たせます。etcd は Raft で両方の一貫性を保ちます。

時計が逆行したとき

NTP デーモンは通常、時計をわずかに速く、または遅く進める slew で補正しますが、大きなずれにはステップで対処します。ntpd は既定で 128 ms を超えるとステップし、chrony の既定の閏秒モードでは、挿入された閏秒のためにカーネルが時計を 1 秒戻します。chrony のドキュメントは、ステップを起動時だけに限ることを勧めています。

makestep 1.0 3      # step (if off by over 1 s) only in the first three updates
leapsecmode slew    # absorb a leap second by slewing, not by stepping back

すり抜けたステップに対しては、ルールを1つ選びます。

Twitter の初代は Fail でした。数ミリ秒待ってから、アラートを出して失敗させるのが無難な既定値です。逆行しない CLOCK_MONOTONIC で時間を測れば、稼働中のプロセスは守られます。再起動は high-water mark がカバーします。

UUIDv7 と B-tree インデックス

2024 年 5 月に公開された RFC 9562 は RFC 4122 に代わるもので、UUIDv7 を定義しました。構成は、ミリ秒単位の 48 ビット Unix タイムスタンプ、4 ビットのバージョン、2 ビットのバリアント、そして乱数用の 74 ビットです。ミリ秒内の厳密な順序が必要なときは、この 74 ビットをカウンターに使います。タイムスタンプは 10889 年まで持ちます。

RFC は、時刻順を持たない UUID はインデックスの局所性が悪く、B-tree への影響が劇的になりうると警告しています。PostgreSQL では、新しい v7 キーは最も右のリーフページに入り、そこでの分割はページを 90% の充填率、つまり B-tree の既定の fillfactor で残します。ランダムな v4 キーはどのページにも当たります。インデックス全体がワーキングセットになり、満杯のページが分割され、チェックポイントのたびに各ページへの最初の変更でページ全体が WAL に書かれます。MySQL の InnoDB は主キーをすべてのセカンダリインデックスにもコピーするので、16 バイトのキーはそれらすべてを大きくします。

PostgreSQL 18 は 2025 年 9 月に uuidv7() を追加しました。UUID は 36 文字のテキストではなく、16 バイトのバイナリで保存します。また v7 は作成時刻が分かってしまうため、RFC はIDがセキュリティ上の役割を持つ場面では v4 を推奨しています。

ULID

ULID の仕様も同じ形で、48 ビットのミリ秒タイムスタンプと 80 ビットの乱数からなります。I、L、O、U を除いた 26 文字の Crockford base32 テキストは、文字列としても正しくソートでき、URL でも読みやすい形式です。monotonic モードはミリ秒内で 1 ずつ加算するので、順序は保てますが、次の値が推測可能になります。ULID はコミュニティの仕様です。データベースのキーには、同等のことをネイティブサポートで実現できる UUIDv7 が適しています。

衝突の確率はどれくらいか

b ビットの乱数を持つ n 個のIDで、どこかで衝突する確率はおよそ n² / 2^(b+1) です。時刻プレフィックス付きのIDが衝突しうるのは同じミリ秒の中だけなので、重要なのは総数ではなくレートです。毎秒 100 万個のIDを1年間、均等に発行した場合を示します。

乱数方式は、小さく計算可能な確率で失敗します。Snowflake が失敗するのは運用上の問題があるときだけですが、そのときは確実に失敗します。どちらの方式でも、一意制約は残しておきます。

Snowflake 型IDジェネレーターの図

図の読み方は次のとおりです。

• クライアントは3つのインスタンスのいずれかで NextId() を呼びます。インスタンスは、最後のミリ秒と 12 ビットのカウンターを使ってメモリから返します。
• etcd は各 worker ID を 10 秒のリースで保持し、保存したタイムスタンプも持ちます。
• NTP は時計を近い値に保ちます（破線の辺）。chrony がステップするのは起動時だけです。
• Order サービスは Postgres に行を書き込み、増加するIDは最も右の B-tree ページに入ります。
• バーは 64 ビットを縮尺どおりに示します。Markdown ブロックには設定を並べています。

ID生成を分かりやすく描く

• ビット配分は縮尺どおりに描きます。 予算が一目で分かります。
• worker ID の出どころを、リースの TTL とともに示します。 重複はそこから始まります。
• クロックは依存先として描きます。 ジェネレーターの正しさは、クロックの正しさで決まります。
• 障害時のルールをキャンバスに書きます。 時計の逆行、リースの喪失、再起動です。システム設計図の例も、同じようにボックスの横に数値を添えています。

Archboard で作る

1. Google または GitHub でサインインし、ダイアグラムを作成します。
2. IDサービス用に基本パックのフレームを追加し、その中に C4 Model パックのアンバー色のコンテナノードを3つ置きます。id-gen-0 から id-gen-2 で、それぞれに worker ID を1つ割り当てます。
3. 左側に、Payment サービスと Order サービス用のコンテナノードを2つ追加し、その下にデータパックの Postgres ノードを置きます。
4. 右側に、etcd 用の紫色のコンテナ、NTP 用にネットワークパックの青いサーバー、そして設定を書いた基本パックの Markdown ブロックを追加します。
5. 接続します。両方のクライアントからフレームへ NextId()、Postgres へ INSERT、etcd へリース、NTP からは破線の時刻同期の辺です。
6. 下に、ビット配分用として基本パックの長方形の楕円ノードを4つ、1 : 41 : 10 : 12 のサイズで追加し、基本のテキストメモも少し添えます。

設計の Mermaid フローチャートは、Mermaid コンバーターで編集可能な最初の下書きになります。この例で使うダイアグラムノードは 14 個で、Free プランの範囲に収まります。

よくある質問

Snowflake ID とは何ですか？ タイムスタンプ、worker ID、ミリ秒ごとのシーケンスから作る 64 ビットのIDで、2010 年に Twitter が導入しました。ジェネレーター同士が通信せずに動作し、IDはおおよそ作成時刻順にソートされます。

UUIDv7 は ULID より優れていますか？ どちらも 48 ビットのミリ秒タイムスタンプと乱数ビットを持ちます。UUIDv7 は IETF の標準で、PostgreSQL 18 の uuidv7() のようにデータベースが対応しています。ULID はテキスト形式が短いのが特徴です。データベースのキーには UUIDv7 を選んでください。

主キーには UUIDv4 と UUIDv7 のどちらを使うべきですか？ ほとんどのテーブルでは UUIDv7 です。新しい値が古い値の後ろにソートされるので、挿入はインデックスの右端付近にとどまります。IDから作成時刻が分かってはいけない場合は UUIDv4 を使います。

Snowflake ジェネレーターは毎秒いくつのIDを生成できますか？ worker あたり 1 ミリ秒に 4,096 個、つまり毎秒約 410 万個で、1,024 個の worker 全体では 42 億個です。実際の限界は、通常はジェネレーターの周りのネットワーク呼び出しです。

時計が逆行するとどうなりますか？ ジェネレーターは、すでに使った可能性のあるミリ秒を再利用してはいけません。時計が追いつくまで失敗させるか、待つか、実時間より先に進む論理クロックを持つかを選べます。Twitter の初代は失敗させました。

無料で始める — 1 シート、クレジットカード不要。