本算法是基于最小費(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)做床估。
