Doris Bitmap 精确去重优化实践
魏翔-美团-OLAP引擎开发工程师 DataFunSummit#2023 目录CONTENT 03结合Doris向量化引擎优化 04优化效果与总结 01精确去重简介 DataFunSummit#2023 01 精确去重简介 •去重计算场景与业界解决方案•MPP架构两阶段聚合•RoaringBitmap简介 DataFunSummit#2023 去重场景 •去重指标计算PV，UV的计算日活用户数订单量客户留存(率)…… SELECT`dt` AS `dt`,first_entranceAS `first_entrance_code`,COUNT(DISTINCTdevice_id)AS `view_uv`,FROMTBLAwhere dt=20230501and type = 'view’GROUP BY dt,first_entrance 业界已有的解决方案 去重指标相较于普通指标（sum,avg）计算上的复杂度较高因此比较容易成为指标计算的性能瓶颈 1.数仓生产：将各种指标在数仓生产环节提前计算好2.模糊去重：HyperLogLog3.精确去重：导入预聚合,减少现场计算量 数仓生产 •指标计算层级 完全依赖数仓生产指标 模糊去重HyperLogLog 原理 •内存桶和哈希函数：将输入数据哈希到多个内存桶中•寻找最长前缀零位（Leading Zero Count，LZC）：对每个哈希值计算LZC•估计基数：通过统计LZC的平均值来估计基数 精确去重简介 •精确的必要性 重要指标无法近似：金钱相关数据驱动决策：近似误差会带来误判灵活维度分析：不同维度下钻分析 •MPP架构下精确去重 过程:两阶段聚合-StreamingAgg-MergeAgg数据结构-明细模型: HashSet-聚合模型: Bitmap（基于RoaringBitmap实现） 去重指标计算 RoaringBitmap简介 •RoaringBitmap数据结构 Bitmap是一种基于位图思想的用于保存聚合后的明细数据（64位非负整数）的数据结构保存明细数据使得其能够支持rollup构建以及任意维度的上卷分析 RoaringBitmap简介 •Container Type RoaringBitmap简介 •AddValueintoBitmap 精确去重简介 •Union时间复杂度 精确去重简介--小结 •关于精确去重指标 1.精确去重指标计算的复杂度高2.精确去重场景中Bitmap兼顾灵活分析和性能 •关于RoaringBitmap1.面向空间优化的2.尽量将计算卸载到BitsetContainer Union常数时间开销上3.数据不宜太离散，低位连续，减少Container数量膨胀 02Bitmap聚合性能优化 DataFunSummit#2023 02 Bitmap聚合性能优化 •现有性能瓶颈•基于输入数据布局的优化•基于计算流程的优化 DataFunSummit#2023 DorisBitmap聚合现有瓶颈 基于输入数据布局的优化 为什么需要字典编码？ •映射非数值类型à数值类型 •低位连续离散值à连续值 基于输入数据布局的优化 高基数字典 •M可能在十/百亿量级 基于输入数据布局的优化 高基数字典 •Tablet编码列分布稀疏•单个Bitmapcontainer数量多•每个container内部元数数量少 基于输入数据布局的优化 字典优化 •(按日)独立编码:每天一个字典表，减少基数优势：基数减少几个数量级缺点：无法解决跨天查询 基于输入数据布局的优化 正交编码优化 •优势:1.Container数据连续，计算高效2.二阶段聚合优化 •劣势：1.预聚合度降低2.数据易倾斜3.无法满足多列去重场景4.Shuffle再聚合，优化效果不明显 基于输入数据布局的优化 正交编码优化 •优势:1.Container数据连续紧凑2.二阶段聚合优化 •劣势： 1.预聚合度降低2.数据易倾斜3.无法满足多列去重场景4.Shuffle再聚合，优化效果不明显 基于计算流程的优化 高基数场景 现状：整个bitmap聚合运算会经历如下阶段 1.多次的array container union操作2.基数超过4096会转bitsetcontainer 问题: 1.合并container时元素上涨导致额外内存分配2.单个array container元素数量变多单次union变重 解决方案: •高基数场景，直接使用bitset，跳过array type•bitmap序列化shuffle时，检查是否需要降级array 03结合Doris向量化引擎 DataFunSummit#2023 结合Doris向量化引擎 •内存使用优化•FastUnion•聚合下推 DataFunSummit#2023 Bitmap内存优化 触发列拷贝的case 1.表达式计算SELECTCOUNT(DISTINCTCASE WHEN `page_type` IN (‘AAA’, ‘BBB’)THEN `device_id` END)FROM TBL 2.Join ProbeSELECTCOUNT(DISTICNTa.user_id)FROM a joinbONa.order_id=b.order_idWHEREb.city_name=‘BEIJING’ Bitmap内存优化 Bitmap列拷贝开销 •Bitmap对象比较大 大量内存拷贝TCMalloc释放内存加锁影响并发性能 •火焰图 Expr计算占比Agg node 56%实际聚合计算的时长不到一半 Bitmap内存优化 Bitmap列拷贝优化 •Jemalloc替换Tcmalloc expr计算时长占比从56%à14% •Bitmap开启Copy OnWrite Bitmap Fast Union Fast Union 1.延迟合并2.减少数据移动 聚合下推 解决的问题 •AggNode和Scanner吞吐不匹配•长范围查询AggNode节点瓶颈 Scan轻量聚合 •数据存储时有序•无需HashTable•Block相邻行聚合 优势 •缓解大范围scan造成的一阶段聚合瓶颈•充分利用scanner线程并发，提高聚合吞吐 劣势 •优化效果和查询模式相关scanner扫描的数据是按照表keys列排序的 04优化效果与总结 DataFunSummit#2023 优化效果 •集群规模•3FE+100BE •基于输入数据分布的优化独立编码:取决于基数减少的量级基数：十亿à亿分区行数：十亿级提升:5倍 正交编码:基数：十亿à千万分区行数:亿级提升：10倍 优化效果 •基于计算流程的优化高基数不使用arraycontainer:基数：亿级以上单分区行数：亿级别维度基数：十/百提升：端倒端时延减少20~30% •结合Doris引擎相关优化BitmapCOW:bitmap相关衍生列指标，QPS50以上，端到端时延减少50%FastUnion:Bitmap精确去重查询端到端时延减少20%聚合下推：分区时间范围超过1年，精确去重查询中端到端时延减少20% 总结
