技术精华-解锁分库分表新姿势：基因法完全解读 在分库分表时，经常会遇到查询的条件不含有分片键的情况，比如说用户表，生成的订单中是依靠userId来关联用户信息，而用户在登录时又可以使用手机号和邮箱来登录，这样只有userId一个分片键就搞不定了。
大麦网中的解决方案是在设计出 用户手机表 用手机号当做分片键 。以及用户邮箱表 用邮箱当做分片键。 当用户用手机或者邮箱登录后，分别从相应的用户手机表和用户邮箱表查询出userId，然后用userId去用户表查询信息。
目前在订单业务中也遇到类似的问题，我们需要既可以通过订单号查询出订单详细，也想通过userId查询该用户下的订单列表，这样就需要即通过order_number查询又要通过userId查询
估计小伙伴就会想了，还是使用附属表路由的方案呗，再设计出一个订单用户表，通过userId去订单用户表查询，得到order_number，然后再去订单表查询信息
首先说这种方案确实可以解决，但就是要额外维护表。而且对于订单这种量级很大的表来说，附属路由表的量级也会很大。
所以最好有另一种方案，可以不用再设计出一张表去维护它，这种方案就是我们要介绍的 基因法
基因法
我们先介绍一下特征：
191 % 32 = 31- 191的二进制： 10111111
- 32的二进制： 100000 也就是2的5次方
- 31的二进制： 11111
让我们观察下这个计算规律：
31的二进制 和 191的二进制最后5位相等，都是11111。如果随便拿一个数转成二进制，然后把二进制的后5位替换成这个11111，然后将这个替换后的值对32进行取模，那么得到的余数也是31，这个5位长度就是靠32的二进制的长度也就是求log2n对数的值
比如说 159，二进制是 10011111 ，对 32 取模，结果还是31
下面让我们把这个计算规律应用到订单号和用户id的业务中
public class TestMain {
public static void main(String[] args) {
//分片数量
int shardingCount = 32;
//订单编号
long orderNumber = 2654324532L;
//用户id
long userId = 45346343212L;
//求shardingCount的log2N对数
int sequenceShift = log2N(shardingCount);
long newOrderNumber = replaceBinaryBits(orderNumber, sequenceShift, (userId % shardingCount));
System.out.println("替换后订单号取模结果:" + (newOrderNumber % shardingCount));
System.out.println("用户id取模结果:" + (userId % shardingCount));
}
/**
* 求log2(N)
* */
public static int log2N(int count) {
return (int)(Math.log(count)/ Math.log(2));
}
public static long replaceBinaryBits(long num1, int numBits, long num2) {
// 将两个数转换成二进制字符串
String binaryStr1 = Long.toBinaryString(num1);
// 计算num2对应的二进制长度，确保它填充到指定的numBits位
String binaryStr2 = Long.toBinaryString(num2 % (1L << numBits));
// 如果binaryStr2长度小于numBits，则在前面补零
while (binaryStr2.length() < numBits) {
binaryStr2 = "0" + binaryStr2;
}
// 计算需要保留的前面部分的长度
int keepLength = binaryStr1.length() - numBits;
// 如果需要替换的位数超过了num1的长度，则直接使用num2的二进制字符串
if(keepLength < 0) {
System.out.println("替换位数超过了第一个参数的位数，直接使用第三个参数的二进制: " + binaryStr2);
// 直接将num2的二进制字符串转换为十进制并打印
return Long.parseLong(binaryStr2, 2);
}
// 保留num1前面的部分和num2的二进制拼接
String resultBinaryStr = binaryStr1.substring(0, keepLength) + binaryStr2;
System.out.println("要替换的二进制后位数" + numBits);
// 打印原始的二进制字符串
System.out.println("num1 替换前的二进制: " + binaryStr1);
// 打印最终的二进制字符串
System.out.println("num1 替换后的二进制: " + resultBinaryStr);
System.out.println("num2 的十进制: " + num2);
System.out.println("num2 的二进制: " + binaryStr2);
// 将结果二进制字符串转换回十进制数值并打印
long resultDecimal = Long.parseLong(resultBinaryStr, 2);
System.out.println("num1 对应的十进制数为: " + resultDecimal);
return resultDecimal;
}
}结果：
要替换的二进制后位数5
num1 替换前的二进制: 10011110001101011100011100110100
num1 替换后的二进制: 10011110001101011100011100101100
num2 的十进制: 12
num2 的二进制: 01100
num1 对应的十进制数为: 2654324524
替换后订单号取模结果:12
用户id取模结果:12流程总结下：
- 假设 分片数量
shardingCount = 32，订单号orderNumber = 2654324532L，用户iduserId = 45346343212L，分片数量32的log2n对数sequenceShift = 5（使用5位二进制表示分片号） - 将
orderNumber转为二进制，为10011110001101011100011100110100 - 将
userId % shardingCount的余数 = 12 转为二进制01100（补全为5位） - 将
10011110001101011100011100110100的后5位替换成01100,替换后为10011110001101011100011100101100 - 将替换后的
10011110001101011100011100101100转为十进制为2654324524 - 计算
2654324524 % 32= 12
看到这相信大家已经明白基因法的原理了，下面来介绍如何具体的应用
现在分布式id的生成基本用的都是雪花算法的原理，我们再来看一下雪花算法的结构
雪花算法
- 第一个部分：1个bit，无意义，固定为0。二进制中最高位是符号位，1表示负数，0表示正数。ID都是正整数，所以固定为0。
- 第二个部分：41个bit，表示时间戳，精确到毫秒，2^41/(1000_60_60_24_365)=69，大概可以使用 69 年。时间戳带有自增属性。
- 第三个部分：10个bit，表示10位的机器标识，最多支持2^10=1024个节点。此部分也可拆分成5位datacenterId和5位workerId，datacenterId表示机房ID，workerId表示机器ID。
- 第四部分：12个bit，表示序列化，同一毫秒时间戳时，通过这个递增的序列号来区分。即对于同一台机器而言，同一毫秒时间戳下，可以生成 2^12=4096 个不重复 id。
假设存在一种情况，在超高的并发下，在同一毫秒，同一台机器，生成两个id，那么这两个id唯一的区别 就是序列号相差1，如果这时我们使用了基因法，分成32张表，也就是取把雪花算法二进制的后5位进行基因替换，那么这两个id不就重复了吗？
确实是会重复但我们要和业务结合起来思考，如果是在订单业务下，**订单id被替换的是用户id和分片数的取模值，**在这种业务下发生重复的概率是非常低的，也就是说需要用户在同一毫秒下创建了2个订单才能重复，这要是正常的用户肯定是不会重复的，除非是机器刷单或者恶意攻击这种情况
改造
下面我们来对雪花算法进行改造，结合基因法来测试一下重复的情况
public synchronized long getOrderNumber(long userId) {
long timestamp = getBase();
// 时间戳部分 | 数据中心部分 | 机器标识部分 | 序列号部分
return ((timestamp - BASIS_TIME) << timestampLeftShift)
| (datacenterId << datacenterIdShift)
| (workerId << workerIdShift)
| sequence << 4
| userId % 16;
}- userId的取模为 16，对其去log2n的对数是4
- 将序列号左移4位，也就是序列号的有效位是8位，最高支持到2的8次方 256，也就是说某个用户在毫秒内，同一机器下最多生成256个订单号不会重复
接下来下面我们来验证一下
循环256次
public void testOrderNumber(){
List<Long> idList = new ArrayList<>();
for (int i = 0; i < 256; i++) {
long orderNumber = snowflakeIdGenerator.getOrderNumber(2222);
idList.add(orderNumber);
}
int count = 0;
Map<Long, List<Long>> collect = idList.stream().collect(Collectors.groupingBy(id -> id));
for (final Entry<Long, List<Long>> entry : collect.entrySet()) {
System.out.println("订单号：" + entry.getKey() + "，数量为：" + entry.getValue().size());
if (entry.getValue().size() > 1) {
count++;
}
}
System.out.println("重复的orderNumber数量：" + count);
}结果
....
订单号：1763164230291425342，数量为：1
订单号：1763164230291425854，数量为：1
重复的orderNumber数量：0下面来做进一步的改造，可根据userId和要配置的分表数量来灵活的生成订单编号
com.damai.toolkit.SnowflakeIdGenerator#getOrderNumber(long, long)
/**
* 获取订单编号
*
* @return orderNumber
*/
public synchronized long getOrderNumber(long userId,long tableCount) {
long timestamp = getBase();
long sequenceShift = log2N(tableCount);
// 时间戳部分 | 数据中心部分 | 机器标识部分 | 序列号部分 | 用户id基因
return ((timestamp - BASIS_TIME) << timestampLeftShift)
| (datacenterId << datacenterIdShift)
| (workerId << workerIdShift)
| (sequence << sequenceShift)
| (userId % tableCount);
}- 需要
userId和tableCount分片数量作为参数传入 - 根据
tableCount计算出log2n的对数sequenceShift - 将序列号左移
sequenceShift位 - 将序列号左移
sequenceShift位后，剩下的位数替换成userId % tableCount的基因 - 拼接好数据后将id返回，作为订单编号
通过上述可知，毫秒内能生成不重复的订单号和分片数量成相反关系，根据业务需求进行相关的调整即可，目前的订单业务是由通过订单编号和用户id查询，可以用基因法，但如果查询的条件变多了，比如查询某个节目类型下的订单列表，或者统计数量，那么用基因法就不适合了，还是要考虑使用附属路由表的方案，或者使用其他类型数据库，比如elasticsearch，而在节目服务服务的数据查询中，就使用到了elasticsearch，小伙伴也直接跳转到节目服务的相关业务介绍模块即可