☰

대규모 흐름의 차이 수를 빠르게 계산하는 방법은 무엇입니까?

tag-icon • tag-icon shell shell-script files diff
대규모 흐름의 차이 수를 빠르게 계산하는 방법은 무엇입니까?

두 개의 큰 스트림(장치/파일)의 차이점(다른 바이트) 수를 계산하고 싶습니다. 예를 들어 하드 드라이브 2개 또는 하드 드라이브 1개 및 /dev/zero.

관련된 프로그램은 입력 스트림만큼 빨라야 하며(예: 1GB/s, 0.2GB/s도 작동할 수도 있음) 최대 몇 GB의 RAM 및 tmp 파일을 사용할 수 있습니다. 특히 계산할 차이를 저장할 만큼 큰 사용 가능한 파일 시스템이 없습니다. 이러한 스트림의 크기는 수 테라바이트입니다.

계산에서는 공백이나 개행 문자를 다른 문자와 다르게 처리할 필요가 없으며 실제로 처리할 수도 없습니다. 이러한 스트림은 바이너리 전용이므로 텍스트로 해석할 수 없습니다.

스트림에 대해 이야기하고 있지만 이러한 장치는 실제로 검색 가능합니다. 그러나 속도상의 이유로 가능하다면 조회 없이 하나의 스트림에서 모든 작업을 수행하는 것이 가장 좋습니다.

내가 지금까지 시도한 것 :

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

그러나 이는 너무 느립니다. wc하나의 CPU 코어만 50% 이상 사용하면 출력이 약 2MB/s에 불과해 100배나 느립니다.

답변1

검색 가능한 파일을 사용하면 이 작업을 병렬화할 수 있습니다. 예를 들어 다음을 수행할 수 있습니다(테스트되지 않음).

# 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

ddif는 처음 시작할 때 한 번만 검색됩니다.

답변2

하드웨어가 지원하지 않으면 1GB/s를 얻을 수 없습니다. 가장 빠른 7200rpm 하드 드라이브는 표면 일부에서는 약 200MB/s를 달성할 수 있으며 전체 표면에서는 100MB~150MB에 가깝습니다. 따라서 드라이브가 비정상적으로 빠르지 않는 한(10krpm, RAID0) "아마도 괜찮은" 수치는 실제로 이상적인 수치보다 높습니다.

cmp -l | wcwc약간 복잡한 단어 수 계산을 요청하므로 CPU가 제한될 수 있습니다 . cmp -l | wc -lCPU 부하가 줄어듭니다.

매우 빠른 디스크가 없으면 cmp -l | wc -l이미 IO 바인딩되어 있을 수 있습니다. 전체 디스크 대역폭을 사용하는 경우 병렬화가 도움이 되지 않습니다.

여전히 CPU에 묶여 있거나 cmp -l | wc -l다른 작업을 위해 CPU를 확보하려는 경우 계산을 수행하는 임시 프로그램이 더 나은 성능을 발휘할 것입니다. 경고, 테스트되지 않았습니다.

#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;
}

관련 정보