分布式key-value数据库及其一致性研究.doc

分布式Key-Value数据库及其一致性研究

摘  要
　　　互联网已进入全面参与的 Web 2.0 时代，伴随而来的是用户量和数据量的爆炸式增长。传统关系型数据库在应付 Web 2.0 网站，特别是超大规模和高并发的社交型网站已经显得力不从心，暴露出很多难以克服的问题。NoSQL 数据库放弃了关系型数据库中的关系模型，通过去除数据之间的耦合使数据库更为适应现代高性能服务架构，从而达到存储系统的高性能。另外，传统的集中式存储无法满足海量数据的需要，为保证高可用性、高可靠性和经济性，越来越多互联网企业采用分布式存储的方式来存储数据，采用冗余存储的方式保证数据的可靠性。
　　　本文在研究 Key-Value 存储储系统的基础上，着重研究分布式系统下的数据一致性机制，一致性机制是保证分布式存储系统能够正常提供服务的基础，在某些特定的业务场景中有着苛刻的要求。著名的分布式 Paxos 算法解决的是分布式系统一致性问题，本文在该算法的基础上，提出并实现了多轮 Paxos 算法，以及领导选举算法，从而保证分布式存储系统的一致性。
　　　本系统在单机存储上使用 Berkeley DB 作为底层存储引擎，在此基础上，通过实现节点管理、节点通信、冗余备份和一致性算法，解决了分布式系统中数据一致性性等难点问题，最终实现了一套分布式 Key-Value 存储系统。
　　　相比于普通的 Key-Value 数据库，本文提出的数据库具有分布式特点，各个节点共同组成一个分布式分布式网络存储服务，能够保证数据的强一致性，具有极高的错误容忍能力，而且系统自带节点管理功能，方便扩展性能，进行高密度地部署。
　　
　　
关键词：NoSQL；Key-Value存储；分布式系统；一致性；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 相关领域的研究现状 2
1.3 论文组织结构 3
第2章 NoSQL存储系统的研究 3
2.1 关系型数据库的缺陷 3
2.2 NoSQL简介 5
2.3 Key-Value存储系统的优势和不足 7
2.3.1 Key-Value数据库的优势 7
2.3.2 Key-Value数据库的不足 7
2.4 如何使用Key-Value数据库 8
2.4.1 Key-Value数据库的设计方法 8
2.4.2 Key-Value数据库与关系型数据库的配合使用 10
2.4.3 Key-Value缓存的使用 11
2.5 国内外 NoSQL 数据库的研究和分析 12
2.5.1 满足极高读写性能需求的Key-Value数据库 12
2.5.2 满足海量存储需求和访问的面向文档的数据库 13
2.5.3 满足高可扩展性和可用性的面向分布式计算的数据库 13
2.5.4 面向图存储的数据库 14
本章小结 14
第3章 分布式系统的复制技术 15
3.1 复制的目的 15
3.2 复制的上下文 16
3.3 复制的模型 17
3.4 分布式系统的复制 19
3.4.1 主动复制 20
3.4.2 被动复制 21
3.4.3 半主动复制 22
3.4.4 半被动复制 22
3.5 数据库的复制 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章 分布式系统的一致性研究 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 一致性协议 33
4.2.1 基于主备份的协议 33
4.2.2 复制的写协议 36
本章小结 36
第5章 分布式一致性算法的研究和实现 38
5.1 系统架构 38
5.2 基于Paxos的一致性算法 39
5.2.1 Paxos算法解决的问题 39
5.2.2 Paxos算法的理论 40
5.2.3 Paxos算法的内容 42
5.2.4 Paxos算法的实现 44
5.3 系统的性能分析 49
本章小结 51
第6章 总结与展望 52
6.1 总结 52
6.2 展望 52
参考文献 52
致谢 56