FaRM-No compromises: distributed transactions with consistency, availability, and performance

[KTurnura]

FaRM是微软自己现如今（2015）用来实验的系统：使用RDMA的硬件技术，实现对内存中数据的高速访问，并通过乐观并发控制的办法，避免事务冲突

[KTurnura]

FaRM和Spanner 区别

他们都实现了复制和两阶段提交

Spanner主要关注于跨地理位置的数据事务安排，建立副本，方便访问，解决了二阶段提交上的时间问题等等

FaRM是一种原型，当时并没有落地，他假设：所有的replica都在同一个数据中心

容错能力范围：针对单个服务器的崩溃，当整个数据中心故障后，如何恢复数据

特点：使用RDMA技术，但也因为该技术限制了某些控制、鉴权系统的使用，因此，FaRM强制使用乐观锁并发控制来结合RDMA使用，在事务提交的过程中验证身份；所获得的性能比Spanner快很多 ，FaRM要比Spanenr快100倍，性能高出太多了！！！

Spanner 和 FaRM针对的是分布式事务系统中不同的瓶颈：FaRM主要针对的系统瓶颈在于服务器上的CPU时间，FaRM将所有的replica放在同一个数据中心中，以此来消除卫星信号和网络传播所带来的延迟 ，而Spanner则是为了解决地理位置上的访问速度，以及跨数据中心容错等问题

[KTurnura]

FaRM内容

FaRM系统中有一个Configuration Manager，他决定每个数据分片中哪个服务器是primary，哪个服务器是backup，使用Zookeeper来帮助他们实现了配置管理器

配置原则：根据key将数据进行分片并分散到一堆primary-backup pair上去

每个数据分片对应一个priamry服务器和一个backup服务器，

当你更新数据时，你需要同时更新primary和backup都更新，而且这些replica不是由Paxos之类的东西来维护的，当你读取数据的时候，你只从primary中读取数据，这种replication的内容是为了容错能力

它所获得容错能力是指：只要给定数据分片中的一个replica是可用的，那么这个数据分片就是可用的，只需要一个活着的replica即可，而不需要大多数是

而当数据中心断电时，每个数据分片只要有一个replica可用，那么他就可以恢复过来 如果有f+1个backup，那么可以容忍f个副本错误

Client除了执行事务之外，还需要在两阶段提交中扮演TM(事务协调器)的角色（这个后续会讲到）

能获得高性能的方式

1. 对数据进行分片

2. 将所有数据都放在服务器RAM（内存上）上

   1. 因此需要容忍供电故障：非易失性RAM 来解决内存因掉电导致的数据丢失

3. 使用RDMA技术：在不对服务器发出终端信号的情况下，他们通过网络接口卡NIC 接收数据包并通过指令直接对服务器内存中的数据进行访问（Kernel bypass）。在不经过内核的情况下，应用层通过NIC直接访问内存代码

[KTurnura]

使用NvRAM的好处

NvRAM ： 非易失性RAM

直接在内存中进行修改，而不需要在磁盘上进行修改（数据持久化的过程）

事务修改数据会大幅度提升

但同时写入多个replica中的内存，并不是一个特别好的选择，因为站点范围内的供电故障会摧毁你所有服务器上的数据

这就违反了不相关性：不同服务器所发生的故障都是不想干的

FaRM的应对方法：FaRM给每个机架都安装了电池，当它们检测到供电结束后，会通知服务器，将内存中的数据持久化到磁盘上

当恢复后，就会读取保存在磁盘上的内存镜像，同时做一些恢复工作

本质还是在使用原始的RAM，只是多了电池而已

但该方法只对供电故障才有用

硬件故障、bug导致的故障，NvRAM对此束手无策，故障后会丢失所有数据

这也是FaRM还需要为每个数据分片建立多个replica的原因（除了使用电池供电外，还需要分片来作为应对其他故障容错的手段）

[KTurnura]

另一个性能瓶颈：网络和CPU

传统TCP-IP协议传输网络会经过太多层，每秒传输的RPC消息远小于NIC的上限 FaRM 思路：减少推送数据包成本 两种方式结合使用

1. kernel bypass

   1. 与其让应用程序通过调用复杂的内核代码来发送所有数据，不如通过对内核保护机制进行配置，以此来让应用程序直接访问网络接口卡，以此消除了所有涉及网络的内核代码调用

      NIC的发展让这种实现方式成为可能

   2. 使用toolkit：DPDK，能够让人们写出性能非常高的网络应用程序

   3. 该论文是通过在Windows上修改后实现的，因为需要内核向应用授权对底层硬件的访问权限

   4. NIC需要非常智能，因为可能不止一个应用，NIC需要知道该如何和多个不同的应用队列进行通信

   

2. RDMA：远程直接内存访问（论文中提到的==one-side RDMA==）

   1. 一种特殊的网络接口卡
   2. 支持remote DMA
   3. 源机可以通过RDMA系统发送一条特殊的消息来告诉NIC，让他直接对目标应用程序地址空间中的内存直接进行读写操作。而目标服务器的CPU和应用程序对于刚刚所做的读写操作并不知情。因此也不会出现中断的情况
   4. 所需要做的只是对目标主机的内存进行读取
   5. 这种方式比kernel by pass更快，

   

   RDMA的作用

FaRM使用RDMA通过RPC这样的协议来发送信息。FRAM有时使用RDMA来读写数据，有时也会使用RDMA来给目标队形的incoming messages queue来追加消息的（论文中的恢复中的原语）

而这个信息是需要通过中断来进行查看的，目标机器通过轮询，对内存中所接受到的消息进行定期检查，来看看其他人在最近是否有给我发送消息。

还可以使用RDMA发送或追加一条消息给一个消息队列或者日志

使用RDMA的代价

TCP软件为了支持重复检查和一些其他的特点，牺牲了可靠的传输能力

这些支持RDMA的NIC使用的是他们自己可靠的sequenced protocol，这和NIC间使用的TCP很像，但又不是TCP

当RDMA NIC进行读取或写操作时，直到你的请求丢失或者得到了一个相应，他才不会继续传输数据，他会一直保持传送数据的状态，直到你的请求丢失或者他得到一个相应为止

他会去询问这个软件该请求是成功了还是失败了

因此，我们在实现这种协议的情况时，也舍掉了TCP中大多数很好的特性

因此RDMA在远程数据中心间的性能不能像本地网络那样让我们满意

能否只使用one-side RDMA来构建分布式事务

即在不发送必须由服务器软件进行解释的消息的情况下，我们只使用RDMA来对服务器中的数据进行读或者写。答案是：No

在事务系统中使用RDMA的难题在于replication以及数据分片

面临的挑战：该如何将事务、数据分片以及replication结合在一起

当FaRM使用one-sideded RDMA 去直接读取数据库中的数据时， 他是没法使用one-sided RDMA来对该数据进行修改的（存在鉴权、数据丢失的情况），因此我们需要使用乐观并发锁控制

[KTurnura]

OCC

只需要在执行事务的时候读取数据就可以了，不用去了解是否有权限读取数据，或者有没有正在读该数据进行修改之类的操作，

在使用OCC的时候 ，数据不会直接写入，我们会将这些写操作缓存在Client本地，直到事务最终结束，当事务最终结束的时候，会试着提交事务， 此时会有一个验证阶段

事务处理系统会试着弄清楚你所做的读和写操作是否与执行顺序一致 ，因为他使用的是脏数据进行计算，而不是使用一致的读值来进行计算

如果验证成功，就可以提交事务

如果不成功，就是在试用该数据的时候，有人弄乱了这个数据，此时存在冲突（多个事务同时对一个对象进行修改），此时我们就不会使用乐观锁机制了

因为在提交的时候，计算的结果就已经是错的了，你所读到的数据就是那些你不想读到的损坏数据，所以直到解决这些问题后，系统才不会被阻塞。相反，事务已经被污染了，我们只能中止他们，并去试着重新执行。

因此FaRM使用one-sided RDMA 来对数据进行快速读取

Validation

当你试着去操作一个数据对象的时候，该如何检测出其他人是否也正在对该数据对象进行写入操作

FaRM的研究原型并不支持SQL之类的东西，他支持了用于事务方面很简单的API，使用该API支持事务

txCreate()
o = txRead(OID) // 对象id，OID是一个复合标识符<regionNumber, memoryAddress>
o.f += 1  
txWrite(OID,o)  //写入到本地的buffer数据
ok = txCommit() // 验证是否成功

==当事务冲突时，会放弃OCC，==

问题：在重试的过程中是否涉及指数补偿

如果没有指数补偿，会在同一时间有大量的事务试着去更新同一个值，那么这些事务就都会被中止，然后重新尝试更新，这样就会导致浪费大量的时间（需要给重试增加随机重试时间）

FaRM的API有点儿类似于NoSQL的APi，没有那种很花式的操作：比如SQL的join操作

他是一种很底层的readwrite接口加上对事务的支持，他的读写和事务支持的接口都是很底层的

因此可以是视为带事务的NoSQL数据库

client通过 Region Number来选择要去进行通信的primary和backup

内存区域块格式

Server 布局

Server memory 会有许多队列，在该系统中的其他服务器里，每个服务器都有一份log日志

意味着每个日志记录着对应服务器所执行的事务，比如有四个服务器，那么会有四个日志队列，每个队列记录着对应服务器所执行的事务

每个服务器内存中总会有N^2个队列（一个服务器和另一台服务器构建的channel中会有一个读队列RQ，一个写队列SQ）。还有一组单独的消息队列，用于处理RPC那样的通信

[KTurnura]

FaRM OOC提交协议

先忽略Commit 阶段的VALIDATE阶段和COMMIT BACKUP阶段 该步骤除了进行replication以外，还实现了事务的有序执行

1. Execute phase ： 这里是Client端事务进行读和写的地方

   每个箭头指的是在机器C上所执行的事务， 当他需要去读取某些内容时，他会使用one-sided RDMA来读取相关primary 服务器上内存中的数据。

   此处对于三个不同数据分片，他们分别有一个primary服务器和backup服务器

   假设事务使用one-sided RDMA分别读取了三个数据分片中的数据（事务所需要的所有数据，以及他要去写入的所有数据（包括version number等））

   client 调用t xCommit时扮演了事务协调器的角色，它所使用的整个协议可以看作是一种很精致的两阶段提交，

2. Commit 阶段

   1. lock

      事务协调器发送lock信息给primary，等待他们回复，并且验证消息，client会给每个primary发送他要访问的object id ， 对于client要写入的每个对象来说，他需要将更新后的对象（object id，最开始获取该对象所获取的版本号，更新的值 ）发送给相关的primary，并将其作为一个新的日志条目追加到primary的日志上

      当第一阶段中期结束

      

      这些新的日志已经落地到了这些primary上的日志里面，primary需要主动处理这些日志条目，他需要做一大堆检查来验证该事务中这个primary所负责的部分能否进行提交。

      此时我们得等待每个primary对它内存中的client日志进行轮训，检查是否有新的日志条目，对其进行处理，向Client发送Yes/No来表达最是否能执行该事务的这部分操作

      如果此时object id 对应的对象被锁（通过锁位来表示）上了，则会拒绝该log消息，然后通过RDMA 发送一条消息给Client，表达No，此时事务被中止

      如果该对象没被锁，则primary回去检查他的版本号， 去确保client发送的版本号和client最开始读取的版本号是一致的（此处应该是和本地的版本号一致），如果版本号一致，并且没有被锁，则Primary会返回一个Yes 信号给client，并对该对象进行加锁 ，

      因为primary通过多CPU来执行多线程任务，这里可能会同时存在其他事务（同一个primary上的其他CPU可能会读取其他client在同一时间传入的log队列，不同事务间可能存在着竞争的情况，或者是，有几个不同的事务要试着对同一个对象进行修改所导致的抢锁）

      primary会使用一个原子指令（compare and swap）来检查版本号以及锁 ，然后执行一个原子操作，对该数据版本进行上锁。这也是为什么lock标志位放在高位，而版本号放在低位的原因。这样我们就可以通过一条指令来对版本号和lock标志位进行compare-and-set操作了

      如果对象被锁住了，则也不会出现阻塞的情况（不等待锁释放 ）

   2. Validate

   3. Commit primary 阶段

      1. 为每个primary日志中追加日志条目，事务协调器只能去等待收到来自RDMA NIC的确认消息，不用去等待primary 去处理日志数据，只要事务协调器收到primary的yes消息，则它就可以返回yes来表示这个事务已经执行成功，
      2. 一旦所有primary知道事务协调器已经提交了这个事务，则primary就可以丢弃这个事务相关的日志条目了
      3. primary会去轮询他的队列，如果在某一时刻有一个commit primary记录，则使用先前收到的log消息中的新内容来更新其内存中的这个对象，更新该对象相关的 版本号，清除该对象上的锁，并将该信数据暴露给其他事务。

[KTurnura]

为什么OOC能够提供有序的执行呢

如果两个事务不存在冲突，则单一事务的版本号和lock标志位就不会改变

此时第一次读取该对象时所获得版本号就和上一个事务提交结束时的版本号相同，

如果存在冲突事务，则后者的事务能看到一个新的版本号和该对象上lock标志位被设定上，无法实际执行该事务

Validation and commit backup

上述过程是没有validation和commit backup的过程，

对于读取对象来说，验证过程是一种优化

而对于写入操作过程来说，并不是优化

commit backup 则是容错这方面的其中一部分方案

validation

事务协调器可以通过one-sided read 来进行验证，这样我们就无需将任务访入日志中，并等待primary去查看我们的日志条目对其进行处理了

代替了对象锁的作用，来让只读变得更快

事务协调器会去刷新该对象的header ，只会去检查lock标志位有没有被设置，并检查当前版本号是否和它一开始读取该对象时的版本号一致（==和lock阶段同一过程==）， 比起发送lock消息来说，发送一个validate消息的速度要来的更快

在验证阶段使用one-sided RDMA 进行读取 ，绕过了CPU

结合RDMA + OCC，强制在不检查锁的情况下进行读取