《去中心化架构系统中的分布式事务机制研究.pdf》由会员分享，可在线阅读，更多相关《去中心化架构系统中的分布式事务机制研究.pdf（77页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 分 类 号 学 号 M201072348 学校代码 10487 密 级 硕士学位论文 去中心化架构 系统 中的分布式事务机制研究 学位申请人 ： 朱陈云海 学科专业 ： 计算机软件与理论 指导教师 ： 胡侃 副教授 答辩日期 ： 2013 年 1 月 30 日 A Thesis Submitted in Partial Fulfillment of the Requirements for the Degree of Master of Engineering Research of Distributed Transaction in Decentralized Architecture
2、Systems Candidate ： Chenyunhai Zhu Major ： Computer Software and Theory Supervisor ： Assoc. Prof. Kan Hu Huazhong University of Science and Technology Wuhan 430074, P.R.China January, 2013 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已
3、在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密 ，在 _年解密后适用本授权书。 不保密。 （请在以上方框内打“”） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日本论文属于 华中科技大学硕士学位论 文 I
4、摘 要 去中心化 NoSQL 系统 的数据存储服务具有 高可扩展和高可用的 特点 ， 且 无单点故障，无主节点性能瓶颈等 问题 。 但是 ， 此类系统 在数据一致性方面仅 提供 了 最终一致性 保障 ， 应用的强一致性需求则由开发者在应用设计 时 自行保证， 从而 增加了应用开发的复杂性。 因此 有必要在 NoSQL 中提供事务 的 ACID 特性 ， 既 保留 NoSQL 杰出 的 系统特性 ， 又可 利用事务机制 自动 解决 开发者需要在应用层维护一致性的问题。传统的分布式事务两阶段提交 协议存在着可用性和性能的问题，目前的研究着重于利用 Paxos 协议 优秀的容错能力， 基于 Paxo
5、s 完成两阶段提交。 在 Paxos 协议 的基础上 ， 设计并实现 了可配置的去中心化事务性 NoSQL 系统DTCassandra。 该系统 能保证 写事务 的 ACID 特性 ， 并提供了一致读、快照读 以及 不一致读 三种级别的读操作。 提出并在 DTCassandra 中实现 了一种可配置的一致读写算法 ,通过使用多种类型的副本，分离了读写操作，以此为基础可以 配置 不同 数量 的读写 副本 ； 使用日志作为载体，对各副本上的操作进行同步，实现了不同类型副本的副本日志 ，提供了分布式状态机的基础 ；最后， 针对 负责写入的副本，使用 Paxos维护 其日志的一致性，针对 负责读取的副
6、本，使用 NWR 法定人数协议来保证强一致性，并且提供可配置的读写可用性 。 采用 基于 Key 的范围进行 数据 分区 的方法 ，在各分区内利用 MVCC 机制 ， 提供 了 局部写事务的 ACID 特性 。改进了两阶段提交协议，将 跨分区的全局事务划分为多个子事务， 以 其中 的主要 子事务作为 控制 整个全局事务的提交 点 ， 提供了在失效发生时保证全局一致性的能力 。 针对 4KB 大小的数据进行了 读写 测试。 测试结果 表明 ， DTCassandra 一致读 操作的 最大 吞吐量 较之 Cassandra 本身提供的法定人数读操作 提高了 50%， 局部写事务的最大 吞吐量 较之
7、法定人数写操作 降低了 60%。 系统 扩展了 Cassandra，能保证 ACID语义，具有高可用性 。 关键字： Paxos，分布式存储系统， 分布式事务， 副本，去中心化架构 华中科技大学硕士学位论 文 II Abstract A decentralized NoSQL system provides highly scalable and available services with no single point of failure or bottleneck of a master node. Yet this kind of system only guarantees ev
8、entual consistency and the strong consistency should be guaranteed by the designer during the application design, which complicates application development. So its necessary to add ACID semantics to NoSQL, which not only retains NoSQLs outstanding system features, but also help developer avoid maint
9、aining consistency in application layer taking advantage of the transaction mechanism. Traditional distributed transactions two phase commit protocol has availability and performance issues. Present studies put emphasis on accomplishing the two phase commitment based on Paxos. A configurable decentr
10、alized transactional NoSQL called DTCassandra is designed and implemented using Paxos protocol. This system provides the ACID semantics of write transactions and reads with three consistency levels including current, snapshot and inconsistent read. A configurable consistent read and write algorithm
11、is presented and implemented which has the following features: First it uses multi-type replicas to separate read and write operation so that different quantities of replicas could be configured; Second it uses log to synchronize write operations across replicas and replicated log for different type
12、 of replica is built to implement distributed state machine; Third, it uses Paxos protocol to maintain consensus for witness replicas and NWR quorum protocol for readable replicas to provide configurable read and write availability with strong consistency. Making use of data partitioning based on ke
13、y range and MVCC mechanism in each partition, fully serializable ACID semantics is provided for local write transactions. 2PC has been improved that global transaction across partitions is divided into multiple sub transactions and a primary sub transaction is used as the synchronous point, which gu
14、arantees consistency when node failure happens. 4KB data is used as test data for all tests. The results shows that the throughput of current read is 50% higher than Cassandra quorum read while the throughput of local write transaction is 60% lower than Cassandra quorum write. ACID semantics could b
15、e guaranteed by extending Cassandra. High availability is also provided. Key words: Paxos, Distributed Storage System, Distributed Transaction, Replication, Decentralized Architecture 华中科技大学硕士学位论 文 III 目 录 摘 要 . I Abstract . II 1 绪 论 1.1 研究背景和问题提出 . (1) 1.2 国内外研究现状 . (3) 1.3 课题背景与研究内容 . (5) 1.4 文章框架
16、结构 . (6) 2 去中心化分布式事务处理系统 DTCassandra 的架构与设计 2.1 系统概述 . (8) 2.2 体系结构与功能模块 . (10) 2.3 工作机制与处理流程 . (14) 2.4 设计思路与技术路线 . (16) 2.5 关键问题与难点分析 . (19) 2.6 小结 . (21) 3 去中心化分布式事务处理系统 DTCassandra 的关键技术 3.1 一致读写算法 . (22) 3.2 多类型副本的定位与管理 . (30) 3.3 副本日志的实现与维 护 . (33) 3.4 失效检测和处理 . (38) 3.5 Paxos 算法的实现 . (40) 3.6
17、 代理节点主要功能 . (44) 3.7 小结 . (49) 4 系统测试与分析 4.1 测试环境 . (51) 4.2 功能测试 . (52) 4.3 性能测试 . (55) 4.4 可用性测试 . (59) 4.5 小结 . (60) 华中科技大学硕士学位论 文 IV 5 总结与展望 . (62) 致 谢 . (64) 参考文献 . (66) 附录 1 攻读学位期间参加的主要科研项目 . (70) 附录 2 攻读学位期间申请的国家发明专利目录 . (70) 华中科技大学硕士学位论 文 1 1 绪 论 本章首先 对 NoSQL 的发展 以及不同架构的优缺点作介绍，并简要说明事务特性为分布式数
18、据存储系统带来的好处，同时指出在去中心化架构系统上加入事务特性时带来的新的问题。 接下来针对相关 国内外研究概况进行了介绍， 接着说明本课题的研究背景和主要研究内容。最后对文章框架组织结构进行描述。 1.1 研究背景 和 问题提出 随着互联网的快速发展， 呈指数增长的在线业务不断考验着现有基础设施的能力极限 1。 首先引起 研究者和开发者关注的就是可扩展性。 虽然我们可以使用MySQL2作为数据存储快速 地 开发网络服务， 在面对扩展性需求时，其对应的解决方法是 分片（ Sharding） ， 但是 当 服务 扩展 到上百万的用户 时 MySQL 则 开始 捉襟见肘 ，其原因是 分片 常常是一
19、个手工的过程，难以进行管理和负载平衡 ，例如曾经Google 的 F17，这是 Google 的广告后台，在许多方面采取手工数据分片，但是随着客户数量的增长，分片的代价越来越大，最近一次的重新分片，花费了两年的时间 8。因而 众多 NoSQL 数据存储系统 作为处理大数据的解决方案应运 而生， 例如 Google的 Bigtable3， Apache Hadoop 的 HBase4， Amazon 的 Dynamo6， 还有 Facebook 的Cassandra5， 这些解决方案 都获得了成功。 然而当今网络服务的存储不仅仅需要满足可扩展性，实际上其需求是彼此冲突的：既需要满足可扩展性以满足
20、不断增长的用户，又 需要快速的 开发 改进，还需要低延迟的读写操作 和高可用性以满足用户需要 ， 甚至还要保证数据的一致性。 NoSQL的优势在于其高可扩展性，高可用性， 高读写性能以及易于管理，但是这些 NoSQL系统的缺点在于 API 过于简单， 一致性模型过于松散，这些都使得应用的开发更加复杂，许多工作转移到了不够高效的应用层 。 部分原因也是由于副本机制的引入 ，副本机制提供了高可用性，却提高了保证一致性的难度。 在众多的 NoSQL 分布式存储系统 中，其架构大致分为两种， 一个是 主从 架构，一个是去中心化架构。 两种架构的 分布式存储系统的 共同特点是 ：高可扩展性，高可用性，将
21、节点的失效考虑为系统运行过程中的常态， 但是 由于架构的不同，它们 华中科技大学硕士学位论 文 2 的系统特点 的侧重也 各不相同 。 主从 架构方面，以 Google 的 Bigtable3为代表， 辅以作为 Google 众多系统基石的 Chubby9和 Google File System10， 在 开源 项目领域则以 Apache Hadoop 的 HBase4为代表 ，辅以 Zookeeper11和 HDFS12。 主从架构的系统特点是 使用了主节点对整个系统进行管理， 于是系统可以方便地达到数据的强一致性， 应用开发者也能够 快速地 进行开发， 同时，只要主节点 的能力 允许，系统
22、就可以达到很大的规模 。这个系列的分布式存储系统都无法单独运作，而是依赖于一些提供了其他功能 支持 的系统，例如 HBase 依赖于 ZooKeeper 和 HDFS， 这样做的好处是 通过模块化的设计，将系统功能的界限划分的很清晰，于是 HBase 就可以专注于数据存储部分的设计与实现。但是这样做的 问题在于主节点的使用要非常具有技巧性， 主节点的功能要尽量精简以减少负载， 否则很容易 成为瓶颈所在， 相应的， 客户端 往往 承担了 一些其他的功能 。 此外， 主节点的可用性则决定着系统的可用性。 去中心化架构方面，以 Amazon 的 Dynamo6为代表 ， 在开源项目领域则以Cassa
23、ndra5为代表 。 去中心化架构 的系统特点是所有的节点都是平等的，所以任何操作都不需要主节点，所有的节点都可以对外处理读写请求，这避免了单点故障，规避了主节点的性能瓶颈，提高了系统的可用性。 去中心化架构的系统往往使用 一致性哈希 13作为数据的分布策略，例如 Cassandra 中，于是每个节点对应着一个 Token，所有的节点构成了一个环，某条数据总是落在两个 Token 间 的那个节点上， 使用分布式哈希表的好处是可以方便 对数据进行分区和 扩展系统 ，因为一个节点的加入或离开只会影响这个节点的直接前驱和后继节点 。 NoSQL 系统的高可扩展性以及高可用性满足了众多网络应用的存储需
24、求， 然而，NoSQL 系统中传统数据库特性的缺失也收到了关注。 Google 在实现了底层的 NoSQL存储后， 就开始在高可扩展的 NoSQL 基础上加入传统数据 库 的高级特性， 如细粒度锁，事务，触发器等等 14。可见，在解决了大规模数据的存储之后， NoSQL 与传统数据库特性的结合也是大势所趋。 事务机制便是其中最为重要的 数据库特性。 在分布式系统中， 分布式事务除了能够满足 事务中多个操作 的原子性操作需求，而且还能够成为更高级的功能的基础，例如在 Google 的 Percolator 系统中的 消息通知 机制 14，还有在 HP 基于 Sinfonia 的minitrans
25、action 实现的 分布式锁管理器和 分布式 B-tree15等等，因此，分布式事务成为 了 NoSQL 进一步 扩展功能时 首先被考虑的特性 。 华中科技大学硕士学位论 文 3 Cassandra 系统是优秀的开源去中心化架构系统，它使用面向列族的存储模型以获得高读写性能，使用去中心化架构以避免单点故障，使用一致性哈希获得高可扩展性， 使用副本机制获得高可用性和持久性， 加上灵活模式的设计，基于 Key 的查询，构成了一个能够处理大规模数据存储的系统 。 当在这样的去中心化架 构系统上加入事务特性时，带来了 更多的问题。 首先，事务机制要求事务内部的各操作也是一致的。然而，对于 Cassa
26、ndra 这样的最终一致性系统来说，其副本之间 的 一致性是使用 last write wins 的简单策略 来完成的， 其时间戳 的设置是在 客户端 进行的 ，因而在 多客户端的 环境下，很难保证写操作的强一致性 。 第二 ， 传统的用于分布式事务的两阶段提交协议（ 2PC） 是昂贵的方法。 两阶段提交依赖于锁机制，此外， 它需要稳定的协调者来同步整个事务提交过程，当协调者出现失效时， 就可能因为锁没有释放而导致之后的操作被 阻塞 住 ，最重要的，两阶段提交需要一个主节点来处理同步：或者是作为协调者的主节点， 来协调系统中的所有事务，实现可序列化的 ACID 语义，或者是一个唯一的时间戳同步
27、器，来实现基于时间戳的快照隔离的 ACID 语义 。 这在去中心化架构的系统上难以完成。 第三， NoSQL 中都将节点失效考虑为一种常态，而事务则不是，事务中的任何一个操作失败都将导致整个事务的中止。因此，事务中的操作在保证强一致性的同时，还要提供一定的容错能力，才能适用于 NoSQL 环境。 1.2 国内外研究现状 本文在上节中介绍了 NoSQL 数据存储系统 的优势和缺点，又介绍了不同架构的NoSQL 系统的特点 ，最后说明了在去中心化架构系统中加入事务特性会遇到的问题 ：副本一致性问题、分布式事务的实现问题以及事务容错问题 。 针对 这些问题，需要对 去中 心化架构的 Cassandr
28、a 系统 有相应了解，此外，也需要对 其他 NoSQL 系统 ，如何维护多机一致性，以及 现有 NoSQL 系统如何实现事务特性有相关了解，下面就国内 外的研究现状进行说明和分析。 1.2.1 NoSQL 系统 研究概况 在分布式系统中，一致性模型描述了副本如何被同步，强一致性保证了所有的副本保证处于相同的状态。然而，一 致性 、 可用性 和 网络分区容忍性 至多只能保证 华中科技大学硕士学位论 文 4 其中两点 ，这就是 Brewer 提出的著名的 CAP 原理 29。 NoSQL 一定程度上基于此理论提出， 不同的 NoSQL 基于不同的 CAP 权衡而建立。 著名的 NoSQL 包括 B
29、igTable3，HBase4， Dynamo6， Cassandras5， Yahoo PNUTS23， Redis31， MongoDB30，SimpleDB32等。在这些系统中满足了可扩展性，然而却牺牲了一个或多个 RDBMS系统特性，例如事务，模式支持或者复杂查询能力 2425。 1.2.2 传统的分布式事务研究概况 经典的分布式事务算法是两阶段提交（ 2PC），然而 两段提交有几项缺点，首先 ，任何一个节点的失效都会导致 提交中止，这对希望发生节点失效时依然保证可用性的系统来说是不可接受的，其次，在每次事务中使用两阶段提交会导致很大的开销，因为两阶段提交的实现中每个参与者需要两次强制
30、写磁盘并且总共需要两轮消息延迟，参与者在这个执行期间会被锁住，最后，当两阶段提交中的协调者失效时，会产生阻塞。 于是产生了非阻塞的三阶段提交 33，但是鲜有实际系统使用，因为其性能表现很差。 Gray 和 Lamport 提出了一种非阻塞的基于 Paxos 的提交协议 35，使用Paxos 来维护一个分布式的协调者，增加了协调者的容错性。 1.2.3 NoSQL 中的事务特性研究概况 Megastore1和 DynamoDB26都提供了跨数据中心的一致副本作为其存储服务。DynamoDB 使用了一个键值对的接口，只在一个区域（ region）内进行 数据 复制。Megastore 在细粒度的数
31、据分区中提供了完整的可序列化的 ACID 语义，它使用了Paxos 作为其同步复制的策略，提供了用户定义的模式，数据库风格的全文引用以及数据分区中用来通信的队列。 Spanner8继承了 Megastore 的工作，使用了一个真实时间 API（ TrueTime API）来提供外部一致性以及一系列强大的特性：非阻塞的 读历史数据，无锁的只读事务，以及原子 模式变更。 Percolator14提供了基于 Bigtable 的多行事务，此系统通过为数据列附加额外的列实现了细粒度的单元格锁，并且锁被分为主锁和从锁，主锁被用作事务提交的同步点，以此提供失效恢复的能力，完成了一个两阶段提交的变 体。然而
32、两阶段提交的代价过于昂贵，这会带来可用性和性能的问题 32334， 通过 Paxos 来运行两阶段提交可以弱化可用性的问题。 Spinnaker21是一个运行于一个数据中心中的数据存储系统，此系统使用了基于key 的范围分区，三路副本，提供了一个事务性的 get-put 接口，其读操作可以选择 华中科技大学硕士学位论 文 5 强一致性或时间线一致性。 Spinnaker 使用了基于 Paxos 的副本协议，然而，只有 leader可以提供一致读，其 follower 职能提供时间线一致性，这限制了其使用场景。 将事务建立在副本存储层之上最早可以追溯至 Gifford 的毕业论文 27。 Sca
33、tter28是一个基于分布式哈希表（ DHT）的键值存储，此系统将事务建立在一致复制层之上。 Scatter 采用了 P2P 系统中 高度去中心化、自组织的 结构，提供了可线性化的一致性，并且可以容忍 churn 的发生。 两阶段提交被用于完成事务， Paxos 用于将写前日志（ write-ahead log）写入磁盘 。 Scalaris36是基于结构化 P2P 覆盖网 chord#3738的一个分布式键值存储， 使用了对称副本策略， 利用一个改 进的 Paxos 原子提交协议 39提供了一致的写操作。 Sinfonia15 是 HP 实现的一个可扩展的分布式系统，其核心是特殊的minit
34、ransaction 语义。此系统的分布式事务被分为三种操作：比较，读，写，以及两个阶段：第一阶段上锁，比较，读，以及缓存写操作，第二阶段提交或终止。与一般的分布式事务不同，使用 minitransaction 需要手动指定三种操作。这个系统的架构将储存和应用节点分离，以此达到控制和容错。 22在 Megastore 串行化事务实现方案的基础上，通过将并发事务之间的读写冲突 检测提前，减少了由于 Paxos 使用的乐观并发导致的冲突事务回滚引发的额外消耗，提出了基于读写集对比的事务强快照隔离和强提交读隔离方案。 40研究了 P-Ring 环境下的分布式事务，提出了一种 MVCC 算法 LSTP
35、。文章注重于读繁忙的环境，只读事务不会中止和阻塞，但是不适合写繁忙环境。 41研究了 P2P 数据库网络中的事务处理机制，主要针对无全局协调器的 P2P环境，研究了如何维护各独立自治的节点数据库上的并行事务的一致性执行。提出了一个事务正确性标准和两个方法。不过这些工作都是基于数据共享的环境，而不是副本环境。 1.3 课题背景与 研究 内容 本文来源于国家科技支撑计划“协同式多语言云翻译服务平台与应用”中的课题二 ： 翻 译 业 务 云 计 算 基 础 架 构 和 海 量 数 据 处 理 系 统 研 发 。 课 题 编 号No.2012BAH114F02。 针对课题的研究内容和现有的研究现状，本
36、文提出了一系列的解决方案及相关的 华中科技大学硕士学位论 文 6 原型系统 基于 Cassandra 的分布式事务处理系统 DTCassandra。 该系统在保持着NoSQL 的高可扩展性、高可用性的基础上， 实现副本一致性以及分布式事务的全局一致性 ，提供了 事务级 写 操作 的接口以及多种一致性级别的读操作接口。 本课题的具体研究内容包括以下几 点 ： （ 1） 去中心化架构 系统 中 副本 组内的 事务机制 研究。 在去中心化架构的系统中，没有主控节点，所有的节点都是对等的， 副本也是一样，当事务中的操作执行在一组副本中时，也要保证 ACID 的特性， 如何在一组副本内维护 事务的 AC
37、ID 特性是本课题的重点研究内容。 （ 2） 去中心化架构系统中 全局事务 机制 研究 。 在去中心化架构的系统中， 难以实现一个全局的 协调者， 否则就会形成性能瓶颈和单点故障 ， 因此传统的两阶段提交协议 无法应用于这样的场景，如何在这样的系统中实现全局的 ACID 特性也是本课题的研究内容。 （ 3） 多种类型的 副本 机制 研究。 在简单的读写 操作环境中 ， 单一类型的副本就可以满足需求，当引入了事务机制之后，写操作和读操作虽然都会涉及副本，但是它们需要的副本功能往往不同， 在这样的前提下， 如何划分不同类型副本的功能以及如何使用这些副本也是本课题的研究内容。 （ 4） 节点失效处理
38、机制研究。 在 NoSQL 中，节点失效被考虑为经常出现的状况，当引入事务机制之后，这样的考虑也不应该改变，如何 进行事务处理过程中的节点失效处理，以及如何应对去中心化架构中特有的节点失效场景也是本课题的研究内容 。 1.4 文章框架结构 下面介绍文章后续各章节的内容框架结构。 第二章的主要内容为架构与设计。 首先进行 DTCassandra 的系统概述，然后介绍 DTCassandra 系统的整体设计思路，接着对 DTCassandra 系统的体系结构和相关模块进行了说明。然后对 DTCassandra 的工作机制和主要工作流程进行说明， 接着分模块讨论了 整个系统的关键技术与难点所在。 第
39、三章的主要内容为主要实现技术。 首先针对 DTCassandra 中使用的一致性 算法进行了分析和介绍，并将其与现有相似算法进行比较。然后 分模块介绍了各模块 华中科技大学硕士学位论 文 7 中 原理和 主要实现技术。 第四章的主要内容为系统测试与分析。首先介绍测试环境，对测试环境的配置进行详细说明。 其次 介绍功能测试，针对 DTCassandra 的基本功能进行 测试。 然后介绍性能测试， 针对 局部写事务和一致读进行微基准测试 和 吞吐量 测试 ，对全局写事务进行吞吐量测试 。 最后介绍可用性测试，测试了节点失效的场景。 第五章的主要内容为总结与展望。对现有的工作做相应的总结，针对需要扩
40、展的功能的展望及可优化部分的说明。 最后是致谢和参考文献以及攻读学位期间主要参加的科研项目和申请的 发明专利信息 。 华中科技大学硕士学位论 文 8 2 去中心化分布式事务处理系统 DTCassandra的架构与设计 本章首先对基于 Cassandra 的分布式事务处理系统 DTCassandra 做简单的整体 概述 ， 再描述该系统的整体 架构 和功能模块，并对每个模块的组成和功能进行详细的说明，接着描述了系统的 主要 工作流程，然后 说明该系统的设计思路 ， 并 对系统实现的关键 算法和机制 进行分析，最后是对本章的总结。 2.1 系统概述 Cassandra 系统是一个用于管理分布在大量商业服务器上非常