Open2023/06/12にコメント追加5

「システム設計の面接試験」から学ぶシステム設計

Reference

ユーザ数ゼロから数百万人へのスケールアップ

一人のユーザをサポートするシステムを構築し、徐々にスケールアップして何百万人ものユーザにサービスを提供することを目指す

垂直スケーリングと水平スケーリング

垂直スケーリング -> スケールアップ
水平スケーリング -> スケールアウト
垂直スケーリングの重大な制約
- ハードウェアとしての限界がある。一台のサーバに無制限にCPUとメモリを追加することは不可能
- フェールオーバーや冗長性がない。一台のサーバがダウンすると、Webサイトやアプリケーションも一緒に完全にダウンしてしまう
垂直スケーリングには限界があるため、大規模なアプリケーションには水平スケーリングがより望ましい

ロードバランサ

受信したトラフィックをロードバランサ・セットで定義されたWebサーバに均等に分散させる
ユーザはロードバランサへ対してパブリックIPで直接接続、ロードバランサからWebサーバに対してはセキュリティ向上のためプライベートIPを使用する
フェールオーバーの問題を解決し、Web層の可用性を向上させる
Webサイトのトラフィックが急増し、2台のサーバでは処理しきれない場合、ロードバランサはこの問題を円滑に処理できる。Webサーバプールにさらにサーバを追加するだけで、ロードバランサは自動的にそれらのサーバにリクエストを送信し始める

データベースレプリケーション

オリジナル(マスター)/コピー(スレーブ)
マスターデータベースは一般に、書き込み操作のみをサポート
スレーブデータベースは、マスターデータベースからデータのコピーを取得し、読み込み操作のみをサポートする

データベースレプリケーションの利点

パフォーマンスの向上
- マスタ/スレーブ構成では、書き込みと更新は全てマスターノードで行われ、読み込み操作はスレーブノードで分散して行われる
- より多くのクエリを並行処理できるため、パフォーマンスが向上する
信頼性
- 災害によってデータベースサーバが破壊されても分散して複製されているため損失を心配する必要はない
高い可用性
- データを複数の場所に複製することで、データベースがオフラインになっても、別のデータベースサーバに保存されているデータにアクセスできるため、Webサイトの運用を継続できる
スレーブデータベースが1つしかなく、それがオフラインになった場合、読み取り操作は一時的にマスタデータベースに誘導される。
- 問題が見つかり次第、新しいスレーブデータベースが古いデータベースを置き換える。
- 複数のスレーブデータベースが利用可能な場合、読み取り操作は他の健全なスレーブデータベースへリダイレクトされる。
マスタデータベースがオフラインになった場合、スレーブデータベースが新しいマスターになるように設定される
- 全てのデータベース操作は、一時的に新しいマスターデータベース上で実行される。
- 本番システムでは、スレーブデータベースのデータが最新でない可能性があるため、新しいマスタを昇格サッせるのはより複雑である
  - データ普及スクリプト実行し、不足数rデータを更新する必要がある
  - マルチマスターや循環レプリケーションといった他のレプリケーション方法もある

キャッシュ

注意点

キャッシュを使用するタイミングの決定
- データの読み取り頻度が高く、変更頻度が低い場合にはキャッシュの使用を検討する。
- キャッシュされたデータは揮発性メモリに保存されるため、キャッシュサーバはデータの永続化には不向きである。
有効期限ポリシー
- キャッシュの消費期限
- 有効期限ポリシーがないと、キャッシュされたデータは永久にメモリに保存される
一貫性
- データストアとキャッシュのデータ変更操作が単一のトランザクションでないため、不整合が発生することがある
- 複数の地域にまたがって拡張する場合、データストアとキャッシュの間の一貫性を維持するのは困難である
障害の軽減
- 単一のキャッシュサーバは、潜在的な単一障害点(SPOF)
- 異なるデータセンターで複数のキャッシュサーバを使用することが推奨される
- 必要なメモリを一定の割合で過剰にプロビジョニングすることでメモリ使用量の増加に伴うバッファを提供する
消去ポリシー
- キャッシュがいっぱいになり、キャッシュにアイテムを追加するリクエストがあると、既存アイテムが削除される可能性がある。
  - キャッシュのエビクション
  - LRU (Latest Recently Used)
    - もっとも一般的なキャッシュ削除ポリシー
  - LFU (Latest Frequently Used)
  - FIFO (First In First Out)

コンテンツデリバリーネットワーク(CDN)

CDNは、地理的に分散したサーバのネットワークであり、静的コンテンツを配信するために使用される
CDNサーバは、画像・動画・CSS・Javascriptファイルなどの静的コンテンツをキャッシュする

注意点

コスト
- CDNはサードパーティのプロバイダーによって運営されており、CDNへのデータ転送とCDNからのデータ転送に課金される
- 使用頻度の低いコンテンツは、キャッシュしても大きなメリットがないので、CDNからの移動を検討する必要がある
キャッシュの有効期限の適切な設定
- 時間的制約のあるコンテンツでは、キャッシュの有効期限設定が重要である
CDNフォールバック
- CDNが故障した場合に、Webサイトやアプリケーションがどのように対処するかを検討する必要がある
- ファイルの無効化
- 以下の操作によって有効期限が切れる前にCDNからファイルを削除できる
  - CDNベンダーが提供するAPIを使用してCDNオブジェクトを無効化する
  - オブジェクトのバージョニングを使用して、オブジェクトの異なるバーションを提供する

ステートレスWeb層

DBにステートを持つことでWebサーバをスケールアウトしやすくする

データセンタ

ジオDNS
- ユーザの位置に基づいてドメイン名をIPアドレスに割り当てるDNSサービス
マルチデータセンター化を達成するための技術的課題点
- トラフィックのリダイレクト
  - トラフィックを適切なデータセンターに誘導するための効果的なツールが必要
  - ジオDNSを使用すると、ユーザの所在地に応じて最も近いデータセンターにトラフィックを誘導できる
- データ同期
  - 一般的な戦略は、複数のデータセンター間でデータを複製すること
- テスト・デプロイ
  - マルチデータセンターのセットアップでは、Webサイトやアプリケーションを異なるロケーションでテストすることが重要になる。
  - 全てのデータセンターにおけるサービスの一貫性を維には、自動デプロイメントツールが不可欠となる

ログ取得、定量化、自動化

必須ではないが、サービスの規模が大きくなると投資が不可欠になる

データベースのスケーリング

垂直スケーリング

スケールアップ
- 既存マシンにさらにパワー(CPU, RAM, DISKなど)を追加することでスケーリングする
- 2013年のstackoverflow.comは毎月1000万人以上のユニークビジターを抱えていたが、一つのマスターDBしかもっていなかった
  - 以外と行ける
欠点
- データベースサーバにCPUやRAMなどを追加できるが、ハードウェアには限界がある。ユーザ数が多い場合、1台のサーバでは不十分である
- 単一障害点のリスクが大きい
- 垂直スケーリングは、全体コストが高い。強力なサーバはより高価になる

水平スケーリング

シャーディング
- 大規模なデータベースをより小さく、より管理しやすいシャードというパーツに分割する
- 各シャードは同じスキーマを共有するが、各シャード上の実際のデータはそのシャード固有
シャーディング戦略を実装する際に考慮すべき最も重要な要素は、シャーディングキーを選択すること
- シャーディングキー(パーティションキー)
  - データの分散方法を決定する1つないし複数の列で構成される
  - データベースへのクエリを正しいデータベースにルーティングすることで、データの取得と修正を効率的に行えるようにする
  - シャーディングキーを選択する際、最も重要な基準の一つは、データを均等に分散できるキーを選択すること
シャーディングはデータベースを拡張するための優れた技術ですが、完璧なソリューションには程遠いもの。

シャーディングによるあらたなシステムに複雑さと課題

データの再シャーディング
- 必要になる場面
  - 急激なデータ増加により、1つのシャードがそれ以上のデータを保持できなくなった場合
  - データの分布が不均一なため、特定のシャードが他シャードよりも早くシャードを使い果たす可能性がある場合
シャード枯渇の際には、シャーディング機能の更新とデータの移動が必要になる
- この問題を解決する手法として一貫性ハッシュがよく使われる
セレブ問題
- ホットスポットキー問題とも呼ばれる
- 特定のシャードへの過度なアクセスは、サーバの過負荷を引き起こすかもしれない
- ケイティ・ベリー、ジャスティン・ビーバ、レディー・ガガのデータが全て同じシャードに入ってしまうことを考える
  - 特定のシャードの負荷が異常に高くなってしまう
- 結合と非正規化
  - データベースが複数のサーバにまたがってシャーディングされると、データベースのシャード間でジョイン操作を行うことが難しくなる。一般的な回避策は、データベースの非正規化を行い、単一のテーブルでクエリを実行できるようにする

スケーリングテクニックまとめ

Web層はステートレスに保つ
各階層で冗長性を確保する
できる限りデータをキャッシュする
複数のデータセンターへの対応
静的アセットをCDNでホスティング
シャーディングによるデータ層の拡張
各サービスに階層を分割する
システムの監視と自動化ツールの使用

おおまかな見積もり

Googleのシニアフェローであるジェフ・ディーンによれば、「おおまかな見積もりとは、思考実験と一般的な性能数値を組み合わせて、どの設計が要件を満たすかについてよい感触を得るためのに行う見積もり」
大まかな見積もりを効果的に行うには、スケーラビリティの基本的な感覚を身につける必要がある

プログラマが知っておくべきレイテンシの数値

Googleのディーン博士が2010年における典型的なコンピュータ操作の時間を明らかにしている。絶対的な数値としては古いが、相対的な値としては参考になる

システム設計の面接試験

システム設計の面接試験
メモリは早いが、ディスクは遅い
- 可能ならディスクのシークは避ける
  - シーク（seek）とは、物理的な駆動部分のあるコンピュータの記憶装置（FDD、MOやHDD、CD・DVDなどの光ディスク）において、ヘッドまたはピックアップレンズが、書き込み・読み取りの目標位置(トラック)まで移動すること。これによりランダムアクセスが可能となる
単純な圧縮アルゴリズムは速い
可能であれば、インターネット送信前にデータを圧縮する
データセンターは通常、異なる地域にあり、データセンターにデータを送るのに時間がかかる

可用性の数値

システム設計の面接試験

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

システム設計の面接試験のフレームワーク

システム設計の面接試験は、2人の同僚が共同で曖昧な問題に対して目標を満たすソリューションを考え出すという、現実世界における問題解決の疑似体験
設計のプロセスによって、自らの設計スキルを証明し、自らの設計上の選択を擁護し、フィードバックに対して建設的に対応する
面接官の第一の目標は、対象者の能力を正確に評価すること
- 一番避けたいのは、面接がうまくいかず、十分なメッセージが得られずに、結論の出ない評価を下すこと
問われるのが技術的な設計能力が全てではない
- 協調性、プレッシャー下での仕事ぶり、曖昧さを建設的に解決する能力、よい質問をする能力
トレードオフを無視した視野の狭さ、頑固さといった危険信号も評価対象

優れたシステム設計の面接試験の4ステップ

ステップ1: 問題を理解し、設計範囲を明確にする

何も考えずし早く答えを出してもボーナスポイントはもらえない
ゆっくりと考える。深く考え、質問をして、要件や前提条件を明確にする
エンジニアにとって最も重要なスキルの1つは、正しく質問し、適切な仮定を立て、システムを構築するために必要な全ての情報を収集すること
質問の具体例
- 具体的にどのような機能を開発するのか
- 製品のユーザ数はどのくらいか
- どの程度のスピードでスケールアップすることを想定しているか？
  - 3ヶ月後、6ヶ月後、1年後のスケーツアップはどの程度を想定しているか
- その会社の技術的な問題は何か
  - 設計をシンプルにするために活用できそうな既存サービスは何か

ステップ2: 高度な設計を提案し、賛同を得る

面接官とコミュニケーションをとる
設計の初期設計図を作成し、フィードバックを求める。面接官をチームメイトとして扱い、一緒に仕事をする。
blueprintがスケールの制約に合っているか、大雑把な計算で評価する。
可能であれば具体的なユースケースを確認する
設計に、APIエンドポイントやデータベーススキーマも含めるべきか
-「Googleの検索エンジンの設計」のような大きな設計であれば、少しレベルが低すぎる
- 多人数参加ボーカーゲームのバックエンド設計のような問題であれば適切

ステップ3: 設計の深掘り

前提:以下の目的を達成している
- 全体的なゴールと機能の範囲について合意した
- 全体設計のために高度な青写真を描いた
- 高度な設計に対して面接官からのフィードバックを得た
  -フォードバックに基づいた深掘りによって、フォーカスすべきエリアについて最初のアイデアを得た
面接官と協力して、アーキテクチャの構成要素を特定し、優先順位をつける
優先順位の高いドメインに対して設計を掘り下げる

システム設計の面接試験

ステップ4: まとめ

面接官がいくつかのフォローアップの質問をしたり、その他の点について自由に話したりできる
- システムのボトルネックを特定し、改善の可能性について議論する
- 面接官に設計を振り返ってもらう
- エラー事例(サーバ障害、ネットワーク損失など)を話す
- 運用上の問題について言及する
  - 数値やエラーログをどのように監視しているか。システムをどのようにロールアウトするか
- 次のスケールカーブにどのように対応するか
やるべきこと
- 常に説明を求めること
- 問題の要件を理解する
- 正解もベストアンサーもない
- 考えていることを面接官に伝える
- 複数のアプローチを提案する
- 青写真について双方合意したら、各構成要素の詳細を確認する
  - 最も重要な構成要素を最初に設計する
- 面接官にアイディアをぶつける。よい面接官は、チームメイトとして一緒に仕事する
- 決してあきらめない
やるべきでないこと
- 面接での典型的な質問に対する準備を怠る
- 要件や前提条件を明確にしないまま、解決策に飛びつく
- 最初に1つのコンポーネントについて詳しく説明する
- ヒントをまったくもらわない
- コミュニケーションをとらないこと
- 設計を伝えたら面接が終了と思うこと
  - 面接官が「おわった」というまで、早く、頻繁にフィードバックを求める

レートリミッターの設計

HTTPの世界では、レートリミッターが指定期間に送信できるクライアントリクエストの数を制限する
- レートリミットのサンプル
  - ユーザは1秒間に2件までしか書き込みができない
  - 同じIPアドレスから1日に作成できるアカウントは最大10個まで
  - 同じデバイスから報酬を請求できるのは、1週間に5回まで
APIレートリミッター使用のメリット
- サービス拒否(DoS)攻撃によるリソースの枯渇を防ぐ
- コストを削減する
  - 過剰なリクエストを制限することは、サーバの数を減らし、より多くのリソースを優先度の高いAPIに割り当てることを意味する
- サーバの過負荷を防ぐ

問題点を理解し、設計範囲を明確にする

クライアントサイドのレートリミット? or サーバサイドのAPIレートリミッター?
レートリミッターは、IPやユーザID、あるいは他のプロパティに基づいてAPIリクエストを制限(スロットリング)する?
システムの規模は?スタートアップ企業向け or 大規模なユーザ基盤をもつ大企業向け?
システムは分散環境で動作する?
レートリミッターは別のサービス?
制限されたユーザに通知する必要がある?

必要条件

過剰なリクエストを明確に制限すること
低遅延であること。HTTPのレスポンスタイムをおそくしない
できるだけ少ないメモリで動作すること
分散型レートリミッターであること
- 複数のサーバやプロセスでレートリミッターを共有可能
例外処理
- リクエストが制限されたとき、ユーザに明確な例外を表示する
高い障害耐性
- レートリミッターに何らかの問題が発生した場合もシステム全体には影響しない

高度な設計を提案し、賛同を得る

レートリミッターはどこに置くか

クライアント側での実装
- 一般に、クライアントのリクエストは悪意のある行為者によって簡単に捏造される可能性があるため、クライアントはレート制限を実施するには信頼性の低い場所
- クライアントの実装を制限できない可能性もある
サーバ側での実装
- APIサーバとは別serviceとして設置
- ミドルウェア(API gateway)のようにレートリミットを作成方法もある
  
  システム設計の面接試験
レート制限は通常、API gatewayと呼ばれるコンポーネント内に実装される
- API gateway
  - レート制限、SSL終了、認証、IPホワイトリスト、静的コンテンツのサービスなどをサポートするフルマネージドサービス
レート制限を設計する際に重要なのはレート制限はどこに実装するべきか、サーバ側あるいはGateway内か
- 絶対的な答えはない。現在の技術スタック、エンジニアリング・リソース、優先順位、目標などに依存する
- 一般的なガイドライン
  - プログラミング言語、キャッシュサービスなど、現在の技術スタックを評価する。
    - 現在使用している言語が、サーバ側でレート制限を実装するのに有効であることを確認する
  - ビジネスニーズに合ったレート制限アルゴリズムを特定する。
    - サーバ側に全てを実装する場合、アルゴリズムは完全に制御できる。
    - サードパーティのGatewayを使用する場合は、選択肢が制限される可能性がある
    - すでにマイクロサービス・アーキテクティングを採用し、認証やIPアドレスリスト作成などのためにAPI Gatewayを設計に組み込んでいる場合、API Gatewayにレート制限を追加できる
  - レートリミッターサービスを独自に構築するのは時間がかかる

レートリミッターのアルゴリズム

トークンバケット(Token bucket)

シンプルでわかりやすく、よく使われる
ロジック
- トークンバケットとは、あらかじめ決められた容量を持つコンテナ
  - あらかじめ決められた容量をもつ容器で、定期的にトークンが入れられる
  - バケットが満杯になると、それ以上トークンは追加されない
- 各リクエストは1つのトークンを消費する
  - リクエストが届くと、バケットに十分なトークンがあるかを確認する
    - 十分なトークンがある場合、各リクエストに対して1つのトークンを取り出し、リクエストは通過する
    - 十分なトークンがない場合、リクエストは破棄される

システム設計の面接試験

トークンバケットアルゴリズムは2つのパラメータをとる
- バケットサイズ
  - バケットに入れられるトークンの最大数
- 補充率
  - 1秒間にバケットに入れられるトークンの数
必要なバケット数
- 通常APIエンドポイントごとに異なるバケットを用意する必要がある
- IPアドレスに基づいてリクエストを制限する必要がある場合、IPアドレスごとにbucketが必要

長所

アルゴリズムの実装が簡単
メモリ効率がよい
トークンバケットは短時間のバーストトラフィックを可能にする

短所

バケットサイズとトークン補充率という2つのパラメータがあるが、これらを適切に調節するのは難しいかもしれない

リーキーバケットアルゴリズム

リクエストの処理速度が一定であることを除けばトークンバケットと似ている
通常先入先出し(FIFO)のキューで実装される
ロジック
- リクエストが到着すると、システムはキューが満杯かをチェックする
  - もし満杯でなければ、リクエストはキューに追加される
  - もし満杯であれば、リクエストは削除される
- リクエストはキューから引き出され、一定時間ごとに処理される

システム設計の面接試験

リーキーバケットアルゴリズムは、以下の2つのパラメータを取る
- バケットサイズ
  - キューサイズに等しい
- 流出率
  - 一定の割合で処理できるリクエストを定義するもの
EC企業のShopifyは、リーキーバケットアルゴリズムをレート制限に使用している

長所

キューサイズに制限があるため、メモリ効率がよい
リクエストは固定レートで処理されるため、安定した流出レートが必要なユースケースに適している

短所

トラフィックのバーストは古いリクエストでキューを満たし、それらが時間内に処理されない場合、新しいリクエストはレート制限される
アルゴリズムには2つのパラメータがあり、それらの適切なチューニングが困難になる可能性がある

固定ウィンドウカウンタアルゴリズム

このアルゴリズムは、タイムラインを固定サイズのタイムウィンドウに分割し、各ウィンドウにカウンタを割り当てる
各リクエストはカウンターを1つずつ増加させる
カウンタが事前に定義された閾値に達すると、新しいタイムウィンドウが始まるまで新しいリクエストは新しいタイムウィンドウが始まるまで落とされる

作成者以外のコメントは許可されていません