❄️

Twitter APIにおけるタイムラインの取得漏れ問題――後編：実証実験

2023/02/07に公開

Twitter

Twitter API

tech

前編：原理と対策

はじめに

前編ではSnowflake IDの仕様から読み取れる性質から起こりうるタイムラインの取得漏れの問題について理論的な考察を行なってきましたが、この問題は現実にどの程度起こる（あるいは起こらない）ものなのでしょうか。そもそも当のTwitterのドキュメントで説明されているのも、この記事でいうところの一般的なポーリング処理でした。というわけで、実際に実験して取得漏れが発生するか確かめてみましょう。

……などともったいぶって書きましたが、結果を先に述べると、実際に取得漏れらしき例を観測しました。しかし考察節で検討するように、まだ疑問点が残っていますので注意してください。

方法

前編で扱った取得漏れの問題を実証するには、Twitterにおいて何らかのタイムラインに対して実際にポーリングを行い、あるリクエスト時点で最新の（IDが最大の）投稿よりIDの小さい投稿が後続のリクエストで初めて現れる例を観測すれば（後に検討するエッジケースを除いて）十分でしょう。前編の問題節に挙げたツイート $A$ と $B$ の例でいうならば、 $A$ と $B$ の投稿時刻の間の隙間にリクエストを行い、タイムラインが $A$ を含みながらも（よりIDの小さい） $B$ を含まないのを観測すれば良いということになります。

では、具体的にどのようにしてタイムラインを観測すれば良いでしょうか。まずは観測する対象とするタイムラインに求められる要件を考えていきましょう。

まず必ず満たすべき要件として、前編で述べたようなポーリング処理を行えるようなタイムラインである必要があります。すなわち、Snowflake IDにより順序づけられ、since_idパラメータ（あるいはそれに相当する機能）によってcursoringできるAPIでアクセス可能である必要があります（要件0）。最新のツイートの列を返すAPIの多くがこれを満たしますが、例外としてTwitter API v2のGET /2/lists/:id/tweets（リストタイムライン）がsince_idパラメータ（およびその代替機能）を持っておらず、この要件を満たしません。

また、前編で見てきたように、TwitterのSnowflake IDは仕様上の最悪値として $k = 1 \mathrm{s}$ の前後がありうるわけですが、実際には多くとも数十 $\mathrm{ms}$ 程度の前後しか発生しないものと想定されます。つまり節の冒頭に述べた隙間は存在したとしても非常に狭いものになることが予想され、これを捉えるのはなかなか骨が折れそうです。この隙間が発生する機会を増やすために、取得するタイムラインの流速はできるだけ高い方が好ましいです（要件1）。

要件1と同様に、隙間を観測する機会を増やすために、利用するAPIのレート制限はなるべく緩いのが望ましいです（要件2）。参考として各種のタイムラインを取得するエンドポイントのレート制限を次に示します。なお、Twitter APIの認証方式としてアプリケーション単体について認証を行うapp-only authenticationと特定のユーザに代わってアクセスを行うための認可を伴うUser Contextがあり、そのそれぞれについてレート制限が設けられています。また、エンドポイントによっては15分ごとの制限に加えて24時間ごとの制限が設けられていることがあります。さらにuser context authであっても同一のアプリケーションのユーザ全体で共有されるレート制限が課されている場合がありますが、今回の実験では実験専用のAPIクレデンシャルを使うものとし、この制限については考慮しないものとします。

API	App (req./15 min.)	User (req./15 min.)	User (req./24 hrs.)
`GET /2/users/:id/tweets`	1500	900	-
`GET statuses/user_timeline`	1500	900	100000
`GET /2/users/:id/mentions`	450	180	-
`GET statuses/mentions_timeline`	-	75	100000
`GET /2/users/:id/timelines/reverse_chronological`	-	180	-
`GET statuses/home_timeline`	-	15	-
`GET lists/statuses`	900	900	-

また、実験結果として観測した投稿のIDを公開したいところですが、それによって対象の投稿を行なったユーザを煩わせてしまう可能性を考えると、一般の個人ユーザよりも公的機関や企業ユーザが観測対象として好ましいと考えられます（要件3）。

最後に、実験の再現性を高めるために、使用するAPIは誰でも使いやすいものを選択するのが望ましいです。具体的には、Twitter API v1.1は新規の利用申請ができないので、v2の方が望ましいということになります（要件4）。大多数の機能についてはv1.1とv2のそれぞれに対応するエンドポイントが存在するのでこれは実装上の詳細と見なせますが、要件0で触れたようにリストタイムラインの取得についてはv1.1のGET lists/statuses以外にこの実験において使えるエンドポイントがありません。

要件1を実現するための選択肢のひとつとして、タイムラインの取得に前後して大量の投稿リクエストを送信することで人工的に流速を引き上げることが考えられます。しかしそのような投稿は特に実験が長引いた場合にTwitterのPlatform manipulation and spam policyやAutomation rulesに抵触すると見なされるおそれがあるため、今回はそのような侵襲的な手法は避けて、自然に投稿されるツイートのみを観測する方針を取りたいと思います。

また、要件2について、同様の機能を持つAPIの複数バージョンのエンドポイントやapp-only/user context authを併用することで実質的にレート制限を緩めることが考えられますが、レート制限を迂回する試みはDeveloper Agreementなどに抵触するため当然ながら行いません。

以上を踏まえて、観測するタイムラインの候補として次のものを検討してみたいと思います：

既製のめぼしいリストタイムライン
Sampled streamに現れたユーザをリストに追加していき、そのリストを観測する
適当な注目されていそうなアカウント（例えば@Twitterや@elonmusk）へのメンションタイムライン
自分のホームタイムライン

まずは候補1についてですが、簡単なWeb検索によりTop 100 Twitter users sorted by Most Tweets - Socialblade Twitter Stats | Twitter Statisticsという一覧を見つけたので、とりあえずこの一覧のアカウントからなるリストを作成してみます。これは先述のリンク先を適当にスクレイピングなどしてAPIでリストに追加していけば作れるものです^[1]。完成したリストをこちらに示します：https://twitter.com/i/lists/1617048330886082560。

完成したリストを見てみるとキャンペーン用のユーザが多く見られ、要件3を良く満たしそうです。個人らしきユーザも見られますが、手作業で無理なく取り除けそうな範囲です。

続いて候補2について、sampled streamはTwitterで投稿される全てのツイートのうち無作為に抽出された1 %をリアルタイムに取得するAPIであり、ここに現れるユーザは少なくとも観測時点で1回は投稿を行なっているアクティブユーザであるので、どんなユーザでも少なからず流速に寄与すると考えられます。また、1つのリストに最大で5000ユーザを追加できるので、うまくユーザを収集できればかなりの流速が期待できます。しかし全ツイートから無作為に抽出する関係から要件3を満たすのは難しそうです。その関係から、今回は作成したリストを公開するのを控えたいと思います。

Sampled streamからリストにユーザを追加するために使用したスクリプトへのリンクを次に示します：stream-to-list.rb。本来ならPOST lists/members/create_allエンドポイントを使うことで比較的速やかに5000ユーザをリストに追加できるはずなのですが、実際には短時間に大量のユーザをリストに追加しようとするとドキュメント上のレート制限に関わりなく403 Forbiddenステータスを返し失敗するという現象が起こりました。この挙動は調べた限りではドキュメント化されていないらしく具体的に待つべき時間も不明なので、今回のスクリプトではエラー時にexponential backoffを行うようにしています。その関係からリストへの追加が想定以上に遅れ、残念ながら今回の実験はリストのユーザ数が5000に満たない状態で行うことにします。

候補3については、要件2のレート制限の観点でリストタイムラインを使う前の2候補に対して不利であり、要件3も満たさない（ビジネスユーザが著名アカウントに対してメンションを付ける蓋然性を考えると、候補2よりもさらに不利そうです）ので、これはあまり有望そうには見えません。ただ、候補として思いついたので一応これも検討してみたいと思います。

候補4は要件2のレート制限の観点で最も有利であり、またユーザをフォローできる枠は少なくとも5000件分はあるので、技術的な条件としては存外に見込みがありそうです。しかし実験用のアカウントを用意するとしても大量のフォローを行うのは明らかなスパム行為ですし、凍結のリスクも極めて高いと考えられます。既に正当な方法によるフォローを多数抱えているアカウントを管理していたならばまだ活用の余地があったのかもしれませんが、残念ながら筆者にはそのようなアカウントの持ち合わせがないのでこの候補は除外とします。

さて、（候補4.を除いた）これらの候補について要件1のタイムラインの流速を評価していきましょう。流速の尺度として、今回はそれぞれのタイムラインから最新の投稿を同時刻に一定数取得して、その中で最古のツイートのSnowflake IDのタイムスタンプを見ることで流速の逆数（s/post）を簡易的に見積もります。見積もりには次のシェルスクリプトを使いました：

estimate-tl-speed.sh

#!/bin/bash

twepoch=1288834974657

if command -v gdate > /dev/null; then
	DATE="${DATE:-gdate}"
fi
now="$("${DATE:-date}" +%s%N)"
if [[ "$now" = *N ]]; then
	# `%N`オペランドに非対応
	now="$((${now%N} * 1000))"
else
	now="$(($now/1000000))"
fi

twurl '/1.1/lists/statuses.json?count=200&list_id=1617048330886082560&include_entities=false' > "list-100-most-users-$now.json" &
twurl "/1.1/lists/statuses.json?count=200&list_id=$STREAM_USERS&include_entities=false" > "list-stream-users-$now.json" &
twurl --bearer '/2/users/783214/mentions?max_results=100' > "mentions-Twitter-$now.json" &
twurl --bearer '/2/users/17874544/mentions?max_results=100' > "mentions-TwitterSupport-$now.json" &
twurl --bearer '/2/users/44196397/mentions?max_results=100' > "mentions-elonmusk-$now.json"

echo "# now=$now"
echo $'file\tcount\toldest id\ts/post'

for f in *-"$now.json"; do
	count="$(jq 'if type == "array" then . else .data end | length' "$f")"
	id="$(jq -r 'if type == "array" then map(.id_str) else .data | map(.id) end | last' "$f")"
	echo -n "$f"$'\t'"$count"$'\t'"$id"$'\t'
	bc <<-BC
		d = $now - $id/2^22 - $twepoch
		scale = 3
		d / (1000 * $count)
	BC
done

見積もった流速とその他の要件をまとめて次の表に示します。なお、流速を計測した日時は2023-02-04T20:33:11+0900で、その時点でsampled streamのユーザから作ったリストのユーザ数は792でした。

候補	要件1／流速の逆数（s/post）	要件2／レート制限（req./15 min.）	要件3／非個人アカウント	要件4／APIバージョン
候補1／`100-most-tweets`リスト	2.091	900	T	v1.1
候補2／Sampled stream	1.347	900	F	v1.1
候補3／@Twitter	3.462	450	F	v2
候補3／@TwitterSupport	4.459	450	F	v2
候補3／@elonmusk	2.159	450	F	v2

流速の逆数は値が低いほど好ましいものです。Sampled streamからユーザを集めて作ったリストが最も流速が高いようなので今回はこれを使うことにしましょう。使用できるAPIのバージョンはv1.1のみになってしまいますが、どうせ間もなく有償になるAPIなのですから多少使いづらくなろうが同じようなものでしょう（Twitter APIの有償化に伴い気力を失ったので検討の仕方が雑なことはご容赦ください）。

エッジケース

先の例で挙げたツイート $B$ に相当する例、つまり前のリクエスト時点の最新ツイートよりIDが小さいにもかかわらず後続のリクエストで初めて現れるツイートの例を観測すればこの記事で扱った取得漏れの問題を実証するのに基本的に十分と考えられますが、エッジケースとして同様の条件を満たすツイートで取得漏れによらないものとして、次の場合が想定できます：

$B$ を投稿したユーザが私たちのアカウントをブロックしていたが、 $B$ を投稿した後にブロックを解除した（あるいは私たちが当該ユーザに対するブロックを解除したケースもありえるが、そもそもそのような操作をしなければ良いので無視できる）
$B$ を投稿したユーザが凍結・削除されていたが、その後に復活した。あるいは非公開アカウントから公開アカウントになった
$B$ を投稿したユーザが観測の最中にタイムラインに追加された

まず1.についてですが、これは私たちのアカウントが実験時点で当該ユーザから存在を認識されるような操作を行っていなければ発生する蓋然性は無視できる程度に低いと考えられます。このためにも、ユーザをリストに追加する場合は非公開リストにて行うべきです。

App-only authを使えばブロックを考慮する必要がなくなりますが、その場合は非公開リストからのツイートの取得ができなくなります。今回は一般の個人アカウントも数多く扱う関係から（通知によって観測対象を煩わせない）非公開リストを使いたいので、残念ですがapp-only authは使わないものとします。

また、投稿とブロックの解除操作をそれぞれ手作業で行っていることを仮定すれば、投稿が観測可能になった時点でその投稿は少なくとも数秒以上前のものになっていると考えられるので、このケースが発生した場合は $B$ の投稿時刻が古いという形でその兆候を掴めるでしょう。

2.についても同様に、 $B$ が投稿されてから、当該ユーザが凍結・削除され再び解除される、あるいは非公開アカウントから公開アカウントになるという一連のイベントが数秒未満のごく短期間で起こるとは考えづらいので、 $B$ の投稿時刻が古い場合について注意すれば良いでしょう。

3.については、今回観測するのはリストタイムラインなのでこれはつまり実験の最中にリストにユーザを追加した場合のことを指します。今回のリストは私たち自身で管理しているものなのでそのような操作を行わなければ良いだけの話ですが、前述のstream-to-list.rbスクリプトは実行に非常に時間がかかるため、うっかりするとスクリプトを走らせたままにしてしまうことも考えられます。というより、筆者自身がうっかりして一度このケースの疑いを除外しきれない実行結果を得てしまったという経緯があります。

もう一点の考慮すべき可能性として、Twitter APIのsince_idパラメータに実在のツイートのIDを指定した場合に、そのツイートより新しいツイートはたとえIDの値が小さくてもレスポンスに含まれるという特別処理が実装されている可能性が想定できます。そのような特別処理が存在した場合はこの記事で提案したような処理は不要ということになってしまうので、このような処理が存在しないことも確かめるべきです。これは実際に $A$ のIDをsince_idパラメータに指定してタイムラインを取得することで容易に確認できるでしょう。

実装

実験でタイムラインを観測するために使用したコードを次に示します：leaky-snowflake-observer。コードの概要を簡単に列挙します（Twitter APIの有償化に伴い気力を失ったので雑な記述です）：

$B$ に相当する例を見つけるまでコマンドライン引数に与えたIDのリストに対して1 sごとのポーリングを行い、見つけたら最新とその1つ前のリクエストのタイムラインを出力する
$k = 1 \mathrm{s}$ という仮定が十分でない可能性を想定してコード中で仮定する $k$ の値をオプション引数として指定できる。実験では余裕をもって $k = 2 \mathrm{s}$ を指定した

結果

前節に示したコードを実行したところ、実際に一般的なポーリング処理では取得漏れしていたであろう例を観測しました。このときの出力を次に示します。ただし今回は要件3.を満たしていない関係から、出力からは各ツイートのユーザIDを除き、ツイートのSnowflake IDはそのタイムスタンプに対応するUnix timeに置換しています。

{
    "k_ms": 2000, // 今回のポーリング処理で仮定した`k`の値
    "start_ms": 1675604020000, // ポーリングの開始時刻（2023-02-05T22:33:40+0900）
    "nth": 3539, // 取得漏れを捕捉したのは3539回目のリクエスト
    "previous": { // 取得漏れを捕捉したリクエストの1つ前のリクエスト
        "retrieved_ms": 1675607557001, // リクエストを送信した時刻（23:32:37）
        "latest_id": 1675607555188,
        "statuses": [ // レスポンスのタイムライン
            1675607555188,
            // 本来ならここに`1675607555001`が入るはず
            1675607554866,
            1675607554618,
            1675607554546
        ]
    },
    "latest": { // 取得漏れを捕捉したリクエスト
        "retrieved_ms": 1675607558001, // 23:32:38
        // since_id = clamp(previous.retrieved_at - k_ms, latest_id - k_ms - 1, latest_id) = 1675607555000
        "statuses": [
            1675607557866,
            1675607557448,
            1675607555188,
            1675607555001
        ]
    }
}

最新のレスポンスにおいて、latest_id = 1675607555188の直前に前回のレスポンスに含まれていなかった1675607555001が現れているのが見て取れます。

考察

前節に示した取得漏れらしきツイート1675607555001（ $T$ とおきます）について、前節で検討したエッジケースに当てはまらないか確認しましょう。

まず $T$ の投稿時刻と捕捉時のリクエストの送信時刻の差はlatest.retrieved_ms - 1675607555001 = 3000と、エッジケース1.と2.を否定するのに十分な短さであると思われます。

また、エッジケース3.についても、観測時点でリストを操作していなかったことを確認しています。

続いて同じくエッジケース節にて想定したような特別処理の存在についてですが、実験の結果を確認するのが遅れてしまい、確認した時点では $T$ がリストタイムラインから取得可能な最大ツイート数の範囲外に流れてしまっていたようで、そのような処理の存在を確認することができませんでした（適当にtwurlで確認すれば良いと高をくくっていました）。もしAPIの有償化までに同様の例を捉えることができたら改めて確認してみたいと思います……。

現時点では取得漏れの例を1つ示したのみですが、今後の展望としてさらに継続的に観測して取得漏れの発生頻度や(Altman and Igarashi, 1989)^[2]におけるradiusの推定を行うことが考えられます。しかしTwitter APIの有償化までにもう時間は残されていませんし、筆者はこのために~$100を負担するつもりがないので、つまり、その、あれです。

また、 $T$ の投稿時刻と捕捉時の1つ前のリクエストの送信時刻の差がprevious.retrieved_ms - 1675607555001 = 2000という値である点も気がかりです。今回は余裕を持って $k = 2000 \mathrm{ms}$ としてパラメータを設定していたから捕捉できましたが（それでもギリギリですね）、前編で提案した処理のままでは捕捉できなかったでしょう。これも今後の展望として検討するべき点ですが、これも、その、あれです。

結論

今回の実験では実際にTwitterのリストタイムラインに対してポーリング処理を行い、一般的なポーリング処理では取得漏れしていたであろう例を観測しましたが、なんと前編で提案した処理でも不十分であったことが分かりました。また、エッジケース節で検討した特別処理の存在や取得漏れの発生頻度についていまだに謎が残されています。……いかがでしたか？　以上です。

補遺：ライセンス

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

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

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

また、前記に加えて、記事に示したコードの内容を次に示す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アカウントへのリダイレクトに恒久的に置き換えられている場合は、代わりとしてそのリダイレクト先のアカウントを表示することもできます。リダイレクト先がリダイレクトしている場合も推移的に同様とします。

脚注

今回は次のXPathで各アカウントのスクリーンネームを得ました：//a[contains(@href, "/twitter/user/")]/text()。ただしリンク先の構造が将来変わる可能性もありますし、何よりもスクリーンネームは変更されうるので、これをコピペで使っても上手く動く保証はできません。一応再現しやすいようにWayback Machineにアーカイブを用意しておきました：https://web.archive.org/web/20230122062649if_/https://socialblade.com/twitter/top/100/most-tweets ↩︎
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/. ↩︎

はじめに

方法

エッジケース

実装

結果

考察

結論

補遺：ライセンス

Discussion