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

ID生成について聞かれることが多いので、独自の観点でまとめてみます。タイトルは適当です…。
DBはMySQL(InnoDB)を想定しています。あしからず。

ID生成を知りたいなら

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

• ID生成大全
• Facebook, Twitter, Instagram等がどうやってIDを生成しているのか まとめ

ID生成方法

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

DB採番/連番型

AUTO_INCREMENT

DBのAUTO_INCREMENTで採番する方法。

Pros

• 数値型で扱える
  • 普通は64ビットの整数型を採用することが多い
• 単調増加する連番ですので、ソート可能でかつインデックスの空間効率がよい
• 単調増加するので、キャパシティを予測しやすい
  • 64ビットあればあまり気にする必要はなさそう

Cons

• DBとのネットワークI/O、DBでのディスクI/O分のレイテンシを想定する必要がある、まぁ当然ですが…
• ID生成がDB(ライター)1台に依存するので、SPoFになりやすい
  • DB依存のアプリケーションならこのSPoFは想定内ではある
• AUTO_INCREMENTの性質上、複数DBで採番するとIDが重複するため、DBを2台以上にできない。
• 保存前にエンティティのIDを確定できず、IDに値があるかないかという判定ロジックが煩雑になりがち(初期値が未定問題)
  • AUTO_INCREMENTのため(書き込み側の都合)にUserAccount#idがOption[Long]を採用した場合は、読み込み側では必ず値があるので邪魔になります。書き込み用と読み込み用のモデルをいちいち用意するもの大袈裟です。

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

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

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

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

• MySQL で採番テーブル

Pros

• 初期値未定問題を回避できる
• 数値型で扱える
• 単調増加する連番ですので、ソート可能でかつインデックスの空間効率がよい
• 単調増加するので、キャパシティを予測しやすい

Cons

• AUTO_INCREMENTと比べるとI/O回数が増えてしまう
• DBとのネットワークI/O、DBでのディスクI/O分のレイテンシを想定する必要がある。
• ID生成がDB(ライター)1台に依存するので、SPoFになりやすい
• 連番の性質上、複数DBで採番するとIDが重複するため、DBを2台以上にできない。
• 連番(/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]

• MySQL InnoDB Primary Key Choice: GUID/UUID vs Integer Insert Performance

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

以下の記事も参考になる

• MySQL InnoDBの介在する大規模サービスにおけるID生成戦略について

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

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

ULID

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

• ソート可能なUUID互換のulidが便利そう

Pros

• ディスクやネットワークを使わずに、各アプリケーション内でID生成できるので、スケールしやすい＆SPoFがない
• UUIDと違って、先頭48bitを使ってソート可能(１ミリ秒以内に2^80を超えない限り)
• MySQL(InnoDB)での空間効率は、UUIDよりよいはず、たぶん。(１ミリ秒以内に2^80を超えない限り)

Cons

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

非DB採番/数値型

DBを利用せずに64ビットLong型のIDを生成する方法があります。
ここからは少し話しがデカくなります。

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

• Scalaを用いて分散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インスタンスまでしかスケールさせられないという制限を持つことになります…。[^ワーカ-instance-num] まぁ、あまり好ましいとは言えないですね。

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

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

• TanUkkii007/reactive-snowflake

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

• スケールするシステムにおけるエンティティの扱いと 分散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(ライター)1台なのでボトルネックが生じやすい
• 非DB採番/文字列型
  • ID生成がDBに依存しない
  • 文字列型IDをアプリケーション内で分散して生成できる
  • UUIDはソート不能だが、ULIDはソート可能なIDを生成できる
• 非DB採番/数値型(分散IDワーカ)
  • ID生成がDBに依存しない
  • ソート可能な数値型IDを特定のノードで分散して生成できる
    • ID生成器を外部ノード上に配置した場合は、アプリケーションからはネットワークI/Oは生じる
  • IDワーカIDを管理するしくみが必要

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

• IDは数値型でなくてよい
• ソート可能
• 分散してID生成可能(SPoFがない)
• おおがかりなしくみが必要ない

脚注

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