digoal
2023-12-14
PostgreSQL , PolarDB , DuckDB , 某音 , 短视频 , 推荐算法
某音，我不得不把你卸载, 因为你知道我太多秘密.
大家都知道抖音的算法牛掰, 看过什么就推荐你什么. 让你越看越依赖, 越用越久, 他的广告费却赚得盆满钵满, 你说气不气人, 该不该卸载.
比如我看过王祖贤, 刘亦菲的小视频, 你就不断给我推, 咋地, 怕全天下不知道我喜欢王祖贤, 刘亦菲拍的倩女幽魂啊?
家里领导一发现, 一吃醋, 榴莲都不够用, 关键榴莲还要我买, 吃确没我的份.
所以把某音卸载还不解恨, 我还要掀桌子.
你的推荐算法不是牛吗, 你不是很丝滑吗? 我让你算法牛, 让你懂我, 让你丝滑.
今天, 我要把你的核心推荐算法按在地上摩擦, 把这个算法的门槛降低到地板难度. 让所有人都能用上, 让天下冒出无数个某音的友商, 卷死你.
1、给视频贴标签. 简单, 阿里云就有类似的视频服务, 可以完成涉黄赌毒、暴力、zz敏感等的识别过滤, 以及根据特征打标. 并给出视频标签s, 以及每个标签对应的权重.
2、刷新视频的推荐指数. 简单, 根据 浏览量 * 各标签的权重 计算出视频的各标签的推荐分数.
3、视频的地域池设计. 简单, 要让本地的好视频可以有上升到全国推荐的池子, 同时要让付费的广告主的视频有VIP通道(推荐特权): 设计三个池: 本地视频池(geohash, table_suffix. 或者以邮编, 或电话区号为后缀.)、全国流量池、付费推荐视频池
- 说白了就是视频浏览量越多, 就把视频放到更大的池子里. 池子的个数, 级别可以根据业务需求自由设计.
4、用户喜好和权重计算. 简单, 1方面是注册的时候勾选喜好, 另一方面是根据用户浏览的视频的(主、副标签及权重, 算出用户每个标签的喜好). 可以使用 JSONB / array 存储.
5、推荐视频. 从3个池子中提取视频, 简单, 本地池: 根据用户的位置查询对应的本地表, 根据喜好标签搜索喜好的视频, 根据权重Limit返回条数; 全国池和付费推荐池以此类推; 总共就查3张表.
6、过滤已读视频. 简单又不简单, 提取过程中, 把用户已读的视频ID剔除即可.
- 不简单的地方1: 一个人可能浏览了很多视频; 视频被很多人浏览过; 所以列表会非常大, 如果每读一次写一条记录, 会很多条, 使用not in过滤会非常慢, 怎么办?
- 简单, 使用roaring bitmap, hll, datasketch 把已读列表存储成1条记录, 由于是lossy type或压缩type, 哪怕存数亿个值也只需要几十KB.
- 《沉浸式学习PostgreSQL|PolarDB 1: 短视频推荐去重、UV统计分析场景》
- PS: 《PostgreSQL 15 preview - Use a hash table to speed up NOT IN(values)》
- hll其实有点类似于bloom, 可以参考 《UID编码优化 - 用户画像前置规则 (bloom, 固定算法等)》 bit占位图示参考:
- 不简单的地方2: 如果已读列表非常大, 会耗费大量的CPU和IO过滤已读, 才能拿到未读的可推荐视频. 怎么解?
- 可以借鉴广度优先和深度优先的思路, 默认是采用类似“广度优先”搜索策略, 所以会遇到大量已读. 但是我们可以使用partial index, 加个hash mod条件, 相对于全局视频数据就变成类似“深度优先”, 可以大幅度减少大量已读. 详细请看后面的SQL设计和索引设计.
- 不简单的地方3: 把已读列表 正向存在视频表(已读的用户)? 还是 反向存在用户表(已读的视频)?
- 简单, 我推荐反向存在用户表里, 不会有锁冲突问题.
- 不简单的地方4: 实时更新还是异步更新已读列表?
- 简单, 推荐异步存储, 先存储在redis/程序临时缓存, 后期合并到数据库内. 如果是异步更新, 在收到数据库提取的推荐视频后, 程序端要根据缓存再过滤一下.
7、如果资源不足导致雪崩了怎么办? 简单:
- 方法1, 预加载, 例如每次给用户批量推荐100条视频, 当用户刷到80条时, 后台已经在请求后面的100条了. 这样用户就会感到丝般柔滑.
- 方法2, 降级到随机推荐. 使用随机采样, 不管数据量多大, 1毫秒以内就可以返回.
我是谁? 没有2把刷子, 我怎么敢掀桌子? 大家说说是不是已经把某音核心推荐算法的门槛降低到地板难度. 让所有人都能用上, 让天下冒出无数个某音的友商.
今天, 你只需要1个PostgreSQL或PolarDB数据库, 普通macbook pro每秒就可以按喜好推荐26.7万个视频, 卷死某音.
其实我在之前公众号的文章中已经透露了一部分demo: 平民的劳斯莱斯, 笔记本玩转短视频推荐
欢迎大家关注我的公众号: PostgreSQL码农集散地
更详细的Demo如下.
AMD64 Chip's OS:
# 拉取镜像, 第一次拉取一次即可. 或者需要的时候执行, 将更新到最新镜像版本.
docker pull registry.cn-hangzhou.aliyuncs.com/digoal/opensource_database:pg14_with_exts
# 启动容器
docker run --platform linux/amd64 -d -it -P --cap-add=SYS_PTRACE --cap-add SYS_ADMIN --privileged=true --name pg --shm-size=1g registry.cn-hangzhou.aliyuncs.com/digoal/opensource_database:pg14_with_exts
##### 如果你想学习备份恢复、修改参数等需要重启数据库实例的case, 换个启动参数, 使用参数--entrypoint将容器根进程换成bash更好. 如下:
docker run -d -it -P --cap-add=SYS_PTRACE --cap-add SYS_ADMIN --privileged=true --name pg --shm-size=1g --entrypoint /bin/bash registry.cn-hangzhou.aliyuncs.com/digoal/opensource_database:pg14_with_exts
##### 以上启动方式需要进入容器后手工启动数据库实例: su - postgres; pg_ctl start;
# 进入容器
docker exec -ti pg bash
# 连接数据库
psql
ARM64 Chip's OS:
# 拉取镜像, 第一次拉取一次即可. 或者需要的时候执行, 将更新到最新镜像版本.
docker pull registry.cn-hangzhou.aliyuncs.com/digoal/opensource_database:pg14_with_exts_arm64
# 启动容器
docker run -d -it -P --cap-add=SYS_PTRACE --cap-add SYS_ADMIN --privileged=true --name pg --shm-size=1g registry.cn-hangzhou.aliyuncs.com/digoal/opensource_database:pg14_with_exts_arm64
##### 如果你想学习备份恢复、修改参数等需要重启数据库实例的case, 换个启动参数, 使用参数--entrypoint将容器根进程换成bash更好. 如下:
docker run -d -it -P --cap-add=SYS_PTRACE --cap-add SYS_ADMIN --privileged=true --name pg --shm-size=1g --entrypoint /bin/bash registry.cn-hangzhou.aliyuncs.com/digoal/opensource_database:pg14_with_exts_arm64
##### 以上启动方式需要进入容器后手工启动数据库实例: su - postgres; pg_ctl start;
# 进入容器
docker exec -ti pg bash
# 连接数据库
psql
如果你的机器实在是拿不出手, 也可以尝试在云起实验室里面完成, 只是可能需要修改一下demo里面的数据量, 改小一点, 否则空间不够.
云起实验室地址:
生产请使用非unlogged table, 例子只是为了快速生成数据.
1、3张视频表, 分别代表 本地视频池、全国视频池、VIP视频池. 三个池子总共生成3000万条记录.
1.1、本地视频池
create unlogged table t_videos_local_pool (
vid int8, -- 视频ID
lid int, -- 地区市, 电话区号
tag int, -- 视频标签
score float4, -- 视频标签权重
unique (vid,lid),
unique (vid,tag)
);
PS: 你高兴的话可以按地域设置更多级别: 例如 市、省、全国.
写入数据: 1000万条记录.
- 100万个视频,
- 每个视频10个标签,
- 标签取值空间
1 ~ 100(也就是假设总共有100个标签, 标签越多性能越好, 因为过滤性越强, 但是为了压测可以获取到更多视频, 这里选择了更容易压出问题的少量标签). - lid 取值空间
1 ~ 360(也就是假设有360个地区市).
insert into t_videos_local_pool
select generate_series(1,1000000), ceil(random()*360), ceil(random()*100), random()*10 from generate_series(1,10) on conflict do nothing;
1.2、创建全国视频池
create unlogged table t_videos_top_pool (
vid int8, -- 视频ID
tag int, -- 视频标签
score float4, -- 视频标签权重
unique (vid,tag)
);
写入数据: 1000万条记录: 100万个视频, 每个视频10个标签, 标签取值空间1 ~ 100.
insert into t_videos_top_pool
select generate_series(1000001,2000000), ceil(random()*100), random()*10 from generate_series(1,10) on conflict do nothing;
1.3、创建VIP视频池
create unlogged table t_videos_vip_pool (
vid int8, -- 视频ID
tag int, -- 视频标签
score float4, -- 视频标签权重
unique (vid,tag)
);
写入数据: 1000万条记录: 100万个视频, 每个视频10个标签, 标签取值空间1 ~ 100.
insert into t_videos_vip_pool
select generate_series(2000001,3000000), ceil(random()*100), random()*10 from generate_series(1,10) on conflict do nothing;
1.4、创建 64个 partial index(分区索引), 避免过滤巨大已读列表带来巨大的无效扫描和CPU开销, 之前已经讲过:
do language plpgsql $$
declare
begin
for i in 0..63 loop
execute format('create index on t_videos_local_pool (lid, tag, score desc) where abs(mod(hashint8(vid),64))=%s', i,i);
execute format('create index on t_videos_top_pool (tag, score desc) where abs(mod(hashint8(vid),64))=%s', i,i);
execute format('create index on t_videos_vip_pool (tag, score desc) where abs(mod(hashint8(vid),64))=%s', i,i);
end loop;
end;
$$;
2、创建用户标签类型
用于存储喜欢的视频标签, 以及对应的权重
create type tag_score as (
tag int, -- 标签
score float4, -- 标签权重
limits int -- 用这个标签获取多少条VID
);
3、用户表
create unlogged table users (
uid int8 primary key, -- 用户ID
lid int, -- 用户所在的地区ID
tag_scores1 tag_score[], -- 标签、权重、对应标签获取多少条. 也可以使用jsonb存储
tag_scores2 tag_score[], -- 标签、权重、对应标签获取多少条 limit = 0的放这个字段. 业务更新tag_scores根据两个字段的结果来计算. 主要是减少PG计算量.
readlist jsonb -- 已读VID, 和分区索引的分区数匹配, 用jsonb数组表示. jsonb[0]表示 abs(mod(hashint8(vid),64))=0 的vid数组
-- PS: 这个地方也可以使用hll或roaringbitmap数组类型代替JSONB, 可以压缩空间, 同时提升性能.
-- 不用担心存不下, Jsonb可以存储1GiB内容, 而且支持压缩(Pglz, lz4...)
);
写入数据: 1000万条记录
- 1000万个用户,
- 每个用户20个标签 (标签取值空间
1 ~ 100), - limit大于0 的 标签5个(和为100, 也就是说每次请求推荐100条未读视频).
- vid 已读列表 (vid
1 ~ 300万取值空间, 对应前面写入的300万个视频).- 重度用户, 每个用户36.5万个已观看视频. userid号段:
1 ~ 1w - 中度用户, 每个用户1万个已观看视频. userid号段:
1w ~ 100w - 一般用户, 每个用户2千个已观看视频. userid号段:
100w ~ 1000w
- 重度用户, 每个用户36.5万个已观看视频. userid号段:
- lid (用户所处的地区码) 取值空间对应前面的
1 ~ 360
insert into users
-- 重度用户, userid号段: `1 ~ 1w`
-- 每个用户的已观看视频都是36.5万个.
select generate_series(1,10000), ceil(random()*360),
-- 每个用户20个标签 (标签取值空间`1 ~ 100`), limit大于0的标签5个(和为100, 也就是说每次请求推荐100条未读视频).
array(
select row(ceil(random()*100), random()*10, 40)::tag_score
union all
select row(ceil(random()*100), random()*10, 20)::tag_score
union all
select row(ceil(random()*100), random()*10, 15)::tag_score
union all
select row(ceil(random()*100), random()*10, 15)::tag_score
union all
select row(ceil(random()*100), random()*10, 10)::tag_score
),
-- limit = 0的标签15个
array (
select row(ceil(random()*100), random()*10, 0)::tag_score from generate_series(1,15)
),
-- 重度用户
-- 每个用户的已观看视频都是36.5万个. (vid 取值空间 `1 ~ 300万`, 对应前面写入的300万个视频).
-- 聚合为jsonb数组, 每个vids列表代表 mod(x,64)=i 的vids. 对应partial index, 用于减少已读的cpu过滤, 提升搜索性能.
(
select jsonb_agg(x) as readlist from
(
select array (select x from
(select ceil(random()*3000000)::int8 x from generate_series(1,365000)) t
where abs(mod(hashint8(x),64)) = i
) x
from generate_series(0,63) i
) t
) ;
insert into users
-- 中度用户, userid号段: `1w ~ 100w`
-- 每个用户的已观看视频都是1万个.
select generate_series(10001, 1000000), ceil(random()*360),
-- 每个用户20个标签 (标签取值空间`1 ~ 100`), limit大于0的标签5个(和为100, 也就是说每次请求推荐100条未读视频).
array(
select row(ceil(random()*100), random()*10, 40)::tag_score
union all
select row(ceil(random()*100), random()*10, 20)::tag_score
union all
select row(ceil(random()*100), random()*10, 15)::tag_score
union all
select row(ceil(random()*100), random()*10, 15)::tag_score
union all
select row(ceil(random()*100), random()*10, 10)::tag_score
),
-- limit = 0的标签15个
array (
select row(ceil(random()*100), random()*10, 0)::tag_score from generate_series(1,15)
),
-- 中度用户
-- 每个用户的已观看视频都是1万个. (vid 取值空间 `1 ~ 300万`, 对应前面写入的300万个视频).
-- 聚合为jsonb数组, 每个vids列表代表 mod(x,64)=i 的vids. 对应partial index, 用于减少已读的cpu过滤, 提升搜索性能.
(
select jsonb_agg(x) as readlist from
(
select array (select x from
(select ceil(random()*3000000)::int8 x from generate_series(1,10000)) t
where abs(mod(hashint8(x),64)) = i
) x
from generate_series(0,63) i
) t
) ;
insert into users
-- 一般用户, userid号段: `100w ~ 1000w`
-- 每个用户的已观看视频都是2000个.
select generate_series(1000001, 10000000), ceil(random()*360),
-- 每个用户20个标签 (标签取值空间`1 ~ 100`), limit大于0的标签5个(和为100, 也就是说每次请求推荐100条未读视频).
array(
select row(ceil(random()*100), random()*10, 40)::tag_score
union all
select row(ceil(random()*100), random()*10, 20)::tag_score
union all
select row(ceil(random()*100), random()*10, 15)::tag_score
union all
select row(ceil(random()*100), random()*10, 15)::tag_score
union all
select row(ceil(random()*100), random()*10, 10)::tag_score
),
-- limit = 0的标签15个
array (
select row(ceil(random()*100), random()*10, 0)::tag_score from generate_series(1,15)
),
-- 一般用户
-- 每个用户的已观看视频都是2000个. (vid 取值空间 `1 ~ 300万`, 对应前面写入的300万个视频).
-- 聚合为jsonb数组, 每个vids列表代表 mod(x,64)=i 的vids. 对应partial index, 用于减少已读的cpu过滤, 提升搜索性能.
(
select jsonb_agg(x) as readlist from
(
select array (select x from
(select ceil(random()*3000000)::int8 x from generate_series(1,2000)) t
where abs(mod(hashint8(x),64)) = i
) x
from generate_series(0,63) i
) t
) ;
以上导入的数据, 相当于平台已经拥有 315.5 亿次有效视频观看, 仅流量广告费就 315.5 亿.
- 315.5 =
36.5*1 + 1*99 + 0.2*900 - 参考知乎的信息: 目前某音信息流广告的一个CPC的价格最低为1元，即如果广告被点击1000次，则需要花费1000元
存储空间占用情况如下, 190GB:
postgres=# \l+
List of databases
-[ RECORD 1 ]-----+-------------------------------------------
Name | postgres
Owner | postgres
Encoding | UTF8
Collate | C
Ctype | en_US.UTF8
Access privileges |
Size | 190 GB
Tablespace | pg_default
Description | default administrative connection database
postgres=# \dt+
List of relations
Schema | Name | Type | Owner | Persistence | Access method | Size | Description
--------+---------------------+-------+----------+-------------+---------------+--------+-------------
public | t_videos_local_pool | table | postgres | unlogged | heap | 470 MB |
public | t_videos_top_pool | table | postgres | unlogged | heap | 404 MB |
public | t_videos_vip_pool | table | postgres | unlogged | heap | 404 MB |
public | users | table | postgres | unlogged | heap | 187 GB |
(4 rows)
4、根据用户的喜好标签, 从本地池、全国池、VIP池 推荐相关视频
根据用户的有效权重标签(tag_scores1), 按推荐指数倒序提取 未读视频100条 (其中从全国池取50%, 本地池取30%, VIP池取20%) 。
以 uid=1 , 搜索partian index 0号分区为例. (注意JSONB数组的下标从0开始, 但是array类型的下标是从1开始的. 很容易搞混). SQL:
select
(
select array_agg(vid) from
(
-- 全国视频池
select vid from t_videos_top_pool t1
-- 取出与用户喜爱的标签匹配的视频
where t1.tag=t.tag
-- 过滤已读VID , 使用partian index 0号分区.
-- 注意JSONB数组的下标从0开始, 但是array类型的下标是从1开始的. 很容易搞混.
and t1.vid not in (select jsonb_array_elements_text( readlist[0] )::int8 from users where uid=1)
-- 使用partian index 0号分区
and abs(mod(hashint8(vid),64)) = 0
-- 按视频推荐权重逆序取出视频
order by t1.score desc
-- limit 条数来自tag_scores1.limits, 其中全国池占比 50%
limit ceil(t.limits*0.5)
) x -- 全国池limit占比 50%
) as top_pool,
(
select array_agg(vid) from
(
-- 本地视频池
select vid from t_videos_local_pool t1
where t1.tag=t.tag
-- 本地池, 增加一个查询条件: 查询与本地用户地域匹配的视频
and t1.lid = (select lid from users where uid=1)
and t1.vid not in (select jsonb_array_elements_text( readlist[0] )::int8 from users where uid=1)
and abs(mod(hashint8(vid),64)) = 0
order by t1.score desc
limit ceil(t.limits*0.3)
) x -- 本地池limit占比 30%
) as local_pool,
(
select array_agg(vid) from
(
-- VIP视频池
select vid from t_videos_vip_pool t1
where t1.tag=t.tag
and t1.vid not in (select jsonb_array_elements_text( readlist[0] )::int8 from users where uid=1)
and abs(mod(hashint8(vid),64)) = 0
order by t1.score desc
limit ceil(t.limits*0.2)
) x -- vip池limit占比 20%
) as vip_pool
from
(
-- 从用户表取出用户的喜好标签, 以及每个标签的返回条数
select (unnest(tag_scores1)).tag as tag, (unnest(tag_scores1)).limits as limits from
users where uid=1
) t;
返回结果例子:
uid=1时:
-[ RECORD 1 ]-----------------------------------------------------------------------------------------------------------------------------------------------------------------
top_pool | {1790916,1132216,1774280,1952156,1160239,1548536,1318177,1702917,1434362,1409981,1860373,1028987,1178555,1116453,1968401,1023390,1260664,1463697,1946324,1291647}
local_pool | {346579,987432}
vip_pool | {2794676,2065227,2732550,2000259,2815806,2957527,2631995,2395876}
-[ RECORD 2 ]-----------------------------------------------------------------------------------------------------------------------------------------------------------------
top_pool | {1908886,1899793,1411568,1929364,1246641,1251799,1314424,1823510,1300298,1251984}
local_pool | {204181,790982,760401}
vip_pool | {2252375,2009571,2816666,2335909}
-[ RECORD 3 ]-----------------------------------------------------------------------------------------------------------------------------------------------------------------
top_pool | {1908886,1899793,1411568,1929364,1246641,1251799,1314424,1823510}
local_pool | {204181,790982,760401}
vip_pool | {2252375,2009571,2816666}
-[ RECORD 4 ]-----------------------------------------------------------------------------------------------------------------------------------------------------------------
top_pool | {1784058,1228510,1439057,1302993,1697334,1233058,1950055,1404547}
local_pool | {227295}
vip_pool | {2975383,2865416,2815158}
-[ RECORD 5 ]-----------------------------------------------------------------------------------------------------------------------------------------------------------------
top_pool | {1026596,1956755,1897653,1391852,1610438}
local_pool | {755830,930305,269404}
vip_pool | {2144222,2556698}
uid=10000000时:
-[ RECORD 1 ]-----------------------------------------------------------------------------------------------------------------------------------------------------------------
top_pool | {1790916,1132216,1774280,1952156,1160239,1548536,1318177,1702917,1434362,1409981,1860373,1028987,1619263,1178555,1413056,1440524,1116453,1968401,1023390,1260664}
local_pool | {420726,101788,787444}
vip_pool | {2794676,2065227,2732550,2000259,2815806,2957527,2631995,2395876}
-[ RECORD 2 ]-----------------------------------------------------------------------------------------------------------------------------------------------------------------
top_pool | {1180991,1899128,1769344,1714725,1384724,1868715,1153425,1852447,1206311,1272872}
local_pool | {217365,795102}
vip_pool | {2406797,2459297,2914047,2450752}
-[ RECORD 3 ]-----------------------------------------------------------------------------------------------------------------------------------------------------------------
top_pool | {1341596,1257155,1918176,1913171,1082175,1972329,1920133,1062190}
local_pool | {858336}
vip_pool | {2043662,2683512,2065115}
-[ RECORD 4 ]-----------------------------------------------------------------------------------------------------------------------------------------------------------------
top_pool | {1566363,1900979,1975859,1776285,1207471,1037560,1177909,1033851}
local_pool | {516241,517531,419669,644382,319791}
vip_pool | {2871970,2389006,2693050}
-[ RECORD 5 ]-----------------------------------------------------------------------------------------------------------------------------------------------------------------
top_pool | {1711028,1908184,1411025,1769915,1306077}
local_pool | {242174,581692,876193}
vip_pool | {2254656,2434176}
PS: 这条SQL有可能会返回重复的vid, 因为同一个视频有多个tag, 当同一个视频的多个tag匹配到同一个用户tag_scores1内的多个tag时, 有一定的概率多次返回这个vid. 这个情况如果是小概率, 建议在服务端进行去重, 减少数据库去重带来的CPU开销. (毕竟应用是无状态的, 更好扩容)。
5、性能测试. 在2022年的macbook pro上测试, 每秒可推荐视频267622个, 已经达到掀桌子的效果.
创建测试脚本, 推荐数据覆盖1000万个用户, 所有的视频分区. 每次从某个随机的hash mod中取100条未读视频:
vi ~/test.sql
\set uid random(1,10000000)
\set mod random(0,63)
select
(
select array_agg(vid) from
(
-- 全国视频池
select vid from t_videos_top_pool t1
-- 取出与用户喜爱的标签匹配的视频
where t1.tag=t.tag
-- 过滤已读VID , 使用partian index 0号分区
and t1.vid not in (select jsonb_array_elements_text( readlist[:mod] )::int8 from users where uid=:uid)
-- 使用partian index 0号分区
and abs(mod(hashint8(vid),64)) = :mod
-- 按视频推荐权重逆序取出视频
order by t1.score desc
-- limit 条数来自tag_scores1.limits, 其中全国池占比 50%
limit ceil(t.limits*0.5)
) x -- 全国池limit占比 50%
) as top_pool,
(
select array_agg(vid) from
(
-- 本地视频池
select vid from t_videos_local_pool t1
where t1.tag=t.tag
-- 本地池, 增加一个查询条件: 查询与本地用户地域匹配的视频
and t1.lid = (select lid from users where uid=:uid)
and t1.vid not in (select jsonb_array_elements_text( readlist[:mod] )::int8 from users where uid=:uid)
and abs(mod(hashint8(vid),64)) = :mod
order by t1.score desc
limit ceil(t.limits*0.3)
) x -- 本地池limit占比 30%
) as local_pool,
(
select array_agg(vid) from
(
-- VIP视频池
select vid from t_videos_vip_pool t1
where t1.tag=t.tag
and t1.vid not in (select jsonb_array_elements_text( readlist[:mod] )::int8 from users where uid=:uid)
and abs(mod(hashint8(vid),64)) = :mod
order by t1.score desc
limit ceil(t.limits*0.2)
) x -- vip池limit占比 20%
) as vip_pool
from
(
-- 从用户表取出用户的喜好标签, 以及每个标签的返回条数
select (unnest(tag_scores1)).tag as tag, (unnest(tag_scores1)).limits as limits from
users where uid=:uid
) t;
开启压测:
pgbench -M prepared -n -r -P 1 -f ~/test.sql -c 6 -j 6 -T 120
压测结果:
transaction type: /root/test.sql
scaling factor: 1
query mode: prepared
number of clients: 6
number of threads: 6
duration: 120 s
number of transactions actually processed: 321112
latency average = 2.242 ms
latency stddev = 1.101 ms
initial connection time = 15.783 ms
tps = 2676.227495 (without initial connection time)
statement latencies in milliseconds:
0.000 \set uid random(1,10000000)
0.000 \set mod random(0,63)
2.241 select ......
2022款 macbook pro 13寸 (M2芯片, 16g mem, 512G ssd). docker容器分配资源:4c 6g, 每秒可以推荐多少个视频ID?
- 267622 个
我这个测试镜像是PG14版本, PG15对not in做了优化, 所以有兴趣的小伙伴使用PG 15测试性能一定还会飙升.
这是个读多写少的场景. 因为刷新用户标签和视频的权重都可以异步进行, 所以查询占比较高, 可以非常容易的通过增加PG只读节点来提升查询qps吞吐.
而如果你使用PolarDB, 则更省成本, 因为多个计算节点共享一份存储. 而传统PostgreSQL增加只读实例都需要复制一份完整的数据.
6、降级处理方法(预处理 或 随机采样)
如果资源不足导致雪崩了怎么办? 简单: 降级到随机推荐即可. 使用随机采样, 不管数据量多大, 1毫秒以内就可以返回.
重新发现PG之美 - 4 随机漫步踏浪而来:
- 在一些论坛、短视频业务中, 编辑精选和地域或大范围精选的内容会采用随机推荐的方式推送给客户.
- 随机查询就有了高并发、低延迟的需求, 然而通用的order by random()随机方法性能太烂, 无法满足需求.
- PG 提供了tablesample method(para)方法, 能够以几千倍的性能满足高并发需求.
视频回放: https://www.bilibili.com/video/BV1cy4y137WU/
降级处理的 SQL 如下:
-- 安装插件
create extension tsm_system_rows ;
create extension tsm_system_time ;
-- 随机采样SQL , 可根据实际的数据量, 块数量调整数值
-- system (5) 表示采样5%的数据块
-- random() < ? 用来增加随机性, 避免同一个数据块的数据全部被取出. 如果你无所谓, 可以去掉这个条件, 性能将更好.
select * from (
select ctid,vid from t_videos_top_pool TABLESAMPLE system (5) where random()<0.01 limit 50 ) t
union all
select * from (
select ctid,vid from t_videos_local_pool TABLESAMPLE system (5) where random()<0.01 limit 30 ) t
union all
select * from (
select ctid,vid from t_videos_vip_pool TABLESAMPLE system (5) where random()<0.01 limit 20) t;
或
-- system_time (5) 表示采样5毫秒
-- random() < ? 用来增加随机性, 避免同一个数据块的数据全部被取出.
select * from (
select ctid,vid from t_videos_top_pool TABLESAMPLE system_time (5) where random()<0.02 limit 50 ) t
union all
select * from (
select ctid,vid from t_videos_local_pool TABLESAMPLE system_time (5) where random()<0.02 limit 30 ) t
union all
select * from (
select ctid,vid from t_videos_vip_pool TABLESAMPLE system_time (5) where random()<0.02 limit 20 ) t;
或
-- system_rows(1000) 表示采样1000条.
-- random() < ? 用来增加随机性, 避免同一个数据块的数据全部被取出.
select * from (
select ctid,vid from t_videos_top_pool TABLESAMPLE system_rows(1000) where random()<0.05 ) t -- 1000*0.05=50 , 相当于limit 50
union all
select * from (
select ctid,vid from t_videos_local_pool TABLESAMPLE system_rows(1000) where random()<0.03 ) t
union all
select * from (
select ctid,vid from t_videos_vip_pool TABLESAMPLE system_rows(1000) where random()<0.02 ) t;
以上才赚300多亿就用掉了190GB笔记本空间, 是不是觉得门槛还是有点“高”.
接下来我使用RB和HLL代替jsonb, 让存储空间更小, 性能再起飞. 相比users表的187GB, users_hll只有19GB.
1、创建hll插件
create extension hll;
2、创建新的用户表, 使用hll存储已读视频列表
create unlogged table users_hll (
uid int8 primary key, -- 用户ID
lid int, -- 用户所在的地区ID
tag_scores1 tag_score[], -- 标签、权重、对应标签获取多少条. 也可以使用jsonb存储
tag_scores2 tag_score[], -- 标签、权重、对应标签获取多少条 limit = 0的放这个字段. 业务更新tag_scores根据两个字段的结果来计算. 主要是减少PG计算量.
readlist hll -- 已读VID, 用hll表示. 不需要再分片, 压缩到一起.
-- 1个小小几十KB的hll可以储存上亿value组成的占位值. 可以提取hll的distinct值个数, 判断vid是否存在于hll中, 将vid添加到hll中, 两个hll可以合并、相减动作.
);
3、定义一个函数, 把jsonb数组 转换为 hll.
create or replace function jsonbarr_to_hll (readlist jsonb) returns hll as $$
select hll_add_agg(hll_hash_bigint(x)) from (
select jsonb_array_elements_text(readlist[i])::int8 AS x from generate_series(0,63) i
) t;
$$ language sql strict;
转换后返回结果范例:
select jsonbarr_to_hll(readlist) from users where uid=10000000;
jsonbarr_to_hllarr | \x148b7f18401500012840018001080210040020ca608c4008040000a10802100401194000880208046084030842210400000221004110c41080212040001421090440000500c6100005088a00040408021008413040101440104000080010802188430880008001110030002200c0710400004250000110802000011800129000090400a46130420100611000200c20104a01044109441084220800000823100020080028080100010840021060088201800200c261884118800088210942010c8118001100400080031405204421840000c000004218c00100020004008c21000210800008421194001084100841000021848228000180021800000407000400002000ca21840121420004413088030000000000000000460384410802018840100c51040200427388200840408c200140010c4200001088420088318840000001006210440108240040110c24180620080220400084000882000d020800330c0118400404002040019001100a138c0008ca208c81100001a00008805010030980100463484610908020804000200000108863204400802108002084213846200080184a11810008822084000040318400008a0008000880201021108a000020108401006018860100831006208c41000000840011001090260846508c40000410000108440208200082100020104220808018082080a1088400840320c420004008400108c60088808026004221800200c08000000000008840084201080418001080010004408802000003082301002000401800408020100200800100480000002840201800004610086100001004002010018000000c00006510400090010002010480104210000000422010010040210023080012000110821080040000400803404213800420c0108040100000884519043000410142018843084011086210460010601802008403400010b001080010182200460008212088000c03080a3008051842011042090021006000801081400040419820008020042008400004020040000442184c1180400006120042104230800140026088a002001108661044010000008270040500403084800004118003104011802018c6218462188a00084009000004220000020400108020804001001000001840208801008431004000441180020040218860004a00802160c2218c02200a008800100211100200000000001002211004200040204000484088010088000021104070088118c2000061118200004110006084400840328821000000000008040008000182218c060084000c0200105100212040008021000620142010c20100001042008001000410880001c0100022084a308840084600000030c42088210002518821004061902200481080290902200020000610884000c01094400040008c010004200420104210008300861080211044028005088230044008461210032082108807004020006008c000082100c810000008000018001000118c412102008821184400840100401080220044000c0008081080051048021440010c029c6218840000000042210942008a300004200400284010001100651840029c061082008442080400082141421000000800000400280010004118803310200842000846004010044000840000420046510002004403002201020088400002209480080030140300429100a3188021800008401094410080300460108211044108405088450004100c00180421002220c00090222002118c21088601042000c400800100004004010886011005
可以计算得出jsonb和hll存储已读视频的存储耗费的差别, 166GB vs 12GB
-- 36.5万个视频 ID jsonb 占用空间: 2MB
postgres=# select pg_column_size(readlist) from users where uid=1;
pg_column_size
----------------
2014023
(1 row)
-- 1万个视频 ID jsonb 占用空间: 55.7KB
postgres=# select pg_column_size(readlist) from users where uid=10001;
pg_column_size
----------------
55713
(1 row)
-- 2千个视频 ID jsonb 占用空间: 11.47KB
postgres=# select pg_column_size(readlist) from users where uid=10000000;
pg_column_size
----------------
11474
(1 row)
-- 36.5万个视频 ID hll 占用空间: 1.29KB
postgres=# select pg_column_size(jsonbarr_to_hll(readlist)) from users where uid=1;
pg_column_size
----------------
1287
(1 row)
-- 1万个视频 ID hll 占用空间: 1.29KB
postgres=# select pg_column_size(jsonbarr_to_hll(readlist)) from users where uid=10001;
pg_column_size
----------------
1287
(1 row)
-- 2千个视频 ID hll 占用空间: 1.29KB
postgres=# select pg_column_size(jsonbarr_to_hll(readlist)) from users where uid=10000000;
pg_column_size
----------------
1287
(1 row)
-- 本例子的1000万个视频, 使用jsonb存储明细已读视频ID, 耗费存储 166GB
postgres=# select pg_size_pretty(2014023*10000::int8 + 55713*990000::int8 + 11474*9000000::int8);
pg_size_pretty
----------------
166 GB
(1 row)
-- 本例子的1000万个视频, 使用hll存储lossy已读视频ID, 耗费存储 12GB
postgres=# select pg_size_pretty(1287*10000000::int8);
pg_size_pretty
----------------
12 GB
(1 row)
4、将users表的数据写入users_hll
insert into users_hll select uid, lid, tag_scores1, tag_scores2, jsonbarr_to_hll(readlist) from users;
空间占用:
postgres=# \dt+
List of relations
Schema | Name | Type | Owner | Persistence | Access method | Size | Description
--------+---------------------+-------+----------+-------------+---------------+--------+-------------
public | t_videos_local_pool | table | postgres | unlogged | heap | 470 MB |
public | t_videos_top_pool | table | postgres | unlogged | heap | 404 MB |
public | t_videos_vip_pool | table | postgres | unlogged | heap | 404 MB |
public | users | table | postgres | unlogged | heap | 187 GB |
public | users_hll | table | postgres | unlogged | heap | 19 GB |
(5 rows)
相比users表的187GB, users_hll只有19GB.
5、改写查询SQL, 以 uid=1 , 搜索partian index 0号分区为例. 使用hll判断视频是否已读
select
(
select array_agg(vid) from
(
-- 全国视频池
select vid from t_videos_top_pool t1
-- 取出与用户喜爱的标签匹配的视频
where t1.tag=t.tag
-- 过滤已读VID , 使用partian index 0号分区
and hll_add(t.readlist, hll_hash_bigint(t1.vid)) <> t.readlist
-- 使用partian index 0号分区
and abs(mod(hashint8(vid),64)) = 0
-- 按视频推荐权重逆序取出视频
order by t1.score desc
-- limit 条数来自tag_scores1.limits, 其中全国池占比 50%
limit ceil(t.limits*0.5)
) x -- 全国池limit占比 50%
) as top_pool,
(
select array_agg(vid) from
(
-- 本地视频池
select vid from t_videos_local_pool t1
where t1.tag=t.tag
-- 本地池, 增加一个查询条件: 查询与本地用户地域匹配的视频
and t1.lid = (select lid from users_hll where uid=1)
and hll_add(t.readlist, hll_hash_bigint(t1.vid)) <> t.readlist
and abs(mod(hashint8(vid),64)) = 0
order by t1.score desc
limit ceil(t.limits*0.3)
) x -- 本地池limit占比 30%
) as local_pool,
(
select array_agg(vid) from
(
-- VIP视频池
select vid from t_videos_vip_pool t1
where t1.tag=t.tag
and hll_add(t.readlist, hll_hash_bigint(t1.vid)) <> t.readlist
and abs(mod(hashint8(vid),64)) = 0
order by t1.score desc
limit ceil(t.limits*0.2)
) x -- vip池limit占比 20%
) as vip_pool
from
(
-- 从用户表取出用户的喜好标签, 以及每个标签的返回条数
select readlist, (unnest(tag_scores1)).tag as tag, (unnest(tag_scores1)).limits as limits from
users_hll where uid=1
) t;
6、对比之前users表的uid=1和uid=10000000的查询结果, 看看lossy有没有什么影响?
因为 hll值是有损压缩过的value, 不存在则一定不存在, 存在可能为假(可能是其他多个值的bit占位填充导致).
所以 使用hll 做not in的判断, 可能会跳过某些其实未读的视频id.
users_hll uid=1 . 相比比jsonb的精准明细, hll 存储36.5 W的已读过滤还是有一定的失真, 某些未读的视频被判定为已读. 不过hll还可以调整精度, 具体参考: https://github.com/citusdata/postgresql-hll
-[ RECORD 1 ]-------------------------------------------------------------------------
top_pool | {1956445,1362842,1193697,1571516,1360160,1964639,1187014,1217925,1714888}
local_pool |
vip_pool | {2271124,2455866}
-[ RECORD 2 ]-------------------------------------------------------------------------
top_pool | {1753513,1882835,1929038,1404547,1499636,1115958,1489987}
local_pool |
vip_pool | {2659002,2420573,2986719,2883030}
-[ RECORD 3 ]-------------------------------------------------------------------------
top_pool | {1753513,1882835,1929038,1404547,1499636,1115958,1489987}
local_pool |
vip_pool | {2659002,2420573,2986719}
-[ RECORD 4 ]-------------------------------------------------------------------------
top_pool | {1404547,1932477,1471356,1193697,1346353}
local_pool |
vip_pool | {2891738,2092056,2197346}
-[ RECORD 5 ]-------------------------------------------------------------------------
top_pool | {1571516,1956445,1464618,1187014}
local_pool |
vip_pool | {2603160,2547271}
users_hll uid=10000000 . 对比jsonb , hll存储 2000 的已读视频失真就小很多.
-[ RECORD 1 ]-----------------------------------------------------------------------------------------------------------------------------------------------------------------
top_pool | {1790916,1160239,1318177,1028987,1619263,1178555,1413056,1116453,1023390,1463697,1753935,1401721,1784943,1302459,1696989,1593359,1441450,1693555,1300704,1912178}
local_pool | {420726}
vip_pool | {2794676,2065227,2631995,2395876,2237920,2001372,2657814,2051098}
-[ RECORD 2 ]-----------------------------------------------------------------------------------------------------------------------------------------------------------------
top_pool | {1899128,1714725,1868715,1153425,1852447,1206311,1272872,1195573,1413299,1483565}
local_pool | {217365,795102}
vip_pool | {2406797,2459297,2522999,2467079}
-[ RECORD 3 ]-----------------------------------------------------------------------------------------------------------------------------------------------------------------
top_pool | {1341596,1913171,1972329,1920133,1062190,1317098,1526785,1836627}
local_pool | {858336}
vip_pool | {2043662,2553297,2180356}
-[ RECORD 4 ]-----------------------------------------------------------------------------------------------------------------------------------------------------------------
top_pool | {1900979,1975859,1776285,1207471,1037560,1033851,1630524,1848453}
local_pool | {517531,419669,205882,556845}
vip_pool | {2871970,2693050,2956581}
-[ RECORD 5 ]-----------------------------------------------------------------------------------------------------------------------------------------------------------------
top_pool | {1711028,1411025,1769915,1306077,1473973}
local_pool | {242174,581692,581780}
vip_pool | {2254656,2434176}
关于失真问题的解决方法:
- 方法1, 调整精度, 具体参考: https://github.com/citusdata/postgresql-hll
- 方法2, 和jsonb一样, 使用数组, 每个mod内的vids存1个hll. readlist字段改成hll类型.
6.1、hll也可以用来估算唯一值, 我们前面测试数据的唯一值(已读视频ID)分布分别为36.5万, 1万, 2000. 下面看看HLL统计的偏差有多少?
postgres=# select # readlist from users_hll where uid=1;
?column?
-------------------
342784.9695243465
(1 row)
Time: 1.521 ms
postgres=# select # readlist from users_hll where uid=10001;
?column?
--------------------
10233.462757098567
(1 row)
Time: 1.183 ms
postgres=# select # readlist from users_hll where uid=10000000;
?column?
--------------------
1969.1239222652832
(1 row)
Time: 0.908 ms
7、压测脚本
vi ~/test1.sql
\set uid random(1,10000000)
\set mod random(0,63)
select
(
select array_agg(vid) from
(
-- 全国视频池
select vid from t_videos_top_pool t1
-- 取出与用户喜爱的标签匹配的视频
where t1.tag=t.tag
-- 过滤已读VID , 使用partian index 0号分区
and hll_add(t.readlist, hll_hash_bigint(t1.vid)) <> t.readlist
-- 使用partian index 0号分区
and abs(mod(hashint8(vid),64)) = :mod
-- 按视频推荐权重逆序取出视频
order by t1.score desc
-- limit 条数来自tag_scores1.limits, 其中全国池占比 50%
limit ceil(t.limits*0.5)
) x -- 全国池limit占比 50%
) as top_pool,
(
select array_agg(vid) from
(
-- 本地视频池
select vid from t_videos_local_pool t1
where t1.tag=t.tag
-- 本地池, 增加一个查询条件: 查询与本地用户地域匹配的视频
and t1.lid = (select lid from users_hll where uid=:uid)
and hll_add(t.readlist, hll_hash_bigint(t1.vid)) <> t.readlist
and abs(mod(hashint8(vid),64)) = :mod
order by t1.score desc
limit ceil(t.limits*0.3)
) x -- 本地池limit占比 30%
) as local_pool,
(
select array_agg(vid) from
(
-- VIP视频池
select vid from t_videos_vip_pool t1
where t1.tag=t.tag
and hll_add(t.readlist, hll_hash_bigint(t1.vid)) <> t.readlist
and abs(mod(hashint8(vid),64)) = :mod
order by t1.score desc
limit ceil(t.limits*0.2)
) x -- vip池limit占比 20%
) as vip_pool
from
(
-- 从用户表取出用户的喜好标签, 以及每个标签的返回条数
select readlist, (unnest(tag_scores1)).tag as tag, (unnest(tag_scores1)).limits as limits from
users_hll where uid=:uid
) t;
8、开启压测:
pgbench -M prepared -n -r -P 1 -f ~/test1.sql -c 6 -j 6 -T 120
9、压测结果:
transaction type: /root/test1.sql
scaling factor: 1
query mode: prepared
number of clients: 6
number of threads: 6
duration: 120 s
number of transactions actually processed: 177222
latency average = 4.062 ms
latency stddev = 5.174 ms
initial connection time = 11.740 ms
tps = 1476.846025 (without initial connection time)
statement latencies in milliseconds:
0.000 \set uid random(1,10000000)
0.000 \set mod random(0,63)
4.062 select ......
users表使用jsonb类型过滤已读视频ID, 每秒推荐267622条视频;
使用users_hll表使用hll类型过滤已读视频ID, 每秒推荐147684条视频;
使用hll存储已读视频ID, 已读视频个数再多也不怕. 你丝滑, 我比你更丝滑.
如果你觉得基于喜好标签还比较传统(但是性能好), 想结合AI, 结合视频特征向量来进行喜好推荐?
PG和PolarDB依旧可以满足你的愿望, 创建vector插件即可, 支持hnsw, ivfflat索引方法, 上千维度向量, 连ChatGPT都在使用PGVector.
更多细节可以参考这些文章:
- 《重新发现PostgreSQL之美 - 23 彭祖的长寿秘诀》
- 《重新发现PostgreSQL之美 - 26 这个推荐算法价值1亿》
- 《重新发现PostgreSQL之美 - 24 滑动窗口分析 2000x》
- 《PostgreSQL 应用开发解决方案最佳实践系列课程 - 2. 短视频业务实时推荐》
- 《[视频直播]亿级用户量的实时推荐数据库到底要几毛钱?》
- 《PostgreSQL 推荐系统优化总结 - 空间、时间、标量等混合多模查询场景, 大量已读过滤导致CPU IO剧增(类挖矿概率下降优化)》
- 《推荐系统, 已阅读过滤, 大量CPU和IO浪费的优化思路2 - partial index - hash 分片， 降低过滤量》
- 《PostgreSQL hll 在留存、UV统计中的通用用法》
- 《PostgreSQL 大量IO扫描、计算浪费的优化 - 推荐模块, 过滤已推荐. (热点用户、已推荐列表超大)》
- 《PostgreSQL 随机采样应用 - table sample, tsm_system_rows, tsm_system_time》
- 《PostgreSQL 生成随机数据方法大汇总》
- 《PostgreSQL x分组, y排序, 每组各取(N动态)条 - 子查询+子查询聚合使用》
- 《PostgreSQL 随机查询采样 - 既要真随机、又要高性能 - table sample方法》
- 《沉浸式学习PostgreSQL|PolarDB 1: 短视频推荐去重、UV统计分析场景》
- 《PostgreSQL 15 preview - Use a hash table to speed up NOT IN(values)》
- 《实时营销, 人群圈选推荐业务 性能优化 - memory copy+rb contains计算瓶颈 - rb hash分片》
- 《PostgreSQL 近似算法库 - DataSketches》
- 《UID编码优化 - 用户画像前置规则 (bloom, 固定算法等)》
