0x00 分布式唯一id的生成策略简介

作为一个分布式唯一id，一般要求其具有以下特征：

  • 全局唯一：在同一业务场景里面必须保持全局的唯一。
  • 趋势递增：在MySQL InnoDB存储引擎中使用的是聚集索引，所以在主键的选择上我们应该尽量使用有序的主键来保证写入的性能。
  • 信息安全：如果id是连续的，那恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险，竞争对手可以直接知道我们一天的单量。所以在一些应用场景下，会需要ID无规则、不连续。

0x01 数据库自增长序列或字段

最常见的方法，利用数据库，可保证全数据库唯一。

优点：

  • 简单，性能可以接受。
  • 代码方便，在INSERT语句中直接把主键字段空出来，交由数据库自动填充即可。
  • 生成的数字id天然排序，对分页或者需要排序的结果很有帮助。

缺点：

  • 不同数据库的语法和内部实现方法不同，在数据库迁移的时候可能需要额外的处理。
  • 在单个数据库或者一主多从的情况下，只有一个主库可以生成，有单点故障的风险。
  • 在性能达不到要求的情况下，难于扩展。
  • 分表分库时可能会带来麻烦。

对于有多个主库的情况下，可以设置每个主库的起始数字不一样但步长一样。比如一个主库生成的id全是奇数，另外一个生成的id全是偶数，也可有效生成分布式唯一id。推广到一般情况就是，我们要部署N台机器，则步长需设置为N，每台的初始值依次为0, 1, 2…N-1。

在这种模式下，系统的水平扩展将会成为问题，在定义好了步长和机器数之后，如果需要添加机器将变得十分困难，我们现在考虑一个场景，现在有2台机器，机器A从1开始发奇数号，机器B从2开始发偶数号。我现在又要再扩展一个机器C，假设现在机器A发号发到101，机器B发号发到102了，那我们就设置机器C的起始发号为1000（假设在扩容时间内前两台机器发号都发不到1000），步长为3，然后A和B继续发号直到遇到编号1000之前的最后一个号，对于机器A来说则是999，对于机器B来说则是998，然后此时修改A和B的步长都为3，这样机器A, B, C就可以在新的发号模式下同时运作且不产生重复号了。修改步长的过程则需要暂停A和B的发号服务然后重新设置。这个扩展方案看似还好，但是如果线上机器很多的话，那就是难以实现的。

0x02 UUID

UUID即通用唯一识别码，其设计的目的就是为了让分布式系统中的所有元素都有唯一的辨识信息，一般来说这个值生成出来就是全球唯一的。GUID是微软公司出的一套UUID生成组件。

UUID的生成即可交给数据库去做，比如可以在MySQL数据库中使用UUID()函数来生成UUID，MySQL中的UUID()函数返回的是带-分隔符的UUID。同时，也可以交给ORM框架去做，例如Hibernate框架就有一套自己的UUID生成机制，其返回的UUID符合如下规则：IP-JVM启动时间-当前时间右移32位-当前时间-内部计数（8-8-4-8-4）。

优点：

  • 简单，很多数据库和编程语言都内置UUID的生成函数。
  • 生成ID的性能好，基本不会有性能问题。
  • 全球唯一，在数据迁移、数据合并或数据库变更等情况下可以从容应对。

缺点：

  • 无法保证趋势递增。
  • 需使用字符串来存储，查询效率低。
  • 存储空间比较大，如果是海量数据就需要考虑存储量的问题；
  • 对MySQL索引不利：如果作为数据库主键，在InnoDB引擎下，UUID的无序性可能会引起数据位置频繁变动，严重影响性能。
  • 信息不安全：基于MAC地址生成UUID的算法可能会造成MAC地址的泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。

0x03 Snowflake算法

这是Twitter公司出的分布式唯一ID的生成算法，其结果是一个64bit的整数（Java中的long类型），其结构如下：

我们从左往右看，第一位一直是0，这一位是不用的，而且它也不能是1，原因很简单，这一位如果是1，那整个值都会变成负数，id是负数这种情况显然是不合理的。所以我们实际可用的只有后面63位。

紧接着的41个bit是时间戳，这个时间戳转换成10进制的毫秒数最大值为2199023255551。Linux的时间戳是从1970年的某个时间开始计时的毫秒数，但我们一般将其即设为从某个时间点开始的毫秒数，比如统一设置的集群启动时间，然后这41位所记录的值即为现在的时间戳减去这个统一的集群启动时间的时间戳。

然后是10bit的集群中的机器id，2的10次方是1024，也就是这个算法最多支持1024个结点，全用上这个集群的规模也可见一斑了。

最后12位是交由集群中的每个结点自行生成的自增长序列值。2的12次方即为4096，也就是说每一毫秒，每个分布式节点都可以生成4096个分布式id而不重复。

需要注意的一点是，如果前端和后端需要用到这个id来打交道的话，JavaScript最大支持的整数的精度是53位，64位已经超出了JavaScript支持的最大整数精度，所以需要用字符串来保存这个生成的id。这一点在Twitter官方有关Snowflake算法的介绍文档中就有提到。

这种丢失精度的现象，你可以在你浏览器的控制台使用如下代码查看：

1
(90071992547409921).toString()

除此之外，还可以自定义精简版的Snowflake算法，比如缩小64位至53位。

优点：

  • 生成效率高
  • 毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。
  • 不依赖数据库，以服务的方式部署，稳定性高。

缺点：

  • 强依赖机器时钟，如果机器时钟回拨，会导致发号重复或服务不可用。

好了，我们来自个实现一下Snowflake算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.util.concurrent.atomic.AtomicLong;

public class SnowflakeIdentifierHelper {

    private final long twepoch;  // 起始时间戳
    private final int timestampBits;  // 时间戳的位数
    private final int workerIdentifier;  // 工作机器id
    private final int workerIdentifierBits;  // 工作机器id的位数
    private final int sequenceBits;  // 最后序列号的位数
    // 毫秒内序列号
    private final AtomicLong sequence = new AtomicLong(0);
    // 最后一次生成id的时间戳
    private final AtomicLong lastTimeStamp = new AtomicLong(0);

    public SnowflakeIdentifierHelper(int workerIdentifier, long twepoch) {
        this(41, 10, 12, workerIdentifier, twepoch);
    }

    public SnowflakeIdentifierHelper(int timestampBits, int workerIdentifierBits, int sequenceBits, int workerIdentifier, long twepoch) {
        this.timestampBits = timestampBits;
        this.workerIdentifier = workerIdentifier;
        this.workerIdentifierBits = workerIdentifierBits;
        // 确保输入的工作机器id在其bit位数所限制的范围之内
        if (workerIdentifier >= (1 << workerIdentifierBits)) {
            throw new IllegalArgumentException("The worker's id not matches the specific length of bits of it.");
        }
        this.sequenceBits = sequenceBits;
        // 确保所有部分的位数加和小于等于63，以防long溢出
        if (this.timestampBits + this.workerIdentifierBits + this.sequenceBits > 63) {
            throw new IllegalArgumentException("The length of bits of Snowflake identifiers is larger than the length of a long integer.");
        }
        this.twepoch = twepoch;
    }

    public long generate() throws InterruptedException {
        long timestamp;
        synchronized (lastTimeStamp) {
            timestamp = System.currentTimeMillis() - twepoch;
            // 必须是1L而不能是1，因为1是int型，1L是long型，1<<41的结果会导致整型溢出
            if (timestamp >= (1L << timestampBits)) {
                throw new RuntimeException("Timestamp overflows.");
            }
            // 生成的时间戳小于最后一次生成的时间戳即出现了时钟回拨现象
            if (timestamp < lastTimeStamp.get()) {
                throw new RuntimeException("Clock moved backwards.");
            }
            // 归零毫秒内计数器，如果毫秒变了的话
            if (timestamp != lastTimeStamp.get()) {
                sequence.set(0);
            }
            lastTimeStamp.set(timestamp);
        }
        long sequenceNumber = sequence.incrementAndGet();
        if (sequenceNumber >= (1L << sequenceBits)) {
            // 如果当前毫秒内计数器值超过其最大值，那就小睡1ms再生成一遍
            Thread.sleep(1);
            return generate();
        }
        // 按位或的效率比加法高哦！
        return (timestamp << (workerIdentifierBits + sequenceBits)) |
                (workerIdentifier << sequenceBits) | sequenceNumber;
    }
}

TL;DR

在generate()函数中为什么要用synchronized？

我们必须用synchronized框起所有与时间戳计算有关的部分，原因在于lastTimeStamp是所有线程的共享变量，AtomicLong仅保证其在加减运算时是线程安全的，并不能保证下面的代码也是线程安全的：

1
2
3
4
5
6
7
8
9
10
11
timestamp = System.currentTimeMillis() - twepoch;
if (timestamp >= (1L << timestampBits)) {
    throw new RuntimeException("Timestamp overflows.");
}
if (timestamp < lastTimeStamp.get()) {
    throw new RuntimeException("Clock moved backwards.");
}
if (timestamp != lastTimeStamp.get()) {
    sequence.set(0);
}
lastTimeStamp.set(timestamp);

在上述代码片中，假设线程1执行了第一行代码，得到的时间戳我们假设是10000，此时处理器切换到了线程2，线程2也得到了一个时间戳假设是20000，线程2执行完了所有的代码，线程2执行完成最后一行代码代码之后将lastTimeStamp设置成了自己生成的时间戳20000，这个时候线程2再切换到线程1继续执行的话，就会抛出RuntimeException("Clock moved backwards.")。线程1就会错误地认为时钟回拨了。所以我们必须让所有有关时间戳的代码并发执行一次完成。

为什么要用AtomicLong而不直接用long？

在32位操作系统中，64位的long和double变量由于会被JVM当作两个分离的32位来进行操作，所以不具有原子性。而使用AtomicLong能让long的操作保持原子型。

上面这份代码的id生成效率是非常高的，我们用如下测试代码生成了1亿条id，耗时46.653s。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadPoolExecutor;

public class Main {

    public static void main(String[] args) throws IOException {
        // 假设worker id是101，起始时间戳是1577808000L
        SnowflakeIdentifierHelper helper = new SnowflakeIdentifierHelper(101, 1577808000L);
        // 创建包含16个线程的线程池
        ThreadPoolExecutor executor = (ThreadPoolExecutor) Executors.newFixedThreadPool(16);
        FileOutputStream fileOutputStream = new FileOutputStream(new File("F:/Desktop/ids.txt"));
        // 循环调用1000次
        for (int j = 0; j < 1000; j++) {
            executor.execute(() -> {
                // 每个线程生成100000条id并写入文件
                for (int i = 0; i < 100000; i++) {
                    try {
                        long id = helper.generate();
                        // 将整数型的id转换成二进制字符串
                        // 方便我们对比查看程序输出结果是否有误
                        String s = Long.toBinaryString(id);
                        // toBinaryString函数会将二进制结果前面的0舍弃，我们给它手动加上
                        s = s.length() == 63 ? "0" + s : s;
                        String result = s.charAt(0) + " " + s.substring(1, 42) + " " + s.substring(42, 52) + " " + s.substring(52, 64) + "\r\n";
                        fileOutputStream.write(result.getBytes());
                    } catch (InterruptedException | IOException ignored) {

                    }
                }
            });
        }
        fileOutputStream.flush();
        executor.shutdown();
    }
}

此后我们将结果转换成二进制字符串写入文件，生成的id文件占地6.58GB，我们将程序的输出文件中节选了10条，如下：

1
2
3
4
5
6
7
8
9
10
0 10110111111000111001111000000000101101101 0001100101 000000000011
0 10110111111000111001111000000000101101011 0001100101 000000000100
0 10110111111000111001111000000000101101110 0001100101 000000000011
0 10110111111000111001111000000000110110011 0001100101 000000000001
0 10110111111000111001111000000000110110100 0001100101 000000000001
0 10110111111000111001111000000000110110100 0001100101 000000000010
0 10110111111000111001111000000000101101110 0001100101 000000000010
0 10110111111000111001111000000000110110100 0001100101 000000000100
0 10110111111000111001111000000000110110100 0001100101 000000000111
0 10110111111000111001111000000000110110100 0001100101 000000000110

0x04 Leaf-segment方案

这种方案和下述的Leaf-snowflake方案都是美团公司提出来的，Leaf-segment方案改进了上述的数据库自增长序列的方案，Leaf-snowflake则改进了上述了的Snowflake算法。

我们先来看一下Leaf-segment方案。基于数据库自增长序列生成id，如果我们直接在创建表的时候指定主键id为AUTO_INCREMENT，在高并发的情况下，可能会增大数据库压力，因为每次获取一个id都要读写一遍数据库。为了解决这个问题，我们单设一个表，将id划分为一个个的号段（segment），然后将号段发配给发号服务器，发号服务器再在号段内不断发号，同时我们定义一个表用于保存某业务的发号信息，其结构如下：

1
2
3
4
5
6
7
8
9
+-------------+--------------+------+-----+-------------------+-----------------------------+
| Field       | Type         | Null | Key | Default           | Extra                       |
+-------------+--------------+------+-----+-------------------+-----------------------------+
| biz_tag     | varchar(128) | NO   | PRI |                   |                             |
| max_id      | bigint(20)   | NO   |     | 1                 |                             |
| step        | int(11)      | NO   |     | NULL              |                             |
| desc        | varchar(256) | YES  |     | NULL              |                             |
| update_time | timestamp    | NO   |     | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+-------------+--------------+------+-----+-------------------+-----------------------------+

其中，biz_tag用来区分业务，max_id表示该biz_tag目前所被分配的id号段的最大值，step表示每次分配的号段长度。原来获取ID每次都需要写数据库，现在只需要把step设置得足够大，比如1000。那么只有当1000个号被消耗完了之后才会去重新读写一次数据库。读写数据库的频率从1减小到了1/step。

在这种方案中，我们需要单独定义一个用于发号的代理服务器，即proxy server，这个服务每次从数据库中申请一个号段，用于发号。整个系统的架构如下图所示：

所有的数据库插入请求来了之后，经proxy server分配id，然后插入数据库。当proxy server中所保存的号段用完了之后，再通过如下方法申请一个新的号段：

1
2
3
4
Begin
UPDATE table SET max_id=max_id+step WHERE biz_tag=xxx;
SELECT tag, max_id, step FROM table WHERE biz_tag=xxx;
Commit

这是一个SQL事务，其具有原子性，要么执行并且全部执行完，要么不执行。在数据库层面上保证了多个proxy server并发读写一个业务号段信息时的安全性，防止脏读。

假设业务test_tag在第一台Leaf机器上是1~1000的号段，当这个号段用完时，会去加载另一个长度为step=1000的号段，假设另外两台号段都没有更新，这个时候第一台机器新加载的号段就应该是3001~4000。同时数据库对应的biz_tag这条数据的max_id会从3000被更新成4000。

优点：

  • 可以方便地进行线性扩展。
  • 容灾性高，Leaf服务内部有号段缓存，即使DB宕机，短时间内Leaf仍能正常对外提供服务。
  • 可以自定义max_id的大小，非常方便业务从原有的ID方式上迁移过来。

缺点：

  • ID号码不够随机，能够泄露发号数量的信息，不太安全。
  • DB宕机会造成整个系统不可用。
  • TP999数据波动大，当号段使用完之后还是会hang在更新数据库的I/O上。

TL;DR

TP999计算方法：

假设一个接口被调用1000次，1000次的调用耗时分别为1ms, 2ms…998ms, 999ms, 1000ms，我们对所有的耗时进行升序排序，并将排序后的序列从1开始标号，然后取标号为1000*99.9%=999的数据，也就是999ms作为其TP999值。

所以，在请求量很小的情况下（≤1000），TP999基本上就是其最慢的那次请求的耗时。

对于TP999波动较大的问题，我们可以采用双缓冲（buffer）优化来解决。这个方案说起来其实很简单，在原有的方案中，proxy server每次都是在发完当前号段最后一个ID后，然后请求数据库去取号，也就意味着号段临界点的ID下发时间取决于下一次从DB取回号段的时间。假如在这期间新的号段没有从数据库中取回来，就会导致进来请求的线程被阻塞。如果请求DB的网络和DB的性能稳定，这种情况对系统的影响是不大的，但是假如取DB的时候网络发生抖动，或者DB发生慢查询就会导致整个系统的响应时间变慢。

为此，我们可以设置一个临界点（比如说为当前号段70%的位置），当号段消费到这个临界点的时候就异步取号，把下一个号段提前加载到内存，而不需要等号段完全消费完成之后再去取号。这样就可以大幅度减少TP999指标。

对于Leaf-segment方案，通常推荐segment长度设置为服务高峰期发号QPS的600倍（10分钟），这样即使DB宕机，Leaf仍能持续发号10-20分钟不受影响。

0x05 Leaf-snowflake方案

Leaf-snowflake方案沿用了原Snowflake对id的设计，其主要解决两个问题，其一就是服务器worker id的分发，其二就是时钟回拨问题。

对于第一个问题，其采用Zookeeper的持久顺序节点的特性自动对snowflake节点配置worker id。其启动时首先连接Zookeeper，检查自己在leaf_forever节点下已经注册过，如果注册过直接取回自己的worker id，否则在这个节点下创建一个新的持久顺序节点，创建成功后取回自己的worker id。同时其取回自己的worker id后，还会将这个id在本机上做缓存，当Zookeeper出现问题，恰好机器出现问题需要重启时，也能保证服务能够正常启动。

TL;DR

判断当前节点在Zookeeper中是否注册过可采用机器网卡的MAC地址或者ip:port的形式查找。

对于时钟回拨问题的解决，首先，机器会周期性地（每隔3秒）向其所属Zookeeper的leaf_forever节点下上传自己的时间戳，机器启动时则与这个节点所记录的时间戳做对比，如果小于，就说明发生了大步长的时钟回拨，这时服务启动失败并报警。然后得到leaf_temproary下所有节点的ip:port，然后通过远程过程调用获取所有正在服务的机器的机器时间，做平均值校验，如果误差小于一定的阈值，则认为当前系统时间准确。

整个的流程图，如下所示：