【Kotlin】ロックフリー・一括生成に対してソート可能なUUID v7生成器を作った

状況

IDとしてUUID v4を使っているプロジェクトで、限定的な状況でIDをソート可能にしたくなりました。
ULIDやUUID v7の生成をサポートするいい感じのライブラリを探しましたが、要件上ロック周り¹が微妙っぽかったり、同一タイムスタンプで生成した場合に確率でエラーになりそう²だったりと、採用できそうなライブラリを見つけられませんでした。

そこで、java-uuid-generatorを参考に、ロックフリーかつ簡易なUUID v7生成器を作りました。
コードはKotlinですが、Javaでも問題なく再現できると思います。

一応それなりに調べて作ったつもりですが、何か問題など有ればコメント頂けると嬉しいです。

ソート可能なUUIDの生成処理とロックの関係

ソート可能なUUIDは、ざっくり言うと「タイムスタンプ + 乱数」で構成されます。

ここで、同一タイムスタンプで複数の生成が行われた場合、乱数部分しか違いが無くなって厳密な生成順でのソートが不可能になります。
UUID v7の要件的にもミリ秒精度が基本かつ同一タイムスタンプ生成内ソートをサポートするかは任意と定義されているようで、最近のマシンでは複数件一括生成するだけでこの問題に当たります。

これを避ける方法の1つとして、生成処理毎にロックして、同一タイムスタンプ内で複数回生成された際に何らかのシーケンシャル値をインクリメントするように生成するやり方が有ります。
ただし、ロックはコードの複雑化や性能低下につながるので、今回は採用しませんでした。

実際に作ったもの

実際に作った生成器は以下の通りです。
なるべく実装を簡易にしたかったため、以下の制約が有ります。

• 別の一括生成とソート順が保証されない
• 4096件までしか一括生成できない
• 全て同一タイムスタンプで生成した扱いになる

import java.security.SecureRandom
import java.util.*

object SortableUuidGenerator {
    private const val UUID_VERSION: Long = 7 shl 12
    // randomUUIDの生成処理を参考にした
    private val numberGenerator = SecureRandom()

    /**
     * 指定された件数のUUID v7を生成し、指定されたマッパー関数で変換したリストを返す
     * @param size 生成するUUIDの件数、シーケンシャル採番の都合で最大4096（12ビットの最大値）まで
     */
    // 上位64ビット:
    //   48ビット目まで: ミリ秒精度のタイムスタンプ
    //   49 ~ 52ビット目: UUIDバージョン
    //   53 ~ 64ビット目: シーケンシャル値
    // 下位64ビット: 乱数
    fun <T> generate(size: Int, mapper: (UUID) -> T): List<T> {
        if (size < 0) throw IllegalArgumentException("サイズは0以上を指定してください $size")
        // 最大4096件に絞ったのは簡単のため
        if (4096 < size) throw IllegalArgumentException("サイズは4096までで指定してください $size")
// 52ビット目まで

        val mostSigBitsBase: Long = System.currentTimeMillis().shl(16) or UUID_VERSION 

        return (0 until size).map { seq ->
            // 下位ビットがシーケンシャルなため、単純加算で書ける
            mapper(UUID(mostSigBitsBase + seq, numberGenerator.nextLong()))
        }
    }
}

以下詳細な解説をまとめます。

作成方針

今回のユースケースでは「一括生成内での順番さえ保持されていればOK（= 別の一括生成とソート順が保証されなくてOK）」でした。
つまり、一括生成処理内でシーケンシャル値を管理すれば、ロックしなくても実現できます。

ロック周りをちゃんと作り込んで厳密にするとか、より高精度なタイムスタンプ利用も考えましたが、要件に対して過剰性能な割に実装が複雑かつ検証も大変となるので、今回は見送りました。

mapperを渡せるようにしているのは、UUIDをラップする値オブジェクトを作りやすくするためです（つまり、不要なら消せます）。

このUUIDの構成

この生成機を使うと018f4d64-a9e0-7000-c5f1-34fa1d006225というようなUUIDが得られます。
これは以下のような構成になっています。

• 018f4d64-a9e0: System.currentTimeMillis()で取得したミリ秒精度のタイムスタンプ
• 7000:
  • 7はUUID v7を表すバージョン
  • 000はシーケンシャル値
• c5f1-34fa1d006225: 64ビット乱数

タイムスタンプの扱い

要件的に使いまわしても困らないため、1度採番したものをそのまま使う方針としました。
値の操作は以下のコードを参考にしました。

シーケンシャル値の扱い

以下のrand_a部分の16進数3桁を0 ~ fffのシーケンシャル値として利用しています。

「Batch UUID creation implementations MAY utilize a monotonic counter that increments for each UUID created during a given timestamp.」となっていたので、これでも仕様は満たせている認識です。

16進数3桁をそのままカウンタにした理由は以下の通りです。

• 4096件同時生成できれば一般的にもほぼ困らない
• 2桁や4桁にすると乱数生成や桁合わせが面倒だが、3桁なら諸々簡単

乱数の扱い

下位64ビットが乱数になります。
var部分の扱いが気になりましたが、「Random data for each new UUIDv7 generated for any remaining space.」となっており、java-uuid-generatorでも乱数で埋められていたため、問題無しと判断しました。

1. 作った方が早そうだったので厳密な検証はしていませんが、リアクティブスタックとReentrantLockの相性が悪そうという点を気にしました。 ↩

2. 具体的にはjava-uuid-generatorを使おうとしていましたが、シーケンシャルずらし処理がオーバーフローしうるように見える点を気にしました。 ↩