概念：“云” MergeTree 表

MergeTree 云表的主要特性是，它不对集群上数据的分片方案进行手动控制。云表中的数据在集群中自行分布，同时为特定键提供本地性属性。

1. 创建云表使其在集群的所有节点上都可见。无需在每个节点上手动创建单独的 Distributed 表和本地表。
2. 当将数据摄取到云表时，在表非常小时，数据会分布在多个集群服务器上，但随着数据增长，会涉及更多服务器（例如，从每服务器千兆字节开始）。用户可以创建一个小表，它不应该太繁琐；但是，在创建表时，我们事先不知道将加载多少数据到其中。
3. 用户指定分片键（任意元组）。分片键范围（按字典顺序）的数据位于某些服务器上。非常小的范围位于多个服务器上，访问它只需从单个服务器读取数据即可，而足够大的范围则分布在所有服务器上。例如，如果我们谈论的是 Web 分析，则分片键可能以 CounterID（网站标识符）开头。像 https://yandex.ru 这样的大型站点的数据应分布在集群中的所有服务器上，而小型站点的数据应仅位于少数服务器上。物理解释：集群应扩展以同时为重型查询提供吞吐量并处理轻型查询的高 QPS，并且对于轻型查询，延迟不应受到影响。通常，这称为数据本地性。
4. 重型查询可以使用集群中的所有服务器，而不是 1 / N，其中 N 是复制系数。因此，一台服务器可以包含不同分片的多个副本。
5. 当用空服务器替换服务器时（节点恢复），数据恢复必须以某种方式并行化。至少读取应分布在不同的服务器上，以避免单个服务器过载。
6. 在每个本地服务器上，读取主键范围应该接触不太多的文件范围或不太小的文件范围（最大程度地减少磁盘寻道）。
7. （可选）能够使用单个磁盘而不是 RAID，但同时在读取中等大小的主键范围时保持吞吐量，并在读取小尺寸范围时保持 QPS。
8. 能够创建具有通用分片方案的多个表（协同分片）。
9. 在添加新服务器时重新平衡数据；在旧服务器长时间不可用时创建额外的副本。
10. SELECT 查询不应需要对协调器的同步请求。在数据重新平衡操作期间，SELECT 查询看不到重复或丢失的数据。
11. 考虑到分片键的条件和当前分片方案的知识，SELECT 查询必须选择足够大的服务器子集。
12. 能够有效地在可用磁盘空间不均的服务器之间分配数据。
13. 集群上 INSERT 的原子性。

超出范围且不予考虑

1. 用于复制和恢复的擦除数据编码。
2. 在具有不同磁盘的系统上进行数据存储 - HDD 和 SSD。一个例子是在 SSD 上存储新数据。

类似的问题通常（在 Map-Reduce 或 blob 存储系统中）通过将数据组织成块来解决。块位于集群的节点上。映射：表或文件 -> 块，块 -> 节点，存储在主节点中，主节点本身可以复制。主节点观察节点的活跃性并维护所有块的合理复制级别。

当块太多时，会出现困难：在这种情况下，主节点无法应对元数据的存储和负载。有必要进行复杂的元数据分片。

在我们的案例中，似乎很想用类似的方式解决问题，其中使用包含数据范围的 MergeTree 类型表的实例来代替块。其他系统中的块称为“平板”或“区域”。但是这有很多问题。一台服务器上的块数量不能太大，因为那样会违反属性 - 最大程度地减少读取数据范围时的寻道次数。问题还来自于每个 MergeTree 表本身都相当繁琐并且由大量文件组成的事实。另一方面，如果维护数据本地性属性，则大小为 1 TB 的表或多或少是正常的。也就是说，如果一台服务器上的多个此类表开始仅用于不太小的数据范围。

各种选项可用于分片数据，包括：根据参数数量较少的公式进行分片。示例是简单哈希、一致性哈希（哈希环、会合哈希、跳转一致性哈希、sumbur）。在其他系统中使用实践表明，纯粹形式的这种方法效果不佳，因为分片方案的可控性差。例如，非常适合缓存。它也可以用作另一种算法的一部分。

相反的选择是将数据分成使用显式指定的表的分片。该表可能包含键范围（或者，在另一种情况下，来自键的哈希范围）及其相应的服务器。这在选择何时以及如何传输数据方面提供了更大的自由度。但与此同时，为了扩展集群，必须动态扩展表的大小，从而打破现有范围。

一种组合选项是，映射由两部分组成：首先，将各种键的集合划分为一些预先固定的不太少且不太多的“虚拟分片”（您也可以称为“逻辑分片”、“迷你分片”）。此数字比服务器数量的假设集群大小大几倍。此外，第二个映射显式指定每个迷你分片在服务器上的位置，并且可以任意控制第二个映射。

这种方法的复杂性在于，划分哈希范围会产生均匀性，但不会为范围查询提供数据局部性；而当按键范围拆分时，很难预先选择均匀分布，因为我们不知道数据到键的分布是什么。也就是说，如果需要数据局部性，则选择预先固定的拆分为迷你分片的方法不起作用。

事实证明，在我们的案例中，唯一可接受的方法是按键范围进行分区，键范围可以动态更改（重新分区）。同时，为了更方便、可管理和数据分布的均匀性，分区元素的数量可以略大于服务器的数量，并且可以单独更改从分区元素到服务器的映射。

每个 ClickHouse 服务器都可以参与某个云。云由文本字符串标识。通过在节点上创建某种类型的数据库 (IDatabase) 可以确保节点在云中的成员身份。因此，一个节点可以在多个云中注册。在协调器中维护在云中注册的节点注册表。

选择云节点以容纳云表的分片的副本。节点还向协调器发送一些附加信息，以便在放置数据时进行选择：确定网络中位置的路径（例如，数据中心和机架）、磁盘空间量等。

云表在云中注册的相应数据库中创建。该表在任何服务器上创建，并在云中注册的所有数据库中可见。

在创建云表时为其设置分片键，任意元组。有时分片键与主键匹配是实用的（例如 - (CounterID, Date, UserID)），有时不同的分片键是有意义的（例如，DateTime 主键，分片键 - UserID）。

分片是多个映射的组合

1. 所有可能的元组的集合，分片键的值，被映射到许多半区间，这些半区间打破了半区间 [0, 1)。最初，这个数字是分区的大小，它等于 1。也就是说，所有值都映射到单个半区间，即整个集合 [0, 1)。然后，随着表中数据量的增加，半区间（即拆分元素）可以通过字典顺序的值分布的中位数大致减半。
2. 对于每个半区间拆分，选择几个云服务器并以某种方式记住，将在这些服务器上放置相应数据的副本。选择是根据服务器在网络上的位置（例如，至少两个副本在不同的数据中心，所有副本在不同的机架中）、已在此服务器上创建的副本数（选择副本数最少的服务器）和可用空间量（从各种服务器中仅选择可用空间量最大的服务器）进行的。

结果，此组合形成了从分片键到多个副本服务器的映射。

假设在此过程中，此映射的两个部分都可能发生变化。

映射 1 的结果可以称为“虚拟分片”或“逻辑分片”。在工作过程中，虚拟分片可以减半。反方向是不可能的 - 虚拟分片的数量只能增长。假设即使对于占用整个集群的表，虚拟分片的数量也将比服务器的数量大几倍（例如，它可能比复制比率大 10 倍）。占用至少十分之一所有数据的数据范围应分布在所有服务器上，以确保重型查询的吞吐量。整个映射由分片键的边界值集指定。此集合很小（大约千字节），并存储在协调器中。

虚拟分片在真实服务器上的映射可以任意更改：当服务器长时间不可用时，副本数量可能会增加，或者增加然后再减少以在服务器之间移动副本。

以下列表项对应于上面的要求编号

1. IDatabase 同步转到协调器以获取或更改表列表。云表列表存储在协调器中云对应的节点中。也就是说，云中的所有表在进入云的每个服务器上都可见。
2. 通过以下事实来确保这一点：最初，分区由单个元素组成，但随着数据量的增加，分区开始进一步分解。负责本地存储此数据的每个副本都可以在达到数据量标准后启动拆分。多个副本可能会竞争性地决定执行此操作，并且使用原子 CAS 做出决定。为了减少问题，可以稍微随机化决定重新分区的时刻。何时需要额外分解虚拟分片的标准变得不那么简单。例如，您可以很快分解到服务器数量 * 复制率，方法是将分片增长到几个千兆字节。但是，即使分片的大小是服务器大小的 1 / N（例如，大约 1 TB），也值得分解分片。在协调器中，您应该立即存储最后一次拆分和上一次拆分，并且不要过于频繁地进行拆分。
3. 通过虚拟分片的数量将比服务器数量多几倍（用户定义）来确保这一点。注意：对于额外的数据传播，您可以对分片键施加一些传播转换。尚未考虑周全。例如，不要使用键 (CounterID, Date, UserID)，而是使用分片 (hash (UserID)% 10, CounterID, Date, UserID)。但在这种情况下，即使是小的 CounterID 也会落入 10 个范围。
4. 类似地。
5. 如果多个虚拟分片位于单个服务器上，则它们的副本将分布在更多服务器上，并且在恢复期间，将有更多的扇出。
6. 小型请求将使用一个分片。而大型请求将使用同一服务器上的多个分片。但是由于每个分片都会小一些，因此 MergeTree 表中的数据可能会由较小的部件集表示。例如，我们现在最大的部件大小为 150 GiB，对于大型表，在一个分区中会形成许多这样的大块。如果有多个表，则每个表中的大块数量会更少。另一方面，当插入数据时，将在每个服务器上生成更多的小部件。这些小部件将导致寻道次数增加。但不多，因为新数据将在页面缓存中。这就是为什么每个服务器的虚拟分片过多可能无法很好地工作的原因。
7. 非常困难。您可以在同一服务器的不同磁盘上拥有相邻分片组。但是，然后中等大小范围的读取将不会并行化（因为整个范围将在一个磁盘上）。在 RAID 中，问题通过块大小相对较小（通常为 1 兆字节）来解决。可以提出在不同磁盘上的不同部件中单独分布数据。但是，仔细设计和实施太困难了。可能最好不要做所有事情，并且至少要做到在 JBOD 服务器上，选择一个服务器磁盘来放置一个分片。
8. 可以使用一个字符串来标识分片方案，该字符串可能在不同的表之间通用。拆分分片的标准是根据具有相同分片方案的所有表的总数据量确定的。
9. 通过更改虚拟分片在服务器上的映射来完全解决此问题。此映射可以独立于其他所有内容进行控制。
10. 服务器可以缓存分片映射（其两个部分）一段时间，并通常异步更新它。当由于虚拟分片的拆分而重新平衡数据时，您应该将旧数据保留更长时间。在服务器之间传输副本时也是如此。根据请求，发起服务器还会询问远程服务器是否具有必要的数据：根据发起服务器缓存的分片方案，所需分片的数据。对于查询，选择每个分片的一个活动副本，其中有数据。如果突然没有，则值得同步更新分片映射，因为由于某种原因，所有副本都被转移到某处。
11. 这很简单。
12. 它是基于以下事实解决的：一个服务器负责多个分片，并且分片副本在服务器之间的分布或多或少是任意的，并且可以考虑磁盘空间量。

要将数据摄取到表中，您可以将 INSERT 查询发送到任何服务器。数据将被划分为范围并记录在所需的服务器上。同时，同步确保我们使用最新的分片映射 - 在插入数据之前请求它，并在 ZK 中提交时检查它是否未过期。

当使用 SELECT 查询时，如果使用了旧的分片映射，则最新数据将不可见。因此，应使 SELECT 的分片映射的异步更新间隔可自定义，并且应添加一个选项以同步使用最新的分片映射。

对于相当大的表，事实证明，INSERT 请求会将数据分解为许多小部件并写入所有服务器（示例：使用 500 台服务器，您需要提交 5000 个分片副本）。这应该可以工作，因为一个分片的所有副本不可访问或抑制的可能性仍然很低。但这将工作缓慢，并且可能不稳定。如果有大量 INSERT，则协调器上的负载将非常可怕。虽然它可以正常承受每秒一次 INSERT。为了实现 INSERT 的高吞吐量，只需使它们并行即可，但总体上保持相同的低 INSERT 频率。然而，这仍然是一个大问题。

以下是可能的解决方案

1. 您可以在分片键的开头添加一些内容。例如，Date % 10 或 toMinute。然后，INSERT 将接触较少的分片（在插入最新数据的典型情况下），但同时在某些时间间隔内，某些分片将比其他分片更热。通常，如果它减少了活动分片的数量，例如，从 INSERT 上的 5000 减少到 500。这对用户来说也非常不方便。
2. 您可以提出某种难以理解的分片方案，其中新数据首先落入一些新的分片中，在该分片中不清楚从哪里开始，然后懒惰地覆盖它。新分片本质上是一个分布式队列。同时，始终请求 SELECT 的新分片。不太好。而且，它仍然与 SELECT 中可见的这些数据传输的原子性相矛盾。或者，如果您允许 SELECT 看不到某些新数据，则可以放宽要求。看起来它通常在超过 500 台服务器的集群大小下无法很好地工作。另一个问题是，为了正确传播主键的范围，虚拟分片的数量必须不小于服务器数量的平方。这太多了。如何解决这些问题 为了分片，您可以添加更多中间映射。以下是一些选项
3. 以任意方式将每个分片拆分为一组分片。例如，10 个部件。这相当于在分片键的开头添加一个随机数 0.N-1，这意味着什么都没有。然后，使用 INSERT，您只能插入到一个随机选择的分片、最小尺寸的分片或某种轮循调度中；结果，INSERT 变得更容易。但这增加了所有点 SELECT 的扇出。为方便起见，可以动态完成这种分区 - 只有足够大的分片才能以这种方式划分（这将有助于避免在分片键以 Date 开头且数据按 Date 顺序插入的情况下过度拆分旧分片）或者从分片数量足够大的情况开始执行这种分区（对扇出 INSERT 请求的顶部限制）。另一个优点：在具有 JBOD 的服务器的情况下，可以优先将此类二级分片放置在一个服务器的磁盘上，这半模拟了 RAID-0。但有一个严重的缺点：无法执行本地 IN / JOIN。例如，如果分片键是 hash (UserID)，并且我们按 UserID 执行 JOIN，则假定此可能性。可以通过始终将所有“对称”分片放置在一台服务器上来避免此缺点。
4. 一种在保持虚拟分片数量的同时传播数据的映射。此映射的本质如下
   • 设置传播因子，例如，N = 10. 作为第一个映射，生成 10 倍以上的范围。例如，如果我们想要最终得到 7 个分片，那么我们将数据划分为 70 个范围。
   • 然后，这些范围在圆圈中以数字 0.6 重新编号，并且具有相同编号的范围将落入一个分片中，结果，将再次有 7 个分片。
   • 此映射的连续模拟：x in [0, 1) -> fractional_part (x * N)，在圆圈上乘以 N。

如果您在笛卡尔坐标系中的图片上绘制它，您会得到一个带有 10 个齿的“锯齿”。

在此之后，显而易见的是，此映射同时传播数据并保留其局部性。

另请参阅：Arnold's cat map。

但是这里描述的内容并不完全奏效。首先，在积累足够的数据之前，不可能创建均匀划分的部件（没有地方可以计数分位数）。其次，根据如此简单的方案，不可能划分间隔。

有一种选择，其中不是将范围分成两半，而是将其分成 4 个部分，然后映射到两个分片中。目前尚不清楚这将如何工作。