ニュースフィードのシステム設計：書き込み時と読み取り時のファンアウト

ホームフィードは、どのソーシャル製品でも最も読まれるページであり、構築に最もコストのかかるページの 1 つです。ユーザーはそれぞれ数百のアカウントをフォローし、各アカウントは自分のペースで投稿します。そしてフィードは、誰かがアプリを開くたびに、ランキングされた状態で数百ミリ秒以内に返ってこなければなりません。

中心となる設計上の問いには、書き込み時のファンアウトと読み取り時のファンアウトという 2 つの古典的な答えがあり、大規模なフィードはどれも最終的に両者を組み合わせることになります。この記事では、数字を使って両者を比べ、ハイブリッドを示し、最後に読み取りと書き込みの経路全体を描いた図を示します。

要件

• ユーザーは、フォローしているアカウントの最近の投稿を、ランキング順か時系列順で見られる。
• フィードを開くのに、99 パーセンタイルで 1 秒を大きく下回る時間しかかからない。
• 新しい投稿は数秒以内にフォロワーのフィードに表示される。
• 重複や抜けのない無限スクロール。
• 1 つのアカウントのフォロワーが数千万人いても動き続ける。

読み取りが大半を占めます。Twitter のアーキテクチャを解説したこの記事 によれば、Twitter は 2013 年、毎秒約 6,000 件のツイートの書き込みに対し、毎秒約 30 万件のタイムラインの読み取りを処理していました。まず読み取りのために設計します。

ざっくりした見積もり

平均値は無害に見えますが、外れ値はそうではありません。フォロワーが 2,000 万人いる投稿者が 1 回投稿すると、2,000 万回のファンアウト書き込みが発生します。これは、ほかの全員の 1 日分のファンアウト処理の 10 分の 1 にあたります。以下の設計が対処すべきなのは、この外れ値です。

書き込み時のファンアウト（プッシュ）

誰かが投稿すると、バックグラウンドのジョブがその人のフォロワーを調べ、各フォロワーのキャッシュ済みフィードの先頭に投稿 ID を挿入します。フィードの読み取りは 1 回の検索で済みます。自分のリストから最新の ID を取り出し、投稿を取得するだけです。

• 強み： 読み取りが速く、予測しやすい。
• コスト： 1 件の投稿で、投稿者のフォロワー数と同じだけの書き込みが発生します。フォロワーが 3,000 万人のアカウントなら、1 件の投稿が 3,000 万回のキャッシュ書き込みになり、フォロワーが目にするのも遅れます。同じ記事では、最大級のアカウントの投稿が全フォロワーに届くまで数分かかっていたことが説明されています。
• 無駄： 今週アプリを開かないユーザーのフィードにまで書き込みます。

キャッシュするフィードは短く保ちます。当時の Twitter は、ホームタイムラインを Redis の 800 件までに制限していました。それより古い投稿は、誰かがそこまでスクロールしたときにデータベースから読みます。

読み取り時のファンアウト（プル）

誰かが投稿しても何もしません。ユーザーがフィードを開いたときに、フォローしているすべてのアカウントの最近の投稿を取得し、マージしてランキングします。

• 強み： 書き込みが安く、大きなアカウントにも追加のコストがかからない。
• コスト： フィードを読むたびに数百人の投稿者に触れます。毎秒 30 万回の読み取りでは、大部分が繰り返しの処理のために、膨大な数のクエリが発生します。

ハイブリッド

大規模なフィードの多くは、この 2 つを組み合わせます。

• 普通のアカウントの投稿は、フォロワーのキャッシュ済みフィードにプッシュする。
• フォロワー数がしきい値を超えるアカウントはファンアウトを省き、その最近の投稿を読み取り時に取得する。
• 読み取り時に、キャッシュ済みフィードと取得した投稿をマージしてから、ランキングする。

しきい値は調整のつまみであって、法則ではありません。ファンアウトの書き込みコストが、追加の読み取りコストを上回り始めるところに設定し、フォロワーの分布が変わったら見直します。大きなアカウントを 1 つもフォローしていないユーザーは、プルの経路のコストを一切払いません。

ランキング

時系列のフィードは時刻で並べます。ランキングされたフィードは 3 つの手順で動きます。候補の投稿を集め（上のマージ済みリストに、あればおすすめも加える）、新しさ、ユーザーがその投稿者とやり取りする頻度、投稿へのエンゲージメントといったシグナルで各候補にスコアを付け、最後にフィルターをかけます（ブロックしたアカウント、既読の投稿、ほぼ重複した投稿）。

ランキングはファンアウトの経路から切り離しておきます。ファンアウトは候補を保存するだけで、ランキングは読み取り時に最新のシグナルを使って行います。そうすれば、ランキングモデルを変えても、キャッシュ済みフィードを埋め直す必要はありません。

削除、ブロック、非公開アカウント

フィードは ID を保持しているので、投稿の削除は投稿ストアへの 1 回の書き込みで済みます。フィードサービスは、解決できなくなった ID を捨てます。ブロックや、非公開に切り替えたアカウントにも、読み取り時に同じフィルターが必要です。数百万のキャッシュ済みフィードから ID を取り除くのは遅く、間違えやすいからです。

ページング

フィードのページングにオフセットを使ってはいけません。ユーザーがスクロールしている間にも新しい投稿が先頭に加わるので、「2 ページ目」がずれて重複が表示されます。最後に返した項目の ID やスコアのように、位置をエンコードしたカーソルを返し、「このカーソル以降の項目」を要求するようにします。ランキングされたフィードでは、セッションのランキング済みリストを短時間保存して、後続のページが最初のページと矛盾しないようにします。

アーキテクチャ図

図の読み方は次のとおりです。

• 書き込み経路（上）： 投稿サービスが投稿を保存してイベントを発行します。ファンアウトワーカーはソーシャルグラフを読み、投稿者のフォロワー数を確認します。
• 判断： ほとんどの投稿者については、ワーカーが投稿 ID を各フォロワーのフィードキャッシュにプッシュします。しきい値を超えるアカウントは何もプッシュせず、その投稿は読み取り時に取得します。
• 読み取り経路（下）： フィードサービスは、ユーザーのキャッシュ済みフィードと、投稿ストアにある大きなアカウントの最近の投稿を読み、マージしてランキングに送ります。
• メディア は CDN を通り、フィードサービスを通ることはありません。
• Markdown ブロック は経験則を設計の隣に置いています。

図に載せるべきこと

• 2 つの経路をはっきり分ける。 書き込みと読み取りでは、スケールの問題が違います。
• ファンアウトのしきい値。 あとで変わるとしても、判断の箇所に数字を書きます。
• 何をどこに保存するか。 フィードキャッシュが持つのは投稿ではなく投稿 ID で、内容は投稿ストアにあります。
• ランキングを行う場所。 読み取り時に動くことが、読み手にわかるようにします。

この設計の中心にあるキャッシュは、それだけで図にする価値があります。キャッシュ戦略の記事 を参照してください。イベントとコンシューマー側は イベント駆動アーキテクチャの記事 で扱っています。また、システム設計図の例 では、同じ約束事を別のシステムに当てはめています。

Archboard で作る

1. Google または GitHub でサインインし、図を作成します。
2. C4 モデルパックから 人物 を追加し、続いて投稿サービス、ファンアウトワーカー、フィードサービス、ランキング用に コンテナ ノードを追加します。
3. 投稿ストアとソーシャルグラフ用に C4 モデルパックの データベース ノードを、投稿イベントとフィードキャッシュ用にデータパックの Kafka と Redis を、クラウドパックから CDN を追加します。
4. フォロワーのしきい値用に、フローチャートパックから 判断 と 開始 / 終了 を追加します。
5. 書き込み経路を上に、読み取り経路を下に描き、経験則を書いた基本パックの Markdown ブロックを追加します。

この例で使うダイアグラムノードは 13 個で、Free プランの範囲に収まります。

よくある質問

書き込み時と読み取り時のファンアウトは、どちらがよいですか？ どちらも単独では不十分です。書き込み時のファンアウトは読み取りが速い一方、フォロワーが非常に多いアカウントで破綻します。読み取り時のファンアウトは書き込みが安い一方、読み取りが遅くなります。大規模なフィードはハイブリッドを使います。

フィードキャッシュには何を保存すべきですか？ 新しい順に並べた投稿 ID を、ユーザーごとに数百件まで保存します。投稿の内容は別に取得します。そうすれば、編集や削除のたびにすべてのフィードを書き直さずに済みます。

有名人の投稿にはどう対処しますか？ フォロワー数がしきい値を超えるアカウントはファンアウトを省き、フォロワーがフィードを開いたときに、その最近の投稿を取得します。

フィードのページングはどう動くべきですか？ ページ番号やオフセットではなく、最後に返した項目に基づくカーソルを使います。そうすれば、ユーザーがスクロールしている間に新しい投稿が加わっても重複が起きません。

ランキングはどこで行いますか？ 読み取り時に、マージした候補のリストに対して行います。ファンアウトから切り離しておけば、キャッシュ済みフィードを作り直さずにランキングを変更できます。

無料で始める — 1 シート、クレジットカード不要。