存储引擎

leveldb的文件组成:

- memtable
- immemtable
- log(journal)
- sstable
- manifest
- current

memtable分析

leveldb中的内存数据库，维护有序的key-value对，底层利用跳表实现，读写的时间复杂度为O（log N）

note： 为什么不选择红黑树呢，（跳表 VS 红黑树） 
一个拥有k个指针的结点称为一个k层结点（level k node）。按照上面的逻辑，50%的结点为1层节点，25%的结点为2层节点，12.5%的结点为3层节点。若保证每层节点的分布如上述概率所示，则仍然能够相同的查询效率。

编码方式

由于内存数据库本质是kv集合，数据项按照key进行排序（方便查找），因此键值得编码规则尤为关键。

内存数据库中，key称为internalKey；[ db/dbformat.h ]
    1、用户定义的key：原生的key值；
    2、序列号：leveldb中，每一次写操作都有一个sequence number，标志着写入操作的先后顺序。由于在leveldb中，可能会有多条相同key的数据项同时存储在数据库中，因此需要有一个序列号来标识这些数据项的新旧情况。序列号最大的数据项为最新值；
    3、类型：标志本条数据项的类型，为更新还是删除；

                        InternalKey结构
     -------------------------------------------------------------    
    |   user_key    |  sequence number(7 bytes)  |  type(1 byte)  |
     ------------------------------------------------------------- 

InternalKey(const Slice& user_key, SequenceNumber s, ValueType t){
    AppendInternalKey(&rep, ParsedInternalKey(user_key, s, t));
}
struct ParsedInternalKey{
    Slice user_key;
    SequenceNumber sequence;
    ValueType type;
};

class MemTable{
public:
    void Add(SequenceNumber seq, ValueType  type, const Slice& key, const Slice& value){
        /*  Format of an entry is concatenation of:
         *      key_size:    varint32 of internal_key.size()
         *      key bytes:   char[internal_key.size()]
         *      value_size:  varint32 of value.size()
         *      value bytes: char[value.size()]
         */
        ......
        table_.Insert(buf);  //插入跳表
    }

private:
    //私有析构?? 只能在Unref()显式调用delete来释放
    //private since only Unref() should be used to delete it;
    ~MemTable(); 

    //key 比较器
    struct KeyComparator{
        const InternalKeyComparator comparator;
        explicit KeyComparator(const InternalKeyComparator& c) : comparator(c){}
        int operator()(const char* a, const char* b) const;
    };

    typedef SkipList<const char*, KeyComparator> Tables;
    Tables table_;
    KeyComparator comparator_;
    int refs_;
    Arena arena_;
};

leveldb compaction

- compaction的时机：
    - 后台线程的定期任务(DB::open()中impl->MaybeScheduleCompaction())
    - 正常读写流程中判定系统达到一个临界状态，此时必须进行Compaction 
- leveldb中的compaction有两种：
    - minor compaction：将immemtable数据写回到Disk的过程；
    - major compaction：将level_N的某个文件和level_N-1中的几个文件合并的过程；

//用户add key/value过程中可能触发compaction
Status DBImpl::MakeRoomForWrite(bool force)}{
    mutex_.AssertHeld();
    assert(!writer_.empty());
    ......
    MaybeScheduleCompaction();    
}

void DBImpl::MaybeScheduleCompaction(){
    ......
    background_compaction_scheduled_ = true;
    env_->Schedule(&DBImpl::BGWork, this);  //调度， call DBImpl::BGWork
}

void DBImpl::BGWork(void* db){
    reinterpret_cast<DBImpl*> (db)->BackgroundCall();
}

void DBImpl::BackgroundCall(){
    ......
    BackgroundCompaction();
}

void DBImpl::BackgroundCompaction(){
    ......
    CompactMemTable();
}

Status DBImpl::WriteLevel0Table(MemTable* mem, VersionEdit* edit, Version* base){
    //构建SSTable
    s = BuildTable(dbname_, env, options_, table_cache, iter, &meta); 

    //edit里面添加信息
    edit->AddFile(level, meta.number, meta.file_size, meta_smallest, metalargest);
}

leveldb版本管理

//leveldb: