在过去的3年中, 随着用户规模的快速增加和移动互联网业务的高速发展, 每天用户和服务产生的数据规模已达PB级, 电信运营商面临着数据爆炸式增长的巨大压力, 可存储并对海量数据进行分析的Hadoop开源系统[1]已成为主流电信运营商、互联网公司的研究和应用热点。然而, Hadoop开源系统并不能完全满足电信运营商的全部需求 (如交互式查询、基于索引的分析优化、多租户支持等) 。为解决这些问题, 设计并研发了Huge Table数据仓库。与Hadoop开源系统相比, Huge Table能支持密集索引、稀疏索引和块索引, 从而加快了查询和分析的速度。查询过程中, Huge Table首先会使用索引。如果没有索引, 系统则会为用户提供针对小数据量的顺序扫描方式和大数据量的Map Reduce方式进行查询。在实际的应用测试评估中, Huge Table的索引和存储引擎极大地提高了查询性能, 满足了现网服务系统的性能需求。

自2009年发放3G牌照后, 我国现已拥有了上亿的移动互联网用户, 他们每天通过手机对互联网的访问产生了高达数十TB的访问记录。这显然是传统关系数据库所无法支持的。除存储容量外, 海量数据带来的更大挑战是如何加载、查询和分析数据。由于商业数据库要对数据进行排序和建立索引, 所以这是很难加载海量数据的。为解决海量数据的加载问题, 在数据库中引入了分库和分区的技术措施, 而分库和分区则导致了海量数据查询和分析性能的大幅下降。举例来说, 尽管对建有索引的列进行查询, 其响应时间也往往都在10 s级。另外, 虽然建立在视图基础上的商业数据仓库针对常用查询也可获得很好的查询性能, 但这些定制化的数据仓库却很难进行水平扩展。当需要增加节点时就必须停服, 且节点的增加并不能使性能得到线性的增长。总之, 电信运营商希望能够提供一种海量存储、高可用、高扩展、支持结构化查询语言 (SQL) 和快速响应的数据仓库。

据此云计算应运而生:Google发布了一系列云计算技术, 如Google文件系统 (GFS) [2]和Map Reduce[3];Apache基于GFS和Map Reduce开发了开源软件Hadoop分布式文件系统 (HDFS) [4]。鉴于HDFS具有优越的高可用性和高扩展性, 因此被广泛地应用到网络企业中, 比如Facebook用其部署了超过2 000个节点的HDFS集群、研发了Hive[5], 以支持将SQL语句转换为Map Reduce程序。因此, 传统的基于数据库的企业应用可运行在HDFS上, 并能获得云计算的相关特性。

但对电信运营商来说, HDFS和Hive并不能满足其全部需求 (特别是在多表嵌套查询处理方面) 。对于一个常见的查询, 如“select a.a1, b.b1, c.c1 from a, b, c where a.employid=b.employid and a.msisdn=c.msisdn”, 系统会启动多轮Map Reduce迭代计算, 每轮Map Reduce需通过扫描所有的数据记录来获得结果。测试过程中, GB级别的表查询时间都需数个小时, 而传统数据仓库同样查询的响应时间只为分钟级别, 所以开源系统基于索引的分析性能已成了电信运营商进行部署的最大障碍。

通过分析HDFS、Hive和Hbase, 我们提出的一种面向电信运营商的Huge Table能满足电信运营商的所有需求, 比如功能、性能、扩展性和可管理性等;提出的基于存储引擎的索引模块和针对海量数据的查询策略, 可创建密集索引、稀疏索引和块索引。利用密集索引可准实时地查询每一条数据记录, 利用稀疏索引可存储数据记录的块信息, 利用块索引可记录每个块里面所包含的索引记录的区间信息。对于Huge Table来说, 密集索引、稀疏索引和块索引对大部分查询都能起到加速作用。在查询过程中, Huge Table首先利用相关列的索引信息进行查询。对于没有索引的列, 用户可利用Huge Table本身提供的查询机制优化查询性能。这些查询机制主要包括针对小数据量的顺序扫描方式及针对大数据量的并行Map Reduce查询机制。

Huge Table的优化主要包括以下几个方面。

索引项和记录项是一一对应的。数据是按照索引顺序进行排列的, 可充分提高查询性能。

只记录索引的块信息, 可在提供查询性能的同时提高加载性能。可快速定位保存记录的数据块, 并在块内查询数据信息。

只记录数据块内的数据区间信息, 在提供查询性能的同时提高加载性能。通过查询数据区间确定是否包含数据记录, 并通过散列函数确定该数据区间是否包含该记录。

分别提供索引查询接口。针对小数据量和大数据量分别提供顺序扫描接口和Map Reduce查询接口。

Google文件系统是一种分布式、大规模可扩展、面向密集数据存取应用的文件系统。该系统具有很强的容错能力, 并能在高并发场景下提供很高的聚合访问性能。GFS在Google有很广泛的应用, 并涵盖了众多产品线及研究项目。当前, Google内部规模最大的GFS集群甚至包括有上千个物理节点, 可提供上百TB存储能力, 可供数百个客户端并发访问。

MR是一种用于处理海量数据的并行编程模型框架, Map函数用于对输入的键值对进行处理并生成中间结果键值对, Reduce汇总具有相同键的所有值并输出汇总计算结果。该模型编写程序能自动并行地运行在大规模部署的通用商业计算节点上。MR运行环境会自动完成很多并行化工作 (如分区输入数据、调度运算任务、处理运行错误等) , 这大大降低了并行程序的开发门槛, 能让更多的没有相关经验的用户方便地利用大规模分布式系统的资源。

Big Table是一种用于结构化数据存储、具有强大可扩展能力的分布式系统, 通常规模可达上千个节点、存储容量可达PB级。目前, Google网页索引、Google地球、Google金融等产品都在使用Big Table。

GFS、MR和BigTable在Google的成功, 催生了一系列开源软件, 例如:Hadoop实现了GFS/MR功能, HBase实现了BigTable功能, 而Hive则能将SQL语句翻译成Map Reduce程序, 可使更多的传统数据库用户方便地利用云计算平台完成他们所熟悉的SQL任务。

此外, Flume[6]和Zookeeper[7]也是非常重要的开源软件。它们可分别用于数据/日志加载和数据节点状态管理/分布式锁。

HugeTable是一种结构化的海量数据存储系统。它支持传统的SQL查询, 主要面向于电信方面的应用。基于中国移动前台业务及后台系统对性能、功能、可扩展性、可管理性等方面的需求, 我们在开发过程中整合并改进了HDFS、HBase、Hive、ZK等开源软件。

基于HugeTable的各种存储引擎, 我们设计了密集索引、稀疏索引和块索引。在查询过程中, Huge Table首先要检查是否存在索引。有索引时HugeTable利用索引对数据进行快速的定位和扫描, 无索引时Huge Table会根据数据量的大小分别启动顺序扫描或Map Reduce扫描来获得查询结果。HugeTable系统架构见图1。由图1可知, HugeTable是基于开源软件Hadoop和Hive研发的, 开发了索引机制和查询模块。

图1 HugeTable系统架构   下载原图

下面主要介绍HugeTable索引的设计方案。

在密集索引中, 每条记录都对应着一条索引项, 如B+树就是一种典型的密集索引结构。HugeTable的主要存储引擎都支持主索引和多个二级索引, 数据记录是按照主索引排序的。HugeTable在建表时即需创建主索引, 而二级索引则可在数据加载后通过一个MapReduce作业来创建。

密集索引的优势主要体现在索引列的高性能查询能力上。例如:采用XXX列索引查询语句“select*from table1 where id=XXX”时, 只需查询XXX列索引, 得到记录位置后即可读取数据, 查询响应时间约为10 ms。当不采用XXX列索引而采用Map Reduce进行数据扫描时, 作业初始化时间则至少为秒级。因此, 密集索引可提高索引列的查询响应性能, 并降低数据IO开销。

稀疏索引记录每个数据块所包含的最大和最小键值。查询时, 将待查询键值与每个索引项的最大和最小键值进行比较而得到候选索引项。每个索引项包含有多个属性值 (如最小、最大键值和文件块号) 。数据库中的数据以文件块的方式进行存储, 文件块的大小在不同系统中有所不同, 每个文件块都有对应的编号, 即文件块号。最大键值和最小键值分别是指该文件块内所有键值中的最大值和最小值。

以电信领域的数据仓库系统为例, 由于系统在一段时间内会产生与同一个移动用户号码 (MSISDN) 相关的多条日志记录, 与同一个MSISDN相关的多条记录都有可能存储在同一个数据块中, 亦即同一个数据块中可能包含有多条具有相同MSIDSN的记录。

基于上述特征, 我们提出了块索引方案。块索引格式为“<key, file ID, block ID>”, 表示在block ID块中包含了某个key, 在该块中可能会包含多个相同的key。以一个具有6.4万条记录的数据块中只包含100个不同的MSISDN记录项的场景为例 (此时可将MSISDN定义为“key”) , 采用密集索引时对同一个块会产生6.4万条记录, 而采用块索引时只需100条索引记录。因此与密集索引相比, 块索引可极大地减少索引数据量。

块索引的优势主要体现在以下3个方面。

与密集索引相比, 由于块索引的数据量较小, 因此读取索引数据的开销也较小。

在块索引列上查询, 可首先通过块索引过滤掉不满足条件的数据块, 只读取相关数据块, 从而提高了查询性能。

通常在加载数据的同时就可以创建索引。

与加载数据本身相比, 创建块索引的成本较低。

以Hive和Hadoop为原型的系统, 是将每个SQL查询都转化为MapReduce查询来获得数据的。这种方式无法满足电信数据仓库的实时响应性能需求, 比如:在数据仓库中对字典表进行的查询, 启动MapReduce本身的时间要远大于数据本身的扫描时间。此外, 索引一般都比数据小很多, 所以扫描索引比数据快得多。

针对上述特性, HugeTable提出了如图2所示的查询框架。当应用提交一个查询SQL时, HugeTable首先会分析查询列的情况:该列有索引时扫描索引就可获得查询结果, 该列无索引时用户可根据应用和数据量本身的特点选择不同的查询方式。比如, 用户数据量较小时可选择顺序扫描查询方式。由于该方式不需启动MapReduce, 节省了启动时间, 所以能提供实时的查询响应能力。另外, 当应用需要实时数据查询响应能力时, 也可优先选择该查询方式;相反, 当用户数据量巨大或应用只需准实时查询响应能力时, 用户需选择MapReduce查询机制。

图2 HugeTable查询框架   下载原图

HugeTable系统已在中国移动现网系统中进行了大量的应用测试评估 (包括四川音乐基地及诺西网关日志存储系统) 。作为数据仓库系统, HugeTable同时也被用于保存GPRS CDR数据。试验系统的测试集群包括1个HugeTable主控节点和4个HugeTable数据节点。在四川音乐基地测试中, HugeTable能在规定的时间内进行音乐订购关系的查询和分析处理;在诺西网关日志存储系统测试中, HugeTable在加载过程中能快速地建立有效的索引系统, 为高速查询分析提供了基础。在后续的查询过程中, 稀疏索引也有效地提高了查询分析性能。

在过去的3年里, 由于用户和移动数据业务的快速增长, 电信服务提供商面临着数据爆炸式增长挑战。传统关系型数据库管理系统 (RDBMS) 已出现了伸缩性不足及性价比高的瓶颈, 与此同时云计算数据仓库已提供了RDBMS的限制能力。基于此, 我们研发了面向电信业务的HugeTable数据仓库系统。

在HugeTable系统中, 我们设计了稀疏索引用于加速查询性能, 设计了密集索引用于满足高性能交互式索引查询。在索引查询基础上, 我们还实现了针对小数据量的顺序扫描实时查询和海量数据的MapReduce查询。在对中国移动现网系统的应用评估中, HugeTable的功能和性能均已达到了应用水平。