como contar o número de diferenças em grandes fluxos rapidamente?

Question

Eu quero contar o número de diferenças (bytes diferentes) em dois fluxos grandes (dispositivos / arquivos). Por exemplo. dois discos rígidos ou um disco rígido e /dev/zero .

O (s) programa (s) envolvido (s) deve (m) ser rápido (s) (digamos 1GB / s, embora 0.2GB / s provavelmente esteja OK), e eles podem usar no máximo alguns GB de RAM e de tmp arquivos. Em particular, não há nenhum sistema de arquivos disponível que seja grande o suficiente para armazenar as diferenças a serem contadas. Os fluxos têm vários TB em tamanho.

A contagem não precisa (e de fato não deve) tratar os espaços em branco ou os feeds de linha de forma diferente dos outros caracteres. Os fluxos são apenas binários e não são interpretáveis como texto.

Eu disse streams, embora os dispositivos sejam realmente procuráveis. Mas, por motivos de velocidade, todos devem ser preferencialmente feitos com um único passe de streaming sem busca, se possível.

O que eu tentei até agora:

cmp -l /dev/sda /dev/sdb | wc

Mas esta é a maneira de desacelerar; wc sozinho usa um núcleo de CPU > 50% e a saída é apenas cerca de 2MB / s, que é muito lenta por um fator de 100.

    

Answer 1

Com arquivos pesquisáveis, você pode paralelizar isso. Por exemplo, você poderia fazer algo assim (não testado):

# Number of jobs to run at once
jobs=4
# Block size
bs=512
# Total number of block to work with
size=1000000
# Or, to calculate the size automatically for one of the disks,
#size=$(( $(df -B 1 /dev/sda | tail -n1 | awk '{ print $2 }') / $bs ))

# Number of blocks per job
count=$(( $size / $jobs )) 
for i in $(seq 1 $jobs) ; do
    seek=$(( ($i - 1) * $count ))
    cmp -l <(dd bs=$bs skip=$seek count=$count if=/dev/sdb1) <(dd bs=$bs skip=$seek count=$count if=/dev/sdb2) | wc &
done

dd só procurará uma vez quando começar.

    

Answer 2

Você não receberá 1 GB / s a menos que seu hardware ofereça suporte a ele. Os discos rígidos mais rápidos de 7200 rpm podem atingir cerca de 200MB / s em parte de sua superfície e mais como 100MB a 150MB em toda a superfície. Portanto, sua figura “provavelmente ok” está acima do ideal, a menos que você tenha unidades excepcionalmente rápidas ( 10krpm, RAID0).

cmp -l | wc pode ser limitado pela CPU porque você está pedindo a wc para contar palavras, o que é um pouco complicado. cmp -l | wc -l reduzirá a carga na CPU.

A menos que você tenha discos muito rápidos, o cmp -l | wc -l provavelmente já estará vinculado a E / S. Se você estiver usando toda a largura de banda do disco, a paralelização não irá ajudá-lo.

Se cmp -l | wc -l ainda estiver ligado à CPU, ou se você quiser liberar sua CPU para fazer outras coisas, um programa ad hoc que faça a contagem terá um melhor desempenho. Atenção, não testado.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define BUFFER_SIZE 1048576
unsigned char buf1[BUFFER_SIZE];
unsigned char buf2[BUFFER_SIZE];
int main (int argc, char *argv[]) {
    FILE *f1, *f2;
    unsigned long long total = 0, diffs = 0;
    unsigned n1, n2, n, i;
    f1 = fopen(argv[1], "r");
    if (f1 == NULL) {perror(argv[1]); return 2;}
    f2 = fopen(argv[2], "r");
    if (f2 == NULL) {perror(argv[2]); return 2;}
    do {
        n1 = fread(buf1, 1, BUFFER_SIZE, f1);
        n2 = fread(buf2, 1, BUFFER_SIZE, f2);
        if (n1 > n2) n = n2; else n = n1;
        for (i = 0; i < n; i++) if (buf1[i] != buf2[i]) ++diffs;
        total += n;
    } while (n1 == BUFFER_SIZE && n2 == BUFFER_SIZE);
    printf("%llu\n", diffs);
    if (ferror(f1)) {perror(argv[1]);}
    if (ferror(f2)) {perror(argv[2]);}
    if (n1 != n2) {
        fprintf(stderr, "Stopped after %llu bytes.\n", total);
        return 1;
    }
    return 0;
}