Twitter APIにおけるタイムラインの取得漏れ問題――前編：原理と対策

• 後編：実証実験

概要

Snowflake IDで順序づけられたリソースの列に対するポーリング処理において、リソースのIDが時系列順であることを仮定してAPIのsince_idパラメータを用いて最新のリソースよりIDの小さいリソースの取得を省く最適化手法が一般的に用いられている。しかしSnowflake IDの値は実際には完全な時系列順でなく$k$-sortedであり、Twitterの実装における最悪の場合で$k = 1 \mathrm{s}$分だけ前後しうる。これにより、取得時点における最新のリソースより小さいIDのリソースが後から追加される可能性があり、一般的な手法ではそのようなリソースの取得まで省いてしまう。これらのリソースを捕捉するためには、後続のリクエストのsince_idパラメータに設定するIDをタイムスタンプ部が前回のリクエスト時点の時刻より$k$以上前になるように調整するべきである。

はじめに：タイムラインのポーリング

Twitter APIではGET statuses/home_timelineやGET statuses/user_timelineなど^[1]のように特定のタイムラインのツイートを時系列降順で取得するエンドポイントがいくつか提供されています。

この記事ではこれらのAPIを使用して最新のタイムラインを定期的に取得する処理（ポーリング）について考えていきます。このような処理は、例えばエンドユーザ向けのクライアントアプリや、^[3]タイムラインを監視してリアルタイムに応答を行うボットなどでよく見られる処理かと思います。具体的なコードに表すと次のような処理です：

本記事が扱うポーリング処理の概観

require 'twitter'

loop do
  # GET lists/statusesでリストTLから最新200ツイート（1リクエストで取得可能な最大件数）を取得
  tweets = client.list_timeline('Twitter/official-twitter-accounts', count: 200)

  do_something(tweets)

  # GET lists/statusesのレート制限は900 req./15 min. = 1 req./s
  sleep 1
end

この記事のコード例ではRubyのtwitter gemを使用します。また、clientは適当なAPIクレデンシャルを設定したTwitter::REST::Clientのインスタンスとします。ただしこの記事の内容は言語やライブラリ、およびAPIのバージョン^[4]によらず適用できるものです。

取得の効率化：since_idパラメータ

前掲のコード例では最新200件のツイートを毎秒取得していますが、これだと同じツイートを何度も繰り返して取得することになってしまいます。TwitterにおいてContent-EncodingとしてサポートされているBrotliによる圧縮を経てもツイートオブジェクトのJSON表現は（少なくともTwitter API v1.1の場合は）あまり小さくないので、毎秒200件の取得ともなると帯域への負荷も軽くはありませんし、Twitter API v2の場合はTweet capsの浪費にも繋がってしまいます。かといって一度に取得する件数を絞ってしまうと、それより多くのツイートが1秒の間に投稿されたときに取得漏れの発生が懸念されます。取得漏れの分を別のリクエストで遡って取得する^[5]こともできますし、堅牢性のためにも実際にそのように実装するのが望ましいでしょうが、それでは結局帯域とレート制限を余分に消費してしまうことになるので、初めから取得漏れの可能性自体を最小限に抑えるに越したことはありません。

そこで取得済のツイートの再度の取得をスキップするために、APIに用意されているsince_idパラメータを利用します。このパラメータは指定された値以下の値のIDのツイートをレスポンスから除く働きを持っています。ツイートのIDの値は投稿時刻順に並ぶとされているので、それまでに取得した中で最新のツイートのIDをsince_idに設定すれば取得済みのツイートをスキップできると考えられます。実際、これはTwitter公式のドキュメントでも推奨されている方法です。この処理を前述のコードに実装したものを次に示します：

since_idパラメータを用いた一般的なポーリング処理

require 'twitter'

parameters = { count: 200 }
loop do
  tweets = client.list_timeline('Twitter/official-twitter-accounts', parameters)
  tweets.first&.id&.then do |latest_id|
    # 最新のツイートのID（最大のID）を記録
    parameters[:since_id] = latest_id
  end

  do_something(tweets)

  sleep 1
end

簡単のために省略した例外処理やレート制限の扱いの粗を無視すれば、一般的に用いられている手法に則ったこのコード例は概ね意図したとおりに動くように見えます。しかし、この手法には本来取得すべき投稿の取得漏れを引き起こす可能性があります。この記事ではそのような問題が起こりうる理由とその対策について考えていきます。

問題

前節のコード例に示した一般的なポーリング処理は「ツイートのIDは投稿時刻順に並ぶ」（⇒「将来投稿される任意のツイートのIDは最新のツイートのID（latest_id）より大きい」）という仮定に依存していました。これが成り立たないと、最新のタイムラインを取得してlatest_idを記録した後にそれより小さいIDのツイートが投稿されて、後続のリクエストでlatest_idをsince_idパラメータに指定することで本来取得するべきそのようなツイートをスキップしてしまう可能性を排除できません。そして実際に、TwitterのIDの仕様を紐解くとこの仮定が厳密には成り立たないことが分かります。

前提知識: Snowflake ID

現在の^[6]TwitterではツイートやユーザなどのIDとしてSnowflakeと呼ばれる内部サービスが生成する値を使用しています^[7]。Snowflakeは大まかに生成時刻順に並んだIDを複数のマシンで並列的に採番できるように設計されています。

Snowflake IDは64-bit整数として表されます。ただし、実際にIDとして使うとされているのは下位の63ビットのみであり、その各ビットには次に示す情報がエンコードされています：

フィールド	範囲	ビット数	説明
timestamp	[22, 63)	41	生成時刻のUnix time（$\mathrm{ms}$単位）からtwepoch = 1288834974657を引いた値
machine id	[12, 22)	10	生成を行うマシンに設定されたID
sequence number	[0, 12)	12	timestampとmachine idの組み合わせごとに一意になるように生成された連番

Snowflake IDのビット列のダイアグラム

0b11111111111111111111111111111111111111111_1111111111_111111111111
  63                                        22         12          0
  timestamp                                 machine id sequence no.

特に注目するべき点として、Snowflake IDはその上位ビットに生成時点のタイムスタンプをエンコードしています。これにより各マシン間で同期することなく全体として大まかに生成時刻順に並んだIDを生成することができるのです。また、これによりAPIを使わなくてもIDの値を見るだけでその生成時刻を把握することができます。具体的にはTwitterにおけるSnowflake IDの生成時刻（$\mathrm{ms}$単位のUnix time）は次に示す擬似コードのようにして求められます：

Snowflake IDの生成時刻を求める

twepoch = 1288834974657
sf2time(id) = (id >> 22) + twepoch

Roughly sorted

ところで、Snowflake IDは大まかに生成時刻順に並ぶなどと歯切れの悪い書き方をしてきましたが、実はSnowflake IDの順序は完全な生成時刻順ではありません。SnowflakeのGitHubリポジトリのREADMEにも書かれているように、複数のマシンで非同期的に生成を行う関係から完全な順序の保証はできないのです。

ここまでではカジュアルに「大まかに」（roughly）という表現を使ってきましたが、より厳密にはSnowflake IDは$k$-sorted (Altman and Igarashi, 1989)^[8]（Wikipedia）であるとされています。具体的には、$k$を所与として、任意のツイートの組について、それらの投稿時刻の差が$k$以内であれば、それらのSnowflake IDのタイムスタンプの差もまた$k$以内に収まるという性質です^[9]。そしてこの$k$の値について前述のREADMEでは次のように述べられています：

we're promising 1s, but shooting for 10's of ms

つまり、IDは最悪の場合で$1 \mathrm{s}$分は前後しうるが、実際上は数十$\mathrm{ms}$分に収めることを目指しているということになります。

完全な時刻順でなくとも、多くの用途ではたかが数十$\mathrm{ms}$程度の前後があったとして問題にならないでしょうから、これはかなり良い性質といえるでしょう。例えば時系列順のタイムラインをユーザに表示するとして、投稿の時刻をそれぞれ最大で数十$\mathrm{ms}$分だけランダムにずらして並び替えたとしても（それでスレッドの順序が入れ替わることがないと仮定すれば）ユーザが違和感を覚えることはないと考えられます。しかし、はじめに節で紹介した一般的なポーリング処理は完全な時刻順という仮定に強く依存しており、これが問題になりえます。

具体例を想像してみましょう。基準となる時刻を$0$（$\mathrm{ms}$）とします。時刻$0$に2つの投稿$A$、$B$を投稿するリクエストがそれぞれAPIサーバに送信されたとしましょう。$A$と$B$はそれぞれ別々のマシンで並列に処理され、Snowflakeによって$A$にはタイムスタンプが$t_{sf,A} = 42$のIDが、Bにはタイムスタンプが$t_{sf,B} = 24$のIDが採番されました。しかしどうも$A$を処理していたマシンの時計が少し遅れていたようで、$A$がデータベースに反映されてAPIからアクセス可能になったのは実際には時刻$t_A = 30$のことでした。そして$B$を処理していたマシンは少々処理が詰まったようで、$B$がアクセス可能になったのは時刻$t_B = 40$でした。ここで先にアクセス可能になったのが$A$である（$t_A < t_B$）一方でSnowflake IDの順序としては$B$が先行しています（$t_{sf,B} < t_{sf,A}$）が、それでも$k = 1000$（$\mathrm{ms}$）の保証は保たれています。

さて、ここであるクライアントが$A$と$B$を含むタイムラインに対してポーリングをしているとしましょう。クライアントは時刻$35$にタイムラインを取得して、レスポンスとして$A$を最新とする投稿の列を得たとします。このとき$B$はまだタイムラインに含まれていません。続いてクライアントは時刻$1035$に再びタイムラインを取得しますが、このときクライアントは$A$のID（$t_{sf,A} = 42$）をsince_idパラメータに指定します。するとレスポンスからはタイムスタンプが$t_{sf,B} = 24 < t_{sf,A}$のIDを持つ$B$が除外されてしまいます。結果としてクライアントは本来取得するべき$B$を取得しないまま処理を続行することになってしまうのです。

対策

前節ではSnowflake IDの並びが完全な投稿時刻順でないことによって一般的に用いられているポーリング手法では投稿の取得漏れが発生する可能性があることを示しました。この節ではこの取得漏れの問題に対する対策を考えていきます。

記事の冒頭の一般的なポーリング処理のコード例ではsince_idパラメータに指定した最新の投稿のID（latest_id）がそれより後に投稿されるツイートのIDより小さいとは限らないことが問題でした。一方で、Snowflake IDのタイムスタンプが互いに$k = 1 \mathrm{s}$以上離れたツイートについては$k$-sortedという性質のおかげで投稿時刻の順序関係が定まります。つまり、もしもlatest_idよりタイムスタンプ部が$1 \mathrm{s}$分小さいSnowflake IDが存在したと仮定すると、そのIDはlatest_idが指すツイートの以後に投稿されるツイートのIDよりも小さいことが保証されるので、そのようなIDをsince_idパラメータに設定すれば将来に投稿されるツイートを全て捕捉するのに十分です。もちろんそのようなIDの投稿が実在するとは限りませんが、次の擬似コードに示すような簡単な計算によってそのような条件を満たす（架空の）Snowflake IDを作り出すことは可能です：

latest_idよりk = 1 s前に相当するSnowflake IDの計算

k = 1000
timestamp = latest_id >> 22
since_id =
    if timestamp <= k then
        latest_id
    else
        ((timestamp - k) << 22) - 1

エッジケース（latest_idが非常に過去のものである場合^[10]）の考慮で少し複雑になっていますが、タイムラインの最新の投稿のみを扱うポーリング処理において、これはほとんどの場合でsince_id = ((timestamp - k) << 22) - 1と等価です。

Snowflake IDのタイムスタンプが$\mathrm{ms}$単位であることに注意してください。それに伴ってkの値も$\mathrm{ms}$単位の1000としています。また、最後にsince_idの値から1を引いているのはsince_idパラメータがexclusiveであることを考慮してのものです（実用上でこれが問題になることはないと考えられるので、過剰な配慮かもしれませんが）。

実在のリソースに対応しないIDをsince_idパラメータに指定することが何らかの問題につながらないか疑問に思われるかもしれませんが、Twitter APIにおけるsince_idパラメータはIDの値による単純な比較を行うのみなので架空のIDでも問題なく機能します。そもそもSnowflakeがIDの値のみによる整列を実現できるように設計されていたことを思い出せば、そのような挙動も自然なものと考えられます。実際にTwitter公式のドキュメント^[3:2]でもmax_idパラメータとして実在のツイートのIDから1を引いたものを指定する手法が紹介されています。ただしECMAScriptのように64-bit整数を正確に扱えない（扱いづらい）環境では計算誤差に注意が必要でしょう^[11]。

さて、前述の計算によって求めたsince_idパラメータの値は取得漏れを防ぐのには十分ですが、この値は少なくともlatest_idより小さいので、特にタイムラインの流速が低くて新しいツイートが現れない場合にsince_idの値が更新されず毎回同じツイートを取得することになってしまいます。もしlatest_idのタイムスタンプがタイムラインを取得した時点の$1 \mathrm{s}$前より後のものであったならば$1 \mathrm{s}$以内の将来にlatest_idより小さいIDのツイートが投稿される可能性があるのでこれも本質的なコストとみなせますが、それより過去のIDの場合はその可能性もないので余分な取得といえましょう。

そこで前述の計算に改良を加えて、latest_idのタイムスタンプが取得時点より$1 \mathrm{s}$以前のものであればlatest_idをそのままsince_idとすることを考えます。タイムラインを取得するリクエストを送信した時刻のUnix time（$\mathrm{ms}$単位）をretrieved_atとすると、次に示す擬似コードのようになります：

latest_idの取得時刻を考慮に入れたsince_idの計算

twepoch = 1288834974657
k = 1000

clamp(x, lower, upper) = max(lower, min(upper, x))
time2sf(unix_time_ms) = max(0, unix_time_ms - twepoch) << 22

timestamp = latest_id >> 22
lower =
    if timestamp <= k then
        latest_id
    else
        ((timestamp - k) << 22) - 1

since_id = clamp(time2sf(retrieved_at - k) - 1, lower, latest_id)

Snowflake IDのタイムスタンプとUnix timeでは基準となる時刻（epoch）が異なることに注意してください。ここではUnix timeを対応するSnowflake ID（の中で最小のもの）に変換するためにtime2sfという関数を導入しています。

また、ここでretrieved_atがクライアント側の時計を基準とした時刻であることにも注意が必要です。この計算ではretrieved_atをサーバ側の時計によって生成されたlatest_idのタイムスタンプと比較していますが、これが意味をなすにはクライアントとサーバの間で時計が十分に同期している必要があるので、クライアントの時計をNTP等の手段でなるべく最新に保っておくべきです。一応ここではクライアントの時計が遅れていても最悪の場合でももう1つ前の擬似コードと等価になるようにsince_idの値を下から押さえていますが、時計が進みすぎている場合はやはり取得漏れの抑止効果を損ねてしまいます。

retrieved_atの時刻からリクエストがサーバに到達するまでの遅延も気になるかもしれませんが、遅延によってretrieved_atがサーバから見て過去の時刻になる分にはツイートの取得漏れには繋がらない（余分なツイートの取得は増えるかもしれませんが）のでこれは問題にならないでしょう。

以上の対策を記事の冒頭のポーリング処理に適用した完成版のコードを次に示します：

Snowflake IDの性質を考慮したポーリング処理（完成版）

require 'twitter'

TWEPOCH = 1288834974657

def time2sf(time)
  # `time`を秒単位のUnix timeに変換してからms単位に換算する。
  # 計算誤差を考慮しなくても良いように、浮動小数点数を返す`Time#to_f`でなく有理数を返す`to_r`を使用する
  unix_time_ms = (time.to_r * 1000).to_i
  (unix_time_ms - TWEPOCH) << 22
end

K_S = 1 # Rubyの`Time#:-`の挙動に合わせて秒単位で定義
K_MS = 1000 * K_S

parameters = { count: 200 }
latest_id = nil
loop do
  retrieved_at = Time.now
  tweets = client.list_timeline('Twitter/official-twitter-accounts', parameters)

  tweets.first&.id&.then do |id|
    # `latest_id`のツイートが削除された場合に`id < latest_id`になりうることに注意
    latest_id = id unless latest_id&.>(id)
  end
  latest_id&.then do |latest_id|
    timestamp = latest_id >> 22
    lower = if timestamp <= K_MS
      latest_id
    else
      ((timestamp - K_MS) << 22) - 1
    end

    parameters[:since_id] = (time2sf(retrieved_at - K_S) - 1).clamp(lower, latest_id)
  end

  do_something(tweets)

  sleep 1
end

このコードでは無駄なツイートの取得を最小限に抑えるように工夫をしましたが、それでも同一のツイートを重複して取得する可能性があることに注意しましょう。ツイートをエンドユーザに表示したり、あるいは^[3:3]ボットとしてツイートに応答するにせよ、多くの用途では同じツイートを重複して処理しないようにアプリケーションの要件^[12]に合わせた工夫が求められるでしょう。

おわりに：プラットフォームを超えて

この記事ではTwitter APIを利用したタイムラインに対するポーリング処理において、Snowflake IDの性質から一般的な実装ではツイートの取得漏れが起こる可能性を示し、またそれに対して比較的容易に実装可能な対策を提案しました。

記事では主にTwitter APIを対象としていましたが、Snowflakeの原理はTwitter以外でも採用されていることがあるので、この記事の内容はその他のAPIに対する同様の処理にも応用できるかもしれません。その中でもとりわけこの記事で扱ったTwitterの例に近いものとしてMastodonというサービスが挙げられるでしょう。

Mastodonはオープンソースのマイクロブログサービスです。これだけだとただのTwitterクローンのように聞こえるかもしれませんが、Mastodonの各サーバ（インスタンスとも呼ばれます）はActivityPubというプロトコルによって互いに「連合」（federate）しており、各サーバのユーザは自身のサーバだけでなく他のサーバのユーザともやり取りすることができます。これにより、メールサーバやはたまたインターネットそれ自体がそうであるように、ユーザはどのサーバを選らんだとしても（もちろんセルフホストも可能です）ActivityPubにより結ばれた同一の広大なネットワーク（Fediverseと呼ばれます）で活動できるのです。

ActivityPubはW3Cにより策定されたオープンな標準であり、Mastodon以外にもPleromaやMisskeyなどの多様な実装が活発に開発されています。その可能性は単なるマイクロブログにとどまらず、動画共有サービスや画像共有サービス、リンクアグリゲータ、ソーシャルリーディング――おっと、列挙しだすとそれだけでひとつの記事になってしまいますね――とにかく、幅広いジャンルのサービスが同じFediverseを介してつながっています。興味があればAwesome ActivityPubのようなリストを見てみると良いでしょう。

さて、そのMastodonはActivityPubによるサーバ間の連合のためのAPIだけでなく、Twitterと同じようにclient-to-serverのやり取りのためのAPIも提供しています。多くのサーバにおいて一部の公開情報を取得するAPIについては認証無しで使えるので、実際にこの記事で提案したポーリング処理を適用してみましょう。

今回はMastodonの開発者自身によって運用されている世界最大のサーバであるmastodon.socialの公開投稿をGET /api/v1/timelines/publicエンドポイントで取得してみます。このAPIにはTwitterと同じく（Fediverse全体でなくサーバ内でユニークな）Snowflake IDによるcursoringを行うためのsince_idパラメータがあるのでこの記事の内容を適用できます。ただしMastodonのSnowflake IDはTwitterのものと違ってタイムスタンプ部が48ビットあり、独自のepoch（twepoch）でなくUnix epochを基準としています。詳細についてはMastodonのソースコードのsnowflake.rbが参考になります。

本記事のポーリング処理のMastodon版

require 'json'
require 'net/http'

def time2sf(time)
  unix_time_ms = (time.to_r * 1000).to_i
  unix_time_ms << 16
end

K_S = 1 # ここでは便宜的にTwitterと同じ値を使う
K_MS = 1000 * K_S

uri = URI('https://mastodon.social/api/v1/timelines/public')
latest_id = nil
Net::HTTP.start(uri.hostname, uri.port, use_ssl: uri.scheme == 'https') do |http|
  loop do
    retrieved_at = Time.now
    response = http.request_get(uri.request_uri)
    response.value
    
    posts = JSON.parse(response.read_body)
    posts.first&.[]('id')&.then do |id|
      id = Integer(id)
      latest_id = id unless latest_id&.>(id)
    end
    latest_id&.then do |latest_id|
      timestamp = latest_id >> 16
      lower = if timestamp <= K_MS
        latest_id
      else
        ((timestamp - K_MS) << 16) - 1
      end

      since_id = (time2sf(retrieved_at - K_S) - 1).clamp(lower, latest_id)
      uri.query = URI.encode_www_form({since_id: since_id})
    end

    do_something(posts)

    # 執筆時点でのmastodon.socialにおけるレート制限は300 req./5 min.だった
    sleep 1
  end
end

実際に現在のMastodonに対してこのような処理を行うのが妥当かはともかく^[13]、Twitterに対するものとほぼ同様の処理が適用できることが確認できました。

Twitterにおいても過去にはサードパーティによるエンドユーザ向けのクライアントアプリケーションの開発が認められていましたが、太平洋標準時2023年1月12日頃からそれらのクライアントが一斉にAPIにアクセスできなくなる現象が報告され、その後の1月19日付でDeveloper Agreementが改定されてTwitterアプリケーション（いわゆる公式クライアントがこれに含まれるでしょう）の代替または類似のサービスまたは製品を作るためにAPIを利用することが禁止されました（引用時点のII.のA.の(c)）。手続の適正性に甚だ疑問を残す経緯ではありますが、とにかく今後からTwitterにおいてサードパーティでエンドユーザ向けのクライアントをまっとうに開発することは絶望的になったといえましょう。

また、日本時間2023年2月2日の@TwitterDevのツイートにて、2月9日から無償のAPI利用をサポートしない旨が発表されました。この記事の執筆時点で詳細は不明なものの、少なくとも今後は今までほど気軽にAPIを利用することができなくなると思われます。

一方で、実装がオープンソースでありオープンなプロトコルの上で動くMastodonであれば全てのサーバのAPIを恣意的にコントロールできる単一の管理者は存在しません。たとえあるサーバの管理者がAPIを制限したとしても他のサーバには影響しませんし、最悪の場合でもセルフホストすれば自分のサーバへの自由なアクセスを保証できます。Twitter APIを取り巻く情勢が目まぐるしく変化しているこの機会にこそ、開発者としてMastodonのようなエコシステムに目を向けてみるのも良いかもしれませんね。

なお、2022年12月にTwitter社からMastodonを含む競合のSNSプラットフォームの宣伝を禁止するポリシー^[14]が発表され、Fediverseの各インスタンスへのリンクを含むツイートを投稿できないように制限が設けられ、さらにそれらのリンクを投稿したユーザが凍結されるという出来事がありました。その後にそのポリシーは削除されましたが、執筆時現在でこの件についてTwitter社からは特に正式な声明が出されておらず、ポリシーの撤回が恒久的なものなのかは不明です。ひょっとするとこの記事の内容も今後同様のポリシーに抵触すると見なされることがあるかもしれませんが、その場合にTwitter上でのこの記事への言及が何らかの不都合な処置を受けたとしても著者は一切の責任を負いかねることを予めご承知おきください^[15]。

さて、この記事（前編）ではSnowflake IDの仕様から読み取れる性質から起こりうるタイムラインの取得漏れの問題について理論的な考察を行なってきましたが、後編ではTwitter APIを対象として実際に一般的なポーリング処理で取得漏れが起こる例を観察します。

最後に、比較的素直な仕組みで$k$-sortedという良い性質を効率良く保証するSnowflakeの原理を考案し実現した開発者の貢献を称え、またAPIを広く一般に無償で開放していたTwitter社の厚意に感謝します。彼らのドキュメントがなければこの記事は書けなかったでしょうし、初めからAPIが公開されていなければこの記事を書く意味もなかったでしょう。また、本記事のコード例で使用したtwitter gemをはじめとするサードパーティーのエコシステムにも大いに助けられました。プラットフォームとしてのTwitterは先行きが不透明な状況が続いていますが、最終的にどこかで開発者たちの働きが報われることを願っています。

補遺：ライセンス

筆者はこの記事の全体をクリエイティブ・コモンズ 表示-継承 4.0 国際 パブリック・ライセンスの条件でライセンスします。同パブリック・ライセンス（またはコードの場合は後述のMIT License）の条件に従う限りにおいて、著作権法上の例外を超えてあなたはこの記事の内容を利用することができます。

同パブリック・ライセンスの第3条(a)(1)(A)(i)に定められている識別情報として、次の情報を指定します：

• 筆者の名前を次のいずれかの形式で：
  • ハンドルネーム：tesaguri
  • それがあなたにとって法律や手続きの上で何らかの便宜に資すると考えるのであれば、後述のcopyright noticeの氏名表記。必要であればさらにハンドルネームを省いても良い
• 筆者のFediverseアカウントを次のいずれか、または両方の形式で、可能であればハイパーリンクとして：
  • URI：https://fedibird.com/@tesaguri
  • Fediverse上での利用の場合は、URIの代わりにユーザ名を表示しても良い：@[e-mail]

また、前記に加えて、記事に示したコード例および擬似コードの内容を次に示すMIT Licenseの条件でもライセンスします：

MIT License

Copyright (c) 2023 Daiki "tesaguri" Mizukami <https://fedibird.com/@tesaguri>

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

なお、いずれのライセンスにおいても、あなたがアクセスした時点でクレジット表示のFediverseアカウントが著者によって別のFediverseアカウントへのリダイレクトに恒久的に置き換えられている場合は、代わりとしてそのリダイレクト先のアカウントを表示することもできます。リダイレクト先がリダイレクトしている場合も推移的に同様とします。

脚注

1. Twitter公式のドキュメントのGet Tweet timelinesページではGET statuses/home_timelineとGET statuses/mentions_timelineおよびGET statuses/user_timelineの3つのエンドポイントが紹介されていますが、ここではより広汎に、Snowflake IDで順序づけられ、since_idやmax_id（Twitter API v1.1）、until_id（Twitter API v2）のようなパラメータによってcursoring^[2]ができるリソースの列をタイムラインとして扱うことにします。具体的にはTwitter API v1.1のGET lists/statusesが返すものも含めます。一方でTwitter API v2のGET /2/lists/:id/tweetsはsince_idパラメータ（およびその代替機能）を持っておらず、この記事の内容が上手く当てはまらないので注意してください。

2. Working with timelines | Docs | Twitter Developer Platform

3. この記事の草稿時点ではまだサードパーティのTwitterクライアントアプリケーションが正式に存在していましたが、おわりに節でも触れるように、その後にサードパーティによるクライアントの運用が禁止されました。

4. より正確にはSnowflake IDで順序づけられてcursoringされるタイムラインを取得するAPI全般に適用できるものと考えられます。Snowflake IDの原理的な性質に関わる内容なので、よほど抜本的な変更が導入されない限りは程度の大小はあれど将来にわたって通用すると思われます。ちなみにTwitter API v2ではタイムラインを遡るのにIDによるcursoringの代わりにpaginationを使うことが推奨されていますが、リンク先のドキュメントでも説明されているとおりポーリングの場合には依然としてsince_idが使われます。

5. 例えばTwitterのいわゆる公式クライアントではタイムラインのビューに"Show more Tweets"というボタンを表示してユーザによる操作で再取得できるようになっています。そのような用途では必ずしも遡る必要があるとは限らないので、countパラメータの値は小さめでも良いかもしれません。一方で^[3:1]ボットなどのunattendedな用途では自動的に再取得する実装になるでしょう。

6. この記事で扱うポーリング処理において目にすることは稀でしょうが、Twitterでは過去のある時期までは連番のIDが用いられており、それらのIDにはこの節の説明が当てはまらないことに注意が必要です。もしSnowflake以前のIDが全て22ビット以内に収まる（Snowflake IDと見なすとタイムスタンプ部が0になる）のであったならば話は簡単だったのでしょうが、実際にSnowflakeが導入される以前のTwitter上の適当なツイートを見ると23ビット分以上の桁数のIDが見られるので、残念ながらそこまで自明に判別できる性質のものではなさそうです。例えばSnowflakeの導入を予告するブログ記事のAnnouncing Snowflakeにリンクした@TwitterEngのツイートhttps://twitter.com/TwitterEng/status/15214161783を例に取ると、そのIDは桁数は34ビットです。そもそもブログ記事の本文でも過去にツイートのIDを保存するためのビット数を増やしたエピソードが言及されています。

7. Twitter IDs | Docs | Twitter Developer Platform

8. T. Altman and Y. Igarashi. 1989. Roughly sorting: sequential and parallel approach. J. Inf. Process. 12, 2 (Jan. 1989), 154–158. https://ci.nii.ac.jp/naid/110002673489/.

9. この説明はTwitter社のブログ記事Announcing Snowflakeの脚注によるものです。「差が$k$以内」（"within a second of one another"）を素直に解釈するならば、Snowflake IDのタイムスタンプ$t_{sf,1}, t_{sf,2}$とそれらに対応するIDの生成時刻$t_1, t_2$について$\left \lvert t_1 - t_2 \right \rvert < k \implies \left \lvert t_{sf,1} - t_{sf,2} \right \rvert < k$のように読めるかも知れませんが、現実の実装として$t_1 \lessgtr t_2 \mp k \land t_{sf,1} \gtrless t_{sf,2} \pm k$（複号同順）の場合を除外できるだろうと考えられるので、$t_1 \lessgtr t_2 \pm k \implies t_{sf,1} \lessgtr t_{sf,2} \pm k$（複号同順）のように解釈するのが適当でしょう。この解釈を採れば対偶から$t_{sf,1} \leq t_{sf,2} - k \implies t_1 \leq t_2 - k < t_2$が従い、(Altman and Igarashi, 1989)の定義（$\left \lbrace a_n \right \rbrace$ is $k$-sorted iff. $\forall i, j. i \leq j - k \implies a_i \leq a_j$）とのギャップも埋められるかと思います。

10. 脚注^[6:1]でも述べたように、Twitter上のツイートのIDにはSnowflakeによらない連番のIDであって32ビットに収まらないものが存在するのでtimestamp <= kはSnowflakeによらないIDの判定条件としては不十分です。よってこの擬似コードにおけるエッジケースの扱いはあくまでオーバーフロー対策程度のものと考えてください。本文でも述べているように、最新の投稿を扱うポーリング処理においてこのケースに遭遇することは稀でしょうし、仮に遭遇したとしても余分な取得が（大量に）発生することはあるかもしれませんが、取得漏れのような問題には繋がりません。また、後述する取得時刻を考慮に入れた計算でこのケースにおける過剰な取得の問題も解消されます。

11. 例えばECMAScriptの場合は十分にモダンな環境ならES2020で導入されたBigIntを使うことで正確に計算できます。このような環境ではTwitter API v1.1のJSONオブジェクトを素直にデシリアライズするとidフィールドが不正確な数値として得られるかと思いますが、同じIDの10進法の文字列による表現がid_strフィールドから得られるので、それをBigIntなどに変換すると良いでしょう。なお、Twitter API v2では初めから文字列型のidフィールドのみが提供されています。また、この記事では詳しくは検討しませんが、今回の用途では計算結果の値が小さければ小さいほどツイートの取得漏れが減る（余分なツイートの取得は増えるかもしれませんが）という性質のものなので、何らかの手法で結果を上から押さえることができれば不正確な計算でももしかしたら活用の余地があるかもしれません。

12. 例えばエンドユーザ向けのクライアントではツイートオブジェクトの内容（の一部）をモデルに保持する必要があるでしょうが、^[3:4]リアルタイムに応答を行うボットではsince_id以降のIDのみを記憶しておけば十分かもしれません。このように、この部分の処理はアプリケーションの要件に依存するところが大きいので、ここでは具体的なコード例を示すことはしません。

13. MastodonにSnowflakeの仕組みを導入する計画段階のissueを見るに、MastodonにおけるSnowflakeの役割としてはサーバ内の投稿と連合先のリモートからの投稿の間で一貫して投稿時刻順に並んだIDを割り当てるというのが主であって、Twitterにおけるそれのようなスケーリングの目的は想定はされているものの主な役割ではないように読めます（筆者はMastodonのコードベースに疎いので、現時点のupstreamの実装が並列な採番を行いうるのかについては分かりませんが）。もちろんネットワークを通じてやって来るリモートの投稿が後からタイムラインに現れるということはごく普通に起こることなので、ここで提案したような処理が上手いことそのような投稿を捕捉することもあり得ることではありますが、不特定のサーバと連合している関係から、投稿がタイムラインに現れるまでの時間の最悪値、ひいては$k$-sortedにおける$k$を一定値に保証するのは困難と考えられ、ここで提案した処理でも投稿を網羅しきることはできないと考えられます。また、フォーク実装も含む不特定多数のサーバが存在することから、同じMastodon互換のAPIを提供しているサーバであってもIDの表現についてここで仮定したような詳細を常に満たすのかについては検討の余地があると考えられます。特に、フォークでない場合もv2.0.0rc1（2017年10月リリース）より前のサーバはSnowflake IDを使っていません（そもそもここまで古いサーバだとSnowflake ID以前の問題として最新バージョンに対して多くの非互換性がありますが）。

14. Promotion of Alternative Social Platforms Policy | Twitter Help（Wayback Machineによる2022-12-18時点のアーカイブ）

15. ポリシーに抵触するおそれを低減した形に記事を改めることもできたでしょうが、他のプラットフォームにおけるSnowflakeの原理の採用事例を省くことは記事の完全性を損ねると判断しました。もう一点としては、流石にもう懲りただろうという淡い期待も草稿の時点では抱いていました。Twitterを主な対象とした記事であるとはいえ、Twitter外に投稿する記事でTwitterという一プラットフォームのポリシーに忖度して内容を制限するのは不健全ですし、それよりもTwitter社が反競争的なポリシーを改めるのが筋というものでしょう。