作为数据库，在一定系统资源（CPU、内存、SSD、磁盘等）的前提下，我们希望：存储更多的数据：使用压缩，这里面有各种压缩世界算法；更快的访问：更快的压缩（写入）/解压缩（读取）算法，更大的缓存。几乎所有的压缩算法都严重依赖于上下文：具有相邻位置的数据通常更相关并且本质上是冗余的；上下文越大，压缩率上限越大（有极限值）。块压缩传统数据库中的块压缩技术对于普通的数据块/文件单元压缩，传统的（流式）数据压缩算法效果很好。时间长了，大家都习惯了这种数据压缩方式。基于这种模型的数据压缩算法层出不穷，新的算法也在不断被实现。包括使用最广泛的gzip、bzip2、谷歌的Snappy、菜鸟Zstd等，几乎所有平台都支持gzip，已经成为行业标准。压缩比、压缩速度、解压速度比较均衡；bzip2是一种基于BWT变换的压缩，本质上是将输入分成块。每个块单独压缩。优点是压缩率很高，但是压缩和解压速度比较慢；Snappy由Google出品。实时压缩场景；LZ4是Snappy的有力竞争者，比Snappy更快，尤其是解压速度；zstd是压缩新秀，压缩比远高于LZ4和Snappy，压缩和解压速度略低；与gzip相比，压缩率不相上下，但压缩/解压速度要快很多。对于数据库，在计算机世界的远古时代，为I/O优化的Btree一直是不可动摇的。针对磁盘优化的Btreeblock/pagesize比较大，正好可以让传统的数据压缩算法获得更大的context。因此，Block/page-basedcompression自然而然地应用到各种数据库中。在这个野蛮的时代，内存的性能和容量与磁盘的性能和容量分得清清楚楚，各种应用对性能的要求比较小，大家相安无事。现在，我们有SSD、PCIeSSD、3DXPoint等，内存越来越大，块压缩的缺点也越来越突出：小块选择，压缩率不够；选块大，性能不堪；更致命不幸的是，块压缩只能节省更大更便宜的磁盘和SSD；越贵越小的内存不仅不节省，反而更加浪费（双缓存问题）。所以对于很多实时性要求高的应用，只能关闭压缩。块压缩原理采用通用压缩技术（Snappy、LZ4、zip、bzip2、Zstd等），按块/页（block/page）进行压缩（块大小通常为4KB~32KB，已知TokuDB块大小foritscompressionrateis2MB~4MB)，这个块是一个逻辑块，而不是内存分页和块设备概念中的物理块。启用压缩后，访问速度会降低。这是因为：写入时，很多记录被打包在一起压缩成块，增大块大小，压缩算法可以获得更大的上下文，从而提高了压缩比；相反，减小块大小会降低压缩率。读取时，即使读取很短的数据，也需要先解压整个block，再读取解压后的数据。因此，块大小越大，同一块中包含的记录数就越多。读取一段数据做的不必要的解压越多，性能就越差。相反，块大小越小，性能越好。一旦启用压缩，为了缓解上述问题，传统数据库一般都需要一个比较大的专用缓存来缓存解压后的数据，这样可以大大提高热点数据的访问性能，但是也造成了双缓存的空间占用问题:1.是操作系统缓存中的压缩数据；二是专用缓存中的解压数据（如RocksDB中的DBCache）。还有一个同样严重的问题：私有缓存毕竟是缓存，在没有安装缓存的情况下，仍然需要对整个块进行解压，这是造成慢查询问题的一大来源（另外一个主要的慢查询来源是在操作系统未安装缓存时）。这些都导致现有传统数据库的访问速度和空间占用是一个权衡问题，无法完全解决，只能做出一些妥协。RocksDB的块压缩以RocksDB为例。RocksDB中的BlockBasedTable是块压缩的SSTable。使用块压缩，索引只定位块。块的大小在dboption中设置。一个块包含多个(key,value)数据，比如M块，索引的大小缩小为1/M：M越大，索引的大小越小；M越大，Block的大小越大，通过压缩算法（gzip、Snappy等）可以获得的context值越大，压缩率越高。在创建BlockBasedTable时，KeyValue被一个一个填充到buffer中。当缓冲区大小达到预定大小（块大小，当然，一般缓冲区大小不会正好等于预设的块大小），缓冲区被压缩并写入BlockBasedTable文件。并记录文件偏移量和缓冲区中的第一个Key（用于创建索引）。如果单条数据太大，大于预设的块大小，则这条数据会单独占用一个块（无论单条数据有多大，都不会拆分成多个块）。写入所有KeyValues后，根据之前记录的每个块的起始Key和文件偏移量创建索引。因此，在BlockBasedTable文件中，数据在前，索引在后，文件末尾包含元信息（作用相当于常用的FileHeader，只是位置在末尾）文件，所以它被称为页脚??）。搜索时，先用searchkey找到searchkey所在的block，然后在DBCache中搜索block，找到后再在block中搜索searchkey，如果没有找到，则从磁盘中读取block/SSD，解压后放入DBCache。RocksDB中有很多DBCache的实现。常用的有LRUCache、ClockCache、CountingCache（用来统计Cache***率等），以及其他一些特殊的Cache。一般操作系统都有文件缓存，所以同一份数据可能同时在DBCache（解压后的数据）和操作系统Cache（压缩后的数据）中。这样会造成内存浪费，所以RocksDB提供了一个折衷方案：在dboption中设置DIRECT_IO选项绕过操作系统缓存，这样就只有DB缓存，可以节省一些内存，但是会在一定程度上降低性能。传统非主流压缩：FM-IndexFM-Index的全称是FullTextMatchingIndex，属于SuccinctDataStructure家族。具有一定的数据压缩能力，可以直接对压缩后的数据进行查找和访问。FM-Index功能非常丰富，历史悠久。它不被认为是一项新技术。它在一些特殊场景中得到了广泛的应用，但由于种种原因，一直不温不火。近年来，FM-Index变得有些活跃。首先，GitHub上有个大牛实现了包括FM-Index在内的全套Succinct算法。其次，Berkeley的Succinct项目也使用了FM-Index。FM-Index属于Offline算法（一次性压缩所有数据，压缩后不可修改），一般基于BWT变换（BWT变换基于后缀数组）。压缩后的FM-Index主要支持以下两个操作：data=extract(offset,length){offset}=search(string)，返回多个匹配字符串的位置/偏移量(offset)FM-Index还支持更多其他操作，有兴趣的朋友可以进一步研究。但是，在笔者看来，FM-Index有几个致命的缺点：实现过于复杂（这一点几位大牛都能攻克，更不用说了）；压缩率不高（比gzip等流式压缩差很多）；搜索（search）和访问（extract）非常慢（在2016年最快的CPUi7-6700K上，单线程吞吐率不超过7MB/sec）；压缩过程缓慢且耗内存（Berkeley'sSuccinct压缩过程的内存消耗是源数据的50倍以上）；数据模型是纯文本，而不是数据库的键值模型。FlatModel转换成KeyValueModel的方法很简单：选择一个Key和Value中没有出现的字符“#”（如果找不到这样的字符，需要转义编码），在每个Key之前插入该字符和之后，并且值紧跟在Key之后。这样search(#key#)返回的就是#key#出现的位置，我们就可以轻松获取到Value了。Berkeley的Succinc项目在FM-Index的FlatText模型上实现了更丰富的行-列（Row-Column）模型。已经付出了很大的努力，取得了一定的成果，但离实用还差得很远。有兴趣的朋友可以仔细调查一下FM-Index，以验证作者的总结和判断。Terark的可搜索压缩（SearchableCompression）Terark公司提出了“可搜索压缩（SearchableCompression）”的概念，其核心是直接对压缩后的数据进行搜索（search）和访问（extract），但数据模型本身是根据其测试报告，KeyValue模型比FM-Index快得多（两个数量级）。具体为：摒弃传统数据库的块压缩技术，采用全局压缩；对Key和Value使用不同的全局压缩技术；Key使用全局压缩技术COIndex，带搜索功能（对应FM-??Index的搜索）；采用全局压缩技术PA-Zip，Value定点访问（对应FM-??Index的extract）。Key的压缩：CO-Index我们需要对Key进行索引，以便有效地搜索和访问所需的数据。使用普通的索引技术，索引的大小远远大于索引中原始键的大小。有些索引使用了前缀压缩，可以在一定程度上缓解索引的膨胀，但是仍然不能解决索引内存占用过大的问题。我们提出了CO-Index（CompressedOrderedIndex）的概念，并通过一个叫做NestedSuccinctTrie的数据结构来实践这个概念。与传统的索引数据结构相比，NestedSuccinctTrie占用的空间要小十倍甚至几十倍。在保持压缩率的同时，还支持丰富的搜索功能：精准搜索；范围搜索；顺序遍历；前缀搜索；正则表达式搜索（不是一一遍历）。与FM-Index相比，CO-Index也有其优势（假设FM-Index中的所有数据都是Key）。表1FM-Indexvs.CO-IndexCO-Index的原理事实上，我们已经实现了很多种CO-Index，其中NestedSuccinctTrie是应用最广泛的一种。下面简单介绍一下它的原理：SuccinctDataStructure简介SuccinctDataStructure是一种能够在接近信息论下限的空间中表达对象的技术。通常用位图表示，在位图上按rank和select定位。虽然可以大大减少内存占用，但实现起来比较复杂，性能也低很多（时间复杂度的常数项很大）。目前SDSL-Lite是开源的，我们使用Rank-Select，是自己实现的，性能比开源实现的要高。以二叉树为例，传统的表达形式是一个节点包含两个指针：structNode{Node*left,*right;};每个节点占用2ptr，如果我们优化传统的方法，节点指针用最小的位数来表示，N个节点需要2*[log2(N)]位。对比传统基础版和传统优化版，假设共有216个节点（包括空节点），传统优化版需要2字节，传统基础版需要4/8字节。比较传统的优化版本和Succinct，假设总共有10亿（~230）个节点。传统优化版中每个指针占用[log2(230)]=30bits，总内存占用：($\frac{2*30}{8}$)*230≈7.5GB。使用Succinct，占用：($\frac{2.5}{8}$)*230≈312.5MB（每个节点2.5bits，0.5bits是rank-select索引占用的空间）。SuccinctTreeSuccinctTree的表达方式有很多种，这里介绍两种比较常见的：图1SuccinctTree表达示例SuccinctTrie=SuccinctTree+TrieLabelTrie可以用来实现Index，图2这个SuccinctTrie使用LOUDS表达，哪个省帽子,is,it,a,fourKey。PatriciaTrie加嵌套仅仅使用了Succinct技术，压缩率远远不够，所以应用了路径压缩和嵌套。这样，压缩率就上了一个新的台阶。将上述技术结合在一起就是我们的NestSuccinctTrie。价值压缩：PA-Zip我们开发了一种压缩技术，叫做PA-Zip（PointAccessibleZip）：每条数据都关联一个ID，数据压缩后，可以用对应的ID访问那条数据数据的。这里的ID就是Point，所以叫PointAccessibleZip。PA-Zip是对整个数据库（KeyValue数据库中所有Value的集合）中的所有Value进行全局压缩，而不是按block/page进行压缩。这是专门针对数据库（KeyValue模型）的需求设计的压缩算法，解决传统数据库压缩的问题：压缩率更高，不存在双缓存问题，只要将压缩后的数据加载到内存中即可，不需要Dedicatedcache，可以直接根据ID读取单条数据。如果把这种读取单条数据看成是一种解压，那么：按照ID的顺序解压时，解压速度（Throughput）一般是每秒500MB（单线程），最大达到7GB左右/s，适合离线分析需求，传统的数据库压缩也可以做到；按ID随机解压时，解压速度一般为300MB/s（单线程），最大达到3GB/s左右，适合在线业务需求，优于传统数据库压缩：按300MB/s随机解压计算，如果每条记录的平均长度为1K，则相当于QPS=300,000；如果每条记录的平均长度为300字节，则相当于QPS=100万；预热，在一些特殊场景下，可能需要对数据库进行预热。因为去掉了专用缓存，TerarkDB的预热相对简单高效。只需预热mmap内存（以避免页面错误）。数据库加载成功后，进行预热。这个预热的吞吐量就是SSD持续读取IO性能（较新的SSD读取性能超过3GB/s）。PA-Zip与FM-Index相比，解决了FM-Index的extract操作，但是性能和压缩率要好很多：表2FM-Index比较PA-Zip结合Key和ValueKey以全局压缩的形式保存在CO-Index中，Value以全局压缩的形式存储在PA-Zip中。搜索密钥，您将获得一个内部ID。根据这个ID去PA-Zip定点访问这个ID对应的Value。整个过程中只接触需要的数据，不需要其他数据。这样就不需要专门的缓存（比如RocksDB中的DBCache），只用mmap，最好配合文件系统缓存。整个DB只有mmap文件系统cache缓存层，再加上超高的压缩率，大大降低了内存占用，大大简化了系统的复杂度，最终完成了数据库性能的大幅提升，从而同时实现超高压缩比和超高随机读性能。从更高的哲学层面上看，我们的存储引擎似乎是从构造方法中衍生出来的，因为CO-Index和PA-Zip紧密配合，完美匹配KeyValue模型，在功能和性能上都“刚好够用”挤压极限硬件，压缩率接近信息论的下限。与其他解决方案相比：传统块压缩源自通用流式压缩。流式压缩的功能非常有限。只有两个操作：压缩和解压缩。对太小的数据块没有压缩效果，不能压缩数据块。之间的冗余。将其放入数据库需要大量的工程工作，就像将飞机的机翼装在汽车上并让它飞起来一样。与FM-Index相比，情况正好相反。FM-Index的功能非常丰富，但它也必须为此付出一些代价——压缩率和性能。在KeyValue模型中，我们只需要它丰富的功能中的一个非常小的子集（经过适配和改造），其他再多的功能也没用，但我们还是要付出那些代价，就像我们的构建是付出了非常高的代价一样一架飞机，但把它放在地上，只靠轮子跑，把它当作汽车使用。Figure2SuccinctTreeexpressedinLOUDS图3Pathcompressionandnestedappendix压缩率&性能测试对比大概是800万条，平均每条数据长度在1K左右。基准代码是开源的：参见Github存储库(https://github.com/Terark/terarkdb-benchmark/tree/master/doc/movies)。Compressionratio（见图4）图4CompressionratiocomparisonRandomread（见图5）图5Randomread性能对比这是各个存储引擎在内存充足的情况下的性能表现。延迟曲线（见图6）图6延迟曲线对比数据集：维基百科英文版维基百科英文版所有文本数据，109G，压缩后为23G。数据集：TPC-H在TPC-H的lineitem数据上，使用TerarkDB和原来的RocksDB（BlockBasedTable）进行对比测试：表3TerarkDB和原来的RocksDB对比测试API接口TerarkDB=TerarkSSTable+RocksDBRocksDB原来是Facebook的LevelDBforGoogleLevelDB的一个分支，编程接口兼容LevelDB，并增加了很多改进。RocksDB对我们有用的地方在于它的SSTable可以是一个插件，所以我们实现了一个RocksDBSSTable，通过RocksDB来发挥我们的技术优势。RocksDB虽然提供了比较完善的KeyValueDB框架，但是为了完全适应我们独特的技术，还存在一些不足，所以需要对RocksDB本身进行一些修改。也许未来的某一天我们会把我们的修改提交到正式版的RocksDB上。Github链接：TerarkDB（https://github.com/Terark/terarkdb），TerarkDB包括两部分：terark-zip-rocksdb（https://github.com/terark/terark-zip-rocksdb），（TerarkSSTableforrocksdb)Terarkforkrocksdb(https://github.com/Terark/rocksdb)，（必须使用这个修改版的rocksdb）为了更好的兼容性，TerarkDB没有对RocksDB的API做任何改动，为了进一步方便对于使用TerarkDB的用户，我们甚至提供了一种方式：无需重新编译程序，只需替换librocksdb.so并设置几个环境变量即可体验TerarkDB。如果用户需要更精细的控制，可以使用C++API详细配置TerarkDB的各种选项。目前可以免费试用并做性能评估，但不能用于生产，因为试用版会随机删除0.1%的数据。Terark命令行工具集我们提供了一套命令行工具，可以将输入的数据压缩成不同的形式，压缩后的文件可以通过TerarkAPI或者其他命令行工具解压或者定点访问（在这个工具集中).详情参见中文版Terarkwiki（https://github.com/Terark/terark-wiki-zh_cn）。
