分布式存儲系統(tǒng)中DHT算法改進(jìn)
1、概述
通常，分布式存儲系統(tǒng)以及分布式緩存系統(tǒng)習(xí)慣采用分布式哈希（DHT）算法來實(shí)現(xiàn)數(shù)據(jù)的分區(qū)分配（路由）以及負(fù)載均衡，普通的分布式hash算法通過增添虛擬節(jié)點(diǎn)，對物理的熱點(diǎn)區(qū)間進(jìn)行劃分，將負(fù)載分配至其他節(jié)點(diǎn)，從而達(dá)到負(fù)載均衡的狀態(tài)，但是這并不能保證集群的負(fù)載就一定很是的均衡。
而一種改進(jìn)過的一致性Hash算法，即帶邊界因子的一致性Hash算法，其嚴(yán)格控制每個節(jié)點(diǎn)的負(fù)載從而能獲得更好的負(fù)載均衡效果[1][2]。
2、普通的DHT算法
假設(shè)有8個Object，通過下圖的DHT算法:
object 0,1,2映射到了虛擬節(jié)點(diǎn)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算法負(fù)債均衡因子并不是很好。
3、帶負(fù)載邊界因子的DHT算法
假設(shè)有8個Object，通過如下圖的DHT with bounded loads算法:
第一輪映射：
object 0,1,2 需要映射到了虛擬節(jié)點(diǎn)vNode0，但是vNode0的權(quán)重因子是 2，因此只完成了 object 0,1 --> vNode0， object 2不能映射到節(jié)點(diǎn) vNode0；
Object 3,4,5 需要映射到了虛擬節(jié)點(diǎn)vNode1：但是vNode1的權(quán)重因子是 2，因此只完成了 object 3,4 --> vNode1， object 5不能映射到節(jié)點(diǎn) vNode1；
Object 6映射到 vNode2：object 6 --> vNode2
Object 7映射到 vNodeN：object 7 --> vNodeN
第二輪映射：
Object 2 映射到 vNode1，但是vNode1權(quán)重因子=0， 不能被接收，繼續(xù)往下一個節(jié)點(diǎn)走，發(fā)現(xiàn)vNode2 權(quán)重因子是2,還剩權(quán)重因子1，可以被映射，因此 object 2-->vNode2
Object 5 映射到 vNode2，但是vNode2現(xiàn)在的權(quán)重因子=0， 不能被接收，繼續(xù)往下一個節(jié)點(diǎn)走，發(fā)現(xiàn)vNodeN 權(quán)重因子是2,還剩權(quán)重因子1，可以被映射，因此 object 5-->vNodeN
最終的映射結(jié)果是
object 0,1映射到了虛擬節(jié)點(diǎn)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é)點(diǎn)都分到2個 object，
顯然帶負(fù)載邊界因子的DHT算法負(fù)債均衡比普通的DHT算法來的好。
這些節(jié)點(diǎn)的負(fù)載因子可以從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
