改進的key/value數(shù)據(jù)存儲設(shè)計方案

何 文

(東北電力大學(xué)信息工程學(xué)院，吉林吉林132012)

緩存系統(tǒng)的應(yīng)用是網(wǎng)站架構(gòu)的核心，因此，要提高網(wǎng)站的性能和穩(wěn)定性，必須選擇優(yōu)秀的緩存系統(tǒng)?，F(xiàn)在的緩存系統(tǒng)大多以key/value存儲數(shù)據(jù)，比較典型的緩存系統(tǒng)有:Memached、Oscache、Ehcache、redis等。其中Memached因其簡單高效、穩(wěn)定性好等特點，被廣泛應(yīng)用到互聯(lián)網(wǎng)緩存系統(tǒng)架構(gòu)中。但是Memached在key/value存儲方案中存在數(shù)據(jù)沖突和rehash導(dǎo)致數(shù)據(jù)遷移兩大問題，將其應(yīng)用到互聯(lián)網(wǎng)緩存系統(tǒng)架構(gòu)中也間接導(dǎo)致了網(wǎng)站訪問速度慢和系統(tǒng)崩潰等問題。本文所提的改進緩存系統(tǒng)有效地彌補了如今web緩存系統(tǒng)本身存在海量數(shù)據(jù)速度訪問慢，滿足不了應(yīng)用需求的不足［1］。實驗表明，改進的緩存系統(tǒng)提高了訪問速度。

1 key/value存儲模型

key/value典型實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)一般為數(shù)組鏈表，利用hash算法均勻分布在hash桶中即存放在數(shù)組中，而hash沖突解決方法是開放鏈表法。

1.1 數(shù)組鏈表數(shù)據(jù)結(jié)構(gòu)

圖1 key/value存儲結(jié)構(gòu):先通過hashcode找到數(shù)組的某一個位置(通過hash算法得出hashcode)，然后插入鏈表的第一個位置;數(shù)據(jù)的查找過程:通過hashcode找到數(shù)組的某一個元素，然后通過key的相等方法在鏈表中找到key對應(yīng)的value元素。

1.2 解決沖突的方法

緩存系統(tǒng)解決沖突的方法是開放鏈表法，將所有為同義詞的結(jié)點鏈接在同一個單鏈表中。

優(yōu)點:拉鏈法處理沖突簡單，且無堆積現(xiàn)象，即非同義詞決不會發(fā)生沖突，因此平均查找長度較短;由于拉鏈法中各鏈表上的結(jié)點空間是動態(tài)申請的，故它更適合于無法確定表長的情況;開放鏈表法為了減少沖突，故而引入裝填因子α，拉鏈法中α值可取1＞α＞0。

缺點:指針需要額外的空間，故當結(jié)點規(guī)模較小時，開放鏈表法較為浪費存儲空間。

圖1 key/value存儲結(jié)構(gòu)

2 key/value存儲方案的改進

key/value存儲方案在軟件工程中有大量的應(yīng)用，尤其是在緩存系統(tǒng)中的應(yīng)用。由于添加的元素越來越多的時候key/value存儲發(fā)生碰撞的幾率越來越大，本節(jié)給出一種改進的存儲方案，主要包括權(quán)重因子、小數(shù)據(jù)量的存儲方案、改進rehash三方面內(nèi)容，最后給出測試結(jié)果。

2.1 權(quán)重因子的改進

當數(shù)組中的元素越來越多的時候，添加一個元素發(fā)生碰撞的幾率也就越來越高。因為數(shù)組的長度是固定的，所以為了提高查詢的效率，必須在數(shù)組里面留出一些空閑的位置，即權(quán)重因子α(0＜α＜1)，也就是權(quán)重因子設(shè)置的過大發(fā)生的碰撞的概率就會越大而設(shè)置過小存儲空間會十分的浪費，由于key/value存儲方案設(shè)計沒有專門的接口來動態(tài)的調(diào)整權(quán)重因子，所以在緩存應(yīng)用中要根據(jù)適當?shù)臋?quán)重因子來滿足需求，進而需要給用戶提供相應(yīng)的接口來調(diào)整權(quán)重因子的大?。?］。

2.2 小數(shù)據(jù)量存儲方案

該方案是為了在緩存系統(tǒng)中更大的節(jié)約內(nèi)存提出來的一種折中方案，該設(shè)計方案只適用于當存放hash桶中元素比較少時(存放少于254個元素)適用。本文引入的數(shù)據(jù)結(jié)構(gòu)zipmap，一個元素(key/value)在zipmap中有5部分組成，如圖2 zipmap存儲結(jié)構(gòu)所示:

len:表示key/value字符串的長度，如果字符串的長度小于254使用一個字節(jié)保存，否則就使用5個字節(jié)來保存;free:當修改已有的key1對應(yīng)的value值且新的value值小于已有value值時不會對空間進行回收，只有當free為4即空閑的字節(jié)數(shù)為4個字節(jié)時才會回收空閑的空間。這樣設(shè)計的目的是為了避免大量的修改key中value值時，造成不必要的元素移動從而影響性能。

2.3 rehash 改進

由于數(shù)組里面的元素裝載過多，hash算法就會發(fā)生碰撞，所以數(shù)組里面的元素達到了權(quán)重因子的比率就要對數(shù)組擴容，最消耗性能的點就出現(xiàn)了:原數(shù)組中的數(shù)據(jù)必須重新計算其在新數(shù)組中的位置，并放進新的數(shù)組里。這個也是在當今key/value存儲處理的一個瓶頸，如何讓它平緩的滑動元素，所以就引入了一個對rehash改進的思想。本文使用了兩個數(shù)組，目的是為了在rehash的時候可以平滑地遷移新的數(shù)組里，而對比現(xiàn)有的key/value存儲方案將全部數(shù)據(jù)遷移到新的數(shù)組中，此操作是key/value存儲的瓶頸［3］。

圖2 zipmap存儲結(jié)構(gòu)

下文提出一個rehash改進事方案來解決key/value數(shù)據(jù)遷移問題，如圖3 rehash的數(shù)據(jù)結(jié)構(gòu)。

大的長方形表示dictht數(shù)據(jù)結(jié)構(gòu)，小的長方形表示dicth數(shù)據(jù)結(jié)構(gòu)即數(shù)組鏈表，dictht的數(shù)據(jù)結(jié)構(gòu)由size、dictEntry、sizemask、used 組成，dictht的數(shù)據(jù)結(jié)構(gòu)是由 rehashidx、兩個 dicth 組成。

圖4對添加一個key/value元素流程圖的分析:

圖3 rehash數(shù)據(jù)結(jié)構(gòu)

圖4 添加元素流程圖

它實際上是一個指針數(shù)組，數(shù)組的個數(shù)由size決定，每個元素(bucket)指向一個dictEntry的單鏈表來解決hash沖突。查詢某個key，需要先hash，定位到數(shù)組某一個元素然后再通過鏈表遍歷找到key對應(yīng)的value值。圖5是針對rehash的流程圖:

第二個 hash桶就是為了rehash而產(chǎn)生，新的hash桶的大小是舊hash桶的兩倍，每一次元素的添加和元素的查找都會進行一次rehash:舊hash桶的每個bucket會rehash加入到新的hash桶里。rehashidx是舊的hash桶需要rehash即遷移到新的hash桶中bucket的索引，從0開始直到舊的hash桶的used等于0。

rehash期間:由于新的hash桶是舊hash桶大小的2倍，每次添加元素時候都會rehash一次，不會出現(xiàn)新的hash桶滿了后而舊的hash桶還有數(shù)據(jù)。元素的查詢會先查舊的hash桶再查詢新的hash桶，在rehash的過程中，不會出現(xiàn)再次擴容［4］。

2.4 改進key/value存儲方案的測試

圖5 rehash的流程圖

本文對改進的key/value存儲進行了測試，測試環(huán)境:Windows XP2000、1G內(nèi)存。

表1 測試插入數(shù)據(jù)結(jié)果對比

由表1可知，當插入元素個數(shù)較少時，改進key/value消耗時間稍長，但是當插入過多的元素時，改進key/value消耗的時間明顯比未改進key/value耗時短。當插入80 000個元素時，未改進key/value存儲耗時大約是改進key/value存儲的3倍，從而驗證了大數(shù)量添加的時候數(shù)據(jù)平滑的移動。

表2 測試權(quán)重因子結(jié)果對比

由表2可知，不同的權(quán)重因子耗時是不一樣，進而得出需要一個合適的權(quán)重因子提高存儲效率，表中得出的結(jié)論權(quán)重因子0.75存儲速度耗時最少。

表3 小數(shù)據(jù)量方案存儲和未改進的key/value存儲對比結(jié)果

表3可知，小的數(shù)據(jù)量對于改進和未改進的key/value存儲，存儲的速度沒有變化，但是小數(shù)據(jù)量存儲方案節(jié)約內(nèi)存。

3 結(jié) 論

key/value存儲是緩存系統(tǒng)的核心。由于緩存系統(tǒng)應(yīng)用在很多互聯(lián)網(wǎng)公司，優(yōu)秀健壯的緩存系統(tǒng)已成為研究熱點之一。本文在標準key/value存儲方案基礎(chǔ)上提出了一種改進的key/value存儲，通過對測試數(shù)據(jù)分析，表明改進的key/value存儲速度明顯加快且，對于小數(shù)據(jù)量節(jié)約內(nèi)存，為公司成本減少開銷。

［1］樂立鸞，李明.Web應(yīng)用系統(tǒng)性能優(yōu)化［J］.科技信息，2007，13(22):294- 295.

［2］張柏禮，呂建華，姚蓓等.Web代理服務(wù)器緩存置換算法研究［J］.計算機科學(xué)與探索，2010，4(11):112-114.

［3］吳繼楠.淺論計算貢緩存工作機制［J］，科技信息，2007，27(6):650-652.

［4］石磊，葉海琴，衛(wèi)琳等.Web緩存命中率與字節(jié)命中率關(guān)系［J］.計算機工程，2007，9(18):84-86.