The Rings¶
环确定数据应该驻留在集群中的位置。帐户数据库、容器数据库和单个对象存储策略都有一个单独的环，但每个环的工作方式相同。这些环由外部管理。服务器进程本身不会修改环，而是由其他工具提供的新的修改后的环。
环使用项目路径的 MD5 哈希中的可配置数量的位作为分区索引，该索引指定应该存储该项目所在的设备。哈希中保留的位数称为分区幂，2 的分区幂次方表示分区数。对完整的 MD5 哈希环进行分区允许集群组件批量处理资源。最终，这比单独处理每个项目或一次处理整个集群更有效率或至少更简单。
另一个可配置值是副本计数，它指示为环中的每个分区分配多少个设备。通过为每个分区分配多个设备，集群可以从驱动器或网络故障中恢复。
将设备添加到环中以描述分配给分区副本分配的可用容量。设备被放置在由区域、可用区和服务器组成的故障域中。区域可用于描述机器之间具有较低带宽或较高延迟的地理系统。许多环将仅由单个区域组成。可用区可用于根据物理位置、电源隔离、网络隔离或任何其他会减少多个副本同时不可用的属性对设备进行分组。
设备被赋予一个权重，该权重描述了与其他设备相比，该设备贡献的相对存储容量。
在构建环时，每个分区的副本将根据设备的权重分配给设备。此外，每个分区的每个副本将优先分配给其故障域尚未为该分区拥有副本的设备。每个设备只能分配一个分区的副本 - 您必须拥有至少与副本数量一样多的设备。
Ring Builder¶
环由一个名为 ring-builder 的实用程序手动构建和管理。ring-builder 将分区分配给设备，并将优化的结构写入磁盘上的 gzip 压缩的序列化文件，以便发送到服务器。服务器进程会偶尔检查文件的修改时间，并在需要时重新加载其内存中的环结构副本。由于 ring-builder 管理对环的更改，因此使用稍微旧的环通常意味着对于一部分分区，其中一个副本的设备将不正确，这很容易解决。
ring-builder 还保留一个单独的构建文件，其中包含环信息以及构建未来环所需的其他数据。保留这些构建文件的多个备份非常重要。一种选择是将构建文件复制到每台服务器，同时复制环文件本身。另一种是将构建文件上传到集群本身。完全丢失构建文件意味着必须从头开始创建新的环，几乎所有分区最终都分配给不同的设备，因此几乎所有存储的数据都必须复制到新位置。因此，从构建文件丢失中恢复是可能的，但数据肯定会在一段时间内无法访问。
Ring Data Structure¶
环数据结构由三个顶级字段组成：集群中设备的列表、指示分区到设备分配的设备 ID 列表的列表，以及一个指示用于计算哈希的分区的 MD5 哈希的位数。
List of Devices¶
设备列表在 Ring 类的内部已知为 devs。设备列表中的每个项目都是一个具有以下键的字典
id |
整数 |
设备列表中的索引。 |
zone |
整数 |
设备所在的可用区。 |
region |
整数 |
可用区所在的区域。 |
weight |
float |
设备相对于其他设备的相对权重。这通常直接对应于设备拥有的磁盘空间量与其他设备相比。例如，一个拥有 1TB 空间的设备可能具有 100.0 的权重，而另一个拥有 2TB 空间的设备可能具有 200.0 的权重。该权重也可用于将随着时间推移而最终拥有比预期更多或更少数据的设备恢复平衡。良好的平均权重为 100.0，允许以后灵活地降低权重（如果需要）。 |
ip |
字符串 |
包含设备的服务器的 IP 地址或主机名。 |
port |
int |
服务器进程侦听以服务设备请求的 TCP 端口。 |
device |
字符串 |
服务器上的磁盘名称。例如： |
meta |
字符串 |
用于存储设备附加信息的通用字段。此信息不直接被服务器进程使用，但可能在调试时很有用。例如，可以存储安装日期和时间以及硬件制造商。 |
注意
设备列表可能包含孔，或设置为 None 的索引，用于从集群中删除的设备。但是，设备 ID 会被重用。设备 ID 被重用以避免在有可用插槽（来自先前删除的设备）时可能耗尽设备 ID 插槽。此设备 ID 重用的结果是，设备 ID（整数值）不一定对应于设备添加到环的时间顺序。此外，某些设备可以通过将其权重设置为 0.0 来暂时禁用。要获取活动设备列表（例如，用于正常运行时间轮询），Python 代码如下所示：
devices = list(self._iter_devs())
Partition Assignment List¶
分区分配列表在 Ring 类的内部已知为 _replica2part2dev_id。这是一个 array('H') 列表，每个副本一个。每个 array('H') 的长度等于环的分区数。 array('H') 中的每个整数是上述设备列表中的索引。
因此，要创建分配给分区的设备字典列表，Python 代码如下所示：
devices = [self.devs[part2dev_id[partition]]
for part2dev_id in self._replica2part2dev_id]
array('H') 用于节省内存，因为可能存在数百万个分区。
Partition Shift Value¶
分区移位值在 Ring 类的内部已知为 _part_shift。此值用于将项目路径的 MD5 哈希移位以计算应驻留数据的分区。在此过程中仅使用哈希的顶部四个字节。例如，要计算路径 /account/container/object 的分区，Python 代码可能如下所示：
objhash = md5('/account/container/object').digest()
partition = struct.unpack_from('>I', objhash)[0] >> self._part_shift
对于使用分区幂 P 生成的环，分区移位值为 32 - P。
Fractional Replicas¶
环不限制为具有整数个副本。为了支持逐渐更改副本计数，环能够具有实数个副本。
当副本数不是整数时，_replica2part2dev_id 的最后一个元素将具有长度小于环的分区数的长度。这意味着有些分区将比其他分区拥有更多的副本。例如，如果一个环具有 3.25 个副本，那么 25% 的分区将具有四个副本，而其余 75% 将只有三个。
Dispersion¶
在每次重新平衡时，环构建器都会计算一个分散度指标。这是在特定故障域中具有过多副本的分区的百分比。
例如，如果您在集群中有三个服务器，但分区的两个副本放置在同一服务器上，则该分区将计入分散度指标。
较低的分散度值更好，并且该值可用于找到“过载”的适当值。
Overload¶
ring-builder 尝试尽可能地使副本彼此远离，同时仍然尊重设备权重。当它无法同时做到这两点时，过载因子决定了会发生什么。每个设备可以接受其所需分区的一些额外分数，以允许副本分散；一旦耗尽该额外分数，副本将比为了耐用性而言更紧密地放置在一起。
本质上，过载因子让操作员可以在副本分散（耐用性）和设备平衡（均匀磁盘使用）之间进行权衡。
默认过载因子为 0，因此将严格遵循设备权重。
使用过载因子 0.1，每个设备将在需要维持分散的情况下接受比其正常情况下多 10% 的分区。
示例：考虑一个由具有相同大小磁盘的机器组成的 3 节点集群；节点 A 有 12 个磁盘，节点 B 有 12 个磁盘，而节点 C 只有 11 个磁盘。让环具有 0.1（10%）的过载因子。
如果没有过载，一些分区最终将只在节点 A 和 B 上拥有副本。但是，有了过载，每个设备都愿意为了分散而接受多达 10% 的分区。节点 C 中缺失的磁盘意味着有相当于一个磁盘的那么多分区想要分布在剩余的 11 个磁盘上，这使得节点 C 中的每个磁盘的额外负载为 9.09%。由于这小于 10% 的过载，因此每个节点上都有一个分区的副本。
但是，这意味着节点 C 中的磁盘将比节点 A 和 B 中的磁盘拥有更多的数据。如果 80% 满是集群的警告阈值，那么节点 C 的磁盘将达到 80% 满，而 A 和 B 的磁盘只有 72.7% 满。
Partition & Replica Terminology¶
所有一致性哈希的描述都描述了将键空间分解为多个范围（vnode、bucket 等）的过程 - 比必须将键空间中的键分配到的“节点”数量多得多。Swift 将这些范围称为 分区 - 它们是总键空间的划分。
每个分区将有多个副本。每个分区的每个副本必须分配给环中的一个设备。在描述分区的特定副本时（例如，当它被分配一个设备时），它被描述为该 分区 的特定 副本，因为它是一个特定的 分区 的特定 副本。单个设备可能会被分配来自许多分区的不同副本，但它不能被分配单个分区的多个副本。
环中的总分区数计算为 2 ** <part-power>。环中的总副本数计算为 <replica-count> * 2 ** <part-power>。
在考虑设备的 权重 时，描述它希望分配的副本数很有用。单个设备，无论权重如何，都不会持有超过 2 ** <part-power> 个副本，因为它不能拥有任何分区的多个副本分配给它。设备可以接受的副本数由其 parts-wanted 计算。设备分配的实际副本数可以与它的 parts-wanted 进行比较，类似于误差百分比的计算 - 观察到的结果与理想目标之间的这种偏差称为设备的 平衡。
在考虑设备的 故障域 时，描述希望分配给它的副本数量很有用。一个层故障域中所需的副本数量是其子层故障域中所需副本数量的总和。但是，当一个故障域中的副本总数超过或等于 2 ** <part-power> 时，显然仅仅考虑副本总数已经不够，而是应该考虑每个副本的分区比例。例如，考虑一个具有 3 个副本和 3 个服务器的环：虽然分散性要求每个服务器仅持有总副本的 ⅓，但放置还受到约束，需要每个服务器拥有 每个 分区的一个 1.0 副本。如果其中一个服务器上的两个设备每个都持有单个分区的一个副本，而另一个服务器没有持有任何副本，那么就无法满足分散性要求。通过考虑一个副本分区价值的十进制分数，我们可以在故障域中推导出所需的总副本数 (1.0 * 2 ** <part-power>)。此外，我们还可以推断出更多关于必须进入故障域的 哪些 副本的信息。例如，考虑一个具有三个副本和两个区域的环，每个区域有两个服务器（总共四个服务器）。三个副本价值的分区将被分配到区域层中的两个故障域。每个区域必须持有某些分区的多个副本。我们将这种副本价值的分区的不完全分数以十进制形式表示为 1.5 (3.0 / 2)。这不仅告诉我们总分区的数量 (1.5 * 2 ** <part-power>)，还告诉我们每个分区必须在此故障域中至少有一个副本（实际上 0.5 的分区将有 2 个副本）。在每个区域内，两个服务器将持有 0.75 的副本价值的分区 - 这既等于“分配给每个区域的副本价值的分数 (1.5) 除以其子层中的故障域数量 (每个区域的 2 个服务器，即 1.5 / 2)” 也等于“总副本数 (3.0) 除以服务器层中的总故障域数量 (2 个服务器 × 2 个区域 = 4，即 3.0 / 4)”。重要的是要考虑，这个环中的每个服务器将仅持有 0.75 的副本价值的分区，这表明任何服务器都不应分配给定分区的最多一个副本。为了简洁起见，一些变量名通常会引用表示副本价值的分区分数（以十进制形式）的概念，称为副本分数 - 这旨在唤起类似于应用于分数的序数词的联想，但推广到副本而不是四*分之一*或五*分之一*。 “n”可能是因为《银翼杀手》而添加的。
构建环¶
首先，环构建器根据权重计算环拓扑中每个层所需的副本分数。
然后，环构建器根据分散性计算环拓扑中每个层所需的副本分数。
然后，环构建器计算单个设备在其加权副本分数和所需副本分数之间的最大偏差。
接下来，我们插值两个副本分数值（加权和所需）在每个层，使用指定的超载（达到最大所需超载）。这是一个线性插值，类似于求解两条点之间的线上的一个点 - 我们计算最大所需超载上的斜率，然后计算该线与所需超载的交点。这成为目标。
从目标值，我们计算任何分区在某个层中可能拥有的最小和最大副本数。这成为 副本计划。
最后，我们根据副本计划计算应分配给每个设备的理想分区数量。
在初始平衡（即，首次放置分区以生成环）时，我们必须将每个分区的每个副本分配给最需要分区的设备，排除已经将其最大数量的该分区的副本分配给该设备故障域的某个父层中的任何设备。
当基于旧环构建新环时，重新计算每个设备所需的分区数量，从当前的副本计划开始。接下来，收集要重新分配的分区。所有已删除的设备都将其分配的分区取消分配并添加到收集列表中。由于添加了新设备而可以更好地提高持久性而可以分散的任何分区副本将被取消分配并添加到收集列表中。任何拥有比现在需要的更多分区的设备都会从这些设备中随机取消分配分区并将其添加到收集列表中。最后，收集到的分区然后使用类似于上述初始分配中的方法重新分配给设备。
每当重新分配分区副本时，都会记录重新分配的时间。在收集要重新分配的分区时，会考虑到这一点，以便在可配置的时间量内不会移动任何分区两次。RingBuilder 类内部将此可配置的时间量称为 min_part_hours。对于已删除设备上的分区的副本，会忽略此限制，因为设备删除仅发生在设备故障时，并且别无选择只能进行重新分配。
由于重新分配分区的随机性，上述过程并不总是能完美地重新平衡环。为了帮助达到更平衡的环，重新平衡过程会重复固定次数，直到副本计划得到满足或无法满足（表明由于最近移动了太多分区而我们可能无法达到完美的平衡）。
复合环¶
请参阅 复合环构建器。
swift-ring-composer (实验)¶
swift-ring-composer 是一种实验工具，用于从其他现有的组件环构建器文件构建复合环文件。它的 CLI、名称或实现可能会在 Swift 的未来版本中更改或完全删除。
目前它的接口类似于 swift-ring-builder。命令结构的形式如下
swift-ring-composer <composite builder file> <sub-command> <options>
其中 <composite builder file> 是一个特殊的构建器，它存储复合环元数据的 json blob。此元数据描述了复合环中使用的组件 RingBuilder，它们的顺序和版本。
目前有 2 个子命令：show 和 compose。 show 子命令不接受任何其他参数，并显示复合构建器文件的当前内容
swift-ring-composer <composite builder file> show
compose 子命令是将组件环构建器缝合在一起以创建复合环文件和复合构建器文件的命令。命令的形式如下
swift-ring-composer <composite builder file> compose <builder1> \
<builder2> [<builder3> .. <builderN>] --output <composite ring file> \
[--force]
看起来可能有很多东西，但实际上很简单。 compose 命令通过 --output 选项接收要缝合在一起的构建器列表和复合环文件的文件名。 --force 选项覆盖环组合的检查。
要更改环设备，首先将设备添加到组件环构建器中，然后使用 compose 子命令创建新的复合环文件。
注意
swift-ring-builder 不能用于检查生成的复合环文件，因为没有与复合环文件名对应的常规构建器文件。您可以编程方式地使用 swift 环类查看复合环文件内部，或者使用以下命令从复合环文件创建临时构建器文件
swift-ring-builder <composite ring file> write_builder
不要使用此构建器文件来管理环设备。
有关更多详细信息，请使用
swift-ring-composer -h
环构建器分析器¶
这是一个用于分析环构建器在特定场景中执行其任务效果的工具。它旨在帮助开发人员量化环构建器的任何改进或回归；它可能对其他人没有用。
环构建器分析器接受包含环构建器的一些初始参数以及一定数量轮次的场景文件。在每一轮中，都会对构建器进行一些修改，例如添加设备、删除设备、更改设备的权重。然后，构建器会重复重新平衡，直到稳定下来。打印该轮次的数据，然后开始下一轮。
场景以 JSON 格式指定。逐步添加设备的示例场景
{
"part_power": 12,
"replicas": 3,
"overload": 0.1,
"random_seed": 203488,
"rounds": [
[
["add", "r1z2-10.20.30.40:6200/sda", 8000],
["add", "r1z2-10.20.30.40:6200/sdb", 8000],
["add", "r1z2-10.20.30.40:6200/sdc", 8000],
["add", "r1z2-10.20.30.40:6200/sdd", 8000],
["add", "r1z2-10.20.30.41:6200/sda", 8000],
["add", "r1z2-10.20.30.41:6200/sdb", 8000],
["add", "r1z2-10.20.30.41:6200/sdc", 8000],
["add", "r1z2-10.20.30.41:6200/sdd", 8000],
["add", "r1z2-10.20.30.43:6200/sda", 8000],
["add", "r1z2-10.20.30.43:6200/sdb", 8000],
["add", "r1z2-10.20.30.43:6200/sdc", 8000],
["add", "r1z2-10.20.30.43:6200/sdd", 8000],
["add", "r1z2-10.20.30.44:6200/sda", 8000],
["add", "r1z2-10.20.30.44:6200/sdb", 8000],
["add", "r1z2-10.20.30.44:6200/sdc", 8000]
], [
["add", "r1z2-10.20.30.44:6200/sdd", 1000]
], [
["set_weight", 15, 2000]
], [
["remove", 3],
["set_weight", 15, 3000]
], [
["set_weight", 15, 4000]
], [
["set_weight", 15, 5000]
], [
["set_weight", 15, 6000]
], [
["set_weight", 15, 7000]
], [
["set_weight", 15, 8000]
]]
}
历史¶
环代码经过多次迭代才达到现在的状态，虽然它在很大程度上保持稳定，但该算法也看到了一些调整，或者甚至可能随着新想法的出现而从根本上发生了变化。本节将尝试描述尝试过的先前想法并尝试解释为什么它们被放弃了。
曾考虑过“活动环”选项，其中每个服务器可以维护其自己的环副本，并且服务器将使用八卦协议来通信它们所做的更改。由于过于复杂且难以在项目时间范围内正确编码，因此放弃了此选项。一个错误很容易将错误数据八卦到整个集群中，并且难以恢复。拥有外部管理的环可以简化流程，允许在将其运送到服务器之前完全验证数据，并保证每个服务器都使用来自同一时间线的环。它还意味着服务器本身不必花费大量资源来维护环。
考虑了几个“环服务器”选项。一个是所有环查找都通过调用单独服务器或一组服务器上的服务来完成，但由于涉及的延迟，因此放弃了此选项。另一个类似于当前流程，但服务器可以向环服务器提交更改请求以构建新的环并将其运回服务器。由于项目时间限制以及环更改目前不频繁到足以手动控制，因此放弃了此选项。但是，缺乏快速自动环更改意味着系统的其他组件必须被编码为处理设备在数小时内不可用，直到有人可以手动更新环为止。
当前的环过程将每个分区的每个副本独立分配给设备。尝试了一种使用三分之一内存的版本，其中第一个分区副本直接分配，而其他两个副本是通过“在其他区域中遍历环”来确定的。由于失去了对给定分区有多少副本移动的控制，因此放弃了此选项。保持每个副本独立允许在给定的时间窗口内仅移动一个分区副本（由于设备故障除外）。使用额外的内存被认为是减少集群中数据移动的良好权衡。
还尝试了另一种环设计，其中分区到设备的分配不存储在内存中的大列表中，而是每个设备都分配了一组哈希或锚点。分区将从数据项的哈希确定，并且最近的设备锚点将确定应存储副本的位置。但是，为了获得合理的数据分布，每个设备必须具有大量的锚点，并且遍历这些锚点以查找副本开始增加。最终，内存节省并不大，并且使用了更多的处理能力，因此放弃了该想法。
还尝试了完全非分区环，但由于分区有助于系统的许多其他组件，尤其是复制，因此放弃了该环。可以批量复制分区副本并与其他副本一起尝试和重试，而不是单独尝试和重试每个数据项。可以计算目录结构的哈希值并与其他副本进行比较，以减少目录遍历和网络流量。
分区和独立分配分区副本也允许获得最佳平衡的集群。其他策略的最佳结果倾向于在设备权重相等时提供 ±10% 的设备平衡方差，在设备权重不同时提供 ±15%。我们当前的策略允许我们获得 ±3% 和 ±8%。
尝试了各种哈希算法。SHA 提供更好的安全性，但环不需要是密码安全的，并且 SHA 速度较慢。Murmur 速度更快，但 MD5 是内置的，并且哈希计算是整体请求处理时间的一小部分。总而言之，一旦决定服务器本身不会维护环，而只是执行哈希查找，MD5 就会因其普遍可用性、良好的分布和足够的速度而被选择。
对于无法平衡的环，放置算法经历了一系列行为上的变化。环构建器希望尽可能地将副本分散开，同时仍然尊重设备权重。在大多数情况下，环构建器可以同时实现这两点，但有时它们会发生冲突。最初的行为是保持副本之间的距离，并忽略设备权重，但这使得从一个区域逐渐过渡到两个区域，或从两个区域过渡到三个区域变得不可能。然后，它被更改为优先考虑设备权重而不是分散性，但这对于接近可平衡的环来说并不好，例如具有 60TB、60TB 和 57TB 磁盘空间的 3 台机器；操作员期望每台机器一个副本，但并不总是得到。之后，超载被添加到环构建器中，以便操作员可以选择分散性和设备权重之间的平衡。随着时间的推移，超载的概念得到了改进，并变得更加准确。
有关一致哈希环的更多背景信息，请参阅 构建一致哈希环。
