分表算法都有哪些？

结论：分片算法（Sharding Algorithm）常见的就五类：哈希取模（Hash Modulo）、范围（Range）、范围加哈希（Range + Hash）、一致性哈希（Consistent Hashing）、目录表（Lookup/Directory）。没有一种通吃：取模均匀但扩容贵，范围扩容便宜但易热点，一致性哈希迁移少但实现重，目录表最灵活但多一次查询。

一、算法对比

二、三种典型结构

① 取模                      ② 范围                       ③ 目录表
 key ── hash % 16            key ── 区间判定               key ── 查映射表
   │                           │                             │
   ▼                           ▼                             ▼
 t_0 t_1 ... t_15          t_2024 t_2025 t_2026         t_shard_a / t_shard_b
 （均匀，扩容全动）         （顺序写，尾部热点）           （灵活，多一跳）

三、一致性哈希的最小实现

public class ConsistentHashRing {
    private final TreeMap<Long, String> ring = new TreeMap<>();
    private final int virtualNodes;

    public ConsistentHashRing(List<String> nodes, int virtualNodes) {
        this.virtualNodes = virtualNodes;
        for (String node : nodes) {
            for (int i = 0; i < virtualNodes; i++) {
                ring.put(hash(node + "#VN" + i), node);
            }
        }
    }

    public String route(String key) {
        if (ring.isEmpty()) {
            throw new IllegalStateException("哈希环为空");
        }
        Map.Entry<Long, String> e = ring.ceilingEntry(hash(key));
        return e != null ? e.getValue() : ring.firstEntry().getValue();  // 回绕
    }

    private long hash(String s) {
        long h = 1125899906842597L;
        for (int i = 0; i < s.length(); i++) {
            h = 31 * h + s.charAt(i);
        }
        return h & Long.MAX_VALUE;
    }
}

虚拟节点（Virtual Node）用来打散数据：一个物理节点映射到 100 到 200 个虚拟节点后，新增节点只影响相邻区间，迁移量约为 1/(N+1)。

四、目录表方案

CREATE TABLE t_shard_route (
  tenant_id  BIGINT UNSIGNED NOT NULL,
  db_name    VARCHAR(32) NOT NULL,
  tbl_name   VARCHAR(64) NOT NULL,
  updated_at DATETIME    NOT NULL,
  PRIMARY KEY (tenant_id)
) ENGINE=InnoDB;

-- 大客户单独指向独立库，普通客户指向共享分片
INSERT INTO t_shard_route VALUES (1001, 'ds_vip', 't_order_0', NOW());
INSERT INTO t_shard_route VALUES (1002, 'ds0',    't_order_3', NOW());

路由表可缓存在应用本地，变更时通过配置中心推送。它把分片规则从代码里抽出来，扩缩容和大客户隔离都不再需要发版。

五、算法落地时的三个约束

1. 路由必须无状态且可复现：同一 key 在任何节点、任何时间都要算出同一个分片，不能依赖本地缓存或随机数。
2. 算法要能被中间件识别：ShardingSphere 支持把自定义算法注册为 CLASS_BASED，否则只能写表达式。
3. 变更要可回滚：新旧算法并行一段时间，靠双写与比对保证数据一致。

六、常见追问

Q1：取模和一致性哈希怎么选？ 分片数固定、追求实现简单就取模；节点会频繁增减、且能接受实现复杂度就一致性哈希。数据库分片更常用「预分片 + 取模」，因为库的增减远没有缓存节点频繁。

Q2：范围分片为什么会有写热点？ 新数据总是落在最大区间，写入集中在一个分片。解法是「范围 + 哈希」两层：先按时间或 ID 段分区，段内再哈希打散。

Q3：分片算法能在线切换吗？ 不能直接切。需要新老算法双写、存量数据迁移、灰度切读，最后才下线旧算法。

小结

• 取模求均匀，范围求有序，一致性哈希求平滑迁移，目录表求灵活。
• 生产上常组合使用：外层范围便于归档，内层哈希保证均匀。
• 算法一旦上线就很难改，选型时要把未来三年的扩容路径一起想清楚。