Scaling Writes (HelloInterview) のメモ

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

Patterns

• Real-time Updates のメモ
• Dealing with Contention のメモ
• Multi-step Processes のメモ
• Scaling Reads のメモ
• Scaling Writes のメモ <--- これ 🟢
• Handling Large Blobs のメモ

Patterns Summary

これらを順に試す。

• (1) Vertical Scaling and Database Choices
• (2) Sharding and Partitioning
• (3) Handling Bursts with Queues and Load Shedding
• (4) Batching and Hierarchical Aggregation

(1) Vertical Scaling and Database Choices

todo

(2) Sharding and Partitioning

todo

(3) Handling Bursts with Queues and Load Shedding

todo

🟢 Load shedding strategy

Uber とか
todo

(4) Batching and Hierarchical Aggregation

todo

使用例:

• Design FE Post Search - How can we address the large volume of writes? / Writes of Like Counts
• YouTube TopK - "How can we handle the massive number of writes to the database?"
• Realtime Updates - "How do you maintain message ordering across distributed servers?"

なお、Yelp は 1rps だったので不要。Ad Click Aggregator のメトリクス集計は Flink を使った。

DD "How do you handle resharding when you need to add more shards?" 🔥🔥

Classic Problem

🟢 Naive - with downtime

The naive approach is to take the system offline, rehash all data, and move it to new shards. This creates hours of downtime for large datasets.

🟢 Smart - without downtime

以下のステップを取る。

• (1) Start Dual Write Write 時に old shard と new shard の両方に書き込む。
• (2) Start Backfiller バックグラウンドで、Backfiller jobを走らせ、移行されるべきデータを徐々に old shard から new shard へコピーする。
• (3) Verify 移行されるべきデータが完全に old shard == new shard になっていることを Verify する。
• (4) Switch Read Read を new shard からの読み取りに切り替える。
• (5) Clean Up 移行されるデータを old shard から削除する。

なお、以下のような Dual Write と Backfiller の競合を防ぐため、個々のレコードには timestamp を持たせる。

• Dual Write： ユーザーがデータを更新し、new に「最新データ（Ver 2）」を書き込む。
• Backfiller： 1歩遅れて、old から読み込んでいた「古い過去データ（Ver 1）」を new に書き込もうとする。

なお、レコードのDeleteに関しては、論理削除を行えば良い。以下の二つのアプローチがある。

• 各レコードに deleted カラムを持たせる
• 削除ログを tombstone に書き込み保存する (TODO)

DD "What happens when you have a hot key that's too popular for even a single shard?" 🔥🔥🔥

例えば、Instagram で Likes テーブルへのレコードの保存。
Celebrity の Postには大量のいいねがつく。
問題になるのは、あるキーのレコードのすべてが一つのノードに乗り切らないこと。

(c.f. あるひとつのレコードにライトリクエストが集中する場合の対策は、Dealing with Contention - DD "What about performance when everyone wants to update the same resource?")

以下の３つの方法があり、2-1 > 2-2 > 1 の順で使われる。

• (1) Split All Keys
• (2) Split Hot Keys Dynamically
  • (2-1) ★ Fanout On Read = We can have the readers always check all the sub-keys
  • (2-2) Writers announce the split to the readers

🟢 (1) Split All Keys

すべてのシャードにsubshard が作る。 ゆえにシャード数が k倍になる。

• Writer は、hashing(post_id, n) でシャードを決め、hashing(user_id, k)でサブシャードを決める。これにより、それぞれのキーのレコードが k個のノードに分散して配置される。
• Reader は常にk個のサブシャードのノードを並行して読む。

🟢 (2) Split Hot Keys Dynamically

• (2-1) ★ Fanout On Read = We can have the readers always check all the sub-keys

Hot Key のみに、追加でK個(事前固定)のサブシャードが作られる。しかしreaderはそれを知らず、どのキーを読む場合も、K＋1個のサブシャードを確認する。

• Writer は基本的にサブシャード 0 に書き込む。しかし、local statistics を用いてあるキーが Hot Key だと検知できた場合は、そのキーへの書き込みをhashing(user_id, k)番目のサブシャードに書き込みを行う。
• Readerは常に、k+1個のサブシャードから並行して読みそれらを集計する。

📝 サブシャード0のレコードの個数 != サブシャード1 ~ Kのレコードの個数 となる。
肝心なのは、どのサブシャードに書き込まれるのかが deterministic ではないが、これは問題ない。

TODO: 本当に「Readerは常に、k+1個のサブシャードから並行して読み」が許容されるのかを調べる。
TODO: Taylor Swift ポストへのLikeのように事前にHot Keyになることがわかってる場合はどうするか？

🟢 (2) Split Hot Keys Dynamically

• (2-2) Writers announce the split to the readers

TODO