本算法是基于最小費(fèi)用最大流算法建模虽画,讀者需要對(duì)最小費(fèi)用最大流算法有一定的基礎(chǔ)荣病,要能理解這個(gè)例題 http://www.cppblog.com/y346491470/articles/153091.html?opt=admin
分布式存儲(chǔ)系統(tǒng)為了保證高可用性和數(shù)據(jù)安全,大都會(huì)保存多個(gè)副本脖岛,但是如果不注意數(shù)據(jù)的分布策略颊亮,遇到機(jī)架級(jí)別的故障就會(huì)導(dǎo)致數(shù)據(jù)不可用,所以將數(shù)據(jù)的多個(gè)副本分配到屬于不同容災(zāi)塊的機(jī)器上應(yīng)該是多副本分布式存儲(chǔ)系統(tǒng)的基本需求绍在。
一種最簡(jiǎn)單的辦法,是直接給集群提供多組機(jī)器揣苏,每組機(jī)器保存所有數(shù)據(jù)的一個(gè)副本,各組機(jī)器屬于不同的容災(zāi)塊脯厨。騰訊的tfs采用的是這種架構(gòu)坑质,但是這種架構(gòu)太依賴機(jī)房的規(guī)劃,不是所有企業(yè)都能這么玩的稼跳。本文就是要給出一個(gè)不依賴機(jī)房規(guī)劃的多副本分容災(zāi)塊分布算法吃沪,實(shí)現(xiàn)每個(gè)容災(zāi)塊的機(jī)器上沒(méi)有重復(fù)的數(shù)據(jù)。
現(xiàn)在的分布式存儲(chǔ)系統(tǒng)一般有兩種數(shù)據(jù)分組方式:
1.以bigtable為代表的红淡,保證了關(guān)鍵字的有序性的按關(guān)鍵字范圍動(dòng)態(tài)分組
2.哈希分組
本文的算法主要針對(duì)哈希分組方式降铸。對(duì)按關(guān)鍵字范圍動(dòng)態(tài)分組的方式,作者沒(méi)有實(shí)際運(yùn)維經(jīng)驗(yàn)桶蝎,就不涉及了谅畅。
哈希分組對(duì)比按關(guān)鍵字范圍動(dòng)態(tài)分組,犧牲了關(guān)鍵字有序性绍豁,導(dǎo)致數(shù)據(jù)庫(kù)難以支持模糊查詢等依賴關(guān)鍵字順序的操作牙捉,好處是實(shí)現(xiàn)簡(jiǎn)單、將容量邪铲、讀、寫(xiě)三個(gè)維度的壓力統(tǒng)一到了一個(gè)維度上昧碉,只要桶的分布均勻,這三個(gè)維度的壓力就都能均勻分布四康。所以針對(duì)一致性哈希的情況狭握,本算法的目標(biāo)變成了:實(shí)現(xiàn)每個(gè)容災(zāi)塊的機(jī)器上沒(méi)有重復(fù)的桶,并且每臺(tái)機(jī)器上桶的數(shù)量盡量平均哎垦。
再來(lái)準(zhǔn)確描述一下現(xiàn)在的問(wèn)題:有n個(gè)桶恃疯,每個(gè)桶有m份副本,集群的機(jī)器分布在k(k>=m)個(gè)容災(zāi)塊中今妄,第一個(gè)容災(zāi)塊有a1臺(tái)機(jī)器盾鳞,第二個(gè)容災(zāi)塊有a2臺(tái)機(jī)器......。現(xiàn)在把這n*m個(gè)副本分配到這些機(jī)器上雁仲,要保證每個(gè)容災(zāi)塊內(nèi)的機(jī)器對(duì)任意一個(gè)桶至多分到一份副本攒砖,每個(gè)機(jī)器上分到的副本數(shù)盡量平均日裙。所謂盡量平均,我量化為“每個(gè)機(jī)器上分到的副本數(shù)的平方和最小”昂拂。
本文的問(wèn)題可以如此建模:
有三類點(diǎn):每個(gè)桶一個(gè)點(diǎn)格侯,每個(gè)容災(zāi)塊一個(gè)點(diǎn),每臺(tái)機(jī)器一個(gè)點(diǎn)联四,再加上源和匯
源向每個(gè)桶連一條邊,容量為m朝墩,每個(gè)桶向每個(gè)容災(zāi)塊連一條邊,容量為1亿卤,每個(gè)容災(zāi)塊向?qū)儆谧约旱臋C(jī)器連一條邊,容量不限秆乳,前面這些邊費(fèi)用都為0傍念,最后每臺(tái)機(jī)器向匯連一條容量不限,費(fèi)用為流量平方的邊憋槐,如下圖:
圖中有三個(gè)桶b1阳仔、b2、b3嘶摊,6臺(tái)機(jī)器评矩,機(jī)器h1屬于容災(zāi)塊d1,機(jī)器h2虱颗、h3蔗喂、h4屬于容災(zāi)塊d2,機(jī)器h5缰儿、h6屬于容災(zāi)塊d3
求出這個(gè)圖的最小費(fèi)用最大流乖阵,就可以構(gòu)造出分布方案了。
許多分布式存儲(chǔ)系統(tǒng)會(huì)從每個(gè)桶的副本中選一個(gè)作為主副本瞪浸,所有讀操作只能在主副本上進(jìn)行,這樣能夠有效提高讀緩存的效果椅棺。選主副本也會(huì)希望盡量平均地分布在每臺(tái)機(jī)器上,可以用類似上面的算法來(lái)做床估。