MaxCompute 海量数据点查介绍for混合云

本文涉及的产品
云原生大数据计算服务 MaxCompute,5000CU*H 100GB 3个月
云原生大数据计算服务MaxCompute,500CU*H 100GB 3个月
简介: 客户需对近3-6个月归档数据进行快速全量查询的需求,涉及查询的423T数据量,达到引擎默认任务数上限,且资源消耗巨大,等于几乎无法查询, 且看maxcompute的海量数据查询方案如何应对这样的场景。

感谢MaxCompute混合云owner 赵奕捷(陆东)  提供的项目分享和技术经验。陆东 是该项目的负责人


项目背景:

      XX客户需求,对目标表过去3-6个月内的数据做全量查询,查询条件是针对固定3列的任意组合查询,结果集的数据量一般小于万级别。 客户期望能够将执行结果在20s内返回。  


    当前难点:客户目标表单日分区的大小: 约500亿条,压缩后逻辑大小在4.7T 左右。   那么3个月的数据则大概在432T,按256M一个split算, 查询约要169万的instance实例,远超过MaxC 最大10万的限制,且会占用大量计算资源, 客户集群的规模在万core级别,接近一整天资源都无法执行返回。


    我们的目标:是能够帮助客户将上文提到的“3-6个月内的固定3列组合查询,在20s内返回”。

    SA的难处:  目前原始数据在200T以上的简单查询(一个or几个where条件),当前市面可以覆盖性能要求的产品,无法同时支持那么大数据量和客户成本。


如何解决问题:

    我们想到数据基于某些列hashcluster聚合或者zorder聚合能力后,再按需计算出每个物理文件指定列的BloomFilter作为海量数据的多列索引文件(BloomFilter文件大小相对于原数据文件大小,几乎可以忽略不计,所以遍历查询BloomFilter非常快)。 相当于数据基于某些列的hashcluster或zorder聚合后,不仅能快速查询指定列(hash,zorder聚合列),还能得到指定bloomfilter的列查询性能收益。 尤其是hash或zorder列 和bloomfilter列有很强的业务相关性时

先介绍下什么是bloomfilter:

    Question1:

       假设一个Int占4字节,那20亿个连续Int,占用的空间约为

       (2000000000*4/1024/1024/1024)≈7.45GB

       有什么办法可以用小一个数量级的空间存储这20亿个数字呢?



      A:如果按位存储就不一样了,20亿个连续Int,占用空间约为  

       (2000000000/8/1024/1024/1024)≈0.233G    

     


      怎么存? bitmap

      比如要表示{1,2,4,6} 用连续8个bit ,分别将 index 1,2,4,6位 设置成1 就可以存储,并快速查询了。   (如果有重复? 怎么办)

  t1.png

      21亿 差不多就是正整数int(2^31)的范围。这样想下,正整数范围内,给定任意长度数组。  用bitmap做排序的话 使用0.233G的空间,可以做到O(N)的时间复杂度。     而快排 ,归并,堆排之类的时间复杂度都在O(NlogN)    

      用处:    很多,高效排序,去重,查询。 这里额外说下数据库的位图索引。

      假设某个地域的人口基本信息表,是1000万条记录的表 ,  主要字段为"姓,名,性别,婚姻状态,区,年龄" 。比如要查询  "男并且已婚  and babala",用bitmap做索引可以做成  

    t2.png 2个向量

    t3.png 3个向量    

     将 男向量 和  已婚向量  与下 ,就能得出“男并且已婚”

    位图索引两个优势,1)用很小空间就能知道所有行, 这两个列的状态 ,不需要访问数据 2)求交集的时候 ,不需要两层循环,时间复杂度 从O(n方) 降到 O(N)


  Question2:

     假设一个爬虫程序,你可能会爬到重复的网页,(网页间错综复杂有无限循环),为了避免,需要知道 每次访问的页面 之前是否已经爬过?

     比较高效的方法的 建立一个宽 bitmap 。 每个URL经过一个哈希函数映射到某一bit位。这样基本就能用O(1) 的效率来查询了。       但问题是,随着爬得urls的数量越多,hash冲突的概率就越高。

      若要降低冲突发生的概率到1%,现有的hash算法 ,需要要将BitSet的长度设置为URL个数的100倍。

      假设一亿条URL(ndv),就得把BitSet长度设为100亿(将近1G多空间) 。

 

     对于Q2的解法 是BloomFilter

     url的字符串str,分别计算h(1,str),h(2,str)…… h(k,str)。然后分别将BitSet的第h(1,str)、h(2,str)…… h(k,str)位设为1

  t4.png

  • 若一个字符串对应的Bit不全为1,则可以肯定该字符串一定没有被Bloom Filter记录过。(这是显然的,因为字符串被记录过,其对应的二进制位肯定全部被设为1了)


  • 但是若一个字符串对应的Bit全为1,也有小概率是未被记录过的。  (如果我的bit够小,那hash冲突的概率很高)


     为了降低冲突率,所以需要了解bloomfilter的参数

     m : BitSet 位数
     n : 插入字符串个数
     k :hash函数个数
     当然,哈希函数也是影响的重要因素 (其实可以通过一些机器学习的手段,找出冲突概率最小的几种模型,用于实战)

    t5.png

   从表格来看 m/n越大越准,k越大越准。   基本上 有2,3个hash函数, BitSet位数,是插入个数的2倍,就可以将冲突率降低到1%以下, 而上文提到hashmap是需要100倍才可以将冲突率降到1%

    t6.png

 冲突率的公式:

  t9.jpg

再介绍什么是zorder:

Z-Order是一个空间填充曲线,用于把多维数据映射到一维数据上,并且尽可能得保持映射前后的相邻位置关系(locality),也就是说多维空间上相邻的点在一维的线上仍然是相邻的

t10.jpg

eg:上图中我要访问x = 0, y = 0、x = 1, y = 0、 x = 0, y = 1 和 x = 1, y = 1 (右图的0,1,2,3)四个数据

  • 在Zorder(y,x)排序里,走一个之字形,连续3步访问4点就可以访问全(下图左)
  • 在传统按y,x排序,需要9步10个点才可以访问全(下图右)
  • 想象下地理位置: 经纬度相近的点,在物理上更靠近的存储,应用中访问更高效。 t11.jpg

最终使用BloomFilter+Zorder的方案

T12.jpg

   

      如模拟客户表接口, 假定客户user表的userid,作为hashcluster聚合,再指定user的电话号,和 门牌地址码(以上数据均为测试模拟数据) 作为BloomFilter建。 在500亿级别的数据中,指定user 的电话号,或者 按地址查询user,都能秒级返回结果。 因为通过userid hash聚合已经将user按相同userid打散存放在对应hash分桶的物理文件中。

      此时通过电话号查询,电话号和user基本是N对1关系(通常N比较小,一个人拥有2,3个电话号),通过电话号的bloomfilter文件过滤出来的真实表物理文件也只有1个(对应userid所在的hash分桶的文件),故查询非常快。

      此时通过门牌地址查询,门牌地址和user基本是1对N(且通常N<10,一个地址被几个家庭成员所共享),所以maxcompute最多会启动N个slot去查询,对于maxcompute这样的分布式系统,并发查10个文件是非常快,且占用资源量非常低的。

      同样场景如果不做hash聚合或者bloomfilter, 会有两个大劣势:

          1)查询电话号码或地址,要去500亿记录的每个物理文件中查询,据上文陈述,这里需要启动169万个slot。相比上面例子的1个 和 N个。差了很多个数据量级

          2)如果只做hash聚合不做bloomfilter,那除hash列其他列无查询收益。依然会启动169万个slot。


      测试:  模拟单分区60E条 ,针对local_num,id_card, add_num 3列的组合查询 ,每条数据15列包含前3列,大小在0.4k左右,总大小3T。

      local号码(电话)、id_card(userid) 组合成zorder聚合 ; local_num(电话),id_card(userid), add_num(地址)3列分别都设置成BloomFilter

      测试如下查询query(测试数据均为模拟数据)

Q1: select * from test_final where local_num='13000002444’;

Q2: select * from test_final where add_num='13000002915’;

Q3: select * from test_final where id_card='130000024443141592’;

Q4: select * from test_final where local_num='13000002444' and add_num='13000002915’;

Q5: select * from test_final where local_num='13000002444' and add_num='13000002915' and id_card='130000024443141592';

      能看到其查询性能差异显著甚至是2个数量级的

    t13.jpg




相关实践学习
基于MaxCompute的热门话题分析
本实验围绕社交用户发布的文章做了详尽的分析,通过分析能得到用户群体年龄分布,性别分布,地理位置分布,以及热门话题的热度。
SaaS 模式云数据仓库必修课
本课程由阿里云开发者社区和阿里云大数据团队共同出品,是SaaS模式云原生数据仓库领导者MaxCompute核心课程。本课程由阿里云资深产品和技术专家们从概念到方法,从场景到实践,体系化的将阿里巴巴飞天大数据平台10多年的经过验证的方法与实践深入浅出的讲给开发者们。帮助大数据开发者快速了解并掌握SaaS模式的云原生的数据仓库,助力开发者学习了解先进的技术栈,并能在实际业务中敏捷的进行大数据分析,赋能企业业务。 通过本课程可以了解SaaS模式云原生数据仓库领导者MaxCompute核心功能及典型适用场景,可应用MaxCompute实现数仓搭建,快速进行大数据分析。适合大数据工程师、大数据分析师 大量数据需要处理、存储和管理,需要搭建数据仓库?学它! 没有足够人员和经验来运维大数据平台,不想自建IDC买机器,需要免运维的大数据平台?会SQL就等于会大数据?学它! 想知道大数据用得对不对,想用更少的钱得到持续演进的数仓能力?获得极致弹性的计算资源和更好的性能,以及持续保护数据安全的生产环境?学它! 想要获得灵活的分析能力,快速洞察数据规律特征?想要兼得数据湖的灵活性与数据仓库的成长性?学它! 出品人:阿里云大数据产品及研发团队专家 产品 MaxCompute 官网 https://www.aliyun.com/product/odps&nbsp;
目录
相关文章
|
3月前
|
存储 算法 数据挖掘
【2023年中国高校大数据挑战赛 】赛题 B DNA 存储中的序列聚类与比对 Python实现
本文介绍了2023年中国高校大数据挑战赛赛题B的Python实现方法,该赛题涉及DNA存储技术中的序列聚类与比对问题,包括错误率分析、序列聚类、拷贝数分布图的绘制以及比对模型的开发。
67 1
【2023年中国高校大数据挑战赛 】赛题 B DNA 存储中的序列聚类与比对 Python实现
|
19天前
|
存储 消息中间件 大数据
大数据-69 Kafka 高级特性 物理存储 实机查看分析 日志存储一篇详解
大数据-69 Kafka 高级特性 物理存储 实机查看分析 日志存储一篇详解
22 4
|
19天前
|
消息中间件 存储 缓存
大数据-71 Kafka 高级特性 物理存储 磁盘存储特性 如零拷贝、页缓存、mmp、sendfile
大数据-71 Kafka 高级特性 物理存储 磁盘存储特性 如零拷贝、页缓存、mmp、sendfile
34 2
|
19天前
|
存储 消息中间件 大数据
大数据-70 Kafka 高级特性 物理存储 日志存储 日志清理: 日志删除与日志压缩
大数据-70 Kafka 高级特性 物理存储 日志存储 日志清理: 日志删除与日志压缩
32 1
|
19天前
|
存储 消息中间件 大数据
大数据-68 Kafka 高级特性 物理存储 日志存储概述
大数据-68 Kafka 高级特性 物理存储 日志存储概述
18 1
|
19天前
|
存储 算法 NoSQL
大数据-138 - ClickHouse 集群 表引擎详解3 - MergeTree 存储结构 数据标记 分区 索引 标记 压缩协同
大数据-138 - ClickHouse 集群 表引擎详解3 - MergeTree 存储结构 数据标记 分区 索引 标记 压缩协同
28 0
|
19天前
|
存储 消息中间件 分布式计算
大数据-137 - ClickHouse 集群 表引擎详解2 - MergeTree 存储结构 一级索引 跳数索引
大数据-137 - ClickHouse 集群 表引擎详解2 - MergeTree 存储结构 一级索引 跳数索引
25 0
|
19天前
|
存储 SQL 分布式计算
大数据-127 - Flink State 04篇 状态原理和原理剖析:状态存储 Part2
大数据-127 - Flink State 04篇 状态原理和原理剖析:状态存储 Part2
14 0
|
19天前
|
存储 消息中间件 大数据
大数据-126 - Flink State 03篇 状态原理和原理剖析:状态存储 Part1
大数据-126 - Flink State 03篇 状态原理和原理剖析:状态存储 Part1
47 0
|
3月前
|
存储 缓存 NoSQL
深入解析Memcached:内部机制、存储结构及在大数据中的应用
深入解析Memcached:内部机制、存储结构及在大数据中的应用