積分排行榜

需求

積分排行榜是 Redis 的經典應用。

倘若數據都存在數據庫中，每次訪問網頁都需要對所有的數據做排序，對于日訪問量大的網站來說，不僅服務器吃不消，用戶體驗也不佳。在 Redis 中提供了 sorted set 數據結構——有序集合，其底層實現是跳表，因此插入和刪除的效率都很高，適用于需實時排序的場景，游戲中的積分排行榜就是一個例子。

ZSET 命令簡介

針對有序集合，Redis 準備了一系列的命令，實現排行榜需要了解相關命令的使用。

1. ZADD：添加新的元素，用法如下：ZADD key score member [score member …] key 表示有序集合的鍵名；member 即是元素數據，score 表示元素的積分。內部主要是按 member 和 score 來排序。
2. ZRANGE：按分數從低到高返回給定排名區(qū)間的元素，用法如下：ZRANGE key start stop [WITHSCORES] start 表示起始排名，stop 為終止排名。ZRANGE 的實現也不難，類二分搜索即可。TODO
3. ZREVRANGE：按分數從高到低返回給定排名區(qū)間的元素，用法和上面的一樣。
4. ZRANK：返回某個元素的排名，用法如下：ZRANK key member 原理類似，類二分搜索 TODO。

實現

拿論壇距離，需要在論壇首頁展示最熱的幾個帖子，這些熱帖會經常更新的。當某個帖子被訪問時，對于帖子的訪問次數，除了寫數據庫之外，還要寫 Redis，即更新 score。

用 python 寫一個 leaderboard：

# -*- coding: utf-8 -*-
#!/usr/bin/python
import redis
class Leaderboard:
    def __init__(self,host,port,key,db):
        self.host = host
        self.port = port
        self.key = key
        self.db = db
        self.r = redis.StrictRedis(host=self.host,port=self.port,db=self.db)
    def isRedisValid(self):
        return self.r is None
    def addMember(self,member,score):
        if self.isRedisValid():
            return None
        return self.r.zadd(self.key,score,member)
    def delMember(self,member):
        if self.isRedisValid():
            return None
        return self.r.zrem(self.key,member)
    def incrScore(self,member,increment):
        """increase score on specified member"""
        if self.isRedisValid():
            return None
        return self.r.zincrby(self.key,member,increment)
    def getRankByMember(self,member):
        """Get ranking by specified member."""
        if self.isRedisValid():
            return None
        return self.r.zrank(self.key,member)
    def getLeaderboard(self,start,stop,reverse,with_score):
        """Return the whole leaderboard."""
        if self.isRedisValid():
            return None
        return self.r.zrange(self.key,start,stop,reverse,with_score)
    def getLeaderboardByPage(self,item_per_page,page_num,reverse=False,with_score=False):
        """Return part of leaderboard configurably."""
        # fix parameters
        if item_per_page <= 0:
            item_per_page = 5
        if page_num <= 0:
            page_num = 1
        # note: it is possible that return value is empty list.
        return self.getLeaderboard((page_num-1)*item_per_page,
                                    page_num*item_per_page-1,
                                            reverse,with_score)
    def getWholeLeaderboard(self,reverse=False,with_score=False):
        """Return the whole leaderboard."""
        return self.getLeaderboard(0,-1,reverse,with_score)

性能

訪問論壇首頁的時候，就可以直接從 Redis 直接獲取最熱的帖子，返回某個帖子的排名復雜度為 O(logN * m)，其中 N 為跳表的長度，m 為匹配長度。