java - 一个简单的重复 block 查找算法在使用 BloomFilter 进行查找时性能更差

Question

我已将两个 ISO 文件合并为一个文件。这两个单独的 ISO 文件都是同一供应商但不同版本的 Linux 发行版。在我编写的程序中(如下所示)，以 512 字节的 block 和 block 的 MD5sum 计算读取的串联文件。 MD5sum 存储在 Hashet<String> 中.如果使用 HashSet 找到具有相同签名的 block 查找，这是记录。

在实际查找 HashSet 之前，使用 BloomFilter 也完成了完全相同的算法。 .作为BloomFilter仅提供“非包含”保证，并且可以提供包含误报，如果 BloomFilter，我也会查找 HashSet报告 key 可能已经存在。

连接后的文件大小 > 1GB，因此 512 字节 block 签名的数量超过 177 万个。使用 BloomFilter 的方法的性能始终是第一种方法的六倍。

为什么会出现这种情况？我在这里做错了什么吗？

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnel;
import com.google.common.hash.PrimitiveSink;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.HashSet;
import java.util.concurrent.TimeUnit;
import org.apache.commons.codec.digest.DigestUtils;
import org.apache.commons.lang3.time.StopWatch;

public class SimpleDedupTrial {

    public static void main(String[] args) throws IOException {

        int blockSize = 512;

        HashSet<String> signatureSet = new HashSet<>();

        File f = new File(
            "D:\\keshav\\per\\projects\\work-area\\dedup-temp\\merged-iso"
        );

        FileInputStream fis = new FileInputStream(f);

        long length = f.length();
        long sizeSaved = 0l;

        StopWatch sw = new StopWatch();

        int len;
        byte[] buffer = new byte[blockSize];
        while ((len = fis.read(buffer)) != -1) {

            String md5Hex = DigestUtils.md5Hex(buffer);

            if (sw.isStopped()) {
                sw.start();
            }
            if (sw.isSuspended()) {
                sw.resume();
            }

            if (signatureSet.contains(md5Hex)) {
                sizeSaved += len;
            } else {
                signatureSet.add(md5Hex);
            }

            sw.suspend();
        }

        sw.stop();

        fis.close();

        System.out.println("Time: "+sw.getTime(TimeUnit.MILLISECONDS));
        System.out.println("File size in MB: "+convertToMB(length));
        System.out.println("Size saved in MB: "+convertToMB(sizeSaved));
        System.out.println("Signature set size: "+signatureSet.size());
        System.out.println("Duplicate ratio: "+ ((double)sizeSaved * 100 / length));

        System.out.println("With Blooom:");
        useBloomFilter();
    }

    private static long convertToMB(long sizeInBytes) {
        return sizeInBytes / (1024 * 1024);
    }

    private static void useBloomFilter() throws IOException {
        int blockSize = 512;

        Funnel<String> strFunnel = (String t, PrimitiveSink ps) -> {
            ps.putString(t, Charsets.US_ASCII);
        };

        HashSet<String> signatureSet = new HashSet<>();

        File f = new File(
            "D:\\keshav\\per\\projects\\work-area\\dedup-temp\\merged-iso"
        );

        FileInputStream fis = new FileInputStream(f);

        long length = f.length();
        long sizeSaved = 0l;

        BloomFilter<String> signatureBloomFilter = BloomFilter.create(
            strFunnel, (length / blockSize)
        );

        StopWatch sw = new StopWatch();

        int len;
        byte[] buffer = new byte[blockSize];
        while ((len = fis.read(buffer)) != -1) {

            String md5Hex = DigestUtils.md5Hex(buffer);

            if (sw.isStopped()) {
                sw.start();
            }
            if (sw.isSuspended()) {
                sw.resume();
            }

            if (signatureBloomFilter.mightContain(md5Hex)) {
                if (!signatureSet.contains(md5Hex)) {
                    signatureBloomFilter.put(md5Hex);
                    signatureSet.add(md5Hex);
                } else {
                    sizeSaved += len;
                }
            } else {
                signatureBloomFilter.put(md5Hex);
                signatureSet.add(md5Hex);
            }
            sw.suspend();
        }

        sw.stop();

        fis.close();

        System.out.println("Time: "+sw.getTime(TimeUnit.MILLISECONDS));
        System.out.println("File size in MB: "+convertToMB(length));
        System.out.println("Size saved in MB: "+convertToMB(sizeSaved));
        System.out.println("Signature set size: "+signatureSet.size());
        System.out.println("Duplicate ratio: "+ ((double)sizeSaved * 100 / length));
    }
}

示例输出:

Time: 819
File size in MB: 1071
Size saved in MB: 205
Signature set size: 1774107
Duplicate ratio: 19.183032558071734
With Blooom:
Time: 4539
File size in MB: 1071
Size saved in MB: 205
Signature set size: 1774107
Duplicate ratio: 19.183032558071734

Answer 1

看起来您有点错过了 Bloom filter 的要点。当我们负担不起内存并同意失去一些准确性时，我们会使用它们。例如，决定向 1/100(或不向他们发送)用户发送 2 条推送通知，以节省存储已收到通知的用户的集合。

在 HashSet 中，您预计访问时间为 O(1)，因此 Bloom filter 不会加速该过程，并且你看它减慢了速度。另一方面，它使用的内存非常少，不足以显示在您的统计信息中。

这是因为指示 not in 和 in 花费的时间大致相同。

您可以阅读更多here .