Edited at

ID生成方法についてあれこれ

ID生成について聞かれることが多いので、独自の観点でまとめてみます。タイトルは適当です…。

DBはMySQL(InnoDB)を想定しています。あしからず。


ID生成を知りたいなら

ID生成に関しては以下の記事がよく纏まっているので参考にしてみてください。値形式など詳しく書かれています。


ID生成方法

以下のID生成方法は、お手軽に採用しやすいもの順で列挙します。


DB採番/連番型


AUTO_INCREMENT

DBのAUTO_INCREMENTで採番する方法。


Pros


  • 数値型で扱える


    • 普通は64ビットの整数型を採用することが多い



  • 単調増加する連番なので、ソート可能でかつインデックスの空間効率がよい

  • 単調増加するので、キャパシティを予測しやすい


    • 64ビットあればあまり気にすることもないと思うが…




Cons


  • DBとのネットワークI/O、DBでのディスクI/O分のレイテンシーを想定する必要がある、まぁ当然ですが…

  • ID生成がDB(Master)1台に依存するので、SPoFになりやすい


    • DB依存のアプリケーションならこのSPoFは想定内ではあると思います



  • 保存前にエンティティのIDを確定できず、IDに値があるかないかという判定ロジックが煩雑になりがち(初期値が未定問題)


    • AUTO_INCREMENTのため(書き込み側の都合)に User#idがOption[Long] を採用した場合は、読み込み側では必ず値があるので邪魔になります。書き込み用と読み込み用のモデルをいちいち用意するもの大袈裟です。



case class User(id: Option[Long], name: String, ...)

object UserDao {
def findById(id: Long): Option[User] = ???
}

def getUserName(id: Long): Option[(Long, String)] = {
UserDao.findById(id).map { result =>
(result.id, result.name) // これは期待する戻り値と異なる型なのでコンパイルエラー。読み込み側に書き込み側の都合が影響する…。
}
}


  • 連番(/users/:idなど)はディレクトリスキャンやレコード数予測に使われる可能性がある。


    • これは対策する方法があります。後述します。




事前採番方式

AUTO_INCREMENTの初期値が未定問題だけを 事前採番 で改善する方式(その他のConsは改善されません)。一般的に事前採番であればシーケンスを使うと思います。PostgreSQLなら使えますね。MySQLでは以下のように採番テーブルを用意しLAST_INSERT_IDを使うと採番可能です(ストレージエンジンはMyISAM)。

CREATE TABLE `user_id_seq`(id bigint unsigned NOT NULL) ENGINE=MyISAM;

UPDATE user_id_seq SET id = LAST_INSERT_ID(id+1)

SELECT LAST_INSERT_ID() AS id

こちらの記事も参考してください。


Pros


  • 初期値未定問題を回避できる

  • 数値型で扱える

  • 単調増加する連番なので、ソート可能でかつインデックスの空間効率がよい

  • 単調増加するので、キャパシティを予測しやすい


Cons


  • AUTO_INCREMENTと比べるとI/O回数が増えてしまう

  • DBとのネットワークI/O、DBでのディスクI/O分のレイテンシーを想定する必要がある。

  • ID生成がDB(Master)1台に依存するので、SPoFになりやすい

  • 連番(/users/:idなど)はディレクトリスキャンやレコード数予測に使われる可能性がある。これは対策する方法が(ry


連番型 + Hashids

ID生成とは直接関係ないですが、連番型で生成したIDをHashidsを使うとハッシュ値として隠蔽できます。IDとハッシュ値を変換テーブルを用意することなく相互に変換可能です。クエリのID条件にはデコードした数値が使えます。

val hashids = new Hashids("this is my salt")

val id = hashids.encode(1) // 1 -> gB0NV05e
val number = hashids.decode(id) // gB0NV05e -> 1

Pros/Consは、連番を隠蔽できる以外は上述と同じなので省略。


非DB採番/文字列型


UUID

仕様としてはv1~v5までありますが、よく使われるのはv1かv4あたり。

UUID version1の生成アルゴリズムをみると分かりますが、まずタイムスタンプは下位と上位が逆転しているのと、ランダム成分が含まれる場合があるので、ソートは不能と考えてよいです。UUID v4の形式はそもそもランダム成分なのでソート不能です。


Pros


  • ディスクやネットワークを使わずに、各アプリケーション内でID生成できるので、スケールしやすい&SPoFがない


Cons


  • 数値型(64bit Longなど)で扱えない(128bitを文字列型として扱う)

  • 乱数成分の影響で、ソート不能でかつインデックスの空間効率が悪い

  • MySQL(InnoDB)で100万件以上扱う場合は、INSERT時間のペナルティが大きくなります(以下に詳しく述べます)


プライマリキーにUUIDを採用した場合のINSERT時間のペナルティ

とりあえず、プライマリキーにUUIDを指定した場合の実験結果を示す、以下の記事をみましょう。1

最初の二つのグラフをみると、INSERT時間が増えていくことがわかります。レコード数が多くなるほどその影響は顕著になります。INSERT時間が遅くなる直接の原因は分からないですが…。

以下の記事も参考にあると思います。

過去に「性能劣化は2割程度」というどこかの記事を読んだことがありますが、2割ってかなり大きいです…。それなりの規模のデータを扱う場合は要注意ですね。

また、タイムシリーズでデータが読み書きされる場合、直近のデータに対するインデックスはインデックス空間上の近い位置(リーフ)に格納されていてほしいですが、UUIDだとソートできないのでインデックスの位置がフラグメントするというか、分散します。こういうケースだと、おそらくSELECTも非効率になるので要注意です。


ULID

上記のUUIDの欠点をカバーするのが、ULIDです。ULIDには乱数成分が含まれますが、先頭にタイムスタンプ成分があるのでソート可能です。詳しくは https://github.com/ulid/spec を参照してください。様々な言語向けの実装がありますが、ロジック自体は難しくないので対応していない言語でも移植は比較的容易だと思います。


Pros


  • ディスクやネットワークを使わずに、各アプリケーション内でID生成できるので、スケールしやすい&SPoFがない

  • UUIDと違って、先頭48bitを使ってソート可能(1ミリ秒以内に2^80を超えない限り)

  • MySQL(InnoDB)での空間効率は、UUIDよりよいはず、たぶん。(1ミリ秒以内に2^80を超えない限り)


Cons


  • 数値型で扱えない(文字列型として扱う)


非DB採番/数値型

DBを利用せずに64ビットLong型のIDを生成する方法があります。

ここからは少し話しがデカくなります。

こういう目的で利用されるのが分散IDワーカーです。僕の職場でも開発・運用されています。

もともとの実装は、twitter/snowflakeです。もうアーカイブされてから久しいですが。

IDの形式は以下です。


  • 41bit タイムスタンプ

  • 10bit マシンID (データセンタID + ワーカーID)

  • 12bit シーケンス


    • 1ミリ秒以内にタイムスタンプが重複する場合にカウントアップされる




Pros


  • 64bit整数値

  • 連続性がある(ソート可能およびインデックスの空間効率がよい)

  • SPoFがない(DBなどに頼らない)


Cons


  • IDワーカーのID管理が面倒(重複するとIDの重複に繋がる)


IDワーカーのID管理

snowflakeの実装はアプリケーション内で利用することができますが、ワーカーIDが5ビットなので32インスタンスまでしか作れません。つまり、インプロセスでID生成器を使った場合は、そのプロセスは32インスタンスまでしかスケールさせられないという制限を持つことになります…。2 まぁ、あまり好ましいとは言えないですね。

そもそもオートスケーリングな環境下でどのホストにどのワーカーIDを割り当てるか? そのインスタンスが突然死した場合ワーカーIDを再利用させるか、など様々な分散環境でのリソース管理の問題がでてきます。こういった課題をsnowflakeではzookeeperを使って解決しています(ウチもzookeeperで管理してます)

zookeeperを使う方法以外には、 JVM限定の話になりますが、akka-cluster を使ってワーカーIDを管理する方法もあります。どちらもハードルは高いですが…。実装例は以下です。

詳しくは以下の資料を参考にしてください。

送信するコマンドメッセージにワーカーIDを含めると、対応するワーカーIDのIDワーカーアクターにメッセージが届くという仕組みです。このアクターは起動していなければ自動的に起動し、 akka-cluster-sharding によってノード上に自動的に分散されます。

https://github.com/TanUkkii007/reactive-snowflake/blob/master/reactive-snowflake-cluster/src/main/scala/org/tanukkii/reactive/snowflake/ShardedIdRouter.scala#L31-L37


TanUkkii007(たぬっきーパイセン)の実装で面白いところ

他にも工夫がされている点があります。1ミリ秒あたり2^12まで採番できるが、twitterの実装ではシーケンスが桁溢れすると次のタイムスタンプまでブロックする。しかし、reactive-snowflakeでは、採番できなかったものとし自分自身のアクターにリトライメッセージを送信し再度採番するようになっている。つまりブロッキングしないようになっている。


まとめ


  • DB採番/数値型


    • ID生成がDBに依存する

    • ソート可能な数値型IDを生成できる

    • 性能を問われる大量のリクエストには向いていない


      • ID生成時にネットワークやディスクのI/Oが生じる

      • ID生成器=DB(Master)1台なのでボトルネックが生じやすい





  • 非DB採番/文字列型


    • ID生成がDBに依存しない

    • 文字列型IDをアプリケーション内で分散して生成できる

    • UUIDはソート不能だが、ULIDはソート可能なIDを生成できる



  • 非DB採番/数値型(分散IDワーカー)


    • ID生成がDBに依存しない

    • ソート可能な数値型IDを特定のノードで分散して生成できる


      • ID生成器を外部ノード上に配置した場合は、アプリケーションからはネットワークI/Oは生じる



    • IDワーカーIDを管理する仕組みが必要



以下のような条件に合致するなら、ULIDで十分でしょう。


  • IDは数値型でなくてよい

  • ソート可能

  • 分散してID生成可能(SPoFがない)

  • 大掛かりな仕組みが必要ない





  1. UUIDのバージョンは不明ですが、乱数成分が原因ではないかと思います。 



  2. データセンターIDをうまく使えばもっと多いインスタンスを立ち上げれますが、いずれにしても上限はあまり考えたくない…。