基於熱點緩存的搜索方法

2023-05-30 04:59:26 2

專利名稱：：基於熱點緩存的搜索方法
技術領域：
：本發明涉及網際網路搜索技術，更具體地說，涉及一種基於熱點緩存的搜索方法。
背景技術：
：由於網際網路的迅速發展，網絡上的信息資源越來越多。與此同時，網絡資源搜索的需求亦持續增加，促進了網絡搜索技術的發展。因此研究快速而準確的搜索技術已是現在網絡信息檢索的首要任務。不同的網絡所使用的搜索技術不盡相同。目前搜索弓I擎主要是以資源伺服器為中心的搜索方式，對於伺服器要求過高，伺服器負荷過重。另外伺服器容量亦無法滿足網絡信息數量以幾何形式增長的速度。而P2P對等網絡概念的出現則可以很好地解決現有搜索技術的瓶頸。P2P網絡廣義上分為兩種結構化P2P網絡和非結構化P2P網絡。簡單來說，非結構化P2P網絡指網絡中節點所維護的路由表無嚴格的組織方式，而結構化P2P網絡指網絡節點所維護的路由表有嚴格的邏輯組織方式。在P2P網絡中無真正意義上的中心伺服器，不需要集中存儲資源，任何一個網絡中的節點都可作為伺服器存在。因此，P2P搜索技術作為一種新興的網絡搜索技術，其發展是未來網絡搜索發展的主要方向。現有的幾種P2P搜索方法亦分為結構化和非結構化兩種。其中非結構化P2P網絡搜索方法主要有洪泛、隨機漫步等，結構化P2P網絡搜索方法主要是基於DHT技術的搜索方法，如Kademlia、Chord、CAN(Content曙AddressableNetwork)、Pastry等。上述幾種P2P搜索方法，基本上針對平衡網絡的應用場景。然而在現實生活中，經常存在熱點的現象，即某時間段內某個特定資源的搜索請求大量增加。現有技術的搜索方法存在查詢過程複雜、查詢速度低、而且會浪費網絡帶寬資源的問題。
發明內容針對現有技術的上述缺陷，本發明要在各種搜索協議的基礎上進行改進，以使搜索速度更快、帶寬消耗更少。本發明的技術方案是，提供一種基於熱點緩存的搜索方法，其中任一節點作為發起節點針對某一關鍵字發出査詢請求時，如果是通過轉發查詢請求而找到保存有關鍵字列表的索引節點，則從所述索引節點接收關鍵字列表和索引節點地址，再根據所述關鍵字列表進行相應操作、同時保存所述索引節點地址；當這個保存了索引節點地址的節點接收到其他節點轉來的針對所述關鍵字的查詢請求時，則向當前發起節點返回該索引節點地址，從而使當前發起節點可根據其收到的索引節點地址快速地找到索引節點。本發明的方法中，任一節點作為發起節點針對某一關鍵字發出査詢請求時，可先判斷自己是否存有關鍵字列表或索引節點地址如果自己保存有所述關鍵字列表，則直接根據所述關鍵字列表進行相應操作；如果自己保存有所述索引節點地址，則直接根據所述索引節點地址找到所述索引節點，然後從所述索引節點接收所述關鍵字列表，並根據所述關鍵字列表進行相應操作；如果自己既未保存關鍵字列表、也未保存索引節點地址，才按預定規則向相鄰節點間轉發查詢請求。本發明的方法中，在轉發査詢請求的過程中，任一節點收到其他節點轉來的針對所述關鍵字的查詢請求時，先判斷自己是否存有關鍵字列表或索引節點地址如果保存有所述關鍵字列表，則該節點將其保存的關鍵字列表和自身地址返回給該發起節點；如果保存有所述索引節點地址，則該節點將其保存的索引節點地址返回給該發起節點；如果該節點中既未保存所述關鍵字列表、也未保存所述索引節點地址，則再向自己的相鄰節點轉發所述查詢請求，直至找到一個存有關鍵字列表或索引節點地址的節點。本發明的方法中，所述發起節點將所述索引節點地址保存在自己的熱點緩5存區(Cache)中。該熱點緩存區中除保存索引節點地址，還可保存熱點關鍵字的優先級信息。由於採取了上述技術方案，本發明的優點包括(l)可提高査詢速度，加快查詢響應；(2)可保證信息的實時有效性；G)可降低對網絡帶寬的佔用率。圖1是本發明熱點緩存的原理圖2是本發明一個實施例中的處理流程圖3是普通Chord協議的查詢示例圖4是使用了本發明方法的Chord協議的査詢示例圖5是使用了本發明方法的Chord協議的査詢流程圖6是Kademlia協議的査詢流程圖7是Kademlia協議的査詢示例圖。具體實施例方式由前面的描述可知，針對現有技術的上述缺陷，本發明提出了一種基於熱點緩存的搜索方法。為了便於說明，我們把發起關鍵字查找的節點叫做發起節點，把存儲熱點資源的節點叫做資源節點，把存儲資源節點地址的集合(即key列表)的節點叫做索引節點。本發明的方法是在每個P2P節點的原路由表外添加一個熱點緩存區，用於存儲索引節點的地址。P2P搜索的首要目的是找到索引節點地址，應用本發明的方法，發起節點可以快速從某一節點的熱點緩存區直接獲得索引節點地址，而不需要經過多路徑的搜索和轉發。本發明的方法可與各種P2P網絡搜索協議相結合，應用範圍廣泛，加快原搜索協議的速度，從而減少帶寬消耗；另外，本發明的方法主要是在每個節點的路由表上增加一塊熱點緩存區和相應的緩存信息更新策略，所以實現簡單。下面將結合附圖和實施例對本發明作進一步說明。圖1示出了本發明的原理，其中，假設網絡中有節點N1，N2，N3，...，Nx，...，Nk，...，Nm…。每個節點都有一個熱點緩存區，即Cache(Nx)。下表對本文中需使用的一些代號進行了說明、定義。tableseeoriginaldocumentpage7從圖l中可以看出，發起節點Nx首次對關鍵字Key進行査詢(lOl)，即査找網絡中包含該關鍵字的所有文件d。經過Ny和Nz的轉發(102，103)，在索引節點Nk處查找到key列表，所以Nk是索引節點；Key列表包含資源節點的地址，即文件d所存放節點的IP位址和埠號列表，Key列表的表達方式是〈Key:IP(d)，PORT(d)〉。索引節點Nk將key列表〈Key:IP(d)，PORT(d)〉和自身的IP位址和埠，記錄著索引節點的地址；Count[i]是熱點關鍵字的優先級，熱點關鍵字被越頻繁發起查詢，其在熱點緩存中的優先級越高。熱點緩存Cache(Nx)的更新方法是當緩存容量滿了後，根據Coimt[i]所顯示的優先級，通過一定的算法，對優先級比較低的熱點進行更新。採取上述方案後，對關鍵定的查詢次數越多，則會有更多節點中保存所述索引節點地址，當其他節點發起新的査詢請求時，可快速從相鄰節點中獲取索引節點地址，再根據索引節點地址與索引節點連接，最終有有益效果包括(1)將索引節點地址存儲在Nx的Cache中，可以加快對Key的査詢速度，因為這個查詢請求到達Nx後，Nx直接將索引節點地址返回給發起節點，而不必再通過後續中間節點Ny及Nz的轉發，才得到索引節點地址，減少了査詢轉發的次數。當這個Key是個熱點關鍵字時，如果很多發起節點對Key進行查詢並保存索引節點的話，網絡中就會大量存在Key的索引節點地址，這樣就會減少查找Key索引節點地址所發生的轉發流量，從而提高查詢速度。(2)將索引節點地址存儲在Nx的Cache中，可以保證信息的實時有效性。因為在動態網絡中Key所對應的資源節點在不停更新，根據結構化系統的要求，這些更新信息將會發布在索引節點Nk上，所以節點Nk上有關Key的列表始終都是最新的，即列表〈Key:IP(d)，PORT(d)〉始終是最新的。保存索引節點地址就是為了使發起節點獲得的key列表是最新的。若Nx直接保存key列表，則發起節點得到的信息可能是過時的，比如〈Key:IP(d)，PORT(d)>所指向的節點可能退出網絡了，也可能資源節點將文件d刪除或不再共享。這樣的話，發起節點得到的信息就無效或者過時，這樣反而增加了查詢的複雜性並降低了査詢的成功率。(3)從整體上看，通過減少轉發次數而減少信息在網絡上傳輸次數和存在的時間，可降低對網絡帶寬的消耗。如圖2所示為一個基於熱點緩存的具體査詢流程，其中，任一節點作為發起節點針對某一關鍵字發出査詢請求(201)時，判斷自己是否存有關鍵字列表(202)、並判斷自己是否存有索引節點地址(203):如果自己保存有所述關鍵字列表，則直接根據所述關鍵字列表進行相應操作(213);如果自己保存有所述索引節點地址，則直接根據所述索引節點地址找到所述索引節點(211)，然後從所述索引節點接收所述關鍵字列表(212)，並根據所述關鍵字列表進行相應操作(213);如果自己既未保存關鍵字列表、也未保存索引節點地址，才按預定規則向相鄰節點間轉發査詢請求。在轉發查詢請求(204)的過程中，任一節點收到其他節點轉來的針對所述關鍵字的査詢請求時，判斷自己是否存有關鍵字列表(205)、並判斷自己是否存有索引節點地址(206):如果保存有所述關鍵字列表，則該節點即為該key值的索引節點。索引節點將其保存的關鍵字列表和自身地址返回給該發起節點(208，209)，並更新自己的Cache。發起節點收到返回信息後再根據所述關鍵字列表進行相應操作、同時保存所述索引節點地址(210);如果保存有所述索引節點地址，則該節點將其保存的索引節點地址返回給該發起節點，並更新自己的Cache。發起節點根據返回的索引節點地址連接索引節點(207)，然後從索引節點接收關鍵字列表和索引節點地址(209)，再根據所述關鍵字列表進行相應操作、同時保存所述索引節點地址(210);本步驟處理方法可根據具體協議做相應改變。如果該節點中既未保存所述關鍵字列表、也未保存所述索引節點地址，，則再向自己的相鄰節點轉發所述查詢請求(204)，如此反覆，直至找到一個存有關鍵字列表或索引節點地址的節點。9下面進一步以Chord搜索協議為例，說明本發明與現有搜索協議結合使用的實施方法。Chord協議構建的網絡為一環形網絡Chord環，網絡中的所有節點均在環上。查詢是單方向的，用平面圖表示即Chord網絡節點的查詢軌跡是順時針的。每個節點維護一個路由表，稱為FingerTable。路由表的存儲信息如下從節點i出發，離本節點距離(1>=2八〗(]=0，1，2，...)的節點的信息。Chord的査詢機制很簡單，發起節點在本身路由表中選擇最接近目標節點的節點作為下一跳，發送査詢信息。接收到查詢信息的節點亦搜索自己的路由表，若存有目標節點的信息，則將該信息返回給發起節點，搜索終止；否則，則選擇下一跳將査詢請求傳遞下去。如此重複下去，直到找到存有目標節點的索引節點為止。圖3是普通Chord的查詢過程。Nx通過Ny，Nz(301，302)，然後在Nk那得到目標節點的信息(303，304)，此次査詢完成。其後的Nn亦對同樣的目標節點發起查詢，要經過包括Nx，Ny，Nz的中間節點(305,301，302)，然後在節點Nk處得到所要信息(303，306)。圖4是使用了本發明的改進Chord的查詢過程。Nx通過Ny，Nz，然後在Nk那得到目標節點的信息(401，402，403，404)，此次査詢完成。但若接下來有節點Nn對同樣索引節點進行査詢，當該査詢請求轉發到Nx(405)時，可直接從Nx處轉到Nk(406)，然後得到所要的目標節點的信息(407)，本次查詢結束。對比可知應用的熱點緩存的二次查詢，查詢跳數要比原協議明顯減少，這是應用本發明得到的效果。下面是本發明與Chord協議結合的具體實施方法見圖5第一步發起節點Nx在自己的Cache中査找索引節點地址(501)，如果存在則對索引節點發起請求Send(Nx，Nk，hop++，Key)(507)，進入第三步。如果不存在，貝UNx在自己的FingerTable中查找key列表〈Key，IP(d)，Port(d)>(502)，如果目標節點Nd存在，則對Nd發起請求Send(Nx，Nd，hop++，Key)，查詢結束。如果Nd不存在，則Nx在FingerTable找一個最接近Nd的節點Ny進行下一步査詢(503):Send(Nx,Ny，hop++，Key),進入第二步。第二步節點Ny(Nz)在接收到查詢信息後，在自己的Cache中查找(504)，如果索引節點地址〈Key，IP，Port〉存在，則向Nk發送請求Send(Nx，Nk，hop++，Key)(507)，並更新Cache中〈Key，IP，Port〉對應的Count[i](506)，進入第三步；若〈Key，IP，Por^不存在於Cache中，Nx就在自己的FingerTable中查找Nd，如果Nd存在於Ny(Nz)的FingerTable中，則該節點Ny(Nz)即為索引節點Nk，進入第三步；若不存在，則Ny在FingerTable找一個最接近Nd的節點Nz進行轉發(505):Send(Nx，Nz，hop++，Key)。重複第二步。第三步索引節點Nk返回資源節點地址列表，即Key列表給Nx:Send(Nk，Nx，hop++，Key),同時返回自己地址信息給Nx。Nx收到後，更新Cache(508)。如果Nx的Cache中已存有索引節點地址〈Key，IP(k),Port(k)>，則只要更新對應的Count[i];如果沒有，則在Cache中，將〈Key，IP(k)，Port(k)〉存入HopSpot[i]中，並初始化對應的Count[i]。査詢過程完成。另外再以Kademlia協議與熱點緩存結合為例，體現本發明可以和各種搜索協議結合的通用性。Kademlia協議構建的網絡為一棵巨大的二叉樹，節點的路由表存儲著一些除本身外其他子樹的節點信息。其路由表稱為k-bucket，第i個k-kucket存儲著距離本節點在區間[2i，2i+l]]內的節點的信息，這裡，距離是以節點ID的異或值決定的，其中0<=i一併返回，並在cache中更新對應信息的Count[i]，否則從自身K-bucket中挑選a個自認為距離目標節點最接近的節點信息返回給發起節點。第三步發起節點Nx接收到返回信息後，若有Nd返回的確認信息，則結束查詢，向目標節點請求連接；若收到的信息是存有索引節點信息的Nk返回的信息，如果Cache中沒有Nk的信息，則將〈Key:IP(k)，PORT(k)〉保存在自己的Cache;如果Cache已存有Nk的信息，則更新相應的優先級Count[i]。然後根據Key列表，向目標節點發送信息，等待確認連接；否則，再將返回信息與自身K-bucket中的信息比較，重新選出若干個節點發送請求查詢信息，重複第二步。圖7顯示了Kademlia協議與熱點緩存結合的査詢過程。Nx發起對索引節點Nk的查詢，通過中間節點Ny，Nz(701，702)在節點Nk處得到key列表信息(703)，將Nk存入Nx的Cache中，並向資源節點發出請求(704)，査詢結束。而接下來的Nm同樣查詢索引節點Nk，查詢到Nx時直接從Nx處得到節點Nk的地址(705)，於是直接從Nk節點獲取Key列表(706)，不需經過其他中間節點如Ny和Nz。然後向資源節點發送請求(707)，查詢結束。從圖中可明顯看出結合了本發明的Kademlia協議査詢的跳數明顯比原協議少。1權利要求1、一種基於熱點緩存的搜索方法，其特徵在於，其中任一節點作為發起節點針對某一關鍵字發出查詢請求時，如果是通過轉發查詢請求而找到保存有關鍵字列表的索引節點，則從所述索引節點接收關鍵字列表和索引節點地址，再根據所述關鍵字列表進行相應操作、同時保存所述索引節點地址；當這個保存了索引節點地址的節點接收到其他節點轉來的針對所述關鍵字的查詢請求時，則向當前發起節點返回該索引節點地址。2、根據權利要求1所述的基於熱點緩存的搜索方法，其特徵在於，任一節點作為發起節點針對某一關鍵字發出査詢請求時，先判斷自己是否存有關鍵字列表或索引節點地址-如果自己保存有所述關鍵字列表，則直接根據所述關鍵字列表進行相應操作；如果自己保存有所述索引節點地址，則直接根據所述索引節點地址找到所述索引節點，然後從所述索引節點接收所述關鍵字列表，並根據所述關鍵字列表進行相應操作；如果自己既未保存關鍵字列表、也未保存索引節點地址，才按預定規則向相鄰節點間轉發査詢請求。3、根據權利要求1所述的基於熱點緩存的搜索方法，其特徵在於，在轉發查詢請求的過程中，任一節點收到其他節點轉來的針對所述關鍵字的查詢請求時，先判斷自己是否存有關鍵字列表或索引節點地址如果保存有所述關鍵字列表，則該節點將其保存的關鍵字列表和自身地址返回給該發起節點；如果保存有所述索引節點地址，則該節點將其保存的索引節點地址返回給該發起節點；如果該節點中既未保存所述關鍵字列表、也未保存所述索引節點地址，則再向自己的相鄰節點轉發所述査詢請求。4、根據權利要求1所述的基於熱點緩存的搜索方法，其特徵在於，所述發起節點將所述索引節點地址保存在自己的熱點緩存區(Cache)中。5、根據權利要求4所述的基於熱點緩存的搜索方法，其特徵在於，所述熱點緩存區中除保存索引節點地址，還保存熱點關鍵字的優先級信息。6、根據權利要求5所述的基於熱點緩存的搜索方法，其特徵在於，所述索引節點地址和熱點關鍵字的優先級信息分別由H叩Spot[i]、Coimt[i]表達，其中參數i是系統動態設置的緩存容量；所述HopSpot[i]的元素是〈Key，IP，(k)，PORT(k)>，記錄著索引節點的地址；所述Coimt[i]是熱點關鍵字的優先級，熱點關鍵字被越頻繁發起查詢，其在熱點緩存中的優先級越高。7、根據權利要求1-6任一項所述的基於熱點緩存的搜索方法，其特徵在於，所述搜索方法是Chord協議搜索方法、或者是Kademlia協議搜索方法。全文摘要本發明涉及一種基於熱點緩存的搜索方法，為解決現有搜索方法查詢過程複雜的問題，本發明中，任一節點作為發起節點針對某一關鍵字發出查詢請求時，如果是通過轉發查詢請求而找到保存有關鍵字列表的索引節點，則從所述索引節點接收關鍵字列表和索引節點地址，再根據所述關鍵字列表進行相應操作、同時保存所述索引節點地址；當這個保存了索引節點地址的節點接收到其他節點轉來的針對所述關鍵字的查詢請求時，則向當前發起節點返回該索引節點地址，使得當前發起節點可根據其收到的索引節點地址快速地找到索引節點。本發明的方法可提高查詢速度、加快查詢響應，可保證信息的實時有效性，並可降低對網絡帶寬的佔用率。文檔編號G06F17/30GK101488137SQ20081006505公開日2009年7月22日申請日期2008年1月14日優先權日2008年1月14日發明者梁蕾娟,陳劍勇,龍海建申請人:深圳三石科技有限公司