PREFIX_TREE(HBASE-4676)是HBase 0.96版本中新增加的一种DataBlock Encode算法。
1.什么是PREFIX_TREE
关于前缀树的介绍可以参考维基百科http://zh.wikipedia.org/wiki/Trie
当然其的实现会有差别
2.HBase中的DataBlock
DataBlock是KeyValue的集合,是Hfile中存储数据的结构体,可以搜索Hfile了解之
3.什么是DataBlock Encode
DataBlock Encode是HBase 0.94版本引入的特性,可以将重复的row/family/qualifier/进行压缩,减少block的空间占用,提高内存使用率,可以通过http://zjushch.iteye.com/blog/1585066了解更多
4.PREFIX_TREE提升从DataBlock中查找数据的效率
在没有PREFIX_TREE之前,无论是否开启DataBlock Encode,都是按照KeyValue的排序,将其一条条顺序地写入到Block中,所以从block中查找数据,只能采用遍历的方式。而开启了PREFIX_TREE后,DataBlock中的数据存储不再是简单的将KeyValue按照顺序进行堆压,而是按照特有的方式进行组织,可以在解析时生成前缀树,并且树节点的儿子是排序的,所以从block中查找数据,其效率至少在二分查找以上。
5.作者提供的DataBlock查找性能对比
说明:
1.作者没有指出单条KV的平均大小
2.NONE 指的是不启用DataBlock Encode;PREFIX指的是PREFIX Encode算法;TRIE才是前缀树block压缩算法。
3. 前缀树压缩算法在不同的block size下查找性能都很稳定,而NONE和PREFIX由于是用遍历的方式查找数据,所以查找性能随着blocksize直线下降。对于我们默认的64K的block大小,性能相差40+倍
4.NONE比PREFIX算法性能好,是由于PREFIX算法需要解压
6.HBase中的PREFIX_TREE结构
PREFIX_TREE会分别对KeyValue中的row family qualifier形成三颗树,以Row为例,插入aa、aac、bb、bc、bc的过程如图
树上的节点分为3类:
branch(黄色): 内部节点,不代表实际数据,必定含有子节点
leaf(绿色):一个叶子节点,没有子节点,代表着实际数据
nub(紫色):branch与leaf的混合,既代表了实际数据,又含有子节点
节点中的数字代表该节点对应的实际数据的数目,如果一个row下有多条KeyValue,那么每条KeyValue对应的qualifier、family、timestamp等都会在encode时进行记录
7.Encode/Decode
PREFIX_TREE的encode算法,相对而言比较复杂,简单地说,它会按顺序向Block中写入ptBlockMeta、所有的row、所有的family、所有的qualifier、所有的timestamp、所有的value。可以看出,这与之前按照keyvalue顺序写入的block结构有很大的不同。 ptBlockMeta里面维护了decode时重建树结构所需要的元数据,以及一些为了压缩所需要的数据。整个encode/decode的过程还是直接看代码为好。
8.实际性能测试
测试环境:
16核CPU,HBase-0.94 version,单客户端200线程,单regionserver,BlockCache命中率100%
说明:
1.在加大BlockSize后,开启PREFIX_TREE,QPS基本无变化,而对于NONE/DIFF而言,QPS影响很大
2.PREFIX_TREE的空间压缩效果接近于DIFF算法
3.DIFF/FAST_DIFF等block encoding算法是以CPU计算换取空间,在不计较空间的情形下,即命中率都为100%,那么开启DIFF/FAST_DIFF,相比于NONE,其性能是反而会下降的,从测试case看大概有5%~20%的下降
个人结论:
PREFIX_TREE在压缩空间的基础上又可以减少CPU,不仅可以取代其他block encoding算法了,像是PREFIX、DIFF、FAST_DIFF都可以退役了,足以成为标配
9.适用场景
a.随机读(Get)
b.一Row多qualifier
c.Key/Value 很小
d.除了scan场景有待测试外,其实对于所有的随机读场景,都可以开启,因为副作用小于正作用(DIFF/FAST_DIFF算法,对于数据无法压缩的场景,会加重CPU,带来副作用)
10.More
之前的顺序存储的Block结构下,逆序scan十分困难(只有后继,没有前继指针),而PREFIX_TREE则可以支持逆序scan,等0.96发布PREFIX_FREE普及后,相信逆序scan功能随之而来
相关推荐
hbase-0.96jar包 hbase-0.96 hbase-0.98都可以用,
赠送jar包:hbase-prefix-tree-1.1.3.jar; 赠送原API文档:hbase-prefix-tree-1.1.3-javadoc.jar; 赠送源代码:hbase-prefix-tree-1.1.3-sources.jar; 赠送Maven依赖信息文件:hbase-prefix-tree-1.1.3.pom; ...
CentOS-6.4 64位系统下hadoop-2.2.0+hbase-0.96+zookeeper-3.4.5 分布式安装配置
赠送jar包:hbase-prefix-tree-1.4.3.jar; 赠送原API文档:hbase-prefix-tree-1.4.3-javadoc.jar; 赠送源代码:hbase-prefix-tree-1.4.3-sources.jar; 赠送Maven依赖信息文件:hbase-prefix-tree-1.4.3.pom; ...
赠送jar包:hbase-prefix-tree-1.2.12.jar; 赠送原API文档:hbase-prefix-tree-1.2.12-javadoc.jar; 赠送源代码:hbase-prefix-tree-1.2.12-sources.jar; 赠送Maven依赖信息文件:hbase-prefix-tree-1.2.12.pom;...
赠送jar包:hbase-prefix-tree-1.2.12.jar; 赠送原API文档:hbase-prefix-tree-1.2.12-javadoc.jar; 赠送源代码:hbase-prefix-tree-1.2.12-sources.jar; 赠送Maven依赖信息文件:hbase-prefix-tree-1.2.12.pom;...
赠送jar包:hbase-prefix-tree-1.1.3.jar; 赠送原API文档:hbase-prefix-tree-1.1.3-javadoc.jar; 赠送源代码:hbase-prefix-tree-1.1.3-sources.jar; 赠送Maven依赖信息文件:hbase-prefix-tree-1.1.3.pom; ...
HBase 元数据修复工具包。 ①修改 jar 包中的application.properties,重点是 zookeeper.address、zookeeper.nodeParent、hdfs....③开始修复 `java -jar -Drepair.tableName=表名 hbase-meta-repair-hbase-2.0.2.jar`
hbase-sdk是基于hbase-client和hbase-thrift的原生API封装的一款轻量级的HBase ORM框架。 针对HBase各版本API(1.x~2.x)间的差异,在其上剥离出了一层统一的抽象。并提供了以类SQL的方式来读写HBase表中的数据。对...
HBase(hbase-2.4.9-bin.tar.gz)是一个分布式的、面向列的开源数据库,该技术来源于 Fay Chang 所撰写的Google论文“Bigtable:一个结构化数据的分布式存储系统”。就像Bigtable利用了Google文件系统(File System...
hbase的hbase-1.2.0-cdh5.14.2.tar.gz资源包
hbase-client-2.1.0-cdh6.3.0.jar
phoenix-hbase-2.2-5.1.2-bin.tar.gz
phoenix-client-hbase-2.2-5.1.2.jar
被编译的hive-hbase-handler-1.2.1.jar,用于在Hive中创建关联HBase表的jar,解决创建Hive关联HBase时报FAILED: Execution Error, return code 1 from org.apache.hadoop.hive.ql.exec.DDLTask. org.apache.hadoop....
hbase-1.2.1-bin.tar.gz.zip 提示:先解压再使用,最外层是zip压缩文件
赠送jar包:hbase-hadoop-compat-1.1.3.jar; 赠送原API文档:hbase-hadoop-compat-1.1.3-javadoc.jar; 赠送源代码:hbase-hadoop-compat-1.1.3-sources.jar; 赠送Maven依赖信息文件:hbase-hadoop-compat-1.1.3....
hbase-1.2.6.1-bin.tar.gz,hbase-1.2.6.1-bin.tar.gz,hbase-1.2.6.1-bin.tar.gz,hbase-1.2.6.1-bin.tar.gz,hbase-1.2.6.1-bin.tar.gz,hbase-1.2.6.1-bin.tar.gz,hbase-1.2.6.1-bin.tar.gz,hbase-1.2.6.1-bin.tar.gz
赠送jar包:hbase-metrics-api-1.4.3.jar; 赠送原API文档:hbase-metrics-api-1.4.3-javadoc.jar; 赠送源代码:hbase-metrics-api-1.4.3-sources.jar; 赠送Maven依赖信息文件:hbase-metrics-api-1.4.3.pom; ...