分散ストレージシステムにおける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