分散式存儲系統中DHT演算法改進

1、概述

通常，分散式存儲系統以及分散式緩存系統習慣採用分散式哈希（DHT）演算法來實現數據的分區分配（路由）以及負載均衡，普通的分散式hash演算法通過增添虛擬節點，對物理的熱點區間進行劃分，將負載分配至其他節點，從而達到負載均衡的狀態，但是這並不能保證集群的負載就一定很是的均衡。

而一種改進過的一致性Hash演算法，即帶邊界因子的一致性Hash演算法，其嚴格控制每個節點的負載從而能獲得更好的負載均衡效果[1][2]。

2、普通的DHT演算法

假設有8個Object，通過下圖的DHT演算法:

object 0,1,2映射到了虛擬節點vNode0 ： object 0,1,2 --> vNode0

Object 3,4,5 映射到了vNode1：object 3,4,5 --> vNode1

Object 6映射到 vNode2：object 6 --> vNode2

Object 7映射到 vNodeN：object 7 --> vNodeN

很明顯，Vnode0和vNode1 都落了三個 object，而 vNode2和vNodeN 都只落了 1個Object，這裡的DHT演算法負債均衡因子並不是很好。

3、帶負載邊界因子的DHT演算法

假設有8個Object，通過如下圖的DHT with bounded loads演算法:

第一輪映射：

object 0,1,2 需要映射到了虛擬節點vNode0，但是vNode0的權重因子是 2，因此只完成了 object 0,1 --> vNode0， object 2不能映射到節點 vNode0；

Object 3,4,5 需要映射到了虛擬節點vNode1：但是vNode1的權重因子是 2，因此只完成了 object 3,4 --> vNode1， object 5不能映射到節點 vNode1；

第二輪映射：

Object 2 映射到 vNode1，但是vNode1權重因子=0， 不能被接收，繼續往下一個節點走，發現vNode2 權重因子是2,還剩權重因子1，可以被映射，因此 object 2-->vNode2

Object 5 映射到 vNode2，但是vNode2現在的權重因子=0， 不能被接收，繼續往下一個節點走，發現vNodeN 權重因子是2,還剩權重因子1，可以被映射，因此 object 5-->vNodeN

最終的映射結果是

object 0,1映射到了虛擬節點vNode0 ： object 0,1 --> vNode0

Object 3,4 映射到了vNode1：object 3,4 --> vNode1

Object 2,6映射到 vNode2：object 2,6 --> vNode2

Object 5,7映射到 vNodeN：object 5,7 --> vNodeN

很明顯，Vnode0，vNode1，vNode2, vNodeN 每個節點都分到2個 object，

顯然帶負載邊界因子的DHT演算法負債均衡比普通的DHT演算法來的好。

這些節點的負載因子可以從IO，CPU，MEM，Disk，Network等輸入因子計算出來。

參考資料

[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

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！