不妥协：分布式事务的一致性，可用性和性能
本文是论文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通过两点优化使得恢复过程中事务可以并行的执行：
- 只需等到几十毫秒的lock recovery阶段结束，就可以获取故障中的数据了，而无需花费几秒去等待lock recovery之后的恢复阶段
- 没有收到失败影响的事务无需等待直接执行
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的编程模型总结起来，如下：
- 应用线程开启一个事务，同时变为协调者（coordinator）
- 在事务中，可以执行任何的逻辑：如read, write, allocate, and free objects
- 事务最后，告诉FaRM进行提交
FaRM架构
- 主备用户容错
- 配置管理器（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备份，保证高可用，于是就有下面的图：
这种主备的模式每次消息都需要和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课，你的鼓励是我继续写下去的动力，期待我们共同进步。
