Bloom Filter: เช็กชื่อผู้ใช้ซ้ำ 100 ล้านคนในเสี้ยววินาที โดยไม่แตะ Database ทำได้ยังไง?

คุณกำลังทำระบบสมัครสมาชิกให้แอปพลิเคชันระดับโลกที่มีผู้ใช้งานแล้วกว่า 100 ล้านคน...

โจทย์คือ: เมื่อผู้ใช้พิมพ์ชื่อ username ในช่องสมัคร ระบบจะต้องขึ้นเครื่องหมายถูก ✅ (ว่าง) หรือกากบาท ❌ (มีคนใช้แล้ว) ทันทีในระดับมิลลิวินาที!

ถ้าคุณวิ่งไป Query SELECT count(*) FROM users WHERE username = '...' ทุกครั้งที่ผู้ใช้พิมพ์ทีละตัวอักษร Database ของคุณจะโดนถล่มจนล่มสลายใน 5 นาที

"งั้นก็เอาชื่อทั้ง 100 ล้านคนไปเก็บไว้ใน Redis สิ!" ➔ แต่พอคำนวณดู ชื่อผู้ใช้ 100 ล้านคนอาจกิน RAM มหาศาลถึง 20-30 Gigabytes! ซึ่งแพงและสิ้นเปลืองมาก

คำถามคือ: มีวิธีไหนไหมที่สามารถจำรายชื่อคน 100 ล้านคนได้ โดยใช้ RAM ไม่ถึง 50 Megabytes และค้นหาได้เร็วกว่าสายฟ้าแลบ?

🪄 เวทมนตร์แห่งบิต: Bloom Filter

วิศวกรระดับโลก (รวมถึงระบบอย่าง Medium, YouTube, หรือ Chrome) ตัดสินใจใช้โครงสร้างข้อมูลเชิงความน่าจะเป็นที่ชื่อว่า Bloom Filter

หลักการของมันไม่ได้เก็บ "ตัวอักษร" ของชื่อผู้ใช้เลยแม้แต่ตัวเดียว! แต่มันทำงานแบบนี้:

1. สร้างกระดาษทดแผ่นยาวๆ ที่มีช่องตาราง 100 ล้านช่อง โดยตอนแรกทุกช่องเขียนเลข 0 ไว้ (Bit Array)
2. เตรียม Hash Functions ไว้สัก 3 ตัว (สมมติชื่อ H1, H2, H3)
3. เมื่อมีคนชื่อ "สมชาย" สมัครสมาชิก:
   • H1("สมชาย") ได้ช่องที่ 14 ➔ เปลี่ยนเป็น 1
   • H2("สมชาย") ได้ช่องที่ 55 ➔ เปลี่ยนเป็น 1
   • H3("สมชาย") ได้ช่องที่ 92 ➔ เปลี่ยนเป็น 1

จบ! ระบบจำ "สมชาย" ได้แล้วโดยใช้พื้นที่แค่ 3 บิต (Bits) ไม่ใช่ 30 ไบต์!

🕵️ วิธีตรวจสอบว่าชื่อว่างหรือไม่

วันต่อมา มีคนพิมพ์ชื่อ "สมหญิง" เข้ามาในระบบ Bloom Filter จะเอาคำว่า "สมหญิง" ไปเข้า Hash 3 ตัวเดิม:

• สมมติ Hash ออกมาได้ช่อง 14, 30, และ 88
• มันเดินไปดูช่อง 14 (เจอเลข 1) ➔ อืม น่าสงสัย...
• มันเดินไปดูช่อง 30 (เจอเลข 0) ➔ จบข่าว! ฟันธง 100% ว่าไม่เคยมีคนชื่อสมหญิงอยู่ในระบบแน่นอน! (เพราะถ้ามี ช่อง 30 ต้องเป็น 1 ไปแล้ว)

⚠️ จุดอ่อนเดียวที่ยอมรับได้: False Positive

ความมหัศจรรย์นี้แลกมาด้วยข้อเสีย 1 อย่าง คือ มันมีโอกาสทายผิด (False Positive)

สมมติมีคนพิมพ์ชื่อ "บ็อบ" ระบบเอาไป Hash แล้วดันบังเอิญไปตรงกับช่อง 14, 55, 92 ซึ่งเป็นช่องเดียวกับที่ "สมชาย" เคยเสกให้เป็น 1 ไว้พอดีเป๊ะ!

"Bloom Filter จะตะโกนบอกว่า 'มีคนชื่อบ็อบแล้ว!' ทั้งที่ความจริงยังไม่เคยมีใครชื่อบ็อบสมัครเลย... นี่คือ False Positive (เตือนภัยหลอก)"

แต่ช้าก่อน! กฎเหล็กของ Bloom Filter คือ: มันอาจจะบอกว่ามีของ ทั้งที่ไม่มีจริง (False Positive) ได้... แต่มันจะ "ไม่มีวัน" บอกว่าไม่มีของ ถ้าของชิ้นนั้นมีอยู่จริงเด็ดขาด (100% No False Negatives)!

🛡️ การประยุกต์ใช้: ด่านหน้าผู้พิทักษ์ Database

ในสถาปัตยกรรมจริง เราจะเอา Bloom Filter ไปวางขวางไว้หน้า Database:

ผลลัพธ์คือ: ทราฟฟิกกว่า 99% (คนที่พิมพ์ชื่อไม่ซ้ำ) จะถูกสกัดไว้ที่ Bloom Filter บน RAM เล็กๆ และมีเพียง 1% (คนที่พิมพ์ชื่อซ้ำ หรือระบบทายผิด) เท่านั้นที่หลุดรอดไปถึง Database!