浅谈DB的分层索引

Time: 二月 29, 2012
Category: storage

HFile是Hbase的底层存储文件结构,目前有两个版本v1和v2,要理解HFile的设计,这里 http://www.slideshare.net/schubertzhang/hfile-a-blockindexed-file-format-to-store-sorted-keyvalue-pairs,这里 https://issues.apache.org/jira/browse/HBASE-3857

HFile在v2里引入分层索引,是很值得研究的地方,对其他key-value db的设计有借鉴意义,此外,还有 compound Bloom filter,同样很值得思考

 

传统keyvalue数据库索引的设计

将索引结构顺序写到磁盘上,形成一个 Data Index Block,Data Index Block 会在数据库文件被打开时全部加载到内存。这样就可以根据内存中的索引数据检查出某个key具体在哪块block上,如果此块Data block IN_CACHE,就直接从内存里返回数据,如果IN_DISK,就lseek到偏移量处,将整块Block加载到内存,通常会使用lru算法来维护内存中的data block块数据,结构如下

在索引文件太大,1GB,数GB这种情况下,对性能会有很大的影响。因为会有频繁的 Data Block 被swaped到磁盘,又cache到内存。

 

分层索引

所以 HFile 在v2中开始引入了分层索引这一尝试,将索引文件分为 root block index 和 non-root block index 两种。root block index 会在数据库文件打开时被加载到内存。而non-root block index 会根据需要加载到内存,non-root block index 可以只有leaf-index block,或者还会有 intermediate level index block,如果Data Block 数据块个数少,leaf-index block 和 root block index足以,否则就需要加入中间层索引,也就是 intermediate level index block,它在 HFile文件里是可选的。实际情况下索引的层级不会超过两层。

root block index 由连续的entries组成,entry的结构如下,entry的个数会被记录在trailer结构里

如果是single level index,那么root block index里的每个entry就对应一个data block,这和 HFile v1是一样的。如果是two level index,那么root block index里的每个entry就指向每个leaf index block,而每个leaf index block则记录了对应的一系列Data block的偏移量。如果是三层,情况就要更复杂一下,root block index 里的entries指向intermediate level index block,而intermediate level index block则指向leaf index block。

leaf index block和intermediate level index block都以相同的格式封装在non-root block index里。结构类似于root block index,都是由连续的entries组成。

  1. numEntries 整块index block里的entry总数
  2. entryOffsets 每个entry的偏移量都记录在这里,目的是为了方便scan,二分搜索
  3. entries entry的结构和上述root block index里相同,由offset, on-disk size, key 组成

性能问题

HFile工作组目前已经在超过100个节点的集群环境里测试超过1个月时间,性能问题仍然有待考证。

如果lru,分层索引表面上可以解决由于索引文件过大而引起的加重IO负担问题。其实不然,会有一个不好的地方,传统的key-value db索引文件大多是平坦模型,能加载多少的数据,取决于服务器的主存规格。加入分层索引,就有了树的高度,就是b树,如果cache不命中,最坏情况下要都磁盘走两次,一次index block,然后才到data block。

至于这个问题是否成为性能问题的关键,要看实际的测试数据如何了

Leave a Comment