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

摘  要
　　　互聯(lián)網(wǎng)已進入全面參與的 Web 2.0 時代，伴隨而來的是用戶量和數(shù)據(jù)量的爆炸式增長。傳統(tǒng)關系型數(shù)據(jù)庫在應付 Web 2.0 網(wǎng)站，特別是超大規(guī)模和高并發(fā)的社交型網(wǎng)站已經(jīng)顯得力不從心，暴露出很多難以克服的問題。NoSQL 數(shù)據(jù)庫放棄了關系型數(shù)據(jù)庫中的關系模型，通過去除數(shù)據(jù)之間的耦合使數(shù)據(jù)庫更為適應現(xiàn)代高性能服務架構，從而達到存儲系統(tǒng)的高性能。另外，傳統(tǒng)的集中式存儲無法滿足海量數(shù)據(jù)的需要，為保證高可用性、高可靠性和經(jīng)濟性，越來越多互聯(lián)網(wǎng)企業(yè)采用分布式存儲的方式來存儲數(shù)據(jù)，采用冗余存儲的方式保證數(shù)據(jù)的可靠性。
　　　本文在研究 Key-Value 存儲儲系統(tǒng)的基礎上，著重研究分布式系統(tǒng)下的數(shù)據(jù)一致性機制，一致性機制是保證分布式存儲系統(tǒng)能夠正常提供服務的基礎，在某些特定的業(yè)務場景中有著苛刻的要求。著名的分布式 Paxos 算法解決的是分布式系統(tǒng)一致性問題，本文在該算法的基礎上，提出并實現(xiàn)了多輪 Paxos 算法，以及領導選舉算法，從而保證分布式存儲系統(tǒng)的一致性。
　　　本系統(tǒng)在單機存儲上使用 Berkeley DB 作為底層存儲引擎，在此基礎上，通過實現(xiàn)節(jié)點管理、節(jié)點通信、冗余備份和一致性算法，解決了分布式系統(tǒng)中數(shù)據(jù)一致性性等難點問題，最終實現(xiàn)了一套分布式 Key-Value 存儲系統(tǒng)。
　　　相比于普通的 Key-Value 數(shù)據(jù)庫，本文提出的數(shù)據(jù)庫具有分布式特點，各個節(jié)點共同組成一個分布式分布式網(wǎng)絡存儲服務，能夠保證數(shù)據(jù)的強一致性，具有極高的錯誤容忍能力，而且系統(tǒng)自帶節(jié)點管理功能，方便擴展性能，進行高密度地部署。
　　
　　
關鍵詞：NoSQL；Key-Value存儲；分布式系統(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 相關領域的研究現(xiàn)狀 2
1.3 論文組織結構 3
第2章 NoSQL存儲系統(tǒng)的研究 3
2.1 關系型數(shù)據(jù)庫的缺陷 3
2.2 NoSQL簡介 5
2.3 Key-Value存儲系統(tǒng)的優(yōu)勢和不足 7
2.3.1 Key-Value數(shù)據(jù)庫的優(yōu)勢 7
2.3.2 Key-Value數(shù)據(jù)庫的不足 7
2.4 如何使用Key-Value數(shù)據(jù)庫 8
2.4.1 Key-Value數(shù)據(jù)庫的設計方法 8
2.4.2 Key-Value數(shù)據(jù)庫與關系型數(shù)據(jù)庫的配合使用 10
2.4.3 Key-Value緩存的使用 11
2.5 國內外 NoSQL 數(shù)據(jù)庫的研究和分析 12
2.5.1 滿足極高讀寫性能需求的Key-Value數(shù)據(jù)庫 12
2.5.2 滿足海量存儲需求和訪問的面向文檔的數(shù)據(jù)庫 13
2.5.3 滿足高可擴展性和可用性的面向分布式計算的數(shù)據(jù)庫 13
2.5.4 面向圖存儲的數(shù)據(jù)庫 14
本章小結 14
第3章 分布式系統(tǒng)的復制技術 15
3.1 復制的目的 15
3.2 復制的上下文 16
3.3 復制的模型 17
3.4 分布式系統(tǒng)的復制 19
3.4.1 主動復制 20
3.4.2 被動復制 21
3.4.3 半主動復制 22
3.4.4 半被動復制 22
3.5 數(shù)據(jù)庫的復制 23
3.6 復制的策略 23
3.6.1  Eager Primary復制 24
3.6.2  Eager Update Everywherre復制 25
3.6.3  基于原子性組播的復制 26
3.6.4  懶惰式復制 27
本章小結 27
第4章 分布式系統(tǒng)的一致性研究 28
4.1 一致性模型 28
4.1.1 強一致性模型 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 復制的寫協(xié)議 36
本章小結 36
第5章 分布式一致性算法的研究和實現(xiàn) 38
5.1 系統(tǒng)架構 38
5.2 基于Paxos的一致性算法 39
5.2.1 Paxos算法解決的問題 39
5.2.2 Paxos算法的理論 40
5.2.3 Paxos算法的內容 42
5.2.4 Paxos算法的實現(xiàn) 44
5.3 系統(tǒng)的性能分析 49
本章小結 51
第6章 總結與展望 52
6.1 總結 52
6.2 展望 52
參考文獻 52
致謝 56