ソート可能なUUID互換のulidが便利そう #Python

UUIDは重複しないIDを生成する手段として便利ですが、特にversion4(乱数によるUUID)を利用する場合は一意性を得るのと同時に乱雑さも得ることになりますので、UUIDに順序性を求めることができません。

UUID - Wikipedia
https://ja.wikipedia.org/wiki/UUID

UUID（Universally Unique Identifier）とは、ソフトウェア上でオブジェクトを一意に識別するための識別子である。UUIDは128ビットの数値だが、十六進法による550e8400-e29b-41d4-a716-446655440000というような文字列による表現が使われることが多い。元来は分散システム上で統制なしに作成できる識別子として設計されており、したがって将来にわたって重複や偶然の一致が起こらない前提で用いることができる。

UUIDだと実現できない一意性と順序を含むIDを生成するのに手段がいろいろ考えられて実装されています。

Facebook, Twitter, Instagram等がどうやってIDを生成しているのかまとめ - Qiita
https://qiita.com/daisy1754/items/98a6e6b17d8161eab081

そのなかで、ulidというUUIDと互換性があり、ミリ秒単位で時系列ソートができるライブラリがありました。

ulidとは

ulid/spec: The canonical spec for ulid
https://github.com/ulid/spec

Universally Unique Lexicographically Sortable Identifier
Google翻訳すると「普遍的にユニークな辞書的に分類可能な識別子」となります。

上記は仕様を提示したリポジトリとなっており、各言語のライブラリを有志が実装している感じです。

128-bit compatibility with UUID

1.21e+24 unique ULIDs per millisecond

Lexicographically sortable!

Canonically encoded as a 26 character string, as opposed to the 36 character UUID

Uses Crockford's base32 for better efficiency and readability (5 bits per character)

Case insensitive

No special characters (URL safe)

Monotonic sort order (correctly detects and handles the same millisecond)

(Google翻訳)

UUIDとの128ビット互換性

1ミリ秒あたり1.21e + 24の一意のULID

辞書式にソート可能

36文字のUUIDとは対照的に、標準的に26文字の文字列としてエンコードされます。

効率性と読みやすさのためにCrockfordのbase32を使用します（1文字あたり5ビット）

大文字小文字を区別しません

特殊文字なし（URLセーフ）

単調ソート順（同じミリ秒を正しく検出して処理します）

同一ミリ秒内での生成でも、同じミリ秒内に2^80 を超えない限り、ソート順が保証されるみたいで、良さそうです。

UUID(v4)だと16進表記RRRRRRRR-RRRR-4RRR-rRRR-RRRRRRRRRRRR に対してulidは32進表記0123456789ABCDEFGHJKMNPQRSTVWXYZ になります。

タイムスタンプ部とランダム部で構成されており、タイムスタンプ部は西暦10889年まで利用できるとのこと。

Timestamp

48 bit integer

UNIX-time in milliseconds

Won't run out of space till the year 10889 AD.

Randomness

80 bits

Cryptographically secure source of randomness, if possible

(Google翻訳)

タイムスタンプ

48ビット整数

UNIX時間（ミリ秒）

西暦10889年までスペースが不足することはありません。

ランダムネス

80ビット

可能であれば、暗号的に安全な乱数の発生源

ランダム部は80ビットとのことなので、UUID(v4)の122ビットより下回りますが、既存のIDとぶつかるまでの回数の期待値はUUID(v4)に劣りますが、タイムスタンプ部と合わせると問題なさそうです。期待値の計算は下記を参考にさせてもらいました。

UUID(v4) がぶつかる可能性を考えなくていい理由 - Qiita
https://qiita.com/ta_ta_ta_miya/items/1f8f71db3c1bf2dfb7ea

UUID

2^{122/2} = 2,305,843,009,213,693,952回

ulid

2^{80/2}  =         1,099,511,627,776回

UUID - Wikipedia
https://ja.wikipedia.org/wiki/UUID

Base32 Encoding
http://www.crockford.com/wrmg/base32.html

使ってみる

ドキュメントにあるPythonの実装を実際に使ってみました。

ahawker/ulid: Universally Unique Lexicographically Sortable Identifier (ULID) in Python 3
https://github.com/ahawker/ulid

仮想環境内でライブラリをインストールします。

> python --version
Python 3.6.6

> mkdir 任意のディレクトリ
> cd 任意のディレクトリ
> python -m venv venv
> . venv/bin/activate
> pip install ulid-py
(略)
Successfully installed ulid-py-0.0.7

上記ライブラリのREADMEのUsageにあるとおりですが、ひととおりお試し。

> python
>>> import ulid
>>> id1 = ulid.new()
>>> id1
<ULID('01D0KDBRASGD5HRSNDCKA0AH53')>
>>> id2 = ulid.new()
>>> id2
<ULID('01D0KDBXEQ15ZT4DDME6CNT39P')>

文字列としても簡単に扱えます。

>>> id1.str
'01D0KDBRASGD5HRSNDCKA0AH53'
>>> id2.str
'01D0KDBXEQ15ZT4DDME6CNT39P'

時間情報を含むため、タイムスタンプも取得できます。

>>> id1.timestamp()
<Timestamp('01D0KDBRAS')>
>>> id1.timestamp().datetime
datetime.datetime(2019, 1, 7, 5, 42, 57, 625000)
>>> id2.timestamp()
<Timestamp('01D0KDBXEQ')>
>>> id2.timestamp().datetime
datetime.datetime(2019, 1, 7, 5, 43, 2, 871000)

当然ながら比較・ソート可能です。

>>> id1 < id2
True
>>> [u for u in sorted([id2, id1])]
[<ULID('01D0KDBRASGD5HRSNDCKA0AH53')>, <ULID('01D0KDBXEQ15ZT4DDME6CNT39P')>]

UUID互換なので、UUIDからulidを生成することもできます。
ただし、当然ながらUUIDは時間情報を含まないので、タイムスタンプはデタラメになります^^

>>> import uuid
>>> uuid4 = uuid.uuid4()
>>> uuid4
UUID('626f8162-66f2-4e44-84ba-2de3457693aa')
>>> id3 = ulid.from_uuid(uuid4)
>>> id3
<ULID('32DY0P4SQJ9S289EHDWD2QD4XA')>
>>> id3.timestamp()
<Timestamp('32DY0P4SQJ')>
>>> id3.timestamp().datetime
datetime.datetime(5399, 9, 15, 5, 0, 1, 650000)

便利ですねー^^

参考

UUID - Wikipedia
https://ja.wikipedia.org/wiki/UUID

Facebook, Twitter, Instagram等がどうやってIDを生成しているのかまとめ - Qiita
https://qiita.com/daisy1754/items/98a6e6b17d8161eab081

ulid/spec: The canonical spec for ulid
https://github.com/ulid/spec

Base32 Encoding
http://www.crockford.com/wrmg/base32.html

「Base N」encodingをまとめてみる。 - 學而時習之
http://bias.hateblo.jp/entry/20160209

三十二進法 - Wikipedia
https://ja.wikipedia.org/wiki/%E4%B8%89%E5%8D%81%E4%BA%8C%E9%80%B2%E6%B3%95#Base32

ahawker/ulid: Universally Unique Lexicographically Sortable Identifier (ULID) in Python 3
https://github.com/ahawker/ulid

UUID(v4) がぶつかる可能性を考えなくていい理由 - Qiita
https://qiita.com/ta_ta_ta_miya/items/1f8f71db3c1bf2dfb7ea