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

Question

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

在实际查找 HashSet 之前，使用 BloomFilter 也完成了完全相同的算法。由于 BloomFilter 仅在 "non-containment" 上提供保证并且可以在包含时提供误报，如果 BloomFilter 报告密钥可能已经存在，我也会查找 HashSet。

拼接后的文件大小>1GB，因此512字节的区块签名数量超过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。

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

A simple duplicate block finding algorithm performs worse when using BloomFilter for lookups

java

algorithm

hash

bloom-filter

md5sum