Copyset Replication -- Curve的数据分布策略

Copyset模块结合chunk的放置共同解决了集群数据如何分布的问题，这里主要的设计考虑点是数据分布的均衡性以充分利用磁盘空间和避免热点。

1. 背景

Curve是网易数帆在2020年7月份开源的一个高性能、高可⽤、高可靠的分布式存储系统，主打高性能、低延迟。

Github代码仓库：https://github.com/opencurve/curve

Curve存储系统的基础设计框架与经典的GFS基本类似，采⽤有中心节点的架构，核心服务由4个部分组成：

• 元数据节点MDS，主要有两个职责，⼀⽅⾯管理和存储元数据信息，另⼀⽅⾯感知集群状态并进⾏调度。元数据存储在etcd中。
• 数据节点ChunkServer， ⼀⽅⾯负责数据的存储，另⼀⽅⾯负责数据⼀致性（如果底层是多副本，需要负责副本间的数据⼀致性）。在我们的实践中，一个chunksever对应与一块盘。
• 客⼾端Client， 向上层应⽤提供对⽂件的操作接口(open、read、write等)， 会和MDS以及ChunkServer交互，与MDS交互实现对元数据的增删改查；与ChunkServer交互实现对数据的增删改查。
• 快照克隆服务器独立于核心服务，对外提供了HTTP接口，用于处理和管理快照克隆任务。

在Curve系统中，存储资源被分成了一个个分片，称之为Chunk，典型的Chunk大小是16MB。为了实现数据高可用、高可靠，chunk通常会被复制多个副本，较为常见的是3个副本的配置，这样的三个副本的组合，叫做复制组，也就是我们称之为CopySet的概念。本文所描述的CopySet Replication指的就是一种复制组如何分布到上述这些ChunkServer上的一种算法。

CopySet Replication的概念在文献「Copysets: Reducing the Frequency of Data Loss in Cloud Storage」而来，本意是为了提高分布式存储系统中的数据持久性，降低数据丢失的概率。如下图所示。

该文献给出的copyset相关的几个术语：

• R : 副本数
• N : 节点数
• S : scatter width 每个节点的数据，复制到了多少个其他的节点
• copyset: 复制组，R个副本所在节点的集合
• permutation：集群N个节点的一个排列

还给出了一种copyset replication的算法：

首先，每次排列的每两个copyset之间只有一个重复的节点，例如{4，5，6}和{3，6，9}之间重复的节点是6。这保证了每增加一个copyset增加该节点的scatter width的R-1。

其次，这种模式（scheme）确保了copyset均匀地覆盖所有节点。因为每一次permutation为scatter width增加R-1，那么总的scatter width为S = P * (R-1)，其中P为permutation的次数。总共的copyset数为P(N/R)=(S/(R-1))(N/R)。

2. curve的copyset生成策略

2.1 设计目标：

copyset生成策略的设计目标是创建集群的一个均衡的初始分布，达到几个目的：

1. copyset需满足故障域约束的要求
2. 每个ChunkServer的copyset数量保持一致
3. 每个ChunkServer的scatter-width满足故障恢复的要求，并且尽可能的均衡

Copyset模块结合chunk的放置共同解决了集群数据如何分布的问题，这里主要的设计考虑点是数据分布的均衡性以充分利用磁盘空间和避免热点。

2.2 核心概念：

2.2.1 copyset

• Copyset指的是复制组，底层ChunkServer使用的是Raft分布式一致性算法，因此，copyset实际上也就自然对应了底层一个raft group。
• 每若干个ChunkServer组成一个copyset，每个ChunkServer上会有多个copyset，也就是说copyset跟ChunkServer是多对多的关系。
• copyset没有一个容量的概念，可以类比桶的概念，chunk可以落到的copyset对应的桶里面。当集群满载的情况下，最终copyset内最大会有多少数据，取决于总的空间除以copyset的数量。

2.2.2 physicalPool

• 物理池是我们扩容的基本单元，也就是一次扩容一个physicalPool。
• 物理池内包含若干台服务器，每台服务器上具有若干个ChunkServer节点。

2.2.3 logicalPool

• 在物理池之上，我们会创建logicalPool和copyset。
• copyset属于逻辑池，每个逻辑池一开始创建固定数量的copyset。
• copyset Id 在逻辑池内唯一，逻辑池Id + copyset Id 唯一确定一个copyset。

2.2.4 Zone

zone指的是curve的故障域，它是一个逻辑概念，zone可以对应到一个实际的物理机架，实现机架级别的物理隔离。

2.2.5 scatter-width

• scatter-width 指的是一个节点上的数据分布到了多少个其他节点上，它表示的是一个节点上的数据分布的分散程度。
• scatter-width 越大，当节点发生故障时，可用于恢复的其他节点数就越多，也就是说scatter-width决定了节点故障时，可用于恢复的并发度。

2.3 copyset生成策略实现

Curve的Copyset生成策略借鉴了「Copysets: Reducing the Frequency of Data Loss in Cloud Storage」中的Copyset算法，并扩展考虑了故障域的设计。其设计基于以下几点考虑：

2.3.1 生成固定数量的copyset

固定数量的copyset是很重要的一个抉择点，根本考虑点是相对于动态数量的copyset方法，更简单，并且实践证明也是够用的。

• 首先创建远超实际节点数的copyset数，均匀分配到每个节点。
• 如果集群中添加了一个新节点，该新节点可以从每个现有的节点上匀走几个copyset，直到copyset再次达到全局平衡。
• 如果从集群中删除节点，则采取相反的均衡措施。

固定数量copyset带来的问题：

• 第一个问题是，当逻辑池内节点数不断增加时，每个节点上的copyset数量就会不断减少。所以只适用于逻辑池节点数相对变化不大的情况。目前Curve扩容是主要是按照扩pool的方式进行，因此不会有这个问题。
• 第二个问题是，初始的copyset数量的确定。这个我们是根据scatter-width的要求来确定的，有两种方式，一种方式是根据scatter-width的要求，生成满足scatter-width的最小copyset数量，还有一种方式是指定copyset数量，验证生成的copyset是否满足scatter-width的要求。其中scatter-width的计算可以依据SLA的要求即故障恢复时间和预留恢复带宽来计算。目前我们的计算结果来看，scatter-width所要求的copyset数量是较少的，一般每个ChunkServer 100个copyset就完全能满足scatter-width的需求，可以说对copyset的约束是比较宽的，我们可以较轻松的选择copyset数量。

2.3.2 在故障域内，基于随机化方法生成copyset

首先要均衡，那么最简单的方法就是随机。但是我们又需要满足故障域的要求，因此，我们采用在故障域内随机。本身故障域内的机器数量是基本均衡的，因此在故障域内随机，总体上仍然能达到均衡。

我们使用3个参数来表示copyset生成的故障域约束：

• 故障域数: ZoneNum
• 副本数: ReplicaNum
• 副本放置到多少个故障域: ZoneChoseNum

其中ZoneChosenNum <= ZoneNum是一定的。

一般来说ZoneChoseNum == ReplicaNum, 但是也存在例如在有3个故障域的集群中将3副本放在2个故障域中，即ZoneNum=3， ReplicaNum=3，ZoneChoseNum=2的情况，因此此处是3个参数。

目前Curve的代码实现中，只支持ZoneChoseNum == ReplicaNum的情况。

首先来考虑一种最简单的情况：对于一个有3个故障域的集群，集群的副本数未3副本，并且分布方式是该3副本分布到3个故障域中，那么ZoneNum=3， ReplicaNum=3，ZoneChoseNum=3。

1. 首先对集群的节点按照故障域分为3个组。
2. 对3个组各自进行随机排列。
3. 按照各个组依次取一个节点的方式，组成3副本，生成一个copyset。
4. 当取完全部copyset后，重复从第2步再次执行排列。
5. 当取到的copyset数量满足给定的copyset数量后，即完成了一次copyset的生成。

那么将上述推广到，ZoneNum = ANY，ReplicaNum == ZoneChoseNum <= ZoneNum 的情况，第3步骤中将按照如下顺序选取各个zone中的节点:

    zone1    zone2    zone3    zone4   ...  zoneN
     1        2        3         4     ...    N
    N+1      N+2      N+3       N+4    ...   2N
...      ...      ...       ...    ...   ...

2.3.3 使用一系列度量来衡量算法的好坏，重试直到得到一个合理的结果

当我们通过随机化的方法生成了copyset以后，如何确保copyset以及scatter width的均衡性？
这里就通过一系列的度量指标去判断。这些指标包括：

• scatter-width的方差与标准差
• scatter-witdth的极差
• scatter-witdth偏离均值百分比

当每次生成copyset时，计算上述一向或多项指标（根据配置），判断生成的copyset是否满足上述指标，如果不满足，则重试生成copyset，直到满足上述指标为止。

这一步骤的流程图如下：

3. scatter width的计算

最后，至关重要的就是scatter-width的计算，scatter width越大，恢复带宽越大，scatter width 表示的是最大同时有多少个copyset可参与恢复。因此:

总恢复带宽 = scatter width * 单个copyset的恢复带宽，
scatter width = 总的恢复带宽 / 单个copyset的恢复带宽  =  （数据容量 / 期望恢复时间）/ 单个copyset的恢复带宽

假设节点每个盘4T，恢复时间3600s，单个copyset的恢复带宽为10MB/s，那么S = (4 * 1024 * 1024) / 3600 / 10 = 116.51，这是scatter width的下限。
下表列出了以单个盘（ChunkServer）大小为4T情况下,单copyset恢复带宽从5MB/s至100MB/s, 恢复时间从1800s至7200s所需scatter width下限：

作者简介：许超杰，网易数帆资深系统开发工程师，自研分布式存储系统Curve的核心开发。