🐱

ユニークint64 ID採番機 katsubushi - fujiwara-ware 2024 day 23

2024/12/23に公開

この記事は fujiwara-ware advent calendar 2024 の23日目です。

katsubushi とは

https://github.com/kayac/go-katsubushi

katsubushi は、ユニークな int64 ID を採番するためのサーバーです。

Memcached protocol, HTTP, gRPC に対応したサーバーとして動作し、クライアントからのリクエストに対してユニークな int64 ID を採番して返します。

なぜ作ったのか

かつて運用していたサービスで、データベースを後から分割(シャーディング)する必要が発生しました。既存のテーブルの ID は int64 で AUTO_INCREMENT していたのですが、シャーディングするためには ID の採番方法を変更する必要がありました。

複数のデータベース間で値が被らないように、かつ int64 の範囲を超えないように、かつ高速に採番するためのサーバーとして katsubushi は作られました。2015 年のことです。

UUID や ULID ではだめ?

UUID はユニークな ID を採番するための方法として一般的です。しかし、UUID v4 はランダムな値であるため、データベースのインデックスの効率が悪くなることがあります。時間に対応する順序性を持った値のほうが望ましかったのです。現在の ULID や UUID v7 はその性質を持っていますが、katsubushi を開発した 2015 年当時はどちらも存在していませんでした。

また、そもそもこれらの値は 128bit です。既存のテーブルの id は BIGINT (int64) だったので、採用できませんでした。

アルゴリズム

katsubushi は 64bit の int を採番します。アルゴリズムはかつて Twitter が使っていた Snowflake と同じです。現在 Discord が発行している形式とも (Epoch が 2015-01-01T00:00:00Z なことも含めて) 同一だったりします。

発行される ID の値は、先頭bit0固定 + 現在時刻(epochからの経過秒数msec単位)41bit + Worker ID 10bit + Sequence 12bit で構成されています。そのため、時系列で後から発行された ID は以前に発行された ID よりも大きくなるという順序性を持っています。

Worker ID は、サーバーを複数台起動する際に重複しないように指定する必要があります。Sequence は、同一 msec に複数回リクエストがあった場合に順番に増加します。つまり、1 msecあたり最大で 4096 個の ID を採番することができます。1台当たり1秒間に 4096 * 1000 = 4,096,000 個の ID を採番することができるため、発行できる ID が不足することは実用上はありません。

Discord のドキュメントも参考にしてください。

https://discord.com/developers/docs/reference#snowflakes

使い方

使い方は簡単です。以下のようにサーバーを起動するだけです。-worker-id は、発行される ID の中に含まれる Worker ID 10bit(1024個)分の領域に対応するものです。

$ katsubushi -worker-id 1

この -worker-id は複数の katsubushi サーバーを起動する際に、それぞれに異なる値を指定することで、ID の重複を避けるために使います。同一の値を指定してしまうと ID が重複してしまう可能性があるため注意が必要です。

これで、デフォルトのポート 11212 で memcached プロトコルのサーバーが起動します。クライアントからのGETリクエスト(keyはなんでもよい)に対して、ユニークな int64 ID を採番して返します。

同時に HTTP のサーバーも起動する場合は -http-port オプションを、gRPC のサーバーも起動する場合は -grpc-port オプションにポート番号を指定してください。

実行例

ポート 8888 で HTTP サーバーを起動する例:

$ katsubushi -http-port 8888 -worker-id 1
2024-12-14T12:12:17.986+0900    INFO    go-katsubushi/app.go:168        Listening server at [::]:11212
2024-12-14T12:12:17.986+0900    INFO    go-katsubushi/app.go:169        Worker ID = 1
2024-12-14T12:12:17.986+0900    INFO    go-katsubushi/http.go:49        Listening HTTP server at [::]:8888

クライアントからリクエストする例

$ curl http://localhost:8888/id
1317328315698122752

$ curl -H "Accept: application/json" http://localhost:8888/id
{"id":"1317328647027167232"}

Worker ID の重複を避ける

katsubushi を複数台で実行する場合、発行する ID の重複を避けるために -worker-id を重複しないように指定する必要があります。しかし、この値を確実に排他的に指定するのは、特に動的にサーバーが増減する場合には困難です。

katsubushi には Redis を利用して、ID の重複を避けるための機能があります。-redis オプションに Redis サーバーの URL を指定すると、Redis を使って重複しないように worker ID を割り当てます。

この機能を使うと katsubushi を各サーバーやコンテナで動的に起動しても、ID の重複を避けることができます。(全体で1024個以内という制約はあります)

Redis をどのように使っているかは、次のスライドを参照してください。fujiwara-ware の raus というライブラリを使って、排他的な割り当てを実現しています。

https://speakerdeck.com/fujiwara3/katsubushi?slide=80

https://github.com/fujiwara/raus

時刻巻き戻りへの対応

katsubushi は、時刻が巻き戻ることを想定して設計されています。

システムの時刻がなんらかの原因で巻き戻った場合、システム時刻から ID を発行すると、過去に発行した ID が再度発行される可能性があります。これを防ぐために、現在時刻の算出には Go の monotonic time を使っています。

またプロセス内部では発行したタイプスタンプの最大値を常に記録し、万が一それより小さい時刻が得られた場合にはエラーで応答します。重複する可能性がある ID を発行するぐらいであれば、エラーを返すほうが安全です。

運用

katsubushi には、サーバーの状況をモニタリングするための API があります。

memcached protocol

memcached protocol では STATS コマンドを実行すると、サーバーの状況を取得できます。本物の memcached が返す情報とフィールド名が同一なので(足りないフィールドはありますが)、既存のツールで監視することができます。

STAT pid 8018
STAT uptime 17
STAT time 1487754986
STAT version 1.1.2
STAT curr_connections 1
STAT total_connections 2
STAT cmd_get 2
STAT get_hits 3
STAT get_misses 0

HTTP

GET /stats をリクエストすると memcached protocol と同様の stats を取得できます。

{
  "pid": 1859630,
  "uptime": 50,
  "time": 1664761614,
  "version": "1.8.0",
  "curr_connections": 1,
  "total_connections": 5,
  "cmd_get": 15,
  "get_hits": 25,
  "get_misses": 0
}

gRPC についてはドキュメントを参照してください。

まとめ

katsubushi は、ユニークな int64 ID を採番するためのサーバーです。Memcached protocol, HTTP, gRPC に対応しており、クライアントからのリクエストに対してユニークな int64 ID を採番して返します。

2015年に開発され、現在まで継続的にメンテナンスされています。現代では UUID v7 などが利用できるため、積極的に採用する必要はないかもしれませんが、分散環境でユニーク性を担保した int64 ID が必要な場合には依然として有用です。

もしこのようなニーズがある場合は、ぜひ katsubushi を試してみてください。

それでは、明日もお楽しみに!

参考資料

https://speakerdeck.com/fujiwara3/katsubushi

https://speakerdeck.com/fujiwara3/kamakura-dot-go-number-5

https://techblog.kayac.com/katsubushi-introduction.html

https://sfujiwara.hatenablog.com/entry/2017/07/01/160511

Discussion