项目地址：https://github.com/skyzh/mini-lsm

个人实现地址：https://gitee.com/cnyuyang/mini-lsm

Task 1-SST Builder

在此任务中，您需要修改：

src/table/builder.rs

src/table.rs

SST由存储在磁盘上的数据块和索引块组成。通常，数据块都是懒加载的-直到用户发出请求，它们才会被加载到内存中。索引块也可以按需加载，但在本教程中，我们简单假设所有SST索引块（元信息块）都可以放入内存（实际上我们没有索引块的实现）。通常，SST文件的大小为256MB。

SST构建器类似于之前实现的<code>BlockBuilder——用户将在构建器上调用add。你应该在SST builder中维护一个BlockBuilder，并在必要时拆分块。此外，你还需要维护块元数据BlockMeta，其中包括每个块中的第一个/最后一个键以及每个块的偏移量。build函数将对SST进行编码，使用FileObject::create将所有内容写入磁盘，并返回一个SsTable对象。

SST的编码如下：

-------------------------------------------------------------------------------------------

| Block Section | Meta Section | Extra |

-------------------------------------------------------------------------------------------

| data block | ... | data block | metadata | meta block offset (u32) |

-------------------------------------------------------------------------------------------

timate_size函数

你还需要实现SsTableBuilder的es，这样调用者就可以知道什么时候可以开始一个新的SST来写入数据。函数不需要非常精确。假设数据块数据量远远大于元数据块，我们可以简单地返回数据块的大小为estimate_size。

除了SST构建器，你还需要完成块元数据的编码/解码，以便SsTableBuilder::build可以生成有效的SST文件。

BlockMeta的编码与解码

先实现元信息的编码与解码。

如图所示就是将内存中的<code>BlockMeta数组写入到磁盘中，同时能将磁盘中的二进制信息还原回来。

编码

先添加BlockMeta的个数，在写入每个BlockMeta，因为first_key和last_key是可变长的字符串类型，所有需要添加长度信息保证正常解码。

pub fn encode_block_meta(

block_meta: &[BlockMeta],

#[allow(clippy::ptr_arg)] // remove this allow after you finish

buf: &mut Vec<u8>,

) {

buf.put_u32(block_meta.len() as u32);

for meta in block_meta {

buf.put_u32(meta.offset as u32);

buf.put_u16(meta.first_key.len() as u16);

buf.put(meta.first_key.raw_ref());

buf.put_u16(meta.last_key.len() as u16);

buf.put(meta.last_key.raw_ref());

}

}

解码

解码就是编码的逆过程

pub fn decode_block_meta(mut buf: &[u8]) -> Vec<BlockMeta> {

let num = buf.get_u32();

let mut block_meta: Vec<BlockMeta> = Vec::with_capacity(num as usize);

for i in 0..num {

let offset: usize = buf.get_u32() as usize;

let first_key_len = buf.get_u16();

let first_key = KeyBytes::from_bytes(buf.copy_to_bytes(first_key_len as usize));

let last_key_len = buf.get_u16();

let last_key = KeyBytes::from_bytes(buf.copy_to_bytes(last_key_len as usize));

block_meta.push(BlockMeta {

offset,

first_key,

last_key,

})

}

block_meta

}

SsTableBuilder建造者

成员变量&构造函数

• builder:BlockBuilder
• first_key:存储的第一个key，用于加快查找
• last_key:存储的最后一个key，用于加快查找
• data:Block编码后的数据
• meta:元信息
• block_size:每个Block的大小

构造函数：

pub fn new(block_size: usize) -> Self {

SsTableBuilder {

builder: BlockBuilder::new(block_size),

first_key: Vec::new(),

last_key: Vec::new(),

data: Vec::new(),

meta: Vec::new(),

block_size,

}

}

finish_block

存在两种情况可能，可能会新生成一个Block用于存储数据：

• Block存不数据
• SsTableBuilder调用build生成SsTable，不再新增数据

fn finish_block(&mut self) {

let builder = std::mem::replace(&mut self.builder, BlockBuilder::new(self.block_size));

let encoded_block = builder.build().encode();

self.meta.push(BlockMeta {

offset: self.data.len(),

first_key: KeyBytes::from_bytes(self.first_key.clone().into()),

last_key: KeyBytes::from_bytes(self.last_key.clone().into()),

});

self.data.append(&mut encoded_block.to_vec())

}

先使用std::mem::replace将self.builder中的数据替换成空的对象，将存满数据的对象返回赋值给builder。

调用builder的build()函数生成Block对象，再调用encode()编码出二进制数据encoded_block。

将元信息添加进meta中，将编码后的二进制数据添加进data。

add操作

pub fn add(&mut self, key: KeySlice, value: &[u8]) {

if self.first_key.is_empty() {

self.first_key = Bytes::copy_from_slice(key.raw_ref()).into();

}

self.last_key = Bytes::copy_from_slice(key.raw_ref()).into();

if !self.builder.add(key, value) {

self.finish_block();

self.builder.add(key, value);

}

}

判断当前Block块能否添加进当前Block，如果不能则调用上述finish_block函数，再进行添加。同时保存用于每个Block的first_key、last_key。

pub fn add(&mut self, key: KeySlice, value: &[u8]) {

if self.first_key.is_empty() {

self.first_key = Bytes::copy_from_slice(key.raw_ref()).into();

}

if !self.builder.add(key, value) {

self.finish_block();

self.builder.add(key, value);

self.first_key = Bytes::copy_from_slice(key.raw_ref()).into();

}

self.last_key = Bytes::copy_from_slice(key.raw_ref()).into();

}

build操作

就是将SsTableBuilder建造者中保存的数据，写入磁盘：

pub fn build(

mut self,

id: usize,

block_cache: Option<Arc<BlockCache>>,

path: impl AsRef<Path>,

) -> Result<SsTable> {

self.finish_block();

let mut buf = self.data;

let meta_offset = buf.len();

BlockMeta::encode_block_meta(&self.meta, &mut buf);

buf.put_u32(meta_offset as u32);

let file = FileObject::create(path.as_ref(), buf)?;

Ok(SsTable {

id,

file,

first_key: self.meta.first().unwrap().first_key.clone(),

last_key: self.meta.last().unwrap().last_key.clone(),

block_meta: self.meta,

block_meta_offset: meta_offset,

block_cache,

bloom: None,

max_ts: 0,

})

}

按照文档说明先写入数据部分，再写入元数据部分，最后写入元数据的偏移距离。

SsTable读取

就是编码的逆过程，即SsTable对象的open方法：

pub fn open(id: usize, block_cache: Option<Arc<BlockCache>>, file: FileObject) -> Result<Self> {

let len = file.1;

let meta_block_offset = (&file.read(len - 4, 4)?[..]).get_u32();

let len = len - meta_block_offset as u64 - 4;

let meta_block = &file.read(meta_block_offset as u64, len)?[..];

let block_meta = BlockMeta::decode_block_meta(meta_block);

Ok(SsTable {

file,

block_meta_offset: meta_block_offset as usize,

id,

block_cache,

first_key: block_meta.first().unwrap().first_key.clone(),

last_key: block_meta.last().unwrap().last_key.clone(),

bloom: None,

block_meta: block_meta,

max_ts: 0,

})

}

Task 2-SST Iterator

在此任务中，您需要修改：

src/table/iterator.rs

src/table.rs

与BlockIterator类似，您需要在SST上实现一个迭代器。请注意，您应该按需加载数据。例如，如果您的迭代器位于块1，则在到达下一个块之前，不应该在内存中保存任何其他块内容。

SsTableIterator应该实现StorageIterator特性，以便将来可以与其他迭代器组合使用。

有一点需要注意的是find_to_key函数。基本上，您需要对块元数据执行二进制搜索，以找到可能包含键的块。有可能key在LSM树中不存在，所以块迭代器在一次查找后立即失效。例如：

--------------------------------------

| block 1 | block 2 | block meta |

--------------------------------------

| a, b, c | e, f, g | 1: a/c, 2: e/g |

--------------------------------------

我们建议只使用每个块的第一个键来执行二分查找，以降低实现的复杂性。如果我们在这个SST中查找b，则相当简单——使用二分查找，我们可以知道块1包含键a<=keys<e。因此，我们加载块1，并寻找块迭代器到对应的位置。

但是，如果我们要寻找d，我们将定位到块1，如果我们仅使用first key作为二分查找条件，但在块1中寻找d将到达块的末尾。因此，我们应该在查找之后检查迭代器是否无效，必要时切换到下一个块。或者您可以利用最后一个关键元数据直接定位到正确的块，这取决于您。

seek_to_first

create_and_seek_to_first与之类似，就是读取0号block块，调用BlockIterator::create_and_seek_to_first方法生成BlockIterator：

pub fn seek_to_first(&mut self) -> Result<()> {

self.blk_iter = BlockIterator::create_and_seek_to_first(self.table.read_block(0)?);

self.blk_idx = 0;

Ok(())

}

seek_to_key

create_and_seek_to_key与之类似，有以下两种情况：

1. 找到第一个不满足key < first_key的，本block中存在大于key

2. 找到第一个不满足<code>key < first_key的，本block中不存在大于key，需要跳转下一个block

<code>pub fn seek_to_key(&mut self, key: KeySlice) -> Result<()> {

let mut index = self.table.find_block_idx(key);

self.blk_iter = BlockIterator::create_and_seek_to_key(self.table.read_block(index)?, key);

if !self.blk_iter.is_valid() && index != self.table.num_of_blocks() - 1 {

index += 1;

self.blk_iter = BlockIterator::create_and_seek_to_first(self.table.read_block(index)?);

}

self.blk_idx = index;

Ok(())

}

find_block_idx

在刚刚的函数实现中，需要为SsTable对象实现find_block_idx方法。找到最后一个first_key <= key的block：

pub fn find_block_idx(&self, key: KeySlice) -> usize {

self.block_meta

.partition_point(|meta| meta.first_key.as_key_slice() <= key)

.saturating_sub(1)

}

• partition_point：常用于迭代器上，它用来找出迭代器中满足某个条件的元素与不满足该条件的元素之间的分界点。此函数返回的是一个索引值，指示了第一个不满足给定谓词（predicate）的元素的位置。
• saturating_sub：用于执行饱和减法。饱和减法是指当减法操作的结果超出类型的表示范围时，结果会被“饱和”到该类型的边界值。

Task 3-Block Cache

在此任务中，您需要修改：

src/table/iterator.rs

src/table.rs

你可以在SsTable上实现一个新的read_block_cached函数。

我们使用moka-rs作为我们的块缓存实现。块以(sst_id,block_id)作为缓存键进行缓存。您可以使用try_get_with从缓存中获取块（如果命中缓存）或者填充缓存（如果未命中缓存）。如果有多个请求读取相同的块并且缓存未命中，则try_get_with将仅向磁盘发出单个读取请求，并将结果广播给所有请求。

在这一点上，你可以修改任务二SST Iterator使用read_block_cached而不是read_block来利用块缓存。

moka-rs

moka 是一个流行的 Rust 第三方库，主要用于提供高性能的缓存解决方案。它被广泛应用于需要快速访问数据的应用场景，比如 Web 服务器、数据库系统和其他对性能有高要求的服务。

主要特点

• 高性能：moka 使用高效的内存分配策略和并发控制机制来实现低延迟和高吞吐量。
• 线程安全：它提供了线程安全的缓存实现，可以轻松地在多线程环境中使用。
• 多种容量限制：moka 支持基于条目数量或总字节数的缓存容量限制。
• LRU 缓存淘汰策略：默认情况下，moka 使用最近最少使用 (Least Recently Used, LRU) 算法来管理缓存中的条目。

使用示例

下面是一个简单的使用示例，创建一个线程安全的缓存，并添加一些键值对：

use moka::sync::Cache;

fn main() {

// 创建一个缓存实例，设置最大容量为 100 个条目

let cache: Cache<String, String> = Cache::new(100);

// 插入一些键值对

cache.insert("key1".to_string(), "value1".to_string());

cache.insert("key2".to_string(), "value2".to_string());

// 获取缓存中的值

if let Some(value) = cache.get("key1") {

println!("Value of key1: {}", value);

} else {

println!("Key1 not found");

}

// 清除缓存

cache.clear();

}

try_get_with

try_get_with 方法是一种在缓存中查找键对应的值的方法，如果键不在缓存中，则会尝试使用一个闭包来计算该值，并将其插入缓存。这个方法对于避免重复计算和提高性能特别有用，因为它可以确保每个键只被计算一次。

read_block_cached

先使用if let获取block_cache的值，再使用try_get_with获取/插入新数据。

pub fn read_block_cached(&self, block_idx: usize) -> Result<Arc<Block>> {

if let Some(ref block_cache) = self.block_cache {

let blk = block_cache

.try_get_with((self.id, block_idx), || self.read_block(block_idx))

.map_err(|e| anyhow!("{}", e))?;

Ok(blk)

} else {

return self.read_block(block_idx);

}

}