简介： PolarDB-X 2.0提供了通明分布式的能力，默认进行主键的哈希拆分，让用户无感知的从单机数据库迁徙到分布式数据库。拆分键的抉择是学术界和工业界钻研已久的问题，一个重要选型是tp优先还是ap优先，两者难以同时兼顾。前言PolarDB-X2.0提供了通明分布式的能力，默认进行主键拆分，让用户无感知的从单机数据库迁徙到分布式数据库。拆分键的抉择是学术界和工业界钻研已久的问题，一个重要选型是tp优先还是ap优先，两者难以同时兼顾。tp优先[1]的目标是缩小分布式事务。filter优先，让sql尽量不跨库。ap优先[2]的目标是利用下推的劣势，网络优化，优先解决等值join。PolarDB-X的主键拆分对于tp查问很敌对，但对于ap查问并不敌对。因而，在迁徙PolarDB-X之后若发现默认的拆分形式不能满足偏ap的需要，能够基于理论workload进行拆分键举荐，联合PolarDB-X的拆分变更能力进行智能的拆分键调整。ap优先的拆分键举荐次要有两种形式：借助优化器[3]后果比拟精确，然而运行工夫太长，将优化器当成黑盒或深度批改优化器，绝对快一点，但速度仍然无奈令人满意；不借助优化器[4]绝对较快，但仍然须要穷举所有的可能，且代价估不准。借助优化器的算法难以优化的起因是指标函数的后果无奈预测，所以无奈给出无效的剪枝。为了可能尽量快的进行举荐，PolarDB-X的拆分键举荐不借助优化器，少用统计信息，基于Amazon RedShift定义的问题设计了一个高效的举荐算法。问题定义本节内容参考自Amazon RedShift的论文[4]。拆分键举荐问题定义为每个表抉择一个拆分列，使得能够节俭的网络代价最大。join可下推须要两个表应用的拆分键恰好是这条边的两个列。下图(b)中A、B、C、D、E、F别离用a、b1、c、d1、c、c做拆分键，则<C,c,E,c,2>、<C,c,F,c,2>、<B,b1,D,d1,2>能够下推，这种拆分能够节俭的代价为6。Join Multi-Graph给定n条查问，第i条查问被看作m个二元join $\{j_{i1},j_{i2},...,j_{im}\}$的汇合。每个jk是一个五元组，$jk=<t1_k,a1_k,t2_k,a2_k,w_{k}>$，示意表$t1_{k}$的$a1_{k}$列与表$t2_{k}$的$a2_{k}$列的等值join，不下推的网络代价是$w_k$。前4列雷同的边$<t1_{k},a1_{k},t2_{k},a2_{k},w1_{k}>$、$<t1_{k},a1_{k},t2_{k},a2_{k},w2_{k}>$会合并为$<t2_{k},a1_{k},t2_{k},a2_{k},w1_k+w2_k>$。$<t1,a1,t2,a2,w>$中w的定义为两表t1和t2的行数别离为r1、r2，$w=min(r1+r2,min(r1,r2)*shardCnt)*count$。公式的含意是若不下推，则导致的网络代价是将两表拉取到CN进行hash join或者将小表作为播送表最初乘以这个等值条件呈现的次数。构建Join Multi-Graph，每张表是一个点，每个jk是一条边，边上有两个列名和代价，下图(a)中最下面的一条边就是<C,c,E,c,2>。这个图可重边，例如BD之间就有两条边（因为列名不同）。

不可近似性这个问题不可近似比为$2^{log^{1-\epsilon}n}$，n为图中波及的列数。这其实是个很蹩脚的论断，这个问题的实践近似比根本等于没有。RedShift的算法为整数线性规划，若超时则调用四个随机算法取个大的。这个算法存在随机算法不足稳定性、超时无奈自主管制等问题。基于以上毛病，PolarDB-X设计了一个基于branch-and-bound的穷举算法。算法设计先看看暴力穷举的伪代码

这个算法的问题在于穷举到最初一张表才会做计算，很多拆分计划齐全没用却被穷举了。从耗时就能够看出没有理论应用价值。表属性工夫(s)12表 8列均匀度数868.986redshift 13表均匀度数1072.81星状图 17表均匀度数1632.696对于这个算法运行过慢的问题，咱们从以下四个层面进行优化。基于branch-and-bound的穷举算法对于一个穷举到表level的计划$Shard=\{P,col\}$，计算以这个计划为根底的所有拆分计划weight的上界upperBound。若上界小于以后找到的最优解即不满足$upperBound(Shard)≥OPT$，则这个计划能够间接废除。上界能够分为4局部计算：以后P的weight。col导致的weight。表level+1到表|V|的最佳计划的weight。表level+1到表|V|的只思考Shard导致的最佳计划的weight，即每张表别离选最优列（区间求和）。3与4的计划可能不是同一个计划，但$1+2+3+4$的值相对是一个上界。计算层面，3是由exactSearch函数里倒序搜寻间接迭代计算出来的。1，2，4能够在穷举Shard时在search函数中进行保护，用树状数组保护4的区间和，每个表的max值用数组记录。


exactSearch与naiveSearch相比看上去搜寻空间变大了，但这是剪枝的要害。下图是一个剪枝的示例，T1可选拆分键为$\{a,b\}$，T2可选拆分键为$\{c,d\}$，T3可选拆分键为$\{e,f\}$，T4可选拆分键为$\{g,h\}$，4张子图别离代表exactSearch函数2-7行的4次循环，即抉择T4的最佳拆分键、抉择T3,T4的最佳拆分键、抉择T2,T3,T4的最佳拆分键、抉择T1,T2,T3,T4的最佳拆分键。红色节点为以后表集的最佳拆分计划，图3得出的,T2,T3,T4的最佳拆分键是{d,f,h}。蓝色为搜寻过程中拜访到的节点，未遍历到底的节点就是被剪枝的局部。图4中，穷举到$T1=a,T2=d$发现有$upperBound(T1=a,T2=d)<OPT$，则进行了剪枝，不再穷举T3,T4的拆分键。

剪枝的能力由upperBound函数、OPT的大小决定，以下增强剪枝的能力。穷举程序改成穷举程序对于暴力搜寻的速度影响很大，例如clique列举问题中的各种启发式[5]。思考度数为{1,9,10}的列表，列表{10,9,1}的总穷举数$为1+9*1+10*9*1=100$，列表{1,9,10}的总穷举数为$10+9*10+1*9*10=190$。另外程序还会影响upperBound函数的值。一个直观的办法是依照点的度降序排序，这里想法用上述{1,9,10}的例子能够解释。留神到剪枝中影响较大的局部是4，若连贯在一起的点在列表中地位靠近，则能够较早减小4，PolarDB-X采纳的基于全局最小割的穷举算法。从全局的角度思考，将图分为两块，使得它们之间的边权最小，将点多的那一块放在后面，之后迭代解决前后两块。这里的每一次宰割都是全局最小割问题，须要调用n次Stoer–Wagner算法，总复杂度为$O(n^2mlogn)$。最小割的思路还用在[6]中，然而解决的并不是相干问题。OPT优化计算出比拟大的OPT可增强剪枝的能力。在extraSearch每轮循环开始时穷举level表所有可拆分的列与后续表的最优计划拼接，初始化一个较大的OPT。在search函数中将shard与Lopt[level+1]进行拼接失去一个较大的OPT。这两个优化能够间接失去拆分计划，实际上是冀望中真正计算出拆分计划的中央，而非依附穷举到最初一张表。

自适应近似以上提出的剪枝策略并不能扭转np-难问题的实质，所以应用近似减速剪枝，即剪枝批改为$upperBound(Shard)≥OPT*ratio$。这个近似的益处是ratio能够保障近似比，ratio随着搜寻工夫逐步增大。须要留神的是在exactSearch中保留后果时须要将weight批改为weight*ratio，否则upperBound时会计算错误，失去近似比。其余算法可能找到一个执行打算，使得有些表无奈被下推，这样的表与未被join的表一起先用filter的列做拆分键。否则回退到主键拆分。另外行数小于阈值的表会被间接举荐为播送表，不参加拆分键举荐的过程。因为整个算法不借助优化器，生成的打算并不一定会变优，所以最初会有一个whatif的过程计算拆分形式变更前后优化器计算出的sql代价的变动。如果评估发现代价并没有变优，零碎会放弃此次举荐的后果。仿真验证表属性工夫(s)35表 8列均匀度数822.05845表 8列均匀度数858.575redshift 30表均匀度数1061.344redshift 40表均匀度数1098.689redshift 60表均匀度数415.98星状图 81表均匀度数1617.041星状图 101表均匀度数1623.012因为剪枝能力受图的性质（随机种子）影响，工夫不肯定随着图的变大而变大。不同状况下能解决的表数目差别较大，难以提前预测工夫。工夫涨幅不是太大，因为自适应近似将工夫压了下来，且大图上树状数组的作用比拟显著。真实情况下图的密度不会像仿真中这么高，能较快解决40、50张表。应用示例在PolarDB-X中应用拆分键举荐，只须要在对应的库中输出sql“sharingadvise”即可（因为须要调用plan cache中的sql作为workload且算法对于CN压力较大，倡议在压测阶段进行拆分键举荐）。以下为workload为tpcc 100仓时基于plan cache进行拆分键举荐的过程演示。属性配置PolarDB-Xpolarx-kernel_5.4.14-16601976_xcluster-20220728CN2台4C32GDN2台4C32GTPCC100仓拆分形式auto库随机key拆分warehouses100terminals50runMins30limitTxnsPerMin0terminalWarehouseFixedtruenewOrderWeight45paymentWeight43orderStatusWeight4deliveryWeight4stockLevelWeight4初始的状况

压测后果

拆分键举荐sharingadvise指令会依据plan cache给出相干的sql倡议以及预计的代价变动。

执行下面举荐进去的拆分键变更语句

验证拆分键变动

再次压测TPCC，tpmC晋升至8倍

总结从下面的试验能够发现，即便是tp查问，谬误的拆分键也会因为大量引入分布式事务导致性能受到很大的影响。PolarDB-X“手自一体”的计划对于拆分键的抉择有肯定要求，拆分键举荐提供了手动抉择拆分键的计划，加重人力累赘。参考文献[1] Andrew Pavlo, Carlo Curino, and Stanley Zdonik. 2012. Skew-aware automatic database partitioning in shared-nothing, parallel OLTP systems. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD '12). Association for Computing Machinery, New York, NY, USA, 61–72.[2] Erfan Zamanian, Carsten Binnig, and Abdallah Salama. 2015. Locality-aware Partitioning in Parallel Database Systems. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (SIGMOD '15). Association for Computing Machinery, New York, NY, USA, 17–30.[3] Rimma Nehme and Nicolas Bruno. 2011. Automated partitioning design in parallel database systems. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data (SIGMOD '11). Association for Computing Machinery, New York, NY, USA, 1137–1148.[4] Panos Parchas, Yonatan Naamad, Peter Van Bouwel, Christos Faloutsos, and Michalis Petropoulos. 2020. Fast and effective distribution-key recommendation for amazon redshift. Proc. VLDB Endow. 13, 12 (August 2020), 2411–2423.[5] Rong-Hua Li, Sen Gao, Lu Qin, Guoren Wang, Weihua Yang, and Jeffrey Xu Yu. 2020. Ordering heuristics for k-clique listing. Proc. VLDB Endow. 13, 12 (August 2020), 2536–2548.[6] Carlo Curino, Evan Jones, Yang Zhang, and Sam Madden. 2010. Schism: a workload-driven approach to database replication and partitioning. Proc. VLDB Endow. 3, 1–2 (September 2010), 48–57原文链接：https://click.aliyun.com/m/10...本文为阿里云原创内容，未经容许不得转载。