RocksDB范围扫描时如何实现字节数组byte[]逐次加1

范围扫描的基础用法 #

RocksDB支持基于Key的范围扫描能力，核心是通过字节数组定位扫描的起止边界：

• 若Key由2个Long类型数据拼接组成（总长度16字节），可通过toBytes(Long.MinValue, Long.MinValue)初始化长度为16的起始字节数组byte[16]
• 用同样的规则设置结束键endKey为toBytes(Long.MinValue, Long.MaxValue)，即可实现部分前缀匹配的扫描：仅遍历Key前64位固定为Long.MinValue、后64位覆盖Long.MinValue到Long.MaxValue区间的所有键。

对应的扫描迭代器示例代码如下：

val iter = newRocksIterator()

new Iterator[Entry] {
  override def hasNext: Boolean = {
    if (iter.isValid) {
      compareKeys(iter.key(), endKey) <= 0
    } else {
      false
    }
  }

  override def next(): Entry = {
    val value = Entry(iter.key, iter.value())
    iter.next()
    value
  }
}

iter.next()的实际工作逻辑 #

很多人会误以为iter.next()的本质是把当前16字节的Key数组逐次加1，直到命中结束键，甚至觉得它和整数加法一样按位递增生成下一个Key，这个理解是完全错误的。

• 你看到源码里这个逻辑跳转到native实现，是因为RocksDB本身是C++实现的存储引擎，Java/Scala端的接口只是JNI包装。iter.next()根本不会在内存里对当前Key做字节数组加法计算下一个Key，它的本质是移动底层LSM树的遍历指针，顺着引擎内部的有序存储结构找下一个Key：优先遍历当前内存MemTable中比当前Key大的最小Key，MemTable遍历完成后依次遍历Immutable MemTable、各层SSTable，靠SSTable的块索引、布隆过滤器快速定位下一个符合字典序的Key。
• 之所以看起来像是Key在逐次递增，是因为RocksDB中所有Key都是严格按照字节字典序有序存储的，迭代器顺着存储结构顺序移动，自然就呈现出Key从小到大逐次递进的效果。

补充说明：如果纯从算法角度实现字节数组按字典序加1，逻辑确实和大端表示的整数按位进位类似：从数组最后一个字节开始加1，如果当前字节加1后溢出为0，就向前一个字节进位继续加1，直到没有进位或者整个数组溢出为止。但这个逻辑和RocksDB迭代器的移动没有关系，不要混淆。

内容的提问来源于stack exchange，提问作者user_1357