システム設計の面接試験を読んだ

システム設計の面接試験を読んだ
https://www.socym.co.jp/book/1406

動機

自分が興味のある分野はソフトウェアアーキテクチャ的な部分だが、今まで読んできたのはコードをどう書くかというのがメインで、システム全体のアーキテクチャについては学んだことがなかったため。
また、いざ転職をするとなったときに焦らなくて良いように下地を作っておきたかった。

感想

最初にトライしたときは知らないアルゴリズムや概念が多く、漫然と読んでいるだけだと分からない部分が多くなって挫折してしまったので、毎日1時間つかって1章ずつ読む、自分で言い換えのメモを取り参考文献もパラ見してみる、
という形で何とか読み通すことができたといった感じ。

Webサービスのスケールアップ、レートリミッタの設計といったやや抽象的で基礎的なところからはじめて、YoutubeやGoogleDriveなど実際のサービスの簡易的な設計までをステップバイステップで解説してくれている。
また、面接試験対策ということで試験官とのやりとりを想定していて、要件を洗い出し方、おおまかな見積もりを出す方法についても解説してくれているのがありがたい。
アルゴリズムやリクエストの流れについては必ず図が掲載されているのもいい。試験の際には言葉だけでなく図も交えて認識をすり合わせていけということなのだろう。
参考文献がほぼ海外サービスのテックブログなのも気軽に読めて良かった。

頻出の項目

サービスが違っていても各章で繰り返し出てくる概念があり、重要そうなのでメモを残しておく。
また、記載はあるものの、書籍内では詳しく解説されていないものがあったので調べた結果を載せておく。

おおまかな見積もりに必要なこと

1. DAUとユーザーが一日に起こすアクション数を仮定する
2. 1アクションにかかるリクエスト数、データ量を仮定する
3. 1, 2からQPS、必要なストレージ量を算出する

コンシステントハッシュ

キャッシュサーバーを複数用意して負荷分散を行うとき、初歩的な方法ではサーバー台数がN台のとき、hash(key) % Nのサーバーにデータを振り分ける。
しかしこの方法ではサーバーの台数を増やしたときにキャッシュミスだらけになってしまう。
そこで、サーバーの増減による再マッピングを軽減するため、ハッシュ関数の出力値の範囲をリング状にしたものの上にデータとサーバーをマッピングし、あるデータを保存するサーバーを時計回りに探索して最初に見つかったサーバーとする。

しかしこの方法にも2点問題がある。

1. サーバーの追加や削除によってデータに偏りが生まれる
2. リング状のキーの分布自体に偏りが発生する可能性がある

上記を解決するために、実際のサーバーをマッピングする代わりに、1:Nとなる仮想ノードを配置することによってキーの分布を均一に近づける方法がある

メッセージキューで疎結合にする

直列な処理の間にメッセージキューを挟むことで、システムが粗結合になる。
プロデューサーとコンシューマーの数を独立して調整可能にすることで、負荷に対して柔軟でコスパのよいシステムを構築できる。

一貫性

DBを複数用意し、書き込み、読み込みを分散させるときにはデータの一貫性が重要になる。

• データの複製について

  • N個のサーバーにデータを非同期で複製し、書き込み時にW個の複製を待ち、読み込み時にはR個の複製を待つとするとき
    • R=1, W=Nのとき高速読み出しに最適化されている
    • W=1, R=Nのとき酵素書き込みに最適化されている
    • W+R > N のとき強い一貫性が保証される
    • W + R <= N のとき強い一貫性は保証されない

• 一貫性モデル

  • 強い一貫性: どのような読み取りでも最も更新されたデータが返される
  • 弱い一貫性: 最も更新されたデータが見えないことがある
  • 最終的な一貫性: 十分な時間があればすべての更新が伝播され、すべての複製データが一貫性を持つ

ブルームフィルタ

URL短縮サービスで、ハッシュ関数+衝突判定を使うときに出てきた。
あるデータが集合に含まれているかどうかの判定に使われる、効率の良い確率的データ構造のこと。

まず、mビットのビット配列を用意し、k個のハッシュ関数を用意する。
ある要素を集合へ追加するときは、k個のハッシュ関数を適用し、k個のインデックスの配列を得て、ビット配列のインデックスの値を0から1に変える。
ある要素が含まれるかを調べるには、k個のハッシュ関数を適用し、k個のインデックスの配列を得て、ビット配列の同位置を調べる。もし1つでも0の場所があればその要素は集合に含まれていないことになる。

データすべてを格納する必要がないため省メモリだが、要素が増えるにつれて偽陽性が増加する

マークルツリー

2つの集合の差分検出のために使われるツリー状のデータ構造

リーフノードの値を使ってハッシュ化した親ノードを作成し、それを最終的に1個になるまで上につなげていく
非リーフノード自体の値を比べることでどこに差分が出ているかがわかるようになる

ゼロ知識でふんわり理解するマークルツリー

ハートビート監視

監視、障害の検出のための機能

• 監視対象の危機にあらかじめ決まった周期で短いデータを送るよう設定しておき、監視側で途切れがないかを確認することで障害を検知する

• 複数台のサーバーがあって、障害を検出するのにマルチキャストでは効率が悪いとき

  • 各ノードはサーバIDとハートビートカウンタを持つテーブルを持っており、ランダムなノードと共有している
  • ハートビートカウンタが増加していないサーバーがあれば、ランダムなノード群にテーブルを送り、他のノードもカウンタが増加していないことを確認できればそのノードがダウンしていると判断する

ポーリング

サーバーから通知を受け取る方法として、ポーリング, ロングポーリング、WebSocketがある。

• ロングポーリングと普通のポーリングの違い

通常のポーリングは何も通知がないとき、サーバは何もなかったことをレスポンスとして返すが、ロングポーリングではサーバ側が新しい通知があるまではレスポンスを保留する

ユニークIDの生成方法

• マルチマスターレプリケーション: DBをk台用意してauto_incrementでkずつ増加させる
  • スケーリングができない
• UUID: 衝突しにくいID生成機構を各サーバが持つ
• チケットサーバ: ユニークIDを発行するための単一のサーバを用意する
  • 単一障害点になってしまう
• snowflakeアプローチ: 任意長のbitを分割して各長さに値を振り分ける
  • Twitterの場合64bitと設定し、下記のように分割している
    • 1: 符号ビット
    • 41: タイムスタンプ
    • 5: データセンタID
    • 5: マシンID
    • 12: シーケンス番号
  • スケーリング可能で、かつIDを時系列で並び替えることができる

ハッシュとチェックサムの違い

チェックサムはハッシュと比べて信頼性は低いものの計算が簡単なので、エラー検出目的に使われる。

Fanout

フィードやタイムラインを構築するとき、普通にRDBから読み出しとかやってると遅いので、あらかじめポスト時点でユーザごとにPostIDを割り振っておいて読み出しを高速化する

アップロードデータ分割

大きなファイルをアップロードするときは、データの分割とアップロード再開を可能にしておく。
1つのファイルを複数ブロックに分割し保存することで、データを変更してアップロードしたときに差分のみを保存すればよくなる