用hll插件根据用户喜好推荐相关内容_云数据库 RDS(RDS)-阿里云帮助中心

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

背景信息

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

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

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

设计背景

用户（uid）完整听完的歌曲（vid），该歌曲有对应的标签（tags），同时一个歌曲可以有多个标签，由此形成映射关系：
```
uid ->> tags ->> musics    
```
根据用户每个tag下的歌曲数排行，得到tag热度：
```
tag(count distinct music)    
...   
```

统计前5个tag及权重：

tag1:40%    
tag2:20%    
tag3:15%    
tag4:15%    
tag5:10%

从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）。

每个标签存储一个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天的数据，就只需要设置一个字段。

当用户听完一首歌, 把这个写入当前日期对应字段，当对应字段已经有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降低更新率。

查询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)

创建索引，示例如下：

create index idx_t_like_1 on t_like (uid, hll_cardinality( hll_union(coalesce(w4,hll_empty()), coalesce(w5,hll_empty())) ));

查看执行计划，示例如下：

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)

写入几千万数据，进行压力测试，示例如下：

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 (

查询某个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查询速度非常快。