ID(採番)生成戦略

概要

RailsでSNS系サービスを作る時に、タイムライン型でページネーションを実現するためにはというメモ。
通常通りソートして、カウンティングするだけでは解決できなかった話と、解決策の話です。

結論

結論から言うとUUID　version1のような時間型で衝突しないid生成がなされていればOK。
あくまでRailsから外れずコード管理のみで考えた時に時系列で並ぶulidの実装に落ち着きました。
https://github.com/ulid/spec

実装の提案

兎にも角にも実装例を見せないと始まらないので、以下に落ち着きました。
cursor型ページネーションの実装になります。
https://gist.github.com/penguinwokrs/45a7cfed3c31698da9b3e2409d83cffe
キモの解説ですが、UUIDをつけてUUID同士を比較して超過以降を抽出しているだけです。

klass.where("`uuid` < '#{cursor}'") # cursorの部分もuuidです。

（...たったこれだけです...ulid...すごい...)

既存の問題

ツイッターのようなサービスでページネーション実装を考えた時に、作成時間を元にソートしてから20件ずつカウンティングすると、偶然にも同時刻でツイートされる可能性は大いにあるため、1ページ目と２ページ目に重複したツイート内容が出てくる可能性がある。
SQL的には、以下のような実装が対応として回避可能である。
Pagination(ページネーション)がずれる、抜ける問題を解決する

採用しなかった理由としては、以下の通りです。

• ミリ秒単位での制御が考慮されていない。
• SQL的にチューニングとメンテが厳しそう。（低コストでできる方法を実現させたかった）

参考文献

• Facebook, Twitter, Instagram等がどうやってIDを生成しているのか まとめ
• Pagination(ページネーション)がずれる、抜ける問題を解決する
• UUID_SHORT
• https://qiita.com/kawasima/items/6b0f47a60c9cb5ffb5c4

所感

大規模なサービスほどスケールする時にどうするかをすごく考えていて、参考なりますね。
MastodonはオープンソースとしてTwitterが作成したsnowflakeを採用していて良いと思ったが、実装をストアドプロシージャで管理していた。
snowflakeの実装はいいと思うが、専用サーバ用意したりストアドプロシージャは現代で考えるとコストが高く感じるのは自分だけだろうか。

トレンド的にGraqhQLがプロダクトへ投入され始めているので、こちらのEdgeとNodeも学んでいきたいところです。

P.S.
実装の提案で補足なのですが、headerの部分でgithubみたいにRFC風に則りやりたかったが、APIを利用する開発陣営との折り合いがつかず、独自実装になりました。

• RFC 5988 "Web Linking": https://tools.ietf.org/html/rfc5988