代码拉取完成，页面将自动刷新
digoal
2020-02-28
PostgreSQL , 近似计算 , hll , hyperloglog , hash
推荐系统在互联网化的应用中是一个提升用户粘性、提高转化率的通用需求.
例如电商, 根据用户喜好, 推荐打折商品.
音乐网站, 根据用户听音习惯, 推荐音乐.
新闻网站, 根据用户浏览习惯, 推荐喜好的内容.
appstore网站, 根据用户下载和使用app习惯, 推荐app
... ...
下面以音乐网站为例子介绍如何设计推荐系统数据库, 以及不同设计方法的差异.
歌曲有对应的标签
一个歌曲可以有多个标签
用户听过什么歌曲(听完的)
形成一个一堆多的映射关系
uid ->> tags ->> musics
根据用户每个tag下的music数排行, 得到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'
;
-- 根据tag里面歌曲id的歌手, 统计最近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来存储uid听完的vid: (标签(hll), 标签n(hll)), 相比普通设计的优势很多
优势:
涉及PostgreSQL hll插件:
https://github.com/citusdata/postgresql-hll
每个标签存储一个hll, 这个hll里面存储的是在这个标签里面, 用户听完的歌曲的vid hashvalue.
create table t_like (
uid int,
tagid int, -- 标签
w1 hll, w1_mod_time timestamp, -- 周一听完的歌曲对应的vid 构成的hash, 周一
w2 hll, w2_mod_time timestamp, -- 周二 ...
w3 hll, w3_mod_time timestamp,
w4 hll, w4_mod_time timestamp,
w5 hll, w5_mod_time timestamp,
w6 hll, w6_mod_time timestamp,
w7 hll, w7_mod_time timestamp,
whole hll, -- 所有
primary key (uid,tagid)
);
这么设计主要是根据业务来, 业务如果只关心1天的, 那就不用搞这么多字段.
当用户听完一首歌, 把这个写入当前日期对应字段, 当对应字段已经有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 (
多跑几轮
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: 23988181
latency average = 0.160 ms
latency stddev = 0.335 ms
tps = 199900.214256 (including connections establishing)
tps = 199956.049571 (excluding connections establishing)
statement latencies in milliseconds:
0.001 \set uid random(1,50000)
0.000 \set tagid random(1,5000)
0.000 \set vid random(1,10000000)
0.158 insert into t_like (
当前记录数4747万条.
postgres=# select count(*) from t_like ;
count
----------
47473788
(1 row)
查询某个uid的标签热度排序, 0.688毫秒响应
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
其他需求: 判断一个vid是否在这个hash里面, 不精确操作. (用于过滤用户已经听过的歌曲)
select whole || hll_hash_integer(:vid) = whole
from
t_like
where uid=:uid and tagid=:tagid;
例如
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)
如果希望精确建议另外存一份精准值
create table t_like_lossless (
uid int,
vid int,
primary key (uid,vid)
);
这个是pk查询, 速度也是非常快的
阿里云即将支持hll插件. 欢迎试用, 现在可以9块9购买PG试用:
https://www.aliyun.com/database/postgresqlactivity
采用PostgreSQL hll近似hash功能, 实现了亿级别关系数据量下, 毫秒级别的推荐查询.
相比之下节省了存储空间, 同时响应速度从3.947毫秒 提升 到0.688毫秒.
https://github.com/citusdata/postgresql-hll
《PostgreSQL sharding : citus 系列6 - count(distinct xx) 加速 (use 估值插件 hll|hyperloglog)》
《PostgreSQL hll (HyperLogLog) extension for "State of The Art Cardinality Estimation Algorithm" - 3》
《PostgreSQL hll (HyperLogLog) extension for "State of The Art Cardinality Estimation Algorithm" - 2》
《PostgreSQL hll (HyperLogLog) extension for "State of The Art Cardinality Estimation Algorithm" - 1》
《Greenplum 最佳实践 - 估值插件hll的使用(以及hll分式聚合函数优化)》
专业推荐数据库 - recdb
https://github.com/DataSystemsLab/recdb-postgresql
专业图数据库
https://github.com/bitnine-oss/agensgraph
您的愿望将传达给PG kernel hacker、数据库厂商等, 帮助提高数据库产品质量和功能, 说不定下一个PG版本就有您提出的功能点. 针对非常好的提议，奖励限量版PG文化衫、纪念品、贴纸、PG热门书籍等，奖品丰富，快来许愿。开不开森.
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。