Skip to content

ทำ Ranking/Leaderboard ด้วย Redis #1

โจทย์ของผมคือผมต้องการ

  1. Ranking ที่อัปเดตแบบ real-time
  2. ไม่ query จาก database โดยตรงและ query บ่อยๆ
  3. Rank หรืออันดับสามารถซ้ำได้

จากข้อ 3 อันดับซ้ำกันได้มี 2 แบบ ตัวอย่างเช่น

แบบที่ 1 non-skipped ranking

แบบที่ 2 skipped ranking

ที่ผมต้องการคือแบบที่ 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 นั่นแหละเพราะฉะนั้นขั้นตอนการทำงานของอัลกอริทึมจะเป็นดังนี้

  1. get score ด้วย userId ด้วยคำสั่ง   zscore ranking user03  จะได้ score 900
  2. นับจำนวนคนก่อนหน้าที่มีคะแนนมากกว่า 900   zcount ranking (900 +inf 
  3. เอาจำนวนจากข้อ 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  ได้

  1. zrangebyscore ranking (900 +inf withscores limit 0 1
  2. เอาข้อมูลที่ได้จาก 1 ไปคำนวณด้วยอัลกอริทึมหา rank ด้วย score ก่อนหน้านี้

จากข้อ 1 เราควรจะได้ ["user02", "1000"]  ซึ่งเมื่อคำนวณ rank ก็จะได้ rank #1 ส่วนการหา lower rank ก็ทำคล้ายกันแต่เปลี่ยนไปใช้คำสั่ง zrevrangebyscore  แทน จะได้

  1. zrevrangebyscore ranking (900 -inf withscores limit 0 1
  2. เอาข้อมูลที่ได้จาก 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 ดูครับ

 

One Comment

Leave a Reply

Your email address will not be published.