간단한 중복 블록 찾기 알고리즘은 조회를 위해 BloomFilter를 사용할 때 성능이 저하됩니다.

Question

두 개의 ISO 파일을 하나의 파일로 연결했습니다. 개별 ISO 파일은 모두 동일한 공급 업체이지만 다른 버전의 Linux 배포판입니다. 내가 작성한 프로그램 (아래에 표시)에서 512 바이트 블록으로 연결된 파일을 연결하고 MD5sum을 계산합니다. MD5sum은 Hashet<String>에 저장됩니다. 동일한 서명을 가진 블록이 HashSet 룩업을 사용하여 발견되면, 이것은 기록된다.

정확한 알고리즘은 HashSet에서 실제로 검색하기 전에 BloomFilter를 사용하여 수행됩니다. BloomFilter은 "비 포함"에 대해서만 보장하고 봉쇄에 오탐을 제공 할 수 있으므로 BloomFilter에서 키가 이미있을 수 있다고보고하면 HashSet을 조회합니다.

연결된 파일 크기가 1GB를 초과하므로 512 바이트 블록 서명 수가 177 만 개를 초과합니다. BloomFilter을 사용하는 접근법의 성능은 일관되게 첫 번째 접근법보다 6 배 이상 높습니다.

그 이유는 무엇입니까? 내가 여기서 한 일이 잘못 되었 니?

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

샘플 출력은 : 당신이 Bloom filter 약간의 포인트를 놓친처럼

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

것 같습니다. 우리는 기억을 감당할 수없고 정확성을 잃을 것에 동의 할 때 사용합니다. 예를 들어, 사용자에게 이미 알림을받은 사용자의 컬렉션을 저장하는 데 저장하라는 메시지가 두 푸시 알림을 1/100 (또는 보내지 않은 사용자)에게 전달하기로 결정했습니다.

O(1)에서 Bloom filter은 처리 시간을 단축시키지 않으므로 속도가 느려집니다. 반면에 그것은 통계에 나타날 정도로 중요하지 않은 아주 적은 메모리를 사용합니다.

in에 대해 not in 이상을 표시하는 데 약 같은 시간이 걸리기 때문입니다.

더 읽을 수 있습니다 here.