信息论之进制压缩算法(在hbase索引压缩中的应用)
前言
大家都知道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数组,也是天引同学提出的建议。天引同学在整个优化的过程中给予了我们很大的帮助,在这里表示感谢)
核心代码
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
react新手入门(序)
之前在软件园使用的是react,当时为了做个集光推送,自己去搭过react,这次项目中继续使用react,于是又重新操作了遍,恰巧公司买了本react的书籍,这本书写的非常好,看着并不觉得拗口,很容易理解,于是我又搭了遍react,然后对比之前写的我的第一个react,感觉这次对react更加深入理解了。先把这本书推荐给大家。 react深入浅出 react安装步骤: 1.通过官网https://nodejs.org/安装node.js和npm, node装好,npm就出来了 2.查看是否安装成功npm -v, node -v 3.npm install --global create-react-app 4.create-react-app first_react_app 5.cd first_react_app 6.npm start 7.进入项目中运行npm install,然后npm start,由于前端数据绑定层是react,UI框架是阿里的Ant Design,这框架不支持ie,所以只能在谷歌等浏览器上操作 image.png image.png 也可以用淘宝的镜像下载淘宝...
- 下一篇
阿里云发布国内首个混合云大数据双活容灾服务
在6月上旬举行的云栖大会上海峰会上,阿里云发布了国内首个混合云大数据集群双活容灾产品-混合云容灾服务下的大数据容灾服务(HDR for Big Data,简称 HDR-BD),并已经在7月份开始邀测。采用业界领先的数据双向实时复制技术,HDR-BD可以实现Hadoop集群双活和准0 RPO容灾,为大数据灾备制定了全新的标准。 常见Hadoop灾备技术的挑战 当前比较常见的Hadoop集群灾备方式是用distcp将数据定期复制到一个备用集群做容灾用途,或者将数据复制到只读集群、二级存储作为备份。这些方案都有明显弱点: RPO大:distcp 的原理决定了期数据复制不能是实时的,用户必须承受小时到天级的RPO RTO长:主站宕机后,将只读集群或二级存储中的数据恢复出来会占用大量时间,而拉起standby集群重新启动业务依然是一个耗时的操作 资源
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- CentOS6,CentOS7官方镜像安装Oracle11G
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- 设置Eclipse缩进为4个空格,增强代码规范
- Mario游戏-低调大师作品
- MySQL8.0.19开启GTID主从同步CentOS8
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- CentOS8编译安装MySQL8.0.19
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池