CSE_lecture7:System modelling + KFS
System modelling & Key-value stores(KVS)
key-value store abstraction
key-value使用唯一的key来标识value，提供接口为get, scan, update, insert, delete，比文件系统更简单
一种想法是可以直接在filesystem上封装一层key-value store的API，key认为是文件名，value为文件的内容。使用system modelling来进行量化
system modelling
在设计系统前，建立其内部模型抽象，提炼出决定系统行为的主要组成部分，实现定性模型。相较于直觉更科学，相较于实验更加高效和普适（但不代表就不用实验了）
现在使用定性模型(qualitative system model)来分析使用filesystem的key-value store：
定义系统的目标：低延迟，并使用少量空间存储更多的数据
分析：以Insert为例，为CREATE + WRITE，共两次system call，并将system call进一步展开
现在只要知道disk read/write的latency就可以在不实现具体系统的情况下进行分析。
结论是并不高效，额外的操作太多。但实际上在value特别大时还是能够接受的。因此在system modelling时需要考虑参数(parameterized)，如static parameters（如disk read/write time）, input parameters（如key-value sizes）, runtime parameters
一般来说，key-value store用于数据大小很小的时候，因此不考虑该实现，即理想状况下只进行一次block write；另一方面这也造成了很大的空间浪费
build key-value store system
核心想法是：将多个key-value放到同一个文件中，减少空间浪费和延迟
使用filesystem而不是直接进行disk操作是因为这样更加方便，同时兼容性好
step 1: a naive key-value storage
将所有的key-value都放在一个单一文件中，以update为例，有两种方法：
- file in-place write: 根据offset进行file write来修改，这需要一次random disk write
- file append: 在文件末尾追加更新值，这一般只需要进行一次sequential disk write
比较之后，append更加高效。
insert和update类似，而delete则会append一个NULL entry，后续进行垃圾回收
step 2: log-structure key-value stores(L-KVS)
log-structured file是append-only的
此时get操作难以高效实现，需要倒序遍历文件
step 3: L-KVS + index
加一层index组件，用于key -> offset的映射，这一层不需要持久化
step 3.1: in-memory hash index + log-structured data file
在内存维护一个map来实现key -> byte offset，问题在于index能否在内存中放下，因此需要允许index放在磁盘上
step 4: L-KVS + (in-memory & disk hybrid index)
使用fat pointer，其既可以指向虚拟内存地址，也可以指向文件的offset
当index既可能在内存中，也可能在磁盘中时，可能导致多次磁盘访问，甚至导致随机磁盘访问，因此不能使用linked-list-based hashing，改进方法为：
- 一个entry放入多个key，减小链的长度
- 使用更高级的hashing方法，如cuckoo hashing
目前的架构还有以下问题：
- log file是永远在增大的，最终导致磁盘空间用尽
- 不支持范围查找
使用compaction来防止log file无限增大，即通过压缩来删除重复的数据，但当文件特别大的时候相当耗时
因此将文件分为多个segment，compaction时挑选一部分segment，并以segment的粒度来进行压缩，同时在segment之间进行merge；在compaction时还能顺便进行垃圾回收，实现删除。此时模型更加复杂了，在compact/merge时进行get性能会受限，因此建模时还需要考虑compact/merge的频率
step 4.1: L-KVS(w/ compaction & merging) + (in-memory & disk hybrid hashing index)
此时还是没有解决范围查找的问题。解决方法为使用B+树作为index，实现key的排序和高效的范围查找，但这和log-structured file不太兼容
step 5: B+ tree-based KVS
B+树中，update/insert需要多次磁盘访问，尤其是随机磁盘访问；但范围查找效果很好
step 6: SSTables(sorted string table) KVS
SSTable基于segmented log file，同时有两个更新：
- 每个segment中的key都排好序
- segment不可修改，因此不是append-only
SSTable的好处在于：
- key的查找很高效：index只存放一部分key的offset，实际查找时夹逼即可
- 支持segment里的范围查找
使用memtable来实现内存的修改，从而将SSTable的修改batch在一起。以insert为例：
- 在memtable中insert
- 当memtable大到一定程度后，排序并写入SSTable
- 当SSTable过多时，进行compact + merge
而查找时，先在memtable查找，再依序查找SSTable，可以在每个SSTable上保留一个稀疏的in-memory index来进行优化
范围查找则需要segment之间也进行排序
SSTable不应当简单地顺序存储，因此还需要优化
step 7: LSM trees
将SSTable摆放为多层架构，除了L0之外，每层的文件都排好序，且没有重复的key；上层的数据比下层的数据更新
任何系统都可能出现corner case，比如LSM tree可能出现写阻塞(write stall)，这是因为前一次写入过于耗时（多次compact）导致的
对于错误处理，比如memtable丢失，可以使用log来恢复memtable
相较于B+ tree，好处是写的性能更好，坏处是range性能稍差