《Doris Bitmap 精确去重优化实践.pdf》由会员分享,可在线阅读,更多相关《Doris Bitmap 精确去重优化实践.pdf(35页珍藏版)》请在三个皮匠报告上搜索。
1、DataFunSummit#2023Doris Bitmap精确去重优化实践魏翔-美团-OLAP引擎开发工程师01精确去重简介02Bitmap 聚合性能优化03结合Doris向量化引擎优化04优化效果与总结目录 CONTENTDataFunSummit#202301精确去重简介DataFunSummit#202301精确去重简介去重计算场景与业界解决方案MPP架构两阶段聚合Roaring Bitmap 简介去重场景 去重指标计算 PV,UV的计算 日活用户数 订单量 客户留存(率)去重指标 相较于 普通指标(sum,avg)计算上的复杂度较高因此比较容易成为指标计算的性能瓶颈SELECT dt
2、 AS dt,first_entrance AS first_entrance_code,COUNT(DISTINCT device_id)AS view_uv,FROM TBLA where dt=20230501 and type=view GROUP BY dt,first_entrance业界已有的解决方案1.数仓生产:将各种指标在数仓生产环节提前计算好2.模糊去重:HyperLogLog3.精确去重:导入预聚合,减少现场计算量数仓生产 指标计算层级完全依赖数仓生产指标维度组合指数增长新增指标周期长数仓加工逻辑臃肿模糊去重 HyperLogLog原理 内存桶和哈希函数:将输入数据哈希到
3、多个内存桶中 寻找最长前缀零位(Leading Zero Count,LZC):对每个哈希值计算 LZC 估计基数:通过统计 LZC 的平均值来估计基数 分桶减少误差StdError 1.04m(m=bucketnum)精确去重简介 精确的必要性 重要指标无法近似:金钱相关 数据驱动决策:近似误差会带来误判 灵活维度分析:不同维度下钻分析 MPP架构下精确去重过程:两阶段聚合-Streaming Agg -Merge Agg 数据结构 -明细模型:HashSet -聚合模型:Bitmap(基于Roaring Bitmap实现)去重指标计算去重指标计算优势缺点数仓生产查询时延很低非常不灵活开发周
4、期长模糊去重(HyperLogLog)查询时延适中支持上卷,灵活维度分析存在误差现场计算明细模型:HashSet支持灵活维度分析高基数场景查询时延很高现场计算聚合模型:Bitmap查询时延较高支持上卷,灵活维度分析高基数场景 Bitmap本身比较大计算吞吐和数据分布强相关Roaring Bitmap简介 Roaring Bitmap 数据结构Bitmap 是一种基于位图思想的用于保存聚合后的明细数据(64位非负整数)的数据结构保存明细数据使得其能够支持rollup构建以及任意维度的上卷分析Roaring Bitmap简介 Container TypeContainer Type数据结构大小Ar
5、ray Containerunsigned short 数组size*16 bitBitset Containerbitset65536 bitRunLen ContainerRun length 编码当size 4096 时:bitset container 更省空间Roaring Bitmap简介 Add Value into Bitmap精确去重简介 Union 时间复杂度union container类型时间复杂度array union arrayO(m+n)array union bitsetO(m)bitset union bitsetO(1)runlen union runlen
6、接近 O(1)精确去重简介-小结 关于精确去重指标1.精确去重指标计算的复杂度高2.精确去重场景中Bitmap 兼顾灵活分析和性能 关于Roaring Bitmap1.面向空间优化的2.尽量将计算卸载到 Bitset Container Union 常数时间开销上3.数据不宜太离散,低位连续,减少Container数量膨胀DataFunSummit#202302Bitmap聚合性能优化DataFunSummit#202302Bitmap聚合性能优化现有性能瓶颈基于输入数据布局的优化基于计算流程的优化Doris Bitmap 聚合现有瓶颈基于输入数据布局的优化为什么需要字典编码?映射非数值类型
7、数值类型 低位连续离散值 连续值基于输入数据布局的优化高基数字典 M可能在十/百亿量级基于输入数据布局的优化高基数字典Tablet 编码列分布稀疏单个Bitmap container数量多每个container 内部元数数量少基于输入数据布局的优化字典优化(按日)独立编码:每天一个字典表,减少基数 优势:基数减少几个数量级 缺点:无法解决跨天查询基于输入数据布局的优化正交编码优化 优势:1.Container 数据连续,计算高效2.二阶段聚合优化 劣势:1.预聚合度降低2.数据易倾斜3.无法满足多列去重场景4.Shuffle再聚合,优化效果不明显基于输入数据布局的优化正交编码优化 优势:1.C
8、ontainer 数据连续紧凑2.二阶段聚合优化 劣势:1.预聚合度降低2.数据易倾斜3.无法满足多列去重场景4.Shuffle再聚合,优化效果不明显基于计算流程的优化高基数场景现状:整个bitmap 聚合运算会经历如下阶段1.多次的 array container union操作2.基数超过4096 会转bitset container问题:1.合并container 时元素上涨导致额外内存分配2.单个array container元素数量变多单次union变重解决方案:高基数场景,直接使用bitset,跳过array typebitmap 序列化shuffle时,检查是否需要降级array
9、DataFunSummit#202303结合Doris向量化引擎DataFunSummit#202303结合Doris向量化引擎内存使用优化Fast Union聚合下推Bitmap内存优化触发列拷贝的case1.表达式计算SELECT COUNT(DISTINCT CASE WHEN page_type IN(AAA,BBB)THEN device_id END)FROM TBL2.Join ProbeSELECTCOUNT(DISTICNT a.user_id)FROM a join b ON a.order_id=b.order_idWHERE b.city_name=BEIJINGBit
10、map内存优化Bitmap 列拷贝开销Bitmap 对象比较大大量内存拷贝TCMalloc 释放内存加锁影响并发性能火焰图Expr 计算占比Agg node 56%实际聚合计算的时长不到一半Bitmap内存优化Bitmap 列拷贝优化Jemalloc 替换TcmallocBitmap开启Copy On Writeexpr 计算时长占比从56%14%Bitmap Fast UnionFast Union1.延迟合并2.减少数据移动聚合下推解决的问题AggNode 和 Scanner 吞吐不匹配长范围查询 AggNode 节点瓶颈Scan轻量聚合数据存储时有序无需HashTableBlock 相邻
11、行聚合优势缓解大范围scan 造成的一阶段聚合瓶颈充分利用scanner 线程并发,提高聚合吞吐劣势优化效果和查询模式相关scanner 扫描的数据是按照表keys列排序的DataFunSummit#202304优化效果与总结优化效果 集群规模 3FE+100BE 基于输入数据分布的优化 独立编码:取决于基数减少的量级基数:十亿 亿分区行数:十亿级提升:5倍 正交编码:基数:十亿 千万 分区行数:亿级 提升:10倍优化效果 基于计算流程的优化 高基数不使用array container:基数:亿级以上单分区行数:亿级别维度基数:十/百提升:端倒端时延减少 2030%结合Doris引擎相关优化 Bitmap COW:bitmap 相关衍生列指标,QPS 50以上,端到端时延减少50%Fast Union:Bitmap 精确去重查询端到端时延减少20%聚合下推:分区时间范围超过1年,精确去重查询中端到端时延减少20%总结