如何解析数据库压缩技术的分析

共计 7875 个字符，预计需要花费 20 分钟才能阅读完成。

今天就跟大家聊聊有关如何解析数据库压缩技术的分析，可能很多人都不太了解，为了让大家更加了解，丸趣 TV 小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。

作为数据库，在系统资源 (CPU、内存、SSD、磁盘等) 一定的前提下，我们希望：

存储的数据更多：采用压缩，这个世界上有各种各样的压缩算法;

访问的速度更快：更快的压缩 (写)/ 解压(读) 算法、更大的缓存。

几乎所有压缩算法都严重依赖上下文：

位置相邻的数据，一般情况下相关性更高，内在冗余度更大;

上下文越大，压缩率的上限越大(有极限值)。

块压缩

传统数据库中的块压缩技术

对于普通的以数据块 / 文件为单位的压缩，传统的 (流式) 数据压缩算法工作得不错，时间长了，大家也都习惯了这种数据压缩的模式。基于这种模式的数据压缩算法层出不穷，不断有新的算法实现。包括使用最广泛的 gzip、bzip2、Google 的 Snappy、新秀 Zstd 等。

gzip 几乎在在所有平台上都有支持，并且也已经成为一个行业标准，压缩率、压缩速度、解压速度都比较均衡;

bzip2 是基于 BWT 变换的一种压缩，本质是上对输入分块，每个块单独压缩，优点是压缩率很高，但压缩和解压速度都比较慢;

Snappy 是 Google 出品，优点是压缩和解压都很快，缺点是压缩率比较低，适用于对压缩率要求不高的实时压缩场景;

LZ4 是 Snappy 一个强有力的竞争对手，速度比 Snappy 更快，特别是解压速度;

Zstd 是一个压缩新秀，压缩率比 LZ4 和 Snappy 都高不少，压缩和解压速度略低; 相比 gzip，压缩率不相上下，但压缩 / 解压速度要高很多。

对于数据库，在计算机世界的太古代，为 I / O 优化的 Btree 一直是不可撼动的，为磁盘优化的 Btree block/page  size 比较大，正好让传统数据压缩算法能得到较大的上下文，于是，基于 block/page 的压缩也就自然而然地应用到了各种数据库中。在这个蛮荒时代，内存的性能、容量与磁盘的性能、容量泾渭分明，各种应用对性能的需求也比较小，大家都相安无事。

现在，我们有了 SSD、PCIe SSD、3D XPoint 等，内存也越来越大，块压缩的缺点也日益突出：

块选小了，压缩率不够; 块选大了，性能没法忍;

更致命的是，块压缩节省的只是更大更便宜的磁盘、SSD;

更贵更小的内存不但没有节省，反而更浪费了(双缓存问题)。

于是，对于很多实时性要求较高的应用，只能关闭压缩。

块压缩的原理

使用通用压缩技术 (Snappy、LZ4、zip、bzip2、Zstd 等)，按块 / 页(block/page) 进行压缩(块尺寸通常是 4KB~32KB，以压缩率著称的 TokuDB 块尺寸是 2MB~4MB)，这个块是逻辑块，而不是内存分页、块设备概念中的那种物理块。

启用压缩时，随之而来的是访问速度下降，这是因为：

写入时，很多条记录被打包在一起压缩成一个个的块，增大块尺寸，压缩算法可以获得更大的上下文，从而提高压缩率; 相反地，减小块尺寸，会降低压缩率。

读取时，即便是读取很短的数据，也需要先把整个块解压，再去读取解压后的数据。这样，块尺寸越大，同一个块内包含的记录数目越多。为读取一条数据，所做的不必要解压就也就越多，性能也就越差。相反地，块尺寸越小，性能也就越好。

一旦启用压缩，为了缓解以上问题，传统数据库一般都需要比较大的专用缓存，用来缓存解压后的数据，这样可以大幅提高热数据的访问性能，但又引起了双缓存的空间占用问题：一是操作系统缓存中的压缩数据; 二是专用缓存 (例如 RocksDB 中的 DBCache) 中解压后的数据。还有一个同样很严重的问题：专用缓存终归是缓存，当缓存未 *** 时，仍需要解压整个块，这就是慢 Query 问题的一个主要来源(慢 Query 的另一个主要来源是在操作系统缓存未 *** 时)。

这些都导致现有传统数据库在访问速度和空间占用上是一个此消彼长、无法彻底解决的问题，只能采取一些折衷。

RocksDB 的块压缩

以 RocksDB 为例，RocksDB 中的 BlockBasedTable 就是一个块压缩的 SSTable，使用块压缩，索引只定位到块，块的尺寸在 dboption 里设定，一个块中包含多条 (key，value) 数据，例如 M 条，这样索引的尺寸就减小到了 1 /M：

M 越大，索引的尺寸越小;

M 越大，Block 的尺寸越大，压缩算法 (gzip、Snappy 等) 可以获得的上下文也越大，压缩率也就越高。

创建 BlockBasedTable 时，Key  Value 被逐条填入 buffer，当 buffer 尺寸达到预定大小(块尺寸，当然，一般 buffer 尺寸不会精确地刚好等于预设的块尺寸)，就将 buffer 压缩并写入 BlockBasedTable 文件，并记录文件偏移和 buffer 中的 *** 个 Key(创建 index 要用)，如果单条数据太大，比预设的块尺寸还大，这条数据就单独占一个块(单条数据不管多大也不会分割成多个块)。所有 Key  Value 写完以后，根据之前记录的每个块的起始 Key 和文件偏移，创建一个索引。所以在 BlockBasedTable 文件中，数据在前，索引在后，文件末尾包含元信息(作用相当于常用的 FileHeader，只是位置在文件末尾，所以叫 footer)。

搜索时，先使用 searchkey 找到 searchkey 所在的 block，然后到 DB  Cache 中搜索这个块，找到后就进一步在块中搜索 searchkey，如果找不到，就从磁盘 /SSD 读取这个块，解压后放入 DB Cache。RocksDB 中的 DB  Cache 有多种实现，常用的包括 LRU Cache，另外还有 Clock Cache、Counting  Cache(用来统计 Cache*** 率等)，还有其他一些特殊的 Cache。

一般情况下，操作系统会有文件缓存，所以同一份数据可能既在 DB  Cache 中(解压后的数据)，又在操作系统 Cache 中(压缩的数据)。这样会造成内存浪费，所以 RocksDB 提供了一个折衷：在 dboption 中设置 DIRECT_IO 选项，绕过操作系统 Cache，这样就只有 DB  Cache，可以节省一部分内存，但在一定程度上会降低性能。

传统非主流压缩：FM-Index

FM-Index 的全名是 Full Text Matching Index，属于 Succinct Data  Structure 家族，对数据有一定的压缩能力，并且可以直接在压缩的数据上执行搜索和访问。

FM-Index 的功能非常丰富，历史也已经相当悠久，不算是一种新技术，在一些特殊场景下也已经得到了广泛应用，但是因为各种原因，一直不温不火。最近几年，FM-Index 开始有些活跃，首先是 GitHub 上有个大牛实现了全套 Succinct 算法，其中包括 FM-Index，其次 Berkeley 的 Succinct 项目也使用了 FM-Index。

FM-Index 属于 Offline 算法(一次性压缩所有数据，压缩好之后不可修改)，一般基于 BWT 变换(BWT 变换基于后缀数组)，压缩好的 FM-Index 支持以下两个最主要的操作：

data = extract(offset, length)

{offset} = search(string)，返回多个匹配 string 的位置 / 偏移(offset)

FM-Index 还支持更多其他操作，感兴趣的朋友可以进一步调研。

但是，在笔者看来，FM-Index 有几个致命的缺点：

实现太复杂(这一点可以被少数大牛们克服，不提也罢);

压缩率不高(比流式压缩例如 gzip 差太多);

搜索 (search) 和访问 (extract) 速度都很慢(在 2016 年最快的 CPU i7-6700K 上，单线程吞吐率不超过 7MB/sec);

压缩过程又慢又耗内存(Berkeley 的 Succinct 压缩过程内存消耗是源数据的 50 倍以上);

数据模型是 Flat Text，不是数据库的 KeyValue 模型。

可以用一种简单的方式把 Flat Model 转化成 KeyValue  Model：挑选一个在 Key 和 Value 中都不会出现的字符“#”(如果无法找出这样的字符，需要进行转义编码)，每个 Key 前后都插入该字符，Key 之后紧邻的就是 Value。如此，search(#key#)返回了 #key# 出现的位置，我们就能很容易地拿到 Value 了。

Berkeley 的 Succinc 项目在 FM-Index 的 Flat  Text 模型上实现了更丰富的行列 (Row-Column) 模型，付出了巨大的努力，达到了一定的效果，但离实用还相差太远。

感兴趣的朋友可以仔细调研下 FM-Index，以验证笔者的总结与判断。

Terark 的可检索压缩(Searchable Compression)

Terark 公司提出了“可检索压缩 (Searchable  Compression)”的概念，其核心也是直接在压缩的数据上执行搜索(search) 和访问(extract)，但数据模型本身就是 KeyValue 模型，根据其测试报告，速度要比 FM-Index 快得多(两个数量级)，具体阐述：

摒弃传统数据库的块压缩技术，采用全局压缩;

对 Key 和 Value 使用不同的全局压缩技术;

对 Key 使用有搜索功能的全局压缩技术 COIndex(对应 FM-Index 的 search);

对 Value 使用可定点访问的全局压缩技术 PA-Zip(对应 FM-Index 的 extract)。

对 Key 的压缩：CO-Index

我们需要对 Key 进行索引，才能有效地进行搜索，并访问需要的数据。

普通的索引技术，索引的尺寸相对于索引中原始 Key 的尺寸要大很多，有些索引使用前缀压缩，能在一定程度上缓解索引的膨胀，但仍然无法解决索引占用内存过大的问题。

我们提出了 CO-Index(Compressed Ordered Index)的概念，并且通过一种叫做 Nested Succinct  Trie 的数据结构实践了这一概念。

较之传统实现索引的数据结构，Nested Succinct Trie 的空间占用小十几倍甚至几十倍。而在保持该压缩率的同时，还支持丰富的搜索功能：

精确搜索;

范围搜索;

顺序遍历;

前缀搜索;

正则表达式搜索(不是逐条遍历)。

与 FM-Index 相比，CO-Index 也有其优势(假定 FM-Index 中所有的数据都是 Key)。

表 1 FM-Index 对比 CO-Index

CO-Index 的原理

实际上我们实现了很多种 CO-Index，其中 Nested Succinct Trie 是适用性最广的一种，在这里对其原理做一个简单介绍：

Succinct Data Structure 介绍

Succinct Data  Structure 是一种能够在接近于信息论下限的空间内来表达对象的技术，通常使用位图来表示，用位图上的 rank 和 select 来定位。

虽然能够极大降低内存占用量，但实现起来较为复杂，并且性能低很多(时间复杂度的常数项很大)。目前开源的有 SDSL-Lite，我们则使用自己实现的 Rank-Select，性能也高于开源实现。

以二叉树为例

传统的表现形式是一个结点中包含两个指针：struct Node {Node *left, *right;};

每个结点占用 2ptr，如果我们对传统方法进行优化，结点指针用最小的 bits 数来表达，N 个结点就需要 2 *[log2(N)]个 bits。

对比传统基本版和传统优化版，假设共有 216 个结点(包括 null 结点)，传统优化版需要 2 bytes，传统基本版需要 4 /8 bytes。

对比传统优化版和 Succinct，假设共有 10 亿 (~230) 个结点。

传统优化版每个指针占用[log2(230)]=30bits，总内存占用：($\frac{2*30}{8}$)*230 asymp; 7.5GB。

使用 Succinct，占用：($\frac{2.5}{8}$)*230 asymp; 312.5MB(每个结点 2.5 bits，其中 0.5bits 是  rank-select 索引占用的空间)。

Succinct Tree

Succinct Tree 有很多种表达方式，这里列出常见的两种：

图 1 Succinct Tree 表达方式示例

Succinct Trie = Succinct Tree + Trie Label

Trie 可以用来实现 Index，图 2 这个 Succinct Trie 用的是 LOUDS 表达方式，其中保存了 hat、is、it、a、四个 Key。

Patricia Trie 加嵌套

仅使用 Succinct 技术，压缩率远远不够，所以又应用了路径压缩和嵌套。这样一来，压缩率就上了一个新台阶。

把上面这些技术综合到一起，就是我们的 Nest Succinct Trie。

对 Value 的压缩: PA-Zip

我们研发了一种叫做 PA-Zip (Point Accessible  Zip)的压缩技术：每条数据关联一个 ID，数据压缩好之后，就可以用相应的 ID 访问那条数据。这里，ID 就是那个 Point，所以叫做 Point Accessible  Zip。

PA-Zip 对整个数据库中的所有 Value(KeyValue 数据库中所有 Value 的集合)进行全局压缩，而不是按 block/page 进行压缩。这是针对数据库的需求(KeyValue   模型)，专门设计的一个压缩算法，用来解决传统数据库压缩的问题：

压缩率更高，没有双缓存的问题，只要把压缩后的数据装进内存，不需要专用缓存，可以按 ID 直接读取单条数据，如果把这种读取单条数据看作是一种解压，那么：

按 ID 顺序解压时，解压速度 (Throughput) 一般在 500MB 每秒(单线程)，*** 达到约 7GB/s，适合离线分析性需求，传统数据库压缩也能做到这一点;

按 ID 随机解压时，解压速度一般在 300MB 每秒(单线程)，*** 达到约 3GB/s，适合在线服务需求，这一点完胜传统数据库压缩：按随机解压 300MB/ s 算，如果每条记录平均长度 1K，相当于 QPS  = 30 万; 如果每条记录平均长度 300 个字节，相当于 QPS = 100 万;

预热(warmup)，在某些特殊场景下，数据库可能需要预热。因为去掉了专用缓存，TerarkDB 的预热相对简单高效，只要把 mmap 的内存预热一下(避免 Page  Fault 即可)，数据库加载成功后就是预热好的，这个预热的 Throughput 就是 SSD 连续读的 IO 性能(较新的 SSD 读性能超过 3GB/s)。

与 FM-Index 相比，PA-Zip 解决的是 FM-Index 的 extract 操作，但性能和压缩率都要好得多：

表 2 FM-Index 对比 PA-Zip

结合 Key 与 Value

Key 以全局压缩的形式保存在 CO-Index 中，Value 以全局压缩的形式保存在  PA-Zip 中。搜索一个 Key，会得到一个内部 ID，根据这个 ID，去 PA-Zip 中定点访问该 ID 对应的 Value，整个过程中只触碰需要的数据，不需要触碰其他数据。

如此无需专用缓存(例如 RocksDB 中的 DBCache)，仅使用 mmap，*** 配合文件系统缓存，整个 DB 只有 mmap 的文件系统缓存这一层缓存，再加上超高的压缩率，大幅降低了内存用量，并且极大简化了系统的复杂性，最终完成数据库性能的大幅提升，从而同时实现了超高的压缩率和超高的随机读性能。

从更高的哲学层面看，我们的存储引擎很像是用构造法推导出来的，因为 CO-Index 和 PA-Zip 紧密配合，*** 匹配 KeyValue 模型，功能上“刚好够用”，性能上压榨硬件极限，压缩率逼近信息论的下限。相比其他方案：

传统块压缩是从通用的流式压缩衍生而来，流式压缩的功能非常有限，只有压缩和解压两个操作，对太小的数据块没有压缩效果，也无法压缩数据块之间的冗余。把它用到数据库上，需要大量的工程努力，就像给汽车装上飞机机翼，然后要让它飞起来。

相比 FM-Index，情况则相反，FM-Index 的功能非常丰富，它就必然要为此付出一些代价 mdash; mdash; 压缩率和性能。而在 KeyValue 模型中，我们只需要它那些丰富功能的一个非常小的子集(还要经过适配和转化)，其他更多的功能毫无用武之地，却仍然要付出那些代价，就像我们花了很高的代价造了一架飞机，却把它按在地上，只用轮子跑，当汽车用。 

图 2 用 LOUDS 方式表达的 Succinct Tree

图 3 路径压缩与嵌套

附录

压缩率 性能测试比较

数据集：Amazon movie data

Amazon movie data (~8 million reviews)，数据集的总大小约为 9GB,   记录数大约为 800 万条，平均每条数据长度大约 1K。

Benchmark 代码开源：参见 Github 仓库(https://github.com/Terark/terarkdb-benchmark/tree/master/doc/movies)。

压缩率(见图 4) 

图 4 压缩率对比

随机读(见图 5) 

图 5 随机读性能对比

这是在内存足够的情况下，各个存储引擎的性能。

延迟曲线(见图 6) 

图 6 延迟曲线对比

数据集：Wikipedia 英文版

Wikipedia 英文版的所有文本数据，109G，压缩到 23G。

数据集：TPC-H

在 TPC- H 的 lineitem 数据上，使用 TerarkDB 和原版 RocksDB(BlockBasedTable)进行对比测试：

表 3 TerarkDB 与原版 RocksDB 对比测试

API 接口

TerarkDB = Terark SSTable + RocksDB

RocksDB 最初是 Facebook 对 Google 的 LevelDB 的一个 fork，编程接口上兼容 LevelDB，并增加了很多改进。

RocksDB 对我们有用的地方在于其 SSTable 可以 plugin，所以我们实现了一个 RocksDB 的 SSTable，将我们的技术优势通过 RocksDB 发挥出来。

虽然 RocksDB 提供了一个相对完整的 KeyValueDB 框架，但要完全适配我们特有的技术，仍有一些欠缺，所以需要对 RocksDB 本身也做一些修改。将来可能有一天我们会将自己的修改提交到 RocksDB 官方版。

Github 链接：TerarkDB(https://github.com/Terark/terarkdb)，TerarkDB 包括两部分：

terark-zip-rocksdb(https://github.com/terark/terark-zip-rocksdb)，(Terark  SSTable forrocksdb)

Terark fork  rocksdb(https://github.com/Terark/rocksdb)，(必须使用这个修改版的 rocksdb)

为了更好的兼容性，TerarkDB 对 RocksDB 的 API 没有做任何修改，为了进一步方便用户使用 TerarkDB，我们甚至提供了一种方式：程序无需重新编译，只需要替换  librocksdb.so 并设置几个环境变量，就能体验 TerarkDB。

如果用户需要更精细的控制，可以使用 C ++ API 详细配置 TerarkDB 的各种选项。

目前大家可以免费试用，可以做性能评测，但是不能用于 production，因为试用版会随机删掉 0.1% 的数据。

Terark 命令行工具集

我们提供了一组命令行工具，这些工具可以将输入数据压缩成不同的形式，压缩后的文件可以使用 Terark  API 或 (该工具集中的) 其他命令行工具解压或定点访问。

看完上述内容，你们对如何解析数据库压缩技术的分析有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注丸趣 TV 行业资讯频道，感谢大家的支持。