[發明專利]利用異步數據詞典在多租戶共享的基礎設施中的基于流的重復數據刪除

有效

• 申請號: 201380020000.1
• 申請日: 2013-05-17
• 公開（公告）號: CN104221003B
• 公開（公告）日: 2017-08-11
• 發明（設計）人: C·E·格羅;F·T·雷赫頓;A·F·徹姆帕格內
• 申請（專利權）人: 阿卡麥科技公司
• 主分類號: G06F15/16
• 分類號: G06F15/16
• 代理公司: 中國國際貿易促進委員會專利商標事務所11038
• 代理人: 李曉芳

本申請基于并要求2012年5月17日提交的序列號No.61/648,209的優先權。

技術領域

本申請一般涉及通過網絡的數據通信。

背景技術

分布式計算機系統在現有技術中是公知的。一個這樣的分布式計算機系統是通常由服務提供者操作并管理的“內容遞送網絡”或“CDN”。服務提供者通常代表使用服務提供者的共享基礎設施的第三方(用戶)提供內容遞送服務。此類型的分布式系統有時被稱為“覆蓋網絡”并且通常是指由網絡或網絡鏈接在一起的獨立計算機與軟件、系統、協議和技術的集合，所述技術被設計以便于各種服務，諸如內容遞送、網絡應用加速、或外包源站點基礎設施的其它支持。CDN服務提供者通常經由數字資產(諸如網站)提供服務遞送，其被提供在用戶門戶中并且然后被布置到網絡。

數據差異化是在服務器與客戶端之間利用資源的共享先前實例，在壓縮術語中也稱為共享詞典之內的數據版本，的公知的技術和方法；所述處理通過僅僅發送差異或自從那些先前實例以來出現的改變而工作。數據差異化涉及壓縮，但是它是稍微有差別的構思。具體地，直觀地，差異(“diff””)是一種壓縮形式。只要接收者與發送者具有相同的初始文件，那些發送者可以給接收者diff而不是整個新文件。diff實際上說明如何從舊文件創建新文件。它通常遠小于整個新文件并且因此是一種壓縮形式。文檔的第一版本與前述文檔的第二版本之間的diff是數據差異；數據差異是利用文檔的第一版本作為預設詞典的文檔的第二版本的壓縮結果。

基于流的重復數據刪除(“重復數據刪除”)系統在現有技術中也是公知的。一般，基于流的重復數據刪除系統通過檢查流過連接的發送對等方的數據和用指到每個對等方關于給定塊已經同步的共享詞典中的參考來替換數據塊進行工作。引用本身遠小于數據并且通常是它的散列或指紋。當接收對等方接收修改的流時，它利用原始數據替換引用以再一次做出整個流。例如，考慮一個系統，其中指紋是用單個字母變量表示的唯一散列。發送對等方的詞典然后可以如圖3所示。接收對等方的詞典可以如圖4所示。然后，例如，如果發送對等方被認為發送諸如“Hello，how are you？Akamai is Awesome！”之類的串，則重復數據刪除系統將處理數據并且發送以下消息：“He[X]re you？[T][M]ome！”。接收對等方利用它的詞典解碼消息。注意，在此示例中，發送對等方并不利用引用[O]替換“ome！”。這是因為，雖然發送對等方具有指紋和在它的高速緩存中存儲它的塊，但是對等方知道(通過機制)接收對等方并不具有。因此，發送對等方在發送它之前不在消息中插入引用。此類型的系統通常以若干公知方式填充是對稱的詞典。在一個方法中，當數據流流過數據處理器時以固定長度的塊(例如，每塊具有15個符號的長度)填充詞典。第一次數據經過發送和接收對等方時，并且假定它們都以同樣的方式構成詞典，則兩個對等方以具有包含相同的條目的詞典終止。但是，此方法不是最優的，因為它常遭受被稱為“偏移”問題的問題，其可以不利地影響生成的指紋并且破壞整個方案。

可替換方法利用以滾動方式計算的散列使用可變長度的塊。在基于被稱為Rabin指紋技術的公知的解決方案中，系統在指紋處理期間跨數據流滑過特定大小(例如，48字節)的窗口。在Muthitacharoen等的標題為“A Low-Bandwidth Network File System”(LBFS)的論文中描述該技術的實施方式，并且結果實現可變大小的抗偏移塊。

當前供應基于流的重復數據刪除產品和服務的廠家通過配對設備解決詞典發現的問題(知道什么信息處于對等方的詞典中)。因此，例如，電器/盒子廠家依賴于在每個末端上的一對設備或處理以彼此通信以維護讓每個端知道什么引用存在于配對的對等方中的表。但是，這類解決方案僅僅在處理表示“路徑中”對的各個盒子與單元時工作。

但是，路徑中配對的解決方案在諸如CDN之類的覆蓋網絡的背景中是不實際的，其中節點的分布更接近地類似樹。因此，例如，在代表性的實施方式中，并且參考特定源服務器(或，一般地說，“租戶”位于“根”處)，覆蓋網絡可以具有更接近于根的父層服務器，和更接近于葉節點的客戶端邊緣服務器。換句話說，替換需要知道一個或多個對等方盒子(諸如在公知的盒子廠家解決方案中)的小集合的盒子，父層服務器可以需要與數十、數百乃至數千的邊緣區域聯系，每個都可能包含許多服務器。在這個背景下，每個機器表不能衡量。

因此，仍然需要提供在覆蓋網絡背景中用于重復數據刪除的增強的技術。

發明內容