[發明專利]一種分布式存儲查詢系統及其運行方法和運行裝置

有效

• 申請號: 201310084186.9
• 申請日: 2013-03-15
• 公開（公告）號: CN103207897A
• 公開（公告）日: 2013-07-17
• 發明（設計）人: 范亞平
• 申請（專利權）人: 北京京東世紀貿易有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 中原信達知識產權代理有限責任公司 11219
• 代理人: 劉光明;陸錦華

技術領域

本發明涉及一種分布式存儲查詢系統及其運行方法和運行裝置。

背景技術

在當今各類網絡中，查詢系統隨處可見，如Internet中的DNS系統，銀行、大型企業等的數據庫系統等。這些查詢系統多數都是數據中心的集中式系統。但是隨著數據量的增大，在一個數據中心存放所有數據變得越發的困難，而且在一個數據中心存方所有數據并不利于數據的抗毀，一旦數據失效將出現難以估量的損失，于是出現了分布式存儲系統。

現在的分布式存儲系統大都是基于分布式哈希表DHT的，這些查詢系統都受到固定拓撲約束的限制（如Chord的環型），因此查詢系統的性能造成一定的影響。于是基于分布式匹配DMM（Distributed?match?making）的存儲查詢系統應運而生。

DMM技術的核心思想為：在每個節點i上保存兩個節點集合P(i)和Q(i)。P(i)集合是所有備份了節點i中的數據的節點的集合，即P(i)中的各個節點都備份了節點i中的數據，例如P(6)={1,2,3}表示節點1、2、3上都備份了節點6的數據。Q(i)表示從i節點發起查詢時的被查詢節點的集合，即從i節點發起的查詢到Q(i)中的節點上進行查詢。例如Q(5)={2,3,4}表示如果節點5發起一個內容查詢請求時，它會同時向節點2、3、4發起查詢請求以期獲得自己想要的數據。很顯然，如果對于任意的i和j，都有P(i)和Q(j)的并集大小為1，則所有的查詢請求都能得到滿足。

DMM技術中還有一個概念是R集合，該集合表示節點i中保存的數據的集合，通常以R(i)表示。與P集合以及Q集合是節點集合不同的是，R集合是數據集合。當節點i收到一個查詢請求時，從R(i)中查找是否有被請求的數據，如果存在則從自己的數據庫中選取相應的數據回復給源節點，否則繼續向Q(i)中的節點進行查詢請求分發。對于每個節點i，由于受限于節點存儲容量的限制，節點i的R集合R(i)應該滿足|R(i)|≤r(i)，其中r(i)為節點i的存儲容量限制。

一方面DMM方案雖然利用了數據備份，但是只是將數據備份利用來縮短查詢時延，并沒有真正實現抗毀保護。另一方面該方案雖然能在一跳虛擬路徑上就完成查詢，在查詢時延上優于Chord等經典結構，但存在的一個明顯問題是需要的存儲量太大。若是要減少存儲量則會造成向很多節點同時提出查詢請求，使得每個節點的查詢負載很重，同時也容易引起網絡中的擁塞。

發明內容

有鑒于此，本發明提供一種基于DMM的分布式存儲查詢系統及其運行方法和運行裝置，能夠兼顧數據的抗毀和查詢時延。

為實現上述目的，根據本發明的一個方面，提供了一種分布式存儲查詢系統。

本發明的分布式存儲查詢系統基于分布式匹配（DMM）方式，該系統滿足如下條件：|P(i)∩B(j)|≥k；其中，i和j表示所述系統中的任意節點，k表示預設的位于區間[1,N-1]內的整數，N表示所述系統的節點總數；P(i)表示所有備份了節點i中的數據的節點的集合；B(i)滿足如下關系：且如果j∈B(i)，則其中Q(i)表示從i節點發起查詢時的被查詢節點的集合。

根據本發明的另一方面，提供了一種分布式存儲查詢系統的運行方法。

本發明的分布式存儲查詢系統的運行方法包括：在節點接收到請求源發送的數據查詢請求后，判斷該節點中是否保存有被請求的數據；若是，則將被請求的數據發送給所述請求源；若否，則向該節點的所述Q集合中的節點發送數據查詢請求。

可選地，在所述節點中保存有被請求的數據的情況下，所述方法還包括：刪除所述請求源發送的數據查詢請求。

可選地，在所述節點中未保存被請求的數據的情況下，所述方法還包括：將所述數據查詢請求當前的生存時間減1，并且在所述數據查詢請求當前的生存時間達到0時刪除所述數據查詢請求；所述生存時間是在所述數據查詢請求被第一次發出時設置的一個正整數。

可選地，所述生存時間被設置為所述分布式存儲查詢系統的節點數。

根據本發明的又一方面，提供了一種分布式存儲查詢系統的運行裝置。

本發明的分布式存儲查詢系統的運行裝置包括：接收模塊，用于接收請求源向節點發送的數據查詢請求；判斷模塊，用于在所述接收模塊接收到所述數據查詢請求后，判斷該節點中是否保存有被請求的數據；發送模塊，用于在所述判斷模塊的判斷結果為是的情況下將被請求的數據發送給所述請求源，在該判斷結果為否的情況下向該節點的所述Q集合中的節點發送數據查詢請求。