服務感知分布式散列表路由的製作方法

2023-05-27 02:49:16

服務感知分布式散列表路由的製作方法
【專利摘要】在一個實施例中，計算機網絡中的節點加入與分布式散列表(DHT)相關聯的全局環，並且維護針對全局環的DHT路由表和DHT資料庫。此外，節點可確定特定的服務類，其中該節點被配置用於該特定的服務類，並且節點可根據特定的服務類加入特定的基於服務的子環，其中該特定的基於服務的子環的所有節點均在全局環內。同樣地，可維護針對特定的基於服務的子環的基於服務的DHT路由表和基於服務的DHT資料庫，以使得由特定的服務類識別的DHT操作(例如，通過門戶節點)被路由至特定的基於服務的子環。
【專利說明】服務感知分布式散列表路由

【技術領域】
[0001]本公開一般涉及計算機網絡，更具體地，涉及分布式散列(hash)表(DHT)。

【背景技術】
[0002]正如本領域技術人員所理解的，分布式散列表(DHT)是基於鍵-值(key-value)對的、分散的、可擴展的以及容錯的資料庫系統。一些眾所周知的DHT協議有Chord、Pastry、Kademlia和P_Grid，這些協議一般定義了節點加入現有的DHT網絡、建立DHT路由表和使用該DHT路由表以向對象的根節點轉發TOT/GET消息的處理。根節點通常被定義為其節點標識符(ID)最接近被存儲(I3UT)或被檢索(GET)的對象的節點。基本的DHT協議對於基於DHT網絡中的單一鍵存儲和檢索對象的簡單應用非常有效。應當注意的是，對象的鍵是通過對對象中的唯一欄位進行散列運算得出的，並且對象的根節點是嚴格基於該散列的結果的。

【專利附圖】

【附圖說明】
[0003]通過參照下面的描述並結合附圖可以更好地理解本發明的實施例，其中相同的標號表示相同的或功能相似的元素，其中:
[0004]圖1示出了計算機網絡的示例；
[0005]圖2示出了網絡設備/節點的示例；
[0006]圖3A-3B示出了簡化的分布式散列表(DHT)環的示例；
[0007]圖4示出了基於服務的DHT子環的示例；
[0008]圖5示出了基於服務的子環中的加入消息的示例；
[0009]圖6示出了基於服務的DHT操作的示例；
[0010]圖7示出了簡化的基於服務的子環路由表的示例；
[0011]圖8示出了基於服務的子環保持存活(keepalive)操作的示例；
[0012]圖9特別是從節點的角度示出了計算機網絡中的服務感知DHT路由的示例簡化過程;
[0013]圖10特別是從門戶節點的角度示出了計算機網絡中的服務感知DHT路由另一示例簡化過程；以及
[0014]圖11示出了計算機網絡中響應於節點離開全局環的服務感知DHT路由的又一示例簡化過程1100。

【具體實施方式】
[0015]MM
[0016]根據本公開的一個或多個實施例，計算機網絡中的節點加入與分布式散列表(DHT)相關聯的全局環，並且維護針對全局環的DHT路由表和DHT資料庫。此外，該節點可確定其被配置用於的特定的服務類，並且可以根據特定的服務類加入特定的基於服務的子環，其中該特定的基於服務的子環的所有節點均在全局環內。同樣地，可為特定的基於服務的子環維護基於服務的DHT路由表和基於服務的DHT資料庫，以使得由特定的服務類識別的DHT操作(例如，通過門戶節點)被路由至特定的基於服務的子環。
[0017]具體實施例
[0018]計算機網絡是通過通信鏈路和區段進行互連的節點的地理上分布的集合，這些通信鏈路和區段用於在端節點(比如，個人計算機和工作站，或其他諸如傳感器之類的設備等等)間傳輸數據。從區域網(LAN)到廣域網(WAN)，許多類型的網絡都是可用的。LAN通常通過位於同一廣義物理位置(比如，建築物或園區)的專用私有通信鏈路連接節點。另一方面，WAN通常通過諸如公用載波電話線、光學光路、同步光纖網絡(SONET)、同步數字體系(SDH)鏈路之類的長距離通信鏈路連接地理上分散的節點。
[0019]圖1是示例簡化的計算機網絡100的示意框圖，其中計算機網絡100示意性地包括通過各種通信方法進行互連的節點/設備200 (例如，如所示的被標記為「 1234」、「3A68」、「58DA」等等)，一般稱作「網絡130」。例如，鏈路可以是有線鏈路或共享介質(例如，無線鏈路)，其中，某些節點200 (諸如，路由器、傳感器、計算機等等)可例如基於物理位置、當前操作狀態等與其他節點200進行通信。通過使用諸如某些已知的有線協議、無線協議等等適當的預定義網絡通信協議，可以在計算機網絡100的節點/設備間交換數據分組140。在本上下文中，協議由一組定義了節點彼此之間如何交互的規則組成。本領域技術人員將理解任何數量的節點、設備、鏈路等等均可被用於該計算機網絡中，並且此處所示的視圖是為了簡單起見。
[0020]圖2是示例節點/設備200的示意框圖，其中該示例節點/設備200可由本文所述的一個或多個實施例用作上面圖1中所示的任何節點。設備可包括通過系統總線250進行互連的一個或多個網絡接口 210 (例如，有線的、無線的等等)、至少一個處理器220和存儲器240。
[0021](一個或多個)網絡接口 210包括用於通過被耦合至網絡100的鏈路傳送數據的機械、電氣以及信令電路。這些網絡接口可被配置為使用一個或多個通信協議發送和/或接收數據。還應當注意的是節點可具有兩個不同類型的網絡連接210，例如，無線和有線/物理連接，並且此處所示的視圖僅僅是為了說明。
[0022]存儲器240包括多個可由處理器220和網絡接口 210尋址的用於存儲與本文所述的實施例相關聯的軟體程序和數據結構的存儲位置。處理器220可包括適用於執行軟體程序和操縱數據結構245的硬體元件或硬體邏輯。作業系統242通過調用支持在設備上執行的軟體處理和/或服務的操作等來在功能上組織設備，作業系統242的某些部分通常駐存在存儲器240中並且可由處理器執行。如本文所述的，這些軟體處理和/或服務可包括路由處理244和說明性的分布式散列表(DHT)處理248。
[0023]包括各種計算機可讀介質的其他處理器和存儲器類型可被用於存儲和執行與本文所述的技術有關的程序指令，這對本領域技術人員是顯而易見的。另外，儘管描述說明了各種處理，可以明確地預期各種處理可被實施為被配置成根據本文的技術(例如，根據相似處理的功能)來運作的模塊。此外，儘管處理被分別示出，但本領域技術人員將理解的是處理可以是其他處理中的例程或模塊。例如，DHT處理248可以是路由處理244的特定組成部分。另外，儘管處理244和248在集中式存儲器240中被示出，替代的實施例提供了這些處理具體地操作於網絡接口 210中。
[0024]如本領域技術人員所理解的，路由處理244包括由處理器220執行的計算機可執行指令以實現由一個或多個諸如先應式或反應式路由協議之類的路由協議提供的功能。在有能力的設備上，這些功能可被配置成管理一個或多個包含諸如被用於做出路由/轉發決策的數據的路由表或轉發表(例如，數據結構245)。
[0025]如上面所提到的，分布式散列表(DHT)是基於鍵-值對的、分散的、可擴展的並且容錯的資料庫系統。基本的DHT協議對於基於DHT網絡中的單一鍵存儲和檢索(PUT和GET)對象的簡單應用非常有效。應當注意的是，對象的鍵是通過對對象中的唯一欄位進行散列運算獲得的，並且對象的根節點是嚴格基於該散列的結果的。也就是說，為了將對象置於節點中，對象的鍵被用於確定網絡(參與DHT 「環」)中對應於那個散列的鍵的特定的節點。
[0026]圖3A示出了說明每一個節點如何具有其自身的鍵空間的示例簡化DHT環300。尤其，為確定節點的鍵空間(其中該節點是「根節點」)，對節點的標識符(ID)(例如，媒體訪問控制(MAC)地址、節點ID等等)被進行散列運算以確定DHT中特定的「位置」(例如，通常是在2128或2256個數字範圍內的數字)。如圖3A所示，例如，假設節點「X」具有的散列環值為「5」，並且節點「Y」具有的值為「20」，於是在具有0-29的位置的環中，節點X與5-19的鍵空間相關聯，並且節點Y與20-29和0-4的鍵空間相關聯(從而成為「環」結構)。為了將對象(例如，文件、數據結構等等)置於網絡中，對象被進行散列運算(例如，對象中的唯一欄位)以將其與特定的鍵(例如，「12」)相關聯，其後相關聯的PUT請求被發送至對應於該鍵空間的節點(例如，節點X)。為了檢索對象(GET)，請求者提交該相同的鍵(例如，「12」)，並且DHT環300被用於確定哪個設備對應於該鍵空間(同樣，節點X)。如圖3B所示，當在DHT環300中插入新節點「Z」時(例如，新節點「Z」的散列ID對應於值「10」)，鍵空間被相應地劃分以使得在示例中節點X處理5-9、節點Z處理10-19並且節點Y處理20-29和0-4。(本領域技術人員將理解的是組織鍵空間的方式有很多，並且此處所示出和描述的組織不意圖限制本發明的實施例的範圍。)
[0027]注意，如果DHT網絡是地理上分散的(通常是這樣)，對象可被存儲在物理上遠離大多數GET發起的位置，這是由於DHT中的每一個節點均具有相同的成為任意對象的根節點的可能性。對PUT沒有使用局部性信息。因此，GET可能劣於最優情況。為了減少GET的延遲，對象被存儲在靠近大多數GET發起的節點是很有必要的。基本DHT協議還不能在對象間做出區分，並且不具有提供不同服務水平的機制。例如，如果DHT環過載，目前沒有允許用於具有較低服務水平的對象的PUT被拒絕而用於具有較高服務水平的對象的PUT被接受的機制。
[0028]因此，本文的技術提供了無縫地解決上述問題的服務感知DHT系統。尤其，本文的技術定義了允許由最有可能通過創建相干的基於服務的「子環」而從中被檢索的節點存儲對象的DHT系統。例如，管理員(操作者)可控制一組節點以存儲對象的每個類，並且通過配置可實現服務差異化。以這種方式，建立了通過服務類型有效地存儲和定位對象的服務感知DHT技術，該服務感知DHT技術考慮到例如局部性、網絡以及硬體信息。如本文所描述的，每一個服務水平由獨立的DHT路由表管理，其中節點可參與多個服務水平，並且一個或多個節點形成DHT覆蓋以將服務水平管理為特定的基於服務的(DHT網絡的每一個節點均參與的「全局」的)子環。
[0029]特別地，根據下面詳細描述的本公開的一個或多個實施例，計算機網絡中的節點加入與DHT相關聯的全局環，並且維護針對該全局環的DHT路由表和DHT資料庫。此外，節點可確定特定的服務類，其中該節點被配置用於該服務類，並且可根據該特定的服務類加入特定的基於服務的子環，其中，該特定的基於服務的子環的所有節點均在全局環內。正因如此，可維護針對特定的基於服務的子環的基於服務的DHT路由表和基於服務的DHT資料庫，以使得由特定的服務類識別的DHT操作(例如，通過門戶節點)被路由至特定的基於服務的子環。
[0030]作為說明，本文所描述的技術可由硬體、軟體和/或固件比如根據DHT處理248、結合路由處理244執行，DHT處理248可包括由處理器220執行以實現與本文所描述的技術相關的功能的計算機可執行指令。例如，本文的技術可被視為常規DHT協議的擴展，並且正因如此,本文的技術可相應地由本領域所理解的執行那些協議的相似的組件處理。
[0031]在操作上，與(如經典DHT協議)僅僅創建一個DHT環不同，本文的技術除了創建全局環外還可以創建多個相干DHT子環，其中每個DHT子環專用於處理一個服務類(即，基於服務的子環)。所有節點通常必須加入全局環(例如，為了下面所描述的保持存活優化)，但每個節點可選擇性地加入所配置的那樣多的子環。又如下面所描述的，諸如「PUT」和「GET」之類的DHT操作可由特定的服務類標識符識別，該特定服務類標識符允許操作被路由至對應的DHT子環。
[0032]圖4示出了根據本文的說明性的實施例的基於服務的DHT子環的示例。尤其，如所示出的，全局環410可包括一個或多個節點200 (比如，上面圖1中所示的節點)，其中，該全局環是通過一般常規的方式根據DHT路由表415和DHT資料庫創建的。然而，與全局環410相關聯的是任意數量的具有全局環的一個或多個節點的基於服務的子環420 (服務「A」和服務「B」)。也就是說，每個(與全局環相關聯的)基於服務的子環的每個節點均在全局環內。例如，節點「1234」位於服務A和服務B中的每個子環以及全局環內。然而，節點「2167」僅位於服務A(和全局環)中，而節點「3A68」僅位於服務B(和全局環)中。應當注意的是，不是全局環410內的每個節點都需要位於多個基於服務的子環420中的任何一個子環內，比如，節點「2498」。此外，除了全局環的路由表415和資料庫之外，還有與每個子環相關聯的獨立的DHT路由表425和資料庫。
[0033]為了配置基於服務的子環，操作者或管理員創建服務類並且將對象映射至將被存儲在DHT子環中的服務類。一般來說，管理員可以基於檢索位置的可能性、節點的CPU、節點的盤容量(capacity)等等分配和識別最「佳」的DHT節點以為每個服務類對象指向PUT和GET。換句話說，操作者可確定DHT節點被配置用於的一個或多個服務類，這可以基於從節點類型、節點性能(capability)、節點位置、節點功能、節點應用(在節點上運行的專門應用或各種類型的應用)等等所選擇的服務類。
[0034]此外，管理員(或自動化處理)還識別針對每個服務類或子環的引導程序(bootstrap)節點(「BN」)。具體地，所有節點必須經由全局引導程序節點加入全局環並且經由相應的服務引導程序節點加入任意服務覆蓋。圖5示出了根據本文的一個或多個實施例的基於服務的子環的加入消息/過程的示例。具體地，除了加入DHT的全局環410 (並因此維護針對全局環的DHT路由表415和DHT資料庫)之外，計算機網絡100的某些節點還可根據它們的(一個或多個)特定的服務類加入一個或多個基於服務的子環420。為了這樣做，加入的節點向引導程序節點(全局BN或服務BN)發送加入消息540，引導程序節點將該加入消息路由至該加入的節點的鍵的根節點。
[0035]例如，對於新節點加入的每一個服務類(例如，節點「2167」加入服務A)，新節點將加入消息540發送至該特定的服務類的引導程序節點(BN)。其後，對應的服務類的引導程序節點將加入消息路由至對應的服務類的根節點，例如，節點「1234」。當加入消息被路由時(如本領域技術人員將理解的)，沿著路徑的每個節點必須將路由表發送至對應於「R」行數字減去I的特定服務類的加入的節點，其中R是新節點將被插入到轉發節點的路由表的行號。通過這個方案，到加入消息540被路由至根節點時，新節點將具有完整的路由表420以參與針對特定的服務類的PUT和GET的路由。換句話說，新節點發送針對其參與的所有服務類/子環(不僅僅是全局環)的加入消息，並且每個加入消息540被發送至針對特定的服務類的引導程序節點。(應當注意的是特定的環/子環的引導程序節點不需要是該環/子環的一部分。)
[0036]根據本文的技術，諸如PUT和GET之類的DHT操作由特定的服務類識別，以使得它們可被適當地路由至多個子環中的特定的基於服務的子環420。圖6示出了基於服務的DHT操作的示例，其中一個或多個面向客戶端的門戶節點630接收DHT操作請求660 (例如，PUT/GET、PUB/SUB等等)，並且將操作轉發至適當的服務覆蓋。也就是說，門戶節點確定所識別的請求的服務類(標籤665，例如，基於對象類型的服務類編號)，並且將該請求路由至特定的基於服務的子環的所選擇的節點(顯然，門戶節點知道每個基於服務的子環/覆蓋的至少一個成員)。其後，該子環的節點可因此在該基於服務的子環內執行DHT機制。通過這種方式，服務類被用於確定哪個DHT路由表和節點來執行所請求的諸如存儲和檢索對象之類的DHT操作。
[0037]每個節點200維護其自身的針對其所屬的每個環和子環的路由表(數據結構245)。圖7示出了簡化的基於服務的子環路由表的示例，其中節點(例如，節點「1234」)維護針對多個基於服務的子環中的每一個子環的獨立的基於服務的DHT路由表420和獨立的基於服務的DHT資料庫，例如，分別針對服務A和服務B的路由表720a和720b。應當注意的是，除了存儲全局路由表410 (圖7中的710)之外還存儲路由表720a和720b。具體地，DHT節點處的基於服務的路由表是該節點處的全局路由表的子集，並且通過定期輪詢和(例如，基於接近度的)鄰居選擇來維護。因此，全局路由表中的每個單元格(條目)能夠包含多個鄰居以覆蓋DHT節點上運行的所有服務。
[0038]DHT協議通常將保持存活用於活躍性(liveliness)和冗餘。由於本文的技術中基於服務的路由表425 (725)是全局路由表415 (715)的子集,在本文的一個或多個實施例中，保持存活僅與全局路由表中的鄰居進行交換。也就是說，本文的技術基於在全局環內進行交換的保持存活消息，維護針對每個特定的子環的保持存活操作，顯然提供了比維護針對每個子環的保持存活更高的效率。顯然，根據本文的技術，鄰居選擇算法中的優化涉及賦予運行多個服務的鄰居更高的權重。可選擇地，該權重可基於與該鄰居的物理接近度的權衡。
[0039]圖8示出了基於服務的子環保持存活操作的示例，其中儘管創建了多個環，服務感知DHT路由不需要發送保持存活消息840以維護每個獨立的環。反而，需要基於服務的DHT子環中的每個節點加入全局環410以消除否則將針對每個獨立的環420發送的保持存活消息。(然而，需注意的是，全局路由表仍包含比無服務感知DHT環多的條目，這是由於輪詢之後所選擇的鄰居可能無法運行節點(例如，節點「1234」)被訂閱的所有服務。)
[0040]此外，當節點離開全局環410時,全局環410中其餘的節點將從該離開的節點參與的(即，該離開的節點已加入的)所有環(子環420和全局環410)中移除該離開的節點。注意，判定節點是否離開全局環可基於顯式通知或是響應於沒有接收到保持存活消息。
[0041]為了說明服務感知DHT路由使用基於服務的DHT子環，下面的用例作為示例(而不是以限制的方式)被給出:
[0042]1.DHT網絡由兩種類型的節點組成:具有持久存儲的節點(例如，盤節點)和不具有持久存儲的節點(例如，無盤節點)。顯然，無盤節點能參與GET操作，但不能參與PUT操作。管理員可將無盤節點配置為一個服務類並且將盤節點配置為另一服務類，以使得PUT操作將僅被路由至盤節點。
[0043]2.內容提供商使用DHT來存儲影片，其中內容提供商具有部署在全球不同部分的DHT節點。理想情況下，內容提供商希望基於地區的影片觀看人口統計數據(例如，國籍、語言、種族等等)向DHT節點存儲不同的影片，這是由於那將允許更高的GET操作的可能性。例如，中國影片相比於墨西哥更有可能在中國被觀看，同時墨西哥影片則更有可能在墨西哥被觀看。所以內容提供商可能希望識別中國的DHT節點以存儲中國影片而識別墨西哥的節點以存儲墨西哥影片。為了實現這點，墨西哥影片可被分配一個服務類而中國影片可被分配另一服務類。
[0044]顯然，可基於服務感知DHT路由提供其他用例，比如，伺服器容量、時區、專門內容等等，本文所描述的那些僅僅作為示例。
[0045]圖9特別是從節點的角度示出了根據本文所描述的一個或多個實施例的計算機網絡中的服務感知DHT路由的示例簡化過程900。過程900可開始於步驟905，並且進行到步驟910，其中，如上面更加詳細地描述的，節點(例如，1234)加入與(例如，在特定的引導程序節點處的)DHT相關聯的全局環410，其中在步驟915中，該節點還維護針對全局環的DHT路由表415和DHT資料庫。此外，在步驟920中，節點可(例如，基於配置)確定該節點被配置用於的一個或多個服務類，以使得其後在步驟925中節點可根據(一個或多個)特定的服務類加入一個或多個對應的基於服務的子環420。如上面所提到的，(一個或多個)特定的基於服務的子環的所有節點均在全局環內(例如，通過針對該子環的專門引導程序節點)。在步驟930中，節點針對其所加入的基於服務的子環420的每個子環維護基於服務的DHT路由表425和基於服務的DHT資料庫。
[0046]過程900示意性地進行到步驟935，其中節點基於在全局環410內進行交換的保持存活消息參與對(一個或多個)特定的子環420的保持存活操作的維護(維護路由表)。此外，在步驟940中，節點可接收由被路由至特定的基於服務的子環的特定的服務類識別的DHT操作(例如，PUT/GET)。過程900示意性地「結束」於步驟945，然而，過程可從任意上面的步驟處繼續以更新服務類、加入新的基於服務的子環、維護保持存活、接收DHT操作等等，並且過程900的視圖不意圖限制本文的實施例的範圍。
[0047]此外，圖10特別是從門戶節點630的角度示出了根據本文所描述的一個或多個實施例的計算機網絡中的服務感知DHT路由的另一示例簡化過程1000。過程1000可開始於步驟1005，並進行至步驟1010，其中，如上面更加詳細地描述的，門戶節點確定與DHT相關聯的全局環410，並且門戶節點還得知該全局環中的至少一個節點(例如，如果其自身未參與該環)。此外，在步驟1015中，門戶節點確定多個服務類並根據該多個服務類確定相關聯的基於服務的子環420，其中如上面所描述的，基於服務的子環的所有節點均在全局環內。注意，此處門戶節點還得知參與每個基於服務的子環的至少一個節點。根據門戶節點操作，在步驟1020中門戶節點將由特定的服務類識別的引入DHT操作(例如，PUT/GET)路由至多個基於服務的子環中的特定的基於服務的子環，其中該特定的基於服務的子環對應於該被識別的特定的服務類。過程1000示意性地結束於步驟1025，儘管顯然還可有更新DHT成員關係(在全局環和/或子環內的節點)、路由DHT操作等的繼續選擇。還應當注意的是在門戶節點還是參與全局環和/或任意子環的節點的情況下，門戶節點還可根據上面圖9中的過程900進行操作。
[0048]最後，圖11示出了響應於節點離開全局環計算機網絡中的服務感知DHT路由的又一示例簡化過程1100。過程1100開始於步驟1105，並進行到步驟1110，其中，如上面更加詳細地描述的，響應於確定特定的節點已離開全局環(例如，明確地離開或未響應保持存活消息)，在步驟1115中節點(DHT節點)可從該特定的節點已加入的所有多個基於服務的子環中移除該特定的節點。其後，說明性的過程1100結束於步驟1120，直到另一節點離開全局環。
[0049]應當注意的是，儘管如上面所描述的過程900-1100中的某些步驟是可選的，但是圖9-11中所示的步驟僅僅是用於說明的示例，並且某些其他步驟可根據需要而被包括或排除。此外，儘管示出了步驟的特定順序，但是此排序僅僅是說明性的，並且在不背離本文的實施例的範圍的情況下可使用任何適當的步驟安排。另外，儘管過程900-1100是被分開描述的，但是來自每個過程的某些步驟可被併入彼此之中，並且過程之間不意圖互相排斥。
[0050]因此，本文所描述的技術提供了計算機網絡中的服務感知DHT路由。具體地，通過指定哪些節點處理服務水平，並且創建針對每個服務水平的獨立的DHT路由表，本文的技術使客戶能夠根據服務水平建立分布式資料庫應用。也就是說，本文的技術允許管理員在考慮到局部性、網絡和訪問模式信息的情況下定義哪些節點在每個服務水平處存儲哪些對象，這是常規「扁平」DHT不能提供的。此外，由於專用環被創建以處理每個服務水平，因此將可減少PUT/GET延遲。換句話說，由於DHT是服務感知的，與將一切都置於一個扁平DHT環中相對，通過服務水平來存儲和定位對象是更加有效的。
[0051]目前可用的某些技術為每個服務創建「命名空間」，並且支持此服務(為該服務運行代碼)的DHT節點註冊到此命名空間，本質上在單一 DHT環的頂部創建了覆蓋樹。這些樹的維護招致顯著的開銷，這是由於必須在每個服務水平上實現保持存活，即，針對多個服務註冊的物理節點必須交換針對每個服務的保持存活。本文所提出的技術不會遇到這個問題，這是由於多個邏輯環被創建並且覆蓋在全局DHT環的頂部，並且保持存活僅被交換以維護全局環。當前可用的技術還缺乏對於每跳操作(例如，多播、路由跟蹤等等)的本地支持，在每跳操作中，消息路由中的每個節點必須執行一些操作，即，這是因為DHT僅執行路由至鍵(route-to-key)。然而,本文的技術本地支持每跳操作,這是由於消息僅需要在已針對該服務進行註冊的節點上路由。
[0052]此外，由於本文的技術不需要被緩存佔用的附加的磁碟空間，本文的技術優於緩存。緩存可能需要對陳舊的緩存條目進行管理。另外，當與運行多個DHT實例相比較時，本文的技術通常更具有可擴展性，並且不需要像多個DHT實例所需的那麼多的處理能力。也就是說，多個DHT實例擴展性不佳，這是由於DHT協議需要被擴展用於多個實例以便於處理在不同埠接收到的消息，並且每個實例還必須發送其自身的保持存活以維護其路由表。
[0053]此外，本文的技術也提供了超過層級式DHT的優勢。具體地，層次式DHT使用在邏輯層級中被互相連接的一系列完整環(完整的鍵空間，也就是說每個鍵僅能夠存在於一個環中)。例如，層級式DHT被用於將多個DHT環(被稱為域)互連以提供更好的故障隔離和安全性。每個域還可被置於不同的管理控制之下。每個葉級管理處於層級中的樹的底部的域，並且樹中的每個較高的層級通過合併所有在下面的域來處理成群的域。頂級域(被稱為通用域)由所有的域組成。
[0054]然而，層級式DHT的主要用途是合併多個扁平DHT以形成通用DHT(提供商間對等)以使得置於一個域中對象對其他域可用。跨域訪問對象是通過代理節點或網關節點進行的。然而，層級式DHT的使用與如本文所描述的服務感知DHT是不同的。例如，本文的技術指向應用，提供了通用DHT路由平臺可被共享的同時允許特定於應用的功能僅駐存在某些節點上的方式。然而，在層級式DHT結構中，葉節點僅屬於一個域。因此，如果物理節點運行多個應用並且域對應於服務(應用)，則DHT節點必須是邏輯節點，並且多個邏輯節點將駐存在物理DHT節點上。儘管虛擬節點對於異構DHT是有用的技術，但是它們不適用於構建服務域。例如，在企業DHT中，物理節點可運行成百上千的應用，並且用於為每個應用程式維護虛擬節點所需的控制消息量將是不可行的。此外，作為實現層級式DHT優勢的折衷，隨著GET傳播的層級越高，針對對象的GET的延遲呈指數地增加。另一方面，如本文所描述的服務感知DHT構架不會受到這個問題的困擾，這是由於其依靠服務類/服務域來將GET指向適當的邏輯環(子環)。
[0055]儘管已經示出和描述了提供服務感知DHT路由的說明性的實施例，需要理解的是可在本文的實施例的精神和範圍之內做出各種其他的改編和修改。具體地，上面的描述一般地提及與Pastry-like DHT協議類似的做法。然而，這些實施例並不就此被限制，而是適用於任何適當的DHT協議。此外，儘管上面的實施例說明了某些類型的可能特別適用的服務或方案，但是這樣的討論僅意圖作為示例而不限制本文的實施例。
[0056]前面的描述已指向具體的實施例。然而，顯而易見的是可對所描述的實施例做出其他變化和修改以實現它們的一部分或全部優勢。例如，可明確地預期到本文所描述的組件和/或元件能夠被實施為存儲在有形(非暫態)計算機可讀介質(例如，盤/CD/RAM/EEPROM等等)中的、具有在計算機、硬體、固件或它們的組合中執行的程序指令的軟體。因此，此描述僅以示例的方式做出，並且不限制本文的實施例的範圍。因此，所附權利要求的目標在於將所有這樣的變化和修改涵蓋在本文的實施例的真實精神和範圍之內。
【權利要求】
1.一種方法，包括: 通過計算機網絡中的節點加入與分布式散列表(DHT)相關聯的全局環； 維護針對所述全局環的DHT路由表和DHT資料庫； 確定所述節點被配置用於的特定的服務類； 根據所述特定的服務類加入特定的基於服務的子環，其中所述特定的基於服務的子環的所有節點均在所述全局環內；以及 維護針對所述特定的基於服務的子環的基於服務的DHT路由表和基於服務的DHT資料庫，其中，由所述特定的服務類識別的DHT操作被路由至所述特定的基於服務的子環。
2.根據權利要求1所述的方法，其中，存在與所述全局環相關聯的多個基於服務的子環，其中，所述多個基於服務的子環中的每一個子環的每一個節點均在所述全局環內。
3.根據權利要求2所述的方法，其中，所述全局環內的一個或多個特定的節點不在所述多個基於服務的子環中的任何一個子環之內。
4.根據權利要求1所述的方法，還包括: 確定所述節點被配置用於的多個服務類； 根據所述多個服務類加入多個基於服務的子環；以及 維護針對所述多個基於服務的子環中的每一個子環的獨立的基於服務的DHT路由表和獨立的基於服務的DHT資料庫。
5.根據權利要求1所述的方法，還包括: 基於在所述全局環內進行交換的保持存活消息，維護針對所述特定的子環的路由表。
6.根據權利要求1所述的方法，其中，服務類是以下各項中的至少一項:節點類型?』節點性能；節點位置；節點功能；以及節點應用。
7.根據權利要求1所述的方法，其中加入所述基於服務的子環包括:通過所述基於服務的子環的特定的引導程序節點加入該基於服務的子環。
8.一種方法，包括: 通過計算機網絡中的門戶節點確定與分布式散列表(DHT)相關聯的全局環； 確定多個服務類並根據所述多個服務類確定相關聯的基於服務的子環，其中，所述基於服務的子環的所有節點均在所述全局環內；以及 將由特定的服務類識別的DHT操作路由至所述多個基於服務的子環中的特定的基於服務的子環，其中該特定的基於服務的子環對應於所識別的所述特定的服務類。
9.根據權利要求8所述的方法，還包括: 確定特定的節點已離開所述全局環；以及，作為響應， 將所述特定的節點從該所述特定的節點已加入的所有多個基於服務的子環中移除。
10.根據權利要求8所述的方法，其中，所述全局環內的一個或多個特定的節點不在所述多個基於服務的子環中的任何一個子環之內。
11.根據權利要求8所述的方法，還包括: 基於在所述全局環內進行交換的保持存活消息，維護針對所述多個子環的路由表。
12.根據權利要求8所述的方法，其中，服務類是以下各項中的至少一項:節點類型；節點性能；節點位置；節點功能；以及節點應用。
13.根據權利要求8所述的方法，其中，所述門戶節點是參與到所述全局環之內的節 點。
14.一種裝置，包括: 網絡接口，該網絡接口作為節點在計算機網絡內進行通信； 處理器，該處理器被耦合至所述網絡接口並且適用於執行一個或多個處理；以及存儲器，該存儲器被配置為存儲能夠由所述處理器執行的處理，所述處理當被執行時，能操作來: 加入與分布式散列表(DHT)相關聯的全局環； 維護針對所述全局環的DHT路由表和DHT資料庫； 確定所述節點被配置用於的特定的服務類； 根據所述特定的服務類加入特定的基於服務的子環，其中所述特定的基於服務的子環的所有節點均在所述全局環內；以及 維護針對所述特定的基於服務的子環的基於服務的DHT路由表和基於服務的DHT資料庫，其中，由所述特定的服務類識別的DHT操作被路由至所述特定的基於服務的子環。
15.根據權利要求14所述的裝置，其中所述處理當被執行時，還能操作來: 確定所述節點被配置用於的多個服務類； 根據所述多個服務類加入多個基於服務的子環；以及 維護針對所述多個基於服務的子環中的每一個子環的獨立的基於服務的DHT路由表和獨立的基於服務的DHT資料庫。
16.根據權利要求14所述的裝置，其中所述處理當被執行時，還能操作來: 基於在所述全局環內進行交換的保持存活消息維護針對所述特定的子環的路由表。
17.一種裝置，包括: 網絡接口，該網絡接口作為門戶節點在計算機網絡內進行通信； 處理器，該處理器被耦合至所述網絡接口並且適用於執行一個或多個處理；以及存儲器，該存儲器被配置為存儲能夠由所述處理器執行的處理，所述處理當被執行時，能操作來: 確定與分布式散列表(DHT)相關聯的全局環； 確定多個服務類，並且根據所述多個服務類確定相關聯的基於服務的子環，其中，所述基於服務的子環的所有節點均在所述全局環內；以及 將由特定的服務類識別的DHT操作路由至所述多個基於服務的子環中的特定的基於服務的子環，其中，所述特定的基於服務的子環對應於所識別的所述特定的服務類。
18.根據權利要求17所述的裝置，其中，所述處理當被執行時，還能操作來: 確定特定的節點已離開所述全局環；並且，作為響應， 將所述特定的節點從該所述特定的節點已加入的所有多個基於服務的子環中移除。
19.根據權利要求17所述的裝置，其中，所述處理當被執行時，還能操作來: 基於在所述全局環內進行交換的保持存活消息，維護針對所述多個子環的路由表。
20.根據權利要求17所述的裝置，其中所述門戶節點是參與到所述全局環內的節點。
【文檔編號】H04L29/08GK104380289SQ201380027181
【公開日】2015年2月25日 申請日期:2013年5月24日 優先權日:2012年5月25日
【發明者】史蒂文·V·梁, 馬尼什·巴德瓦耶 申請人:思科技術公司