高效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