Snowflakeが解こうとする識別子の問題

分散サービスでは複数ノードが同時にレコードを作るため、衝突しない識別子が必要です。Twitterアーカイブの IdWorker.scala は時刻・データセンター・ワーカー・連番を一つのIDに組み合わせます。IDごとの中央発行要求を避けられる一方、ワーカー割当と時計の動作は運用上の前提として残ります。READMEによると公開された初期版は引退し、社内版はTwitterのインフラに依存する形で書き直されました。本稿は確認したアーカイブ版に範囲を限定します。

時計逆行のリスクを伴う識別子を生成する分散ワーカー

時刻・ワーカー・連番を組み合わせる

原型の設計は時刻値、ワーカー番号、連番を整数IDに組み合わせます。時刻部分は概ねの並び順を助け、ワーカー部分は同時に動く生成器を区別し、連番は同じ時間区間に同一ワーカーが複数IDを作るためのものです。各部分のビット幅、時刻単位、基準時点は実装によって異なります。Snowflakeと呼ばれるライブラリでも形式や運用条件が違う可能性があり、名称だけで互換性を判断できません。

2010年のアーカイブコードでは時刻がIDの上位ビットに置かれるため、異なるミリ秒のIDをおおよその時間順に並べる助けになります。同じミリ秒ではworkerとsequenceのビットも結果を決めるため、IDの大小だけで複数ノードの出来事の因果順序は証明できません。Discordのエンジニアも、自社のメッセージ構造においてSnowflake IDを時系列に並べられると説明していますが、これはそのデータ設計での使い方です。このコードは初期公開実装の特定動作であり、すべてのSnowflake派生実装の保証ではありません。

コードはワーカーIDとデータセンターIDがビット範囲外なら初期化を拒否するが、別サーバー間の重複割当を防ぐ責任は配備側に残る。

一意性は配備全体の条件に依存する

時刻・ワーカー・連番の方式では組み合わせが重ならないことが一意性の前提です。同じ時間帯に動く二つの生成器へ同じワーカーIDを割り当てないこと、同一ワーカーが時間区間内で連番を再利用しないこと、基準時点と時間単位を一貫して扱うことが必要です。ビット配置図だけではこの条件は証明できません。設定配布、再起動、コンテナ移動、障害後の状態復旧も検討対象です。

時計逆行は別の境界事例です。後の時刻でIDを発行したワーカーのシステム時計が過去へ戻ると、以前使った時間値を再び通る可能性があります。衝突の有無は逆行処理、連番状態、その後の呼び出しの実装によります。Twitterアーカイブのissue #6は、逆行後に例外を出す前に連番を0へ戻すと、過去の時刻値へ戻った際に重複IDを生み得る特定の欠陥経路を報告しています。これは当該コード経路の記録であり、すべてのSnowflake派生実装が同じ問題を持つという意味ではありません。

実装の前提を明らかにするテスト

利用するバージョンのコードと設定を読み、前提条件を試験します。ワーカーIDが二重割り当てされないか、時間区間内の連番を使い切ったときにどうなるか、時計逆行時にエラー・待機・再利用のどれが起きるかを確認します。再起動、コンテナ移動、障害復旧、時間単位の境界、基準時点の変更も含めます。呼び出しが失敗した後にどの状態が残るか、再試行が業務操作を二重実行しないかも調べます。

正常系で一つの生成器から多数のIDを作るだけでは不十分です。二つのプロセスに同じワーカーIDを設定する、テスト時計を過去へ動かしてから進める、連番を使い切る、状態を保持または初期化して再起動する試験を用意します。時計エラーが返っただけで次の呼び出しが安全とは限りません。保持される時刻の記録と連番状態が重複を防ぐことを確認してください。一意性が重要な業務では保存層の重複検出と復旧処理も試験対象です。

専門家の視点：並び順はアプリケーション上の便宜

DiscordのシニアスタッフソフトウェアエンジニアBo Ingramは、DiscordのメッセージシステムでSnowflake IDが時系列に並べられると説明しています。記事では、Discordがチャンネルと固定時間枠を組み合わせてメッセージを保存する運用例が示されています。ここから分かる実務上の点は、ソート可能なIDがより大きなデータ配置の一部として使われることです。ID単独でパーティション設計やホットスポットを解決するわけではなく、全ワーカー間の絶対順序を保証する根拠にもなりません。

Twitterの元リポジトリは現在アーカイブされています。READMEは初期版が引退し、社内版は書き直されてTwitterのインフラに依存すると説明しています。2010年のコードを現行の汎用本番ライブラリの保証書のように扱うべきではありません。採用する版のワーカー割当、時計逆行の処理、ビット配置、運用説明を確かめましょう。確定した因果順序や全体順序が必要なら別の仕組みで定義します。

出典

Twitter Archive: Snowflake source repository Bo Ingram, Senior Staff Software Engineer at Discord: How Discord Stores Trillions of Messages Twitter Archive Snowflake 2010: IdWorker.scala Twitter Archive Snowflake issue #6: Duplicate ids possible if clock moves backwards