前回、せっかくPythonでSnowflake作ったので、一念発起してGitHubに晒してみた。
実はGitHubに自前のコードを公開するのは初めてだ。
ま、仕事で非公開のレポジトリはガンガン使ってるけどな。
とりあえずユーザー名とレポジトリ名を決めないとだが、ユーザー名はmitakadaiと無駄に主語を大きくしてやった。
レポジトリ名は元の名前がsnowflake(雪片)なんで、ice crystals(雪の結晶)にした。
英辞郎で snowflakes grown from ice crystals (氷の結晶が成長してできた雪片) なんて例文を見付けたからなのはここだけの秘密だ。
ということで、GitHubデビューのURLは
https://github.com/mitakadai/icecrystals
にござるよ。
ユニークID生成方法としてはUUIDが有名だよね。
基本UUID(version4)で必要十分なんだけど、問題もあって
なんてのがよく出る欠点。
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を生成する。
ぱっと見、必要なユニーク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クラスの使い方など説明するまでもない簡単な作りだ。
実行してみた限り、ちゃんとユニークで連番になってると思う。
まあ、参考程度にどうぞ。
あ、スレッドセーフじゃないので注意ね。
Pythonで62進数を作ってみた。
なぜ62進数かって?
それは英数字全部合わせて62文字だから。
Base64とか+とか/とか入って嫌じゃないですかー。
さっそく書いてみた。
def _make_use_chars_base_62():
return [str(i) for i in xrange(0, 10)] + \
[chr(i) for i in xrange(ord('a'), ord('z')+1)] + \
[chr(i) for i in xrange(ord('A'), ord('Z')+1)]
def encode_base_62(decimal):
base_62_str = ''
use_chars = _make_use_chars_base_62()
while True:
base_62_str = use_chars[decimal % 62] + base_62_str
decimal -= decimal % 62
decimal /= 62
if decimal == 0:
break
return base_62_str
def decode_base_62(base_62_str):
decimal = 0
use_chars = _make_use_chars_base_62()
for c in base_62_str:
decimal *= 62
decimal += use_chars.index(c)
return decimal
もうちょっとキレイで速いコード書けそうだけど、まあいいや。時には妥協も必要さ。
encodeの方のループ抜ける所はdo-whileで書きたいけど、Pythonにはdo-whileないんだよね…
動かしてみよう。
>>> encode_base_62(0)
'0'
>>> encode_base_62(10)
'a'
>>> encode_base_62(36)
'A'
>>> encode_base_62(62)
'10'
>>> encode_base_62(124)
'20'
>>> encode_base_62(100000000)
'6LAze'
>>> decode_base_62('6LAze')
100000000
>>> decode_base_62('0')
0
なんとなく大丈夫そう。
本当はきっちりテストコード書くべきだけど、まあいいや。
62進数、というより英数字62文字で数値を表現したい場合は時々出てくるので、その時にきっちり検証しておこう。
プログラマたるもの、暇な時はアルゴリズムとデータ構造で時間を潰すべきと言えよう。
ということで、Pythonでキューを作ってみた。
プログラマたるもの、キューくらいサクッと書けないといけないね。
class OresamaQueue(object):
def __init__(self):
self._buffer = []
def dequeue(self):
if len(self._buffer) > 0:
return self._buffer.pop()
else:
return None
def enqueue(self, obj):
self._buffer = [obj] + self._buffer
解説するとこもないくらい単純なキューの実装だ。
Pythonのリストにはリストの末尾を削除しつつその値を返してくれるpop()というステキメソッドがあるので、dequeueは楽勝で書けた。
enqueueもPythonではリスト同士を足し合わせると1つのリストに合体してくれるので、[obj]で受け取った値を配列にして既存の配列と足し算しちまえばいい。
テストをしよう。手動で。
>>> import OresamaQueue >>> q = OresamaQueue() >>> q.enqueue(1) >>> q.enqueue(2) >>> q.enqueue(3) >>> q.dequeue() 1 >>> q.dequeue() 2 >>> q.dequeue() 3 >>> q.dequeue() >>> q.dequeue() is None True
うん、見事なまでの先入れ先出し、まごうことないキュー。
ま、Pythonには最初からQueueモジュールがあるので、そっち使えばいいんだけどね。
新しい一方向ハッシュ関数SHA-3をPythonで使いたくなったのでGoogle様にお伺いを立てるとpysha3を使えば良いとのお返事が。
そこでさっそくインストールしてみる。
$ pip install pysha3
CのSHA-3ライブラリのラッパーになってるようだ。
速度も期待できるかな。
さっそく使ってみる。
$ python
>>> import hashlib
>>> import sha3
>>> hashlib.sha3_256('Hello, world!').hexdigest()
'b6e16d27ac5ab427a7f68900ac5559ce272dc6c37c82b3e052246c82244c50e4'
>>> hashlib.sha3_512('Hello, world!').hexdigest()
'101f353a4727cc94ef81613bb38a807ebc888e2061baa4f845c84cd3c317f3430fda3dbeb44010844b35bccc8e190061d05b4d002c709615275a44e18e494f0c'
import sha3するとhashlibにパッチ当ててくれる。
monkey patchとかいうやつだ。
こいつのお陰でhashlibでSHA-2とかと同じ書き方でSHA-3が計算できるので便利。
ちょっとお行儀悪い気もするけど…