奇虎360 HBASE二级索引的设计与实践  

赵健博  系统部  2015/4/24 

内容梗概 

• 背景  • 设计  • 实践 



 Page 2  

背景 

• 仅基于RK的索引问题：

– 索引单一 – 多维度（字段/列）查询困难

• 多字段分别作为RK，写入多次 • 组合字段作为RK，设计复杂，不灵活 – 不经过索引的并行scan过滤，大量资源消耗，无实效性可言

• 多维度实时查询需求强烈：

– 基于DNS 的网络行为特征分析

– 基于病毒样本的网络行为特征分析 

 Page 3  

背景 

• 通用模式：

– 将数据结构化存储（海量的数据，千亿级别） – 对多个列或者多列之间建立索引 – 指定条件：

• 单列等值、范围 • 多列之间与、或

– 获取结果：

• 满足条件的记录 • 满足条件的记录个数 • 满足条件的记录按照某列，或者某几列的统计 

 Page 4  

内容梗概 

• 需求  • 设计  • 实践 



 Page 5  

设计 

• 总体设计 • 索引设计 • 索引类型 • 写路径 • 读路径 • 分裂 • 索引重建 • 优化 • 汇聚操作 • 模糊查询 



 Page 6  

总体设计 



rowkey

RK1 RK2 RK3 RK4



cf1 cf1

c21 c22 c23 c24

cf1:col2=c22



c21 RK1



c22



RK2



rowkey



cf1 cf1



c23 RK3 RK1

c24 RK4 RK2



c21 c22



RK3 c23



RK4 c24



 Page 7  

总体设计 



/



Region1



Region2



RegionServer



Region3



Region4



TableA



RegionServer



分布式、并发式数据查询与索引构建



 Page 8  

索引设计 

rowkey RK1 RK2

RK3 RK4



INDEX=>cf1:col2->Int cf1:col1 cf1:col2

cf1 Region1 c21 c22

c23 cf1 Region2 c24



 Page 9  

索引设计 



rowkey



INDEX=>cf1:col2->Int cf1:col1 cf1:col2



Region1 Region1

RK1 RK2



cf1 c21 c22



Region2. Region2

RK3 RK4



c23 cf1 c24



INDEX:col INDEX Region1

INDEX Region2



索引和数据在同一个



内，但索引数据存储在单独



中



 Page 10  

索引设计 



rowkey

RK1 RK2



cf1:col1 cf1:col2

c21 c22



INDEX1=>cf1:col2->Int INDEX2=>cf1:col1->Int,cf1:col2->Int



反序列化信息：



 Page 11  

索引设计 

• 索引的说明存储在表schema中

– {NAME => 'whitelist_dsv', FAMILIES => [{NAME => 'INDEX', BLOOMFILTER => 'INDEXROW', COMPRESSION => 'LZO', VERSIONS => '1', INDEX=>{IDX_CERT=>value:cert_sha1# IDX_SIGN=>value:sign_corp#IDX_SHA1=>value:sha1} }, {NAME => 'value', BLOOMFILTER => 'ROW', VERSIONS => '1', COMPRESSION => 'LZO'}]}

• 索引说明可以动态变更

 Page 12  

索引类型 

索引类型  Char  Byte  Short  Int  Long  Float  Double  String  Text  多列组合索引 



长度  2  1  2  4  8  4  8  -  -  - 



备注  等值，范围查询  等值，范围查询  等值，范围查询  等值，范围查询  等值，范围查询  等值，范围查询  等值，范围查询  精确匹配，范围查询  模糊查询  索引优化 

 Page 13  

写路径 



RegionServer



Region



Put 2



Region



1 MemStore



Put 4



HLog



 Page 14  

读路径 



get col1 where col2=c21 | col3=c31

createScanner condition



create indexScanner IndexFamily

OR



Region



Leaf

startRow: SK+IDX1+c21 endRow: SK+IDX1+c21' ss



Leaf

startRow: SK+IDX2+c31 ss endRow: SK+IDX2+c31'



 Page 15  

读路径 



Region



IndexFamily OR



next



dataFamily



next



RK list



Leaf



Leaf



ss



seek



sfs sfs



ss ss



 Page 16  

分裂 



parent parent



splitKey



RK1 RK2



INDEX



Parent Region



c21 cf1 c22



 Page 17  

分裂 

parent RK1

daughterB RK2



cf1 c21

cf1 c22



daughterA INDEX Region



INDEX



daughterB Region



 Page 18  

分裂 



parent parent



splitKey



RK1 RK2



create indexScanner startRow parent.SK+IDX+c22 endRow parent.SK+IDX+c22'



create indexScanner startRow daughterB.SK+IDX+c22 endRow daughterB.SK+IDX+c22'



daughterB RK2



INDEX



Parent Region



cf1 c21 c22



cf1 c22



INDEX



daughterB Region



 Page 19  

索引重建 



• 索引会有垃圾：

– 数据覆盖写操作，导致数据超过最大version。但由 于value不同，导致索引产生垃圾

• 索引重建流程：

– 重建前，记录当前所有索引文件 – 扫面数据，重新生成索引 – 删除掉之前记录的索引文件，重建完成



• 状态跟踪：

– INDEXTABLE保存状态



 Page 20  

优化 



• 列和时间建立联合索引



• 常用组合查询建立联合索引



• 查询表达式的转换：

– (A | B) & (C | D) ó (A&C) | (A&D) | (B&C) | (B&D )



• New Bloomfilter type • 多范围与操作查询优化 • 索引的带外数据（TODO）



 Page 21  

New BloomFilter Type 



INDEX1=>cf1:col2->Int



rowkey

RK1 RK2



cf1:col1 cf1:col2

c21 c22



Simple Case get cf



 Page 22  

New BloomFilter Type 

• INDEXROW • 针对定值查询优化

– 单列索引定值 – 组合索引定值

• 写入时，对索引数据的中的原RowKey截断， 构建BF

– StartKey+INDEX+value+原RowKey – 去除原RowKey后（黄色部分），构建BF数据

• 查询索引时，根据检索表达式定值部分匹配BF

 Page 23  

New BloomFilter Type 

INDEX1=>cf1:col2->Int



rowkey

RK1 RK2



cf1:col1 cf1:col2

c21 c22



Simple Case get cf



 Page 24  

多范围与操作查询优化 

• a’ < A < a’’ & b’ < B < b’’ • 传统过程：

– 获取列A在(a’, a’’)区间的RK集合RKS1 – 获取列B在(b’, b’’)区间的RK集合RKS2 – 对RKS1和RKS2取交集

• 问题：

– A和B集合任何一个过大，查询时间都很长 – 内存风险

• 解决

– A和B建立联合索引 – 支持多范围查询，并优化 



 Page 25  

多范围与操作查询优化 

2 col

SK+IDX+1+1+RK1 SK+IDX+1+2+RK2 SK+IDX+1+3+RK3 SK+IDX+1+4+RK4 SK+IDX+1+5+RK5 SK+IDX+1+6+RK6 SK+IDX+2+1+RK7 SK+IDX+2+2+RK8 SK+IDX+2+3+RK9 SK+IDX+2+4+RK10 SK+IDX+2+5+RK11 SK+IDX+2+6+RK12 SK+IDX+3+1+RK13 SK+IDX+3+2+RK14 SK+IDX+3+3+RK15 SK+IDX+3+4+RK16 SK+IDX+3+5+RK17 SK+IDX+3+6+RK18



() () ()

 Page 26  

索引的带外数据 

• 检索过程能不能再快？ 

INDEX1=>cf1:col2->Int



rowkey

RK1 RK2



cf1:col1 cf1:col2

c21 c22



Simple Case get cf



 Page 27  

索引的带外数据 

INDEX1=>cf1:col2->Int



rowkey



cf1:col1 cf1:col2



RK1 c21 RK2 c22



• 优点：

– 一次scan，获取结果 – 顺序IO，极高性能



cf1:col1



Simple Case get cf



• 缺点：

– 更多的存储成本 



 Page 28  

汇聚操作 

• 利用coprocessor框架实现 • 操作：

– Count

• 通过索引获取记录，统计获取的记录个数 • 直接通过索引统计记录个数

– groupBy

• 通过索引获取记录，然后列计数统计

• 采样优化

– 如果仅仅是估算大概数量，可以通过采样部分region 的统计结果来估算整体的计数情况 

 Page 29  

模糊查询 

• 模糊查询

– 通过某列值中的某个term查询整行 – 通过某列值中的子短语查询整行 – 通过通用规则（*/?）查询整行

• 实现：

– Lucene引擎引入到HBase – 写Text类型列时，建立RK与文档，列值分词与文档

的映射。实现分词=>文档=>RK关系 – 查询时，根据条件，通过Lucene引擎找到文档，然

后从文档中取出RK，最后再根据RK获取整行 

 Page 30  

二级索引方案比较 



奇虎360 



单列，多列联合索引  YES 



多列之前与或查询 



YES 



索引动态修改 



YES 



索引重建 



YES 



模糊查询 



YES 



汇聚操作 



YES 



单独索引表 



NO 



Region分配策略修改  NO 



数据与索引一致性问题  NO 



多范围与操作优化 



YES 



华为 

YES  YES  NO？ NO？ NO NO YES YES YES NO



 Page 31  

内容梗概 

• 需求  • 设计  • 实践 



 Page 32  

实践 

• 表设计

– 单列索引 – 单列与时间的联合索引 – 多列组合索引

• 查询表达式优化

– (A | B) & (C | D) ó (A&C) | (A&D) | (B&C) | (B&D)

 Page 33  

单并发写入性能 

 Page 34  

检索性能数据 



70台机器 {CPU：2路6核，内存：64GB，12*4TB磁盘}



列与索引列  数据规模  容量 



CASE1 



CASE2 



19列 + 17个索引



10列 + 10个索引



5000亿行（18万亿KV） 4000亿行（8万亿KV） 



500+TB



200+TB



高频查询 



单列定值  (A|B) & (C|D)  



单列定值 



查询时延  返回条目数  查询次数 



平均5.5s  5000  70000+ 



平均6s  3000+  2400+ 



 Page 35  

Thanks!