亿级毫秒响应实时推荐系统-解决方案探索(postgresql)
最近接触推荐相关业务需求过程中参考了不少德哥的文章，收益良多，强烈推荐德哥文章链接：https://github.com/digoal
业务应用场景
假如某个主播平台资源中，共有2000w主播，运营关注到Aken在平台上比较喜欢A主播，期盼给他推荐更多和A类似的主播，1个或N多个。
站在技术角度，我们如何去实现？
假如来1个千万级数据全量搜索计算，现有的Mongodb、MySQL、Oracle等技术组件毫秒级有没有这个可能？
为什么要讨论这个问题
DT数据时代，通过用户画像条件组合，快速提取精准目标群体进行精准营销，已经是当今行业的普遍需求。例如：
淘宝平台根据用户购买习惯，推荐相关商品。
头条网站根据用户浏览习惯，推荐相关资讯。
网易云音乐根据用户听歌喜好，推荐相关歌曲。
因此这本质上是一个：实时推荐系统的问题。
通用的解决方案
营销推荐基于用户画像，通用解决方案是给用户贴标签，然后根据标签组合，圈出需要的用户。
表现在数据库层面，通常会用到宽表，以及分布式的系统。宽表用于存储用户标签，例如每个字段代表一个标签，业务查询语句通过标签字段进行组合，搜索符合条件的id，即目标用户或推荐对象。
回到上面主播推荐的业务场景，画像表的设计会是下面这个样子:
create table tab_aken_signature (
uid int primary key,
tag1 float4, -- 主播属性1
tag2 float4, -- 主播属性2...
tagn float4 -- 主播属性n );
通用的解决方案的痛点
l 用户、主播特征属性多，容易突破单表限度
运营为了提高效率效率，标签数量通常会非常多，行业内有100个标签的算是非常小的了，标签高达千个、上万个已不属罕见。因此，标签数量往往会突破关系型DB的字段数量或行宽限制，比如MySQL innodb表字1024上限，比如mongodb的单条文档大小16MB，这时候就需要分库分表，将字段拆解到多个表或集合中。比如目前公司用户画像100多个标签使用Json拆到了多个collection中。拆分后类似join等逻辑需要依靠应用层实现。
l 用户喜好类型多样化，单一索引搜索困难
标签的组合具有不固定性，很难通过单一索引或部分字段索引达到高效检索的目的，如果为提高性能，1千个字段就需要创建1千个索引，存储成本非常高。
l 组件不一定支持智能算法相关计算技术
推荐需要依靠巨大的数据集进行排序，然后去top N，如果数据库组件本身无法高效支持该计算场景，需要应用逻辑计算到具体uid才能进入DB进行key-value进行快速召回。
推荐系统的改进方案
考虑到通用方案存在的以上问题，我们可以将上游计算和数据读取分为两个独立的链路，利用流水上报服务将用户流水操作flink/spark在DB外围计算得到具体的标签、权重等信息，然后将计算结果回写DB或ES、ClickHou集群，并将具体的uid传给推荐服务作为拉取DB数据的条件，这样就实现了具体key获取对应数据的转化。
但前提是必须由下游数仓DW或其他渠道定期供数到在线系统。
改进方案的痛点
整套系统需要依赖数据仓库通过etl/spark/flink等定期加载数据到关系型数据库里面，然后数据计算及推荐服务逻辑完全需要依靠DB外围的算法实现。这里会存在以下几个主要问题：
l 推荐时效只能做到离线推荐或准时性推荐。假设画像数据从数仓按天入库，推荐计算至多只能基于昨天的动态进行，时效延迟1天，无法满足用户行为更新频繁、时效要求高的业务场景，从而可能导致错失不少目标用户群体。比如我昨天在平台浏览并下单购买了笔记本，然后推荐服务今天才对我进行笔记本电脑导购推荐，这个信息完全延迟了一天，哪怕你的推荐算法再精确，我早已经成为了无效目标用户。
l 数据一致性问题计算层缓存需定期回写DB，会和数据库存储之间存在一定的延迟，对数据一致性较高的服务，会有更大的挑战，需要加大成本优化。
l 性能可能比较低完整的推荐逻辑需要多个架构层及系统进行交互，目前接触的系统如果推荐请求可以直接命中推荐服务本地cache，则完整的推荐逻辑大概耗时300~400ms，当推荐请求无法命中本地cache，重走召回逻辑，则耗时大概700~800ms甚至更高。
l 需要独立的智能算法团队支持，比如向量计算相关的开发技术。
基于PostgreSQL的新方案探索
首先，对于推荐系统，我理解的核心思想有两点：
1.给用户推荐那些和他们喜欢物品相似的物品。
2.喜欢物品怎么表示，以及物品之间相似度怎么计算是需要我们重点考虑的。
l 新方案探索-数据表示画像属性：从多列标签或多key设计方式，将特征数据位图化、向量化（内容、用户、环境等）
uid int ---primary key，每个uid代表一个推荐对象
tagval bit(64) ---文本标签转位图
tagarr text[] ---元素列表或元组加权
l 新方案探索-数据存储当特征数据位图和向量化之后，我们并不需要传统的宽表模式。
akendb=# \d+ tab_aken_signature
Table "public.tab_aken_signature"
Column | Type | Collation | Nullable | Default | Storage | Stats target | Description
--------+---------+-----------+----------+---------+----------+--------------+-------------
id | integer | | | | plain | |
tagval | bit(64) | | | | extended | |
tagarr | text[] | | | | extended | |
Indexes:
"idx_tagarr" gin (tagarr _text_sml_ops)
Access method: heapakendb=#
l 新方案探索-索引方式
从Btree改为gin索引(Generalized Inverted Index)。gin存储 (key, posting list), 和Btree相比，gin索引更适合多值类型的元素搜索。
akendb=# create extension smlar;
CREATE EXTENSIONakendb=# create index idx_signature on tab_aken_signature using gin(tagarr _text_sml_ops )
l 新方案探索-数据计算基于向量矩阵，使用相似算法，如：Euclidean Distancen、overlap distance等。
select id,tagarr from tab_aken_signature
where tagarr % '{1_0110110101111001,2_0111100111100000,3_1010110010111110,4_1011111011110100}'
limit 10;
关于PostgreSQL兼容的更多相似算法，参考：https://github.com/eulerto/pg_similarity
l 新方案探索-测试模型随机1亿主播，设置64个主播特征，向量化。
insert into tab_aken_signature
select id,val::bit(64),regexp_split_to_array('1_'||substring(val,1,16)||',2_'||substring(val,17,16)||',3_'||substring(val,33,16)||',4_'||substring(val,41,16), ',')
from (select id, (sqrt(random())::numeric*9223372036854775807*2-9223372036854775807::numeric)::int8::bit(64)::text as val from generate_series(1,156250) t(id)) t;
nohup pgbench -h 9.107.133.92 -p 11005 -U tbase -d akendb -M prepared -n -r -P 1 -f ./test.sql -c 64 -j 10 -t 10 &
测试数据验证：
akendb=# select count(*) from tab_aken_signature;
count
-----------
100000000
(1 row)akendb=# select * from tab_aken_signature limit 10;
id | tagval | tagarr -------------------------------------------------------------+-------------------------------------------------------------------------------
1 | 0101011101100100100101111001000100010110101011101111111001100111 | {1_0101011101100100,2_1001011110010001,3_0001011010101110,4_1010111011111110}
2 | 1110001100010000101010110010010000111110110000011000100001001011 | {1_1110001100010000,2_1010101100100100,3_0011111011000001,4_1100000110001000}
3 | 0110111011001011001101110111111111001000011101010010010000100100 | {1_0110111011001011,2_0011011101111111,3_1100100001110101,4_0111010100100100}
l 推荐测试1-以点搜点场景：以歌搜单曲、以人搜人（主播）等。如下根据用户喜好，在1亿主播中推荐最类似的主播，耗时Time: 2.643 ms。
akendb=# set smlar.type = overlap;
akendb=# set smlar.threshold = 2; --在相似度超过50%的主播中推荐完全相似的1个
akendb=# select smlar( tagarr, '{1_0100001010100000,2_0100111110001111,3_0100111111101101,4_1110110100101101}') as similarity,
length(replace(bitxor(bit'0100001010100000010011111000111101001111111011010010110100101111', tagval)::text,'0','')) hm_distance,*
from tab_aken_signature
where tagarr % '{1_0100001010100000,2_0100111110001111,3_0100111111101101,4_1110110100101101}' and length(replace(bitxor(bit'0100001010100000010011111000111101001111111011010010110100101111', tagval)::text,'0','')) < 2 limit 100;
similarity | hm_distance | id | tagval | tagarr
--------+-------------+----+------------------------------------------------------------------+---------------------------------------------------- 4 | 0 | 8 | 0100001010100000010011111000111101001111111011010010110100101111 | {1_0100001010100000,2_0100111110001111,3_0100111111101101,4_1110110100101101}
(1 row)Time: 2.643
msakendb=#
l 推荐测试1-以点搜群场景：以文章搜文章集合、以歌曲搜歌单列表、以人搜社交群体等。如下根据用户喜好，在1亿数据中且相似度超过50%的主播中推荐30个（或N个）主播，耗时Time: 2.797 ms
akendb=# set smlar.type = overlap;
akendb=# set smlar.threshold = 2; --在相似度超过50%的主播中推荐最相似的30个
akendb=#select smlar( tagarr, '{1_0100001010100000,2_0100111110001111,3_0100111111101101,4_1110110100101101}') as similarity ,
length(replace(bitxor(bit'0100001010100000010011111000111101001111111011010010110100101111', tagval)::text,'0','')) as hm_distance,id,tagarr
from tab_aken_signature
where tagarr % '{1_0100001010100000,2_0100111110001111,3_0100111111101101,4_1110110100101101}' order by similarity desc,hm_distance
limit 30;
similarity | hm_distance | id | tagarr
------------+-------------+--------+-------------------------------------------------------------------------------
4 | 0 | 8 | {1_0100001010100000,2_0100111110001111,3_0100111111101101,4_1110110100101101}
2 | 13 | 73473 | {1_0101001001100010,2_0100011000001110,3_0100111111101101,4_1110110100101101}
2 | 16 | 27276 | {1_0101001111000101,2_0101010000001111,3_0100111111101101,4_1110110100101101}
2 | 16 | 82574 | {1_0101010011110001,2_0111001101001010,3_0100111111101101,4_1110110100101101}
2 | 18 | 55714 | {1_0111110101111011,2_1100111110111110,3_0100111111101101,4_1110110100101101}
2 | 18 | 68023 | {1_0101101010001100,2_1000111111110011,3_0100111111101101,4_1110110100101101}
2 | 20 | 153629 | {1_0111001011001110,2_0001100111111010,3_0100111111101101,4_1110110100101101}
2 | 20 | 100863 | {1_0100100000101101,2_1011101101101110,3_0100111111101101,4_1110110100101101}
2 | 24 | 149608 | {1_1010110011111011,2_0011001010000001,3_0100111111101101,4_1110110100101101}
2 | 24 | 56512 | {1_0010101100010110,2_1001101000100010,3_0100111111101101,4_1110110100101101}
2 | 26 | 78559 | {1_1011001010001110,2_0011010101000000,3_0100111111101101,4_1110110100101101}
(11 rows)
Time: 2.797 msakendb=#
l 新方案探索-效果对比1.相对于通用流行方案，新方案可以将服务时效从秒级的离线推荐晋级到毫秒级实时推荐。2.索相对于通用流行方案，新方案在索引及数据计算上，在传统btree基础丰富了如gin、gist等索引技术，通过简单extension扩展即可支持多种相似算法，无需依赖独立的向量计算技术攻坚团队。当然，如果公司内有专业算法团队，能将相关算法扩展到pg则会更好。3.索相对于通用流行方案，新方案在整体的架构和组件复合上会显得更加精简，对组件的运维复杂度及运营成本也会随之下降，而在架构上给系统加持cache来解决高并发问题，将会使基于pg的方案显得更加强健。
>>>
参考资料
1.https://github.com/digoal
2.https://github.com/jirutka/smlar
3.https://github.com/eulerto/pg_similarity
- 发表于 2020-12-10 14:06
- 阅读 ( 50 )
