Bloom Filter — "Kesinlikle Yok" mu, "Belki Var" mı?

Büyük bir düğünün vestiyerinde, her misafir adının gösterdiği birkaç askıya bir kurdele bağlıyor. Birinin gelip gelmediğini merak edersen, onun askılarına bakarsın. Askılardan biri boşsa o kişi kesinlikle gelmemiştir.

Nasıl çalışır?

Bloom filter?Terimin tanımını açBloom filterBir şeyin kümede olup olmadığını az bellekle cevaplayan bit dizisi. "Kesinlikle yok" ya da "belki var" der; eklenmiş bir şeyi hiç kaçırmaz.Sözlükte gör →, başta hepsi 0 olan bir bit dizisidir. Bir hesap eklerken birkaç hash fonksiyonu hesabın adını dizideki birkaç konuma çevirir ve o bitler 1 yapılır.

Sorgularken aynı konumlara bakılır. Bitlerden biri 0 ise hesap kesinlikle eklenmemiştir. Hepsi 1 ise “belki var” denir, çünkü o bitleri başka hesaplar da doldurmuş olabilir.

Yanlış alarm nereden gelir?

“Belki var” deyip aslında olmayan her cevap bir false positive?Terimin tanımını açfalse positiveOlmayan bir şey için "var" ya da "belki var" denmesi; yanlış alarm. Bloom filter'da yalnızca bu yönde hata olur.Sözlükte gör →’tir. Bloom filter’da bunun tersi, yani var olanı kaçırmak, hiç olmaz.

Yanlış alarm oranını iki şey belirler: dizinin boyu ve hash sayısı. Yer bolsa birkaç hash, temiz bir müşterinin en az bir bitinin boş kalma ihtimalini artırır. Yer darsa her ek hash diziyi daha çabuk doldurur.

Kendin gör

1. Varsayılanla oynat. Küçük filtre, 1 hash: 20 temiz müşteriden 11’ine “belki var” dendi.
2. “3 hash” seç. Küçük dizi neredeyse doldu ve yanlış alarm 15’e çıktı.
3. “Büyük (256 bit)” ve “1 hash” seç. Yanlış alarm 2’ye düştü.
4. Büyükte “3 hash” seç. Hiçbir temiz müşteri için veritabanına gidilmedi.

Tuzaklar

“Belki var” cevabını kesin saymak. Bir müşteriyi “belki şüpheli” diye engellersen temiz insanları cezalandırırsın. “Belki var” yalnızca “veritabanına sor” demektir.

Silmeye çalışmak. Bir biti 0 yapmak, o biti paylaşan başka hesapları da filtreden siler. Silme gerekiyorsa filtreyi baştan kur ya da sayaçlı bir türünü kullan.

Boyu başta yanlış seçmek. Eklenen kayıt sayısı tahminini aşınca bitler dolar ve yanlış alarm hızla artar. Beklenen kayıt sayısını ve kabul edilebilir oranı baştan belirle.

Aşağıdaki örnek bir ödeme servisinden: şüpheli hesap listesi açılışta bir Bloom filter’a yükleniyor, “kesinlikle yok” diyenler için veritabanına gidilmiyor.

1
@Component
2
class SuspiciousAccountFilter {
3

4
    private static final int EXPECTED_ACCOUNTS = 2_000_000;
5
    private static final double FALSE_POSITIVE_RATE = 0.001;
6

7
    private final SuspiciousAccountRepository repository;
8
    private volatile BloomFilter<String> filter = empty();
9

10
    SuspiciousAccountFilter(SuspiciousAccountRepository repository) {
11
        this.repository = repository;
12
    }
13

14
    private static BloomFilter<String> empty() {
15
        return BloomFilter.create(Funnels.stringFunnel(StandardCharsets.UTF_8), EXPECTED_ACCOUNTS, FALSE_POSITIVE_RATE);
16
    }
17

18
    /** Rebuilt from scratch: bits cannot be removed safely. */
19
    @EventListener(ApplicationReadyEvent.class)
20
    @Scheduled(cron = "0 0 3 * * *")
21
    void rebuild() {
22
        BloomFilter<String> fresh = empty();
23
        repository.streamAllIbans().forEach(fresh::put);
24
        filter = fresh;   // swap in one step; readers never see a half-built filter
25
    }
26

27
    boolean mightBeSuspicious(String iban) {
28
        return filter.mightContain(iban);
29
    }
30
}

1
@Service
2
class RecipientScreening {
3

4
    private final SuspiciousAccountFilter filter;
5
    private final SuspiciousAccountRepository repository;
6
    private final Counter databaseChecks;
7

8
    RecipientScreening(SuspiciousAccountFilter filter, SuspiciousAccountRepository repository, MeterRegistry registry) {
9
        this.filter = filter;
10
        this.repository = repository;
11
        this.databaseChecks = registry.counter("screening.database.checks");
12
    }
13

14
    boolean isSuspicious(String iban) {
15
        if (!filter.mightBeSuspicious(iban)) {
16
            return false;   // "definitely not": no database round trip
17
        }
18
        databaseChecks.increment();
19
        return repository.existsByIban(iban);   // "maybe": the database has the last word
20
    }
21
}

1
interface SuspiciousAccountRepository extends JpaRepository<SuspiciousAccount, Long> {
2

3
    boolean existsByIban(String iban);
4

5
    @Query("select a.iban from SuspiciousAccount a")
6
    Stream<String> streamAllIbans();
7
}

Kendini sına