Alguém pode explicar como funciona a Compressão Diferencial Remota?

Question

Eu sei que a RDC é como a DFSR (Distributed File System Replication) mantém os dados em todos os dispositivos compartilhados em um diretório ativo sincronizado juntos. Eu só entendi que o RDC divide os dados em pedaços, então ele fixa cada um desses pedaços no que é chamado de assinatura. O conjunto de assinaturas é transferido do servidor para o cliente. O cliente compara as assinaturas do servidor com as suas próprias. O cliente então solicita que o servidor envie apenas os dados para as assinaturas que ainda não estão no cliente.

O que eu não entendo é esta citação de Microsoft :

"RDC divides a file's data into chunks by computing the local maxima of a fingerprinting function that is computed at every byte position in the file. A fingerprinting function is a hash function that can be computed incrementally. For example, if you compute the function F over a range of bytes from the file, Bi...Bj, it should then be possible to compute F(Bi+1...Bj+1) incrementally by adding the byte Bj+1 and subtracting the byte Bi. The range of bytes from the file, Bi...Bj, is called the hash window. The length of this window, in bytes, is called the hash window size.

The RDC library's FilterMax signature generator "slides" the hash window across the entire file by adding the byte at the leading edge and subtracting the byte at the trailing edge of the window. Meanwhile, the generator continually examines the sequence of fingerprint function values over a given range of bytes, called the horizon size. If a fingerprint function value is a local maximum within the range, its byte position is chosen as a "cut point," or chunk boundary.

After the file has been divided into chunks, the signature generator computes a strong hash value (an MD4 hash), called a signature, for each chunk. The signatures can be used to compare the contents of two arbitrarily different versions of a file.

Because the size of the signature file grows linearly with the size of the original file, comparing very large files can be expensive. This cost is reduced dramatically by applying the RDC algorithm recursively to the signature files. For example, if the original file size is 9 GB, the signature file size would typically be about 81 MB. If the RDC algorithm is applied to the signature file, the resulting second-level signature file size would be about 5.7 MB."

O que eu não entendo é duas coisas: o que qualquer coisa desse tipo "pode ser calculada incrementalmente" tem a ver com o funcionamento do RDC? E como a recursividade ajuda a reduzir a largura de banda?

    

Answer 1

A parte sobre "Incrementalmente" é simplesmente dizer que a janela de hash pode "deslizar" tirando um byte da frente da janela e adicionando o próximo byte ao final da janela. Assim, a janela pode deslizar de forma incremental a partir do início de um arquivo até o final, a fim de detectar "deslocamentos" entre instâncias de um arquivo. Digamos, por exemplo, você tem um documento de texto. As impressões digitais são geradas a partir dos blocos de dados desse documento de texto. Em seguida, em um momento posterior, você adiciona um parágrafo de texto ao início desse documento de texto. A janela pode começar no início e incrementar o arquivo até corresponder a um bloco para o qual já tenha uma impressão digital.

Com relação à parte sobre recurisividade, digamos, por exemplo, você tem um bloco de dados composto pelos bytes "ABCD" e outro bloco composto pelos bytes "GHIJ". Cada bloco pode ter uma impressão digital de "01" e "02" ou quatro bytes. Em vez de transmitir todos os quatro bytes, o algoritmo tira uma impressão digital de "0102" (ambas as impressões digitais juntas), o que pode produzir uma impressão digital de "03". Se o arquivo de destino tiver a mesma impressão digital das impressões digitais, pode-se presumir que todos os blocos subjacentes estão inalterados e não precisam ser transmitidos.