FaRM高性能分布式事务

Title: No compromises: distributed transactions with consistency, availability, and performance

FaRM Overview

FaRM = Fast + Remote + Memory

为何要学习FaRM

  • 另一种对transactions+replication+sharding的实现：这仍然在研究领域，没有投入实际生产。

  • 乐观并发控制OOC(stric serializability)

  • 利用了了RDAM NICs的巨大性能潜力。

整体设计

  • FaRM全部通讯都在一个数据中心

    • 与Spanner不同的是，Spanner全球性的广域的设计

  • configuration manager：使用ZooKeeper, 选择主从复制 primaries/backups

  • Shards采用主从复制(只有在恢复的时候会进行通信)
    P1 B1
    P2 B2
    …

    • 只要至少有一个shard的副本就能恢复
    • f+1的副本就容忍f次的故障

  • 事务代码充当两阶段提交的事务协调器(TC)

FaRM目标

  • 每秒完成百万数量级的事务
    • 时间的预算是几十微妙

性能提升

如何高性能

  • 在多个服务器上进行分片(在评估中是90个)

  • 数据必须符合总RAM(因此没有磁盘读取)

  • 降低CPU的利用率

    • 非易失性RAM(因此没有磁盘写入)
    • one-sided RDMA(快速跨网络访问内存)

  • 快速用户级访问网卡

  • 事务+复制协议，利用单边RDMA

NVRAM (non-volatile RAM)

FaRM 直接写入RAM不需要写入磁盘 — eliminates a huge bottleneck

  • RAM write takes 200 ns, hard drive write takes 10 ms, SSD write 100 us
    • ns = nanosecond, ms = millisecond, us = microsecond
      但是当我们在电源故障后将会使RAM的内容丢失，RAM不能持久化。因此我们使用了UPS。

UPS(distributed uninterruptible power supply)

装备电池在每个机架上，当服务器发生断电时，可以再让运行机器几分钟。具体执行过程如下

  • 电源硬件通知软件当主电源断电，软件停止所有事务，软件将FaRM的RAM的数据写入到SSD，可能几分钟后机器就会关机。

  • 在重新启动时，FaRM从SSD读取保存的内存映像“非易失性RAM”

如果奔溃阻止了软件写入SSD?

例如FaRM或内核中的bug或者cpu/内存/硬件错误，FaRM处理单机崩溃和复制崩溃(除了电源故障)必须是独立的!因此崩溃不会阻止FaRm写入将RAM的数据写入SSD

总结:

NVRAM消除了持久写入瓶颈，剩下的瓶颈是网络和CPU

降低CPU使用率(Reduce CPU Utilization)

通常情况

为什么网络在通常情况下会是性能瓶颈？

  • FaRM假设只有一个数据中心，因此具有较低的光速延迟
  • 但网络数据处理的CPU成本往往很大

网络交互：
从应用中将数据写入socket的缓存中通过TCP封装，传递给网卡的硬件驱动，通过网卡进行发送。如下述例子所述

1
2
3
4
5
6
app                       app
---                       ---
socket buffers            buffers
TCP                       TCP
NIC driver                driver
NIC  -------------------- NIC

大量昂贵的CPU操作如系统调用、复制信息、中断、上下文转换。这些都会成为FaRM的性能瓶颈

Kernel bypass

NIC直接访问内存

FaRM应用直接与网卡交互，没有系统调用与内核参与

  • 网卡使用DMA访问用户的RAM

  • FaRM轮询DMA(内存)区域检查收入的消息

    • NIC会维持一个接收消息的队列

  • 网卡轮询DMA(内存)区域检查发送的消息

    • NIC会维持一个发送消息的队列

  • 轮询是一个线程，用于代替系统中断，直接访问消息队列

one-sided RDMA

remote NIC directly reads/writes memory：宏观来讲就是直接访问另一台机器的内存且接收方CPU不参与操作

RDMA：是一些现代网卡实现的特殊功能。网卡寻找通过网络到达的特殊命令包，并自行执行命令(而不将包交给CPU)。这些命令指定内存操作，例如将值写入地址或从地址读取并通过网络将值发回。

此外，RDMA网卡允许应用程序代码直接与NIC通信以发送特殊的RDMA命令包，并在“硬件ACK”包到达时收到通知，表明接收网卡已经执行了命令。

  • “One-sided” “指的是一台计算机中的应用程序代码使用这些RDMA网卡直接读取或写入另一台计算机中的内存，而不涉及另一台计算机的CPU。

  • FaRM有时使用RDMA作为一种快速方法来实现类似rpc的方案，以便与接收计算机上运行的软件进行通信。

  • RDMA的好处是速度快。单向RDMA读写只需1/18微秒，而传统RPC可能需要10微秒。即使FaRM使用RDMA进行消息传递也比传统RPC快得多:接收器中的用户空间代码经常轮询传入的NIC队列，以便快速查看新消息，而不是涉及中断和用户/内核转换。

实现


该图表示了FaRM应用通过Kernel bypass + RDMA降低了CPU的利用率。NIC是一个特殊的网卡同时支持kernel bypass与RDMA。

  • 通过Kernel bypass发送消息将直接发送包到NIC不需要CPU参与

  • 通过one-sided RDMA，接收方的接收处理包也不需要CPU的参与

  • RDMA Read： “Validate”阶段仅使用one-sided读取。

    • 将请求对象的包(头部设置为RDMA包)，加入NIC的发送队列，传送到目的主机的接收队列，进行定时轮询内存区域，FaRM应用将对象的数据再通过NIC回复给请求主机

  • RDMA Write： “Lock”阶段以这种方式使用RDMA。(不需要加入NIC队列)

    • 发送方使用RDMA将请求消息写入接收方FaRM软件轮询(定期检查)的内存区域，将请求消息放入消息队列进行处理、Record写入Log，接收方以同样的方式发送应答。

编程模型与架构

Setup

组成成分

  • Region： 可以看作一个2GB的字节数组，其中包含了多个Object。同时Region也对应着(Pi,Bi)的映射

  • Object： 一个数据结构，用于存储数据。object有唯一的一个标识符为oid，oid对应了Region号与地址，并且object的头部包含了一个64为的整数，高1位表示的是否Lock，低63位标识版本号

  • Zookeeper： 作为FaRM的服务协调，提供一个Coordinator Management

  • SSD： 断电时存储RAM内的数据

API

1
2
3
4
5
6
7
8
9
Txn BEGIN

O <------ Read(oid)

O.f + 1 = 1

write(oid,O)

Txn COMMIT

该例子中我们使用了两个API为read与write。我们通过调用read方法填入oid(object id)从而实现了获得数据对象O，在O的字段上+1并缓存到本地，之后再调用write方法将对象写入。(一个事务可能跨多个Region)

分布式事务与复制

图中虚线为处理读取，实线是写入，点线是硬件回复。其中P1、P2是处理读写事务，P3是只读事务。C为Zookeeper中的Coordinator[[ZooKeeper 论文笔记]]、P为Primary、B为Backup。黑色的方块为对象(副本中只有一个Backup，因此该副本只有一个容错)

  • Coordiantor获取LOCK消息最后一条Ack消息的点为序列化点

  • Coordiantor获取VALIDATE消息的最后一条ACK消息的点为Decision点，事务开始提交

  • Coordiantor获取COMMIT-PRIMARY的第一条ACK消息为开始提交的报告给应用，事务提交结束

执行阶段(Execute phase)

Coordinator进行操作

  • one-sided RDMA对Primary进行读取(OCC)

  • 将修改对象的内容缓存到本地

  • 记录这些primary的地址以及读取并记录到的数据的版本号。

    • 如果Primary与backup与coordinator位于同一台机器上就不会使用RDMA进行读，而是使用本地内存进行访问(读取操作)

在Figure4中该阶段读取了三个分片，为S1，S2，S3

提交阶段(Commit phase)

目标

  • 原子性的分布式提交：全部写入或都没写入

  • 序列化：每个事务都有先后顺序

五个步骤

  1. Lock(写入日志). Coordinator通过RDMA Write发送一条Lock消息给每台读取对象的primary的日志中

  • Lock记录包含了这包含了oid、版本号和写对象的新值

  • Lock消息既是预读日志条目(Read-ahead log)，也是对主服务器的RPC请求。

  • 日志将被加入到NVRAM中防止断电或者电源故障

收到LOCK后primary会做什么?

  • FaRM软件轮询内存中的日志, 发现写入的日志

    • 检查日志，如果对象已经加锁了或者写入的对象的版本号与读取的不相同
      • 发送一个no的回复给coordinator

  • 反之，将对象的Lock flag设置为1，回复一个yes给coordinator

    • 并不会修改对象，也不会修改对象的版本号

  • lock检查->版本号检查->lock的设置是原子性

    1. 使用原子性的compare-and-swap指令将对象锁定在指定版本
    2. 防止其他CPU也在处理LOCK，或者客户端正在用RDMA读取
  1. Validate(检查读取对象). Coordinator使用one-sided RDMA发送Validate消息给读取对象的primary，该消息只包含了oid以及版本号，执行读取验证(read Validate)。

Priamry处理

检查Validate的版本号与primary内存中的版本号以及对象是否上锁

  • 如果冲突，则验证失败，发送no给coordinator，事务将会终止。

  • 如果相同，则验证相同，发送yes给coordinator。

  • Validate默认使用的是one-side RDMA。

  1. Commit backups.(副本写入日志) Coordiantor写入一个COMMIT-BACKUP的记录(与Lock内容相同)到Backups的不易失的日志中，并等待不会让CPU中断的NIC硬件返送ACK消息。

  2. Commit primaries(处理日志). coordinator在接受到所有COMMIT-BACKUP的ACK消息后，Coordinator发送COMMIT-PRIMARY消息给每一台Primary中。

  • coordinator会等待硬件的ACK应答
    • 不会等待Primary处理日志
    • 硬件应答意味着Primary的NVRAM很安全

Primary处理日志

  • 将新值拷贝到对象的内存中

  • 增加对象的版本号

  • 清除对象的lock flag，设置为0

  1. Truncate. Primary与Backup中的日志会一直保存直到被截断。Coordinator接收到所有Primary的ACK后，将会阶段Primay与Backup的日志

QA:

Q：为什么发现锁已经被其他锁占用后是中止而不是等待解除阻塞

A：Figure4中是读写事务，发现锁被其他事务占用说明我们读操作读取的数据的就已经被修改了，因此会破坏Strict Serializability，产生错误。

Q：Primary与Backup是主从复制，那为什么他们不直接通讯？

A：应用的设计是这样的，他们的一致性是由CM来保证(Lock与commit Backup消息内容相同)。只有在崩溃恢复时Primary与Backup会进行沟通。

Q：下述案例中，T2在T1完成Lock与Validate后，在T1提交前提交，这样会有什么样的错误(T1的validate阶段读取了T2修改的版本号)

1
2
3
T1: Wx0 Wy0 Rz0 .....   L V .... C

T2:             Rz0 Wz1 ... C

A：T1 < T2 ，T2在T1之后开始，因此根据严格序列化规则：T2必须看见T1的写入，因此根据该规则，T2的读也需要在T1提交之后才能执行。意思也就是T2比T1提前提交这种情况也是不会出现的。

Log Record type

Log record type Content
LOCK transaction ID, IDs of all regions with objects written by the transaction, and addresses, versions, and values of all objects written by the transaction that the destination is primary for
COMMIT-BACKUP contents are the same as lock record
COMMIT-PRIMARY transaction ID to commit
ABORT transaction ID to abort
TRUNCATE low bound transaction ID for non-truncated transactions and transaction IDs to truncate
表中展示了每条日志信息的类型以及对应的内容

Correctness

乐观并发控制(OCC)

OCC = Serializability + Snapshot isolation(MVCC)

对于读写事务中对于读操作是不需要加锁的，而写操作仍是需要加锁。读操作是通过Strict Serializaiblility来实现一致性。

严格的序列化： 序列化点总是在开始执行和向应用程序报告完成之间(Figure4)

对于读操作我们在提交阶段加上了冲突检测版本号

  • 版本号冲突(写对象有锁或是版本号改变)的话事务中止(abort)
  • 版本号相同则进行提交(commit)

FaRM使用OCC的原因：

  • 使用了one-sided RDMA读取
  • 服务器(CPU)不需要主动参与读取

Validate的作用

当我们处理两事务：假设开始时X=0，y=0

  • T1：if x == 0 ，set y = 1
  • T2：if y == 0 ，set x = 1

我们假设可能产生的结果:绝不可能并发执行时产生x=1，y=1

  • T1产生：x = 0 ，y = 1
  • T2产生：x = 1 ，y = 0
1
2
3
4
   excution   commit
T1 Rx0 Ry0  | Ly Vx            Cy

T2 Rx0 Ry0  |       Lx Vy(fail)   Cx

当我们并发执行T1与T2：T1的x与T2的y都可以上锁

  1. 首先T1先开始提交，将y上锁(不会增加对象版本号)，验证x；
  2. 然后T2开始提交，将x上锁，验证y，但是由于y已经上锁(说明y可能已经别其他对象修改)，因此需要中止T2事务

只读事务

一个纯只读的FaRM事务只使用使用one-sided RDMA read：不需要写入、不需要日志、不需要锁。速率十分的快。(个人觉得不需要validate阶段像spanner的只读事务一样)

提交时机

  • 在最后一次读取后提交只读事务

  • 在获取写锁时提交读写事务是可序列化的

    • 在可序列化的点上的对象的版本号与执行阶段的相同

  • Locking确定对象被写入，Validate确定对象为只读

    • 如果没有失败，这就相当于在序列化点原子地执行和提交整个事务。

提交协议

  • 传统两段提交协议： Participant可以在处理prepare消息时预留资源以提交事务，或者在没有足够的资源时拒绝准备事务。

  • FaRM的提交协议：

    • 在提交过程中避免Backup的CPU参加，Coordinator必须为所有参与者保留日志空间，以保证进度。
    • Coordinator为所有提交协议记录预留空间，包括在开始提交协议之前截断主日志和备份日志中的记录。
      • 如果截断被附加在另一条消息上，截断记录保留也会被释放

Spanner 与 FaRM

共同之处

都是关于分片、复制和使用了事务的二段提交(2PC)

不同之处

Spanner:

  • 重点讨论由于地理复制而引起的网络延迟

  • Paxos提供容错延迟

  • TrueTime 让客户端读取当地的副本

  • 性能方面: 读写事务处理花费10到100 ms (Tables 3 and 6)

FaRM

  • 重点讨论减少CPU的利用率

  • RDMA、直接NIC获取、NVRAM去避免磁盘写入

  • RDMA让FaRM可以使用OCC

  • 性能方面: 58微秒的时间处理简单的事务 (6.3, Figure 7)

    • i.e. 比Spanner快100倍

总结

  • 超快速度的分布式事务

  • 硬件是还处于研究阶段(NVRAM和RDMA)，但可能很快就会普及

  • 使用OCC提高速度并允许快速One-sided RDMA读取

FQA

Q: 目前使用FaRM的系统有哪些?

A: FaRM似乎是一个研究系统，而不是用于生产。我怀疑它会影响未来的设计，也许它本身会发展成一个生产系统。

Q: 为什么公司(微软，谷歌，Facebook，雅虎等)会公开他们的软件，而不是对他们的设计保密?

A: 这些公司发表的论文只涉及他们所编写软件的一小部分。他们发表文章的原因之一是，这些系统部分是由具有学术背景的人(即拥有博士学位的人)开发的，这些人认为他们人生的一部分使命是帮助世界理解他们发明的新思想。他们为自己的工作感到自豪，希望人们能欣赏他们的工作。另一个原因是，这些论文可能有助于公司吸引顶尖人才，因为这些论文是如何在那里进行智力上有趣的工作的。

Q: FaRM真的标志着分布式系统在一致性/可用性方面的必要妥协的结束吗?

A: 论文的这一部分看起来更像是广告而不是科学。历史表明，没有哪个绩效水平高到没有人会想要更高的，而那些人很可能愿意在其他方面做出妥协，以获得他们所需的绩效。

Q: FaRM的局限性是什么?

A: 数据必须符合RAM。如果事务冲突很多，OCC将产生大量中止。事务API(在他们的NSDI 2014论文中描述)看起来使用起来很尴尬，因为回复在回调中返回。应用程序代码必须紧密交织执行应用程序事务和轮询RDMA NIC队列和日志来自其他计算机的消息。应用程序代码在执行最终会中止的事务时可以看到不一致。应用程序可能不能为自己的目的免费使用线程，因为FaRM将线程固定到核心，并使用所有核心。FaRM需要特殊的网络硬件，但尚未广泛部署。只有当所有的计算机彼此靠近时，这种设计才有意义;它不是地理分布的秘方(因此容错能力有限)。当然，FaRM是一个旨在探索新想法的研究原型。它不是一般用途的成品。如果人们继续从事这项工作，我们最终可能会看到FaRM的后代没有那么多粗糙的地方。

Q: 为什么FaRM基于RDMA的RPC比传统RPC更快?

A: 传统RPC要求应用程序对本地内核进行系统调用，内核要求本地NIC发送一个数据包。在接收计算机上，NIC将数据包写入内存中的队列，并中断接收计算机的内核。内核将数据包复制到用户空间，然后上下文切换到接收应用程序。接收应用程序反向发送应答(系统调用内核，内核与NIC通话，另一端的NIC中断内核，等等)。这一点是为每个RPC执行大量的代码，而且速度不是很快。

相反，FaRM安排应用程序代码可以直接读写内存以与NIC通信，并将CPU内核(本文称之为硬件线程)专门用于轮询传入消息。这消除了中断、系统调用、在用户和内核之间复制数据以及上下文切换的成本。

Q: FaRM的大部分性能来自于硬件。软件设计在哪些方面对性能有贡献?

A: FaRM速度快的一个原因是硬件速度快。但是硬件已经存在了很多年了，但是还没有人知道如何将所有的部件组合在一起，从而真正发挥硬件的潜力。FaRM做得这么好的一个原因是他们同时投入了大量的精力来优化网络、持久存储和CPU的使用;许多以前的系统只优化了一个，而不是全部。一个特定的设计点是FaRM对许多交互使用快速单边RDMA(而不是较慢的完整RPC)的方式。

Q: 其他系统是否使用UPS(不间断电源，带电池)来实现快速而持久的存储?

A: 这种想法是古老的;例如，Harp复制文件服务在20世纪90年代早期就使用了它。许多存储系统以相关的方式使用电池(例如在RAID控制器中)来持续写入而不等待磁盘。然而，FaRM使用的这种电池设置并不是特别常见，所以必须通用的软件不能依赖它。如果您将自己的硬件配置为有电池，那么修改Raft(或k/v服务器)以利用电池是有意义的。

Q:如果没有电池支持的RAM, FaRM的设计还有意义吗?

A: 我不确定FaRM在没有非易失性RAM的情况下是否有意义，因为这样单方面的日志写入(例如图4中的COMMIT-BACKUP)就不会在电源故障时持续存在。您可以修改FaRM，以便在返回之前将所有日志更新写入SSD，但这样会大大降低性能。SSD写入大约需要100微秒，而FaRM的单边RDMA写入非易失性RAM只需要几微秒。

Q: DRAM本身不是不稳定的吗?

A: 作者通过使用UPS使RAM“非易失性”，允许FaRM在电源故障时将RAM的内容写入SSD。但是，这确实不是完全非易失性的，因为如果计算机由于任何其他原因而崩溃，而不是电源故障，那么故障机器的内存内容就会丢失。这就是为什么他们在多台机器上复制每个区域，并具有快速恢复协议的原因。

Q: 如果电源即将失效，FaRM服务器将RAM复制到SSD。他们能用机械硬盘驱动器代替ssd吗?

A: 他们使用ssd是因为它们速度快。他们本可以在不改变设计的情况下使用硬盘驱动器。然而，在断电期间将数据写入磁盘将花费大约10倍的时间，在恢复供电后将数据读入磁盘将花费大约10倍的时间。这需要更大的电池和更大的耐心。

Q:FaRM中主、备份和配置管理器之间的区别是什么?为什么有三个角色?

A: 数据在许多主/备份集之间进行分片。备份的目的是存储碎片数据和日志的副本，以防主服务器出现故障。主数据中心执行对分片中数据的所有读写操作，而备份数据中心只执行写操作(以保持它们的数据副本与主数据中心的副本相同)。只有一个配置管理器。它跟踪哪些主备份处于活动状态，并跟踪数据如何在它们之间进行分片。在较高的级别上，这种安排类似于GFS，后者也在许多主/备份集之间对数据进行分片，并且也有一个主系统来跟踪数据的存储位置。

Q: FaRM在小范围内可行吗?

A: 我认为FaRM只有在需要每秒支持大量事务时才有意义。如果您只需要每秒处理几千个事务，您可以使用现成的成熟技术，如MySQL。您可以设置一个比作者的90台机器系统小得多的FaRM系统。但是FaRM没有意义，除非你是在分片和复制数据，这意味着你至少需要四个数据服务器(两个分片，每个分片两个服务器)和一些用于ZooKeeper的机器(尽管你可能可以在这四台机器上运行ZooKeeper)。然后，也许你有一个成本约为10,000美元的系统，每秒可以执行数百万个简单交易，这是非常好的。

Q: 第3节似乎说单个事务的读取可能会看到不一致的数据。这看起来不像是可序列化的!

A:Farm仅保证提交的事务的可序列化性。如果事务看到了第3节所讨论的那种不一致，FaRM将中止事务。应用程序必须处理不一致，因为它们不应该崩溃，这样它们就可以请求提交，这样FaRM就可以中止它们。

Q: FaRM如何确保事务的读取是一致的?如果一个事务读取了一个正在被另一个事务修改的对象，会发生什么?

A: 这里有两个危险。首先，对于一个大对象，读取器可能会在并发事务写入它之前读取对象的前半部分，而在并发事务写入它之后读取后半部分，这可能会导致读取程序崩溃。其次，如果读事务不能与并发写事务串行化，则不允许提交它。

根据我对作者之前的NSDI 2014论文的阅读，第一个问题的解决方案是每个对象的每个缓存行都有一个版本号，单缓存行RDMA读写是原子的。读取事务的FaRM库获取对象的所有缓存行，然后检查它们是否都具有相同的版本号。如果是，标准库将对象的副本提供给应用程序;如果没有，库将通过RDMA再次读取它。第二个问题是由FaRM在第4节中描述的验证方案解决的。在VALIDATE步骤中，如果自我们的事务启动以来，另一个事务写入了由我们的事务读取的对象，那么我们的事务将被中止。

Q: 日志截断是如何工作的?什么时候可以删除日志条目?如果截断调用删除了一个条目，那么之前的所有条目也都被删除了吗?

A: 在TC看到主服务器和备份服务器的日志中都有一个COMMIT-PRIMARY或COMMIT-BACKUP后，TC告诉主服务器和备份服务器删除事务的日志条目。为了使恢复知道尽管截断了事务，但事务还是完成了，第62页提到，即使在截断之后，primary也会记住已完成的事务id。截断意味着删除截断点之前的所有日志条目;这是因为每个主/备份在每个TC上都有一个单独的日志。

Q:是否可能在COMMIT-BACKUP期间发生中止，可能是由于硬件故障?

A: 我想是的。如果其中一个备份没有响应，并且TC崩溃，那么事务可能会在恢复期间中止。

Q:当许多事务需要修改同一个对象时，FaRM性能会受到影响吗?

A:当多个事务同时修改同一个对象时，其中一些事务将在图4的LOCK阶段看到锁已经被持有。在VALIDATE阶段，读者可能会看到更改的版本或锁定标志。每个这样的事务都将中止并从头开始重新启动。如果这种情况经常发生，业绩确实会受到影响。“乐观并发控制”中的“乐观”指的是希望这样的冲突将很少发生，并且执行无锁读取的能力将产生高性能。事实上，对于作者测量的应用程序，FaRM获得了出色的性能。一个很可能的原因是，它们的应用程序具有相对较少的冲突事务，因此没有太多中止。

Q: 图7显示了当操作数量超过每微秒120次时延迟的显著增加。为什么呢?

A: 我怀疑服务器的极限是总共每秒只能处理大约1.4亿次操作。如果客户端发送操作的速度比这快，其中一些将不得不等待;这种等待会增加延迟。

Q:什么是vertical Paxos?

A: 它是Paxos协议的一种风格，其中外部主服务器执行重新配置，而Paxos组在进行重新配置时可以继续执行操作 (see https://lamport.azurewebsites.net/pubs/vertical-paxos.pdf for the details). 在FaRM论文中，作者使用术语“垂直Paxos”来松散地表示配置管理是由外部服务(Zookeeper和CM)完成的，事务的处理写是通过标准的主/备份协议完成的。

参考

  1. FaRM论文
  2. FaRM FQA
  3. FaRM Lecture