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

羅 軍，陳席林，李文生

?

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

羅 軍，陳席林，李文生

(重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044)

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

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

1 概述

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

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

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

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

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

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

2 SSDB系統(tǒng)架構(gòu)

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

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

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

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

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

(3)后臺進(jìn)程定期對SSTable文件進(jìn)行歸并排序，形成有層次的SSTable文件結(jié)構(gòu)。

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

3 內(nèi)存中的MemTable結(jié)構(gòu)

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

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

4 Log文件

Log文件主要是用于系統(tǒng)宕機(jī)后恢復(fù)數(shù)據(jù)，假如沒有Log文件，因?yàn)閯倢懭氲挠涗浭潜４嬖趦?nèi)存中的，此時(shí)如果系統(tǒng)宕機(jī)，內(nèi)存中的數(shù)據(jù)沒有來得及Dump到磁盤，從而會丟失數(shù)據(jù)。為了避免這種情況，采取先寫日志再寫內(nèi)存[12]的策略，這樣即使系統(tǒng)宕機(jī)，也可以從Log文件中恢復(fù)，不會造成數(shù)據(jù)的丟失。

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

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

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

類型包括FULL、FIRST、MIDDLE、LAST，如果記錄類型是FULL，則代表當(dāng)前記錄完整地存儲在一個(gè)物理塊中，沒有被不同的物理塊切割開。假設(shè)有3條記錄Record A、B和C，其中，A大小為10 KB，B為80 KB，C為12 KB，如圖2所示，由于A為10 KB<32 KB，能夠放在一個(gè)物理塊中，因此其類型為FULL；而Block 1因?yàn)榉湃肓薃，還剩下22 KB，不足以放下B，所以在Block 1的剩余部分放入B的開頭一部分，類型標(biāo)識為FIRST，代表了是一個(gè)記錄的起始部分；B還有58 KB沒有存儲，這些只能依次放在后續(xù)的物理塊，因?yàn)锽lock 2大小只有32 KB，仍然放不下B的剩余部分，所以Block 2全部用來放B，且標(biāo)識類型為MIDDLE，表示這是B中間的一段數(shù)據(jù)；B剩下的部分可以完全放在Block 3中，類型標(biāo)識為LAST，代表了這是B的末尾數(shù)據(jù)；C因?yàn)榇笮?2 KB，Block 3剩下的空間足以全部放下它，所以其類型標(biāo)識為FULL。讀取數(shù)據(jù)時(shí)根據(jù)記錄類型來拼接出邏輯記錄，供后續(xù)流程處理。由于一次物理讀取為一個(gè)塊，因此加快了讀取磁盤日志的速度，從而提高數(shù)據(jù)恢復(fù)的效率[13]。

5 SSTable文件

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

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

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

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

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

6 Compaction過程

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

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

7 Cache機(jī)制

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

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

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

8 Bloom Filter過濾器

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

9 一致性哈希

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

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

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

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

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

圖5 Cache和對象的key值分布

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

現(xiàn)在假設(shè)Cache B宕機(jī)，這時(shí)受影響的將僅是那些沿著Cache B逆時(shí)針遍歷直到上一個(gè)Cache A之間的對象，即原本映射到Cache B上的那些對象。因此這里僅需要變動對象object4，將其重新映射到Cache C上即可，如圖6 所示。

圖6 Cache B被移除后的對象key映射

由于hash映射無法保證分配的絕對均衡，如果Cache較少，則對象并不能被均勻地映射到Cache上，假設(shè)僅有 2臺服務(wù)器A和C，如圖6所示，則object1映射到Cache A上，而object2、object3、object4則都映射到Cache C上，映射不均。為此，在其中添加了很多的虛擬節(jié)點(diǎn)，然后建立實(shí)際服務(wù)器和虛擬節(jié)點(diǎn)的對應(yīng)關(guān)系，如圖7所示，實(shí)際服務(wù)器Cache A對應(yīng)2個(gè)虛擬節(jié)點(diǎn)Cache A1和A2，只要是映射到虛擬節(jié)點(diǎn)A1和A2上的對象都將存儲到Cache A上，因此，Cache A中存儲了object1和object2；Cache C中存儲了object3和object4，從而實(shí)現(xiàn)了相對簡單的負(fù)載均衡。

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

10 主從同步與讀寫分離

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

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

圖8 主從復(fù)制與讀寫分離示意圖

11 性能測試

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

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

圖9 沒有任何讀寫請求時(shí)加一次讀寫請求的測試結(jié)果

圖10 已有1寫4讀持久請求時(shí)加一次讀寫請求的測試結(jié)果

12 結(jié)束語

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

[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ù)庫在高速緩存方面的應(yīng)用[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)實(shí)現(xiàn)[M]. 楊冬青, 譯. 北京: 機(jī)械工業(yè)出版社, 2001.

[13] 朗格科技. levelDB技術(shù)[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性能調(diào)優(yōu)與架構(gòu)設(shè)計(jì)[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

中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)基金資助項(xiàng)目(CDJZR10180014)。

羅 軍(1961－)，男，副教授、碩士，主研方向：數(shù)據(jù)庫技術(shù)，大型MIS系統(tǒng)建模及設(shè)計(jì)，基于數(shù)據(jù)庫的應(yīng)用系統(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