作者：王东阳
leveldb 中min_max搜寻剖析
前言
leveldb是一个写性能非常优良的存储引擎，是典型的LSM树(Log Structured-Merge Tree)实现。LSM树的核心思想是将随机写转化为间断写，从而晋升写操作的吞吐能力，整体架构如下：
尽管在内存中，所有的数据都是按序排列的，然而当多个memetable数据长久化到磁盘后，对应的不同的sstable之间是存在交加的，在读操作时，须要对所有的sstable文件进行遍历，重大影响了读取效率。因而leveldb后盾会“定期“整合这些sstable文件，该过程也称为compaction。随着compaction的进行，sstable文件在逻辑上被分成若干层，由内存数据间接dump进去的文件称为level0层文件，前期整合而成的文件为level i层文件，这也是leveldb这个名字的由来。 https://www.bookstack.cn/read...
在leveldb的压缩过程中, 须要向上层搜寻和相互重叠的sstable进行合并，如下图所示：
下层数据如何疾速的查问下一层中和以后sstable文件重叠的文件列表呢？由上图能够看出每个sstable中都有一个最小值min和最大值max，示意以后文件所蕴含key的最大值和最小值，能够当成一个数据区间，Level0层的key区间相互有重叠，残余其它层中，每一层中的sstable文件，所蕴含的key区间，相互不重叠，所以对它们排序后，无论是最大值还是最小值都是严格递增的。
除了文件压缩，leveldb在执行查问的过程中，也会利用sstable的min,max的属性信息进行疾速查找申请key所在的文件。
本文次要基于leveldb:table.go 和 leveldb_rs:table.rs介绍sstable区间搜寻相干接口代码的实现算法。
tFile
Go
文件的构造如下，次要蕴含文件的形容信息fd，文件中数据的大小size，以及文件中蕴含key的最小，最小值 (imin,imax). 在本文中，咱们只须要关注imin,imax就能够了。
// tFile holds basic information about a table.type tFile struct { fd storage.FileDesc seekLeft int32 size int64 imin, imax internalKey}接下来是tFile中的办法，须要留神的是上面的办法中都有一个参数icmp *iComparer ,咱们能够了解为一个比拟器，用于判断key大小时候应用的。
首先是tFile的after办法，判断给定的key是否在这个文件的前面 ,这个办法咱们能够这么了解，在一个程度数轴上，以后tFile的imin,imax对应数轴上的一个区间，判断给定的key是否在这个区间的前面，也就是判断给定ukey是否比以后文件中的最大值imax要大。
after 办法示意图： │ │ │ │ ukey ────────▼──────────▼─────────▲───────► imin imax │ │对应代码如下
// Returns true if given key is after largest key of this table.func (t *tFile) after(icmp *iComparer, ukey []byte) bool { return ukey != nil && icmp.uCompare(ukey, t.imax.ukey()) > 0}同理，tFile的before办法用来判断给定的ukey是否在在以后文件的后面，也就是判断ukey是否比以后文件中的最小值imin要小。
// Returns true if given key is before smallest key of this table.func (t *tFile) before(icmp *iComparer, ukey []byte) bool { return ukey != nil && icmp.uCompare(ukey, t.imin.ukey()) < 0}overlaps用来判断指定区间[umin,umax]是否和以后文件的区间[imin,imax]有重叠。咱们能够反向来思考什么状况下两个区间不重叠。
- tFile区间的最小值imin大于另外一个区间的最大值umax
- tFile区间的最大值imax小于另外一个区间的最大值umin
overlaps 办法示意图 │ │ │ │ umin umax ────▼───────▼──────────▲──────▲───────► imin imax │ tFile│ │ │ │ │ umin umax │ │ ──────▲──────▲─────▼──────▼──────► │tFile │ imin imax │ │// Returns true if given key range overlaps with this table key range.func (t *tFile) overlaps(icmp *iComparer, umin, umax []byte) bool { return !t.after(icmp, umin) && !t.before(icmp, umax)}Rust
rust代码中tFile的定义如下，跟go中定义十分类似，咱们这里也只关注外面的imin，imax就能够。
#[derive(Clone)]pub struct tFile { fd: storage::FileDesc, seek_left: Arc<atomic::AtomicI32>, size: i64, imin: internalKey, imax: internalKey,}接下来是tFile的办法实现，同样所有的办法都有一个参数icmp: &IComparer<T>，用于比拟key。 首先是after办法，判断指定ukey是否在以后tFile的前面，跟Go版本一样，只须要判断ukey是否比imax大就能够了。
impl tFile { // Returns true if given key is after largest key of this table. pub fn after<T>(&self, icmp: &IComparer<T>, ukey: &[u8]) -> bool where T: Comparer, { return ukey.len() > 0 && icmp.u_compare(ukey, self.imax.ukey()) == Greater; }before办法,判断指定ukey是否在以后tFile的后面，跟Go版本一样，只须要判断ukey是否比imin小就能够了。
// Returns true if given key is before smallest key of this table. pub fn before<T>(&self, icmp: &IComparer<T>, ukey: &[u8]) -> bool where T: Comparer, { return ukey.len() > 0 && icmp.u_compare(ukey, self.imin.ukey()) > Greater; }overlaps用来判断指定区间[umin,umax]是否和以后文件的区间[imin,imax]有重叠，跟GO本版一样，不多说。
// Returns true if given key range overlaps with this table key pub fn overlaps<T>(&self, icmp: &IComparer<T>, umin: &[u8], umax: &[u8]) -> bool where T: Comparer, { return !self.after(icmp, umin) && !self.before(icmp, umax); }tFiles
tFiles用来示意SST中每一层的文件的汇合。
Go
在goleveldb中，tFiles的定义如下
// tFiles hold multiple tFile.type tFiles []*tFile为了反对排序，tFiles须要实现上面的办法
func (tf tFiles) Len() int { return len(tf) }func (tf tFiles) Swap(i, j int) { tf[i], tf[j] = tf[j], tf[i] }func (tf tFiles) nums() string { x := "[ " for i, f := range tf { if i != 0 { x += ", " } x += fmt.Sprint(f.fd.Num) } x += " ]" return x}接下来会讲tFiles外面比拟外围的一些办法。 searchMin，searchMax，searchMinUkey，searchMaxUkey这四个办法调用的前提是tFiles中的所有文件都曾经依照升序排好序，且tFiles中的所有tFile的key区间相互不重叠，所以此时tFiles中的所有文件无论是依照imin,还是依照imax都是枯燥递增的. 举例来说，如果三个相互不重叠的区间 [5,7], [1,4]，[9,11], 无论基于imin还是imax，排序的后果都是
[1,4] [5,7] [9,11]
searchMin
searchMin用于在tFiles中查问imin大于等于ikey的，且imin最小的tFile的索引，也就是在排序后的tFiles中搜寻满足条件的最右边的的tFile。
// Searches smallest index of tables whose its smallest// key is after or equal with given key.func (tf tFiles) searchMin(icmp *iComparer, ikey internalKey) int { return sort.Search(len(tf), func(i int) bool { return icmp.Compare(tf[i].imin, ikey) >= 0 })}举例来说，对于三个区间
[1,4] [5,7] [9,11]
如果ikey等于3， 那么搜寻imin大于等于ikey的最右边的区间就是 [5,7].
searchMax
searchMax 用于在tFiles中查问 imax 大于等于 ikey 的，且 imax 最小的tFile的索引，也就是在排序后的tFiles中搜寻满足条件的最右边的的tFile。
// Searches smallest index of tables whose its largest// key is after or equal with given key.func (tf tFiles) searchMax(icmp *iComparer, ikey internalKey) int { return sort.Search(len(tf), func(i int) bool { return icmp.Compare(tf[i].imax, ikey) >= 0 })}举例来说，对于三个区间
[1,4] [5,7] [9,11]
如果ikey等于3， 那么搜寻imin大于等于ikey的最右边的区间就是 [5,7].
searchMinUkey
searchMinUkey 跟searchMin相似，用于在tFiles中查问 imin.ukey() 大于等于 umin 的，且 imin 最小的tFile的索引，也就是在排序后的tFiles中搜寻满足条件的最右边的的tFile。
// Searches smallest index of tables whose its smallest// key is after the given key.func (tf tFiles) searchMinUkey(icmp *iComparer, umin []byte) int { return sort.Search(len(tf), func(i int) bool { return icmp.ucmp.Compare(tf[i].imin.ukey(), umin) > 0 })}searchMaxUkey
searchMaxUkey 跟searchMax相似，用于在tFiles中查问 imax.ukey() 大于等于 umax 的，且 imax 最小的tFile的索引，也就是在排序后的tFiles中搜寻满足条件的最右边的的tFile。
// Searches smallest index of tables whose its largest// key is after the given key.func (tf tFiles) searchMaxUkey(icmp *iComparer, umax []byte) int { return sort.Search(len(tf), func(i int) bool { return icmp.ucmp.Compare(tf[i].imax.ukey(), umax) > 0 })}overlaps
overlaps 判断区间[umin,umax]是否和tFiles中某个文件的区间有重叠
// Returns true if given key range overlaps with one or more// tables key range. If unsorted is true then binary search will not be used.func (tf tFiles) overlaps(icmp *iComparer, umin, umax []byte, unsorted bool) bool { if unsorted { // Check against all files. for _, t := range tf { if t.overlaps(icmp, umin, umax) { return true } } return false } i := 0 if len(umin) > 0 { // Find the earliest possible internal key for min. i = tf.searchMax(icmp, makeInternalKey(nil, umin, keyMaxSeq, keyTypeSeek)) } if i >= len(tf) { // Beginning of range is after all files, so no overlap. return false } return !tf[i].before(icmp, umax)}这个办法中的第三个参数 unsorted 示意以后tFiles是否是排序的，为什么要进行辨别呢？因为在SST中，Level 0层的不同文件之间key是有重叠的，无奈进行排序。对于这种没有排序的tFiles，就只能应用遍历的办法一个一个的tFile进行比拟，工夫复杂度是O(n)。对于曾经排序的tFiles，咱们能够应用二分法进行搜寻，
- 首先在tFiles中搜寻imax大于等于umin的最右边的区间。
- 如果搜寻不到，就示意[umin,umax]大于所有的tFile，必定不重叠
- 如果搜寻到了，还须要再判断搜寻到的tFile.imin.ukey()是否小于等于umax
- 联合下面步骤1和3， 如果都满足，也就是tFile.imax.ukey() >= umin 且 tFile.imin.ukey() <= umax ，满足两个区间重叠的充沛必要条件
getOverlaps
getOverlaps 用于在tFiles中求和指定区间[umin,umax]有重叠的区间列表，在本文中咱们次要关注如何在排序的tFiles疾速求取的算法
if !overlapped { var begin, end int // Determine the begin index of the overlapped file if umin != nil { index := tf.searchMinUkey(icmp, umin) if index == 0 { begin = 0 } else if bytes.Compare(tf[index-1].imax.ukey(), umin) >= 0 { // The min ukey overlaps with the index-1 file, expand it. begin = index - 1 } else { begin = index } } // Determine the end index of the overlapped file if umax != nil { index := tf.searchMaxUkey(icmp, umax) if index == len(tf) { end = len(tf) } else if bytes.Compare(tf[index].imin.ukey(), umax) <= 0 { // The max ukey overlaps with the index file, expand it. end = index + 1 } else { end = index } } else { end = len(tf) } // Ensure the overlapped file indexes are valid. if begin >= end { return nil } dst = make([]*tFile, end-begin) copy(dst, tf[begin:end]) return dst }这里算法也特地奇妙，通过两次二分法疾速确定与指定区间[umin,umax]重叠的最右边区间以及与指定区间[umin,umax]重叠的最左边区间的下一个区间。
1，调用 tf.searchMinUkey(icmp, umin) 在tFiles中搜寻imin.ukey()大于等于umin的最右边的tFile，
searchMinUkey 办法示意图： ┌─────────┐ ┌───────────┐ ┌───────────┐ │ │ │ │ │ │ │ tFile1 │ │ tFile2 │ │ tFile3 │ │ │ │ │ │ │ ────────┴────▲────┴──▲─┴───────────┴────┴───────────┴────────────────────────► │ │ │ │ umin umax如图， tf.searchMinUkey(icmp, umin) 搜寻失去tFile2，然而tFile1也有可能和[umin,umax]重叠，所以须要额定判断一下
} else if bytes.Compare(tf[index].imin.ukey(), umax) <= 0 { // The max ukey overlaps with the index file, expand it. end = index + 1 } else {2，调用 tf.searchMaxUkey(icmp, umax) 在tFiles中搜寻imax.ukey()大于等于umax的最右边的tFile。这里也有两种状况须要思考，一种是搜寻到的tFile3不和umax重叠，也就是tFile3齐全在[umin,umax]的左边
searchMaxUkey 状况一示意图： ┌────────┐ ┌──────────┐ ┌──────────┐ │ │ │ │ │ │ │ tFil1 │ │ tFile2│ │ tFile3 │ └────────┴────┴──────▲───┴─▲─┴──────────┴────► │ │ │ │ umin umax第二种就是搜寻到的fFile3刚好和[umin,umax]重叠
searchMaxUkey 状况二示意图： ┌────────┐ ┌────────────┐ ┌──────────┐ │ │ │ │ │ │ │ tFil1 │ │ tFile2 │ │ tFile3 │ └────────┴────┴─────────▲──┴─┴─────▲────┴─────────► │ │ │ │ umin umax这种状况也要独自解决下
} else if bytes.Compare(tf[index].imin.ukey(), umax) <= 0 { // The max ukey overlaps with the index file, expand it. end = index + 13，最终基于1，2步骤的两个索引begin和end，取两头的局部[begin,end)就是要求的后果。这个算法另外一个奇妙的中央就在于[begin,end) 是一个左闭右开区间，所以如果begin==end的话，就能够示意找不到重叠的区间了。
总结
leveldb中通过在sstable中记录min、max的信息，能够在合并sstable时防止读取整个sstable来判断是否产生重叠。通过min_max索引，算法能够更高效地实现二分查找。这种min_max索引形式在数据库我的项目中被广泛应用，晋升查问效率。
同时，本文介绍了min_max索引在go和rust两种语言中的不同实现，来帮忙读者从代码层面理解min_max索引的不同实现计划。