共计 10564 个字符，预计需要花费 27 分钟才能阅读完成。
简介：PolarDB MySQL 是阿里云自研的云原生数据库，次要解决在线事务负载 (OLTP, OnLine Transactional Processing)，深受企业用户的青眼。前言数据库迁徙上云是大数据时代的一大趋势，PolarDB MySQL 是阿里云自研的云原生数据库，次要解决在线事务负载(OLTP, OnLine Transactional Processing)，深受企业用户的青眼。当下，数据分析对于企业的重要性越发显著：企业应用数据驱动决策，利用剖析后果精准调配资源，从而降低成本，晋升企业效率，推动业务翻新，疾速适应外部环境的变动。然而，传统数仓架构的滞后性限度了企业的翻新步调。因而，企业对 OLTP 数据库提出更高的要求，心愿能在 OLTP 数据库同时进行简单的实时剖析(OLAP, OnLine Analytical Processing)，及时应答业务环境的高速变动。为满足混合负载(HTAP, Hybrid Transactional/Analytical Processing) 的需要，局部客户抉择了 MySQL + Clickhouse 的计划，但困扰于着两套独立零碎的高应用和高保护老本，以及零碎间的数据不统一等问题。客户寻求在一套零碎上完满地应答 HTAP 负载的解决方案。对此，PolarDB MySQL 技术团队提出了基于 In-Memory Column Index(以下简称 IMCI)的 HTAP 技术计划，在 PolarDB MySQL 行存反对 OLTP 的根底上，原生地构建列存索引以及实现列存计算引擎，反对高效地实时剖析，在 TPC- H 测试中取得数百倍于行存的减速成果。对于 PolarDB HTAP 和 IMCI 的具体介绍参考《400 倍减速, PolarDB HTAP 实时数据分析技术解密》[1]。本文介绍数据的压缩办法以及 PolarDB HTAP 在列存数据压缩上的工作。PolarDB MySQL 作为云原生数据库，具备存储计算拆散的特点，计算资源独能够进行按需分配，而存储始终固定存在且持续增长的，须要压缩对存储老本进行管制。IMCI 的数据存储是为列存格局，列数据相比于行数据具备更高的相似性，利于数据压缩。通过压缩，IMCI 在大部分业务场景将列存存储空间缩小到十分之一，大幅缩小客户的存储老本。另外 IMCI 通过数据压缩，缩小数据的大小和存储拜访开销，并探索将计算下推到压缩数据从而减速剖析，进一步为客户提供更好的 OLAP 查问性能，实现 HTAP 零碎性能和老本的兼得。后文次要分为 4 个局部，在“数据压缩概述”局部咱们从数据压缩的实践根底——信息论谈起，联合数据库中的数据压缩问题进行探讨。在“压缩算法分类和介绍”中，咱们将压缩办法分为通用压缩和轻量压缩，介绍数据库中最常见的通用压缩办法原理，而后逐个介绍轻量压缩，并探讨字符串的轻量字典压缩，为下一个局部铺垫。在“提早解压减速计算”局部，咱们介绍压缩数据上的间接查问的优化技术，又称为提早解压技术，而后剖析基于字符串字典压缩优化的原理和难点。最初，咱们进行“总结以及后续工作”的探讨，瞻望 PolarDB HTAP 在数据压缩方向的后续工作。数据压缩概述压缩算法包含无损压缩和有损压缩，本文咱们只探讨无损压缩，即解压后的文本与压缩前的文本完全相同，后文的“压缩”都是指无损压缩。压缩算法由编码和解码两局部形成，编码和解码实质上是将文本映射到另一个更紧凑的文本空间以及逆映射的过程。压缩与概率是严密相干的。所有的压缩算法对于输出数据都有肯定的事后假如，这种假如能够用概率形容，例如假如某种数据反复的概率或某几种数据一起呈现的概率高。香农的论文《通信的数学原理》，被视为古代信息论钻研的开始，正是信息论将数据呈现的概率和数据所需编码长度分割起来。在论文中，香农从统计物理学中借鉴了熵的概念，定义了信息熵[2]:
H(S)即信息熵，S 是所有信息 s 形成的汇合，p(s) 是信息 s 呈现的概率，s ∈ S。i(s)示意须要编码单个信息所须要的比特数，而信息熵 H(S)是 i(s)以概率 p(s)为权重的加权均匀，示意编码信息汇合 S 所需的总比特数。举个例子简略了解这两个公式。咱们假如 96 个可打印字符呈现的概率雷同，那么编码每个字符须要的均匀比特数，即 i(s) = log_2(96) = 6.6 bits/char，显然，至多 7 bits 才能够示意 96(2^7=128)个不同的字符。如果咱们基于一个英文文本集 (例如 Calgary Corpus) 进行统计，应用字符的频率近似概率，计算出信息熵的平均值 i(s)为 4.5 bits/char，具体编码能够通过 huffman 编码算法失去。这个估算认为字符间是独立的，如果思考上相邻字符、单词间的关联联合超大文本进行统计，编码字符所须要的比特数是 1.3 bits/char，8/1.3 = 6.15 近似为任意英文文章的压缩比的上界。通用压缩算法对输出数据仅做简略的假如，如假如数据存在部分相似性等。GZIP 和 BOA 在 Calgary Corpus 文本集的压缩成果为 2.7 bits/char 和 2.0 bits/char，如果要更靠近英文文本的压缩上界，通用压缩算法须要英文词频和语法等作为输出，这将影响其通用性。咱们在下一部分对常见通用压缩算法的原理进行简略介绍。
编码可打印字符所须要的比特数，因而数值越小，阐明压缩成果越好，图源自[2]。理解压缩与概率的关联后，咱们看看数据库系统中的数据压缩问题。首先咱们关注 OLTP 数据库和 OLAP 数据库的数据存储格局，常见的 OLTP 数据库的存储引擎包含基于 B +Tree 的 innodb 和基于 LSM-Tree 的 X -Engine 和 rocksDB 等，它们应用行式存储，表数据按行程度宰割，每个记录会蕴含各个不同的列。而 OLAP 数据库应用列式存储，表数据按列垂直宰割，每列数据独自存储。假如应用通用压缩算法，同一列数据的部分相似性个别高于不同的列，因而列存相比行存人造具备更高的压缩比。
行式存储，表数据按行程度宰割 vs 列式存储，表数据按列垂直宰割 另一方面因为列存按列组织数据，因而不同的列能够抉择不同的压缩算法，在下一部分咱们将看到轻量压缩依据不同列的类型和特色，借此取得远高于通用压缩的压缩比和压缩解压性能。论文 [3] 剖析了列存绝对行存减速查问的起因，包含高压缩，批处理和提早物化等，其中仅思考压缩，相比行存，列存数据库均匀取得 10 倍以上的查问减速比。咱们在 IMCI 的 TPC- H 测试中验证了这一论断，而且在业务实在数据中能够达到均匀 10 倍的压缩比。可见数据压缩对于列存数据库尤为重要。压缩算法分类和介绍学术上对于压缩算法曾经有了相当充沛的钻研，最新的学术工作开始摸索深度学习办法更准确地预计数据的概率分布，从而晋升压缩比，但暂未有大规模的理论利用。大部分压缩算法的区别在于工程上的优化。咱们将压缩分为通用压缩和轻量压缩，通用压缩对输出不做简单的假如，以块为粒度压缩数据，实用于各类数据；轻量压缩的应用存在限度条件，须要数据满足肯定个性，例如有序性，distinct 值少等，但压缩比，压缩和解压速度上优于通用压缩，并能进一步优化查问。两类压缩算法不抵触，通常会联合应用取得更高的压缩比。通用压缩咱们简要介绍 LZ4 和 ZSTD，它们是在目前数据库畛域最为罕用的两种疾速压缩算法，绝对于其余通用压缩算法，它们的压缩和解压性能较为突出，更适宜数据库的数据拜访模式。LZ4 的特点是解压速度快，但压缩比个别，在 lzbench 规范测试中，解压速度达到 4.97GB/s。Zstd 全称为 Zstandard，定位是提供高压缩比的疾速压缩算法，由 Facebook 于 2016 年公布的。Zstd 采纳了无限状态熵（FSE，Finite State Entropy）编码器，取得了更高的压缩比的同时解压性能依然放弃在较高水平，lzbench 测试中解压速度到 1.38GB/s。事实上，包含 LZ4 和 ZSTD 在内，常见的 snappy, zlib, gzip 等压缩算法都属于 LZ77 算法的变体，因而咱们简略介绍 LZ77 算法的原理。LZ77 算法及其变体都应用了随 cursor 挪动的滑动窗口。Cursor 指向以后须要压缩的第一个地位，并把窗口分为两局部，cursor 之前的局部，称为字典；蕴含 cursor 开始的局部，称为 lookahead buffer。这两个局部的大小是由参数设置，在算法执行过程中是固定的。根本算法非常简单，循环执行以下步骤：查找从 cursor 开始并齐全蕴含在 lookahead buffer 中的字符串与字典中的字符串的最长匹配。输入一个压缩后果三元组 (p, n, c)，为字典中的地位 p、匹配的长度 n 和匹配局部的下一个字符 c。p 是绝对 cursor 的间隔，具体含意是匹配字符串在字典中的第一个字符绝对 cursor 的偏移量。将光标向前挪动 n + 1 个字符。咱们举个例子，如下图所示，应用 LZ77 算法压缩字符串 aacaacabcabaaac，围绕字符的方框示意 cursor，加粗的字符串局部是字典，大小为 5，下划线字符串局部为 lookahead buffer，大小为 4(包含 cursor 指向的字符)。
LZ77 算法压缩字符串 aacaacabcabaaac, 压缩后果为 (0, 0, a), (1, 1, c), (3, 4, b), (3, 3, a), (1, 2, c) step1: 滑动窗口的字典局部为空，lookahead buffer 为 aaca，字典为空无奈匹配，间接输入(0, 0, a)。step2: 以后字典为 a，lookahead buffer 为 acaa，匹配 a 后的下一个字符为 c，输入(1, 1, c)。step3: 以后字典为 aac，lookahead buffer 为 aaca，在 step3 中，未优化的状况下，匹配到 aac 时应该完结，优化解决后理论匹配的字符串为 aaca，下一个字符为 b，输入(3, 4, b)。step4: 以后字典为 caacab，lookahead buffer 为 caba，匹配 cab 后的下一个字符为 a，输入(3, 3, a)。step5: 以后字典为 abcaba，lookahead buffer 为 aac，相似 step3，匹配 aa 后的下一个字符为 c，输入(1, 2, c)。step3 和 step5 产生的(3,4,b) 和(1,2,c)比拟非凡，仔细观察会发现匹配的字符串超出了字典，即 n > p，此时字典匹配在 cursor 的边界 [cursor – p, cursor – 1]，这部分被当成 ring buffer, 匹配到开端后又从头开始匹配，实现了对间断反复字符串的编码优化，这个压缩成果和上面介绍的轻量压缩中的 RLE 编码成果类似。联合解压过程动静产生字典的过程，能够更好了解这个解决。解压比较简单，整个过程是边解压边应用之前解码的数据作为以后字典。step3 和 step5 的须要非凡解决，当字典中呈现的地位 p 小于匹配的长度 n，将 p 到 cursor 的字符串复制 n / p 次后加上剩下的 n % p 个字符即可。从 LZ77 算法的原理中，咱们不难理解为什么 LZ4, ZSTD 等 LZ77 变种的算法在压缩和解压方面的性能具备不对称性。这种不对称性体现在随着压缩等级增大，压缩比减少，压缩速度降落，但解压速度简直不受影响，因为压缩过程中的计算复杂度取决于字典窗口的大小和匹配字符的长度等，而解压的过程仅仅是从字典中定位，拷贝数据到输入中。轻量压缩前文提到通用压缩以块为粒度压缩数据，这导致数据的随机拜访存在读放大问题，即读取一个记录须要将块中所有的记录进行解压，计算代价大。这在内存计算为主的场景中重大影响性能，因而通用压缩罕用于落盘数据，而内存压缩，应用轻量压缩办法。上面分字符串类型编码，数值类型编码，数据类型无关编码三个类别探讨轻量压缩办法。[字符串类型编码]Prefix 编码：前缀编码(incremental encoding/front coding)，通过将字符串按字典序排列，将以后字符串示意为和上一个字符串反复的局部的长度 + 不反复的残余局部。[数值类型编码]FOR 编码：FOR，Frame Of Reference 存储与最小值进行相减后的后果。毋庸数据有序，压缩和解压速度很快，能够在压缩后的数组上进行 O(1) 随机访存，只须要额定存储的最小值信息。Delta 编码：存储两两相邻相减的后果，有序存储的数据，两两相邻相减后的后果取值范畴很小，例如主键两两相邻相减后近似常数。NS 编码: Null Supression, NS 算法实质是设计新的编码，尽量只存储数据的无效位 (非 0 位)，节俭前缀存在的间断的 0 的存储开销。学术界次要关注这类轻量压缩算法，设计了诸多编码联合 SIMD 优化, 代表性的 varint-GB, SIMD-BP128, simple_8b, fastpfor 等，也在业界宽泛应用，例如 google 的 protobuf 即应用了 varint 进行编码。NS 假如待压缩数据为非正数(因为正数补码最高为 1，不存在有效位)。常见和 FOR 编码, Delta 编码等联合应用，例如 FOR 编码, Delta 编码逻辑上将数据范畴从 int64 放大到 int16，再应用 NS 编码将数据物理存储代价缩小到 int16 即可。[数据类型无关编码] 字典编码：字典编码实质是将重复性较高的一段数据作为字典 entry，应用字典下标 number 代替原文的字典 entry，达到压缩的目标。解压过程，将下标对应的数据从字典中取出即可。咱们按字典 entry 的设计简略将字典编码分为三个子类。Entry 为残缺的单个记录 (例如残缺的字符串)，编码后原数据用字典中的下标代替，实用于 distinct 值较少的列。应用 base + offset 解决数值数据，Entry 为 base，原数据编码后为(下标, offset) 的二元组。应用 common prefix + suffix 解决二进制数据，Entry 为 common prefix，编码后为 (下标, suffix) 的二元组。RLE 编码：要求间断反复的数据尽可能集中在一起，因而须要排序。编码后果为 (value，length，position) 的三元组，例如 0，0，1，1，1… 的数据，编码为(0, 2, 0)，(1, 3, 2)，压缩成果取决于 avg run length，压缩比近似 data size/avg run length。Bitmap 编码：distinct 值极其少的状况下应用 bitmap 压缩，例如数据为性别 male, female，转化为两个 bit 位数等同于列数据长度的 bitmap。bitmap 自身就有汇合的语义，能够用于 group by 等操作的优化以及汇合运算。Constant 编码：针对近似 Constant 的数据，呈现频率最高的数据视为 Constant，而只记录所有不等于这个 Constant 的异样值和它们的行号，Constant 编码在理论业务数据中对应应用了默认值的列。比照通用压缩算法和轻量压缩算法介绍，不难发现轻量压缩算法的压缩和解压较为简单，计算代价小，并且压缩后的数据依然能够参加计算，例如 RLE 编码后的数据用于减速求和，FOR 编码的数据更紧凑，CPU 计算效率更高。字符串的轻量字典压缩本节咱们展开讨论字符串的字典压缩算法，咱们按构建字典 entry 的粒度将字典压缩分为三类：对整个字符串，子字符串和单个字符编码的字典。别离应用 direct map，pattern map，char map 辨别三类算法。这三类算法及对应的典型算法如下：direct map: dictionarypattern map: FSST，见论文[4]char map: huffman 其中，从算法 1 -> 算法 3，算法的通用水平低 -> 通用水平高，解压速度高 -> 解压速度低，压缩比则与理论数据的散布无关。对于 cardinality 较小的数据如 category 类的数据应应用 dictionary，可取得较高的压缩比。对于 pattern skew 的状况，例如 urls 汇合，FSST 更实用。Huffman 编码在 GZIP 和 ZSTD 中应用，应用 Huffman 编码对滑动窗口压缩过的数据再进行压缩，进一步减少压缩比。字典压缩算法通常具备保序性: 如下图所示字典映射后原字符串和编码绝对程序不变，不便间接在压缩数据上进行 range 查问优化。
保序性示例，压缩编码后的数据程序不变, abc(8) < abcdef(17) < xyz(95)，括号内为编码后的数据 编码方式的变长 vs 定长，变长的压缩比更高，但解压速度更慢，变长数据通过 padding 能够转化为定长，便于应用 SIMD 减速计算。direct map 则是定长编码，而 pattern map 和 char map 为变长，编码方式影响三者的解压速度。
三类字符串字典压缩示例，从左到右，压缩的粒度从高到低，通用水平低 -> 通用水平高，解压速度高 -> 解压速度低。提早解压减速计算数据压缩能缩小存储空间和 IO 的开销，代价是须要领取额定的计算资源对数据进行解压，是工夫换空间的 trade-off。因为 IO 带宽相比计算资源更容易成为瓶颈，因而开启压缩后，性能会晋升。但数据在内存压缩时，数据解压占用计算资源，升高并行度，可能导致列存查问成倍的性能降落。因而如果条件容许，防止解压或者提早解压，间接在压缩数据上查问是有必要的。例如对于以下查问：SELECT COUNT(1) FROM table_a WHERE col_1 = “xxx”; 假如咱们将 col_1 列数据以压缩后的编码寄存，并在执行查问时应用字典将查问条件中的字符串 ”xxx” 映射为数字，查问时就能应用字典压缩后果与 ”xxx” 的映射值间接进行比拟，从而将 string 比拟转化为 int 数据比拟，可缩小内存带宽压力和计算代价，进步性能。可见在特定的查问和应用了特定的压缩算法下，咱们可能间接在压缩数据上查问，因为数据压缩后比拟的计算量减少，内存中可 cache 更多数据，查问性能将有显著的晋升。Oracle IMC，DB2 BLU 等列存产品实现了尽可能防止解压操作的优化，而且将该优化作为和同类列存产品比照的一个重要特色。本节咱们介绍论文 [5] 的间接查问压缩数据的算法原理。反对提早解压的算子 [SCAN 下推]Scan 算子的提早解压减速，次要是谓词下推，在压缩数据上间接过滤。string 类型数据，对于 string 类型字典压缩：应用保序 direct map 字典编码，压缩后数据类型由 string -> int，通过重写查问，将 string 比拟转化为 int 数据比拟，可反对 QE, NE, Between, LT, GE, IN, 前缀的 like 等比拟，实用于 cardinality 不大的列(50,000~100,000)。
direct map 字典编码，编码后的数据具备保序性，图中 ’Whole Milk*’ 含糊匹配被改写为 p_name 的 [32000, 32100] 中的 range 查问。应用 Pattern map 例如 FSST, 压缩后依然是 string，可反对 QE, NE, IN 等操作。因为 Pattern map 字典不保序摸，因而只反对点查问的提早解压。
Pattern map 字典的查问改写。提早解压次要减速点查问。int 类型数据，例如 int64 类型应用 FOR 算法压缩到 15bits，当查问条件为 col = value，则将 value 改写为 value – min 即可。[JOIN]论文 [5] 提到 RLE 和 bit vector 编码，以 nested loop join 为例，当发现其中一列为 RLE 时，便能跳过 k 次比拟 (k 是 run length)。此为如果应用了全局字典，即不同的列应用了雷同的字典压缩，那两列能够间接进行提早解压的比拟操作，返回匹配的行 id，从而减速 JOIN。[GROUPBY 聚合] 数据以 RLE 编码，bitmap 编码或者字典编码时能够减速 groupby 聚合。RLE，bitmap 和字典相当于曾经进行一轮聚类，在这根底上，能够对例如 aggregation, distinct 计算进行优化，例如 RLE 编码的求和转化为 v * run length 的和，distinct 相干计算仅须要扫描字典或者返回字典大小。压缩数据 SCAN 的谓词下推 AP 查问通常须要扫描大量落盘数据。压缩数据 SCAN 的谓词下推，常与字典压缩算法联合，实现提早解压减速查问。压缩数据 SCAN 的谓词下推，次要包含以下 3 个过程：元信息查看，是否合乎提早解压的条件。谓词改写，应用雷同的字典改写查问条件。谓词下推，扫描压缩数据，返回匹配行。实际上，在数据库中字符串的比拟，不仅须要思考 charset，还要思考 collation。Collation 定义了字符集中元素的程序，它实质是一种映射，将字符映射为可比拟程序的编码。如果 collation 为二进制序 binary，间接在压缩数据上比拟没有问题，但简直所有字符集默认的 collation 不是 binary，例如 latin1 字符集的默认 collation 为 latin1_swedish_ci，下图为该 collation 的局部截图。能够看到只管 A, a 等二进制编码不同，但在比拟时被认为是雷同。大部分 collation 问题在于它是 n 对 1 的映射关系，而无损压缩算法是 1 对 1 映射，因而无奈间接应用压缩后的编码进行比拟。
左侧为图例，collation 秩序图中能够看到在 latin1 字符集，collation 为 latin1_swedish_ci 的状况下，ascii 码为 41, 61, C0…E3 编码的字符在比拟时是雷同的 collation 序。咱们举个例子来阐明这个问题，字符串“abc”,“abcdef”,“xyz”,“åbc”字典压缩后为“8,17,95,100”，压缩后是保障字典序的，“abc”和“åbc”仅看压缩的编码“8”和“100”是不同的，在带 collation 的比拟时却被认为是同一个字符串，因而无奈使用提早解压，必须进行解压后应用带 collation 的比拟。那问题是能够应用 collation 程序代替字典序吗？显然是不行的，如果咱们只保留 collation，在这个例子中，如果要解码数字 1，它即能够是“abc”，又能够是“åbc”，无奈逆映射，可见 collation 只能用于程序的比拟。
带 collation 的比拟问题：在这个例子中，åbc 和 abc 在字典编码的地位是保序的 8 < 100，但理论比拟时带 collation 会认为它们雷同(都是 1)，如果心愿提早解压优化，那么 8 和 100 须要被映射到 1，这是一个额定信息，无奈在不解压字符串的状况下取得(黄色曲线示意 encode 空间到 collation 空间的变换，有个“X”示意无奈间接应用字符串的 collation 进行这个变换) 一个解决方案是通过额定保留 collation 后果，能够减速应用列默认 collation 进行比拟的查问。通过存储 collation 后果，能够在字符串比拟时节俭计算，毛病是存储 collation 编码须要额定内存和存储空间，对压缩比有更高的要求。在 IMCI 中，咱们验证了压缩数据 SCAN 的谓词下推成果，在不同的 scan 查问场景中取得了 3 ~ 20 倍的查问减速。总结以及后续工作数据压缩作为数据库一项重要技术，在列存执行中联合提早解压，在零碎性能和老本的均衡中起到关键作用。本文首先介绍数据压缩的实践根底，信息论，其为压缩成果定义了边界，而后剖析了数据压缩在行存和列存数据库中的不同。压缩办法分为通用压缩和轻量压缩，数据库中最常见的通用压缩算法 LZ4 和 ZSTD 都基于 LZ77 算法，而后咱们逐个介绍轻量压缩办法。随后咱们探讨轻量压缩数据上的间接查问技术，在该局部咱们介绍基于字典压缩实现字符串提早解压的原理，对性能的影响以及须要解决的问题。IMCI 是 PolarDB 迈向数据分析市场的第一步，接下来咱们将始终如一地深挖技术，联合业务场景，优化 HTAP 细节并落实到客户的理论利用，为客户降本增效继续赋能。最初，咱们瞻望 PolarDB HTAP 在压缩技术方面的后续工作：摸索压缩相干的最新的学术研究成绩在用户理论场景的最佳实际。在基于规定的列压缩抉择算法上，摸索并落地基于 schema 和数据特色实现按列的智能压缩算法抉择。摸索数据内存压缩技术，增大内存的数据密度，同时利用提早解压的技术计划，减速查问，实现性能和老本的兼得。参考 400 倍减速, PolarDB HTAP 实时数据分析技术解密 阿里云社区 Introduction to Data Compression. Guy E. Blelloch.Daniel J. Abadi, Samuel R. Madden, and Nabil Hachem. 2008. Column-stores vs. row-stores: how different are they really? In Proceedings of the 2008 ACM SIGMOD international conference on Management of data (SIGMOD ’08). Association for Computing Machinery, New York, NY, USA, 967–980.Peter Boncz, Thomas Neumann, and Viktor Leis. 2020. FSST: fast random access string compression. Proc. VLDB Endow. 13, 12 (August 2020), 2649–2661.Daniel Abadi, Samuel Madden, and Miguel Ferreira. 2006. Integrating compression and execution in column-oriented database systems. In Proceedings of the 2006 ACM SIGMOD international conference on Management of data (SIGMOD ’06). Association for Computing Machinery, New York, NY, USA, 671–682. 原文链接：https://click.aliyun.com/m/10… 本文为阿里云原创内容，未经容许不得转载。
