Page cover

Data Structure 1: Bloom Filter

Struktur Data Bloom Filter: Pengertian, Cara Kerja, dan Implementasi dalam Go

Pendahuluan

Dalam pemrosesan data, seringkali kita perlu melakukan dua operasi penting:

  1. Membership Query: Memeriksa apakah suatu data d ada dalam kumpulan data S.

  2. Insertion: Menambahkan d ke S tanpa duplikasi.

Solusi naif menggunakan array atau hash table bisa tidak efisien karena membutuhkan memori besar. Bloom Filter hadir sebagai struktur data probabilitas yang menyeimbangkan penggunaan memori dan kecepatan, meski dengan toleransi false positive.

Konsep Dasar

1. Bit Array

Awalnya, data direpresentasikan dengan bit array. Misal, himpunan {0, 1, 4} direpresentasikan sebagai:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7  
-----------------------------  
1 | 1 | 0 | 0 | 1 | 0 | 0 | 0

Setiap data di-hash ke posisi bit tertentu. Namun, ukuran array harus sebesar jumlah data, sehingga tidak efisien.

2. Fungsi Hash

Untuk menghemat memori, digunakan fungsi hash h(x) yang memetakan data ke indeks dalam array yang lebih kecil. Misal, h(x) = x mod 8.

Masalah: Tabrakan (collision) terjadi ketika dua data berbeda di-hash ke indeks yang sama. Ini mengurangi akurasi dan memperlambat pencarian.

Bloom Filter: Solusi Probabilistik

Bloom Filter mengatasi masalah tabrakan dengan menggunakan beberapa fungsi hash sekaligus. Setiap data di-hash oleh k fungsi hash, dan setiap hasil hash menentukan posisi bit yang akan diset ke 1.

Contoh:

  • Data "hello" di-hash ke posisi 9, 4, 1.

  • Data "alice" di-hash ke posisi 8, 1, 2.

Bit array setelah penyisipan:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9  
--------------------------------------  
0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1

Pengecekan Keanggotaan:

  • Jika semua bit pada posisi hash suatu data bernilai 1, data mungkin ada di himpunan (bisa false positive).

  • Jika ada bit yang 0, data pasti tidak ada (no false negative).

Implementasi dalam Bahasa Go

1. Struktur Data

package main

import (
	"hash/fnv"
)

type BloomFilter struct {
	bits    []bool      // Array bit
	size    int         // Ukuran array
	hashes  int         // Jumlah fungsi hash (k)
}

func NewBloomFilter(size, k int) *BloomFilter {
	return &BloomFilter{
		bits:   make([]bool, size),
		size:   size,
		hashes: k,
	}
}

2. Fungsi Hash

Menggunakan kombinasi hash FNV-1a dengan indeks sebagai parameter:

func (bf *BloomFilter) getPosition(item string, i int) int {
	h := fnv.New64a()
	h.Write([]byte(item))
	h.Write([]byte{byte(i)}) // Tambahkan indeks sebagai salt
	sum := h.Sum64()
	return int(sum % uint64(bf.size))
}

3. Operasi Tambah dan Cek

// Add: Menambahkan data ke Bloom Filter
func (bf *BloomFilter) Add(item string) {
	for i := 0; i < bf.hashes; i++ {
		pos := bf.getPosition(item, i)
		bf.bits[pos] = true
	}
}

// Check: Memeriksa apakah data mungkin ada
func (bf *BloomFilter) Check(item string) bool {
	for i := 0; i < bf.hashes; i++ {
		pos := bf.getPosition(item, i)
		if !bf.bits[pos] {
			return false
		}
	}
	return true
}

4. Contoh Penggunaan

func main() {
	bf := NewBloomFilter(1000, 3)

	// Tambahkan data
	bf.Add("apple")
	bf.Add("banana")

	// Cek keberadaan
	println(bf.Check("apple"))  // true
	println(bf.Check("banana")) // true
	println(bf.Check("cherry")) // false (mungkin false positive)
}

Karakteristik Bloom Filter

  1. False Positive vs. False Negative

    • False Positive: Data tidak ada tapi dikatakan ada (bisa terjadi).

    • False Negative: Data ada tapi dikatakan tidak ada (tidak mungkin).

  2. Kompleksitas

    • Ruang: O(m), dengan m = ukuran bit array.

    • Waktu: O(k), dengan k = jumlah fungsi hash.

  3. Parameter Optimal Untuk meminimalkan false positive:

    • Ukuran array: m = -(n ln p)/(ln 2)^2

    • Jumlah hash: k = (m/n) ln 2 Dimana n = jumlah data, p = probabilitas false positive.

Aplikasi di Dunia Nyata

Use Case Real-World untuk Bloom Filter

1. Validasi Username yang Sudah Terdaftar

  • Masalah: Mengecek ketersediaan username secara real-time tanpa query database berulang.

  • Solusi:

    • Simpan semua username terdaftar dalam Bloom Filter.

    • Saat registrasi, cek Bloom Filter:

      • Jika false, username pasti belum terdaftar.

      • Jika true, lakukan pengecekan ulang ke database.

2. Pendeteksian URL Berbahaya

  • Masalah: Browser perlu memblokir URL phishing/malware dengan cepat.

  • Solusi:

    • Simpan daftar URL berbahaya di Bloom Filter.

    • Saat pengguna mengakses URL, cek Bloom Filter:

      • Jika true, tampilkan peringatan atau lakukan verifikasi lebih lanjut.

3. Cache Layer untuk Database

  • Masalah: Query database untuk data yang tidak ada menghabiskan sumber daya.

  • Solusi:

    • Simpan record yang sudah dihapus di Bloom Filter.

    • Sebelum query database, cek Bloom Filter:

      • Jika true, lewati query (data sudah dihapus).

Best Practice Implementasi

Aspek
Rekomendasi

Ukuran Array (m)

Gunakan rumus m = -(n * ln(p)) / (ln(2)^2) untuk meminimalkan false positive.

Jumlah Hash (k)

Optimal: k = (m/n) * ln(2). Mulai dengan 3-5 hash.

Penyimpanan

Simpan bit array di memory (Redis/Memcached) untuk akses cepat.

Persistence

Backup berkala ke disk/database.

Monitoring

Hitung false positive rate dan sesuaikan parameter.

Masih belum dapat intuisi nya? Saya akan coba terangkan sekali lagi ya🥰

Alur dan Simulasi Bloom Filter

1. Inisialisasi

Bloom Filter diinisialisasi dengan:

  • Bit Array: Array berisi 0 atau 1 (direpresentasikan sebagai []bool di Go).

  • Fungsi Hash: Sejumlah k fungsi hash independen.

  • Ukuran Array (m): Jumlah bit dalam array.

Contoh: Membuat Bloom Filter dengan:

  • Ukuran array (m) = 10

  • Jumlah fungsi hash (k) = 3

bloom := NewBloomFilter(10, 3)

Bit array awal:

[0] [0] [0] [0] [0] [0] [0] [0] [0] [0]

2. Menambahkan Data

Setiap data di-hash oleh k fungsi hash untuk mendapatkan k posisi bit. Bit pada posisi tersebut diubah ke 1.

Contoh: Tambahkan data "apple":

  1. Hash "apple" dengan 3 fungsi hash:

    • h1("apple") → Posisi 1

    • h2("apple") → Posisi 4

    • h3("apple") → Posisi 7

  2. Set bit di posisi 1, 4, dan 7 ke 1:

Bit array setelah ditambahkan "apple":

[0] [1] [0] [0] [1] [0] [0] [1] [0] [0]

Tambahkan data "banana":

  1. Hash "banana" dengan 3 fungsi hash:

    • h1("banana") → Posisi 3

    • h2("banana") → Posisi 4

    • h3("banana") → Posisi 9

  2. Set bit di posisi 3, 4, dan 9 ke 1:

Bit array setelah ditambahkan "banana":

[0] [1] [0] [1] [1] [0] [0] [1] [0] [1]

3. Pemeriksaan Keanggotaan

Untuk memeriksa apakah suatu data ada:

  1. Hash data dengan k fungsi hash.

  2. Jika semua bit di posisi hash bernilai 1 → data mungkin ada.

  3. Jika ada bit yang 0 → data pasti tidak ada.

Contoh: Periksa "apple":

  1. Hash "apple" → Posisi 1, 4, 7.

  2. Bit di posisi 1, 4, 7 = 1.

  3. Hasil: True (mungkin ada).

Periksa "cherry":

  1. Hash "cherry" → Posisi 0, 2, 5.

  2. Bit di posisi 0, 2, 5 = 0.

  3. Hasil: False (pasti tidak ada).

4. Simulasi False Positive

Kasus: Periksa "grape":

  1. Hash "grape" → Posisi 1, 3, 9 (misal).

  2. Bit di posisi 1, 3, 9 = 1 (karena di-set oleh "apple" dan "banana").

  3. Hasil: True (padahal "grape" tidak pernah ditambahkan → false positive).

Bit array saat ini:

[0] [1] [0] [1] [1] [0] [0] [1] [0] [1]

5. Ilustrasi Alur Lengkap

Ilustrasi

6. Parameter yang Mempengaruhi Akurasi

  1. Ukuran Array (m): Semakin besar m, semakin kecil kemungkinan false positive.

  2. Jumlah Fungsi Hash (k): Terlalu sedikit → collision meningkat. Terlalu banyak → bit array cepat penuh.

Rumus Optimal:

  • Ukuran array: ( m = -\frac{n \ln p}{(\ln 2)^2} )

  • Jumlah hash: ( k = \frac{m}{n} \ln 2 )

Di mana:

  • ( n ): Jumlah data yang akan disimpan.

  • ( p ): Toleransi probabilitas false positive.

Kesimpulan Simulasi

  • Bloom Filter tidak menyimpan data asli, hanya merepresentasikan keanggotaan data melalui bit array.

  • Tidak ada false negative: Jika hasilnya False, data pasti tidak ada.

  • Ada false positive: Jika hasilnya True, data mungkin ada atau tidak.

Contoh Koding Go

Berikut penjelasan implementasi Bloom Filter dalam skenario nyata, disertai contoh kode Go dan Docker Compose:

Implementasi di Go dengan Docker

1. Struktur Bloom Filter

// bloom_filter.go
package main

import (
	"encoding/gob"
	"fmt"
	"hash/fnv"
	"os"
	"sync"
)

type BloomFilter struct {
	bits     []bool
	size     int
	hashes   int
	mu       sync.RWMutex
}

func NewBloomFilter(size, hashes int) *BloomFilter {
	return &BloomFilter{
		bits:   make([]bool, size),
		size:   size,
		hashes: hashes,
	}
}

// Add: Menambahkan data ke filter
func (bf *BloomFilter) Add(data string) {
	bf.mu.Lock()
	defer bf.mu.Unlock()

	for i := 0; i < bf.hashes; i++ {
		pos := bf.hash(data, i) % bf.size
		bf.bits[pos] = true
	}
}

// Contains: Memeriksa keberadaan data
func (bf *BloomFilter) Contains(data string) bool {
	bf.mu.RLock()
	defer bf.mu.RUnlock()

	for i := 0; i < bf.hashes; i++ {
		pos := bf.hash(data, i) % bf.size
		if !bf.bits[pos] {
			return false
		}
	}
	return true
}

// Hash function dengan FNV + salt
func (bf *BloomFilter) hash(data string, salt int) int {
	h := fnv.New32a()
	h.Write([]byte(data))
	h.Write([]byte{byte(salt)})
	return int(h.Sum32())
}

// Save ke file
func (bf *BloomFilter) Save(path string) error {
	file, err := os.Create(path)
	if err != nil {
		return err
	}
	defer file.Close()

	encoder := gob.NewEncoder(file)
	return encoder.Encode(bf.bits)
}

// Load dari file
func (bf *BloomFilter) Load(path string) error {
	file, err := os.Open(path)
	if err != nil {
		return err
	}
	defer file.Close()

	decoder := gob.NewDecoder(file)
	return decoder.Decode(&bf.bits)
}

2. REST API dengan Gin

// main.go
package main

import (
	"net/http"
	
	"github.com/gin-gonic/gin"
)

var bloom *BloomFilter

func main() {
	// Inisialisasi Bloom Filter (1 juta elemen, 0.1% false positive)
	bloom = NewBloomFilter(9585059, 7) // m dan k dihitung dari rumus

	r := gin.Default()
	
	r.POST("/add", func(c *gin.Context) {
		data := c.Query("data")
		bloom.Add(data)
		c.Status(http.StatusOK)
	})
	
	r.GET("/check", func(c *gin.Context) {
		data := c.Query("data")
		exists := bloom.Contains(data)
		c.JSON(http.StatusOK, gin.H{"exists": exists})
	})
	
	r.Run(":8080")
}

3. Docker Compose

# Dockerfile
FROM golang:1.24-alpine

WORKDIR /app
COPY . .

RUN go mod tidy
RUN go build -o bloom-app .

CMD ["./bloom-app"]
# docker-compose.yml
version: '3.8'

services:
  bloom-api:
    build: .
    ports:
      - "8080:8080"
    volumes:
      - ./data:/app/data  # Untuk persistence
    restart: unless-stopped

Cara Menjalankan

  1. Build dan jalankan dengan Docker:

    docker-compose up --build

  2. Contoh penggunaan API:

    # Tambahkan data
curl -X POST http://localhost:8080/add?data=apple

# Cek data
curl http://localhost:8080/check?data=apple
# Output: {"exists": true}

curl http://localhost:8080/check?data=unknown
# Output: {"exists": false}

Optimasi untuk Production

  1. Gunakan Redis:

    // Ganti []bool dengan Redis BitArray
client.SetBit(ctx, "bloom_filter", offset, 1)

  2. Multiple Hash Libraries:

    // Gunakan hash farmhash atau murmur3 untuk performa
import "github.com/spaolacci/murmur3"

  3. Monitoring:

    • Hitung metrik:

      • bloom_false_positives_total

      • bloom_memory_usage_bytes

Implementasi ini cocok untuk sistem yang memprioritaskan kecepatan dan skalabilitas, seperti validasi real-time atau caching layer. Bloom Filter menjadi garda terdepan sebelum akses ke sumber daya yang lebih berat seperti database.

Kesimpulan

Bloom Filter menawarkan solusi efisien untuk masalah keanggotaan data dengan mengorbankan sedikit akurasi. Implementasinya yang sederhana dan penggunaan memori minimal membuatnya cocok untuk sistem yang memprioritaskan kecepatan dan skalabilitas. Namun, pengguna harus mempertimbangkan trade-off antara ukuran memori dan tingkat false positive.

Referensi:

https://loop-learn-share.netlify.app/data-structure/bloom_filter.html

PreviousTesting 1: Load and performance testingNextSystem Design 1: Back of The Envelope Estimation

Last updated