非關係型資料庫Cassandra中分區路由方法
2023-06-08 13:38:41 1
專利名稱：非關係型資料庫Cassandra中分區路由方法
技術領域：
本發明涉及一種路由方法，尤其涉及一種非關係型資料庫Cassandra中分區路由方法。
背景技術：
Cassandra是一個混合型的非關係的資料庫，類似於Google的BigTable。其主要功能比Dynomite (分布式的Key-Value存儲系統)更豐富，但支持度卻不如文檔存儲 MongoDB (介於關係資料庫和非關係資料庫之間的開源產品，是非關係資料庫當中功能最豐富，最像關係資料庫的。支持的數據結構非常鬆散，是類似json的bjson格式，因此可以存儲比較複雜的數據類型。)Cassandra最初由!^cebook開發，後轉變成了開源項目。它是一個網絡社交雲計算方面理想的資料庫。以Amazon專有的完全分布式的Dynamo為基礎，結合了 Google BigTable基於列族(Column Family)的數據模型。Cassandra的主要特點就是它不是一個資料庫，而是由一堆資料庫節點共同構成的一個分布式網絡服務，對Cassandra 的一個寫操作，會被複製到其他節點上去，對Cassandra的讀操作，也會被路由到某個節點上面去讀取。對於一個Cassandra群集來說，擴展性能是比較簡單的事情，只管在群集裡面添加節點就可以了。和其他資料庫比較，Cassandra具有三個突出特點
模式靈活使用Cassandra，像文檔存儲，你不必提前解決記錄中的欄位。你可以在系統運行時隨意的添加或移除欄位。這是一個驚人的效率提升，特別是在大型部署上。真正的可擴展性Cassandra是純粹意義上的水平擴展。為給集群添加更多容量，可以指向另一臺電腦。你不必重啟任何進程，改變應用查詢，或手動遷移任何數據。多數據中心識別你可以調整你的節點布局來避免某一個數據中心起火，一個備用的數據中心將至少有每條記錄的完全複製。Cassandra分區路由方法的依據為Chord協議，更確切的說，Cassandra分區路由方法採用的算法是Chord協議的簡化版實現。Chord是在2001年由麻省理工學院提出，其核心思想就是要解決在P2P應用中遇到的基本問題如何在P2P網絡中找到存在特定數據的節點。在Cassandra中，一個數據中心往往是由成千上萬臺廉價伺服器組成，每臺伺服器被稱為一個節點。在每臺伺服器中，數據都是以Key-value對存放，所以讀操作就是按照請求的Key值去龐大的數據中心查找存在該key值對應的value的節點的過程。Cassandra 具體路由算法如下
系統中每個節點在一定空間內隨機被分配一個ID值，代表其在環上的位置。每個節點都存儲一張路由表，表內順時針按照離本節點2、4、8、16、32.……21的距離選定個其他節點的IP信息來記錄。其每個節點存儲的路由表格式如圖2所示。如圖1所示，一個具體的查詢過程如下
一個Key值的讀請求從客戶端到某個節點，該節點作為代理節點，對請求數據的Key值進行一致性哈希運算，得要一個鍵值，按照這個鍵值，根據集群組建時定下的複製策略來確定保存這個數據的η個節點的ID號，以查找其中一個節點為例，先從該代理節點的路由表中，找一個和該哈希得到的鍵值距離最近、並且存活在網絡中的節點next (注此距離即為 key值哈希得到的鍵值和節點ID之間的差)。如果該節點的id巧合和上述根據請求Key 值哈希得到的鍵值相等，那麼你已經找到所要的節點。如果不相等，則到next進行遞歸查找。一般或需要經過多次查詢才能找到數據所在的節點。這個次數是可以被證明小於等於 Iog2N的。這就是Cassandra所用到的基本的路由思想。現有Cassandra中分區路由方法的缺點是算法靈活性不足，比較死板，路由效率並不高，而且節點間如果存在大量路由信息，也會降低系統效率。存在此缺點的原因是，在 Cassandra路由算法中，如圖2所示，每個節點的路由表中第三列中只記錄一個節點的信息，導致路由效率不高；而且，按照其第二列距離來說，此距離是由減法得到的，這裡也有可以提升的空間。
發明內容
本發明所要解決的技術問題在於克服現有Cassandra中分區路由方法的缺點，提供一種具有更高效率的非關係型資料庫Cassandra中分區路由方法。本發明的思路是將Kad算法的思想引入現有Cassandra分區路由方法中，對現有分區路由方法進行改進，從而提高路由效率。Kad (Kademlia，通常簡稱為 Kad)是美國紐約大學的 PetarP. Maymounkov 和 David Mazieres在2002年發布的一項研究結果。Kad算法是一種分布式哈希表(DHT)技術，不過和其他DHT實現技術比較，如chord等，Kad通過獨特的以異或算法為距離度量基礎，建立了一個全新的DHT拓撲算法，相比於其他算法，可以大大提高路由查詢速度。具體而言，本發明採用以下技術方案
一種非關係型資料庫Cassandra中分區路由方法，所述非關係型資料庫Cassandra — 個數據中心中每個節點在一定空間內隨機被分配一個ID值，該ID值在本數據中心內是唯一的，這個ID在本代表其在環上的位置；每個節點都存儲一張路由表，路由表內記錄有按照離本節點的距離所選定的多個其他節點的IP信息；進行路由搜索時，根據節點間的距離由近到遠進行遞歸查找，所述節點間的距離是通過對兩節點的ID進行異或運算得到。進一步地，所述路由表中保存有與本節點距離為
2的節點信息，i = m、k,k為預先設定的整數。本發明將Kad算法的思想引入現有Cassandra分區路由方法中，以異或算法(XOR) 為節點間距離的度量基礎，並對路由表進行了修改。相比現有路由方法，本發明具有以下優點。
一.方便進行網絡劃分，節點按照二進位中每一bit的O或1建成一棵二叉樹；
二.使每個節點保持的路由信息更豐富，同樣是將整個網絡按照劃分成Iog2N份，在 Cassandra原來的方法中中，是保持Iog2N個路由節點，但在本發明中，則是保存了 Iog2N個隊列，這樣就保存了更多的節點，使得命中率更高。每個隊列長度為配置值t 是根據網絡狀態設置的常數)，記錄網絡中對應節點區域的多個節點，並且根據活躍時間對這些節點進行換入換出。
圖1為現有Cassandra分區路由方法的流程圖； 圖2為現有Cassandra分區路由方法的路由表結構； 圖3為本發明的路由表結構；
圖4為本發明路由方法與現有路由方法的效率對比結果。
具體實施例方式下面結合附圖對本發明的技術方案進行詳細說明
本發明中，所述非關係型資料庫Cassandra中每個節點在一定空間內隨機被分配一個 ID值，代表其在環上的位置；每個節點都存儲一張路由表，路由表的結構如圖3所示，我們可以將圖3所示的路由表和現有技術的路由表(圖2)進行比較。針對於每一個節點，在圖2 的路由表中，在與本節點減法對應距離的範圍內只存放一個節點，(第二列表示與本節點的對應距離，第三例表示存儲的節點)。而在本發明的路由表中，在與本節點對應的距離範圍內，存放著若干個節點。其中，節點間的距離是通過對兩節點的ID進行異或運算得到。在進行路由搜索時，按照以下步驟
步驟1、接收到查詢請求的節點將查詢請求中的key值進行哈希，得到的哈希值即為所要查找目標節點的ID;
步驟2、將目標節點ID與本節點ID進行異或運算得到兩節點的距離，查找路由表，看路由表對應的距離範圍那一行第三列上，有無目標節點，如存在，直接返回目標節點；如不存在，則轉步驟3;
步驟3、將該距離範圍內那一行的第三列所存放的所有節點ID與目標節點ID異或，找出異或值最小的那個節點，以該節點為本節點執行步驟2，依次遞歸查找，直到返回目標節
點ο具體而言，假設ID值為χ的節點要查找ID值為y的節點，則按照以下的遞歸操作步驟進行路由查找
第一步、將key值進行哈希，這個哈希函數可以具體應用時再定義。哈希得到的數值就是目標節點1。所以，過程演變成從χ節點查找y節點。第二步、對x、y異或計算出χ與y的距離dis，即diS=X XOR y，X0R表示異或。根據dis屬於的[2n，2n+1)，求出η;在節點χ的路由表中第η行中第三列中比較有無目標節點， 如果存在，則將返回目標節點此該目標節點的信息，包括IP等。如果不存在，則將此行第三列中所有節點ID與目標節點ID進行異或，找出與目標節點異或值最小的那個節點ζ。第三步、如果第二步中沒有找到目標節點y，則路由到第二步最後得到的節點ζ進行從第二步開始的遞歸查找，直到查詢出目標節點y，並返回。為了驗證本發明的有益效果，模擬了一個數據中心，其中有64個節點，每個節點各自存有Key-value對，並假設在某一隨機節點查詢某一 key值，此需要路由到目標節點去取值。分別採用本發明方法與現有方法進行路由查找，並對比兩種方法找到目標節點所需經過的路由節點數。最終得到的對比結果如附圖4 (截取了實驗的一部分數據)所示，其中，第二列表示本節點即發起查找請求的節點，第三列表示要查找的目標節點，第四列和第五列表示依據改進前後算法，路由過程經過的節點。在十次實驗中，原本算法需路由節點數44 (將該表中第四列中所用顯示到的節點相力Π)個，而本發明(即圖中的改進算法)只需路由節點數33 (將該表中第五列中所用顯示到的節點相加)個。由此，相比現有方法，本發明的路由效率提升了 25%。
權利要求
1.一種非關係型資料庫Cassandra中分區路由方法，所述非關係型資料庫Cassandra 一個數據中心中每個節點在一定空間內隨機被分配一個ID值，該ID值在本數據中心內是唯一的，這個ID代表其在環上的位置；每個節點都存儲一張路由表，路由表內記錄有按照離本節點的距離所選定的多個其他節點的IP信息；進行路由搜索時，根據節點間的距離由近到遠進行遞歸查找，其特徵在於，所述節點間的距離是通過對兩節點的ID進行異或運算得到。
2.如權利要求1所述非關係型資料庫Cassandra中分區路由方法，其特徵在於，所述路由表中保存有與本節點距離為 的節點信息，I = 0,1,2,-,A',^為預先設定的整數。
3.如權利要求2所述非關係型資料庫Cassandra中分區路由方法，其特徵在於，該方法包括以下步驟步驟1、接收到查詢請求的節點將查詢請求中的key值進行哈希，得到的哈希值即為所要查找目標節點的ID;步驟2、將目標節點ID與本節點ID進行異或運算得到兩節點的距離，查找路由表，看路由表對應的距離範圍那一行第三列上，有無目標節點，如存在，直接返回目標節點；如不存在，則轉步驟3;步驟3、將該距離範圍內那一行的第三列所存放的所有節點ID與目標節點ID異或，找出異或值最小的那個節點，以該節點為本節點執行步驟2，依次遞歸查找，直到返回目標節點ο
全文摘要
本發明公開了一種非關係型資料庫Cassandra中分區路由方法。所述非關係型資料庫Cassandra一個數據中心中每個節點在一定空間內隨機被分配一個ID值，該ID值在本數據中心內是唯一的，這個ID在本代表其在環上的位置；每個節點都存儲一張路由表，路由表內記錄有按照離本節點的距離所選定的多個其他節點的IP信息；進行路由搜索時，根據節點間的距離由近到遠進行遞歸查找，所述節點間的距離是通過對兩節點的ID進行異或運算得到。本發明通過對現有路由方法進行改進，以異或算法為距離度量基礎，有效提高了非關係型資料庫Cassandra中的數據查詢效率。
文檔編號H04L12/56GK102201986SQ20111011879
公開日2011年9月28日 申請日期2011年5月10日 優先權日2011年5月10日
發明者陳葉輝, 陳國慶 申請人:蘇州兩江科技有限公司