LSM树详解 - 知乎LSM Tree原理详解 - 简书(13条消息) 最容易理解的LSM树--以示例讲解合并查找过程\_lsm树示例\_土豆西瓜大芝麻的博客-CSDN博客
leveldb笔记之20:写入与读取流程 - Ying
LevelDB存储6：适者生存 —— Cache - 知乎LevelDB LRUCache浅谈 - 掘金LevelDB 源码解析之 Cache 缓存 - 掘金问题集数据什么时候过期？参考源码include/leveldb/cache.h: 定义Cache接口 util/cache.cc: 实现LRU缓存 table/table.cc: 读取Data Block时使用缓存 db/table_cache.cc：实现一个Table结构的缓存原理shardedLRUCache定义了多个LRUCache，用来实现分段式锁。每个LRUCache其实就是hashtable和hashnode。而in_use\_和lru\_只是从另外二个维度将hashnode使用双向链表连接起来。最新插入的数据排在链表尾部。就是将hashtable中的node分成了两组：in_use\_：正在被使用的放一组，通过双向链表把他们连接起来lru\_：没有被使用的node，最新的在最前面。所以每次淘汰从最后取。如果in_use\_使用结束的node放入lru，lru中被使用的节点要移动到in_use\_。中图的插入和淘汰只是
当前版本的引用计数至少是1。生成新版本时，将旧的当前版本Unref，就是引用计数减1。MANIFEST简而言之：每次启动都会根据当前 current文件指向MANIFEST文件进行恢复，MANIFEST第一条记录了一个版本的全部信息，后面是迭代的变化记录。根据当前MANIFEST生成一个版本后（当前版本+改变=最新版本），就会新建一个MANIFEST，存放新建的版本，后续将其他的变化记录在这个文件中。如果数据库本身没有重启，这个manifest会一直增长，即每次重启新建MANIFEST。manifest文件专用于记录版本信息。leveldb采用了增量式的存储方式，记录每一个版本相较于上一个版本的变化情况。VersionEdit的内容将持久化到MANIFEST里的。即：MANIFEST里面保存的是VersionEdit。一个Manifest内部包含若干条Session Record，其中第一条Session Record记载了当时leveldb的全量版本信息，其余若干条Session Record仅记录每次更迭的变化情况。因此，每个manifest文件的第一条Session Record
入口函数MaybeScheduleCompaction() void DBImpl::BackgroundCompaction()CompactionMinor Compaction：Immutable Memtable向level-0中的SSTable文件的转换（优先级高）。Major Compaction：将SSTable移到更高的Level去，需要保证Level 0以上的SSTable每层之间的键有序无重叠。Major Compaction其实就是一个归并排序的过程，对多个输入的SSTable，多路归并，输出多个连续的SSTable，代替原来的文件。根据Level 0的特殊性，可以分为两种类型：Level 0 -> Level 1Level n -> Level n + 1 （n > 0)将多个小SSTable合并成一个大SSTable，可以解决查找的效率问题。但是，如果不断地有新的小SSTable进来，这些小SSTable都需要和这个大的SSTable进行合并，不管多大的SSTable来合并，都需要读取所有的磁盘数据，并且写入所有的磁盘数据。大的SSTabl
可以通过布隆过滤器快速判断对应的键有没有在这个SSTable里。如果判断键在SSTable，那也只有很小的概率是键不在这个SSTable里。这是典型的用空间换时间的思想，选择布隆过滤器是因为布隆过滤器的空间占用非常小，可以加载到内存中，进行快速判定。
LevelDB SSTable文件数据布局 - 掘金深入浅出LevelDB —— 05 SSTable - 叉鸽 MrCroxx 的博客Archive - Ying's Blog参考源码使用table_builder_test进行梳理整个过程。Table类：读取sstable。sstable写入过程：创建文件 for: 插入kv创建data_block 将多个data_block插入到文件末尾 filter block写入sstable meta_index_block 写入 index block 写入footer//编解码BlockHandler，编解码Footer，根据BlockHandler读取一个键的内容 table/format.h table/format.cc //不断添加键值对，逐渐构建一个Block，主要是添加键值对，然后生成Block的数据 *table/block_builder.h table/block_builder.cc //对一个Block进行读取相关的功能 table/block.h table/block.cc table/f
源码：log_writer.cc。为了不丢失数据，需要持久化的功能。把数据持久化到磁盘上，最常用的技术就是日志技术，也就是当修改数据时，先把对数据的修改写到磁盘上，然后在MemTable里做修改。因为日志记录了每个操作，只要对日志进行重放便可以恢复MemTable，这样就做到了数据库实例崩溃、宕机或者停机维护的时候数据不丢失。这种日志技术在数据库里面很常用（Redis里的Aof，Innodb里的Redo Log都是这样的技术），一般称为WAL （Write Ahead Log），正如名字一样，就是在写入前先写入日志的意思。Put操作也不能简单的写入到 memtable，而是要先写日志、再写 memtable，都更新完成后再返回写入成功，write-ahead logging 名字也是由此而来。因为日志的写入都是Append的，也就是顺序写，所以写磁盘也是顺序写，虽然磁盘的随机写效率比较低，但是顺序写效率还是很高的，所以就算加入了日志，写效率还是很高，依然可以满足写多的场景。另外可以通过控制日志写同步的策略在性能和可靠性之间做折中：每次写入都做一次sync，可靠性最高，不会丢数据，但是性
设计MemTable是一个内存数据结构，简单说它就是一个SortedMap：MemTable是一个Map，提供了Get接口，也就是可以快速地根据键查找到值，也可以使用Put接口插入Kv。MemTable是Sorted，也就是里面存储的键都是有序的，可以按照键的顺序迭代Map，或者做范围查询。有了MemTable提供的Get和Put，就有了一个简单的内存Kv数据库，可以实现Kv的查询，插入和范围查询。Put，Delete，Update实际上都是一个Put。Update：等价于新插一个同样的key（LevelDB中没有Update）。Delete：将当前最新的key插入空，并且标志置为删除。因为MemTable是内存数据结构，不需要磁盘IO，所以读写的速度非常快，所以就达到了场景需求：高效的写性能。然而这会有个问题，当数据库实例崩溃、宕机或者停机维护的时候，存储的数据就会丢失，这时候需要持久化数据。class MemTable { typedef SkipList<const char*, KeyComparator> Table; KeyComparator comp
动静结合——编码 - 知乎参考源码util/coding.h util/coding.cc：编码实现的源代码定长整数32位和64位。变长整数1标识后面还有字节要读取，0表示结束。Slicelevel只保存字符串类型。无论字符串是英文还是中文，slice都是指向二进制的字符串，不关心中文英编码形式。至于打印，就是将slice指向的二进制传递给string进行打印。对于slice来说，它只关心二进制，至于解码打印或者比较，交给string。
YJ-Ma的小屋🍉
勿在浮沙筑高台
