具有大文件的 Java CRC (Adler)

Question

我有以下情况:一个包含大文件的目录树(大约 5000 个文件，大小约为 4Gb)。我需要在这棵树中查找重复项。

我尝试使用 Java 内置的 CRC32 和 Adler32 类，但它非常慢(每个文件大约 3-4 分钟)。

代码是这样的:

1) Init map <path, checksum>
2) Create CheckSum instance (CRC32 or Adler32);
3) Read file per block (10-100 bytes);
4) In each iteration call update()
5) Result checksum passed in map <path, summ>
6) Find duplicates

问题:有什么方法可以加快第 3-4 行校验和的收集速度吗？

Answer 1

我会通过以下方式解决这个问题:

1. 尝试使用 Java 8 并行流或类似的东西，以便利用我的多核 CPU 来加快速度。
2. 用所有文件填充 map 。
3. 获取所有文件大小。
4. 删除所有具有唯一文件大小的文件。如果您的文件“非常正常”，这很可能已经消除了几个较大的文件。这实际上可以通过使用文件大小作为映射中的键和列表作为值来完成。然后删除列表大小为 1 的所有条目。
5. 获取每个文件的下一个(第一次:第一个)4K 字节的校验和。
6. 删除所有具有唯一校验和的文件。
7. 重复4.和5.，直到所有无唯一校验和的文件全部读取完毕。
8. 其余文件是重复的文件(如果校验和没有冲突)。
9. 比较重复文件的文件内容，以防发生冲突。

加快校验和的关键是分块进行并在之间进行比较。如果第一个字节已经不同，为什么要查看剩余的字节。

加速比较的另一个关键可能是反转 map 。我会使用 Map<checksum, List<path>>而不是Map<path, checksum> 。这样您就可以非常直接地消除所有具有大小为 1 的列表的条目，而无需任何进一步的查找或比较。

可能还有比这更聪明的方法，只需抛弃我读到该任务时想到的内容即可。

我已经画了一个几乎可以执行此操作的小程序。它不会获得碎片中的校验和。原因是，当我对 236670 个文件、总共 6 GB 数据运行时，只花了 7 秒。免责声明:我有一个 SSD。但也许我什至会更新部分校验和的程序。

import java.io.*;
import java.nio.file.*;
import java.nio.file.attribute.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.stream.*;
import java.util.zip.*;

public class FindDuplicates {
    public static void main(final String... args) throws IOException {
        findDuplicates(argsOrCurrentDirectory(args));
    }

    private static String[] argsOrCurrentDirectory(final String... args) {
        return args.length == 0 ? new String[] {"."} : args;
    }

    private static void findDuplicates(final String... paths) throws IOException {
        final Stream<Path> allFilesInPaths = find(paths);

        final Map<Long, List<Path>> filesBySize = allFilesInPaths.collect(Collectors.groupingByConcurrent(path -> path.toFile().length()));
        final Stream<Path> filesWithNonUniqueSizes = getValueStreamFromDuplicates(filesBySize);

        final Map<Long, List<Path>> filesByChecksum = filesWithNonUniqueSizes.collect(Collectors.groupingBy(FindDuplicates::getChecksum));
        final Stream<Path> filesWithNonUniqueChecksums = getValueStreamFromDuplicates(filesByChecksum);

        filesWithNonUniqueChecksums.forEach(System.out::println);
    }

    private static Stream<Path> toPaths(final String... pathnames) {
        return Arrays.asList(pathnames).parallelStream().map(FileSystems.getDefault()::getPath);
    }

    private static Stream<Path> find(final String... pathnames) {
        return find(toPaths(pathnames));
    }

    private static Stream<Path> find(final Stream<Path> paths) {
        return paths.flatMap(FindDuplicates::findSinglePath);
    }

    private static Stream<Path> findSinglePath(final Path path) {
        try {
            return Files.find(path, 127, ($, attrs) -> attrs.isRegularFile());
        } catch (final IOException e) {
            System.err.format("%s: error: Unable to traverse path: %s%n", path, e.getMessage());
            return Stream.empty();
        }
    }

    public static <V> Stream<V> getValueStreamFromDuplicates(final Map<?, List<V>> original) {
        return original.values().parallelStream().filter(list -> list.size() > 1).flatMap(Collection::parallelStream);
    }

    public static long getChecksum(final Path path) {
        try (final CheckedInputStream in = new CheckedInputStream(new BufferedInputStream(new FileInputStream(path.toFile())), new CRC32())) {
            return tryGetChecksum(in);
        } catch (final IOException e) {
            System.err.format("%s: error: Unable to calculate checksum: %s%n", path, e.getMessage());
            return 0L;
        }
    }

    public static long tryGetChecksum(final CheckedInputStream in) throws IOException {
        final byte[] buf = new byte[4096];
        for (int bytesRead; (bytesRead = in.read(buf)) != -1; );
        return in.getChecksum().getValue();
    }
}