Twitterはタイムラインをどうやってキャッシュしているか #Twitter

Twitterの内部構造を読解してみる

前口上

Twitterのようなマイクロブログサービスでは短時間で書き込みも多く、特にタイムライン周りは単にRDBのデータを出し入れるするだけではスケールしなくなります。

インターネット上に断片ながらTwitterの中の人がアーキテクチャについて解説した記事や動画がいくつか落ちていたので、Twitterがタイムラインをどうやってキャッシュしているかについてまとめてみたいと思います(推測を含みます)。

Twitterのテーブル構造

単純なTwitterのテーブル定義をRDBで定義すると以下のようになると思います。

tweets ツイート

id
user_id
contents
tweet_at

followers フォロワー

source_user_id
destination_user_id

users ユーザー

id
user_name

timelines タイムライン

user_id
tweet_id
seq

タイムラインは単なるSQLの集計ではない

Twitterでは各ユーザーがツイートを投稿でき、他のユーザーをフォローすることができます。

ユーザーはフォローしている人たちのツイートを自身のホームタイムラインで閲覧することができ、該当ユーザーのプロフィールページに行けばユーザーが過去投稿したツイート一覧、ユーザータイムラインを閲覧することができます。

単純なSNSならSQLでフォローしているユーザーのIDを取得して、該当ユーザーIDが過去のとある期間につぶやいたツイートを取得してくればタイムラインが完成するわけですが、ことはそんなに簡単ではありません。

何千人もユーザーをフォローしている人なら集計は重くなりますし現実問題一定の間引きが必要になるでしょう。おすすめのツイートや広告ツイートなどもホームタイムラインに差し込む要件もあります。そこでタイムラインは個別のテーブルが必要になるわけです。

Twitterはタイムラインのメインのデータ構造として、取得時に集計するPULLベースのアーキテクチャーではなく、フォローしているユーザーがつぶやいたら各タイムラインに書き込むようなPUSHベースのアーキテクチャを採用しています。

今回の主題とはずれますが他にも、とある人がフォローしている人の一覧と、とある人をフォローしている人の一覧はあえて重複して持つなどの工夫はあるようです。

アプリレイヤーでタイムラインを出し入れするのは高コスト

Twitterを使っているとタイムラインの底にたどり着くことがあると思います。一件無限スクロールのように見えて、タイムラインは長さにキャップがあるようです。ホームタイムラインは300ツイートまでとかそんな感じですかね。

実際1週間前のホームタイムラインを再現したいというシーンは少なくとも一般ユーザーにはなくて、フォローしている人が過去何をつぶやいていたか調べたい場合は検索や該当ユーザーのユーザータイムラインで確認すると思います。

おすすめや広告などの差込をタイムラインに行うにあたって、差込や入れ替えを愚直にWebアプリのレイヤーでやると

timelinesテーブルからuser_idのデータ取得
tweet_idを差し込み、入れ替え、削除
timelinesテーブルのuser_idのデータをトランザクションで総入れ替え

になると思います。

ただ、ユーザー数が多くリアルタイム性の高いTwitterのようなサービスではこれは比較的高価な操作で、RDBのような汎用性が高いテーブル構造に保存しているわけではなく、カスタマイズされたRedis上で特殊用途のデータ構造を使って表現しているようです。

Haplo: Hybrid ListとBTreeをRedisに実装

パブリックな情報を追う限り、Twitterが使用しているインメモリのキャッシュストアはMemcached+RedisからPelikanに移行としようとしているのが最新状況のようです。

タイムライン以外ではMemcachedが多く、タイムライン周りはRedis。MemcachedとRedisを統一したPelikanを内製してタイムライン以外は割合Pelikanに移行できており、タイムラインも載せようとしているタイミングでキャッシュ周りをリードされていた方はレイオフになったようですね。。。

Pelikanはオープンソース化されているのですが、GitHubのTwitter配下にあったものがメンテナの権限がなくなったためpelikan-ioに移っています。少し前にC++からRustベースのコードに部分的に移行したようでRustConfで発表がありました。

タイムラインはRedisなのですが、そのまま使っているのではなくカスタマイズしたRedis、Haploとして使っているようです。データ構造としてHybrid ListとBTreeを追加しています。BTreeはRDBのインデックスにも使われますね。

古いバージョンのRedisをフォークしてしまったのと、おそらくRedis側がカスタムのデータ構造をいくつも持つ設計にしたくない(特にBTree)ため普通のRedisではこれらのデータ構造をサポートしていないのだと思います。

Hybrid Listを作るモチベは圧縮効率とパフォーマンス

タイムラインは主にHybrid Listを使っています。

Redisは組み込みで

ziplist
連結リスト

をサポートしていますが、ziplistと連結リストを合わせたものをHybrid Listと呼んでいるようです。

Twitterのタイムラインは基本的にtweet_idの集合なのですが、連結リストにおいては不利めな構造なのもある思います。コンテンツの部分がポインタと比べて十分大きければポインタ部分は無視できると思うのですが、tweet_idはidなのでポインタとの差分が小さく最適化の余地があるのではないかと。

単純なziplistだとフォロワー数の多い有名人がつぶやくとたくさんのタイムラインに書き込む必要があり、ヒープが足りなくなるなどの問題があったようです。

その他パフォーマンス、費用面での工夫など

Redisはインメモリのデータストアなので登録ユーザー全てのタイムラインを準備すると費用面がつらくなります。実際、直近ログインしたかどうかでキャッシュの戦略は変えているようです。

ツイート時のタイムライン書き込みにキューがあるようなので、有名人がつぶやくとタイムラインの更新が死ぬ問題は他にも緩和策はありそうです。

ここら辺は想像成分多めですが、Celebrity Clusterと言っている動画はあったので、自分が初期のTwitterを作っていたら、一定のフォロワー数がいる人だけフラグをつけてキューの進出速度を変えるなり特殊操作をするかもしれません。実際Twitterは1日にフォローできる人数に制限があり、相互フォロー狙いで急にbotがCelebrityにならないような制限を持っている気もします。

最後に

少し古いですが、RedisのドキュメントにTwitter cloneを作る記事もあるのでそれも読んでみると面白いかもしれません。

結構頑張って記事や動画を観たのですが、抜け漏れありそうなので間違いあればご指摘ください。

Twitterはタイムラインをどうやってキャッシュしているか

前口上