HBase是怎样从HFile中找到某个rowkey

如果创建表时，指定了BloomFilter，那么就根据BloomFilter快速的判断该rowkey是否在这个HFile中。但BloomFilter也会存在错误率。所以主要来看下不使用BloomFilter下，是如何查找到rowkey在哪个HFile下。 

HBase首先根据时间戳和查询列的信息对file做一次过滤，将查询范围缩小。仍然需要扫描其余的文件，storeFile之间是无序的，而且StoreFile的rowkey范围会有交叉，所以并不会按照StoreFile顺序的查找。HBase会首先查看每个StoreFile的最小的rowkey，然后按照从小到大的顺序进行排序，结果放到一个队列中。接下来只会扫描比查询Rowkey大的记录的StoreFile，下面开始查询数据，整个过程用到了类似归并排序的算法，首先通过poll取出队列的头storefile，会从storefile读取一条记录返回；接下来呢，该StoreFile的下条记录并不一定是查询结果的下一条记录，因为队列的比较顺序是比较的每个storefile的第一条符合要求的rowkey。所以，hbase会继续从队列中剩下的storefile取第一条记录，把该记录与头storefile的第二条记录做比较，如果前者大，那么返回头storefile的第二条记录；如果后者大，则会把头storefile放回队列重新排序，在重新取队列的头storefile。然后重复上面的整个过程，直到找到key所在的HFile。范围缩小到该HFile后，就根据HFile文件中的索引去定位到块，快速的找到对应的记录。单个HFile文件中的索引主要是根据索引块的大小来提升速率。

Region下单个HFile文件数越多，一次查询就会需要更多的IO操作，延迟必然会越来越大。

如下图一所示，随着数据写入不断增加，文件数不断增多，读取延时也在不断变大

文件数基本稳定，进而IO Seek次数会比较稳定，延迟就会稳定在一定范围。下图是不断写入数据，hfile数量变多，不断Compaction合成大文件，文件数量基本稳定，查询时延也基本稳定

HFile结构

HFile的数据块，元数据块通常采用压缩方式存储，压缩之后可以大大减少网络IO和磁盘IO

图中上面三层为索引层，在数据量不大的时候只有最上面一层，数据量大了之后开始分裂为多层，最多三层，如图所示。最下面一层为数据层，存储用户的实际keyvalue数据。这个索引树结构类似于InnoSQL的聚集索引，只是HBase并没有辅助索引的概念。

图中红线表示一次查询的索引过程（HBase中相关类为HFileBlockIndex和HFileReaderV2），基本流程可以表示为：

1. 用户输入rowkey为fb，在root index block中通过二分查找定位到fb在’a’和’m’之间，因此需要访问索引’a’指向的中间节点。因为root index block常驻内存，所以这个过程很快。

2. 将索引’a’指向的中间节点索引块加载到内存，然后通过二分查找定位到fb在index ‘d’和’h’之间，接下来访问索引’d’指向的叶子节点。

3. 同理，将索引’d’指向的中间节点索引块加载到内存，一样通过二分查找定位找到fb在index ‘f’和’g’之间，最后需要访问索引’f’指向的数据块节点。

4. 将索引’f’指向的数据块加载到内存，通过遍历的方式找到对应的keyvalue。

上述流程中因为中间节点、叶子节点和数据块都需要加载到内存，所以io次数正常为3次。但是实际上HBase为block提供了缓存机制，可以将频繁使用的block缓存在内存中，可以进一步加快实际读取过程。所以，在HBase中，通常一次随机读请求最多会产生3次io，如果数据量小（只有一层索引），数据已经缓存到了内存，就不会产生io。