基于Redis內存數據庫的快速查找算法

郎泓鈺　任永功

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

?

基于Redis內存數據庫的快速查找算法

郎泓鈺任永功

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

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

關鍵詞key-value型存儲系統Redis數據庫Map/ReduceCuckoo hash

0引言

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

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

1基于Redis的快速查找算法

1.1Redis簡介

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

1.2基于Redis的前綴匹配

Redis數據庫同樣提供了很好的索引機制，以實現高性能的實時搜索?；赗edis研究者已經實現了不同的搜索功能。這里我們主要討論用于前綴匹配的索引。

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

1.3改進的排序查找算法CSR_Hash

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

1.3.1Hash沖突

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

1.3.2Cuckoo Hash

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

圖1　Cuckoo Hash表

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

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

1.3.3改進的CSR_Hash算法

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

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

(1) 獲得鍵key；

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

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

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

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

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

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

圖2　改進的CSR_Hash算法原理

2CSR_Hash算法在云圖書銷售系統中的設計與實現

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

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

2.1基于Bootstrap與Ajax的前端搜索的請求實現

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

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

Web前端請求query下發并從服務器端接收結果的實現過程為：

＄(″#query″).autocomplete

Source:function(request,response)

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

＄ajax

//實際發送的是Ajax請求

url : ″ajax/sug.do″

//發送請求的目的地址

dataType : ″json″

//數據類型為json

data :

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

//發送查詢請求

Success:function(data)

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

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

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

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

將Map/Reduce編程模型與Redis數據庫相結合，可以提高系統的實時性和高并發性。具體的實現過程為：

//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系統實現過程

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

表1　節點配置表

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

圖4　圖書銷售系統的節點信息

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

圖5　系統實現效果圖

3實驗結果分析

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

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

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

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

圖7　云集群節點的個數與查找時間之間的關系

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

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

4結語

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

參考文獻

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

[2] 覃雄派,王會舉,杜小勇,等.大數據分析——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] 王珊,肖艷芹,劉大為,等.內存數據庫關鍵技術研究[J].計算機應用,2007,27(10):2353-2357.

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

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

[9] 唐誠.Redis數據庫在微博系統中的實踐[J].廈門城市職業學院學報,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].現代電子技術,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)。郎泓鈺，碩士生，主研領域：數據挖掘。任永功，教授。

中圖分類號TP399

文獻標識碼A

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