LevelDB 是由 Google 开发的 key-value 非关系型数据库存储系统,是基于 LSM(Log-Structured-Merge Tree) 的典型实现,LSM 的原理是:当读写数据库时,首先纪录读写操作到 Op log 文件中,然后再操作内存数据库,当达到 checkpoint 时,则写入磁盘,同时删除相应的 Op log 文件,后续重新生成新的内存文件和 Op log 文件。
LevelDB 内部采用了内存缓存机制,也就是在写数据库时,首先会存储在内存中,内存的存储结构采用了 skip list 结构,待达到 checkpoint 时,才进行落盘操作,保证了数据库的高效运转。
如上图所示,整个 LevelDB 由以下几部分组成:
整体结构清晰紧凑,非常容易理解。
DB() { };
virtual ~DB();
static Status Open(const Options& options,
const std::string& name,
DB** dbptr);
virtual Status Put(const WriteOptions& options,
const Slice& key,
const Slice& value) = 0;
virtual Status Delete(const WriteOptions& options, const Slice& key) = 0;
virtual Status Write(const WriteOptions& options, WriteBatch* updates) = 0;
virtual Status Get(const ReadOptions& options,
const Slice& key, std::string* value) = 0;
virtual Iterator* NewIterator(const ReadOptions& options) = 0;
virtual const Snapshot* GetSnapshot() = 0;
virtual void ReleaseSnapshot(const Snapshot* snapshot) = 0;
整体接口分为:
DB() { };
virtual ~DB();
static Status Open(const Options& options,
const std::string& name,
DB** dbptr);
virtual Status Put(const WriteOptions& options,
const Slice& key,
const Slice& value) = 0;
virtual Status Delete(const WriteOptions& options, const Slice& key) = 0;
virtual Status Get(const ReadOptions& options,
const Slice& key, std::string* value) = 0;
virtual Status Write(const WriteOptions& options, WriteBatch* updates) = 0;
virtual Iterator* NewIterator(const ReadOptions& options) = 0;
virtual const Snapshot* GetSnapshot() = 0;
virtual void ReleaseSnapshot(const Snapshot* snapshot) = 0;
LevelDB 使用的 Op log 日志采用了文件记录的方式,且文件使用了 mmap 方式操作,以提高效率。
Op log 存储切分为 32KB 大小的数据块,每个 32KB 数据块存储着 Op log,每 个Op log 格式如下:
其中:
memtable 是 LevelDB 数据库的内存存储结构,采用了 skip list 结构存储,如下图所示:
skip list 是一种可以代替平衡树的存储结构,它采用概率的方式来保证平衡,而平衡树则是采用严格的旋转树结构来保证平衡,复杂度会高一些。
对于 skip list,会有 n 层链表,其中 0 层保存所有的值,越往上层,保存的值越少。每当插入一个值时,会通过概率计算该值需要插入的最高层级 k,然后从 0~k-1 层,分别插入该值。
其中每个表项的存储结构如下:
key_size | key_value | sequence_num&type | value_size | value
其中:
sequence_num:表示操作的序列号,每一个数据项都会带有一个序列号,用以表示数据的新旧程度。
type:表示数据的类型,分为:
sstable 作为落盘的存储结构,每个 sstable 最大 2MB,从宏观来看,它属于分层的结构,即:
level 3 及之后:存储大小不超过上一级大小的 10 倍
之所以这样分层,是为了提高查找效率,也是 LevelDB 名称的由来。当每一层超过限制时,会进行 compaction 操作,合并到上一层,递归进行。
从微观的角度看,每个 sstable 文件结构入下图所示:
其中:
另外 Data Block 及 Meta Block 的存储格式是统一的,都是如下格式:
其中 type 表示是否是压缩存储,目前 LevelDB 支持 key 值的 snappy 压缩或者不压缩。
而上图中的 Block data 的格式则为:
上图有几点要说明:
对于 Meta Block 来说,它保存了用于快速定位 key 是否在 Data Block 中的信息,具体方法是:
对于 LevelDB 来说,它采用了简单的 sequence num 机制来管理,具体为:
LevelDB 短小精悍,代码运行效率高效,且通俗易懂,是一个非常不错的 k-v 存储系统。
注:图片来源于网络
← GCanvas 渲染引擎介绍 如何实现一个 Git Diff 解析器 →题图:https://unsplash.com/photos/9wwF-VmSOrY By @eberhard grossgasteiger