Generating unique id numbers in Azure

Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Generating unique id numbers in Azure

Ad

Ad

Ad

Ad

Ad

Ad

Ad

Ad

Ad

Ad

Ad

Ad

Generating unique ID numbers
in Microsoft Azure
kyrt Takekazu Omi
takekazu.omi@kyrt.in
@takekazuomi
2014/3/29 1.0.1

Generating unique ID numbers
in Microsoft Azure
スケーラブルなID生成手法の比較と、twitter snowflakeに見る工夫
2014/2/26 kyrt @takekazuomi 2

Agenda
• Challenge
• スケーラブルなサービスとスケーラブルな採番
• twitter snowflake
• スケーラブルな分散採番サービスの例
• Cloud Design Patterns
• 応用例
kyrt @tak...

Challenge
スケーラブルなサービスには、スケーラブルな採番が必須
課題と背景的な話
「またの名をChallengeを課題と訳さないで」
2014/2/26 kyrt @takekazuomi 4

ID生成の要件
1. ユニークである
重複が無い。これはIDをキーにしたいので当然ですね。
2. 時系列で増えていく（または減っていく）
IDが生成される度に増加していくのは連番での重要な性質の一つ
3. 秒間の発行数
採番を一箇所で行わずに分...

ID生成のパターン
1. SQL Databaseの自動連番を使う
• スケールしない、耐障害性を考慮すると複数台必要
2. ID Providerが完全に独立して存在する
• GUID等、128bit 16 byte
3. 擬似ID Prov...

最初の２つ
• SQL Database の利用
• 秒間の発番数、同時接続数に問題なければ、従来どおり利用可能
• 上記の問題があるなら、複数のDBを使う(sharding)という方法もある
• しかし、仕組みとしてはちょっと重い。コストも高...

時系列のキーの例
.Netなら、Tikcs などを使う
こんな感じ
var id =
string.Format("{0:D19}{1:N}",DateTime.UtcNow.Ticks, Guid.NewGuid());
var revers...

擬似ID Provider パターン
• Clientで擬似的にIDを生成し
て、UNIQUE性は、永続化レ
イヤーで担保
• retryの発生頻度にパフォーマ
ンスが依存
• 性能が永続化レイヤーに依存
• スケールのためには永続化レ
イヤー...

CacheなどのNetwork Service を利用
• RBDの自動連番より小さなレ
イテンシー(1-2ms)
• IDは時系列で増える
• 耐障害性に課題
• HA構成、永続化オプションを
考慮
• 工夫
• 起動時の時間＋increme...

課題整理
1. latency（レイテンシー）
HAのために、Node間通信、永続化に時間がかかる。retryが発生すると
時間がかかる
2. reliability（信頼性）
採番系が一箇所なのは、UNIQUEの担保には有利だが、障害に弱くな...

特性の比較
kyrt @takekazuomi 12
latency reliability scalability data size
SQL 自動連番 ◯ × × ◯
GUID等 ◯ ◯ ◯ ×
Pseudo ID and Retry △※...

ここまでのまとめ
• 永続化ストレージ
• latency（↓）、 reliability（↑）、 scalability（↓）、 data size（↑）
• scalability改善には、パーティショニングが必要 → パーテーションを
跨...

こんなのがあったら
•GUIDのように速く
•SQL の自動採番のように並んで
•簡単に使える
•そんなに長くない(longぐらいで入ると嬉し
い）
kyrt @takekazuomi 14

twitter snowflake
https://github.com/twitter/snowflake/
kyrt @takekazuomi 15

snowflake の短い説明
• snowflake は、Twitter 社が作成した、UNIQUEなID生成のネッ
トワークサービス。いくつかの簡単な保証で高いスケーラビリ
ティを実現
• Twitter 社が、MySQLから Cassan...

基本的なアイディア
• Clock Skew （クロックスキュー）に上手く対応することで、
オンメモリの計算だけでUNIQなIDを生成する
• 永続化レイヤーの支援無しにUNIQなIDが生成できる、ID生成
はオンメモリなので速い（10k id...

データ構造
• snowflake では、64bitを上記のように分割して使います
• timeが時間由来の数字でミリ秒単位
• machine id は、datacenter id と、worker id で構成されていて、
Cluster内...

ポイント
• 時間由来のデータが先頭 41bit なので発番の時間順に並びます
• ms で41bit だと (2^41)*(10^-3)/60/60/24/365 で約69年
• 各インスタンスは、クラスター内でUNIQUEな、machin...

コード上の工夫
• なかなか興味深かったので、 IdWorker.scala をC#で写経
https://gist.github.com/takekazuomi/9571376
kyrt @takekazuomi 20

time skew対策
• 最後に発番してからtimestampが戻っていないか確認 L63
• 巻き戻っていればエラーで帰る（呼び出し側が再試行する）
kyrt @takekazuomi 21

time 41bit の有効利用
• 開始時間を採番の開始時間と合わせてbitを有効利用
• TwEpoch は、2010/11/04。2010/11/01 + 69年
kyrt @takekazuomi 22

sequence
• 同一timestampなら、_sequence をインクリメントして採番
`L72 <https://gist.github.com/takekazuomi/9571376#file-
idworker-cs-L72>`_...

起動時に
Worker Idの重複を確認
構成
• snowflake のWorkerは複数の
Nodeで構成
• Nodeの起動時にWorker Idの
重複をzookeeperを使って担
保
• GUID では、MAC Address
48...

machine idを重複させない仕組
• snowflakeでは、 machine id の下位5bitの Worker Idを
zookeeperで管理しています
• 起動時にWorker Idで、 Ephemeral Nodes を作成
...

Micorosoft Azure でどうするか
• Azure Blobのリースを使うとほぼ同じことができます
• Worker Idのpathのleaseが取れば、重複なしで起動Ok
• インスタンスが生きてる間は、Leaseを更新
• 参考...

まとめ
• snowflakeは、on memory で時間情報を元に高速にIDを生成す
る
• IDの一部にはmachine idが含まれていて、nodeの起動時に
zookeeperを使って重複を確認する
• 起動後は、node-zooke...

Appendix
2014/2/26 kyrt @takekazuomi 28

リファレンス
• Twitter IDs, JSON and Snowflake
• https://dev.twitter.com/docs/twitter-ids-json-and-snowflake
• snowflake source ...