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

 (llimllib.github.io)
2 คะแนน โดย GN⁺ 2025-07-01 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Bloom filter เป็นโครงสร้างข้อมูลที่ใช้หน่วยความจำน้อยเพื่อคัดกรองการมีอยู่ในเซตขนาดใหญ่ได้อย่างรวดเร็ว โดยแยกได้เพียงว่า “ไม่มีแน่นอน” กับ “อาจมีอยู่”
  • แกนสำคัญคือ bit vector และแฮชฟังก์ชันหลายตัว โดยเมื่อแทรกข้อมูลจะเปลี่ยนบิตในตำแหน่งที่ผลแฮชชี้ไปให้เป็น 1
  • ตอนตรวจสอบ ถ้าตำแหน่งเดิมมีบิตใดบิตหนึ่งเป็น 0 ก็สามารถตัดออกได้ แต่ถึงทุกบิตจะเป็น 1 ก็ยังมีโอกาสเกิด false positive อยู่
  • แฮชฟังก์ชันควรเป็นอิสระต่อกัน กระจายตัวใกล้เคียงสม่ำเสมอ และต้องเร็ว โดยมีกรณีศึกษาที่เปลี่ยนจาก md5 เป็น murmur แล้วได้ความเร็วเพิ่มขึ้นประมาณ 800%
  • ความแม่นยำและต้นทุนของฟิลเตอร์ขึ้นอยู่กับสมดุลของจำนวนสมาชิกที่คาดไว้ n, จำนวนบิต m, และจำนวนแฮช k โดยทั้งการแทรกและการตรวจสอบอยู่ที่ระดับ O(k)

วิธีการทำงานของ Bloom filter

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

การตรวจสอบการมีอยู่และ false positive

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

เกณฑ์การเลือกแฮชฟังก์ชัน

  • แฮชฟังก์ชันสำหรับ Bloom filter ควร เป็นอิสระต่อกัน และ กระจายตัวใกล้เคียงสม่ำเสมอ พร้อมทั้งต้องเร็วที่สุดเท่าที่เป็นไปได้
  • แฮชเชิงเข้ารหัสอย่าง sha1 แม้จะใช้กันแพร่หลาย แต่ก็อาจไม่ใช่ตัวเลือกที่ดีเสมอไปสำหรับ Bloom filter
  • ตัวอย่างแฮชที่เร็วและเรียบง่ายมีดังนี้
  • มีกรณีที่เปลี่ยนการติดตั้งใช้งาน Bloom filter จาก md5 เป็น murmur แล้วได้ความเร็วเพิ่มขึ้นประมาณ 800%

แฮชที่ใช้ในงานติดตั้งใช้งานจริง

  • อิมพลีเมนเทชันหลายตัวใช้แฮชฟังก์ชันต่างกันสำหรับ Bloom filter
    • Chromium: ใช้ murmur
    • Plan9: ใช้แฮชแบบง่ายที่เสนอไว้ใน Mitzenmacher 2005
    • Sdroege Bloom filter: ใช้ fnv1a
    • Squid: ใช้ MD5
    • RedisBloom: ใช้ murmur
    • Apache Spark: ใช้ murmur
    • influxdb: ใช้ xxhash
    • bloomd: สองแฮชแรกใช้ murmur, สองแฮชถัดไปใช้ SpookyHash และหลังจากนั้นใช้การผสมของทั้งสองแบบ
    • fleur, flor, bloom: ใช้ fnv
    • Sqlite: เพิ่ม Bloom filter สำหรับ analytical query
    • RocksDB: ตั้งค่าได้ และในซอร์สระบุว่า xxh3 ในตระกูล xxhash ให้ผลดีที่สุด
    • ScyllaDB: ใช้ murmur

การกำหนดขนาดฟิลเตอร์และจำนวนแฮชฟังก์ชัน

  • Bloom filter สามารถปรับ อัตรา false positive ได้
    • ฟิลเตอร์ที่ใหญ่ขึ้นจะลด false positive
    • ฟิลเตอร์ที่เล็กลงจะเพิ่ม false positive
  • อัตรา false positive คำนวณโดยประมาณได้จาก (1-e^-kn/m)^k
    • n: จำนวนองค์ประกอบที่คาดว่าจะถูกแทรก
    • m: จำนวนบิตของฟิลเตอร์
    • k: จำนวนแฮชฟังก์ชัน
  • ยิ่งมีแฮชฟังก์ชันมาก การตรวจสอบและการแทรกก็ยิ่งช้าลง และฟิลเตอร์ก็เต็มเร็วขึ้นด้วย
  • ในทางกลับกัน ถ้ามีแฮชฟังก์ชันน้อยเกินไป ก็อาจทำให้ false positive มากเกินไป
  • เมื่อกำหนด m และ n แล้ว ค่า k ที่เหมาะสมที่สุดเลือกได้ด้วย (m/n)ln(2)
  • การกำหนดขนาดฟิลเตอร์ทำได้ตามลำดับนี้
    • กำหนดค่า n ที่คาดไว้แบบคร่าว ๆ
    • เลือกค่า m
    • คำนวณค่า k ที่เหมาะสมที่สุด
    • คำนวณอัตราความผิดพลาดจาก n, m, k ที่เลือก
    • ถ้ายอมรับอัตราความผิดพลาดนี้ไม่ได้ ให้เปลี่ยน m แล้วคำนวณใหม่

ประสิทธิภาพและเงื่อนไขการใช้งานที่เหมาะสม

  • ใน Bloom filter ที่มี m บิตและแฮชฟังก์ชัน k ตัว ทั้งการแทรกและการตรวจสอบการมีอยู่ล้วนเป็น O(k)
  • เวลาเพิ่มองค์ประกอบหรือตรวจสอบ ก็เพียงนำองค์ประกอบผ่านแฮชฟังก์ชัน k ตัว แล้วตั้งค่าหรือตรวจสอบบิตที่เกี่ยวข้อง
  • ประสิทธิภาพเชิงพื้นที่ขึ้นอยู่กับอัตราความผิดพลาดที่ยอมรับได้
  • ถ้าช่วงขององค์ประกอบที่แทรกได้มีข้อจำกัดมาก การใช้ bit vector แบบกำหนดแน่นอนอาจดีกว่า
  • ถ้าไม่สามารถประมาณจำนวนองค์ประกอบที่จะถูกแทรกได้เลย แม้เพียงคร่าว ๆ hash table หรือ scalable Bloom filter อาจเหมาะสมกว่า

เอกสารอ้างอิงและตัวอย่างการใช้งาน

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-07-01
ความคิดเห็นจาก Hacker News

  • บทความนี้เขียนมาโดนคนอย่างผมพอดี เคยได้ยินชื่อ Bloom filter และทุกครั้งที่มีคนพูดถึงก็คิดว่าจะไปค้นดูสักที พออ่านบทความนี้แล้วในที่สุดก็ได้ค้นจริง ๆ และมันเป็นบทนำที่ตรงตามที่ผมต้องการอย่างสมบูรณ์แบบ :)

    • ผมรู้จัก Bloom filter เมื่อกว่า 10 ปีก่อน ตอนถูกมอบหมายให้ไปทำสำหรับ ฟีเจอร์ค้นหาของ iBooks
    • เป็นโครงสร้างที่สนุกมาก ถ้าเจอปัญหาที่ต้องใช้ Bloom filter จะตื่นเต้นเลย แต่น่าเสียดายที่แล้วแต่สายงาน กรณีแบบนั้นอาจพบได้ไม่บ่อย

  • ปี 2009 ผมทำ Bloom filter ด้วย CUDA ตอนอยู่มหาวิทยาลัย และอาจารย์ที่ปรึกษาเคยอยู่ Nvidia มาก่อน แต่หลังจากนั้นในเส้นทางอาชีพกลับไม่ได้เขียนโปรแกรม GPU เลย
    ถ้าตอนนั้นเลือกอีกทาง อาจทำเงินได้ 100 ล้านดอลลาร์ ก็ได้

    • ผมก็คล้ายกัน ปี 2009 ลองใช้ CUDA v1 บน GeForce 8 ด้วยความอยากรู้ และน่าจะทำหนึ่งในรูปแบบแรก ๆ ของชุดเครื่องมือชีวสารสนเทศที่ปรับแต่งให้เหมาะกับ GPU
      แล้วก็ไปทำอย่างอื่น พลาดเงินก้อนใหญ่ไป
    • ถ้าคิดว่านี่เป็นไอเดียวิทยาการคอมพิวเตอร์ตั้งแต่ปี 1970 ก็ดูไม่น่าจะเป็นไปได้มากนัก ไอเดียที่น่าลองบน GPU อเนกประสงค์คงมีคนเล็งกันหมดแล้ว
      10 ปีก่อนผมเคยทำ hashcash implementation บน GPU แต่ตอนนี้คงแทบไม่มีค่าอะไรแล้ว
    • ผมเคยพอร์ตอัลกอริทึมแมชชีนเลิร์นนิงไปเป็น CUDA สำหรับโปรเจกต์เกียรตินิยมปริญญาตรี จากนั้นก็แค่ยักไหล่แล้วไปเขียนโปรแกรมฝังตัว
    • ถ้าซื้อ Bitcoin ก็คงทำเงินได้มากกว่านั้นเยอะ

  • ฝากโน้ตถึงผู้เขียน: ส่วนอินเทอร์แอคทีฟ ดีมาก ถ้าอยากให้เห็นแก่นชัดขึ้น น่าจะให้ตัวอย่างสตริงสองตัวที่เกิด hash collision กัน โดยให้ใส่ตัวหนึ่งในช่องอินพุตแรก แล้วให้นำอีกตัวไปตรวจในช่องที่สอง
    แบบนั้นจะช่วยแสดงว่าทำไมคำตอบถึงเป็น “อาจอยู่ ในเซ็ต” เสมอ ไม่ใช่ “อยู่”

    • "bloom" กับ "demonstrators " ชนกัน ระวังอักขระช่องว่างท้ายสตริงตัวหลังด้วย
      ทั้งคู่ชนกันที่ fnv: 7, murmur: 12

  • ผมมีทริกหนึ่งที่ชอบ ถ้าบางครั้งต้องตรวจ membership จำนวนมากในเซ็ตที่อาจมีขนาดเล็ก ก็สามารถใส่ Bloom filter 64 บิต แบบเก็งไว้ก่อนพร้อมฟังก์ชันแฮชที่ง่ายมาก ๆ ได้
    ฟังดูโง่มาก แต่ต้นทุนต่ำจนคุ้มจะลองเสี่ยง ถ้าไม่เวิร์กก็เพิ่มเวลาราว 10ns ต่อการ insert และ membership check แต่ถ้าเวิร์กจะลดงานได้มหาศาล

    • Chromium ก็ทำแบบนี้หลายที่ ในบทความลิงก์เฉพาะตัวอย่าง Safe Browsing ที่ใช้ murmur แต่ Blink ซึ่งเป็น renderer มักใช้ rapidhash และใช้ไมโครฟิลเตอร์แบบนี้ในหลายจุด
      ตัวอย่างเช่น querySelector() ในบางกรณี, การกรองล่วงหน้าก่อน lookup hash ในบัคเก็ต CSS, และการปฏิเสธ element อย่างรวดเร็วเวลามองหาแอตทริบิวต์ Aria บางตัวเพื่อ accessibility น่าแปลกที่ฟิลเตอร์เล็กมากขนาด 32 บิตหรือ 64 บิตยังใช้งานได้ แต่ในทางปฏิบัติมักได้ผลอยู่บ่อย ๆ นอกจากนี้ยังมี Bloom filter ที่ใหญ่กว่านี้บางส่วนด้วย หลายอันในนี้ผมเป็นคนเพิ่มเอง

  • ผมขอให้ ChatGPT ทำตัวหนึ่งด้วย Python โดยใช้วิธี ตัด md5 digest พื้นฐานออกมาใช้เหมือนเป็นหลาย ๆ hash ถ้าเป็นงานที่ไม่สำคัญมากก็น่าจะโอเค

  • มี visualization อีกแบบของ Bloom filter ดูได้ท้ายหน้านี้:
    https://www.chrislaux.com/hashtable.html

  • ผมคิดว่าเคยเห็นมาก่อน แต่จริง ๆ แล้วเป็นอีกหน้านี้: https://bdupras.github.io/filter-tutorial/
    หน้านี้มีข้อมูลเพิ่มอีกนิด เพราะเปรียบเทียบ Bloom filter กับ cuckoo filter

  • เมื่อไม่นานมานี้ผมใช้ Bloom filter ทำฟีเจอร์ ป้องกันสแปมข้อความล็อก ใน logger จะ hash ข้อความแล้วใส่เข้า filter และถ้ามีรายการอยู่แล้วก็จะไม่พิมพ์ข้อความออกมา
    ทุก ๆ ไม่กี่วินาทีจะวนผ่าน filter แล้วล้างบิตทั้งหมด ซึ่งเหมาะดีเพราะไม่ต้องกังวลเรื่องการล้างบิตทั้งหมดของ filter แบบ atomic ถ้ามีข้อความเข้ามาระหว่างนั้น แค่บิตบางส่วนถูกล้างก็เพียงพอให้ข้อความนั้นกลับมาออกล็อกอีกครั้ง implementation เดิมนับจำนวนข้อความที่เคยเห็นแล้วอิ่มตัวที่ N ทำให้เมื่อมีข้อความบางอันถูกพิมพ์ซ้ำ ๆ มันจะโผล่ให้เห็นได้แค่ตามอัตราที่ filter ถูกล้าง
    ค่อนข้างน่าพอใจที่จากแค่รู้จัก Bloom filter เฉย ๆ แล้วมันได้พบ use case จริงอย่างเป็นธรรมชาติ และสร้างการปรับปรุงได้มาก

  • ถ้าอยากอ่านต่อ บทความเรื่อง Bloom filter ของ Eli Bendersky ก็ดีเหมือนกัน:
    https://eli.thegreenplace.net/2025/bloom-filters/

  • แนวคิดที่ต้องใช้เพื่อเข้าใจ Bloom filter, เซ็ต และ hash table นั้นโดยความรู้สึกแล้วทับซ้อนกันประมาณ 95% เซ็ตคือ hash table สำหรับ membership check ที่สนใจเฉพาะ key ไม่ใช่ value และ Bloom filter ก็คือเซ็ตที่ใช้ข้อเท็จจริงว่า hashing แบบ many-to-one “บีบอัด” key space ผ่าน collision
    พูดได้ว่าเป็นการตั้งใจใช้ฟังก์ชันแฮชที่ชนกันเยอะ ถ้า key ใดเคยถูก hash แล้วจะต้องได้ผลว่าใช่แน่นอน แต่อาจมี key อื่นที่สร้าง hash เดียวกันอยู่ด้วย นี่ไม่ใช่บั๊ก แต่เป็นฟีเจอร์

    • ดีใจที่ไม่ได้มีแค่ผมที่เข้าใจ Bloom filter ว่าเป็น hash table ที่ไม่ติดตามข้อมูลจริง แต่ติดตามเฉพาะบัคเก็ตที่มีข้อมูล
    • สิ่งสำคัญที่คำอธิบายนี้ขาดไปคือ Bloom filter ใช้ ฟังก์ชันแฮชหลายตัว เพื่อลด collision เช่น ถ้ามี 3 hash การจะตัดสินว่า key หนึ่งอยู่ในเซ็ตได้ hash ทั้งสามตัวต้องตรงทั้งหมด
      วิธีนี้ลดโอกาส false positive collision ขณะยังคงรับประกันว่าไม่มี false negative
    • ถ้าเข้าใจ Bloom filter อย่างถูกต้องแล้ว ก็แทบจะไปถึงจุดที่เข้าใจ random projection และ implementation บางส่วนของ locality-sensitive hashing ได้แล้ว