0%

LevelDB源码解析(三)- MemTable解析

前言

在LevelDB中,MemTable其实就是在内存中的一个跳表。

1
private final ConcurrentSkipListMap<InternalKey, Slice> table;

稍等,为什么table的Key不是String,而是InternalKey

InternalKey

我们看看InternalKey的定义

1
2
3
4
5
6
public class InternalKey
{
private final Slice userKey;
private final long sequenceNumber;
private final ValueType valueType;
}

里面包含三个字段,分别是

  • userKey,就是我们用户增删的key
  • seqNumber是每一次操作的时候,由LevelDB分配的
  • ValueType分为两种,分别是删除和新增。

我们以这个为例

1
2
3
db.put("foo", "v1"); //1
db.put("foo", "v2"); //2
db.delete("foo"); //3
  1. userKey=foo, seqNum = 1, valueType = VALUE
  2. userKey=foo, seqNum = 2, valueType = VALUE
  3. userKey=foo, seqNum = 3, valueType = DELETE

这个时候,我们抛出一个问题,第2条put执行完之后,在MemTable中还有没有internelKey1?

其实这个问题取决于compare方法。

comparator

新建这个跳表的时候,传入的comparatorInternalKeyComparator

1
2
3
4
5
6
7
8
9
10
InternalKeyComparator#compare
@Override
public int compare(InternalKey left, InternalKey right)
{
int result = userComparator.compare(left.getUserKey(), right.getUserKey()); //1
if (result != 0) {
return result;
}
return Long.compare(right.getSequenceNumber(), left.getSequenceNumber()); //2
}
  1. 这里的userComparatorBytewiseComparator,而BytewiseComparator就是简单的比较userKey了。我们三次操作的userKey都是foo,所以这里返回的是0
  2. 进入第二步,就是比较seqNum,seqNum越大的,InternalKey越小,注意,是越小。

所以这里问题解答出来了,执行完这三个语句之后,三个InternalKey都会在跳表中,同时seqNum越大的,排名越靠前。

所以这就导致我们对某个userKey进行search的时候,我们的InternelKey的构造,userKey=foo,seq=currentSeq,valueType=Value。

这样查找的时候,使用ceilingEntry方法查找,这个方法查找的是最近的一个和他一样或者比他大的。

compact

一个MemTable什么时候停止写入,变成磁盘的SSTable呢?

答案在makeRoomForWrite方法中:

1
memTable.approximateMemoryUsage() <= options.writeBufferSize()

这里的options.writeBufferSize,默认情况下是4 << 20,也就是4G。

具体的compact逻辑在compactMemTableInternal方法中,使用tableBuilder,建立SSTable后,加入到VersionSet中。

但是具体加入到哪一个Level中呢?一定就是Level0吗?

答案是不一定。看代码,这里的meta就是新生成SSTable。

1
2
3
4
5
6
7
8
9
int level = 0;
if (meta != null && meta.getFileSize() > 0) {
Slice minUserKey = meta.getSmallest().getUserKey();
Slice maxUserKey = meta.getLargest().getUserKey();
if (base != null) {
level = base.pickLevelForMemTableOutput(minUserKey, maxUserKey);
}
edit.addFile(level, meta);
}

具体放入哪个Level,是由pickLevelForMemTableOutput这个方法决定的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int pickLevelForMemTableOutput(Slice smallestUserKey, Slice largestUserKey) {
int level = 0;
if (!overlapInLevel(0, smallestUserKey, largestUserKey)) {
// Push to next level if there is no overlap in next level,
// and the #bytes overlapping in the level after that are limited.
InternalKey start = new InternalKey(smallestUserKey, MAX_SEQUENCE_NUMBER, ValueType.VALUE);
InternalKey limit = new InternalKey(largestUserKey, 0, ValueType.VALUE);
while (level < MAX_MEM_COMPACT_LEVEL) {
if (overlapInLevel(level + 1, smallestUserKey, largestUserKey)) {
break;
}
long sum = Compaction.totalFileSize(versionSet.getOverlappingInputs(level + 2, start, limit));
if (sum > MAX_GRAND_PARENT_OVERLAP_BYTES) {
break;
}
level++;
}
}
return level;
}

这个方法中,overlapInLevel方法是判断新SSTable的userKey范围是否与这一层的某个文件userKey的范围重合。

如果不重合,就直接下沉到下一个Level进行查找。

图例:MemTable变成了SSTable,范围是13 ~ 18。那么他会放到哪一层呢?

  1. 首先看Level 0,没有一个SSTable的Key范围和他有重合的
  2. 再看Level 1,还是没有一个SSTable的Key范围和他有重合的。
  3. 再次下沉到Level 2,发现第一个SSTable与他有重合。
  4. 所以新的SSTable会被放到Level 1。

最终结果如下图所示。

Welcome to my other publishing channels