数据库压缩技术探索

紧缩过程又慢又耗内存(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的数据构造实践了章一ㄅ念。

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

表1 FM-Index比较CO-Index

CO-Index的道理

较之传统实现索引的数据构造，Nested Succinct Trie的空寄┞芳用小十几倍甚至几十倍。而在保持钙揭捉?缩率的同时，还支撑丰富的搜刮功能：

精确搜刮;
范围搜刮;
次序遍历;
前缀搜刮;
正则表达式搜刮(不是逐条遍历)。

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

一旦启悠揭捉?缩，为了缓解以上问题，传统数据库一般都须要比较大年夜的专用缓存，用来缓存解压后的数据，如许可以大年夜幅进步热数据的拜访机能，但又引起了双缓存的空寄┞芳用问题：一是操作体系缓存中的紧缩数据;二是专用缓存(例如RocksDB中的DBCache)中解压后的数据。还有一个同样很严重的问题：专用缓存终归是缓存，当缓存未射中时，仍须要解压全部块，这就是慢Query问题的一个重要来源(慢Query的另一个重要来源是在操作体系缓存未射中时)。

Succinct Data Structure介绍

Succinct Data Structure是一种可以或许在接近于信息论下限的空间内来表达对象的技巧，平日应用位图来表示，用位图上的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≈ 7.5GB。
应用Succinct，占用：($\frac{2.5}{8}$)*230≈ 312.5MB(每个结点2.5 bits，个中0.5bits是 rank-select 索引占用的空间)。

Succinct Tree

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