Design FB Post Search (HelloInterview) のメモ

この記事で学んだことをメモる。

High Level Design

• 上のメモでは、InvertedIndex をDynamoDBに収納しているが、記事と動画では、
  • 投稿日によるソートのためのインデックスは Redis List に収納している。
  • ライク数によるソートのためのインデックスは Redis SortedSetに収納している。
• ライク数によるソートのためのインデックスにおいては、ランク値が順次更新されていくので注意する。

DD How can we handle the large volume of requests from users?

CDN でキャッシュする。(ref. Scaling Reads - CDN and Edge Caching)

📝 Cache-Control headers tell a CDN how long to store a resource and whether to validate it before serving.

DD How can we handle multi-keyword, phrase queries?

Bigram を Indexed Index に含める。

なお、ストレージコストを抑えたいならば、次の方法を取る。

1. ドキュメントでの出現頻度が高い bigram だけをinverted index に含める
2. 複数語による検索時は、inverted index から結果が含まれていない場合は、各単語での検索を並行して行い、最後にそれらの結果の intersection を取る。

TODO: Step1 は Count-Min Sketch を使うことができる。

📝 Lucene では、Word/Token単位の N-gram を Shingle と呼んでいる。

DD How can we address the large volume of writes?

Post Creation

厳密には、Post Creation 時に、「そのPostに含まれる単語のそれぞれについて、inverted index を更新する」部分の書き込み負荷が高い。これをなんとかしたい。

結論、PostService --> Kafka <-- IndexWorker --> Redis Cluster構成にする。

• PostServiceサーバーはトラフィックに合わせてオートスケーリング。
• バッファとしてKafkaを使用。Partitionを利用する。
• IndexWorker は Kafkaのキューの長さに合わせてオートスケーリング。
• Redis Cluster は、単語をキーとしてパーティションする。

ref. Scaling Writes のメモ

Like Event 🔥🔥

100K rpsに対応する必要がある。

Likesテーブルから特定の動画のLike数を求めるクエリは重すぎるため、Post.like_countにcacheしておく。ここで問題になるのは以下の二つ。

• Like テーブル: 100K rps　のwriteは1つのDBでは過負荷。
• Post テーブル: 人気のPostには大量のLikeがつく。よって、Post.like_count を毎回更新すると過負荷になる。
• Redis Inverted Index: Postのlike_count更新のたびに更新すると過負荷になる。

このために、Like サービスは、Likesテーブルへのレコード作成と、Kafkaへのエンキューの Dual Writeを行う。
このために、Like サービスは、Likesテーブルへのレコード作成を行い、CDC を Kafkaへのエンキューし、Like countの集計を行う。

Like テーブルのレコード作成

DB を user_id をパーティションキーとしてシャーディングする。
100K / 10K = 10 シャードあれば良い。

Post の like count を Batching して書きこむ

Likeカウントは Kafka のメッセージを 30秒間隔でワーカーが Batching し、ワーカーがまとめて処理。そのWindowでの各投稿の like_count の増加分を　Post.like_count に加算する。

これだけでも十分負荷は下がるが、さらなる最適化として、2-stage architecture を行う。

2-Stage Architecture

(2) において InvertIndex の ランクである Like数を以下のように更新する。

• InvertedIndex の ランクを rounded(log like_count) にする。
• Postsテーブルの CDC を IndexWorker が読み取り、その変更によってrounded(log like_count)の値が変更された場合のみ、InvertedIndex を更新する。
• Like count top N のクエリ時には、上位2N個アイテムを読み出し、それぞれの正確なlike_countを posts テーブルで確認してソートし、topNのみを返す。

📝 LikeCountをリアルタイムで正確に求めるのは難易度が高い。似たものは以下。

• Ad Click Aggregator
  • Clickカウントは Kafka + Flink で集計
• YouTube TopK
  • Viewカウントは Kafka + Batching and Hierarchical Aggregation で集計

DD How can we optimize storage of our system?

インデックス作成後、定期ジョブで以下を行う。

• Stop words (e.g. the, and) -> 削除
• 出現回数が非常に高いキーワード -> top 1000のように検索結果として表示するpost数の上限(cap)を決め、それ以降は削除
• 検索頻度が非常に低いキーワード -> cold storage (S3) へ移動

なおS3においては、object key をkeywords/<hash(keyword)>し、ファイル内に post_id のリストを入れれば良い。
TODO: なぜhashにするのか調べる。