全局压缩-革命性的数据库技术

作者: rockeet 发表日期: 2017年03月08日分类: 未分类评论: 8 条阅读次数: 11,958 次

全局压缩-革命性的数据库技术

背景

作为数据库，在系统资源(cpu, 内存, ssd, 磁盘 …) 一定的前提下，我们希望：

存储的数据更多：采用压缩，这个世界上有各种各样的压缩算法……
访问的速度更快：更快的压缩(写)/解压(读) 算法，更大的缓存……

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

位置相邻的数据，一般情况下相关性更高，内在冗余度更大
上下文越大，压缩率的上限越大(当然,有个极限)

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

gzip 几乎在在所有平台上都有支持，并且也已经成为一个行业标准；压缩率、压缩速度、解压速度都比较均衡
bzip2 是基于bwt变换的一种压缩，本质是上对输入分块，每个块单独压缩；优点是压缩率很高，但压缩和解压速度都比较慢
snappy 是 google 出品的，优点是压缩和解压都很快，缺点是压缩率比较低，适用于对压缩率要求不高的实时压缩场景
lz4 是 snappy 一个强有力的竞争对手，速度比snappy更快，特别是解压速度
zstd 是一个压缩新秀，压缩率比 lz4 和 snappy 都高不少，压缩和解压速度略低；相比gzip，压缩率不相上下，但压缩/解压速度要高很多

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

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

现在，我们有了ssd，PCIe ssd，3d xpoint ……，内存也越来越大，块压缩的缺点也日益突出：

块选小了，压缩率不够，块选大了，性能无法忍
更要命的是，块压缩，节省的只是更大更便宜的磁盘、ssd
更贵更小的内存不但没有节省，反而更浪费了（双缓存问题）

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

块压缩的原理

使用通用压缩技术（snappy,lz4,gzip,bzip2,zstd,等等）按块/页(block/page)进行压缩（块尺寸通常是 4K~32K，以压缩率著称的 TokuDB 块尺寸是 2M~4M），这个块是逻辑块，而不是内存分页、块设备概念中的那种物理块。

以 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，可以节省一部分内存，但在一定程度上会降低性能。

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

写入时，很多条记录被打包在一起压缩成一个个的块，增大块尺寸，压缩算法可以获得更大的上下文，从而提高压缩率；相反地，减小块尺寸，会降低压缩率。
读取时，即便是读取很短的数据，也需要先把整个块解压，再去读取解压后的数据。这样，块尺寸越大，同一个块内包含的记录数目越多，为读取一条数据，所做的不必要的解压就也就越多，性能也就越差。相反地，块尺寸越小，性能也就越好。

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

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

传统非主流压缩：FM-Index

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

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

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

实现太复杂（这一点可以被少数的大牛们克服，不提也罢）
压缩率不高（比流式压缩例如 gzip 差太多）
搜索和访问速度太慢（在2016年最快的 CPU上，单线程吞吐率不超过7MB/sec）
压缩过程又慢又耗内存（Berkeley 的 Succinct 压缩过程内存消耗是源数据的50倍以上）
数据模型是 Flat Text，难以兼容数据库的行列(Row-Column)模型

Berkeley 的 Succinct项目为了在 Flat Text 模型上实现行列模型，付出了巨大的努力，达到了一定的效果，但离实用还相差太远。

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

Terark 的全局压缩

Terark 公司提出了“全局压缩”的概念，其核心也是直接在压缩的数据上执行搜索，但数据模型是KeyValue模型，并且速度要比FM-Index快得多（两个数量级）：

摒弃传统数据库的块压缩技术
对key使用有Index功能的全局压缩技术
对value使用可定点解压的全局压缩技术

对 key 的压缩（即索引的压缩）

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

Terark 自己研发了一种叫做 Nest Succinct Trie 的索引技术，只考虑 key 本身，不考虑 key 对应的 value，这个压缩率一般能达到 5 倍左右。对于一些特殊的 key，压缩率更高，比如对url的压缩率能达到 10 倍以上。相比传统索引的膨胀，两者相差十几倍甚至几十倍。并且，在保持这个压缩率的同时，支持丰富的搜索功能：

精确搜索
范围搜索
前缀搜索
正则表达式搜索（不是逐条遍历）

（RocksDB 的 API 不支持正则表达式搜索，所以这个功能需要通过 Terark 的专有 API 来调用）

对value的压缩

对整个数据库（KeyValue 数据库中所有 Value 的集合）进行全局压缩，而不是按 block/page 进行压缩。

这种压缩是 Terark 专门针对数据库的需求，精心设计的一个压缩算法，用来彻底解决传统数据库压缩的问题：

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

按 RowID 顺序解压时，解压速度（Throughput）一般在 500MB每秒(单线程)，最高达到约 7GB/s，适合离线分析性需求，传统数据库压缩也能做到这一点
按 RowID 随机解压时，解压速度一般在 300MB每秒(单线程)，最高达到约3GB/s，适合在线服务需求，这一点完胜传统数据库压缩：按随机解压 300MB/s 算，如果每条记录平均长度 1K，相当于 QPS = 30万，如果每条记录平均长度300个字节，相当于QPS = 100万！
预热(warmup)，在某些特殊场景下，数据库可能需要预热。因为去掉了专用缓存，TerarkDB 的预热非常简单却又极其高效，只要设置 mmapPopulate，数据库加载成功后就是预热好的，这个预热的 Throughput 就是 ssd 连续读的 io 性能(较新的 ssd 性能是以 GB/s计的)。

结合 Key 与 Value

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

这样，不需要专用的缓存(例如 RocksDB 中的 DB Cache)，使用 mmap，完美配合文件系统缓存，整个 DB 只有这一层缓存，再加上超高的压缩率，大幅降低了内存用量，并且大幅简化了系统的复杂性，最终大幅提高了数据库的性能。

可以看到，Terark 存储引擎完全摒弃了传统数据库的块压缩，另辟蹊径，同时实现了超高的压缩率和超高的随机读性能。

一般大家会认为性能和压缩率是鱼与熊掌不可兼得，但是，Terark 让大家可以兼得了鱼与熊掌。

附录

压缩率&性能测试比较

测试数据集 & Benchmark代码

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

Benchmark 代码开源：参见Github仓库。

压缩率

随机读

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

延迟曲线

其他测试集

Wikipedia英文版，109G，压缩到23G。

Nest Succinct Trie

Succinct Data Structure

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

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

以二叉树为例

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

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

对比传统基本版和传统优化版，假设共有个结点(包括null结点)，传统优化版需要2 bytes, 传统基本版需要4/8 bytes
对比传统优化版和Succinct，假设共有10亿(~ )个结点
- 传统优化版每个指针占用 = 30 bits，总内存占用： ≈ 5GB，
- 使用 Succinct，占用： ≈ 5MB(每个结点2.5 bits，其中0.5bits是 rank-select 索引占用的空间）

Succinct Tree

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

Succinct Trie = Succinct Tree + Trie Label

Trie可以用来实现Index，下面这个Succinct Trie用的是 LOUDS 表达方式，其中保存了hat,is,it,a 四个 Key。
succinct-trie-louds

Patricia Trie 加嵌套

仅使用 Succinct 技术，压缩率远远不够，所以又应用了路径压缩和嵌套。这样一来，压缩率就上了一个新的台阶。
succinct-nest-patricia-trie
把上面这些技术综合到一起，就是 Terark 的 Nest Succinct Trie。

TerarkDB = Terark SSTable + RocksDB

RocksDB 最初是 facebook 对 google 的 leveldb 的一个fork，编程接口上兼容leveldb，并且增加了很多改进。

RocksDB 对Terark有用的地方在于它的 SSTabl e是可以 plugin 的，所以 Terark 实现了一个 RocksDB 的 SSTable，把 Terark 的技术优势通过 RocksDB 发挥出来。

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

Terark 内部的评测显示，对某个 key 平均长度23个字节，value 平均长度 592 字节，总量 550GB，接近 9 亿条的 key value 的数据，full compact 之后，压缩到47G，同时，在16核32线程，64G 内存的机器上，随机读的 QPS 超过200万，相同的测试 RocksDB 原版因为内存不够，QPS 只有 3000。

Github链接：terarkdb，terarkdb包括两部分：

terark-zip-rocksdb（Terark SSTable for rocksdb）
Terark fork rocksdb（必须使用这个修改版的 rocksdb）

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

目前只有C++版，下面简单介绍一下使用方式（完整版参见 terark-zip-rocksdb）：

#include <table/terark_zip_table.h>
/// other includes...

  ///....
  TerarkZipTableOptions opt;

  /// TerarkZipTable needs to create temp files during compression
  opt.localTempDir = "/path/to/some/temp/dir"; // default is "/tmp"

  /// 0 : check sum nothing
  /// 1 : check sum meta data and index, check on file load
  /// 2 : check sum all data, not check on file load, check on record read
  opt.checksumLevel = 2; // default 1

  ///    < 0 : only last level using terarkZip
  ///          this is equivalent to terarkZipMinLevel == num_levels-1
  /// others : use terarkZip when curlevel >= terarkZipMinLevel
  ///          this includes the two special cases:
  ///                   == 0 : all levels using terarkZip
  ///          >= num_levels : all levels using fallback TableFactory
  /// it shown that set terarkZipMinLevel = 0 is the best choice
  /// if mixed with rocksdb's native SST, those SSTs may using too much
  /// memory & SSD, which degrades the performance
  opt.terarkZipMinLevel = 0; // default

  /// optional
  opt.softZipWorkingMemLimit = 16ull << 30; // default
  opt.hardZipWorkingMemLimit = 32ull << 30; // default

  /// to let rocksdb compaction algo know the estimate SST file size
  opt.estimateCompressionRatio = 0.2;

  /// the global dictionary size over all value size
  opt.sampleRatio = 0.03;

  /// other opt are tricky, just use default

  /// rocksdb options when using terark-zip-rocksdb:

  /// fallback can be NULL
  auto fallback = NewBlockBasedTableFactory();
  auto factory = NewTerarkZipTableFactory(opt, fallback);
  options.table_factory.reset(factory);

  /// terark-zip use mmap
  options.allow_mmap_reads = true;

  /// universal compaction reduce write amplification and is more friendly
  /// for large SST file, terark SST is better on larger SST file.
  /// although universal compaction needs 2x SSD space on worst case, but
  /// with terark-zip's high compression, the used SSD space is much 
  /// smaller than rocksdb's block compression schema
  options.compaction_style = rocksdb::kCompactionStyleUniversal;

  /// larger MemTable yield larger level0 SST file
  /// larger SST file make terark-zip better
  options.write_buffer_size     = 1ull << 30; // 1G
  options.target_file_size_base = 1ull << 30; // 1G

  /// single sst file size on greater levels should be larger
  /// sstfile_size(level[n+1]) = sstfile_size(level[n]) * target_file_size_multiplier
  options.target_file_size_multiplier = 2; // can be larger, such as 3,5,10

  /// turn off rocksdb write slowdown, optional. If write slowdown is enabled
  /// and write was really slow down, you may doubt that terark-zip caused it
  options.level0_slowdown_writes_trigger = 1000;
  options.level0_stop_writes_trigger = 1000;
  options.soft_pending_compaction_bytes_limit = 2ull << 40;
  options.hard_pending_compaction_bytes_limit = 4ull << 40;

#include <table/terark_zip_table.h>

/// other includes...

///....

TerarkZipTableOptions opt;

/// TerarkZipTable needs to create temp files during compression

opt.localTempDir = "/path/to/some/temp/dir"; // default is "/tmp"

/// 0 : check sum nothing

/// 1 : check sum meta data and index, check on file load

/// 2 : check sum all data, not check on file load, check on record read

opt.checksumLevel = 2; // default 1

/// < 0 : only last level using terarkZip

/// this is equivalent to terarkZipMinLevel == num_levels-1

/// others : use terarkZip when curlevel >= terarkZipMinLevel

/// this includes the two special cases:

/// == 0 : all levels using terarkZip

/// >= num_levels : all levels using fallback TableFactory

/// it shown that set terarkZipMinLevel = 0 is the best choice

/// if mixed with rocksdb's native SST, those SSTs may using too much

/// memory & SSD, which degrades the performance

opt.terarkZipMinLevel = 0; // default

/// optional

opt.softZipWorkingMemLimit = 16ull << 30; // default

opt.hardZipWorkingMemLimit = 32ull << 30; // default

/// to let rocksdb compaction algo know the estimate SST file size

opt.estimateCompressionRatio = 0.2;

/// the global dictionary size over all value size

opt.sampleRatio = 0.03;

/// other opt are tricky, just use default

/// rocksdb options when using terark-zip-rocksdb:

/// fallback can be NULL

auto fallback = NewBlockBasedTableFactory();

auto factory = NewTerarkZipTableFactory(opt, fallback);

options.table_factory.reset(factory);

/// terark-zip use mmap

options.allow_mmap_reads = true;

/// universal compaction reduce write amplification and is more friendly

/// for large SST file, terark SST is better on larger SST file.

/// although universal compaction needs 2x SSD space on worst case, but

/// with terark-zip's high compression, the used SSD space is much

/// smaller than rocksdb's block compression schema

options.compaction_style = rocksdb::kCompactionStyleUniversal;

/// larger MemTable yield larger level0 SST file

/// larger SST file make terark-zip better

options.write_buffer_size = 1ull << 30; // 1G

options.target_file_size_base = 1ull << 30; // 1G

/// single sst file size on greater levels should be larger

/// sstfile_size(level[n+1]) = sstfile_size(level[n]) * target_file_size_multiplier

options.target_file_size_multiplier = 2; // can be larger, such as 3,5,10

/// turn off rocksdb write slowdown, optional. If write slowdown is enabled

/// and write was really slow down, you may doubt that terark-zip caused it

options.level0_slowdown_writes_trigger = 1000;

options.level0_stop_writes_trigger = 1000;

options.soft_pending_compaction_bytes_limit = 2ull << 40;

options.hard_pending_compaction_bytes_limit = 4ull << 40;

8 个回复

foudrer说道：

2017年3月24日下午4:51

作者，你好！TerarkDB的技术非常值得期待，我会持续关注TerarkDB。
我这里有几个问题，不知道您是否能够回答一下。
1、在TerarkDB中，key与value是使用不同的压缩技术进行存储的，是吗？
2、我看文中提到了与RocksDB的对比，对比的过程中，TerakDB是在full compact之后测试的QPS，是否有在读写混合的场景下，TerakDB的QPS的变化情况？

感谢，期待您的答复。我最近也在研究一些关于succinct的技术，也看了github上的Terak上的，有时间我也仔细研究一下TerakDB

登录以回复
- rockeet说道：
  
  2017年3月30日下午12:14
  
  你的第一个问题，答案是 YES
  
  你的第二个问题，读写混合的场景下，只有少量写操作时（比如5%），我们的仍具有压倒性的优势，随着写操作的占比越多，我们的优势会减小。
  
  登录以回复
sillycross说道：

2017年9月19日下午3:17

你好！
感觉Succinct Nested Trie这个想法非常有意思，有一个问题不太理解，希望能够不吝赐教。
这个做法个人的理解，核心是压缩路径表示的“路径”本身没法压缩，而您的解决方案是再用一个trie来记录这些路径，确实非常有趣！
但是这个做法对于（例如）随机的字符串，感觉压缩效果并不会比普通的压缩路径trie有实质提升吧？比如考虑100万个长度100的随机01串，那么普通的压缩路径trie长得基本是20层满二叉树，前19层都是老老实实一步一个字符，最后到叶子的那一层一下子80个字符。这样用来维护“压缩路径”的trie树实质依然维护着100万条长度80的01串，这个子问题并没有太大的减小吧？为什么会达到那么高的压缩率呢？
更严谨一些的说的话，如果你有n个长度位m的随机01串，那么你一层nest只能把原问题转化为n个长度为m-log n的随机01串的子问题，即使你能不考虑常数地nest很多层，只要串长m一大也难以接受吧？
希望作者不吝指教，多谢！

登录以回复
- rockeet说道：
  
  2019年3月4日下午5:04
  
  压缩的就是自然的业务数据，随机数据用任何算法都无法压缩。
  
  登录以回复
hhh2000说道：

2018年12月14日下午7:23

您好，我对自动机比较感兴趣，经常来您的博客看，学到了不少知识，自己也做了一些实现（DFA最小化，AcTrie等），对自动机的高压缩率和高速度也有了感性认识，感觉很神奇 😯 ，也对您能把理论转为实用工业产品感到佩服，就是来晚了点，没赶上开源 😀 ，希望您能开发出更好对产品，我也能学到更多。

然后在这篇文章里，对key实现说的比较多，对value的实现方法没怎么提，我挺好奇实现方法是什么，因为对value和key要求不同，key需要index，value则一般没这个要求，而是可能更注重压缩率和便于按ID提取。我对value压缩用什么方法实现比较感兴趣：1、是否也是用的自动机技术，比如利用反向搜索功能。2、大概实现方法是什么，能不能介绍一下，当然不方便就算了。最后祝越办越好。

登录以回复
- hhh2000说道：
  
  2018年12月15日下午2:42
  
  补充一下，我昨天粗略看了Succinct Data Structure，发现貌似只能用在trie，不能用在DAWG上，还是有新的方法可以，如果不行的话正则表达式dfa就没法应用Succinct结构了
  
  登录以回复
  - rockeet说道：
    
    2019年3月4日下午5:10
    
    Succinct 也可以用在 DAWG 上，只要不追求 100% 的纯粹 Succinct。
    可以把大部分 DAWG 图的大部分内容比如 90% 都用 Succinct 来表达。
    下载包中的 adfa_build.exe 就支持这样的结构（-u 选项）。
    
    登录以回复
- rockeet说道：
  
  2019年3月4日下午5:14
  
  对，value 只需要按 id 提取，功能上的需求比 key 简单得多，所以对于 value 我们就只针对它必须的功能，设计了一种算法，这个算法暂时不便透露太多细节。
  
  登录以回复

发表评论

您必须登录后才能发表评论。

全局压缩-革命性的数据库技术

全局压缩-革命性的数据库技术

背景