背景
Databend Clustering 的设计受到 Snowflake Data Clustering 和 Oracle Attribute Clustering 的启发。
注：这里的 Clustering 是分组、聚类的意思，下文将译为聚类。
聚类后的表会依据表中某一组列的值，以某种顺序存储数据。聚类有利于分区的打消（partition elimination）和文件碎片整顿（file defragmentation）。默认状况下，数据是依照天然维度存储在表中的。因而，须要依据聚类键（cluster key）对表进行重聚类。另一方面，即便表曾经聚类过，数据失去无效地组织，但如果一直地写入新的数据，聚类状况会随着工夫的推移而变差。因而，有必要减少重聚类（recluster）操作。
设计
如果打算理解更具体的原理和图景，请参考 摸索 Snowflake auto clustering 设计 一文。
执行全表排序的老本十分高，尤其是对于一直有新数据流入的表。为了在高效剪枝和低成本之间获得均衡，只须要对表进行粗略排序而不是齐全排序。因而，在观测指标 一节中引入了两个指标来确定表是否曾经无效聚类。从新聚类的目标是为了缩小重叠 “overlap“ 和深度 “depth"。
为了防止对同一份数据进行屡次搅动，这里将数据块划分到不同的层（level），就像 LSM 树一样。那么重聚类就与 LSM 树的压缩操作相似。层示意该块中的数据被聚类的次数。重聚类操作是在同一层上进行的。
pub struct ClusterStatistics {
... ...
pub level: i32,
}重聚类操作的工作流程能够划分为两个工作：块抉择（Block Selection）和块合并（Block Merge）。
语法
alter table [if exists] tbl_name recluster [final] [where condition] 如果指定 “final"，那么优化将会重复执行直到该表的聚类水平足够好。否则，重聚类的工作流程将只会运行一次。
观测指标
"overlap“ 与指定块重叠的块数。"depth“ 在同一点重叠的块数。这些点是从聚类值域范畴中的最小值和最大值中收集的。
块抉择
新流入的数据的初始层是第 0 层（level 0）。咱们首先要关注的就是这些较新的数据，换句话说，抉择操作优先在第 0 层执行。这样做的长处是能够缩小写放大。1. 计算每个点的深度和重叠的块数，汇总失去 “avg_depth"。这个算法曾经反映在 system$clustering_information 中，这里不再进行复述。avg_depth 的现实后果是 1。为了实现粗略排序，须要定义一个阈值（threshold）或者是一个比率（ratio）（”threshold = blocks_num * ratio"）。只有 “avg_depth" 不大于该阈值。就认为这一层中的块的聚类水平足够好，那么咱们将对下一层执行块抉择。2. 抉择深度最大的点范畴（一个或多个）并抉择该范畴所笼罩的区块作为下一次块合并的对象集。如果存在不止一个的深度最大的范畴，那么在块合并过程中，可能会呈现多组块并行的状况。
Tip:
- 聚类键（cluster key）可能会在表中存在数据的时候创立 / 变更，故而可能存在一些没有按聚类键进行排序的块。目前打算是在重聚类过程中临时疏忽这些块。
- 如果某个块的聚类键只有一个值（最大值和最小值相等，达到一个不变的状态）且行数 “row_num” 为 “1_000_000”，那么重聚类时，将其所处层数设为 -1 并过滤掉。
- 须要思考选定的块的总大小，免得在排序时遇到内存溢出（out of memory, OOM）。
块合并
接下来就须要对收集到的块进行排序和合并。当合并后的块超过某个确定的阈值（”1_000_000" 行）之后，就会进一步拆分成多个块。新生成的块放入下一层。而后，咱们须要组织块并生成新的段和快照，最初更新表的元信息。如果在此期间有新的 DML 执行，以后的工作流将无奈提交（commit），并返回谬误。具体的解决流程依然须要进一步的探讨。抉择和合并操作会反复进行，直到表的聚类水平足够好。
回顾
这篇 RFC 介绍了 Databend 反对 Recluster Table 的背景，以及重聚类操作的相干设计和工作流程。重聚类的第一版代码实现能够查看 https://github.com/datafusela…，Databend 自 v0.8 起正式提供对重聚类的反对。
对于 Databend
Databend 是一款开源、弹性、低成本，基于对象存储也能够做实时剖析的旧式数仓。期待您的关注，一起摸索云原生数仓解决方案，打造新一代开源 Data Cloud。
- Databend 文档：https://databend.rs/
- Twitter：https://twitter.com/Datafuse_…
- Slack：https://datafusecloud.slack.com/
- Wechat：Databend
- GitHub：https://github.com/datafusela…
文章首发于公众号：Databend