面向LSM-tree结构的内存管理——从一篇Fast'14的论文说起

文/兰兆千

LSM-tree结构

LSM-Tree全称是Log Structured Merge Tree,是一种分层,有序,面向磁盘的数据结构。基于LSM-Tree的LevelDB、RocksDB与HBase等凭借其出色的写入性能与不俗的读性能,成为了众多分布式系统的存储基石。
LSM-Tree的基本思想可以概括为顺序写入与逐级压缩。如图1所示是最原始的LSM-Tree结构,数据的存储可以分为数层。最上层是由内存组成的原地更新(in place update)的排序树,下方的各层为基于磁盘块组成的数据追加(append only)的B树。
图1 LSM-Tree示意图(来源[1])

当插入Key时,会直接内存中的C0层,这一过程是十分迅速的。若C0层达到了一定的限制,则将C0与C1层进行一次压缩(Compaction),一次性写入磁盘作为新的C1层。磁盘上的相邻各块也可以进行压缩,这一压缩的过程是异步的。

对于读过程,从LSM-Tree自上而下的进行查找,直到找到对应的数据。由于上层的数据一定比下层的数据新,读过程的正确性得以保证。相比于最基本的B树,LSM-Tree写入过程更快,但读过程需要多次查询。它非常适合写比读频繁的应用场景。

RAMCloud

存储系统发展发展至今,对于速度的要求越来越高,存储介质的IO速度已经成为了瓶颈。现今越来越大的内存出现,很多基于内存的存储系统得到了更广阔的应用,如Redis和memcache等。RAMCloud就是一个基于DRAM的分布式存储系统,其架构如图2所示。整个系统由多个数据节点组成,每个节点由两部分组成,master模块基于内存,负责所有的读写请求;backup模块基于磁盘,是master模块的数据备份,是节点高可靠的保证。master和backup节点均采用LSM-Tree的结构。
图2 RAMCloud架构
RAMCloud利用了低网络延迟(比磁盘读写低)提供了高性能KV抽象的读写。对于RAMCloud的架构我们不做过多探讨,我们主要专注于探讨LSM-tree结构上内存管理的特点。

LSM-tree的内存结构的内存管理

RAMCloud在FAST’14上面发表了一篇论文[2],着重介绍了其内存管理的方法。本文认为LSM-tree的内存是一种每次申请定长或者一定范围内大小的内存块,维持一段时间后大部分进行释放并替换为更大的块的使用模式。RAMCloud舍弃了运行环境提供的内存申请方式如C的malloc,主要原因有二:

  • 通用型内存管理在LSM-tree的场景下,一般会浪费50%左右的内存空间。非拷贝的内存管理会经常造成内存空洞,对于内存块大小变化很敏感,所以内存利用率不高;拷贝式的内存管理由于需要遍历所有live data会有一些内存上的消耗。
  • GC经常会造成停机,时长经常在几百微妙到毫秒级别,已经是系统内RPC调用的几百倍,这是不可接受的。
    RAMCloud认为对于LSM-tree的内存结构来说,一个理想状态的allocator具有以下特点:
  • 拷贝式的内存分配,避免内存空洞
  • 不需要进行全局扫描,可以只进行局部扫描

RAMCloud的设计实现

所以RAMCloud提出了如下的设计:

  • 内存分成8MB大小的段(Segment),分配的对象在上面进行
  • 使用一个hashtable来记录申请的内存对象实际的内存地址
  • 选择内存空闲程度高的段进行拷贝整理,整理后释放旧的段
  • 整理时通过引用计数来判断对象是否存活
  • 内存整理是并行的

其中并行整理利用了RAMCloud内部内存使用的特点。对于LSM-tree而言,组成其C1及以下层的内存一旦被创建并写入数据后,就不会再被更改。这一特性使得并行整理的内存不必考虑整理的同时会写入的问题,极大地减小了复杂度。另一方面,用于内存地址映射的hashtable可以提供一个很简单的方式将整理后的读请求转发到新的位置。
这在整理线程(cleaner thread)和服务线程(service thread)间会产生两个同步问题问题:

  • Hash Table的冲突:服务线程需要读hash table,同时整理线程需要更新hash table,这里的冲突不可避免。RAMCloud的实现采用的是分段锁的形式。
  • 内存释放的问题:整理线程将旧内存整理到新的位置时,旧的内存可能仍然被服务线程所使用。这里采用的是等待策略,旧的内存需要等待服务线程全部执行完一次RPC操作后才进行释放重用。如何确定所有的服务线程全部执行完一次操作,利用到了另几篇文章的思想[3][4]。

另外一个关键性的问题是整理死锁问题,由于将旧内存整理至新内存块时需要有一个空闲的新内存块,如果系统处于内存不足的情况,没有新的内存块可供内存整理使用,整个系统处于死锁。RAMCloud的做法是会将内存保留一部分放在一个单独的池子里,保证旧内存在整理后释放也是先进入这个池子。
同时,由于不允许跨Segment的对象存在,内存整理可能并不会经常有效,如图3所示的是一个内存整理失败的例子。

图3 整理无进展问题

对于这种情况,需要在选择要整理的内存段时进行预估,保证最坏情况下也能够有所进展。主要是对内存段内最大的对象大小进行统计,那么压缩后每个段最多浪费这么多的内存,即可算出最多压缩后占几个段。具体不再详述。

RAMCloud的backup所带来的的问题

上述机制是仅存在master节点的情况,但对于RAMCloud而言,其使用了磁盘作为master的backup,所有的操作需要同步记录在磁盘中,这给内存整理带来了挑战。
首先有一个问题就是内存整理后,需要把整理后的内存块也更新到磁盘中,这大大降低了内存整理的效率。在这里RAMCloud引入了两层整理的概念(Two-level cleaning)。

Two-level cleaning

最大的改动是将Segment改为变长的模式,将所有内存分成小段(Seglet),每个Seglet只有64KB大小,每个Segment可以由多个Seglet组成,可以不连续。其默认大小仍为8MB。将内存整理分为两部分:

  • 压缩(Compaction):只涉及一个内存Segment变成更小的Segment,占用了更少的Seglet数目。
  • 联合整理(Combined cleaning):与前文所述相同,同时会将磁盘上的backup进行整理。

前者的消耗比较小,后者的消耗比较大。策略上尽量多做前者少做后者,同时推迟后者的执行可以提高整体效率,因为整理时间越晚,越少的对象会存活,开销也就越小。

RAMCloud实现的测试结果

这个地方原文写的很多,有兴趣的可以去详细查阅。简要的结论是:

  • 在没有很大性能损失的情况下,RAMCloud能达到80~90%的内存利用率
  • 两层整理比一层整理的效率提高6倍

总结

LSM-Tree的结构带来了独特的读写模式,对于生成的数据块不会进行更改,这给并行整理带来了可能,实际上这为很多基于内存的存储引擎带来了启发。文章另外的一些设计如内存分段处理,其实与G1GC的思想是很类似的,都是为了节约全局tracing开销。
另外文章中的两层整理的设计,确实是系统实现中不错的创新,贯彻了最小开销的思想。比如对于backup磁盘整理而言,其整理一个Segment的成本效益模型(cost-benefit)抽象为图4。
图4 RAMCloud选取整理Segment时的成本效益模型
其中u为当前Segment的空间存活率,benefit可以理解为两部分,一部分是整理可以获得的空间,另一部分SegmentAge代表的是稳定程度,稳定程度越高的应当整理,整理后不易释放,可以减少后续的整理开销。这对其他类似的LSM系统有一定的指导意义。

参考文献

[1] Lu L, Pillai T S, Gopalakrishnan H, et al. Wisckey: Separating keys from values in ssd-conscious storage[J]. ACM Transactions on Storage (TOS), 2017, 13(1): 1-28.
[2] Rumble S M, Kejriwal A, Ousterhout J. Log-structured memory for DRAM-based storage[C]//12th {USENIX} Conference on File and Storage Technologies ({FAST} 14). 2014: 1-16.
[3] McKenney P E, Slingwine J D. Read-copy update: Using execution history to solve concurrency problems[C]//Parallel and Distributed Computing and Systems. 1998: 509-518.
[4] Appavoo J, Hui K, Soules C A N, et al. Enabling autonomic behavior in systems software with hot swapping[J]. IBM systems journal, 2003, 42(1): 60-76.

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×