分布式系统：FaRM

硬件新趋势

RDMA

• RDMA：remote DMA，远程内存直接访问。
• 硬件支持：需要网卡的特殊支持
• 可以远程读/写另一台机器上的内存。
• 特点：应用程序直接与网卡交互，所以绕过本机的OS内核（不用TCP/IP协议栈）。在对方机器上，网卡直接读/写内存，不需要对方CPU的参与。
• 写操作成功能收到对方网卡硬件发来的ACK（确认）。
• 也可以用来实现类似RPC的效果。发送方用RDMA写到远端内存。接收方用poll查询有没有新RPC命令。执行完后，接收方用相同的方法发送回复。
• single-cache-line RDMA reads and writes are atomic. （1条cache行能有多大？FaRM正确性依赖于这条。所以，存储的每个object不能过大。见课程lec 8 FAQ）
• 消除网络瓶颈。

non-volatile RAM

• 不怕断电的RAM。其实只是普通的RAM，不怕断电是因为接在UPS上。停电后UPS会继续供电，维持一小段时间，内存的东西就写到固态硬盘保存。然后正常关机。等供电恢复，再从固态硬盘读回到内存。
• 固态硬盘平时不用，只在供电故障时用。平时读写的速度就非常快。
• SSD写要100ms，non-volatile RAM写只要几个ms。
• 消除硬盘瓶颈。

系统架构

• 类似GFS
• 一台配置管理器（configuration manager），相当于GFS的master
  • 只有1台，没有副本。大概是因为1台崩溃概率不大。而且有non-valatile RAM做保障，不怕断电。
• Primary/Backup 每份数据复制 f + 1 份。1个primary处理读/写，f 个backup执行与Primary一样的写操作（读就不必了）保持数据完全一致。
  • f 台挂掉也没事，只有1台活着就行。但是任何1台挂掉，系统都不是立刻可用(immediately available)。而是先恢复到 1 + f 份replicas。
  • Primary/Backup与Raft不一样。Raft是多数活着就可以保持可用。但是如果超过半数不能恢复运行，就可能会丢失数据。
  • 每个服务器既存放数据，同时也可以作为transaction coordinator (TC)。
    • 数据的replicating不是通过primary，而是TC自己直接发给backups。
• ZooKeeper保存当前的1) 配置编号，2) 配置包含了哪些服务器，3) 那台机器是CM。——2台服务器同时想做CM，ZooKeeper负责裁定哪台做CM。网络分区时，防止了裂脑。
  • 为什么不用Zookeeper做：manage leases，detect failures, coordinate recovery？因为Zookeeper不用RDMA，而CM用RDMA来实现恢复，更高效。

乐观并发控制

1. Execute Phase
   读取值和版本号。计算结果暂时写到本地。
2. Commit Phase
   四个步骤：
   LOCK、锁住要写的region
   VALIDATE、 检查读过的region版本号未改变
   COMMIT-BACKUP、将新值直接写入到backup的log
   COMMIT-PRIMARY、叫primary将新值写入

四个步骤与RDMA

• LOCK需要对方CPU参与
  • 因为单纯RDMA没有办法实现compare-and-swap。
  • 加锁需要CM利用单边RDMA write将加锁请求放到primary的log中，等对方CPU执行一个CAS操作。
  • 对方通过LOCK-REPLY消息答复加锁是否成功。
• VALIDATE和COMMIT-BACKUP是RDMA单边读、RDMA单边写
  • 完全不用对方cpu参与
• COMMIT-BACKUP和COMMIT-PRIMARY都只等硬件答复ACK。不等对方CPU真正把log应用到数据区Region。
  • 这样速度快。log应用到数据区与CM处理事务可以并行。

故障和恢复

• 凡是有节点失效，都要先经历重新配置（reconfiguration），然后恢复事务状态（transaction state recoery）。
• 恢复的时候，是primary先在region内部协调完，replicate完log，然后以region为单位整体投1票。
• 决定整个事务投票结果的是CM。
  • 如果看到1个commit-primary票，就决定commit
  • 否则等待所有region的票都来，
    • 如果至少有1个区域投COMMIT-BACKUP，且其他区域都投COMMIT-BACKUP或者LOCK票，则commit。否则abort。

课前问题

Suppose there are two FaRM transactions that both increment the same object. They start at the same time and see the same initial value for the object. One transaction completely finishes committing (see Section 4 and Figure 4). Then the second transaction starts to commit. There are no failures.(无机器故障) What is the evidence that FaRM will use to realize that it must abort the second transaction? At what point in the Section 4 / Figure 4 protocol will FaRM realize that it must abort?

• 答：因为其中1个事务彻底完成了提交，那么锁释放，版本已经改变。第二个事务LOCK不会成功。因为Locking can fail if any object if any object version changed since it was read. 就是说，LOCK不仅看锁状态，还检查版本号。

疑问

• 第60页提到，we use Zookeeper znode sequence number to implement an atomic compare-and-swap
• 疑问：为什么不是用version？
  setData(path, data, version)
  if znode.version = version, then update

参见

6.824’s lec8