LSM
wiscKey论文精读 - 飞书云文档
经典LSM实现-LevelDB
适合磁盘索引的结构通常有俩中，一种是就地更新B+，一种是就地更新LSM。
B+树读取性能更好，B+树随机写入很差，LSM写入性能更好。接下来内容都讨论LSM Tree。
最直观的想法是将随机写入改成顺序写入，最简答的方法就是假设一个无限大小的文件，每次kv为一组，一直向后追加。这样会引出几个问题。
同一个key可能被写入多次，更早的key就无效了，会浪费磁盘空间。读取的性能是不可接受的，读取一个数据可能要扫描全部文件。
一个简单的优化想法就是合并这个无限大的文件，将被覆盖的key清理掉，只保留最新的key，但这样就不能在一个文件中操作（不能将压缩过程变成更新，类似GC），因此需要将文件分段。
每次合并本质上就是一个归并排序的过程（为了支持范围查询，以及空间压缩），那么就需要找到所有分段文件中有重合范围的文件，进行合并。而且不能合并一个正在写入的文件。
为了降低读取的复杂度，第一个想法就是使用内存，将最近新写入的kv存储在内存数据结构中，红黑树，跳表等。那么问题是合适将数据结构dump到磁盘？最简单的是根据其大小的区别，然而在dump之前我们不能继续向其中写数据。为了更好的确定内存中的数据结构什么时候应该被写入，我们应该在内存中维护一个不变内存表和活跃内存表，周期性的将不变内存表dump到内存中形成一个文件。
这些都没有解决最先写入且从未更新的key尧都区全量数据的问题，为解决这个问题LSM结构引入了分层的思想。由于我们区分了不变内存，因此从内存dump到磁盘的文件一定是有序的。L0中每个文件内是不会出现重复的现象，但是文件之间可能是乱序的。
从L1开始，每个层级内的SSTable文件必须保证Key范围有序且不重叠。这是通过compaction实现的。
我们假设直接从内存写入磁盘的文件为第0层，从第0层合并数据到第二层。那么从c1-ck层，他们的数据只会出现一次。而c1-ck是发生过合并的文件。由于ci+1 是ci中具有重叠部分的文件合并的产物，因此可以说在同一层内是不存在重叠key的，因为重叠key已经在其上一层被合并了。那么只有c0层是可能存在重叠的文件的。所以当要读取磁盘上的数据时，最坏情况下只需要读取c0的所有文件以及c1-ck每一层中的一个文件即c0+k个文件即可找到key的位置，分层合并思想使得非就地更新索引在常数次的IO中读取数据。
L1 的每个文件负责的 Key 范围是 由 Compaction 动态划分的，而非预先固定。例如：
如果 L0 和 L1 的合并数据覆盖 [a, z]，Compaction 可能将其拆分为多个文件（如 [a, g]、[h, m]、[n, z]），每个文件大小接近 target_file_size（默认 2MB）。
LSM tree中，文件更新完全通过原子替换实现。
L1和L2的归并步骤
- 选择 L1 层的所有 SSTable 文件
- 选择 L2 层中与 L1 层有键范围重叠的 SSTable 文件
- 对这些文件进行多路归并排序
- 生成新的 L2 层 SSTable 文件
- 删除旧的 L1 和 L2 层参与合并的文件
leveldb最多有8层，假设第0层最多6个文件，我们只需要读取14个文件就能找到一个key。
用户在读取同一个key的时候，只要读取最上面的最新版本即可。简单来说，同一层只有一个相同的key，但是不同层可能有多个相同的key的（不同版本）。
在一个巨大的日志文件中找一个key也是很难的，leveldb中有三个模块，元数据区，索引区，数据表。
元数据区存在布隆过滤器，可以直接判断key是不是在当前文件。布隆过滤器存在假阳，当假阳发生时，需要读取索引块。这个索引存储了key和对应value的偏移量，可以直接在内存中进行二分查找。实际上存储数据的结构叫做sstable。
为了标记哪些SStable属于哪一层，因此要存在一个sstable的元数据管理文件，在levelDB中叫做MANIFEST文件。其中存储每一个sstable的文件名，所属的级别，最大与最小的key的前缀。
LSM树中，一层有多个文件，这允许多个文件进行并行写入操作，小文件可以独立合并，避免每次合并都要重写整个层的数据。小规模更新对系统影响小，且每个层都可以维护自己的布隆过滤器。
LSM tree优化方向
LSM 是牺牲读取性能和空间利用率为代价，换取写入性能的。因此，对LSM的结构优化目标就是想办法提高读取性能和空间录用率。
KV分离对SSD的优化
SSD上引用LSM技术带来俩个问题，第一写放大缩短了SSD寿命，第二传统LSM无法充分发挥SSD的并行写入特性。
相较于机械硬盘，随机读取与顺序读取的性能在固态上没有那么显著。意味着过分追求顺序读取而进行的激进优化是没有必要的。其中最明显的就是将key和value放在一个文件内（sstable），在机械硬盘上这种结构能保证一次读取就获得数据，减少了磁头的寻道次数，而对于固态哟安这样会导致合并压缩过程中，对同意kv进行多次写入与移动，从而降低了SSD的寿命。虽然也是读取一次但对于固态硬盘来说两次读取也要快于机械硬盘一次读取，而为了有效的减少LSM造成的读写放大，wisckey中将key与value分离存储，value仅存储在vlog中以仅追加的方式，而key存储在之前的lsm tree结构中。专业带来了俩个好处。不需要频繁的移动value的值，所以写放大减少，LSM存储固定大小的key使得其存储占用变小，在内存中可以同时存储更多的key进而提高了key的数据量，间接降低了读放大问题。
对于范围查询，由于真正的value都存储在vLog中因此是无序的，所以进行范围查询就是需要进行随机读取（先从LSM顺序读key再随机读value），这必然会造成性能的下降，传统的随机读取是串行的难以发生固态并行随机读取的特性，因此在wisckey中根据迭代器方法调用prev，next来排序号lsm中读取一定的key到内存中，加速 随机的范围查询性能，这种读取是异步进行的，充分发挥固态硬盘的并行读取性能。
实现细节工程优化
kv分离带来的挑战
kv分离会导致vLog文件不断增大，那么就需要合并，如何合并才能保证对性能的影响最小化？同时由于移动了value的位置，LSM结构中维护的value的位置信息也需要更新。数据具体如何布局？VLog日志如何拆分？Wisckey崩溃后如何才能保证数据一致性
在sstable文件中数据布局: <key, addr(vlogName,offset,size)>
在vlog文件中的数据布局: <keySize,valueSize,key,Value>
这里的key是一个固定大小的字符串，addr是一个地址指针应该是一个64或者128的int值。
value log中存储了 key大小（确定读取程度）值大小，key和value的具体值。这里再将key存放一遍是为了故障恢复需要使用。
随机点查：
- 先访问内存表是否命中key，如果找到地址信息判断是在内存中还是磁盘中(LRU缓存)
- 在内存中被缓存了value则直接返回，否则去磁盘中查找，根据vlog的名字找到具体的vlog文件
- 然后根据offset定位字节的首地址，根据size读取内容并返回
- 基于一定策略将整个vlog涉及的bolck缓存下来
范围查询，会返回一个迭代器。
- 根据迭代器 next 还是 prev判断 是在游标之前读还是之后读，
- 预先读取一定的key，交由底层的线程池异步的取ssd中获取数据
- 将异步结果缓存在内存中 等到迭代器的调用
随机、顺序写入
- 将set写操作写入vlog日志中（存储key的作用之一就是即作为预写日志，又作为值日志）
- 将返回的地址信息写入LSM中返回
- 写入返回成功
合并压缩
head是最后写的，tail是最早写的
其中合并后得到的新value log文件，可能在之后仍需要被再次合并
- Vlog分为多个文件，其中存在一个活跃vlog文件，用于写入数据最为head地址。（有些类似kafka，会又活跃的vlog）
- 最先写入的日志在最后（早）的vlog中，存在tail地址。
- 多个写入线程在head地址出追加日志
- 而只有一个后台执行收集运行在尾部
- 每次选择一个vlog文件的内容去lsm结构中随机查询（可并行化）将没有失效的key重新写回到head地址出重新追加到vlog中。
- 然后更新lsm中这些key的新地址
- 并释放老的vlog文件
- 这一过程中需要先将数据写入新的vlog文件后，刷新到固态硬盘后一步更新索引。
- 最后扇出老文件，保证次过程中进程崩溃不会造成数据丢失。
故障恢复
- wisckey的设计中预写日志就是值日志
- 因此引擎进程只需要定时保存head和tail的地址即可
- 数据库恢复时需要获取崩溃前最新的地址然后从tail到head将日志进行redo即可（会有检查点的操作）
同时为了保证一致性查询，在查询key时要做一些必要的一致性就爱你差
- 当前key如果在tail预head索引范围外则忽略
- 当前位置上的值具有key预查询的key不匹配则忽略
- 当发生上述情况时，引擎直接返回错误信息。
改进和优化
写缓冲区，为减少写入的系统调用次数，多个小key的写入会被缓存在内存中回去在一起同意的写入lsm的sstable中，但会优先写入vlog中当做预写日志处理。
空间放大率：数据的实际大小预逻辑上的大小比值用来衡量空间放大情况，对于固态硬盘来说，价格昂贵，降低空间放大率会节省成本
在线垃圾收集：GC过程会造成引擎的性能尖刺，通过并发的在线分批次进行的GC操作来对前台读写行的影响。
小value的存储：经过论文测试value大于4kb时读取性能才会有极大的提升，incid可以设置一个阈值，当value大于次阈值时才进行kb分离，而再次之前用传统lsm tree的格式。