分布式Key-Value數(shù)據(jù)庫(kù)及其一致性研究

摘  要
　　　互聯(lián)網(wǎng)已進(jìn)入全面參與的 Web 2.0 時(shí)代，伴隨而來(lái)的是用戶量和數(shù)據(jù)量的爆炸式增長(zhǎng)。傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)在應(yīng)付 Web 2.0 網(wǎng)站，特別是超大規(guī)模和高并發(fā)的社交型網(wǎng)站已經(jīng)顯得力不從心，暴露出很多難以克服的問(wèn)題。NoSQL 數(shù)據(jù)庫(kù)放棄了關(guān)系型數(shù)據(jù)庫(kù)中的關(guān)系模型，通過(guò)去除數(shù)據(jù)之間的耦合使數(shù)據(jù)庫(kù)更為適應(yīng)現(xiàn)代高性能服務(wù)架構(gòu)，從而達(dá)到存儲(chǔ)系統(tǒng)的高性能。另外，傳統(tǒng)的集中式存儲(chǔ)無(wú)法滿足海量數(shù)據(jù)的需要，為保證高可用性、高可靠性和經(jīng)濟(jì)性，越來(lái)越多互聯(lián)網(wǎng)企業(yè)采用分布式存儲(chǔ)的方式來(lái)存儲(chǔ)數(shù)據(jù)，采用冗余存儲(chǔ)的方式保證數(shù)據(jù)的可靠性。
　　　本文在研究 Key-Value 存儲(chǔ)儲(chǔ)系統(tǒng)的基礎(chǔ)上，著重研究分布式系統(tǒng)下的數(shù)據(jù)一致性機(jī)制，一致性機(jī)制是保證分布式存儲(chǔ)系統(tǒng)能夠正常提供服務(wù)的基礎(chǔ)，在某些特定的業(yè)務(wù)場(chǎng)景中有著苛刻的要求。著名的分布式 Paxos 算法解決的是分布式系統(tǒng)一致性問(wèn)題，本文在該算法的基礎(chǔ)上，提出并實(shí)現(xiàn)了多輪 Paxos 算法，以及領(lǐng)導(dǎo)選舉算法，從而保證分布式存儲(chǔ)系統(tǒng)的一致性。
　　　本系統(tǒng)在單機(jī)存儲(chǔ)上使用 Berkeley DB 作為底層存儲(chǔ)引擎，在此基礎(chǔ)上，通過(guò)實(shí)現(xiàn)節(jié)點(diǎn)管理、節(jié)點(diǎn)通信、冗余備份和一致性算法，解決了分布式系統(tǒng)中數(shù)據(jù)一致性性等難點(diǎn)問(wèn)題，最終實(shí)現(xiàn)了一套分布式 Key-Value 存儲(chǔ)系統(tǒng)。
　　　相比于普通的 Key-Value 數(shù)據(jù)庫(kù)，本文提出的數(shù)據(jù)庫(kù)具有分布式特點(diǎn)，各個(gè)節(jié)點(diǎn)共同組成一個(gè)分布式分布式網(wǎng)絡(luò)存儲(chǔ)服務(wù)，能夠保證數(shù)據(jù)的強(qiáng)一致性，具有極高的錯(cuò)誤容忍能力，而且系統(tǒng)自帶節(jié)點(diǎn)管理功能，方便擴(kuò)展性能，進(jìn)行高密度地部署。
　　
　　
關(guān)鍵詞：NoSQL；Key-Value存儲(chǔ)；分布式系統(tǒng)；一致性；Paxos算法

ABSTRACT
　　The Internet has come into the web2.0 era which brings the explosive growth of user and data. It has been hard for traditional relational-database to deal with Web2.0 website especially large scale SNS website. NoSQL database is more comfortable for the modern architecture of high-performance service, because it removes the data-structured coupling, which improves the efficiency of data store. On the other hand, traditional centralized data store can't satisfy the requirements of big data. In order to gain high availability, high reliability and economical benefit，more and more internet enterprises take  distributed database as their data store, which ensures its reliability by replication.
　　This article studies distributed database and the consistency of distributed system. The key problem of distributed system is maintaining the consistency of data, which is very strict in some cases. A lot of algorithm is introduced to solve this problem and the Paxos algorithm is considered to the most effective approach in dealing with consistency. This article use multi-paxos algorithm which is based on Paxos to solve the consensus of distributed data store.
　　This article builds a distributed key-value database. We use Berkeley DB as its local store engine. By implementing node communication, replication and consistency mechanism, we solve the main problem of distributed system, such as consistency, availability, redundancy and fault tolerant.
　　Compared to ordinary key-value database, this key-value data store is a distributed system, all node make up a distributed network store service, ensuring the strong consensus of data and provides high-availability, high-reliability, scalability and fault-tolerant for data store.  
Key words: NoSQL; Key-Value Store; Distributed System; Consensus; Paxos Algorithm

目  錄
摘  要 I
ABSTRACT II
第1章 緒論 1
1.1 課題的研究目的和意義 1
1.2 相關(guān)領(lǐng)域的研究現(xiàn)狀 2
1.3 論文組織結(jié)構(gòu) 3
第2章 NoSQL存儲(chǔ)系統(tǒng)的研究 3
2.1 關(guān)系型數(shù)據(jù)庫(kù)的缺陷 3
2.2 NoSQL簡(jiǎn)介 5
2.3 Key-Value存儲(chǔ)系統(tǒng)的優(yōu)勢(shì)和不足 7
2.3.1 Key-Value數(shù)據(jù)庫(kù)的優(yōu)勢(shì) 7
2.3.2 Key-Value數(shù)據(jù)庫(kù)的不足 7
2.4 如何使用Key-Value數(shù)據(jù)庫(kù) 8
2.4.1 Key-Value數(shù)據(jù)庫(kù)的設(shè)計(jì)方法 8
2.4.2 Key-Value數(shù)據(jù)庫(kù)與關(guān)系型數(shù)據(jù)庫(kù)的配合使用 10
2.4.3 Key-Value緩存的使用 11
2.5 國(guó)內(nèi)外 NoSQL 數(shù)據(jù)庫(kù)的研究和分析 12
2.5.1 滿足極高讀寫性能需求的Key-Value數(shù)據(jù)庫(kù) 12
2.5.2 滿足海量存儲(chǔ)需求和訪問(wèn)的面向文檔的數(shù)據(jù)庫(kù) 13
2.5.3 滿足高可擴(kuò)展性和可用性的面向分布式計(jì)算的數(shù)據(jù)庫(kù) 13
2.5.4 面向圖存儲(chǔ)的數(shù)據(jù)庫(kù) 14
本章小結(jié) 14
第3章 分布式系統(tǒng)的復(fù)制技術(shù) 15
3.1 復(fù)制的目的 15
3.2 復(fù)制的上下文 16
3.3 復(fù)制的模型 17
3.4 分布式系統(tǒng)的復(fù)制 19
3.4.1 主動(dòng)復(fù)制 20
3.4.2 被動(dòng)復(fù)制 21
3.4.3 半主動(dòng)復(fù)制 22
3.4.4 半被動(dòng)復(fù)制 22
3.5 數(shù)據(jù)庫(kù)的復(fù)制 23
3.6 復(fù)制的策略 23
3.6.1  Eager Primary復(fù)制 24
3.6.2  Eager Update Everywherre復(fù)制 25
3.6.3  基于原子性組播的復(fù)制 26
3.6.4  懶惰式復(fù)制 27
本章小結(jié) 27
第4章 分布式系統(tǒng)的一致性研究 28
4.1 一致性模型 28
4.1.1 強(qiáng)一致性模型 29
4.1.2 順序一致性模型 29
4.1.3 因果一致性模型 30
4.1.4 FIFO一致性模型 31
4.1.5 最終一致性 32
4.2 一致性協(xié)議 33
4.2.1 基于主備份的協(xié)議 33
4.2.2 復(fù)制的寫協(xié)議 36
本章小結(jié) 36
第5章 分布式一致性算法的研究和實(shí)現(xiàn) 38
5.1 系統(tǒng)架構(gòu) 38
5.2 基于Paxos的一致性算法 39
5.2.1 Paxos算法解決的問(wèn)題 39
5.2.2 Paxos算法的理論 40
5.2.3 Paxos算法的內(nèi)容 42
5.2.4 Paxos算法的實(shí)現(xiàn) 44
5.3 系統(tǒng)的性能分析 49
本章小結(jié) 51
第6章 總結(jié)與展望 52
6.1 總結(jié) 52
6.2 展望 52
參考文獻(xiàn) 52
致謝 56