leveldb源码阅读8 Orient面试

介绍一下这个项目（分模块）

本项目主要参考Google开源项目levelDB，实现了一个基于LSM结构的键值存储引擎。

项目中实现了日志、布隆过滤器、内存分配器、缓存管理、文件读写、SSTable存储、写前日志（WAL），MemTable管理等核心模块，对各模块进行了单元测试。用键值对存储，支持快速写入和高效查询，具备良好的稳定性和性能。

项目介绍：

本项目主要基于log structure merge实现一个键值对存储引擎。（具体的过程db.h里面还是写的很清楚的）

写入时首先会写入日志，再回写到memtable中，再写到缓存（缓存满了怎么办）中。如果memtable（底层是跳表）超过原有的大小，会将其转换成sst，加入磁盘中（其实也就是写入某个路径下的文件里），并且创建一个新的memtable。

读取时，首先从cache中读取，再从memtable中读取,最后从sst磁盘中读取，但是在真正进入磁盘读取之前会先用布隆过滤器确认磁盘中是否存在。

根据以上的需求我们实现了内存管理，文件读写，sstable，memtable，跳表，日志等模块。可以进行快速写入和高效查询。

内存管理（内存分配器，和缓存设计）

设计内存池机制和分片LRU缓存系统，优化内存管理，支持多分片减少锁竞争，并通过回调函数实现缓存项淘汰时的资源清理。

内存池

这个类实现了一个基于内存槽的内存分配策略。

内存槽是一个数组，其中的每个结点块是不同大小的内存块链表，依次从8字节，16，32，…一直到4*1024字节，因此少于4*1024字节的内存不会用内存槽分配，直接malloc或者new分配即可。

内存池则是一个char*，会为其预分配4*1024*1024字节的数据。

内存池槽中的每个数组属所分配的每块空间都是在内存池中，内存池满时会重新分配新的内存池，剩余部分如果一个block都无法满足，会将其挂载到其它合适的数组的某个链表中；一般会直接申请十个内存块，以免频繁申请。

公共接口：allocate，deallocate，reallocate

allocate：满足大于0小于4kb时，找到相应的内存槽填入内存槽，内存槽指针指向下一个内存块。
deallocate：满足大于0小于4kb时，找到相应的内存槽，将该内存加入其中，内存槽指针指向新加入的位置，因为一般是头插法。
reallocate：先deallocate，再allocate

私有函数：fill_slot，fill_mem_pool

第二个函数用于分配新的4MB的内存池。
第一个函数用于填内存槽，也就是当需要分配空间但是内存槽中没有相应字节的内存管理时，寻找到对应的sloti，一次性分配FILL_BLOCK_CNT也就是10个块。填内存槽时会出现三种情况：
- 内存池容量足够分配所有块，直接分配
- 内存池容量只够分配一部分块，先分配一部分块
- 内存池容量一块也不够，剩余部分挂在到slot上，重新申请内存池（内存池会修改指针和大小，但是slot作为某种形式的数组/链表，是始终存在的，挂载也可以避免内存碎片；之后重新运行该函数，继续分配。

cache

Cache中持有N（默认为5）个指向CachePolicy的指针，相当于5个分片，可以减少哈希冲突以及减少锁的范围；LRUCache和LFUCache都是CachePolicy的子类。

为什么使用LRU缓存，LFU呢，其它缓存为什么不行？

LRU:淘汰最久未被访问的数据项
LFU:淘汰访问频率最低的缓存项

LRU实现简单,并且更加适合具有局部性原理的访问模式.

leveldb中为什么存在lru链表和in-use链表，两个链表？

一个存放lru中的结点,另一个存放被lru淘汰的结点,结点被淘汰了但是不一定没有被其它引用,贸然删除可能造成不好的结果,每隔一段时间,遍历in-use链表,如果引用计数变为0,将其删除.

两个哈希函数的作用；回调函数的作用。

这两个哈希和leveldb中两个链表是一样的作用.

回调函数: 在缓存条目被删除或替换时，执行一些清理操作，通常是在缓存项被淘汰、移除或替换后进行特定的资源释放或额外的操作。

lrucache-leetcode 另：锁的设计

文件读写和WAL（文件读写，WAL）

实现了高效的文件读写操作，优化了WAL和SSTable文件的持久化过程，同时支持并发读取。

并发读取：

从文件中读取指定数量的字节存储到缓冲区中

由于函数原型中自带偏移量，因此不会更新文件描述符的内部偏移量

以此把证线程安全，适合多线程环境

file_write

主要用于对WAL Write-Ahead Log文件和Sorted String Table的持久化操作，实现关注于高效的文件写入，缓冲区，内存映射文件等技术，优化文件写入。

将文件中的数据从用户空间写到文件描述符fd指向的文件，
将fd指向文件的缓冲数据同步到磁盘中，

在缓冲区中追加数据时，需要考虑到缓冲区内存是否可以容纳所有的数据，如果可以就直接写入，不行的话先将缓冲区中的数据刷新到磁盘再写入。

file_read

主要用于打开文件，从缓冲区中读取数据，注意实现多线程环境下的并发读取。

顾名思义，Write-Ahead Logging先写日志，再更新数据。

levelDB中的文件读写和WAL都是在log_writer和log_reader中实现的。leveldb中的结构为
1
2
3
+--------------+---------+----------+------+
| checksum(4B) | len(2B) | type(1B) | data |
+--------------+---------+----------+------+
checksum是校验数据的准确性；len为长度；type为类型，即如果一条数据在一个block中存放不下，这里会例句该block是数据的前面，中间或者后面部分；data为数据。

这里将WAL和文件读写分开实现。

WAL和文件读写分开实现有助于遵循单一职责原则和依赖注入原则。

q1：WAL如何利用filewrite作为私有变量实现的

利用filewriter作为私有成员，利用了crc循环冗余校验值存储，同时保留长度，作为wal读写。

日志系统实现（日志）

使用单例模式设计日志系统，采用spdlog库实现高效的多线程日志记录，并确保日志实例的唯一性和高效性。

实现方案：利用单例模式实现日志。

参考的库是典型的c++日志库spdlog，它使用内存映射文件和异步日志记录技术，能够快速记录；支持多线程，能够保障线程安全（手段为互斥锁）；具有多种日志级别，采取了灵活的日志格式化选项，支持跨平台，多后端。

对于spdlog::logger加上共享指针shared_ptr，便携化资源释放。

对于创建一个日志单例采取的是最为经典的静态局部变量的懒汉单例，static既能保证共享性下只存在一个实例，也能保证变量的创建不被打乱，相比于双重锁和智能指针实现的更完善也更简单。

持久化（Mentable，sstable）

实现了SkipList作为Memtable的数据结构，通过优化算法提高内存中的数据存取效率，支持基本的读写操作。

设计并实现了SkipList作为Memtable的数据结构，优化内存中的数据存取效率。
提高了跳表（SkipList）在并发读写下的线程安全性，使用锁机制避免数据竞争。

sstable

设计SSTable文件格式，实现了数据块（Data Block）、索引块（Index Block）、元数据块（Meta Block）等的存储，并使用多级索引优化查询性能。

在leveldb中，当将memory db的数据持久化文件中时，leveldb会以一定的规则进行文件组织，文件格式变为sstable。这个部分也模仿一下leveldb，那先回顾一下leveldb中的结构。见leveldbS源码阅读3 - File System (sstable,cache,option)，详谈leveldb中的sstable

查询时，一般会通过footer先在meta block中利用bloom filter查询，如果不存在则直接返回，减少了磁盘IO，然后再通过Index block找到之后对于相应的Data block即可。（通过 Footer -> IndexBlock -> DataBlock 的多级索引方式）

有个问题，sstable中的地址是footer最小吗，如果是的话，那怎么存放datablock的，一个sstable是一整个完整的连续空间吗？

SSTable 是一个完整的、连续的磁盘文件。Footer 是整个 SSTable 文件的最后一个固定部分，不是存储的最小地址。Footer 的大小是固定的，程序可以通过文件总大小减去 Footer 大小快速找到 Footer 的起始位置。

Data Block

存储key，value数据对

DataBlock_1 ~ DataBlock_N：即DataBlock，由DataBLockBuilder操作

+-----------------------------+
| Record_1 - Record_n        |  <-- n条记录，每条记录是一个键值对
+-----------------------------+
| Restart Point_1 - ..._k    |  <-- k个重启点，从该位置开始一组记录
+-----------------------------+
| Restart_Num(4B)            |  <-- 重启点数量
+-----------------------------+
| Restart_Offset(8B)         |  <-- 重启点数组的起始偏移量
+-----------------------------+

datablock中主要需要存储数据，为了最有效的存储数据，我们在类的private中设置了pre_key，这是为了比较前缀，只存储相同的数据，在它的记录中，它的存储格式为shared_key_len,unshared_key_len,value_len,unshared_key_conten,value_content，同时为了查找时的效率加快，每相隔16条记录会设置一个重启点，同时利用一个数组记录重启点数组每次的偏移量；

由于偏移量的大小只能写完16条才能记录，不能实时，同时为了防止多次进行磁盘IO，因此每个数据块都是先存放在缓冲区中，等到最后满时创建数据块，创建之后就不能再添加数据了。

Meta Block

存储filter相关信息

MetaBlock：存放Filter等信息，这里每个SST只设置一个MetaBlock

filter_block和datablock的机制差不多，更简单一点，基本调用bloomfilter中的函数，创建过滤器，添加键，判断键是否存在之类的。

Index Block

存储每个data block的索引信息

IndexBlock_1 ~ IndexBlock_N：存放对应的DataBLock的Offset信息、最大Key信息

 +------------------------+---------------+-----------------+
 | _shortest_key_size(4B) | _shortest_key | _offsetInfo(8B) |
 +------------------------+---------------+-----------------+

Footer

存储meta index block和index block的索引信息

Footer：存放MetaBlock、IndexBlock的Offset信息

+---------------------------+----------------------------+
| MetaBlock_OffsetInfo (8B) | IndexBlock_OffsetInfo (8B) |
+---------------------------+----------------------------+

布隆过滤器

模拟LevelDB中的布隆过滤器，通过优化哈希函数的数量和位数组大小来保证在高假阳性率情况下的准确性。

leveldb中时通过键的位数确立哈希函数的个数，这里的构造函数中直接通过传入的键的数量和假阳性率确立最佳的哈希函数数量和为数组大小（这些是论文中有结论，能确保最为准确。默认假阳性率为0.01

创建过滤器时，会通过键和双重哈希增量模拟每次的哈希函数，哈希的方法采用的是murmur_hash，最终存储到相应大位中，同时判断是否存在其中也是对齐进行哈希计算，只要判断出一次不存在那就一定不存在与数组中，但是全部存在也不能证明一定在数组中。

数据库接口

设计并实现了数据库的接口层，支持数据高效的Put，Delete，Get操作，完善整体逻辑。

/*
   * Put逻辑：
   * 1. 写WAL(fsync同步);
   * 2. 写memtable;
   * 3. 写缓存(提高读性能);
   * 4. 如果memtable超限，应该落盘，并且开启一个新的memtable;

   * Delete逻辑：
   * 1. 写WAL;
   * 2. 写memtable;
   * 3. 删除缓存;
   * 4. 如果memtable超限，应该落盘，并且开启一个新的memtable;

   * Get逻辑：
   * 1. 读cache，有则直接返回，否则进入2;
   * 2. 依次从memtable、sst文件向下查找;
   * 3. 找到的数据写入缓存;
   * 4. 返回结果;
*/

压测

手撕LRUcache
手撕线程池https://zhuanlan.zhihu.com/p/1173596229
手撕跳表