概述

本文力争简明扼要介绍ScyllaDB 的内存分配器实现。ScyllaDB 是用C++重写了Cassandra，据称在等同配置下，获得了10倍的性能提升。我们知道，单纯用C++重写Java程序，并不能保证性能得到大幅度提升。一定有其它一些秘密武器，光凭借这一点，就值得研究。

其实，ScyllaDB在系统设计与实现上，作了一些创新性工作，或者引入了一些比较新的技术方案。例如，用户态TCP协议栈，用户态IO调度器，用户态任务调度器，以及本文要介绍的Log-Structured Memory Allocator 等等。详情，请见seastar介绍。

本文着重介绍Log-Structured Memory Allocator（下文简称LSA）。关于LSA，在RAMCloud中有实现，论文在这里。

看到Log-Structured 很多会想到Log-Structured Merge Tree(下文简称LSM）, leveldb等存储引擎就是基于此实现的。其实，LSA和LSM有着异曲同工之妙。LSM的写操作与LSA分配内存操作对应，LSM的删除数据操作与LSA的释放内存操作对应，LSM的Compaction操作与LSA的Compaction操作对应，LSM的写限流功能与LSA的内存使用节流机制对应。所以，LSA分配器并不陌生。

LSA解决什么问题？

在存储引擎实现中，内存利用率是一个非常重要的指标。当产生内存碎片后，系统即便时内存充足，也有可能面临无法分配内存的情况。通过移动内存，腾挪空间的方式，整理出连续内存区域，是一种很自然想到的办法。

例如，有些缓存系统在空闲时间，执行内存碎片回收的任务。通常，这类重型任务放在凌晨。这个方案简单直观，能解决部分问题，也有明显不足：首先，随着云计算业务发展，共享是缓存集群就没有所谓空闲时间段了（各种业务高峰分布趋于均衡）；其次，时效性差，也有可能服务器无法熬到空闲时期，内存碎片化已经很严重了；另外，在内存碎片整理期间，服务质量下降；

有没有可控的，可持续的方式控制内存碎片程度呢？显然是有的。LSA分配内存，在形成内存碎片后，能够在持续可控地移动内存内容，腾挪空间，达到消除内存碎片，从而提升内存利用率。

所以，LSA 解决内存碎片化，利用率不高的问题。

ScyllaDB的LSA如何实现？

ScyllaDB采用Share-Nothing架构。具体地，为CPU的每一个logical-core构建相互独立的资源，包括独立的协议栈实例，独立的任务引擎，独立的IO调度器等等。显然，也会为每一个logical-core构建独立的内存分配器，即LSA实例。大量采用lock-free设计，代码就非常容易读了。

先放一张大图。

在这种图中，虚线左边是LSA的接口，虚线右边是LSA的实现逻辑。
先看看LSA接口：

Region: LSA将虚拟内存抽象为若干Region, 分配的内存对象必须属于某一个Region，并且其所属的Region负载该内存对象的释放。
RegionGroup: 一个Region 属于一个RegionGroup。RegionGroup主要用于内存容量统计与限制，RegionGroup可以嵌套。根据业务逻辑，将不同的Region聚合在一起。
Tracker: 这个是一个控制类，通过参数来控制LSA行为；
AllocationStrategy: 每一个Region拥有的AllocationStrategy对象，通过它来分配内存，释放内存。

在看看LSA实现部分：

Segment: LSA管理内存的小单位, 它将连续内存区域切分为固定尺寸段，称为Segment;
SegmentPool: 每一个logical-core 拥有全局的对象，该对象管理内存Segment; 每一个Segment都会对应一个descriptor, 这些descriptor存放在SegmentPool中。该SegmentPool为该logical-core上所有的Region服务。
SegmentZone: SegmentPool将连续的内存区域切分为若干Segment, 这些Segment的集合，称之为SegmentZone。SegmentPool向系统申请内存后，就会创建一个SegmentZone, 创建后，它的Size就不会改变。
ObjectDescriptor：每一个内存对象都会分配一个ObjectDescriptor, 用于描述对象是存活还是被是否，描述对象尺寸，记录对象迁移函数，对齐尺寸。

系统启动后，为每一个logical-core构造一个LSA实例。初始状态，SegmentPool 为空。当某个Region分配内存对象时候，SegmentPool会申请批量的Segment, 构成一个SegmentZone。然后，分配一个Segment 给Region。 Region在该Segment中分配一块区域即可。

SegmentPool 内存Layout示意图。

LSA 腾挪空间的过程叫做Compaction，主要做的事情就是通过腾挪空间，回收内存。那么，Compaction在什么时机触发呢？

在CPU空闲事情，会依次对可以做Compaction的Region试图做Compaction动作；
在无法分配出要求的内存时候，进入Compaction动作，腾挪一些空间出来；
通过API 主动触发回收内存操作；

LSA通过RegionGroup来实现内存节流机制。如果RegionGroup关联的Region使用的内存超过阈值了，通过RegionGroup提交的函数就会缓存在队列中，直到超时，或者有内存空间被回收，导致该RegionGroup关联的Region内存使用量降低到阈值以下。这个机制，可以保证某些操作不至于无限制使用内存，而导致其他组件无内存可用，导致服务不可用。