分库分表后全局ID生成方案

JavaEdge

发布于 2022-11-30 15:11:29

5170

发布于 2022-11-30 15:11:29

文章被收录于专栏：JavaEdgeJavaEdge

依据数据库的第二范式，数据库中每一个表中都需要有一个唯一的主键，其他数据元素和主键一一对应。

那么关于主键的选择就成为一个关键点了，一般有如下方案：

使用业务字段作为主键比如说对于用户表来说，可以使用手机号，email或者身份证号作为主键。对大部分场景，这并不适用，像评论表，你很难找到一个业务字段主键。而对于用户表，考虑的是业务字段是否能够唯一标识人，一人可有多个email和手机号，一旦出现变更email或手机号，就需要变更所有引用的外键信息，所以使用email或者手机作为主键不行。身份证号码确实是用户唯一标识，但由于过于私密，并非用户系统的必须属性，你的系统如果没有要求做实名认证，肯定不会要求用户填写身份证号。而且已有身份证号码也会变化，比如1999年时身份证号从15位变为18位，但主键一变更，以该主键为外键的表也都要随之变更，影响很大。
使用生成的唯一ID作为主键因此，更推荐使用生成的ID作为数据库主键。不仅是因为其唯一性，且一旦生成就不会变更，可随意引用。

单库单表时，使用数据库自增字段作为ID，最简单，对研发也透明。但分库分表后，同一逻辑表的数据被分布到多个库中，若使用DB自增字段主键，则仅可保证在该库中唯一，无法保证全局唯一。若设计一用户系统时，使用自增ID作为用户ID，就可能出现不同库有两个相同ID的用户，这肯定不能接受，那你能咋办呢？推荐搭建发号器服务，生成全局唯一ID。

1 数据库自增id

提供一个专门用于生成主键的库，这样服务每次接收请求都

先往单点库的某表里插入一条没啥业务含义的数据
然后获取一个数据库自增id
取得id后，再写入对应的分库分表

优点

简单，是个人都会

缺点

因为是单库生成自增id，所以若是高并发场景，有性能瓶颈。若硬是要改进，那就专门开个服务：

该服务每次就拿到当前id最大值
然后自己递增几个id，一次性返回一批id
然后再把当前最大id值修改成递增几个id之后的一个值

但无论怎么说都只是基于单库。

适用场景

分库分表原因其实就俩：

单库的并发负载过高
单库的数据量过大

除非并发不高，但数据量太大导致的分库分表扩容，可用该方案，因为可能每秒最高并发最多就几百，那么就走单独的一个库和表生成自增主键即可。并发很低，几百/s，但是数据量大，几十亿的数据，所以需要靠分库分表来存放海量数据。

当数据库分库分表后，使用自增字段就无法保证 ID 的全局唯一性了吗？ 1.使用数据库的自增，设置起始值和步长不一样，不是一样可以实现吗？ 2.预估每天的数据量，预先生成ID存入缓存（比如Redis）里面，然后去取，这种方法也简单？但是这其实很难预估数据量，某一天有活动咋办？不同的起始值也可，只是增加人工成本，增加了库表咋办？忘了设置咋办？

2 UUID（Universally Unique Identifier，通用唯一标识码）

2.1 优点

本地生成，不依赖任何第三方系统，所以在性能和可用性上都比较好。

2.2 缺点

2.2.1 无序

生成的ID做好具有单调递增性，即有序。为什么ID要有序呢？因为在系统设计时，ID可能成为排序字段。比如实现评论系统，一般会设计两个表：

评论表存储评论的详细信息，其中有ID字段，有评论的内容，还有评论人ID，被评论内容的ID等等，以ID字段作为分区键
评论列表存储着内容ID和评论ID的对应关系，以内容ID为分区键

获取内容的评论列表时，需按照时间序倒排，因为ID时间上有序，所以可按评论ID倒序排列。若评论ID不在时间上有序，就得在评论列表中再冗余createTime列以排序，假设内容ID、评论ID和时间都8字节，就要多出50%存储空间存储时间字段，浪费存储空间。

ID有序会提升数据的写性能

MySQL InnoDB主键也是一种索引。索引数据在B+树中有序排列。当插入的下一条记录ID递增时，DV只需将其追加到后面。但若插入数据无序，则DB查找数据应该插入的位置，再挪动该数据后面的数据，造成多余数据移动开销。

导致 B+ 树索引写时有着过多的随机写操作，而机械磁盘：

随机写时，需先“寻道”找到要写入位置，即让磁头找到对应磁道，很耗时
顺序写就无需寻道，大大提升索引写性能

写时不能产生有顺序的 append 操作，而需要 insert，将会读取整个 B+ 树节点到内存，在插入这条记录后会将整个节点写回磁盘，这种操作在记录占用空间较大情况下，性能下降明显

2.2.2 过长

由32个16进制数字组成的字符串，若作为DB主键使用，较耗费空间。

2.2.3 不具备业务含义

现实使用的ID中都包含有一些有意义数据，这些数据会出现在ID的固定位置。如身份证：

前6位地区编号
7～14生日不同城市电话号码的区号不同，前三位即可看出所属运营商。

而若生成的ID可被反解，则从反解出的信息中即可验证ID，从而知道该ID生成时间、从哪个机房发号器生成、为哪个业务服务，这都有助问题排查。

Snowflake算法则可完美弥补UUID缺点。

适用场景

随机生成文件名、编号等，生成Request ID标记单次请求。

3 系统时间

获取当前时间即可。但问题是高并发时，会有重复，这肯定不合适啊，而且还可能修改系统时间！

适用场景

若用该方案，一般将当前时间跟很多其他的业务字段拼接起来，作为一个id。若业务上你可以接受，那也行。

你可以将别的业务字段值跟当前时间拼接起来，组成一个全局唯一的编号，比如订单编号： 时间戳 + 用户id + 业务含义编码。

4 snowflake算法（主流方案）

4.1 组成

twitter开源的分布式id生成算法，将一个64位long型id：

1 bit：不用因为二进制里第一个bit为如果是1，那么都是负数，但是我们生成的id都是正数，所以第一个bit统一0
41 bit：ms时间戳可表示数字多达2^41 - 1，即可标识2 ^ 41 - 1个毫秒值，就是69年
10 bit：记录工作机器id 代表该服务最多可部署在2^10=1024台机器。若你的系统部署在多机房，则10位机器ID可继续划分为2～3位IDC表示（可支撑4或8个IDC机房）和7～8位机器ID（支持128-256台机器）
12 bit：记录同一个毫秒内产生的不同id序列号 2 ^ 12 - 1 = 4096，即可区分同一个毫秒内的4096个不同id

4.2 举例

64位的long型的id，64位的long => 二进制

0 | 
0001100 10100010 10111110 10001001 01011100 00 |
10001 | 
1 1001 | 
0000 00000000

2018-01-01 10:00:00 做一些计算，再换算成一个二进制，41bit存储：

0001100 10100010 10111110 10001001 01011100 00

机房id，17=》换算成一个二进制=》

机器id，25=》换算成一个二进制=》

snowflake算法服务，会判断一下，当前这个请求是否是，机房17的机器25，在2175/11/7 12:12:14时间点发送过来的第一个请求，如果是第一个请求

假设，在2175/11/7 12:12:14时间里，机房17的机器25，发送了第二条消息，snowflake算法服务，会发现说机房17的机器25，在2175/11/7 12:12:14时间里，在这一毫秒，之前已经生成过一个id了，此时如果你同一个机房，同一个机器，在同一个毫秒内，再次要求生成一个id，此时我只能把加1

0 | 0001100 10100010 10111110 10001001 01011100 00 | 10001 | 1 1001 | 0000 00000001

比如我们来观察上面的那个，就是一个典型的二进制的64位的id，换算成10进制就是910499571847892992。

4.3 实践

利用这个工具类，自己搞个服务，然后对每个机房的每个机器都初始化这么一个东西，刚开始这个机房的这个机器的序号就是0。然后每次接收到一个请求，说这个机房的这个机器要生成一个id，你就找到对应的Worker，生成。这个算法生成的时候，会：

把当前毫秒放到41 bit中
然后5 bit是机房id
5 bit是机器id
接着就是判断上一次生成id的时间如果跟这次不一样，序号就自动从0开始；要是上次的时间跟现在还是在一个毫秒内，他就把seq累加1，就是自动生成一个毫秒的不同的序号

该算法可以确保每个机房每个机器每一毫秒，最多生成4096个不重复的id。

利用这个snowflake算法，可以开发自己公司的服务，甚至对于机房id和机器id，反正给你预留了5 bit + 5 bit，你换成别的有业务含义的东西也可。

不同公司也会依据自身业务的特点对Snowflake算法做一些改造：

减少序列号位数，增加机器ID位数以支持单IDC更多的机器
在其中加入业务ID字段来区分不同业务。如组成规则：1位兼容位恒为0 + 41位时间信息 + 6位IDC信息（支持64个IDC）+ 6位业务信息（支持64个业务）+ 10位自增信息（每毫秒支持1024个号）

主要因为在单机房只部署一个发号器节点，且使用KeepAlive保证可用性。业务信息指的是项目中哪个业务模块使用，如用户模块生成的ID，内容模块生成的ID，把它加入进来：

希望不同业务发出来的ID可以不同
因为在出现问题时可以反解ID，知道哪个业务发出的ID

工程化

为业务生成全局唯一ID，一般有如下算法实现：

嵌入业务代码

即分布在业务服务器中。

好处业务代码在使用时无需跨网络调用，性能好些，但需更多机器ID位数支持更多业务服务器。由于业务服务器数很多，难保证机器ID唯一性，所以需引入ZooKeeper等分布式一致性组件保证每次机器重启时，都能获得唯一机器ID。

作为独立的服务部署

即发号器服务。业务在使用发号器的时候就需要多一次的网络调用，但是内网的调用对于性能的损耗有限，却可以减少机器ID的位数，如果发号器以主备方式部署，同时运行的只有一个发号器，那么机器ID可以省略，这样可以留更多的位数给最后的自增信息位。即使需要机器ID，因为发号器部署实例数有限，那么就可以把机器ID写在发号器的配置文件里，这样即可以保证机器ID唯一性，也无需引入第三方组件了。微博和美图都是使用独立服务的方式来部署发号器的，性能上单实例单CPU可以达到两万每秒。

Snowflake算法设计的非常简单且巧妙，性能上也足够高效，同时也能生成具有全局唯一性、单调递增性和有业务含义的ID，但是它也有一些缺点，最大缺点就是依赖系统时间戳，一旦系统时间不准，就有可能生成重复ID。所以如果我们发现系统时钟不准，就可以让发号器暂时拒绝发号，直到时钟准确。

如果请求发号器的QPS不高，比如说发号器每毫秒只发一个ID，就会造成生成ID的末位永远是1，那么在分库分表时如果使用ID作为分区键就会造成库表分配的不均匀。解决：

时间戳不记录毫秒而是记录秒，这样在一个时间区间里可以多发出几个号，避免出现分库分表时数据分配不均
生成的序列号的起始号可以做一下随机，这一秒是21，下一秒是30，这样就会尽量的均衡了

生产都使用变种的Snowflake算法，这些改造：

让算法中的ID生成规则符合自己业务的特点
解决诸如时间回拨等问题

如果我们发现系统时钟不准，就可以让发号器暂时拒绝发号，直到时钟准确为止。我们的程序本身就是运行在系统中的，如何来判断系统中的时间是否准确呢？可以暂时记录上次发好的时间，然后和这次的时间比较。

假设通过容器化来部署发号器，且同时会有多个发号器容器运行，那这个 worker Id 如何生成。容器自身的 id 是一串很长的16进制，无法转换为 worker id 吧？难道也需要引入 zookeeper？有没有其他简单可行的方案？容器ID太长了。其实引入zk也还好，对于zk是弱依赖，只是启动的时候拉一下机器ID。

其它方案

百度开源的UidGenerator

（仅支持单机部署）使用Snowflake算法，单机QPS可达600万。项目说明：https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md 。

美团Leaf（分布式ID生成系统）

QPS近5万。项目地址：https://tech.meituan.com/2017/04/21/mt-leaf.html 。

微信序列号生成器

文档地址：https://www.infoq.cn/article/wechat-serial-number-generator-architecture

递增但不连续的数字序列解决方案。
设计目标QPS1000万以上。
通过在递增过程中使用“步长”将每秒磁盘写入由1000万级降至1万。
设计原理相对于Snowflake更通俗易懂。
可以使用hash的负载均衡策略组建集群。
缺点：需要自己实现集群中机器增减后更新负载均衡策略的逻辑。

Java版最简单Demo

使用spring boot搭建一个web工程，使用Controller调用Service实现数字递增 Service类

import org.springframework.stereotype.Service;

import javax.annotation.PostConstruct;
import java.util.concurrent.atomic.AtomicLong;

@Service
public class GeneratorService {

private AtomicLong id;

@PostConstruct
private void init(){
id = new AtomicLong(0);
}

public long getId(){
return id.incrementAndGet();
}
}

单机测试QPS 3万（测试工程、测试脚本在同一机器运行。）硬件信息：CPU 2.7 GHz Intel Core i7 | 内存 16 GB 2133 MHz LPDDR3 测试工具：JMeter

4.3 实现

public class IdWorker {

    private long workerId;
    private long datacenterId;
    private long sequence;

    public IdWorker(long workerId, long datacenterId, long sequence) {
        // sanity check for workerId
        // 这儿不就检查了一下，要求就是你传递进来的机房id和机器id不能超过32，不能小于0
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(
                    String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(
                    String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
        }
        System.out.printf(
                "worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
                timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);

        this.workerId = workerId;
        this.datacenterId = datacenterId;
        this.sequence = sequence;
    }

    private long twepoch = 1288834974657L;

    private long workerIdBits = 5L;
    private long datacenterIdBits = 5L;

    // 这个是二进制运算，就是 5 bit最多只能有31个数字，也就是说机器id最多只能是32以内
    private long maxWorkerId = -1L ^ (-1L << workerIdBits);

    // 这个是一个意思，就是 5 bit最多只能有31个数字，机房id最多只能是32以内
    private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
    private long sequenceBits = 12L;

    private long workerIdShift = sequenceBits;
    private long datacenterIdShift = sequenceBits + workerIdBits;
    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    private long sequenceMask = -1L ^ (-1L << sequenceBits);

    private long lastTimestamp = -1L;

    public long getWorkerId() {
        return workerId;
    }

    public long getDatacenterId() {
        return datacenterId;
    }

    public long getTimestamp() {
        return System.currentTimeMillis();
    }

    public synchronized long nextId() {
        // 这儿就是获取当前时间戳，单位是毫秒
        long timestamp = timeGen();

        if (timestamp < lastTimestamp) {
            System.err.printf("clock is moving backwards.  Rejecting requests until %d.", lastTimestamp);
            throw new RuntimeException(String.format(
                    "Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }

        if (lastTimestamp == timestamp) {
            // 这个意思是说一个毫秒内最多只能有4096个数字
            // 无论你传递多少进来，这个位运算保证始终就是在4096这个范围内，避免你自己传递个sequence超过了4096这个范围
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0;
        }

        // 这儿记录一下最近一次生成id的时间戳，单位是毫秒
        lastTimestamp = timestamp;

        // 这儿就是将时间戳左移，放到 41 bit那儿；
        // 将机房 id左移放到 5 bit那儿；
        // 将机器id左移放到5 bit那儿；将序号放最后12 bit；
        // 最后拼接起来成一个 64 bit的二进制数字，转换成 10 进制就是个 long 型
        return ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift)
                | (workerId << workerIdShift) | sequence;
    }

    private long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    private long timeGen() {
        return System.currentTimeMillis();
    }

    // ---------------测试---------------
    public static void main(String[] args) {
        IdWorker worker = new IdWorker(1, 1, 1);
        for (int i = 0; i < 30; i++) {
            System.out.println(worker.nextId());
        }
    }

}