Intro

有着高可用性与强可串行性的事务提供了一个单机且不会失效的抽象，按照顺序执行事务。FaRM利用了RDMA与非易失性DRAM。非易失性通过将电池接入DRAM实现，当电源失效时将数据写入SSD。这种趋势消除了存储与网络瓶颈，然而暴露出了CPU瓶颈。FaRM遵循了三种原则来针对CPU瓶颈：减少消息数、使用单侧RDMA读写而不是消息、高效利用并行性。

FaRM使用了4-Phase Commit Protocol。

单侧RDMA不需要远程CPU的参与。FaRM事务的执行与验证中使用了单侧RDMA读。Coordinator在将记录写入非易失性WAL时使用单侧RDMA，coordinator将commit记录写入远程副本中。因此不需要前台的CPU参与，CPU在之后的后台任务中可以lazy原地截取log。

使用单侧RDMA需要新的错误恢复协议。FaRM不能依赖服务器来拒绝租期过期的请求。同时也不能依赖传统的确认参加者拥有所有的事务资源的机制。

FaRM的错误恢复有效的利用了并行。

Hardware Trend

NV DRAM

分布式UPS，在检测到电源失效时可以将DRAM的内容写入SSD，不仅避免了SSD的同步写入问题，同时保护了SSD的寿命。另一种方式时NVDIMM，然而这种设备是特制的。

Architecture

FaRM提供给了应用全局寻址空间的抽象。FaRM API提供了获取本地或远程对象的透明方法。应用可以在成为coordinator后开始事务。在事务执行阶段可以执行任意逻辑。在结束后，调用FaRM来提交事务。

FaRM使用乐观并行控制。执行过程的更新在本地缓存，只有在成功的commit后才会被其他的事务可见。Commit与当前的事务冲突时会失败。在事务执行中，FaRM保证了单个对象的读取是原子的，只会读取已经提交的数据，连续的读取会返回相同的数据。然而不保证不同对象的读取是原子的，未提交的事务可能会在执行过程中看到不一致的数据。

FaRM API提供了无锁读取，提供给只读取单个对象的事务。局部性提示，可以将相关的对象放到同一个机器集合中。可以用来优化性能。

![](Pasted image 20220213172740.png)

FaRM使用4元组表示了不同的配置。使用ZooKeeper来保存，但是不需要ZooKeeper来做租约与恢复。只在配置更新时调用ZooKeeper。

FaRM的寻址空间由2G大小的region组成，每一个分为1个主副本与f个备份。每个机器在NVRAM中存储多个region，可以被其他机器通过RDMA访问。Object总是从包含region的主副本中读取，如果在本地使用内存访问，如果在其他机器使用RDMA。每个object有64bit的版本用来并发控制欲复制。从region标识符到副本的映射由CM维护。映射按需的获取，并且与RDMA引用一起缓存。

通过联系CM来分配新的region。CM赋予region单调增加的标识符并且选择副本。副本的选择平衡了每个机器中的region数量，每个副本在不同的failure domain中，同时副本可以在用户指定的与之搭配的副本相同region中。Machine向选择的副本机器发送带有region标识符的prepare message。如果所有的副本机器成功分配region，CM向所有的副本发送commit。2P保证了在使用region之前映射有效并且在所有的副本上复制。

每个machine有环形缓冲区，FIFO。作为消息队列或者事务log使用。每个发送接收者都有保存在接收者的log与消息队列。发送者通过RDMA将记录追加到log中。接收者周期性拉取记录来处理log。

Tx

FaRM继承了事务与复制协议来提高性能。相比传统的协议使用更少的消息，并且利用了RDMA读写。FaRM在主从副本上使用NVRAM保存数据与事务log，使用未复制的coordinator直接与primary和backup通信。使用乐观并发控制与读检验。

在执行阶段，使用RDMA读取object并且在本地缓存写入。在coordinator中记录所有访问object的地址与版本。

在commit阶段，

Lock：coordinator想所有写入object的primary机器发送lock记录。包含了写入object的新的值、版本和object的所有region的列表。Primary使用Compare-and-Swap来处理记录，并且返回锁是否获取。如果有其他的事务改变或者lock了object，lock会失败。失败后coordinator会向所有primary发送abort。
Validate：Coordinator从primary读取进行读检验，如果version出现了改变则取消transaction
Commit Backups：Coordinator写入COMMIT-BACKUP到backup的log中，当backup的网卡返回ack后继续，不需要占用backup的CPU
Commit Primaries：在所有的COMMIT-BACKUP收到ack后，coordinator向所有的primary写入COMMIT-PRIMARY，当收到任何一个ack后向应用返回成功

为什么需要Validate

Validate=单侧RDMA获取Object版本（与lock），如果版本改变或者lock被设置，则失败

VALIDATE example:
x and y initially zero
T1:
if x == 0:
y = 1
T2:
if y == 0:
x = 1
(this is a classic test example for strong consistency)
T1,T2 yields y=1,x=0
T2,T1 yields x=1,y=0
aborts could leave x=0,y=0
but serializability forbids x=1,y=1

suppose simultaneous:
T1: Rx Ly Vx Cy
T2: Ry Lx Vy Cx
what will happen?
the LOCKs will both succeed!
the VALIDATEs will both fail, since lock bits are both set
so both will abort – which is OK

how about:
T1: Rx Ly Vx Cy
T2: Ry Lx Vy Cx
T1 commits
T2 aborts since T2’s Vy sees T1’s lock or higher version
but we can’t have both V’s before the other L’s
so VALIDATE seems correct in this example
and fast: one-sided VALIDATE read rather than LOCK+COMMIT writes

正确性

LOCK+VALIDATE保证了事务ACID

Fault-Tolerant

the critical issue:
if a transaction was interrupted by a failure,
and a client could have been told a transaction committed,
or a committed value could have been read by another xaction,
then the transaction must be preserved and completed during recovery.

look at Figure 4.
a committed write might be revealed as soon the
first COMMIT-PRIMARY is sent (since primary writes and unlocks).
so by then, all of the transaction’s writes must be on all
f+1 replicas of all relevant shards.
the good news: LOCK and COMMIT-BACKUP achieve this.
LOCK tells all primaries the new value(s).
COMMIT-BACKUP tells all backups the new value(s).
TC doesn’t send COMMIT-PRIMARY until all LOCKs and COMMIT-BACKUPS complete.
backups may not have processed COMMIT-BACKUPs, but in NVRAM logs.

similarly, TC doesn’t return to client until at least one
COMMIT-PRIMARY is safe in primary log.
this means’ TC’s decision will survive f failures of any shard.
since there’s one shard with a full set of COMMIT-BACKUP or COMMIT-PRIMARY.
any of which is evidence that the primary decided to commit.

Optimistic

two classes of concurrency control for transactions:
pessimistic:
wait for lock on first use of object; hold until commit/abort
called two-phase locking
conflicts cause delays
optimistic:
read objects without locking
don’t install writes until commit
commit “validates” to see if other xactions conflicted
valid: commit the writes
invalid: abort
called Optimistic Concurrency Control (OCC)

Steve's

6.824-FaRM