ID Generation
実装:
id-generation// 実行:go test ./id-generation/
この章で作るもの
分散環境で「調整なしに」一意なIDを発番する4方式を、外部ライブラリなしで実装する。
- UUIDv4 — 全部乱数
- UUIDv7 — 時刻 + 乱数(2024年に標準化された新しい既定)
- ULID — 中身は v7 とほぼ同じ、表現が人間向き
- Snowflake — 時刻 + ノードID + 連番、乱数なしの64bit
この章の肝は3つ。
- どの方式も材料は「時刻・乱数・ノードID」の3つで、配合が違うだけ
- 時刻を上位ビットに置くと辞書順=時刻順になり、DBのインデックスに優しくなる
- 衝突を乱数で「確率的に無視」するか(UUID系)、ノードID+連番で「構造的に排除」するか (Snowflake)。後者は時計の巻き戻りが敵になる
問題設定: 採番テーブルに聞きに行きたくない
一意なIDを作る一番素朴な方法は、DBの連番(AUTO_INCREMENT)に聞くこと。 これは単一DBなら完璧だが、サーバーが増えると「発番のために毎回中央に問い合わせる」 ボトルネックと単一障害点になる。
そこで「各サーバーが誰にも聞かずにその場で発番して、それでも衝突しない」方式が欲しくなる。 以降の4方式はすべてこの問題への答えで、違いは材料の配合だけ。先に全体を1枚で見ておく:
時刻ノードID連番乱数
1. UUIDv4: 全部乱数
// NewUUIDv4 は128bit中122bitが純粋な乱数のUUIDを返す。時刻もノードIDも使わない。
// rand には crypto/rand.Reader を渡す(テストでは固定バイト列を注入する)。
func NewUUIDv4(rand io.Reader) (string, error) {
var b [16]byte
if _, err := io.ReadFull(rand, b[:]); err != nil {
return "", fmt.Errorf("idgen: read random: %w", err)
}
b[6] = (b[6] & 0x0f) | 0x40 // version 4
b[8] = (b[8] & 0x3f) | 0x80 // variant 10
return formatUUID(b), nil
}コードの読みどころ: version と variant の「刻印」
UUID は「ただの乱数128bit」ではなく、規格が ID自身に「どの方式で作ったか」を 埋め込む場所を予約している。6バイト目の上位4bitが version、8バイト目の上位2bitが variant。乱数で16バイト埋めた後、この2箇所だけ規格の値で刻印し直すのが b[6] と b[8] の2行で、& マスク が消しゴム、| 値 がはんこの役割になっている:
0x0f = 0000 1111 ← 下位4bitだけ残すマスク
0x40 = 0100 0000 ← 上位4bitに 0100(=4) を書き込む値
b[6] = 1111 1111 (乱数がたまたま全部1だったとする)
b[6] & 0x0f = 0000 1111 (AND: 上位4bitをゼロにして場所を空ける)
| 0x40 = 0100 1111 (OR: 空けた場所に version「4」を刻印)
b[8] & 0x3f | 0x80 = 10xx xxxx (同じ要領で variant「10」を刻印)この刻印は16進表記にそのまま現れる。テストの期待値 ffffffff-ffff-4fff-bfff-ffffffffffff を見ると、3グループ目が必ず 4 で始まり、 4グループ目が 8/9/a/b のどれかで始まる(10xx は16進で 8,9,a,b の4通り)。 手元にある UUID をどれか眺めると、必ずこの形をしているはず。 後述の UUIDv7 の | 0x70 も、同じはんこの「7」版。
128bit のうち version と variant の6bitを除いた122bitが純粋な乱数。 衝突確率は誕生日のパラドックスで見積もれて、50%衝突に達するのはおよそ 2^61 ≒ 230京個生成したとき。毎秒10億個発番しても73年かかる。「確率的に無視」で実用上十分。
メリット
- 何の調整も状態も要らない。時刻もノードIDも不要で、実装が最も単純
- IDから生成時刻や発番元が漏れない(推測不能性が欲しい場面ではこれが長所になる)
デメリット
- 完全にランダムなので、B-Tree インデックスへの挿入位置が毎回バラバラになる。 主キーにすると、挿入のたびに違うページを触ってキャッシュが効かず、断片化も進む (後述)
- IDを見ても時刻順に並べられない
実例
- PostgreSQL の
gen_random_uuid()、各言語の標準ライブラリ。事実上どこにでもある
試してみる: 何個生成しても、生成順と辞書順は一致しない(たまたま一致したら引き直してほしい)。
2. UUIDv7: 時刻 + 乱数
v4 の「インデックスに優しくない」問題への答えが UUIDv7(RFC 9562、2024年)。 先頭48bitをミリ秒タイムスタンプにして、残りを乱数にする。
// NewUUIDv7 は先頭48bitにミリ秒タイムスタンプを置くUUIDを返す(RFC 9562)。
// 生成時刻順に文字列比較でもソートできるのが v4 との違い。
func NewUUIDv7(now time.Time, rand io.Reader) (string, error) {
var b [16]byte
ms := uint64(now.UnixMilli())
if ms >= 1<<48 {
return "", errors.New("idgen: timestamp exceeds 48 bits")
}
// 先頭6バイト = 48bit ミリ秒(big endian)。上位バイトが先頭に来るから辞書順=時刻順になる。
for i := 0; i < 6; i++ {
b[i] = byte(ms >> (40 - 8*i))
}
if _, err := io.ReadFull(rand, b[6:]); err != nil {
return "", fmt.Errorf("idgen: read random: %w", err)
}
b[6] = (b[6] & 0x0f) | 0x70 // version 7
b[8] = (b[8] & 0x3f) | 0x80 // variant 10
return formatUUID(b), nil
}上位バイトから時刻を詰めている(big endian)のがポイントで、 これにより文字列比較 = 時刻順が成立する。
メリット
- 時刻順にソート可能で、インデックスの挿入が常に「右端」に集中する(後述)
- UUID互換の128bit。既存の UUID カラム・ツールにそのまま入る
- 同一ミリ秒内でも74bitの乱数があり、衝突は確率的に無視できる
デメリット
- IDから生成時刻が読める。「いつ作られたか」を隠したいリソース(招待コード等)には不向き
- ミリ秒内の順序は保証されない(規格には乱数部を連番化するオプションもある)
実例
- PostgreSQL 18 の
uuidv7()。新規システムの主キーの新しい既定になりつつある
試してみる: 連打しても生成順と辞書順が一致し続ける。先頭の色付き部分(時刻)が 少しずつ進むのが見える。
3. ULID: 同じ配合、人間向きの表現
ULID は「48bit ミリ秒 + 80bit 乱数」で、ビットの配合は UUIDv7 とほぼ同じ。 違いは表現で、Crockford base32 という「紛らわしい I, L, O, U を除いた32文字」で 26文字にエンコードする。UUID の36文字より短く、ダブルクリックで全選択でき、 大文字小文字の区別もない。
// crockford は ULID が使う base32 アルファベット。
// 紛らわしい I, L, O, U を除いてあり、大文字小文字の区別もない。
const crockford = "0123456789ABCDEFGHJKMNPQRSTVWXYZ"
// NewULID は「48bit ミリ秒 + 80bit 乱数」を Crockford base32 で26文字にしたIDを返す。
// 中身は UUIDv7 とほぼ同じ配合で、表現(短くて人間が扱いやすい文字列)が違う。
func NewULID(now time.Time, rand io.Reader) (string, error) {
ms := uint64(now.UnixMilli())
if ms >= 1<<48 {
return "", errors.New("idgen: timestamp exceeds 48 bits")
}
var random [10]byte
if _, err := io.ReadFull(rand, random[:]); err != nil {
return "", fmt.Errorf("idgen: read random: %w", err)
}
var out [26]byte
// 時刻部: 48bit を5bitずつ10文字に(50bit分の器に上位2bitはゼロ詰め)。
for i := 9; i >= 0; i-- {
out[i] = crockford[ms&31]
ms >>= 5
}
// 乱数部: 80bit を5bitずつ16文字に。
for i := 0; i < 16; i++ {
out[10+i] = crockford[take5(random[:], i*5)]
}
return string(out[:]), nil
}
// take5 はバイト列の bitOffset ビット目から5ビットを取り出す。
func take5(b []byte, bitOffset int) int {
byteIdx := bitOffset / 8
v := int(b[byteIdx]) << 8
if byteIdx+1 < len(b) {
v |= int(b[byteIdx+1])
}
return (v >> (11 - bitOffset%8)) & 31
}コードの読みどころ: 8bit の世界から 5bit を切り出す
base32 は「5bit = 1文字」だが、データは8bit単位のバイト列で持っている。 8と5は割り切れないので、文字の境界がバイトの境界をまたぐ。 take5 はそのために「隣り合う2バイトを16bitの窓として並べ、そこから5bitを取り出す」:
乱数バイト列: [1010 0110] [1101 0001] ...
bitOffset=5 から5bit欲しい
2バイトを連結: 1010 0110 1101 0001 (16bitの窓)
右シフトで位置合わせ: ^^^^ ^ → 0110 1 = 13
& 31 (0001 1111) で下位5bitだけ残す時刻部のほうは 48bit を単純に >>= 5 で右から5bitずつ剥がしている。 48bit は5で割り切れない(10文字 = 50bit)ので、先頭の2bitはゼロ詰めになる。
メリット
- 短い・コピペしやすい・URLに安全。「人間がIDを扱う」場面に強い
- もちろん辞書順=時刻順
デメリット
- UUID ではないので、UUID型カラムや既存ツールとの互換性はない
- 標準化文書(RFC)を持たないコミュニティ仕様
実例
- 各言語のライブラリ経由で広く使われる。Shopify や Cloudflare の内部IDなど、 ログやURLにIDが露出するシステムで好まれる
試してみる: v7 と同じく生成順と辞書順が一致する。26文字の見た目の違いを v4/v7 と見比べてほしい。
4. Snowflake: 乱数を使わない
Twitter が2010年に公開した方式。41bit ミリ秒 + 10bit ノードID + 12bit 連番を int64 に詰める。乱数がなく、衝突回避は「ノードIDを事前に配っておく」ことと 「同一ミリ秒内は連番を増やす」ことで構造的に行う。
// Snowflake は「41bit ミリ秒 + 10bit ノードID + 12bit 連番」を int64 に詰める発番器。
// 乱数を使わず、衝突回避を「ノードIDの事前配布」と「同一ミリ秒内の連番」で行う。
// 64bit に収まるのが UUID 系(128bit)との最大の違い。
type Snowflake struct {
mu sync.Mutex
nodeID int64
epoch time.Time
lastMs int64
seq int64
now func() time.Time
}
// NewSnowflake は nodeID ∈ [0, 1023] の発番器を返す。now が nil なら time.Now を使う。
func NewSnowflake(nodeID int, epoch time.Time, now func() time.Time) (*Snowflake, error) {
if nodeID < 0 || nodeID > 1023 {
return nil, errors.New("idgen: nodeID must fit in 10 bits (0-1023)")
}
if now == nil {
now = time.Now
}
return &Snowflake{nodeID: int64(nodeID), epoch: epoch, lastMs: -1, now: now}, nil
}
// Next は次のIDを返す。時計が巻き戻ったら、黙って重複の危険を冒すのではなくエラーにする。
func (s *Snowflake) Next() (int64, error) {
s.mu.Lock()
defer s.mu.Unlock()
ms := s.now().Sub(s.epoch).Milliseconds()
if ms < 0 || ms >= 1<<41 {
return 0, errors.New("idgen: timestamp out of 41-bit range")
}
if ms < s.lastMs {
return 0, fmt.Errorf("idgen: clock moved backwards by %dms", s.lastMs-ms)
}
if ms == s.lastMs {
s.seq++
if s.seq >= 1<<12 {
// 同一ミリ秒で4096個使い切った。実物は次のミリ秒まで busy wait する。
return 0, errors.New("idgen: sequence exhausted in this millisecond")
}
} else {
s.lastMs = ms
s.seq = 0
}
return ms<<22 | s.nodeID<<12 | s.seq, nil
}コードの読みどころ: シフトで3つの値を1つの int64 に詰める
最後の ms<<22 | s.nodeID<<12 | s.seq が本体。左シフトは「その値の置き場所まで ビットをずらす」操作で、3つの部品を重ならない位置に置いてから OR で合成している:
ms << 22 = [ミリ秒 41bit][0000000000][000000000000]
nodeID << 12 = [ 0][ノード10bit][000000000000]
seq = [ 0][ 0][連番 12bit ]
OR で合成 = [ミリ秒 41bit][ノード10bit][連番 12bit ]テストで id >> 22(右シフトで時刻を取り出す)、(id >> 12) & 0x3ff(ノード部だけ マスクで抜く)と分解しているのは、この詰め方の逆操作。 ミリ秒が最上位にあるから、int64 の数値比較がそのまま時刻順になる。
メリット
- 64bit に収まる。UUID系(128bit)の半分で、int64 の主キーにそのまま入る。 インデックスも半分、JSON でも短い
- 時刻順ソート可能。同一ミリ秒内の順序まで連番で保証される
- 乱数がないので衝突が「確率的に低い」ではなく「起きない」(前提が守られる限り)
デメリット
- ノードIDの配布という運用が発生する。「誰にも聞かない」を実現するために 「事前に一度だけ配る」を受け入れる設計
- 時計の巻き戻りに弱い。NTP補正などで時計が戻ると同じ時刻を再び使ってしまうため、 実装は巻き戻りを検出してエラーにする(テストで固定してある)。乱数がない代償
- 秒間 409.6万/ノード(4096/ms)が上限
実例
- Twitter(出自)、Discord・Instagram のID。Discord の snowflake は API 仕様書に ビット構造がそのまま載っている
試してみる: 連打すると同一ミリ秒内は連番部だけが増える。時刻・ノード・連番の 3部品が見えるのは乱数なし方式ならでは。
なぜ「ソート可能」が効くのか
DBの主キーインデックス(B-Tree)は、キーの順序で並んだページの木。
- UUIDv4: 挿入位置が毎回ランダムなページになる。ページキャッシュが効かず、 どのページも中途半端に埋まって断片化する
- UUIDv7 / ULID / Snowflake: 新しいIDは常に「一番右のページ」に追記される。 触るページが局所化してキャッシュに乗り、ページは順に満杯になっていく
「ランダムな主キーで挿入が遅い」は実務で本当に踏む問題で、 これが v4 から v7 への移行が進む最大の理由。この現象は B-Tree の章のデモで実際に見られる(昇順挿入は右端だけが光り、 ランダム挿入は毎回違う場所が光る)。ページとキャッシュの理屈は ディスクとページで扱っている。
4方式の比較
| 方式 | ビット | 配合 | ソート可能 | 実例 |
|---|---|---|---|---|
| UUIDv4 | 128 | 乱数のみ | 不可 | gen_random_uuid()、各言語標準 |
| UUIDv7 | 128 | 時刻48 + 乱数74 | 可 | PostgreSQL 18 uuidv7() |
| ULID | 128 (26字) | 時刻48 + 乱数80 | 可 | ログ・URL露出系のID |
| Snowflake | 64 | 時刻41 + ノード10 + 連番12 | 可(ms内も) | Twitter、Discord、Instagram |
簡略化したこと
- UUIDv7 の同一ミリ秒内単調性オプション(乱数部の一部を連番にする)は未実装
- ULID のデコード(文字列から時刻を復元する)は未実装
- Snowflake の連番枯渇は「次のミリ秒まで待つ」のが実物だが、ここではエラーにした
- ノードIDの配布方法そのもの(ZooKeeper、IPから導出、など)は扱っていない
参考資料
- RFC 9562 — UUIDv7 を含む UUID の現行規格
- ULID spec — 仕様と各言語の実装一覧
- Announcing Snowflake — Twitter による原典
- Discord API: Snowflakes — 実物のビット構造が読める