โจทย์ของผมคือผมต้องการ
- Ranking ที่อัปเดตแบบ real-time
- ไม่ query จาก database โดยตรงและ query บ่อยๆ
- Rank หรืออันดับสามารถซ้ำได้
จากข้อ 3 อันดับซ้ำกันได้มี 2 แบบ ตัวอย่างเช่น
แบบที่ 1 non-skipped ranking
#1, user01 score 1000 #1, user02 score 1000 #2, user03 score 900 #2, user04 score 900 #3, user05 score 800
แบบที่ 2 skipped ranking
#1, user01 score 1000 #1, user02 score 1000 #3, user03 score 900 #3, user04 score 900 #5, user05 score 800
ที่ผมต้องการคือแบบที่ 2 คืออันดับมีการข้ามได้ตามจำนวนคนของ rank ก่อนหน้าที่ซ้ำกัน จากตัวอย่างอันดับ 1 คะแนน 1000 ผู้เล่นที่มีคะแนน 900 มีคะแนนเป็นอันดับ 2 ก็จริงแต่อันดับ 1 มี 2 คนทำให้อันดับข้ามไป เป็นอันดับ 3 แทน
การทำ ranking ไม่มีอะไรซับซ้อนก็แค่ sort by score จากมากไปน้อยก็จริงๆ แต่ถ้าต้อง query database ทุกครั้งคงไม่ดีแน่ๆ ผมต้องการให้มันทำงานได้เร็วและ database ไม่ทำงานหนักด้วยเลยใช้ Redis เพราะ 1) เป็น in memory cache ทำงานเร็ว 2) มี data structure ให้ใช้ ที่น่าสนใจคือ “Sorted Set” ซึ่งข้อดีคือข้อมูลที่มีการเรียงลำดับไว้แล้วแบบนี้เราสามารถทำงานด้วย time complexity O(log N) ได้
เครื่องมือครบแล้วทีนี้มาวิเคราะห์ข้อมูลก่อนออกแบบอัลกอริทึมกันสักหน่อย จากตัวอย่างข้อมูลแบบที่ 2 จะเห็นว่าอันกับ #3 คนแรกที่ถูกนับข้ามมามันก็คือ index ใน list นั่นแหละเพราะฉะนั้นขั้นตอนการทำงานของอัลกอริทึมจะเป็นดังนี้
- get score ด้วย userId ด้วยคำสั่ง zscore ranking user03 จะได้ score 900
- นับจำนวนคนก่อนหน้าที่มีคะแนนมากกว่า 900 zcount ranking (900 +inf
- เอาจำนวนจากข้อ 2 บวกด้วย 1 ก็จะได้ rank ของผู้เล่นที่มีคะแนน 900
จาก document ของ Redis คำสั่ง zscore นั้นใช้ O(1) ส่วน zcount ใช้ O(log N) เท่านั้นเอง time complexity ถือว่าโอเคแล้ว
มาดูอีกตัวอย่างที่ยากขึ้นมาหน่อย ตอนนี้เรามีอัลกอริทึมที่หา rank ด้วย score แล้ว ทีนี้ถ้าเราจะหา upper และ lower rank ที่อยู่ถัดจาก current rank ของเราจะทำยังไง?
สิ่งที่เราต้องทำคือหา score ที่มากกว่าและน้อยกว่า score ปัจจุบันไป 1 อันดับ เมื่อได้ score นั้นแล้วก็จะสามารถหา upper และ lower rank ได้โดยใช้อัลหอริทึมหา rank ด้วย score ข้างบน
หาลำดับที่อยู่สูงกว่าสามารถใช้ zrangebyscore ได้
- zrangebyscore ranking (900 +inf withscores limit 0 1
- เอาข้อมูลที่ได้จาก 1 ไปคำนวณด้วยอัลกอริทึมหา rank ด้วย score ก่อนหน้านี้
จากข้อ 1 เราควรจะได้ [“user02”, “1000”] ซึ่งเมื่อคำนวณ rank ก็จะได้ rank #1 ส่วนการหา lower rank ก็ทำคล้ายกันแต่เปลี่ยนไปใช้คำสั่ง zrevrangebyscore แทน จะได้
- zrevrangebyscore ranking (900 -inf withscores limit 0 1
- เอาข้อมูลที่ได้จาก 1 ไปคำนวณด้วยอัลกอริทึมหา rank ด้วย score ก่อนหน้านี้
ผลลัพธ์จาก zrevrangebyscore ในข้อ 1 ควรจะได้ [“user05”, “800”] และเมื่อคำนวณแล้วจะได้ rank #5
จาก document zrevrangebyscore และ zrangebyscore ใช้ time complexity O(log N + M) โดย M เป็นค่าคงที่เป็นจำนวน limit ที่เรากำหนดจากตัวอย่างนี้เราใช้ limit 0 1 หมายความว่า offset=0 และ limit=1 เราเลือกมาแค่ 1 ตัว เพราะฉะนั้น M จึงเท่ากับ 1
โพสต์นี้ผมให้เป็นตอนที่ 1 ไว้ก่อนแล้วกัน ถ้าขยันจะเขียนการทำ ranking โดยใช้ Redis โดยเรียงอันดับตามแบบที่ 1 non-skipped ranking ดูครับ
[…] “ทำ Ranking/Leaderboard ด้วย Redis #1” แล้วผมทำ ranking […]