まえがき
データにIDを持たせたいとき、単純な方法としては、DBの提供するauto incrementを使う場合やUUIDを利用することがある。それぞれの方法の利点欠点は以下の通り。
データベースのauto incrementを使う場合
利点:
特別な実装が必要ない
欠点:
DBを1台で運用するとデータベースがパフォーマンス・障害のボトルネックになる
DBを二台にするとIDのユニークさや順序の保証が困難
UUID(v4)※1を利用する場合
利点:
分散環境で各々がIDを生成しても衝突しない
IDを公開したくない場合に、推測されにくいIDを生成できる
欠点:
128ビット必要、DBのインデクシングやプログラミング言語で扱うときに不利なことがある
IDから時間の情報が失われる、例えば2つのIDを比べてどちらが古い投稿か判断できない
世界の大企業がどうしてるか
調べてみると多くの企業がブログなどで自分たちのやり方を公開していた。
大きく分けて２通りの方法があった
- Twitterのsnowflakeに端を発するタイムスタンプから一意なIDを生成する方法
- Facebook, FlickrのDBごとに利用できる値の範囲を区切った上でauto incrementを利用する方法
各社のやり方を以下にまとめる。
snowflakeをOSSとして公開 (現在は非公開)
タイムスタンプに基づいて一意なIDを生成するためのプログラム、専用サーバーでの動作を想定
日本語解説スライド
タイムスタンプ、マシンID, 同一マシン内でのシーケンスIDを元に64ビットの一意なIDを生成
- IDから時系列比較可能
- IDから時間の復元が可能
- 69年でオーバーフロー
SmartNews
Twitterのsnowflakeを参考にRedis+Luaでshakeflakeを開発し運用
http://instagram-engineering.tumblr.com/post/10853187575/sharding-ids-at-instagram
Twitterのsnowflakeを参考にPL/PGSQL (PostgreSQLでサポートされるプログラミング言語)で独自に実装
DBのテーブルをいくつかの論理的なshardに分けた上で
- タイムスタンプ
- テーブルのshard ID
- 同一テーブル内でのauto incrementする値のmod
をもとに64bitの数を生成
Flickr
http://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/
Ticket serverというのを運用している
これはMySQLのauto increment機能を使ってユニークなIDを発行する専用のサーバー
MySQLのreplace intoクエリを使って、DB上の一つのデータをひたすら上書きしつつ、auto incrementされたIDのみを取得
負荷分散のために2台のticket serverをround robinで回している
2台のticket serverはそれぞれ偶数と奇数を担当
結構単純というか愚直っぽい戦略。"dumbest possible thing that will work (動作する最も単純なやり方)"というFlickrのモットーの現れなんだ、とのこと
分散環境に対応できるように、MySQLサーバがあらかじめ利用できるIDのプールを持っておく、その上でauto_incrementを利用
出典: QuoraでHarrison Fisk (FBのDBパフォーマンスチーム所属)が回答
注釈
※1. 投稿時には単にUUIDとしれっと書いてましたが、UUIDは1から5までのバージョンがあり、バージョンごとに特性が異なります。
rubyのSecureRandom.uuidはversion 4のUUIDを返すため、暗にv4を想定した書き方になってましたが、
UUID v1は時間とMACアドレスを元にIDを生成するため、上記のInstagramの方法などと近く、
ランダム性がなく時間の情報を残した形になっています
↩