- システム設計において、完全な整合性、可用性、低遅延、高スループットを同時に満たすことは、実質的に難しい課題である
- アプリケーションに合ったバランスポイントを見つける形で、適切な設計を探すことが重要である
- Blueskyは、フォロー中フィード/タイムラインの設計で、書き込み性能を改善するために、整合性を一部犠牲にするトレードオフを採用した
- その結果、ユーザーに悪影響を与えることなく、P99レイテンシが96%以上減少する効果を得た
タイムラインのファンアウト
- Blueskyでユーザーが投稿を行うと、システムによってインデックス化され、データベースに保存され、APIレスポンスとして提供される
- 同時に、この投稿を各フォロワーのタイムラインテーブルに挿入する「ファンアウト」処理が行われる
- これはフォロワー一覧を取得した後、各フォロワーのタイムラインテーブルに逆順で挿入する方式である
- タイムラインテーブルはユーザーごとにパーティショニングされ、分散DB(ScyllaDB)に保存され、高可用性のため複数のシャードにレプリケーションされる
- ユーザーごとに異なるシャードへ割り当てられる可能性がある
- ストレージ容量を節約するため、一定の長さを超えたタイムラインでは古い投稿参照を定期的に削除する
ホットシャード問題
- Blueskyには約3,200万人のユーザーがおり、タイムラインデータベースは数百のシャードに分かれている
- 数百万人が利用するシステムでは、極端に多くのフォロー関係を持つユーザーが存在しうる
- 1つのシャードには多数のユーザーのタイムラインがまとめて保存される
- 特定のユーザーが非常に多くの書き込みを発生させると、そのシャードが過負荷状態（「ホットシャード」）になる
- このようなホットシャードでは書き込みや読み取り処理が集中し、同じシャード上の他のユーザーにも遅延が波及する問題が生じる
レイテンシの蓄積
- あるユーザーが2,000,000人のフォロワーを持つ場合、順次書き込むと20分以上かかることがある
- これを減らすためにファンアウトを並列化すると、平均レイテンシは短くなる
- しかし、P99レイテンシ（約15ミリ秒以上）が何度も発生し、並列処理全体を遅らせる可能性がある
- フォロワーが非常に多い場合、P99またはP99.9レイテンシにより、全体のファンアウト時間が最悪では数分から数十分にまで延びることがある
ロッシーなタイムライン
- フォロー数が過度に多いユーザーに対しては、すべての投稿を正確な順序で表示することは現実的に不可能である
- 人間が実際にすべての投稿を消費することも難しい
- そのため、一定のしきい値（例:
reasonable_limit）を超えるフォロー数を持つユーザーのタイムラインでは、一部の書き込みを確率的に「ドロップ」する方式を導入した
loss_factor = min(reasonable_limit / num_follows, 1) の式を使用する- ファンアウト時に乱数を生成し、
loss_factorより大きい場合はタイムラインへの書き込みを省略する
- これにより、特定ユーザーのタイムラインに対する過剰な書き込みを抑え、シャード全体の性能低下を防ぐ
キャッシュについて
- タイムライン書き込みは毎秒100万件以上発生するため、各書き込みごとにユーザーのフォロー数をDBで直接参照すると負荷が非常に大きくなる
- その代わりに、Redisにフォロー数の多いアカウントを sorted set としてキャッシュする
- ファンアウトサービスのインスタンスは30秒ごとにこのキャッシュ情報をメモリへ読み込む
- その結果、ファンアウト処理中でも高フォロー数ユーザーの情報を高速に参照できる
- キャッシュ情報が完全に最新である必要はないため、ある程度の不完全さを受け入れつつ、性能とスケーラビリティを高めるアプローチである
結果
- ロッシーなタイムラインを導入した後、Timelinesデータベースではホットシャードが事実上なくなった
- ファンアウト1ページの処理にかかるP99レイテンシは90%以上減少した
- ファンアウト全体の処理時間を見ると、P99基準で5〜10分かかっていた処理が10秒未満に短縮された
- 整合性を一部犠牲にしても、サービス利用者の期待を十分に満たしつつ、大規模なスケーラビリティを維持できることを示した
- Blueskyのタイムラインアーキテクチャには依然として改善の余地があるが、今回の変更で書き込みスループットとスケーラビリティが大幅に向上した
1件のコメント
Hacker Newsの意見
システム好きとして、こういう記事を楽しむタイプだ。「完璧であるべきだ」という考え方に陥りやすい
タイムラインをアカウントの人気度に応じたハイブリッド方式で実装しない理由が気になる
興味深い問題に対する興味深い解決策だ。共有してくれてありがとう
一貫性を犠牲にするこの戦略について気になる。読み取りまたは書き込みで完全なファンアウト以外の方法について何か考えがあるのか知りたい
どのユーザーもフォローしている何千人ものユーザーが投稿したすべてを、完全な時系列で受け取る必要はないが、タイムラインに常に新しいコンテンツがあるよう、十分な量のコンテンツを提供するのは合理的だ
ホットシャード問題を避けるためにフォロワー数を制限する方法がどう機能するのか気になる
AWSにはこの問題に対する優れた一般的アプローチがある
何十万人ものユーザーをフォローしているアカウントは、コンテンツをスクレイピングするボットアカウントであることが明らかだ。ブロックして終わりでいい
ユーザーのプロフィールへ直接移動してすべての投稿を見ると、タイムラインにあるはずの投稿がないことがある
各「ページ」が次のページの取得をブロックする形でファンアウトを実装した理由が気になる