Bloom Filter
Probabilistic data structure ที่เช็ค “ไม่มีแน่นอน” ได้เร็วมาก — ใช้ bit array ใน memory ลด IO ที่ไม่จำเป็น
ปัญหา
“username paul มีในระบบมั้ย?” → ทุก query ต้อง hit DB → ช้าถ้ามีเยอะ
วิธีทำงาน
- เก็บ bit array ใน memory (เช่น 1024 bits ทั้งหมดเป็น 0)
- INSERT username
jack:hash(jack)→ set bit ที่ตำแหน่งนั้นเป็น 1 - QUERY username:
- Bit = 0 → username ไม่มีแน่นอน (no false negative) → ไม่ต้อง query DB
- Bit = 1 → username อาจมี (false positive ได้) → ค่อยไป check DB
Properties สำคัญ
- No false negative — ถ้า bloom filter บอกว่า “ไม่มี” → ไม่มีจริง 100%
- False positive ได้ — ถ้าบอกว่า “อาจมี” → ต้อง verify กับ DB
- หลาย hash functions = false positive rate ต่ำลง
- ขนาด array ใหญ่ขึ้น = false positive rate ต่ำลง
- ลบไม่ได้ — ลบ bit ทำให้ key อื่นที่ hash ไปจุดเดียวกัน “หาย” (false negative)
ใช้กันแพร่หลายใน
| ระบบ | ใช้ทำอะไร |
|---|---|
| Cassandra | เช็คว่า key มีในแต่ละ SSTable มั้ย ก่อน read disk |
| Bitcoin | เช็ค transaction ใน block |
| Web crawler | เช็คว่า URL ครอลแล้วหรือยัง |
| PostgreSQL | ผ่าน extension bloom |
| LevelDB/RocksDB | เช็ค key ในแต่ละ level ก่อน read |
Key Points
- Bloom filter บอก “ไม่มีแน่นอน” ได้ — แต่ “อาจมี” ต้อง verify
- ใช้ bit array + hash functions ใน memory → เร็วมาก ไม่ต้อง IO
- ลบไม่ได้ — limitation หลัก
- ลด IO ที่ไม่จำเป็นได้มาก — Cassandra, Bitcoin, web crawler ใช้กันทั่วไป
Related
- Database Indexing — bloom filter ช่วยลด unnecessary index lookups
- Database Engines — LevelDB, RocksDB ใช้ bloom filter ทุก level
- Database Internals — ลด IO cost