2012/04/27

Snowflake的なID生成方法

作っているプログラムでランダムなIDが必要となったため、ちょっとリサーチしました。久しぶりにJavaでコードを書いています。

UUID

完全に分散した環境で使用するのには、UUID(Universally Unique Identifier)が最適です。1IDあたり16バイトの容量が必要となる点をのぞけば、理想的なIDと言えると思います。ただIDは大量に使用されるので、16バイトというサイズはちょっと気になります。

Snowflake

SnowflakeはTwitterが使用しており、Apache Licenseで公開しているID生成方法です。ある程度分散した環境でも、1IDあたり8バイトの容量で利用できます。また非常に重要な特徴としてIDの先頭部分にタイムスタンプ利用しており、生成されたIDはある程度時系列に並びます。8バイト、つまり64bitを下記のように振り分けて使用します。

  • 先頭42bitにタイムスタンプ(ms)を割り当て、時刻を分散
  • 10bitのマシンIDを割り当て、ID生成を行うマシンを分散
  • 12bitのシーケンスIDを割り当て、同一時刻(ms)、同一マシンでのIDを分散
タイムスタンプに42bitしか割り当てないのは心もとないですが、基準時刻をシフトさせることで利用できる期間をのばしています。

参考

Snowflake的なID生成方法

Snowflakeは魅力的なのですが、テスト環境等も含めてマシンIDを管理するのは意外に面倒です。ただ、この体系の本質的な特徴は「先頭にタイムスタンプを割り当てた分散ID生成」であり、このテクニックはいろいろ応用できそうです。

今回使用する構成ではAmazon DynamoDBでDHCPのようにworkerを管理することにしました。DynamoDBをアトミックカウンターとして使用するという超贅沢仕様で、ついでにidの取得時刻、開放時刻等も記録してみました。worker idが枯渇するリスクを下げるため、worker idは24時間に一度更新しています。

0 件のコメント:

コメントを投稿