2021SC@SDUSC HBase(十)项目代码分析——HBase的压缩编码

2021SC@SDUSC

• 一、简述
• 二、key的编码
• • • prefix
    • diff
• 三、 DataBlock解压
• • • 新Indexable Delta Encoding
• Trie单词查找树

编码+压缩能够成倍的减少数据的磁盘占用空间，节省可观的存储费用。同时，缩通常情况下可以提高系统吞吐率，让系统可以做更多的功
在存储层面节省空间的处理上，Hbase提供了两种方案：
1、基于key的编码。用于将key重复部分进行简单处理达到节约空间的目的。
2、基于数据库（data block）的压缩。对数据块进行压缩，实现节省硬盘。
参考链接

主要是针对于key很长而且有大量部分重复的场景，如果key大部分长得不一样，那么编码几乎没有优势：

把key中和前一条记录相同的部分省略不计，然后再增加一列，记录省略的长度
原始数据：
编码后的数据：
可以看到增加prefix len一列，记录从第一位开始重复的位数，但是key一列的记录被简化了

diff则是基于prefix基础之上模式，它直接将和上条记录一样部分省略；diff和prefix不同之处在于它认为每条记录都有一个唯一主键，所以，diff增加了两列，一列是timestamp，一列是type；这样处理好处是主键被分割后可以在压缩后有比较好的效率；默认diff是被禁用的，因为在scan的时候diff的性能比较差。

hbase作为一种schema free的数据库，相当于传统的关系型数据库更加灵活，用户无需设计好表的结构，也可以在同一张表内写入不同schema的数据。然而，由于缺少数据结构的支持，hbase需要很多额外的数据结构来标注长度信息，且无法针对不同的数据类型采用不同的压缩方式。针对这一问题，hbase提出了编码功能，用来降低存储开销。由于编码对cpu开销较小，且效果较好，通常cache中也会开启编码功能。
旧DIFF Encoding
hbase很早就支持了DataBlockEncoding，也就是是通过减少hbase keyvalue中重复的部分来压缩数据。
DIFF 编码之后，对某个文件的seek包含以下两步：
1、通过index key找到对应的datablock
2、从第一个完整KV开始，顺序查找，不断decode下一个kv，直到找到目标kv为止。
DIFF encoding对小kv场景使用效果较好，可以减少2-5倍的数据量。

从性能角度考虑，hbase通常需要将meta信息装载进block cache。如果将block大小较小，meta信息较多，会出现meta无法完全装入Cache的情况, 性能下降。如果block大小较大，DIFF Encoding顺序查询的性能会成为随机读的性能瓶颈。针对这一情况，我们开发了Indexable Delta Encoding，在block内部也可以通过索引进行快速查询，seek性能有了较大提高。
在通过BlockIndex找到对应的数据块后，我们从数据块末尾找到每个完整KV的offset，并利用二分查找快速定位到符合查询条件的完整kv，再顺序decode每一个Diff kv，直到找到目标kv位置。
通过Indexable Delta Encoding， HFile的随机seek性能相对于使用之前翻了一倍，以64K block为例，在全cache命中的随机Get场景下，相对于Diff encoding rt下降50%，但存储开销仅仅提高3-5%。Indexable Delta Encoding目前已在线上多个场景应用，经受了双十一的考验，整体平均读rt减少10%-15%。

Hbase中单独拿出一个工程来实现Trie的数据结果，既达到压缩编码的效果，又可以方便查询。
树里面有三种类型的数据结构：branch（分支）、leaf（叶子）、nub（节点）
1、branch分支节点：以其为结果的词并没有出现过，但是to、tea等次的分支的地方，单个t的词没有出现过。
2、leaf叶子节点：下面没有子节点
3、nub节点：结余两者之间

* Example inputs (numInputs=7):
* 0: AAA
* 1: AAA
* 2: AAB
* 3: AAB
* 4: AAB
* 5: AABQQ
* 6: AABQQ
*

* Resulting TokenizerNodes:
* AA <- branch, numOccurrences=0, tokenStartOffset=0, token.length=2
* A <- leaf, numOccurrences=2, tokenStartOffset=2, token.length=1
* B <- nub, numOccurrences=3, tokenStartOffset=2, token.length=1
* QQ <- leaf, numOccurrences=2, tokenStartOffset=3, token.length=2

描述该数据结构用了两个类Tokenizer和TokenizerNode
发起点PrefixTreeCodec，这个类是继承自DataBlockEncoder接口的，DataBlockEncoder是专门负责编码压缩的，它里面的有3个重要的方法，encodeKeyValues（编码）、decodeKeyValues（反编码）、createSeeker（创建扫描器）。

private void internalEncodeKeyValues(DataOutputStream encodedOutputStream,
ByteBuffer rawKeyValues, boolean includesMvccVersion) throws IOException {
rawKeyValues.rewind();
PrefixTreeEncoder builder = EncoderFactory.checkOut(encodedOutputStream, includesMvccVersion);
try{
KeyValue kv;
while ((kv = KeyValueUtil.nextShallowCopy(rawKeyValues, includesMvccVersion)) != null) {
builder.write(kv);
}
builder.flush();
}finally{
EncoderFactory.checkIn(builder);
}
}

PrefixTreeCodec里面的encodeKeyValues方法，这是入口，internalEncodeKeyValues是实际编码的地方。从rawKeyValues里面不断读取kv出来，用PrefixTreeEncoder.write方法来进行编码，最后调用flush进行输出。

rowTokenizer.addSorted(CellUtil.fillRowRange(cell, rowRange));
addFamilyPart(cell);
addQualifierPart(cell);
addAfterRowFamilyQualifier(cell);

这是PrefixTreeEncoder.write方法里的，这里就跳到Tokenizer.addSorted方法里面

public void addSorted(final ByteRange bytes) {
++numArraysAdded;
if (bytes.getLength() > maxElementLength) {
maxElementLength = bytes.getLength();
}
if (root == null) {
root = addNode(null, 1, 0, bytes, 0);
} else {
root.addSorted(bytes);
}
}

如果root节点为空，就new一个root节点出来，有了根节点之后，就把节点添加到root节点的孩子队列里面。

public void addSorted(final ByteRange bytes) {// recursively build the tree
if (matchesToken(bytes) && CollectionUtils.notEmpty(children)) {
TokenizerNode lastChild = CollectionUtils.getLast(children);
if (lastChild.partiallyMatchesToken(bytes)) {
lastChild.addSorted(bytes);
return;
}
}
int numIdenticalTokenBytes = numIdenticalBytes(bytes);// should be <= token.length
int tailOffset = tokenStartOffset + numIdenticalTokenBytes;
int tailLength = bytes.getLength() - tailOffset;
if (numIdenticalTokenBytes == token.getLength()) {
if (tailLength == 0) {// identical to this node (case 1)
incrementNumOccurrences(1);
} else {
int childNodeDepth = nodeDepth + 1;
int childTokenStartOffset = tokenStartOffset + numIdenticalTokenBytes;
TokenizerNode newChildNode = builder.addNode(this, childNodeDepth, childTokenStartOffset, bytes, tailOffset);
addChild(newChildNode);
}
} else { split(numIdenticalTokenBytes, bytes);
}
}

1、先添加一个AAA进去，它是根节点，parent是null，深度为1，在原词中起始位置为0。
2、添加一个AAA，它首先和之前的AAA相比，完全一致，走的是incrementNumOccurrences(1)，出现次数（numOccurrences）变成2。
3、添加AAB，它和AAA相比，匹配的长度为2，尾巴长度为1，那么它走的是这条路split(numIdenticalTokenBytes, bytes)这条路径

protected void split(int numTokenBytesToRetain, final ByteRange bytes) {
int childNodeDepth = nodeDepth;
int childTokenStartOffset = tokenStartOffset + numTokenBytesToRetain;
TokenizerNode firstChild = builder.addNode(this, childNodeDepth, childTokenStartOffset,
token, numTokenBytesToRetain);
firstChild.setNumOccurrences(numOccurrences);// do before clearing this node's numOccurrences
token.setLength(numTokenBytesToRetain);//shorten current token from BAA to B
numOccurrences = 0;//current node is now a branch
moveChildrenToDifferentParent(firstChild);//point the new leaf (AA) to the new branch (B)
addChild(firstChild);//add the new leaf (AA) to the branch's (B's) children
TokenizerNode secondChild = builder.addNode(this, childNodeDepth, childTokenStartOffset,
bytes, tokenStartOffset + numTokenBytesToRetain);
addChild(secondChild);//add the new leaf (00) to the branch's (B's) children
firstChild.incrementNodeDepthRecursively();
secondChild.incrementNodeDepthRecursively();
}

split完成的效果：

1. 子节点的tokenStartOffset 等于父节点的tokenStartOffset 加上匹配的长度，这里是0+2=2
   2)创建左孩子，token为A，深度为父节点一致，出现次数和父亲一样2次
   3）父节点的token长度变为匹配长度2，即（AA），出现次数置为0
   4）把原来节点的子节点指向左孩子
   5）把左孩子的父节点指向当前节点
   6）创建右孩子，token为B，深度为父节点一致
   7）把右孩子的父节点指向当前节点
   8）把左右孩子的深度递归增加。
   4、 添加AAB，和AA完全匹配，最后一个孩子节点AAB也匹配，调用AAB节点的addSorted(bytes)，因为是完全匹配，所以和第二步一样，B的出现次数加1
   5、添加AABQQ，和AA完全匹配，最后一个孩子节点AAB也匹配，调用AAB节点的addSorted(bytes), 成为AAB的孩子

if (matchesToken(bytes) && CollectionUtils.notEmpty(children)) {
TokenizerNode lastChild = CollectionUtils.getLast(children);
if (lastChild.partiallyMatchesToken(bytes)) {
lastChild.addSorted(bytes);
return;
}
}

走进递归，和最后一个节点前缀部分匹配
6、添加AABQQ，增加QQ的出现次数
接下来在flush时继续操作，为这棵树构建索引信息，方面查询。