[發(fā)明專(zhuān)利]基于網(wǎng)絡(luò)計(jì)算的糾刪碼更新方法及系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 201910341782.8
• 申請(qǐng)日: 2019-04-26
• 公開(kāi)（公告）號(hào): CN110190926B
• 公開(kāi)（公告）日: 2020-09-18
• 發(fā)明（設(shè)計(jì)）人: 王芳;馮丹;唐英杰;謝燕文
• 申請(qǐng)（專(zhuān)利權(quán)）人: 華中科技大學(xué)
• 主分類(lèi)號(hào): H04L1/00
• 分類(lèi)號(hào): H04L1/00;H04L12/931;H04L12/24
• 代理公司: 華中科技大學(xué)專(zhuān)利中心 42201
• 代理人: 曹葆青;李智

本發(fā)明公開(kāi)了一種基于網(wǎng)絡(luò)計(jì)算的糾刪碼更新方法及系統(tǒng)，屬于數(shù)據(jù)可靠存儲(chǔ)領(lǐng)域，更新方法包括：?jiǎn)?dòng)節(jié)點(diǎn)確定待更新節(jié)點(diǎn)；中心化控制器確定節(jié)點(diǎn)間的傳輸路徑，以及參與計(jì)算的交換機(jī)；啟動(dòng)節(jié)點(diǎn)和數(shù)據(jù)節(jié)點(diǎn)向該交換機(jī)發(fā)送數(shù)據(jù)，該交換機(jī)對(duì)接收的數(shù)據(jù)進(jìn)行異或并將結(jié)果發(fā)送至待更新的節(jié)點(diǎn)，以完成對(duì)待更新的數(shù)據(jù)塊或校驗(yàn)塊的更新。本發(fā)明能夠減少糾刪碼修復(fù)操作和糾刪碼更新操作引入的網(wǎng)絡(luò)流量，并提高操作效率。

技術(shù)領(lǐng)域

本發(fā)明屬于數(shù)據(jù)可靠存儲(chǔ)領(lǐng)域，更具體地，涉及一種基于網(wǎng)絡(luò)計(jì)算的糾刪碼修復(fù)方法、糾刪碼更新方法及系統(tǒng)。

背景技術(shù)

糾刪碼作為一種數(shù)據(jù)冗余策略，被廣泛應(yīng)用在分布式存儲(chǔ)系統(tǒng)中以提供數(shù)據(jù)可靠性。通常，糾刪碼以一定數(shù)量的數(shù)據(jù)塊作為輸入，對(duì)其進(jìn)行編碼后產(chǎn)生一定數(shù)量的校驗(yàn)塊，這樣一組數(shù)據(jù)塊和校驗(yàn)塊一起構(gòu)成了一種被稱(chēng)為條帶的邏輯結(jié)構(gòu)。

糾刪碼修復(fù)操作，是指在降級(jí)讀或者數(shù)據(jù)重建任務(wù)中，通過(guò)網(wǎng)絡(luò)從其他節(jié)點(diǎn)上讀取多個(gè)可用塊，然后通過(guò)相關(guān)的矩陣運(yùn)算修復(fù)出丟失數(shù)據(jù)塊的操作，如圖1(a)所示；由于來(lái)自多個(gè)節(jié)點(diǎn)的數(shù)據(jù)都要傳輸至客戶(hù)端或重建節(jié)點(diǎn)，因此客戶(hù)端或重建節(jié)點(diǎn)所在的下行鏈路會(huì)形成一個(gè)網(wǎng)絡(luò)瓶頸。糾刪碼更新操作，是指為保證同一條帶上數(shù)據(jù)塊和校驗(yàn)塊的一致性，更新一個(gè)數(shù)據(jù)塊的同時(shí)對(duì)條帶內(nèi)所有校驗(yàn)塊也進(jìn)行更新的操作，如圖1(b)所示；由于被更新的數(shù)據(jù)節(jié)點(diǎn)會(huì)承擔(dān)所有的數(shù)據(jù)發(fā)送任務(wù)，數(shù)據(jù)節(jié)點(diǎn)所在的上行鏈路會(huì)形成一個(gè)網(wǎng)絡(luò)瓶頸。根據(jù)圖1(a)和圖1(b)所示的操作原理可知，傳統(tǒng)的糾刪碼修復(fù)操作和更新操作，均會(huì)引入大量的網(wǎng)絡(luò)流量，并且存在單鏈路瓶頸問(wèn)題，這一方面會(huì)導(dǎo)致修復(fù)和更新操作的效率低下、耗時(shí)較長(zhǎng)，另一方面會(huì)嚴(yán)重影響網(wǎng)絡(luò)中其他應(yīng)用的性能。

圖1(c)所示的基于鏈?zhǔn)絺鬏斅窂降男迯?fù)方法可緩解糾刪碼修復(fù)操作中的單鏈路瓶頸問(wèn)題，該修復(fù)方法中，每個(gè)節(jié)點(diǎn)接收到數(shù)據(jù)后將其與本地存儲(chǔ)的數(shù)據(jù)進(jìn)行異或運(yùn)算后將運(yùn)算結(jié)果繼續(xù)向后轉(zhuǎn)發(fā)，這個(gè)過(guò)程一直重復(fù)直至數(shù)據(jù)到達(dá)啟動(dòng)該修復(fù)操作的啟動(dòng)節(jié)點(diǎn)。圖1(c)所示的糾刪碼修復(fù)方法能夠緩解瓶頸鏈路的傳輸壓力，達(dá)到鏈路負(fù)載均衡的目的，但并未真正減少所引入的網(wǎng)絡(luò)流量，這些流量將繼續(xù)占用稀缺的帶寬資源進(jìn)而影響系統(tǒng)中其他應(yīng)用的性能。

圖1(d)所示的基于樹(shù)型傳輸路徑的糾刪碼更新方法可緩解糾刪碼更新操作中的單鏈路瓶頸問(wèn)題，該更新方法將所有需要被更新的節(jié)點(diǎn)按照樹(shù)型結(jié)構(gòu)進(jìn)行組織，其中，被更新的數(shù)據(jù)節(jié)點(diǎn)作為根節(jié)點(diǎn)，被更新的校驗(yàn)節(jié)點(diǎn)作為中間節(jié)點(diǎn)和葉子節(jié)點(diǎn)，根節(jié)點(diǎn)負(fù)責(zé)計(jì)算更新增量、更新數(shù)據(jù)塊并將增量轉(zhuǎn)發(fā)給其子節(jié)點(diǎn)，子節(jié)點(diǎn)接收到更新增量后更新本地校驗(yàn)塊并將更新增量繼續(xù)向下轉(zhuǎn)發(fā)給其子節(jié)點(diǎn)，這個(gè)過(guò)程一直重復(fù)直到更新增量到達(dá)所有的葉子節(jié)點(diǎn)。圖1(d)所示的糾刪碼更新方法將原本被更新數(shù)據(jù)節(jié)點(diǎn)的傳輸壓力分散給了多個(gè)校驗(yàn)節(jié)點(diǎn)，但是并沒(méi)有完全消除網(wǎng)絡(luò)瓶頸，而且，該方法并未真正減少所引入的網(wǎng)絡(luò)流量，這些流量將繼續(xù)占用稀缺的帶寬資源進(jìn)而影響系統(tǒng)中其他應(yīng)用的性能。

總體而言，現(xiàn)有的糾刪碼修復(fù)方法和糾刪碼更新方法會(huì)引入大量的網(wǎng)絡(luò)流量，會(huì)嚴(yán)重影響網(wǎng)絡(luò)中其他應(yīng)用的性能，并且操作效率較低。

發(fā)明內(nèi)容

針對(duì)現(xiàn)有技術(shù)的缺陷和改進(jìn)需求，本發(fā)明提供了一種基于網(wǎng)絡(luò)計(jì)算的糾刪碼修復(fù)方法、糾刪碼更新方法及系統(tǒng)，其目的在于，減少糾刪碼修復(fù)操作和糾刪碼更新操作引入的網(wǎng)絡(luò)流量，并提高操作效率。

為實(shí)現(xiàn)上述目的，按照本發(fā)明的第一方面，提供了一種基于網(wǎng)絡(luò)計(jì)算的糾刪碼修復(fù)方法，包括：

(S1)啟動(dòng)節(jié)點(diǎn)根據(jù)編碼關(guān)系確定參與修復(fù)操作的可用節(jié)點(diǎn)，并將各可用節(jié)點(diǎn)及其自身的位置信息均發(fā)送至網(wǎng)絡(luò)中的中心化控制器；

(S2)中心化控制器根據(jù)網(wǎng)絡(luò)拓?fù)浯_定啟動(dòng)節(jié)點(diǎn)到各可用節(jié)點(diǎn)間的傳輸路徑，以及傳輸路徑上參與計(jì)算的交換機(jī)，并將所確定的信息發(fā)送至啟動(dòng)節(jié)點(diǎn)；

(S3)啟動(dòng)節(jié)點(diǎn)根據(jù)傳輸路徑建立與各可用節(jié)點(diǎn)間的連接后，向各可用節(jié)點(diǎn)發(fā)送數(shù)據(jù)請(qǐng)求；