分布式存儲(chǔ)系統(tǒng)的分容災(zāi)塊數(shù)據(jù)分布算法

本算法是基于最小費(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)用為流量平方的邊憋槐,如下圖:

Paste_Image.png

圖中有三個(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)做床估。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末诱渤,一起剝皮案震驚了整個(gè)濱河市勺美,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌赡茸,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件遗菠,死亡現(xiàn)場(chǎng)離奇詭異辙纬,居然都是意外死亡叭喜,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén)譬涡,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)启绰,“玉大人沟使,你說(shuō)我怎么就攤上這事∽徘悖” “怎么了燕少?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵客们,是天一觀的道長(zhǎng)材诽。 經(jīng)常有香客問(wèn)我恒傻,道長(zhǎng),這世上最難降的妖魔是什么睁枕? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任沸手,我火速辦了婚禮契吉,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘栅隐。我一直安慰自己租悄,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布胶哲。 她就那樣靜靜地躺著潭辈,像睡著了一般。 火紅的嫁衣襯著肌膚如雪寄摆。 梳的紋絲不亂的頭發(fā)上修赞,一...
    開(kāi)封第一講書(shū)人閱讀 52,713評(píng)論 1 312
  • 那天,我揣著相機(jī)與錄音勾邦,去河邊找鬼割择。 笑死,一個(gè)胖子當(dāng)著我的面吹牛蕉饼,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播昧港,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼慨飘,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了休弃?” 一聲冷哼從身側(cè)響起圈膏,我...
    開(kāi)封第一講書(shū)人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤稽坤,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后尿褪,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體杖玲,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年臼闻,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了囤采。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片数焊。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖互墓,靈堂內(nèi)的尸體忽然破棺而出缤谎,到底是詐尸還是另有隱情褐着,我是刑警寧澤托呕,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布频敛,位于F島的核電站馅扣,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏差油。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一蓄喇、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧妆偏,春花似錦、人聲如沸钱骂。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)愉烙。三九已至,卻和暖如春解取,著一層夾襖步出監(jiān)牢的瞬間齿梁,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工肮蛹, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留勺择,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓伦忠,卻偏偏與公主長(zhǎng)得像省核,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子昆码,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容