何 文

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

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

1 key/value存儲模型

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

1.1 數組鏈表數據結構

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

1.2 解決沖突的方法

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

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

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

圖1 key/value存儲結構

2 key/value存儲方案的改進

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

2.1 權重因子的改進

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

2.2 小數據量存儲方案

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

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

2.3 rehash 改進

由于數組里面的元素裝載過多，hash算法就會發(fā)生碰撞，所以數組里面的元素達到了權重因子的比率就要對數組擴容，最消耗性能的點就出現了:原數組中的數據必須重新計算其在新數組中的位置，并放進新的數組里。這個也是在當今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存儲進行了測試，測試環(huán)境: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存儲，存儲的速度沒有變化，但是小數據量存儲方案節(jié)約內存。

3 結 論

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

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

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

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

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