一、布景
2022年11.10号晚8点，月黑风高
各大电商公司正在等待着行将到来的大促…
而作为买卖订单组的咱们也不例外，此时咱们在紧盯监控大盘，企图找到体系蛛丝马迹的问题，以便及时应对，假如这时候出了问题，那就关乎着团队的面子，关乎着本年的绩效，当然还关乎着本年的年终奖……，秃然，古怪的现象发生了
注：本文是中大型互联网公司遇到的真实事例，其知识点的深度和广度拿来面试都足够，主张认真阅览并且了解涉及到的相关知识点。若有任何问题可在谈论区指出~
二、现象
随着事务的发展，订单单库承载的压力越来越大，因而后续对数据库做了水平拆分，运用shardingjdbc的能力做了分库分表。
依据数据量增加预期进行预估，订单库一共分了16个库，每个库16个表，所以一共是256张表。扼要的结构如下：
理论上，每个分库的恳求QPS相差不大才是契合预期的，究竟当时做数据库拆分也便是为了均分流量，均分压力。但古怪的现象是不同的分库访问QPS竟然有5倍之差！如下图所示：
3库的QPS达到了16K以上，而11库的QPS只是只有3K，发生了严峻的流量歪斜现象，按这种趋势下去，分库分表的带来的收益会因为某些库的压力过大而大为降低
三、猜测
先来猜测下为什么会发生这种现象？
猜测一：下单大账户
因为订单分库分表战略是选用的买家ID进行路由的，也便是同一个买家的订单都会存储到一个分库里，同样的，同一个买家的恳求也都会打到同一个分库上，所以有可能是某位超级大买家张狂买买买？
第二种可能性是订单分库分表算法不行随机，导致大部分买家的订奇数据不均匀的落到了某些分库中，发生了数据歪斜的现象
四、猜测验证思路
猜测一验证思路
关于猜测一的验证，在当天（11.10）下单的用户中，group by uid，看每个uid创立的奇数，即可判别出是否有下单大账户
4.1 猜测二验证思路
对新注册的用户，运用分库分表的算法核算其下的订单应该存储到哪个订单库，看存储是否是否均匀
这就需求了解订单的分库分表算法
4.1.1 订单的分库分表算法
在公司的用户体系中，用户ID是用long型来存储的。
订单分库分表的算法中，取用户ID的第49-56位（共8位bit位，低4位分库，高4位分表），然后与分库分表的个数减一相与（订单共分了16库16表），即可得到分库分表Index，代码如下所示：
分库算法：
public int getDbIndex(Long userId){
return (userId >>> 8) & 15 + 1;
}
分表算法：
public int getTableIndex(Long userId){
return (userId >>> 12) & 15 + 1;
}
这里的+1是因为&15后核算的值区间为[0-15]，加1后为[1-16]，咱们界说的分库分表Index的规模也是[1-16]，和算法相匹配
这里为什么选用&15的办法而不是%16的办法，是因为若num的值为2的幂的情况下，能够用&(num-1) 替代 % num，而位运算的功能高于取余运算，这个特性是参阅了HashMap的源码，有兴趣能够看看java.util.HashMap#putVal函数
为了更明晰易懂，图示如下：
再举个实践比如，若userId为：1526102172100467200
其经过getDbIndex分库算法核算的图示如下：
如上介绍，订单的分库分表算法的生成逻辑是依赖用户ID的，那么现在问题来了，用户ID是如何生成的？是不是订单取的用户ID的49-56位散列不均匀，然后导致分库分表数据歪斜？下面介绍下用户ID的生成算法
4.1.2 用户ID生成算法
在散布式体系中，为了确保生成的ID是仅有的，有多种算法，咱们选用的是雪花算法
如上图所示，雪花算法是由时刻戳（41位）+作业机器ID（10位）+ 序列号（12位）组成。其间作业机器ID的bit位数和序列号的bit位数能够依据事务需求自行分配
这样，将时刻戳放在首位，一方面能够尽可能的防止生成重复ID，别的一方面能够确保生成的ID是趋势递增的，若运用的是innodb存储引擎，B+树作为主键索引的情况下，递增这个特性对数据插入是十分友爱的
在我司，对雪花算法进行了必定的改造，在long型的64位中融入了事务编码，其构成如下：
64位ID = 1(占位)+ 41(毫秒)+8(事务编码)+5(机器ID)+9(累加位)
其间订单分库分表取的是用户ID的第49-56位，对应到上述的算法中，也便是取了2（事务编码）+ 5(机器ID) + 1（重复累加），如下图黄色部分，所以假如该部分的生成不行随机，那完全会导致订奇数据分库分表的数据歪斜
五、猜测验证
5.1 猜测一验证
如下图，统计了每个买家下奇数，按倒序排列，可见，单用户下奇数最多的是9单。依据这个结论，基本能够扫除下单大账户的问题
5.2 猜测二验证
经过测试，咱们发现新创立的用户ID创立的订单都会散布在1,3,5这三个订单库，这表明分库分表算法取的因子位对错随机的
可是为什么分在了1,3,5库？
订单分库分表因子位取的是下图算法中标记黄色区域的8位，它的组成是2bit（事务规矩）+ 5bit（机器ID）+ 1bit（累加位）
那么8位因子位即可依据上述的推导核算出来，分别是00 01000 0，00 01001 0，00 01010 0，经分库算法核算后得1,3,5
和预期相符，至此水落石出
六、问题处理
处理这个问题，最好的办法便是让用户ID的49-56位生成得更随机一些
用户ID的生成算法改造如下：
long userId = (timestamp - idepoch) << 22 | machineId << 15 | busid << 7 | this.sequence;
即：
1-42 时刻戳 共42位
43-49 机器ID位，共7位
50-57 事务ID位，共8位
58-64 累加位 ，共7位
其间订单ID取的49-56位全部选用了随机数生成算法进行生成
七、拓宽
1、为什么取用户ID的49-56位作为订单分库分表的因子位？
实践上，咱们在生成订单ID时也选用了雪花算法，并将用户ID的49-56位作为订单ID的事务bit位进行填充。这样，订单ID就交融了用户ID的信息，咱们无需扫描全库全表，也无需树立映射表，就能够运用订单ID和用户ID来查询订单信息。
分库分表的最佳功率通常在需求路由到特定库和表的情况下得以体现，不然扫描256张表的功能会特别低。。。
2、为什么分了16个库16张表？
这个挑选取决于事务的需求以及数据库机器的装备。举例来说，假如咱们要支撑未来5年的事务发展，当时每天的订单增加量为10万条，一年便是3650万条。依据数据库的装备，每张表最多包容200万条数据，并且还要留有必定的缓冲，因而咱们能够开始核算出需求进行分库分表的数量。
至于为什么挑选16，因为16是2的幂，运用2的幂能够运用位运算替代取余运算，然后提高功能。这种特性也被广泛使用在相似HashMap等数据结构中。
3、雪花算法在实践生产上的运用体会如何，有遇到过线上问题吗？
在实践生产中，雪花算法的体现仍是相对稳定的，尽管理论上存在时钟回拨等问题，可是这些问题的兜底方案现已得到了广泛的使用，因而实践运用体会仍是比较良好的。
八、总结
本文介绍了分库分表流量歪斜的问题排查与处理思路
思路总结如下：
1、明确订单分库分表的路由算法，是经过取用户ID上的49-56位核算而来
2、用户ID的生成选用的是雪花算法。雪花算法是一种生成大局仅有ID的算法，经过在散布式体系中生成ID，避免了重复的问题。因为每个雪花都是独一无二的，因而称之为“雪花算法”。一般地，咱们会对雪花算法进行必定的改造，以契合公司事务的需求，比如在我司就在64位中划分了8位作为事务bit位，由事务填充相关的信息。
3、为处理散布不均的问题，咱们选用了更改用户ID生成算法的办法，将其49-56位愈加随机、均匀化的办法。
九、ChangeList
- 2023年03月21日 经谈论区@weixiaoo同学提示，将&num修正为&(num-1)
- 2023年03月21日 补充分表算法
