其他
美团 Doris Bitmap 精确去重优化实践
导读 本文将分享美团 Doris Bitmap 去重场景的一些优化与实践。
本次分享主要分为以下四个部分:1. 精确去重简介
2. Bitmap 聚合性能优化
3. 结合 Doris 向量化引擎优化
4. 优化效果与总结
分享嘉宾|魏翔 美团 后端开发工程师
编辑整理|马信宏
内容校对|李瑶
出品社区|DataFun
数仓生产:在 OLAP 引擎现场计算能力出现之前,去重指标的计算可以在数据仓库生产环节完成。数仓中预先计算好指标数据,查询时相当于 online 引擎直接获取提前计算好的结果数据。 模糊去重替代:相较于精确去重,模糊去重具有更高的聚合吞吐量。在某些场景下,可以用模糊去重结果替代精确去重。 预聚合处理:在导入数据时进行预聚合,构建预聚合模型以减少现场精确去重的计算量。通过优化聚合模型,确保精确去重的处理速度。
Bitmap 的优化主要面向空间而非计算。从刚刚介绍的三种 Container 中可以看出 Bitmap 的优化目标是减少空间占用,而非提高计算效率。 优化时应将大量计算卸载到位运算上,这样可以使用高效的向量化位运算指令加速计算,同时能够减少 Array Container 内存开销。 Bitmap 数据结构适用于相对密集的数据。数据最好是低位连续的,否则如果数据过于离散,索引到 Container 的代价会很高,同时 Container 的数量也会很多。
Bitmap 聚合性能优化
非数值类型去重限制
高基数情况下的聚合与吞吐性能问题
内存拷贝开销
在一阶段聚合预算过程中,Doris 基于分片数据进行计算。如果 tablet 中的数据连续,则会形成 Bitset Container,从而提高计算效率。 在二阶段聚合过程中,不同 tablet 中的数据天然无交集。因此,二阶段仅需将一阶段 shuffle 过来的结果相加即可,无需进行 merge 计算。
数据按此方式分布,预聚合度较低。因为按照设备 ID 区间分桶,无法保证所有相同 key 的数据集中在同一区间从而分入同一个桶在桶内聚合。 冗余倾斜问题。不同设备产生的数据量不同,可能导致某些 device ID 的数据量较大,而其他设备的数据量较小。 无法满足多列去重场景。例如,若需按 device ID 和 user ID 进行区间分桶,则无法实现正交。 该优化方法基于一定的前提假设,即数据从 tablet 读取后直接进行聚合。若涉及中间 join 操作和 shuffle 过程,则该前提假设不成立,优化效果将减弱。因此,此优化方法对于单表场景具有显著优势。
索引 keys 数量减少:由于正交编码将数据分散到多个 tablet 中,相同 key 的数据被分布在不同的区间,从而降低了索引 keys 的数量。 Container 优化:在正交编码中,Container 内的数据相对集中,更多地采用 Bitset 或 Run Length 这类存储大量数据且可用位运算的 Container。
多次 Array Container 做 union:由于 Array Container 数量较多,需要进行多次 union 操作。 Array Container 转 Bitset:当 Array Container 超过 4096 时,需将其转换为 Bitset。
额外内存分配:在 Array Container 过程中,元素上涨可能导致额外内存分配。 Union 操作繁重:随着 Array Container 元素增多,union 操作变得复杂,且内部元素可能被多次重复合并。
结合 Doris 向量化引擎优化
优化 bitmap 内存使用和拷贝开销:由于 bitmap 内存使用较大,拷贝开销较高,我们对这部分进行了优化,以降低内存消耗和提高数据处理效率。 引入Fast Union:Roaring Bitmap 支持高效接口,即 Fast Union。我们对向量化引擎进行了改造,以利用 Fast Union 进行更快速的 union 操作。
表达式计算过程中的列拷贝:以 SQL 中的 CASE 语句为例,EXPR 执行计算,并将结果放入最后一列。这个过程必然涉及到从device id 列中拷贝bitmap 对象到expr result 列中的操作。由于 bitmap 较大,拷贝过程可能会变得缓慢。 多表关联时列拷贝:在 join 操作的 probe 阶段,系统会将 build block 和 probe block 中的数据拼接在一起,然后返回上一层。这个过程同样需要进行一次拷贝。
延迟合并:在 Fast Union 中,无需每次合并后都计算 bitmap 的基数,避免了中间计算过程结果的维护开销。计算完成后,直接返回一个 Bitmap,省去了中间变量的维护。 减少数据移动次数:在传统方法中,合并顺序不受控制,可能导致将较大的 Bitmap 移动到较小的 Bitmap 上,造成效率低下。Fast Union 则可以优化这一过程,将较小的 Bitmap 移动到较大的 Bitmap 上,降低数据移动次数。
使用高效的位运算:优化分为两部分。第一部分是针对输入数据的布局进行优化,提高数据处理效率;第二部分是对 bitmap 计算流程进行改造,提高计算性能。 内存优化:使用了更高效的内存分配器和锁机制,降低了内存分配和同步的开销。同时,利用 bitmap 的 copy-on-write 特性,减少了不必要的内存拷贝。 支持 bitmap 的 fast union 接口:通过 fast union 操作,提升去重计算吞吐性能。 聚合下推优化:针对特殊场景,通过并发优化聚合下推过程,进一步提高了性能。
分享嘉宾
INTRODUCTION
魏翔
美团
后端开发工程师
教育经历:2018 ~ 2021, 北京航空航天大学,计算机技术。
工作履历:2021 ~ 至今, 美团基础研发平台。主要工作内容:负责 OLAP 引擎的开发、性能优化相关工作,主要工作内容如下:spark load 导入优化、Doris 向量化改造、Bitmap 精确去重场景优化。