スケーラブルな採番とsnowflake
snowflake は、Twitter 社が作成した、ユニークなID生成のネットワークサービスです。いくつかの簡単な保証で高いスケーラビリティを実現しています。Twitter 社が、MySQLから Cassandra に移行するにあたって、Cassandra にシーケンシャルな id 生成の仕組みが無かったことから作成したそうです。 snowflake についてはTwitter IDs, JSON and Snowflakeに書いてあります。
snowflake のコードは、Apache License, Version 2.0 でSnowflakeに公開されています。
スケーラブルな採番、背景的な話
Cloudでスケーラビリティのあるサービスを見据えてコードを書いていると採番に関する問題が必ず出てきます。従来、RDBの自動採番などに頼っていたのがコスト、スケーラビリティ、耐障害性の観点から問題となり、別の方法を考える必要が出てくるというのが一般的です。
「ID＝連番」という話なら始まると話が混乱するので、基本に返って採番の要件を整理するところから初めましょう。ざっと考えたところ4つほどの条件が出てきたので、この線で話を進めます。
- ユニークである：重複が無い。これはIDをキーにしたいので当然ですね
- 時系列で増えていく（または減っていく）：IDが生成される度に増加していくのは連番での重要な性質の一つです
- 秒間の発行数：採番を一箇所で行わずに分散してスケールするのがスケールする
- 連続性（連続した欠落の無い番号の生成）
最後の連続性に関しては、スケーラビリティとパフォーマンスを両立させての実現は難しいでしょう。スケールと対象外性を考えて分散環境でID生成の度にどうしてもNode間でメッセージのやりとりをせざるを得ず、パフォーマンスを犠牲にせざる得ないので、今回は外して考えます。オンプレでも限定された条件下でのみ可能な採番ですね。
これとは別に何処で採番するかという観点もあります。これは２つのパターンがあります。
- Cluster Service で採番
- クライアントで採番
Cluster Service で採番するパターンとしては、memcached/Redis などの カウンター (incr command) を使ったり、storage を使った分散counterを使ったパターンが知られています。Snowfrakeもこの１種です。クライアントでの採番は、通信を伴わないので一番速い（コストが小さい）ですが制約もあります。
採番のユニーク性
採番と考えると最低限の要求は 「一意であること UNIQUENESS」でしょう。これには、発番した時にユニーク性を担保するか、永続化したときにユニーク性を担保するかの２つの選択肢があります。採番した時に一意性を担保するパターンとしては、GUIDを使う方法よく知られています。ここでは、Guidを使う方法については深くふれません、GUIDs are globally unique, but substrings of GUIDs aren’tで面白い話が書いてあるんのでぜひ読んでみてください。（中には Snowflakeへのヒントになることも記述されています）
GUIDは非常に手軽で便利ですが、128bit(longlong)でかなり長い。時系列で並ばないなどの問題があります。
永続化レイヤーでの一意性の担保
一方永続化したときにユニーク性を担保するという考えもあります。一意なIDを振出すのはコストが高いので、擬似的な（一意性を十分期待できる）IDを振り出して永続化して可否を判断して、ダメならもう一度やってみるというのが「永続化レイヤーでの一意性の担保」の基本的な考え方です。
これは、永続化レイヤーが用意した限定された条件の下でユニーク制約を実装を利用することでユニーク性を担保するというアーキテクチャです。この場合は、「永続化レイヤーの制約」、「重複時の再試行」の２点を考慮しなければいけません。
例えば、Azure Tableでは、同一パーテーション内のRow Keyは一意であることが保証されています。他のパーテーションでは同一のRowkeyを持つことができますが、同一パーテーション内同じRawkeyは Insert できません。
この場合、Partition Key + Row Key でユニークになるので、ランダムなキーを生成して、TableにInsertできればそのパーテーション内ではユニークだと保証されるわけです。RDBのUniq制約でも同様です。Shareding されたデータベースでは、Inserできれば Shard内でユニークだという事になります。いずれも、Partition 内、 Shard 内という条件が付いていることに気を付けてください。永続化レイヤーによって異なった制約となりますが、分散システムではなんからの制約を伴うことが一般的です。
重複時の再試行
永続化レイヤーでUNIQ性を保証をする場合、「重複時の再試行」を前提としてください。クライアントがデータを永続化するまで、IDが有効かどうかわからないので、永続化した時に重複だった場合は再度IDを生成し直して処理を再試行する必要があります。
時系列で増減
IDがランダムではなく、時間と共に増加あるいは減少して欲しいことがあります。このようにIDが並んでいると、永続化レイヤーがレンジクエリーをサポートしていれば、前方一致で効率的に目的のデータを取得することができます。しかし時系列で増加するIDを発番しようとしてNodeのクロックを使うと信頼性が問題になります。
通常、複数Nodeで発番した場合は同一時刻で複数のコードが動くのでIDが重複します。それ以外にもNode内でも問題があります。Nodeのクロックは、外部のtime service に同期させているので、ローカルの時刻は随時進んだり戻ったりします。そのため、時刻だけを元に単純に採番するとIDが重複します。これらの時刻の不安定性に起因する問題を Clock Skew （クロックスキュー）問題と言います。
分散システムの問題の多くは、時刻の同期問題でもあり根が深いので、ここはスルーで先に行きます。
これらの問題を回避するために、IDの一部にランダムな要素を付与する方法が一般的に使われています。
例えば、下記のような感じ
private static void Hoge()
{
var r = new Random();
for (var i = 0; i < 100; i++)
{
var id = string.Format("{0:D19}_{1:D4}", DateTime.Now.Ticks, r.Next(10000));
Console.WriteLine(id);
}
}
ここで発番しているのは擬似的なUNIQ性を持ったIDでです。最終的なUNIQ性の保証は別のレイヤーに預ける前提です。ランダム桁数は、衝突の頻度と衝突時の再試行のコストを鑑みて決定します。この例だと、4桁取っていますが、昨今のCPUだとシングルCoreで同一Tick内で2-3程度は発番できるようなので、100coreぐらいあれば、2*100/10000 = 1/50 となって、結構な頻度で衝突します。（この数字は結構いい加減なので参考程度で）
順番を逆にしたい場合は、下記のようにします。
private static void Hoge()
{
var r = new Random();
for (var i = 0; i < 100; i++)
{
var id = string.Format("{0:D19}_{1:D3}", long.MaxValue - DateTime.Now.Ticks, r.Next(1000));
Console.WriteLine(id);
}
}
こうすると、最新のものが最初にきます。先頭から指定行を取得するようなクエリーをサポートしている永続化レイヤーで最新の情報を取得する場合にはこの並びが便利に使えます。
秒間の発行数
秒間どれぐらいの数のIDを生成可能なのかも重要なファクターです。一般的にオンメモリで計算のみで発番するものが一番速く、永続化付きKVS、RDBMSの順の速度になります。
ID生成はクラスターで行って、分散することでスケールするというのは基本的な考え方で、その場合ID生成クラスターのNodeコストが問題となります。一般的にメモリーで計算のみで発番するものはIDのユニーク性と耐障害性の両立が難しく、なんからの永続化をすることで問題を回避するという方法が取られる場合が多いようです。RDBはID生成を目的としてクラスター化するにはコスト高いのが問題となると思います。
クライアントで擬似的なUNIQ IDを生成して、永続化時に担保させるという方法はリーズナブルにスケールする方法だと言えます。
Snowflake
Clock Skew に上手く対応することで、オンメモリの計算と最低限のノード間通信でUNIQなIDを生成する仕組みです。永続化レイヤーの支援無しにUNIQなIDが生成できる、オンメモリなので速い（10k ids per second per processSnowflake）というのが特徴です。
ある意味GUIDと似ているのですが、64bit(long) で実現しているところ、おおよそ時系列で増えていく「(Roughly) Time Ordered」なことが異なっています。
データ構造
snowfake では、64bitを下記のように分割して使います。timeが時間由来の数字でミリ秒単位です。machine id は、datacenter id と、worker idで構成されていて、Cluster内のNode固有の値になります。sequence number は、同一時間（timeが同じ）間にカウントアップされていく連番です。
| 64 bits | ||||
|---|---|---|---|---|
| 0 |
|
machine id 10bit |
|
|
| datacenter id 5bit | worker id 5bit | |||
前記の時間ベースのID生成と比較すると、IDにNode固有の番号（machine id）が含まれている、同一時間内の採番では乱数ではなくカウンターを使って重複を避けていることが異なっているのがわかります。
実は、この構成は GUID V1と似ています。GUID V1 は、 timestamp 60 bits、computer identifier (MAC Address) 48 bits、uniquifier (乱数＋シーケンス）14 bits、fixed （）バージョン等） 6 bits から構成されています。全体的にGUIDの方がBitの使い方がリッチで余裕がある構成です。データは、DWORD-WORD-WORD-WORD-BYTE[8] として扱われます。Endian の問題もあってtimestamp由来なのに時系列で並びません。timestampは、100 ns 単位です。
snowflake は、GUIDを64 bits (正確には最上位が0固定のなので63 bits）に押し込んでUNIQ性を確保しています。
ではどうやって64bitに押し込んでいるのでしょう。
- 範囲の制限: 簡単に言うと、GUIDは グローバルにUNIQだけど、snowflakeは発番体系内でUNIQです。別のサービスで使っている snowflake clusterと比較するとUNIQ性は保証されません。ここは大きな違いですが、別サービスとIDが被るのは問題無いので、実用上は制限にはなりません。これで、MAC Address 48 bits の所を10 bits に押し込めています。
- timestampの精度と範囲: GUIDは、100 ns 、snowflakeは、1 ms です。timestamp の精度を下げ、開始時間（0の時の日時、何時からの時間なのか）をサービス開始時などに合わせることで、timerのラップアラウンドの問題を軽減しています。(2^41)*(10^-3)/60/60/24/365 で約69年持ちます。ちなみにGUIDは、(2^60)*(10^-7)/60/60/24/365 で3655年以上持ちます。開始は、1582/10/15 0:00 です（3千年以上もつの開始はあまり重要じゃないですね）69年保てば問題無い気がしますね。これで、41 bitsにしています
ソースコード上での工夫
なかなか興味深かったので、IdWorker.scalaをC#で写経してみました。（scala が非常に分かりやすくて感動しました）
基本的な流れは、非常にシンブルです。
NextId()をざっと見てみましょう。
- 現在のtimestamp を取得L60
- 最後に発番してからtimestampが戻っていないか確認L63
- 巻き戻っていればエラーで帰る（呼び出し側が再試行する）L66
- 同一timestampなら、_sequence をインクリメントして採番L72
- timestamp が進んでいれば、_sequence = 0で採番L82
この他は、下記のコードがポイントです。
timestampの開始時間を、採番開始時間にオフセットさせるL87
同一 timestamp 内で、_sequence がオーバーフローした場合は、timestampが変わるまで待つL75
この他に、Worker Idの管理には、zookeeper を使っているなど興味深いところはありますが、今回はこの辺でまとめます。
最後に
実は、この記事を書いている途中に、Global Microsoft Azure Bootcamp 2014があり、このネタで発表してしまったので長らくお蔵入りしていました。読み直してみたら、セッションでは時間の都合で話をしなかった内容もあり、それなりに役に立つかなと思ったので公開します。肝心のsnowflake の採番が速い理由が書いてありませんが、採番node間の通信が最低限で（生きているかどうか）、重複採番の防止にしか使われていないのが、一番効いている気がします。
合わせて、セッション資料も御覧ください。