数据库压缩技术探索

按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)。

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)

与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的文件体系缓存这一层缓存，再加上超高的紧缩率，大年夜幅降低了内存用量，并且极大年夜简化了体系的复杂性，最终完成数据库机能的大年夜幅晋升，大年夜而同时实现了超高的紧缩率和超高的随机读机能。

固然可以或许极大年夜降低内存占用量，但实现起来较为复杂，并且机能低很多(时光复杂度的常数项很大年夜)。今朝开源的有SDSL-Lite，我们则应用本身实现的Rank-Select，机能也高于开源实现。

大年夜更高的┞奋学层面看，我们的存储引擎很像是用构造法推导出来的，因为CO-Index和PA-Zip慎密合营，完美匹配KeyValue模型，功能上“刚好够用”，机能上压沾竽暌共件极限，紧缩率切近亲近信息论的下限。比拟其他筹划：

传统块紧缩是大年夜通用的流式紧缩衍生而来，流式紧缩的功能异常有限，只有压休和解压两个操作，对太小的数据块没有紧缩效不雅，也无法紧缩数据块之间的冗余。把它用到数据库上，须要大年夜量的工程尽力，就像给汽车装上飞机机翼，然后要让它飞起来。
比拟FM-Index，情况则相反，FM-Index的功能异常丰富，它就必定要为此付出一些价值——紧缩率和机能。而在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)

启悠揭捉?缩时，随之而来的是拜访速度降低，这是因为：

写入时，很多笔记录被打包在一路紧缩成一个个的块，增大年夜块尺寸，紧缩算法可以获得更大年夜的高低文，大年夜而进步紧缩率;相反地，减小块尺寸，会降低紧缩率。
攫取时，即就是攫取很短的数据，也须要先把全部块解压，再去攫取解压后的数据。如许，块尺寸越大年夜，同一个块内包含的记录数量越多。为攫取一条数据，所做的不须要解压就也就越多，机能也就越差。相反地，块尺寸越小，机能也就越好。