位图在推荐系统中的妙用
最近正好闲了下来, 有时间做个技术总结吧. 这个还是两年多之前做的需求, 最后选择了位图作为推荐系统的核心数据结构, 过程很有意思, 简单总结一下.
1.业务背景
当初广告对外投放因为整体进线索量不足, 导致很多销售老师很多时间无客户可联系, 但是公海池的线索量多达几百万, 大量的潜在用户需要重新挖掘.
线索量这么大, 怎么更好的利用资源进行触达呢? 首先需要识别出哪些才是好资源, 利用一些用户属性 比如最后沟通时间、沟通时长、是否上过试听课以及额外打的一些标签等进行权重计算, 不过这些属于算法侧的工作, 此篇文章不做详细描述.
根据销售人员和线索消耗量, 决定每天 10w 条线索供给, 质量按从好到坏排序, 销售老师可以选择要或者不要这条线索, 并且要求销售老师如果当天已经推荐过此条线索, 就不能再给他推荐了, 但要按优质顺序推荐给其他人
例如: 销售小王拿到了张三这条线索, 但是感觉这条线索不适合自己, 于是把他扔掉, 之后当天销售小王不会再拿到张三这条线索了, 开始向销售小李推荐线索, 按优质顺序那小李会再次拿到张三这条线索的.
image.png
2.项目分析
项目受众: 销售群体 -> 有明显的操作高峰和低峰, 需要考虑并发问题.
项目目的: 联系关单 -> 只能一个人成单, 不允许出现资源冲突, 也就是说一条客户线索不能同时被两个销售所拥有.
产品诉求: 按算法排好的顺序从上往下推, 推完第一轮推第二轮, 只要资源可以使用就可以.
既然要求顺序, 核心就是遍历推荐, 随着领取越来越多, 越往后性能下降越明显, 遍历的客户线索条数增加, 如果使用数据库作为扫描对象压力过大.
如果使用缓存肯定比数据库性能要高一数量级, 考虑数据结构采用集合或布隆过滤器, 但是集合占用空间较大, 数据比对复杂, 不适于中大型数据规模采用, 例如: 推荐10条未被推荐的数据, 则需要根据已推荐和总推荐数据取差集, 在大数据量场景下是非常局限的.
布隆过滤器底层同样采用位图定位方式, 但设计本身存在数据误差, 对于推荐资产价值高数据无法接受存在可能性误差情况.
最后选择了位图结构, 占用空间小排列连续, 是非常符合当前业务的.
3.项目设计
每日总计 10w 条线索, 每条占用1个bit, 总计占用内存约 12.2 kb. 假定总共1000人, 每人维护一个推荐bit结构, 则共计消耗内存 11.9 M
通过上面的计算看出来, 占用内存还是很小的, 资源方面是OK的, 我们来看下具体的逻辑图.
image.png
上图表示的是每个销售的 bitmap推荐结构, 游标从左到右检查, 标记为1的表示已将当前线索推荐过给他, 或者线索生命周期结束后由全局状态同步过来.
每个销售拥有一个 bitmap推荐结构 并不能解决真正的冲突, 因为你永远不知道别人是否拿到了这条线索, 所以我们同时需要一个管理全局的 bitmap结构.
image.png
其中有 1 的空格表示被临时占领或永久占用, 即使自己的bitmap为0, 只要扫描全局资源为1, 当前销售不能获取
image.png
3.系统优化点
3.1 设置系统最大扫描次数, 不能无限扫描下去.
image.png
3.2 我们知道如果使用bitmap一条一条验证的话, 会大量增加IO次数, 这里我们计算游标值, 采用字符串批量读取, 解析成二进制字符串来进行寻找0
获取字符串
字符串转换二进制
image.png
3.3 资源全局位图与销售位图定期同步不能推荐的线索填充 1, 避免在请求中扫描过多失效线索
image.png
3. 业务模式图
image.png
4. 总结
因为 id 值是单调递增的, 所以这个业务场景实现起来可以直接使用位图
思考如果id值是特别大的话我该怎么实现呢? 留言区交流下吧.