基于HBASE的大数据压缩算法的研究

陈洁　陈冬杰　黄帮明

摘要：近年来，社交网络、电子商务、网络游戏、在线视频等，新一代大规模互联网应用迅猛发展。这些新兴的应用出现了数据存储量大、业务增长速度快等特点。该文将总体分析HBASE 中支持的压缩算法，并对这两种压缩算法做对比，对以后的建设提供了指导作用。对于大数据时代的到来，如何提高查询时间和存储容量、系统的稳定性和使用廉价的硬件设备，研究压缩算法具有重要的现实意义。

关键词：压缩算法； HBASE ；列存储

中图分类号：TP302.7 文献标识码：A 文章编号：1009-3044（2014）13-3146-02

Research on HBASE Based Big Data Compression Algorithm

CHEN Jie1，CHEN Dong-jie2，HUANG Bang-ming2

（1.Chongqing University of Posts and Telecommun-ications， Chongqing 400064， China； 2.China Mobile Group Design Institute Co.，Ltd，Chongqing 400042， China）

Abstract：In recent years， social networking， e-commerce， online games， online video， etc.， the rapid development of a new generation of large-scale Internet applications. These emerging applications appeared in data storage capacity， fast business growth characteristics. This article analyzes the overall compression algorithm HBASE supported， and these two compression algorithms do comparison on future construction provides a guiding role. For the arrival of the era of big data， how to improve the query time and storage capacity， the system's stability and the use of inexpensive hardware device， the compression algorithm research has important practical significance.

Key words：compression algorithm； HBASE； column-oriented

1 概述

随着信息化技术的飞速发展与人们对网络的需求，各种系统数据量也越来越大，存储空间也不断的增加，对后期的建设和维护也带来了极大的影响。由于数据库太大，导致该数据库备份时间长，严重影响系统运行的稳定性；由于数据库太大，尽管这个时候数据库磁盘空间也大大提高了，但仍然无法跟上数据增长的速度，而其随着数据量的增大，数据的查询与存储效率也越来越低。为了提高数据库的性能，如何改进数据库查询效率的同时也越来越关注如何将数据压缩技术应用到数据库系统中。面临大数据时代，引起数据库太大，因此必须采用数据压缩技术，对数据进行压缩存储，解决目前由大数据引起地各种问题。压缩技术主要是减少文件所占的存储空间，并且要求压缩过程中不丢失信息。不丢失信息也就是经解压缩文件与压缩之前的文件完全相同。该文介绍了HBASE ，主要介绍HBASE 中支持的压缩算法。并对其中的压缩算法进行了对比分析，并得出结果。

2 HBASE 概述

HBASE是Apache的Hadoop项目的子项目[1]。HBASE 是一个开源的、分布式的、面向列的存储系统。HBASE 是Google Bigtable的开源实现，类似Google Bigtable利用GFS作为其文件存储系统，HBASE 利用Hadoop HDFS作为其文件存储系统；Google运行MapReduce来处理Bigtable中的海量数据，然而HBASE 同样利用Hadoop MapReduce来处理HBASE 中的海量数据；Google Bigtable利用 Chubby作为协同服务，然而HBASE 利用Zookeeper作为对应协调系统。HBASE [2]是一个面向列、可伸缩的、以键值对形式来存储数据的分布式存储系统，是Google的Big-table[3]的一种开源实现，它与传统的关系型数据库模型不一样。HBASE 是Hadoop的一个子项目，它是在HDFS[4]之上开发的面向列的分布式数据库，可用于实时地随机读写大规模数据集。并且利用HBASE 可搭建起大规模结构化存储集群在廉价PC Sever上。当用户由关系数据库向HBASE 迁移时就不必对程序重新修改，因此降低了迁移成本，能促进HBASE 发展且具有现实应用价值。HBASE 不同于传统的关系数据库，采用基于列的存储而不是基于行的存储模式。在基于列存储的数据库的数据表中，数据表中的每列单独存放在相邻的物理单元；这样查询时只需要访问涉及的列，不需要将整行数据都进行读取处理，大大降低系统的I/O开销；读取每列时可以由一个线程进行处理完成，同时也支持读取并发处理。

3 压缩算法

压缩算法分为无损压缩和有损压缩。两者相比，无损压缩比不高，但是它100%的保存了原始信息。无损压缩从压缩模型上主要分为基于统计的压缩算法和基于字典的压缩算法。基于字典压缩算法主要有LZ77[4]算法、LZ78[5]算法、LZW[6]算法、LZSS[7]算法。基于统计压缩算法主要有香浓-凡诺编码（Shanno-Fano）、游程长度编码（RLC）、哈夫曼编码（Huffman）、动态哈夫曼、算术编码。目前HBASE 支持的压缩算法主要有Gzip[8]和LZO [9]。endprint

3.1 Gzip压缩算法

采用Gzip 算法对大数据进行压缩，在压缩过程中首先使用LZ77算法，再使用Huffman编码。LZ77算法的核心思想主要通过相同内容的替换来实现。如果文件中有两块内容相同，那么只要知道前一块的位置和大小，我们就可以简单表达确定后一块内容的相关信息。后一块信息（a，b）可以这样表示，a表示两者之间的距离，b表示相同内容的长度。当这一对信息（a，b）的大小小于被替换内容的大小，这样文件就得到压缩。Huffman编码的压缩原理：把文件中某段位长的值看作是符号。根据这些符号在文件中出现的频率，再对这些符号进行重新编码。按照这样的算法编码，文件的一些部分位数变少了然而一些部分位数变多了，因为变小的部分大于变大的部分，所以整个数据因此得到压缩。

3.2 LZO压缩算法

LZO是Lempel-Ziv-Oberhumer的缩写，LZO是基于LZSS算法是一种无损算法。LZO与Gzip不同在于解压速度，LZO在快速解压表现尤为明显。LZO和LZ77算法类似也是基于字典思想的一种压缩算法，同时使用固定长度滑动窗口用来缓存字典信息，所以LZO的编码也是需要使用一个偏移量，重复长度期待当前字符串。但是LZO与LZ77有一些区别， LZO的编码中没有了LZ77编码的第3项：新字符，当压缩字符与滑动窗体的字典信息没有匹配时使用一个标志位加字符内容标示而不是一个三元组；还有 LZ77使用的是固定的压缩长度，LZO的压缩长度是可变的，范围在13个字节和4096字节之间，最后一点是LZ77压缩时需要滑动窗口内对待压缩数据做最大压缩匹配字符串的搜索，滑动窗口越大搜索消耗的时间也就越大，这是LZ77算法压缩很慢的原因之一，在LZO算法放弃最大压缩匹配字符串的搜索，而是使用的哈希映射的查找方式查找匹配的字符串[10]。

4 算法的分析与比较

数据压缩的性能指标主要有：压缩率、压缩速度、解压速度、压缩时间。衡量压缩空间上的变量主要指标是压缩率。同时压缩时间是衡量数据压缩性能的一个很重要的指标。对于大数据的特点，在这里主要讨论压缩率。压缩率与压缩速度公式如下：

[压缩率=][压缩之后数据大小原始数据大小]，[压缩速度=原始数据大小压缩时间]

通过多次测试求平均值的方法得出压缩率[f]，对于定量的文件[A]大小进行压缩。[T1]表示第一次对文件大小进行压缩时得出的压缩结果，[Tn]表示第n次文件进行压缩取得的压缩结果。

[f1] 根据第一次压缩求到的压缩率[f1=AT1]，第n次的压缩率为[fn=ATn]，由此可以通过多次测试得出压缩率[f=] [f1+f2+.....fnn]。为了比较两种压缩的效果，采用定量的数据压缩。通过测试得以下数据。

表1 测试数据结果

[压缩算法＼&原始文件GB＼&压缩后文件GB＼&压缩速度MB/S＼&压缩率%＼&Gzip＼&16.6＼&3.6＼&17.5＼&21.5＼&LZO＼&16.6＼&5.8＼&49.3＼&35.1＼&]

从以上测试数据可知：当文件大小与硬件设备相同条件下，Gzip压缩率优于LZO压缩，但是压缩速度上LZO压缩更为突出。在空间和时间性能的限制中，Gzip的压缩率较低，压缩效果好，LZO压缩速度快。根据不同的需求可以选择不同的压缩，当对空间要求较高将采用Gzip压缩，当对时间要求比较严格可采用LZO压缩。

5 总结

本文对HBASE中支持的两种算法进行了比较、分析，并得出结果。在不同的场景根据需求将选择不同的算法。如果在要求读取压缩文件时，将进一步考虑解压速度。大数据如此重要，以至于其获取、储存、查询、共享、分析，数据挖掘乃至可视化地呈现，都成为了当前重要的研究课题。

未来的工作中，我们将会对如何对大数据挖掘、分析用户行为展开进一步地研究，以提高信息的可用性与有效性。同时，进一步研究如何规划大数据存储策略，是未来大数据挑战的工作之一。

参考文献：

[1] HBASE.http：//HBASE.apache.org/[EB/OL].[2011-02-16].

[2] HBASE ：bigtable-like structured storage for hadoop hdfs[EB/OL].http：/hadoop.apache.org/HBASE /，2010

[3] Fan Chang， Jeffrey Dean ， Sanjay Chemawat，et al.Bigtable：a distributed storage system for structured data[C].Proceedings of 7 th USENIX Symposium on Operating Systems Design and Implementation，Seattle，W A，USE：USENIX Association，2006：205-218.

[4] Shvachko K V. HDFS Scalability： The limits to growth[J].login，2010，35（2）：6-16.

[5] Wolff F G，Papachristou C.Multiscan-based test compression and hardware decompression using LZ77[C]//Test Conference， 2002. Proceedings. International.IEEE，2002： 331-339.

[6] Li M，Zhu Y.Image classification via LZ78 based string kernel： a comparative study[C]//Advances in knowledge discovery and data mining.Springer Berlin Heidelberg，2006：704-712.

[7] Nelson M R.LZW data compression[J].Dr. Dobb's Journal，1989，14（10）：29-36.

[8] Wiseman Y.The relative efficiency of data compression by LZW and LZSS[J].Data Science Journal，2007，6：1-6.

[9] Gailly J L， Adler M. gzip：The compressor data[J].2011.

[10] 罗燕新.基于HBASE的列存储压缩算法的研究与实现[D].华南理工大学， 2011.endprint

3.1 Gzip压缩算法

采用Gzip 算法对大数据进行压缩，在压缩过程中首先使用LZ77算法，再使用Huffman编码。LZ77算法的核心思想主要通过相同内容的替换来实现。如果文件中有两块内容相同，那么只要知道前一块的位置和大小，我们就可以简单表达确定后一块内容的相关信息。后一块信息（a，b）可以这样表示，a表示两者之间的距离，b表示相同内容的长度。当这一对信息（a，b）的大小小于被替换内容的大小，这样文件就得到压缩。Huffman编码的压缩原理：把文件中某段位长的值看作是符号。根据这些符号在文件中出现的频率，再对这些符号进行重新编码。按照这样的算法编码，文件的一些部分位数变少了然而一些部分位数变多了，因为变小的部分大于变大的部分，所以整个数据因此得到压缩。

3.2 LZO压缩算法

LZO是Lempel-Ziv-Oberhumer的缩写，LZO是基于LZSS算法是一种无损算法。LZO与Gzip不同在于解压速度，LZO在快速解压表现尤为明显。LZO和LZ77算法类似也是基于字典思想的一种压缩算法，同时使用固定长度滑动窗口用来缓存字典信息，所以LZO的编码也是需要使用一个偏移量，重复长度期待当前字符串。但是LZO与LZ77有一些区别， LZO的编码中没有了LZ77编码的第3项：新字符，当压缩字符与滑动窗体的字典信息没有匹配时使用一个标志位加字符内容标示而不是一个三元组；还有 LZ77使用的是固定的压缩长度，LZO的压缩长度是可变的，范围在13个字节和4096字节之间，最后一点是LZ77压缩时需要滑动窗口内对待压缩数据做最大压缩匹配字符串的搜索，滑动窗口越大搜索消耗的时间也就越大，这是LZ77算法压缩很慢的原因之一，在LZO算法放弃最大压缩匹配字符串的搜索，而是使用的哈希映射的查找方式查找匹配的字符串[10]。

4 算法的分析与比较

数据压缩的性能指标主要有：压缩率、压缩速度、解压速度、压缩时间。衡量压缩空间上的变量主要指标是压缩率。同时压缩时间是衡量数据压缩性能的一个很重要的指标。对于大数据的特点，在这里主要讨论压缩率。压缩率与压缩速度公式如下：

[压缩率=][压缩之后数据大小原始数据大小]，[压缩速度=原始数据大小压缩时间]

通过多次测试求平均值的方法得出压缩率[f]，对于定量的文件[A]大小进行压缩。[T1]表示第一次对文件大小进行压缩时得出的压缩结果，[Tn]表示第n次文件进行压缩取得的压缩结果。

[f1] 根据第一次压缩求到的压缩率[f1=AT1]，第n次的压缩率为[fn=ATn]，由此可以通过多次测试得出压缩率[f=] [f1+f2+.....fnn]。为了比较两种压缩的效果，采用定量的数据压缩。通过测试得以下数据。

表1 测试数据结果

[压缩算法＼&原始文件GB＼&压缩后文件GB＼&压缩速度MB/S＼&压缩率%＼&Gzip＼&16.6＼&3.6＼&17.5＼&21.5＼&LZO＼&16.6＼&5.8＼&49.3＼&35.1＼&]

从以上测试数据可知：当文件大小与硬件设备相同条件下，Gzip压缩率优于LZO压缩，但是压缩速度上LZO压缩更为突出。在空间和时间性能的限制中，Gzip的压缩率较低，压缩效果好，LZO压缩速度快。根据不同的需求可以选择不同的压缩，当对空间要求较高将采用Gzip压缩，当对时间要求比较严格可采用LZO压缩。

5 总结

本文对HBASE中支持的两种算法进行了比较、分析，并得出结果。在不同的场景根据需求将选择不同的算法。如果在要求读取压缩文件时，将进一步考虑解压速度。大数据如此重要，以至于其获取、储存、查询、共享、分析，数据挖掘乃至可视化地呈现，都成为了当前重要的研究课题。

未来的工作中，我们将会对如何对大数据挖掘、分析用户行为展开进一步地研究，以提高信息的可用性与有效性。同时，进一步研究如何规划大数据存储策略，是未来大数据挑战的工作之一。

参考文献：

[1] HBASE.http：//HBASE.apache.org/[EB/OL].[2011-02-16].

[2] HBASE ：bigtable-like structured storage for hadoop hdfs[EB/OL].http：/hadoop.apache.org/HBASE /，2010

[3] Fan Chang， Jeffrey Dean ， Sanjay Chemawat，et al.Bigtable：a distributed storage system for structured data[C].Proceedings of 7 th USENIX Symposium on Operating Systems Design and Implementation，Seattle，W A，USE：USENIX Association，2006：205-218.

[4] Shvachko K V. HDFS Scalability： The limits to growth[J].login，2010，35（2）：6-16.

[5] Wolff F G，Papachristou C.Multiscan-based test compression and hardware decompression using LZ77[C]//Test Conference， 2002. Proceedings. International.IEEE，2002： 331-339.

[6] Li M，Zhu Y.Image classification via LZ78 based string kernel： a comparative study[C]//Advances in knowledge discovery and data mining.Springer Berlin Heidelberg，2006：704-712.

[7] Nelson M R.LZW data compression[J].Dr. Dobb's Journal，1989，14（10）：29-36.

[8] Wiseman Y.The relative efficiency of data compression by LZW and LZSS[J].Data Science Journal，2007，6：1-6.

[9] Gailly J L， Adler M. gzip：The compressor data[J].2011.

[10] 罗燕新.基于HBASE的列存储压缩算法的研究与实现[D].华南理工大学， 2011.endprint

3.1 Gzip压缩算法

采用Gzip 算法对大数据进行压缩，在压缩过程中首先使用LZ77算法，再使用Huffman编码。LZ77算法的核心思想主要通过相同内容的替换来实现。如果文件中有两块内容相同，那么只要知道前一块的位置和大小，我们就可以简单表达确定后一块内容的相关信息。后一块信息（a，b）可以这样表示，a表示两者之间的距离，b表示相同内容的长度。当这一对信息（a，b）的大小小于被替换内容的大小，这样文件就得到压缩。Huffman编码的压缩原理：把文件中某段位长的值看作是符号。根据这些符号在文件中出现的频率，再对这些符号进行重新编码。按照这样的算法编码，文件的一些部分位数变少了然而一些部分位数变多了，因为变小的部分大于变大的部分，所以整个数据因此得到压缩。

3.2 LZO压缩算法

LZO是Lempel-Ziv-Oberhumer的缩写，LZO是基于LZSS算法是一种无损算法。LZO与Gzip不同在于解压速度，LZO在快速解压表现尤为明显。LZO和LZ77算法类似也是基于字典思想的一种压缩算法，同时使用固定长度滑动窗口用来缓存字典信息，所以LZO的编码也是需要使用一个偏移量，重复长度期待当前字符串。但是LZO与LZ77有一些区别， LZO的编码中没有了LZ77编码的第3项：新字符，当压缩字符与滑动窗体的字典信息没有匹配时使用一个标志位加字符内容标示而不是一个三元组；还有 LZ77使用的是固定的压缩长度，LZO的压缩长度是可变的，范围在13个字节和4096字节之间，最后一点是LZ77压缩时需要滑动窗口内对待压缩数据做最大压缩匹配字符串的搜索，滑动窗口越大搜索消耗的时间也就越大，这是LZ77算法压缩很慢的原因之一，在LZO算法放弃最大压缩匹配字符串的搜索，而是使用的哈希映射的查找方式查找匹配的字符串[10]。

4 算法的分析与比较

数据压缩的性能指标主要有：压缩率、压缩速度、解压速度、压缩时间。衡量压缩空间上的变量主要指标是压缩率。同时压缩时间是衡量数据压缩性能的一个很重要的指标。对于大数据的特点，在这里主要讨论压缩率。压缩率与压缩速度公式如下：

[压缩率=][压缩之后数据大小原始数据大小]，[压缩速度=原始数据大小压缩时间]

通过多次测试求平均值的方法得出压缩率[f]，对于定量的文件[A]大小进行压缩。[T1]表示第一次对文件大小进行压缩时得出的压缩结果，[Tn]表示第n次文件进行压缩取得的压缩结果。

[f1] 根据第一次压缩求到的压缩率[f1=AT1]，第n次的压缩率为[fn=ATn]，由此可以通过多次测试得出压缩率[f=] [f1+f2+.....fnn]。为了比较两种压缩的效果，采用定量的数据压缩。通过测试得以下数据。

表1 测试数据结果

[压缩算法＼&原始文件GB＼&压缩后文件GB＼&压缩速度MB/S＼&压缩率%＼&Gzip＼&16.6＼&3.6＼&17.5＼&21.5＼&LZO＼&16.6＼&5.8＼&49.3＼&35.1＼&]

从以上测试数据可知：当文件大小与硬件设备相同条件下，Gzip压缩率优于LZO压缩，但是压缩速度上LZO压缩更为突出。在空间和时间性能的限制中，Gzip的压缩率较低，压缩效果好，LZO压缩速度快。根据不同的需求可以选择不同的压缩，当对空间要求较高将采用Gzip压缩，当对时间要求比较严格可采用LZO压缩。

5 总结

本文对HBASE中支持的两种算法进行了比较、分析，并得出结果。在不同的场景根据需求将选择不同的算法。如果在要求读取压缩文件时，将进一步考虑解压速度。大数据如此重要，以至于其获取、储存、查询、共享、分析，数据挖掘乃至可视化地呈现，都成为了当前重要的研究课题。

未来的工作中，我们将会对如何对大数据挖掘、分析用户行为展开进一步地研究，以提高信息的可用性与有效性。同时，进一步研究如何规划大数据存储策略，是未来大数据挑战的工作之一。

参考文献：

[1] HBASE.http：//HBASE.apache.org/[EB/OL].[2011-02-16].

[2] HBASE ：bigtable-like structured storage for hadoop hdfs[EB/OL].http：/hadoop.apache.org/HBASE /，2010

[3] Fan Chang， Jeffrey Dean ， Sanjay Chemawat，et al.Bigtable：a distributed storage system for structured data[C].Proceedings of 7 th USENIX Symposium on Operating Systems Design and Implementation，Seattle，W A，USE：USENIX Association，2006：205-218.

[4] Shvachko K V. HDFS Scalability： The limits to growth[J].login，2010，35（2）：6-16.

[5] Wolff F G，Papachristou C.Multiscan-based test compression and hardware decompression using LZ77[C]//Test Conference， 2002. Proceedings. International.IEEE，2002： 331-339.

[6] Li M，Zhu Y.Image classification via LZ78 based string kernel： a comparative study[C]//Advances in knowledge discovery and data mining.Springer Berlin Heidelberg，2006：704-712.

[7] Nelson M R.LZW data compression[J].Dr. Dobb's Journal，1989，14（10）：29-36.

[8] Wiseman Y.The relative efficiency of data compression by LZW and LZSS[J].Data Science Journal，2007，6：1-6.

[9] Gailly J L， Adler M. gzip：The compressor data[J].2011.

[10] 罗燕新.基于HBASE的列存储压缩算法的研究与实现[D].华南理工大学， 2011.endprint