redis2.6 + lua scripting で snowflake 風の timestamp based id を生成

https://github.com/twitter/snowflake
twitterのID生成に使用されているという噂のsnowflakeですが、こちらは導入にZooKeeperやCassandraが必要という事があり、若干敷居が高いです。

もう少しカジュアルに初められる手段として、redisと、2.6以降から機能追加されたLua Scripting機能を組み合わせて、同種のid生成処理を試してみました。


◯snowflake
snowflakeは、timestampの数値をベースとした64bit idを生成するための仕組みです。
timestamp値を基にid生成することで、以下のメリットが得られます。

• 生成されたidから、idが生成された時刻を復元することができる。
• 生成日時が古いidより生成日時が新しいidの方が基本的に数値が大きくなるため、idを用いた時間sortができる。

ただし、通常多くの言語処理系ではtimestampは64bitで表現されています。

また、timestamp値だけをidとして用いると、並列処理でid生成を行った際に重複が発生する可能性があります。

そのため64bitでidを表現したいのであれば、timestamp部のサイズの省サイズ化と、idとして重複を発生させない仕組みが必要です。

省サイズ化については、timestampをそのまま使うのでなく、ある一定時刻のtimestamp値(epoch)を減算することで少ないbit数で表現するようにしています。基本的に今後生成するid値は未来のtimestamp値をベースにすれば良いので、id生成を始める前の過去分の情報を削ることでサイズを節約する、というアプローチです。

実際のsnowflakeのソースでは以下のようになっています（抜粋）

val twepoch = 1288834974657L // Thu Nov 04 10:42:54 JST 2010
var timestamp = System.currentTimeMillis()
timestamp - twepoch

重複の抑制については、id情報にnode idと、各ノードが発行するsequenceという値を付与することによってある程度防いでいます。
実際のsnowfalke id のbit layoutは以下。

• time - 41 bits (millisecond precision w/ a custom epoch gives us 69 years) 
• configured machine id - 10 bits - gives us up to 1024 machines 
• sequence number - 12 bits - rolls over every 4096 per machine (with protection to avoid rollover in the same ms)

unsigned な long で無くても整数値で扱える事を意図してか、実際は 63bit (41+10+12)の情報量でidの表現を行なっています。

◯redis + lua scripting でのid生成
evalコマンドによるscripting機能対応は2.6より追加された機能なので、まず2.6以降のredisをインストールする必要があります。
http://redis.io/download

なお、scripting処理はevalコマンドを用いて行えます。
http://redis.io/commands/eval

次に、redis nodeのnode id と sequence 情報を表現するための入れ物を用意します。
ここではnode idのkeyは"node_id", sequenceについては"sequence"とします。
redisを複数台用意する場合は、node_idのvalueは各redis serverごとに異なる数値を割り当てます。

$ redis-cli set sequence 1
$ redis-cli set node_id 1

続いて、id生成処理を行うlua scriptを用意します。lua内部で'sequence'はインクリメントし、自分自身のnode_idの値を取得し、timestamp - epoch の値とを組み合わせてidを生成しています。

-- id.lua
local epoch = 1288834974657
local seq = tonumber(redis.call('INCR', 'sequence')) % 4096
local node = tonumber(redis.call('GET', 'node_id')) % 1024
local time = redis.call('TIME')
local time41 = ((tonumber(time[1]) * 1000) + (tonumber(time[2]) / 1000)) - epoch
return (time41 * (2 ^ 22)) + (node * (2 ^ 12)) + seq

その上で以下のようにevalコマンドでluaスクリプトを発行すると、id値が生成されます。

$ redis-cli --eval id.lua
(integer) 347205555082385408

生成に関しては以上です。


◯運用にあたっての制約
本体のsnowflakeについても同じ事が言えますが、単一ノード内で、１ミリ秒以内に4096回以上idの生成を行うと、idが重複してしまう可能性があります。
なので、"redisノード数 × 4096回 / ms" 以上のオーダーでid生成が行われそうな場合は、逐次redisのノードを増やしていく必要があります。

また、idの重複に関しては、上記の仕組みだけでは検知できないので、生成したidを取得した側で重複チェックを行う必要があります。

また、各redisノードに設定されたnode idが万が一重複してしまうとid重複の発生確率も高くなるので、運用的に重複が起こらないようにする必要があります。

また、osの時刻が過去にずれてしまった場合、仕組み的にidの重複が起こりやすくなります。この部分についても実際は考慮が必要になると思います。

実際、一意のidを少ないビット量で表現するのにはどうしても制約がつきまとうので、運用には工夫が必要になるとは思います。
厳密にuuidを運用したい場合は、以下のRFCの記述なども参考になると思います。
http://www.ietf.org/rfc/rfc4122.txt

まあ、手軽にやる方法として、一応ご紹介いたしました、みたいな記事でした。