挑战某音短视频核心推荐算法-Demo篇
digoal约 27 分钟原理篇: 点击进入
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里面的数据量, 改小一点, 否则空间不够.
云起实验室地址:
https://developer.aliyun.com/adc/scenario/exp/f55dbfac77c0467a9d3cd95ff6697a31
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开销, 之前已经讲过:
《重新发现PostgreSQL之美 - 23 彭祖的长寿秘诀》
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, 可以压缩空间, 同时提升性能.
);
写入数据: 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 ~ 1000wlid (用户所处的地区码) 取值空间对应前面的
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元
https://www.zhihu.com/question/319130381
存储空间占用情况如下, 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 databasepostgres=# \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测试性能一定还会飙升.
《PostgreSQL 15 preview - Use a hash table to speed up NOT IN(values)》
这是个读多写少的场景. 因为刷新用户标签和视频的权重都可以异步进行, 所以查询占比较高, 可以非常容易的通过增加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类型.
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?
如果你觉得基于喜好标签还比较传统(但是性能好), 想结合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, 固定算法等)》
欢迎关注我的github (https://github.com/digoal/blog) , 学习数据库不迷路.
近期正在写公开课材料, 未来将通过视频号推出.