跳至主要內容

MiniLSM基本组件

Reo Lee2024年10月29日大约 6 分钟日常笔记lsmkv存储源码阅读

MiniLSM源码阅读笔记（二）

LSM

LsmStorageOptions主要保存lsm相关的配置信息。

pub struct LsmStorageOptions {
    // block大小，字节为单位
    pub block_size: usize,
    // sstable大小，以字节为单位
    pub target_sst_size: usize,
    // 内存中最大的memtable数量
    pub num_memtable_limit: usize,
    // compaction选项
    pub compaction_options: CompactionOptions,
    // 是否开启wal
    pub enable_wal: bool,
    // 是否可序列化
    pub serializable: bool,
}

LsmStorageState维护存储的核心组件状态，包括memtable、sstable的状态。

pub struct LsmStorageState {
    // 当前的可修改的memtable
    pub memtable: Arc<MemTable>,
    // 不可修改的memtable列表，按顺序存储
    pub imm_memtables: Vec<Arc<MemTable>>,
    // 不可修改的memtable列表持久化成sstable的l0层，按顺序存储
    pub l0_sstables: Vec<usize>,
    // 保存每一层对应的sstable id列表
    pub levels: Vec<(usize, Vec<usize>)>,
    // 保存每个sstable id对应的sstable对象
    pub sstables: HashMap<usize, Arc<SsTable>>,
}

LsmStorageInner包含存储状态以及lsm的配置信息，主要负责对存储状态的修改（压实、事务处理等）。

pub(crate) struct LsmStorageInner {
    // lsm状态，加读写锁进行并发控制
    pub(crate) state: Arc<RwLock<Arc<LsmStorageState>>>,
    // lsm全局锁
    pub(crate) state_lock: Mutex<()>,
    // sstable路径
    path: PathBuf,
    // 内存中的block缓存
    pub(crate) block_cache: Arc<BlockCache>,
    // 下一个sstable的id
    next_sst_id: AtomicUsize,
    // lsm选项
    pub(crate) options: Arc<LsmStorageOptions>,
    // compaction相关
    pub(crate) compaction_controller: CompactionController,
    // manifest相关
    pub(crate) manifest: Option<Manifest>,
    // mvcc相关
    pub(crate) mvcc: Option<LsmMvccInner>,
    // compaction过滤器
    pub(crate) compaction_filters: Arc<Mutex<Vec<CompactionFilter>>>,
}

MiniLsm为顶层封装结构体，主要为上层提供操作接口。

pub struct MiniLsm {
    // lsm tree对象
    pub(crate) inner: Arc<LsmStorageInner>,
    // 通知flush线程停止
    flush_notifier: crossbeam_channel::Sender<()>,
    // flush线程
    flush_thread: Mutex<Option<std::thread::JoinHandle<()>>>,
    // 通知compaction线程停止
    compaction_notifier: crossbeam_channel::Sender<()>,
    // compaction线程
    compaction_thread: Mutex<Option<std::thread::JoinHandle<()>>>,
}

MemTable

memtable是LSM的在内存中的组件，实现结构为线程安全的跳表，主要提供高效的数据检索和修改。

memtable分为两种：可修改的mutable和不可修改的immutable，mutable在任意时刻只能有一个，而immutable则可以有多个。当mutable的大小达到上限后会被冻结为immutable，等待被持久化为sstable文件。

pub struct MemTable {
		// 线程安全跳表
    pub(crate) map: Arc<SkipMap<KeyBytes, Bytes>>,
    // wal对象，用来持久化保存memtable修改日志
    wal: Option<Wal>,
    // 跳表id
    id: usize,
    // 跳表预估占用内存大小
    approximate_size: Arc<AtomicUsize>,
}

memtable提供了以下方法：

// 构造函数：创建带有wal的memtable，path是wal的文件路径
// 注意wal和memtable是一对一的
fn create_with_wal(id: usize, path: impl AsRef<Path>) -> Result<Self>
// 从wal文件中恢复memtable
fn recover_from_wal(id: usize, path: impl AsRef<Path>) -> Result<Self>
// 获取key对应的值
fn get(&self, key: KeySlice) -> Option<Bytes>
// 修改key对应的值为value
fn put(&self, key: KeySlice, value: &[u8]) -> Result<()>
// 范围检索，生成带有边界的iterator
fn scan(&self, lower: Bound<KeySlice>, upper: Bound<KeySlice>) -> MemTableIterator
// 将wal落盘
fn sync_wal(&self) -> Result<()> 
// 将immutable转换为sstable文件
fn flush(&self, builder: &mut SsTableBuilder) -> Result<()>

SSTable

sstable是LSM在磁盘中的核心数据结构。LSM在磁盘中是典型的分层结构：每一层都是由若干sstable组成，sstable是由block及其索引组成，而block是由若干key-value对及其索引组成。

sstable的结构：

-------------------------------------------------------------------------------------------
|         Block Section         |          Meta Section         |          Extra          |
-------------------------------------------------------------------------------------------
| data block | ... | data block |            metadata           | meta block offset (u32) |
-------------------------------------------------------------------------------------------

其中Block Section包含的是具体的block数据；Meta Section则是每个block的元数据，可以视为block的索引；Extra部分保存的是Meta Section的偏移值。

data block的结构：

----------------------------------------------------------------------------------------------------
|             Data Section             |              Offset Section             |      Extra      |
----------------------------------------------------------------------------------------------------
| Entry #1 | Entry #2 | ... | Entry #N | Offset #1 | Offset #2 | ... | Offset #N | num_of_elements |
----------------------------------------------------------------------------------------------------

其中Data Section包含的是具体的key-value键值对，Offset Section中则是每个key-value的偏移值，可以视为key-value的索引；Extra部分则保存了block中key-value对的个数。

key-value键值对的结构：

---------------------------------------------------------------------------
|                             Entry #1                              | ... |
---------------------------------------------------------------------------
| key_len (2B) | key (key_len) | value_len (2B) | value (value_len) | ... |
---------------------------------------------------------------------------

上述结构都只介绍了核心的组件，实际上还有一些附加的信息，具体来看各个部分结构体的定义。

block的结构体：

pub struct Block {
		 // 序列化后的data section
    pub(crate) data: Vec<u8>,
    // 序列化后的offset section
    pub(crate) offsets: Vec<u16>,
}

block相关的方法：

// 将整个block对象序列化为字节数组
fn encode(&self) -> Bytes
// 从字节数组反序列化得到block对象
fn decode(data: &[u8]) -> Self

blockmeta保存的是对应block的元数据信息，其结构体定义：

pub struct BlockMeta {
    // block的在sstable中的偏移
    pub offset: usize,
    // block中的第一个key（最小的key）
    pub first_key: KeyBytes,
    // block中的最后一个key（最大的key）
    pub last_key: KeyBytes,
}

blockmeta相关的方法：

// 将blockmeta数组序列化成字节数组
fn encode_block_meta(block_meta: &[BlockMeta], max_ts: u64, buf: &mut Vec<u8>)
// 将Meta Section字节数组反序列化成blockmeta数组
fn decode_block_meta(mut buf: &[u8]) -> Result<(Vec<BlockMeta>, u64)>

sstable的结构体：

pub struct SsTable {
    // sstable对应的磁盘中的文件
    pub(crate) file: FileObject, 
    // meta section对应的block的元数据列表
    pub(crate) block_meta: Vec<BlockMeta>,
    // meta section的偏移值
    pub(crate) block_meta_offset: usize,
    // sstable id
    id: usize,
    // 内存中缓存的block，用来快速检索block
    block_cache: Option<Arc<BlockCache>>,
    // sstable中的最小key，起始位置
    first_key: KeyBytes,
    // sstable中的最大key，末尾位置
    last_key: KeyBytes,
    // bloom过滤器，用来快速检索key是否存在
    pub(crate) bloom: Option<Bloom>,
    // sstable中最后一次修改的时间戳
    max_ts: u64,
}

sstable相关的方法：

// 构造函数：打开ssatble文件，初始化sstable对象
fn open(id: usize, block_cache: Option<Arc<BlockCache>>, file: FileObject) -> Result<Self>
// 根据block索引从block cache或者sstable中读取对应的block
fn read_block(&self, block_idx: usize) -> Result<Arc<Block>>
// 查找key所在的block索引
fn find_block_idx(&self, key: KeySlice) -> usize

WAL

wal（write-ahead-log）用来持久化保存对LSM的修改日志，每一次操作都会先被记录并持久化到wal中，之后才会被提交到LSM结构修改，这样保证存储引擎宕机时不会发生数据的丢失。wal的日志持久化格式为：

------------------------------------------------------------------------------------------------------------
|                                          WAL Record #1                                             | ... |
------------------------------------------------------------------------------------------------------------
| key_len (2B) | key (key_len) | timestamp (8B) | value_len (2B) | value (value_len) | checksum (4B) | ... |
------------------------------------------------------------------------------------------------------------

wal的结构体：

pub struct Wal {
		// 持久化的日志文件
    file: Arc<Mutex<BufWriter<File>>>,
}

wal相关方法：

// 构造函数：创建wal文件
fn create(path: impl AsRef<Path>) -> Result<Self>
// 根据wal日志恢复memtable
fn recover(path: impl AsRef<Path>, skiplist: &SkipMap<KeyBytes, Bytes>) -> Result<Self>
// 向wal日志中添加修改记录
fn put(&self, key: KeySlice, value: &[u8]) -> Result<()>

Manifest

manifest记录LSM在内存中的数据（memtable、compaction任务等）与持久化后的文件的对应关系，通常用json格式保存，以便在系统重启的时候能够恢复到正常的状态。

manifest的结构体：

pub struct Manifest {
		 // manifest文件
    file: Arc<Mutex<File>>,
}

// manifest保存的内存数据类型
// 每种类型都包含一个json对象
pub enum ManifestRecord {
		// level0层所有的sstable id
    Flush(usize),
    // 创建过的所有memtable id
    NewMemtable(usize),
    // 执行过compaction的所有sstable id
    Compaction(CompactionTask, Vec<usize>),
}

manifest的存储格式如下，其中slice保存的是序列化后的json对象

--------------------------------------------------------------
|                 Manifest Record #1                   | ... |
--------------------------------------------------------------
| len (8B) | serialized json obj (len) | checksum (4B) | ... |
--------------------------------------------------------------

manifest相关方法：

// 构造函数，创建一个新的manifest文件
fn create(path: impl AsRef<Path>) -> Result<Self>
// 从manifest文件中恢复得到ManifestRecord列表
fn recover(path: impl AsRef<Path>) -> Result<(Self, Vec<ManifestRecord>)>
// 向manifest文件中添加一条ManifestRecord
fn add_record(&self, _state_lock_observer: &MutexGuard<()>, record: ManifestRecord) -> Result<()>
上次编辑于: 2024/11/9 12:55:30