No Compromises: Distributed Tran

(原文链接)[https://blog.acolyer.org/2016/01/14/no-compromises/]

让我们进行思想实验。 在过去的几天里，我们一直在研究事务提交协议，并根据消息延迟和强制写入的次数来评估它们的成本。 但是暂时假设网络I / O和存储I / O并不是瓶颈，那些操作确实很便宜。 相反，想象一下CPU是否是瓶颈。 在如此疯狂的世界中，事务处理系统（和数据存储）的最佳设计会看起来一样吗？ 您会做出哪些取舍？

这个疯狂的世界是真实的，它由许多小的电池供电，它改变了一切！ 我们可以称其为FaRMville。 在FaRMville中，您可以具有严格的可序列化性的分布式事务，并且仍然获得令人难以置信的高性能，低延迟，可持久的和高可用性。 在FaRMville中，事务是由FaRM处理的，FaRM是我们去年首次查看的快速远程存储系统。

一个90台机器的FaRM集群每秒完成450万笔TPC-C“新订单”交易，其第99个百分位数的延迟为1.9毫秒。 如果您准备以“仅” 4M tps的速度运行，则可以将延迟减少一半。 哦，它可以在大约60毫秒内从故障中恢复。 当然，由于FaRMville是一个充满挑战的世界，挑战了我们所有的假设，因此作者不得不根据第一原理设计新的事务，复制和恢复协议……

本文证明了现代数据中心中的新软件可以消除折衷的需求。 它描述了FaRM（一种主内存分布式计算平台）中的事务，复制和恢复协议。 FaRM为分布式ACID事务提供了严格的可序列化性，高可用性，高吞吐量和低延迟。 这些协议是从第一原理开始设计的，以利用数据中心中出现的两种硬件趋势：具有RDMA的快速网络和提供非易失性DRAM的廉价方法。

点评：硬盘的IO和网络的IO 都被极大的缩减了，在2种新技术产品的出现下。一个就是可持久化的内存，一个是RDMA

知识卡片：RDMA网络协议允许用户程序绕过操作系统内核直接进行网络通信。这样既避免了用户空间到系统空间的复制开销，也可以省去进入内核处理的开销，极大地降低了网络时延，并且提高了吞吐量。此外， RDMA技术还提供了新的网络原语，网卡可以绕过处理器直接处理对服务器内存的读写请求。网卡提供了对远程内存的读（read）、写（write）和原子（atomics）操作，可以极大地提升远程服务器的CPU使用效率。

one-side RDMA

image.png

知识卡片：可持久化内存

image.png

我们在晨报上曾经遇到过RDMA，它代表远程直接内存访问。 one-side RDMA是RDMA支持的最快的通信方法，它绕过CPU可以单向直接访问另一台计算机的内存。

数据中心中的DRAM变得越来越便宜。

典型的数据中心配置每2插槽计算机具有128-512GB的DRAM，而DRAM的成本不到12美元/ GB。 这意味着1 PB的DRAM仅需要2000台计算机，这足以容纳许多有趣应用程序的数据集。

正是我前面提到的那些“小电池”使事情变得非常有趣……分布式UPS取代了集中式，昂贵的UPS（不间断电源），将锂离子电池集成到了每个机箱的电源单元中。 架。 估计费用不到每焦耳0.005美元，并且比传统的UPS更可靠。 所有这些电池意味着我们可以将内存当作稳定的存储来对待……

分布式UPS有效地使DRAM持久耐用。 发生电源故障时，分布式UPS使用电池中的能量将内存内容保存到SSD中。 这不仅避免了对SSD的同步写入，从而提高了普通情况下的性能，还通过仅在发生故障时写入SSD来保留SSD的寿命。 另一种方法是使用非易失性DIMM（NVDIMM），它们包含自己的专用闪存，控制器和超级电容器（例如[2]）。 不幸的是，这些设备是专用的，昂贵的且笨重的。 相比之下，分布式UPS使用商用DIMM并利用商用SSD。 唯一的额外成本是SSD和UPS电池本身的预留容量。

在最坏的情况下，使用这种方法的非易失性成本约为0.55美元/ GB，保留的SSD容量的存储成本约为0.90美元/ GB。 因此，总的附加成本约为基本DRAM成本的15％。

高性能网络与RDMA的结合以及将内存视为稳定存储的能力消除了网络和存储瓶颈，因此暴露了CPU瓶颈。

FaRM的协议遵循以下三个原则来解决这些CPU瓶颈：减少消息数量，使用one-side RDMA读写代替消息以及有效利用并行性。

减少消息数量的原因是打包，拆包和分派中所涉及的所有CPU（即使在不太极端的硬件情况下，串行化和反序列化也已成为瓶颈。） FaRM使用主备份复制和乐观并发四阶段提交协议。

one-side RDMA可以直接访问远程数据，而完全不涉及远程CPU，并且对本地CPU的要求最低。 但是，如果不涉及远程CPU，那么在远程区域也不会进行任何其他处理，这需要对系统的设计有所不同。 （单向RDMA请求的处理在NIC中进行，NIC是网络接口控制器）。

FaRM事务在事务执行和验证期间使用one-side RDMA读取。 因此，他们在远程只读参与者上不使用CPU。 此外，当在事务中修改的对象副本上将记录记录到非易失性WAL时，协调器使用one-side RDMA。 例如，协调器使用一个one-side RDMA将提交记录写入远程备份。 因此，事务在备份时不使用前台CPU。 延迟截断日志以就地更新对象时，稍后将在后台使用CPU。

由于这种情况非常罕见，因此值得再次强调的是，这些预写日志仅保存在内存中，因为内存是稳定的存储。

故障检测和恢复也必须看起来有些不同……

例如，FaRM不能在租约到期时依靠服务器去拒绝进来的请求，因为请求由不支持租约的NIC来服务。 我们通过使用精确的成员资格来确保该计算机同意当前的配置成员资格，并仅向作为成员的机器发送单边操作，从而解决了该问题。 FaRM也不能依赖传统机制来确保参与者在准备阶段具有提交事务所必需的资源，因为事务记录被写入参与者日志中而不涉及远程CPU。 相反，FaRM使用预留来确保日志中有足够的空间来存储在开始提交之前提交和截断事务所需的所有记录。

点评：不能使用租约和传统的事务提交方式主要是因为现在的这套方案主要是靠网卡直接操作内存，绕过了CPU。

事务模型

FaRM使用乐观并发并提供严格的可序列化性。 在事务的执行阶段，对象读取是从内存中进行的（本地访问或通过RDMA），所有写入均在本地进行缓冲。 记录访问的每个对象的地址和版本。 在事务结束时，提交协议如下进行：

1. 锁定阶段：协调器将LOCK记录写入每台机器上的日志，这是任何写入对象的主要记录。 该记录包含每个书面对象的版本和新值。 原语通过尝试使用CAS将对象锁定在指定的版本来处理这些消息。 他们发回一条消息，指示是否已成功获取所有锁。 如果从事务读取对象以来，任一对象版本被更改，或者另一个事务将对象锁定，则协调器将中止该事务并将中止记录写入所有主数据库的日志中。

2. 验证阶段：协调器现在检查事务读取的所有对象的版本是否都未更改。 可以通过单面RDMA进行操作，而无需远程CPU参与。 如果主要对象持有的阈值tr对象超过某个阈值，则使用RPC代替（RPC变得便宜的的临界点是4）。 如果版本已更改，则事务中止。

3. 提交备份阶段：每次备份时，协调器都会将提交备份记录写入日志，并等待NIC的确认（不涉及远程CPU）。

4. 提交主数据库阶段：每次备份时都从NIC收到确认（对于在出现故障时确保严格序列化是必要的），协调器会将提交主数据库记录写入每个主数据库的日志中。 一旦收到至少一个硬件确认，就可以向应用程序报告完成情况。 原语通过更新就位的对象，增加其版本并对其进行解锁来处理这些记录。

5. 截断：“备份和主记录将记录保留在日志中，直到被截断。 协调器在收到来自所有主节点的确认后，会在主节点上截断日志并延迟备份。 它通过在其他日志记录中附带截断的事务的标识符来实现。 备份会在截断时间将更新应用到其对象副本。”

image.png

FaRM提交阶段使用Pw（f + 3）是单面RDMA写入，其中Pw是作为事务写入的对象的Primary机器数，而Pr是单面RDMA读取的数量，其中Pr是从远程读取但是不能写的对象数。 读取验证会在关键路径上增加两个单边RDMA延迟，但这是一个很好的权衡：在没有负载的情况下，增加的延迟只有几微秒，而CPU开销的减少会导致更高的吞吐量和负载下的延迟。

Epochs

FaRM依靠对每个数据区域的主和备份的精确了解。 更改配置后（例如，由于机器故障且正在更换），所有机器必须在允许对象突变之前就新配置的成员资格达成一致。 FaRM重新配置协议负责将系统从一种配置转移到另一种配置。

使用单面RDMA操作对于获得良好的性能很重要，但是它对重新配置协议提出了新的要求。 例如，一种实现一致性的常用技术是使用租约：服务器在答复访问对象的请求之前检查它们是否持有对象的租约。 如果将服务器从配置中逐出，系统将保证在其租约到期之前不会更改其存储的对象。 当服务于使用消息与系统通信的外部客户端的请求时，FaRM使用此技术。 但是由于FaRM配置中的计算机使用RDMA读取对象而不涉及远程CPU，因此服务器的CPU无法检查它是否持有租约。 当前的NIC硬件不支持租约，目前尚不清楚将来是否支持租约。

当机器收到配置标识符大于自身配置的NEW-CONFIG消息时，它准备通过更新其当前配置标识符和缓存区域映射的副本来迁移到新配置，并为分配给它的任何新区域分配空间 。 “从这一点来看，它不会向不在配置中的计算机发出新请求，并且会拒绝来自这些计算机的读取响应和写入确认。 它还会开始阻止来自外部客户端的请求。”机器使用NEW-CONFIG-ACK回复配置管理器。 一旦从新配置中的所有计算机接收到确认，协调器就会通过发送NEW-CONFIG-COMMIT消息来提交新配置。 然后，成员解除阻止先前阻止的外部客户端请求，并启动事务恢复。

错误侦查和恢复

即使整个集群发生故障或断电，我们也可以为所有提交的事务提供持久性：可以从存储在非易失性DRAM中的区域和日志中恢复所有提交状态，即使每个对象最多f个副本丢失了非持久性对象的内容，我们也可以确保持久性 。 FaRM还可以维护出现故障和网络分区的可用性，前提是存在一个分区，该分区包含保持彼此连接的大多数计算机以及Zookeeper服务中的大多数副本，并且该分区包含每个对象的至少一个副本。

错误可以被恢复通过5个阶段

1. 故障检测，使用非常短的租约（5-10毫秒）。任何租约到期都会触发恢复。一个90节点的群集可以使用5毫秒的租约，且没有误报。 “要在负载下获得短期租赁，需要小心的实现”！
2. 使用上面简要描述的重新配置协议进行重新配置。
3. 事务状态恢复，使用分布在由要恢复的事务修改的对象副本上的日志。首次访问被阻止访问恢复区域，直到已获取所有用于恢复事务的写锁为止。然后清空日志，以确保在恢复期间处理所有相关记录。在日志耗尽过程中，确定了一组恢复事务（提交阶段跨越配置更改的事务）。通过NEED-RECOVERY消息交换有关这些事务的信息。然后获取锁，复制日志记录，以便每个参与者都有一个完整的集合，并且协调器驱动提交协议来决定是提交还是中止。给定事务的协调器由一致的哈希确定。
4. 批量数据恢复。数据恢复（重新复制数据以确保将来可以容忍f个复制失败）对于恢复正常操作不是必需的，因此它被延迟到所有区域都变为活动状态为止，以最大程度地减少对延迟至关重要的锁的恢复的影响。
5. 分配器状态恢复– FaRM分配器将区域分成1MB的块，用作分配小对象的平板。空闲列表需要通过扫描区域中的对象在新的主数据库上恢复，该对象在计算机上的所有线程之间并行化。

在TPC-C测试中，系统在丢失节点后不到50ms的时间内即可恢复大部分吞吐量。 完整的数据恢复仅需4分钟以上。

我的思考与启发

1. 基于RDMA 和 NVM 可能是未来分布式系统的一个可能趋势。
2. 这篇文章为我打开了一个全新的世界。
3. 很多地方还是一知半解，需要将来储备了更多知识回来重新消化。