Consistent Hashing は、分散システムが頻繁にスケールアップ、スケールダウンするような動的な環境で運用すると、実にうまくいくハッシュ技法である。 Consistent Hashing の核となる概念は、論文 Consistent Hashing and RandomTrees で紹介された。 The Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web）で紹介されましたが、DynamoDBを紹介した有名な論文 – Dynamoの後に人気を博しました。 Amazonの高可用性Key-Valueストア）を紹介した論文で有名になりました。 それ以来、一貫性のあるハッシュは人気を博し、分散システムの設計とスケーリングを効率的に行うための多くのユースケースを発見しました。 この技術を徹底的に利用した2つの有名な例として、ピアツーピアネットワークのBit TorrentとウェブキャッシュのAkamaiが挙げられます。 この記事では、Consistent Hashing の必要性とその内部について深く掘り下げ、さらに重要なこととして、配列とバイナリ検索を使用して実装します。

Consistent Hashing のコア テクニックに入る前に、まずいくつかのことをクリアにしておきます。 ハッシュ関数とは、任意のサイズのドメインから別の固定サイズのドメインに値をマッピングする関数で、通常ハッシュ空間と呼ばれます。 例えば、URLを32ビットの整数に、WebページのHTMLコンテンツを256バイトの文字列にマッピングするようなものです。 これらのハッシュ関数の出力として生成された値は、通常、元の実体の効率的な検索を可能にするキーとして使用されます。

単純なハッシュ関数の例としては、32 ビット整数を 8 ビット整数のハッシュ空間にマッピングする関数があります。 この関数は算術演算子 modulo を使って実装することができ、modulo 256 を使って の範囲の数値を生成し、その表現に 8 ビットを使うことで実現できる。 このような整数領域にキーをマッピングするハッシュ関数は、多くの場合modulo Nを適用して値、つまりハッシュ空間をの範囲に限定する。

優れたハッシュ関数は以下の特性を持ちます。

• 関数は計算効率が高く、生成された値は検索しやすい
• 関数は、ほとんどの一般使用例において、顕著な相関なしにデータを均一に拡散させる疑似ランダム生成器のように動作する

さて、ハッシュ関数とは何かを見たので、それらをどのようにして使用して、ある程度拡張できる分散システムを構築できるかを調べてみましょう。

分散ストレージ システムの構築

ユーザーがファイルをアップロードして、必要に応じてアクセスできる分散ストレージ システムを構築しているとします。 このサービスは、ファイルをアップロードするためにユーザー

• upload に、ファイルを取得してその内容を返すためにファイル
• fetch に、次の API を公開します

舞台裏では、システムはファイルが保存されてアクセスされるストレージ ノードを持っています。 これらのノードは、ディスクにファイルのコンテンツを置いたり取得したりする関数 put_file と fetch_file を公開し、メイン API サーバーに応答を送信し、そこからユーザーに応答を返します。

初期の負荷を維持するために、システムには 5 つの Stogare ノードがあり、分散方式でアップロード ファイルを保存します。 複数のノードを持つことで、システム全体が圧倒されないようにし、ストレージがほぼ均等に分散されます。

ユーザーがファイルのパスでupload機能を呼び出すと、システムはまず、ファイルの保持に責任を負うストレージ ノードを識別する必要があります。

# storage_nodes holding instances of actual storage node objectsstorage_nodes = def hash_fn(key): """The function sums the bytes present in the `key` and then take a mod with 5. This hash function thus generates output in the range . """ return sum(bytearray(key.encode('utf-8'))) % 5def upload(path): # we use the hash function to get the index of the storage node # that would hold the file index = hash_fn(path) # we get the StorageNode instance node = storage_nodes # we put the file on the node and return return node.put_file(path)def fetch(path): # we use the hash function to get the index of the storage node # that would hold the file index = hash_fn(path) # we get the StorageNode instance node = storage_nodes # we fetch the file from the node and return return node.fetch_file(path)

ここで使用されるハッシュ関数は、単にバイトを合計して 5 でモジュロし、ハッシュ空間 に出力を生成します (システムには 5 つのストレージ ノードがあるため)。 4273>

たとえば、5 つのファイル ‘f1.txt’, ‘f2.txt’, ‘f3.txt’, ‘f4.txt’, ‘f5.txt’ があるとします。txt’ があるとします。これらにハッシュ関数を適用すると、これらはそれぞれストレージ ノード E、A、B、C、D に保存されていることがわかります。

システムがある程度普及して 7 ノードに拡張する必要があるとき、事態は面白くなります。 ハッシュ関数を変更することは、ファイルとストレージ ノードのマッピングと関連付けを変更することを意味します。 4273>

新しいハッシュ関数では、同じ 5 つのファイル ‘f1.txt’, ‘f2.txt’, ‘f3.txt’, ‘f4.txt’, ‘f5.txt’ がストレージ ノード D, E, F, G, A と関連付けられることになります。 4273>

スケールアップまたはスケールダウンのたびにハッシュ関数を変更しなければならず、そのためにデータのすべてではなく半分でも移動しなければならない場合、処理は非常に高くなり、長期的には実現不可能になります。 そこで、スケールアップまたはスケールダウン時に必要なデータ移動を最小限に抑える方法が必要です。そこで、Consistent Hashing が適合し、必要なデータ転送を最小限に抑えることができます。 これらの関連付けは純粋に基礎となるハッシュ関数によって駆動されるため、このハッシュ関数をシステム内のストレージ ノードの数から独立させることができれば、この欠陥に対処できます。

Consistent Hashing では、ハッシュ空間を巨大かつ一定、どこか のオーダーに保ち、ストレージ ノードとオブジェクトを両方ともこの巨大ハッシュ空間のスロットにマッピングすることによって、この状況に対処しています。 従来のシステムでは、ファイルはハッシュ化されたインデックスのストレージ ノードと関連付けられていましたが、このシステムでは、ファイルとストレージ ノードが衝突する可能性は限りなく低く、したがって、この関連を定義する別の方法が必要です。 この方法で関連付けを定義すると、

• ストレージ ノードの数に依存しないハッシュ関数を維持し、
• 絶対衝突によってではなく、関連付けを相対的に維持することができます

Consistent Hashing では平均して k/n 単位のデータのみがスケール アップおよびスケール ダウン中に移行される必要があります。 ここで、kはキーの総数、nはシステム内のノード数である。

これを実装する非常に単純な方法は、ハッシュ空間と同じサイズの配列を割り当て、ファイルとストレージ ノードを文字通りハッシュされた場所の配列に配置することです。 関連付けを行うには、アイテムのハッシュ化された位置から右に向かって繰り返し、最初のストレージ ノードを見つけます。 配列の末尾に到達してストレージノードが見つからない場合は、インデックス 0 に戻って検索を続行します。 この方法は非常に簡単に実装できますが、次のような制限があります。

• このような大きな配列を保持するには巨大なメモリが必要です。
• 右方向に毎回反復して関連を見つけるのは O(hash_space)

これを実装するより良い方法は 2 つの配列を使うことです。1 つは nodes というストレージ ノード用の配列で、もう一つは keys というハッシュ空間のストレージ ノード位置を保持しているものです。 ストレージノードnodesはハッシュ空間の位置keysに存在するというように、2つのアレイは1対1で対応する。 4273>

Consistent Hashingにおけるハッシュ関数

このハッシュ空間全体のサイズとしてtotal_slotsを定義し、通常2^256のオーダーで、ハッシュ関数はSHA-256とmod total_slotsで実装することができる。 total_slotsは巨大で定数であるため、以下のハッシュ関数の実装は、システムに存在するストレージノードの実際の数に依存せず、したがってスケールアップやスケールダウンなどの事象に影響されないままである。

def hash_fn(key: str, total_slots: int) -> int: """hash_fn creates an integer equivalent of a SHA256 hash and takes a modulo with the total number of slots in hash space. """ hsh = hashlib.sha256() # converting data into bytes and passing it to hash function hsh.update(bytes(key.encode('utf-8'))) # converting the HEX digest into equivalent integer value return int(hsh.hexdigest(), 16) % total_slots

システムに新しいノードを追加する

システムに新しいノードを追加してスケールアップする必要がある場合、この例では新しいストレージ ノードが必要です。 新しいノードがシステムに追加されると、新しいノードが収まる位置の左側の位置でハッシュされ、右側のノードに関連付けられたファイルにのみ影響します。 他のすべてのファイルと関連付けは影響を受けないので、移行されるデータの量と変更される必要のあるマッピングを最小限に抑えることができます。

上の図から、新しいノード K がノード B と E の間に追加されるとき、セグメント B-K に存在するファイルの関連付けを変更してノード K に割り当てたことがわかります。

これをnodesとkeysの配列を使って低レベルで実装すると、まずハッシュ関数を使ってHash Space内の新しいノードの位置を取得します。 次に、バイナリサーチを使用して、ソートされた keys 配列の中でその位置より大きい最小のキーのインデックスを見つける。 このインデックスが、キーと新しいストレージノードがそれぞれkeys配列とnodes配列に配置される場所となります。

def add_node(self, node: StorageNode) -> int: """add_node function adds a new node in the system and returns the key from the hash space where it was placed """ # handling error when hash space is full. if len(self._keys) == self.total_slots: raise Exception("hash space is full") key = hash_fn(node.host, self.total_slots) # find the index where the key should be inserted in the keys array # this will be the index where the Storage Node will be added in the # nodes array. index = bisect(self._keys, key) # if we have already seen the key i.e. node already is present # for the same key, we raise Collision Exception if index > 0 and self._keys == key: raise Exception("collision occurred") # Perform data migration # insert the node_id and the key at the same `index` location. # this insertion will keep nodes and keys sorted w.r.t keys. self.nodes.insert(index, node) self._keys.insert(index, key) return key

システムから新しいノードを削除する

システムから既存のノードを削除してスケールダウンする必要がある場合。 we

• Hash Space から削除するノードの位置を見つける
• populate the node to be associated with the node to be removed
• remove the node from the Hash Space

システムからノードを削除すると、ノード自身に関連するファイルのみに影響します。 他のすべてのファイルと関連付けは影響を受けず、したがって、移行するデータ量と変更する必要のあるマッピングを最小限に抑えます。

上の図から、ノード K をシステムから削除すると、ノード K と関連するファイルの関連付けをそのすぐ右にあるノードに変更することがわかります。

これをnodesとkeys配列を使って低レベルで実装するために、バイナリサーチを使ってkeys配列内のノードKが存在するインデックスを取得します。 インデックスが得られたら、そのインデックスに存在する keys 配列と nodes 配列からキーを削除します。

def remove_node(self, node: StorageNode) -> int: """remove_node removes the node and returns the key from the hash space on which the node was placed. """ # handling error when space is empty if len(self._keys) == 0: raise Exception("hash space is empty") key = hash_fn(node.host, self.total_slots) # we find the index where the key would reside in the keys index = bisect_left(self._keys, key) # if key does not exist in the array we raise Exception if index >= len(self._keys) or self._keys != key: raise Exception("node does not exist") # Perform data migration # now that all sanity checks are done we popping the # keys and nodes at the index and thus removing the presence of the node. self._keys.pop(index) self.nodes.pop(index) return key

アイテムとノードの関連付け

さて、一貫したハッシュ処理がスケールアップおよびスケールダウン時のデータ移行を最低限に抑えるために役立つ方法を見てきましたが、次は与えられたアイテムに対して「右のノード」を効率的に見つける方法を見てみましょう。 関連付けを見つける操作は、システム上で起こる読み取りと書き込みのたびに呼び出されるものであるため、非常に高速で効率的でなければなりません。 まずアイテムをハッシュ関数に渡し、そのアイテムがハッシュ空間内でハッシュされた位置を取得する。 この位置をkeys配列でバイナリサーチして、（ハッシュ関数で取得した）位置より大きい最初のキーのインデックスを取得する。keys配列に位置より大きいキーがない場合は、折り返して0番目のインデックスが返される。 このようにして得られたインデックスは、アイテムに関連付けられた nodes 配列内のストレージ ノードのインデックスとなります。

def assign(self, item: str) -> str: """Given an item, the function returns the node it is associated with. """ key = hash_fn(item, self.total_slots) # we find the first node to the right of this key # if bisect_right returns index which is out of bounds then # we circle back to the first in the array in a circular fashion. index = bisect_right(self._keys, key) % len(self._keys) # return the node present at the index return self.nodes

Python で Consistent Hashing を実装したソース コードは github.com/arpitbbhayani/consistent-hashing.

まとめ

Consistent Hashing は任意の分散システムを水平方向に拡張および管理するのに最も重要なアルゴリズムの 1 つです。 このアルゴリズムはシャード化されたシステムで動作するだけでなく、負荷分散、データ分割、サーバー ベースのスティッキー セッションの管理、ルーティング アルゴリズム、およびその他多くのアプリケーションで使用されることが分かっています。 多くのデータベースは、そのスケール、パフォーマンス、膨大な負荷を処理する能力を Consistent Hashing に負っています。

• Hash Functions – Wikipedia
• Consistent Hashing – Wikipedia
• Consistent Hashing – Stanford
• Consistent Hashing と RandomTrees

Dynamo: Amazon’s Highly Available Key-value Store

その他、お勧めの記事もあります。

• Python Caches Integers
• Fractional Cascading – Speeding up Binary Searches
• Copy-on-Write Semantics
• What makes MySQL LRU cache scan resistant
• Building Finite State Machines with Python Coroutines

This article was originally published on my blog – Consistent Hashing.

この記事を読んで気に入っていただけたなら、私のニュースレターを購読して、記事を直接受信トレイに届けてもらい、私に @arpit_bhayani.

と声をかけていただければと思います。