CIickHouse - 你没有见过的列存储

CIickHouse - 你没有见过的列存储

ClickHouse - 你没有见过的列存储

概述

本节课程分为四个部分

1. 数据库基本概念
2. 列式存储
3. ClickHouse存储设计
4. ClickHouse典型应用场景

课前部分主要罗列课程中涉及到的概念。对于不熟悉的概念，同学们可以提前查询预习；课中部分主要罗列每一部分的关键思路，帮助同学们跟上课程的进度；课后部分是一些问题，帮助同学们在课后梳理本课程的重点。

课前 （必须）

数据库基本概念

1. 数据库
2. DBMS：数据库管理系统
3. OLTP 数据库 ： OLTP（Online transactional processing）
4. OLAP 数据库：OLAP (Online analytical processing)
5. SQL (Structured Query Language)
6. 词法分析
7. 语法分析
8. AST (Abstract syntax tree)

列式存储

1. 行式存储
2. 列式存储
3. 数据压缩
   a. LZ4
   b. Run-length encoding
   c. Delta encoding
4. 延迟物化
   a. 物化
   b. Cpu cache
   c. 内存带宽
5. 向量化
   a. SIMD （single instruction multiple data）
   b. SSE指令集
   c. AVX指令集

ClickHouse存储设计

1. Shard key
2. 索引
   a. 哈希索引
   b. B-Tree
   c. B+Tree
   d. LSM-Tree

ClickHouse典型应用场景

1. Kafka
2. Spark
3. Hdfs
4. Bitmap
5. 字典编码

课中

数据库基本概念

数据库是什么

数据库是结构化信息或数据的有序集合，一般以电子形式存储在计算机系统中。通常由数据库管理系统 (DBMS) 来控制。在现实中，数据、DBMS 及关联应用一起被称为数据库系统，通常简称为数据库。

一个简单的例子

1. 数据解析整理成有序集合

2. 数据的写入和读取，可以通过查询语言获取想要的信息

数据库的类型

1. 数据库有很多种，至于各种数据库孰优孰劣，主要取决于企业希望如何使用数据。
2. 关系数据库：关系型数据库是把数据以表的形式进行储存，然后再各个表之间建立关系，通过这些表之间的关系来操作不同表之间的数据。
3. 非关系数据库 ： NoSQL 或非关系数据库，支持存储和操作非结构化及半结构化数据。相比于关系型数据库，NoSQL没有固定的表结构，且数据之间不存在表与表之间的关系，数据之间可以是独立的。NoSQL的关键是它们放弃了传统关系型数据库的强事务保证和关系模型，通过所谓最终一致性和非关系数据模型（例如键值对，图，文档）来提高Web应用所注重的高可用性和可扩展性。
4. 单机数据库：在一台计算机上完成数据的存储和查询的数据库系统。
5. 分布式数据库 ： 分布式数据库由位于不同站点的两个或多个文件组成。数据库可以存储在多台计算机上，位于同一个物理位置，或分散在不同的网络上。
6. OLTP 数据库 ： OLTP（Online transactional processing）数据库是一种高速分析数据库，专为多个用户执行大量事务而设计。
7. OLAP 数据库：OLAP (Online analytical processing) 数据库旨在同时分析多个数据维度，帮助团队更好地理解其数据中的复杂关系

OLAP数据库

1. 大量数据的读写，PB级别的存储
2. 多维分析，复杂的聚合函数

3. 离线/实时分析，对查询速度有要求

SQL

1. 一种编程语言，目前几乎所有的关系数据库都使用 SQL (Structured Query Language ) 编程语言来查询、操作和定义数据，进行数据访问控制。
2. SQL的结构

查询包含一系列含有最终结果的字段, 紧跟 SELECT关键词。星号（“*”）也可以用来指定查询应当返回查询表所有字段，可选的关键词和子句包括：

• FROM子句指定了选择的数据表。FROM子句也可以包含 JOIN 二层子句来为数据表的连接设置规则。
• WHERE子句后接一个比较谓词以限制返回的行。WHERE子句仅保留返回结果里使得比较谓词的值为True的行。
• GROUP BY子句用于将若干含有相同值的行合并。 GROUP BY通常与SQL聚合函数连用，或者用于清除数据重复的行。GROUP BY子句要用在 WHERE子句之后。
• HAVING子句后接一个谓词来过滤从 GROUP BY子句中获得的结果，由于其作用于 GROUP BY子句之上，所以聚合函数也可以放到其谓词中。
• ORDER BY子句指明将哪个字段用作排序关键字，以及排序顺序(升序/降序)，如果无此子句，那么返回结果的顺序不能保证有序。

3. SQL的用途
   a. 定义数据模型

CREATE TABLE default.test_insert_local
(
   `p_date` Date,
   `id` Int32
)
ENGINE = MergeTree
PARTITION BY p_date
ORDER BY id
SETTINGS index_granularity = 8192
复制代码

b. 读写数据库数据

insert into default.test_insert_local values ('2022-01-01', 1);

select count() from default.test_insert_local;
复制代码

4. SQL的优点

• 标准化，ISO和ANSI是长期建立使用的SQL数据库标准
• 高度非过程化，用SQL进行数据操作，用户只需提出“做什么”，而不必指明“怎么做”，因此用户无须了解存取路径，存取路径的选择以及SQL语句的操作过程由系统自动完成。这不但大大减轻了用户负担，而且有利于提高数据独立性。
• 以同一种语法结构提供两种使用方式，用户可以在终端上直接输入SQL命令对数据库进行操作。作为嵌入式语言，SQL语句能够嵌入到高级语言（如C、C#、JAVA）程序中，供程序员设计程序时使用。而在两种不同的使用方式下，SQL的语法结构基本上是一致的。
• 语言简洁，易学易用：SQL功能极强，但由于设计巧妙，语言十分简洁，完成数据定义、数据操纵、数据控制的核心功能只用了9个动词：CREATE、ALTER、DROP、SELECT、INSERT、UPDATE、DELETE、GRANT、REVOKE。且SQL语言语法简单，接近英语口语，因此容易学习，也容易使用。

数据库的架构

1. Client
2. Parser
   词法分析，语法分析，生成AST树 (Abstract syntax tree)

3. Analyzer
   变量绑定、类型推导、语义检查、安全、权限检查、完整性检查等，为生成计划做准备
4. Analyzer
   变量绑定、类型推导、语义检查、安全、权限检查、完整性检查等，为生成计划做准备
5. Optimizer

• 为查询生成性能最优的执行计划
• 进行代价评估
• Executor 将执行计划翻译成可执行的物理计划
• Storage engine
  a. 管理内存数据结构【index、内存数据、缓存（Query cache、Data cache、Index cache）】
  b. 管理磁盘数据【磁盘数据的文件格式、磁盘数据的增删查改】
  c. 读写算子【数据写入逻辑、数据读取逻辑】

一个sql的执行流程

设计数据库存储的要点

1. 性能瓶颈在哪里：数据选择、数据读取、构造内存数据、计算
2. 选择什么样的数据格式：是否可以并发处理、是否可以构建索引、行存，列存 或者 行列混合存储
3. 选择什么样的索引：读写的方式：读多写少、读少写多、点查场景、分析型场景

列式存储

什么是列存

1. 行存的存储

2. 列存的存储

列存的优点

a. 数据压缩

• 数据压缩可以使读的数据量更少，在IO密集型计算中获得大的性能优势
• 相同类型压缩效率更高
• 排序之后压缩效率更高
• 可以针对不同类型使用不同的压缩算法
• 几种常见的压缩算法

【LZ4】

输入：abcde_bcdefgh_abcdefghxxxxxxx

输出：abcde_(5,4)fgh_(14,5)fghxxxxxxx
复制代码

(5,4) 代表向前5个byte，匹配到的内容长度有4，即"bcde"是一个重复

重复项越多或者越长，压缩率就会越高

【Run-length encoding】

输入：WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

输出：12W1B12W3B24W1B14W
复制代码

压缩重复的数据

【Delta encoding】

输入：105, 135, 112, 135, 143, 147

输出：105(base),30, -23, 23, 8, 4
复制代码

将数据存储为连续数据之间的差异，而不是直接存储数据本身

b. 数据处理

【查询优化】1.可以选择特定的列做计算而不是读所有列 2.对聚合计算友好

【延迟物化】

• 物化：将列数据转换为可以被计算或者输出的行数据或者内存数据结果的过程，物化后的数据通常可以用来做数据过滤，聚合计算，Join

• 延迟物化：尽可能推迟物化操作的发生

• 缓存友好
• CPU / 内存带宽友好
• 可以利用到执行计划和算子的优化，例如filter
• 保留直接在压缩列做计算的机会

【向量化】

• SIMD
  single instruction multiple data，对于现代多核CPU，其都有能力用一条指令执行多条数据
  对于代码

for (size_t i = 0; i < 100; ++i) 
 c[i] = a[i] + b[i];
复制代码

非向量化执行

c[0] = a[0] + b[0]; 
c[1] = a[1] + b[1];
... ... 
复制代码

如果这时候CPU也可以并行的计算我们写的代码，那么理论上我们的处理速度就会是之前代码的100倍，幸运的是SIMD指令就是完成这样的工作的，用SIMD指令完成这样代码设计和执行就叫做向量化

• 执行模型
  数据需要按批读取
  函数的调用需要明确数据类型

• 列存数据库适合设计出这样的执行模型，从而使用向量化技术

列存 VS 行存

ClickHouse的存储设计

ClickHouse的架构

1. 架构图

2. 表定义和结构

3. 集群架构

ClickHouse的存储架构

1. 数据结构

a.文件组织

b.文件内容

对于表

CREATE TABLE test.test_insert_local
(
    `p_date` Date,
    `id` Int32
)
ENGINE = MergeTree
PARTITION BY p_date
ORDER BY id
SETTINGS index_granularity = 8192
复制代码

它的文件组织

├── 20220101_1_1_0
│   ├── checksums.txt
│   ├── columns.txt
│   ├── count.txt
│   ├── data.bin
│   ├── data.mrk3
│   ├── default_compression_codec.txt
│   ├── minmax_p_date.idx
│   ├── partition.dat
│   ├── primary.idx
│   └── versions.txt
├── 20220102_2_2_0
│   ├── checksums.txt
│   ├── columns.txt
│   ├── count.txt
│   ├── data.bin
│   ├── data.mrk3
│   ├── default_compression_codec.txt
│   ├── minmax_p_date.idx
│   ├── partition.dat
│   ├── primary.idx
│   └── versions.txt
├── detached
└── format_version.txt
复制代码

c. part和partition

• part是物理文件夹的名字
• partition是逻辑结构

d. part和column

• 每个column都是一个文件
• 所有的column文件都在自己的part文件夹下

e. column和index

• 一个part有一个主键索引
• 每个column都有列索引

索引设计

1. 主键索引

CREATE TABLE hits_UserID_URL
(
    `UserID` UInt32,
    `URL` String,
    `EventTime` DateTime
)
ENGINE = MergeTree
PRIMARY KEY (UserID, URL)
ORDER BY (UserID, URL, EventTime)
SETTINGS index_granularity = 8192, index_granularity_bytes = 0;
复制代码

2. 数据按照主键顺序一次排序
   UserID首先做排序,然后是URL,最后是EventTime

3. 数据被组织成granule

• granule是引擎做数据处理的最小数据单位，引擎读数据的时候不是按照一行一行读取的，而是最少读取一个granule
• 方便构建稀疏索引
• 方便并行计算

4. 每个granule都对应primary.idx里面的一行

5. 默认每8192行记录主键的一行值，primary.idx需要被全部加载到内存里面

6. 每个主键的一行数据被称为一个mark

7. 每个列都有这样一个mark文件，mark文件存储所有granule在物理文件里面的地址，每一列都有一个mark文件

8. mark文件里面的每一行存储两个地址

• 第一个地址称为block_offset，用于定位一个granule的压缩数据在物理文件中的位置，压缩数据会以一个block为单位解压到内存中。
• 第二个地址称为granule_offset，用于定位一个granule在解压之后的block中的位置。

索引的缺陷和优化

1. 缺陷：数据按照key的顺序做排序，因此只有第一个key的过滤效果好，后面的key过滤效果依赖第一个key的基数大小

2. 二级索引

• 在URL列上构建二级索引

3. 构建多个主键索引

• 再建一个表(数据需要同步两份,查询需要用户判断查哪张表)

• 建一个物化视图(数据自动同步到隐式表,查询需要用户判断查哪张表)

• 使用Projection(数据自动同步到隐式表,查询自动路由到最优的表)

数据合并

• 一个part内的数据是有序的

• 不同part之间的数据是无序的

• 数据合并是将多个part合并成一起的过程

• part的合并发生在一个分区内

• 数据的可见性
  数据合并过程中，未被合并的数据对查询可见
  数据合并完成后，新part可见，被合并的part被标记删除

数据查询

1. 对于查询

SELECT
    URL,
    count(URL) AS Count
FROM hits_UserID_URL
WHERE UserID = 749927693
GROUP BY URL
ORDER BY Count DESC
LIMIT 10
复制代码

2. 通过主键找到需要读的mark
3. 切分marks，然后并发的调度reader

4. Reader 通过mark block_offset得到需要读的数据文件的偏移量
5. Reader 通过mark granule_offset得到解压之后数据的偏移量

1. 构建列式filter做数据过滤

ClickHouse的典型使用场景

大宽表存储和查询

1. 动态表结构

CREATE TABLE test_multi_columns
(
    `p_date` Date,
    `id` Int32,
    `map_a` Map(String, Int32)
)
ENGINE = MergeTree
PARTITION BY p_date
ORDER BY map_a
复制代码

1. map中的每个key都是一列

2. map中的每一列都可以单独的查询

3. 使用方式同普通列，可以做任何计算

4. 大宽表查询

可以建非常多的列查询的时候引擎可以快速选择需要的列，查询的时候引擎可以快速选择需要的列

离线数据分析

1. 数据导入

数据可以通过spark生成clickhouse格式的文件

导入到hdfs上由hive2ch导入工具完成数据导入

数据直接导入到各个物理节点

2. 数据按列导入

保证查询可以及时访问已有数据

可以按需加载需要的列

实时数据分析

1. 数据可以被立刻查询
2. 使用memory table减少parts数量

• 数据先缓存在内存中
• 到达一定阈值再写到磁盘

复杂类型查询

1. bitmap索引

• 构建

• 查询
  

2. bitmap64类型

select countDistinct(uid)
from user_detial
where tag_id = 'a' and uid in 
(
    select uid from user_detail
    wherer tag_id = 'b'
)  
复制代码

3. lowcardinality

• 对于低基数列使用字典编码
• 减少数据存储和读写的IO使用
• 可以做运行时的压缩数据过滤

课后

1. 列存和行存的差别是什么，使用场景有什么不同
2. 列存的优点有哪些
3. 列存的缺点有哪些
4. 列存适合什么样的索引
5. ClickHouse的列存是什么样的存储架构
6. ClickHouse的索引是怎么设计的
7. ClickHouse的查询是怎么使用索引的