ClickHouse计算速度是如何做到领跑OLAP类产品的

数据分析类产品的发展历史

image.png

单机数据库时代

关系型数据库是发展了很多年的技术，在单机时代，微软的sql server ,甲骨文的oracle RDBMS，IBM的DB2是商业数据库的霸主。但是商业数据库实在太贵了，后来出现了开源的MySQL。阿里则干脆喊出了去IOE的口号。O就是oracle数据库。

在数据库上，用户不仅有OLTP的使用需求，也有分析的需求，就是OLAP。但是单机数据库，无论硬件性能还是软件扩展能力，都是有限的。为了应对分析需求，一般采用一些技巧来实现，一般有这几种方式

  • 构建CUBE，按照要分析的问题，预计算出结果。这种思想在后来的Apache kylin上也有体现。
    • 这种方式的缺点在于，
      1. 维度多的时候数据膨胀会比较厉害；
      2. 需要预先把要分析的维度加入CUBE，不够灵活。
  • 分库分表。单表的查询在百万以内还能应付，超过千万级别，性能急剧下降。因此一般会根据某些列拆成多张表，查询时只命中需要的表即可。这种思想类似于数仓中的分区概念。

MapReduce时代

2004年，Google发表了MapReduce论文，开启了大数据时代。Google产生的大数据需要分析，传统的数据库依赖单机的性能来提升查询能力，但单机的能力毕竟是有限的，无法支持PB级别的规模，Google则另辟蹊径，通过MapReduce算法，把成千上万的小型机调动起来运行同一个分析程序。

雅虎支持的开源社区则根据Google论文的思想，开发了Hadoop，成为现代大数据套件的鼻祖。Hadoop包含了MapReduce运行框架和HDFS分布式文件系统。之后的十多年间，围绕Hadoop衍生出了一整套的大数据生态系统，有做资源管理的，有做调度的，有做任务管理的，有做分布式锁的。要在生产环境把hadoop完整的跑起来，需要玩转多个组件，还真不容易。

MapReduce，解决了对大数据的分析需求。

SQL on hadoop时代

hadoop需要自己编写MapReduce的逻辑，使用门槛非常的高。一个公司内，需要有专门的大数据团队，来给各个业务方写分析程序。严重制约了使用范围。为了降低使用门槛，数据库常用的SQL语言被搬了出来。SQL可以说是数据分析领域受众最广的语言了。hive 就是典型的代表。数据存在在HDFS上，用户输入SQL，程序自动的拆解成MapReduce逻辑。用户不再需要关心底层的数据是怎么分布的，分析程序该如何根据哪个partition拆解MapReduce。大大降低了使用门槛。

SQL on hadoop的本质，是提供了SQL的interface，但底层还是MapReduce的DAG执行方式。每个任务的执行结果，需要写入磁盘。每个阶段执行完后，下一个阶段才能开始执行。这种方式延时会非常高，跑一个复杂的job，需要几个小时；一个简单的job也需要几分钟。因此通常称为离线任务，放到晚上业务空闲期跑。

SQL on hadoop 解决了对分析大数据的体验的需求。

MPP时代

离线任务能够帮助人们分析大数据，但是由于运行时间长，只能做一些固定模式的报表，每天晚上跑一跑前一天的数据，给领导一个报表。

需求是无止境的，互联网业务产生了海量的数据，往往要深入挖掘数据的价值，挖掘这个动作本身，就意味着分析存在不确定性，需要反复的探索数据，尝试不同的方式分析数据。用离线任务去分析，一个job几分钟乃至几个小时，黄花菜都凉了。因此大数据挖掘，对快的要求越来越高。

MapReduce框架代表了在算法层面提升了规模。而另一方面，最近十几年，硬件也在飞速发展。200x年的时候，单机内存有限。今天的服务器，动不动就几百个G，国产化的SSD的单价做到了0.5元/GB。单机几百G的内存，再加几个T的SSD，网卡普遍用上了万兆网卡。单机的硬件性能大大加强。

于是出现了一批新的运行框架，例如Spark， Presto， 充分利用单机的内存做计算，计算结果通过网络传输给下游节点，而不是写到磁盘，再传给其他机器。这些新的软件，不再采用Hadoop的MapReduce运行框架，而是借鉴MapReduce的思想，自己实现了计算逻辑。

这些新的计算系统，抛弃了除了HDFS以外的hadoop生态圈。原来跑起来hadoop需要一堆软件协同，现在只需要一个开箱即用的软件即可。当然像Presto,Spark，本身还是需要读写HDFS，也算是SQL on hadoop 的延续。

DAG vs MPP

本章节命名MPP不是很恰当，MPP只是其中的一种调度和运行模型。MPP源于并行数据库，每个进程都是一个独立的可运行数据库，有完整的解析，优化，codegen，和资源管理，每个进程只负责一部分数据。除了MPP模型，还有DAG模型，DAG的运行前提是shared storage，比如HDFS，由全局节点解析，优化，分配和协调每个节点的任务。

基于内存的OLAP引擎，能够在秒级别完成大规模数据的分析，并拿到结果。做到了之前数据库、数仓做不到的性能和延时。在此之前，要在短时间分析大量数据是不可能的，因而不得不采取一些技巧来完成，例如预计算，流计算，把计算结果保存到NoSQL中，用户查询的时候，直接查询NoSQL的结果即可。但这些技巧本身对用户来说非常不灵活，规则的任何变化，都需要把历史数据重跑一遍。基于内存的计算引擎，让真正的OLAP成为可能。用户不再需要做各种预定义的规则。只需要保存原始的数据，在需要的时候，可以立即通过SQL获得结果。

MPP解决了人们对于快速分析大数据的需求。

ClickHouse

Presto是2012年FB研发出来的，目的是为了加速Hive的查询。Presto是基于Java开发的，大部分的大数据套件都是基于Java开发的，Java的开发生态比较丰富，开发门槛比较低。ClickHouse是2016年俄罗斯开源的OLAP系统，由于ClickHouse的年代更近，因而采用了最新的一些技术，用论文里边一句时髦的话叫state of the art，使得ClickHouse的运行速度领先同类OLAP引擎。本文就从代码层面探究ClickHouse的一些优势。

采用c++ 17语言

ClickHouse的第一个优势是采用c++语言，而且是c++17的标准。能用c++写大型程序的都是好汉。现代软件重要的是协同开发，而不是单打独斗。大数据生态，大多采用java开发，是有道理的。java一次编译，处处运行优势，可以让每一个开发者只负责其中一部分功能，然后以jar包的形式分发，打包成jar包就说明解决了编译问题，而运行时问题则交给jvm，其他开发者只需要引用jar包，就可以完成协同开发，这促进了java丰富的开发生态，基本上需要什么基础轮子，就有对应的jar包，不需要自己重复造轮子。这一点是c++不能比的。c++不同的编译器编译出来的二进制lib，不同的硬件平台上编译出来的lib，都有兼容性问题，这阻碍了基础套件的分发和共享。导致c++代码协同研发必须共享代码，而共享代码在不同编译器上有会遇到各种各样的编译问题。所以很少有基于c++实现的大数据软件。如何提升c++程序的协同开发效率，我会专门开一篇文章介绍LLVM。

鉴于上述描述的c++协同开发的困难，ClickHouse能够用c++代码来实现，说明老大哥还是非常彪悍的，往年用c++搞出了nginx，现在又用c++码出了ClickHouse，c++代码比JAVA代码，在执行效率上高一些，再加上c++能够利用一些指令级别的优化，因而整体而言，c++程序的运行速度要快于JAVA。

更难能可贵的是，ClickHouse采用了c++ 17的标准，用clang10编译器，采用了很多新的语言特性，新的语言特性的优势在于：

  1. 编程代码更加简洁，编程效率会更高。例如auto关键字，让c++有了类似脚本语言的快感。
  2. 一些新的特性让性能上更上一层楼。比如std::move通过移动构造函数，避免生成临时对象。 std::unique_ptr智能指针，既能够管理对象内存，又能够像对象一样在函数间传递(相对auto_ptr)，却不用承担shared_ptr锁的开销。
  3. 更加复杂的编译时表达能力。像enable_if,is_same_v等语法，决定编译时的动作，让模板编程能力更加复杂。在以前，编译时动作只有宏编程，c++11之后，这些新的特性，让开发者有更多的选项告诉编译器该怎么做。
  4. 可变长度模板参数列表。模板参数可以像函数的可变长度参数列表一样，支持不定长模板参数列表，快速实例化模板。这个特性会在下文的木版化执行阶段介绍。

这里无意介绍c++11到c++17所有的特性，只是摘出来ClickHouse用到的一些特性做介绍，对c++11/17感兴趣的同学，网上有很多介绍文章。

用最新的编译器+最新的语言特性，带来了编程效率和执行效率的提升，让ClickHouse领先同类产品一个段位。这大概就是后发优势吧

模板化执行代码

在SQL执行引擎中，逻辑执行计划生成物理执行计划，要根据相应的数据类型，函数名称、参数列表，寻找合适的执行代码。例如 1 + 2.2这个计算，要寻找到一个plus函数，参数类型分别是int和float，即签名是plus(int, float)的函数。实现方式上，会提供不同类型的重载函数。

一般而言，有几种方式，第一是采用虚函数的方式，在执行时，根据实际类型选择合适的函数入口。但是我们都知道虚函数是通过虚表实现的。运行时查找函数需要经过一跳。如果每一行记录都在运行时做一次虚表跳转，代价是很大的。

解决方法就是第二种形式，在编译时绑定执行函数。但是还要解决一个泛化的问题，要提供一系列函数，而不止是一个函数。ClickHouse采用的是模板化编程，同一个名字的函数，用模板实现，乃至模板套模板。参数的类型用模板类型表示。并通过可变模板类型参数列表物化出真正的代码，这一过程是在ClickHouse编译时确定的。等到物化执行计划阶段，调用可变模板类型参数列表的函数，逐个匹配各个类型，寻找到合适的类型，就执行对应的函数。可变模板类型列表是一个很重要的概念，ClickHouse依赖它完成泛化代码的编写、代码实例化、运行时多态、

上边提到的1+2.2可能有点复杂，我们首先以单参数函数为例介绍，比如函数abs(-1)，计算-1的绝对值。首先clickhouse提供了一个模板实现FunctionUnaryArithmetic，囊括了所有的单参数数学函数，参数可以是不同的类型，从uint8到decimal256,也可以是string。abs.cpp，则提供了abs算子的具体实现AbsImpl::apply，当然这个算子也用数据类型作为模板，可以支持不同位数的数字，该算子作为FunctionUnaryArithmetic的模板参数。FunctionUnaryArithmetic要做的，就是在运行时根据传入的参数实际类型，选择不同的执行路径，主要是区分是string还是数字。怎么实现运行时动态参数选择呢？主要是通过上文提到的可变长度的模板参数列表来实现:

ClickHouse调用castTypeToEither 函数，并且传入实际的数据类型，和回调函数，当匹配到某一个类型时，就执行f这个lambda函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static bool castType(const IDataType * type, F && f)
{   
    return castTypeToEither<
        DataTypeUInt8,
        DataTypeUInt16,
        DataTypeUInt32,
        DataTypeUInt64,
        DataTypeUInt256,
        DataTypeInt8,
        DataTypeInt16,
        DataTypeInt32,
        DataTypeInt64,
        DataTypeInt128,
        DataTypeInt256,
        DataTypeFloat32,
        DataTypeFloat64,
        DataTypeDecimal<Decimal32>,
        DataTypeDecimal<Decimal64>,
        DataTypeDecimal<Decimal128>,
        DataTypeDecimal<Decimal256>,
        DataTypeFixedString
    >(type, std::forward<F>(f));

1
2
3
4
5
6
template <typename... Ts, typename T, typename F>                
static bool castTypeToEither(const T * type, F && f)             
{                                                                
    /// XXX can't use && here because gcc-7 complains about parentheses around && within ||
    return ((typeid_cast<const Ts *>(type) ? f(*typeid_cast<const Ts *>(type)) : false) || ...);
}

castTypeToEither是怎么实现的呢，如上代码样例，模板参数中的Ts是一个可变长度的列表。实现中，为了表达『命中类型就执行f』这个语义，用了短路求值法，但是因为编译器不支持&&这种写法，而用了?:双目运算符。如果检查类型匹配，就以匹配的类型执行，不匹配就检查下一个类型，语法上使用了||… 来表达对每一个模板参数执行相同操作。由于回调函数也是模板，传入实际类型就相当于实例化了对应代码。由于模板函数在编译时有调用才会实例化，不按照这种做法，我们恐怕要在一个地方为每一种类型编写一下调用函数才能实例化。castTypeToEither是非常重要的一个函数，由它实例化出了每一种计算函数的实现。

看到了单参数的实现，接下来看多参数的实现，以上边提到了1+2.2为例，介绍ClickHouse的实现方式,由于双参数的类型组合比单数更多，相当于N*N个组合，比如int8 + float, int16+float,int32+float, float+float。 一般有个做法是，在具体实现时，只实现同类型的，比如Int8+int8， float+float。语法检查器在检查时，会优先寻找函数名匹配，参数类型也完全匹配的函数实现。 如果其中一个参数不匹配，比如Int32+float，找不到这个组合的实现，语法检查器会挨个检查每个函数实现，是否能够做类型转换，把实际类型转化成函数声明类型而不影响精度，比如针对int32+int32的函数实现，float不能转化成int32，所以不能采用该实现，针对float+float，发现int32能够转化成float，那么就会把语法树变成cast(int32 as float) + float来解决这个问题，虽然两者语义上有一定差别，毕竟int 转float在大数情况下会损失精度，但是好歹在目前情况下实现了该运算。

按照这种做法，先强制转化类型，把数据拷贝出来一份，生成一份新的数据，再去计算。

ClickHouse没有这样做，它没有在语法检查阶段添加这种强制类型转换的逻辑。而是用模板实现两个不同类型的计算，然后通过castTypeToEither函数，实例化出不同的组合。

1
2
3
4
5
template <typename F>
static bool castBothTypes(const IDataType * left, const IDataType * right, F && f)
{    
    return castType(left, [&](const auto & left_) { return castType(right, [&](const auto & right_) { return f(left_, right_); }); });
}

在castBothTypes函数中，通过castType嵌套castType，获得左右两个函数的实际类型后，用实际类型回调lambda函数f。比如你传入的是int+float,就会实例化出该类型。在ClickHouse的编译阶段(注意，不是SQL的编译阶段)，就会通过上文提到的几个函数，实例化出不同的组合，既有int+float,也有int64+float，更有decimal128+float，还有float+decimal128等等各种组合。

ClickHouse的这种做法的好处是什么呢？减少了一次类型转换的开销，节省一个算子。

值得注意的是，模板函数提升的是泛化的能力，总不能给每一种类型都实现一个重载函数吧，在执行效率上，由于是运行时多态，挨个检查每个类型，找到合适的再回调，需要有多次跳转指令，和虚函数也没多大差别，不能充分利用CPU流水线。但是由于ClickHouse采用的是列式方式计算，每一大块数据(几万行数据)只需要执行一次查找即可，不需要每一行数据都做这个检查。但假如你用的是按行处理，那恐怕性能就急剧下降了。

列式计算

上文提到了ClickHouse是按列式计算的，按照列式计算有两个好处，

####1. 更高的存储压缩比
存储时按照列式存储，同一种类型的数据在压缩时会获得一个更好的压缩比，节省存储空间，读取时速度也会更快。

####2. 利用向量化加速计算
按照列式处理，一次加载一批数据，利用单条指令同时操作多条数据，获得提速效果。一次操作一列数据，可以完全放到CPU缓存中。像Presto这种计算引擎，虽然提供了列式的接口，仅仅利用了存储上列的优势，没有用到计算上的优势。向量化如何提速，会在下文介绍。

向量化

向量化主要是利用单条指令操作多条数据，指令称为SIMD指令。在运行时，把满足寄存器大小的数据放到寄存器，CPU一条指令操作寄存器上的多条数据。

向量化一般有两种方式：

1. 利用编译器自动向量化

在编写程序时，如果是符合一定规范的循环语句，循环语句内部是简单的操作，比如+-*/等，编译器优化器，可以把循环语句折叠成向量化执行。

1
2
3
4
5
static void NO_INLINE vectorVector(const A * __restrict a, const B * __restrict b, ResultType * __restrict c, size_t size)
{   
    for (size_t i = 0; i < size; ++i)
        c[i] = Op::template apply<ResultType>(a[i], b[i]);
}

2. 显式使用SIMD指令

c++ 提供了SIMD指令，可以一次把128bit的数据加载到寄存器，以下边的大小写转换的函数为例，一个字符是8bit，一次把128bit，也就是16个字节的字符串加载到寄存器，通过CPU一条指令操作16个字符，相当于获得了16倍的提速。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
    static void array(const UInt8 * src, const UInt8 * src_end, UInt8 * dst)
    {   
        const auto flip_case_mask = 'A' ^ 'a';

#ifdef __SSE2__
        const auto bytes_sse = sizeof(__m128i);
        const auto src_end_sse = src_end - (src_end - src) % bytes_sse;

        const auto v_not_case_lower_bound = _mm_set1_epi8(not_case_lower_bound - 1); 
        const auto v_not_case_upper_bound = _mm_set1_epi8(not_case_upper_bound + 1); 
        const auto v_flip_case_mask = _mm_set1_epi8(flip_case_mask);

        for (; src < src_end_sse; src += bytes_sse, dst += bytes_sse)
        {   
            /// load 16 sequential 8-bit characters
            const auto chars = _mm_loadu_si128(reinterpret_cast<const __m128i *>(src));

            /// find which 8-bit sequences belong to range [case_lower_bound, case_upper_bound]
            const auto is_not_case
                = _mm_and_si128(_mm_cmpgt_epi8(chars, v_not_case_lower_bound), _mm_cmplt_epi8(chars, v_not_case_upper_bound));

            /// keep `flip_case_mask` only where necessary, zero out elsewhere
            const auto xor_mask = _mm_and_si128(v_flip_case_mask, is_not_case);

            /// flip case by applying calculated mask
            const auto cased_chars = _mm_xor_si128(chars, xor_mask);

            /// store result back to destination
            _mm_storeu_si128(reinterpret_cast<__m128i *>(dst), cased_chars);
        }   
#endif

        for (; src < src_end; ++src, ++dst)
            if (*src >= not_case_lower_bound && *src <= not_case_upper_bound)
                *dst = *src ^ flip_case_mask;
            else
                *dst = *src;
    }

LLVM动态编译执行代码

上文在介绍模板化编程时指出，CickHouse实现多态的方式是通过在运行时检查不同参数类型，直到找到一个合适的类型，再运行这个类型的实例化计算代码。相当于多条跳转指令才能找到真正的执行代码。虽然采用列式计算，但是如果数据块比较多，这个计算开销也是不小的。 再加上计算时函数套函数，一个很小的操作都需要调用函数完成，实际上完成一行的计算需要多条指令才能做到。为了在这上边提升计算速度，ClickHouse还提供了动态编译和JIT的方法。

说到c++的动态编译，就离不开LLVM。LLVM是一种现代化的编译器，我会再开一篇文章详细介绍LLVM和JIT技术。 动态编译代码，就是在程序运行时，把SQL的执行计划，编译成可执行的机器指令，并且在当前程序中执行这些指令。动态编译是相对于静态编译而言的。通常静态编译是说，写完代码用g++、clang++等工具编译成二进制文件，然后运行这个二进制文件。动态代码则是程序运行时动态编译的。动态编译和执行称为JIT技术。

LLVM 为c++提供了很了不起的JIT技术支持。往常只有java代码才有动态编译一说。c++有了动态编译，才给数据库技术加速计算提供了新的方法。

以plus函数为例，plus的运算符提供了编译方法，通过llvm实现一个指令，b.CreateAdd完成左右两个参数的加法的指令。

1
2
3
4
static inline llvm::Value * compile(llvm::IRBuilder<> & b, llvm::Value * left, llvm::Value * right, bool)
{   
    return left->getType()->isIntegerTy() ? b.CreateAdd(left, right) : b.CreateFAdd(left, right);
}

使用静态代码执行，需要多层函数嵌套，乃至每一行都需要调用一个函数，开销很大，而在JIT 技术下，一个区块的数据只需要调用一个函数就可以了。

当然，动态编译代码代价很大。我们经常说，开发者大部人时间就是等待编译器做编译。JIT也一样，动态编译需要时间，编译一次代价很大。因此在编译后要把结果缓存下来复用。

总结

大数据系统发展了这么多年，数据规模越来越大，速度越来越快。而人们对数据分析的强烈需求是永无止境的。新的编程技术不断涌现，硬件水平也不断发展，每隔几年出现新的、更强大的、更快速的大数据系统。
ClickHouse作为比较新的OLAP引擎，在很多场景的benchmark上处于领先地位。本文从代码层面介绍了为什么ClickHouse计算速度快。ClickHouse利用c++17标准，clang11编译器，相当于最新的编程语言；同时利用模板泛化编程，泛化实现大量算子；也利用指令集别的并行计算，加速计算；利用LLVM动态编译代码，优化执行逻辑。

本文主要探讨为什么计算快，对clickhouse架构方面涉及不多。OLAP引擎一直在发展，新的技术也会不断出现。我们会持续关注，并把最新的技术应用到我们的云计算中。