ทำความเข้าใจ Bloom Filter ผ่านตัวอย่าง

• Bloom Filter คือ โครงสร้างข้อมูลเชิงความน่าจะเป็น ที่ช่วยตรวจสอบได้อย่างรวดเร็วและประหยัดหน่วยความจำว่าองค์ประกอบอยู่ในเซตหรือไม่
• มันบอกได้เพียงว่าองค์ประกอบนั้น ไม่มีอยู่แน่นอน หรืออาจมีอยู่ก็ได้ และมีความเป็นไปได้ที่จะเกิด false positive
• โครงสร้างพื้นฐานใช้ bit vector และ hash function หลายตัวเพื่อตั้งค่าบิตของแต่ละองค์ประกอบเป็น 1
• อัตราความคลาดเคลื่อนและประสิทธิภาพ จะขึ้นอยู่กับขนาดของฟิลเตอร์และจำนวน hash function ซึ่งสามารถปรับให้เหมาะกับการใช้งานได้
• ยังแนะนำ hash function ที่เหมาะสมและ วิธีตั้งค่าที่เหมาะสมที่สุด รวมถึงประสิทธิภาพด้านพื้นที่และกรณีการใช้งานจริง

---

Bloom Filter คืออะไร

• Bloom Filter เป็นโครงสร้างข้อมูลที่ใช้ ตรวจสอบได้อย่างรวดเร็วและประหยัดหน่วยความจำ ว่าองค์ประกอบหนึ่ง ๆ มีอยู่ในเซตหรือไม่
• เพื่อให้ได้ประสิทธิภาพนี้ Bloom Filter จึงเป็นโครงสร้างข้อมูลเชิงความน่าจะเป็น โดยผลการตรวจสอบจะแบ่งเป็น "ไม่มีอยู่ในเซตแน่นอน" หรือ "อาจมีอยู่ในเซต"
• โครงสร้างหลักของ Bloom Filter คือ bit vector
• เมื่อเพิ่มองค์ประกอบเข้าไป จะนำแต่ละองค์ประกอบไป hash หลายครั้ง แล้วตั้งค่าบิตของดัชนีนั้นเป็น 1
• หากบิตที่ตรงกับดัชนีจาก hash function แต่ละตัวเป็น 1 ทั้งหมด จะตัดสินว่า "อาจมีอยู่" แต่ถ้าไม่ใช่จะถือว่า "ไม่มีอยู่แน่นอน"

ตัวอย่างหลักการทำงาน

• ใช้ hash function หลายตัว (เช่น Fnv, Murmur) เพื่อแมปองค์ประกอบไปยังดัชนีบิตหลายตำแหน่ง
• เมื่อเพิ่มองค์ประกอบเข้าไป จะเปลี่ยนบิตของดัชนีที่คำนวณได้ให้เป็น 1
• เมื่อตรวจสอบว่ามีองค์ประกอบใดอยู่หรือไม่ หากดัชนีที่ได้จาก hash function ชุดเดิมและวิธีเดียวกันเป็น 1 ทั้งหมด ก็จะถือว่า "อาจมีอยู่"
• หากมีบิตใดบิตหนึ่งเป็น 0 ก็สามารถตัดสินได้อย่างแน่นอนว่า "ไม่มีอยู่ในเซต"
• ด้วยเหตุนี้จึงเกิดความเป็นไปได้ของ false positive

หัวข้อขั้นสูง

ข้อควรระวัง: ผู้เขียนไม่มีประสบการณ์ในการนำ Bloom Filter ไปใช้กับบริการขนาดใหญ่จริง

การเลือก hash function

• แนะนำให้ใช้ hash function ที่ เป็นอิสระต่อกัน และมี การกระจายตัวสม่ำเสมอ
• hash function เชิงเข้ารหัส (เช่น sha1) ไม่เหมาะ เพราะทำงานช้า
• ตัวอย่างของ hash function ที่เร็วและเรียบง่าย ได้แก่ Murmur, xxHash, Fnv, HashMix เป็นต้น
• ในกรณีใช้งานจริง มีประสบการณ์ว่าสามารถเพิ่มความเร็วได้มากกว่า 800% เมื่อลองเปลี่ยนจาก md5 เป็น murmur

การกำหนดขนาดของ Bloom Filter

• ขนาดฟิลเตอร์ (m) ยิ่งใหญ่ อัตรา false positive ก็ยิ่งลดลง
• โดยทั่วไปอัตรา false positive สามารถประมาณได้ด้วย (1-e^(-kn/m))^k
• ต้องกำหนดจำนวนองค์ประกอบที่คาดหวัง (n), ขนาดฟิลเตอร์ (m), และจำนวน hash function (k) ให้เหมาะสม

จำนวน hash function ควรมีเท่าไร?

• ยิ่งมี hash function มาก ความเร็วก็ยิ่งลดลง และฟิลเตอร์ก็เต็มเร็วขึ้น
• ถ้าน้อยเกินไป อัตรา false positive จะสูงขึ้น
• ค่า k ที่เหมาะสมที่สุดคำนวณได้จาก (m/n)ln(2)
• ในการออกแบบให้ทำตามขั้นตอนต่อไปนี้:
  • ประมาณจำนวนองค์ประกอบที่คาดหวัง n
  • กำหนดจำนวนบิต m
  • คำนวณค่า k ที่เหมาะสมที่สุด
  • ตรวจสอบว่าได้อัตราความคลาดเคลื่อนตามต้องการหรือไม่ ถ้าไม่ได้ให้ปรับ m

ประสิทธิภาพและประสิทธิผลด้านพื้นที่

• ใน Bloom Filter การ เพิ่มองค์ประกอบ/ตรวจสอบการมีอยู่ มีความซับซ้อนเชิงเวลา O(k)
• ประสิทธิภาพด้านพื้นที่ขึ้นอยู่กับขอบเขตความคลาดเคลื่อนที่ยอมรับได้และช่วงขององค์ประกอบ
• หากไม่สามารถคาดการณ์ช่วงขององค์ประกอบได้แม้เพียงคร่าว ๆ hash table หรือ Scalable Bloom Filter อาจเหมาะกว่า

กรณีการใช้งาน

• ตัวอย่างการใช้งานแบบละเอียดดูได้ที่ Wikipedia
• C. Titus Brown นำเสนอ กรณีการประยุกต์ใช้ Bloom Filter ในชีวสารสนเทศศาสตร์

เอกสารอ้างอิง

• Broder, Mitzenmacher : Network Applications of Bloom Filters: A Survey — เป็นบทความภาพรวมเกี่ยวกับ Bloom Filter
• Wikipedia – Bloom Filter
• Kirsch, Mitzenmacher: Less Hashing, Same Performance
• Almeida และคณะ: Scalable Bloom Filters

[GN⁺]

ความคิดเห็นบน Hacker News

• รู้สึกว่าบทความนี้เหมาะกับคนแบบผมมาก ได้ยินชื่อมานานแต่ทุกทีก็คิดว่าจะค่อยไปหาอ่านแล้วก็ผัดวันมาตลอด พอได้อ่านครั้งนี้ก็เลยไปดูจริงจังเสียที และมันให้ความรู้สึกเหมือนบทนำที่ผมต้องการพอดี
  • ผมรู้จัก Bloom filter ครั้งแรกตอนทำฟีเจอร์ค้นหาให้ iBooks นี่ก็เกิน 10 ปีมาแล้ว
  • Bloom filter สนุกมาก เวลาทำโจทย์แล้วมีจังหวะที่ต้องใช้ Bloom filter จะตื่นเต้นสุดๆ แต่น่าเสียดายที่แล้วแต่โดเมนจึงไม่ได้มีโอกาสแบบนั้นบ่อย
• มีข้อเสนอแนะอย่างหนึ่งถึงผู้เขียน ส่วนที่เป็นอินเทอร์แอกทีฟดีมากอยู่แล้ว ถ้าอยากให้เข้าใจคุณสมบัติของ Bloom filter มากขึ้น น่าจะยกตัวอย่างสตริงสองตัวที่ทำให้เกิด hash collision แล้วให้ลองพิมพ์ตัวหนึ่ง จากนั้นพิมพ์อีกตัวในช่องที่สอง แบบนี้จะช่วยให้เข้าใจได้ง่ายว่าทำไมผลลัพธ์แบบเฉพาะตัวอย่าง "ไม่แน่ชัดว่าอยู่ในเซต แต่ก็น่าจะมี (maybe)" ถึงเกิดขึ้น
  • ตัวอย่างเช่น "bloom" กับ "demonstrators " (มีช่องว่างท้ายคำ) ชนกันที่ fnv: 7, murmur: 12
• สมัยเรียนมหาวิทยาลัยในปี 2009 เคยทำ Bloom filter ด้วย CUDA อาจารย์ที่ปรึกษาเคยทำงานที่ Nvidia มาก่อน แต่สุดท้ายเส้นทางอาชีพกลับไปคนละทางกับ GPU programming โดยสิ้นเชิง บางทีก็คิดว่าถ้าเลือกอีกแบบอาจทำเงินได้ 100 ล้านดอลลาร์ก็ได้
  • แต่พอมาคิดว่าเป็นไอเดียวิทยาการคอมพิวเตอร์ตั้งแต่ปี 1970 ก็คงเป็นไปไม่ได้ แนวคิดที่เกี่ยวกับ GPGPU ก็ดูเหมือนถูกศึกษาไปมากแล้ว ผมเองก็เคยทำ Hashcash บน GPU เมื่อ 10 ปีก่อน แต่ตอนนี้มองแล้วแทบไม่มีมูลค่าเลย
  • หลังจากพอร์ตอัลกอริทึมแมชชีนเลิร์นนิงไปเป็น CUDA สำหรับโปรเจ็กต์จบ ก็รู้สึกว่ามันไม่ได้พิเศษอะไร แล้วก็เปลี่ยนสายไปทำ embedded programming
  • ผมก็คล้ายๆ กัน ปี 2009 น่าจะเป็นคนแรกๆ ที่ทำชุดเครื่องมือ bioinformatics ที่ optimize สำหรับ GPU บน GeForce 8 กับ CUDA v1(!) ทำเพราะความอยากรู้อยากเห็นล้วนๆ แล้วหลังจากนั้นก็ไปอีกเส้นทางหนึ่งเลย เลยพลาดโอกาสทำเงินก้อนโต
  • มีมุกปนจริงจังว่าถ้าตอนนั้นซื้อ Bitcoin คงได้เงินมากกว่านี้อีก
• มีทริกที่ผมชอบอยู่แบบหนึ่ง สำหรับ set ขนาดเล็กที่จำนวนสมาชิกอาจน้อยและมีการเช็ก membership บ่อย ผมจะยัด 64-bit Bloom filter เข้าไปพร้อมกับ hash function ง่ายๆ มันดูงี่เง่าแต่ต้นทุนต่ำมากจนลองใช้แบบเสี่ยงดวงได้เลย ถ้าไม่เวิร์กก็แค่เพิ่มเวลาราว 10ns ตอนเช็ก membership หรือ insert แต่ถ้าเวิร์กขึ้นมาจะลดงานไปได้มหาศาล
  • Chromium ก็ใช้ทริกแบบนี้อยู่หลายจุด ในบทความพูดถึงแค่ Safe Browsing แต่ในเลเยอร์ Blink ใช้ rapidhash กับไมโครฟิลเตอร์แบบนี้หนักมาก เช่น querySelector(), prefilter สำหรับ hash lookup ใน CSS bucket, และการ reject อย่างรวดเร็วตอนค้นหา attribute ของ Aria เพื่อเรื่อง accessibility ฟิลเตอร์เล็กๆ แบบ 32-bit, 64-bit ก็ใช้งานได้ดีจริง ฟิลเตอร์ Bloom ที่ใหญ่กว่านี้ก็ถูกใช้ตามความเหมาะสม และผมเองก็เคยเพิ่มฟีเจอร์พวกนี้โดยตรงด้วย
• เพิ่งมีประสบการณ์ใช้ Bloom filter กับฟีเจอร์ป้องกันสแปมของข้อความล็อก โดยแฮชข้อความล็อกแล้วใส่ลงใน filter ถ้ามีอยู่ใน filter แล้วก็จะไม่พิมพ์ออกมา และจะล้างบิตทั้งหมดของ filter เป็นระยะๆ โดยไม่จำเป็นต้องล้างทั้งก้อนแบบ atomic ต่อให้มีบางบิตถูกลบระหว่างที่ข้อความกำลังเข้ามา ก็แค่ทำให้ข้อความนั้นถูกล็อกอีกครั้ง ก่อนหน้านี้ผมเก็บตัวนับแยกตามข้อความ แต่แบบนี้มีประสิทธิภาพกว่ามาก เป็นเคสที่ได้ใช้ Bloom filter จริงๆ แล้วพอใจมาก
• ถ้าต้องการตัวอย่างการทำภาพประกอบ Bloom filter มีข้อมูลดีๆ อยู่ช่วงท้ายของหน้านี้
• ขอแนะนำบทความแนะนำ Bloom filter อีกชิ้นของ Eli Bendersky ถ้าอยากรู้ละเอียดขึ้น ดูได้ที่นี่
• ผมคิดว่าแนวคิดที่ต้องใช้ในการเข้าใจ Bloom filter, set และ hash table นั้นซ้อนทับกันเกือบ 95% set ก็คือ hash table ที่สนใจเฉพาะ key ส่วน Bloom filter คือ set ที่ใช้คุณสมบัติเรื่อง collision ของการแฮชอย่างจงใจ ใช้ hash function ที่ออกแบบให้เกิด collision ได้ง่าย ถ้า key ใดเคยถูกใส่เข้ามาแล้วก็จะตรงแน่นอน แต่ก็อาจมี key อื่นที่ให้ค่า hash เดียวกันได้ นี่จึงไม่ใช่บั๊ก แต่เป็นคุณสมบัติที่ตั้งใจไว้
  • ผมเองก็มอง Bloom filter ว่าเหมือน hash table ที่เอาข้อมูลจริงออกไปแล้วติดตามเฉพาะ bucket ดีใจที่ไม่ได้มีแค่ผมคนเดียวที่มีมุมมองแบบนี้
  • น่าจะเสริมอีกหน่อยว่าที่ Bloom filter ลด collision ได้เพราะใช้ hash function หลายตัว เช่น ถ้า hash function ทั้ง 3 ตัวตรงหมดจึงจะถือว่าอยู่ใน set โครงสร้างแบบนี้ทำให้ลดโอกาส false positive ได้ ขณะที่ false negative จะไม่เกิดขึ้นเลย
  • ถ้าเข้าใจ Bloom filter แล้ว ก็มีแนวโน้มว่าจะเข้าใจ random projection หรือ implementation บางแบบของ Locality Sensitive Hashes ได้ต่อทันที
• เคยจมลึกกับ Bloom filter ตอนดีบักปัญหา read spike ของ Cassandra รู้สึกแปลกที่มีการ lookup sstable เยอะมากทั้งที่เป็น key ที่ไม่มีอยู่จริง กว่าจะเข้าใจความหมายของ Bloom filter ที่ติดอยู่กับแต่ละ sstable ก็ใช้เวลาอยู่พักหนึ่ง ค่า false positive เริ่มต้นที่ 0.1 สูงเกินไปสำหรับเคสของเรา เพราะส่วนใหญ่เป็น cache miss และ false positive ทำให้เกิดการ lookup ไร้ประโยชน์จำนวนมาก พอลดอัตราลงเป็น 0.01 การใช้หน่วยความจำเพิ่มขึ้นเพียงเล็กน้อย แต่ลด read ที่ไม่จำเป็นลงได้มาก จน p99 read latency ลดลงถึง 16~18%
• ผมชอบ Bloom filter มาก เวลาเล่าเรื่องเทคนิคมักจะย้ำอยู่ 3 แนวคิดหลักเสมอ คือ Bloom filter, Random Weight Hashing (Rendezvous Hashing, Highest Random Weight Hashing) และ Cumulative flow diagram ผมมองว่าสามอย่างนี้จำเป็นมากสำหรับการดูแลระบบ distributed system ที่ซับซ้อน
  • ผมว่าหัวข้อโครงสร้าง distributed hash table ก็สำคัญไม่แพ้กัน เช่น circle, chord, CAN, kademlia และสถาปัตยกรรมอื่นๆ