Redisを使ったレコメンド機能の実装

それRedisでできるよ、期でしょうか。最近Redisでレコメンド機能をつくってみたのでご紹介です。

ここで”レコメンド機能”というのは、 Amazonでいう”この商品を見たお客様はこれも見ています”や、ブログの関連記事を出す機能のこと。

user:1がproduct:Aをみたときに、product:Aに似ているproduct:Bをレコメンドしたい。 product:Aとproduct:Bがどれくらい似ているか:類似度を算出した後は、 Redis得意のSorted Setを使って類似度のランキングをつくれば似ているproductを出すことができます。

類似度の算出にはいろいろ方法があるようですが、 Redisのデータ構造と相性のよい Jaccard [wikipedia]という方法を使いました。

この例に適用すれば、 product:Aを見たユーザー群(RedisのSet)と、product:Bを見たユーザー群があった時に、類似度 = (product:Aとproduct:Bを両方見た人数) / (product:Aまたはproduct:Bのいずれかを見た人数) となります。

productページを見た時に、ユーザーIDをproductのSetに追加しておけば、

SADD product:A user:1

類似度は

similarity = count(SINTER product:A product:B) / count(SUNION product:A product:B)

となります。

これをSorted Setに入れておきます。 AとBが似ているならばBとAも似ているので逆方向も。

ZADD similarity:product:A similarity product:B
ZADD similarity:product:B similarity product:A

similarity:product:A には、product:Aに似たproductのIDが入っているので似ている順に10件とるのはお得意の

ZREVRANGE similarity:product:A 0 9

さらに、ただいまなんでもluaスクリプト期でもあるので、Redisのluaスクリプティングを使いたくなる理由を考えます。

SINTERとSUNIONは、Set同士のそれぞれANDとORをとって、その結果得られるSetの要素を返してくれますが、ここで欲しいのは要素ではなく、要素数。残念ながら、SINTER,SUNIONした結果の要素数だけとる方法はありません。しかも要素数は単純に割り算した後すぐにSorted SetにZADDします。これはアプリケーション側でやらずにRedis側でやった方が速そうです。

下につけたluaスクリプトを書けばこう書けます。

EVALSHA {sha1} 0 similarity:product:A product:A product:B product:B

product:A Setとproduct:B Setの類似度を計算し similarity:product:A Sorted Setにその類似度をスコアとしてproduct:Bを追加します。

-- sjaccardstore( 'j:sim:u:1', 'sim:u:1', 'sim:u:2', 'u:2' )
local function sjaccardstore( destination1, set1, set2, member1 )
    local sinter_count = 0
    local sunion_count = 0
    do
        -- minimize scope for tables
        local sinter = redis.call( 'sinter', set1, set2 )
        sinter_count = #sinter
    end
    do
        local sunion = redis.call( 'sunion', set1, set2 )
        sunion_count = #sunion
    end

    local jaccard = 0
    if sunion_count ~= 0 then
        jaccard = sinter_count / sunion_count
    end

    if jaccard ~= 0 then
        redis.call( 'zadd', destination1, jaccard, member1 )
    else
        redis.call( 'zrem', destination1, member1 )
    end

    -- lua number converts to redis integers
    -- we want float, so return string
    return jaccard
end
return tostring( sjaccardstore( ARGV[1], ARGV[2], ARGV[3], ARGV[4] ) )

-- sjaccardstorebothways( 'j:sim:u:1', 'j:sim:u:2', 'sim:u:1', 'sim:u:2', 'u:2', 'u:1' )
local function sjaccardstorebothways( destination1, destination2, set1, set2, member1, member2 )
    local jaccard = sjaccardstore( destination1, set1, set2, member1 )
    if jaccard ~= 0 then
        redis.call( 'zadd', destination2, jaccard, member2 )
    else
        redis.call( 'zrem', destination2, member2 )
    end

    return jaccard
end
return tostring( sjaccardstorebothways( ARGV[1], ARGV[2], ARGV[3], ARGV[4], ARGV[5], ARGV[6] ) )

RedisのCPUがあまってるならluaスクリプティングもいいんじゃないでしょうか。 wallclock timeで10倍くらい高速ですし。

        s/iter jaccard  sunion  sinter     lua
jaccard   3.85      --    -35%    -69%    -91%
lua      0.334   1051%    645%    255%      --

ベンチマークスクリプトはこちら