HBase原理-迟到的‘数据读取流程’部分细节

笔者去年年底分享了一篇关于HBase中数据读取(scan)逻辑的文章(戳这里),主要介绍了scan的基本流程以及实现框架,看官反应甚是强烈。文章最后还挖了一个不大不小的坑,承诺后期会就部分细节进行深入分析,然而因为部分原因这个坑一直没填上。HBase-Scan的细节其实并不好讲,涉及太多代码层面的底层逻辑,大部分童鞋应该都不会太过关心。虽说如此,挖了的坑,含着泪也要填上,当然为了把坑填好,笔者将会使出洪荒之力将这些核心细节通过各种辅助化方式(示例、图解等)进行解读,方便读者理解。注:笔者能力有限、水平一般,如有不对还望指教。

简单地回顾一下scan的整个流程,如下图所示:



55

上图是一个简单的示意图,用户如果对整个流程比较感兴趣,可以阅读之前的文章,本文将会关注于隐藏在这个示意图中的核心细节。这里笔者挑出了其中五个比较重要的问题来说明,这些问题都是本人之前或早或晚比较困惑的问题,拿出来与大家分享。当然,如果大家有反馈想了解的其他细节,也可以单独交流探讨。


1. 常说HBase数据读取要读Memstore、HFile和Blockcache,为什么上面Scanner只有StoreFileScanner和MemstoreScanner两种?没有BlockcacheScanner?

HBase中数据仅仅独立地存在于Memstore和StoreFile中,Blockcache中的数据只是StoreFile中的部分数据(热点数据),即所有存在于Blockcache的数据必然存在于StoreFile中。因此MemstoreScanner和StoreFileScanner就可以覆盖到所有数据。实际读取时StoreFileScanner通过索引定位到待查找key所在的block之后,首先检查该block是否存在于Blockcache中,如果存在直接取出,如果不存在再到对应的StoreFile中读取。


2.  数据更新操作先将数据写入Memstore,再落盘。落盘之后需不需要更新Blockcache中对应的kv?如果不更新,会不会读到脏数据?

如果理清楚了第一个问题,相信很容易得出这个答案:不需要更新Blockcache中对应的kv,而且不会读到脏数据。数据写入Memstore落盘会形成新的文件,和Blockcache里面的数据是相互独立的,以多版本的方式存在。


3. 读取流程中如何使用BloomFilter(简称BF)对StoreFile进行过滤?

过滤StoreFile发生在上图中第三步,过滤手段主要有三种:根据KeyRange过滤、根据TimeRange过滤、根据BF过滤。下面分别进行介绍:

(1)根据KeyRange过滤:因为StoreFile是中所有KV数据都是有序排列的,所以如果待检索row范围[startrow,stoprow]与文件起始key范围[firstkey,lastkey]没有交集,比如stoprow < firstkey 或者 startrow > lastkey,就可以过滤掉该StoreFile。 

(2)根据TimeRange过滤:StoreFile中元数据有一个关于该File的TimeRange属性[minimumTimestamp, maxmumTimestamp],因此待检索的TimeRange如果与该文件时间范围没有交集,就可以过滤掉该StoreFile;另外,如果该文件所有数据已经过期,也可以过滤淘汰。

(3)根据BF过滤:BF在几乎所有的LSM模型存储领域都会用到,可说是标配,比如HBase、Kudu、RocksDB等等,用法也是如出一辙,和HBase一样,主要用来读取数据时过滤部分文件;除此之外,BF在大数据计算(分布式Join实现)中也扮演重要的角色,参考Impala中Hash Join的实现(戳这里)。BF的具体工作原理笔者假设童鞋都了解(不了解的童鞋可以参考上述链接文章)。

现在来看看HBase中如何利用BF对StoreFile进行过滤(注:接下来所有关于HBase BF的说明都按照Row类型来,Row-Column类型类似),原理其实很简单:首先把BF数据加载到内存;然后使用hash函数对待检索row进行hash,根据hash后的结果在BF数据中进行寻址查看即可确定是否存在该HFile。第二步就是BF的原理,并没有什么好讲的,主要来看看HBase是如何将BF数据加载到内存的。

看过笔者之前文章的童鞋都知道,BF数据实际上是和用户KV数据一样存储在HFile中的,那就需要先看看BF信息是如何存储在HFile中的,查看官方文档中HFile(v2)组织结构图如下:



56

HFile组织结构中关于BF有两个非常重要的结构-Bloom Block与Bloom Index。Bloom Block主要存储BF的实际数据,可能这会大家要问为什么Bloom Block要分布在整个HFile?分布的具体位置如何确定?其实很简单,HBase在写数据的时候就会根据row生成对应的BF信息并写到一个Block中,随着用户数据的不断写入,这个BF Block就会不断增大,当增大到一定阈值之后系统就会重新生成一个新Block,旧Block就会顺序加载到Data Block之后。这里隐含了一个关键的信息,随着单个文件的增大,BF信息会逐渐变的很大,并不适合一次性全部加载到内存,更适合的使用方式是使用哪块加载哪块!

这些Bloom Block分散在HFile中的各个角落,就会带来一个问题:如何有效快速定位到这些BF Block?这就是Bloom Index的核心作用,与Data Index相同,Bloom Index也是一颗B+树,Bloom Index Block结构如下图所示:



57

上图需要重点关注Bloom Block的Block Key:Block中第一个原始KV的RowKey。这样给定一个待检索的 rowkey,就可以很容易地通过Bloom Index定位到具体的Bloom Block,将Block加载到内存进行过滤。通常情况下,热点Bloom Block会常驻内存的!

到此为止,笔者已经解释清楚了HBase是如何利用BF在读取数据时根据rowkey过滤StoreFile的,相信Kudu、RocksDB中BF的原理基本相同。

再回到出发的地方,我们说在实际scan之前就要使用BF对StoreFile进行过滤,那仔细想下,到底用哪个rowkey过滤?实际实现中系统使用scan的startrow作为过滤条件进行过滤,这是不是有问题?举个简单的例子,假设小明检索的数据为[row1, row4],如果此文件不包含row1,而包含row2,这样在scan前你利用row1就把该文件淘汰掉了,row2这条数据怎么办?不是会被遗漏?

这里系统实现有个隐藏点,scan之前使用BF进行过滤只针对get查询以及scan单条数据的场景,scan多条数据并不会执行实际的BF过滤,而是在实际seek到新一行的时候才会启用BF根据新一行rowkey对所有StoreFile过滤。


4. 最小堆中弹出cell之后如何对该cell进行检查过滤,确保满足用户设置条件?检查过滤之后是继续弹出下一个cell,还是跳过部分cell重新seek到下一列或者下一行?

scan之所以复杂,很大程度上是因为scan可以设置的条件非常之多,下面所示代码为比较常规的一些设置:

Scan scan = new Scan();
scan.withStartRow(startRow) //设置检索起始row
        .withStopRow(stopRow) //设置检索结束row
        .setFamilyMap(Map<byte[], Set<byte[]> familyMap>) //设置检索的列族和对应列族下的列集合
        .setTimeRange(minStamp, maxStamp) // 设置检索TimeRange
        .setMaxVersions(maxVersions) //设置检索的最大版本号
        .setFilter(filter) //设置检索过滤器
        …

在整个Scan流程的第6步,将堆顶kv元素出堆进行检查,实际上主要检查两个方面,其一是非用户条件检查,比如kv是否已经过期(列族设置TTL)、kv是否已经被删除,这些检查和用户设置查询条件没有任何关系;其二就是检查该kv是否满足用户设置的这些查询条件,代码逻辑还是比较清晰的,在此不再赘述。核心代码主要参考ScanQueryMatcher.match(cell)方法。

相比堆顶元素检查流程,笔者更想探讨堆顶元素kv检查之后的返回值-MatchCode,这个Code可不简单,它会告诉scanner是继续seek下一个cell,还是直接跳过部分cell直接seek到下一列(对应INCLUDE_AND_SEEK_NEXT_COL或SEEK_NEXT_COL),抑或是直接seek到下一行(对应INCLUDE_AND_SEEK_NEXT_ROW或SEEK_NEXT_ROW)。还是举一个简单的例子:

58

上图是待查表,含有一个列族cf,列族下有四个列[c1, c2, c3, c4],列族设置MaxVersions为2,即允许最多存在2个版本。现在简单构造一个查询语句如下:

Scan scan = new Scan(r1, r4); // 表示检索范围为[r1, r4]
scan.setFamilyMap(Map<cf, Set<c1,c2>>) //仅检索列族cf下的c1列和c2列
        .setMaxVersions(1) //设置检索的最大版本号为1

下面分别模拟直接跳过部分纪录seek到下一列(INCLUDE_AND_SEEK_NEXT_COL)的场景以及跳过部分列直接seek到下一行(INCLUDE_AND_SEEK_NEXT_ROW)的场景:

(1)假设当前检索r1行,堆顶元素为cf:c1下的kv1(版本为v1),按照设置条件中检索的最大版本号为1,其他条件都满足的情况下就可以直接跳过kv2直接seek到下一列-c2列。这种场景下就会返回INCLUDE_AND_SEEK_NEXT_COL。

(2)假设当前检索r1行,堆顶元素为cf:c2下的kv3(仅有1个版本),满足设置的版本条件,系统检测到c2是检索的最后一列之后(c3、c4并不需要检索),就会返回指示-略过c3、c4直接seek到下一行。这种场景下就会返回INCLUDE_AND_SEEK_NEXT_ROW。

至此,笔者针对scan流程中的第6步进行了比较详细的解读,对认为比较重要的点进行了简单演示。其实还是有很多内容,但大多都大同小异,原理类似。有兴趣读HBase源码的同学可以参考这里的解读,相信会有所帮助。


5. 每次seek(key)命令是不是都需要所有scanner真正seek到指定key?延迟seek是如何优化读性能的?

这是本文探讨的最后一个话题,严格来说,这个话题并不涉及scan的流程,而仅仅是对scan的一项优化。但是个人认为理解这项优化对scan的流程理解有着相当重要的意义,同时也是阅读HBase-Scan模块源码必须要迈过的一道坎。

先回到scan的流程,根据之前的理解,如果堆顶元素出堆检查之后指示scanner需要跳过部分cell直接seek到下一列或者下一行,此时所有scanner都需要按照指示执行seek命令定位指定位置,这本身没有毛病。然而这可能并不高效,试想这么一种场景:

(1)当前有3个StoreFile文件,因此对应3个StoreFileScanner,现在接到指示需要seek 到(rowk, cf:c1)位置,刚好这三个文件中都存在这样的KV,差别在于时间戳不同

(2)于是这3个Scanner很顺从地在文件中找到指定位置,然后等待最小KV出堆接受检查

(3)最小KV出堆接受检查之后满足用户条件,而且用户只需要检索最新版本。因此检查之后告诉所有scanner直接seek到下一行。

有没有发现一些小小的问题?没错,3个scanner只有1个scanner做了’有用功’,其他两个scanner都做了’无用seek’。这很显然一定程度上会影响scan性能。

HBase提出了一个很巧妙的应对方案-延迟seek,就是3个scanner接到seek指示的时候,实际上并没有真正去做,而只是将scanner的指针指向指定位置。那童鞋就会问了,那什么时候真正去seek呢?只需要在堆顶元素弹出来的时候真正去执行就可以。这样,就可以有效避免大量’无用seek’。

好了,本文核心内容就基本介绍完了,接下来扯点闲篇。任何存储系统的核心模块无非读写模块,但不同类型的数据库侧重不同。MySQL类系统(Oracle、SQLServer等)侧重于写,写就是它的灵魂!为了实现事务原子性,数据更新之前要先写undo log,为了实现数据持久性,又引入redo log,为了实现事务隔离性,还需要实现各种锁,还有类似double write等一系列机制…… ,个人认为,搞懂了数据更新写入流程基本就搞懂了MySQL存储引擎。与MySQL相对,HBase类系统(RocksDB、Kudu )更侧重读,读是它的灵魂!HBase将所有更新操作、删除操作都简单的当作写入操作来处理,对于更新删除来说确实简单了,但却给数据读取带来了极大的负担,数据读取的时候需要额外过滤删除数据、处理多版本数据,除此之外,LSM所特有的多文件存储、BloomFilter过滤特性支持等等无不增加了数据读取的难度。个人认为,只有搞懂了数据读取才可能真正理解HBase内核。

范欣欣

就职于网易杭州研究院后台技术中心数据库技术组,从事HBase开发、运维,对HBase相关技术有浓厚的兴趣。邮箱:libisthanks@gmail.com

在 “HBase原理-迟到的‘数据读取流程’部分细节” 上有 11 条评论

  1. 其实我一直有个疑问,hdfs io块大小默认是128M,但是hbase一个block默认64k,也就是说hbase可以做到一次物理io只读取64k,而不是底层hdfs一次io的128M,感觉有点矛盾;找了一下代码最后好像调用的是HFileBlock.AbstractFSReader.readAtOffset这个方法调用IOUtils类读取的,难道说hdfs最小io可以低于一个块的大小?范神可以指点一下吗?谢谢~

    1. hdfs最小io单元应该是默认64M(记得是),hbase一次io是64k,到hdfs层面可以读一次64M出来,然后在64M的block里面取64k就可以了。还是一次IO操作。

      1. 64M好像是hadoop1了。如果真的是这样的话,每次get操作都很有可能要读取一整个hdfs数据块(假设都没有缓存命中率),这样对性能没有影响吗?

          1. 谢谢范神啦,虽然我也感觉后台实现八成跟传统关系型数据库类似,要读取一整个数据块;但是为了读一个只有几k的cell,底层的hdfs要先读取几百兆的数据块,然后再加载那几k进来,始终感觉有些费解。

  2. 2. 数据更新操作先将数据写入Memstore,再落盘。落盘之后需不需要更新Blockcache中对应的kv?如果不更新,会不会读到脏数据?
    如果理清楚了第一个问题,相信很容易得出这个答案:不需要更新Blockcache中对应的kv,而且不会读到脏数据。数据写入Memstore落盘会形成新的文件,和Blockcache里面的数据是相互独立的,以多版本的方式存在。

    ================================================
    求教: 假设落盘的数据比blockcache的新, 那么下一次get命中blockcache, 还会再去扫描hfile再合并吗? 如果会那么blockcache意义何在? 如果不会那么是不是会有脏数据?

    1. 1. blockcache意义:如果最新的数据在blockcache中(或者用户想要获取多个版本数据,其中某个版本数据在blockcache中),get就会直接在blockcache中获取,不会到文件中查找。如果最新的数据不在blockcache中,而且用户只获取最新版本,get操作首先会在blockcache中查找,找不到就去文件中查找。
      2. 不会存在脏数据

      1. 如果只在blockcache里面找,怎么能确定找到的是最新版本而不是老版本呢?难道rs还在内存里面维护了每个column的版本信息吗?

        1. 按照我的理解,只要用户需要最新版本,rs一定会搜索所有可能存在这条数据的memstore和hfiles并做一次多路归并。在搜索hfile时可能对应的一些blocks已经在blockcache中,此时免去io操作。也就是说blockcache无法避免每次的多路扫描归并,只能减免过程中的一些io操作。
          我没看过源码,以上都是我yy的,请博主指教。

发表评论

电子邮件地址不会被公开。 必填项已用*标注