輪読会で読むことになったので、メモ
1章 ユーザー数0から数百万人のスケールアップ
トラフィックをさばくための説明が多い。
- 非リレーショナルデータベース使うときはこんなとき
データが構造化されたグループに限定されていない場合
柔軟性の高い機能を実行する必要がある場合
より多様な入力を行う必要がある場合
データへのアクセスをより迅速に提供できる場合
形状やサイズが柔軟であったり、将来的に変化する可能性のあるデータを保存する場合
データリレーションシップが表形式のプライマリキーと外部キーの形式にうまく収まらない場合
- 垂直スケーリングと水平スケーリング → 基本水平でロードバランサーよね。
- データベースはマスターとスレーブ用意して、読み込みはスレーブで行おう
- キャッシュを使用する注意点 → 揮発性、有効期限、一貫性
たしかに、キャッシュのキー重複すると書き換わるので注意せんとあかん
1章まとめ
どうスケーリングするか
Web層はステートレスに保つ
状態データを外に出す
各階層で冗長性を確保する
可能な限りデータをキャッシュする
キャッシュ有効期限
静的コンテンツをCDNでホスティング
CDNフォールバック (CDNの故障をクライアントが検知し、オリジンにリソースをリクエストできる状態にする)
シャーディングによるデータ層の拡張
セレブ問題 (= ホットスポット・キー問題）が発生する可能性がある
複数のDBサーバを跨ってシャーディングされるとJOINが難しい。一般的な回避策はDBの非正規化
システムの監視と自動化
2章 おおまかな見積もり
覚えておくべき概念
- 2のべき乗
- レイテンシ数値 (プログラマが知っておくべきレイテンシの数値
でぐぐろう)
メモリは早いが、ディスクは遅い
可能ならディスクのシークは避ける
単純な圧縮アルゴリズムは速い
可能であれば、インターネット送信前にデータを圧縮する
データセンターは通常、異なる地域にあり、データセンターにデータを送るのに時間がかかる
- 可用性の数値 → SLA(稼働率)を 99.xxx％でできる限り100に近づける
例: Twitterの QPSのストレージ見積もり
前提条件
- 月間アクティブユーザ数3億人
- 50%のユーザが毎日Twitterを利用
- ユーザは1日平均2件のツイートを投稿
- ツイートの10%はメディアを含む
- データは5年間保存
推定値
- デイリーアクティブユーザ(DAU) → 3億人 * 50% = 1億5000万人
- ツイートのQPS → 1億5000万 * 2ツイート/ 24時間 / 3600秒間 = ~3500
- ピーク時のQPS → 2 * QPS = ~7000
平均的なツイートサイズ
- ツイートID → 64B
- テキスト → 140B
- メディア → 1MB
- メディアの保存量 → 1億5000万210%*1MB = 30TB/日
- 5年間のメディア保存量 →30TB * 365 * 5 = ~55PB
メモ
QPS、ピークQPS、ストレージ、キャッシュ、サーバー数 を計算しておくと面接で◯
3章 システム設計の面接試のフレームワーク
- システム設計の利点は、問題解決の疑似体験ができること
- 協調性、重圧可での仕事ぶり、曖昧さを建設的に議論できるか がみられてる
- 視野の狭さ、過剰ながんこさ、オーバーエンジニアリングでトレードオフ考えないのは駄目
ステップ1: 問題を理解し、設計範囲を明確にする
いきなり飛びつくのではなく、具体を明確に、ユーザー数、サービスのスケール、技術的課題、等聞く。
ステップ2: 高度な設計を提案し、賛同を得る
省略
ステップ3: 設計の深堀り
面接官の思考性にあわせて、深ぼる要素を選定する
→ つまり、面接官を事前に調査できるとなおヨシ
ステップ4: まとめ
やるべきこと → 前提を質問し、コミュニケーションとりながらすすめること
やるべきでないこと → 一つに深ぼりすぎること、コミュニケーションをとらないこと。(大事なので2回)
時間配分
ステップ1: 問題を理解し設計範囲を明確にする 3~10分
ステップ2: 高度な設計を提案し、賛同を得る 10~15分
ステップ3: 設計を深堀りする 10~25分
ステップ4: まとめる 3~5分
4章 レートリミッターの設計
複数リクエストがサーバー過負荷や、コスト増幅になる。また、攻撃にもなる。
ステップ1: 問題を理解し設計範囲を明確にする
- クライアントサイドなのか、サーバーサイドなのか?
- レートリミッターの発火条件は? IP/ユーザーID もしくは他の要件?
- システム規模は?
- 分散環境か?
- 制限されたユーザーに通知する必要ある?
ステップ2: 高度な設計を提案し、賛同を得る
レート制限を実装する時に重要なのは、サーバー側なのか、あらたなミドルウェアか?
いくつかあるが、トークンバケットとリーキーバケットの違いは頭にいれておこう。
トークンバケット → リクエストが来るたびにバケットからトークンを取り、さらに処理します。トークンがない場合、リクエストはドロップされ、ユーザーは再試行する必要があります。
リーキーバケット → キューを使用してレート制限を実装するシンプルで直感的な方法です。これは単純な先入れ先出しのキュー（FIFO）です。新しいリクエストがキューに追加され、新しいリクエストのスペースがない場合、それらは破棄（リーク）されます。
ステップ3: 設計の深堀り
Redisを用いたレートリミッターの実装方法の話。
やはりRedisは集中型データストアなので、複数のレートリミッターのためヨシ
ステップ4: まとめ
システムアーキテクチャ、分散環境におけるレートリミッター、性能の改善化、監視について話してきたが、以下を言及できると更にいい
- ハードウェアとソフトウェアのレートリミッター
- 異なるレベルでのレート制限
- アプリケーションレイヤーの話だけだったが、IP等はまた別で考えてね
- レート制限を受けないようにする
- クライアントキャッシュでAPIを頻繁に叩かせない
- 例外から回復できるように、エラーハンドリングしっかりする
- 再発火ロジックに十分なバックオフタイムを追加する
感想
5章 コンシステントハッシュの設計
コンシステントハッシュの説明
図の説明は省略
5章まとめ
- サーバ追加、削除時に最小化したキーを再分配できる
- データが均等に分散されるため、水平スケーリングが容易
6章 キーバリューストアの設計
- キーバリューストアのペアの値として、 文字列、リスト、オブジェクトが使用可能
- ベクタークロック: 前のデータのバージョンを+1した上でログに残し、最終的にログには1バージョンにつき一つのデータしか有効にしない
- マークルツリー: 二つのトランザクションのハッシュ値二つをあわせたデータに対して、新たに一つのハッシュ値を計算するという操作を繰り返して完成するハッシュ値のツリー構造のことです。
分散型キーバリューストア
分散ハッシュテーブルとも呼ばれ、キーバリューのペアを分散して配置する。
CAPの定理の理解が重要になる
CAPの定理 → 一貫性、可用性 、および 分割耐性（CAPの「C」、「A」、「P」）という3つの望ましい特性のうち、2つだけを提供することができるというもの
-
CP データベース: CP データベースは、可用性を犠牲にして一貫性とパーティション耐性を提供します。任意の 2 つのノード間でパーティションが発生すると、システムはパーティションが解決されるまで、一貫性のないノードをシャットダウンする (つまり、使用不可にする) 必要があります。
-
AP データベース: AP データベースは、一貫性を犠牲にして可用性とパーティション耐性を提供します。パーティションが発生すると、すべてのノードは利用可能なままになりますが、パーティションの間違った端にあるノードは他のノードよりも古いバージョンのデータを返す可能性があります。(パーティションが解決されると、AP データベースは通常、ノードを再同期して、システム内のすべての不整合を修復します。)
-
CA データベース: CA データベースは、すべてのノードにわたって一貫性と可用性を実現します。ただし、システム内の 2 つのノード間にパーティションがある場合はこれを行うことができないため、フォールト トレランスを提供できません。
7章 分散システムにおけるユニークIDジェネレータの設計
もう一度 → システム設計の面接試験における最初のステップは、明確な質問をすること
アプローチ方法↓ (長所と短所は省略)
- マルチマスターレプリケーション → データベースサーバの数に応じて、IDがインクリメントされる。
- UUID → 128ビットなので、毎秒10億個のUUIDを100年間生成して、1回衝突する可能性が50%
- チケットサーバ → 単一のデータベースサーバで集中的にauto_increment を使う
- Twitterによるsnowflakeアプローチ → IDを異なるセクションでわけて構成する
- 符号ビット (1ビット)
- タイムスタンプ (41ビット)
- データセンターID (5ビット)
- マシンID (5ビット)
- シーケンス番号 (12ビット)
8章 URL短縮サービスの設計
- おおまかな見積もり
301 → 恒久的な転送
302 → 一時的な転送
BASE62 → ‘A'～'Z’、‘a'～'z’、‘0'～'9’の62種類、64の場合は + と - が入る
分析を重視する場合、クリック率やクリック元をより簡単に追跡できる302リダイレクトの方が適している。
9章 Webクローラの設計
- Web マイニング → ウェブサイトの構造やウェブ上のデータを利用して行うデータマイニングのことである。ウェブ上にあるデータやコンテンツ、テキスト情報から役立つ情報を抽出する処理のことで、掲示板やブログ、商品レビューの情報から意見・評判を抽出するシステム、SNSサイトやEコマースサイトからの人間や商品の関係性を抽出するシステム等が実用化されている。
Webクローラの基本的なアルゴリズムはシンプル↓
- URLが与えられたら、指定されたすべてのページをダウンロード
- これらのWebページから、URLを抽出する
- ダウンロードするURLのリストに新しいURLを追加する。1~3をループする。
だが、実際のWebクローラは複雑性が高い。
良いクローラの特徴として、スケーラビリティ、ポライトネス、拡張性、堅牢性。
詳細は割愛(再度読む)
10章 通知システムの設計
通知には3種類ある。 モバイルプッシュ、SMS、eメール
- 通知で重要なこと → 再通知、トラッキング、スケーラブルな設計、二重送信、ユーザー設定の尊重、レート制限
11章 ニュースフィードシステムの設計
Fanoutサービス → ある投稿をフォロワーや友人全員に配信すること。つまり 1対N
ニュースフィードキャッシュ層を多く持つと良い?
12章 チャットシステムの設計
チャットシステムは、1vs1か 1vsNかでだいぶ設計が変わるので、質問をし機能要件を具体化することが重要視される。
- ロングポーリング → クライアントが利用可能なメッセージがあるorタイムアウト閾値に達するまで接続しておく。
- WebSocketについて調べてみた
- ハートビート機能 → 送信側MCAの転送キューにメッセージがない場合，受信側MCAに対して一定間隔でハートビートメッセージを送信し，受信側MCAの応答の有無によってお互いが正常に動作していることを確認する機能
- ふるえるぞハート！燃えつきるほどヒート！！
- Pub/Sub メッセージングとは
13章 検索オートコンプリートシステムの設計
インクリメンタルサーチや、自動サジェスト
- トライデータ構造 → あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している
14章 YouTube の設計
- トランスコーディング → 1つのコーディングから、別のエンコーディングにデータを変換する処理。
- raw動画は大量の記憶領域を消費する。互換性を担保するために、フォーマット対応必須。高品質と低品質で動画を用意するとヨシ。特にモバイルは、ネットワーク状況で高品質と低品質使いこなすことがスムーズ体験には欠かせない
- メタデータ → データのためのデータ
15章 Googleドライブの設計
- 複数環境下からの同期の競合を考える必要性あり
印象に残った点
- あくまでも、システム設計の面接に解はなく、そこまでのプロセスが重要である
- レートリミッターのアルゴリズム興味深い
- 以前やった実装で、リリース重視したから retry の分数でごまかしたけど、リーキーバケットアルゴリズムで実装したらヨシだな
- ん〜5章のコンシステントハッシュ、一読したけどちんぷんかんぷんだった また読もう
- CAPの定理は、サービスによって、キーバリューストアの設計を変える必要がある。
- 6章だが、ネットワーク障害時には、データの正確性を重視してシステムを止める or 使えることを重視して、多少の値の不正確さを許容する 必要性がある。トレードオフ
- Twitterによるsnowflakeアプローチ。 複数構成で作成する方が、デバッグしやすくてよさそう
- 9章、クローラの設計のシステム面接ってなかなかないだろうが、設計の方法はぼんやりと理解した
- 前職でも、クローラしすぎて某サイトからアクセス制限返すようにされたっけ
- 12章のWebSocket、どこかでしっかりと学んでおきたい。チャットシステムの設計は、かなり力つきそう。１からやってみたい。
- 13章の検索、elasticsearch以外で詳しくなりたい
- トライデータ構造をRDBで表現すると、カオスになるが、もし表現するのであれば、検索テーブル自体をマスタで持たせた方が良さそう
- 14章 メタデータ → jsonbで使うことたまにあるけど、可変しやすいから使うが、PUT必要なら使わんわな
実際の設計面の話は参考にしつつも、この設計を面接で問いてくる企業はそこまで多くなさそう。
実際に大きな、7章以降の題材を設計することになった時に、また読みに戻ってくる。
