概念： "云" MergeTree 表

MergeTree 云表的核心特性在于无需手动控制集群上数据的分片方案。云表中的数据会自动分布在整个集群中，同时为特定键提供数据局部性。

1. 创建云表后，它会在集群的所有节点上可见。无需手动在每个节点上创建单独的分布式表和本地表。
2. 当向云表中导入数据时，如果表非常小，数据会分布在几个集群服务器上，但随着数据量的增长，会涉及更多服务器（例如，每个服务器从千兆字节开始）。用户可以创建一个小表，这操作不应过于繁琐；但在创建表时，我们无法预先知道将向其中加载多少数据。
3. 用户指定一个分片键（任意元组）。分片键范围（按字典序）的数据位于某些服务器上。非常小的范围位于多个服务器上，访问它只需读取单个服务器上的数据即可，而足够大的范围则分布在所有服务器上。例如，如果我们谈论的是网络分析，分片键可能以 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 来做出决定。为了减少问题，可以稍微随机化决定重新分区的时刻。需要额外拆分虚拟碎片的标准结果并不简单。例如，您可以很快将碎片拆分到服务器数量 * 复制率，方法是将碎片增长到几个 GB。但即使当碎片的大小为服务器大小的 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 MB）来解决。可以提出在不同磁盘上的不同块中单独分布数据的方案。但设计和仔细实现它太困难了。可能最好不要做整件事，并且至少要确保在 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。例如，如果分片键是哈希（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 个部分，然后将其映射到两个分片中。目前尚不清楚这将如何工作。