从一到无穷大 #42：ClickHouse - 极致工程优化的Lightning Fast Analytics

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

本作品 (李兆龙 博文, 由 李兆龙 创作)，由 李兆龙 确认，转载请注明版权。

引言

因为各种各样的事情快两个月没写文章，在春节假期前的最后一个周末怀着复杂的情绪动笔，着实和之前心如止水的搞技术不太一样。本命年还有一个多月结束，要问得到的人生意义是什么，大抵是把每一天当作最后一天来活，就少了很多毋须有的想法，整个人也就走到正轨去了。

ClickHouse当今的流行程度毋庸置疑，可以说是业界极致工程优化的代名词，ClickHouse - Lightning Fast Analytics for Everyone这篇论文整体的基调也是这样，即真正意义上的Industrial Paper，这并不是一个贬义词，虽然论文本身并没有提出什么新的想法，但是瑕不掩瑜，文章把工程上做的事情描述的非常全面，因为篇幅问题，每个点并没有解释的非常清楚，但是也不需要，因为使用到的不管是存储技术还是计算技术实际都是业界通用的，各家的实现情况只是权衡和人力的因素而已。

话说回来，世俗意义上“成功”开源项目的核心战略优势也在这里，有时自研项目的现状并不是眼高手低，而是确实有限的人力需要优先满足业务需求，大方向上也就是有所为有所不为，且必须要考虑ROI，这就进一步要求人效比，拿数据，所以我时常提起在大厂做开源项目云服务的同学是ToB圈子里相对更有开源成就感的人，Title上也更加好看，但同时思考差异化的压力也更大，这当然也告诉我们大可不必对很多开源明星有着不切实际的仰望之心。

论文开篇提出ClickHouse希望解决现代AP场景的几个核心挑战：

1. 海量数据的导入：要求高效的索引和压缩策略，分布式，而且因为近期数据一般更有价值，就需要利用物化视图，降冷等策略处理历史数据，保证实时查询的性能。
2. 同时执行的查询期望延迟较低：高时延要求的查询通常可以分为ad-hoc（一般翻译成即席查询）和重复查询。ad-hoc只能从查询优化和执行优化入手，这个之前一系列文章讨论过通用做法[10][11]。重复查询从我们的经验看可以改变数据分布，创建物化视图，基于历史查询创建Cache，还有一些查询预测的做法可以识别并预测相同模版查询的到来，从而做预取等操作。多个查询到来时优先级与资源分配，限制自然也是需要做的，否则总是会出现一个低优查询突发一堆高优查询被干掉，举个用户角度的例子就是告警请求影响到了页面交互，这在任何时候都是不应该的。
3. 开放性：为了与现有数据架构集成，现代分析数据库应该表现出高度的开放性，以读取和写入任何系统、位置或格式的外部数据。
4. 便捷的查询语言：更强大的SQL与性能分析工具。
5. 部署：需要提供数据复制，跨平台性，硬件兼容性，以及为了最大化裸机性能，最好使用Native语言来实现，而不是JVM类。

从我的角度讲，1，2是最重要的，因为这就是我现在正在做的事情，3也有点用，因为这和X-Stor的设计哲学是相辅相成的，X-Stor未来也需要这样一个模块，或许可以构建在AP引擎之上，这里的设计还需要再琢磨下。4，5则不是本篇文章的重点，不展开讨论，但是确实是一个开源项目得以成功的关键。

论文没有提出新想法，都是业界通用的做法，不过确实工程上可圈可点，所以本文的重点是看看CK团队认为哪些做法比较重要，即what和why，值得放在论文中，并附上我自己对这些特性的经验与想法。

模块划分

STORAGE LAYER

On-DiskFormat

MergeTree引擎的插入分为两种形式，同步插入的情况下每个Insert语句都会创建一个Part，异步插入和一般LSM的写入一致，维护内存memtable，基于大小和时间维度做下刷，后者适应于实时分析的场景，因为一般客户端无法接受批量导入的时延。

对于磁盘存储结构，都是老生常谈的东西，官方文档基本上描述的清楚了，想快一点看[1]也可以。

大致描述就是把8192个行定义为granules，这是最小的逻辑单位，主键索引就是这一层，但是读取的最小逻辑单位是Block，默认1MB，内部可能包含多个granules，块本身也可以被压缩，为了能够在压缩的情况下快速随机访问单个granules，ClickHouse 还为每一列存储了一个映射，该映射将每个granules ID 与其包含的压缩块在列中的偏移量以及granules在未压缩块中的偏移量关联起来。

列可以进一步进行字典编码或使用两种wrapper data types：

1. LowCardinality(T) 将原始列值替换为整数 ID，从而显著减少具有少量唯一值的数据的存储开销。
2. Nullable(T) 向列 T 添加一个内部位图，表示列值是否为 NULL

Data Pruning

文中提到了：

1. 主键索引：存储主键到granules ID的映射
2. Table projections：主键不同的另外一张表，可以加快筛选不同于主表主键列的查询速度，但会增加插入、合并和空间消耗的开销。查询优化器根据估计的 I/O 成本在从主表读取和投影之间进行选择。
3. skipping 索引：包括Min-max indices，Set indices，Bloom flter indices 具体细节可以参考[7]

Merge-time Data Transformation

文中提到了：

1. Replacing merges：去除重复主键行，默认删除时间戳较老的，也可以指定一个特殊的版本用作判断哪一行应该被留下。从[12]中可以看到因为行的去处是在compact时发生的，所以查询并不能确保完全没有重复值，这对于部分业务场景是致命的。
2. Aggregating merges：标准物化视图实现，可以参考官方文档的AggregatingMergeTree和SummingMergeTree，我们之前想做一个类似的事情，不同的是要支持first/last/mean等复杂算子，但是后续发现在存算分离的系统做物化视图完全没必要这样玩，直接搞几个计算节点跑SQL，结果写到目标表完事，隔离又好，速度又快，就是相对的实时性差一些。
3. TTL (time-to-live) merges：可以重新压缩，删除数据，或者把数据写入到更廉价的存储，这个地方想做的通用工程上还是要下不少功夫的，因为不是从一个log直接拿数据上传，而是需要把存量数据转换并上传到三方，过程中也要注意隔离和资源使用。之前我们的一种做法是在compact的时候判断ttl去做相关逻辑，不知道ck是怎么做的。

Updates and Deletes

1. Mutations rewrite：比较有意思的做法，就地重写表。为了防止更新导致的大小暂时翻倍，此操作是非原子的，即并行 SELECT 语句可以读取突变和未突变的部分，但是可预料到的开销非常大。
2. Lightweight deletes：轻量级删除仅更新内部位图列，指示行是否被删除，compact和查询的时候做过滤，可以从[13]中看到Presto这样的列存系统在做行删的时候对查询性能影响是很大的，因为查询的时候需要去掉被删除的数据。

Idempotent Inserts

客户端在将数据发送到服务器以插入表中后如何处理连接超时？在这种情况下，客户端很难区分数据是否成功插入。
前面章节提到的ReplacingMergeTree也可以处理这种情况，传统上，通过将数据从客户端重新发送到服务器并依靠主键或唯一约束来拒绝重复插入来解决该问题，由于这些数据结构索引每个数据项，因此它们的空间和更新开销对于大型数据集和高写入来说难以承受，所以CK有个轻量级的玩法，服务器维护最后插入的 N 个Part的哈希值，并忽略具有已知哈希值Part的重新插入。

Data Replication

文中给了一个简单的case：

1. Node1收到两个Insert语句，并写入复制流，为图中的1，2
2. Node2重放日志，为图中的3
3. Node2从Node1下载数据，为图中的4
4. Node3重防日志，为图中的3，5
5. Node3从Node1下载数据，为图中的4，6
6. Node3执行merge，并记录log，为图中的7

这里比较重要的一点是并不是简单同步log，然后把数据重放到引擎，这样的架构最大的问题就是几副本整个集群的开销就是几倍，所以实际的数据部分是从主来拉取的。如果有统一的持久化层负责可靠性，天生就拥有了这个能力，但可惜的是很多价格当前还是有类似的问题。

QUERY PROCESSING LAYER

极端简单的描述，基本上可以理解为啥也没说。

把查询的并行分为三层，分布式计划划分后的Node层面并行，多个Block的Core级别并行，Simd指令级并行。

node层面不谈了，simd层面上从[11]的DATA-PARALLEL EXECUTION (SIMD)章节中可以看到很多分析型场景的瓶颈是在数据访问，即IO层面，并不是计算层面，所以simd的优化并不是所有场景有显著效果的。

从Core层面并行来说，因为ck和Velox都是典型的Plan-Driven，而不是像duckdb那样的Morsel-Driven，所以必须要在计划生成的时候就指定好并行数，即同步点下pipeline的数量就是最大并行数。

论文中还描述了一些其他优化策略：

1. Query optimization：constant folding，extracting scalars from certain aggregation functions，common subexpression elimination, transforming disjunctions of equality flters to IN-lists
2. Query compilation：code-gen
3. Primary key index evaluation：淦，没看懂前两个优化，只看懂允许把部分函数比如toYear(k) = 2024转换为关键列的比较 k >= 2024-01-01 && k < 2025-01-01，利用排序性
4. Data skipping：利用Data Pruning提到的索引结构来跳过数据。
5. Hash tables：哈希表的实现对于aggregation 和 hash joins至关重要，ck的哈希表实现非常丰富，实现了三十多种哈希表，这个可以在后续有需求时仔细调研下。

Workload Isolation

ClickHouse ofers concurrency control, memory usage limits, and I/O scheduling, enabling users to isolate queries into workload classes. By setting limits on shared resources (CPU cores, DRAM, disk and network I/O) for specifc workload classes, it ensures these queries do not afect other critical business queries.
Concurrency control prevents thread oversubscription in scenarios with a high number of concurrent queries. More specifcally, the number of worker threads per query are adjusted dynamically based on a specifed ratio to the number of available CPU cores.
ClickHouse tracks byte sizes of memory allocations at the server, user, and query level, and thereby allows to set fexible memory usage limits. Memory overcommit enables queries to use additional free memory beyond the guaranteed memory, while assuring memory limits for other queries. Furthermore, memory usage for aggregation, sort, and join clauses can be limited, causing fallbacks to external algorithms when the memory limit is exceeded.
Lastly, I/O scheduling allows users to restrict local and remote disk accesses for workload classes based on a maximum bandwidth, in-fight requests, and policy (e.g. FIFO, SFC [32]).

Workload classes的思路是没问题的，Velox中没有这样的实现，在Velox中把不同的操作，比如访问对象存储，计算，spill等分为不同的folly::exector，以此做线程隔离，并没有IO级别的隔离。

但是在Velox中内存的限制基本和ck一致，使用树型的memory pool追踪全局的内存，并在查询超过单独设置的内存上限时触发Spill和MemoryArbitrator，以此为高优查询释放内存。

INTEGRATION LAYER

有两种方法可以使外部数据在 OLAP 数据库中可用:

1. push-based:第三方组件将数据库与外部数据存储连接起来，比如 ETL 工具，将远程数据转换格式后推送到目标系统。
2. pull-based:在基于拉的模型中，数据库本身连接到远程数据源并拉取数据以查询本地表或将数据导出到远程系统。

ck使用后者，确实是一个很有意思的功能，可以把远程存储当作本地表做查询或者写入，虽然没有技术难点，但是做到像ck这样支持五十多种外部系统的工程量是不可想象的。

总结

文章中讲到的东西很浅而广，聚焦于what和why，而不是how，不过也可以理解，篇幅就这些，想尽可能的照顾到更多的团队。当作AP入门文章还是很不错的，作为对平时日常工作有帮助的硬核技术文章就显得不够分量了，但是正好适合我现在这种脑子不太清醒的状态。

参考：

1. 透过ClickHouse学习列式存储数据库
2. ClickHouse - Lightning Fast Analytics for Everyone
3. ClickHouse 的第一篇研究论文：如何打造一款超高速的现代数据分析数据库？
4. youtube VLDB 2024 - ClickHouse: Lightning Fast Analytics for Everyone
5. youtube ClickHouse Meetup (Guangzhou, China) - ClickHouse: The What, Why, and How
6. ClickHouse - Lightning Fast Analytics for Everyone vldb2024
7. ClickHouse的索引原理
8. PAX：一个 Cache 友好高效的行列混存方案
9. PAX（Partition Attributes Across）
10. 从一到无穷大 #37 Databricks Photon：打响 Spark Native Engine 第一枪
11. 从一到无穷大 #39：从 Vectorized Mode vs Code Gen 权衡特定场景执行引擎技术选型标准
12. ReplacingMergeTree
13. 从一到无穷大 #41：大浪淘沙：Presto演进史

原文地址：https://blog.csdn.net/weixin_43705457/article/details/145216337

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！