ลอง Redis HyperLogLog

เมื่อช่วงเย็นกำลังพยายามหาวิธีเพิ่มความเร็วในการทำงานของการใช้งาน Set ใน Redis อยู่ ซึ่งในตอนนี้ก็ใช้สำหรับการนับคนในพื้นที่ เช่น

เมื่อนาย X เข้ามาที่พื้นที่ A เมื่อเวลา 17:10น.​ เราก็จะเอา นาย X ไปเพิ่มอยู่ใน SET ของ พื้นที่ A ที่ช่วงเวลา 17:00–17:15

แล้วถ้านาย Y เข้ามาในพื้นที่ A เช่นเดียวกัน ในเวลา 17:11น. เราก็จะเอานาย Y ไปเพิ่มอยู่ใน Set เดียวกัน ซึ่งจะได้เป็น

Set ( A, 17:00–17:15) = [ X, Y ]

ซึ่งในช่วงเวลานั้น แม้ว่า นาย X อาจจะออกไปข้างนอก แล้วเข้ามาใหม่ เนื่องจากคุณลักษณะของ Set ซึ่งไม่เก็บค่าซ้ำ จึงทำให้ช่วงเวลาที่เหลือ ก็จะมีแค่ นาย X และ นาย Y

ที่นี้ถ้าเราต้องการนับจำนวนคนในพื้นที่ A ในเวลา 17:00–17:15 เราก็แค่นับจำนวนสมาชิกใน Set เท่านั้นเอง

Count(Set(A, 17:00–17:15)) = 2

นอกจากนี้ถ้า สมมติว่า ทั้งอาคารประกอบด้วย พื้นที่ A และพื้นที่ B มีใครอยู่ในบริเวณอาคารในช่วงเวลา 17:00–17:15 บ้าง โดยการนำ Set ของพื้นที่ A และ B มาทำกระบวนการที่เรียกว่า Union ขึ้นมา

Set( B, 17:00–17:15) = [ Y, Z]

Union(A,B) = [X, Y , Z]

จะเห็นว่าแม้ว่า Y จะอยู่ในพื้นที่ B แต่พอมารวมกันก็จะถูกตัดตัวซ้ำออกไปทำให้การนับจำนวนเป็นไปอย่างแม่นยำ

ปัญหาของการใช้ Set ใน Redis คือ มันใช้ทรัพยากรค่อนข้างเยอะ ทั้ง CPU และ Memory โดยเฉพาะเมื่อ Set มีขนาดใหญ่

HyperLogLog

ทีนี้ใน Redis รุ่นหลังๆ ก็มี Structure ที่ชื่อว่า HyperLogLog มาช่วยเหลือ ซึ่ง HyperLogLog เป็น อัลกอลิทึมสำหรับปัญหา Count-Distinct โดยที่มันจะใช้ทรัพยากรน้อยลง เพราะตัวมันเป็นกลุ่มของ Probabilistic DataStructure ดังนั้นจึงมีโอกาสที่ มีความคลาดเคลื่อนในความแม่นยำได้ โดยอาจจะมี ไปถึง 2% ขณะที่ Redis บอกว่า Error อยู่ที่ 0.98%

สิ่งสำคัญที่จะต้องดูก่อนที่จะตัดสินใจว่าเราจะใช้ตัวนี้ คือเรายอมรับในความคลาดเคลื่อนได้แค่ไหน

• ถ้าความแม่นนำของตัวเลขมีความสำคัญมากๆๆ ไม่ควรใช้
• ถ้าต้องการความสามารถทั้งหมดของ Set ไม่ควรใช้

ทั้งนี้เพราะ HyperLogLog จะใช้ได้แค่ เพิ่มสมาชิก, รวม, และนับ เท่านั้น

ขณะที่ Set จะสามารถแสดงรายการใน Set, ลบ , หรือกระบวนการอื่นๆ เช่น Intersection

อันนี้เป็นตัวอย่างเบื้องต้น

เมื่อทำการรันโปรแกรมดูก็จะได้ผลลัพธ์คือจำนวนของผู้ใช้ในแต่ละ Set และจำนวนผู้ใช้จากการ Merge นั่นเอง

ถือว่าเป็นอีกท่านึงที่ ถ้าเราไม่ได้จำเป็นต้องได้ผลลัพธ์ที่ต้องพลาดไม่ได้ ใช้ทรัพยากรในการทำงานน้อย HyperLogLog ถือเป็นอีกกระบวนท่านึงที่สามารถใช้งานได้ครับ