不妥协：分布式事务的一致性，可用性和性能

本文是论文No compromises: distributed transactions with consistency, availability, and performance的读书笔记，水平有限，未能很好的读懂，惭愧。

本文是mit 6.824 Schedule: Spring 2016的第1课，前面课程内容可以在分布式找到，更多详细资料可以到：distributed-system查看。

概述

如果事务具有强一致、高可用的特性，将大大的简化我们构建分布式应用的难度，但是在之前人们的认知中，分布式事务的设计一直表现的很糟糕，这就迫使在构建分布式系统的时候或者彻底不使用分布式事务，或者使用弱一致性，或者只使用单机事务，应用方通过数据分区来保证事务中的数据都落在一台机器上。

我想我们可以对上面的窘境说88了，在现代数据中心中，我们完全可以同时满足强一致、高可用、高性能。

本文会介绍FaRM（fast remote memory）系统，一个内存分布式计算平台。FaRM提供了如下的事务特性：

• 强序列化
• 高性能
• 数据持久化
• 高性能

在90台机器4.9TB数据的情况下，在高峰时FaRM能达到1.4亿每秒的吞吐量（FaRM achieves a peak throughput of 140 million TATP transactions per second on 90 machines with a 4.9 TB database），并且能够在50ms内进行故障恢复。

而能达到如此性能的关键点是：

• 网络使用RDMA（Remote Direct Memory Access）
• 存储使用non-volatile DRAM

基于以上两个硬件上的改变，设计了全新的事务、数据复制和恢复协议。

介绍

我们希望分布式事务能达到的一个理想状态是：事务“在一台永不故障的机器上，事务的执行都是严格串行的”一样的效果。

但是之前的一些设计都存在缺陷，Dynamo和memcached为了提高性能要么是不支持事务，要么放弃了强一致，只提供弱一致的保证。另外一些设计则只能保证单机事务，跨机器的则无能为力。

本文提出的FaRM平台，通过使用

• 网络使用RDMA
• 存储使用non-volatile DRAM

解决了网络和存储的瓶颈，此时CPU的瓶颈出现了，FaRM在设计上遵循下面3条原则：

• 减少消息数量
• 使用RDMA进行数据的存取而不是消息
• 高效利用并发

FaRM允许数据分布在不同机器上，同时允许跨机器的分布式事务。FaRM通过使用vertical Paxos，而不是通过Paxos协议进行coordinators和数据的复制，此时副本是主-备，然后协调者是单个，不进行复制。FaRM使用4阶段的乐观提交协议（lock, validation, commit backup, and com- mit primary）。

FaRM通过使用RDMA来进一步减少CPU的负载，具体是：

• 在事务执行和验证阶段，通过RDMA进行读
• coordinators通过RDMA将WAL(write-ahead logs)日志写入到副本中

因为使用RDMA不需要CPU参与，因此有效的减少了CPU的使用。

由于servers处理请求时不再需要CPU参与，因此传统的故障恢复（failure-recovery）协议不再适合FaRM，因为传统的租约模式需要server在收到请求后进行判断是否拒绝请求，但是现在请求直接通过网卡处理了，CPU无法干预了。

一个可能的解决方案是：precise membership，保证所有机器都在当前membership configuration上达成一致了，然后只会发送请求给组员。

另一个问题是FaRM不能再依赖于传统的2阶段提交中，prepare阶段需要participants对资源进行锁定，然后在commit阶段进行提交，因为此时servers写logs的时候不再经过CPU了。一个解决方案是：reservations，我们确保在提交之前，我们又足够的空间来存储commit的日志。

在FaRM中故障恢复策略快是因为有效的利用了并行。具体是FaRM将恢复的每个数据都均匀的分布上集群上，然后并行的对每台机器进行恢复。

另外，FaRM通过两点优化使得恢复过程中事务可以并行的执行：

1. 只需等到几十毫秒的lock recovery阶段结束，就可以获取故障中的数据了，而无需花费几秒去等待lock recovery之后的恢复阶段
2. 没有收到失败影响的事务无需等待直接执行

FaRM利用高速网络进行高频的心跳机制，实现了快速的失败探测，同时利用priorities 和 pre-allocation防止误判。

硬件趋势

• Largemain memory
• Non-volatilememory
• Fastnetwork with RDMA

编程模型和架构

Progamming Model

FaRM提供了如上图的一个抽象地址空间，在我们看来所有的数据都在一个全局的地址空间中，通过FaRM提供的API让我们能够透明的访问本地和远端的数据。

• Distributedshared memory abstraction
• FaRM APIprovides transparent access to local and remote objects

FaRM的编程模型总结起来，如下：

1. 应用线程开启一个事务，同时变为协调者（coordinator）
2. 在事务中，可以执行任何的逻辑：如read, write, allocate, and free objects
3. 事务最后，告诉FaRM进行提交

FaRM架构

FaRM Architecture

• 主备用户容错
• 配置管理器（configuration manager）：负责leases，detect failures， coordinate recovery

如何对地址进行寻址

前面提到FaRM将所有内存放到一起进行管理，那具体怎么操作呢？

• 内存以2GB进行划分，每个2GB称为一个region，然后每个region分布在一个primary，f个backup上
• region到primary-backups关系保存在CM上
• 应用可以指定目标机器，新分配的region将在这些机器上

如何申请内存

• CM通过2PC阶段和副本进行通信，申请region
• 在region可用前，mapping信息需要传递给所有副本

如何进行RAMD写

在读取上，每个机器都有一个ring buffer，实现了FIFO队列，在写的时候，sender通过RDMA直接写到尾部，然后NIC（网卡）直接给ACK，receiver周期性的从头部读取数据处理。

分布式事务和复制

前面的一篇论文Efficient Optimistic Concurrency Control提出的2PC提交会有一个问题，coordinate如果挂了或者participants挂了，会影响整个进程，因此一个想法就是进行primary-backup备份，保证高可用，于是就有下面的图：

2PC

这种主备的模式每次消息都需要和Primary和Backup同时交互，并且需要消耗CPU。

而FaRM在提交上使用：

• one-sided RDMA进行操作
• 减少消息数量
• 使用OCC（乐观并发控制）
  • version number（用户读数据的版本验证）
  • 整体流程：本地执行+锁写记录+验证读记录+提交并解锁

Lock

• 写lock record到写数据的primary上
• primary尝试着锁住记录，然后进行回应

Validate

• 通过RDMA进行读，然后比较version是否改变了

Commit backups

• 通过RDMA写log到所有backups
• coordinate等待所有backups回复

commit primaries

• 通过RDMA写commit-primary记录到每个primary
• primary处理记录，然后unlock
• 只要coordinator收到一个primary的NIC回复，就认为成功，返回给应用

Truncate

• coordinator收到所有primary的回复后，进行truncate
• 在提交其他日志的时候，捎带上truncate
• backups在truncation的时候，进行数据的更新操作

故障恢复

TODO

实验

略

这是6.824: Distributed Systems的第11课，你的鼓励是我继续写下去的动力，期待我们共同进步。