Scaling Concurrent Log-Structured Data Stores
如上图所示, LSM-DS的模型可以抽象成上图的形式, 任何数据的读写请求, 都会涉及Pd, Pm和P'm这三个指针, 同时后台的compact任务也需要访问和修改这3个指针. 那么这样一来, 这三个指针就必须进行一些同步的操作来保证正确性, 这篇论文的核心就是提供了一组算法来最大化的降低锁竞争和提升并发度, 进而提升性能. 上图中抽象的模型和三个指针的含义非常容易理解, 大家看图中的描述文字吧, 就不多解释了.
为了实现高并发, 论文设计了两个钩子函数, 分别是beforeMerge和afterMerge, 在compact(或者说merge)之前和之后调用. compact过程(或者说merge过程)结束之后, 返回一个新的指针指向disk的component, 并且作为参数传递给afterMerge函数. 如果内存中的memtable是多线程安全的, 那么get请求无须加锁, 因为即使在get操作过程中, 这3个指针发生了变化, 那么也不影响正确性, 最坏情况是有些component被访问了两次. 但是put操作就需要精心设计了, 防止put数据到无效的内存component上. 为此论文引入了读写锁来对读写操作进行同步控制. 基本的算法如下图所示:
上面的算法没有考虑snapshot的功能, 类似levelDB, 我们可以用时间戳来实现snapshot功能, 但是引入snapshot功能之后, 算法需要考虑更多关于snapshot的细节, 优化之后的算法如下图:
需要一个额外的active表来记录所有被snapshot的timestampput的流程没有太大的变化, 仅仅是在插入memtable之后, 多了一个getTs()的函数调用, 返回合适的ts, 并且把ts从active表中删除多了一个GetSnap函数, 论文中详细解释了如果只选择当前时间直接作为snapshot timestamp的问题, 本质上就是因为get或者put操作需要持续一段时间, 所以算法进行了优化来解决这个问题. 方法就是维护active表, 当然active表尽可能lockfree来做到nonblocking. getSnap会选择比所有active表里timestamp都小的一个作为timestamp. 考虑到getSnap也支持并发操作, 需要仔细更新snapTime变量, 为此引入了CAS操作.getTs操作会选择大于snapTime的最小timestamp返回snapshot的功能让原本简单的流程复杂化了, 论文中还给出了read-modify-write的算法, 详细算法大家阅读论文吧. 在实现上, cLSM基于levelDB修改了代码. levelDB使用了一个全局mutex来保护临界区, 因为只有单个写线程, 所以没有引入类似active表这样复杂的机制. cLSM使用上述算法支持了原生levelDB的所有接口, 尽可能的消除了代码中需要block的地方. 由于cLSM消除了单个写线程的限制, 所以log中的数据可能会出现无序现象, 不过由于每个item都关联了timestamp, 所以按照时间来recover日志也非常容易.
总结下, 论文通过巧妙的设计并发控制算法, 最大限度的减少了代码的临界区, 提升了读写并发度. 不过我认为支持并发写对性能提升帮助不大, 因为不管是SSD还是机器硬盘, 顺序写的性能都要高于并发写. 对于读性能提升来说, 从论文中给出的数据来看效果不错, 提升了一倍以上, 不过这只限于当数据读请求的瓶颈到达CPU的时候, 因为绝大部分瓶颈都在存储设备上而不是CPU. 所以整体上看论文的研究成果实用性不是特别强, 仅仅对少量情况有性能提升的效果和优势, 另外这篇论文的正确性缺乏论证, 如果论文能够提供一份机遇TLA+的形式化证明, 可能就更完善了.
PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees
这篇论文发表在2017年的SOSP上, 读完之后发现论文的思路和dostoevsky有异曲同工之妙. 我们知道LSM的模型主要的写放大在于compact, 特别是对于类似levelDB这种leveling compact style来说, 需要多次读写level i和level i+1的数据, 因此会引入更多的IO操作. 为此RocksDB引入了tiering compact style, 仅仅在同一个level上进行compact, 不引入层与层之间的compact. 但是这种策略对读请求来说却非常不友好, 因为每次读需求多次IO.
