羅 軍，陳席林，李文生

?

高效Key-Value持久化緩存系統(tǒng)的實現(xiàn)

羅 軍，陳席林，李文生

(重慶大學計算機學院，重慶 400044)

傳統(tǒng)的緩存系統(tǒng)為了追求更高的性能大多是基于內(nèi)存存儲的，數(shù)據(jù)的持久化功能并不完善，因而系統(tǒng)會受到內(nèi)存容量的限制，并且在系統(tǒng)宕機時會導致數(shù)據(jù)全部丟失，無法恢復。為此，在分析傳統(tǒng)緩存系統(tǒng)的基礎上，針對數(shù)據(jù)的持久化運用LSM-Tree理論以及Merge-Dump存儲引擎進行改進，并參考Google的單機持久化存儲系統(tǒng)LevelDB，實現(xiàn)一個分布式的Key-Value持久化緩存系統(tǒng)SSDB，結合傳統(tǒng)緩存系統(tǒng)的優(yōu)點并利用一致性哈希、布隆過濾器等思想對SSDB進行一系列優(yōu)化。對SSDB性能測試的結果表明，優(yōu)化后的持久化緩存系統(tǒng)SSDB是純內(nèi)存存儲的，能有效降低數(shù)據(jù)的存儲成本，且在讀寫性能上只比Redis下降約 600 QPS。

LSM-Tree理論；Merge-Dump存儲引擎；緩存系統(tǒng)；持久化存儲；一致性哈希；布隆過濾器

1 概述

隨著信息技術的發(fā)展，應用程序對后臺性能的要求越來越高，數(shù)據(jù)量也越來越大。在大數(shù)據(jù)時代，人們總希望存在一個Key-Value存儲機制，像HashMap一樣在內(nèi)存中處理大量的Key-Value對，以便提高數(shù)據(jù)的查找、修改速度。最近幾年，業(yè)界不斷涌現(xiàn)出很多各種各樣的NoSQL[1]產(chǎn)品：Memcached[2]，Redis[3]，LevelDB[4]等，它們在很多時候都是作為數(shù)據(jù)庫前端Cache使用的，因為它們比數(shù)據(jù)庫少了很多sql解析、磁盤操作等開銷，通過緩存數(shù)據(jù)庫查詢結果，減少數(shù)據(jù)庫訪問次數(shù)，以提高動態(tài)Web應用的訪問速度[5]。

很多公司都曾使用過MySQL+Memcached這樣的架構，通過Memcached將熱點數(shù)據(jù)加載到Cache以加速訪問，但隨著業(yè)務數(shù)據(jù)量的不斷增加和訪問量的持續(xù)增長，出現(xiàn)了如下問題：

(1)MySQL需要不斷進行拆庫拆表，Memcached也需不斷跟著擴容，擴容和維護工作占據(jù)大量開發(fā)時間。

(2)Memcached內(nèi)存容量有限，一旦內(nèi)存容量不足，系統(tǒng)將根據(jù)LRU[6]算法丟棄數(shù)據(jù)，導致命中率低，從而大量的訪問直接穿透DB，造成MySQL無法支撐。雖然在這點上其他的產(chǎn)品(如Redis)通過虛擬內(nèi)存技術做了改進，但是當數(shù)據(jù)量很大時，需要頻繁的與磁盤進行數(shù)據(jù)交互，導致系統(tǒng)性能大幅度下降。

(3)數(shù)據(jù)都在內(nèi)存中，一旦系統(tǒng)宕機，數(shù)據(jù)將全部丟失，無法恢復。

為了解決上述問題，本文對已有的Redis、LevelDB等產(chǎn)品進行改進，實現(xiàn)了SSDB。SSDB參考Google的LevelDB[7]，采用Bigtable的Merge-Dump[8]作為存儲引擎，犧牲隨機讀換取順序寫，以實現(xiàn)數(shù)據(jù)的高效持久化存儲。

2 SSDB系統(tǒng)架構

SSDB作為存儲系統(tǒng)，數(shù)據(jù)記錄的存儲介質包括內(nèi)存以及磁盤文件，主要由以下部分組成：內(nèi)存中的MemTable，Immutable MemTable以及磁盤上的Log文件和SSTable文件，如圖1所示。

該架構主要參考LevelDB和BigTable的Merge-Dump存儲模型，理論基礎都是LSM-Tree[9]。對數(shù)據(jù)的操作一般包括增刪查改，其中，增刪改都是寫操作，并且刪改操作還是隨機寫，如果數(shù)據(jù)在磁盤中，隨機寫將極大地降低系統(tǒng)的性能，在最優(yōu)情況下，即數(shù)據(jù)在內(nèi)存中，隨機寫也要先找到key所在的位置然后再進行修改。LSM-Tree將修改和刪除操作以追加記錄的方式實現(xiàn)，將隨機I/O寫轉換成順序I/O寫，充分利用磁盤順序I/O的特性來優(yōu)化寫磁盤的性能。比如刪除key1的操作，就是簡單地追加一條新記錄key1：Deleted而已。這樣做的好處是提升了寫性能，但是使得數(shù)據(jù)的讀取過程變得復雜，因此LSM-Tree就是犧牲隨機讀來換取順序寫，適用于數(shù)據(jù)更新較頻繁的緩存系統(tǒng)。

SSDB是一個高效的持久化Key-Value緩存系統(tǒng)，整個系統(tǒng)的讀寫過程如下：

(1)所有的更新先寫Log，再寫MemTable，數(shù)據(jù)的更新以追加新記錄的方式進行。

(2)MemTable中的數(shù)據(jù)達到一個門限值時，創(chuàng)建新的MemTable和Log文件，并將原MemTable轉為Immutable MemTable，等待后臺進程將其Dump到磁盤，形成key有序的SSTable文件。

(3)后臺進程定期對SSTable文件進行歸并排序，形成有層次的SSTable文件結構。

(4)讀數(shù)據(jù)時先讀內(nèi)存中的MemTable，再讀內(nèi)存中的Immutable MemTable，最后讀磁盤中的SSTable文件。

3 內(nèi)存中的MemTable結構

總體來說，所有記錄都是存儲在Memtable、Immutable Memtable以及 SSTable中的，Immutable Memtable在結構上和Memtable是完全一樣的，區(qū)別僅在于Immutable Memtable是只讀的，不允許寫操作。當Memtable占用內(nèi)存的容量達到一個門限值時，則自動轉換為Immutable Memtable，等待Dump到磁盤中，同時會創(chuàng)建新的Memtable供寫操作寫入新數(shù)據(jù)，MemTable提供數(shù)據(jù)的讀、寫、刪除操作接口，刪除某個key的記錄是以插入一條新記錄完成的，但是會打上一個key的刪除標記，真正的刪除操作是惰性的，由以后的歸并過程來做。

Memtable中的記錄是Key有序存儲的，在系統(tǒng)插入新記錄時要將其插到合適的位置上以保持這種key的有序性。Memtable采用SkipList[10]作為核心數(shù)據(jù)結構，取代傳統(tǒng)的紅黑樹[11]，由于SkipList對于樹的平衡的實現(xiàn)是基于一種隨機化的算法，因此對SkipList的插入和刪除工作比較容易實現(xiàn)。與沒有優(yōu)化的平衡樹相比較，SkipList在插入數(shù)據(jù)時可以避免頻繁的樹節(jié)點調整操作，因而寫入效率較高。

4 Log文件

Log文件主要是用于系統(tǒng)宕機后恢復數(shù)據(jù)，假如沒有Log文件，因為剛寫入的記錄是保存在內(nèi)存中的，此時如果系統(tǒng)宕機，內(nèi)存中的數(shù)據(jù)沒有來得及Dump到磁盤，從而會丟失數(shù)據(jù)。為了避免這種情況，采取先寫日志再寫內(nèi)存[12]的策略，這樣即使系統(tǒng)宕機，也可以從Log文件中恢復，不會造成數(shù)據(jù)的丟失。

為了加快從日志中恢復數(shù)據(jù)的效率，對于每一個Log文件，將它切割成以32 KB為單位的物理塊，每次讀取以塊為單位，一個Log文件由連續(xù)的32 KB大小的塊構成，這樣一條Key-Value記錄可能存儲在一個塊中，也可能存儲在連續(xù)的多個塊中，如圖2和圖3所示。

圖2 數(shù)據(jù)記錄、物理塊、日志文件結構

圖3 數(shù)據(jù)在日志文件中的存儲格式

類型包括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沒有存儲，這些只能依次放在后續(xù)的物理塊，因為Block 2大小只有32 KB，仍然放不下B的剩余部分，所以Block 2全部用來放B，且標識類型為MIDDLE，表示這是B中間的一段數(shù)據(jù)；B剩下的部分可以完全放在Block 3中，類型標識為LAST，代表了這是B的末尾數(shù)據(jù)；C因為大小為12 KB，Block 3剩下的空間足以全部放下它，所以其類型標識為FULL。讀取數(shù)據(jù)時根據(jù)記錄類型來拼接出邏輯記錄，供后續(xù)流程處理。由于一次物理讀取為一個塊，因此加快了讀取磁盤日志的速度，從而提高數(shù)據(jù)恢復的效率[13]。

5 SSTable文件

當Memtable占用內(nèi)存的容量達到一個門限值時，則自動轉換為Immutable Memtable，后臺調度會將Immutable Memtable的數(shù)據(jù)導出到磁盤，形成一個新的SSTable文件。SSTable就是由內(nèi)存中的數(shù)據(jù)不斷導出并進行歸并操作后形成的，所有的SSTable文件構成一種層級結構，對于磁盤中的數(shù)據(jù)來說，level0是最新的，level1次之，level2再次之，逐層遞減，數(shù)據(jù)由低層向高層歸并，在歸并的過程中去掉重復的數(shù)據(jù)并刪除已被打上刪除標記的數(shù)據(jù)。

傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)在存儲數(shù)據(jù)時一般是key無序的，通過建立有序的索引來對數(shù)據(jù)進行快速定位，而SSTable中的文件是由后臺異步導出和歸并排序產(chǎn)生的，并不會影響數(shù)據(jù)的讀寫過程，因此可以將數(shù)據(jù)按key有序存儲，為了提高查找效率，可以用多個文件來分開存儲數(shù)據(jù)，每個文件存儲一個范圍內(nèi)的key數(shù)據(jù)記錄，這樣只需存儲每個文件的最小key和最大key就可以快速定位要查找的記錄在哪個文件當中。

SSTable和Log一樣都將文件劃分為固定大小的物理塊，每個塊分為3個部分：數(shù)據(jù)存儲區(qū)，數(shù)據(jù)壓縮類型(Snappy壓縮[14]或者無壓縮2種)，CRC數(shù)據(jù)校驗碼[15]。但是由于Log文件中的記錄是Key無序的，而SSTable文件中的記錄是key有序的，因此在邏輯結構上存在著很大的差別。將SSTable文件劃分為數(shù)據(jù)存儲區(qū)和數(shù)據(jù)管理區(qū)，數(shù)據(jù)存儲區(qū)存放實際的數(shù)據(jù)記錄，因為數(shù)據(jù)記錄是key有序的，所以在數(shù)據(jù)管理區(qū)就可以提供一些索引指針等管理數(shù)據(jù)，從而更快速高效地查找相應的記錄。

SSTable文件中數(shù)據(jù)記錄是key有序的，因此相鄰的 2條記錄在key部分很可能存在重疊，比如key[5]=“test5”，Key[6]=“test6”，那么兩者存在重疊的部分test，為了減少key的存儲量，下一個key可以只存儲和上一條key不同的部分，而兩者的共同部分可以從上一個key中獲得。在每個數(shù)據(jù)存儲塊中，每條數(shù)據(jù)記錄的內(nèi)部結構如圖4所示，每條記錄包含5個字段：key共享長度，比如上文的key[6]記錄，它的key和上一條記錄key[5]共享的key部分的長度是test的長度，即4；key非共享長度，對于key[6]來說，非共享的長度是6的長度，即1；value長度以及最后面的value內(nèi)容字段中存儲實際的value值；而key非共享內(nèi)容則實際存儲6這個key字符串。

圖4 數(shù)據(jù)在SSTable文件中的存儲格式

6 Compaction過程

SSDB的寫入操作很簡單，刪除記錄也僅僅是寫入一個刪除標記，但讀取過程相對較復雜，需要在內(nèi)存以及各個SSTable層級文件中根據(jù)時間順序依次查找，代價很高。為加快讀取速度，運用BigTable中的Minor Compaction方式和Major Compaction方式來對已有數(shù)據(jù)記錄進行整理壓縮，刪除掉一些無效的數(shù)據(jù)，減小數(shù)據(jù)規(guī)模和文件數(shù)量等。

Minor Compaction方式就是簡單地在磁盤上新建一個 第0層的SSTable文件，并將MemTable中的數(shù)據(jù)導出到SSTable文件；Major Compaction通過合并不同層級的SSTable文件，對多個文件進行多路歸并排序，然后依次判斷各個Key記錄是否還需要保存，如果不需要則直接丟棄，否則就將其寫入下一層中新生成的一個SSTable文件中，最后刪除掉參與Compaction過程的SSTable文件，從而減少數(shù)據(jù)的存儲空間和文件數(shù)量，提高從SSTable文件中查找數(shù)據(jù)的效率。

7 Cache機制

Compaction過程使得系統(tǒng)從磁盤中讀取數(shù)據(jù)的性能有了一定的提升，但是直接從磁盤中讀取數(shù)據(jù)依然效率低下，如果數(shù)據(jù)在SSTable文件中，則需要進行多次磁盤訪問操作，在最優(yōu)的情況下，即要找的數(shù)據(jù)在第0層，也需要 2次磁盤讀操作，第1次將SSTable文件中的索引部分讀入內(nèi)存，然后根據(jù)索引就可以確定key是在哪個物理塊中存儲；第2次讀入這個物理塊的內(nèi)容，然后在內(nèi)存中查找。

為了減少磁盤訪問的次數(shù)，使用了2種Cache：Table Cache和Block Cache。其中，Table Cache緩存SSTable文件的索引信息，Block Cache緩存物理塊內(nèi)容。從磁盤中查找數(shù)據(jù)時，首先判斷key在哪個SSTable文件中，然后檢查該SSTable文件是否在Table Cache中，若不在則讀取該SSTable文件并將其緩存，若在則通過索引定位到物理塊，并檢查該物理塊是否在Block Cache中，若不在則將該物理塊讀入內(nèi)存并緩存，若在則直接在內(nèi)存中查找。

SSDB就是通過這2個Cache來加快讀取速度的。如果讀取的數(shù)據(jù)局部性比較好，則性能會有明顯的提高。由于Cache容量有限，而新訪問的數(shù)據(jù)一般都會被Cache，因此容量滿后采用LRU算法和FiveMinuteRule[16]原則進行替換，F(xiàn)iveMinuteRule原則即如果數(shù)據(jù)被訪問的頻率在5 min以內(nèi)，那么就應該盡量將該數(shù)據(jù)寫入到內(nèi)存中去。

8 Bloom Filter過濾器

在數(shù)據(jù)的讀取過程中，如果數(shù)據(jù)不在內(nèi)存中，則會去磁盤中找，現(xiàn)在假設一種極端的情況，要查找的數(shù)據(jù)不在緩存系統(tǒng)中，則數(shù)據(jù)的查找過程將要經(jīng)歷內(nèi)存中的MemTable、Immutable MemTable和磁盤中的各層SSTable文件，而最后返回數(shù)據(jù)不存在，筆者無法容忍這種極端情況下的性能損失。因此，為了快速判斷要查找的數(shù)據(jù)是否在緩存系統(tǒng)中，從而避免不必要的查找過程，使用了一種多哈希函數(shù)映射的快速查找算法——布隆過濾器[17]，該算法能夠非?？焖俚嘏卸硞€元素是否在一個集合之外。這種判定只會對在集合內(nèi)的數(shù)據(jù)錯判，而不會對集合外的數(shù)據(jù)錯判，這樣如果判定數(shù)據(jù)不在緩存系統(tǒng)中，則可快速認定該數(shù)據(jù)不在，有效地提高了系統(tǒng)的讀操作性能。

9 一致性哈希

SSDB是一個分布式的緩存系統(tǒng)，將數(shù)據(jù)均勻分散地存儲到多臺緩存服務器上，假如有個服務器，采用傳統(tǒng)的hash映射算法hash(key)%，則會遇到如下2個問題：

(1)一個服務器宕機了，這樣所有映射到的數(shù)據(jù)都會失效，然后需要把移除，這時候映射公式變成了hash(key)%(-1)。

(2)由于訪問加重，需要添加服務器，這時候服務器是+1臺，映射公式變成了hash(key)%(+1)。

映射公式的改變意味著突然之間幾乎所有的Cache都失效了。對于服務器而言，這是一場災難，洪水般的訪問都會直接沖向后臺服務器[18]。為了解決上面的問題，使用了一致性哈希算法[19]。

Consistent Hashing的基本思想就是將對象和Cache都映射到同一個Hash數(shù)值空間中，并使用相同的Hash算法。如圖5所示，假設當前有A、B和C共3臺Cache，hash(Cache A)=key A，hash(Cache B)=key B，hash(Cache C)=keyC。

圖5 Cache和對象的key值分布

在這個環(huán)形空間中，如果沿著順時針方向從對象的key值出發(fā)，直到遇見一個Cache對應的key，那么就將該對象存儲在這個Cache上，因為對象和Cache的hash值是固定的，所以這個Cache必然是唯一和確定的。

現(xiàn)在假設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上，映射不均。為此，在其中添加了很多的虛擬節(jié)點，然后建立實際服務器和虛擬節(jié)點的對應關系，如圖7所示，實際服務器Cache A對應2個虛擬節(jié)點Cache A1和A2，只要是映射到虛擬節(jié)點A1和A2上的對象都將存儲到Cache A上，因此，Cache A中存儲了object1和object2；Cache C中存儲了object3和object4，從而實現(xiàn)了相對簡單的負載均衡。

圖7 引入虛擬節(jié)點后的Cache映射

10 主從同步與讀寫分離

假如有20億的數(shù)據(jù)量和4臺緩存服務器，則在負載均衡的情況下，每臺大約有5億的數(shù)據(jù)量，如果數(shù)據(jù)訪問比較集中，則會出現(xiàn)在單臺服務器上大量的數(shù)據(jù)訪問，由于單機的吞吐量和性能有限，從而使得該服務器無法承受，因此運用了傳統(tǒng)關系數(shù)據(jù)庫中的主從同步、讀寫分離策略，通過單點寫多點讀的主從同步架構有效地提高了系統(tǒng)的讀寫性能。

主從同步的實現(xiàn)比較簡單，如圖8所示。選擇一臺服務器作為master，多臺服務器作為slave，master負責寫操作，多個slave負責讀操作，master的寫操作將會先寫日志，一旦寫入日志，就會在下一個同步周期同步到slave，為了使系統(tǒng)不受網(wǎng)絡抖動的影響，同步支持斷點續(xù)傳。由于不是立刻同步，因此從slave中讀取數(shù)據(jù)會有些許延遲，但是該架構可以有效地提高系統(tǒng)的吞吐量[20]。

圖8 主從復制與讀寫分離示意圖

11 性能測試

用PHP和Python編寫測試代碼分別對SSDB和Redis進行性能測試，PHP代碼產(chǎn)生到服務器的請求，Python代碼負責并發(fā)的執(zhí)行PHP代碼從而產(chǎn)生并發(fā)的請求。用SSDB-set、SSDB-get、Redis-set、Redis-get分別表示SSDB寫、SSDB讀、Redis寫、Redis讀，SSDB-set--表示在SSDB服務器上已有個寫、個讀持久請求的情況下再執(zhí)行一次寫操作測試。

在每完成1 000次請求后，服務器計算出請求的平均處理速度，單位為QPS(Query Per Second)，即單個進程每秒請求服務器的成功次數(shù)=總請求數(shù)/(總進程數(shù)′請求時間)。將測試結果放在Highcharts插件中展示，如圖9和圖10所示。從圖中可以看出，總體上SSDB的讀寫性能大致低于Redis 600 QPS左右，因為SSDB打破了Redis內(nèi)存容量的限制，當內(nèi)存容量不足時，數(shù)據(jù)會被寫入到磁盤，而不會像Redis那樣選擇丟棄，同時也不會像Memcached那樣使用LRU算法丟棄舊數(shù)據(jù)，由于大部分數(shù)據(jù)會被寫入到磁盤，因此性能會有所下降，但是SSDB運用了Bigtable的Merge- Dump存儲引擎以及LSM-Tree思想，將隨機寫轉換成順序寫，充分利用了磁盤的順序訪問特性，使得SSDB的寫性能并沒有下降太多，同時SSDB對磁盤中的數(shù)據(jù)進行了歸并排序以及建立索引和Cache等，也有效地保證了系統(tǒng)的讀性能。

圖9 沒有任何讀寫請求時加一次讀寫請求的測試結果

圖10 已有1寫4讀持久請求時加一次讀寫請求的測試結果

12 結束語

SSDB是一個高效的Key-Value持久化緩存系統(tǒng)，與Redis相比，SSDB支持數(shù)據(jù)的持久化，使得系統(tǒng)不受內(nèi)存容量的限制，并且在系統(tǒng)發(fā)生故障或者宕機后不會丟失數(shù)據(jù)，同時優(yōu)化后SSDB的讀寫性能在整體上只是略有下降。因此，SSDB特別適用于當今的海量數(shù)據(jù)規(guī)模應用。目前SSDB已經(jīng)支持PHP、Java、C++等編程語言，未來還將會對它的性能和可用性做進一步的優(yōu)化和完善，特別是在一致性哈希上，決定采用Amazon的分布式Key-Value存儲引擎Dynamo[21]架構的實現(xiàn)方案，Dynamo架構在一致性哈希上做了更多的改進，支持數(shù)據(jù)同時存儲在多個物理節(jié)點上，是一個去中心化的分布式系統(tǒng)，因而使得系統(tǒng)在容錯上不會有任何的單點故障，同時還節(jié)約了服務器成本。

[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] 楊 艷, 李 煒, 王 純. 內(nèi)存數(shù)據(jù)庫在高速緩存方面的應用[J]. 現(xiàn)代電信科技, 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. 數(shù)據(jù)庫系統(tǒng)實現(xiàn)[M]. 楊冬青, 譯. 北京: 機械工業(yè)出版社, 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性能調優(yōu)與架構設計[M]. 北京: 電子工業(yè)出版社, 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

中央高?；究蒲袠I(yè)務費專項基金資助項目(CDJZR10180014)。

羅 軍(1961－)，男，副教授、碩士，主研方向：數(shù)據(jù)庫技術，大型MIS系統(tǒng)建模及設計，基于數(shù)據(jù)庫的應用系統(tǒng)平臺； 陳席林、李文生，碩士研究生。

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