【原创】HPB之go leveldb数据库的Get操作源码


#1

前文介绍了Put操作的流程,基本原理就是将要写入的数据先追加到log文件中,然后写入内存,就算Put完成。

leveldb是key-value类型的数据库,因此要进行某个value的查询,必须知道key才行,如此也就限制了leveldb无法进行条件查询,分区,分组,排序等操作。本文来看看仅有的Get操作是如何做的。先看Get函数入口

func (db *DB) Get(key []byte, ro *opt.ReadOptions) (value []byte, err error) {

​    err = db.ok()

​    if err != nil {

​        return

​    }

​    se := db.acquireSnapshot()

​    defer db.releaseSnapshot(se)

​    return db.get(nil, nil, key, se.seq, ro)

}

进入函数,先判断数据库状态是否ok。然后获取数据库快照,然后就是db.get了。因为数据库后台会不断的检查并合并表,导致数据库文件的删除和增加,因此需要进行快照。直接进入db.get函数

func (db *DB) get(auxm *memdb.DB, auxt tFiles, key []byte, seq uint64, ro *opt.ReadOptions) (value []byte, err error) {

​    ikey := makeInternalKey(nil, key, seq, keyTypeSeek)

	 .........

​    em, fm := db.getMems()

​    for _, m := range [...]*memDB{em, fm} {
  

​        defer m.decref()

​        if ok, mv, me := memGet(m.DB, ikey, db.s.icmp); ok {

​            return append([]byte{}, mv...), me

​        }

​    }

​    v := db.s.version()

​    value, cSched, err := v.get(auxt, ikey, ro, false)

​    v.release()


​    return

}

db.get函数主要是两部分,由于数据的存储分成内存存储(由put操作放入的)和磁盘存储(由compaction操作从内存中放入磁盘的),所以查询也是先查内存,再查磁盘。leveldb既然是分层的数据库,那最新的数据自然是在最上层,即memdb,然后是level0,level1… 如果内存中查不到,那就需要到磁盘上去查了,v.get就是在磁盘上查询的处理。

func (v *version) get(aux tFiles, ikey internalKey, ro *opt.ReadOptions, noValue bool) (value []byte, tcomp bool, err error) {

​    ukey := ikey.ukey()

​    var (

​        tset  *tSet

​        tseek bool

​        // Level-0.

​        zfound bool

​        zseq   uint64

​        zkt    keyType

​        zval   []byte

​    )

​    err = ErrNotFound

	//walkoverlapping是用来定位ikey位于哪个文件中的
​    v.walkOverlapping(aux, ikey, func(level int, t *tFile) bool {

​        if level >= 0 && !tseek {

​            if tset == nil {

​                tset = &tSet{level, t}

​            } else {

​                tseek = true

​            }

​        }

​        var (

​            fikey, fval []byte

​            ferr        error

​        )

​        if noValue {

​            fikey, ferr = v.s.tops.findKey(t, ikey, ro)

​        } else {
			 //从上述调用函数可知,novalue为false,因此使用find进行查找
​            fikey, fval, ferr = v.s.tops.find(t, ikey, ro)

​        }

​        switch ferr {

​        case nil:

​        case ErrNotFound:

​            return true

​        default:

​            err = ferr

​            return false

​        }
	     //这里是为了跟找到的文件中的key进行比较,确认最新的数据
​        if fukey, fseq, fkt, fkerr := parseInternalKey(fikey); fkerr == nil {

​            if v.s.icmp.uCompare(ukey, fukey) == 0 {

​                // Level <= 0 may overlaps each-other.

​                if level <= 0 {

​                    if fseq >= zseq {

​                        zfound = true

​                        zseq = fseq

​                        zkt = fkt

​                        zval = fval

​                    }

​                } else {

​                    switch fkt {

​                    case keyTypeVal:

​                        value = fval

​                        err = nil

​                    case keyTypeDel:

​                    default:

​                        panic("leveldb: invalid internalKey type")

​                    }

​                    return false

​                }

​            }

​        } else {

​            err = fkerr

​            return false

​        }

​        return true

​    }, func(level int) bool {

​        if zfound {

​            switch zkt {

​            case keyTypeVal:

​                value = zval

​                err = nil

​            case keyTypeDel:

​            default:

​                panic("leveldb: invalid internalKey type")

​            }

​            return false

​        }

​        return true

​    })

​    if tseek && tset.table.consumeSeek() <= 0 {

​        tcomp = atomic.CompareAndSwapPointer(&v.cSeek, nil, unsafe.Pointer(tset))

​    }

​    return

}

行数是多了点,但逻辑也很简单,具体来讲就是3步:1、先根据要查找的ikey,定位到可能存在ikey的文件,2、读取文件找到ikey,ivalue,3、如果当前查找的文件在level0,根据fseq找出最新的数据。 至此,查找完成。

稍微多解释下:

1、如何定位到可能存在ikey的文件?答案在walkOverlapping函数中,从之前的分享中,我们知道leveldb的文件都是有序存储的,每个文件的minkey和maxkey都会存起来,因此根据ikey与minkey,maxkey的比较,就能确定可能的文件。

2、读取文件一定能找到ikey,ivalue吗? 答案是不一定,因此每个文件的minkey,maxkey是不一样的,在level0层的文件的key的范围可能存在重复,因此可能找不到ikey,也可能会找到多个ikey.

3、为什么level0的数据需要判断最新,其他层的数据就不需要判断? 因为level0层的key范围可能存在重叠,而level1层及之后的层,每一层之间的文件的key范围不会发生重叠,这个就归功于compaction了,后续介绍compaction的时候再讲。

至此,Get操作结束。