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アプリのレイヤーでやると

1. timelinesテーブルからuser_idのデータ取得
2. tweet_idを差し込み、入れ替え、削除
3. 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を作る記事](https://redis.io/docs/manual/patterns/twitter-clone/)もあるのでそれも読んでみると面白いかもしれません。

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

## 参考リソース
* [Scaling Redis at Twitter](https://www.youtube.com/watch?v=rP9EKvWt0zo), 2014
* ["Cache à la carte: a framework for in-memory caching" by Yao Yue](https://www.youtube.com/watch?v=pLRztKYvMLk), 2015
* [Using Redis at Scale at Twitter - by Rashmi Ramesh of Twitter - RedisConf17 -](https://www.youtube.com/watch?v=QznaOSk20nU), 2017
* [RustConf 2021 - Whoops! I Rewrote It in Rust by Brian Martin](https://www.youtube.com/watch?v=m-Qg3OoPIdc)
* [Pelikan](https://github.com/pelikan-io/pelikan)
* [Timelines at Scale](https://www.infoq.com/presentations/Twitter-Timeline-Scalability/)
* [Real-Time Delivery Architecture at Twitter](https://www.infoq.com/presentations/Real-Time-Delivery-Twitter/)