書籍「System Design Interview : Mastering Basic Introduction to System Analysis and Design」を読んだので内容をまとめる。
以下の内容は、ほとんどClaude3 Opusを使用して作成している。
CHAPTERごとの要約
CHAPTER 1: SCALE FROM ZERO TO MILLIONS OF USERS
システム設計における基本的な概念と、シンプルなサーバー構成から数百万ユーザーをサポートする分散システムまでの段階的なスケーリングの方法を解説。垂直スケーリングと水平スケーリング、データベースのレプリケーション、キャッシュ、CDNなどの技術を使ってシステムを拡張していく手順を示している。
印象的なフレーズ
- A journey of a thousand miles begins with a single step.
- Iterating on what we have learned in this chapter could get us far.
重要なポイント
理解度を確認する質問
1. 垂直スケーリングと水平スケーリングの違いを説明してください。
2. データベースのレプリケーションとは何ですか？ どのような利点がありますか？
3. システム設計において、どのようにしてシステムの可用性を向上させますか？
CHAPTER 2: BACK-OF-THE-ENVELOPE ESTIMATION
システム設計インタビューでよく出題される、ラフな見積もりの手法を紹介。2の累乗、レイテンシー、可用性など、エンジニアが知っておくべき基本的な概念を説明し、Twitterのユースケースを使って、ストレージ容量やQPSの見積もり方を例示している。
印象的なフレーズ
- Back-of-the-envelope calculations are estimates you create using a combination of thought experiments and common performance numbers to get a good feel for which designs will meet your requirements.
- Back-of-the-envelope estimation is all about the process.
重要なポイント
- エンジニアは、パフォーマンスの数値感覚を身に付けておく必要がある。
- 2の累乗、レイテンシー、可用性など、覚えておくべき基本的な数値がある。
- 明確な数値がなくても、ラフな見積もりができる能力が求められる。
理解度を確認する質問
1. Back-of-the-envelope estimationとは何ですか？ その目的は何ですか？
2. システムのストレージ容量やQPSを見積もるために必要な情報は何ですか？
3. エンジニアが知っておくべきレイテンシーの値にはどのようなものがありますか？
CHAPTER 3: A FRAMEWORK FOR SYSTEM DESIGN INTERVIEWS
システム設計インタビューを攻略するための4つのステップからなるフレームワークを提案。要件を明確にし、ハイレベル設計を作成し、重要なコンポーネントに深堀りし、最後にまとめを行う。それぞれのステップにおけるコツや、NGポイントも合わせて解説している。
印象的なフレーズ
- Every system design interview is different.
- Your interview is not a trivia contest.
- Understand the requirements and clarify ambiguities.
重要なポイント
理解度を確認する質問
1. システム設計インタビューを攻略するための4つのステップは何ですか？
2. システム設計において、要件を明確にすることが重要なのはなぜですか？
3. システム設計インタビューで避けるべきことは何ですか？
キーワード
システム設計インタビュー、問題の明確化、ハイレベル設計、詳細設計、ラップアップ
CHAPTER 4: DESIGN A RATE LIMITER
レートリミッター（API に対するリクエスト数を制限するシステム）の設計方法を解説。トークンバケツ、リーキングバケツ、固定ウィンドウカウンターなどのアルゴリズムを比較し、レートリミッターをスケーラブルかつ、高可用性を担保できるように設計していく。分散環境における課題解決の方法にも触れている。
印象的なフレーズ
- Rate limiting helps protect services against abusive behaviors targeting the application layer.
- The interaction between an interviewer and a candidate helps to clarify the type of rate limiters we are trying to build.
重要なポイント
理解度を確認する質問
1. レートリミッターを実装する主な目的は何ですか？
2. トークンバケツアルゴリズムとリーキーバケツアルゴリズムの違いは何ですか？
3. 分散環境でレートリミッターを実装する際の課題は何ですか？
キーワード
レートリミッター、トークンバケツ、リーキーバケツ、固定ウィンドウ、スライディングウィンドウ、分散環境
CHAPTER 5: DESIGN CONSISTENT HASHING
分散システムでのサーバー追加・削除時のデータ再配置を最小限に抑える技術である、コンシステントハッシュの概念と実装方法を解説。ノードの管理にはバーチャルノードを使うなど、実践的なテクニックも紹介している。
印象的なフレーズ
- Consistent hashing is a special kind of hashing such that when a hash table is re-sized and consistent hashing is used, only k/n keys need to be remapped on average.
- Consistent hashing is widely used in real-world systems.
重要なポイント
- 分散システムでは、ノードの追加や削除が頻繁に発生する。
- ノードが変更されたときのデータの再配置を最小限に抑えるために、コンシステントハッシュが使われる。
- 仮想ノードを使うことで、データの偏りを解消できる。
理解度を確認する質問
1. コンシステントハッシュとは何ですか？ どのような利点がありますか？
2. コンシステントハッシュにおける仮想ノードの役割は何ですか？
3. コンシステントハッシュが実際のシステムでどのように使われているか例を挙げてください。
キーワード
コンシステントハッシュ、分散ハッシュテーブル、仮想ノード、データ分散
CHAPTER 6: DESIGN A KEY-VALUE STORE
Key-Value型のデータストアの設計方法を解説。CAP定理をベースに、データのパーティショニング、レプリケーション、整合性の担保など、分散システムならではの設計上の課題をクリアしていく。Dynamo、Cassandra、BigTableなどの実際のシステムを参考に、詳細設計までカバーしている。
印象的なフレーズ
- Nowadays, key-value stores are classified based on the two CAP characteristics they support.
- You shall work with the interviewer to identify and prioritize components in the architecture.
重要なポイント
CHAPTER 7: DESIGN A UNIQUE ID GENERATOR IN DISTRIBUTED SYSTEMS
分散システムでユニークIDを生成する仕組みの設計方法を解説。IDの生成には、マルチマスターレプリケーション、UUID、チケットサーバーなどの手法があるが、Twitterで使われているSnowflake方式が望ましいとして、その詳細を解説している。
印象的なフレーズ
- The objective is to design a unique ID generator that can generate non-repetitive incrementing IDs in a distributed environment.
- Instead of generating an ID directly, we divide an ID into different sections.
重要なポイント
- 分散システムでは、IDの重複を避けるために、グローバルにユニークなIDを生成する必要がある。
- IDの生成には、UUID、チケットサーバー、Snowflake方式などの選択肢がある。
- IDの構成要素（タイムスタンプ、シーケンス番号など）を適切に設計する。
理解度を確認する質問
1. 分散システムでユニークIDを生成するための要件は何ですか？
2. Twitterで使われているSnowflake方式のIDの構成要素は何ですか？
3. マルチマスターレプリケーションを使ったID生成の問題点は何ですか？
キーワード
ユニークID生成、水平スケーリング、タイムスタンプ、Snowflake
CHAPTER 8: DESIGN A URL SHORTENER
短縮URLサービス（例: tinyurl）の設計方法を解説。短縮URLに使う文字種の選択、ハッシュ関数、データベーススキーマ、短縮/展開のフローなどをカバー。最後に、レートリミッターやアナリティクスなど、実際のサービスに必要な機能も触れている。
印象的なフレーズ
- URL shortening and analytics services are commonly asked system design interview questions.
- Base conversion is another approach commonly used for URL shorteners.
CHAPTER 9: DESIGN A WEB CRAWLER
ウェブクローラー（インターネット上のページを収集し、インデックスを作成するボット）の設計方法を解説。ブロードクロールとフォーカスクロール、増分クロールなどの手法を整理し、URL frontier、HTMLパーサー、ストレージなどの、クローラーを構成する要素をどう設計するかを議論。並列分散処理を使ってスケールさせるポイントにも触れている。
印象的なフレーズ
- Building a scalable web crawler is an extremely complex task.
- Politeness, robustness, and extensibility are the most important characteristics of a good web crawler.
重要なポイント
CHAPTER 10: DESIGN A NOTIFICATION SYSTEM
モバイルプッシュ通知、SMS、emailなど、複数の経路で通知を送るシステムの設計方法を解説。独立性の高い、疎結合なマイクロサービスとメッセージキューを組み合わせたアーキテクチャを推奨。例外処理、遅延対策、分析などの実装ポイントを挙げ、詳細に設計している。
印象的なフレーズ
- Building a scalable system that sends out millions of notifications a day is not an easy task.
- Decouple different components in the notification system using message queues.
重要なポイント
- 通知システムでは、複数の配信チャネルを柔軟にサポートする必要がある。
- メッセージキューを使って、システムの疎結合性を高める。
- 配信の信頼性、リアルタイム性、スケーラビリティなどの要件を満たす設計が求められる。
理解度を確認する質問
1. 通知システムが対応すべき配信チャネルにはどのようなものがありますか？
2. 通知システムの設計でメッセージキューを使う理由は何ですか？
3. 通知システムに求められる主な非機能要件は何ですか？
キーワード
通知システム、プッシュ通知、SMS、Eメール、メッセージキュー、ファンアウト
CHAPTER 11: DESIGN A NEWS FEED SYSTEM
SNSのニュースフィードを生成するシステムの設計方法を解説。記事の投稿から、友人のタイムラインへの配信まで、非同期処理を使って効率的に処理する。記事データはキャッシュとデータベースを使い分ける。データモデルやファンアウト方式について詳しく議論している。
印象的なフレーズ
- Each news feed is not just a list of posts; it contains rich metadata like the user, comments, likes, etc.
- Cache is extremely important for a news feed system.
重要なポイント
- ニュースフィードの生成では、膨大な量の投稿データを高速に処理する必要がある。
- フィードデータのファンアウト方式（プッシュ型とプル型）を適切に選択する。
- 投稿データのスキーマ設計、キャッシュ戦略、データベースのスケーリングが重要。
理解度を確認する質問
1. ニュースフィードの生成において、フィードパブリッシュフローとフィード取得フローの違いは何ですか？
2. ニュースフィードシステムにおいて、キャッシュを使う主な目的は何ですか？
3. ファンアウトにおけるプッシュ型とプル型の長所と短所は何ですか？
キーワード
ニュースフィード、キャッシュ、ファンアウト、プッシュモデル、プルモデル、スケーラビリティ
CHAPTER 12: DESIGN A CHAT SYSTEM
チャットサービスの設計方法を解説。メッセージのやりとりにはWebSocket を使って双方向通信を実装。サービスディスカバリー、メッセージ同期、プレゼンス管理などの課題をクリアしながら、1対1およびグループチャットをスケーラブルに設計している。
印象的なフレーズ
- The fundamental responsibility of a chat service is to enable real-time message exchange between clients.
- How a chat service synchronizes messages to multiple devices reveals the ingenuity of the engineering team.
重要なポイント
- チャットサービスの設計では、メッセージの low latency が重要な要件となる。
- WebSocket を使って、サーバーとクライアント間の双方向通信を実現する。
- 複数デバイス間でのメッセージ同期の仕組みを工夫する。
理解度を確認する質問
1. チャットサービスにおいて、WebSocketを使うメリットは何ですか？
2. チャットサービスにおけるサービスディスカバリーの役割は何ですか？
3. オンラインプレゼンス管理において、ハートビートメカニズムが必要なのはなぜですか？
キーワード
チャットシステム、WebSocket、ロングポーリング、サービスディスカバリー、オンラインプレゼンス
CHAPTER 13: DESIGN A SEARCH AUTOCOMPLETE SYSTEM
検索エンジンのサジェスト機能（検索語の自動補完）の設計方法を解説。histórical dataからどう効率的にインデックス（Trie）を構築するか、前方一致検索をどう高速に行うかなど、パフォーマンスに重点を置いた設計を議論。データ構造とアルゴリズムの選択が設計のカギ。
印象的なフレーズ
- Search autocomplete helps users find results faster and discover popular queries they may not have thought about.
- The system must be able to store previous queries, and efficiently retrieve a subset of them when a user types a prefix.
重要なポイント
- 検索のオートコンプリートでは、履歴データから関連するクエリを高速に抽出する必要がある。
- クエリログの収集パイプラインと、クエリ補完用のインデックス（Trie）の設計がポイント。
- レスポンス速度を上げるために、様々な最適化を行う。
理解度を確認する質問
1. 検索オートコンプリートシステムの主要な構成要素は何ですか？
2. オートコンプリート用のインデックスとして、Trieが適している理由は何ですか？
3. レスポンス速度を上げるための最適化手法にはどのようなものがありますか？
キーワード
検索オートコンプリート、Trie、データ収集、バックエンド、フロントエンド、プレフィックス検索
CHAPTER 14: DESIGN YOUTUBE
動画配信サービスの設計方法を解説。動画のエンコーディングと、CDNを使った配信方法を中心に、大量の動画データをさばくためのテクニックを紹介。ユーザーから見た使い勝手の良さと、インフラコストのバランスを取るのがポイント。
印象的なフレーズ
重要なポイント
理解度を確認する質問
1. 動画配信サービスにおけるビデオトランスコーディングの目的は何ですか？
2. ビデオのアップロード処理を高速化するための工夫にはどのようなものがありますか？
3. 動画配信におけるCDNコストを最適化するための方法は何ですか？
CHAPTER 15: DESIGN GOOGLE DRIVE
オンラインストレージサービスの設計方法を解説。シンプルなシングルサーバーでスタートし、ボトルネックを潰しながら段階的に設計を洗練させていく。ブロックサーバー、メタデータの管理、同期ロジック、通知サーバーなど、システムを構成する要素を一つずつ議論。運用コストにも配慮が必要。
印象的なフレーズ
- Cloud storage services (e.g., Google Drive) have become very popular in recent years.
- It is unrealistic to build everything from scratch in an hour but system design interviews are not about that anyway.
重要なポイント
- オンラインストレージサービスの設計では、シンプルな設計から始めて段階的に改善していくアプローチが有効。
- ファイルのアップロード、ダウンロード、同期、バージョン管理など、基本的な機能の設計が重要。
- メタデータの管理、通知機能、コスト最適化など、実際のサービスに必要な要素を盛り込む。
よく使われる重要な概念
- CAP定理（Consistency, Availability, Partition Tolerance）
分散システム設計における重要な定理。一貫性、可用性、分断耐性の3つの特性のうち、2つしか満たせないという制約がある。システムの要件に応じて、適切なトレードオフを選択する必要がある。
- 水平スケーリングと垂直スケーリング
システムの拡張性を高めるための2つのアプローチ。水平スケーリングはサーバー台数を増やすことで、垂直スケーリングは単一サーバーのスペックを上げることでスケーラビリティを実現する。
- シャーディングとレプリケーション
データを複数のノードに分散して格納する方法。シャーディングはデータを分割してスループットを上げ、レプリケーションは複製を作って可用性と耐障害性を高める。
- コンシステントハッシュ
分散ハッシュテーブルにおいて、ノードの追加や削除が発生してもデータの再配置を最小限に抑えるためのアルゴリズム。仮想ノードの概念を使うことで、データの偏りを解消できる。
- メッセージキュー
非同期通信を実現するためのミドルウェア。システムの疎結合性を高め、依存関係を減らすことができる。スケーラビリティと信頼性の向上に寄与する。
- パブリッシュ・サブスクライブモデル
メッセージングシステムにおいて、パブリッシャーが発行したメッセージを、サブスクライバーが非同期に受信するモデル。イベントドリブンなシステムを実現するのに適している。
- ブルームフィルター
要素が集合に属しているかを確率的に判定するためのデータ構造。少ないメモリで高速に判定できるが、偽陽性（実際には存在しないのに存在すると判定される）の可能性がある。
- マークル木
大量のデータを効率的に検証するためのデータ構造。ハッシュ値を木構造で管理することで、部分的なデータ検証が可能になる。
- トライ（プレフィックス木）
文字列検索を高速に行うためのデータ構造。文字列のプレフィックスを共有することで、メモリ効率が良い。オートコンプリートなどの用途に適している。
- バックプレッシャー
データの流量を制御する仕組み。データの発生速度が処理速度を上回ったときに、データの流入を制限することでシステムの安定性を保つ。
書評
システム設計は、ソフトウェアエンジニアにとって避けて通れない重要なスキルである。特に、大規模なWebサービスを開発する際には、アーキテクチャの選択がシステムの成否を左右すると言っても過言ではない。本書「System Design Interview」は、実際のシステム設計インタビューを想定した問題を通じて、システム設計の考え方と実践的なテクニックを学ぶことができる良書である。
本書から学ぶべき最も重要なことは、システム設計に正解はないということだ。提示される問題は、要求が曖昧で、解釈の余地が大きい。そのため、設計者には、要件を明確にし、ユースケースを具体化し、トレードオフを適切に評価する能力が求められる。また、システムを一気に完璧に設計するのではなく、シンプルな設計から始めて、ボトルネックを特定しながら段階的に改善していくアプローチが重要だ。
システム設計で鍵となるのは、スケーラビリティ、可用性、パフォーマンスなどの非機能要件をいかに満たすかである。本書では、データのパーティショニング、レプリケーション、キャッシュ、負荷分散など、スケーラブルでレジリエントなシステムを設計するための基本的な概念とテクニックが体系的に説明されている。また、CAP定理など、分散システム固有の制約を理解し、適切なトレードオフを選択することの重要性も強調されている。
さらに、本書は、実世界のシステムを例に、具体的な設計の進め方を示している。Googleの検索エンジン、FacebookのニュースフィードなどのサービスMを題材に、実際にどのような設計上の課題があり、それをどのように解決するかを議論している。これらの事例は、システム設計の考え方を実践的に学ぶための格好の教材となっている。
システム設計の極意は、機能要件と非機能要件のバランスを取りながら、シンプルさ、柔軟性、拡張性を備えたアーキテクチャを設計することにある。本書は、そのために必要な知識と経験を体系的に学ぶための優れたガイドブックである。アーキテクチャの設計力は一朝一夕には身につかないが、本書で学んだ原理原則と思考プロセスを実践の中で繰り返し適用していくことで、優れたシステムを設計する力を着実に高めていくことができるだろう。
