前言近些年, 数据库系统所服务的数据量, 呈现出指数级的增长态势, 与此同时, 它还面临着诸多挑战, 诸如处理的业务需求变得越发复杂, 实时性要求变得越来越高。单机数据库系统, 已渐渐无法满足现代的数据库服务要求, 所以, 分布式数据库或者数据仓库, 得到了越来越广泛的运用。在实时分析也就是OLAP这个领域当中, 分布式数据仓库能够充分地去发挥系统所具备的分布式特性, 把复杂的OLAP任务分解之后下发到系统里的所有节点之上进行计算, 以此来提升分析性能分布式数据仓库还能够颇为方便地对系统节点予以扩容, 从而应对用户业务数据量增加所产生的需求。然而分布式数据仓库用户没办法避开的一个问题是: 随着数据仓库集群规模不断增大, 扩容所带来的性价比呈愈发降低的态势。一个导致这种现象出现的原因是, 表连接Join是数据库业务里被极为广泛运用的算子之一, 在分布式计算当中依靠系统节点间的数据交互, 当分布式集群规模变大时, 节点之间的数据交互代价会显著增多, 处于这种情形下对分布式系统的网络处理能力有着相当大的考验, 而且依赖用户的数据表设计以及SQL编写能力来减轻数据交互压力。业界不同的分布式数据库系统, 针对这个问题提出了各异的Join运行时过滤算法。for以下简称ADB PG是一款PB级的, 采用MPP架构的云原生数据仓库, 同样也面临着上述问题所带来的挑战。本文从ADB PG架构设计的视角出发, 探讨在ADB PG里的实现方案, 还介绍了基于Bloom的ADB PG Join功能的技术细节。ADB PG架构简介ADB PG是基于开源项目构建而成的, 它是在单机的情形下进行扩展操作的, 它把多个PG服务同时启动在了单个或者多个服务器上头并且组成了集群, 依据分布式的形式来提供数据库服务。ADB PG把每一个PG服务称作一个, 还引进了Slice的概念, Slice用来处理分布式系统里的网络结构。当数据库碰到MPP多阶段计算时, 比如Hash Join左右表的Join Key不符合相同的Hash分布, 那就得借助网络传输对头进行重分布, ADB PG把网络传输的前后阶段切成不一样的。下面是一个ADB PG集群示意图。在这样的架构情形之下, 要如何去解决大规模集群环境里表连接Join所存在的性能方面的问题呢, 业界针对解决这个问题的其中一个方案选择是引入网络代理节点, 把同一机器内部的网络数据发送到本地的代理节点那里, 由代理节点去和其他机器上面的代理节点开展网络收发相关工作以此来减少网络拥塞状况, 该方案对于ADB PG架构所带来的挑战较为巨大, 并且也没有从根本层面上减少Join的网络开销情况。所以为了能够从Join的根源之处减少Join计算所涉及的数据量, ADB PG进行了Join方案的设计以及实现。和Bloom是为了在Join计算之前, 将一部分数据筛选出去, 这事儿需要一个用来实现的“载体”。针对ADB PG的架构设计、存储层以及网络层的特点, 先把这些特点结合起来之后, 我们选用Bloom当作实现的具体形式。Bloom是一种具概率性质的数据结构, 常常被运用来判定一个元素是不是归属于一个集合, 它的优点在于其空间效率极其高, 计算性能一般来讲也处在较高水平, 缺点就是存在阳性误判率false, 然而不存在false, 也就是说Bloom判定一个元素是否属于集合的结果并非单纯的true或false, 而是或者为true、或者为false。上图呈现的是一个关于标准Bloom的计算思路的示意图形其中的0、1乃是Bloom用来表示集合信息的bit array, 也就是说每一位是用一个bit来进行存储的。上方的x、y、z意味着向Bloom里头插入的三个元素, 它们分别借助3种hash算法来计算hash值, 之后在bit array中进行置位操作。而下方是对元素w是否属于集合的判断, 鉴于3个hash值里的某一位没在bit array中被置位, 能够确定的是w不属于集合。Bloom 通常由以下几个参数描述布卢姆过滤器中, 位阵列的大小, 是m个比特, 也就是m bits。k --- 使用的hash函数个数kp --- 误判率n --- Bloom 插入的元素个数我们省略推导过程直接将各个参数的关系给出​当Bloom 足够大时可以简化为在展开Bloom设计工作期间, 针对于n以及m我们能够依据实际的计算场景预先予以确定, 上述提及的公式能够被视作自变量是k, 而应变量成为p的函数p(k), 此一函数在k大于0的时候一般而言并非是单调的该单调性由n与m之间的比例关系予以确定。所以在Bloom进行设计操作时, 需要思考怎样去确定hash函数k的数量从而获取到最小的误判率p。依据上面给出的式子加以计算能够得出结果, 当p处于极小值状态时, 与之相对应的k的值是:​Bloom 的参数设计怎样把Bloom运用到ADB PG Join过滤优化方面, 我们第一步要去设计挑选Bloom的参数呢。对于Bloom插入元素的数量n, 能够直接采用执行计划里得到的Join右表计划行数而要去获取理想的过滤率, 降低误判率p, ADB PG采用了PG高版本Bloom的想法, 设计Bloom大小Bytes为n的两倍, 也就是总体n:m达成1:16。于这般设计里头, 能够经计算达成那般态势便是可以算出最佳的取值是k确确定定是为11的, p(k)那个函数呢呈现出来的样子就如同下面所展示的图形一样, 在k等于11这种状况之下是能够获取到最小的p值的, 而这个最小的p值便是0.046%。k等于11 , 表明针对每一个元素, 得计算11 个hash值以便插入到Bloom bit array当中, 这对于ADB PG而言是不能接受的, 构建Bloom时所产生的代价明显过高, 而为构建Bloom , ADB PG会把误判率、hash计算等诸多因素纳入考量范围, 从而挑选出适宜的k值。在明确构建Bloom的基本原则达成之后, 接下来遇到的便是工程实现相关的问题。Bloom的工程实现呈现出极为简单且高效的特性, 一般而言, 我们能够径直运用数组去构建Bloom, 借助位操作达成Bloom的插入以及查找操作。如下图示, 乃是针对向一个Bloom数组之内插入元素的计算示意图像。​ Join in ADB PG当完成了ADB PG Hash Join的Bloom设计过后, 接下来要探讨怎样把Bloom应用到Join当中去, ADB PG依据Bloom进行了对应的命名将其称作Join。1 Join 的实现方式因为ADB PG优化器常常会挑选把右表当作小一表, 把左表当作大一表, 所以ADB PG把Join的设计特性弄成单向过滤的, 也就是仅用在右表过滤左表, 暂时不思索左表过滤右表的样式与此同时, 我们同样能够把Join灵便用到Hash Join左表链路不同算子的过滤当中。因为Hash Join的形式存在差异, Join的实现形式能够归纳成Local Join和MPP Join这两种形式, 且依据是否具备下推算子的能力来做更进一步的区分。Local Join本地连接是指, 右面表格与左面表格的连接键都满足同样的哈希分布, 不需要再进行数据操作。这时, 哈希、哈希连接以及左面表格扫描处于同一个切片内部, 也就是处于同一个进程之中。我们能够直接在进程空间里, 把布隆过滤器传递给左面表格扫描算子, 从而进行过滤输出。​MPP JoinMPP Join是说, 左右表的Join Key都不满足同样的Hash 分布, 要针对Join Key数据。前文介绍过, ADB PG的Hash Join和Hash算子肯定处在同一个Slice内部, 所以基于基本准则只需要考虑左表的情形, 也就是左表在Hash Join之前存在的状况。存在MPP Join的另一种情况, 左表下并非简单的Scan, 也不存在关联信息把Join Key的Bloom下推到Scan, 那么以减少网络传输数据量作为最后准则, 把Bloom过滤置于前, 以此去减少相应的数据。​2 Bloom 网络传输Join于各个计算节点建造了一个Local Bloom, 每个计算节点得要收集所有别的节点的Bloom, 且于本地组建完整的Bloom以后才能够开启过滤计算, 我们把Bloom的收发划分成两种模式, 全量传输以及位传输在发送以前, 能够对两种模式的数据量的大小予以判断, 然后自适应挑选数据量小的模式。​Bloom 全量传输​Bloom 位传输性能测试接下来, 我们要针对ADB PG Join进行性能表现的测试, 测试集群是依照ADB PG公有云建造的实例, 测试运用TPC-H 1TB测试集scale等于10000, 测试借助开启以及关闭Join功能来对比执行性能 , 下图呈现了TPC-H执行性能存在差异的Query测试结果。能够瞧见, Join在Q5、Q8、Q9以及Q17上都实现了较大程度的性能提升, 当中Q17的优化性能是最为出色的, 执行时间从137s优化到了8s。然而Q10出现了稍微的性能回退: 从10s回退至12s, 缘由是Q10的Join Key是完全匹配的, Join没办法做到动态提前过滤, 且优化器没能准确估算代价, 致使计划依旧使用了Join。此之外, Q20因优化器下推规则之故未选择Join, 实际上经分析得出, Q20与Q17相类比较适宜运用Join。为解决这些问题, ADB PG优化器相关功能仍处于开发迭代之中。总结未来规划依据ADB PG架构设计, 鉴于存储层以及网络层特点, 采用Bloom当作Join的实现形式, 于TPC - H测试里达成了显著的性能提升成果。往后我们会从以下几个方面展开进一步的开发以及优化, 以此提升客户使用体验