本文介绍如何使用hll插件实现根据用户喜好推荐相关内容。

背景信息

推荐系统在互联网应用中主要用于提升用户粘性、提高转化率,常见场景如下:

  • 电商网站根据用户购买习惯,推荐商品。
  • 音乐网站根据用户收听喜好,推荐音乐。
  • 新闻网站根据用户浏览习惯,推荐新闻。
  • 应用网站根据用户下载和使用应用习惯,推荐应用。

本文以音乐网站为例介绍如何设计推荐系统数据库,以及不同设计方法的差异。

设计背景

  1. 用户(uid)完整听完的歌曲(vid),该歌曲有对应的标签(tags),同时一个歌曲可以有多个标签,由此形成映射关系:
    uid ->> tags ->> musics    
  2. 根据用户每个tag下的歌曲数排行,得到tag热度:
    tag(count distinct music)    
    ...   
  3. 统计前5个tag及权重:
    tag1:40%    
    tag2:20%    
    tag3:15%    
    tag4:15%    
    tag5:10%  
  4. 从tag标签的歌曲库中,排除用户听过的,然后根据这些歌曲的推荐权重(例如播放次数倒排),按比例推荐新的歌曲。

普通设计

该设计适合所有数据库,但是缺点是当数据量庞大时,可能会使用聚合查询,效率较低。示例如下:

create table t_like(     
uid int,  -- 用户ID    
tagid int,  -- 歌曲标签ID   
vid int,   -- 歌曲ID    
mod_time timestamp,  -- 最后一次更新时间, 仅与上次时间超过1天时更新。    
primary key (uid,tagid,vid)     
);    
    
insert into t_like values (:uid, :tagid, :vid, :mod_time)     
 on conflict (uid,tagid,vid) do update    
set mod_time=excluded.mod_time    
where    
excluded.mod_time - t_like.mod_time > interval '1 day'    
;    
    
-- 统计最近1天的top 10的tag。    
select tagid, count(*) from t_like     
where uid=:uid     
and now()-mod_time < interval '1 day'  
group by tagid     
order by count(*) desc limit 10;    

压力测试示例如下:

vi test.sql  
\set uid random(1,50000)    
\set tagid random(1,5000)    
\set vid random(1,10000000)    
insert into t_like values (:uid, :tagid, :vid, now())     
 on conflict (uid,tagid,vid) do update    
set mod_time=excluded.mod_time    
where    
excluded.mod_time - t_like.mod_time > interval '1 day';    
  
pgbench -M prepared -n -r -P 1 -f ./test.sql -c 32 -j 32 -T 240  
  
transaction type: ./test.sql  
scaling factor: 1  
query mode: prepared  
number of clients: 32  
number of threads: 32  
duration: 240 s  
number of transactions actually processed: 80975327  
latency average = 0.095 ms  
latency stddev = 0.340 ms  
tps = 337396.279382 (including connections establishing)  
tps = 337406.018908 (excluding connections establishing)  
statement latencies in milliseconds:  
         0.000  \set uid random(1,50000)    
         0.000  \set tagid random(1,5000)    
         0.000  \set vid random(1,10000000)    
         0.094  insert into t_like values (:uid, :tagid, :vid, now())    
  
db1=# select tagid, count(*) from t_like     
where uid=1        
and now()-mod_time < interval '1 day'  
group by tagid     
order by count(*) desc limit 10;    
 tagid | count   
-------+-------  
  2519 |     4  
  3049 |     4  
  3648 |     4  
  1777 |     3  
  1352 |     3  
  1491 |     3  
  1064 |     3  
   572 |     3  
   692 |     3  
   301 |     3  
(10 rows)  
  
Time: 3.947 ms  

基于hll近似计算的设计

使用hll来存储用户(uid)听完的歌曲ID(vid),相比普通设计有如下优势:

  • 数据量小,使用近似hll hash聚集代替真实值。
  • 查询效率高,支持索引,不需要计算,毫秒响应。
  • 支持hash union、add等操作,适合滑窗计算,满足更多业务需求。
说明 hll插件使用方法请参见基数统计(hll)
  1. 每个标签存储一个hll,hll里面存储的是该标签内用户完整听完的歌曲的ID hash值。
    create table t_like (    
    uid int,     
    tagid int, -- 标签    
    w1 hll, w1_mod_time timestamp, -- 周一听完的歌曲对应的vid构成的hash。   
    w2 hll, w2_mod_time timestamp, -- 周二听完的歌曲对应的vid构成的hash。
    w3 hll, w3_mod_time timestamp, -- 周三听完的歌曲对应的vid构成的hash。    
    w4 hll, w4_mod_time timestamp, -- 周四听完的歌曲对应的vid构成的hash。    
    w5 hll, w5_mod_time timestamp, -- 周五听完的歌曲对应的vid构成的hash。    
    w6 hll, w6_mod_time timestamp, -- 周六听完的歌曲对应的vid构成的hash。    
    w7 hll, w7_mod_time timestamp, -- 周日听完的歌曲对应的vid构成的hash。    
    whole hll,                   -- 所有    
    primary key (uid,tagid)    
    );  
    说明 w1~w7是根据业务设置的,如果业务只关心1天的数据,就只需要设置一个字段。
  2. 当用户听完一首歌, 把这个写入当前日期对应字段,当对应字段已经有value,并且最后修改时间不是今天时,覆盖该value,否则追加hash。使用的是insert into on conflict语法,示例如下:
    -- 设置观看历史行为hash。    
    insert into t_like (    
    uid,    
    tagid,    
    w5,     
    w5_mod_time,    
    whole    
    )    
    values (    
    1,  -- uid    
    200,  -- 标签ID  
    hll_hash_integer(12346)||hll_empty(),  -- 观看过的vid, 多个则继续。   
    now(),     
    hll_hash_integer(12346)||hll_empty()   -- 观看过的vid    
    )    
    on conflict (uid,tagid)     
    do update    
    set w5=    
    case     
    when date(t_like.w5_mod_time) <> current_date     
    then excluded.w5     
    else hll_union(coalesce(t_like.w5,hll_empty()), excluded.w5)    
    end,    
    w5_mod_time = excluded.w5_mod_time,    
    whole = hll_union(coalesce(t_like.whole,hll_empty()), excluded.whole)    
    where    
    hll_union(coalesce(t_like.w5,hll_empty()), excluded.w5) <> coalesce(t_like.w5,hll_empty())    
    or    
    hll_union(coalesce(t_like.whole,hll_empty()), excluded.whole) <> coalesce(t_like.whole,hll_empty())    
    ;    
    说明 实际业务中也可以批量合并更新,针对单个用户的单个标签聚合更新,使用hll union降低更新率。
  3. 查询uid 1最近2天的top 10标签,示例如下:
    select tagid,     
    hll_cardinality( hll_union(coalesce(w4,hll_empty()), coalesce(w5,hll_empty())) ) as vids     
    from t_like    
    where uid = 1    
    order by 2 desc limit 10;    
        
        
        
     tagid | vids     
    -------+------    
       200 |    2    
    (1 row)    
  4. 创建索引,示例如下:
    create index idx_t_like_1 on t_like (uid, hll_cardinality( hll_union(coalesce(w4,hll_empty()), coalesce(w5,hll_empty())) ));
  5. 查看执行计划,示例如下:
    postgres=# explain select tagid,     
    hll_cardinality( hll_union(coalesce(w4,hll_empty()), coalesce(w5,hll_empty())) ) as vids    
    from t_like    
    where uid = 1    
    order by 2 desc limit 10;    
                                            QUERY PLAN                                             
    -------------------------------------------------------------------------------------------    
     Limit  (cost=0.11..0.15 rows=1 width=12)    
       ->  Index Scan Backward using idx_t_like_1 on t_like  (cost=0.11..0.15 rows=1 width=12)    
             Index Cond: (uid = 1)    
    (3 rows)    
  6. 写入几千万数据,进行压力测试,示例如下:
    vi test.sql    
    \set uid random(1,50000)    
    \set tagid random(1,5000)    
    \set vid random(1,10000000)    
    insert into t_like (    
    uid,    
    tagid,    
    w5,     
    w5_mod_time,    
    whole    
    )    
    values (    
    :uid,    
    :tagid,    
    hll_hash_integer(:vid)||hll_empty(),    
    now(),    
    hll_hash_integer(:vid)||hll_empty()    
    )    
    on conflict (uid,tagid)     
    do update    
    set w5=    
    case     
    when date(t_like.w5_mod_time) <> current_date     
    then excluded.w5     
    else hll_union(coalesce(t_like.w5,hll_empty()), excluded.w5)    
    end,    
    w5_mod_time = excluded.w5_mod_time,    
    whole = hll_union(coalesce(t_like.whole,hll_empty()), excluded.whole)    
    where    
    hll_union(coalesce(t_like.w5,hll_empty()), excluded.w5) <> coalesce(t_like.w5,hll_empty())    
    or    
    hll_union(coalesce(t_like.whole,hll_empty()), excluded.whole) <> coalesce(t_like.whole,hll_empty())    
    ;    
        
        
    pgbench -M prepared -n -r -P 1 -c 32 -j 32 -T 120 -f ./test.sql    

    测试结果如下:

    transaction type: ./test.sql    
    scaling factor: 1    
    query mode: prepared    
    number of clients: 32    
    number of threads: 32    
    duration: 120 s    
    number of transactions actually processed: 24636321    
    latency average = 0.156 ms    
    latency stddev = 0.339 ms    
    tps = 205301.110313 (including connections establishing)    
    tps = 205354.851711 (excluding connections establishing)    
    statement latencies in milliseconds:    
             0.001  \set uid random(1,5000000)    
             0.001  \set tagid random(1,5000)    
             0.000  \set vid random(1,10000000)    
             0.154  insert into t_like (    
  7. 查询某个uid的标签热度排序,示例如下:
    postgres=# select tagid,     
    hll_cardinality( hll_union(coalesce(w4,hll_empty()), coalesce(w5,hll_empty())) ) as vids    
    from t_like    
    where uid = 1    
    order by 2 desc limit 10;    
     tagid | vids     
    -------+------    
       200 |    2    
      1413 |    1    
      1996 |    1    
      2642 |    1    
      3664 |    1    
      4340 |    1    
    (6 rows)    
        
    Time: 0.688 ms    
    说明 响应时间为0.688毫秒。

其他需求,例如过滤用户已经听过的歌曲:

  • 判断一个歌曲ID(vid)是否在这个hash里面,不精确操作。示例如下:
    postgres=# select whole || hll_hash_integer(1) = whole        
    from     
    t_like     
    where uid=1 and tagid=200;  -- 返回false表示不包含vid:1。    
     ?column?     
    ----------    
     f    
    (1 row)    
        
    postgres=# select whole || hll_hash_integer(12345) = whole     
    from     
    t_like     
    where uid=1 and tagid=200;   -- 返回true表示包含vid:12345。    
     ?column?     
    ----------    
     t    
    (1 row)    
  • 判断一个歌曲ID(vid)是否在这个hash里面,精确操作。建表语句示例如下:
    create table t_like_lossless (    
    uid int,    
    vid int,    
    primary key (uid,vid)    
    );    
    说明 primary key查询速度非常快。