共计 5719 个字符，预计需要花费 15 分钟才能阅读完成。
简介：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… 本文为阿里云原创内容，未经容许不得转载。
