从零实现LevelDB 3. MemTable实现

#C++##golang##项目##基础架构工程师##数据库##软件开发2024笔面经##牛客创作赏金赛#

在本节，我们将会了解并实现：

1. LevelDB的内部键InternalKey和LookupKey及对应的比较器
2. Memtable

本节的代码包括InternalKey实现 、InternalKey和UserKey比较器实现 、memtable实现。

InternalKey

介绍

当用户调用db->Put(a, b)时，LevelDB会对用户传入的Key(下称UserKey)进行内部封装处理，封装后的Key称为InternalKey。

InternalKey由UserKey、SequenceNumber(序列号)和ValueType(类型)组成,其组成如下图。

可以看到,InternalKey在UserKey的基础上,增加了两部分:7byte的序列号和1byte的ValueType。

其中，ValueType是为了区分键的操作类型，即插入或删除。

在第一节介绍过，LevelDB中的删除也是"插入"。当删除时，会将ValueType置为kTypeDeletion，代表此时的键值是要删除,而如果ValueType是kTypeValue，则说明键值是新插入。

const (
	TypeDeletion InternalKeyKind = iota
	TypeValue
	TypeError
	TypeValueForSeek = TypeValue
)

在这里，我们暂时忽略TypeError和TypeValueForSeek类型。

LevelDB有一个全局唯一的序列号，每次写入时该序列号都会递增，而SequenceNumber就是这个序列号，每个InternalKey都包含不同的SequenceNumber，且该序列号单调递增。

所以在LevelDB中，每一个InternalKey都是不一样的，因为哪怕UserKey相同，其SequenceNumber也是不同的。

SequenceNumber越大，表示对应的键越新。在UserKey相同的情况下，新的键会覆盖旧的键。

InternalKey实现

func MakeInternalKey(ukey []byte, ktype InternalKeyKind, seqNum uint64) InternalKey {
	var buf = bytes.NewBuffer([]byte{})
	binary.Write(buf, binary.LittleEndian, ukey)
	binary.Write(buf, binary.LittleEndian, (seqNum<<8)|uint64(ktype))
	return buf.Bytes()
}

func (ikey InternalKey) UserKey() []byte {
	if len(ikey) < 8 {
		return []byte{}
	}
	return ikey[:len(ikey)-8]
}

func (ikey InternalKey) Kind() InternalKeyKind {
	if len(ikey) < 8 {
		return TypeError
	}
	return InternalKeyKind(ikey[len(ikey)-8])
}

func (ikey InternalKey) SeqNumber() uint64 {
	if len(ikey) < 8 {
		return 0
	}
	i := len(ikey) - 7
	seqNum := uint64(ikey[i+0])
	seqNum |= uint64(ikey[i+1]) << 8
	seqNum |= uint64(ikey[i+2]) << 16
	seqNum |= uint64(ikey[i+3]) << 24
	seqNum |= uint64(ikey[i+4]) << 32
	seqNum |= uint64(ikey[i+5]) << 40
	seqNum |= uint64(ikey[i+6]) << 48
	return seqNum
}

InternalKey比较器

在我们了解了InternalKey的格式与组成后，那么在本节，我们将了解如何比较两个InternalKey的大小，其规则比较简单：

如果UserKey不同，那么直接比较UserKey即可；

如果UserKey相同，那么我们则要比较SequenceNumber，序列号越大，说明是新插入的数据，则比另外的InternalKey更"小"，要排在更前面(排在前面的数据优先级大于后面的数据)。

对于InternalKey的比较器实现如下。

func (InternalKeyComparer) Compare(a, b []byte) int {
	aKey := ikey.InternalKey(a)
	bKey := ikey.InternalKey(b)
	r := UserKeyComparator.Compare(aKey.UserKey(), bKey.UserKey())
	if r == 0 {
		anum := aKey.SeqNumber()
		bnum := bKey.SeqNumber()
		if anum > bnum {
			r = -1
		} else if anum < bnum {
			r = 1
		}
	}
	return r
}

在Compare中，首先先将传入的参数转化成InternalKey类型，然后先调用UserKey的比较器进行比较，如果相等，再通过序列号进行比较。

LookupKey

LookupKey是为了查找而生的，它在InternalKey的基础上增加了InternalKey的长度。

type LookupKey []byte

// InternalKey_Length(uint32) | InternalKey
func MakeLookupKey(ukey []byte, num uint64) LookupKey {
	ikey := MakeInternalKey(ukey, TypeValueForSeek, num)
	ikey_len := uint32(len(ikey))
	var buf = bytes.NewBuffer([]byte{})
	binary.Write(buf, binary.LittleEndian, ikey_len)
	binary.Write(buf, binary.LittleEndian, ikey)
	return LookupKey(buf.Bytes())
}

func (lkey LookupKey) MemtableKey() []byte {
	return lkey
}

func (lkey LookupKey) InternalKey() InternalKey {
	return InternalKey(lkey[4:])
}

func (lkey LookupKey) UserKey() []byte {
	return lkey[4 : len(lkey)-8]
}

从MakeLookupKey的实现我们知道，它首先构造一个用于寻找的InternalKey(TypeValueForSeek)，然后将这个InternalKey的长度和InternalKey写人缓存后返回。

Memtable实现

Memtable是基于跳表实现的，其定义如下。

type Memtable struct {
	table   *skiplist.Skiplist
	memSize int
}

其中，memSize代表Memtable的大小。

此外，如果想为了后续的扩展，可以将table的类型改为有序数据结构接口，而不局限在*skiplist.Skiplist中，这样，后续如果想更换其他有序内存数据结构，也不用改动原有代码。

基本操作

插入

前文已经提到，当用户传入UserKey时，会将其封装成InternalKey，所以当用户要插入(UserKey, UserValue)时，在内部就变成了(InternalKey, UserValue)了。

在字节序列中，为了能获取InternalKey和UserValue的边界，我们还要在其前面加上各自的长度。

所以，最终的存储格式是InternalKey的长度 + InternalKey + UserValue的长度 + UserValue，如makeMemtableEntry函数所示。

func makeMemtableEntry(seq uint64, ktype ikey.InternalKeyKind, ukey, uvalue []byte) []byte {
	var buf = bytes.NewBuffer([]byte{})
	ikey := ikey.MakeInternalKey(ukey, ktype, seq)
	binary.Write(buf, binary.LittleEndian, uint32(len(ikey)))
	binary.Write(buf, binary.LittleEndian, ikey)
	binary.Write(buf, binary.LittleEndian, uint32(len(uvalue)))
	binary.Write(buf, binary.LittleEndian, uvalue)
	return buf.Bytes()
}

有了makeMemtableEntry这个函数，memTable的Add实现就非常简单，只要直接Put并更新table的大小即可。

func (memTable *Memtable) Add(seq uint64, ktype ikey.InternalKeyKind, ukey, uvalue []byte) {
	memEntry := util.MakeMemtableEntry(seq, ktype, ukey, uvalue)
	memTable.memSize += len(memEntry)
	memTable.table.Put(memEntry)
}

再次强调一次，删除也是属于插入，也是调用Add接口，因为删除只是将ktype的类型改为删除类型。

查找

在查找时，我们传入的不是ukey，而是lookupkey。

在上文有提到，lookupkey是由序列号和userkey组成而来。序列号由快照传入，当未传入快照时，则设置为LevelDB中最大的序号。

在跳表中，相同的UserKey，序号越大反而越小(越新)，

因此通过Seek后，迭代器会找到第一个大于等于lookupkey的值，如果该值的userkey与lookupkey的userkey相同，

就是此时DB中的最新记录，否则，DB中不存在该userkey。

func (memTable *Memtable) Get(lkey ikey.LookupKey) ([]byte, error) {
	ukey := lkey.UserKey()
	it := memTable.table.NewIterator()
	// 找到第一个>=lkey的值
	it.Seek(lkey)
	if it.Valid() {
		memEntry := it.Key()
		key_length := binary.LittleEndian.Uint32(memEntry)
		internal_key := ikey.InternalKey(memEntry[4 : 4+key_length])
		if comparator.UserKeyComparator.Compare(ukey, internal_key.UserKey()) == 0 {
			if internal_key.Kind() == ikey.TypeValue {
				value_length := binary.LittleEndian.Uint32(memEntry[4+key_length:])
				value := memEntry[8+key_length : value_length+8+key_length]
				return value, nil
			} else if internal_key.Kind() == ikey.TypeDeletion {
				return nil, errors.ErrDeletion
			} else {
				return nil, errors.ErrUndefined
			}
		}
	}
	return nil, errors.ErrNotFound
}

支持迭代器

总体来说，memTable的迭代器都是基于跳表的迭代器实现，其中比较有变化的就是Key的实现。

因此用户传入的UserKey已经被封装成InternalKey，所以，Iterator中，Key返回的是InternalKey。

// 返回InternalKey
func (it *Iterator) Key() []byte {
	memEntry := it.listIter.Key()
	key_length := util.GetUint32(memEntry)
	internal_key := ikey.InternalKey(memEntry[4 : 4+key_length])
	return []byte(internal_key)
}