4 เทคนิคที่ควรรู้ในการทำงานกับ Streaming Data
ช่วงนี้ผมทำงานเกี่ยวกับ streaming data processing ซะส่วนใหญ่ครับ เจอโจทย์ที่สามารถแก้ได้ด้วยสติปัญญาที่มี แต่พบว่า มันแพงมากในแง่ของการใช้ทรัพยากร เพราะข้อมูลเยอะมาก ตัวอย่างความแพงก็เช่น ใช้ ram เยอะ ใช้ network io เยอะ เลยต้องไปทำการบ้านเพิ่ม พบว่ามี 4 สิ่งที่คิดว่าน่าจะเอามาใช้ประโยชน์ในการทำงานกับ streaming data processing คือ
- Reservoir sampling
- Bloom filter
- Count-min sketch
- HyperLogLog
4 เทคนิคนี้ เป็นสิ่งที่มีข้อจำกัดว่าจะทำงานได้ดีกับข้อมูลที่มีลักษณะ streaming และเนื่องจากเป็นการใช้ประโยชน์จากเรื่องความน่าจะเป็น(probability) สิ่งที่แลกมาก็คือความถูกต้องของข้อมูลจะไม่แม่นยำมากนัก
Reservoir sampling
เป็น algorithm ในเรื่องของการสุ่มครับ ทีนี้ทำไมการสุ่มถึงใช้การสุ่มแบบทั่วไปไม่ได้ล่ะ??? ก็แค่จับสิ่งที่มีทั้งหมดมารวมในกล่องละก็เลือกมาตามจำนวนที่ต้องการ
ปัญหาของเราคือ มันเป็น streaming ไงครับ เราไม่รู้ว่ามันจะมีกี่ตัว กี่ก้อน กี่อัน มันมาเรื่อยๆ แล้วก็ไม่จบด้วย
Reservoir sampling เลยถูกสร้างมาแก้ปัญหาสิ่งนี้
โจทย์ก็ง่ายๆ ครับ เราอยากสุ่มเอาข้อมูล 15 สิ่งมาใช้งาน สมมติเป็น IP ของลูกค้าที่วิ่งเข้ามาใช้งานระบบของเราละกัน ก็คือเราจะได้ IP มา 15 IP จากข้อมูลที่วิ่งเข้ามา
หลักการทำงานของ Reservoir sampling คือ
- เราจะจองพื้นที่สำหรับเก็บ IP k อันไว้ก่อน(reservoir) แล้ว IP ที่วิ่งเข้ามา k อันแรก ก็เอามาเก็บไว้ในพื้นที่นี้ สมมติพื้นที่นี้เป็นกล่องละกัน (ถ้างงก็คิดซะว่าเป็น array) เราก็จะได้ กล่องที่เก็บ IP 15 อัน และมี 15 IP แรกเก็บไว้ในกล่อง 15 กล่อง
- จากนั้น IP อันที่ 16 วิ่งเข้ามา เราจะเช็คด้วยเงื่อนไขที่ว่า เราจะสุ่มเลขตั้งแต่ 0 ถึง 1 ถ้าออกมามากกว่า 15/16 เราจะไม่เก็บ IP นีไว้ในกล่อง 15 อัน แต่ถ้าน้อยกว่า 15/16 เราจะเก็บไว้ใน 15 กล่องของเรา โดยสุ่มเอา IP ที่อยู่ในนั้น ออกมาสักตัวแล้วแทนที่ด้วย IP อันที่ 16 (ขอให้ทดไว้ในใจเรื่องตัวเลข 15/16 ไว้ก่อน)
- พอ IP อันที่ 17 เข้ามาเราจะทำเหมือนเดิมคือสุ่มเลข(ทศนิยม)ตั้งแต่ 0 ถึง 1 และถ้ามันมากกว่า 15/17 เราจะไม่เก็บ IP นีไว้ในกล่อง 15 อัน แต่ถ้ามากกว่า 15/17 เราจะเก็บไว้ใน 15 กล่องของเรา โดยสุ่มเอา IP ที่อยู่ในนั้น ออกมาสักตัวแล้วแทนที่ด้วย IP อันที่ 17
- ให้วนไปเรื่อยๆ โดยเปลี่ยนเลข 17 เป็น 18 ในรอบถัดไป และรอบถัดๆ ไป n รอบ และเราก็จะได้ของที่เราสนใจคือ IP มา k อัน ในทีนี้ก็คือ 15 อัน
ตัวเลข 15/16 หรือ 15/17 ก็คืออัตราส่วนความน่าจะเป็นที่เราจะเอามันใส่ในกล่องที่เราต้องการ คือ k/n
ซึ่งในข้อมูลก้อนแรกๆ หลังจากอันดับที่ k ก็คือ 16 เป็นต้นไปที่เข้ามา โอกาสที่มันจะถูกเก็บไว้ในกล่องจะมีมาก (random number from 0 to 1< 15/16) แต่ข้อมูลก้อนหลังๆ สมมติก้อนที่ 100000 ความน่าจะเป็นที่มันจะถูกเก็บในกล่องจะมีน้อยมาก (random number from 0 to 1< 15/100000) ก็คือยิ่งข้อมูลมาก ของในกล่องจะเริ่มไม่ถูกเปลี่ยนแล้ว
ในเชิงคณิตศาสตร์ คลิปนี้ได้พิสจูน์ว่ามันเทียบเท่าการสุ่มแบบทั่วไปได้
Implementation
ง่ายมากจน implement เองได้ครับ
Bloom filter
เป็น data structure อีกแบบนึง ที่ไว้ใช้ในการเช็คว่า ข้อมูลที่เราสนใจ อยู่ในกลุ่มของข้อมูลทั้งหมดหรือเปล่า
เหมือนเดิมเลยครับ ก็จับมาไล่เช็คแบบง่ายๆ ไล่เช็คทีละตัวเลย ไม่ได้หรือไง? (O(n))
ก็ย้อนมาที่ปัญหาของเราครับ ข้อมูลของเราเยอะมาก ถ้าไล่เช็คทีละตัว ก็อีก 3 วันนู่นละครับ(ก็เวอร์ไป) ปัญหาคือมันจะช้ามากครับ ตัว processing ของเราคงจะต้องรอนานหน่อยในการที่จะจบกระบวณการ process ถ้าต้องเช็คของว่ามีข้อมูลอยู่หรือยัง
Bloom filter เลยถูกสร้างมาแก้ปัญหาสิ่งนี้ (ชื่อ Bloom filter มาจากชื่อผู้ที่คิดมันขึ้นมา คือ Burton Howard Bloom)
โจทย์ง่ายๆ ครับ เราอยากเช็คว่า IP ของลูกค้าคนนี้ เคยเข้ามาใช้งานแล้วหรือยัง
ก่อนจะไปถึงหลักการทำงาน ต้องมีเตรียมของก่อน
- พื้นที่ หรือเปรียบเทียบเป็นกล่องหลายๆ กล่อง ยิ่งเยอะยิ่งดี โดยแต่ละกล่องจะแปะตัวเลข index ไว้ ตั้งแต่ 0 และเรียงไปเรื่อยๆ (ถ้างงก็คิดซะว่าเป็น array) โดยใส่เลข 0 ไว้ในทุกกล่อง
- hash function ที่สามารถแปลง IP เป็นตัวเลขที่ไม่ซ้ำได้ (unique) ยิ่งเยอะยิ่งดี ในที่นี้จะสมมติให้มี 2 อันละกัน
หลักการทำงานของ Bloom filter คือ
- เอาข้อมูลก็คือ IP อันแรก มาเข้า hash function ก่อน สมมติ
# IP1: hash1(IP1) -> 20, hash2(IP1) -> 200- เอาเลขที่ได้ เป็นตำแหน่งในการเซ็ตค่าในกล่องหลายๆ กล่องของเรา
[0->0][1->0]...[20->1]...[199->0][200->1][201->0]...- เอา IP อันที่ 2 เข้ามาเข้า hash function อีก
# IP2: hash1(IP2) -> 13, hash2(IP2) -> 205- เอาเลขที่ได้ เป็นตำแหน่งในการเซ็ตค่าในกล่องหลายๆ กล่องของเรา โดยยังมีค่าจาก IP อันแรกอยู่
[0->0]...[13->1]...[20->1]...[199->0][200->1]...[205->1]...- เอา IP อันที่ 3 เข้ามา hash function อีก
# IP3: hash1(IP3) -> 205, hash2(IP2) -> 64- เอาเลขที่ได้ เป็นตำแหน่งในการเซ็ตค่าในกล่องหลายๆ กล่องของเรา โดยยังมีค่าจาก IP อันแรกและอันที่ 2 อยู่ ซึ่งตรงนี้ ตำแหน่งที่ 205 เคยถูกเซ็ตมาแล้ว ก็ไม่ต้องไปทำอะไรกะมัน
[0->0]...[13->1]...[20->1]...[64->1]...[200->1]...[205->1]...สมมติเราอยากจะเช็คว่ามี IP อันที่ 4 ว่ามีอยู่ใน list ของเราหรือยัง เราจะเอามันมาเข้า hash function
# IP4: hash1(IP4) -> 22, hash2(IP4) -> 99เราจะเอาเลขนี้มาเช็คว่าตำแหน่งที่ 22 และ 99 ถูกเซ็ตค่าไว้หรือยัง โดยถ้ามีตำแหน่งใดตำแหน่งนึงยังไม่ถูกเซ็ต ก็ถือว่า ยังไม่มี IP นี้มาก่อน
ในมุมของ time complexity ตัวอย่างนี้จะใช้ O(n) เอง จาก hash function 2 ตัว และเราไม่ต้อง loop ในการหาค่าในกล่องของเรา เพราะเรามี index ตำแหน่งของกล่องกำกับแล้ว
ดูเหมือนจะดี แต่ปัญหามันคือ มันอาจจะเกิด false positive ได้ คือ เอาค่ามาเช็คแล้วมันบอกว่า เคยมีค่านี้อยู่แล้ว แต่จริงๆ มันไม่มี
สมมติ IP5 เข้ามา
# IP5: hash1(IP5) -> 64, hash2(IP5) -> 20ตำแหน่งที่ 20 และ 64 ถูกเซ็ตจาก IP อื่นไว้แล้ว มันจะถูกบอกว่า IP5 มีอยู่ใน list ของเราแล้ว ซึ่งจริงๆ ยังไม่มี นี่คือ false positive
ส่วนกรณี false negative คือจริงๆ แล้ว IP มีอยู่ แต่ผลลัพธ์ว่าไม่มี จะไม่เกิดขึ้นแน่นอน เพราะหลังจากเข้า hash function แล้ว โอกาสที่จะเจอกรณีที่กล่องที่เคยถูกเซ็ตไว้แล้ว มีการเซ็ตค่ากลับนี่ไม่มีเลย นอกจากจจะมี bug 55555
ถ้าเราอยากลดโอกาสการซ้ำกันของค่าใน hash เราก็ต้องมี hash function เพิ่มขึ้น ในขณะเดียวกัน กล่องหรือ memory เราก็ต้องมีค่าเยอะขึ้นด้วย เพื่อป้องกันการเกิด false positive ทีนี้ ต้องเพิ่มขนาดไหน เยอะขนาดไหน คำนวณได้ทีนี่
ตัวอย่าง สมมติอยากเก็บ 40 ล้าน IP และให้โอกาสเกิด false positive 0.00001 % หรือ 1 ใน 10 ล้าน IP สิ่งที่ต้องใช้คือ
- 160 MB Memory สำหรับเก็บกล่อง 1,341,908,173 กล่องในการเก็บค่าจาก hash function
- 23 hash functions (O(23))
ด้วย resource นี้ จะเกิด false position ประมาณ 4 ครั้ง
Implementation
- Redis (https://oss.redislabs.com/redisbloom/)
- Java (https://github.com/addthis/stream-lib)
- Python (https://pyprobables.readthedocs.io/en/latest/#import-pyprobables-and-setup-a-bloom-filter)
- Go (https://github.com/willf/bloom)
ศึกษาเพิ่มเติมได้ที่
Count-min sketch
ก็เป็น data structure อีกแบบหนึ่ง เอาไว้นับจำนวนข้อมูลจำนวนข้อมูลที่เราสนใจจากข้อมูลทั้งหมด
คงไม่ต้องถามแล้วว่าก็นับมันแบบซื่อๆ ไม่ได้หรอ?? (O(n))
มันใหญ่มากครับ รอไม่ไหว
Count-min sketch เลยมาช่วยการนับนี้
โจทย์ง่ายๆ ครับ เราอยากเช็คว่ามี user คนนี้เข้ามาใช้งานกี่ครั้ง สมมตินับจาก IP ละกัน
ก่อนจะไปถึงหลักการทำงาน ต้องมีเตรียมของก่อน ซึ่งจากชื่อเนี่ย มันคือ sketch หรือภาพร่าง ภาพร่างในที่นี้จะเป็นกล่องเรียงกันเหมือนตาราง หรือจะเรียกง่ายๆ ว่าเป็นอาเรย์ 2 มิติ(2 dimensional array) ก็ได้ โดยในมิติแนวนอนหรือแต่ละแถวจะเก็บผลลัพธ์จาก hash function ที่ให้ค่าตัวเลขที่ไม่ซ้ำ(unique) ในตำแหน่ง index ของมิติแนวตั้ง งงเนาะ ดูตารางละกัน
+---------+---+---+---+---+---+---+---+---+---+
| - | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---------+---+---+---+---+---+---+---+---+---+
| hash1() | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| hash2() | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| hash3() | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| hash4() | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---------+---+---+---+---+---+---+---+---+---+ขอแสดงตัวอย่างเท่านี้พอ เพื่อความง่ายต่อการอธิบาย
หลักการทำงานคือ
- เอา IP แรกที่เข้ามา ไปเข้า hash function ทั้ง 4 อัน สมมติได้ค่า 4, 5, 2, 7 ตามลำดับ
- เอามาบันทึกลง sketch โดย +1 ไปในช่อง index ตำแหน่งของค่าที่ได้ตามแถวของ hash function
+---------+---+---+---+---+---+---+---+---+---+
| - | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---------+---+---+---+---+---+---+---+---+---+
| hash1() | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | <- 4
| hash2() | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | <- 5
| hash3() | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | <- 2
| hash4() | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | <- 7
+---------+---+---+---+---+---+---+---+---+---+- เอา IP อันที่ 2 ที่เข้ามา ไปเข้า hash function ทั้ง 4 อัน สมมติได้ค่า 2, 0, 6, 8 ตามลำดับ
- เอามาบันทึกลง sketch โดย +1 ไปในช่อง index ตำแหน่งของค่าที่ได้ตามแถวของ hash function
+---------+---+---+---+---+---+---+---+---+---+
| - | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---------+---+---+---+---+---+---+---+---+---+
| hash1() | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | <- 2
| hash2() | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | <- 0
| hash3() | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | <- 6
| hash4() | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | <- 8
+---------+---+---+---+---+---+---+---+---+---+- เอา IP อันที่ 3 ที่เข้ามา ไปเข้า hash function ทั้ง 4 อัน สมมติได้ค่า 1, 7, 2, 5 ตามลำดับ
- บันทึกเหมืิอนเดิม
+---------+---+---+---+---+---+---+---+---+---+
| - | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---------+---+---+---+---+---+---+---+---+---+
| hash1() | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | <- 1
| hash2() | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | <- 7
| hash3() | 0 | 0 | 2 | 0 | 0 | 0 | 1 | 0 | 0 | <- 2
| hash4() | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | <- 5
+---------+---+---+---+---+---+---+---+---+---+- เอา IP อันที่ 4 ที่เข้ามา ไปเข้า hash function ทั้ง 4 อัน สมมติได้ค่า 2, 1, 8, 7 ตามลำดับ
- บันทึกต่อไป
+---------+---+---+---+---+---+---+---+---+---+
| - | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---------+---+---+---+---+---+---+---+---+---+
| hash1() | 0 | 1 | 2 | 0 | 1 | 0 | 0 | 0 | 0 | <- 2
| hash2() | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | <- 1
| hash3() | 0 | 0 | 2 | 0 | 0 | 0 | 1 | 0 | 1 | <- 8
| hash4() | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 2 | 1 | <- 7
+---------+---+---+---+---+---+---+---+---+---+- เอา IP อันที่ 5(สุดท้ายของตัวอย่างละ) ซึ่งเป็น IP ซ้ำจากอันที่ 1 ไปเข้า hash function ทั้ง 4 อัน ต้องได้ค่า 4, 5, 2, 7 ตามลำดับเหมือนเดิม
- บันทึกสุดท้าย
+---------+---+---+---+---+---+---+---+---+---+
| - | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---------+---+---+---+---+---+---+---+---+---+
| hash1() | 0 | 1 | 2 | 0 | 2 | 0 | 0 | 0 | 0 | <- 4
| hash2() | 1 | 1 | 0 | 0 | 0 | 2 | 0 | 1 | 0 | <- 5
| hash3() | 0 | 0 | 3 | 0 | 0 | 0 | 1 | 0 | 1 | <- 2
| hash4() | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 3 | 1 | <- 7
+---------+---+---+---+---+---+---+---+---+---+สรุปลำดับจะเป็นแบบนี้ [IP1, IP2, IP3, IP4, IP1] ตามลำดับ
สมมติเราอยากจะนับ IP1 เข้ามากี่ครั้ง เราจะเอาไปเข้า hash function ทั้ง 4 อัน ซึ่งจะได้ 4, 5, 2, 7 ตามลำดับ เราจะเอาเลขในตำแหน่งนี้มาใช้งาน ซึ่งจะได้เป็น
+---------+---+---+---+---+---+---+---+---+---+
| - | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---------+---+---+---+---+---+---+---+---+---+
| hash1() | 0 | 1 | 2 | 0 | 2 | 0 | 0 | 0 | 0 | <- 4
| hash2() | 1 | 1 | 0 | 0 | 0 | 2 | 0 | 1 | 0 | <- 5
| hash3() | 0 | 0 | 3 | 0 | 0 | 0 | 1 | 0 | 1 | <- 2
| hash4() | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 3 | 1 | <- 7
+---------+---+---+---+---+---+---+---+---+---+-> min(2, 2, 3, 3)
แล้วเราจะเอาค่าน้อยสุดมาใช้(ที่มาของชื่อ Count-min) ซึ่งก็คือ 2
การเอาค่าน้อยสุดมาใช้ ก็เพื่อหลีกเลี่ยงการได้ hash ซ้ำกันแล้วค่ามันจะถูก +1 มาจากค่าอื่น
สมมติอีก อยากจะนับ IP2 เข้ามากี่ครั้ง ทำเหมือนเดิม เข้า hash function ทั้ง 4 แล้วจะได้ 2, 0, 6, 8 ตามลำดับ เลขที่จะเอามาใช้งานคือ
+---------+---+---+---+---+---+---+---+---+---+
| - | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---------+---+---+---+---+---+---+---+---+---+
| hash1() | 0 | 1 | 2 | 0 | 2 | 0 | 0 | 0 | 0 | <- 2
| hash2() | 1 | 1 | 0 | 0 | 0 | 2 | 0 | 1 | 0 | <- 0
| hash3() | 0 | 0 | 3 | 0 | 0 | 0 | 1 | 0 | 1 | <- 6
| hash4() | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 3 | 1 | <- 8
+---------+---+---+---+---+---+---+---+---+---+-> min(2, 1, 1, 1)
เราจะเอาค่าน้อยสุดมาใช้ ซึ่งก็คือ 1
ดูเหมือนจะดีอีกแล้ว.. แต่!!!!! ถ้าหากมี IP100 เข้ามาแล้วค่าจาก hash function ทั้ง 4 ได้เป็น 7, 2, 5, 4 ตามลำดับ
สังเกตเห็นปัญหาไหมครับ?? มันคือค่าเดียวกันกับ IP1 แต่เปลี่ยนลำดับ แล้วมันก็จะถูกบันทึกใน sketch ตามกระบวณการ แล้วเรามานับว่า IP1 และ IP100 เข้ามากี่ครั้งแล้ว เราจะได้ค่าเดียวกัน คือ IP1 -> min(3, 3, 4, 4) หรือ IP100 -> min(4, 4, 3, 3) ซึ่งก็คือ 3
ในการหลีกเลี่ยงปัญหา ก็ควรมีจำนวน hash function ที่มากกว่านี้ เพื่อหลีกเลี่ยงโอกาสที่มันจะให้ค่าที่ซ้ำกันแต่ต่างลำดับ
แล้วควรจะมีกี่ตัว แล้วต้องเตรียม sketch เราให้กว้างขนาดไหน คำนวณได้ที่
มีการอธิบายที่ไปที่มาของการคำนวณของแต่ะละตัวเลขอยู่ ผมจะขอข้ามไป บางส่วนผมเองก็เข้าไม่ถึง
ซึ่งผมลองใช้ตัวเลขเดียวกันกับ Bloom filter เลยคือ นับ 40 ล้าน IP โดยกำหนดว่า ให้มีความผิดพลาดในการนับได้ 0.00001 % (1 ใน 10 ล้าน) สิ่งที่ต้องใช้คือ
- 308.889 MB Memory สำหรับเก็บกล่อง 462,111 (27183 กล่อง x 17)กล่องจาก hash function
- 17 hash functions ซึ่งตรงนี้ อาจจะมากไป ขึ้นอยู่กับการ implement hash function ของเราด้วย ถ้ามันไม่ไป block อะไรในการทำงาน ก็อาจจะรับได้ ถ้าปรับให้พลาดได้ 0.1% เนี่ย จะเหลือแค่ 7 เอง
ด้วย resource นี้ จะมีการนับพลาดราวๆ 4 ครั้ง
ด้วยตัวเลขข้างบน ผมสรุปเอาโดยที่ผมยังไม่รู้ว่า Epsilon(error factor) คืออะไร ส่งผลยังไงกับตัวเลขนะครับ แต่จากการคำนวณโดยให้ค่า Epsilon เป็น 0.0001 ถือว่าทำให้มีโอกาสผิดพลาดน้อยที่สุด
ในแง่ time complexity ทั้งเขียนและอ่านจะอยู่ที่ O(ln(1 / δ)) ซึ่ง δ คือความน่าจะเป็นในการเกิด error (อ้างอิงจากเว็บที่คำนวณ Count-min sketch ด้านบนครับ) แต่ลำพังการอ่านอย่างเดียว ผมว่า O(n) สำหรับการใช้งาน hash function และอีก O(n) ในการ loop หาตัวที่น้อยที่สุดก็พอ (อยากจะ optimize ในส่วนนี้ก็ได้นะครับ แต่ผมว่า loop 17 รอบนี่ ก็ไวมากแล้ว)
ซึ่งจริงๆ ยังมีอีก 1–2 วิธีในการลดการนับเกินลองศึกษาเพิ่มเติมดูได้ครับ
Implementation
- Redis (https://github.com/RedisLabsModules/countminsketch)
- Java (https://github.com/addthis/stream-lib)
- Python (https://pyprobables.readthedocs.io/en/latest/#import-pyprobables-and-setup-a-count-min-sketch)
- Go (https://godoc.org/github.com/dustin/go-probably)
ศึกษาเพิ่มเติมได้ที่
HyperLogLog
เรื่องนี้ซับซ้อนใช้ได้ระดับนึงในการที่จะเข้าใจว่ามันทำงานยังไง
มันเป็น algorithm ครับ เพื่อใช้ช่วยในการประมาณจำนวนสิ่งที่ไม่ซ้ำกัน (Cardinality or How many unique items in there?) ยกตัวอย่างเช่น Set
สมมติว่ามี set ที่มี สมาชิกเป็น [1,2,2,4,4,1] จะมีจำนวนสมาชิก(ซึ่งไม่ซ้ำกัน) คือ 3 ตัว
ปัญหาก็เดิมๆ ครับ ข้อมูลเยอะ และไหลมาเป็น stream เพราะฉะนั้น การนับแบบปกติดูจะทำให้เกิดปัญหา เพราะเราต้องการความเร็วในการ process เรารอนานมากไม่ได้ ซึ่งจริงๆ แล้ว นอกจากเรื่องความเร็วแล้ว มันใช้ memory ในการประมาณไม่เยอะอีกด้วย
อย่างที่เกริ่นไปก่อนแล้ว มันค่อนข้างซับซ้อน ผมจะค่อยๆ ไล่ไปทีละที่มานะครับ
LogLog
ใน paper(http://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf) เนี่ย เขาสังเกต pattern ของในรูปของ 0*1 เช่น ความน่าจะเป็นที่ค่า(ที่ถูก hash ให้เป็นเลขฐาน 2) 1จะมีความน่าจะเป็น 1/1, 01 เป็น 1/2, 001 เป็น 1/4, 0001 เป็น 1/8 ก็เลยสรุปได้เป็น
1 / (2^k) หรือ 2 ^ -kหมายความว่า โดยเฉลี่ยแล้ว ถ้าอยากจะเห็น 000001 จะต้องทำให้ได้ค่า hash มา 32 ครั้ง
โจทย์ของ LogLog เนี่ย คือการหาค่า 2^k หรือจำนวนทั้งหมดนั่นเอง
ตัวอย่าง สมมติผมอยากโยนเหรียญ 32 เหรียญพร้อมกัน โดยอยากให้มันออกหัวหมดทุกครั้ง(มี 0 ติดกัน 32 ตำแหน่งตั้งแต่ตำแหน่งแรก) ความน่าจะเป็นจะอยู่ที่ 1/(2³²) จากการที่มันเป็นความน่าจะเป็น ถ้าหากผมเจอการโยนเหรียนที่ออกหัวหมด 32 ครั้ง ตามสูตรผมสามารถตีความไปเองเลยว่า มันต้องผ่านการโยนทั้ง 32 เหรียญมาแล้ว 2³² ครั้งถึงจะเกิดเหตุการณ์นี้ขึ้น ผมเอาเลข 32 มาประเมินได้ 2³² แปลว่า ผมลดจำนวนครั้งในการโยน แทนที่ผมจะนับการโยน 4,300 ล้าน(ขอเป็นเลขกลมๆ เนาะ ขี้เกียจมาพิมพ์ 4,294,967,296 ทุกครั้ง) ผมประเมินจากเลข 32 เท่านั้นเอง มันคือ
2³² = 4,300 ล้านถ้าเราต้องการจะรู้ว่าจำนวนเหรียญที่จะสามารถนับได้ จากโอกาสทั้งหมดที่จะเป็นไปได้ ก็เอามาใส่ในรูป Logarithm ได้ เพราะความสัมพันธ์ระหว่างการโอกาสที่เหรียญทั้งหมดจะออก กับการจำนวนเหรียญทีมี มันคือรูป inverse ของ exponential
log (4,300 ล้าน) = 32 # log ฐาน 2 นะจ๊ะมาต่อที่ ถ้าหากเราเอาเลข 32 มาจัดอยู่ในรูปเลขฐาน 2 (คือ 0 หรือ 1) เราจะได้ 100000คือมี 6 หลัก ถ้าเราเอา 6 หลักนี้ มาบรรจุเลข 0 หรือ 1 ความน่าจะเป็นที่เราจะบันทึกตัวเลขสูงสุดได้ คือ 2⁶ ก็คือ 64 แปลว่า จริงๆ แล้ว ด้วยเลขฐาน 2 จำนวน 6 หลัก สามารถเก็บค่าได้ถึง 64 (หรือค่า k)
เลขที่ได้ จริงๆ ควรจะเป็น 64 มากกว่า 32 ถ้าอิงจากการเก็บเลขฐาน 2
เพราะฉะนั้น ควรจะเป็น 2⁶⁴ คือจำนวนทั้งหมดที่สามารถประเมินได้
log (2⁶⁴) = 64และ 64 หรือจำนวนเหรียญทั้งหมดที่สามารถโยนได้ ถ้าเราอยากรู้ว่าจะเก็บเลข 64 ในรูปเลขฐาน 2 จะต้องใช้กี่หลัก(bits) สามารถคำนวณได้ในรูป Logarithm เช่นเดียวกัน
log (64) = 6จัดรูปซะใหม่เป็น
log (log (2⁶⁴)) = 6แปลว่า ด้วยการเก็บข้อมูล 6 bits สามารถประเมินเลขได้ถึง 2⁶⁴ เลยทีเดียว
ก็เลยเป็นที่มาของชื่อ LogLog จากการ Log สองครั้ง
จะเห็นได้ว่าตัวอย่างที่ยกมา มีเรื่องของการโยนเหรียญ(หัวหรือก้อย หรือ 0 หรือ 1)ให้หน้าออกมาเหมือนกันแล้วนับโอกาสของความน่าจะเป็น ในกระบวณการเตรียมการนับก็เลยมีการเอาข้อมูลที่เราสนใจ คือ
- เอามาเข้า hash function (อีกแล้ว) โดยให้มันคืนค่าเป็น binary format หรือเลขฐาน 2
- สมมติให้เอาเข้า hash function ออกมา 6 หลักพอ ออกมาเป็น
000001 - แล้วจับเลข 0 ที่ติดกันจากตำแหน่งแรก (leading zero) มากที่สุด มาเป็นเลขชี้กำลังฐาน แล้วให้ 2 คือเลขฐาน ก็จะเป็น 2⁵
- เข้… ในตัวอย่างนี้ โยนครั้งเดียว แต่สามารถประเมินว่ามีการโยนมาแล้ว 32 ครั้ง
ด้วยความที่มันเพี้ยนขนาดนี้ 2^k เลยใช้ไม่ได้ละ เลยมีกระบวณการเพิ่มเติมคือ ต้องเอาค่ามาเข้า hash function หลายๆ อัน แล้วเอา leading zero ทั้งหมดที่ได้มาเฉลี่ย แปลว่า ถ้า hash function ยิ่งเยอะ ค่า error ก็จะน้อยลง ก็ยิ่งแม่นยำขึ้น
ซึ่งการเอามาเข้า hash function นั้น มันก็แพงในแง่ของการใช้ CPU อยู่ เลยใช้สิ่งที่เรียกว่า Stochastic averaging มาช่วย ซึ่งทำให้เหลือการเข้า hash function แค่ครั้งเดียว สามารถศึกษา Stochastic averaging ได้จาก
สิ่งที่ LogLog เอามาใช้จาก Stochastic averaging คือเรื่องนับค่าแล้วเอามาเก็บใน bucket โดยมีขั้นตอนดังนี้
- หยิบ 5 หลักแรกมาจาก hash function มาก่อน มาทำเป็น bucket id เช่น สมมติได้ค่า
00100001xx...xx(สมมติให้มี 32 bit) ก็จะได้00100เป็น id - หยิบจำนวน leading zero ถัดจากนั้นมาใส่ใน bucket คือ
00ก็คือ 2 - สมมติเก็บใน array ก็จะได้ตำแหน่งที่ 4 (
00100คือ 4)เก็บค่า 2 - ถ้ามีค่าตก bucket เดียวกัน แล้วมากกว่า ก็เก็บค่าที่มากกว่าที่ bucket นั้น
วนเก็บแบบนี้ไปเรื่อยๆ ตามจำนวนข้อมูลท่ีเราจะนับ แล้วก็เอามาใส่สูตร
(2^k) x buckets x factorโดย
- k คือ ค่าเฉลี่ยของค่าใน buckets ทั้งหมด(ในที่นี้คือ 32) ซึ่งเก็บแต่เฉพาะค่าที่มากสุด
- buckets คือจำนวน buckets ที่บันทึกได้ ซึ่งมากสุดก็คือ 32 จำนวน ถ้าหากเราให้ hash function คืนค่า 32 bit
- factor คือค่าคงที่ ที่ปรับตามจำนวน bit เพื่อทำให้ค่าที่ได้ผิดพลาดน้อยสุด ซึ่งสำหรับ 32 buckets ค่า factor อยู่ที่ประมาณ 0.7 (สำหรับการคำนวณต้องตามไปดูใน paper ครับ)
ซึ่งสูตรนี้ จะทำให้มีค่า error อยู่ที่
standard error = 1.30 / sqrt(buckets)ตัวอย่างนี้ ให้มี 32 buckets ค่า standard error จะเป็น 0.23 ก็คือ มีโอกาส 23% ที่จะเกิด error
แต่ถ้าเราเพิ่มให้มี buckets เป็น 1024 ค่า(หยิบ 10 bits แรก และเหลือ 22 bits หลังไว้หา leading zero) standard error จะเหลือเพียง 4%
ในมุมของ memory กรณีนี้ เราใช้ 5 bits เพื่อเก็บจำนวน leading zero
ถ้าเรามี 1024 buckets ก็เท่ากับว่าเราใช้ memory ราวๆ 5.12k เอง
แต่มันยังดีได้อีก ถ้าเอาเฉพาะ 70% ของค่าที่เรียกจากน้อยไปมากจาก buckets (เอา 30% มากสุดทิ้งไป) ค่า standard error จะเป็น
standard error = 1.05 / sqrt(buckets)ถ้ามี 1024 buckets จะมี standard error เหลือ 0.032 หรือราวๆ 3.2%
เรียกว่า Super-LogLog
แต่มันยังดีได้อีก ยังไม่หมด
HyperLogLog
เพราะมีการค้นพบอีกว่า ถ้าแทนที่จะเอามาหาค่าเฉลี่ยแบบเลขคณิต ของค่าที่มากที่สุดใน buckets แต่มาใช้ Harmonic mean(ไม่มีชื่อไทยมั้งนะ ใช้ทับศัพท์เลย)แทนเพื่อลดค่า leading zero ที่มากเป็นพิเศษไป จะทำให้เหลือ standard error เหลือ
standard error = 1.04 / sqrt(buckets)นอกจากจะใช้ Harmonic mean แทนแล้ว ยังมีเงื่อนไขอีก 2 ข้อคือ
- สำหรับกรณี buckets ทั้งหมดไม่ถูกเติมทั้งหมด
- สำหรับกรณี hash function เรา อาจจะคืนค่ามาซ้ำกันกับข้อมูลที่ต่างกัน
โดยสูตรที่ใช้คือ
HM x buckets x factorโดย HM คือค่าที่คืนมาจาก Hamonic mean โดยเฉลี่ยจากค่ามากสุดใน bucket ทุกอันเช่นเคย จากตัวอย่าง 32 buckets จะได้
32 / sum of (1 / (2 ^ k))โดย
- k คือค่ามากสุดที่เก็บในแต่ละ bucket
ส่วน buckets และ factor นี่เหมือนของ LogLog เลย
ได้ค่าการนับมาแล้ว ยังเอาไปใช้ไม่ได้ครับ ยังมีเงื่อนไขอีก 2 ข้อ คือ
- ถ้าผลลัพธ์ น้อยกว่า (2.5 x buckets) และมี bucket ที่เก็บค่า 0 (คือไม่มี hash ออกมาแล้วตก bucket นี้เลย คือกรณี buckets ทั้งหมดไม่ถูกเติม) ให้คืนค่า
(-buckets) x log(V / 32)โดย V คือจำนวน bucket ที่เก็บค่า 0
* เลข 2.5 มาจากค่าคงที่ที่มาจาก Linear counting(http://dblab.kaist.ac.kr/Prof/pdf/ACM90_TODS_v15n2.pdf)
- และถ้าผลลัพธ์(E)มีค่ามากกว่า (2^(buckets))/30 (เพื่อเช็คกรณี hash คืนค่าซ้ำกัน)ให้คืนค่า
(2 ^ buckets) x log(1 - (E / 2 ^ buckets))ซึ่งเลข (2^(buckets))/30 กับสูตร ก็มาจาก Linear couting เช่นกัน
ถ้าไม่ตกสองเงื่อนไขนี้ ก็ใช้ค่าผลลัพธ์ที่ได้เลย
แล้วมันก็เรียกว่า HyperLogLog (https://stefanheule.com/papers/edbt13-hyperloglog.pdf)
จาก standard error ด้านบน สมมติว่ามี 1024 buckets ก็จะเป็น 0.03 หรือ 3% น้อยกว่า Super-LogLog นิดนึงง
ถามว่ายังมีดีกว่านี้อีกไหม
ตอบว่า มีครับ!!
มี HyperLogLog++ ครับ โดยการปรับปรุงหลักๆ คือ ใช้ hash function 64 bit และข้อปรับปรุงเงื่อนไขใน range ของข้อมูล อีก 1–2 ข้อ เพื่อปรับปรุงความแม่นยำและการใช้ memory
ตรงนี้ผมยังไปไม่ถึงครับ แค่อ่านและทำความเข้าใจ paper ของ LogLog และ HyperLogLog ก็อ้วกละครับ ซึ่งจริงๆ เรื่อง HyperLogLog++ นี่อยู่ใน paper เดียวกับ HyperLogLog ครับ
Implementation
สรุป
ถึงแม้ว่าเทคนิคตรงนี้ จะทำงานได้เร็วและไม่ต้องใช้ memory เยอะ แต่สิ่งที่ต้องแลกมาก็คือเรื่องความถูกต้องของข้อมูล และมันไม่สามารถที่จะดึงข้อมูลกลับมาได้ เพราะส่วนใหญ่จะถูก hash ไว้ แล้วบันทึก เพราะฉะนั้นก่อนจะเอาเทคนิคเหล่านี้ไปใช้งาน ควรจะประเมินความเสี่ยงตรงนี้ก่อน
สำหรับการ implement ผมมองว่า เครื่องมือที่พร้อมที่สุดตอนนี้ คือ Redis ที่แทบจะทำงานได้เร็วพอๆ กับ ram เลย มี modules ที่พร้อมใช้งาน บางอันก็ต้องติดตั้งเพิ่ม บางอันก็พร้อมใช้เลย และผมเองก็เพิ่งมาค้นเจอว่า มี module อีกตัว tdigest ไว้จัดอันดับจำนวนสำหรับการทำงานกับ streaming data ซึ่งผมว่าน่าจะได้ใช้ประโยชน์อีกเหมือนกัน
จบครับ!!
