leveldb-Impl: Version.java

Manifest与Current文件是LevelDB保存在稳定存储中的文件版本信息，在LevelDB被打开后，其会先通过Current文件找到当前的Manifest文件，读取并反序列化其中数据，并在内存中维护文件版本信息，以便后续操作。

先来说说Version，Version表示了当前leveldb的版本信息，
版本信息内容包括：1当前每一层的SSTable文件元信息。2记录被Seek太多次需要Compact的文件元信息，以及文件所在的level。3记录所有level层中compaction score 最大的那一层及其level，用于比较判断是否需要对此level层进行compact。

leveldb/Version.java at master · dain/leveldb · GitHub

public class Version
        implements SeekingIterable<InternalKey, Slice>
{
    private final AtomicInteger retained = new AtomicInteger(1);
    private final VersionSet versionSet;
    private final Level0 level0;
    private final List<Level> levels;

    // move these mutable fields somewhere else
    private int compactionLevel;
    private double compactionScore;
    private FileMetaData fileToCompact;
    private int fileToCompactLevel;

AtomicInteger是提供原子操作的Integer类,通过线程安全的方式操作加减。

leveldb内部只有一个VersionSet进行管理所有的Version. 当不断有新版本生成的时候，那么就需要不断地 Append 到 versionset 里面。 当旧的 Version 不再服务读请求之后，这个 Version 就会从Versionset中移除。

leveldb的第一层level0 并新建List<Level> levels记录文件所在level信息。

FileMetaData使用来表示sstable的元数据。fileTocompact记录下一个等待compact的file。当fileMataData文件查找到一定次数时就要执行合并操作。

version改变时结合compactionLevel和compactionScore的信息确定下次compaction的level和文件。

fileToCompactLevel记录文件压缩到哪个level。

对 Version 的修改主要发生于 compaction 之后。compaction 分为 minor compaction 和 major compaction，其中 minor compaction 是落 memtable 到 L0，只会新增文件，而 major compaction 会跨 level 做合并，既新增文件也删除文件。每当这时，便会生成一个新的 VersionEdit 产生新的 Version。

public Version(VersionSet versionSet)
    {
        this.versionSet = versionSet;
        checkArgument(NUM_LEVELS > 1, "levels must be at least 2");

        this.level0 = new Level0(new ArrayList<FileMetaData>(), getTableCache(), getInternalKeyComparator());

        Builder<Level> builder = ImmutableList.builder();
        for (int i = 1; i < NUM_LEVELS; i++) {
            List<FileMetaData> files = new ArrayList<>();
            builder.add(new Level(i, files, getTableCache(), getInternalKeyComparator()));
        }
        this.levels = builder.build();

    }

先判断versionset里的level层数>1 若为Level0则新建对象level0，由FileMetaData TableCache 和 InternalKeyComparartor组成。

ImmutableList.builder方法新建builder对象，更新产生新的version，将新的level对象add到builder中。

public void assertNoOverlappingFiles()
    {
        for (int level = 1; level < NUM_LEVELS; level++) {
            assertNoOverlappingFiles(level);
        }
    }

判断SStables有没有重复的Key范围

public void assertNoOverlappingFiles(int level)
    {
        if (level > 0) {
            Collection<FileMetaData> files = getFiles().asMap().get(level);
            if (files != null) {
                long previousFileNumber = 0;
                InternalKey previousEnd = null;
                for (FileMetaData fileMetaData : files) {
                    if (previousEnd != null) {
                        checkArgument(getInternalKeyComparator().compare(
                                previousEnd,
                                fileMetaData.getSmallest()
                        ) < 0, "Overlapping files %s and %s in level %s", previousFileNumber, fileMetaData.getNumber(), level);
                    }

                    previousFileNumber = fileMetaData.getNumber();
                    previousEnd = fileMetaData.getLargest();
                }
            }
        }
    }

根据PreviousFileNumber（InternalKey类)  ,fileMetaData 和所在的 level，检查是否有重叠的Files

private TableCache getTableCache()
    {
        return versionSet.getTableCache();
    }

获取TableCache

public final InternalKeyComparator getInternalKeyComparator()
    {
        return versionSet.getInternalKeyComparator();
    }

获取InternalKey比较器

 public synchronized int getCompactionLevel()
    {
        return compactionLevel;
    }

获取compaction的level

public synchronized void setCompactionLevel(int compactionLevel)
    {
        this.compactionLevel = compactionLevel;
    }

设置compaction的level

public synchronized double getCompactionScore()
    {
        return compactionScore;
    }

获取compactionScore,决定是否触发compaction

public synchronized void setCompactionScore(double compactionScore)
    {
        this.compactionScore = compactionScore;
    }

设置CampactionScore

@Override
    public MergingIterator iterator()
    {
        Builder<InternalIterator> builder = ImmutableList.builder();
        builder.add(level0.iterator());
        builder.addAll(getLevelIterators());
        return new MergingIterator(builder.build(), getInternalKeyComparator());
    }

如果每个iterator中的key有序，但是所有iterator中的所有key全局无序，此时，需要一种能够“归并”多路有序iterator的结构。这一结构即MergingIterator 


传入level0的iterator和所有Level的iterator，以及用来比较InternalKey的Comparator。InternalKey迭代器迭代器组合了MemTable Iterator、Immutable MemTable Iterator、每个Level-0 SSTable的Iterator，和level>1的所有SSTable的Concatenating Iterator。

List<InternalTableIterator> getLevel0Files()
    {
        Builder<InternalTableIterator> builder = ImmutableList.builder();
        for (FileMetaData file : level0.getFiles()) {
            builder.add(getTableCache().newIterator(file));
        }
        return builder.build();
    }

新建InternalTableIterator的对象获取TableCache中的level0的file。迭代方法使用时都反复需要获取其中iterator是否为valid或获取其value，不需要每次都访问到最下层的iterator，只需要访问缓存状态即可。

List<LevelIterator> getLevelIterators()
    {
        Builder<LevelIterator> builder = ImmutableList.builder();
        for (Level level : levels) {
            if (!level.getFiles().isEmpty()) {
                builder.add(level.iterator());
            }
        }
        return builder.build();
    }

遍历每一层Level,获取level的Iterator

public LookupResult get(LookupKey key)
    {
        // We can search level-by-level since entries never hop across
        // levels.  Therefore we are guaranteed that if we find data
        // in an smaller level, later levels are irrelevant.
        ReadStats readStats = new ReadStats();
        LookupResult lookupResult = level0.get(key, readStats);
        if (lookupResult == null) {
            for (Level level : levels) {
                lookupResult = level.get(key, readStats);
                if (lookupResult != null) {
                    break;
                }
            }
        }
        updateStats(readStats.getSeekFileLevel(), readStats.getSeekFile());
        return lookupResult;
    }

获取level0的LookupKey

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;
    }

pickLevelForMemTableOutput:从Memtable中dump到level0
leveldb中的db文件本身没有层次概念，所有的db文件都一样，如何确定这个文件是在哪一层由pickLevelForMemTableOutput方法实现。

public boolean overlapInLevel(int level, Slice smallestUserKey, Slice largestUserKey)
    {
        checkPositionIndex(level, levels.size(), "Invalid level");
        requireNonNull(smallestUserKey, "smallestUserKey is null");
        requireNonNull(largestUserKey, "largestUserKey is null");

        if (level == 0) {
            return level0.someFileOverlapsRange(smallestUserKey, largestUserKey);
        }
        return levels.get(level - 1).someFileOverlapsRange(smallestUserKey, largestUserKey);
    }public boolean overlapInLevel(int level, Slice smallestUserKey, Slice largestUserKey)
    {
        checkPositionIndex(level, levels.size(), "Invalid level");
        requireNonNull(smallestUserKey, "smallestUserKey is null");
        requireNonNull(largestUserKey, "largestUserKey is null");

        if (level == 0) {
            return level0.someFileOverlapsRange(smallestUserKey, largestUserKey);
        }
        return levels.get(level - 1).someFileOverlapsRange(smallestUserKey, largestUserKey);
    }

 

参考：深入浅出LevelDB —— 08 Iterator – 叉鸽 MrCroxx 的博客