当前位置: 代码迷 >> 综合 >> 一文了解 ClickHouse 的向量化执行
  详细解决方案

一文了解 ClickHouse 的向量化执行

热度:76   发布时间:2023-12-13 15:20:38.0

ClickHouse在计算层做了非常细致的工作,竭尽所能榨干硬件能力,提升查询速度。它实现了单机多核并行、分布式计算、向量化执行与SIMD指令、代码生成等多种重要技术。

多核并行

ClickHouse将数据划分为多个partition,每个partition再进一步划分为多个index granularity,然后通过多个CPU核心分别处理其中的一部分来实现并行数据处理。

在这种设计下,单条Query就能利用整机所有CPU。极致的并行处理能力,极大的降低了查询延时。

分布式计算

除了优秀的单机并行处理能力,ClickHouse还提供了可线性拓展的分布式计算能力。ClickHouse会自动将查询拆解为多个task下发到集群中,然后进行多机并行处理,最后把结果汇聚到一起。

向量化执行与SIMD

ClickHouse不仅将数据按列存储,而且按列进行计算。传统OLTP数据库通常采用按行计算,原因是事务处理中以点查为主,SQL计算量小,实现这些技术的收益不够明显。但是在分析场景下,单个SQL所涉及计算量可能极大,将每行作为一个基本单元进行处理会带来严重的性能损耗:

?对每一行数据都要调用相应的函数,函数调用开销占比高;

?存储层按列存储数据,在内存中也按列组织,但是计算层按行处理,无法充分利用CPU cache的预读能力,造成CPU Cache miss严重;?按行处理,无法利用高效的SIMD指令;

ClickHouse实现了向量执行引擎(Vectorized execution engine),对内存中的列式数据,一个batch调用一次SIMD指令(而非每一行调用一次),不仅减少了函数调用次数、降低了cache miss,而且可以充分发挥SIMD指令的并行能力,大幅缩短了计算耗时。向量执行引擎,通常能够带来数倍的性能提升。

What IS SIMD ?

SIMD

即 single instruction multiple data 英文首字母缩写,单指令流多数据流,也就是说一次运算指令可以执行多个数据流,一个简单的例子就是向量的加减。

SSE 与 SMID 关系

SSE(为Streaming SIMD Extensions的缩写)是由 Intel公司在1999年推出Pentium III处理器时,同时推出的新指令集。如同其名称所表示的,SSE是一种SIMD指令集。SSE有8个128位寄存器,XMM0 ~XMM7。可以用来存放四个32位的单精确度浮点数。可以看出,SSE 是一套专门为 SIMD(单指令多数据)架构设计的指令集。通过它,用户可以同时在多个数据片段上执行运算,实现数据并行(aka:矢量处理)。

SSE2是SSE指令的升级版,寄存器与指令格式都和SSE一致,不同之处在于其能够处理双精度浮点数等更多数据类。SSE3增加了13条新的指令。

参考:https://www.cnblogs.com/xidian-wws/p/11023762.html

C++使用SIMD编程的3种方法

SIMD指令集的使用,有如下三种方式:

?编译器优化 即使用C/C++编写程序之后,带有SIMD优化选项编译,在CPU支持的情况下,编译器按照自己的规则去优化。?使用intrinsic指令 参考Intel手册,针对SIMD指令,可以在编程时直接使用其内置的某些库函数,编译的时候在cpu和编译器的支持下会生成对应的SIMD指令。比如:double _mm_cvtsd_f64 (__m128d a) 该函数编译时就会翻译成指令:movsd?嵌入式汇编 内联汇编直接在程序中嵌入对应的SIMD指令。

Intrinsics头文件与SIMD指令集、Visual Studio版本对应表

VS和GCC都支持SSE指令的Intrinsic,SSE有多个不同的版本,其对应的Intrinsic也包含在不同的头文件中,如果确定只使用某个版本的SSE指令则只包含相应的头文件即可。

例如,要使用SSE3,则

#include <tmmintrin.h>

如果不关心使用那个版本的SSE指令,则可以包含所有

#include <intrin.h>

参考资料:https://www.cnblogs.com/huaping-audio/p/4115890.html

简单运算的Intrinsic和SSE指令对比 使用Intrinsic函数的代码:

  __m128 a1, b2;__m128 c1;for (int i = 0; i < count; i++){a1 = _mm_load_ps(a);b2 = _mm_load_ps(b);c1 = _mm_add_ps(a1,  b2);}

对应汇编指令代码:

   for(int i = 0; i < count; i ++)_asm{movaps  xmm0, [a];movaps  xmm1, [b];addps  xmm0, xmm1;}

简要说明其中一种操作:

addps XMM,XMM/m128 源存储器内容按双字对齐,共4个单精度浮点数与目的寄存器相加,结果送入目的寄存器

计算机硬件支持与编译器支持

要能够使用 Intel 的 SIMD 指令集,不仅需要当前 Intel 处理器的硬件支持,还需要编译器的支持。

$ grep -q sse4_2 /proc/cpuinfo && echo "SSE 4.2 supported" || echo "SSE 4.2 not supported"

如果你的机器支持SSE4.2,那么,将打印:

SSE 4.2 supported

使用SIMD考量

?利用优点: 频繁调用的基础函数,大量的可并行计算?尽量避免: SSE指令集对分支处理能力非常的差,而且从128位的数据中提取某些元素数据的代价又非常的大,因此不适合有复杂逻辑的运算。

How Clickhouse USE SIMD ?

大家在搜索CLICKHOUSE为什么快的文章中,都提到了CH使用到的技术列式存储,压缩,向量引擎。

CH在所有能够提高CPU计算效率的地方,都大量的使用了SIMD。

本文以clickhouse其中的一个简单的LowerUpperImpl函数为例(这个函数完成大小写转换)。

测试产出SIMD模式与非SIMD模式下benchmark的效率对比。

code如下,关键节点已加注释:

  template <char not_case_lower_bound, char not_case_upper_bound>
struct LowerUpperImpl
{
public:static void array( char * src, char * src_end, char * dst){//32const 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){//_mm_loadu_si128表示:Loads 128-bit value;即加载128位值。//一次性加载16个连续的8-bit字符const auto chars = _mm_loadu_si128(reinterpret_cast<const __m128i *>(src));//_mm_and_si128(a,b)表示:将a和b进行与运算,即r=a&b//_mm_cmpgt_epi8(a,b)表示:分别比较a的每个8bits整数是否大于b的对应位置的8bits整数,若大于,则返回0xff,否则返回0x00。//_mm_cmplt_epi8(a,b)表示:分别比较a的每个8bits整数是否小于b的对应位置的8bits整数,若小于,则返回0xff,否则返回0x00。//下面的一行代码对这128位的寄存器并行操作了3遍,最后得到一个128位数,对应位置上是0xff的,表示//那个8-bit数在 [case_lower_bound, case_upper_bound]范围之内的,其余的被0占据的位置,是不在操作范围内的数。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));//每个0xff位置与32进行与操作,原来的oxff位置变成32,也就是说,每个在 [case_lower_bound, case_upper_bound]范围区间的数,现在变成了32,其他的位置是0const auto xor_mask = _mm_and_si128(v_flip_case_mask, is_not_case);//将源chars内容与xor_mask进行异或,符合条件的字节可能从uppercase转为lowercase,也可能从lowercase转为uppercase,不符合区间的仍保留原样。const auto cased_chars = _mm_xor_si128(chars, xor_mask);//将结果集存到dst中_mm_storeu_si128(reinterpret_cast<__m128i *>(dst), cased_chars);}
#endif
#ifndef __SSE2__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;
#endif}
};

完整代码参考 这里[1]

测试结果如下:

32位输入:

root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread sse.cpp && ./a.out
new des is abcdefghabcdefghabcdefghabcdefgh
花费了6.8059秒
root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread nosse.cpp && ./a.out
new des is abcdefghabcdefghabcdefghabcdefgh
花费了9.39051秒

64位输入:

root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread sse.cpp && ./a.out
new des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh
花费了9.26642秒
root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread nosse.cpp && ./a.out
new des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh
花费了17.3588秒

128位输入:

root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall  -pedantic -pthread sse.cpp && ./a.out
new des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh
花费了10.2672秒
root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall  -pedantic -pthread nosse.cpp && ./a.out
new des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh
花费了31.7568秒

这只是其中一个简单的函数。但,为什么Clickhouse快?管中窥豹,可见一斑。

Clickhouse 仅短短几年在OLAP领域横空出世,这和Clickhouse在设计和细节上追求极致密不可分。

对于俄罗斯人,开源一款产品可是大事。但不开源还则罢了。一旦开源,必是行业大事。一如nginx。

本文转载自:https://www.jianshu.com/p/fc384f18ff1a,作者:金科_

引用链接

[1] 这里: https://github.com/Johnny-Three/clickhousedive/blob/master/main.cpp

  相关解决方案