UUIDv7が解決するMySQLのプライマリキーに関するパフォーマンス問題

UUIDv7の標準仕様がもうすぐ策定されるようなので調べてみました。

UUIDとは

UUID（Universally Unique Identifiers）は、サーバーでの調整なしにクライアント側で自律的に生成できる一意かつ予測困難性を備えた識別子です。

連番整数（MySQLでのAUTO_INCREMENT）とは異なり、UUIDは分散データベースで全体的な一意性を保証するための調整が必要ないため、シャーディングされたデータベース環境では好まれます。

現在一般的に使用されているUUIDv4は122bitのランダム値から生成されます。完全にランダムであるため、時系列で順序づけすることはできません。
その一方で予測困難性については非常に優れています。

UUIDv4におけるMySQLでのパフォーマンス問題

MySQLにおいてUUIDv4をプライマリキーに設定するとパフォーマンスが劣化することが知られています。
以下でその理由を解説していきます。

MySQLのストレージエンジンであるInnodbにおいてプライマリキーはクラスタ化インデックスとしてB+ツリーに格納されます。
クラスタ化インデックスにおいては以下のようにB+ツリーのリーフノードに、そのキーに対応するレコード全体が格納されます。

参照　MySQLでプライマリキーをUUIDにする前に知っておいて欲しいこと

B+ツリーのリーフノードにおいてプライマリキーの値はソートされて格納されるため、プライマリキーの値がUUIDv4などの時系列順でないランダム値である場合、挿入のたびにB+ツリーの異なる位置に挿入されることとなります。

MySQLではバッファプールにデータの一部がキャッシュされていますが、このようにランダムにデータが挿入されるとデータの局所性が悪くなるため書き込み時、読み込み時のキャッシュヒット率が減少します。
キャッシュヒット率が減少するとディスクIOが増えるためパフォーマンスに悪影響を与えます。

UUIDv7

UUIDv4におけるパフォーマンス問題を解決するためには生成されるIDを時系列順にする必要があります。
一般的に時系列ソート可能なIDジェネレーター(ULIDやSnowflake等)では、生成されるIDの先頭にタイムスタンプを格納するという方法が用いられます。

UUIDv7においてこの手法が導入され、時系列ソート可能になりました。
構造としては以下のとおりです。

    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                           unix_ts_ms                          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |          unix_ts_ms           |  ver  |       rand_a          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |var|                        rand_b                             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                            rand_b                             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

ミリ秒精度以外にもマイクロ秒、ナノ秒精度を指定することも可能です。精度を上げるだけランダム性が減少します。

まとめ

MySQLにおいてUUIDv4を使用時にパフォーマンスが劣化する理由について解説しました。
UUIDv7では時系列順にソートが可能であるため、この問題を回避することが可能です。

参考資料

https://buildkite.com/blog/goodbye-integers-hello-uuids
https://asnokaze.hatenablog.com/entry/2021/04/28/030550