当数据库用户的要害业务零碎具备宏大数据量时，IT 老本、数据老本等都会居高不下，此时，通过压缩来升高存储老本是再天然不过的抉择。但对于很多数据库的用户而言，压缩并不能一劳永逸：抉择高压缩比，压缩、解压往往须要消耗大量工夫，通常也会升高内存、硬盘的读写性能，显然对提早敏感的要害业务场景不实用；抉择低压缩比，压缩文件仍然会占据不少硬盘空间，这又与压缩的初衷南辕北辙。
数据压缩最终目标是降本增效，降本不能就义效率，因而实现高压缩比的前提肯定是先保障高性能，这也是更适宜用户要害业务零碎的压缩计划。在往年 5 月举办的 2022 中国国内大数据产业博览会上，OceanBase 的“高压缩比分布式存储引擎”荣获了“当先科技成果奖”。OceanBase 获奖的要害起因是这一自研的引擎创造性地解决了传统数据库无奈均衡“性能”和“压缩比”的难题，本文也将分享咱们对破解这一难题的思考。
对于作者
赵赛铜（乘骥）
OceanBase 高级开发工程师，TPC-H 我的项目组成员。目前在 OceanBase 存储 - 剖析解决组，工作方向是存储构造和剖析解决性能的保护与开发。
作为齐全自主研发的原生分布式数据库，OceanBase 在存储架构、数据编码、数据日志等方面一直挑战技术极限，进一步拓展了高级压缩技术能力的边界。其中，基于数据编码的存储压缩技术是 OceanBase 实现高压缩比的核心技术之一，OceanBase 自研了一套对数据库进行行列混存编码的压缩办法 (encoding），应用列级别的字典、差值、前缀等编码算法，在通用压缩算法之前对数据进行编码压缩，能够在不影响数据读写性能的同时，显著进步数据压缩率，帮忙用户大大降低存储老本。本篇文章将分享 OceanBase 对数据库压缩技术的思考，介绍咱们在数据编码畛域的技术创新思路与计划：
数据压缩到底在解决什么问题；
如何做出更适宜理论业务场景的数据压缩；
数据编码压缩的成果测试。
数据压缩到底在解决什么问题？
通常而言，数据压缩是计算机依照肯定的算法对数据进行解决，变换成占用更小空间格局的过程，能进步数据的传输、存储和解决效率。以常见的摩斯电码为例，它将文本中呈现概率高的字母 (e, t, i) 借助用时比拟短的编码来示意。这样做能够进步发送电报的效率，在雷同的工夫传输更多字符，此种办法就可了解为一种数据压缩。
与此同时，从摩斯电码的设计中咱们也不难看出压缩算法的成果是和数据的散布与特色相干的，不同的零碎也会针对本人的数据特色和利用场景采纳不同的压缩算法。在数据库畛域，存储的数据会受到 schema、类型、值域等限度，类似度会比拟高，存储的数据也会存在一些冗余，这些特色使得数据库中的数据能够被更好地编码与压缩。
保障高性能的压缩，才是用户须要的压缩
目前市面上的数据库产品根本都提供了压缩性能，然而因为存储引擎架构和数据库利用场景的不同，产品之间的数据库压缩设计和能力也会产生一些差异。
传统的事务型数据库通常应用定长块存储数据，这样能够保障读写性能，但会带来额定开销和空间节约。面向 OLTP 场景的数据库要在数据的写入和更新场景反对更高的 TPS，通常会应用行存及 B +Tree 类的存储引擎，对于数据的压缩会比拟激进。这样的存储引擎通常会将定长的内存数据页与长久化数据块对应起来治理数据，而且有些状况下须要将更新数据实时写到数据块中，会导致对页内大量行进行 dml 操作也须要对整个数据页进行从新压缩，带来更多的 overhead；而且定长数据块在进行压缩前难以确定压缩后的数据块大小，也会带来一些空间节约等问题。
另一方面，剖析型数据库人造更适宜高压缩比，但压缩会升高查问和更新性能。面向 OLAP 场景的数据仓库等零碎的数据，通常是批量导入的，增量数据绝对较少。因而剖析型数据库通常应用列存，增量数据写日志，定期重整基线数据的存储引擎。这样的存储引擎通常在批量导入和后盾数据重整时进行数据压缩，并采纳压缩比更高的压缩策略。如以更大的数据块为单位进行压缩，将更多数据压缩到同一个数据块中，将同一列的数据存储在相邻的数据中，并针对这一列数据的特色对数据进行压缩率更高的编码。但压缩后，可能会明显降低数据的点查性能，减小数据更新的 tps。
总结来说，应用压缩率越高的压缩算法，压缩和解压数据的 overhead（开销）就越大，对读写性能影响也越大。同时，在咱们和用户的交换中也发现，相较于数据压缩率，用户往往更在意数据库性能，尤其是在要害业务场景中。如果在读写门路上对数据进行压缩和解压，会不可避免地耗费计算资源，也会对事务处理性能带来影响。因而，在传统数据库解决业务的场景中，出于性能思考，广泛只会对归档或备份等拜访不频繁的数据开启压缩性能，而对查问和更新比拟频繁的数据只能放弃压缩，以满足业务的性能要求。
只有在保障高性能的前提下实现高压缩，才是真正对用户有价值的高压缩，也能实现真正的降本增效。OceanBase 基于 LSM-Tree 架构自研的存储引擎，实现了对 OLTP 与 OLAP 负载的同时反对，也能在提供高效的事务处理能力的同时，依据数据存储的特色进行自适应编码压缩，提供高效的数据压缩能力。在过来服务用户的教训中，OceanBase 的存储空间甚至能够升高到用户原有数据库系统存储空间的十分之一，能为企业降本增效施展重要作用，帮忙企业更好地打造外围竞争力。
OceanBase 如何做好数据压缩
LSM-Tree 存储架构为数据库压缩提供了更多的可能
只管对 B+ 树类的存储引擎进行更高效的压缩也有很多钻研，例如在 FAST 2022 上，《Closing the B+-tree vs. LSM-tree Write Amplification Gap on Modern Storage Hardware with Built-in Transparent Compression》这篇论文通过可计算存储硬件 (Computational storage device)，利用存储硬件外部的通明压缩能力对 B 树类存储引擎的数据压缩进行优化，使其写放大达到了靠近 LSM-Tree 架构存储引擎的成果。 但 LSM-tree 中内存数据页更新与数据块落盘解耦，和 sstable 数据紧凑排布的特点，使得 LSM-tree 绝对 B 树类存储引擎，依然更适宜在对查问 / 更新带来更少负面影响的前提下实现更高效的数据压缩。
利用好批量数据落盘的个性，能力实现更高效的压缩
因为 LSM-Tree 的构造个性，OceanBase 的长久化数据是批量落盘的，将变更数据保留在内存中，并通过后台任务批量写入到磁盘上，这样做能够让数据块治理更简略：
- 打消了传统 B+Tree 的磁盘随机写瓶颈和存储空间碎片化问题，使得数据写入性能比传统的实时更新数据块的形式更高；
- 能够将数据更新（增删改）与压缩动作解耦，数据更新门路上没有压缩动作，对性能影响更小；
- 在批量落盘的过程中，数据库能够自适应地调整数据块中的数据数量，并在间断对数据块进行压缩的过程中，利用上一个块的压缩率等先验常识对下一个块进行更好的压缩。
OceanBase 充分利用批量数据落盘的个性，实现了更高的数据压缩比。在 OceanBase 中数据的更新会写入到 clog 和 memtable 中，OceanBase 的 memtable 是内存中的 B+ 树索引，提供高效的事务处理能力。memtable 会定期通过 compaction 生成硬盘长久化数据 sstable，多层 sstable 会采纳 leveled compaction 策略进行增量数据重整。sstable 中数据块的存储分为两层，其中 2M 定长的数据块 (宏块) 作为 sstable 写入 IO 的最小单元，存储在宏块中的变长数据块（微块）作为数据块压缩和读 IO 的最小单元。
数据编码不应该成为手动挡，它应该成为自动挡
咱们认为让数据库来抉择数据的编码方式，有利于用户更好地应用编码性能。OceanBase 的自适应编码技术会主动为每个数据块抉择适合的编码算法，充沛升高用户的学习老本。OceanBase 从 2.0 版本开始引入了行列混存的微块存储格局（PAX），充分利用了同一列数据的局部性和类型特色，在微块外部对一组行以列存的形式存储，并针对数据特色按列进行编码。变长的数据块和间断批量压缩的数据也能够让咱们通过同一个 sstable 中曾经实现压缩的数据块的先验常识来对下一个数据块的压缩进行领导，在数据块中压缩尽量多的数据行，并抉择更优的编码算法。也正是 LSM-Tree 的存储架构使得 OceanBase 能在事务性能和压缩率上获得更好的均衡。
如何做出更适宜理论业务场景的数据压缩
实现更高压缩率的要害：通用压缩 + 数据编码
OceanBase 中同时反对不感知数据特色的通用压缩 (compression) 和感知数据特色并按列进行压缩的数据编码 (encoding)。这两种压缩形式是正交的，也就是说咱们能够对一个数据块先进行编码，而后再进行通用压缩，来实现更高的压缩率。
OceanBase 中的通用压缩是在不感知微块外部数据格式的前提下，将整个微块通过通用压缩算法进行压缩，依赖通用压缩算法来检测并打消微块中的数据冗余。目前 OceanBase 反对用户抉择 zlib, snappy, zstd, lz4 算法进行通用压缩。通常 snappy 和 lz4 压缩速度比拟快，但压缩率比拟低，其中 lz4 压缩与解压的速度会更快一些。zlib 和 zstd 压缩率比拟高然而压缩速度绝对更慢，其中 zstd 解压速度会更快一些。用户能够依据表的利用场景，通过 DDL 对指定表的通用压缩算法进行配置和变更。
因为通用压缩后的数据块在读取进行扫描前须要对整个微块进行解压，会耗费肯定 CPU 并带来 overhead。为了升高解压数据块对于查问性能的影响，OceanBase 将解压数据的动作交给异步 IO 线程来进行，当数据块的 IO 完结后，会调用回调函数对数据块进行解压，并按需将解压后的数据块放在 block cache 中。这样联合查问时对预读 (prefetching) 技术的利用，能够为查询处理线程提供数据块的流水线，打消掉解压带来的额定开销。
通用压缩的长处是对被压缩的数据没有任何假如，任何数据都可能找到模式并压缩。但对于关系型数据库来说系统对数据库内存储的结构化数据有着更多的先验常识，OceanBase 认为利用这些先验常识能够对数据进行更高效的压缩。
OceanBase 的数据编码算法
上文提到在关系型数据库中，因为 schema 和数据类型的限度，同一列的数据类型，精度，值域往往都是雷同的。而且在理论利用中，同一列中相邻的数据也通常会有本人的特色。如上面两个场景：
- 业务中通过一列数据存储城市，性别，产品分类等具备类型属性的值时，这些列数据块外部数据的基数 (cardinality) 也会比拟小，这时数据库能够间接在用户数据字段上建设字典，来实现更高的压缩率；
- 在有的业务场景中数据是按时序插入到数据库中的，那么这些插入的数据行中的工夫相干字段，自增序列等数据的值域会绝对比拟小，也会有枯燥递增等个性，那么利用这些个性数据库也能够更不便地为这些数据做 bit-packing，差值等编码。
为了实现更高的压缩比，帮忙用户大幅升高存储老本，OceanBase 设计了多种编码算法，最终在 OceanBase 的负载上实现了很好的压缩成果。OceanBase 依据理论业务场景需要实现了单列数据的 bit-packing 编码、字符串 HEX 编码、字典编码、RLE 编码、常量编码、数值差值编码、定长字符串差值编码，同时也翻新地引入了列间等值编码和列间子串编码，可能别离对数据库中一列数据或几列数据间可能产生的不同类型数据冗余进行压缩。
Bit-packing 和 HEX 编码：升高存储的位宽
Bit-packing 和 HEX 编码相似，都是在压缩数据的基数较小时，通过更小位宽的编码来示意原数据。比方对一列 int64 类型的数据，数据的值域在 [0, 7] 之间，这时咱们能够通过存储低 3 位数据来示意元数据，减小不必要的全 ’0’ 高位数据的存储。或者对一列字符串类型的数据，如果所有字符的基数小于 17，那么能够将呈现过的每个字符映射到 [0x0, 0xF] 内的一个 16 进制数上，这样能够用一个 4 位的 16 进制数来示意原字符，减小每个字符编码后的存储空间。而且这两种编码能够与其余编码叠加，对于其余编码产生的数值或字符串数据，都能够再通过 bit-packing 或 HEX 编码进一步去除冗余。
bit-packing
HEX 编码
字典编码和 RLE 编码：单列数据去重
字典编码则能够通过在数据块内建设字典，来对低基数的数据进行压缩。当低基数的数据在微块内的散布也具备局部性，也就是列内雷同数据会散布在相邻的行中时，咱们也能够应用游程 (RLE) 编码的形式对存储的字典的援用值进行压缩。更进一步地，当低基数列的数据块中大部分行都是雷同的值，咱们还会采纳常量编码，将呈现频率最高的数据存储为常量值，其余十分量值数据和对应的行下标存储为 exception list，进行更进一步的压缩。
字典编码 /RLE 编码
差值编码：利用数据的值域压缩
差值编码也是罕用的编码方法，OceanBase 中的差值编码分为数值差值编码和定长字符串差值编码。数值差值编码次要用来对值域较小的数值类数据类型进行压缩。对于日期，工夫戳等数据，或其余邻近数据差值较小的数值类数据，能够只存储最小值，每行存储原数据与最小值的差值，这些差值通常也能够通过 bit-packing 压缩。定长字符串编码则能够比拟好地对人工生成的 ID，如订单号 / 身份证号，或 url 等有肯定模式的字符串进行压缩，对一个微块的数据存储一个模式串，每行额定存储与模式串不同的子串差值，来达到更好的压缩成果。
整形差值
字符串差值
列间编码：减小多列数据冗余
为了利用不同列间数据的相似性加强压缩成果，OceanBase 还引入了列间编码。通常状况下，列存数据库只会对数据在列外部进行编码，但在理论利用中有很多表除了同一列数据之间存在相似性，不同列的数据之间也可能有肯定的关系。
- 当两列数据大部分值雷同时，应用列间等值编码，这样一整列都是另外一列的援用，能够只存储与援用列的行不同的数据；
- 当一列数据是另外一列数据的前缀时，也能够应用列间子串编码，只存储残缺的一列和一列的后缀。
这种列间编码能够对复合列、系统生成的一些数据做出更好的压缩，也可能升高在数据表设计范式上的问题导致的数据冗余。
自适应压缩技术：让数据库抉择编码算法
数据编码的压缩成果不仅与表的 schema 相干，同时还与数据的散布，微块内数据值域等数据自身的特色相干，这也就意味着比拟难以在用户设计表数据模型时指定列编码来实现最好的压缩成果。为了加重用户的应用累赘，也为了实现更好的压缩成果，OceanBase 反对在合并过程中自适应地探测适合的编码方式，对同一列在不同数据块中反对应用不同的算法来进行编码。
而对每个微块的每一列数据探测并抉择最合适的编码须要大量的计算，会给 compaction 过程带来更多的 CPU 计算压力，所以 OceanBase 会通过剖析数据类型，值域，NDV 等特色，联合 compaction 工作中上一个微块对应列抉择的编码算法和压缩率，通过一个启发式算法来实现编码抉择，在探测到绝对更适宜的编码算法的同时保障了合并时数据编码带来的计算开销在能够承受的区间内。
最初一步：编码数据的查问优化
为了可能更好地均衡压缩成果和查问的性能，咱们在设计数据编码格局时也思考到了对查问性能带来的影响。
行级粒度数据随机拜访
通用压缩中如果要拜访一个压缩块中的一部分数据通常须要将整个数据块解压后拜访；某些剖析型零碎的数据编码中面向的多是扫描的场景，点查的场景比拟少，所以采纳了在拜访某一行数据时须要对相邻数据行或数据块内读取行之前所有行进行解码计算的数据编码的格局(如 PFor 等差值编码)。
OceanBase 须要更好地反对事务型负载，就意味着要反对绝对更高效的点查，因而 OceanBase 在设计数据编码格局时保障了编码后的数据是能够以行为粒度随机拜访的。也就是在对某一行进行点查时只须要对这一行相干的元数据进行拜访并解码，减小了随机点查时的计算放大。同时对于编码格局的微块，解码数据所须要的所有元数据都存储在微块内，让数据微块有自解释的能力，也在解码时提供了更好的内存局部性。
缓存解码器
在 OceanBase 目前的数据解码实现中，每一列数据都须要初始化一个解码器对象来解析数据，结构解码器时会须要进行一些计算和内存调配，为了进一步减小拜访编码数据时的 RT，OceanBase 会将数据的解码器和数据块一起缓存在 block cache 中，拜访 cache 中数据块时能够间接通过缓存的解码器解析数据，而解码器的结构与缓存也是由异步 IO 的回调线程来实现的，以升高初始化解码器的 overhead。当不能命中 block cache 中缓存的解码器时，OceanBase 还会为解码器用到的元数据内存和对象构建缓存池，在不同查问间复用这些内存和对象。
通过上述细节上的优化，行列混存格局的 sstable 编码数据也能够很好地反对事务型负载。
因为编码数据行列混存的格局，使得在剖析型查问的解决上，编码数据有着和列存数据类似的个性，数据分布更紧凑，对 CPU cache 更加敌对。这些个性也让咱们能够利用列存罕用的一些优化伎俩对剖析型查问进行优化，充分利用 SIMD 等办法来提供更高效的剖析型负载解决。
同时因为编码数据中咱们会存储字典、null bitmap、常量等能够形容数据分布的元数据，在扫描数据时咱们也能够利用这些数据对于局部过滤，聚合算子的执行过程进行优化，实现在压缩数据上间接进行计算。许多数据仓库也会用相似的办法来优化查问执行，在 SIGMOD 2022 中，《CompressDB: Enabling Efficient Compressed Data Direct Processing for Various Databases》这篇论文也系统地采纳了相似的思维，通过将局部计算下推到存储层，间接在未解压的数据上执行来进步零碎的效率，失去了很不错的性能。
OceanBase 在 3.2 版本中对剖析解决能力进行了大幅的优化，其中就包含聚合与过滤计算下推到存储层执行，和在向量化引擎中利用编码数据的列存特色进行向量化的批量解码。在查问时充分利用了编码元数据和编码数据的列存储局部性，在编码数据上间接进行计算，大幅提高了下推算子的执行效率和向量化引擎中的数据解码效率。基于数据编码的计算下推和向量化解码也成为了反对 OceanBase 高效解决剖析型负载，在 TPC-H benchmark 中达到优良性能指标的重要性能。
数据编码压缩的成果测试
不同的压缩形式如何影响 OceanBase 的压缩成果，以下咱们会通过一个简略的测试进行察看。
咱们应用 OceanBase 4.0 版本，别离在交易场景的 TPC-H 10g 的数据模型和用户行为日志场景的 IJCAI-16 Brick-and-Mortar Store Recommendation Dataset 数据集上对 OceanBase 的压缩率进行测试：
- TPC-H 是对订单，交易场景的建模，咱们对 TPC- H 模型中数据量比拟大的两张表：存储订单的 ORDERS 表，和存储商品信息的 LINEITEM 表的压缩率进行统计。在 OceanBase 默认配置（zstd + encoding）下，这两张表的压缩率能够达到 4.6 左右，相较只开启 encoding 或 zstd 压缩时晋升显著。
- IJCAI-16 taobao user log 则是淘宝脱敏后的实在业务数据，存储了用户浏览商品时的行为日志。在 OceanBase 默认配置（zstd + encoding）下压缩率能够达到 9.9，只开启 encoding 压缩率能够达到 8.3，只开启 zstd 压缩率为 6.0。
能够看到 OceanBase 在面对实在的业务数据时会有更杰出的数据压缩成果，在 TPC-H 这种数据冗余绝对更少的数据集上也有着优良的数据压缩能力。
写在最初
本文介绍了 OceanBase 对于数据库中数据压缩的思考和实现计划。目前 OceanBase 已基于 LSM-Tree 存储引擎，在存储老本与查问性能之间实现均衡，并实现了零碎的工程实际。
咱们很快乐地看到，OceanBase 自研存储引擎的压缩能力曾经 在金融、政府公共服务、能源、交通、运营商等多个行业失去充沛验证，显著晋升了客户业务零碎的稳定性、安全性，可能无效升高存储老本 70%-90%，在同一业务场景下，OceanBase 的数据存储量仅为 MySQL/Oracle 数据库的 1/4-1/3。
随着 OceanBase 零碎架构的演进，咱们会反对越来越多的数据类型和利用场景，提供更高效的数据管理与拜访能力。OceaBase 的存储引擎仍在一直迭代降级，咱们也会对数据编码压缩性能在不同场景、不同存储架构下的优化做出更多尝试，在更丰盛的数据模型上，利用古代硬件的个性对数据的编码压缩成果、以及编码数据的拜访做出更多的优化，一直地为用户带来更好的应用体验。