Quine Tweet: 自分自身へのリンクを持つ再帰的ツイート
This tweet is recursive. https://t.co/bZISaPd3Ts
— Quine Tweet (@quine_tweet) 2016年9月19日
「このツイートはありません」となっていますが、URL をクリックすれば自分自身に飛べます。
以下、このツイートが生まれるまでの経緯を長々と書きます。
問題設定
そのツイート自身の URL を埋め込んだツイートを作ります。ツイートの URL はツイートをした後でないと決まらないし、ツイート文面を後から更新する手段はない（と思う）ので、単純ですが意外に難しい問題です。
調査
ご存知のように、現在のツイートの URL は次のような形式です。
https://twitter.com/<username>/status/<id>
username はそのままなので、id を事前に予測できれば解決です。*1
調べてみるとこの id は、snowflake という分散ナンバリングシステムで決められているようでした。いくつかの解説記事によると、id は以下のような 64 ビット整数であるようです。
+--------------------+--------------------+-------------------+ | timestamp (42 bit) | worker-id (10 bit) | sequence (12 bit) | +--------------------+--------------------+-------------------+
それぞれの意味は以下の通り。細かいことは snowflake のソースコード*2を見て確かめました。
- sequence: 同じミリ秒枠内での衝突を回避するためのシーケンス番号（ミリ秒ごとに 0 リセット）
- worker-id: この id を発行したサーバ固有の番号 *3
- timestamp: System.currentTimeMillis() - 1288834974657L の値。（2010-11-04 10:42:54 頃からの経過ミリ秒）
上位ビットが timestamp なので、この番号はおおよそ時間順に増えていきます。
アプローチ
それぞれの値を予測して id を作り、ツイートを投げてみて、外れたらツイ消し。Quine ツイートに成功するまで、延々とこれを続けます。各ツイート試行は独立と仮定すれば、典型的なベルヌーイ試行ですね。
観察と見積
TL に流れているツイートをいくつか集めて、それぞれの値の傾向を観察して、成功までにかかりそうな時間を見積もりました。
- sequence はミリ秒ごとにリセットされるので、0 と予想するのが鉄板です。実際、TL に流れているツイートの sequence をいくつか拾ってみると 0 が多めでした。1 日にツイッターに流れる全ツイート数は数億で、1 日は 8640 万ミリ秒なので、時間帯の偏りを考えればこんなものでしょう。
- worker-id は原理的には 2^10 = 1024 通りの値を取りえます。いくつかのツイートを観察しても特に傾向はつかめませんでした。
- timestamp は、なんとなく ±500 ミリ秒くらいの精度で当てられるんじゃないかなーと考えました。
これらの観察から、値が一致する確率（ヒット率と呼ぶことにします）をそれぞれ 50 % 、0.1 % 、0.1 % と仮定しました。それぞれの値が一致する確率は独立と仮定して、Quine ツイートが生まれる確率は 50 % × 0.1 % × 0.1 % = 0.00005 % 、期待値で言うと 200 万回のツイートで 1 回成功する計算になります。
ツイッター API のレートリミットを調べると、1 時間に 100 ツイート程度が許されるそうです。少し余裕を見て、40 秒に 1 回ツイートすることにしました。200 万回のツイートをするには 3 年弱かかる計算になります。
| 値 | 事前見積 |
|---|---|
| sequence ヒット率 | 50 % |
| worker-id ヒット率 | 0.1 % |
| timestamp ヒット率 | 0.1 % |
| 必要なツイート数期待値 | 2M 個 |
| 所要時間の見込み | 3 年 |
心が折れそうになりましたが、3 年がかりの Quine というのもロマンがあっていいだろう*4、と前向きに考え、とりあえずやってみることにしました。
簡易版での試行
専用の Twitter アカウントを作成し、次のような適当な予測で挑戦しました。
- sequence は 0 固定。
- worker-id は「前回の失敗ツイートの worker-id をそのまま送る」という戦略。ナンバリングサーバが常時 1024 台起動してはなさそうですし、ロードバランサの振り分け先にも偏りあるんじゃないかと期待。
- timestamp は単純に、前回の失敗ツイートから 40,000（40 秒）を足して作ります。ただし、ローカルの時計と前回の失敗ツイートの timestamp のズレを見て、ツイート発射タイミングは調整します。
これで半日走らせてみましたが、まあ、当たりませんでした。
失敗データの分析
試行によって 1000 ツイート分くらいの失敗データが溜まったので、それぞれの値のヒット率を評価してみました。
| 値 | 事前見積 | 簡易版 |
|---|---|---|
| sequence ヒット率 | 50 % | 80 % |
| worker-id ヒット率 | 0.1 % | 7.0 % |
| timestamp ヒット率 | 0.1 % | 0.05 % |
| 必要なツイート数期待値 | 2M 個 | 35k 個 |
| 所要時間の見込み | 3 年 | 17 日 |
worker-id は予想よりもかなり当てやすいことがわかりました。
timestamp は、1000 ツイート程度では 1 回もヒットしませんでした。事前見積から言っても、1000 ツイートで timestamp がヒットする期待値は 1 なので、ヒットなし自体は想定範囲です。しかし、誤差分布を見てみると ±1500 ミリ秒くらいで広がっていて、予想よりも厳しそうです。誤差分布をカーネル密度推定してヒット率を見積もったところ、0.05 % でした。ネットワーク越しだとこんなものか。
しかし worker-id のヒット率がだいぶ楽観視できるようになったので、所要時間の期待値を計算しなおすと、約 17 日になりました。3 年に比べたら全然行けます。ロマンはなくなりましたが。
改良版での挑戦
17 日なら待ってもいいんですが、せっかくなので予測方式を改良しました。
- sequence は変わらず 0 固定。
- worker-id は、「直近 5 つの失敗ツイートの worker-id を多数決して選ぶ」としました。*5
- timestamp のタイミング補正に PID 制御を導入しました。
これでヒット率を見てみました。（2 日ほど走らせた時点）
| 値 | 事前見積 | 簡易版 | 改良版 |
|---|---|---|---|
| sequence ヒット率 | 50 % | 80 % | 75 % |
| worker-id ヒット率 | 0.1 % | 7.0 % | 9.8 % |
| timestamp ヒット率 | 0.1 % | 0.05 % | 0.08 % |
| 必要なツイート数期待値 | 2M 個 | 35k 個 | 15k 個 |
| 所要時間の見込み | 3 年 | 17 日 | 8 日 |
sequence が若干悪化しましたが、簡易版でデータ採取したときは Twitter が混雑していない時間帯だったのかも。（そういうときは sequence の衝突が生じにくい）
とにかく、これで所要時間の期待値は約 8 日に。そこでちょうど帰省するタイミングになったので、モニタリングの仕組みだけ作ってそのまま放置しました。
結果
簡易版の実験を 9 月 13 日にやって、改良版を 9 月 14 日の 0 時ごろから改良版の実行を開始しました。9 月 20 日の朝 5 時ごろ、14377 ツイート目にして、ついに Quine に成功しました。苦節 6 日と 5 時間。だいたい予想通りですね。
正直、いろいろ不安でした。せっかく成功したのにスクリプトのバグでツイ消ししてしまわないか*6とか、Twitter 側で完全に recursive なツイートはエラー扱いにするような処理が入っていないかとか。「開始から 5 日経ってるから、そろそろ当たってもおかしくない……」みたいな典型的なギャンブラーの誤謬に陥ったり。実際にうまくいくとホッとしました。この不安、3 年間は耐えられなかった気がする。
関連研究
やり始めた後で気づいたんですが、ネタ自体は既出でした。ショック。
これは 2009 年のツイートです。当時の Twitter では、id がただの連番で、一定間隔でツイートを投げれば番号がおよそ 200 増える（作者による解説の図を見ると、あんまりブレてない）ので、今よりだいぶ難易度が低かったようです。ミリ秒当てしなくていいのは大きい。Self referential tweet http://twitter.com/SelfRefer/status/3128391843
— Diomidis Spinellis (@SelfRefer) 2009年8月4日
現在のナンバリングシステムになってからのものとしては、次のツイートがありました。
ただしこれはチートという噂です。TinyURL を作りかけの状態でツイートし、そのツイートの URL で TinyURL を完成させる、という手順でできるそうです。I love recursion, as seen here: http://t.co/M8jOdH8
— Markus Persson (@notch) 2011年8月15日
まあ今より簡単だろうがチートだろうが既出ネタは既出ネタなんですが、楽しかったのでよいことにします。
今後の課題
もともと作りたかったのは「自分自身を埋め込んだツイート」だったのですが、残念ながら「このツイートはありません」となってしまいました。ツイート作成時点（自分自身がまだ作成されていない）でリンク先をフェッチして記録するようなので、当たり前ですね。普通の Twitter card のリンクなら 1 週間程度で再クロールしてくれるらしいですが、ツイートのリンクは Twitter card とは別の仕組みで埋め込まれているっぽいので、クロールし直してくれない予感がします*7。残念。何か手はあるかなあ。
予測的な改良の余地は 2 つ。まず、ツイート発射スクリプトが Ruby なので、発射タイミング自体がミリ秒単位では制御できていません。リアルタイム OS でもっときちんと制御して発射すれば、クライアント側のブレが減って timestamp のヒット率が上がる可能性があります（が、ネットワークと Twitter サーバのブレは消せないので、大きく改善することはないと思っている）。それから worker-id は、プロダクションレベルのサービスやロードバランサの知識を持っている人が考えれば、もっと賢い予測方法を思いつくのかも知れません。
他に作りたいのは、相互再帰的なツイートのペアです。といっても同じような難易度で作れるはず（所要時間は倍になる）。今後も Quine Tweet の採掘を続けるためには、自宅 PC ではつらいので VPS などを借りたいところです。が、このためにお金は払いたくないなあ。。。*8
まとめ
Quine を作るには、データサイエンスや制御理論のちょっとした知識が役に立つこともあります*9。Quine 自体は何の役にもたちませんが、いろんな知識・技術を実践的に試すきっかけに最適なので、ぜひあなたも。
*1:余談ですが、username の部分は別の文字列に変えてもツイートは開けるようです（正しい username に転送される）。username を変えてもデッドリンクにならないようにこうなっていると思われますが、他人のツイートを URL 上では偽装できるとも言えますね……。
*2:GitHub のリポジトリからは消えていますが、README にある通り、リリースは残っています。
*3:snowflake のソースコード内では、datacenter-id と worker-id という名前で、それぞれ 5 ビットずつのようです。
*4:3 年ならおそらく生きているうちには終わるだろうし、投稿スクリプトもほとんど sleep なので電気代はかからないし。
*5:同数の場合は適当。5 というパラメータは、1000 の失敗ツイートのデータでシミュレーションして一番ヒット率が高くなった値。
*6:実際、成功時の処理に typo があって例外になってました。ツイ消しには至らなかったものの、これだから Ruby は……（逆恨み）
*7:存在しなかったツイート URL が後から現れる可能性を考慮する必要は（普通は）ないので。
*8:他にも Twitter bot 作りたいネタはあるんですが、VPS をケチっているので話が進まない。
*9:大したことしてないのに偉そう。