ユニークID生成方法としてはUUIDが有名だよね。
基本UUID(version4)で必要十分なんだけど、問題もあって
- 128bitもいらない、uint64で扱いたいのに
- 完全にランダムなのでソートする意味がない
なんてのがよく出る欠点。
1はまだ我慢しろとか上位or下位64bit使ってなんとかするとか逃げようもある。
しかし2、特に時系列でIDが増加していって欲しいなんてリクエストがあると途端に使えなくなる。
で、RDBMSのオートインクリメント機能使ったり、きちんとロック処理入れてカラムに現在のIDを保持、ID生成するたびにインクリメント、とかやることになる。
それで何が嫌なのって、処理数が増えるとID生成の箇所が間違いなくボトルネックと化す。
処理を軽くしようとmemcachedやredis使った所で単一点なのは変わらず、クラスタ化か? なんて話となり、結構ブルーなのである。
で、なんかUUIDくらいお手軽で、現実的なところでユニーク性が保証できて、おおよそ時系列に沿って値が増加するユニークID生成方が欲しい。
そう思い、google先生に教えを請いた所、snowflakeという生成方法があるそうだ。
snowflakeはTwitterが以前使っていたユニークID生成方法で、かつてはgithubで公開されていたそうだ。
いまでもその残骸は残っている。
https://github.com/twitter/snowflake
生成方法などはこのスライドがわかりやすい。
http://www.slideshare.net/moaikids/20130901-snowflake
簡単に言うと、3つの値からユニークIDを生成する。
- 最上位bitは0
- 次の41bitはunix time ミリ秒
- 次の10bitはあらかじめユニークに割り振ったmachine id
- 下位12bitは発行する度にインクリメントされていくシリアルナンバー
ぱっと見、必要なユニークID生成が1msで4096ID以下であればユニーク性は守られるであろう。
それで足りないなら、複数マシン／プロセスでmachine idをユニークに割り振って分散すればいい。
さらに、unix timeは通常のepoch(1970-01-01 00:00:00 UTC)ではなく、任意の時刻にセットすることで割り降れるID空間を広げる工夫も入っているようだ。
上位bitがunix timeなので、うまく時系列に並ぶ作りだ。(ミリ秒まで同じタイミングの場合は並ばないケースあり)
最上位bitが必ず0なのでsignedでも安心して使える。
なかなか良い設計に思える。さすがはTwitterだな。
とはいえ、いまは使っていないとのことなので、これでも追いつかなくなったのかID生成。
恐るべしTwitter。
といろいろだらだら書いてきたけど、本題はここから。
この便利なsnowflakeを書いてみたよ、Pythonで。
import time
class Snowflake:
def __init__(self, machine_id, epoch=0, init_serial_no=0):
self._machine_id = machine_id
self._epoch = epoch
self._serial_no = init_serial_no
def generate(self):
unique_id = (
((int(time.time() * 1000) - self._epoch) & 0x1ffffffffff) << 22 |
(self._machine_id & 0x3ff) << 12 |
(self._serial_no & 0xfff)
)
self._serial_no += 1
return unique_id
def main():
snowflake = Snowflake(0, epoch=int(time.time() * 1000))
for i in xrange(100):
print snowflake.generate()
main()
Snowflakeクラスの使い方など説明するまでもない簡単な作りだ。
実行してみた限り、ちゃんとユニークで連番になってると思う。
まあ、参考程度にどうぞ。
あ、スレッドセーフじゃないので注意ね。