基于分段散列的服務命名研究

趙國鋒，賈雯軒

(重慶郵電大學未來網絡研究中心，重慶400065)

0 引言

域名系統(domain name system，DNS)和IP地址是當前網絡僅有的2個命名空間［1］，并且IP地址同時代表位置(locator)和身份(identifier)，使得IP語義超載，限制了很多網絡新功能的使用，如移動性、多宿主等。當前網絡是一個以IP為傳輸核心的架構，用戶需要找到某個服務或者數據，必須要先將DNS域名轉化為IP，再進行尋址查找，一旦IP改變，傳輸就會中斷，并沒有一種對服務本身進行查找的方法。現在有很多研究學者都提出對當前網絡進行改革，主要分為“革命式”和“演進式”，演進式主要是以一種不斷打補丁的方式對當前網絡進行“修補”，并沒有從根本上對網絡架構進行改革。這種方式只是治標不治本，可能會緩解一時之急，但是不能作為長期的策略。要采用革命式的方式來改革網絡架構才能從根本上解決移動性、擴展性、多宿主和流量控制等問題。而用戶對網絡的需求是對網絡上服務的需求，用戶關心的是服務的內容而不是服務的位置，所以，本文提出的是一種以服務為核心，面向服務的網絡，是一種“革命式”的發(fā)展模式，將重點轉移到服務的內容。

1 服務ID

本文認同 NDN［2］(named data networking)思想，認為每一片服務都有自己的名字，并針對服務對服務的identity進行命名。本文是基于身份位置相分離，得到的服務名字和服務位置是一種對應關系，有一個名字位置對(pair)，SID:locator。這意味著，每一個服務ID(SID)至少有一個locator與之對應。locator只用于路由，而identifier只在應用層負責對服務身份的判斷，不再與locator綁定用于路由。將服務的identifier與locator分離，服務的identifier是不會隨著服務遷移后的位置的變化而改變，通信不會發(fā)生中斷，可很好地解決移動性問題。

當基于身份位置相分離來介紹未來因特網架構，identifier必須滿足一些要求。以下是根據ITU［3］(International Telecommunications Union)的提議總結的一些通常的要求:

1)服務的名字可以與多個服務位置相關聯并且不隨位置變化而變化;

2)服務的名字是在應用層;

3)與服務名字有關的session不會因為服務位置的變動而中斷;

4)服務的名字在一個指定范圍內是全球唯一的。

用戶對名字的關心問題有3點不變性、可達性和可信性。不變性是指不管服務遷移到任何地方，服務的名字始終唯一;可達性是指即使網絡和服務失敗名字的內容或者服務也達;可信性是指用戶不考慮內容在哪兒，但是希望內容是可信的。

在未來網絡架構中，服務命名基于以上設計原則和用戶所關心的問題，提出名字由兩部分組成，服務屬性和服務提供商。其中服務的屬性是一個六元組，S=＜N，V，Ts，Te，P，M ＞，分別由字母和數字組成。N為服務的名字，是對服務的描述性名字，不需要唯一，可以同一個名字對應多個服務，也可以一個服務對應多個描述名字;V為服務的版本號;Ts為服務發(fā)布時間;Te為服務的有效時間，在這個時間內服務是可用的，過了有效時間，則需要重新發(fā)布或者更新服務;P為服務的私有性，表示該服務是否屬于私有，是否允許訪問;M表示是否允許遷移，因為有些服務雖然不是私有，但是也不允許遷移，所以，需要將私有性和可遷移性區(qū)別對待。這些屬性都是由服務提供商來確定的，在這里，統稱為服務屬性。

在服務名字中，服務提供商(SISP)由字母和數字組成，最終被Hash為一個64位的數。服務屬性也同樣是被分段Hash為一個64位的值。這2部分的64位值再組合，就得到了最終的128位的UID(unique identifier)，這是一個全球唯一的服務ID。保證了服務SID的全球唯一性。N屬性和SISP之間的關系為一個SISP可以提供多個N屬性;一個N屬性也可以是由多個SISP提供的。

例子:news/text/2011.4/2.0/describe/… #sina

2 哈希選擇

對于每一個唯一的服務都有一個唯一的標識，就像每個人都有自己唯一的指紋一樣。為了避免重復存儲同一個服務，每當新發(fā)布一個服務時，新服務在Hash表中就會有相應的記錄，以表示這些已經發(fā)布的服務，但是若是在Hash表中，直接以字符串的形式存儲，既費內存又費查找時間，因為服務的ID字符串是不定長的。若要存儲200億個服務信息本身至少需要2 TB，即為2 000 GB的容量，而哈希表的存儲效率一般只為50%，那也就是需要4TB以上的空間，并且就算把這些服務全部存儲在計算機內存中，由于服務字符串長度的不固定，以字符串形式來進行查找效率會很低。所以，本文使用一個Hash函數，將服務ID的每一部分隨機的映射為一個64位二進制，即8個字節(jié)的整數空間，服務的兩段標識總共需要128位16字節(jié)的整數空間，這樣大大地節(jié)省了存儲服務信息所需要的存儲空間，也足以存儲互聯網上的服務，這128位二進制就相當于服務ID的指紋［4］。只要選擇的Hash函數足夠好，就可以保證不會產生2個相同的服務ID指紋避免沖突。當一個服務發(fā)布到該注冊中心時，先在Hash表中查找是否有這個服務對應的服務ID指紋，來決定是否要發(fā)布這個服務。對Hash之后的值查找的速度要比直接對字符串查找的速度快幾倍到幾十倍。

本文選用的是MURMUR哈希函數，該函數生成的結果為64位，并且分布很平均，可以減少沖突概率。本文結合結構化P2P網絡信息搜索方式來進行名字與位置關系搜索，利用chord［5］算法來實現對注冊中心之間的搜索，而每一個注冊中心內部都是一個服務器集群，每個服務器上我們設定只存儲10億的數據，那么只需要保證在10億的數據內SID得到的哈希值沒有沖突就可以了。

對服務名字字符串采用分段哈希，將服務屬性和服務提供商分別哈希為64位的哈希值，將服務提供商的64位哈希值經過取模(mod)運算得到的值作為判斷存儲在chord節(jié)點的哪個節(jié)點上，將服務屬性的64位哈希值作為判斷存在注冊中心內部哪個具體的服務器上。這樣的好處是在服務名字和提供商的內部進行分段Hash，存儲時更有利于將相類似的服務存儲在一起，方便查找，同時也進一步降低了Hash沖突的概率。

圖1是將服務名字分段哈希的示意圖，將服務的屬性部分和服務提供商部分分別進行哈希處理，最終得到一個唯一的ID值。

圖1 SID哈希生成UID Fig.1 Hash SID to UID

3 位數驗證

服務ID由服務名字和服務提供商這2部分組成。這2部分分別由Hash函數進行Hash，每一部分得到64位的Hash值，兩者結合生成一個總長度為128位的Hash值。位數的確定是基于2個不可反駁的事實:服務信息總量不會超過存儲總量，服務提供商的數量不會超過人口的數量。所以，就目前所有的信息總的來說，算上數字存儲設備和模擬存儲設備。以目前人類的技術可以存儲至少295艾字節(jié)(exabytes)的信息，這個數字相當于1后面有20個零。

對于服務名稱，設一個服務的大小1 bit，設服務總數量為M，設總存儲容量為S，S=295艾字節(jié)，則有

實際上一個服務的大小遠大于1 bit，則

所以，M＜ ＜265，服務總數量遠小于264，服務名字也遠小于264。

對于服務提供商，設服務提供商有N個，總人口數量為70億，

所以，服務提供商的數量是絕對遠小于264這么多的。

本文采用極值的推算法，如果一個服務只占1 bit的話，264可以表示18 446 744 073 709 552 000這么多個服務，這個18 446 744 073 709 552 000 bit幾乎是全球所有的服務器的存儲容量的總和，并且服務不可能只占1 bit，所以，服務的數量是肯定比264少，那么，服務的名稱也不會比服務的數量多。所以，64位用來存儲服務的名字是絕對足夠的。對于服務提供商而言，如果說如果地球上有100億的人口(實際上人口不足70億)，那么每個人都可以同時作為1 844 674 407這么多個ISP，這是不現實的，因為ISP的數量是絕對比人口的數量少的，不可能每個人都是一個ISP，更不可能每個人同時作為1844674407這么大數量的ISP，所以，64位的空間對ISP來說是綽綽有余的。所以，可以證明，分別用64位來表示服務的名字和服務提供商的數量是絕對足夠的。

4 Hash函數碰撞

生日悖論，至少需要多少人，才能保證至少有2個人同一天生日的概率大于1/2?

設S為有S個元素的集合，從S中隨機選取一個的選法有1/S種，再選第2個和第1個沖突的概率為1/S，再選第3個和前2個沖突的概率為2/S，從S中選取第r個元素和之前的元素相同的概率為(r－1)/S。則從S中隨機任選r個元素互不相同的概率為，因為有ex=，當x=，S→∞時，有原式≈，所以，2個元素相同的概率所以，當p=1/2，S=366時，得到r≥23。這比我們直觀想象的值要小的多。

“生日攻擊法”，生日攻擊［6］方法沒有利用Hash函數的結構和任何代數弱性質，它只依賴于消息摘要的長度，即Hash值的長度。一個64位散列函數，它有2種可能的散列值，要想100%地找到一組碰撞，就需要264+1次約等于1019次攻擊。但是基于生日攻擊［2］的原理，只需要232+1約等于109次攻擊，就有約50%的概率能夠找到一對相同的值。

一般認為，對于n比特輸出的理想Hash函數，碰撞攻擊的復雜度上界為O(2n/2)，對于隨機選取的2n/2個消息，MURMUR為64位的Hash函數，n=64，即S=264，r=232代入，得到P為找到一對碰撞的概率約為0.39［7-8］。對于隨機選取的2n+1/2個消息，找到一對碰撞的概率為0.63。分段Hash后，2端同時沖突的概率為0.39×0.39等于0.152 1。對于所有64位的哈希函數沖突率為這么大，結合存儲容量和查找時間復雜度考慮，我們認為64位的MURMUR哈希函數是符合實驗要求的。

5 結論

本文的目的主要是在基于面向服務的未來網絡的大環(huán)境下，提出對服務名字的命名規(guī)則以及選擇適當的哈希函數對其進行處理，并對哈希函數性能的判斷。最后得出服務名字六元組和選擇的MURMUR哈希函數進行分段哈希是合理的，更利于保持服務身份和位置的對應關系，便于服務的搜索查找。借鑒P2P的信息存儲方式來存儲服務的名字和位置的對應關系。

［1］BALAKRISHNAN H，LAKSHMINARAYANAN K，RATNASAMY S，et al.A layered naming architecture for the Internet［J］.ACM SIGCOMM Computer Communication Review，2004，34(4):343-352.

［2］ZHANG L，ESTRIN D，BURKE J，et al.Named data networking(ndn)project［EB/OL］.［2012-10-30］.http://ccn-uff.wdfiles.com/local—files/projetos/NDN%20Project%20Technical%20Report.pdf.

［3］KAFLE V P，OTSUKI H，INOUR M.An ID/locator split architecture of future networks［C］//Innovations for Digital Inclusions，K-IDI 2009.Kaleidoscope:IEEE press，2009:1-8.

［4］董芳，費新元，肖敏.對等網絡Chord分布式查找服務的研究［J］.計算機應用，2003，23(11):25-28.FANG D，FEIXIN Y，MIN X.Research on Peer-to-peer network Chord distributed lookup service［J］.Journal of Computer Applications，2003，23(11):25-28.

［5］吳軍，數學之美［M］.北京:人民郵電出版社，2012.JUN W.The beauty of mathematics［M］.Beijing:People’s Posts and Telecommunications Press，2012.

［6］WAGNER D.A generalized birthday problem［M］.Heidelberg:Springer-Verlag，2002:288-304.

［7］魏悅川.Hash函數的安全性分析與設計［D］.長沙:國防科學技術大學，2007.WEI Yuechuan.Hash function security analysis and design［D］.Changsha:University of Defense Technology，2007.

［8］STOICA I，MORRIS R，LIBEN N D，et al.Chord:a scalable peer-to-peer lookup protocol for internet applications［J］.IEEE/ACM Transactions，2003，11(1):17-32.