感谢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 就可以存储，并快速查询了。   （如果有重复？ 怎么办）

 

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

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

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

    2个向量

    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

 

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

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

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

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

   

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

   

 冲突率的公式:

 

再介绍什么是zorder:

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

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个点才可以访问全(下图右)
• 想象下地理位置： 经纬度相近的点，在物理上更靠近的存储，应用中访问更高效。

最终使用BloomFilter+Zorder的方案

   

      如模拟客户表接口, 假定客户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个数量级的