[システムデザイン面接] 第5章: 一貫性ハッシュ
大規模なシステムを設計するために必要な基本的なコンポーネントは何でしょうか?
この記事では、ルーティングシステムで一般的に使用される一貫性ハッシュを直接実装し、データに基づいて議論します。
完全なコードはGithubで確認できます。
この記事はかなり長いので、説明の便宜上、 以降は「~」を使用します。🙏
ハッシュとは?
一貫性ハッシュに入る前に、まずハッシュについて簡単に触れておきましょう。
辞書的な定義によると、ハッシュとは「任意の長さのデータ文字列を入力として受け取り、固定サイズの出力(通常はハッシュ値またはハッシュコード)を生成する数学的関数」です。
簡単に言えば、同じ入力文字列は常に同じハッシュコードを返すということです。このハッシュの特性は、暗号化やファイルの整合性検証など、さまざまな目的で使用されます。
では、一貫性ハッシュとは?
一貫性ハッシュは、分散サーバーやサービス間でデータを均等に分散させるための技術です。
一貫性ハッシュを使用しなくても、データを均等に分散させることは不可能ではありません。しかし、一貫性ハッシュは水平スケーリングを容易にすることに焦点を当てています。一貫性ハッシュを探る前に、簡単なハッシュルーティング方法を通じて一貫性ハッシュがなぜ登場したのかを理解しましょう。
ノードベースのハッシュルーティング方法
hash(key) % n
この方法はシンプルでありながら効率的にトラフィックを分散させます。
しかし、水平スケーリングには大きな弱点があります。ノードリストが変更されると、トラフィックが再分配される可能性が高く、新しいノードにルーティングされることになります。
特定のノードでキャッシュを管理している場合、ノードがグループから離れると大規模なキャッシュミスが発生し、サービスの中断を引き起こす可能性があります。
4つのノードで実験したところ、1つのノードが離れるだけでキャッシュヒット率が27%に急落することが観察されました。実験方法の詳細は以下の段落で説明します。
一貫性ハッシュルーティング方法
一貫性ハッシュは、大規模なキャッシュミスの可能性を最小限に抑えるために設計された概念 です。
アイデアはシンプルです。ハッシュ空間の開始と終了をリングで接続し、その上にノードを配置します。各ノードは自分のハッシュ空間を割り当てられ、トラフィックを待ちます。
ノードを配置するために使用されるハッシュ関数は、モジュロ演算とは独立しています。
次に、この一貫性ハッシュを実装したルーターにトラフィックが入る状況を仮定しましょう。
ハッシュ関数を通過したトラフィックは、リング上の最も近いノードにルーティングされます。ノードBは将来のリクエストに備えてkey1
をキャッシュします。
大量のトラフィックが発生しても、トラフィックは同じ原則に従ってそれぞれのノードにルーティングされます。