读操作

读操作作为写操作的逆过程，充分理解了写操作，将会帮助理解读操作。

下图为在一个sstable中查找某个数据项的流程图：

读操作 - 图1

大致流程为：

  • 首先判断“文件句柄”cache中是否有指定sstable文件的文件句柄，若存在，则直接使用cache中的句柄；否则打开该sstable文件，按规则读取该文件的元数据，将新打开的句柄存储至cache中；
  • 利用sstable中的indexblock进行快速的数据项位置定位，得到该数据项有可能存在的两个datablock；
  • 利用index block中的索引信息，首先打开第一个可能的data block；
  • 利用filter block中的过滤信息，判断指定的数据项是否存在于该datablock中，若存在，则创建一个迭代器对datablock中的数据进行迭代遍历，寻找数据项；若不存在，则结束该datablock的查找；
  • 若在第一个datablock中找到了目标数据，则返回结果；若未查找成功，则打开第二个datablock，重复步骤4；
  • 若在第二个datablock中找到了目标数据，则返回结果；若未查找成功，则返回Not Found错误信息；缓存

在leveldb中，使用cache来缓存两类数据：

  • sstable文件句柄及其元数据；
  • data block中的数据；

因此在打开文件之前，首先判断能够在cache中命中sstable的文件句柄，避免重复读取的开销。

元数据读取

读操作 - 图2

由于sstable复杂的文件组织格式，因此在打开文件后，需要读取必要的元数据，才能访问sstable中的数据。

元数据读取的过程可以分为以下几个步骤：

  • 读取文件的最后48字节的利用，即Footer数据；
  • 读取Footer数据中维护的(1) Meta Index Block(2) IndexBlock两个部分的索引信息并记录，以提高整体的查询效率；
  • 利用meta index block的索引信息读取该部分的内容；
  • 遍历meta index block，查看是否存在“有用”的filterblock的索引信息，若有，则记录该索引信息；若没有，则表示当前sstable中不存在任何过滤信息来提高查询效率；数据项的快速定位

sstable中存在多个datablock，倘若依次进行“遍历”显然是不可取的。但是由于一个sstable中所有的数据项都是按序排列的，因此可以利用有序性已经indexblock中维护的索引信息快速定位目标数据项可能存在的data block。

一个index block的文件结构示意图如下：

读操作 - 图3

index block是由一系列的键值对组成，每一个键值对表示一个datablock的索引信息。

键值对的key为该data block中数据项key的最大值，value为该datablock的索引信息（offset, length）。

因此若需要查找目标数据项，仅仅需要依次比较indexblock中的这些索引信息，倘若目标数据项的key大于某个datablock中最大的key值，则该datablock中必然不存在目标数据项。故通过这个步骤的优化，可以直接确定目标数据项落在哪个datablock的范围区间内。

注解

值得注意的是，与data block一样，indexblock中的索引信息同样也进行了key值截取，即第二个索引信息的key并不是存储完整的key，而是存储与前一个索引信息的key不共享的部分，区别在于datablock中这种范围的划分粒度为16，而index block中为2 。

也就是说，indexblock连续两条索引信息会被作为一个最小的“比较单元“，在查找的过程中，若第一个索引信息的key小于目标数据项的key，则紧接着会比较第三条索引信息的key。

这就导致最终目标数据项的范围区间为某”两个“data block。

读操作 - 图4

过滤data block

若sstable存有每一个data block的过滤数据，则可以利用这些过滤数据对datablock中的内容进行判断，“确定”目标数据是否存在于data block中。

过滤的原理为：

  • 若过滤数据显示目标数据不存在于datablock中，则目标数据一定不存在于data block中；
  • 若过滤数据显示目标数据存在于datablock中，则目标数据可能存在于data block中；

具体的原理可能参见《布隆过滤器》。

因此利用过滤数据可以过滤掉部分data block，避免发生无谓的查找。

查找data block

读操作 - 图5

在data block中查找目标数据项是一个简单的迭代遍历过程。虽然datablock中所有数据项都是按序排序的，但是作者并没有采用“二分查找”来提高查找的效率，而是使用了更大的查找单元进行快速定位。

与index block的查找类似，data block中，以16条记录为一个查找单元，若entry1的key小于目标数据项的key，则下一条比较的是entry 17。

因此查找的过程中，利用更大的查找单元快速定位目标数据项可能存在于哪个区间内，之后依次比较判断其是否存在与datablock中。

可以看到，sstable很多文件格式设计（例如restart point， indexblock，filter block，maxkey）在查找的过程中，都极大地提升了整体的查找效率。