ソート可能な UUID を生成する ksuid を試してみる。

こんにちは k-jun です。今日は UUID のユニーク性を持ちながら、ソート可能な値を生成する ksuid を試してみます。

https://github.com/segmentio/ksuid

特徴としては以下の３つが挙げられており、Unix の sort コマンドでソートしてあげると生成順に並ぶようです。

  • Naturally ordered by generation time
  • Collision-free, coordination-free, dependency-free
  • Highly portable representations

よく似ているものとして ULID があるのでこちらとも以下の点を比較してみます。

  • データ型の取り回し
  • 生成速度

Logic

Binary KSUIDs are 20-bytes: a 32-bit unsigned integer UTC timestamp and a 128-bit randomly generated payload. The timestamp uses big-endian encoding, to support lexicographic sorting. The timestamp epoch is adjusted to May 13th, 2014, providing over 100 years of life. The payload is generated by a cryptographically-strong pseudorandom number generator.

32-bit 分の timestamp と 128-bit 分のランダムな payload で値を生成しているようです。先頭の箇所が timestamp であれば確かに生成順にソートは可能ですね。

UUID の生成方法も見てみると、128-bit で構成されるようなので KSUID は純粋に UUID の先頭に timestamp をつけた形式となりそうです。

ULID はどうでしょうか...?

README.md の図を参照すると、どうやら 48-bit 分の timestamp と、80-bit 分のランダムな payload で構成されるようです。

if the same millisecond is detected, the random component is incremented by 1 bit in the least significant bit position (with carrying). For example:

また、同じ millisecond に生成された ID に関しても順序を担保するべく、Random 関数が同じ milisecond に呼ばれたことを検知し、1 bit だけずらした ID を生成するようです。

同じ millisecond に生成された ID に関しての言及は自分が見た限りでは ksuid には見られないので、この点は ULID の方が信用できそうです。(記述あったらごめんなさい...) UUID v4 をそのままくっつけていそうなので、ここの順序性は気にしていないのかもしれません。

Install & Example

適当にインストールして使ってみます。

$ go install github.com/segmentio/ksuid/cmd/ksuid@latest
$ ksuid
1xJnDtfrgJucdg1AH3WJ3L1aHsV

同じ millisecond で ID を生成するのもなかなか難しそうです。

$ ksuid -n 3
1xJnHJ519QoMtt7v3Mo5XRfwcdn
1xJnHNjEekqR3EuhrrqVt6Ah4fj
1xJnHNUvkw0TBs7OnkmOpM4MMKC

inspect で timestamp を見ることもできるみたいです。

$ ksuid -f inspect 1xJnHJ519QoMtt7v3Mo5XRfwcdn


REPRESENTATION:

  String: 1xJnHJ519QoMtt7v3Mo5XRfwcdn
     Raw: 0DB6C5B13F4FD9C482CD769FFFA7D7D87F91A35B

COMPONENTS:

       Time: 2021-08-28 01:32:49 +0900 JST
  Timestamp: 230081969
    Payload: 3F4FD9C482CD769FFFA7D7D87F91A35B

Compirison

では、ULID と比較してみましょう。ULID の方も Install & Example

$ go get -v github.com/oklog/ulid/v2/cmd/ulid
$ ulid
01FE47GTB519KKW38PWC5TCQ6K

比較は普通に ID を cli で生成してみて、総実行時間を計測します。

ksuid

$ time bash -c 'for i in {1..10000}; do ksuid > /dev/null; done'
bash -c 'for i in {1..10000}; do ksuid > /dev/null; done'  13.98s user 12.55s system 86% cpu 30.714 total

ULID

$ time bash -c 'for i in {1..10000}; do ulid > /dev/null; done'
bash -c 'for i in {1..10000}; do ulid > /dev/null; done'  13.50s user 11.82s system 86% cpu 29.413 total

ほとんど差がない...。Performance はそこまで差分が無いんでしょうね... まあ乱数生成して timestamp くっつけるだけですしおすし。

データの取り回し

取り回しも ULID のほうが楽そうです。というのも、UUID と同じデータ長にしてくれているので、UUID 互換だからですね。

うーん、自分の比較ではどう考えても ULID のほうが便利そうです。必要になったら ULID を使いますかね...。 それでは今回はこのへんで。