wiscKey论文精读
wiscKey论文精读
- 经典的LSM实现-LevelDB
- 机遇与挑战
- KV分离对SSD的优化
- KV分离带来的挑战
- 实现细节
- 优化与改进
经典的LSM实现-LevelDB
适合磁盘的索引结构通常有两种,一种是就地更新(B+Tree),一种是非就地更新(LSM)。就地更新的索引结构拥有最好的读性能(随机读与顺序读)，而随机写性能很差，无法满足现实工业中的工作负载要求。而非就地更新的索引结构-LSM充分发挥顺序写入的高性能特性，成为写入密集的数据系统的基础。
顺序写入的写操作时间复杂度为O(1)，但是带来的第一个问题就是同一个key会占用多个存储空间(更新操作)，直观的想法就是有一个无限大的文件可以无限追加数据。那么读取数据就需要从尾部一直读取到头部，找到的第一个key就返回，但是假设第一个key写入后从未更新那么想要读取此key每次就要读取全量的数据其读取复杂度为O(n)，n为写入次数，同时范围查询就需要磁盘排序后输出O(NLogN)
第一个优化想法就是合并这个无限大的文件，将被覆盖的key清理掉，只保留最新的key，但这样就不能在一个文件中操作(你不能边压缩边更新,类似GC)，因此需要将文件分段。
每次合并本质上是一次归并排序的过程(为了支持范围查询，以及空间压缩)，那么就需要找到所有分段文件中有重合范围的文件，进行合并(min_key与max_key)。并且不能合并一个正在写入的文件(假设按大小划分文件)。
为了降低读取的复杂度，第一个想法就是利用内存，将最近最新写入的kv存储在内存数据结构中，红黑树，跳表等。 那么问题是何时将此数据结构dump到磁盘?最简单的是根据其大小的区别，然而在dump之前我们不能继续向其中写入数据，因此在内存中应该存在一个活跃内存表和一个不变内存表，二者相互交替，周期性的将不变内存表dump到内存中形成一个分段文件。
但这还不够，依旧没有解决最先写入且从未更新的key要读取全量数据的问题，为解决这个问题LSM结构引入了分层设计的思想。将所有的kv文件分为c0-ck 共k+1层。c0层是直接从不变的内存表中dump下的结果。而c1-ck是发生过合并的文件。由于ci+1 是ci中具有重叠部分的文件合并的产物，因此可以说在同一层内是不存在重叠key的，因为重叠key已经在其上一层被合并了。那么只有c0层是可能存在重叠的文件的。所以当要读取磁盘上的数据时，最坏情况下只需要读取c0的所有文件以及c1-ck每一层中的一个文件即c0+k个文件即可找到key的位置，分层合并思想使得非就地更新索引在常数次的IO中读取数据。
通常c0文件定义为2M，每一级比上一级大一个数量级的文件大小。所以高层的文件难以被一次性的加载到内存，因此需要一定的磁盘索引机制。我们对每个磁盘文件进行布局设计，分为元数据块，索引块，数据块三大块。元数据块中存储布隆过滤器快速的判断这个文件中是否存在某个key，同时通过对排序索引(通常缓存在内存中)二分查找定位key所在磁盘的位置。进而加速读取的速度，我们叫这种数据文件为SSTABLE(字符串排序表)。
为了标记哪些SStable属于那一层因此要存在一个sstable的元数据管理文件，在levelDB中叫做MANIFEST文件。其中存储每一个sstable的文件名，所属的级别，最大与最小key的前缀。
作为一个DB引擎，必须保证数据库进程崩溃前后的数据一致性，常见的做法就是使用预写日志。
将所有的操作记录在一个仅追加的log文件中(称之为WAL)，所有的写入操作都要保证写入WAL成功后才能继续，因此当数据库崩溃后写入WAL的操作将被回溯，反之则被丢弃(只有写入WAL成功才会回复客户端ack)。那么从尾部重放这个WAL文件的操作即可恢复DB。
但是这个过程由于会消耗磁盘的空间因此也需要不断的进行压缩，同时如果WAL过大也会使得数据库恢复的时间增大这是不可接受的，为此我们需要支持checkpoint特性。
机遇与挑战