Misskey: (API)sinceId とuntilIdを同時に指定したい

[tateisu]

sinceIdを使って新しいデータを読もうとした際、一度に読める件数よりも未取得のデータが多いとギャップが発生します。

単純にするためストリーミングを無視した例を述べます。
TLを最初に取得してIDが40…21のNoteを得たとします。(新しい方が始端)。
画面OFFにします。
モバイルアプリだと画面OFFの間に受信し続けるのはバッテリー的に厳しいので受信は停止します。
画面ONになったタイミングでsinceId=40を指定して差分取得します。
その時未取得のデータはIDが90…41だったとします。
20件のデータを読むと、読める範囲は新しい方に偏るはずです。(A)
IDが90…71のNoteを得て、70…41の間は「ギャップ」が出来ます。
ユーザがギャップを読む操作を行うと、
アプリはsinceId=40,untilId=71を指定してギャップを読み込みます。
次も全て読めるとは限らず、範囲内の新しい方から何件かが読めます。
…というようなユースケースを想定しています。

(B)
これとは別のアプローチとして、order byをID昇順にするオプションがあるとギャップは発生しなくなります。たとえば未取得のデータはIDが90…41だったときにsinceId=40とreverse=trueを指定したとしましょう。order by id asc limit 20 だと古い順に20件読めます。
この場合最新のデータは読めませんがギャップは発生しません。もし最新データが欲しければsinceIdを指定しなければ(A)とほぼ同様の出力が得られるので、ギャップを作った後にギャップを下から埋めるということも可能です。

また、逆順ソートがあると「特定時刻から連続した未来のノートを取得する」が可能になります。(Mastodonはこの機能がなく、一度に読める件数も少ないので特定時刻から連続した未来のノートを取得するのが困難です)

---

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

[mei23]

おそらくMisskeyの現状の実装でsince指定でもギャップは発生させない仕様なのではと思われます。
（上記の(B)の仕様に相当）

ですので、Mastodonで起きる以下の事象は起きないと思われます。

20件のデータを読むと、読める範囲は新しい方に偏るはずです。

APIのTL取得(ホーム/ローカル/グローバル/ソーシャル/ユーザー)は以下のように実装されています。

  untilIdより小さい方を降順で指定件数取得して返す
  (untilId=40の場合[39,38,37 ... 20]を返す)

sinceId 
  sinceIdより大きい方を昇順で指定件数取得して返す(接着している部分を昇順で返す)
  (sinceId=40の場合[41,42,43 ... 70]を返す)

なお、ActivityPub Outboxの場合は、since_idの取得範囲は同じですが降順になってます。
（仕様的に逆順を許容してなさそうなため）

  until_idより小さい方を降順で指定件数取得して返す
  (until_id=40の場合[39,38,37 ... 20]を返す)

since_id 
  since_idより大きい方を昇順で指定件数取得して逆転させて返す(接着している部分を降順で返す)
  (since_id=40の場合[70,69,68 ... 41]を返す)

[tateisu]

挙動の説明ありがとうございます。

いくつか考えました。前の書き込みと違うことを言います

(A)「差分の古い方を読めて先頭にギャップができる」だと、ユーザはギャップを読み飛ばす選択ができません。未読をすべて消化する主義の人ならそれでも良いかもしれませんが、流量の多いTLでは無理があります。

(B)「新しい方を読めて中間にギャップができる」方を好むユーザの方が多いと思います。
最新のノートがある程度取れた状態で、ギャップを読み飛ばす選択ができるからです。

(C)差分取得ではなく、「特定日時の前後のノートを取得する」用途には現状のsinceIdの挙動はとても良いと思います。これはこれでよい。

さて
アプリ的には現状でも(B)を実現することは可能です。

• ID範囲を指定せずに取得することで最新トゥートの取得はできます。
• 中間のギャップは untilId だけを指定して読めばギャップの消化は一応可能です。

しかしこれは「(最新の差分取得には)sinceIdを使わない」と言ってるのと同じで
読み込む範囲には無駄が発生します。

以下のサポートがあれば無駄読みをなくせます。

• sinceIdの取得範囲を新しい方に偏らせるパラメータを用意する
• sinceId とuntilIdを同時に指定できるようにする

ご検討いただければと思います。

[tateisu]

SubwayTooter のストリーミング対応が進んだので、現時点での見解を書きます。

(A) sinceId とuntilIdの両方を指定した取得が可能である方が望ましいです。ギャップの発生はありえます。たとえば始端の更新をsinceId,SinceDate REST APIで繰り返し行って一定時間内に「結果0件」を得られなかった場合は「先頭にギャップが存在する」ことになります。このギャップの上にストリーミング受信したデータが追加されていきます。

(B) IDの大小比較をクライアントが行えないという条件は厳しすぎます。REST APIで取得している最中にストリーミング受信したデータが発生した場合、データを並べる順序と次回RESTリクエスト時のページネーション用パラメータをクライアント側で判断する必要があります。

• MisskeyはIDの大小関係をクライアントに対して保証していない
• ストリーミング受信できるのは通知と投稿のタイムラインである
• 投稿のタイムラインはREST APIの時点で時刻順にソートされている
• 投稿は時刻でページネーションできる
• 通知は時刻でページネーションできない

というMisskeyの実装に合わせると

• 投稿に関しては並び順もページネーションのパラメータも createdAt をキーとするのが最も適切であるように思えます。投稿の時刻がミリ秒単位で重複する可能性はゼロではありませんがほぼ無視できるはずです。

• 通知に関してはページネーションを時刻で指定することはできません。REST APIとストリーミング受信の両方で最新のIDがどれなのかクライアント側で判定する必要があります。

(C)MisskeyはIDの大小関係を保証していません。ただしIDの先頭32ビットはunix time らしく、2038年までは文字列の辞書順ソートで大小判定すると時刻順に並ぶようです。クライアントは2038年まではこれを利用してもよいでしょうか？

(D)外部から未来の時刻の投稿や通知イベントがサーバに届いて、サーバ側がcreatedAtを現在時刻までにクリップして記録しない場合は、createdAtを使ったページングは取得漏れの原因になります。たとえばクライアントが取得した最新の投稿の時刻が3分先の未来だった場合、それをページネーションのsindeDateに指定するとクライアントは3分間の範囲を取りこぼすことになります。

クリッピングが行われるならそれはクライアント側ではなくサーバ側の時計で、投稿データを記録する際に行われるべきです。たとえばマストドンでは投稿はcreated_atとsnowflake IDを持ち、後者はサーバ上の時刻で未来にはならないように考慮されています。

[tateisu]

「符号なし32bitなら2106年まで大丈夫」だそうな
How can mongodb handle ObjectId timestamp beyond Tue, 19 Jan 2038? - Stack Overflow https://stackoverflow.com/questions/42097779/how-can-mongodb-handle-objectid-timestamp-beyond-tue-19-jan-2038

[syuilo]

ありがとうございます。通知も時刻を用いてページネーションできるようにしますね

[tateisu]

https://github.com/syuilo/misskey/blob/master/src/server/api/endpoints/notes/timeline.ts#L212
＞sort._id = 1;

投稿のタイムラインはREST APIの時点で時刻順にソートされていると前に伺いましたが、コード上はそうなっていなかったようです。

[tateisu]

https://github.com/syuilo/misskey/blob/develop/src/models/note.ts#L21
NoteにはcreatedAt のインデクスが既にあります。 sinceDate, untilDateが指定された時にソート順をidではなくcreatedAtにしてほしいです。

https://github.com/syuilo/misskey/blob/develop/src/models/notification.ts#L8
NotificationにはcreatedAtのインデックスがないので、時刻でのページネーションを行うにはまずインデクスを作成してからのほうが良いと思います。やはり sinceDate, untilDateが指定された時にソート順をidではなくcreatedAtにしてほしいです。

[tateisu]

sinceDate,untilDateを指定した時にソート順がIDのままなのは、クライアントの都合以前にDBサーバでのクエリ実行計画が非効率なんじゃないかと不安になります。

単純に考えたらuntilDateの条件を満たす全てのデータを抽出してからid順にソートするか、またはid順インデックスを順にスキャンしつつuntilDateの条件を満たすデータを抽出するかの二択です。

[mei23]

sinceDate, untilDate を指定した時にidでソートしているのは部分はまずそう（普通にバグ？）
untilDateを使って過去に向けて遡っている時に、取得した最後の投稿に未来の方の日付が登場した場合
untilDateに未来の方の日付を入れてリクエスト→取得済みの部分を再度取得 で循環してしまいそう。

[mei23]

また、Web UIは一見DateでTLを遡ってそうで実際はidを使用してそう。