[發(fā)明專利]基于批處理和流水線的分層數(shù)據(jù)一致性協(xié)議優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 201810084245.5
• 申請日: 2018-01-29
• 公開（公告）號(hào): CN108462737B
• 公開（公告）日: 2021-02-02
• 發(fā)明（設(shè)計(jì)）人: 王野;何榮祥;劉璐;徐晗;侯慶輝;張欽宇
• 申請（專利權(quán)）人: 哈爾濱工業(yè)大學(xué)深圳研究生院
• 主分類號(hào): H04L29/08
• 分類號(hào): H04L29/08;G06F3/06;G06F9/46;G06F9/50;G06F9/54
• 代理公司: 深圳市添源知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 44451
• 代理人: 羅志偉

本發(fā)明提供了一種基于批處理和流水線的分層數(shù)據(jù)一致性協(xié)議優(yōu)化方法，包括以下步驟：S1、客戶端判斷待發(fā)送請求數(shù)是否大于0，如果是，則進(jìn)入下一步驟，如果否，則結(jié)束；S2、客戶端向隨機(jī)節(jié)點(diǎn)發(fā)送請求；S3、當(dāng)節(jié)點(diǎn)接收到請求后，轉(zhuǎn)發(fā)給其他所有節(jié)點(diǎn)；S4、當(dāng)其他節(jié)點(diǎn)收到轉(zhuǎn)發(fā)請求后，保存當(dāng)前請求和請求ID，并向其他所有節(jié)點(diǎn)發(fā)送只包含請求ID的確認(rèn)消息；S5、如果對(duì)某一個(gè)請求ID接收到超過半數(shù)的節(jié)點(diǎn)的確認(rèn)信息，則認(rèn)為該請求已經(jīng)被多數(shù)節(jié)點(diǎn)接收，處于可排序狀態(tài)。本發(fā)明的有益效果是：能夠有效降低Multi?Paxos協(xié)議中領(lǐng)導(dǎo)者節(jié)點(diǎn)資源消耗，同時(shí)保證較高的系統(tǒng)性能并且易于工程實(shí)現(xiàn)。

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

本發(fā)明涉及分布式存儲(chǔ)，尤其涉及分布式存儲(chǔ)中一種基于批處理和流水線的分層數(shù)據(jù)一致性協(xié)議優(yōu)化方法。

背景技術(shù)

信息技術(shù)的發(fā)展推動(dòng)著時(shí)代的變革，新一代通信技術(shù)、新型計(jì)算模式的演進(jìn)加深了科學(xué)研究、商業(yè)應(yīng)用、日常生活等各個(gè)應(yīng)用領(lǐng)域的信息化程度。大數(shù)據(jù)時(shí)代的到來和數(shù)據(jù)的爆炸性增長，如何高效、可靠地存儲(chǔ)海量數(shù)據(jù)成為了一項(xiàng)極具挑戰(zhàn)性的工作。傳統(tǒng)的單一節(jié)點(diǎn)的集中式存儲(chǔ)系統(tǒng)已經(jīng)不能滿足需求，越來越多的公司采用分布式存儲(chǔ)系統(tǒng)。與集中式存儲(chǔ)系統(tǒng)相比，分布式存儲(chǔ)系統(tǒng)具有可避免單點(diǎn)故障，降低成本和高可擴(kuò)展性等優(yōu)點(diǎn)。

實(shí)現(xiàn)分布式系統(tǒng)的基本操作是數(shù)據(jù)復(fù)制。數(shù)據(jù)復(fù)制是指在可能分布于多個(gè)機(jī)架、機(jī)房、區(qū)域范圍內(nèi)甚至全球范圍數(shù)據(jù)中心的不同服務(wù)器上對(duì)某個(gè)對(duì)象進(jìn)行多份相同的拷貝。地域上的復(fù)制通過在不同的地理區(qū)域中復(fù)制冗余數(shù)據(jù)可以在全球范圍內(nèi)實(shí)現(xiàn)數(shù)據(jù)持久化、容錯(cuò)和容災(zāi)等功能。通過復(fù)制可以實(shí)現(xiàn)數(shù)據(jù)的高可用性、可擴(kuò)展性以及實(shí)現(xiàn)快速響應(yīng)。在全球范圍服務(wù)和應(yīng)用的時(shí)代，復(fù)制是解決大數(shù)據(jù)挑戰(zhàn)的必需。

伴隨著分布式存儲(chǔ)系統(tǒng)中的復(fù)制產(chǎn)生的一個(gè)重要問題是如何保證副本間的數(shù)據(jù)一致性。分布式系統(tǒng)的數(shù)據(jù)一致性是指數(shù)據(jù)在多個(gè)副本之間能否保持一致的特性。即能夠保證節(jié)點(diǎn)互通的情況下從各個(gè)節(jié)點(diǎn)請求到的數(shù)據(jù)必須是一致的，同時(shí)外部請求對(duì)數(shù)據(jù)做出修改時(shí)，各個(gè)節(jié)點(diǎn)之間也必須同步。

如果分布式系統(tǒng)沒有做好一致性保證，那么當(dāng)用戶訪問不同副本中同一個(gè)數(shù)據(jù)，得到的結(jié)果就會(huì)不一致，導(dǎo)致系統(tǒng)中的數(shù)據(jù)不可靠。對(duì)于金融或者一些其他的對(duì)數(shù)據(jù)的可靠性要求高的行業(yè)來說，數(shù)據(jù)一致性的要求更為必要。

目前能夠同時(shí)保證較好的可靠性和可用性的分布式存儲(chǔ)系統(tǒng)數(shù)據(jù)復(fù)制方式是狀態(tài)機(jī)復(fù)制。它通常是基于復(fù)制日志實(shí)現(xiàn)的，每一個(gè)服務(wù)器存儲(chǔ)一個(gè)包含一系列指令的日志，并且按照日志的順序進(jìn)行執(zhí)行。保證復(fù)制日志相同是通過一致性算法來實(shí)現(xiàn)。就算有些服務(wù)器會(huì)宕機(jī)，一旦指令被正確的復(fù)制，每一個(gè)服務(wù)器的狀態(tài)機(jī)按照日志順序處理他們，就會(huì)輸出結(jié)果返回給客戶端。因此，服務(wù)器集群就形成了一個(gè)高可靠的狀態(tài)機(jī)。也就是說，狀態(tài)機(jī)復(fù)制的內(nèi)部實(shí)現(xiàn)是通過一致性協(xié)議來保證各個(gè)節(jié)點(diǎn)達(dá)成一致的執(zhí)行順序。

在分布式領(lǐng)域?yàn)榱私鉀Q數(shù)據(jù)的一致性問題，已經(jīng)有很多研究者提出了不同的一致性協(xié)議，其中比較有代表性的有二階段提交、三階段提交、Paxos協(xié)議以及Raft協(xié)議。Google分布式一致性庫Chubby的作者曾總結(jié)到，所有的分布式一致性算法都是Paxos協(xié)議的一個(gè)不完備版本。近些年來提出的分布式一致性算法如ZAB協(xié)議、Raft協(xié)議等都是在Multi-Paxos的思想上加以改進(jìn)的。這個(gè)觀點(diǎn)強(qiáng)調(diào)了Paxos協(xié)議在分布式一致性協(xié)議中的重要地位。因此，針對(duì)Paxos協(xié)議的改進(jìn)算法也有很多。

其中，研究如何解決領(lǐng)導(dǎo)者節(jié)點(diǎn)為中心的協(xié)議的節(jié)點(diǎn)瓶頸問題是近幾年對(duì)Paxos的研究比較熱門的方向之一。在以領(lǐng)導(dǎo)者為中心的分布式一致性協(xié)議中，如Multi-Paxos協(xié)議、Raft協(xié)議、ZAB協(xié)議等，領(lǐng)導(dǎo)者節(jié)點(diǎn)的資源消耗明顯大于普通節(jié)點(diǎn)。當(dāng)負(fù)載提高時(shí)，領(lǐng)導(dǎo)者節(jié)點(diǎn)最先消耗完節(jié)點(diǎn)資源成為系統(tǒng)瓶頸。針對(duì)這一問題，很多研究者提出了不同的優(yōu)化方案：

a)Mencius Mencius為了避免領(lǐng)導(dǎo)者節(jié)點(diǎn)成為瓶頸，使用了一種輪轉(zhuǎn)Leader的機(jī)制。這樣可以實(shí)現(xiàn)負(fù)載在所有節(jié)點(diǎn)上的有效均衡，但是Mencius的一個(gè)明顯缺點(diǎn)是：容錯(cuò)性很差，任意節(jié)點(diǎn)出現(xiàn)故障，都會(huì)使系統(tǒng)無法對(duì)外提供服務(wù)。