MySQLでもULIDを発行した〜い！ので検証してみた

どうもみなさんはじめまして、2023年3月入社の id:convto です。
7月はLayerXエンジニアブログを活発にしよう月間ということらしく、その一環で個人的に調査・検討していた内容で一本書いたろうかなということで筆を取らせていただきました。

ちょっと遅刻しちゃいましたが許してください。

モチベーション

ULIDはmsec単位でsort可能な性質を持っていて、かつ多くのユースケースにとって十分な採番能力をもっているIDです。

ですが、たとえばDML実行などでSQLから生成できなくて困る場合があります。
ULIDはすこし特徴のあるencodingを使っていたりする都合でDMLでの生成が難しく、素直にやるとアプリケーション側でID生成処理を書く必要があります。なんとかならないかといろいろとやり方を検討したかたもいらっしゃるのではないでしょうか。(N敗)

そこで、SQL経由でのULID生成について検討してみます。

まずはULIDの仕様について確認し、その後MySQLでの実装について考えてみます。

ULIDの仕様を見てみる

specは GitHub上で管理されています。

構成

ULIDは以下のように構成される128bitのIDです。

0                   1                   2                   3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      32_bit_uint_time_high                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     16_bit_uint_time_low      |       16_bit_uint_random      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       32_bit_uint_random                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       32_bit_uint_random                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

ようするに前半48bitがmsec精度unix timestamp, 後半80bitが疑似乱数という構成です。

monotonic counter

一応仕様では単位時間に激しく採番するようなワークロードも考慮していて、msec単位で複数の採番があった場合、末尾をmonotonic counterにするような挙動もサポートされています。

https://github.com/ulid/spec/blob/d0c7170df4517939e70129b4d6462cc162f2d5bf/README.md#monotonicity

When generating a ULID within the same millisecond, we can provide some guarantees regarding sort order. Namely, if the same millisecond is detected, the random component is incremented by 1 bit in the least significant bit position (with carrying).

最近策定されるこういう系のIDの仕様は timestamp + 一定以上のrandom + 単位時間の大量発行のためのcounter を仕様でサポートするケースが多いですね。

specからリンクされてるいくつかの言語のULID実装を見たところ、実装ではoptionとしてmonotonic counterをonにできるようなパターンが多かったです。単位時間の採番が多くないワークロードがメインのユーザーにとっては性能が落ちるわけだしそれはそうねという感じでした。

あと、採番の主体者が複数いた場合のmonotonic counterの同期などは考慮していない実装が多かったです。(ライブラリなのでしょうがない部分があるのと、そもそも同期するなり合意取るなりしてる間にmsec過ぎそうだしでそうだねとなった) まあ実用上は十分でしょうという感じだと思われます。

採番能力としてはmonotonic counterを考慮するとmsec単位で80bitで約1.2e+24(1.2𥝱)くらいの採番能力があります。

monotonic counterを信頼しないとしても要は誕生日攻撃などと同じなので任意の衝突確率のときの採番数は概算できて、よくID生成の文脈で比較される衝突確率50%くらいの採番数で考えると

$2 ^ {n/2}$

でおおよその値が求められます。(nはrandom bit数)(詳細が気になる人は https://auth0.com/blog/birthday-attacks-collisions-and-password-strength/ あたりを読むと面白いかも)

ULIDの場合はだいたい1兆くらいで、monotonic counterを考慮しなかったとしても、実用上はmsec単位の採番量がとんでもなく多いケース以外は衝突する可能性は低いとみなして良いと思います。(それもあって多くの実装ではoption提供してるのだとおもわれる)

encoding

ULIDは Crockford's Base32 でエンコードされます。

これは I, L, O, U の見間違えやすい文字を抜いた32文字でなるエンコーディングです。利用可能文字は

0123456789ABCDEFGHJKMNPQRSTVWXYZ

となっていて、一文字あたり5bitを表現できるエンコーディングになっています。

MySQLでどのように生成するか

MySQLではstored functionの登録が可能なので、そこに登録する関数を作ることを目標とします。(UDFなどでも自作関数を登録できますが、マネージドサービスで動くMySQLなども考えると考慮することが多そうなので今回は検討しません)

また、今回は検証の簡単のためにmonotonic counterについての仕様は考慮しないこととします。それでも十分な採番能力なので、完全な仕様準拠ではないですが多くのユースケースで困ることはなさそうにおもいます。

Crockford's Base32 のエンコーディングが一番難しそうな部分で、byte単位で整列していないのでいくつかのキリのいいブロックに分けつつ文字列に変換することになりそうです。

まずはhexで生成してみる

今回の検証ではmonotonic counterは取り扱わないので、純粋に

48bit msec unix timestamp
80bit random

を生成することを目的にします。

今回はまずはじめにhexで作ってみて、そのあとエンコーディングを考慮した実装にするようなステップですすめていきます。

最初はmsec unixtimestampを取得することを考えます。mysqlには UNIX_TIMESTAMP 関数がありますが、デフォルトだとsec精度で、追加で精度の指定ができません。

そのかわり渡された日付が秒以下の精度を持っていたときはそれを引き継ぐ挙動であることが記載されています。なのでmsec精度のunix timestampは以下のように取得できます。(扱いやすさのために1000でかけてFLOORしています)

FLOOR(UNIX_TIMESTAMP(CURRENT_TIMESTAMP(4))*1000)

あとは任意の基数変換をしつつ、48bitになるようにpaddingをとればよいです。たとえばhexなら12文字ほしいので以下のように書けば足りない分のpaddingがとれます。

LPAD(HEX(FLOOR(UNIX_TIMESTAMP(CURRENT_TIMESTAMP(4))*1000)), 12, '0')

また、random取得も標準で RONDOM_BYTES 関数が準備されています。SSLで生成した乱数をつかっているというのを明示していて、一定信頼できる乱数ソースではありそう。これを使ってhexをとると

HEX(RANDOM_BYTES(10))

とできます。あとは繋げて

CONCAT(
  LPAD(HEX(FLOOR(UNIX_TIMESTAMP(CURRENT_TIMESTAMP(4))*1000)), 12, '0'),
  HEX(RANDOM_BYTES(10))
)

で生成できます。

ここまでで一旦stored functionに登録してみると、

CREATE FUNCTION gen_ulid_hex ()
RETURNS CHAR(32) DETERMINISTIC
RETURN CONCAT(
  LPAD(HEX(FLOOR(UNIX_TIMESTAMP(CURRENT_TIMESTAMP(4))*1000)), 12, '0'),
  HEX(RANDOM_BYTES(10))
);

SELECT gen_ulid_hex();
-- > 01894EDF16E25687CB8CC32524B49DA6

となり、無事それっぽい出力がなされていそうです。

Crockford's Base32 encode

ここからが山場です。base32 encode して出力していきます。

encode時のブロック分け

実装にあたっていくつかの言語のライブラリの実装を読み歩いて気づいたんですが、ULIDは以下二つのブロックに分けてencodeしてるようです

timestamp 10char
random 16char

base32は1charあたり5bit表現できるので、timestampに割り当てられてる10 charは本来50bitぶん表現できます。timestamp は値としては48bitしか入っていないので、2bitぶんの表現容量を無駄にしていることになります。

この部分ちょっと勿体なく思うかもしれないんですが、そもそもULID自体が128bit(16byte)で5で割り切れないため、すこしオーバーして130bitを表現できる26 charとしてencodeせざるえません。
(なんでそんな割り切れないややこしいencoding使うねんという話はそうなんですが、hexに比べたら無駄bitを考慮しても20%以上文字数削減できるのでやる意義はある)

どうせ2bit余ってるから、せっかくだからキリのいいtimestampとrandomの分け目で消費しようっちゅー話なんでしょう。ここをちゃんとわけないと境界の文字は時刻と乱数が混ざってmsec単位のsortの信頼性に響くし、しっかりうまくやってるんだなぁという気持ちになりました。

これはundocumentedなので実装読んだときの面白ポイントの一つでした。

mysqlではもろもろの算術演算が64bitまでなことが多いので、

50bit(timestamp 48bit あまり 2bit)
40bit(random 前半)
40bit(random 後半)

みたいな感じで処理するようにしてみます。

encode処理

これはちょっと方針がむずいんですが、わかりやすさ優先ということで32でMODとって1文字ずつbase32として評価する方針でやってみます。 (もしかしたらunrollとかすると効果あるかもだけど、計測する前からこねるのも微妙なので今回は素朴にやります)

まずはencode処理に着目し、64bit以下の任意の長さの数値を与えた時に Crockford's Base32 encode する処理を考えます。

今回は素朴にやっていくので、末尾5bitを評価して Base32 char として結果に詰めて、5bit 右にshiftする処理をループすれば良いでしょう。
DIVとMODを使えばこの操作は実現できます。

ほしいサイズに満たなかったらpadをつめるような挙動もあると便利なので、期待する文字長も渡せるようにしてみます。

MySQLでやると以下のようになります。

DELIMITER //
CREATE FUNCTION to_crockford_b32 (src BIGINT, encoded_len INT)
RETURNS TEXT DETERMINISTIC
BEGIN
  DECLARE result TEXT DEFAULT '';
  DECLARE b32char CHAR(32) DEFAULT '0123456789ABCDEFGHJKMNPQRSTVWXYZ';
  DECLARE i INT DEFAULT 0;

  ENCODE: LOOP
    SET i = i + 1;
    SET result = CONCAT(SUBSTRING(b32char, (src MOD 32)+1, 1), result);
    SET src = src DIV 32;
    IF i < encoded_len THEN
      ITERATE ENCODE;
    END IF;
    LEAVE ENCODE;
  END LOOP ENCODE;

  RETURN result;
END; //
DELIMITER ;

これを使ってみると以下のような感じになります

SELECT to_crockford_b32(2000, 5);
-- > 001YG

うまく動いていそうです。

ID生成！

さいごに、encode処理に先ほど説明した

50bit(timestamp 48bit あまり 2bit)
40bit(random 前半)
40bit(random 後半)

のブロック分けした値を渡していく処理を作ります。

DELIMITER //
CREATE FUNCTION gen_ulid ()
RETURNS CHAR(26) NOT DETERMINISTIC
BEGIN
  DECLARE msec_ts BIGINT DEFAULT FLOOR(UNIX_TIMESTAMP(CURRENT_TIMESTAMP(4)) * 1000);
  DECLARE rand CHAR(20) DEFAULT HEX(RANDOM_BYTES(10));
  DECLARE rand_first BIGINT DEFAULT CONV(SUBSTRING(rand, 1, 10), 16, 10);
  DECLARE rand_last BIGINT DEFAULT CONV(SUBSTRING(rand, 11, 10), 16, 10);
  RETURN CONCAT(
    to_crockford_b32(msec_ts, 10),
    to_crockford_b32(rand_first, 8),
    to_crockford_b32(rand_last, 8)
  );
END; //
DELIMITER ;

とりまわしのためにRONDOM_BYTES()の結果は先ほどと同じく一度HEXで受け取っています。裏側は/dev/urandomあたりへのアクセスな気がするので、大差なさそうですが一応1回でとってくるようにしています。

で、これを使ってみます

SELECT gen_ulid();
-- > 01H57VAB8TH98GR0T1WPT8SM04

26文字のいかにもそれっぽい文字列が出力されました！！

正しい形式のULIDなら既存ツールを用いて時刻を取り出せるはずなので試してみます。

https://github.com/oklog/ulid のコマンドラインツールで生成されたIDを評価してみます。

$ ulid 01H57VAB8TH98GR0T1WPT8SM04
Thu Jul 13 14:43:40.954 UTC 2023

発行時刻と一致する結果が得られ、またmsec精度の値が埋め込まれていることが確認できます！わいわい

感想とか今後の展望とか

今回はまずは検証ということで、現実的にMySQLでULIDの発行はできるのか検討してみました。
いろいろ手を動かしてみた感じ、整理すれば割と現実的だなという手応えでした。この記事を書き始めた時の当初の目的は達成できたので満足しています。

また stored function の仕組みを使えば管理も難しくなさそうなので、この方向はすこし可能性を感じました。

とはいえまだPoCであり、今回は一切パフォーマンス計測などしていないので、いくつかのアプローチ比較してベンチマークとかもとりたいですね！

また、monotonic counter周りについても考慮していないので、単位時間の採番が多いユースケース向けにSQLでできることはないか考えてみるのも面白そうです。(monotonic counterには排他制御が絡むので、いろいろな手段を比較してどのように実現するか考える必要がありそう)

未検証な内容もまだまだありますが、手を動かして解像度も上がったのでとても良かったです！

LayerX エンジニアブログ

LayerX のエンジニアブログです。