SIGMOD'19
Gui Huang, Xuntao Cheng, Jianying Wang, Yujie Wang, Dengcheng He, Tieying Zhang, Feifei Li, Sheng Wang, Wei Cao, and Qiang Li {qushan,xuntao.cxt,beilou.wjy,zhencheng.wyj,dengcheng.hedc, tieying.zhang,lifeifei,sh.wang,mingsong.cw,junyu}@alibaba-inc.com Alibaba Group
本文介绍了阿里为了应对电商平台workload而开发的一个KV存储引擎X-Engine,X-Engine结构上选取了比较流行的LSM-Tree结构,很多地方看起来和RocksDB有一些相似的地方,但是设计上根据电商平台的负载特征做了许多的优化,用到了诸如多线程、异步、流水线以及专有硬件(指FPGA)等新技术。X-Engine已经被运用到阿里的实际生产环境中,并且通过了双十一活动的检验,并表现出了良好且稳定的性能。
E-Commerce的特征以及主要问题
X-Engine主要针对电子商务平台开发,阿里结合其双十一活动的经验,总结了电商平台workload的几个主要特征:
活动开始时TPS激增
诸如双十一这样的大型电商活动,在11日0点这样的活动开始时间,大量用户创建大量的订单,使得存储引擎的TPS(Transaction Per Seconds)急剧升高。这就造成了一个“海啸”的问题(tsunami problem),下图为阿里的2018年双十一活动开始前后的TPS变化,可以看到在0点的时候系统TPS增加到原来的122倍(此时X-Engine依旧维持了相对稳定的TPS)。一般解决这样的“海啸”问题的方法是增加服务器数量,实现集群的横向扩展,但是这样的缺点是成本高。
buffer很快被大量数据填满
由于访问量的增加,使得存储引擎的内存缓存被大量数据迅速填满,即使现在内存可以上升到几百G,但这对现在电商平台的数据量来说还是十分不够的,这就需要对系统进行“泄洪”(flood discharge problem),也就是将数据从memory转移到storage中。存储引擎则需要尽可能高效地将数据进行转移。
随着促销活动的改变,数据的冷热会发生迅速的切换
电商平台会有各种促销活动,这种促销活动会吸引大量用户对商品数据进行访问,从而形成热点数据。而当促销活动发生切换的时候,访问热点迅速发生变化(fast-moving current problem)。此时存储引擎需要及时对数据热点的变更作出反应,从storage中取出新的热点数据并缓存。
X-Engine Design
针对上面提到的主要特征和问题,阿里设计开发了X-Engine。X-engine总体结构采用了LSM-Tree的结构,并基于不同的存储设备(NVM/SSD/HDD)实现了分层存储(tier storage),支持事务,并在读写事务处理以及compaction处理上做了多种优化,以应对电商平台的workload特征。
总体结构
X-Engine基于PolarFS构建,可以作为PolarDB的一个组件。总体可以分为memory的热数据层和storage的温/冷数据层,memory中有Active memtable和多个Immutable memtable,以及Read cache和Index。storage中数据分为多层,不同层的数据通过不同的存储设备存储,每一层数据以extent为单位组织(类似RocksDB的SSTable)。下面详细介绍X-Engine在各个部分以及优化措施。
Read Path
Extent
X-Engine的Extent类似于RocksDB的SSTable,用来持久化存储数据,下图是Extent的基本结构。
Data Block和Index Block部分和SSTable类似,区别在于Extent的元数据部分主要是Schema,X-Engine是以Row为形式存储一个table,Schema中存储的就是一个Table的各个column的属性。Schema带有一个version,是为了在更新schema的时候不需要去修改旧的数据。
Cache
X-Engine的cache比起RocksDB多了一个Row Cache(但是RocksDB其实也有一个Row cache,好像实现不一样)。Row Cache用于缓存最近访问的记录,通过哈希组织数据,并通过LRU进行数据淘汰。另一个Block Cache就和RocksDB基本一样,都是以data block为粒度对数据进行缓存。
Meta Index
X-Engine的Meta Index用来记录LSM-Tree结构的变化,类似Manifest(这一部分有点没理解),结构如下:
LSM-Tree中每个subtable都有其meta index,meta index起始于一个根节点,并在每次更新之后创建新的节点。如上面的L0的extent-i,它对应meta snapshot v,当extent-i被compaction之后创建新的meta snapshot v+1,v+1只需要指向原来的extent-i而不需要产生实际的IO,同时cache的数据也不需要变化。同时这样的CoW的结构使得事务可以访问任意版本的数据,避免了锁的开销。X-Engine中有GC机制来清理过期的snapshot。
Incremental Cache Replacement
这一项是针对compaction对cache的影响进行的优化,原来的LSM-Tree实现中,当SST被compact,则对应的内存中的数据会被evict,造成突然的cache miss,这个问题在前些年的一篇论文LSbM-Tree中也有被提到。X-Engine的这个Incremental Cache Replacement的原理就是在compaction的时候检查一个block是否被cache,如果是,则将cache中的内容替换为merge之后的block,再结合后面的reuse机制,可以有效地缓解compaction对cache命中率带来的影响。
Write Path
X-Engine的写优化主要是memtable的优化以及写Redo log上的优化。
Multi-Version Memtable
memtable上做了一点简单的优化,像RocksDB的memtable,如果多次更新同一个key,那么这个key会以<key, sequence_number>的形式在memtable中存储,如果要查找最新的key,则可能需要读多个旧值。X-Engine的Multi-Version Memtable对此的优化就是将同一个key的不同版本单独链起来。这样Skiplist中不会出现一个key的多个版本,同一个key的多版本中按照新旧组织顺序,最新的key可以最快被访问到。
Asynchronous & Pipeline
这一块是X-Engine优化比较多的,总体的结构如下:
X-Engine通过MVCC以及two-phase-locking实现了SI(Snapshot Isolation)和RC(Read Committed)级别的隔离等级。读写事务被分成两个阶段,分别是Read/Write Phase和Commit Phase。在R/W Phase,读请求通过Read path处理,更新请求被缓存到Transaction Buffer中;在Commit Phase中数据从Transaction Buffer中被写到DB中。
传统的事物处理流程中,用户线程需要执行完整的R/W+commit之后才能返回,X-Engine使用异步的方式将commit解耦出来,Commit阶段线程只需要将请求添加到Task Queue中即可返回,再由系统线程处理Queue里面的请求,提升了用户线程请求效率。同时一个队列中的请求还能通过batch的方式提升IO性能。
在处理commit的时候X-Engine通过pipeline的方式优化的效率。具体的,commit可以分成三个阶段:
1)将txn从Transaction Bufer移动到Log Buffer,并计算校验和:内存访问 & 计算
2)将数据写到Disk:Disk IO
3)插入memtable:内存访问
4)commit: 内存访问
根据每个阶段请求的不同分成不同的线程来执行,以提升带宽(没看懂为啥)。同时每个stage的线程数不同,如stage1分配一个线程,而插入memtable分配了多个线程并行插入。
Flush & Compaction
intra-L0 Compaction
因为L0存储的数据是比其他层都新的,意味着被访问的概率最大,而L0是无序的,所以X-engine引入了Intra-L0 Compaction,本质上是一个L0层内的compaction,对L0的数据进行整理。(RocksDB也有)
Accelerating Compaction
对于其他层的compaction,X-Engine主要做了三个方面的优化:
1)Data Reuse:对于没有重叠的数据块,不进行merge而只改变meta
其中reuse可以从三个粒度进行:没有overlap的extent可以reuse,没有overlap的data block可以reuse,data block可以被拆分(split)来促成reuse。这种方法在别的论文中也很常见。
2)Asynchronous IO:X-Engine将compaction分成Read-Merge-Write三个阶段,其中Merge阶段可以作为Read的回调函数执行,实现异步IO,提升Compaction的效率。
3)FPGA Offloading:将Compaction offload到FPGA上去执行,从而降低了Compaction对CPU资源的占用,具体的方法在FAST 20的那篇论文中有讲述。
Evaluation
测试部分主要是针对前面背景部分提出的三个问题进行测试,分别对比了InnoDB和RocksDB。
E-commerce Transaction
首先论文对比了电商平台workload下的三个DB的性能,下面的比例分别是lookup, range lookup, update, insert,可以看到在read intensive的workload中还是InnoDB表现稍好,这主要是因为LSM-Tree的结构如果在缓存未命中的时候,需要查找多层数据,而InnoDB是基于B+树,这方面X-Engine个RocksDB就有天然的劣势。
Raw KV Performance
测试底层KV接口下的性能,由于InnoDB没有提供KV接口,所以这里只对比了X-Engine和RocksDB,可以看到无论是带宽还是延迟,X-Engine都要比RocksDB优秀不少。
Write Path Optimization
为了验证Write Path中的异步写以及流水线的有效性,论文测试了不同队列数以及线程数的性能(1 queue = no pipeline),其中异步+8线程性能最好。
MySQL Performance
单点操作基本还是X-Engine好,但是Range Scan性能跟InnoDB没法比,这也是来自B+树的天然优势。