--- title: "04-分布式分库分表：基因法完全解读" created: 2025-12-11 aliases: - 分布式分库分表：基因法完全解读 tags: - 项目 --- # 分布式分库分表：基因法完全解读 ## 视频 ![[image-6151071f.png]] ## 一、问题背景 ### 分片键不足的困境 在分库分表的设计中，经常遇到**查询条件不含分片键**的情况。典型场景是用户表： - 订单通过 `userId` 关联用户信息 - 用户登录时可使用手机号或邮箱 - 仅用 `userId` 作为分片键无法满足多种查询需求 ### 传统解决方案：附属表路由 创建附属表维护映射关系： - **用户手机表**：以手机号为分片键，存储 `userId` - **用户邮箱表**：以邮箱为分片键，存储 `userId` - 查询流程：手机号/邮箱 → 查询附属表得到 `userId` → 查询原表 ### 存在的问题 这种方案虽然可行，但需要**额外维护附属表**。对于订单这类数据量巨大的业务，附属表的维护成本会很高。 **需求**：既能通过 `order_number` 查询订单详情，也能通过 `userId` 查询用户订单列表，且无需维护额外的映射表。 **解决方案**：基因法（Genetic Algorithm in Sharding） --- ## 二、基因法的数学原理 ### 核心特征观察 通过取模运算的二进制性质，我们发现一个有趣的规律： ```text 191 % 32 = 31 191的二进制： 10111111 32的二进制： 100000 (2的5次方) 31的二进制： 11111 ``` **关键观察**：31 的二进制（`11111`）与 191 的二进制最后 5 位完全相同。 ### 数学规律 如果我们将任意数的二进制后 5 位替换为另一个数的后 5 位，再对 32 取模，结果就是那个被替换的数对 32 的取模结果。这里的 5 位长度 = log₂(32)。 **验证**： ```text 159的二进制： 10011111 159 % 32 = 31 （最后5位也是 11111） ``` ### 通用公式 对于分片数 `shardingCount = 2^n`： - 计算 `sequenceShift = log₂(shardingCount)` - 将数字 A 的二进制后 `sequenceShift` 位替换为数字 B 的后 `sequenceShift` 位 - 新数字对 `shardingCount` 取模 = B 对 `shardingCount` 取模 --- ## 三、基因法在订单系统中的应用 ### 代码演示 ```java 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); } } ``` ### 执行结果 ```yaml 要替换的二进制后位数: 5 num1 替换前的二进制: 10011110001101011100011100110100 num1 替换后的二进制: 10011110001101011100011100101100 num2 的十进制: 12 num2 的二进制: 01100 num1 对应的十进制数为: 2654324524 替换后订单号取模结果: 12 用户id取模结果: 12 ``` ### 流程总结 1. **参数**：分片数 `shardingCount = 32`，订单号 `orderNumber = 2654324532`，用户 `userId = 45346343212` 2. **计算**：`sequenceShift = log₂(32) = 5` 3. **二进制转换**： - `orderNumber` → `10011110001101011100011100110100` - `userId % 32 = 12` → `01100` 4. **位替换**：将订单号的后 5 位替换为 `01100` 5. **结果**：`10011110001101011100011100101100` → 十进制 `2654324524` 6. **验证**：`2654324524 % 32 = 12` ✓ --- ## 四、与雪花算法结合 ### 雪花算法结构回顾 雪花算法生成的 64 位 ID 结构： | 部分 | 位数 | 说明 | | --- | --- | --- | | 符号位 | 1 | 固定为 0（保证为正数） | | 时间戳 | 41 | 精确到毫秒，可用约 69 年 | | 数据中心 | 5 | 最多 32 个数据中心 | | 机器ID | 5 | 最多 32 台机器 | | 序列号 | 12 | 同毫秒内最多 4096 个 | ### 重复性分析 **关键问题**：在同一毫秒、同一台机器上生成两个 ID 时，它们唯一的区别是序列号相差 1。如果用基因法将后 5 位替换，这两个 ID 会重复。 **但结合业务考虑**： - 对于订单场景，后 5 位被替换为 `userId % shardingCount` - 重复需要同一用户在**同一毫秒内创建多个订单** - 正常用户不会这样做，只有机器刷单或恶意攻击才会触发 - **重复概率极低，可以接受** --- ## 五、改造后的雪花算法 ### 基础版本（固定分片数） ```java 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 个不重复订单号 ### 测试验证 ```java public void testOrderNumber(){ List idList = new ArrayList<>(); for (int i = 0; i < 256; i++) { long orderNumber = snowflakeIdGenerator.getOrderNumber(2222); idList.add(orderNumber); } Map> collect = idList.stream() .collect(Collectors.groupingBy(id -> id)); int count = 0; for (final Entry> entry : collect.entrySet()) { if (entry.getValue().size() > 1) { count++; } } System.out.println("重复的orderNumber数量: " + count); // 结果: 0 } ``` ### 灵活版本（支持参数化） ```java /** * 获取订单编号 * @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 生成逻辑 - 充分评估业务中同一用户同毫秒多次操作的概率 - 当查询维度增加时及时切换为其他方案 --- ## 参考资源 - [技术精华-解锁分库分表新姿势：基因法完全解读](https://www.yuque.com/u22210564/ykdrdh/lnsmfsas4e7b3cvs) - [技术精华-雪花算法完全解读](https://www.yuque.com/u22210564/ykdrdh/iyxwyiy6ga7p4rqi) - [组件讲解-分布式ID生成器揭秘](https://www.yuque.com/u22210564/ykdrdh/ahgwiywela7xxego) --- **企业级项目导航**：⬅️ [[03-从决策到落地：如何根据业务优雅设计库表|03-从决策到落地：如何根据业务优雅设计库表]] | 04-分布式分库分表：基因法完全解读 | ➡️ [[05-订单服务分库分表设计思维全景|05-订单服务分库分表设计思维全景]]