Leveldb: Basic Settings

November 26, 2016

Database Leveldb

（待完善……）

Slice(include/leveldb/slice.h)

为操作数据的方便，将数据和长度包装成 Slice 使用，直接操控指针以避免不必要的数据拷贝
```
class Slice {
    … 
    private: 
        const char* data_; 
        size_t size_; 
};
```
Option(include/leveldb/option.h)

leveldb 中启动时的一些配置，通过 Option 传入，get/put/delete 时，也有相应的 ReadOption/WriteOption。
Env(include/leveldb/env.h util/evn_posix.h)

考虑到移植以及灵活性，leveldb 将系统相关的处理（文件/进程/时间之类）抽象成 Env，用户可以自己实现相应的接口，作为 Option 传入。默认使用自带的实现。
varint(util/coding.h)

leveldb 采用了 protocalbuffer 里使用的变长整形编码方法，节省空间。
ValueType(db/dbformat.h)

leveldb更新（put/delete）某个key时不会操控到db中的数据，每次操作都是直接新插入一份kv数据，具体的数据合并和清除由后台的compact完成。

所以，每次 put 都会添加一份 KV 数据，即使该 key 已经存在；而 delete 等同于 put 空的 value。为了区分 live 数据和已删除的 mock 数据，leveldb 使用 ValueType 来标识：
```
enum ValueType { 
    kTypeDeletion = 0x0, 
    kTypeValue = 0x1 
};
```
SequenceNumber(db/dbformat.h)

leveldb中的每次更新（put/delete) 操作都拥有一个版本，由 SequnceNumber 来标识，整个db有一个全局值保存着当前使用到的SequnceNumber。SequnceNumber 在 leveldb 有重要的地位，key 的排序，compact 以及 snapshot 都依赖于它。

typedef uint64_t SequenceNumber: 存储时，SequnceNumber 只占用56 bits, ValueType 占用8 bits，二者共同占用 64bits（uint64_t).

0-56 56-64

SequnceNumber ValueType
user_key & memtable_key & internal_key
- user_key: 用户使用的 key
- memtable_key: memtable 中使用的 key
- internal_key: sstable 中使用的 key
InternalKey(db/dbformat.h) & ParsedInternalKey (db/dbformat.h)

InternalKey: userkey ＋元信息（8 bytes, SequnceNumber|ValueType), ParsedInternalKey 为 InternalKey 分拆得到的结构体
```
class InternalKey {
    …
    private:
        std::string rep_;
}
    
struct ParsedInternalKey { 
    Slice user_key; 
    SequenceNumber sequence; 
    ValueType type; 
};
```
LookupKey(db/dbformat.h)

db 内部为查找 memtable/sstable 方便而设置的类：
```
class LookupKey { 
    … 
    private: 
        const char* start_;
        const char* kstart_;
        const char* end_;
};
```
start_ kstart_ - end_

internal_key_size internal_key: userkey_data + SequenceNumber

(varint32) (InternalKey_size: char[] + uint64)

对 memtable lookup 时使用 memtable_key [start_,end_], 对 sstable lookup 时使用 internal_key [kstart_, end_]。
memtable entry