改進的key/value數據存儲設計方案

何 文

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

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

1 key/value存儲模型

key/value典型實現的數據結構一般為數組鏈表，利用hash算法均勻分布在hash桶中即存放在數組中，而hash沖突解決方法是開放鏈表法。

1.1 數組鏈表數據結構

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

1.2 解決沖突的方法

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

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

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

圖1 key/value存儲結構

2 key/value存儲方案的改進

key/value存儲方案在軟件工程中有大量的應用，尤其是在緩存系統中的應用。由于添加的元素越來越多的時候key/value存儲發生碰撞的幾率越來越大，本節給出一種改進的存儲方案，主要包括權重因子、小數據量的存儲方案、改進rehash三方面內容，最后給出測試結果。

2.1 權重因子的改進

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

2.2 小數據量存儲方案

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

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

2.3 rehash 改進

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

圖2 zipmap存儲結構

下文提出一個rehash改進事方案來解決key/value數據遷移問題，如圖3 rehash的數據結構。

大的長方形表示dictht數據結構，小的長方形表示dicth數據結構即數組鏈表，dictht的數據結構由size、dictEntry、sizemask、used 組成，dictht的數據結構是由 rehashidx、兩個 dicth 組成。

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

圖3 rehash數據結構

圖4 添加元素流程圖

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

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

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

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

圖5 rehash的流程圖

本文對改進的key/value存儲進行了測試，測試環境:Windows XP2000、1G內存。

表1 測試插入數據結果對比

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

表2 測試權重因子結果對比

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

表3 小數據量方案存儲和未改進的key/value存儲對比結果

表3可知，小的數據量對于改進和未改進的key/value存儲，存儲的速度沒有變化，但是小數據量存儲方案節約內存。

3 結 論

key/value存儲是緩存系統的核心。由于緩存系統應用在很多互聯網公司，優秀健壯的緩存系統已成為研究熱點之一。本文在標準key/value存儲方案基礎上提出了一種改進的key/value存儲，通過對測試數據分析，表明改進的key/value存儲速度明顯加快且，對于小數據量節約內存，為公司成本減少開銷。

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

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

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

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