背景

• 最近一段时间笔者有幸开始接触OLAP领域的业务。百忙之中抽出时间结合自己对ClickHouse、Spark、Doris等引擎了解，写篇关于OLAP引擎的文章。通过对OLAP引擎原理的剖析、各大厂对OLAP引擎的一些使用情况给读者一个对OLAP引擎直观的了解和感受。

• 笔者思索如果自己从头设计一个OLAP的分析引擎，应该如何做，核心关键点是什么？这边文章就是笔者结合clickhouse等引擎及自己的思考总结的一篇关于OLAP引擎的文章。

• 结合ClickHouse和Hbase等框架，笔者认为从海量数据中进行高效率查询的核心思想是：能够快速把待搜索的数据范围降低到原来的1/n，然后再结合索引或者热点数据放在内存等思路，就能实现高效率的查询。

• 笔者直观上能想到的方法包括：

• 数据分区分片
• 数据排序
• 数据分块与分布式查询（如spark mapreduce的处理方式）
• 列式存储、列裁剪
• 预聚合
• 主键索引+二级索引+位图索引+布隆索引等
• 使用多样化的存储引擎满足不同场景的需要

• 下面笔者就目前能想到的几种办法深入分析，对OLAP引擎的原理进行更深一步的分析。

OLAP引擎原理

数据分区

• 通过把数据分区写入，查询时通过分区缩小查询范围，就可以提高查询的效率。
• 包括hive、spark、clickhouse等都支持分区，分区本质上做到了按需查询，缩小查询范围。

数据排序

• MergeTree这个词，可能大家都会联想到LSM-Tree这个数据结构，我们常用它来解决随机写磁盘的性能问题，MergeTree的核心思想和LSM-Tree相同。MergeTree存储结构需要对用户写入的数据做排序然后进行有序存储，数据有序存储带来两大核心优势。
• 存储有序性本身就是一种可以加速查询的索引结构，根据排序键中列的等值条件或者range条件我们可以快速找到目标行所在的近似位置区间(下文会展开详细介绍)，而且这种索引结构是不会产生额外存储开销的。
• 列存文件在按块做压缩时，排序键中的列值是连续或者重复的，使得列存块的数据压缩可以获得极致的压缩比。

• 如上图所示，无论是机械硬盘(disk)，SSD还是内存，顺序写入都会比随机写入的IO写入性能要强很多。如果可以做到顺序得往硬盘写入数据，就能达到比较好的写入性能。
• LSM Tree，看名字感觉是一个树的数据结构。实际上LSM Tree并不是真正意义上的一棵树，它不像是B数或者B+数，是一个纯粹的数据结构。LSM Tree更像是一种数据存储读写方案，它有多个已经排序的数据结构组成。

LSM Tree 论文中有这样的图片介绍，图片里面有C0 tree，C1 tree，C0 tree存储在内存，C1 tree存储在硬盘中。

• LSM Tree的写入流程会先写数据到C0 tree（内存），当C0 tree超过一定数据大小的时候，在flush到硬盘C1 tree。在通过不断的合并硬盘中的C1..Cn tree，最终合并到一个更大的有序文件。

C0 tree C0 tree是在内存存储的有序列表，Google BigTable 称为memtable，HBase 称为MemStore。这种数据结构通过跳表实现。

• 搜索

• 查询
  

• 删除

数据分块与分布式查询

• 数据分片是将数据进行横向切分，这是一种在面对海量数据的场景下，解决存储和查询瓶颈的有效手段，是一种分治思想的体现。以clickhouse为例，ClickHouse支持分片，而分片则依赖集群。每个集群由1到多个分片组成，而每个分片则对应了ClickHouse的1个服务节点。分片的数量上限取决于节点数量（1个分片只能对应1个服务节点）。

• ClickHouse并不像其他分布式系统那样，拥有高度自动化的分片功能。ClickHouse提供了本地表（Local Table）与分布式表（Distributed Table）的概念。一张本地表等同于一份数据的分片。而分布式表本身不存储任何数据，它是本地表的访问代理，其作用类似分库中间件。借助分布式表，能够代理访问多个数据分片，从而实现分布式查询。

• 这种设计类似数据库的分库和分表，十分灵活。例如在业务系统上线的初期，数据体量并不高，此时数据表并不需要多个分片。所以使用单个节点的本地表（单个数据分片）即可满足业务需求，待到业务增长、数据量增大的时候，再通过新增数据分片的方式分流数据，并通过分布式表实现分布式查询。

预聚合

• 分布式的查询不可避免会有聚合过程，这个过程中shuffle大量的数据往往会带来网络I/O的性能瓶颈。诸如spark、clickhouse等引擎都使用到了预聚合的技术。

• 以spark为例。spark map-side预聚合，在每个节点本地对相同的key进行一次聚合操作，类似于MapReduce中的本地combiner。

• map-side预聚合之后，每个节点本地就只会有一条相同的key，因为多条相同的key都被聚合起来了。其它节点在拉取所有节点上的相同key时，就会大大减少需要拉取的数据数量，从而也就减少了磁盘IO以及网络传输开销。

• 通常来说，在可能的情况下，建议使用reduceByKey或者aggregateByKey算子来替代掉groupByKey算子。因为reduceByKey和aggregateByKey算子都会使用用户自定义的函数对每个节点本地的相同key进行预聚合。而groupByKey算子是不会进行预聚合的，全量的数据会在集群的各个节点之间分发和传输，性能相对来说比较差。

  下图可以形象的展示预聚合的原理

  
  

• 

• 

各类索引

一级索引

• MergeTree 的主键使用 PRIMARY KEY 定义，待主键定义之后，MergeTree 会依据 index_granularity 间隔（默认 8192 行），为数据表 生成一级索引并保存至 primary.idx 文件内。一级索引是稀疏索引，意思就是说：每一段数据生成一条索引记录，而不是每一条数据都生成索引，如果是 每一条数据都生成索引，则是稠密索引。稀疏索引的好处，就是少量的索引标记，就能记录大量的数据区间位置信息，比如不到 24414 条标记信息，就 能为 2E 条数据提供索引（算法：200000000 / 8192）。在 ClickHouse 中，一级索引常驻内存。总的来说：一级索引和标记文件一一对齐，两个索引标 记之间的数据，就是一个数据区间，在数据文件中，这个数据区间的所有数据，生成一个压缩数据块。

二级索引

• 又称之为跳数索引。目的和一级索引一样，是为了减少待搜寻的数据的范围。这里不再赘述，可自行百度。

数据压缩

• 以ClickHouse为例。ClickHouse 的数据存储文件 column.bin 中存储是一列的数据，由于一列是相同类型的数据，所以方便高效压缩。在进行压缩的时候，请 注意：一个压缩数据块由头信息和压缩数据两部分组成，头信息固定使用 9 位字节表示，具体由 1 个 UInt8（1字节）整型和 2 个 UInt32（4字节）整型 组成，分别代表使用的压缩算法类型、压缩后的数据大小和压缩前的数据大小。每个压缩数据块的体积，按照其压缩前的数据字节大小，都被严格控制在 64KB～1MB，其上下限分别由 min_compress_block_size（默认65536=64KB）与 max_compress_block_size（默认1048576=1M）参数指定。具体压 缩规则：原理的说法：每 8192 条记录，其实就是一条一级索引 一个索引区间 压缩成一个数据块。

多种引擎集成

• 目前我们面对的数据查询场景日益复杂，希望一种引擎能够处理所有场景显然不切实际。多种引擎处理各自合适的场景，应当说即是一种趋势，也是一种必然。一个良好的OLAP引擎需要集成多种子引擎，处理多种场景数据处理需求。
• 以ClickHouse为例。ClickHouse 也支持在创建库的时候，指定库引擎，目前支持5种，分别是：Ordinary，Dictionary， Memory， Lazy， MySQL，其实 Ordinary 是默认库引擎，在此类型库引擎下，可以使用任意类型的表引擎。

1、Ordinary引擎：默认引擎，如果不指定数据库引擎创建的就是 Ordinary 数据库
2、Dictionary引擎：此数据库会自动为所有数据字典创建表
3、Memory引擎：所有数据只会保存在内存中，服务重启数据消失，该数据库引擎只能够创建 Memory 引擎表
4、MySQL引擎：改引擎会自动拉取远端 MySQL 中的数据，并在该库下创建 MySQL 表引擎的数据表
5、Lazy延时引擎：在距最近一次访问间隔 expiration_time_in_seconds 时间段内，将表保存在内存中，仅适用于 Log 引擎表


• ClickHouse 的表引擎提供了四个系列（Log、MergeTree、Integration、Special）大约 28 种表引擎，各有各的用途。比如 Log 系列用来做小表数据分 析，MergeTree 系列用来做大数据量分析，而 Integration 系列则多用于外表数据集成。Log、Special、Integration 系列的表引擎相对来说，应用场景 有限，功能简单，应用特殊用途，MergeTree 系列表引擎又和两种特殊表引擎（Replicated，Distributed）正交形成多种具备不同功能的 MergeTree 表 引擎。
• 关于表引擎功能

第一：MergeTree 表引擎主要用于海量数据分析，支持数据分区、存储有序、主键索引、稀疏索引、数据 TTL 等。MergeTree 支持所有 ClickHouse
SQL 语法，但是有些功能与 MySQL 并不一致，比如在 MergeTree 中主键并不用于去重。
第二：为了解决 MergeTree 相同主键无法去重的问题，ClickHouse 提供了 ReplacingMergeTree 引擎，用来做去重。ReplacingMergeTree 确保数据
最终被去重，但是无法保证查询过程中主键不重复。因为相同主键的数据可能被 shard 到不同的节点，但是 compaction 只能在一个节点中进行，而且 
optimize 的时机也不确定。
第三：CollapsingMergeTree 引擎要求在建表语句中指定一个标记列 Sign（插入的时候指定为 1，删除的时候指定为 -1），后台 Compaction 时会将主
键相同、Sign 相反的行进行折叠，也即删除。来消除 ReplacingMergeTree 的限制。
第四：为了解决 CollapsingMergeTree 乱序写入情况下无法正常折叠问题，VersionedCollapsingMergeTree 表引擎在建表语句中新增了一列 
Version，用于在乱序情况下记录状态行与取消行的对应关系。主键相同，且 Version 相同、Sign 相反的行，在 Compaction 时会被删除。
第五：ClickHouse 通过 SummingMergeTree 来支持对主键列进行预先聚合。在后台 Compaction 时，会将主键相同的多行进行 sum 求和，然后使用
一行数据取而代之，从而大幅度降低存储空间占用，提升聚合计算性能。
第六：AggregatingMergeTree 也是预先聚合引擎的一种，用于提升聚合计算的性能。与 SummingMergeTree 的区别在于：SummingMergeTree 对
非主键列进行 sum 聚合，而 AggregatingMergeTree 则可以指定各种聚合函数。


• ClickHouse 的表引擎系列家谱
  
  

• 

小结

• 以上介绍了设计OLAP引擎的关键点，并展示了一些通用的引擎对基本原理的应用。

• clickhouse基本集成了上面的原理的关键点，性能出众。

• 在 1 亿数据集体量的情况下，ClickHouse 的平均响应速度是 Vertica 的 2.63 倍、InfiniDB 的 17 倍、MonetDB 的 27 倍、Hive 的 126 倍、MySQL 的 429 倍以及Greenplum 的 10 倍。详细的测试结果可以查阅：https://clickhouse.tech/benchmark/dbms/。

• 目前国内社区火热，各个大厂纷纷跟进大规模使用情况：

• 今日头条内部用 ClickHouse 来做用户行为分析，内部一共几千个 ClickHouse 节点，单集群最大 1200 节点，总数据量几十 PB，日增原始数据 300TB 左右。
• 腾讯内部用 ClickHouse 做游戏数据分析，并且为之建立了一整套监控运维体系。
• 携程内部从 18 年 7 月份开始接入试用，目前 80% 的业务都跑在 ClickHouse 上。每天数据增量十多亿，近百万次查询请求。
• 快手内部也在使用 ClickHouse，存储总量大约 10PB， 每天新增 200TB， 90% 查询小于 3S。

• 但是其也存在缺点：

1、没有完整的事务支持
2、稀疏索引导致 ClickHouse 不擅长细粒度或者 key-value 类型数据的查询需求
3、缺少高频率，低延迟的修改或删除已存在数据的能力。仅能用于批量删除或修改数据
4、不擅长 join 操作。


• 后续会有文章详细介绍Clickhouse、Doris等开源OLAP引擎的使用，敬请期待。