分布式存儲系統中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 6映射到 vNode2：object 6 --> vNode2
Object 7映射到 vNodeN：object 7 --> vNodeN
第二輪映射：
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
