Misskey: Snowflake ID の追加

[tateisu]

https://github.com/syuilo/misskey/blob/develop/src/server/api/endpoints/notes/timeline.ts#L212

現在のMisskeyはTLをID順で表示していますが、それだとリモートから古い投稿が流れてきたときにTLの先頭にでてしまいます。たとえばリモートの何かを誰かがブーストしたら、TLにはリノートとリノートされた投稿の二つが並ぶことがあります。本来ならリノートされた投稿はTLのその時刻に表示されるべきではありませんが、「IDが採番された時刻」が新しいので出てしまいます。マストドンがSnowflake IDに移行した理由はこれを避けるためでした。

MisskeyにはTLをsinceDateでページネーションできる（なぜかソート順はcreatedAtではない)機能がありますが、createdAtでは重複や未来の時刻がありうるので、ページネーションのキーにすると境界で欠けが発生する可能性があります。

MisskeyもSnowflakeIDを「追加」して、WebUIやクライアントはその順序でTLを表示するよう徐々に移行すると上記の問題を回避できます。

TLの並び順とページネーションだけの問題なので、他のAPIに使うオブジェクトIDをいじくる必要はありません。

ソート順とページネーションに使うだけの値を新たに作って、ユニークなインデックスつきのカラムに記録して、TL取得APIのページネーション用のパラメータを追加するだけです。

対象となるタイムライン

• ホーム、ローカル、ソーシャル、連合。可能ならハッシュタグTL、リストTLも
• 通知TL

snowflake IDの採番

• 上位48ビットにミリ秒単位のunix time 、 下位16ビットにノイズ値
• 投稿の時刻を反映するが、未来の時刻はサーバ上の現在にクリップする
• 衝突があり得るので、投稿をDBに記録する際にノイズ値を変えてリトライする

現在付近のTLを差分取得する場合はノイズの大小による取得漏れが発生し得ますが、その確率はごくわずかです。どちらかというとリモートの投稿の時計が過去の方にずれているために発生する取得漏れの方が目立つでしょう。「ほぼほぼリアルタイムで送られてきた投稿ならサーバ上の時計での現在時刻をもとにsnowflake IDを生成する」という回避策もありますがまあ良し悪しありますね。投稿を受信した経路（リモートからリアルタイムにFan-outされてきたか、ユーザがリモートの投稿をrenoteした等のアクションによりローカルに複製されたか）によって切り替える方法もありますが、これだと他タンスのメンテナンスによりかなり古い投稿が流れてきた時にサーバ上の現在時刻で採番してしまう可能性もあります。このあたりの詳細は実装者の裁量で決定されるべきでしょう。

related: https://github.com/syuilo/misskey/issues/2275

---

Want to back this issue? Post a bounty on it! We accept bounties via Bountysource.

[mei23]

みたいなの考えてました
（せっかくSnowflake作ったのにページングにしか使用しないのはもったいないというのもあり）

• ページングに使用するIDだけではなく、投稿IDも含めて新体系にする
• IDが12バイトの16進数文字列で構成されている点は変更しない
• 既存Noteは、既存のIDをそのまま移行する
• 新規到着Noteは、8000～ではじまるIDを新規採番する

これにより既存IDとの連続性を保ち、クライアントの実装は既存のIDと同じ扱いで良いようにする

既存ID体系
7fffffffaaaaaabbbbcccccc

7fffffff: 32bit UNIX Time 秒
aaaaaabbbbcccccc: マシンID+PID+カウンタ 64bit

新規ID体系
8000aaaaaaaaaaaabbbbbbbb

8000: 固定(8000-ffffまでのなにかに決めればいい)
aaaaaaaaaaaa: 48bit UNIX Time ミリ秒
bbbbbbbb: 32bit ノイズ

あと、JavaScriptで64bit整数型はなにかと扱いづらい印象があったり。

[tateisu]

＞JavaScriptで64bit整数型はなにかと扱いづらい印象があったり。
それはその通りなので、どちらの案にせよ文字列型を利用するべきですね。

IDの刷新については個人的には何も意見がありません。

[acid-chicken]

MongoDBのIDは先頭がUNIX時間に基づく採番だったような気がしますが、これだと順番が入れ替わってしまったりするのでしょうか。

[tateisu]

MongoDBのIDで困るポイントはいくつかあります。

• 「採番した時間」なのでリモートからきた過去の投稿に現在の時間が適用されること
• 大小関係の精度が秒単位であること
• 32ビット符号なしとして2106年にオーバーフローすること

なにより、MongoDBの開発元自体がIDを使った大小比較を保証しないはずです。

[tateisu]

IDの刷新という考え方は、MongoDB のオブジェクトIDとは相性が悪いと言うことはできるかもしれません。
オブジェクトID _id をDBの利用者が指定することはできないはずです。「_idとは別のカラムXにsnowflake IDを格納して、サービス中の全てのクエリで_idではなくXを使うように書き換える」という実装になってしまうでしょう。これは移行負荷が高いと思います。

snowflake IDをソートとページング専用のデータとして使う方が影響範囲は小さくなるはずです。

[syuilo]

文字列型にしたらソートできるんでしょうか？

[acid-chicken]

@syuilo 文字列でもASCIIコードによるバイナリと変わらないので問題はなさそうです。

[syuilo]

なるほど

[tateisu]

JavaScript だと文字列同士を比較演算子にかけると辞書順（Unicode文字コード順）で比較できます
https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/String#%E6%96%87%E5%AD%97%E5%88%97%E3%81%AE%E6%AF%94%E8%BC%83

Array.sort のデフォルト比較関数もUnicodeコードポイントの昇順です。
https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

他の言語も何かしら文字列の大小比較は持っていますし、なければ書けばいいだけのことです。