背景技術(shù)

本發(fā)明的一些實(shí)施例涉及輸入數(shù)據(jù)流的分割，更具體地但不僅限于，涉及通過將輸入數(shù)據(jù)流拆分成采用向量處理并行分割的多個(gè)子數(shù)據(jù)流來分割輸入數(shù)據(jù)流。

當(dāng)今是信息時(shí)代，需要在各地之間存儲和/或傳輸?shù)臄?shù)據(jù)量迅速增加。考慮到用于存儲數(shù)據(jù)的存儲空間和/或用于傳輸數(shù)據(jù)的網(wǎng)絡(luò)帶寬，巨大的數(shù)據(jù)量可能主要帶來成本和/或復(fù)雜性的挑戰(zhàn)。

常用于減少存儲和/或傳輸?shù)臄?shù)據(jù)的量的一種解決方案是重復(fù)數(shù)據(jù)刪除(通常稱為“智能壓縮”或“單實(shí)例存儲”)，其是通過消除冗余數(shù)據(jù)來減少數(shù)據(jù)量的方法。雖然存在用于重復(fù)文件刪除的方法，但是考慮到數(shù)據(jù)壓縮，塊重復(fù)刪除可以呈現(xiàn)更好的結(jié)果。在塊重復(fù)刪除中，實(shí)際上只保留數(shù)據(jù)流的數(shù)據(jù)段(塊)的唯一一個(gè)實(shí)例，而與已經(jīng)保留的數(shù)據(jù)段相同的冗余數(shù)據(jù)段替換為指向保留數(shù)據(jù)段的副本的指針。塊重復(fù)刪除處理可包括多個(gè)數(shù)據(jù)類型例如，數(shù)據(jù)文件、媒體文件、流數(shù)據(jù)等的數(shù)據(jù)流，以識別一個(gè)或多個(gè)數(shù)據(jù)段(塊)的唯一實(shí)例。使用Rabin-Karp滾動(dòng)哈希和/或Buzhash等哈希算法為每個(gè)分段生成唯一的數(shù)(哈希值)。將針對每個(gè)分段生成的哈希值與針對先前分段生成的現(xiàn)有哈希值進(jìn)行比較，并且若該哈希值等于現(xiàn)有哈希值，則該分段不保留，而由指向現(xiàn)有分段的副本的指針替代。此外，若該分段更新，可僅保留改變的數(shù)據(jù)，而不保留可能包括大量這種分段的剩余未改變數(shù)據(jù)。

主要挑戰(zhàn)之一是有效地分割數(shù)據(jù)流，以使對分段的數(shù)據(jù)內(nèi)容的改變盡可能少地影響分段。如業(yè)內(nèi)已知，滾動(dòng)哈希技術(shù)可以用于對數(shù)據(jù)流進(jìn)行分割。使用滾動(dòng)哈希，計(jì)算在數(shù)據(jù)流中對數(shù)據(jù)序列進(jìn)行移位的哈希值(在每個(gè)滾動(dòng)序列中刪除結(jié)束數(shù)據(jù)項(xiàng)并插入新數(shù)據(jù)項(xiàng))。檢查所計(jì)算的哈希值是否符合預(yù)定義的一個(gè)或多個(gè)分割標(biāo)準(zhǔn)，且若識別出符合，將各個(gè)滾動(dòng)序列的起始點(diǎn)指定為分段邊界或切割點(diǎn)。

發(fā)明內(nèi)容

根據(jù)本發(fā)明的第一方面，提供一種分割輸入數(shù)據(jù)流的系統(tǒng)，包括：處理器，用于：將輸入數(shù)據(jù)流拆分成多個(gè)子數(shù)據(jù)流，使得所述多個(gè)子數(shù)據(jù)流的每個(gè)子數(shù)據(jù)流與所述多個(gè)子數(shù)據(jù)流中與其相鄰的子數(shù)據(jù)流具有重疊部分；在所述處理器的處理管線中同時(shí)分割所述多個(gè)子數(shù)據(jù)流以創(chuàng)建多個(gè)分割的子數(shù)據(jù)流；根據(jù)所述多個(gè)子數(shù)據(jù)流中的每兩個(gè)連續(xù)子數(shù)據(jù)流的重疊部分的至少一個(gè)重疊分段同步所述多個(gè)分割的子數(shù)據(jù)流的每個(gè)分割的子數(shù)據(jù)流的排序，連接所述多個(gè)分割的子數(shù)據(jù)流以創(chuàng)建分割的數(shù)據(jù)流。

術(shù)語“同時(shí)”因此具有在持續(xù)時(shí)間中重疊的含義，還包括同時(shí)的，例如，發(fā)生在同一時(shí)間的含義。

在本發(fā)明第一方面的第一種實(shí)現(xiàn)方式中，所述處理器是單指令多數(shù)據(jù)(single-instruction-multiple-data，簡稱SIMD)處理器。

根據(jù)第一方面的第一種實(shí)現(xiàn)方式，在第一方面的第二種實(shí)現(xiàn)方式中，所述處理器用于：計(jì)算滾動(dòng)序列的滾動(dòng)哈希值；其中，所述滾動(dòng)序列應(yīng)用于所述多個(gè)子數(shù)據(jù)流中的每個(gè)子數(shù)據(jù)流的連續(xù)數(shù)據(jù)項(xiàng)的多個(gè)序列中的每個(gè)序列；當(dāng)所述滾動(dòng)哈希值符合至少一個(gè)分割標(biāo)準(zhǔn)時(shí)將序列指定為可變長分段以分割所述多個(gè)子數(shù)據(jù)流中的每個(gè)子數(shù)據(jù)流，其中，所述滾動(dòng)序列包括序列的連續(xù)數(shù)據(jù)項(xiàng)的子集。

根據(jù)第一方面的第一或第二種實(shí)現(xiàn)方式中的任一種實(shí)現(xiàn)方式，在第一方面的第三種實(shí)現(xiàn)方式中，所述多個(gè)序列的每個(gè)序列包括預(yù)定義的最少連續(xù)數(shù)據(jù)項(xiàng)。

根據(jù)第一方面的第一至第三種實(shí)現(xiàn)方式中的任一種實(shí)現(xiàn)方式，在第一方面的第四種實(shí)現(xiàn)方式中，當(dāng)在檢測所述滾動(dòng)哈希值對所述至少一個(gè)分割標(biāo)準(zhǔn)的符合性之前，所述多個(gè)序列中的至少一個(gè)大序列的連續(xù)數(shù)據(jù)項(xiàng)的數(shù)量超過預(yù)定義最大值，所述處理器用于將所述至少一個(gè)大序列指定為可變長分段。

根據(jù)第一方面的第一至第四種實(shí)現(xiàn)方式中的任一種實(shí)現(xiàn)方式，在第一方面的第五種實(shí)現(xiàn)方式中，所述處理器用于當(dāng)所述同步失敗時(shí)，依次分割所述輸入數(shù)據(jù)流。

根據(jù)本發(fā)明的第二方面，提供一種分割輸入數(shù)據(jù)流的方法，包括：將輸入數(shù)據(jù)流拆分成多個(gè)子數(shù)據(jù)流，使得所述多個(gè)子數(shù)據(jù)流的每個(gè)子數(shù)據(jù)流與所述多個(gè)子數(shù)據(jù)流中與其相鄰的子數(shù)據(jù)流具有重疊部分；在處理器的處理管線中同時(shí)分割所述多個(gè)子數(shù)據(jù)流以創(chuàng)建多個(gè)分割的子數(shù)據(jù)流；根據(jù)所述多個(gè)子數(shù)據(jù)流中的每兩個(gè)連續(xù)子數(shù)據(jù)流的重疊部分的至少一個(gè)重疊分段同步所述多個(gè)分割的子數(shù)據(jù)流的每個(gè)分割的子數(shù)據(jù)流的排序，連接所述多個(gè)分割的子數(shù)據(jù)流以創(chuàng)建分割的數(shù)據(jù)流。

在本發(fā)明第二方面的第一種實(shí)現(xiàn)方式中，計(jì)算滾動(dòng)序列的滾動(dòng)哈希值；其中，所述滾動(dòng)序列應(yīng)用于所述多個(gè)子數(shù)據(jù)流的每個(gè)子數(shù)據(jù)流的連續(xù)數(shù)據(jù)項(xiàng)的多個(gè)序列中的每個(gè)序列的滾動(dòng)序列；當(dāng)所述滾動(dòng)哈希值符合至少一個(gè)分割標(biāo)準(zhǔn)時(shí)將序列指定為可變長分段以分割所述多個(gè)子數(shù)據(jù)流中的每個(gè)子數(shù)據(jù)流，其中，所述滾動(dòng)序列包括序列的連續(xù)數(shù)據(jù)項(xiàng)的子集。