yoskhdia’s diary

DDDとかプログラミングとかアーキテクチャとか雑多に

Snowflake形式のIDを採用した場合の苦労ポイント

高速にIDを採番できる仕組みを検討したとき、Snowflake形式のID生成は選択肢のひとつとして有力です。 Snowflakeを紹介する記事は見つかりますが、実際に採用して苦労した話はあまり聞かないため、備忘的に書いてみるエントリです。

Snowflakeとは

1つのIDは64bit(ScalaではLong型)に収まり、ID採番サービスを複数のデータセンターに分散可能かつ高速に採番可能に設計されたID生成の方式です。 先頭ビットにタイムスタンプを持つため、順序があることも特徴のひとつです。 Twitter社がオリジナルの考案者です。*1

github.com

カヤック社からSnowflake形式でID生成可能なKatsubushiというオープンソースのソフトウェアがGithubで公開されています。 発表スライドも参考になります。

github.com

他のID生成方式

他にはDBのシーケンスを利用したりUUIDを使うことが一般的かと思います。 以下がとても簡潔にまとめられており参考になります。

qiita.com

Snowflakeの他にULIDなども取り上げられていますが、ある程度の速度と順序性を得ようと思うと、Snowflakeに似た「タイムスタンプ」と「一定ルールの連番またはランダムな数値」を組み合わせるパターンが主なように思います。 このパターンに該当するID生成方式は、このエントリで取り上げる問題と同様の問題を抱える可能性があります。

苦労ポイント

JavaScriptで切り捨てが発生する

developer.mozilla.org

MAX_SAFE_INTEGER 定数は 9007199254740991 である値です。その数である理由は JavaScriptIEEE 754 で指定されたとおり倍精度浮動小数点型数値を使用し安全に -(253 - 1) と 253 - 1 との間の数を表すことができるからです。

と記載のあるように、JavaScriptでは数値は内部的に倍精度浮動小数点型数値で保持されるため、整数として表現可能な範囲は64bit Longよりも小さいです。 そのため例えば、Snowflake方式で 398419938554941447 と採番されたIDは、数値のままJavaScriptに渡されると 398419938554941400 のように下2桁が 0 に切り捨てられてしまいます。

記録されたデータをRe:dashMetabaseなどのツールで、素直に参照すると正しいIDを参照することができません。 この場合は、CASTCONVERT関数を使って文字列に一度変換する必要があります。

他にも(公開・非公開問わず)APIのレスポンスパラメータとしてIDを加える場合に、利用者がJavaScriptAjaxなど)を使ってリクエストしてくると問題は拡大していきます。 特に公開APIとして、不特定多数の利用者が想定される場合は、途中で変更することは痛みが伴うため、API設計時に考慮した方が良いでしょう。

非同期にIDを採番すると時間に対して順序が逆転することがある

高速にIDを生成したいニーズは、大量のリクエストがあるサービスでおこるように思います。 私の場合は、ユーザIDの他にサイトのページを閲覧した履歴(ログ)やコンバージョンをした履歴を記録する際のIDとして採用しました*2*3

ID採番を非同期に行うとき、実時間に対してIDの順序が同じになるとは限りません。 例えば、リクエスト1、リクエスト2と来た時、これらを非同期に処理する*4と、リクエスト2の方が先にIDを取得することがありえます。 リクエスト順に採番しようとすると、ロックを行わざるをえないためそのままボトルネックになり本末転倒です*5。 ただし、これはオートインクリメントなどで採番する場合でも同様ではあります。 IDサービスをアプリケーションとは別に構築し、それに非同期に(大量に)リクエストし得る点がオートインクリメントとは別種の悩ましさを生むように思います。

このとき、採番主体*6以上の単位でソートすると順序が逆転するようになります。 例えば、閲覧履歴を記録するケースでは、ユーザ単位にデータベースへレコードを作成します。 ユーザ単位でみれば、IDが十分な間隔で消費されていれば、リクエストの順にIDに含まれるタイムスタンプも増えていくことが期待できるため、IDでソートしても大きな問題にはなりにくいです。 しかし、そのサイト全体で(複数ユーザをまたいで)IDによるソートを行うと、時間の順序に並ぶ可能性は低くなります。

なお、時間順序がおおまか(Roughly)であることは、公式リポジトリのREADMEにも以下のように記載があります*7

(Roughly) Time Ordered

We have a number of API resources that assume an ordering (they let you look things up "since this id").

However, as a result of a large number of asynchronous operations, we already don't guarantee in-order delivery.

IDの順序が時間順であることを期待したコードがあると、不可思議なバグになる可能性があります。

他にも

以下のようなとき同様の問題に遭遇する可能性があります。 レアケースではありますが、いざ遭遇すると謎の現象のように感じることになります。

  • 複数のワーカー(ノード)でIDサービスを構築するとき、クライアントが固定のワーカーだけにリクエストしない場合
    • IDの一部にWorkerIDを含むため、この番号の大きいワーカーで振り出されるIDはそれより小さい番号のワーカーよりもIDが大きくなるため。
    • ただし、IDのタイムスタンプはミリ秒単位であるため、1ミリ秒よりも早く複数のワーカーにリクエストしない限り問題ありません。
  • IDサービスを利用するクライアントサイド(=アプリケーションサーバ)で一度に複数のIDを取得してプールしておく場合
    • 前掲のKatsubushiでは一度にまとめてIDを取得できます。そうなると、まとめて取得してプールし、スループットをあげたくなります。
    • しかし、複数のクライアントが同時にIDサービスにリクエストする可能性があるため、クライアントそれぞれがまとめて取得したIDをプールするとエンドユーザは順番が前後したIDを割り当てられてることがあります。
    • エンドユーザからのリクエストをスティッキーセッションによるロードバランシングなどで同じアプリケーションサーバへ到達できるようにすれば問題ありません。ただし、スケールアウトの問題が別に発生します。

これらが複合した場合、一見よく分からない事象が発生し得ます。 特にIDをプールする方法は安易にとりたくなるのですが、複数のクライアント(アプリケーションサーバ)を稼働させる場合に時間順序はほとんど期待できなくなります。

おわりに

当初からSnowflakeを使う場合はIDの順序へ依存していることは少なくなるよう努めると思いますが、既にサービスが稼働していて、それがDBのオートインクリメントに使用していた場合などにIDの順序が時間順であることを期待するコードはよく見かけられます。 ここから、Snowflake形式のIDへ乗り換えることは大きな痛みを伴います*8。 また、他のアプリケーションとデータを共用することがある場合も注意が必要です。 異なるコンテキストのシステムで、IDに期待する順序性については明確にしておいた方が良いでしょう。

SnowflakeなどのID形式を採用する場合は、(アプリケーションとして無視できない範囲の)IDの順序に依存したコードは極力避けるべきです。 DateTimeカラムを用意し、適切なインデックスを作成することも検討しましょう。

余談

タイムスタンプをIDに含める形式の場合、時間のズレ(巻き戻り)が問題になることがあります。 Snowflakeの場合はTime skewを検知してWaitすることが織り込まれていますし、KatsubushiではGo言語のMonotonic Time対応が入っているため、あまり気にしていません。
ref: Go1.9から使える Monotonic Clocks を試してみた
ref: use Monotonic time by fujiwara · Pull Request #21 · kayac/go-katsubushi · GitHub

*1:現在はサポートされておらず過去タグから参照可能なのみです。

*2:まさに順序性と速度が求められていました。

*3:もっとも、RDB以外のデータストアでも利用できることやINSERTする前に採番できることが優先要件でした。

*4:特に公平性(fairness)を考慮しない場合

*5:アプリケーションサーバによっては、リクエスト直後に真っ先に採番するようにすればリクエスト順のID取得はできるかもしれません。しかし、複数のアプリケーションサーバにロードバランシングしている場合には、どこかのリクエストキューの詰まり具合によって発生しうるため根本的な解決にはなりません。

*6:適切な日本語思い浮かばず…。一意にしたい単位と言い換えるべきでしょうか。

*7:「妥当な範囲でkソートできる」のような記載もあるのですがまだ理解できてません…。ご存知の方がいらっしゃいましたら教えてください…。->2022/11追記 https://en.wikipedia.org/wiki/K-sorted_sequence に解説有り

*8:しかしながら、ID生成方式を変えたいシーンは往々にしてこのような場合が多いように思います。