A: Ok, você está sincronizando isso por toda a Internet; e o que usa você para fazer a sincronização?
B: Oh, nós implementamos o algoritmo rsync.
A: Aham. E o que você faz com os arquivos que são muito grandes?
B: A mesma coisa.
A: E você também sincroniza pastas?
B: Sim.
A: E como você faz isso?
B: Nós fazemos uma iteração nas pastas, usando o algoritmo em cada arquivo, recursivamente nas subpastas.
A: Você pode tentar duas coisas para mim? Primeiro, um arquivo muito grande; e segundo, uma base de código grande, e veja se ele aguenta.
Introdução
Em primeiro lugar, eu sou um admirador do algoritmo (original) rsync. Eu acho que ele foi uma primeira punhalada na sincronização de arquivo, e era tão bom que as pessoas ainda o implementam hoje.
Mas, se você não entende suas forças e fraquezas, você pode acabar se decepcionando.
O problema
Você possui dois arquivos, A’ e A que são diferentes, porém semelhantes. Eles residem em dois locais diferentes conectados por uma rede. Você quer fazer o A’ idêntico ao A.
A solução mais simples é só copiar A, mas dada a semelhança entre os dois arquivos, tem que haver um jeito melhor.
Interlúdio histórico
As redes costumavam ser notoriamente ruins no início dos anos 90. Todo mundo que estava transferindo arquivos a grandes distâncias instintivamente sabia sobre um download de tamanho crítico.
Levaria muito tempo se o arquivo fosse muito grande, produzindo uma chance de 100% de algo dar errado em algum lugar, resultando em um download interrompido. Mesmo que o download tivesse sucesso, as chances eram de uma pequena parte do arquivo ser corrompido, e você tinha que começar tudo de novo. Os dois primeiros alívios para esse problema foram as checksums para detectar danos acidentais, e as retomadas (ser capaz de iniciar um download em um determinado ponto).
O Rsync cuidou de downloads interrompidos e também proporcionou uma solução melhor quando o arquivo estava corrompido. Além disso, permitiu a propagação de baixo custo de pequenas mudanças, abrindo um novo leque de aplicações. Os administradores de sistema tinham uma nova arma.
A estratégia RSync
O Rsync faz uma única viagem. Primeiro ele cria uma assinatura de A ‘ e a envia. Em outro lugar, ele verifica o arquivo local, tenta encontrar as partes que estão na assinatura enquanto constrói uma receita como uma sequência de instruções. É possível derivar o algoritmo a partir de uma versão primitiva, melhorando-o passo a passo.
Já que é muito divertido, vou fazer isso aqui. Enquanto estamos brincando, vamos abstrair o IO, porque atrapalha a visão algoritmica.
Marco 0
Vamos atacar isso no puro estilo homem das cavernas. Fazer uma assinatura é dividir o arquivo em blocos de mesmo tamanho (exceto talvez o último). Iterando sobre os blocos, você calcula uma compilação e acumula resumos e identificadores de blocos. Identificadores de blocos são apenas seus número: o primeiro bloco tem id 0, o segundo bloco id 1, e assim por diante.
let file_signature f b_size =
let f_len = String.length f in
let rec loop acc s i =
if s = f_len
then acc
else
let b_len = min b_size (f_len - s) in
let b = String.sub f s b_len in
let b_sig = block_signature b in
let acc' = (b_sig,i) :: acc in
loop acc' (s+b_len) (i+1)
in
loop [] 0 0
Temos muitas opções de escolha para calcular uma assinatura de bloco. Vamos dar uma de preguiçosos e pegar Digest.string, que é a soma de verificação md5 do bloco.
let block_signature block = Digest.string block
Para recriar o arquivo, você precisará interpretar o fluxo de instruções. Mas o que seriam essas instruções?
Bem, nesta versão, pode ser sido dito a você para copiar um bloco ou escrever um char.
type instruction = | C of char | B of int
Ok, como você combina a assinatura junto com o novo arquivo para gerar um fluxo de instruções? A primeira coisa que vem à mente é varrer o novo arquivo, iniciando na posição s.
- Considere o bloco começando em s e tente encontrá-lo na assinatura.
- Se encontrá-lo, adicione uma instrução B j, e pule um bloco para frente.
- Se perder isso, adicione uma instrução C c, e avance uma posição para frente.
Vamos fazer isto:
let updates f0_sig b_size f1 =
let f1_len = String.length f1 in
let rec loop acc s =
if s = f1_len
then List.rev acc
else
let b_len = min b_size (f1_len - s) in
let block = String.sub f1 s b_len in
let u,step =
try
let d = block_signature block in
let i = List.assoc d f0_sig in
(B i), b_len
with Not_found -> (C block.[0]), 1
in
let acc' = u :: acc in
loop acc' (s + step)
in
loop [] 0
O último passo no nosso esquema de sincronização é criar um arquivo usando o antigo, juntamente com o fluxo de instruções.
let apply old b_size ins =
let old_len = String.length old in
let buf = Buffer.create old_len in
let add_block i =
let s = i * b_size in
let b_len = min b_size (old_len - s) in
let block = String.sub old s b_len in
Buffer.add_string buf block
in
let add_char c = Buffer.add_char buf c in
let () = List.iter (function
| B i -> add_block i
| C c -> add_char c)
ins
in
Buffer.contents buf
Então foram precisas 60 linhas de código para ter uma primeira tentativa de um algoritmo de sincronização.
Vamos tentar isso em um exemplo:
let bs = 5
let remote = "aaaaabbbbbcccccdddddeeeeefffffggggghhhhhiiiiijjjjjkkk"
let mine = "aaaaabXbbbcccccddddde012"
let mine_s = file_signature mine bs
let delta = updates mine_s bs remote
let mine2 = apply mine bs delta;;
val bs : int = 5
val remote : string = "aaaaabbbbbcccccdddddeeeeefffffggggghhhhhiiiiijjjjjkkk"
val mine : string = "aaaaabXbbbcccccddddde012"
val mine_s : (Digest.t * int) list =
[("$\240\t\221\19200\222\199\2035\190|\222~#\n", 4);
("P\248M\175:m\253j\159 \201\248\239B\137B", 3);
("g\199b'k\206\208\158\228\22314\2137\209d\234", 2);
("\196\148\"\21926Lm\179V E=\201O\183,", 1);
("YO\128;8\nA9n\214=\2029P5B", 0)]
val delta : instruction list =
[B 0; C 'b'; C 'b'; C 'b'; C 'b'; C 'b'; B 2; B 3; C 'e'; C 'e'; C 'e';
C 'e'; C 'e'; C 'f'; C 'f'; C 'f'; C 'f'; C 'f'; C 'g'; C 'g'; C 'g';
C 'g'; C 'g'; C 'h'; C 'h'; C 'h'; C 'h'; C 'h'; C 'i'; C 'i'; C 'i';
C 'i'; C 'i'; C 'j'; C 'j'; C 'j'; C 'j'; C 'j'; C 'k'; C 'k'; C 'k']
val mine2 : string = "aaaaabbbbbcccccdddddeeeeefffffggggghhhhhiiiiijjjjjkkk"
Ok, ele funciona, mas quão bom ele é?
Antes que eu possa responder a isso, primeiro uma nota sobre o tamanho do bloco. Há algumas “forças” a serem consideradas:
- o tamanho do bloco precisa ser grande em comparação com a assinatura dele
- se o tamanho do bloco for grande, você vai encontrar menos resultados entre a assinatura e o novo arquivo, então você precisa enviar mais dados de volta
- se o tamanho do bloco for pequeno, você tem muitos deles, ou seja, a sua assinatura será maior e você precisa de uma pesquisa eficiente
O tamanho melhor de bloco dependerá não só do tamanho do arquivo, mas das mudanças reais.
Quão importante é isso mesmo?
Bem, vamos sincronizar duas imagens:
Essas duas imagens são bitmaps de 5,5 MB cada (armazenadas como .bmp).
(Eu, na verdade, fiz upload das versões menores, já que parece inútil deixar seu navegador baixar mais de 10 MB por apenas duas amostras das imagens bobas)
Eu vou sincronizá-las usando tamanhos de blocos diferentes e ver no que dá.
let main () =
let bs = int_of_string (Sys.argv.(1)) in
let () = Printf.printf "bs=%i\n" bs in
let remote = get_data "new_image.bmp" in
let () = Printf.printf "remote: size=%i%!\n" (String.length remote) in
let mine = get_data "old_image.bmp" in
let mine_s = X.file_signature mine bs in
let () = Printf.printf "mine_s: len=%i%!\n" (Array.length mine_s) in
let delta = X.updates mine_s bs remote in
let (nbs,ncs) = List.fold_left (fun(bs,cs) i ->
match i with
| X.B _ -> (bs+1,cs)
| X.C _ -> (bs,cs+1)
) (0,0) delta
in
let mine2 = X.apply mine bs delta in
let () = Printf.printf "mine2: size=%i%!\n" (String.length mine2) in
let () = Printf.printf "bs=%i;cs=%i\n" nbs ncs in
| block size | # block signatures | blocks | chars | time |
| 8192 | 704 | 535 | 1384448 | 71s |
| 4096 | 1407 | 1084 | 1323008 | 92s |
| 2048 | 2813 | 2344 | 960512 | 92s |
| 1024 | 5626 | 4995 | 646144 | 115s |
| 512 | 11251 | 10309 | 482304 | 172s |
| 256 | 22501 | 20972 | 391424 | 283s |
| 128 | 45001 | 42508 | 319104 | 537s |
A primeira coluna é o tamanho do bloco. A segunda é o número de blocos no arquivo, a terceira é o número de instruções B e a quarta é o número de instruções C.
As últimas colunas são medidas do tempo de execução no meu laptop. O tempo de processamento é o maior problema. Ocaml é rápido, mas não o suficiente para compensar a minha brutal ineficiência. Imagine o que faria com um filme de 4 GB.
Marco 1
O problema é rapidamente revelado: List.assoc não é adequado para listas longas.
Uma melhor solução é usar um array, classificá-lo na assinatura do bloco e usar a busca binária.
let block_signature block = Digest.string block
let file_signature f b_size =
let f_len = String.length f in
let s = ref 0 in
let n_blocks = (f_len + b_size -1) / b_size in
Array.init n_blocks
(fun i ->
let start = !s in
let b_len = if start + b_size > f_len then f_len - start else b_size in
let b = String.sub f start b_len in
let b_sig = block_signature b in
let () = s := start + b_len in
(b_sig,i)
)
type instruction =
| C of char
| B of int
let updates f0_sig b_size f1 =
let my_cmp (s0,i0) (s1,i1) = String.compare s0 s1 in
let () = Array.sort my_cmp f0_sig in
let len = Array.length f0_sig in
let rec lookup b=
let rec find min max =
let mid = (min + max) / 2 in
let (ms,mi) = f0_sig.(mid) in
if ms = b
then mi
else if min > max then raise Not_found
else if b > ms then find (mid+1) max
else find min (mid -1)
in
find 0 (len -1)
in
let f1_len = String.length f1 in
let rec loop acc s =
if s = f1_len
then List.rev acc
else
let b_len = min b_size (f1_len - s) in
let block = String.sub f1 s b_len in
let u,step =
try
let d = block_signature block in
let i = lookup d in
(B i), b_len
with Not_found -> (C block.[0]), 1
in
let acc' = u :: acc in
loop acc' (s + step)
in
loop [] 0
let apply old b_size ins =
let old_len = String.length old in
let buf = Buffer.create old_len in
let add_block i =
let s = i * b_size in
let b_len = min b_size (old_len - s) in
let block = String.sub old s b_len in
Buffer.add_string buf block
in
let add_char c = Buffer.add_char buf c in
let () = List.iter (function
| B i -> add_block i
| C c -> add_char c)
ins
in
| block size | # block signatures | blocks | chars | time(s) |
| 8192 | 704 | 535 | 1384448 | 41 |
| 4096 | 1407 | 1084 | 1323008 | 20 |
| 2048 | 2813 | 2344 | 960512 | 7.8 |
| 1024 | 5626 | 4995 | 646144 | 1.9 |
| 512 | 11251 | 10309 | 482304 | 1.1 |
| 256 | 22501 | 20972 | 391424 | 0.8 |
| 128 | 45001 | 42508 | 319104 | 0.9 |
Uau, isso é completamente inesperado (mas não estamos reclamando). Então, o que aconteceu? Bem, a pesquisa era tão dominante que estava encobrindo todos os outros comportamentos.
Agora com o lookup fora do caminho, outras coisas podem ser observadas. O problema agora é que um ‘engano’ não só faz uma instrução C ser emitida, mas o mais importante, ele faz outro sumário ser calculado. Quanto menos blocos forem encontrados, maior o tempo de processamento.
Marco 2
O custo do engano foi resolvido por Andrew Tridgell por meio da introdução de uma segunda função hash mais fraca.
Ele usou o checksum Adler-32. Isso significa que adler32(buffer[a+1:b+1])= cheap(adler32(buffer[a:b]), o que o torna adequado para o nosso problema aqui. A biblioteca padrão ocaml não possui um módulo Adler32, então eu fiz um.
É uma implementação naieve na medida em que segue a definição de perto. De fato, a maioria das operações de módulo pode ser evitada fazendo alguma administração extra.
Eu não me incomodei.
module Adler32 = struct
type t = {mutable a: int; mutable b: int; mutable c: int}
let padler = 65521
let make () = {a = 1 ;b = 0; c = 0}
let from buf offset length =
let too_far = offset + length in
let rec loop a b i=
if i = too_far
then {a; b; c = length}
else (* modulo can be lifted with a bit of math *)
let a' = (a + Char.code(buf.[i])) mod padler in
let b' = (b + a') mod padler in
loop a' b' (i+1)
in
loop 1 0 offset
let reset t = t.a <- 1;t.b <- 0; t.c <- 0
let digest t = (t.b lsl 16) lor t.a
let out t c1 =
let x1 = Char.code c1 in
t.a <- (t.a - x1) mod padler;
t.b <- (t.b - t.c * x1 -1) mod padler;
t.c <- t.c - 1
let rotate t c1 cn =
let up x = if x >= 0 then x else x + padler in
let x1 = Char.code c1 in
let xn = Char.code cn in
t.a <- up ((t.a - x1 + xn) mod padler);
t.b <- let f = (t.c * x1) mod padler in
let r = (t.b - f + t.a -1) mod padler in
up r
let update t buf offset length =
let too_far = offset + length in
let rec loop i =
if i = too_far then ()
else
let x = Char.code buf.[i] in
let () = t.a <- (t.a + x) mod padler in
let () = t.b <- (t.b + t.a) mod padler in
let () = t.c <- t.c + 1 in
loop (i +1)
in
loop offset
let string block =
let t = from block 0 (String.length block) in
digest t
end
O Adler32 é muito mais fraco do que o md5 e usá-lo te expõe a colisões. Então, na verdade, ele age como um teste barato que pode produzir falsos positivos. Essa é a razão pela qual o algoritmo rsync mantém ambos: se o Adler32 do buffer for encontrado na assinatura, existe uma segunda verificação para ver se o md5s combina. O fato de às vezes um precisar girar checksum e em outras vezes precisar reinicializar uma parte do buffer, complica o cálculo das atualizações um pouco.
O código é mostrado abaixo.
let updates f0_sig b_size f1 =
let my_cmp (wh0,sh0,i0) (wh1, sh1,i1) = compare wh0 wh1 in
let () = Array.sort my_cmp f0_sig in
let len = Array.length f0_sig in
let rec lookup w =
let rec find min max =
let mid = (min + max) / 2 in
let (mw, ms,mi) = f0_sig.(mid) in
if mw = w
then (ms,mi)
else if min > max then raise Not_found
else if w > mw then find (mid+1) max
else find min (mid -1)
in
find 0 (len -1)
in
let f1_len = String.length f1 in
let weak = Adler32.from f1 0 b_size in
let rec loop acc b e =
if b = f1_len
then List.rev acc
else
let wh = Adler32.digest weak in
let step_1 () =
let bc = f1.[b] in
let a = C bc in
let b' = b + 1 in
if e +1 < f1_len
then
let e' = e + 1 in
let ec = f1.[e] in
let () = Adler32.rotate weak bc ec in
loop (a:: acc) b' e'
else
let e' = e in
let () = Adler32.out weak bc in
loop (a:: acc) b' e'
in
try
let (s0,i0) = lookup wh in
let sh = Digest.substring f1 b (e - b) in
if s0 = sh
then
let b' = e in
let e' = min f1_len (e + b_size) in
let a = B i0 in
let () = Adler32.reset weak in
let () = Adler32.update weak f1 b' (e' - b') in
loop (a :: acc) b' e'
else step_1 ()
with Not_found -> step_1 ()
in
loop [] 0 b_size
O código, de fato, é um pouco mais confuso porque temos mais coisas para controlar, ao mesmo tempo, mesmo assim ainda é muito pequeno. Vamos ver quão bem é o seu desempenho:
| block size | # block signatures | blocks | chars | time(s) |
| 8192 | 704 | 535 | 1384448 | 0.9 |
| 4096 | 1407 | 1084 | 1332008 | 0.9 |
| 2048 | 2813 | 2344 | 960512 | 0.8 |
| 1024 | 5626 | 4995 | 646114 | 0.6 |
| 512 | 11251 | 10309 | 482304 | 0.6 |
| 256 | 22501 | 20401 | 537600 | 0.7 |
| 128 | 45001 | 42508 | 319104 | 0.7 |
Isso remove quase completamente o custo de uma falha, pelo menos para as coisas desse tamanho. A escolha do tamanho do bloco afeta, no entanto, a quantidade de dados que você precisa enviar.
Existe um monte de outras coisas que você pode fazer aqui:
- BlockSizeHeuristic: algo como O(sqrt (file_size))
- SuperInstructions: fazer instruções para blocos e caracteres consecutivos
- função Emit: não acumula as atualizações, mas as emite (usando uma função callback)
- Assinaturas menores: você pode considerar deixar cair alguns bytes do hash forte
- IO
- Compactar fluxo de atualização
- …
O último problema que ainda existe é que algumas modificações não são bem tratadas pelo algoritmo (por exemplo um byte alterado em cada bloco).
Talvez você possa tentar um algorítimo melhor.
Existe um monte deles por aí, e vale a pena dar uma conferida. (Antes que saiba que você estará se deparando com trees merkle ou set reconciliation).
De qualquer maneira, eu já ultrapassei a minha cota para este artigo, porém ainda quero falar uma coisa sobre sincronização de pastas.
O próximo problema
Você possui duas trees de arquivos, A ‘e A que são tão diferentes, porém semelhantes. Elas residem em dois locais diferentes ligados por uma rede. Você quer fazer a A’ idêntica a A.
O que não fazer
Não ande a pasta e não faça ‘rsync’ em cada arquivo que você encontrar.
Um pequeno cálculo vai mostrar o quão ruim ele realmente é.
Suponha que você tenha 20 mil arquivos, cada um com 1 KB. Suponha que um rsync te custe por volta de 0.1s
(ler o arquivo, enviar a assinatura, construir o fluxo de atualizações, aplicando-os).
Isso custa a você cerca de 2 mil segundos ou mais do que meia hora. Os administradores do sistema sabem melhor:
eles não hesitariam: “fazer um tar da tree, sincronizar os tars, e extrair o tar sincronizado”.
Suponha que cada uma das ações demore 5 segundos (superestimando), você ainda estará sincronizado em 15 segundos.
Ou talvez você possa tentar unison. É ocaml também, você sabe.
Se divirta!
***
Texto original disponível em http://blog.incubaid.com/2012/02/14/rediscovering-the-rsync-algorithm/
De 0 a 10, o quanto você recomendaria este artigo para um amigo?