[發明專利]一種基于主動哈希和布隆過濾器的高效緩存方法

有效

• 申請號: 201310237798.7
• 申請日: 2013-06-17
• 公開（公告）號: CN103294822A
• 公開（公告）日: 2013-09-11
• 發明（設計）人: 劉建偉;馬妍
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京慧泉知識產權代理有限公司 11232
• 代理人: 王順榮;唐愛華

（一）技術領域：

本發明基于主動哈希和布隆過濾器的高效緩存方法，可用于高速緩存中數據的高效查找，屬于計算機技術應用領域。

（二）技術背景：

現如今的很多系統，如：電子病歷（Electronic?Healthcare?Record，簡稱EHR）、域名系統（Domain?Name?System，簡稱DNS）等具有數據量大、具備高度隱私性、數據類型多樣等特點，造成其安全存儲、查找操作的復雜性和艱巨性。對這樣數據的處理除了完成基本功能之外，還必須考慮CPU和內存等物理因素，同時要防范常見的網絡攻擊，如拒絕服務攻擊（Deny?of?Service，簡稱DoS）。

高速緩存是為了提高數據查找效率而設置的，針對查詢流量大等特點，存儲時需要采用哈希鏈式存儲，并且由于數據查找操作頻繁，因此對查找算法的要求很高。采用哈希均勻的算法是查找效率提高的前提，所以，必須對哈希算法進行優化。對于查找命中的情況，如果能夠盡量減少平均查找長度，對于大量查找操作，其好處是明顯的。另外，由于實際中攻擊者往往大量發送不存在的查詢請求，以實施DoS攻擊，因此針對查找失敗的情況，也要進行算法的優化，避免CPU資源被大量耗盡。

哈希表是一個非常有用的、非常基礎的數據結構，在數據的查找方面尤其重要，應用的非常廣泛。然而，任何事物都有兩面性，哈希也存在缺點，即數據的局部集中性會使散列的性能急劇下降，且越集中，性能越低。數據集中，即搜索鍵在通過哈希函數運算后，得到同一個結果，指向同一個桶，這時便產生了數據沖突。通常解決數據沖突的方法有：拉鏈法和開地址法。拉鏈法我們用的非常多，即存在沖突時，簡單的將元素鏈在當前桶的最后元素的尾部。

分離鏈接法的做法是將哈希到同一個值的所有元素保留到一個表中，為方便起見，這些表都有表頭，因此，表的實現與普通的鏈表相同。如果空間很緊，可以避免表頭。

在傳統的哈希表查找算法中，對于訪問頻繁的關鍵字，如果在生成哈希表的時候將該節點置于某一鏈表的后部，則每次都要進行相當多次的鏈表遍歷才能查找到該項，勢必會增加平均查找長度，降低效率。

事實上很多事物和現象都存在一個延續性原理，即在最近一段時間內不曾訪問過的也在不久的將來訪問的可能性也較小。該思想在操作系統的頁面淘汰算法中大量使用。一種主動的哈希查找算法也是基于此思想得出的。對于電子病歷庫來說，如果一個病人的病歷在一段時間內沒有被訪問到，則意味著該病歷在不久的將來訪問的可能性也比較小。為減少平均查找長度，可將該項向后移動。對不頻繁訪問節點的向后移動可以轉化成對最近訪問鏈表節點的向前移動。在主動的哈希查找算法中，當訪問某個節點時，則將該節點前移至鏈表的表頭。以此來減少整個訪問過程中的平均查找長度。

對于傳統的主動哈希查找算法，雖然已經減小了平均查找長度，但是也存在一定的弊端。可以考慮下面情況。

假設某關鍵詞的訪問頻率很低，在某一時刻，有一個該詞的訪問，按照主動哈希查找算法，在訪問完該詞后，需將該詞提至鏈表頭部，之后，該詞一直沒有訪問過，則在有限的一段時間里（該段時間指從該詞被訪問到該鏈表其余節點均被訪問）有些節點被排在該詞之后。這種情況下，必然會增加整個鏈表的平均查找長度。另外，這種方法對于鏈表的排序修改過于頻繁，也增加了系統的負擔。

基于以上原因，已有人提出一種改進的主動哈希查找算法。該算法并非對于每個訪問到的節點都前移至表頭，而是先作判斷，如果該節點屬于經常訪問的則將其移至表頭，如果是偶爾訪問到的，則不做位置移動。

至此，問題轉化成為如何判定哪些節點屬于“經常訪問”的。對這個性質的評判標準成為該算法的重點。可以稱對節點訪問的經常性為“訪問度”。在這里，可以用對該節點訪問的時間間隔作為判斷依據。“時戳”記錄了最近一次訪問該項的時間，用1970年1月1號零點距該時間的秒數表示。

在這里，將某個節點的訪問度描述成當前訪問時間和上一次訪問時間的時間差（用秒來計算）的倒數，時間間隔越長，則訪問度越小。

在哈希表節點中還設置了一個“平均值”為對應鏈表各節點“訪問度”的平均。當訪問到一個節點時，如果新計算的“訪問度”不小于“平均值”，則將該節點移動至表頭；否則，節點位置不動。比較之后，要更新節點的“平均值”為新的平均值。

本發明就是針對EHR、DNS這類特殊數據庫系統的高速緩存，提供一種基于主動哈希和布隆過濾器的高效緩存方法。

（三）發明內容：

1、目的：

本發明提供一種基于主動哈希和布隆過濾器的高效緩存方法，以實現查找效率的大幅提高。