分散ストレージシステムにおけるDHTアルゴリズムの改善

1. 概要

通常、分散ストレージ システムや分散キャッシュ システムでは、分散ハッシュ (DHT) アルゴリズムを使用してデータの分割 (ルーティング) と負荷分散を実現します。通常の分散ハッシュ アルゴリズムは、仮想ノードを追加することで物理的なホットスポットを分割し、負荷を他のノードに分散することで負荷分散を実現します。ただし、これではクラスターの負荷が完全に分散されることは保証されません。

改良されたコンシステントハッシュアルゴリズム、すなわち境界係数を備えたコンシステントハッシュアルゴリズムは、各ノードの負荷を厳密に制御し、より優れた負荷分散効果を実現できます[1][2]。

[[222256]]

2. 通常のDHTアルゴリズム

以下に示す DHT アルゴリズムを使用して、オブジェクトが 8 個あると仮定します。

オブジェクト 0,1,2 は仮想ノード vNode0 にマップされます: オブジェクト 0,1,2 --> vNode0

オブジェクト 3,4,5 は vNode1 にマップされます: オブジェクト 3,4,5 --> vNode1

オブジェクト 6 は vNode2 にマップされます: オブジェクト 6 --> vNode2

オブジェクト 7 は vNodeN にマップされます: オブジェクト 7 --> vNodeN

明らかに、Vnode0 と vNode1 には 3 つのオブジェクトがありますが、vNode2 と vNodeN には 1 つのオブジェクトしかありません。DHT アルゴリズムの負債バランス係数はあまり良くありません。

3. 負荷境界係数を用いたDHTアルゴリズム

以下に示すように、制限付き負荷アルゴリズムを使用した DHT を使用し、オブジェクトが 8 個あると仮定します。

マッピングの第 1 ラウンド:

オブジェクト 0、1、2 は仮想ノード vNode0 にマップする必要がありますが、vNode0 の重み係数は 2 であるため、オブジェクト 0、1 --> vNode0 のみが完了し、オブジェクト 2 はノード vNode0 にマップできません。

オブジェクト 3、4、5 は仮想ノード vNode1 にマップする必要があります。ただし、vNode1 の重み係数は 2 なので、オブジェクト 3、4 --> vNode1 のみが完了し、オブジェクト 5 はノード vNode1 にマップできません。

オブジェクト 6 は vNode2 にマップされます: オブジェクト 6 --> vNode2

オブジェクト 7 は vNodeN にマップされます: オブジェクト 7 --> vNodeN

マッピングの2回目のラウンド:

オブジェクト 2 は vNode1 にマッピングされていますが、vNode1 の重み係数は 0 であるため、受信できません。次のノードに移動すると、vNode2 の重み係数は 2 であり、残りの重み係数は 1 であるため、マッピングできることがわかります。したがって、オブジェクト 2 --> vNode2

オブジェクト 5 は vNode2 にマッピングされていますが、vNode2 の重み係数は 0 であるため、受信できません。次のノードに進むと、vNodeN の重み係数は 2 であることがわかります。残りの重み係数は 1 であるため、マッピングできます。したがって、オブジェクト 5 -->vNodeN

最終的なマッピング結果は

オブジェクト 0,1 は仮想ノード vNode0 にマップされます: オブジェクト 0,1 --> vNode0

オブジェクト 3,4 は vNode1 にマップされます: オブジェクト 3,4 --> vNode1

オブジェクト 2,6 は vNode2 にマップされます: オブジェクト 2,6 --> vNode2

オブジェクト 5,7 は vNodeN にマップされます: オブジェクト 5,7 --> vNodeN

明らかに、Vnode0、vNode1、vNode2、vNodeN の各ノードは 2 つのオブジェクトに分割されます。

明らかに、負荷境界係数を使用した DHT アルゴリズムの負債バランスは、通常の DHT アルゴリズムよりも優れています。

これらのノードの負荷係数は、IO、CPU、MEM、ディスク、ネットワークなどの入力係数から計算できます。

参考文献

[1] https://research.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html

[2] https://medium.com/vimeo-engineering-blog/improving-load-balancing-with-a-new-consistent-hashing-algorithm-9f1bd75709ed