分布式分库分表：基因法完全解读
视频
一、问题背景
分片键不足的困境
在分库分表的设计中，经常遇到查询条件不含分片键的情况。典型场景是用户表：
- 订单通过
userId关联用户信息 - 用户登录时可使用手机号或邮箱
- 仅用
userId作为分片键无法满足多种查询需求
传统解决方案：附属表路由
创建附属表维护映射关系：
- 用户手机表：以手机号为分片键，存储
userId - 用户邮箱表：以邮箱为分片键，存储
userId - 查询流程：手机号/邮箱 → 查询附属表得到
userId→ 查询原表
存在的问题
这种方案虽然可行，但需要额外维护附属表。对于订单这类数据量巨大的业务，附属表的维护成本会很高。
需求：既能通过 order_number 查询订单详情，也能通过 userId 查询用户订单列表，且无需维护额外的映射表。
解决方案：基因法（Genetic Algorithm in Sharding）
二、基因法的数学原理
核心特征观察
通过取模运算的二进制性质，我们发现一个有趣的规律：
191 % 32 = 31
191的二进制： 10111111
32的二进制： 100000 (2的5次方)
31的二进制： 11111
关键观察：31 的二进制（11111）与 191 的二进制最后 5 位完全相同。
数学规律
如果我们将任意数的二进制后 5 位替换为另一个数的后 5 位，再对 32 取模，结果就是那个被替换的数对 32 的取模结果。这里的 5 位长度 = log₂(32)。
验证：
159的二进制： 10011111
159 % 32 = 31
（最后5位也是 11111）
通用公式
对于分片数 shardingCount = 2^n：
- 计算
sequenceShift = log₂(shardingCount) - 将数字 A 的二进制后
sequenceShift位替换为数字 B 的后sequenceShift位 - 新数字对
shardingCount取模 = B 对shardingCount取模
三、基因法在订单系统中的应用
代码演示
public class TestMain {
public static void main(String[] args) {
int shardingCount = 32; // 分片数量
long orderNumber = 2654324532L; // 订单编号
long userId = 45346343212L; // 用户ID
int sequenceShift = log2N(shardingCount); // 求log2(32) = 5
long newOrderNumber = replaceBinaryBits(orderNumber, sequenceShift, userId % shardingCount);
System.out.println("替换后订单号取模结果: " + (newOrderNumber % shardingCount)); // 12
System.out.println("用户id取模结果: " + (userId % shardingCount)); // 12
}
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);
String binaryStr2 = Long.toBinaryString(num2 % (1L << numBits));
// 补齐到指定位数
while (binaryStr2.length() < numBits) {
binaryStr2 = "0" + binaryStr2;
}
int keepLength = binaryStr1.length() - numBits;
if(keepLength < 0) {
System.out.println("替换位数超过了第一个参数的位数");
return Long.parseLong(binaryStr2, 2);
}
String resultBinaryStr = binaryStr1.substring(0, keepLength) + binaryStr2;
System.out.println("num1 替换前的二进制: " + binaryStr1);
System.out.println("num1 替换后的二进制: " + resultBinaryStr);
System.out.println("num2 的二进制: " + binaryStr2);
return Long.parseLong(resultBinaryStr, 2);
}
}
执行结果
要替换的二进制后位数: 5
num1 替换前的二进制: 10011110001101011100011100110100
num1 替换后的二进制: 10011110001101011100011100101100
num2 的十进制: 12
num2 的二进制: 01100
num1 对应的十进制数为: 2654324524
替换后订单号取模结果: 12
用户id取模结果: 12
流程总结
- 参数：分片数
shardingCount = 32，订单号orderNumber = 2654324532，用户userId = 45346343212 - 计算：
sequenceShift = log₂(32) = 5 - 二进制转换：
orderNumber→10011110001101011100011100110100userId % 32 = 12→01100
- 位替换：将订单号的后 5 位替换为
01100 - 结果：
10011110001101011100011100101100→ 十进制2654324524 - 验证：
2654324524 % 32 = 12✓
四、与雪花算法结合
雪花算法结构回顾
雪花算法生成的 64 位 ID 结构：
| 部分 | 位数 | 说明 |
|---|---|---|
| 符号位 | 1 | 固定为 0（保证为正数） |
| 时间戳 | 41 | 精确到毫秒，可用约 69 年 |
| 数据中心 | 5 | 最多 32 个数据中心 |
| 机器ID | 5 | 最多 32 台机器 |
| 序列号 | 12 | 同毫秒内最多 4096 个 |
重复性分析
关键问题：在同一毫秒、同一台机器上生成两个 ID 时，它们唯一的区别是序列号相差 1。如果用基因法将后 5 位替换，这两个 ID 会重复。
但结合业务考虑：
- 对于订单场景，后 5 位被替换为
userId % shardingCount - 重复需要同一用户在同一毫秒内创建多个订单
- 正常用户不会这样做，只有机器刷单或恶意攻击才会触发
- 重复概率极低，可以接受
五、改造后的雪花算法
基础版本（固定分片数）
public synchronized long getOrderNumber(long userId) {
long timestamp = getBase();
// 时间戳 | 数据中心 | 机器ID | 序列号 | 用户ID基因
return ((timestamp - BASIS_TIME) << timestampLeftShift)
| (datacenterId << datacenterIdShift)
| (workerId << workerIdShift)
| (sequence << 4)
| (userId % 16);
}
说明：
userId取模 16，其 log₂(16) = 4- 序列号左移 4 位，有效位为 8 位
- 毫秒内同一机器最多生成 256 个不重复订单号
测试验证
public void testOrderNumber(){
List<Long> idList = new ArrayList<>();
for (int i = 0; i < 256; i++) {
long orderNumber = snowflakeIdGenerator.getOrderNumber(2222);
idList.add(orderNumber);
}
Map<Long, List<Long>> collect = idList.stream()
.collect(Collectors.groupingBy(id -> id));
int count = 0;
for (final Entry<Long, List<Long>> entry : collect.entrySet()) {
if (entry.getValue().size() > 1) {
count++;
}
}
System.out.println("重复的orderNumber数量: " + count); // 结果: 0
}
灵活版本（支持参数化）
/**
* 获取订单编号
* @param userId 用户ID
* @param tableCount 分表数量（应为2的幂次）
* @return 订单号
*/
public synchronized long getOrderNumber(long userId, long tableCount) {
long timestamp = getBase();
long sequenceShift = log2N(tableCount); // 根据分表数计算移位位数
// 时间戳 | 数据中心 | 机器ID | 序列号 | 用户ID基因
return ((timestamp - BASIS_TIME) << timestampLeftShift)
| (datacenterId << datacenterIdShift)
| (workerId << workerIdShift)
| (sequence << sequenceShift)
| (userId % tableCount);
}
private int log2N(long count) {
return (int)(Math.log(count) / Math.log(2));
}
特点：
- 支持灵活的分表数量
- 毫秒内能生成的不重复订单号数与分表数成反比
- 根据业务需求动态调整
六、适用范围与限制
适用场景
- 二维查询：订单号 + 用户ID
- 数据量大：无需维护额外映射表
- 基数稳定：查询条件维度固定且有限
不适用场景
- 多维查询：按订单号、用户ID、商品类型、时间范围等多条件查询
- 统计汇总：需要跨分片统计
- 复杂关联：需要多表关联查询
推荐方案
| 查询复杂度 | 推荐方案 | 说明 |
|---|---|---|
| 简单（1-2维） | 基因法 | 无需额外表，查询高效 |
| 中等（3维以上） | 附属路由表 | 增加映射表维护成本 |
| 复杂（多条件/聚合） | ElasticSearch | 专业搜索引擎，更灵活 |
七、总结
基因法通过利用二进制取模的数学性质，在分布式ID中优雅地编码分片信息，实现了无需额外维护表即可支持多键查询的方案。
核心优势：
- 避免维护映射表的成本
- 充分利用ID的位空间
- 在业务约束下几乎无重复风险
- 适合雪花算法改造
使用建议：
- 根据分片数灵活调整 ID 生成逻辑
- 充分评估业务中同一用户同毫秒多次操作的概率
- 当查询维度增加时及时切换为其他方案
参考资源
企业级项目导航：⬅️ 03-从决策到落地：如何根据业务优雅设计库表 | 04-分布式分库分表：基因法完全解读 | ➡️ 05-订单服务分库分表设计思维全景
💬 评论