ClickHouse 内幕(2)基础数据结构
ClickHouse 以性能好被大家所熟知,而一个数据库的性能优化是一个庞大的系统性工程。本文着眼于 ClickHouse 内部的基础数据结构,以揭露 ClickHouse 性能优化的冰山一角。
在软件工程中并不是所有的执行路径都需要优化,只有关键执行路径才需要花费大力气进行优化。对于数据库领域来说关键执行路径,一句话就可以概括,一个查询中对每行数据都需要执行的函数或者代码。而基础数据类型是关键执行路径上的算法的基础,所以对它们的优化对性能有重要影响。
PS:本文的讨论基于 ClickHouse 24.1。
最后更新于:2024-06-03
一、基础数据类型
根据实践经验有大概一半的列是字符串类型,所以字符串是一个重要基础数据类型。ClickHouse 是一个列式数据库,数据处理的过程中也是以列式进行处理,每个列的数据需要用数组表示,所以数组也是重要数据类型。
本文讨论 ClickHouse 的内部的重要基础数据类型:StringRef、PodArray。
二、StringRef
StringRef 的工作原理类似 std:string_view,它可以表示对字符串序列的引用,比如字符串 str=”abcdef”,那么 StringRef(str.data() + 1, 2)表示”bc”,请注意这里 StringRef 实际上没有对”nc”进行拷贝。
StringRef 被广泛运用在 ClickHouse 关键执行路径中,比如:内存中对于 String 类型列的表示 ColumnString、Aggregate 和 Join 算子用到的关键数据结构 HashMap 等。下图展示了 String 类型列中使用 StringRef,避免了数据拷贝。
![](https://static001.geekbang.org/infoq/c3/c3351f385696477e65a240dfcca05dda.png)
因为应用广泛,所以 ClickHouse 对 StringRef 进行了深度优化。
StringRef 最重要的操作是判断相等,所以判断相等的函数 memequalWide 是重点优化对象。如何判断两个字符串相等,ClickHouse 采用了批量处理的思路,而不是逐一对比每个字符。
1. size <= 16
当字符串长度小于等于 16 的时候,根据字符串的长度分成以下 4 中情况处理。主要思路是尽量将字符串当做比较大的数据类型(整型)做比较,以节约 CPU 计算周期。这么做的原因是 64 位 CPU 一次计算可以对比 8 个字符,将其当做较大的数据类型作比较可以最大限制的减小比较的次数。
由于不是所有情况 size 都能被数据类型的长度整除,对比前 n 个字节后,在再次对比后 n 个字节,这里是个很巧妙的设计,因为两次对比可以完成对所有字符的比较。
![](https://static001.geekbang.org/infoq/46/4686061d5947792606b63deaba04291e.png)
2. size > 16
![](https://static001.geekbang.org/infoq/7a/7a95b3843cb9b687f766fa22a48bef96.png)
1.对于大于 64 字节的部分使用 compare64,compare64 是 4 个 compare8 的组合。
2.对于剩余能被 16 整除的部分使用 compare8,compare8 是一个向量比较函数,使用 SSE2 指令集,一次对比两个 16 个字符的字符串。
3.使用 compare8 函数对比剩余部分的的后 16 个字符。
3. compare8 函数
通过 SSE2 指令集(SIMD 指令)一次性对比两个 16 个字符的数据是否相等。
三、PodArray
PodArray 是 ClickHouse 的自定义 vector,ClickHouse 中几乎所有的数据类型的列在内存中的表示都会用到 PodArray,所以 ClickHouse 对 PodArray 也是进行了大量的优化。
绝大多数细致的优化都是针对场景的,所以首先明确 PodArray 设计的应用场景,它主要用于存储列式的数据,ClickHouse 中列式的数据在内存中会划分为小的 Chunk,默认 Chunk 的长度是 6.5w 左右,总结下来 PodArray 主要用于存储大量的数据的类似 vector 的数据结构。
1. 支持 Stack 内存分配
因为栈的空间是有限的,传统的动态数组结构比如 std::vector,数据都是分配在堆上,这样的设计具有普适性,但是对数据的访问会有一次跳转,不利于数据 cacheline 的命中率。针对这一点 ClickHouse 提供了 Stack 上的内存分配方案 PODArrayWithStackMemory。
其工作原理如下。首先 PodArray 继承了 AllocatorWithStackMemory,AllocatorWithStackMemory 是一个内存分配器,其特点是当需要分配的内存小于一定阈值的时候使用栈上的空间,当大于阈值的时候分配对上的空间,并把栈上的数据拷贝到堆上。
2. Padding
PaddedPodArray 是带有 Padding 的 PodArray,其左右都填充了一些空白的内存空间,这些内存空间被初始化为了 0,其内存结构如下:
![](https://static001.geekbang.org/infoq/38/38ca09758e58ac270044df02ce9311ea.png)
2.1 left padding
ClickHouse 中有很多变长的数据类型,变长的数据类型指的是每个值的长度是不固定的,比如 String。对于这种数据结构在存储的时候需要存储一个 offset 数组和一个数据数组,如下:
![](https://static001.geekbang.org/infoq/f3/f3370e1bc8ee73f807d4098968ee90fd.png)
当需要获取某个元素的时候,需要计算元素的长度,计算方式如下:
每次都需要判断 i 是不是为 0,if 语句会大大影响 CPU 指令的 cache 命中率,并且不能触发编译器的自动向量化操作,从而影响性能。
当有了 left padding 后,代码可以优化为:
去掉了 if,消除了对 CPU 指令 cache 命中率的影响,同时如果循环调用,可以触发编译器的自动向量化操作。
PS:CPU 指令 cache 命中率对性能的影响可以参考:ClickHouse内幕(5)基于硬件的性能优化
PS:编译器自动向量化触发条件:requirements-for-vectorizable-loops
2.2 right padding
Right padding 设计的主要作用是提升 SIMD 指令函数的效率并简化编码。比如:一个简单的 SSE 版本的 memory copy 函数,在没有 right padding 的情况下,其实现可能如下:
但是如果 dst 和 src 各有 15 个 byte 的 right padding,那么实现可以优化为如下:
3. emplace_back 函数
PodArray 的函数,直接在末尾的内存空间上构建要插入的对象,相对提前构建好对象然后在拷贝到 PodArray 的方式减小了一次内存拷贝的开销。这个优化方式跟 std::vector 的 emplace_back 函数类似。
在创建对象的时候使用了 c++特性 placement new operator,其允许在指定内存地址创建对象。关于 placement new operator 请参考:stackoverflow。
版权声明: 本文为 InfoQ 作者【京东科技开发者】的原创文章。
原文链接:【http://xie.infoq.cn/article/12e437b1b600040343b1bf63b】。文章转载请联系作者。
评论