高效Key-Value持久化缓存系统的实现

罗 军，陈席林，李文生



高效Key-Value持久化缓存系统的实现

罗 军，陈席林，李文生

(重庆大学计算机学院，重庆 400044)

传统的缓存系统为了追求更高的性能大多是基于内存存储的，数据的持久化功能并不完善，因而系统会受到内存容量的限制，并且在系统宕机时会导致数据全部丢失，无法恢复。为此，在分析传统缓存系统的基础上，针对数据的持久化运用LSM-Tree理论以及Merge-Dump存储引擎进行改进，并参考Google的单机持久化存储系统LevelDB，实现一个分布式的Key-Value持久化缓存系统SSDB，结合传统缓存系统的优点并利用一致性哈希、布隆过滤器等思想对SSDB进行一系列优化。对SSDB性能测试的结果表明，优化后的持久化缓存系统SSDB是纯内存存储的，能有效降低数据的存储成本，且在读写性能上只比Redis下降约 600 QPS。

LSM-Tree理论；Merge-Dump存储引擎；缓存系统；持久化存储；一致性哈希；布隆过滤器

1 概述

随着信息技术的发展，应用程序对后台性能的要求越来越高，数据量也越来越大。在大数据时代，人们总希望存在一个Key-Value存储机制，像HashMap一样在内存中处理大量的Key-Value对，以便提高数据的查找、修改速度。最近几年，业界不断涌现出很多各种各样的NoSQL[1]产品：Memcached[2]，Redis[3]，LevelDB[4]等，它们在很多时候都是作为数据库前端Cache使用的，因为它们比数据库少了很多sql解析、磁盘操作等开销，通过缓存数据库查询结果，减少数据库访问次数，以提高动态Web应用的访问速度[5]。

很多公司都曾使用过MySQL+Memcached这样的架构，通过Memcached将热点数据加载到Cache以加速访问，但随着业务数据量的不断增加和访问量的持续增长，出现了如下问题：

(1)MySQL需要不断进行拆库拆表，Memcached也需不断跟着扩容，扩容和维护工作占据大量开发时间。

(2)Memcached内存容量有限，一旦内存容量不足，系统将根据LRU[6]算法丢弃数据，导致命中率低，从而大量的访问直接穿透DB，造成MySQL无法支撑。虽然在这点上其他的产品(如Redis)通过虚拟内存技术做了改进，但是当数据量很大时，需要频繁的与磁盘进行数据交互，导致系统性能大幅度下降。

(3)数据都在内存中，一旦系统宕机，数据将全部丢失，无法恢复。

为了解决上述问题，本文对已有的Redis、LevelDB等产品进行改进，实现了SSDB。SSDB参考Google的LevelDB[7]，采用Bigtable的Merge-Dump[8]作为存储引擎，牺牲随机读换取顺序写，以实现数据的高效持久化存储。

2 SSDB系统架构

SSDB作为存储系统，数据记录的存储介质包括内存以及磁盘文件，主要由以下部分组成：内存中的MemTable，Immutable MemTable以及磁盘上的Log文件和SSTable文件，如图1所示。

该架构主要参考LevelDB和BigTable的Merge-Dump存储模型，理论基础都是LSM-Tree[9]。对数据的操作一般包括增删查改，其中，增删改都是写操作，并且删改操作还是随机写，如果数据在磁盘中，随机写将极大地降低系统的性能，在最优情况下，即数据在内存中，随机写也要先找到key所在的位置然后再进行修改。LSM-Tree将修改和删除操作以追加记录的方式实现，将随机I/O写转换成顺序I/O写，充分利用磁盘顺序I/O的特性来优化写磁盘的性能。比如删除key1的操作，就是简单地追加一条新记录key1：Deleted而已。这样做的好处是提升了写性能，但是使得数据的读取过程变得复杂，因此LSM-Tree就是牺牲随机读来换取顺序写，适用于数据更新较频繁的缓存系统。

SSDB是一个高效的持久化Key-Value缓存系统，整个系统的读写过程如下：

(1)所有的更新先写Log，再写MemTable，数据的更新以追加新记录的方式进行。

(2)MemTable中的数据达到一个门限值时，创建新的MemTable和Log文件，并将原MemTable转为Immutable MemTable，等待后台进程将其Dump到磁盘，形成key有序的SSTable文件。

(3)后台进程定期对SSTable文件进行归并排序，形成有层次的SSTable文件结构。

(4)读数据时先读内存中的MemTable，再读内存中的Immutable MemTable，最后读磁盘中的SSTable文件。

3 内存中的MemTable结构

总体来说，所有记录都是存储在Memtable、Immutable Memtable以及 SSTable中的，Immutable Memtable在结构上和Memtable是完全一样的，区别仅在于Immutable Memtable是只读的，不允许写操作。当Memtable占用内存的容量达到一个门限值时，则自动转换为Immutable Memtable，等待Dump到磁盘中，同时会创建新的Memtable供写操作写入新数据，MemTable提供数据的读、写、删除操作接口，删除某个key的记录是以插入一条新记录完成的，但是会打上一个key的删除标记，真正的删除操作是惰性的，由以后的归并过程来做。

Memtable中的记录是Key有序存储的，在系统插入新记录时要将其插到合适的位置上以保持这种key的有序性。Memtable采用SkipList[10]作为核心数据结构，取代传统的红黑树[11]，由于SkipList对于树的平衡的实现是基于一种随机化的算法，因此对SkipList的插入和删除工作比较容易实现。与没有优化的平衡树相比较，SkipList在插入数据时可以避免频繁的树节点调整操作，因而写入效率较高。

4 Log文件

Log文件主要是用于系统宕机后恢复数据，假如没有Log文件，因为刚写入的记录是保存在内存中的，此时如果系统宕机，内存中的数据没有来得及Dump到磁盘，从而会丢失数据。为了避免这种情况，采取先写日志再写内存[12]的策略，这样即使系统宕机，也可以从Log文件中恢复，不会造成数据的丢失。

为了加快从日志中恢复数据的效率，对于每一个Log文件，将它切割成以32 KB为单位的物理块，每次读取以块为单位，一个Log文件由连续的32 KB大小的块构成，这样一条Key-Value记录可能存储在一个块中，也可能存储在连续的多个块中，如图2和图3所示。

图2 数据记录、物理块、日志文件结构

图3 数据在日志文件中的存储格式

类型包括FULL、FIRST、MIDDLE、LAST，如果记录类型是FULL，则代表当前记录完整地存储在一个物理块中，没有被不同的物理块切割开。假设有3条记录Record A、B和C，其中，A大小为10 KB，B为80 KB，C为12 KB，如图2所示，由于A为10 KB<32 KB，能够放在一个物理块中，因此其类型为FULL；而Block 1因为放入了A，还剩下22 KB，不足以放下B，所以在Block 1的剩余部分放入B的开头一部分，类型标识为FIRST，代表了是一个记录的起始部分；B还有58 KB没有存储，这些只能依次放在后续的物理块，因为Block 2大小只有32 KB，仍然放不下B的剩余部分，所以Block 2全部用来放B，且标识类型为MIDDLE，表示这是B中间的一段数据；B剩下的部分可以完全放在Block 3中，类型标识为LAST，代表了这是B的末尾数据；C因为大小为12 KB，Block 3剩下的空间足以全部放下它，所以其类型标识为FULL。读取数据时根据记录类型来拼接出逻辑记录，供后续流程处理。由于一次物理读取为一个块，因此加快了读取磁盘日志的速度，从而提高数据恢复的效率[13]。

5 SSTable文件

当Memtable占用内存的容量达到一个门限值时，则自动转换为Immutable Memtable，后台调度会将Immutable Memtable的数据导出到磁盘，形成一个新的SSTable文件。SSTable就是由内存中的数据不断导出并进行归并操作后形成的，所有的SSTable文件构成一种层级结构，对于磁盘中的数据来说，level0是最新的，level1次之，level2再次之，逐层递减，数据由低层向高层归并，在归并的过程中去掉重复的数据并删除已被打上删除标记的数据。

传统的数据库系统在存储数据时一般是key无序的，通过建立有序的索引来对数据进行快速定位，而SSTable中的文件是由后台异步导出和归并排序产生的，并不会影响数据的读写过程，因此可以将数据按key有序存储，为了提高查找效率，可以用多个文件来分开存储数据，每个文件存储一个范围内的key数据记录，这样只需存储每个文件的最小key和最大key就可以快速定位要查找的记录在哪个文件当中。

SSTable和Log一样都将文件划分为固定大小的物理块，每个块分为3个部分：数据存储区，数据压缩类型(Snappy压缩[14]或者无压缩2种)，CRC数据校验码[15]。但是由于Log文件中的记录是Key无序的，而SSTable文件中的记录是key有序的，因此在逻辑结构上存在着很大的差别。将SSTable文件划分为数据存储区和数据管理区，数据存储区存放实际的数据记录，因为数据记录是key有序的，所以在数据管理区就可以提供一些索引指针等管理数据，从而更快速高效地查找相应的记录。

SSTable文件中数据记录是key有序的，因此相邻的 2条记录在key部分很可能存在重叠，比如key[5]=“test5”，Key[6]=“test6”，那么两者存在重叠的部分test，为了减少key的存储量，下一个key可以只存储和上一条key不同的部分，而两者的共同部分可以从上一个key中获得。在每个数据存储块中，每条数据记录的内部结构如图4所示，每条记录包含5个字段：key共享长度，比如上文的key[6]记录，它的key和上一条记录key[5]共享的key部分的长度是test的长度，即4；key非共享长度，对于key[6]来说，非共享的长度是6的长度，即1；value长度以及最后面的value内容字段中存储实际的value值；而key非共享内容则实际存储6这个key字符串。

图4 数据在SSTable文件中的存储格式

6 Compaction过程

SSDB的写入操作很简单，删除记录也仅仅是写入一个删除标记，但读取过程相对较复杂，需要在内存以及各个SSTable层级文件中根据时间顺序依次查找，代价很高。为加快读取速度，运用BigTable中的Minor Compaction方式和Major Compaction方式来对已有数据记录进行整理压缩，删除掉一些无效的数据，减小数据规模和文件数量等。

Minor Compaction方式就是简单地在磁盘上新建一个 第0层的SSTable文件，并将MemTable中的数据导出到SSTable文件；Major Compaction通过合并不同层级的SSTable文件，对多个文件进行多路归并排序，然后依次判断各个Key记录是否还需要保存，如果不需要则直接丢弃，否则就将其写入下一层中新生成的一个SSTable文件中，最后删除掉参与Compaction过程的SSTable文件，从而减少数据的存储空间和文件数量，提高从SSTable文件中查找数据的效率。

7 Cache机制

Compaction过程使得系统从磁盘中读取数据的性能有了一定的提升，但是直接从磁盘中读取数据依然效率低下，如果数据在SSTable文件中，则需要进行多次磁盘访问操作，在最优的情况下，即要找的数据在第0层，也需要 2次磁盘读操作，第1次将SSTable文件中的索引部分读入内存，然后根据索引就可以确定key是在哪个物理块中存储；第2次读入这个物理块的内容，然后在内存中查找。

为了减少磁盘访问的次数，使用了2种Cache：Table Cache和Block Cache。其中，Table Cache缓存SSTable文件的索引信息，Block Cache缓存物理块内容。从磁盘中查找数据时，首先判断key在哪个SSTable文件中，然后检查该SSTable文件是否在Table Cache中，若不在则读取该SSTable文件并将其缓存，若在则通过索引定位到物理块，并检查该物理块是否在Block Cache中，若不在则将该物理块读入内存并缓存，若在则直接在内存中查找。

SSDB就是通过这2个Cache来加快读取速度的。如果读取的数据局部性比较好，则性能会有明显的提高。由于Cache容量有限，而新访问的数据一般都会被Cache，因此容量满后采用LRU算法和FiveMinuteRule[16]原则进行替换，FiveMinuteRule原则即如果数据被访问的频率在5 min以内，那么就应该尽量将该数据写入到内存中去。

8 Bloom Filter过滤器

在数据的读取过程中，如果数据不在内存中，则会去磁盘中找，现在假设一种极端的情况，要查找的数据不在缓存系统中，则数据的查找过程将要经历内存中的MemTable、Immutable MemTable和磁盘中的各层SSTable文件，而最后返回数据不存在，笔者无法容忍这种极端情况下的性能损失。因此，为了快速判断要查找的数据是否在缓存系统中，从而避免不必要的查找过程，使用了一种多哈希函数映射的快速查找算法——布隆过滤器[17]，该算法能够非常快速地判定某个元素是否在一个集合之外。这种判定只会对在集合内的数据错判，而不会对集合外的数据错判，这样如果判定数据不在缓存系统中，则可快速认定该数据不在，有效地提高了系统的读操作性能。

9 一致性哈希

SSDB是一个分布式的缓存系统，将数据均匀分散地存储到多台缓存服务器上，假如有个服务器，采用传统的hash映射算法hash(key)%，则会遇到如下2个问题：

(1)一个服务器宕机了，这样所有映射到的数据都会失效，然后需要把移除，这时候映射公式变成了hash(key)%(-1)。

(2)由于访问加重，需要添加服务器，这时候服务器是+1台，映射公式变成了hash(key)%(+1)。

映射公式的改变意味着突然之间几乎所有的Cache都失效了。对于服务器而言，这是一场灾难，洪水般的访问都会直接冲向后台服务器[18]。为了解决上面的问题，使用了一致性哈希算法[19]。

Consistent Hashing的基本思想就是将对象和Cache都映射到同一个Hash数值空间中，并使用相同的Hash算法。如图5所示，假设当前有A、B和C共3台Cache，hash(Cache A)=key A，hash(Cache B)=key B，hash(Cache C)=keyC。

图5 Cache和对象的key值分布

在这个环形空间中，如果沿着顺时针方向从对象的key值出发，直到遇见一个Cache对应的key，那么就将该对象存储在这个Cache上，因为对象和Cache的hash值是固定的，所以这个Cache必然是唯一和确定的。

现在假设Cache B宕机，这时受影响的将仅是那些沿着Cache B逆时针遍历直到上一个Cache A之间的对象，即原本映射到Cache B上的那些对象。因此这里仅需要变动对象object4，将其重新映射到Cache C上即可，如图6 所示。

图6 Cache B被移除后的对象key映射

由于hash映射无法保证分配的绝对均衡，如果Cache较少，则对象并不能被均匀地映射到Cache上，假设仅有 2台服务器A和C，如图6所示，则object1映射到Cache A上，而object2、object3、object4则都映射到Cache C上，映射不均。为此，在其中添加了很多的虚拟节点，然后建立实际服务器和虚拟节点的对应关系，如图7所示，实际服务器Cache A对应2个虚拟节点Cache A1和A2，只要是映射到虚拟节点A1和A2上的对象都将存储到Cache A上，因此，Cache A中存储了object1和object2；Cache C中存储了object3和object4，从而实现了相对简单的负载均衡。

图7 引入虚拟节点后的Cache映射

10 主从同步与读写分离

假如有20亿的数据量和4台缓存服务器，则在负载均衡的情况下，每台大约有5亿的数据量，如果数据访问比较集中，则会出现在单台服务器上大量的数据访问，由于单机的吞吐量和性能有限，从而使得该服务器无法承受，因此运用了传统关系数据库中的主从同步、读写分离策略，通过单点写多点读的主从同步架构有效地提高了系统的读写性能。

主从同步的实现比较简单，如图8所示。选择一台服务器作为master，多台服务器作为slave，master负责写操作，多个slave负责读操作，master的写操作将会先写日志，一旦写入日志，就会在下一个同步周期同步到slave，为了使系统不受网络抖动的影响，同步支持断点续传。由于不是立刻同步，因此从slave中读取数据会有些许延迟，但是该架构可以有效地提高系统的吞吐量[20]。

图8 主从复制与读写分离示意图

11 性能测试

用PHP和Python编写测试代码分别对SSDB和Redis进行性能测试，PHP代码产生到服务器的请求，Python代码负责并发的执行PHP代码从而产生并发的请求。用SSDB-set、SSDB-get、Redis-set、Redis-get分别表示SSDB写、SSDB读、Redis写、Redis读，SSDB-set--表示在SSDB服务器上已有个写、个读持久请求的情况下再执行一次写操作测试。

在每完成1 000次请求后，服务器计算出请求的平均处理速度，单位为QPS(Query Per Second)，即单个进程每秒请求服务器的成功次数=总请求数/(总进程数´请求时间)。将测试结果放在Highcharts插件中展示，如图9和图10所示。从图中可以看出，总体上SSDB的读写性能大致低于Redis 600 QPS左右，因为SSDB打破了Redis内存容量的限制，当内存容量不足时，数据会被写入到磁盘，而不会像Redis那样选择丢弃，同时也不会像Memcached那样使用LRU算法丢弃旧数据，由于大部分数据会被写入到磁盘，因此性能会有所下降，但是SSDB运用了Bigtable的Merge- Dump存储引擎以及LSM-Tree思想，将随机写转换成顺序写，充分利用了磁盘的顺序访问特性，使得SSDB的写性能并没有下降太多，同时SSDB对磁盘中的数据进行了归并排序以及建立索引和Cache等，也有效地保证了系统的读性能。

图9 没有任何读写请求时加一次读写请求的测试结果

图10 已有1写4读持久请求时加一次读写请求的测试结果

12 结束语

SSDB是一个高效的Key-Value持久化缓存系统，与Redis相比，SSDB支持数据的持久化，使得系统不受内存容量的限制，并且在系统发生故障或者宕机后不会丢失数据，同时优化后SSDB的读写性能在整体上只是略有下降。因此，SSDB特别适用于当今的海量数据规模应用。目前SSDB已经支持PHP、Java、C++等编程语言，未来还将会对它的性能和可用性做进一步的优化和完善，特别是在一致性哈希上，决定采用Amazon的分布式Key-Value存储引擎Dynamo[21]架构的实现方案，Dynamo架构在一致性哈希上做了更多的改进，支持数据同时存储在多个物理节点上，是一个去中心化的分布式系统，因而使得系统在容错上不会有任何的单点故障，同时还节约了服务器成本。

[1] Strauch C. NoSQL Databases[EB/OL]. [2011-02-24]. http:// www.christof-strauch.de/nosqldbs.pdf.

[2] Fitzpatrick B. Distributed Caching with Memcached[J]. Linux Journal, 2004, 2004(124): 72-74.

[3] Sanfilippo S, Noordhuis P. Redis[EB/OL]. [2011-03-19]. http://redis.io.

[4] Ghemawat S, Dean J. LevelDB[EB/OL]. [2011-05-12]. http:// leveldb.googlecode.com/svn/trunk/doc/index.html.

[5] 杨 艳, 李 炜, 王 纯. 内存数据库在高速缓存方面的应用[J]. 现代电信科技, 2011, 41(12): 59-64.

[6] Ghemawat S, Dean J. LevelDB[EB/OL]. [2011-05-12]. http:// leveldb.googlecode.com/svn/trunk/doc/impl.html.

[7] Chrobak M, Noga J. LRU is Better than FIFO[J]. Algorithmica, 1999, 23(2): 180-185.

[8] Chang F, Dean J, Ghemawat S, et al. Bigtable: A Distributed Storage System for Structured Data[J]. ACM Transactions on Computer Systems, 2008, 26(2): 1-26.

[9] O’Neil P, Cheng E, Gawlick D, et al. The Log-structured Merge-Tree(LSM-Tree)[J]. Acta Informatica, 1996, 33(4): 351-385.

[10] Pugh W. Skip Lists: A Probabilistic Alternative to Balanced Trees[J]. Communications of the ACM, 1990, 33(6): 668-676.

[11] Sedgewick R. Left-leaning Red-Black Trees[C]//Proc. of Dagstuhl Workshop on Data Structures. Wadern, Germany: [s. n.], 2008.

[12] UIIman J D, Widom J. 数据库系统实现[M]. 杨冬青, 译. 北京: 机械工业出版社, 2001.

[13] 朗格科技. levelDB技术[EB/OL]. [2011-10-19]. http://www. samecity.com/blog/index.asp.

[14] Gunderson Co.. Snappy——A Fast Compressor/Decompressor [EB/OL]. [2011-11-08]. http://code.google.com/p/ snappy.

[15] Borrelli C. IEEE 802.3 Cyclic Redundancy Check[EB/OL]. (2001-03-21). http://www.xilinx.com/support/documentation/ application_notes/xapp209.pdf.

[16] Gray J, Putzolu F. The 5 Minute Rule for Trading Memory for Disc Accesses and the 10 Byte Rule for Trading Memory for CPU Time[C]//Proc. of ACM SIGMOD International Con- ference on Management of Data. San Francisco, USA: [s. n.], 1987: 395-398.

[17] Mitzenmacher M. Compressed Bloom Filters[J]. IEEE/ACM Transactions on Networking, 2002, 10(5): 604-612.

[18] 张 亮. 一致性Hash算法(Consistent Hashing)[EB/OL]. [2010-02-02]. http://blog.csdn.net/sparkliang/article/details/52 79393.

[19] Karger D, Sherman A, Berkheimer A, et al. Web Caching with Consistent Hashing[J]. Computer Networks, 1999, 31(11): 1203-1213.

[20] 简朝阳. MySQL性能调优与架构设计[M]. 北京: 电子工业出版社, 2009.

[21] DeCandia G, Hastorun D, Jampani M, et al. Dynamo: Amazon’s Highly Available Key-Value Store[C]//Proc. of the 21st ACM SIGOPS Symposium on Operating Systems Principles. Stevenson, USA: [s. n.], 2007: 205-220.

编辑 任吉慧

Implementation of Energy-efficient Key-Value Persistent Caching System

LUO Jun, CHEN Xi-lin, LI Wen-sheng

(College of Computer Science, Chongqing University, Chongqing 400044, China)

Most of the traditional caching systems are based on memory storage in order to achieve higher performance, and their data persistence is not perfect. So these systems may be limited to memory capacity. Also they may lose all the data and be impossible to restore when systems break down. After analyzing the traditional caching systems, this paper applies the Log Structured Merge-Tree(LSM-Tree) theory and Merge-Dump storage engine to improve their data persistence, and then implements a distributed Key-Value persistent caching system Sorted Set DB(SSDB) by referencing the stand-alone persistent storage system LevelDB of Google. It combines SSDB with advantages of traditional caching systems, consistent Hashing, Bloom filter and so on to optimize its performance. It tests the performance of SSDB, and the results show that because of pure memory storage, SSDB can effectively reduce the cost of data storage, and it has just a slight decrease of 600 Query Per Second(QPS) in reading and writing performance compared with Redis.

LSM-Tree theory; Merge-Dump storage engine; caching system; persistent storage; consistent Hashing; Bloom filter

中央高校基本科研业务费专项基金资助项目(CDJZR10180014)。

罗 军(1961－)，男，副教授、硕士，主研方向：数据库技术，大型MIS系统建模及设计，基于数据库的应用系统平台； 陈席林、李文生，硕士研究生。

2013-03-06

2013-04-08 E-mail：710732542@qq.com

1000-3428(2014)03-0033-06

A

TP311

10.3969/j.issn.1000-3428.2014.03.007