การกำหนดชื่อผู้ใช้ในหน้าลงทะเบียนผู้ใช้ เราจะทราบได้อย่างไรว่าชื่อนั้นได้รับการลงทะเบียนแล้ว?

แม้ว่าการสอบถามฐานข้อมูลที่จัดทำดัชนีจะช่วยได้ แต่ก็ช้าและมีการเรียกใช้เครือข่าย

เพื่อความรวดเร็ว เราสามารถแคชรายชื่อผู้ใช้ที่ลงทะเบียนไว้ในที่เก็บคีย์-ค่า เช่น Redis

อย่างไรก็ตาม นั่นหมายถึงการแคชข้อมูลนับล้านรายการและเพิ่มรอยเท้าหน่วยความจำของเราเป็นสองเท่า

เราจะทำอย่างไรให้ดีขึ้นในปัญหาที่ดูเหมือนเล็กน้อยนี้

ฟิลเตอร์บานอาจเป็นคำตอบ มาดูกัน!

Bloom Filter คืออะไร?

ฟิลเตอร์บลูมช่วยตอบคำถามง่ายๆ เพียงข้อเดียว

มีองค์ประกอบอยู่ในชุดที่กำหนดหรือไม่?

ตัวกรอง Bloom เป็นโครงสร้างข้อมูลที่น่าจะเป็น จากคำถามข้างต้น จะแสดงคำตอบอย่างใดอย่างหนึ่งต่อไปนี้

• น่าจะใช่
• 100%ไม่

และข้อได้เปรียบที่ใหญ่ที่สุดคือทำสิ่งนี้ในเวลาและสถานที่คงที่

มันทำงานอย่างไร?

ตัวกรองบานประกอบด้วยสองส่วน

• อาร์เรย์บิตขนาด N
• ฟังก์ชันแฮชหลายรายการ

เริ่มต้นครั้งแรกเป็นอาร์เรย์บิตขนาด N โดยบิตทั้งหมดตั้งค่าเป็นศูนย์ สมมติว่าความยาวของอาร์เรย์เป็น 10 ในตอนนี้

การเพิ่มรายการ

การเพิ่มรายการเป็นเรื่องเล็กน้อย

• รายการที่ระบุว่า "เสือ" ถูกแฮชโดยใช้ฟังก์ชันการแฮช
• แฮชที่สร้างขึ้นนั้นถูกดัดแปลงตามความยาวอาร์เรย์เพื่อรับดัชนีที่มีขอบเขต
• จากนั้นดัชนีของอาร์เรย์บิตจะถูกตั้งค่าเป็น 1

เช่นเดียวกับการเพิ่มรายการ เราแฮชองค์ประกอบโดยใช้ฟังก์ชันการแฮชและดัดแปลงเพื่อให้ได้ดัชนีที่มีขอบเขต

ผลลัพธ์ได้รับการประเมินดังนี้

• หากค่าดัชนีของอาร์เรย์บิตเป็น 0 แสดงว่ารายการนั้นไม่ ได้ อยู่ในชุด
• มิฉะนั้น รายการอาจจะอยู่ในชุด

การจัดเก็บตัวกรองบาน

แทนที่จะเก็บตัวกรอง Bloom เป็นอาร์เรย์ เราสามารถแปลงการแสดงบิตเป็นเลขฐานสิบได้

ตัวอย่างเช่น เราสามารถแปลงอาร์เรย์ที่มี1001119 เป็น 19 และเก็บไว้ในแคช

ถ้ารายการไม่เปลี่ยนแปลงบ่อยนัก เซิร์ฟเวอร์สามารถส่งเลขทศนิยมไปยังไคลเอนต์ได้ ทำให้การตรวจสอบทำได้ในฝั่งไคลเอ็นต์

เราทำได้ดีกว่านี้ไหม?

หากฟังก์ชันแฮชให้ผลลัพธ์เป็นดัชนี 1 สำหรับทั้ง "เสือ" และ "วัว" การตรวจสอบว่า "วัว" อยู่ในชุดนั้นหรือไม่ จะได้คำตอบว่า ใช่แม้ว่าจะไม่ใช่ก็ตาม

เราสามารถลดโอกาสเกิด False Positive ได้ด้วยวิธีต่อไปนี้

• เพิ่มความยาวของอาร์เรย์
• เพิ่มจำนวนของฟังก์ชันแฮช

แทนที่จะเป็นหนึ่งดัชนี เราสามารถรับได้หลายดัชนีโดยใช้แฮชหลายตัว

เมื่อเพิ่มรายการ ดัชนีที่ได้รับทั้งหมดจะถูกตั้งค่าเป็น 1

รายการถูกอ้างว่าอาจอยู่ในชุด เฉพาะในกรณีที่ดัชนีทั้งหมด ถูกตั้งค่าเป็น 1

การใช้ประโยชน์จากวิธีการเหล่านี้ เราสามารถลดความน่าจะเป็นของผลบวกปลอมได้อย่างมาก

แอพพลิเคชั่น

ลองมาดูตัวอย่างในชีวิตจริงกัน

ตรวจสอบว่ามีชื่อผู้ใช้อยู่ในขั้นตอนการลงชื่อสมัครใช้ของผู้ใช้หรือไม่

• เมื่อสร้างชื่อผู้ใช้ ชื่อผู้ใช้จะถูกเพิ่มไปยังตัวกรอง Bloom ที่จัดเก็บในที่เก็บคีย์-ค่า
• เมื่อผู้ใช้ป้อนชื่อผู้ใช้ในหน้าลงทะเบียนผู้ใช้ เซิร์ฟเวอร์จะค้นหาตัวกรอง Bloom ก่อน
• หากชื่อผู้ใช้ไม่ได้อยู่ในตัวกรอง Bloom เซิร์ฟเวอร์จะส่งคืนข้อผิดพลาดไปยังไคลเอนต์ทันที
• มิฉะนั้น เซิร์ฟเวอร์จะสอบถามและตรวจสอบข้ามฐานข้อมูล

• สื่อจะรักษาตัวกรองบานสำหรับผู้ใช้แต่ละคน
• ก่อนแนะนำบทความ สื่อจะตรวจสอบว่ามี ID บทความอยู่ในตัวกรอง Bloom ของผู้ใช้หรือไม่
• บทความที่ไม่อยู่ในตัวกรอง Bloom แนะนำให้ผู้ใช้

• เมื่อเข้าถึง URL ก่อนอื่น Chrome จะตรวจสอบว่า URL นั้นเป็นส่วนหนึ่งของรายการที่เป็นอันตรายหรือไม่
• แทนที่จะสอบถามเซิร์ฟเวอร์ Google ทุกครั้ง Google จะสร้างตัวกรอง Bloom โดยใช้รายการที่เป็นอันตรายที่กำหนดไว้ล่วงหน้าและส่งไปยังเบราว์เซอร์
• เบราว์เซอร์แฮช URL และตรวจสอบกับตัวกรอง Bloom ก่อนเข้าถึงเว็บไซต์

แม้ว่าอาจมีผลบวกปลอมแต่ตัวกรองการผลิดอกจะมีประโยชน์เมื่อเราต้องการบอกว่ารายการนั้น ไม่ได้ อยู่ในรายการอย่างแน่นอนหรือไม่

สามารถใช้เป็นตัวกรองชั้นแรกได้เนื่องจากมีประสิทธิภาพทั้งในด้านเวลาและพื้นที่

ฉันหวังว่าคุณจะพบว่าสิ่งนี้มีประโยชน์ แล้วพบกันใหม่ตอนหน้า!