关于云原生:探索Snowflake-auto-clustering-设计

Context

Snowflake IPO 大火之后大家开始缓缓理解到这个齐全基于云架构而设计的旧式数据仓库。

Snowflake 利用云端近似有限的计算和存储资源，基于存算拆散的旧式架构，真正实现了按需、按量的付费模式，极大的升高了用户的应用老本，让用户更加专一于数据价值的开掘。对于传统的数据仓库来说，Snowflake 就像一块降维打击的二向箔。

在业务增长过程中，用户的数据持续增长，从而导致单表变大，查问的 SQL 模式也可能会发生变化，这时问题就呈现了：之前比拟快的查问当初变慢了。Snowflake 为了解决这个问题，提供了一个硬核性能：Auto Clustering，让你在建表时无需指定任何分区字段，而查问则越跑越快 。这里咱们就来摸索下 Snowflake 的 Auto Clustering 机制是如何实现的。

什么是 Auto Clustering

Snowflake 的 Clustering 性能和传统数据的 Partition 性能相似。但在传统的数据库系统中，大多依赖一些动态的分区规定来实现数据的物理隔离，如按工夫，按用户特色 hash 等等，在 Hive 等数据仓库中，最常见到的还是依照工夫分区。当一个带有分区字段相干查问过去的时候，分区的裁剪能够间接疏忽掉不匹配的数据，这样就能够大大减少了数据的读取和计算，从而进步查问性能。留神：这里的 Clustering 是指分组、聚类的意思，留神不要了解为分布式、集群等概念。

动态分区用法非常简单，比方在 Hive 中：

-- Create Partition
ALTER TABLE table_name ADD PARTITION(dt='2020-03-26',hour='08')location'/path/table/20200326/08';
-- Then load data into the partition

开发人员在建表的时候必须晓得数据的散布状况和未来面对的查问模式，减少了用户的心智累赘。它有以下毛病：

• 动态分区的规定是固定的，但数据却是随工夫在变动的，比方业务持续增长过程中，按天分区的表新的分区会变大，从而导致分区散布不平均。

Snowflake 在设计中齐全摈弃了传统的动态 Partition 概念，而是提出了 Auto Clustering 的新设计。简而言之，用户再也不必关怀我的表是如何分区了，用户只管写入和查问就是，数据分组，性能优化我会主动做！

Micro Partition（微分区）

尽管摈弃了动态分区，但 Snowflake 外面还是有 Micro-Partition 和 Cluster Key 的概念。

• Cluster Key 是排序键，能够由多个字段组成，相似 ClickHouse 的 Order Key。

• Micro-Partition 是数据的根本组成单元，一个表的数据由多个 Micro-Partition 组成。咱们能够将它了解为一个物理文件，这个物理文件限度在 50 MB-500 MB 的大小（未压缩），物理文件采纳了列式存储，不同的列存储在不同的间断空间内。Snowflake 会存储 Micro-Partition 的信息到元数据服务中，不便查问时通过元数据索引进行剪枝，如：

  • 每个列的区间索引，最大值、最小值等 (ZoneMap index）

  • 列散布的直方图信息

  • 其余..

Clustered Tables

数据表建设后，默认数据是天然序，天然序意味着咱们没有做任何解决，数据就依照流入的顺序排列，此时表处于 Unclustered 状态。当表经验了 Clustering 后，每个 Micro-Partition 会依照指定的 Key 进行排序，能够了解为给表加了一个排序键，此时表处于 Clustered 状态。

上图来自 Snowflake 文档。
Clustered 的次要目标是让大部分的查问能高效的裁剪数据，防止不须要的 IO 读取和计算。举个例子：

select name, country from t1 where type = 2 and date = '11/2';

怎么让表白到 Well-Clustered？在原始的数据排列中（天然序），下面的 SQL 会扫描到 4 个 Micro-Partition。而在 Clustered 状态下，数据曾经依照 Cluster Key->(date, type) 进行排序，所以只会扫描到 1 个 Micro-Partition，其余的 Micro-Partition 都被引擎联合了存储在元数据的索引进行了裁剪过滤。

一般来说，大表不会是动态的数据，大多会是时序数据，也就是说数据一直地实时流入。因而，对整个表级别的数据全排序是十分不事实的，不仅代价较高，实时流入的数据也会影响全排序后果。另外一种办法是只对流入的数据进行排序，这样尽管新数据有比拟好的程序，但随着数据在一直地流入，数据整体的程序会逐步趋于凌乱。

联合下面的剖析，一个表如果能达到 Well-Clustered（表数据的整体有序度高），这样查问能力高效。在这个前提下，还须要保障“新数据能实时高效流入”（确保 DML 高效），两者之间存在一个平衡点，Snowflake 的做法是优先保障新数据能实时高效流入，新数据是不须要对数据整体的有序度“负责”，因为新数据相比历史数据来说量级较小，影响的有序度也较小，它只需保障部分有序就行了（确保新数据查问也能高效）。新数据在后盾会异步进行合并，保障“表数据的整体有序度高”，也就是说，数据的整体有序是一个渐进的过程，而不是整体相对有序的。

如何掂量 Well-Clustered？

Snowflake 引入了几个次要的指标来掂量表的 Well-Clustered 水平：

• Overlaps: 在一个 Range 范畴内，有多少个 Micro-Partition 有重叠
• Depth: 在一个数据点中，有多少个 Micro-Partition 有重叠

下面的图从上到下展现了四种表 Cluster 的状态，第一种状况是 4 个 Micro-Partition 齐全重叠，这种状况是最蹩脚的，因为它没有任何区分度，命中了 A-Z 这个 Range 的查问会不可避免地扫描四个分区。随着 Depth 指标的降落，表中 Micro-Partition 变得逐步离散，Overlaps 指标也在降落，表也逐步变得更加 Well-Clustered。

当然，在理论的表散布中，Micro-Partition 的散布要达到最上面那样规整（全局有序）是不事实的，因为所须要的开销太大了。

• levels：Micro-Partition 所属的级别

为了缩小写放大，Micro-Partition 的合并策略和 LSM-tree 相似，Micro-Partition 在后盾一直地合并后造成新的 Micro-Partition，每次合并实现后，Micro-Partition 的 Level 值就会自增（clickhouse 也有相似的 Part 合并逻辑），所以 Level 示意的就是 Micro-Partition 经验过的合并次数（用来掂量经验过的合并老本）。新数据流入的 Micro-Partition Level 默认是 0，Level 越低的 Micro-Partition 中，Overlaps 和 Depth 指标相对来说会越高，在一直合并的过程中，Micro-Partition 变得越来越离散，表也变得更加 Well-Clustered。

留神：Micro-Partition 只会和同 Level 的 Micro-Partition 合并，Level 存在最大值，防止写放大太重大。Auto Clustering 是如何进行的

Auto Clustering 是如何进行的

Auto Clustering 次要分为两大工作：

• Part-Selection 工作
• Part-Merge 工作

这块和 ClickHouse 的逻辑很相似，但显著的区别是 Snowflake 对云切实太偏爱了，下面所有的工作都能够在云端拉起独立的过程进行，而不须要占用用户的计算资源，并且这两个过程也是微服务化的，能够按需弹性伸缩。

Part-Selection 工作

Selection 工作会从某个 Level 中抉择出 Micro-Partition 列表汇合，抉择的策略是启发式的。
下面提到的 2 个指标能够构建一个启发式的算法：

1. Level 低的 Micro-Partition 被抉择的优先级高，因而新流入的数据能有较高优先级合并到下个 Level，Level 越高的 Micro-Partition 除非在有短缺的资源状况下，否则不会被合并。
2. Depth 高的 Micro-Partition 被抉择的优先级高。

因而 Selection 的指标就是升高 Level 中 Micro-Partition 的均匀深度，AvgDepth。AvgDepth 又是如何计算的呢？
上面四个 Micro-Partition 的状况下：

咱们对每个端点进行剖析，如果没有 overlap，depth 疏忽，因为 depth 的目标就是掂量 overlap 的水平，引入 depth=0 会导致数据有偏差，此时 depth 示意一个端点笼罩了几个分区。

最终的计算形式是：

AvgDepth = Sum(DepthOfOverflapPoint) / OverflapPointsCnt

Snowflake 没有公开具体的 Selection 算法，不过大略是 Level+AvgDepth 联合的一个公式进行排序，咱们假如它是以每个 Level 的 AvgDepth 排序抉择某个 Level，而后去程序遍历此 Level 下的所有端点，超过了 AvgDepth 的间断端点会被抉择作为 Range。

• 下面的曲线是如何构建的？
  横轴对应的就是 Key 的 Range，纵轴示意 Depth，计算形式大略是：遍历所有的 Micro-Partition，将 Micro-Partition 的 Range 的 Depth 进行求和（即下面的 DepthOfOverflapPoint )，得出对应端点的 Y 值（这里应该能够用差分数组的数据结构进行优化）

• 抉择的策略是什么？
  上图是抉择了两个 Micro-Partition 列表的汇合示例，抉择的形式是程序遍历所有的端点，如果端点的 Depth 超过了 AvgDepth，就会被抉择，间断抉择的端点形成一个 Range。

• 为什么不间接选最高的 Depth？
  能够发现最高点 Depth 尽管最高，但笼罩的 Range 变窄，这样导致抉择的 Micro-Partition 数量太小，对升高 AvgDepth 的影响较少。

• 抉择的后果是什么？
  看有多少个符合条件的波峰，上图是两个符合条件的波峰，这两个波峰互不重合，能够作为抉择的后果汇合，汇合中内蕴含了 Micro-Partition 的 batches。
  ClickHouse 中也有相似的抉择策略算法，倡议读者有工夫也能够去理解下。

Part-Merge 工作

接管到 Selection 的列表后，Part-Merge 能够独立地进行 Micro-Partition 的排序和合并，相似一个归并排序的过程。合并后的 Micro-Partition 就是一个全局有序的大 Micro-Partition 了。值得一提的是，合并后的分区如果超过了 500 MB 的阈值下限，就会被决裂成更小的 Micro-Partition，这和 ClickHouse 存储一个大的分区文件是不同的。
猜想可能是：

1. Snowflake 和 ClickHouse 不一样，它不再保护 Micro-Partition 外部的稠密索引，稠密索引的最小粒度就是 Micro-Partition。
2. 在云端对象存储中，读取整个 Micro-Partition 比在 Micro-Partition 外部进行局部 Range 尽管 IO 开销稍大，但差别不会太大，而且对象存储个别都有对象级别的 Cache，所以 Snowflake 的元数据只存储了 Micro-Partition 粒度的索引。

其余

• 免费

Snowflake 的 Auto Clustering 尽管没有应用客户的计算资源，但费用还是要算在用户头上的，在 Billing & Usage 页面能够看到对应的计费状况。

• 易用性

目前，市面上大部分数据仓库都须要用户在建表时指定分区字段，预先判断数据的散布状况，这无疑减轻了用户的应用累赘，如果查问模式跟分区无关，做查问优化则十分艰难，Auto Clustering 则很好的解决了这些问题。

Databend 社区也在研发 Auto Clustering 性能，通过技术创新一直晋升产品的易用性和智能性。

相干配图，参考文章起源：

• Automatic Clustering at Snowflake

• How does automatic clustering work in Snowflake

• zero-to-snowflake-automated-clustering-in-snowflake

对于 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