背景

在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识。如在各产品的系统中，数据日渐增长，对数据分库分表后需要有一个唯一ID来标识一条数据或消息，数据库的自增ID显然不能满足需求，此时一个能够生成全局唯一ID的系统是非常必要的。

概括下来，那业务系统对ID号的要求有哪些呢？

  1. 全局唯一性：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。
  2. 趋势递增：在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B+tree的数据结构来存储索引数据，在主键的选择上我们应该尽量使用有序的主键保证写入性能。
  3. 单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求。
  4. 信息安全：如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，会需要ID无规则、不规则。

上述1、2、3对应三类不同的场景，3和4需求还是互斥的，无法使用同一个方案满足。

同时，除了对ID号码自身的要求，业务还对ID号生成系统的可用性要求极高，想象一下，如果ID生成系统瘫痪，整个平台、领域的功能都无法执行，这就会带来一场灾难。

由此总结出一个分布式ID生成系统应该做到如下几点：

  1. 平均延迟和TP999延迟都要尽可能低；
  2. 可用性5个9；
  3. 高QPS。

常见方法介绍

UUID

UUID(Universally Unique Identifier)的标准型式包含32个16进制数字，以连字号分为五段，形式为8-4-4-4-12的36个字符，示例：550e8400-e29b-41d4-a716-446655440000。

优点：

  • 性能非常高，本地生成，没有网络消耗。

缺点：

  • 不易于存储。UUID太长，16字节128位，通常以36长度的字符串表示，很多场景不适用。
  • 信息不安全。基于MAC地址生成UUID的算法可能会造成MAC地址泄露。
  • ID作为主键时在特定的环境会存在一些问题，比如做DB主键的场景下，UUID非常不适用。
    • MySQL官方有明确的建议，主键要尽量越短越好，36个字符长度的UUID不符合要求；
    • 对MySQL索引不利。如果作为数据库主键，在InnoDB引擎下，UUID的无序性可能会引起数据位置频繁变动，严重影响性能。

雪花算法 snowflake

twitter开源的分布式id生成算法。
把一个64位的long型的id，1个bit是不用的，用其中的41 bit作为毫秒数，用10 bit作为工作机器id，12 bit作为序列号。
理论上最多支持1024台机器每秒生成4096000个序列号。

  • 1 bit：固定值0
    因为二进制里第一个bit为如果是1，那么都是负数，但是我们生成的id都是正数，所以第一个bit统一都是0
  • 41 bit：表示的是时间戳，单位是ms
    41 bit可以表示的数字多达2^41 - 1，也就是可以标识2 ^ 41 - 1个毫秒值，换算成年就是表示69年的时间
  • 10 bit：记录工作机器id
    代表的是这个服务最多可以部署在2^10台机器上面，也就是1024台机器。
    但是10 bit里5个bit代表机房id，5个bit代表机器id，意思就是最多代表2 ^ 5个机房(32个机房)，每个机房里可以代表2 ^ 5个机器(32台机器)。
  • 12 bit：记录同一个毫秒内产生的不同id
    12 bit可以代表的最大正整数是2 ^ 12 - 1 = 4096，也就是说可以用这个12bit代表的数字来区分同一个毫秒内的4096个不同的id

优点：

  • 高并发分布式环境下生成不重复 id，每秒可生成百万个不重复 id。
  • 基于时间戳，以及同一时间戳下序列号自增，基本保证 id 有序递增。
  • 不依赖第三方库或者中间件。
  • 算法简单，在内存中进行，效率高。

缺点：

  • 强依赖机器的时钟，如果服务器时钟回拨，会导致重复ID生成

时钟回拨

时钟回拨，就是服务器上的时间突然倒退到之前的时间。

时钟回拨通常是由各种系统时钟同步问题引起的，排除人为原因。
网络中存在许多参与时间同步的设备，例如NTP服务器，它们都需要时钟同步才能保证网络的准确性和可靠性。

时钟回拨一般是由以下四个方面原因引发的：

  1. NTP时间同步。
    网络时间协议（Network Time Protocol）最初是由UNIX系统引入的，现在已经成为一种全球性的时间同步协议。NTP服务器从全球各个原子钟获取准确时间，并将尽可能准确的时间广播给其它设备。但是，如果NTP服务器本身时间同步不准确，或者连接到NTP服务器的路由器或防火墙配置不当，就会导致时钟回拨问题。
  2. 虚拟化技术导致的时钟不同步。
    在虚拟化环境中，虚拟化层和客户机之前经常需要进行时钟同步。然而，由于虚拟机是共享物理服务器的硬件资源，它们在访问真实时间方面存在困难。这种困难可能会导致时钟回拨问题。
  3. 硬件故障导致的时钟不同步。
    磁盘损坏、CPU错误和电源故障等硬件故障都可能导致时钟不同步，从而引发时钟回拨问题。
  4. 操作系统错误。操作系统问题可能会导致时钟回拨问题。

雪花算法如何解决时钟回拨问题？

  1. 百度 UIDGenerator
  2. 美团 Leaf
    • 由于强依赖时钟，对时间的要求比较敏感，在机器工作时NTP同步也会造成秒级别的回退，建议可以直接关闭NTP同步。
    • 要么在时钟回拨的时候直接不提供服务返回ERROR，等时钟追上。
    • 或者做一层重试，回拨时间小的时候，不生成ID，wait等待时间点到达。
  3. 利用拓展位，回拨之后在拓展位上+1，这样依然可以保持ID唯一。但是这个要求我们提前从机器id或者序列号中预留出扩展位。

数据库生成

百度 UidGenerator

美团 Leaf

leaf-segment

leaf-segment方案在使用数据库的基础上，做了如下改变：

  1. 原方案每次获取ID都得读写一次数据库，造成数据库压力大。改为利用proxy server批量获取，每次获取一个segment(step决定大小)号段的值。用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力。
  2. 各个业务不同的发号需求用biz_tag字段来区分，每个biz-tag的ID获取相互隔离，互不影响。如果以后有性能需求需要对数据库扩容，不需要上述描述的复杂的扩容操作，只需要对biz_tag分库分表就行。
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 |
+-------------+--------------+------+-----+-------------------+-----------------------------+

优点：

  1. Leaf服务可以很方便的线性扩展，性能完全能够支撑大多数业务场景。
  2. ID号码是趋势递增的8byte的64位数字，满足上述数据库存储的主键要求。
  3. 容灾性高：Leaf服务内部有号段缓存，即使DB宕机，短时间内Leaf仍能正常对外提供服务。、
  4. 可以自定义max_id的大小，非常方便业务从原有的ID方式上迁移过来。

缺点：

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

双buffer优化

对于第二个缺点，Leaf-segment做了一些优化，简单的说就是：
Leaf 取号段的时机是在号段消耗完的时候进行的，也就意味着号段临界点的ID下发时间取决于下一次从DB取回号段的时间，并且在这期间进来的请求也会因为DB号段没有取回来，导致线程阻塞。如果请求DB的网络和DB的性能稳定，这种情况对系统的影响是不大的，但是假如取DB的时候网络发生抖动，或者DB发生慢查询就会导致整个系统的响应时间变慢。

为此，我们希望DB取号段的过程能够做到无阻塞，不需要在DB取号段的时候阻塞请求线程，即当号段消费到某个点时就异步的把下一个号段加载到内存中。而不需要等到号段用尽的时候才去更新号段。这样做就可以很大程度上的降低系统的TP999指标。

采用双buffer的方式，Leaf服务内部有两个号段缓存区segment。当前号段已下发10%时，如果下一个号段未更新，则另启一个更新线程去更新下一个号段。当前号段全部下发完后，如果下个号段准备好了则切换到下个号段为当前segment接着下发，循环往复。

  • 每个biz-tag都有消费速度监控，通常推荐segment长度设置为服务高峰期发号QPS的600倍（10分钟），这样即使DB宕机，Leaf仍能持续发号10-20分钟不受影响。
  • 每次请求来临时都会判断下个号段的状态，从而更新此号段，所以偶尔的网络抖动不会影响下个号段的更新。

leaf-snowflake

Leaf-segment方案可以生成趋势递增的ID，同时ID号是可计算的，不适用于订单ID生成场景，比如竞对在两天中午12点分别下单，通过订单id号相减就能大致计算出公司一天的订单量，这个是不能忍受的。面对这一问题，我们提供了 Leaf-snowflake方案。

sequence

  1. 支持用户自定义允许时间回拨的范围；
  2. 解决了跨毫秒时起始值从0开始增长的问题；
  3. 解决了高并发场景中获取时间戳性能的问题；

System.currentTimeMillis()的性能问题
单线程下产生延迟说明在系统底层上该线程和其他进程或线程产生了竞争，探究下hotspot中的实现:

1
2
3
4
5
6
jlong os::javaTimeMillis() {
  timeval time;
  int status = gettimeofday(&time, NULL);
  assert(status != -1, "linux error");
  return jlong(time.tv_sec) * 1000  +  jlong(time.tv_usec / 1000);
}

以下是查询得知，涉及到汇编层面了：

  • 调用gettimeofday()需要从用户态切换到内核态；
  • gettimeofday()的表现受系统的计时器（时钟源）影响，在HPET计时器下性能尤其差；
  • 系统只有一个全局时钟源，高并发或频繁访问会造成严重的争用。

既然频繁地从用户态切换到内核态会导致性能问题，那我们能不能减少切换的次数呢？
1ms我们可以调用多次System.currentTimeMillis()，但是如果我们精度是1ms，是不是我们只要让它保证1ms获取一次就可以了，这样还大大的减少了和其他线程抢夺资源的概率，同时也节约了资源。
我们把每1ms获取到的数据保存到内存中，这样我们所有的线程都从内存中取数据。

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
public class SystemClock {

    private final long period;
    private final AtomicLong now;

    private SystemClock(long period) {
        this.period = period;
        this.now = new AtomicLong(System.currentTimeMillis());
        scheduleClockUpdating();
    }

    private static SystemClock instance() {
        return InstanceHolder.INSTANCE;
    }

    public static long now() {
        return instance().currentTimeMillis();
    }

    public static String nowDate() {
        return new Timestamp(instance().currentTimeMillis()).toString();
    }

    private void scheduleClockUpdating() {
        ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor(runnable -> {
            Thread thread = new Thread(runnable, "System Clock");
            thread.setDaemon(true);
            return thread;
        });
        scheduler.scheduleAtFixedRate(() -> now.set(System.currentTimeMillis()), period, period, TimeUnit.MILLISECONDS);
    }

    private long currentTimeMillis() {
        return now.get();
    }

    private static class InstanceHolder {
        // 1ms
        public static final SystemClock INSTANCE = new SystemClock(1);
    }
}

滴滴 tinyid

采用segment号段算法实现，tinyid参考了美团leaf，并对其做了扩展，增加了多db支持和tinyid-client，从而获得了更好的性能和可用性。