1、概述

通常，分布式存儲系統(tǒng)以及分布式緩存系統(tǒng)習慣采用分布式哈希（DHT）算法來實現(xiàn)數(shù)據(jù)的分區(qū)分配（路由）以及負載均衡，普通的分布式hash算法通過增添虛擬節(jié)點，對物理的熱點區(qū)間進行劃分，將負載分配至其他節(jié)點，從而達到負載均衡的狀態(tài)，但是這并不能保證集群的負載就一定很是的均衡。

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

[[222256]]

2、普通的DHT算法

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

object 0,1,2映射到了虛擬節(jié)點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 需要映射到了虛擬節(jié)點vNode0，但是vNode0的權重因子是 2，因此只完成了 object 0,1 --> vNode0， object 2不能映射到節(jié)點 vNode0；

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

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

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

第二輪映射：

Object 2 映射到 vNode1，但是vNode1權重因子=0， 不能被接收，繼續(xù)往下一個節(jié)點走，發(fā)現(xiàn)vNode2 權重因子是2,還剩權重因子1，可以被映射，因此 object 2-->vNode2

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

最終的映射結果是

object 0,1映射到了虛擬節(jié)點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 每個節(jié)點都分到2個 object，

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

這些節(jié)點的負載因子可以從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