AirJD 焦点
AirJD

没有录音文件
00:00/00:00
加收藏

奇虎360 HBASE二级索引的设计与实践 by 赵健博

发布者 dber
发布于 1450227664504  浏览 2814 关键词 HBase, 存储, NoSQL 
分享到

第1页

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

赵健博  系统部  2015/4/24 



第2页

内容梗概 

• 背景  • 设计  • 实践 



 Page 2  



第3页

背景 

• 仅基于RK的索引问题:

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

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

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

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

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

 Page 3  



第4页

背景 

• 通用模式:

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

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

– 获取结果:

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

 Page 4  



第5页

内容梗概 

• 需求  • 设计  • 实践 



 Page 5  



第6页

设计 

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



 Page 6  



第7页

总体设计 



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  



第8页

总体设计 



/



Region1



Region2



RegionServer



Region3



Region4



TableA



RegionServer



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



 Page 8  



第9页

索引设计 

rowkey RK1 RK2

RK3 RK4



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

cf1 Region1 c21 c22

c23 cf1 Region2 c24



 Page 9  



第10页

索引设计 



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  



第11页

索引设计 



rowkey

RK1 RK2



cf1:col1 cf1:col2

c21 c22



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



反序列化信息:



 Page 11  



第12页

索引设计 

• 索引的说明存储在表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  



第13页

索引类型 

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



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



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

 Page 13  



第14页

写路径 



RegionServer



Region



Put 2



Region



1 MemStore



Put 4



HLog



 Page 14  



第15页

读路径 



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  



第16页

读路径 



Region



IndexFamily OR



next



dataFamily



next



RK list



Leaf



Leaf



ss



seek



sfs sfs



ss ss



 Page 16  



第17页

分裂 



parent parent



splitKey



RK1 RK2



INDEX



Parent Region



c21 cf1 c22



 Page 17  



第18页

分裂 

parent RK1

daughterB RK2



cf1 c21

cf1 c22



daughterA INDEX Region



INDEX



daughterB Region



 Page 18  



第19页

分裂 



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  



第20页

索引重建 



• 索引会有垃圾:

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

• 索引重建流程:

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



• 状态跟踪:

– INDEXTABLE保存状态



 Page 20  



第21页

优化 



• 列和时间建立联合索引



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



• 查询表达式的转换:

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



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



 Page 21  



第22页

New BloomFilter Type 



INDEX1=>cf1:col2->Int



rowkey

RK1 RK2



cf1:col1 cf1:col2

c21 c22



Simple Case get cf



 Page 22  



第23页

New BloomFilter Type 

• INDEXROW • 针对定值查询优化

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

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

– StartKey+INDEX+value+原RowKey – 去除原RowKey后(黄色部分),构建BF数据

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

 Page 23  



第24页

New BloomFilter Type 

INDEX1=>cf1:col2->Int



rowkey

RK1 RK2



cf1:col1 cf1:col2

c21 c22



Simple Case get cf



 Page 24  



第25页

多范围与操作查询优化 

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

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

• 问题:

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

• 解决

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



 Page 25  



第26页

多范围与操作查询优化 

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  



第27页

索引的带外数据 

• 检索过程能不能再快? 

INDEX1=>cf1:col2->Int



rowkey

RK1 RK2



cf1:col1 cf1:col2

c21 c22



Simple Case get cf



 Page 27  



第28页

索引的带外数据 

INDEX1=>cf1:col2->Int



rowkey



cf1:col1 cf1:col2



RK1 c21 RK2 c22



• 优点:

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



cf1:col1



Simple Case get cf



• 缺点:

– 更多的存储成本 



 Page 28  



第29页

汇聚操作 

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

– Count

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

– groupBy

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

• 采样优化

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

 Page 29  



第30页

模糊查询 

• 模糊查询

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

• 实现:

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

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

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

 Page 30  



第31页

二级索引方案比较 



奇虎360 



单列,多列联合索引  YES 



多列之前与或查询 



YES 



索引动态修改 



YES 



索引重建 



YES 



模糊查询 



YES 



汇聚操作 



YES 



单独索引表 



NO 



Region分配策略修改  NO 



数据与索引一致性问题  NO 



多范围与操作优化 



YES 



华为 

YES  YES  NO? NO? NO NO YES YES YES NO



 Page 31  



第32页

内容梗概 

• 需求  • 设计  • 实践 



 Page 32  



第33页

实践 

• 表设计

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

• 查询表达式优化

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

 Page 33  



第34页

单并发写入性能 

 Page 34  



第35页

检索性能数据 



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  



第36页

Thanks!



支持文件格式:*.ppt, *.pptx, *.pdf
上传最后阶段需要进行在线转换,可能需要1~2分钟,请耐心等待。