入口

org.apache.hadoop.hbase.io.hfile.HFileReaderImpl.HFileScannerImpl#seekTo(org.apache.hadoop.hbase.Cell, boolean) ：

public int seekTo(Cell key, boolean rewind) throws IOException {
  HFileBlockIndex.BlockIndexReader indexReader = reader.getDataBlockIndexReader();
  BlockWithScanInfo blockWithScanInfo = indexReader.loadDataBlockWithScanInfo(key, curBlock,
                                                                              cacheBlocks, pread, isCompaction, getEffectiveDataBlockEncoding(), reader);
  if (blockWithScanInfo == null || blockWithScanInfo.getHFileBlock() == null) {
    // This happens if the key e.g. falls before the beginning of the file.
    return -1;
  }
  return loadBlockAndSeekToKey(blockWithScanInfo.getHFileBlock(),
                               blockWithScanInfo.getNextIndexedKey(), rewind, key, false);
}

大邏輯分為兩步走：

1. 檢索 index block 定位到 data block 的位置；
2. 在 data block 中根據 key進行遊標定位。

檢索 index block

1. 獲取 root index block（該 block 在 load-on-open 階段就已經被加載並解析完畢）；
2. 通過二分查找在 root index block 種定位 entry，這裏 key 的對比邏輯會走 CellComparatorImpl#compare(Cell, Cell)，右邊是 KeyValue$KeyOnlyKeyValue 如果發現比最小的 key 小，則直接返回 -1（標識遊標停在文件初）；

3. 這裏會開啓一個循環，目的是為了定位到具體的 data block。根據 entry 取下一個要讀的 block，從 entry 取出要讀的 block 的 offset 和 size，以讀取下一個 block，根據 lookupLevel 和 searchTreeLevel 判斷要讀的 block 的類型：

   1. searchTreeLevel 是索引樹的高度，為 1 説明只有 root index block，為 2 説明 root index block 指向 leaf index block，大於 2 則中間有 n-2 層 intermediate-level block，以此類推；
   2. lookupLevel 是當前讀到的 level，如果小於 searchTreeLevel 説明還要讀 index block，否則就要讀 data block；

4. 查看讀出來的 block 類型，如果是 data block 則跳出循環，否則：

   1. 查看該 key 在該 index block 中的位置，這裏也使用二分，右邊的實現是 BytebufferKeyOnlyKeyValue：HFileBlockIndex#locateNonRootIndexEntry -> HFileBlockIndex#binarySearchNonRootIndex -> PrivateCellUtil#compareKeyIgnoresMvcc
   2. 如果小於 0（即小於 index block 記錄的最小值），則拋出異常：The key xxx is before the first key of the non-root index block，因為在上一步已經確定該 key 在該 hfile 的範圍裏；
   3. 定位到具體的 entry（這裏會修改 index block 裏 buffer 的 position），用於檢索下一層 block；
   4. 回到上一層的第三步，直到找到 data block。

檢索 data block

調用 HFileReaderImpl.HFileScannerImpl#loadBlockAndSeekToKey -> HFileReaderImpl.HFileScannerImpl#blockSeek，遍歷 data block 中的數據（BytebufferKeyOnlyKeyValue）和指定 key 對比：

1. blockSeek 有個參數 seekBefore（默認為 false），用於控制當找到匹配上的 data entry 時，是否需要回退一個單位，如果回退，則返回 1，否則返回 0（0 表示精準匹配，遊標停在匹配的位置）；
2. 如果第一次匹配就發現 cmp <0（即比 data block 的第一個 data entry 都要小），則返回 -2；
3. 不斷往下匹配，直至找到第一個大於指定 key 的 data entry（cmp<0），將該 block 的 buffer position 回滾一個單位，返回 1（表示遊標停在最後一個小於 key 的 entry 上，下一個 entry 就比 key 大了）

Seek 的使用場景

Seek 主要應用於兩類場景：

1. 點查：給定 key，查找符合條件的該 key 最新版本的數據。考慮到 HBase 的數據會包含 timestamp，需要考慮較為複雜的，同 key 不同 timestamp 的情況：

   • 點查的 key 小於文件第一條數據：底層 scanner seek 返回 -1/-2。此時調用 seekTo 使 scanner 遊標停在文件初始位置；
   • 底層 scanner 的 seek 返回 0。精準匹配，直接讀取數據即可。
   • 底層 scanner seek 返回 1。由於 scanner 會回退一個數據單位，可直接讀取當前數據比對 key。
2. 區間掃描：給定 key，掃描大於等於該 key 的所有數據。該場景和點查的邏輯有一點不同，即 scanner seek 返回 1 的時候，需要往下推進一個數據單位，因為 HBase 做 seek 操作時都會有一次回退。