郎泓鈺　任永功

(遼寧師范大學計算機與信息技術學院　遼寧 大連 116081)

?

基于Redis內存數(shù)據(jù)庫的快速查找算法

郎泓鈺任永功

(遼寧師范大學計算機與信息技術學院遼寧 大連 116081)

摘要大數(shù)據(jù)時代的到來，使許多云環(huán)境下的新型應用蓬勃發(fā)展。針對大數(shù)據(jù)管理的新需求，key-value型數(shù)據(jù)存儲系統(tǒng)成為當今研究的熱點。基于key-value引擎的內存數(shù)據(jù)庫Redis以及Cuckoo Hash技術，提出一種混合哈?？焖俨檎宜惴–SR_Hash。通過對實驗結果的分析，表明該算法有效地縮短了查詢響應時間，并將其應用在通過Hadoop云平臺以及Map/Reduce編程模型實現(xiàn)的圖書銷售系統(tǒng)中，對圖書數(shù)據(jù)進行實時高效的解析與推薦，增強了NoSQL數(shù)據(jù)庫與Map/Reduce結合的實時性和高并發(fā)性。

關鍵詞key-value型存儲系統(tǒng)Redis數(shù)據(jù)庫Map/ReduceCuckoo hash

0引言

隨著移動互聯(lián)技術的高速發(fā)展，網(wǎng)絡上的數(shù)據(jù)量成指數(shù)性增長。針對大數(shù)據(jù)管理的新需求，面向特定應用的NoSQL數(shù)據(jù)庫應運而生[1,2]。key-value存儲系統(tǒng)成為當下比較流行的話題，尤其是在構建搜索引擎以及提供云計算服務的時候，如何保證系統(tǒng)在海量數(shù)據(jù)環(huán)境下的高性能、高可靠性、高擴展性及低成本成為研究重點[3-5]。其中Redis數(shù)據(jù)庫通過把數(shù)據(jù)保存在內存中或者使用虛擬內存技術來提高系統(tǒng)的使用效率，同時Redis采用key-value存儲模式來加速鍵值對內容的排序與定位。

在日常生活中，人們經(jīng)常需要使用搜索引擎來解決實際問題，其中一項關鍵的技術就是數(shù)據(jù)查找。在key-value型數(shù)據(jù)庫當中，哈希查找方法由于其查找速度快，維護方便等原因而得到廣泛的應用[6-8]。

1基于Redis的快速查找算法

1.1Redis簡介

作為key-value型內存數(shù)據(jù)庫，Redis提供了鍵(key)和值(value)的映射關系，而且它支持多種不同的數(shù)據(jù)類型。目前，新浪微博作為最大的Redis用戶，已有400多個端口在同時運行著Redis，進而實時并快速滿足用戶對微博消息的查看與轉發(fā)功能[9]。Redis數(shù)據(jù)庫基于內存的特性使其具有優(yōu)秀的讀操作速度。因此，基于Redis數(shù)據(jù)庫的系統(tǒng)在進行查找操作時，可以在納秒級的時間內得到匹配結果。

1.2基于Redis的前綴匹配

Redis數(shù)據(jù)庫同樣提供了很好的索引機制，以實現(xiàn)高性能的實時搜索。基于Redis研究者已經(jīng)實現(xiàn)了不同的搜索功能。這里我們主要討論用于前綴匹配的索引。

形如谷歌、百度、雅虎等許多搜索引擎，當用戶在界面的搜索框里輸入短語或標題時，搜索框下方會自動根據(jù)用戶的輸入從后端數(shù)據(jù)庫里匹配一些相關的內容。這個搜索過程是很快的，在按鍵的一瞬間就會出現(xiàn)一些提示，這些提示按該短語被搜索的次數(shù)進行排名，進而可以幫助用戶快速找到想要搜索的事物；同樣，一些用戶在進行搜索的時候不太確定他想找的東西是什么，但是大概了解，這一提示還可以幫助這類用戶完成查詢功能。Redis會把每一個字母進行拆分，然后放到Centre里去，它會自動按照字母的方式進行排序，如同建了一個索引一樣。在查詢的時候就可以按照這個順序進行查找；在對關鍵詞進行索引時，是通過分詞的方式把一個標題分成很多個詞語，然后在Redis里建一個ID庫，成立一個數(shù)據(jù)的列表。在前綴匹配的搜索過程中，當用戶在搜索“Computer”的時候，首先肯定會按“C”鍵，Redis會根據(jù)這個字母找到其在前綴索引中的第一個坐標，并找到里面標記順序的序號。然后根據(jù)這個序號找一段詞，之后會列出相關的實際詞的內容，這個時候再根據(jù)這些實際詞找出其對應的ID，最后通過ID找出這些數(shù)據(jù)，顯示結果。

1.3改進的排序查找算法CSR_Hash

在key-value數(shù)據(jù)存儲模型中，比較典型的是采用哈希函數(shù)來實現(xiàn)鍵到值的映射。在進行查找操作時，基于key的Hash值可以直接定位到數(shù)據(jù)所在的點，從而達到快速尋址的目的，并支持大數(shù)據(jù)量和高并發(fā)查詢。為了進一步提高查詢效率，提出了一種基于Redis內存數(shù)據(jù)庫及Cuckoo Hash[10-15]方法的快速排序查找算法CSR_Hash。

1.3.1Hash沖突

使用Hash函數(shù)H可以加速鍵key的索引進程。然而，由于數(shù)據(jù)集中各元素鍵的取值可能有一個很大的范圍，所以即使當數(shù)據(jù)集中的元素個數(shù)不是很多時，也很難選取出一個合適的Hash函數(shù)H，使其保證對于任意不同的keyi和keyj有H(keyi)≠H(keyj)。若keyi≠keyj而H(keyi)=H(keyj)，則這種現(xiàn)象稱為哈希沖突。在哈希技術中，沖突是不可避免的，只能盡量減少沖突的概率。因此哈希沖突處理是影響哈希表性能的主要因素。為了解決這一問題，通過選擇Cuckoo Hash法與鏈表法相結合的方式，建立一個公共溢出區(qū)，并添加鍵頻項來提高查找搜索的效率。

1.3.2Cuckoo Hash

Cuckoo Hash使用兩個Hash表Table1和Table2，兩個Hash函數(shù)，H1和H2。對于一個鍵key來說，表Table1和Table2分別使用Hash函數(shù)H1和H2來創(chuàng)建key在Table1和Table2中的地址，如圖1所示。

圖1　Cuckoo Hash表

在進行插入操作時，Cuckoo Hash首先根據(jù)哈希函數(shù)H確定key在這兩個Table中的地址。如果其中一個地址為空，就可以直接存儲到該地址；若兩個地址均被占用，則將這兩個地址中的一個key移到其自己的第二個Hash地址中。由于每個key都使用兩個不同的地址進行存儲，因此這個過程會循環(huán)往復，直到找到空閑地址為止。該算法可以提供恒定的查找時間O(1)(查找只要求檢查Hash表中的兩個位置)，而插入時間則取決于高速緩存的大小O(n)。

與鏈地址法和線性探測法相比，Cuckoo Hash法提供了更加快捷和可靠的查找、刪除以及更新操作，但其在插入操作過程中對內存的開銷是不容忽視的。

1.3.3改進的CSR_Hash算法

本文提出了一種基于Cuckoo Hash及鏈地址法處理沖突的混合哈希表查找方法，并在哈希表結構中添加用來提供查找對比的鍵頻項count。count用來存儲一段時間內該元素被查找的頻率，由該元素被查詢次數(shù)除以哈希表中所有元素被查找的總次數(shù)計算得到。

改進的Cuckoo Hash表的建立過程如下：

(1) 獲得鍵key；

(2) 根據(jù)哈希函數(shù)H1、H2檢查Cuckoo Hash中兩個表Table1、Table2所對應的地址是否為空，如果其中一個為空，則直接插入到空地址當中；

(3) 否則根據(jù)哈希函數(shù)H3插入到鏈地址哈希表Table3中，并為其添加鍵頻項Lcount；

(4) 為Cuckoo Hash表中的數(shù)據(jù)元素添加鍵頻項Ccount，并通過直接采用快速排序算法，根據(jù)Ccount的值由大到小對鍵key進行排序，將出現(xiàn)概率大的分配在所需比較次數(shù)少的位置，從而提高哈希表的整體查找效率；

(5) 對鏈地址表中的數(shù)據(jù)元素同樣根據(jù)其Lcount的大小進行排序，將Lcount值大的元素上浮至鏈地址表的表頭；當系統(tǒng)空閑，或者鏈地址表中元素的Lcount值大于Cuckoo Hash表中元素的Ccount值時，鏈地址表中的元素將被移到Cuckoo Hash表中，以方便查找。

由于在鏈地址表中的插入操作比在Cuckoo Hash表中所花費的時間少得多，所以用兩種方法相結合的方式可以提高系統(tǒng)效率。

同樣，在進行查找操作時，首先根據(jù)H1、H2查找鍵key是否存在于Cuckoo Hash的兩個Table中，如果不存在于Cuckoo Hash的任何一個表中，則直接通過H3到鏈地址表Table3中進行查找。算法原理如圖2所示。

圖2　改進的CSR_Hash算法原理

2CSR_Hash算法在云圖書銷售系統(tǒng)中的設計與實現(xiàn)

圖3為云圖書銷售系統(tǒng)的總體設計。當Android或者PC端用戶通過瀏覽器登錄到系統(tǒng)的查詢頁面進行查找操作時，系統(tǒng)利用Ajax的異步性以及動態(tài)性，實時將需要查找的請求數(shù)據(jù)傳輸給云計算平臺中的NameNode節(jié)點；節(jié)點收到實時的請求數(shù)據(jù)后，利用云平臺的Map/Reduce框架執(zhí)行分布式操作，并結合改進后的CSR_Hash算法在云端的Redis數(shù)據(jù)庫中完成查找過程，來快速匹配出用戶需要的數(shù)據(jù)。之后通過云端HDFS文件系統(tǒng)將結果發(fā)送給前端。若沒有匹配到結果，則不予提示。

由于Redis是內存數(shù)據(jù)庫，當系統(tǒng)掉電時，數(shù)據(jù)將會丟失。因此本系統(tǒng)結合云計算平臺的數(shù)據(jù)庫Hbase，用來定時同步Redis數(shù)據(jù)庫中的數(shù)據(jù)。當Redis數(shù)據(jù)庫無法正常工作時，NameNode將直接訪問Hbase，進行查詢操作，以確保系統(tǒng)正常工作。

2.1基于Bootstrap與Ajax的前端搜索的請求實現(xiàn)

Bootstrap 是基于CSS、HTML和JavaS-cript設計Web應用程序中常用的前端開發(fā)技術，它可以搭建美觀且功能強大的網(wǎng)站。在本系統(tǒng)中，主要利用Bootstrap框架來設計搜索引擎的Web頁面部分。

Ajax是Web 2.0的核心技術[16]。不同于傳統(tǒng)的Web模式(請求-等待-響應)，它采用異步無刷新的交互方式，即通過Ajax引擎提交請求，服務器做出處理將結果送給客戶端，Ajax引擎再次響應進行信息的獲取，來實現(xiàn)“按需要獲取數(shù)據(jù)”的局部頁面更新效果，從而提高應用程序的效率。

Web前端請求query下發(fā)并從服務器端接收結果的實現(xiàn)過程為：

＄(″#query″).autocomplete

Source:function(request,response)

//source為輸入內容，有改變則發(fā)送請求

＄ajax

//實際發(fā)送的是Ajax請求

url : ″ajax/sug.do″

//發(fā)送請求的目的地址

dataType : ″json″

//數(shù)據(jù)類型為json

data :

query : (″#query″).val()

//發(fā)送查詢請求

Success:function(data)

//返回時將data填充對話框

2.2基于Map/Reduce的分布式查找算法

Map/Reduce是Google公司基于HDFS基礎上實現(xiàn)的一種針對海量數(shù)據(jù)處理的并行編程模型，利用它可以簡化程序員的開發(fā)工作。

Map/Reduce在任務處理時，主要采用“分而治之”的策略。首先把輸入的數(shù)據(jù)集拆分成N個數(shù)據(jù)塊并分配到不同的DataNode節(jié)點上，之后由多個DataNode節(jié)點通過“代碼找數(shù)據(jù)”的模式完成Map任務并生成中間數(shù)據(jù)；之后Reduce任務會對輸入的參數(shù)進行計算和匯總，來得到最終的計算結果。

將Map/Reduce編程模型與Redis數(shù)據(jù)庫相結合，可以提高系統(tǒng)的實時性和高并發(fā)性。具體的實現(xiàn)過程為：

//Map過程解析出關鍵字

Function Map(QuestAll,QuestKeyword)

LineMessage←QuestAll.toString();

JspQuest[]←LineMessage.split(″″);

If JspQuest[1].Indexof(″sug.jsp?query″)

QuestKeyword←JspQuest[1]..splite(″query=|″);

//Reduce過程查找排序

Function Reduce(QuestKeyword,Result.value)

Result.value←CSR_Hash(″QuestKeyword″);

2.3系統(tǒng)實現(xiàn)過程

為了提高本系統(tǒng)檢索模塊的效率，提升用戶的使用體驗，使用戶可以利用高效的搜索提示功能，完成檢索查找工作。因此在設計中，服務器端運用云計算相關技術，在使用因特爾酷睿i3處理器，百兆以太網(wǎng)網(wǎng)卡以及4 GB內存硬件的基礎上，利用開源的Cent OS作為云計算平臺的操作系統(tǒng)，在系統(tǒng)之上搭建了Hadoop-0.20.2版本的云集群，相關的節(jié)點配置如表1所示。

表1　節(jié)點配置表

如圖4所示，通過Hadoop云平臺提供的50070端口，我們可以查看該平臺文件系統(tǒng)實時的使用情況。

圖4　圖書銷售系統(tǒng)的節(jié)點信息

圖5為系統(tǒng)實現(xiàn)的效果圖。當用戶輸入字母“a”之后，輸入的內容會被實時下發(fā)到系統(tǒng)中，系統(tǒng)首先對輸入的數(shù)據(jù)進行關聯(lián)，然后對關聯(lián)的結果以評分的先后順序進行排序，之后把排名前五位的結果返回到Web前端。當用戶再次輸入字母“l(fā)”之后，由于沒有使用空格等分隔符，因此這里沒有進行分詞操作，而是直接作為一個詞，繼續(xù)進行關聯(lián)排序，最終獲得結果，傳送到前端顯示。

圖5　系統(tǒng)實現(xiàn)效果圖

3實驗結果分析

為了測試改進后算法的性能，在圖書銷售系統(tǒng)中進行兩個實驗。

實驗一在單節(jié)點實驗環(huán)境中，完成相同查找任務的前提下，鏈地址哈希法Chained_Hash、Cuckoo Hash法及改進后的查找方法CSR_Hash用時情況如圖6所示。

圖6　完成相同查找任務的前提下三種算法在時間花銷上的對比

實驗二完成相同查找任務的前提下，分別在計算節(jié)點為1～6時對改進后的查找算法進行測試，實驗結果如圖7所示。

圖7　云集群節(jié)點的個數(shù)與查找時間之間的關系

圖6通過對Chained_Hash、Cuckoo_Hash以及CSR_Hash三種算法的對比可以看出：在查找成功的情況下，對于小批量的key查找，三種算法在效率上的差別并不大；但是隨著key查找數(shù)量的增加， Chained_Hash算法由于在遍歷查找的時候緩存性較差所以是三者中時間花銷是最大的；Cuckoo_Hash算法雖然天生具有高概率的特性，且hash key分布均勻，但由于其哈希沖突處理時間較長，在相同條件下查找的成功率較低，因此在平均用時上比Chained_Hash略少；而CSR_Hash算法采用雙Hash地址查找方式，并且在表中添加用來標記查找頻率的鍵頻項，因此在查找成功時，查詢的速度最快。但是在查找不成功的時候可以看出，采用改進的CSR_Hash算法由于不成功時需要進行多次查找確認，所以在時間上開銷比Cuckoo_Hash大，但仍比Chained_Hash法查找所用時間少。

從圖7中可以很明顯觀察到，在查找量一定的前提下，隨著云集群節(jié)點的增加，查找所需時間明顯減少；當節(jié)點數(shù)到達6個以后，此時再增加節(jié)點的個數(shù)，查找的時間開始趨于穩(wěn)定。這是由于云集群自身節(jié)點通信需要時間，而且算法本身也需要時間進行處理。

4結語

key-value型數(shù)據(jù)庫是應用于云環(huán)境下的典型云存儲系統(tǒng)。在基于前綴匹配的搜索查詢操作中，系統(tǒng)需要根據(jù)用戶提供的關鍵字，快速找到并推薦用戶需要的信息，采用哈希表結構可以直接定位數(shù)據(jù)所在的節(jié)點，且維護方便?；趉ey-value引擎的Redis內存數(shù)據(jù)庫，提出了一種改進的快速查找算法CSR_Hash，并將其應用在基于云平臺的圖書銷售系統(tǒng)中進行查找提示服務，充分發(fā)揮了Redis數(shù)據(jù)庫高效的索引與查詢優(yōu)勢。使得海量數(shù)據(jù)下的云圖書銷售系統(tǒng)擁有更好的發(fā)展前景。基于key-value數(shù)據(jù)模型的存儲系統(tǒng)只支持簡單的數(shù)據(jù)查詢操作，所以如何結合Map/Reduce模型來實現(xiàn)資源的負載均衡，是接下來研究的重點。除此之外，云環(huán)境下數(shù)據(jù)管理的安全性始終是研究熱點，需要我們不斷的學習與探索。

參考文獻

[1] 申德榮,于戈,王習特,等.支持大數(shù)據(jù)管理的NoSQL系統(tǒng)研究綜述[J].軟件學報,2013,24(8):1786-1803.

[2] 覃雄派,王會舉,杜小勇,等.大數(shù)據(jù)分析——RDBMS與MapReduce的競爭與共生[J].軟件學報,2012,23(1):32-45.

[3] 陳全,鄧倩妮.云計算及其關鍵技術[J].計算機應用,2009,29(9):2562-2567.

[4] Robert Escriva,Bernard Wong,Emin Gün Sirer.HyperDex:A distributed,searchable key-value store[J].Acm Sigcomm Computer Communication Review,2012,42(4):25-36.

[5] Christian Tinnefeld,Alexander Zeier,Hasso Plattner.Cache-conscious data placement in an in-memory key-value store[C]//Proceedings of the 15th Symposium on International Database Engineering & Applications,Lisboa,2011:134-142.

[6] 王珊,肖艷芹,劉大為,等.內存數(shù)據(jù)庫關鍵技術研究[J].計算機應用,2007,27(10):2353-2357.

[7] 袁培森,皮德常.用于內存數(shù)據(jù)庫的Hash索引的設計與實現(xiàn)[J].計算機工程,2007,33(18):69-71.

[8] 馬如林,蔣華,張慶霞.一種哈希表快速查找的改進方法[J].計算機工程與科學,2008,30(9):66-68.

[9] 唐誠.Redis數(shù)據(jù)庫在微博系統(tǒng)中的實踐[J].廈門城市職業(yè)學院學報,2012,14(3):55-59.

[10] Rasmus Pagh.Flemming Friche Rodler Cuckoo Hashing[J].Journal of Algorithms,2004,51(2):122-144.

[11] Lai Y,Zhongzhi S.An efficient data mining framework on Hadoop using java persistence API[C]//IEEE 10th International Conference on Computer and Information Technology,2010:203-209.

[12] Zhao Fuyao,Liu Qingwei.A string matching algorithm based on efficient hash function[C]//International Conference on Information Engineering and Computer Science,2009:1-4.

[13] Ye Junmin,Li Songsong,Hao Guangquan,et al.Prefix and suffix query of chinese word segmentation algorithm for maximum matching[C]//International Conference on Image Analysis and Signal Processing,2011:74-77.

[14] Chouvalit Khancome,Veera Boonjing,Pisit Chanvarasuth.A two-hashing table multiple string pattern matching algorithm[C]//Tenth International Conference on Information Technology: New Generations,2013:696-701.

[15] Dean J,Ghemawat S.MapReduce:a flexible Data processing tool[J].Communications of The ACM,2010,53(1):72-77.

[16] 王錕,方明.Aajx技術研究與應用[J].現(xiàn)代電子技術,2008,31(6):93-98.

A FAST SEARCH ALGORITHM BASED ON REDIS MEMORY DATABASE

Lang HongyuRen Yonggong

(SchoolofComputerandInformationTechnology,LiaoningNormalUniversity,Dalian116081,Liaoning,China)

AbstractThe arrival of the era of “big data” makes the novel applications in cloud environment in full swing. Aiming at the new requirements of big data management, the key-value data storage system is becoming the focus of current researches. This paper proposes a fast hybrid hash search algorithm (CSR-Hash), it is based on Redis, an in-memory database of key-value engine, and the technology of Cuckoo Hash. Through analysing experimental results, it shows that the algorithm effectively shortens the query responding time. We applied the algorithm in a book sales system implemented through cloud platforms of Hadoop and Map/Reduce programming model to carry out efficient parsing and recommendation on book data, this enhanced the real-time and high-concurrency performances of the combination of NoSQL database and Map/Reduce.

KeywordsKey-value storage systemRedis databaseMap/ReduceCuckoo hash

收稿日期：2014-10-28。遼寧省計劃項目(2012232001)；遼寧省自然科學基金項目(201202119)。郎泓鈺，碩士生，主研領域：數(shù)據(jù)挖掘。任永功，教授。

中圖分類號TP399

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.05.011