在本文中，我们将考虑使用链式复制的简单有效的KV存储体系结构，该体系结构已得到积极研究并已成功应用于各种系统中。

这是链复制文章的前半部分。第二部分在这里。首先，将有一些理论，然后是经过各种修改的一些使用示例。

目的是说明问题并与主要/备用协议进行比较。
链复制是一种基本方法。
链复制-分布式请求。
FAWN：Wimpy节点的快速数组。

1.简介

1.1目的

假设我们要设计一个简单的键值存储。该存储库将具有一个非常小的接口：

写（键，对象）：通过键保存/更新值。
读取（键）：通过键返回存储的值。

我们还知道数据大小相对较小（所有内容都适合一台服务器，不需要分片），但是可能会有很多写/读请求。

我们的目标是承受大量请求（ 高吞吐量，HT ），具有高可用性（ HA ）和强一致性（ SC ）。

在许多系统中，牺牲SC来实现HA + HT，因为要满足所有这三个属性是一项艰巨的任务。 Amazon Dynamo是一个巨大的飞跃，它催生了许多Dynamo风格的数据库，例如Cassandra，Riak，Voldemort等。

1.2主要/备份

构建这种存储系统最常见，最简单的方法之一就是使用主/备份复制。
我们有1个主服务器，几个备份服务器，写入/读取操作仅通过主服务器进行。

这里的图片显示了一种可能的交互协议（主要是等待所有备份发送的ack，然后将ack发送给客户端），还有其他选项（不是互斥的），例如：

Primary严格组织写请求。
一旦其中一个备份响应ack，主服务器就会发送ack。
法定人数和暗示的移交。
等等

还需要一个单独的过程来监视群集的状态（将配置分发给参与者），并且当主机服务器崩溃时，进行（启动）新的选举，并确定在脑裂的情况下该怎么做。同样，根据需求，此逻辑的一部分可以作为复制算法的一部分执行，也可以作为第三方应用程序（例如，用于存储配置的Zookeeper）执行。

显然，迟早，主/备份复制的性能将受到两个瓶颈的限制：

主服务器性能。
备份服务器数。

向集群提出的可靠性/一致性要求越多，此刻就会越快。

还有其他方法可以实现我们的目标吗？

1.3链复制

通常，链复制由一系列服务器（链）组成，这些服务器具有特殊角色HEAD（与客户端通信的服务器）和TAIL（链的末端，SC保证）。链至少具有以下属性：

承受下降到n-1台服务器。
写入速度与SC Primary / Backup的速度没有显着差异。
在发生HEAD崩溃的情况下，群集的重新配置发生的速度比主要服务器快得多，其余服务器的速度则相对于主要服务器/备份服务器而言要快得多。

一个很小但很重要的一点- 服务器之间需要可靠的FIFO连接。

让我们进一步详细研究构建链复制的各种方法。

2.基本方法

2.1运算算法

客户端将写请求发送到头节点，将读请求发送到尾节点。答案总是来自尾巴。 Head收到更改请求后，计算必要的状态更改，将其应用，然后将其发送到下一个节点。尾部处理后，ACK响应将沿着链向下发送回去。显然，如果读取请求返回x的某个值，则它将存储在所有节点上。

2.2复制协议

我们从头到尾对服务器编号，然后在每个节点上

我

$我$ 我们将另外存储：

$Pending_i$ -节点尚未收到尾部处理的已接收请求的列表。
$Sent_i$ -服务器发送到其后继服务器的请求的列表，这些请求尚未被tail处理。
$History_i（密钥）$ -键值的更改历史记录（您既可以存储历史记录，也可以存储总值）。注意：
$H i s t o r y_{j} （ k e y ） s u b s e t e q H i s t o r y_{i} （ k e y ）， f o r a l l j > i$
$History_j（key）\ subseteq History_i（key），\ forall j> i$
并且：
$S e n t_{i} s u b s e t e q P e n d i n g_{i} H i s t o r y_{i} （ k e y ） = H i s t o r y_{i + 1} （ k e y ） c u p S e n t_{i}$
$Sent_i \ subseteq Pending_i \\ History_i（key）= History_ {i + 1}（key）\ cup Sent_i$

2.3服务器故障转移

如简介中所述，我们需要某种主流程，该流程可以：

标识故障服务器。
通知其前任和后继电路更改。
如果服务器是头尾服务器，它将通知客户其更改。

我们相信主进程是稳定的，绝不会崩溃。这样的过程的选择超出了本文的范围。

第二个非常重要的假设是，我们假设服务器是故障停止：

如果发生任何（内部）故障，服务器将停止工作，并且不会给出错误的结果。
服务器故障始终由主进程确定。

让我们看看如何添加新服务器：
从理论上讲，可以将新服务器添加到链中的任何位置，添加到尾部似乎是最困难的-您只需要将当前尾部的状态复制到新服务器，将链中的更改通知向导并通知旧尾部，现在需要进一步发送请求。

最后，考虑三种可能的故障情况：

2.3.1头部跌落
只需从链中卸下服务器，然后分配下一个新磁头。只有这些请求的丢失

P e n d i n g_{h e a d}

$Pending_ {head}$ 没有进一步发送-

P e n d i n g_{h e a d} s e t m i n u s S e n t_{h e a d}

$Pending_ {head} \ setminus Sent_ {head}$

2.3.2落尾
我们从链中删除服务器，然后将之前的服务器分配给新的服务器

S e n t_{t a i l - 1}

$Sent_ {tail-1}$ 清除（所有这些操作都标记为已处理的尾巴）

P e n d i n g_{t a i l - 1}

$Pending_ {tail-1}$ 减少。

2.3.3中间节点下降

k

$k$
向导通知节点

k - 1

$k-1$ 和

k + 1

$k + 1$ 关于链中的重新排序。
可能的损失

已 发 送 k - 1

$已发送{k-1}$ 如果节点

k

$k$ 我没有设法将它们进一步发送给我的继任者，因此，在删除节点之后

k

$k$ 从链中再次发送第一件事

已 发 送 k - 1

$已发送{k-1}$ 而且只有那一个结

k - 1

$k-1$ 继续处理新请求。

2.4与备份/主要协议的比较

在链式复制中，只有一台服务器（尾部）参与读取请求的执行，并立即给出答案，而在P / B主数据库中，它可以等待写入请求完成的确认。
在这两种方法中，写请求都在所有服务器上执行，由于并行执行，P / B的执行速度更快。

故障链复制延迟：

头：读取请求的执行不会中断，写请求会延迟2条消息-从主服务器到新头的所有服务器，从主服务器到新头的所有客户端。
中间服务器：读取请求不会中断。录制请求可能会在运行时延迟 $Sent_i$ 没有更新损失。
尾部：延迟对两个消息的读写请求-通知 $尾巴-1$ 关于新尾巴的信息，并提醒客户有关新尾巴的信息。

故障P / B延迟：

主要：5个消息延迟以选择新的主要和同步状态。
备份：如果没有写入请求，则没有读取延迟。出现录制请求时，可能会延迟1条消息。

如您所见，链复制最严重的尾部故障比P / B（主要）的最严重尾部故障更快。

这种方法的作者进行了负载测试，显示了与P / B协议相当的性能。

3.分布式查询（带有分摊查询的链复制-CRAQ）

基本方法有一个明显的弱点-尾巴，它处理所有读取请求。这可能导致两个问题：

尾巴成为热点，即处理任何更多请求的服务器。
当在多个数据中心中放置一条链时，尾部可能距离很远，这会减慢写请求的速度。

CRAQ的思想非常简单-让读取请求到达除tail之外的所有服务器，并且为了确保一致性，我们将存储对象版本的向量以用于写入请求，并且在出现歧义的情况下，节点将请求tail以获得最新的固定版本。

3.1 CRAQ

我们对CRAQ架构进行形式化：
除尾部外，每个节点都处理读请求并返回响应，而头则从写请求中返回响应（与基本方法比较）。

在每个非尾节点上，可以存储同一对象的多个版本，并且这些版本形成严格单调递增的序列。对于每个版本，将添加一个附加属性“ clean”或“ dirty”。最初，所有版本都是干净的。

节点收到写入请求后，便立即将接收到的版本添加到版本列表中，然后：

如果该节点为tail，则将版本标记为干净，这时该版本被视为固定版本，并向链下发送确认。
否则，它将版本标记为脏，并将请求进一步发送到链下。

节点一旦收到后继的确认，就会将该版本标记为“干净”并删除所有以前的版本。

节点收到读取请求后：

如果节点已知的对象的最新版本是干净的，则它将返回它。
否则，他会要求拖尾以获取该对象的最新固定版本，然后将其返回给客户端。（通过构造，这样的版本将始终在节点上）。

对于具有大量读取请求的应用程序，CRAQ性能随节点的增长呈线性增长 ，在具有大量写入请求的情况下，性能不会比基本方法差。

CRAQ可以位于一个或多个数据中心中。这使客户可以选择最近的节点以提高读取请求的速度。

3.2 CRAQ中的一致性

CRAQ提供了很强的一致性，除了一种情况：当节点从tail接收到最新的提交版本时，tail可以在节点响应客户端之前提交新版本。在这种情况下，CRAQ 在整个链上提供单调读取 （顺序读取请求已成过去，但可以返回旧数据）。

弱一致性也是可能的：

最终一致性：节点将不会从尾部请求最新的提交版本。这将破坏整个链上的单调读数，但将单调读数保留在同一节点上 。另外，它还可以承受网络分区的容忍度 。
有界的最终一致性：仅在特定点之前返回脏版本。例如，脏版本和干净版本之间的差异不应超过N个修订版本。或时间限制。

3.3服务器故障转移

类似于基本方法。

3.4可选

CRAQ具有一项有趣的功能-您可以在录制操作期间使用多播。假设head通过多播发送更改，并且仅向该链向下发送此事件的某些标识符。如果更新本身尚未到达节点，那么当Tail发送更改确认消息时，它可以等待并从下一个节点接收更新。同样，tail可以通过多播发送固定确认。

4. FAWN：Wimpy节点的快速数组

一项非常有趣的研究，与本文的主题没有直接关系，但可以作为使用链复制的示例。

高性能键值存储（Dynamo，memcached，Voldemort）具有共同的特征-它们需要I / O，最少的计算，对大量随机密钥的并行独立访问，以及高达1Kb的小键值。

具有HDD的服务器不适合此类群集，因为其查找操作时间长（访问时间随机），并且具有大量DRAM的服务器消耗的功率出乎意料的大-2GB DRAM相当于1Tb HDD。

最初研究的目标是构建功耗最小的有效（带宽）集群。三年中50％的服务器成本是电费，现代节能模式不如它们宣传的那样有效-在20％负载的测试中，CPU消耗保持在50％，加上其他服务器组件根本没有节能模式（例如，DRAM至少已经可以工作了。重要的是要注意，在这样的群集中，CPU和I / O之间的距离变大了-功能强大的CPU被迫等待I / O操作完成。

4.1架构

FAWN集群基于旧服务器构建，价格为250美元（2009年价格），带有集成的500MHz CPU，512Mb RAM和32Gb SSD。如果您熟悉Amazon Dynamo架构或一致的哈希，那么您将熟悉FAWN架构：

每个物理服务器包含几个虚拟节点，每个虚拟节点都有自己的VID。
VID形成一个环，每个VID负责“自身后面”的范围（例如，A1负责范围R1中的密钥）。
为了提高可靠性，将数据顺时针复制到后续节点的R中。（例如，在R = 2的情况下，A1上的密钥被复制到B1和C1），因此我们得到了链复制（基本方法）。
读取请求转到尾链，即从A1读取密钥将转到C1。
写请求到达头链，一直到末尾。

服务器映射存储在前端服务器的群集中，每个前端服务器负责其特定的VID列表，并且可以将请求重定向到另一台前端服务器。

4.2测试结果

在负载测试中，FAWN在随机读取闪存驱动器上达到QPS的QPS的90％。

下表比较了各种配置的总拥有成本（TCO），其中传统的基础是一台1000美元的服务器，消耗200W功率（2009年价格）：

因此，如果：

大数据，少量查询：FAWN + 2Tb 7200 RPM
少量数据，大量请求：FAWN + 2GB DRAM
平均值：一汽+ 32GB SSD

链复制：构建有效的KV存储库（第1/2部分）