【読書メモ】System Design Interview – An insider's guide Chapter 1: Scale From Zero To Millions Of Users

# この記事は何？

Alex Xu 氏の **System Design Interview – An insider's guide**　の **Chapter 1: Scale From Zero To Millions Of Users** を読んで内容をメモしたものです。

1から数百万ユーザーにスケールするシステムの構築を考えます。

https://www.amazon.co.jp/System-Design-Interview-insiders-Second/dp/B08CMF2CQF

## 最初のステップ

まずは一つのサーバー上で全てが動いているWEBシステムを考える。１つのWEBサーバーだけ。
トラフィックは以下の流れ。

1. クライアントがDNSにURLを問い合わせ
2. DNSがIPを返却
3. クライアントが返却されたIPへ問い合わせ
4. サーバーがリクエストにHTML応じてを返す

サーバーへのリクエスト送信元は以下の２つが考えられる。
1. WEBアプリケーション
2. モバイルアプリケーション

## DBの切り離し

ユーザーが増えると１つのサーバでは不十分になる。次は web tire(ウェブ層) と data tire(データ層) の切り離しを考える。

### どのDBを使うべきか？

RDB、NOSQLがある。
RDB: SQLのjoinができる
NoSQL: 以下４種に大別される。joinは基本サポートされない

1. key-value
2. graph
3. column
4. document

基本的にはRDBが良い選択だが、向かないケースも有る。以下のような場合はNoSQLが向くかもしれない。

- 超低レイテンシーが求められる
- 非構造化データをあつかう
- シリアライズ/デシリアライズデータのみ扱えれば良い(JSON, XML, YAML etc.)
- 大量のデータ

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

垂直スケーリング：スケールアップとも。CPUやRAMの増強をさす。
水平スケーリング：スケールアウトとも。サーバー台数を増やす。

大きなアプリケーションの場合は水平スケーリングが望ましい。

## ロードバランサーの導入

ロードバランサーでトラフィックを複数のサーバーに分散することでアクセス増加に対応する。

DNSには、ドメイン名に対して登録するIPをロードバランサーのIPにする。

クライアントからアクセスされると、トラフィックはロードバランサーに転送される。

その後、トラフィックは背後のWEBサーバーに均等に分散される。

WEBサーバーは通常クライアントから直接アクセスはできなくなる。
ロードバランサーとWEBサーバーはPrivateIPで通信する。

## DBのレプリケーション

WEB層に関しては冗長性が追加されたがDBは１つしか無い。DBのレプリケーションを行う。

レプリケーションはDBシステムにおいて、オリジナルDBとコピーされたDBがmaster/slave の関係で表される。

```mermaid
flowchart TD
    A[Web servers] -->|write| B(master DB)
	  B <-->|replication| C(Slave DB1)
	  B <-->|replication| D(Slave DB2)
    B <-->|replication| E(Slave DB3)
		A -->|read| C
		A -->|read| D
		A -->|read| E
```

以下のようなメリットがある。

- リードクエリを処理を並列に処理でき、パフォーマンスが上がる
- 信頼性の向上。データ損失の可能性が減る
- 高可用性：サーバの設置箇所を分散することで達成可能

DBがダウンした場合はどうなるか。

- slaveのみダウンしたときは、読み込みが一時的にmasterに向かう。他に行きているslaveがあればそちらに向かう
- masterがダウンした場合はslaveが新たなマスターに昇格する。落ちたmasterのデータが反映されていない可能性があるので、本番環境ではバックアップスクリプトを流して反映する。マルチマスター形式などより複雑な形式もある。

## レスポンスタイムの向上

次はレスポンスの速度を上げるための手段を考える

### キャッシュ

よくアクセスするデータを一時的に保存し、高速にアクセスするための仕組み。

WEB層とDB層の間にキャッシュ層を置くことで、レスポンスを高速化する

キャッシュにデータが有ればキャッシュを返し、なければDBから取得する。

キャッシュの考慮事項

- いつ使うかを決める。読み込みが多いが、書き込みが少ないときに有効。
- 重要なデータは永続DBに保存する
- 保存期限を決める。期限が切れたらキャッシュを削除する。短すぎるとDBからの読み込みが増えるが、長すぎるとデータが古くなってしまう
- 一貫性。データストアとキャシュの状態を一致させる必要があるか。スケールすると一貫性を保つのが難しくなる。
- １つのキャッシュサーバーは単一障害点になりうる。複数のキャッシュサーバーを用意するのが望ましい。他にはオーバープロビジョン戦略がある。
- キャッシュサイズの上限を考えて，キャッシュ内に必要なデータを保存し，不要なデータを追い出すことをCache Eviction という. LRUや LFU, FIFO のアルゴリズムがある。どれを使うかを検討する。

### CDN

地理的に分散したサーバーで、画像や動画、javascript, CSSなどの静的ファイルの配信に使用される。

動的コンテンツキャッシングの仕組みはこの本では扱わない。これはHTMLページをリクエストパス、クエリストリング、クッキーやリクエストヘッダに基づいてキャッシュできる仕組みを指す。

ここでは静的コンテンツのキャッシングにフォーカスして扱う。
CDNはユーザーの所在地に近いサーバーからコンテンツを取得して配信する。
```mermaid
flowchart LR
    A[UserA] -->|get image.png| C(CDN)
	  C -->|if not in CDN, get image.png| D(WEBServer)
	  D -->|store image.png in CDN| C
    C -->|return image.png| A
		B[UserB] --> |get image.png| C
	  C -->|return image.png| B
```

問い合わせの流れ

1. Userが画像のURLにリクエスト。これはCDNのURLとなる。例としては https://myste.cloudfront.net/logo.png　など
2. CDNに画像がキャッシュされていれば返却。なければコンテンツを格納しているオリジンサーバーのURLにCDNが問い合わせる。オリジンサーバーはS3などのストレージや、WEBサーバーとなる。
3. オリジンは 画像をCDNに返却する。ヘッダにTTL（Time-to-Live)が設定されており、これがキャッシュをどのくらいの時間残しておくかを決定する。
4. CDNが画像をキャッシュし、ユーザーに画像を返却する。
5. 別ユーザーが同じ画像を問い合わせたとき、キャッシュされている画像を返却する。（TTLがまだ有効な場合）

### CDNを使うときの考慮事項

- コスト面：CDNはサードパーティーが運営している。CDNの利用にお金がかかるので考慮する。使用頻度の低いコンテンツをキャッシュするのはメリットがない。
- キャッシュ期限を適切にする。
- CDNがダウンしたときの動作：CDNがダウンしたときは、クライアントが問題を検知し、オリジンサーバーに問い合わせる必要がある
- ファイルの無効化方法：CDNの期限が切れる前に削除することもできる。
    - CDNに用意されているAPIを使って削除
    - オブジェクトのバージョニングを使う。URLにパラメータでバージョンを指定することで、別のものを取得する

### ステートレスなWEB層

WEB層の水平スケーリングを考える。セッションデータをWEB層から切り出す必要がある。例えば NoSQLストレージに入れておくなど。各クラスターのサーバーはセッションデータをDBから取得する。

これをステートレスなWEB層という.

スティッキーセッションを使って、おなじクライアントからのリクエストをつねに同じサーバーにルーティングすればWEBでセッションを保持していても大丈夫だが、サーバーの追加削除が難しくなる。サーバーが落ちたときの対策も難しい。

ステートレスアーキテクチャの図は以下のようになる

```mermaid
flowchart TD
    A[User1] -->|http request| B(WEB servers)
	  C[User2] -->|http request| B
	  D[User3] -->|http request| B
		B --> |fetch state|E(Shared Storage)

```

全体像は以下

![download (1).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/164843/d66d199c-289a-3fc2-ae0b-30614fe05a66.png)


キャッシュと セッション用 NoSQL DB が増えた.

NoSQLにする理由としてスケールしやすいという点がある。スケールとはトラフィックに応じてWEBサーバーを自動で追加したり削除したりする操作を指す。AWSのオートスケーリングなど。

より広範囲の地域のユーザーに快適に使用してもらうためには複数のデータセンターが重要になる。

## データセンター

地域ごとにロードバランサーでルーティングを割り振る設定を行うことで、大規模なデータセンターの障害に対応する。

![download (2).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/164843/d5f5fdcc-ffaf-9917-7421-c7fd958bebf8.png)

技術的な課題

- トラフィックのリダイレクト。GeoDNSがユーザーのもっとも近い地域のデータセンターにルーティングする。
- データの同期：異なる地域では異なるDBやキャッシュとなる。フェイルオーバーの際にどうやって同期を取るか。一般的にはレプリケーションを行う。
- テストとデプロイ：アプリのテストを異なる地域で行うこと、サービスを継続的にすべてのデータセンターで行うために自動デプロイが重要。

更にシステムをスケールするには、異なるコンポーネントを分離して独立にスケールできるようにする必要がある。メッセージキューが重要。

## メッセージキュー

非同期のコミュニケーションを可能にする。

入力側＝プロデューサー、パブリッシャー
受け取り側＝コンシューマー、サブスクライバー
などの呼び名がある。

コンシューマーはプロデューサーが落ちていてもメッセージを受信できる。

例えば写真編集アプリを考える。クロップ、ぼかしなどの操作を写真に加えられるとする。これらの操作タスクは完了までに時間がかかる。

まずプロデューサーが写真への処理タスクをキューに格納する。その操作を処理するワーカーが処理ジョブをキューから取り出し、写真へ編集を加える。プロデューサーとコンシューマー独立にスケールできるようになる。

```mermaid
flowchart LR
    A[Producer] -->|publish| B(queue)
		B -->|consume|C[Consumer]
```

**アプリケーションを疎結合にすることが重要になってくる。**

## ロギング、メトリクス、自動化

サイトがかなり大きくなったので、調査のためのログ収集がより重要になってくる。

ロギング：エラーの原因を特定するのに役立つ。エラーログを監視し、収集サービスに集めて検索星をあげることができる

メトリクス：異なる指標を集めることでシステムのヘルスチェックを詳細に行えるようにする。いかが収集する指標の例。

- CPU, メモリ, diskIOなど、ホストマシンの指標
- 集約された指標。例えばDB層全体、キャッシュ層全体のもの。
- KPIとなる指標。日時ユーザー数、収益など。

自動化：システムが大きくなるほど、自動ビルドツールなどが有効になってくる。

## DBのスケーリング

２つのアプローチがある。

### 垂直スケーリング

マシンのCPU,RAM,DISKなどのスペックを上げること。以下の課題がある。

- ハードウェア制限。
- 単一障害点のリスク
- コストが増加する

### 水平スケーリング

sharding （一つのテーブルを複数の物理PCに分割して記録する方式）を使用する。同じテーブルスキーマだが、中身のデータが個々のマシンでことなる。

例えばユーザーIDの値により４つのマシンに分散してユーザーデータを記録する。

```mermaid
flowchart TB
    A[User_id % 4 ] -->B(DB1)
    A[User_id % 4 ] -->C(DB2)
    A[User_id % 4 ] -->D(DB3)
    A[User_id % 4 ] -->E(DB4)

```

**シャードでもっとも重要なことは、シャーディングに使用するキーである。上記で言うところのユーザーID.　パーティションキーとも呼ばれる。**

キーの値によってDBへの分散性が決まるため。カーディナリティの高いものにする。

シャーディングは完璧でなく、以下の課題がある。

- データの Resharding: シャードの枯渇が起こると、シャーディング関数をアップデートする必要がある。Consistent Hashing がよく用いられる。Consistent Hashing はハッシュテーブルのサイズの変更をしても柔軟にマッピングできるため、ノードの追加・削除が発生する分散データベースやキャッシュの保存先を決定するといった用途に使われます。
- Celebrity problem: hotspot key problem とも。ヘビーユーザーなど特定のパーティションキーに偏りがある場合、読み込みに障害が出たりする。そのデータ用にシャードを用意するなど対策が必要。
- Join操作：shardingすると難しくなる。DBを非正規化し、一つのクエリで検索できるようにして対応するのが一般的。

# まとめ
ユーザー数が少数から数百億に対応するためにどのようなステップでスケーリングさせるのかがとても参考になりました。
洋書ですがわかりやすい英語なので、英語に抵抗のない方にはおすすめです。