Build a news feed in Redis (fan-out-on-write aka Push model)

但是好像用 Cassandra 會比較適合?

--

可以用 sorted set 來儲存每個用戶的 news feed
用作品的 created_at timestamp 當 score
保持每個 set 的容量為 800 之類的

當用戶發佈了作品之後

就透過 message queue 把這個作品的 id 寫入該用戶的所有 followers 的 news feed 裡
或許也可以只寫入到所謂的 "active users"(例如七天內登入過的用戶)的 news feed 裡
因為明星級的用戶可能有很大量的 followers

news_feed:user_183 = [
user_8:song:5232, 8783421
user_2:song:432, 8509823
user_4:photo:23, 8323490
user_7:album:1232, 5323453
...
]

用 message queue 把作品 id 寫入各用戶的 news feed 時
或許也可以區分活躍用戶與非活躍用戶
活躍用戶的 task 的優先權比較高

當 A 用戶 follow 了 B 用戶之後

可以先取出 A 用戶的 news feed 的最後一個項目
看它的 created_at 是多少
然後撈出 B 用戶的比這個 created_at 還新的作品
接著寫入 A 用戶的 news feed
最後在 truncate 一下(用 ZREMRANGEBYRANK 指令)只保留 800 個項目

當用戶刪除了作品之後

可能有幾種做法:

一是在刪除之後就透過 message queue 遍歷所有 followers 的 news feed
然後把該作品刪掉(用 ZREM 指令)
但是仍然可能遇到還沒刪完就有用戶去讀自己的 news feed 的情況

二是在用戶讀自己的 news feed 的時候才檢查
假設是用 redis 的 list 或 sorted set
一開始就直接讀出 list 裡的 id 列表(當然會分頁)
然後根據 id 再去 mysql 裡撈出真正的 model(例如歌曲、專輯、照片等)
然後檢查有沒有哪些項目被標示為刪除了(假設是虛刪)
有的話就從 redis list 中刪掉
然後再撈下一個分頁的資料來補足
如果還是有應該被刪掉的資料就再重複整個過程

三是幫每個作品維護一個「哪些用戶的 news feed 會有這個作品」的 list
http://stackoverflow.com/questions/12357770/how-to-implement-user-feed-like-in-twitter-or-facebook-on-redis

當然這些方法一起用可能會更好

這裡的刪除可能不只是作品本身被刪除
也可能是 A 用戶 unfollow 了 B 用戶
所以也要把 B 用戶的作品從 A 用戶的 news feed 中刪掉
這個情況的話
似乎只能遍歷 A 用戶的 news feed 來刪掉 B 用戶的作品了?

ref:
http://highscalability.com/blog/2013/10/28/design-decisions-for-scaling-your-high-traffic-feeds.html

Redis 可以用來幹嘛?

Data Types

string
list
set
sorted set
hash (dict)
publish / subscribe

Redis 数据结构使用场景
http://get.jobdeer.com/523.get

谈 Redis 应用场景
http://www.qixing318.com/article/talking-about-redis-application-scenario.html

List 就是链表,相信略有数据结构知识的人都应该能理解其结构。使用Lists结构,我们可以轻松地实现最新消息排行等功能。Lists的另一个应用就是消息队列,可以利用Lists的PUSH操作,将任务存在Lists中,然后工作线程再用POP操作将任务取出进行执行。

Set 集合的概念就是一堆不重复值的组合。利用Redis提供的Sets数据结构,可以存储一些集合性的数据,比如在微博应用中,可以将一个用户所有的关注人存在一个集合中,将其所有粉丝存在一个集合。Redis还为集合提供了求交集、并集、差集等操作,可以非常方便的实现如共同关注、共同喜好、二度好友等功能

Sorted Set 可以通过用户额外提供一个优先级(score)的参数来为成员排序,并且是插入有序的,即自动排序。当你需要一个有序的并且不重复的集合列表,那么可以选择sorted set数据结构,比如twitter 的public timeline可以以发表时间作为score来存储,这样获取时就是自动按时间排好序的。

Pub/Sub 从字面上理解就是发布(Publish)与订阅(Subscribe),在Redis中,你可以设定对某一个key值进行消息发布及消息订阅,当一个key值上进行了消息发布后,所有订阅它的客户端都会收到相应的消息。这一功能最明显的用法就是用作实时消息系统,比如普通的即时聊天,群聊等功能。

Redis 可以用來幹嘛?

大部分情況並不是用 redis 來「取代」資料庫
資料庫其實還是建議用 mysql
只是拿 redis 儲存相對不重要的資料
通常會把統計、計數的部份獨立出來用 redis 處理

How to take advantage of Redis just adding it to your stack?
http://oldblog.antirez.com/post/take-advantage-of-redis-adding-it-to-your-stack.html

Redis 在电商中的实际应用场景
http://kenny7.com/2012/09/redis-usage-scenario.html

列出最新的 20 則評論

SQL 可能是 SELECT * FROM foo WHERE ... ORDER BY created_at DESC LIMIT 20

可以改用 redis 的 list
假設我們有一個叫 latest.comments 的 redis list
可以 trim 這個 list 最多只記錄 20 個 item
每當一個 comment 被新增到資料庫之後
就 push comment id 到 redis list(LPUSH)
這樣每次我只要去撈 latest.comments 取出 comment ids
然後去資料庫把這些 comments 一次撈出來就好了

如果是要列出不同目錄下的最新 30 則文章
其實可以每個目錄都建立一個 redis list

當 sql 的條件很複雜的時候
就可以考慮改用 redis list 了

按 score 排行榜

可以使用 redis sorted set
sorted set 是當你把資料放進去的時候就排序了(用 score 來排序)

ZADD leaderboard <score> <username>

# get the top 100 users by score
ZREVRANGE leaderboard 0 99

# tell the user its global rank
ZRANK leaderboard <username>

Counter

INCR page_view:song:123

統計特定時間內的瀏覽人數

统计 10 分钟内在线用户数
http://lztian.com/blog/3170.html

daily unique user using bitmap
http://wbj0110.iteye.com/blog/2040189

Notification

redis> HSET user:<userId>:message:ur system 1//1条未读系统消息
(integer) 1
redis> HINCRBY user:<userId>:message:ur system 1 //未读系统消息+1
(integer) 2
redis> HINCRBY user:<userId>:message:ur comment 1 //未读评论消息+1
(integer) 1
redis> HSET user:<userId>:message:ur system 0//设为系统消息已读
(integer) 1
redis> HGETALL user:<userId>:message:ur //获取这key hashkey 和value
1) "system"
2) "0"
3) "comment"
4) "1"
SUBSCRIBE key

Timeline / Feed

redis> ZADD user:100000:feed:topic  61307510400000 <feedId> //score 为timestamp
(integer) 1
redis> EXPIRE user:100000:feed:topic 24*60*60 //set timeout to one day
(integer) 1
redis> ZADD user:100000:feed:friend 61307510400000 <feedId> //不同类型feed
(integer) 1
redis> EXPIRE user:100000:feed:friend 24*60*60 //set timeout
(integer) 1

用 Redis 做來排行榜統計

熱門藝人
熱門歌曲
熱門專輯
熱門播放清單
即時、每日、每週、每月、所有時間

from datetime import date, datetime, timedelta

from pytz import timezone

from svapp.redis import rdb


def get_last_iso_year_and_week(the_date):
    """
    計算 ISO 定義下的上一週
    """

    d = the_date - timedelta(weeks=1)
    year = d.isocalendar()[0]
    week = d.isocalendar()[1]

    return year, week


def get_weekday_start_and_end(iso_year, iso_week):
    """
    ISO 的定義是每週的第一天是禮拜一
    The Jan 4th must be in week 1 according to ISO
    """

    d = date(iso_year, 1, 4)
    start_date = d + timedelta(weeks=(iso_week - 1), days=-d.weekday())
    end_date = start_date + timedelta(days=6)

    return start_date, end_date


def ndays_later(n, timezone_str='Asia/Taipei'):
    """
    n 天後的日期

    n = 0 表示今天
    n = 1 表示明天(一天後)
    n = 2 表示後天(兩天後)
    n = -1 表示昨天
    """

    tz = timezone(timezone_str)
    the_date = datetime.now(tz) + timedelta(n)

    return the_date


def date_key(n=0):
    """
    默認回傳今天的 date_key

    格式 20140602
    """

    the_date = ndays_later(n)
    key = the_date.strftime('%Y%m%d')

    return key


"""
各 counter type 的加權參數
TODO: 這些數值要再想一下
"""
COUNTER_TYPES = {
    'view': 0.5,
    'play': 1,
    'play_full': 2,
    'embed_play': 1,
    'embed_play_full': 2,
    'like': 3,
    'add_to_playlist': 4,
}


def check_counter_type(counter_type):
    if counter_type not in COUNTER_TYPES.keys():
        raise RuntimeError


def increase_song_counter(song, counter_type):
    """
    用 hash 儲存歌曲的各種 counter

    範例:
    counter:song:978
    {
        'view': 1244.5,
        'play': 456,
        'play_full', 211,
        ...
    }
    """

    check_counter_type(counter_type)

    key = 'counter:song:%s' % (song.id)
    rdb.hincrby(key, counter_type, 1)


def update_song_leaderboard(song, counter_type):
    """
    用 sorted set 儲存當日的歌曲排行榜
    這個排行榜是即時更新的
    """

    inc = COUNTER_TYPES[counter_type]
    style_ids = (0, song.style)
    for style_id in style_ids:
        key = 'leaderboard:song:style:%s:realtime' % (style_id)
        rdb.zincrby(key, song.id, inc)

        # 這個資料應該每天 achive 存進 mysql
        key = 'leaderboard:song:style:%s:%s' % (style_id, date_key())
        rdb.zincrby(key, song.id, inc)


def trim_leaderboard(key, topN):
    """
    只保留 sorted set 的 top 100
    rdb.zremrangebyrank(key, 0, -101)
    """

    value = -abs(topN) - 1
    rdb.zremrangebyrank(key, 0, value)


def get_song_leaderboard(when='realtime', style_id=0, topN=20):
    if isinstance(when, (date, datetime)):
        when = when.strftime('%Y%m%d')

    key = 'leaderboard:song:style:%s:%s' % (style_id, when)

    result = rdb.zrevrange(key, 0, topN - 1, withscores=True)

    return result


def get_song_leaderboard_weekly(year, week, style_id=0, topN=20):
    """
    TODO:
    1. 檢查 week_key 是否已存在
    2. 在 update_song_leaderboard() 的時候就直接建 week 和 month 的 key,這樣就不需要 zunionstore
    """

    week_key = 'leaderboard.week:song:style:%s:%s%02d' % (style_id, year, week)

    start_date, end_date = get_weekday_start_and_end(year, week)
    date_range = [start_date + timedelta(days=n) for n in xrange(0, 6)]
    date_range_keys = ['leaderboard:song:style:%s:%s' % (style_id, d.strftime('%Y%m%d')) for d in date_range]

    rdb.zunionstore(week_key, date_range_keys)

    result = rdb.zrevrange(week_key, 0, topN - 1, withscores=True)

    return result


def get_song_leaderboard_monthly(year, month, style_id=0, topN=20):
    """
    TODO: 檢查 month_key 是否已存在
    """

    # leaderboard.monthly:song:style:0:201406
    month_key = 'leaderboard.month:song:style:%s:%s%02d' % (style_id, year, month)

    search = 'leaderboard:song:style:%s:%s%02d??' % (style_id, year, month)
    day_keys = rdb.keys(search)
    rdb.zunionstore(month_key, day_keys)

    result = rdb.zrevrange(month_key, 0, topN - 1, withscores=True)

    return result