简介： 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和数据特色实现按列的智能压缩算法抉择。摸索数据内存压缩技术，增大内存的数据密度，同时利用提早解压的技术计划，减速查问，实现性能和老本的兼得。 立刻收费体验 PolarDB HTAP能力，2000元测试代金券限量领。----》https://www.aliyun.com/databa... 参考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...本文为阿里云原创内容，未经容许不得转载。