对 2000 多亿条数据做一次 group by 需要多久？

2020-02-27 892浏览

1.对2000多亿条数据做一次 Group By需要多久易杰@腾讯
2.
3.关于我 06年加入腾讯现负责社交广告引擎研发关注高性能架构
4.• 章节1 业务背景 • 章节2 系统架构 • 章节3 核心实现 • 章节4 性能数据 • 章节5 总结
5.腾讯社交广告 • 覆盖8亿优质用户 • 精准的定向能力
6.多维数据分析场景异动分析广告效果诊断提升收入大盘分析合约广告锁量用户出价建议曝光和人群预估朋友圈 11- 20- 12点 30岁广东目标人群覆盖男性广告效果人群管理分析和扩展定向人群用户画像预估分析铜牌会活跃用员户消费能力分析相似人群扩展多维交叉分析年龄段分析手机品牌分析营销策略制定
7.多维数据分析场景  多维度人群下钻分析  相似人群扩展  时延<100ms
8.SQL举例 • 广告主查询用户年龄的分布 select age, count(*) from log where advertiser_id=123 group by age; • 运营查询不同曝光次数的用户的占比、点击率、收入等 SELECT exposure_num, COUNT(*) as user_num, SUM(sum_click) / SUM(exposure_num) as click_rate, SUM(sum_cost) AS total_cost FROM (SELECT qq, COUNT(*) AS exposure_num, SUM(click_count) AS sum_click, SUM(cost) AS sum_cost FROM log GROUP BY qq) temp_table GROUP BY exposure_num;
9.系统目标流程描述：原始数据集高性能过滤 Where 分组 Group by 低成本聚合 Sum Count … 结果可扩展 • 千亿规模原始数据集 • 索引规模相对原始数据集膨胀可控 • 增量数据修改 • （毫）秒级端到端响应 • 利用SSD磁盘，降低内存使用 • 接口易用，支持SQL/RPC 业界实现：SQL-on-Hadoop(Hive/Dremel/Kylin/Drill)、Druid 自研：Pivot
10.• 章节1 业务背景 • 章节2 系统架构 • 章节3 核心实现 • 章节4 性能数据 • 章节5 总结
11.系统架构 PhpMy Admin SQL RPC  全量+增量，满足多种需求查询引擎过滤数据导出分组聚合全量索引全量数据 MapReduce 全量索引增量索引增量数据 Spark Streaming  索引分片，多级聚合  标准SQL接口，降低使用门槛  唯快不破
12.Lambda架构
13.• 章节1 业务背景 • 章节2 系统架构 • 章节3 核心实现 • 章节4 性能数据 • 章节5 总结
14.索引文件设计索引数据结构：全局信息检索查询流程：查询条 • Where age>=20 and age<30 件命中列 • 找到age满足条件的列值ID 值倒排拉 • 拉出列值对应的倒排拉链链集合运 • 根据逻辑对结果进行集合运算算列值字典倒排数据正排数据每一列(Column)的值列值ID对应的文档ID 列式存储的压缩数据编码为列值(Term ) ID 列表
15.列值字典String压缩 • 前缀压缩节省空间 • 例如词表：{“aa”, “abc”, “abcd”, “abd”, “abe”} • 实现采用更高效的Vector前缀压缩 • 词ID快速定位
16.倒排数据存储 • 倒排 – 列值对应的文档ID列表 • 位图（Bitmap）压缩存放倒排拉链列表 • RoaringBitmap支持AND、OR等运算，线性性能 • 根据元素个数动态选择有序数组或bitmap存储 • 基于RoaringBitmap源码做了存储和性能的优化 Roaring与其他位图算法的性能比较： Roaring性能最优
17.正排数据存储  60%的索引空间是正排数据  减少磁盘IO访问-列存储  最大程度节省磁盘空间-编码压缩数据编码步骤：简单类型预配置编码算法变长类型抽样编码对比选择编码算法筛选11种编定长类型编码：定长数组编码、列值个数索引编码、定长列表编码、变长列表编码码算法 String类型编码：单string长度索引编码、多string长度索引编码、单string列表编码、多string列表编码简单字典编码：适用列值重复较多的string类型 Huffman字典编码：列值分布不均匀情况下对简单字典编码的优化二进制String编码：较特殊的二进制数据类型
18.正排数据压缩编码 • 定长数组编码 • 适用列值取值平均个数约等于最大值，譬如年龄 • 数值压缩存放 • 定长列表编码 • 适用列值稀疏情形 • 文档ID差值压缩存放
19.分组（Group By）实现 • 基于排序 • 代价高， O(n*log(n)) • 数据库Group by未命中索引时 • 基于索引 • 同一组的数据在此索引(有序) 连续排列 • 数据库Group by有序命中索引时
20.遍历正排数据实现分组 • 按照列的顺序逐列分组 • 当列值作为key，map规模可控 • 按照树形结构进行分组 • 一个文档可能被分到多个组分层Group By Doc Id到group Id映射
21.基于倒排数据实现分组 • 集合求交更快 • 适用分组数较少时倒排分层Group By 集合求交
22.分组性能对比 • 6000万条数据，按照性别、年龄两列分组查询 6 5 5 4 3 2 1 0.3 0 基于排序的算法 Pivot算法耗时（秒）
23.求和实现算法（SUM） • Group By后对各个组的某列进行SUM求和 • 借鉴Group by算法，实现了两种SUM算法基于倒排集合求交基于列值字典遍历正排 累加变乘法，操作结果集数量级优化 方法和Group By类似 适用结果集合总数较少时 适用结果集合总数很大时
24.分区管理 • 数据存储与管理 • 方便对“过期”数据清理 • 提升查询性能 • 大部分请求并不需要检索全量数据 • 缩小数据扫描范围 • 关键字Partition • select count(*) from log partition('20170201','20170202');
25.优先级调度 • 不抢占 • 先到先处理处理切片数据 • 任务级优先调度 • 先处理优先级高的任务 • 分片级优先调度 • 更细粒度的调度是否有高优先级任务 Y N 当前任务下一片数据高优先级任务
26.插件设计 • 开放Functor
27.索引更新设计 • 公司TDW集群管理索引，可靠性高 • 支持增量更新 • 譬如用户的行为（标签）会随时变更 • 打补丁更新方式，记录新增和删除的增量索引 • 增量索引和检索独立部署 – 避免IO干扰增量索引设计：全量索引新增索引 dump 新增文档删除索引旧增量索引 dump 删除文档增量文档 Build 新增索引删除索引新增量索引
28.并行计算设计有序中间结果有序中间结果索引切片索引切片过滤->分组-> 聚合过滤->分组-> 聚合多索引切片并行处理 … 中间结果管理逻辑有序中间结果独立可并行计算数据集  可配置内存空间管理，中间结果可导出到磁盘  聚合过程独立并行  一致性哈希算法（google jump Consistent hash），切分数据均匀 …… 独立可并行计算数据集单节点结果集 …… 聚合服务最终结果集有序中间结果独立可并行计算数据集聚合聚合聚合不重叠结果集 …… 不重叠结果集聚合单个检索节点内部计算流程 … 单节点结果集
29.• 章节1 业务背景 • 章节2 系统架构 • 章节3 核心实现 • 章节4 性能数据 • 章节5 总结
30.性能数据 • Pivot VS Druid：Druid索引小，Pivot查询快数量级
31.性能数据
32.性能数据
33.性能数据
34.• 章节1 业务背景 • 章节2 系统架构 • 章节3 核心实现 • 章节4 性能数据 • 章节5 总结
35.总结 • 进一步完善SQL • 资源管理
36.Thanks