您现在的位置是:首页 > 文章详情

信息论之进制压缩算法(在hbase索引压缩中的应用)

日期:2018-07-10点击:454


前言

大家都知道hbase的使用中,最重要的是rowkey的设计。而rowkey的设计中有三个关键点:

1、前缀预防读写热点

2、前缀适合查询场景

3、在满足1、2的前提下,关注索引的存储空间

关于1和2,介绍的文章很多。这篇文章主要分析一下索引的空间利用率,并试图推导出一套具有广泛应用价值的存储压缩思想。

信息的量化

我们先用世界杯的例子介绍一下信息论一个重要的概念 信息量

2018年的世界杯在俄罗斯举办,有32个国家参赛(为了方便说明,我们将32个国家进行编号1-32)。我们要猜冠军会是哪个国家。假设现在来了一个从未来穿越过来的机器人,它已经知道比赛结果。我们可以向它提问,它可以告诉我们,我们的猜测是“对”还是“错”,不过问它一次要给它一块钱。那么我们要问多少次(花多少钱)才能知道结果呢?

很容易知道,我们问它5次就能知道结果(先猜冠军出现在1-16号,如果猜对,则继续猜1-8号;以此类推),也就是说需要花5块钱。

如果我们对当今足球的格局多一些了解,我们可以猜的更聪明一点:比如我们把巴西、德国、意大利、英格兰、法国、西班牙、葡萄牙少数几个实力强的国家放到一组,其余大多数国家放大另一组,我们可以用更少的次数猜出结果,比如说猜4次(花4元)就能知道结果。省下的一块钱就是源于我们掌握的足球知识,即信息。

信息需要量化,量化的标准不是人名币,而是比特(bit)。猜世界杯冠军的问题包含32种取值的可能性,信息量是log232 = 5 bit. 

进制压缩算法

存储压缩的思路是先分析存储的数据所包含的信息量,再看数据实际占用的存储空间。也就是评估存储的空间利用率,分析压缩的理论极限值。

hbase没有字段类型,存储的是byte数组(一般会将rowkey字符串按一定的编码如utf-8进行存储)。rowkey设计中经常包含大量10进制字符组成的子串,如交易号、时间戳等。

一个10进制字符取值有10种可能性,含有的信息量是log210 =  3.3bit.  但一个10进制字符用utf-8编码后需要占用1个字节的存储。空间利用率不到50%。

 如果我们能将10进制字符映射成更高的进制,映射成我们熟悉的16进制自然能提高一些空间利用率,因为一个16进制字符的信息量是log216 =  4bit, 有没有更好的方案呢?

在utf-8中,单字节字符对应ASCII中128个字符,如果能将10进制字符的信息与ASCII码建立联系,就能将10进制转化成128进制,就能做到1个字节存储 log2128 =  7bit的信息。

方法是将10进制字符组成的字串对应的数字转化为2进制形式,然后每7个bit与一个ASCII码对应(ASCII码中128个字符可对应0-127)。

我们压缩的核心思想是先分析空间利用率(根据数据的信息量和实际占用的空间分析压缩的理论极限值)。然后根据数据的概率分布特征(10进制数字可以认为是0-9等概率分布,如果0-9不是等概率分布并且我们知道它们先验概率的话,可以先使用Huffman进行一次重编码)对数据进行重编码。

优化后,我们将每个字节存储3.3bit的信息提高到存储7bit的信息,空间利用率提高超过50%。

适用场景适用于那些没有数据类型(或只能以字符串存储)的数据库(如hbase、odps),并且数据中低进制子串(如10进制,16进制)占比较高的场景。

延伸思考

更进一步,我们要问:在以utf-8编码的前提下,我们能不能做到一个字节存储8bit的信息呢?

答案是不能,原因在于utf-8为了解码,部分bit用来标记下一个字符是几个字节编码的。

若字节的bit是以0开头,则该字节会单独解码成一个字符。若字节的bit是以110开头,则该字节连同下一个字节组合解码一个字符。以此类推。

再进一步,我们要问:在hbase的rowkey中我们存储10进制的数字,为什么要用utf-8来编码,能不能直接存储10进制数字对应的二进制形式组成的byte数组呢?这样对于rowkey中的10进制字符,不是可以做到一个字节存储8bit的信息么?

如果rowkey全部由10进制数字组成,我们可以直接存0进制数字对应的二进制形式组成的byte数组,事实上绝大多数场景,组成rowkey的还有很多非10进制字符(如英文字符),对于这部分字符我们如何存储呢?是转化为unicode对应的数字,还是通过utf-8或者其他编码方式存储?不管怎么存储,解码的复杂度将会大大增加。对于不需要解码rowkey内容的场景,这是一种可选方式。 

备注:这部分的内容与hbase团队的天引同学进行过讨论,对于10进制的子串能否直接存储数字对应的二进制形式组成的byte数组,也是天引同学提出的建议。天引同学在整个优化的过程中给予了我们很大的帮助,在这里表示感谢

  

核心代码

 


原文链接:https://yq.aliyun.com/articles/609880
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章