TwitterのステータスIDが53bitを越えたお話

僕の記事の間違いを指摘していただいているすばらしい記事です。僕の記事よりこちらの記事をご覧ください。
http://archive.guma.jp/2010/12/twitter-json.html

先日、29日の7時過ぎごろにTwitterのステータスIDが53bitを越えました。
こんな中途半端なビット数を超えただけでなぜこんな記事にするかというと、一部のクライアントで動作がおかしくなることがあるからです。
(14:14　追記しました)
(14:31　もひとつ追記しました)
TwitterのAPIはXMLとJSONの2種類で結果を取得できます。このうちXMLで処理してる場合は内部で64bit INTで処理していれば特に問題は起きません。
問題が起きるのはJSONの場合です。JSONはJavascriptでevalすればそのまま中身が取り出せることからもわかるように、Javascriptの連想配列などの記述そのものです。そして、Javascriptにおける数値型というのは64bit 浮動小数で表現されます。
この64bit 浮動小数は1bitの符号部、11bitの指数部、52bitの仮数部から構成されます。この64bitの数値から実際の値はsは符号部, eは指数部, mは仮数部とした場合、
(-1)^s*2^e*mという式で求められます。仮数部は52bitですが、2進数の小数点数としてあらわした際の1.10010101... の整数部分、1を省略することになっているので実際の値は53bit分保持できます。
このことから、Javascriptでは2^52*0b1.1111111111111111111111111111111111111111111111111111の9007199254740991が正しく扱うことのできる最大の値になってしまいます。

じゃぁなんでTwitterのIDが急に53bitを突破するようなことになったのか。
最近、といっても11月の頭ごろからですが、前々からアナウンスされていたようにTwitterはID生成アルゴリズムをSnowflakeと呼ばれるものに変更しました。
このSnowflakeでは64bitの整数を生成して、64bitの内訳は、1bitはSignFlagなので置いておいて、41bitのEpoch秒を少し変形させたミリ秒、10bitのMachineID、12bitのある1秒の範囲におけるマシン内でのユニークなIDから構成されています。
このことから見てわかるように、SnowflakeはIDを生成するだけのサーバを複数台用意してID生成の負荷分散をするために変更したものと思われます。
さて、id中に時刻が含まれているために、ある特定の日を境にJSONで正しくパースできなくなってしまいました。Epoch秒を少し変形　と書きましたが、実際にはEpoch秒のミリ秒表現 - 1288834974657という計算の結果を使用しています。
このことから53bitを突破して54bit目以降を使用してしまうのは2010/11/29 07:14:18.304(JST)となるわけです。
実際にはMachineIDやマシン内でユニークなIDは0埋めされていることが多く、浮動小数の誤差が出てもあまり問題にならないことが多いですが、マシン内でユニークなIDが0でない場合に浮動小数の誤差で本来意図しないステータスを指し示してしまう可能性があります。

このように53bitを越える値を正しく扱えないためにJSONにはid_strという値が追加されています。id_strはステータスIDを文字列として表現したもので、Javascriptなどでは53bit越えると正しく扱えないから文字列としてあつかってちょ！と、中の人が言っていました。

意図しないステータスIDを指し示してしまった場合、全然しらないひとにReplyしてしまったり、ユーザが意図したPostと違ったPostをFavoriteしてしまったり、in_reply_to_status_idからリプライを取得したら全然違うのが取得できてしまったでござる。などということが起こります。

ようするに、JSONを使ってTwitterAPIを利用している場合、ステータスIDを文字列として扱うコードに変更しましょうね。ということでした。

ちなみにPHPも似たような問題が発生します。32bitシステムだと2147483647を超えた値はfloatで扱われ、PHPのfloatは倍精度なので53bit以上の値が...(最初に戻る) ということです。文字列で扱うか、64bit環境でintとして扱うかしないといけないみたいです。

追記：twitter4jのようなライブラリもJSONを扱っているなら問題が起きるかもしれません。JSONを仕様書通りにパースするとidの値はdoubleなので最終的な型が64bit整数型であってもdoubleの時点で値が化けてしまうので同じ問題が発生します。id_strをパースしてlongなどの64bit整数型へ変換するか、idの値を仕様書を無視して64bit整数型でパースしないとだめです。
追記：twitter4jのコードを読んだところ、idを文字列としてパースした後longへ変換しているので今回の問題は発生しません。