大数据下的大表JOIM计算和优化.pdf

大数据下的大表join计算和优化 talkingdata tech vp 周海鹏 2014-10 移动大数据 “人们“人们”眼中的眼中的talkingdata app analytics game analytics mobile ad tracking enterprise 游戏运营分析 移动广告监测 企业级解决方案 移动应用统计分析 11500+11500+ l 应用款数 7 7.5.5亿亿+ + l 累计覆盖 25250000万万+ + l 日活设备 3 35%5%覆盖 覆盖 l top盈收游戏 2 2.5.5亿亿+ + l 玩家覆盖 1 1000000万万+ + l 日活玩家 4 49 9家家 l 网盟对接 4 40%0%覆盖 覆盖 l 行业广告主 15150000万点击 万点击 l 日监测点 l 两大两大一线应用市场 l 三大三大运营商 l 四大四大银行 移动大数据 业务模型业务模型 talkingdata 大数据平台 移动互联网 数据 人口统计学 信息 web 浏览日志 日常生活 数据 广告行业 投放、优化、 防作弊 o2o 旅游、餐饮、社区 游戏 虚拟生活 金融、证券 汽车、健康 服务 移动大数据 我们面临的需求和我们面临的需求和挑战（挑战（3个个v） 秒级别查询秒级别查询 分钟级别更新分钟级别更新 多维查询多维查询 交互式查询交互式查询 8亿设备亿设备 2500w日活日活 移动大数据 传统技术体系和缺陷传统技术体系和缺陷 u 大数据量大数据量查询速度慢 查询速度慢 u 大集群构建大集群构建成本高昂成本高昂 u 多维交叉多维交叉计算能力低效计算能力低效 u 流式计算流式计算无法回朔无法回朔 移动大数据 大表大表join操作的难点和解决思路操作的难点和解决思路：bitmap u 以以bitmap计算替换原始日志扫描计算替换原始日志扫描（优化存储优化存储，降低成本降低成本） hash join hash table l location s location hash join hash table a agent hash join hash table c customer u 高效的内存计算（高效的内存计算（优化速度优化速度，优化功能优化功能） u 优化优化：逻辑计算等价逻辑计算等价 u 优化优化：串行改并行串行改并行 移动大数据 bitmap是什么是什么 bitmap indexes have traditionally been considered to work well for low-cardinality columns, which have a modest number of distinct values, either absolutely, or relative to the number of records that contain the data. /wiki/bitmap_index#cite_note-ewah-13 u 光谱分析光谱分析、恒星数据分析（恒星数据分析（1990年之前年之前） u oracle db index 移动大数据 bitmap的生成的生成 移动大数据 bitmap查询如何完成业务逻辑查询如何完成业务逻辑 select count（*（*） from user where user.status = married and user.region = central or user.region = west status = “married” region = “central” region = “west” 0 1 1 0 0 1 and 0 1 0 0 1 1 0 0 1 1 0 0 or 0 1 1 0 0 1 0 1 1 1 1 1 = and 0 1 1 0 0 1 = 移动大数据 bitmap的实现的实现、压缩算法和参考压缩算法和参考 u 原生bitmap（java） u wah（word-aligned hybrid ） /p/javaewah/ u conciseset（talkingdata） /metamx/extendedset u fastbit（vertica） /fastbit/ u 参考资料 /wiki/bitmap_index 移动大数据 bitmap 在计算上的效能在计算上的效能 left outer join (select devid from activeuser where job_time=20141008001501 and productid=3012470 group by devid) l on (n.devid=l.devid) where l.devid is not null; (select devid from newuser where job_time=20141007001501 and productid=3012470) n select count(*) from 移动大数据 bitmap 在计算上的效能在计算上的效能 0 1000000 2000000 3000000 4000000 5000000 6000000 7000000 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 查询效率（查询效率（ns） hive(4个datanode节点) bitmap（1个计算节点） 查询效率（查询效率（ms） 172672 904 移动大数据 bitmap 在存储上的在存储上的效能效能 原始日志 bitmap 存储性能 存储性能 500 t 0.9 t 移动大数据 bitmap优化（代数运算等价变换优化（代数运算等价变换） u 降序计算 u 先与后或 u 分拆计算-fork-join u 分拆计算-分布式 移动大数据 商业案例商业案例 u 激活客户：20，0000 u 营销成本：500，0000 u 激活客户：10，0000 u 管理成本：1000，0000 移动大数据 总结总结 u 开源（archsum