我们将继续考虑使用链复制的示例。 在第一部分中给出了基本的定义和体系结构，我建议您在阅读第二部分之前先熟悉一下它。

在本文中，我们将研究以下系统：

• Hibari是用erlang编写的分布式容错存储库。
• HyperDex-分布式键值存储，支持按辅助属性快速搜索和范围搜索。
• ChainReaction-因果关系+一致性和地理复制。
• 无需使用其他外部监视/重新配置过程即可构建分布式系统。

5. Hibari

Hibari是用erlang编写的分布式容错KV存储库。 使用链式复制（基本方法），即 达到严格的一致性。 在测试中，Hibari显示出高性能-在两台服务器上每秒完成数千次更新（1Kb请求）

5.1架构

一致性哈希用于放置数据。 存储的基础是物理和逻辑块。 物理砖是一台装有Linux的服务器，也许是一个EC2实例，通常是整个VM。 逻辑积木是一个存储实例，集群的主要进程通过该存储实例工作，每个块都是任一链中的一个节点。 在下面的示例中，集群在每个物理块上配置了2个逻辑块，链长为2。请注意，在物理块上“涂抹”了链的节点以提高可靠性。

主进程（请参阅第一部分中的定义）称为管理服务器 。

数据存储在“表”中，这些表被简单地分为命名空间，每个表至少存储在一个链中，每个链仅将数据存储在一个表中。

Hibari客户端从管理服务器接收更新，其中列出了所有链（和所有表）的所有头和尾。 因此，客户立即知道将请求发送到哪个逻辑节点。

5.2散列

Hibari使用一对 $$$\ {T，K \}$ 确定存储密钥的链的名称 $$$K$ 在桌子上 $$$T$ ：键 $$$K$ 映射到间隔 $$$[0.1，1.0）$ （使用MD5），将其划分为一个链负责的部分。 这些部分的宽度可以不同，具体取决于链的“重量”，例如：



因此，如果某些物理块非常强大，则可以给位于其上的链分配更宽的部分（然后更多的键将落在它们上）。

6. HyperDex

该项目的目标是建立一个分布式键值存储库，与其他流行的解决方案（BigTable，Cassandra，Dynamo）不同，该存储库将支持快速搜索辅助属性并可以快速执行范围搜索。 例如，在先前考虑的系统中，要搜索某个范围内的所有值，您必须遍历所有服务器，这显然是不可接受的。 HyperDex使用Hyperspace Hashing解决了此问题。

6.1架构

超空间哈希的想法是建立 $$$n$ 每个属性对应一个坐标轴的三维空间。 例如，对于对象（名字，姓氏，电话号码），该空间可能如下所示：



灰色超平面穿过所有按键，其中姓氏=史密斯，黄色穿过所有按键，其中姓氏= John。 这些平面的交点形成对姓名为John和姓Smith的人的搜索查询电话号码的响应。 所以要求 $$$k$ 属性返回 $$$（n-k）$ 维子空间。

搜索空间分为 $$$n$ 维不相交的区域，并且每个区域都分配给单个服务器。 具有来自区域的坐标的对象存储在该区域的服务器上。 因此，在对象和服务器之间建立了哈希。

搜索查询（按范围）将确定结果超平面中包含的区域，从而将轮询服务器的数量减少到最少。

这种方法存在一个问题-所需服务器的数量从属性的数量呈指数增长，即 如果属性 $$$k$ 那你需要 $$$O（2 ^ k）$ 服务器。 为了解决此问题，HyperDex将超空间的分区应用到子空间（具有较低维度）中，子空间分别具有属性的子集：

6.2复制

为了确保严格的一致性，作者开发了一种特殊的方法，该方法基于链复制- 依赖于值的链 ，其中每个后续节点通过对相应属性进行散列来确定。 例如钥匙 $$$（“ John”，“ Smith”）$ 首先将其哈希到密钥空间（我们得到头链，也称为点领导 ），然后从哈希$$ $ inline $“ John” $ inline $ 到相应轴上的坐标，依此类推。 （有关示例更新，请参见下图。 $$$u_1$ ）

所有更新都通过一个点领导，该领导对请求进行排序（线性化）。



如果更新导致该区域发生变化，则首先在旧版本之后立即写入新版本（请参阅更新）。 $$$u_2$ ），并在收到来自尾部的ACK之后，将更改前一服务器到旧版本的链接。 并发请求（例如 $$$u_2$ 和 $$$u_3$ ）并未违反一致性，如果收到，领导者会将版本控制和其他元信息添加到服务器 $$$u_3$ 之前 $$$u_2$ 可以确定订单已中断，您需要等待 $$$u_2$ 。

7. ChainReaction

使用因果+收敛模型，该模型为因果（因果）收敛增加了无冲突收敛的条件。 为了实现因果收敛，将元数据添加到每个请求，该元数据指示所有因果相关键的版本。 ChainReaction使您可以在多个数据中心进行地理复制，并且是CRAQ理念的进一步发展。

7.1架构

FAWN的体系结构仅需进行少量更改即可使用-每个DC包括数据服务器 -后端（数据存储，复制，形成DHT环）和客户端代理 -前端（将请求发送到特定节点）。 每个密钥被复制到R个连续的节点，形成一个链。 读请求按尾部处理，头按写入。

7.2一个数据中心

我们注意到链复制产生的一个重要属性-如果节点 $$$k$ 因果关系与某些客户端操作一致，然后与所有先前的节点一致（也是如此）。 所以如果操作 $$$Op$ 是我们最后一次在网站上看到的 $$$j$ ，然后所有因果相关（来自 $$$Op$ ）读取操作只能在从头到头的节点上执行 $$$j$ 。 尽快 $$$Op$ 将在尾部执行-没有读取限制。 表示在DC中由尾部执行的写操作 $$$d$ 像DC-Write-Stable（d）一样 。

每个客户端都以格式（密钥，版本，chainIndex）存储客户端请求的所有密钥的列表（元数据），其中chainIndex是响应最后一个密钥请求的节点在链中的位置。 仅针对客户端不知道其是否为DC-Write-Stable（d）的密钥存储元数据 。

7.2.1写操作

请注意，一旦操作变为DC-Write-Stable（d），则没有读取请求可以读取以前的版本。

对于每个写请求，添加了在最后一次写操作之前对其执行读操作的所有键的列表。 客户端代理收到请求后，就会立即对元数据中所有键的尾部执行阻塞读取（我们正在等待确认存在相同或更新版本，换言之，我们满足因果一致性条件）。 收到确认后，写入请求将发送到相应链的头部。



一旦新值存储在 $$$k$ 链中的节点，通知将发送到客户端（带有最后一个节点的索引）。 客户端更新chainIndex并删除已发送密钥的元数据，如下所示 众所周知，它们是直流写入稳定的（d）。 同时，记录继续进行进一步的延迟传播 。 因此，优先考虑在第一个 $$$k$ 节点。 尾部存储密钥的新版本后，便会向客户端发送通知，并将通知发送到链中的所有节点，以便它们将密钥标记为稳定。

7.2.2读取操作

客户端代理将读取请求发送到 $$$指数：=兰德（1，chainIndex）$ 电路中的节点，同时分配负载。 作为响应，节点发送值和该值的版本。 响应发送到客户端，同时：

• 如果版本稳定，则新的chainIndex等于链的大小。
• 如果版本较新，则新的chainIndex =索引。
• 否则，chainIndex不会更改。

7.2.3节点故障转移

它几乎与基本方法完全相同，不同之处在于在某些情况下客户端上的chainIndex变为无效-这在执行请求时很容易确定（此版本没有密钥），并将请求重定向到链的头部以搜索具有所需版本的节点。

7.3（ $$$N$ ）数据中心（地理复制）

我们以单服务器体系结构中的算法为基础，并将其最小化。 首先，在元数据中，我们不仅需要version和chainIndex值，还需要N维的版本化向量。

我们用与DC-Write-Stable（d）类似的方式定义Global-Write-Stable-如果对所有DC的尾部执行写操作，则将其视为Global-Write-Stable。

每个DC中都有一个新组件-remote_proxy ，它的任务是从其他DC接收/发送更新。

7.3.1执行写操作（在服务器上 $$$我$ ）

开始类似于单服务器架构-我们执行阻塞读取，然后写入第一个 $$$k$ 链的结。 此时，客户端代理会向客户端发送一个新的chainIndex向量，其中零位到位（位置除外） $$$我$ -有意思 $$$k$ 。 接下来-像往常一样。 最末尾的另一项操作-将更新发送到remote_proxy，它会累积多个请求，然后发送所有内容。

这里出现两个问题：

• 如何确保来自不同DC的不同更新之间的依赖性？
  
  每个remote_proxy存储一个本地版本向量 $$$rvp$ 尺寸 $$$N$ ，它存储发送和接收的更新数量，并在每次更新中发送。 因此，当从另一个DC接收更新时，remote_proxy会检查计数器，如果本地计数器较小，则会阻塞操作，直到接收到相应的更新。
• 如何在其他DC中为此操作提供依赖关系？
  
  这是使用布隆过滤器实现的。 从客户端代理执行写/读操作时，除了元数据外，还将为每个键发送一个Bloom过滤器（称为响应过滤器）。 这些筛选器存储在AccessedObjects列表中，并且在请求写/读操作时，元数据还会发送OR筛选器已发送的键（称为依赖筛选器）。 同样，在写操作之后，将删除相应的过滤器。 将写操作发送到另一个DC时，还将发送此请求的依赖项筛选器和响应筛选器。
  
  此外，已接收到所有这些信息的远程DC会检查响应过滤器的设置位是否与几个查询过滤器的设置位一致，则此类操作可能是临时依赖的。 可能-因为布隆过滤器。

7.3.2读取操作

类似于单服务器体系结构，针对使用chainIndex向量而不是标量进行了调整，并且DC中可能没有密钥（因为更新是异步的）的可能性-然后等待或将请求重定向到另一个DC。

7.3.3解决冲突

由于有了元数据，因果相关的操作始终以正确的顺序执行（有时您必须为此阻塞流程）。 但是，不同地区的竞争变化可能导致冲突。 为了解决这种情况，使用了Last Write Wins，在每次更新操作中都有一对 $$$（时钟，s）$ 在哪里 $$$c$ -代理小时，以及 $$$s$ -DC的ID。

7.3.4处理节点故障

与单服务器架构相似。

8.在可伸缩复制协议的设计中利用分片

该研究的目的是构建具有分片和复制功能的分布式系统，而无需使用外部主进程来重新配置/监视集群。

在当前的主要方法中，作者看到了以下缺点：

复制：

• Primary / Backup-如果错误地将Primary标识为出故障，则导致状态不一致。
• 仲裁交集-在群集重新配置期间可能导致状态差异。

严格的一致性：

• 协议在需要时依赖多数投票算法（例如Paxos） $$$2 * N + 1$ 掉结 $$$N$ 节点。

检测节点故障：

• P / B和CR表示使用故障停止模型对故障节点进行理想检测，这在实践中是无法实现的，因此您必须选择合适的扫描间隔。
• ZooKeeper会遇到相同的问题-对于大量客户端，需要大量时间（> 1秒）来更新配置。

作者提出的称为弹性复制的方法没有这些缺点，并且具有以下特征：

• 严格的一致性。
• 承受跌落 $$$N$ 节点必须具有 $$$N + 1$ 结。
• 重新配置而不会失去一致性。
• 无需基于多数票的共识协议。

汇总板：

8.1复制品的组织

每个分片定义一系列配置 $$$\ mathcal {C} = C_1 :: C_2 :: C_3 \点$ 例如，新配置不包含某种形式的副本 $$$\ mathcal {C} = \ mathcal {C}：:(副本\ setminus R_j）$

配置序列的每个元素包括：

• 副本-一组副本。
• orderer-具有特殊角色的副本的ID（请参见下文）。

每个分片都由一组副本表示（通过构造- $$$N$ ），即 我们没有划分“碎片”和“副本”的角色。

每个副本存储以下数据：

• conf-此副本所属的配置的ID。
• orderer-哪个副本是此配置的订购者。
• 模式-复制模式，以下三种之一： $$$等待中$ （来自非 $$$C_1$ ）， $$$活动$ （来自的所有副本 $$$C_1$ ）， $$$IMMUTABLE$ 。
• 历史记录-对实际副本数据的操作顺序 $$$op_1 :: op_2 :: \点$ （或只是一个条件）。
• 稳定-此副本固定的历史记录前缀的最大长度。 显然， $$$0 <=稳定<=长度（历史）$ 。

副本订购者的主要目标是将请求发送到其余副本，并维护最大的历史记录前缀：

8.2分片的组织

碎片被组合成称为弹性带的环。 每个分片仅属于一个环。 每一个碎片的先驱 $$$X$ 扮演特殊角色-他是他的音序器。 定序器的工作是在复制失败的情况下为后继程序提供新的配置。


需要两个条件：

• 每个弹性带具有至少一个碎片和一个工作副本。
• 每个弹性带都有至少一个碎片，所有复制品都在其中工作。

第二个条件似乎太严格了，但是它等同于主过程永不失败的“传统”条件。

8.3使用链复制

您可能已经猜到了，副本是按链条组织的（基本方法）-订购者将是头名，略有不同：

• 如果CR发生故障，则在ER中将节点抛出链外（并替换为新的），从而创建新链。
• CR中的读取请求由尾部处理，在ER中，它们以与写入请求相同的方式遍历整个链。

8.5发生故障时重新配置

• 副本由分片的副本和定序器分片的副本监视。
• 一旦检测到故障，副本就会发送有关此命令。
• 定序器发送新配置（没有失败的副本）。
• 创建一个新副本，该副本将其状态与松紧带同步。
• 之后，定序器发送带有添加副本的新配置。

参考文献

• bar原
• hyperdex.orgerdex.org
• HyperDex：分布式，可搜索的键值存储
• 连锁反应
• 在可伸缩复制协议的设计中利用分片