Doris Bitmap 精确去重优化实践

DorisBitmap精确去重优化实践 魏翔-美团-OLAP引擎开发工程师 DataFunSummit#2023 01精确去重简介 目录 CONTENT 03结合Doris向量化引擎优化 02Bitmap聚合性能优化04优化效果与总结 01 精确去重简介 DataFunSummit#2023 01 精确去重简介 •去重计算场景与业界解决方案 •MPP架构两阶段聚合 •RoaringBitmap简介 DataFunSummit#2023 •去重指标计算 PV，UV的计算日活用户数 订单量 客户留存(率) …… 去重指标相较于普通指标（sum,avg）计算上的复杂度较高 因此比较容易成为指标计算的性能瓶颈 SELECT `dt`AS`dt`, first_entranceAS`first_entrance_code`,COUNT(DISTINCTdevice_id)AS`view_uv`,FROMTBLA wheredt=20230501andtype='view’ GROUPBYdt,first_entrance 业界已有的解决方案 1.数仓生产：将各种指标在数仓生产环节提前计算好 2.模糊去重：HyperLogLog 3.精确去重：导入预聚合,减少现场计算量 •指标计算层级 完全依赖数仓生产指标 •维度组合指数增长 •新增指标周期长 •数仓加工逻辑臃肿 原理 •内存桶和哈希函数：将输入数据哈希到多个内存桶中 •寻找最长前缀零位（LeadingZeroCount，LZC）：对每个哈希值计算LZC •估计基数：通过统计LZC的平均值来估计基数 m StdError≈1.04(m=bucketnum) •精确的必要性 重要指标无法近似：金钱相关 数据驱动决策：近似误差会带来误判灵活维度分析：不同维度下钻分析 •MPP架构下精确去重 过程:两阶段聚合 -StreamingAgg -MergeAgg数据结构 -明细模型:HashSet -聚合模型:Bitmap（基于RoaringBitmap实现） 去重指标计算 去重指标计算 优势 缺点 数仓生产 •查询时延很低 •非常不灵活•开发周期长 模糊去重（HyperLogLog） •查询时延适中•支持上卷，灵活维度分析 •存在误差 现场计算—明细模型:HashSet •支持灵活维度分析 •高基数场景查询时延很高 现场计算—聚合模型:Bitmap •查询时延较高•支持上卷，灵活维度分析 •高基数场景Bitmap本身比较大•计算吞吐和数据分布强相关 •RoaringBitmap数据结构 Bitmap是一种基于位图思想的用于保存聚合后的明细数据（64位非负整数）的数据结构保存明细数据使得其能够支持rollup构建以及任意维度的上卷分析 •ContainerType ContainerType 数据结构 大小 ArrayContainer unsignedshort数组 size*16bit BitsetContainer bitset 65536bit RunLenContainer Runlength编码 当size>4096时: bitsetcontainer更省空间 •AddValueintoBitmap •Union时间复杂度 unioncontainer类型 时间复杂度 arrayunionarray O(m+n) arrayunionbitset O(m) bitsetunionbitset O(1) runlenunionrunlen 接近O(1) •关于精确去重指标 1.精确去重指标计算的复杂度高 2.精确去重场景中Bitmap兼顾灵活分析和性能 •关于RoaringBitmap 1.面向空间优化的 2.尽量将计算卸载到BitsetContainerUnion常数时间开销上 3.数据不宜太离散，低位连续，减少Container数量膨胀 02 Bitmap聚合性能优化 DataFunSummit#2023 02 Bitmap聚合性能优化 •现有性能瓶颈 •基于输入数据布局的优化 •基于计算流程的优化 DataFunSummit#2023 为什么需要字典编码？ •映射 非数值类型数值类型 •低位连续 离散值连续值 高基数字典 •M可能在十/百亿量级 高基数字典 •Tablet编码列分布稀疏 •单个Bitmapcontainer数量多 •每个container内部元数数量少 字典优化 •(按日)独立编码:每天一个字典表，减少基数 优势：基数减少几个数量级缺点：无法解决跨天查询 正交编码优化 •优势: 1.Container数据连续，计算高效 2.二阶段聚合优化 •劣势： 1.预聚合度降低 2.数据易倾斜 3.无法满足多列去重场景 4.Shuffle再聚合，优化效果不明显 正交编码优化 •优势: 1.Container数据连续紧凑 2.二阶段聚合优化 •劣势： 1.预聚合度降低 2.数据易倾斜 3.无法满足多列去重场景 4.Shuffle再聚合，优化效果不明显 高基数场景 现状：整个bitmap聚合运算会经历如下阶段 1.多次的arraycontainerunion操作 2.基数超过4096会转bitsetcontainer 问题: 1.合并container时元素上涨导致额外内存分配 2.单个arraycontainer元素数量变多单次union变重 解决方案: •高基数场景，直接使用bitset，跳过arraytype •bitmap序列化shuffle时，检查是否需要降级array 03 结合Doris向量化引擎 DataFunSummit#2023 03 结合Doris向量化引擎 •内存使用优化 •FastUnion •聚合下推 DataFunSummit#2023 触发列拷贝的case 1.表达式计算SELECTCOUNT(DISTINCT CASEWHEN`page_type`IN(‘AAA’,‘BBB’)THEN`device_id`END) FROMTBL 2.JoinProbe SELECT COUNT(DISTICNTa.user_id)FROMajoinb ONa.order_id=b.order_idWHEREb.city_name=‘BEIJING’ Bitmap列拷贝开销 •Bitmap对象比较大大量内存拷贝 TCMalloc释放内存加锁影响并发性能 •火焰图 Expr计算占比Aggnode56%实际聚合计算的时长不到一半 Bitmap列拷贝优化 •Jemalloc替换Tcmalloc •Bitmap开启CopyOnWrite expr计算时长占比从56%14% FastUnion 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% 总结