[發明專利]數據分塊的處理方法和裝置

有效

• 申請號: 201310616966.3
• 申請日: 2013-11-27
• 公開（公告）號: CN104142969B
• 公開（公告）日: 2018-04-06
• 發明（設計）人: 王瑤寶
• 申請（專利權）人: 北京星網銳捷網絡技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京同立鈞成知識產權代理有限公司11205
• 代理人: 劉芳

技術領域

本發明涉及通信技術，尤其涉及一種數據分塊的處理方法和裝置。

背景技術

拉賓指紋算法的計算效率高、隨機性好，且可將數據更改對連續指紋序列的影響限制在局部范圍內，因此可以廣泛應用于重復數據中數據分塊場景，例如：廣域網加速、數據中心備份等。目前，拉賓指紋算法是將字符串以多項式的形式進行表示，該多項式被另一個不可約多項式求余，所得的余數即為該字符串的指紋。具體的，假設A=([b₁,b₂,…b_m-1,b_m])是包含m個字符的字符串，那么可以根據A構造相應的(m-1)度的多項式：A(t)=b₁t^m-1+b₂t^m-2+…+b_m-1t+b_m，其中，t是不定元。同時，給定一個k次多項式（即上述的不可約多項式）：P(t)=a₁t^k+a₂t^k-1+…a_k-1t+a_k，則A(t)除以P(t)的余數f(t)的次數為(k-1)，從而對于給定的字符串A，定義A的指紋f(A)為：f(A)=A(t)modP(t)。

但是，現有的拉賓指紋算法相對復雜，處理速度相對較慢，從而降低了分塊性能。

發明內容

本發明提供一種數據分塊的處理方法和裝置，用于有效地提高分塊處理能力。

本發明的第一個方面是提供一種數據分塊的處理方法，包括：

將寬度為m的窗口在待處理文件中滑動；

當所述待處理文件中的字符b_i滑出所述窗口時，查詢表格，獲取與所述字符b_i對應的U(b_i)和T((P_b+i-1-U(b_i))》23)；并根據公式P_b+i=(2⁸(P_b+i-1-U(b_i)))mod2³²+b_m+i+T((P_b+i-1-U(b_i))》23)，對所述窗口中的字符進行拉賓指紋運算，獲取對應的指紋P_b+i；再對所述P_b+i進行求模，獲取求模結果R_b+i；將i加1，重復執行該步驟，直至獲取到求模結果R_b+N；

根據所述求模結果R_b+i至R_b+N，進行邊界判定，獲取所述待處理文件的數據分塊結果，并將所述數據分塊結果返回給處理器，以供所述處理器根據接收到的所述數據分塊結果，計算每個數據塊對應的哈希值，并用所述哈希值替代對應的數據分塊進行傳輸處理；

其中，初始時，i等于1；P_b+i-1為所述P_b+i對應的窗口的前一個窗口中的字符對應的指紋；b_m+i為移進當前窗口的字符；N為所述待處理文件的字節長度，N和m為整數，且N大于m。

本發明的另一個方面是提供一種數據分塊的處理裝置，包括：

滑動模塊，用于將寬度為m的窗口在待處理文件中滑動；

處理模塊，用于當所述待處理文件中的字符b_i滑出所述窗口時，查詢表格，獲取與所述字符b_i對應的U(b_i)和T((P_b+i-1-U(b_i))》23)；并根據公式P_b+i=(2⁸(P_b+i-1-U(b_i)))mod2³²+b_m+i+T((P_b+i-1-U(b_i))》23)，對所述窗口中的字符進行拉賓指紋運算，獲取對應的指紋P_b+i；再對所述P_b+i進行求模，獲取求模結果R_b+i；將i加1，重復執行該步驟，直至獲取到求模結果R_b+N；