Neng Liangpornrattana
Aug 13 · 5 min read

วันก่อนดู talk เกี่ยวกับ data algorithm แล้วเจอว่ามันมีสิ่งที่ทำอะไรได้เหมือนกับ Bloom filter ได้ แต่สามารถลบของที่อยู่ใน data ที่เราเอามา filter ได้
หากยังไม่รู้จัก Bloom filter สามารถจิ้มไปอ่านที่ผมเขียนเอาไว้ก่อนได้

ซึ่งหลักๆ ทั้ง Bloom filter และ Cuckoo filter มีเอาไว้แก้ปัญหาในการเช็คว่ามีข้อมูลหรือสิ่งที่เรากำลังพิจารณาอยู่ในกลุ่มของข้อมูลหรือเปล่า เช่น IP นี้ เคยมาเยี่ยมชมเว็บไซต์เราหรือยัง

ในปริมาณข้อมูลที่ใหญ่ขึ้นเรื่อยๆ แล้วเราจะไปเช็คในฐานข้อมูลที่เราเก็บไว้ อาจจะใช้เวลานานในการค้นหา เราอาจจะใช้ data structure ประเภทนี้มาช่วยเพื่อลดเวลาการเช็คค่า

Cuckoos

เป็นตระกูลนกประเภทนึง ที่มีลักษณะการฝากฟักไข่และเลี้ยงลูก เช่น นกกาเหว่าในบ้านเรา ที่จะแอบไปไข่ไว้ในรังนกอีกา แล้วก็ฝากกาเลี้ยงจนโต แต่นกตระกูลนี้ในยุโรป มันป่าเถื่อนกว่านั้นตรงที่ หลักจากที่ลูกนกได้ออกมาจากไข่แล้ว มันจะพยายามกำจัดไข่ฟองอื่นๆ ให้ออกไปจากรัง โดยให้เหลือมันตัวเดียว ละก็ให้พ่อแม่บุญธรรมเลี้ยงมันตัวเดียว เลวสึดดดด

ช่างมัน นั่นมันเรื่องของนก

ทีนี้ ไอ้ data structure + algorithm ตัวนี้ มันจะมีพฤติกรรมเหมือนนก Cuckoo นี่แหละ

Cuckoo hashing

ก่อนจะไปดูตัว filter อยากให้เข้าใจเรื่องนี้ก่อน คือ Cuckoo hashing ซึ่งมันมีไว้แก้ปัญหาการชนกันของ hash (hash collisions) ในตาราง key-value ที่ค่า key ถูก generate มาจาก hash function และ value ก็คือค่าที่เราเอาไป generate key

จริงๆ มันก็ไม่ได้แก้ท่าพิศดารอะไรหรอก ถ้าหากมันดัน generate ค่า(key)มาชนกัน สิ่งที่มันทำคือ มันจะไล่ค่า(value)เดิมให้ไปอยู่ที่อื่น(ซึ่งมีวิธีในการเลือกที่อยู่ใหม่ให้มัน ไม่ได้ทิ้งนะ) ซึ่งวิธีนี้มันก็เหมือนๆ กับพฤติกรรมของนก Cuckoo นี่เลย เขาเลยเอามาตั้งเป็นชื่อ

Algorithm ของ Cuckoo hashing ง่ายมาก คือ

  • เตรียม hash function 2 ตัว คือ h() และ h’() และ hash table ไว้ 2 ตัว สำหรับบันทึกค่าจาก h() เรียก T และ h’() เรียก T’
  • สมมติมีค่าอยู่หลายๆ ค่า เอาค่าทีละตัวเข้า h() เพื่อหาค่า key แล้วเก็บไว้ใน T โดยให้ key ที่ได้ ชี้ไปยังค่าที่เอามาเข้า hash function
  • ทำไปเรื่อยๆ ทีละตัว
  • ถ้าหากเจอค่าที่ h() คืนค่ามา key ซ้ำ ให้เอา key นั้น ชี้ไปยังค่าใหม่ ใน T
  • แล้วเอาค่าเดิมที่ถูกแทนที่ ไปเข้า h’() จะได้ key มาใหม่ แล้วเก็บไว้ใน T’ โดยให้ key ที่ได้ ชี้ไปยังค่าที่เอามาเข้า hash function
  • แล้วก็ทำไปเรื่อยๆ ทีละตัว ถ้าเข้า h() แล้วให้ key ซ้ำ ก็เก็บไว้ แล้วไล่มันไปอยู่อีกที่
  • ถ้าหาก h’() ยังให้ค่า key อื่นซ้ำอีกใน T’ ก็ไล่มันไปเข้า h() แล้วเก็บใน T

สรุปคือ ถ้า key ซ้ำ มันจะสลับไปเก็บอีก table นั่นเอง

ตรงนี้ มันเหมือนพฤติกรรมของนก Cuckoo!!!

ปัญหาคือมันจะเจอกรณี recursive คือสลับไปๆ มาๆ ไม่จบสักที ซึ่งตรงนี้ เราอาจจะกำหนดจำนวนรอบในการสลับระหว่าง table เช่น ถ้าเกินจำนวนรอบที่กำหนดไว้ ให้ถือว่ามัน recursive

สิ่งที่ต้องทำต่อคือ ปรับปรุง hash function ทั้งสองใหม่ แล้ว re-hash มันใหม่

ถ้างง มีตัวอย่าง

สำหรับตัวอย่าง ผม copy มาจาก wikipedia เลย

ภาพแรกนี้จะอธิบายถึง hash function ตัวอย่างทั้งสองตัว ว่าทำงานยังไง และถ้าเอาค่ามาเข้า hash function แล้ว ผลลัพธ์ที่ได้จะมีค่าอะไรบ้าง

ตัวอย่างนี้ กำหนดให้ table for h(k) เป็น T และ table for h’(k) เป็น T’
มันจะเริ่มทำตั้งแต่ค่า 20 ไปถึง 39 ตามตัวอย่าง

  • เอา 20 ไปเข้า h() ได้ 9 แล้วเอา key 9 ชี้ไปยัง 20 ใน T
  • เอา 50 ไปเข้า h() ได้ 6 แล้วเอา key 6 ชี้ไปยัง 50 ใน T
  • ปัญหาแรกอยู่ตรงนี้ เอา 53 เข้า h() ดันได้ 9 มันซ้ำ!!
  • เอา 9 ชี้ไปยัง 53 ใน T และไล่ 20 ออกไป
  • เอา 20 ไปเข้า h’() ได้ 1 แล้วเอา key 1 ชี้ไปยัง 20 ใน T’
  • เริ่มค่าถัดไป คือ 75 เข้า h() ดันได้ 1 อีก เอ้า!! ไล่ 53 ไปอยู่ใน T’
  • เอา 53 ไปเข้า h’() ได้ 4 แล้วเอา key 4 ชี้ไปยัง 53 ใน T’
  • ทำไปเรื่อยๆ จนความซ้ำไปซ้ำมา เกิดขึ้นที่ค่า 105 คือ มันไปเตะ 50 ออกไป T’
  • ละ 50 ก็ไปเตะ 53 ใน T’ ไป T
  • พอ 53 กลับมา T ก็ไปเตะ 75 ไป T’ อีก
  • ดีที่ h’() ยังจัดที่ให้ 75 อยู่ใน T’

ตัวอย่างก็ประมาณนี้นะครับ

ทีนี้ ถ้าหากเรามี Cuckoo hash table แล้ว เราสามารถใช้มันแทน data structure ใน Bloom filter ได้

Cuckoo filter

มาถึงพระเอกของเรา คือ จากการใช้ Cockoo hash table ใน Bloom filter เนี่ย มันก็ยังใช้ memory เยอะอยู่ ก็เลยมีการวิจัยขึ้น

ซึ่ง paper นี้ก็เป็น resource หลักในการเขียน post นี้

paper นี้ เสนอสิ่งที่เรียกว่า partial-key cuckoo hashing ซึ่งวิธีการของสิ่งนี้ จะอธิบายแทรกในส่วนของ algorithm ที่จะอธิบายถัดไป

Cuckoo filter algorithms

Operation ที่ทำได้ใน Cuckoo filter มี 3 สิ่ง คือ Insert, Lookup และ Delete ซึ่ง Delete นี่แหละ เป็นสิ่งที่ผมว่ามันน่าจะใช้เป็นทางเลือกที่ดีมากในการเป็น candidate กับ Bloom filter

Insert

น่าจะเป็นส่วนที่ซับซ้อนที่สุดละ

f = fingerprint(x);
i1 = hash(x);
i2 = i1 ⊕ hash(f);
if bucket[i1] or bucket[i2] has an empty entry then
add f to that bucket;
return Done;
// must relocate existing items;
i = randomly pick i1 or i2;
for n = 0; n < MaxNumKicks; n++ do
randomly select an entry e from bucket[i];
swap f and the fingerprint stored in entry e;
i = i ⊕ hash(f);
if bucket[i] has an empty entry then
add f to bucket[i];
return Done;
// Hashtable is considered full;
return Failure;

จาก algorithm ด้านบน มันใกล้เคียงกับ Cuckoo hashing มาก แต่ต่างกันที่รายละเอียดย่อยๆ

Buckets

i1, i2 ในทีนี้จะเป็นที่อยู่หรือ key ของ bucket แล้ว เมื่อเปรียบเทียบกับ Cuckoo hashing ค่า key จะชี้ไปที่ค่า แต่คราวนี้ key จะชี้ไปที่ bucket ที่เก็บค่าอีกที ซึ่งการกำหนดขนาดของ bucket ก็ต้องปรับตามขนาดของข้อมูลทีมี

Fingerprint(fixed-size)

ใช้ fingerprint(fixed-size) ของค่า(หมายถึง fingerprint อาจจะมี 20 หลัก แต่เราเก็บ 10 หลักก็พอแล้ว) แทนที่จะใช้ค่านั้นๆ เพื่อ minimize พื้นที่ในการบันทึก ซึ่งค่า fixed-size นี้จะมีผลต่อเรื่อง false positive จากการชนกันจาก hash function ด้วย

partial-key cuckoo hashing

ใช้เทคนิคที่เรียกว่า partial-key cuckoo hashing ในการ relocate ค่าใน hash table คือการเก็บด้วย fingerprint(fixed-size) เนี่ยตรงนี้เป็น challenge อย่างนึงตรงที่ ถ้าต้องมีการไล่ค่าเดิมให้ไปอยู่อีกที่(relocation) มันมีความจำเป็นต้องรู้ค่าจริงๆ (ที่ไม่ใช่ fingerprint) เพื่อเอาไปเข้า hash function แต่เราดันบันทึกค่า fingerprint(fixed-size) จะทำให้ความสามารถในการ relocation ด้วยค่าจริงๆ จะทำไม่ได้เลย เพราะถูกแปลงเป็น fingerprint ไว้แล้ว การ hash มันจะไม่สามารถย้อนไปมาระหว่าง hash function ได้
สิ่งที่ partial-key cuckoo hashing ทำคือ

i1 = hash(x)
i2 = i1 ⊕ hash(x’s fingerprint)
i1 = i2 ⊕ hash(x’s fingerprint)

มันใช้ xor เป็นตัว operate ในการที่จะหา i2 จาก i1 และ hash ของ fingerprint
และหา i1 จาก i2 และ hash ของ fingerprint ด้วย

เพิ่มเติมนิดหน่อย

i2 = i1 ⊕ hash(x’s fingerprint)

จริงๆ กรณีนี้ ทำแบบนีได้

i2 = i1 ⊕ x’s fingerprint

แต่ hash มันเพื่อให้แน่ใจว่า i1 และ i2 จะไม่อยู่ใกล้กัน
ความใกล้-ไกล ขึ้นอยู่กับจำนวน fixed-size ของ fingerprint หาก fixed-size มากก็ไกลมาก แต่ถ้าเอามา hash คือแน่ใจว่ามันจะไม่อยู่ใกล้กันแน่นอน เพื่อลดโอกาสการชนกันของค่า key จาก hash function

แต่ปัญหาการชนกันก็ยังหนีไม่พ้นเพราะการ fixed-size มันทำให้โอกาสที่จะเกิดการชนกันก็มากขึ้นตามไปด้วย

Lookup

f = fingerprint(x);
i1 = hash(x);
i2 = i1 ⊕ hash(f);
if bucket[i1] or bucket[i2] has f then
return True;
return False;

การค้นหานี่ตรงไปตรงมา คือเอาค่ามาแปลงเป็น fingerprint ก่อนแล้วเอามาเช็คว่าอยู่ใน i1 หรือ i2 หรือเปล่า ถ้ามีก็แสดงว่ามีค่านี้อยู่ ซึ่ง i1 และ i2 ก็หาได้จาก partial-key cuckoo hashing

Delete

f = fingerprint(x);
i1 = hash(x);
i2 = i1 ⊕ hash(f);
if bucket[i1] or bucket[i2] has f then
remove a copy of f from this bucket;
return True;
return False;

การเอาของออกจาก filter ก็ไม่ยาก ซึ่ง Bloom filter ทำไม่ได้

False positive

ปัญหา false positive ไม่ได้หายไปไหน และสาเหตุการเกิดก็คล้ายๆ กับ Bloom filter มาก ถ้าดันมีค่าที่ให้ fingerprint(fixed-size) เหมือนกัน และยังอยู่ใน bucket เดียวกันอีก ก็จะเกิดปัญหา ซึ่งเราสามารถลดโอกาสเกิด false positive ได้ด้วยการเพิ่มขนาดของ fixed-size ของ fingerprint แต่ก็จะทำให้ขนาดในการเก็บข้อมูลใหญ่ขึ้นตามไปด้วย

Cuckoo filter vs Bloom filter

ใน paper อ้างว่ามี 3 สิ่งที่ Cuckoo filter ทำได้ดีกว่า Bloom filter คือ

  • สามารถลบของจาก filter ได้
  • ค้นหาของใน filter ได้เร็วกว่า
  • ใช้พื้นที่ได้ดี(efficient)หรือน้อยกว่า

ความเด็ดของ Cuckoo filter คือมันสามารถลบของจาก filter ได้นี่แหละ ซึ่ง Bloom filter ทำไม่ได้ แต่สิ่งที่แลกมาก็การเอาของใส่ใน filter ก็จะช้าลง เพราะเจอขั้นตอนการทำ relocation

เรื่องความเร็วในการหาของ ก็ค่อนข้างเห็นชัดเพราะมันมีแค่ 2 hash function ไปหาของ 2 bucket ซึ่งซับซ้อนน้อยกว่า Bloom filter เพราะมันต้องมา tune เรื่อง จำนวน hash function อีก มีแค่ 2 function ไม่พอแน่นอน

ส่วนเรื่องขนาดในการเก็บ filter อ้างจากใน paper มันได้ดีมากกว่า Bloom filter ก็จริง แต่ด้วยตัวเลขผมว่าไม่ได้เยอะมาก ไม่ได้รู้สึกว้าวอะไรกับมัน รวมถึง false positive rate ก็ไม่ได้ต่างกันมาก

จบ!!!

LINE Developers Thailand

Closing the distance. Our mission is to bring people, information and services closer together

Neng Liangpornrattana

Written by

A data plumber, basketballer, workout addicted, dog and cat lover

LINE Developers Thailand

Closing the distance. Our mission is to bring people, information and services closer together

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade