1. Introduction

本文介绍FaRM（Fast Remote Memory），一个内存分布式计算平台，不妥协CAP。

1.1. 分布式事务特性

它提供ACID的分布式事务，并支持：

强串行化保证
高可用性
高吞吐量
低延迟

1.2. 实现基于的硬件

该协议利用下面2个硬件趋势实现：

快速的RDMA（Remote Direct Memory Access）
非易失性DRAM（通过写入SSD实现）

这些减少了存储和网络的瓶颈，但暴露CPU瓶颈，因此FaRM协议使用下面3个方法降低瓶颈：

减少消息数量
使用单边的RDMA进行读写，而不使用消息（它不使用CPU，减少了瓶颈）
- 在事务执行和validation阶段，通过RDMA进行读
- 协调者通过RDMA将WAL写入到副本中
高效利用并行化

1.3. 提交和恢复协议特性

FaRM可以让事务在多台机器上覆盖，提交协议特性如下：

它不使用协调协议（如Paxos），而使用垂直Paxos减少消息传输数量
使用单个协调者进行主备复制
使用四阶段提交协议（lock, validation, commit backup, commit primary)，协议使用乐观并发控制

由于使用了单边RDMA，CPU不参与，因此需要新的恢复协议，：

使用precise membership（精确成员）保证节点同意当前的成员配置，并只向已有成员发送单边操作

系统不能根据租约过期而拒绝请求，因为这个判断需要CPU参与
使用reservation（预留）保证在事务提交之前，所有需要提交的记录都有足够的日志空间用于提交和截断

系统不能依赖类似2PC中prepare阶段检查节点是否允许提交事务，因为这个阶段数据需要锁定，而锁定只锁CPU线程，而数据和日志写入没有CPU参与

1.4. 快速故障检测和恢复特性

快速故障检测可通过高频率的心跳实现，并且使用优先级以及预分配来避免误报。

快速恢复是由于利用并行，并且：

收到节点失效的事务，只需要等待lock recovery阶段即可访问数据，时间是毫秒级的
未受节点失效的事务，即使集群存在部分失效，也可以继续无阻塞运行

2. 硬件趋势

2.1. 非易失性DRAM

使用分布式不中断电源供应系统（Distributed UPS）保证数据不丢失，当外部电源损坏时，该系统利用电池中的电力，将数据保存到SSD中。

另外的方式是使用特殊的硬件，如DIMMs（DRAM中包含自己的闪存）

2.2. RDMA网络

FaRM使用单边的RDMA操作，可以不使用远程节点的CPU。相比RPC，不仅节省CPU时间，还节省了消息传输数量（因为RPC，尤其是基于可靠通信的RPC需要应答）

3. 编程模型和系统架构

FaRM提供集群全局的地址空间，所有的应用访问这个全局的地址空间，因此一个对象的访问可透明化访问（数据在本地还是远程），这通过FaRM API实现。

3.1. 编程模型

主要有3个：

应用的线程可随时启动一个事务，并成为事务的协调者
事务中可执行任意的操作，如读、写、分配空间、释放空间等等
事务结束时，线程通知FaRM来提交事务

事务使用乐观并发控制。任何事务提交前，数据被缓存在本地，对其它事务不可见。提交产生冲突时，返回失败。

事务提供严格串行化隔离性：

单独对象的读取是原子的
- 只读取已提交的数据，若对象未被写入，则事务中读到的数据不变
- 对象在本事务中发送写入，则会读到最新的数据
多对象读取不保证原子性，但保证事务的执行是严格串行化的
- 之前提过的通过快照实现串行化是一种乐观的并发控制，它在提交时检查冲突，但这增加了复杂性。

此外，若事务只是单对象读，则会使用无锁方式读取；且还提供“局部性提示”，让上层定位该机器上相关对象的位置。

3.2. 系统架构

架构中有：

CM节点（配置管理器），负责租约、检测错误、协调和恢复
数据节点，分为2层：
- Application层：
- FaRM层：数据存于NVRAM中，包括：
  - Regions
  - 事务日志
  - 消息队列

配置使用ZooKeeper达成共识（即垂直Paxos的应用），但不用它检测错误和协调恢复，这是由CM节点完成的。

arch

3.2.1. 寻址

内存以2GB进行划分，称为一个Region。一个Region分布在一个主副本，$f$个备副本上，此时系统可容忍$f$个错误。
Region的主备关系保存在CM节点上。
所有的读都落在主副本上，通过访问本地内存（若数据在本地）或者RDMA（若数据在远程节点）实现。

应用可指定目标机器，将新Region分配到该机器上

3.2.2. 申请内存

CM给新Region分配单调递增的标识符，并为该Region选择副本
利用2PC，将区域标识符向相关副本提交，保证在Region可用前，Region和副本的映射信息传递到所有的副本上

3.2.3. RAMD写

上述的消息队列实际上是一个环形的缓冲区，有FIFO特性。

写入时，发送者将请求通过RDMA写入队列尾部，网卡直接返回ACK，接受方周期读取队列头部处理写入请求。

4. 分布式事务和复制

使用四阶段提交协议：

Lock：协调者（发起事务线程）向事务中涉及到写的主节点发送LOCK指令到这些节点日志上，主节点使用CAS锁住记录（根据版本号），若上锁失败则中止事务，否则返回成功。此时达到“串行化点”。
Validate：协调者通过单边RDMA从主节点读取版本号，比较是否改变（若对象数量过多，则会使用RPC）
Commit Backups：协调者将COMMIT-BACKUP写入备节点的日志上，等待对方网卡的回应（要所有的）
Commit Primaries：协调者发送COMMIT-PRIMARY到主节点的日志上，主节点处理记录，并解锁。只有一个主节点的网卡回复，则认为是成功的，可将结果返回给应用
Truncate：协调者收集到所有回复后，可进行日志截断。截断消息可通过其它日志记录的提交请求中捎带，节点收到后，既可以应用变更，同时也可以截断日志。

协议比2PC和Paxos比，提高了可用性，且降低了消息传输次数。

txCommit

具体的日志项格式定义以及消息数据结构定义如下：

5. 故障恢复

FaRM拥有一个主和$f$个备，可容忍$f$个数据丢失的错误，也能保证数据不丢失。

FaRM在故障和网络分区中也能保证可用，前提是：

节点大部分存活
ZooKeeper的节点大部分存活
节点包含所有数据至少1个副本（即不丢失数据）

FaRM故障恢复有5个步骤：failure detection, reconfiguration, transaction state recovery, bulk data recovery, allocator state recovery

5.1. 故障检测

FaRM使用租约检测错误。

每个节点持有CM的租约，CM维护租约，租约过期会触发错误恢复流程。

租约使用三次握手完成：

节点向CM发送租约请求
CM回复同意，并捎带租约请求，返回给节点
节点返回同意给CM

租约时间很短，以保证高可用，并降低误报率。

可以看成三次握手式的心跳

5.2. 重新配置

使用7个步骤完成：

Suspect：CM发现哪个节点租约过期，则怀疑哪个节点失效
Probe：CM向剩余节点发送RDMA读，任何失败的节点都会被怀疑
Update Configuration：CM向ZooKeeper存储$[c+1, S, F, CM_{id}]$，这里
- $c$为当前配置序列号
- $S$为正常的机器集合
- $F$为机器与错误域（Region）的映射
- $CM_{id}$为当前CM的标识符
Remap Regions：新CM重新构建映射
Send New Configuration：CM发送NEW-CONFIG信息，发送新配置到所有的机器上，若CM改变，则租约也会被重置
Appliy New Configuration：节点收到新配置后，重建映射（如创建新Region，将数据映射到新Region上），然后回复消息，发送NEW-CONFIG-ACK,若CM变化，则租约会被重置（由于三次握手，租约在本节点也有一份），在此期间，外部的请求会被拒绝
Commit New Configuration：CM收到所有的回复后，提交配置，发送NEW-CONFIG-COMMIT，它也可被视为一次租约授予，节点收到后，可允许外部请求，并开始事务状态恢复

后3步实际上是一个2PC，同时捎带了一次租约的3次握手。

5.3. 事务状态恢复

FaRM在变更配置后，通过分布在对象副本（事务修改过的）的日志恢复事务状态，状态包括：

被事务修改的对象副本状态
事务执行结果

txr

恢复同样分为7步，时间线如上图：

Block：当主节点挂了后，一个备节点会被提升为主节点，此时Region不可用，直到所有更新该Region的事务都反映在新的主节点上。实现通过阻塞该Region的请求，直到第4步所有的写锁备恢复事务获取后才解除。
Drain Logs：由于网卡不能直接拒绝旧配置下的RDMA请求，因此使用drain log保证相关记录在恢复时被处理（个人理解为：处理完剩余日志中的项）。所有的机器收到NEW-CONFIG-COMMIT后，处理日志中的所有的记录，处理完毕后，会新配置标志会被记录到lastDrained中，若之后日志项的配置标志小于等于lastDrained，则会被拒绝处理。
Find Recovering TXs：寻找事务，事务在提交阶段经历多个配置变化。每个机器都有对给定的事务是否要恢复达成共识。CM读取各个机器上的lastDrained变量，对于每个从lastDrained开始发生映射变化的Region，CM会发送2个配置标识符到NEW-CONFIG消息中（主副本最后一个配置标识符，所有副本最后一个配置标识符）。除了下面情况，所有的事务都要被恢复：
- 对于写：lastReplicaChange[r] < c，左边是上述第二个变量
- 对于读：lastPrimaryChange[r] < c，左边是上述第一个变量
- 协调者没在新配置中移除
之后，每个备节点给主节点发送NEED-RECOVERY消息，告诉主节点哪些事务需要恢复。
Lock Recovery：主节点收到每个备节点的NEED-RECOVERY消息后，将要恢复的事务分片，并发进行锁恢复。主节点每个线程从备节点拉取日志，日志中的记录没被保存在本地，然后给相关对象加上必要的锁。做完之后，第1步被阻塞的Region才能接受外部的请求。
Replicate Log Record：主节点的线程将日志复制到备节点，通过REPLICATE-TX-STATE，保证备节点不丢失事务。
Vote：通过这个阶段决定恢复的事务是否能提交。主节点向协调者的对等线程发送RECOVERY-VOTE：
- 若副本看到COMMIT-PRIMARY或COMMIT-RECOVERY，则投票commit-primary
- 若副本看到COMMIT-BACKUP且没看到ABORT-RECOVERY，投票commit-backup
- 若副本看到LOCK且没看到ABORT-RECOVERY，投票lock
- 若主节点没有相关记录的日志，且事务已经被截断，投票truncated，没被截断则投票unknown
- 否则投票abort
Decide：
- 若所有Region投票commit-primary，则决定提交事务
- 否则等待所有相关Region的投票，若至少有一个commit-backup，且其它所有的只包含lock、commit-backup以及truncated，决定提交事务
- 否则终止事务
然后协调者向所有相关节点发送COMMIT-RECOVERY/ABORT-RECOVERY消息，收到所有节点的回应后，发送TRUNCATE-RECOVERY消息。

5.4. 大规模数据恢复

每个节点给CM发送REGIONS-ACTIVE消息，当主节点的所有Region都开放访问（active，解除阻塞），然后CM返回ALL-REGIONS-ACTIVE，此时开始数据恢复。

恢复时，新的空间会被分片，并且根据线程进行分区，并发恢复。线程从主节点获取数据，通过单边RDMA的方式。为了减少前台操作的影响，每次恢复读取操作都会插入一个随机的时间间隔。

恢复的数据也会被检查，通过检查版本号，数据更改使用CAS，只有版本号更高的数据才会被应用。

5.5. 分配器状态恢复

FaRM将Region分成Blocks（1MB），并用slab分配小对象。

每个Allocator包含2个元数据：

block header：包含对象的大小
slab的free lists

当新的block被创建时，block header需要被复制到备结点，而slab free list只会备保存在主节点。

每个对象头包含一个位，表示对象被分配还是被清理，这个位也会被复制。当错误发生时，free list可以通过扫描Region中的对象恢复。

分配器恢复的时间：收到ALL-REGIONS-ACTIVE后即可，并且每扫描100个对象停顿100μs以降低前台性能影响。而对象释放在slab free list恢复后进行。

论文阅读-不妥协：支持CAP的分布式事务（FaRM）