郎泓鈺　任永功

(遼寧師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院　遼寧 大連 116081)

?

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

郎泓鈺任永功

(遼寧師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院遼寧 大連 116081)

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

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

0引言

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

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

1基于Redis的快速查找算法

1.1Redis簡(jiǎn)介

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

1.2基于Redis的前綴匹配

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

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

1.3改進(jìn)的排序查找算法CSR_Hash

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

1.3.1Hash沖突

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

1.3.2Cuckoo Hash

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

圖1　Cuckoo Hash表

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

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

1.3.3改進(jìn)的CSR_Hash算法

本文提出了一種基于Cuckoo Hash及鏈地址法處理沖突的混合哈希表查找方法，并在哈希表結(jié)構(gòu)中添加用來(lái)提供查找對(duì)比的鍵頻項(xiàng)count。count用來(lái)存儲(chǔ)一段時(shí)間內(nèi)該元素被查找的頻率，由該元素被查詢次數(shù)除以哈希表中所有元素被查找的總次數(shù)計(jì)算得到。

改進(jìn)的Cuckoo Hash表的建立過(guò)程如下：

(1) 獲得鍵key；

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

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

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

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

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

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

圖2　改進(jìn)的CSR_Hash算法原理

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

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

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

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

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

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

Web前端請(qǐng)求query下發(fā)并從服務(wù)器端接收結(jié)果的實(shí)現(xiàn)過(guò)程為：

＄(″#query″).autocomplete

Source:function(request,response)

//source為輸入內(nèi)容，有改變則發(fā)送請(qǐng)求

＄ajax

//實(shí)際發(fā)送的是Ajax請(qǐng)求

url : ″ajax/sug.do″

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

dataType : ″json″

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

data :

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

//發(fā)送查詢請(qǐng)求

Success:function(data)

//返回時(shí)將data填充對(duì)話框

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

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

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

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

//Map過(guò)程解析出關(guān)鍵字

Function Map(QuestAll,QuestKeyword)

LineMessage←QuestAll.toString();

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

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

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

//Reduce過(guò)程查找排序

Function Reduce(QuestKeyword,Result.value)

Result.value←CSR_Hash(″QuestKeyword″);

2.3系統(tǒng)實(shí)現(xiàn)過(guò)程

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

表1　節(jié)點(diǎn)配置表

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

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

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

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

3實(shí)驗(yàn)結(jié)果分析

為了測(cè)試改進(jìn)后算法的性能，在圖書銷售系統(tǒng)中進(jìn)行兩個(gè)實(shí)驗(yàn)。

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

圖6　完成相同查找任務(wù)的前提下三種算法在時(shí)間花銷上的對(duì)比

實(shí)驗(yàn)二完成相同查找任務(wù)的前提下，分別在計(jì)算節(jié)點(diǎn)為1～6時(shí)對(duì)改進(jìn)后的查找算法進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果如圖7所示。

圖7　云集群節(jié)點(diǎn)的個(gè)數(shù)與查找時(shí)間之間的關(guān)系

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

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

4結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

[3] 陳全,鄧倩妮.云計(jì)算及其關(guān)鍵技術(shù)[J].計(jì)算機(jī)應(yīng)用,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] 王珊,肖艷芹,劉大為,等.內(nèi)存數(shù)據(jù)庫(kù)關(guān)鍵技術(shù)研究[J].計(jì)算機(jī)應(yīng)用,2007,27(10):2353-2357.

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

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

[9] 唐誠(chéng).Redis數(shù)據(jù)庫(kù)在微博系統(tǒng)中的實(shí)踐[J].廈門城市職業(yè)學(xué)院學(xué)報(bào),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技術(shù)研究與應(yīng)用[J].現(xiàn)代電子技術(shù),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。遼寧省計(jì)劃項(xiàng)目(2012232001)；遼寧省自然科學(xué)基金項(xiàng)目(201202119)。郎泓鈺，碩士生，主研領(lǐng)域：數(shù)據(jù)挖掘。任永功，教授。

中圖分類號(hào)TP399

文獻(xiàn)標(biāo)識(shí)碼A

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