课程实验：分布式Key值存储系统

Task1：LSM Tree源码阅读和分析

github链接：https://github.com/HuangDunD/RucDDBS

任务：阅读 src/storage 和 include/storage 部分的代码并完成代码分析报告

Main Data Structure

Block

Block类有以下成员函数：

1. Block(const std::string &block_content)：构造函数，接受一个字符串参数，是包含某种数据块的字符串。
2. get(const std::string &key) const：接受一个Key作为参数，返回一个包含布尔值和字符串的对。这是用于从数据块中获取特定Key的值。
3. NewIterator() const：返回一个指向Iterator的std::unique_ptr。这是用于遍历数据块的迭代器。
4. extract(uint64_t position, uint64_t *size, std::string &s) const：接受一个位置、一个大小指针和一个字符串引用作为参数。这是用于从数据块的特定位置提取数据的函数。

此外，Block类还有一个私有成员变量block_content_，这是存储数据块内容的字符串。

注意，复制构造函数和赋值运算符被禁用，这意味着不能复制Block类的实例。这是因为Block类的实例包含大量数据，复制它们会消耗大量内存。

Entry

Entry 是一个KV结构的struct，存放key_,value_

SSTable

SSTable是用来存放Block的一个表，实现了以下接口

1. SSTable: 构造函数，接收一个ifstream，一个BlockCache。它文件的末尾读取索引的偏移量和大小，然后加载索引块并创建一个新的迭代器。
2. loadBlock 方法用于从给定的偏移量和大小加载一个块。它从文件中读取块的数据。如果块是压缩的，它会使用snappy库进行解压缩。
3. get 方法用于从SSTable中获取一个Key的值。它使用索引迭代器来查找包含该Key的块。如果找到了包含Key的块，它会从块中获取Key的值。如果没有找到包含Key的块，它会返回一个表示失败的对。

LevelZero

LevelZero是对LST Tree DiskStorage的抽象，集成了DiskStorage面向的服务

支持 add,search,save_meta等功能

• add方法：将memtable中的KV创建新的SSTable。这是将内存中的数据持久化到磁盘的过程。
• search方法：在LevelZero中查找指定的键。
• size方法：返回LevelZero的大小。
• save_meta方法：保存元数据。涉及到将内存中的数据写入磁盘。

DiskStorage

集成了LevelZero的disk layer服务，为 LST Tree的Disk部分，向上级提供服务。

1. add方法接受一个SkipList类型的参数memtable，将其添加到level0_中，并将no_的值加1。no_是一个用于跟踪添加操作的计数器。如果level0_溢出，需要调用一个合并函数（在这段代码中并未显示）。每次添加操作后，都会调用save_meta方法保存元数据。

2. search方法接受一个字符串key作为参数，返回在level0_中搜索key的结果。返回类型是一个包含布尔值和字符串的对，布尔值表示是否找到了键，字符串则是键对应的值。

3. read_meta方法用于读取元数据。如果元数据文件存在，它会打开文件并读取一个uint64_t类型的值到no_。如果元数据文件不存在，它会将no_设置为0，并调用save_meta方法保存元数据。

4. save_meta方法用于保存元数据。它会打开元数据文件，并将no_的值作为字节流写入文件

SkipList

该类用于做内存中的mmtable，利用跳表为链表建立了多级索引，加速了CRUD速度。

• put 在SkipList中插入一个新的KV。如果Key已经存在于跳跃列表中，那么就更新该Key的值；如果Key不存在，那么就创建一个新的节点。

  函数首先使用findGreatorOrEqual函数查找大于或等于给定Key的第一个节点。如果找到的节点的Key等于给定的Key，那么就更新该节点的值，并更新跳跃列表的字节大小。

  如果找到的节点的Key不等于给定的Key，那么就需要插入一个新的节点。首先，生成一个随机的height。如果生成的height大于当前的最大height，那么就需要扩大跳跃列表的height。然后，创建一个新的节点，并更新指针，使得新的节点正确地插入到跳跃列表中。最后，更新跳跃列表的条目数量和字节大小。

• get : 类似有序数组的查找，受segment的影响，平均时间为O(log(n))

• del: 先获取位置，类似链表的删除。

• enlargeHeight：由于height只影响效率，不影响正确性，仅仅加高head和tail的next array

KVStore

KVStore是面向事务的KV存储服务，支持以下操作：

1. put:接受KV对和一个事务对象。如果启用了log record，它会创建一个log并将其添加到log manager。然后，它将KV添加到内存表中。如果内存表的空间超过了预设的阈值，它会将内存表的内容添加到磁盘存储，并清空内存表。
2. del：检查 mmtable中是否有，如果有，删除并记录到log record。如果mmtable中没有，就再diskstorage中搜索，找到了先缓存到mmtable，再返回
3. reset： 清空mmtable
4. flush： 将mmtable中的值flush到diskstorage

Layer Graph

Module	SubModule	Description
KVStore	mmTable(SkipList), DiskStorage	提供整个数据存储服务最高级抽象
mmTable		内存缓冲表，用SkipList实现
DiskStorage	LevelZero	提供Disk持久化服务
LevelZero	SSTable	与Disk交互的部分，其中有多个SSTable
SSTable	Block	有序的Table，方便顺序写入Disk
Block	Entry	SSTable中存取数据的最小单位，Entry
Entry		封装KV对