読書メモ：システム設計の面接試験①
先日購入した以下の書籍の読書メモです。アフィリンクとかじゃあないです。
https://amzn.asia/d/5AeSGTfamzn.asia
1章：ユーザー数０から数百万人へのスケールアップ
以下のような基本的な内容を扱っています。
- 単一サーバーをホストした際のリクエストの流れ
- データベース
- 垂直スケール / 水平スケール
- ロードバランサ
- データベースのレプリケーション
- キャッシュ
- CDN
- ステートレスとステートフル
- データセンター
- メッセージキュー
- ログ
- データベースのスケール
- シャーディングの話とか
一番最初は非常にシンプルな構成で、Webアプリ、データベース、キャッシュなどの全てが単一のサーバーに置かれてる状況を想定して、どんどんリッチでスケーラビリティを持つ、今っぽい構成に変えていく…って流れで構成された章でした。バックエンドエンジニアなら基本的に抑えてるであろう内容だったりするので自分は流し読みしました。
一番最後にデータベースのシャーディングの話が出ているのですが、セレブ問題（特定のデータにやたらとIOが集中する問題でホットスポットキー問題などの名前がついてるらしい？）など、高度なトピックもちょろっと紹介されていたりしました。
2章：おおまかな見積もり
Googleの超天才エンジニア、ジェフ・ディーンの有名な図を引用しながら見積もりの話が導入されています。
内容的には以下のサイトに載ってるもので、ざっくり各処理にどのくらいのレイテンシが期待されるかを示したものです。
Numbers Every Programmer Should Know By Year
プラスでSLO/SLAの考え方が紹介されてました。
3章：システム設計の面接時のフレームワーク
面接時の心構え的なものを説明しているのがこの章です。似たような内容の話をnoteだかMediumだったかで読んだ覚えがあります。面接官と一緒にディスカッションしながら進めようね、あとこういうふうにしちゃダメだよ、という実践的なことが書かれてる印象でした。
「言うは易し、行うは難し」という印象で、モブ面接的なことをやらないと多分自分は身につかない気がしたので転職する際にここで書かれていたことを気にしながら訓練しないとなぁと感じました。
4章：レートリミッターの設計
Ratelimitのアルゴリズムを紹介する章です。スライディングウィンドウは仕事でも利用したことのあるアルゴリズムだったので知ってましたが、rate limitにいろんなバリエーションがあるなんて知りませんでした。紹介されていたのは以下のアルゴリズムです。
- トークンバケット（Token Bucket）
- リーキーバケット（Leaky Bucket）
- 固定ウィンドウカウンタ（Fixed window counters）
- スライディングウィンドウログ（Sliding window log）
- スライディングウィンドウカウンタ（Sliding window counters）
それぞれ得手不得手があるのでユースケースによって使い分けることが重要。実務上ではAPI Gatewayなどの機能やプラグインとかで実現することが多い気がします。
5章：コンシステントハッシュの設計
この章に関して、自分は以前以下のブログを読んでたので頭に入ってきやすかったです。このブログを読めばこの章で書かれてることは大体理解できる気がします。
Consistent Hashing （コンシステントハッシュ法） - Carpe Diem
シャーディングやパーティショニングといったDatabaseのスケール戦略を考えるにあたり、単純にkeyをhash化したものをサーバーの台数で割ってあげて、どのサーバーに割り当てるのかを計算する、というのが素朴なシャーディングの発想です。以下の数式で表現されるもの。
Nはサーバーの台数で、keyというのがDBに保存されるレコードのイメージです。一見よさそうに思えますが、サーバーをスケールさせたり、障害が発生して台数が減ったりした際、つまりNが変化した際にどのようなことが起こるのかを考えてみましょう。
大抵のkeyは別のサーバーに割り当てられることになります。この課題を解決するのがコンシステントハッシュと呼ばれるアルゴリズムです。
ハッシュ空間をリング上に捉え、ハッシュリング上にノードをプロットします。recordを保存するノードを選択する際に、keyをhash化し、このリング上でどこにプロットされるのかを考え、プロットされた点から時計回りに見て一番近いノードに保存する、みたいなことをやるアルゴリズムです。Wikipediaのイメージ図を拝借します。
ノードを追加する場合も削除する場合も、リバランスを考えなきゃならないobjectが少なく済むので楽でいいよねって発想です。
ただ2つ課題があって削除と追加を繰り返してると以下のような状況になり得ます。
これらの課題を解決する仮想ノードの紹介もされています。
１つのノードに対して、ハッシュリング上に複数のプロットを行うことで上記の課題を解決することができます。
感想
あまり「就活対策本」みたいな類の本は普段読まないし、就活をゲーム化する感覚が好きじゃあないので、感覚的には ウッとなるタイトルではあるのですが普通に勉強になるので買ってよかったです。今回読んだ前半部分に当たる章では基本的な考え方や普段利用しているComponentのアルゴリズムの紹介的な章がメインで、後半になるにつれてシステム設計っぽさが出てきます。Youtubeを設計するには？みたいな切り口で議論を展開する章とかもあるので読むのが楽しみです。
