分布式唯一全局 ID 解决方案之一

发表于 阅读次数： 评论数： 本文字数： 4.7k 阅读时长 ≈ 4 分钟

大纲

1、分布式 ID 简介

1.1、业务背景

在复杂的分布式系统中，往往需要对大量的数据和消息进行唯一标识。比如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中数据日渐增长，对数据分库分表后需要有一个唯一 ID 来标识一条数据或消息。具体一点的如订单、骑手、优惠劵也都需要有唯一标识，此时一个能够生成全局唯一 ID 的系统是非常必要的。

1.2、ID 生成规则的硬性要求

  • 全局唯一：不能出现重复的 ID ，既然是唯一标识，这是最基本的要求
  • 单调递增：保证下一个 ID 大于上一个 ID，例如事务版本号、IM 增量信息、排序等特殊需求
  • 趋势递增：在 MySQL 的 InnoDB 存储引擎中使用的是聚集索引，由于多数 RDBMS 使用 BTree 的数据结构来存储索引数据，在主键的选择上面应该尽量使用有序的主键来保证写入性能
  • 信息安全：如果 ID 是连续的，恶意用户的爬取工作就非常容易做了，直接按照顺序下载指定 URL 即可 所以在一些应用场景下，需要 ID 无规则或者不规则，让竞争对手不好猜

上述的全局唯一、单调递增、趋势递增需求分别对应三类不同的业务场景，但单调递增和信息安全这两个需求是互斥的，无法使用同一个方案满足

1.3、ID 生成系统的可用性要求

  • 低延迟：发一个获取分布式 ID 的请求，服务器就要快，极速
  • 高可用：一个获取分布式 ID 的请求，服务器就要在保证 99.999% 成功率的情况下创建一个唯一分布式 ID
  • 高 QPS：假如并发一堆创建分布式 ID 的请求同时杀过来，服务器要顶得住且一下子成功创建 10 万个唯一分布式 ID

2、UUID 生成 ID

2.1、概述

UUID 按照 OSF 制定的标准计算，用到了以太网卡地址、纳秒级时间、芯片 ID 码和许多可能的数字，并由以下几部分的组成：当前日期和时间、时钟序列、全局唯一的 IEEE 机器识别号。UUID 的标准形式包含 32 个 16 进制的数字，以连字号分为 5 段，形式为 cb6ce510-74fe-4e18-ac3d-05a5c96d3a0f 的 36 个字符。特别注意，基于 MAC 地址生成 UUID 的算法可能会造成 MAC 地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。

2.2、优缺点

  • 优点：性能高，本地生成，没有网络消耗。如果只考虑唯一性，那么可以使用
  • 缺点：无序，长度较长，入库性能差，作为数据库主键时，会导致索引效率下降，空间占用较多
  • 适用场景：只要对存储空间没有苛刻要求的都能够适用，比如各种链路追踪、日志存储等

为什么无序的 UUID 会导致入库性能变差？

  • 无序：即无法预测 ID 的生成顺序，不能生成递增的有序数字
  • ID 长度过长：分布式 ID 一般都是作为主键，但是 MySQL 官方推荐主键尽量越短越好，36 个字符长度的 UUID 不是很推荐
  • B+ 树索引分裂：既然分布式 ID 是主键，然后主键是包含索引的，MySQL 的索引是通过 B+ 树来实现的，每一次新的 UUID 数据的插入，为了查询的优化，都会对索引的底层 B+ 树进行修改。因为 UUID 数据是无序的，所以每一次 UUID 的数据插入都会对主键底层的 B+ 树进行很大的修改，这一点非常不好。插入的 ID 完全无序，不但会导致一些中间节点产生分裂，也会白白的创造出很多的不饱和节点，这样大大的降低了数据库的插入性能

3、数据库自增 ID

3.1、概述

在分布式应用里，数据库的自增 ID 机制的主要原理是使用：MySQL 数据库自增 ID 和 replace into 来实现的。利用给字段设置 auto_increment 和 auto_increment_offset 来保证 ID 自增，每次业务使用下列 SQL 读写 MySQL 得到 ID。

mysql-replace-into

这里的 replace into 跟 insert 功能类似，不同点在于 replace into 首先会尝试插入数据到表中，如果发现表中已经有此行数据（根据主键或者唯一索引判断），则先删除旧数据，否则直接插入新数据

3.2、优缺点

优点：

  • 非常简单，利用现有数据库系统的功能实现，成本小
  • ID 单调自增，可以实现一些对 ID 有特殊要求的业务

缺点：

  • 生成的是单调递增的 ID，同时 ID 是可计算的，不适用于订单 ID 生成场景，否则竞争对手很从容易猜到
  • 分库分表后，同一数据表的自增 ID 容易重复，无法直接使用（可以设置自增步长，但局限性很明显）
  • 强依赖数据库，当数据库异常时整个系统不可用，属于致命问题。配置主从复制可以尽可能的增加可用性，但是数据一致性在特殊情况下难以保证，主从切换时的不一致可能会导致重复生成 ID
  • 生成 ID 的性能瓶颈限制在单台 MySQL 的读写性能，如果设计一个单独的数据库来实现分布式应用的数据唯一性，即使使用预生成方案，也会因为事务锁的问题，高并发场景容易出现单点瓶颈

适用场景：

  • 单数据库实例的表 ID（包含主从同步场景），部分按天计数的流水号等，不适用于分库分表场景、全局唯一 ID 场景

数据库的自增 ID 机制为什么不适合作为分布式 ID？

  • 在高并发的场景下，数据库压力还是很大，每次获取 ID 都得读写一次数据库，非常影响性能，不符合分布式 ID 里面的低延迟和高 QPS 的规则
  • 系统水平扩展比较困难，为了提高 MySQL 的性能，如果要增加 MySQL 数据库该怎么做？

3.3、MySQL 集群场景

在分布式系统中可以多部署几台机器，每台机器设置不同的初始值，且自增步长和机器数相等。比如有 2 台机器，设置自增步长为 2，TicketServer1 的初始值为 1（1，3，5，7，9，11 …）、TicketServer2 的初始值为 2（2，4，6，8，10 …）。如下所示，分别设置两台机器对应的参数，TicketServer1 从 1 开始生成 ID ，TicketServer2 从 2 开始生成 ID ，两台机器每次生成 ID 之后都递增 2。

1
2
3
4
5
6
7
TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1

TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2

假设要部署 N 台机器，自增步长需设置为 N，每台的初始值依次为 0，1，2 … N-1，那么整个架构就变成了如下图所示：

global-unique-id-mysql

这种架构貌似能够满足性能的需求，但有以下几个缺点：

  • 数据库压力还是很大，每次获取 ID 都得读写一次数据库，只能靠堆机器来提高性能
  • ID 没有了单调递增的特性，只能趋势递增，这个缺点对于一般业务需求不是很重要，可以容忍
  • 系统水平扩展比较困难，比如定义好了自增步长和机器台数之后，如果要添加机器该怎么做？假设现在只有一台机器生成 ID 是 1，2，3，4，5（自增步长是 1），这个时候需要扩容机器一台。可以这样做：把第二台机器的初始值设置得比第一台超过很多，比如 14（假设在扩容时间之内第一台不可能发到 14），同时设置自增步长为 2，那么这台机器下发的号码都是 14 以后的偶数。然后摘掉第一台，把 ID 值保留为奇数，比如 7，然后修改第一台的自增步长为 2。让它符合我们定义的号段标准，对于这个例子来说就是让第一台以后只能产生奇数。扩容方案看起来复杂吗？貌似还好，现在想象一下如果线上有 100 台机器，这个时候要扩容该怎么做？简直是噩梦，所以系统水平扩展方案复杂难以实现。

4、基于 Redis 生成全局 ID 策略

4.1、概述

因为 Redis 是单线程的，天生保证了原子性，可以使用原子操作 INCR 和 INCRBY 来生成分布式唯一 ID

4.2、优缺点

优点：

  • 整体吞吐量比数据库方案要高

缺点：

  • Redis 实例或集群宕机后，找回最新的 ID 值有点困难
  • Redis 单机环境下，存在单点故障问题，导致 ID 生成服务不可用
  • 生成的是单调递增的 ID，同时 ID 是可计算的，不适用于订单 ID 生成场景，否则竞争对手很从容易猜到

适用场景：

  • 比较适合计数场景，如用户访问量，订单流水号（日期 + 流水号）等

4.3、Redis 集群场景

通过 Redis 集群来生成唯一 ID 时，需要设置相同的自增步长，且自增步长等于节点数，同时 Key 要求设置相同的有效期，以此来获得更高的吞吐量。假设一个集群中有 5 台 Redis，此时可以初始化每台 Redis 的值分别是 1，2，3，4，5，然后自增步长都是 5，那么各个 Redis 生成的 ID 为：

  • A：1，6，11，16，21
  • B：2，7，12，17，22
  • C：3，8，13，18，23
  • D：4，9，14，19，24
  • E：5，10，15，20，25

这种方式最大的缺点是复杂性太高，需要严重依赖第三方服务，集群管理繁琐，而且代码配置繁琐。一般来说，越是复杂的方案，越不可靠。

5、SnowFlake（雪花算法）

5.1、概述

SnowFlake 算法来源于 Twitter，使用 Scala 语言实现，利用 Thrift 框架实现 RPC 接口调用，最初的项目起因是数据库从 MySQL 迁移到 Cassandra，而 Cassandra 没有现成可用的 ID 生成机制，就催生了该算法。SnowFlake 的特性如下：

  • SnowFlake 生成 ID 能够按照时间有序生成
  • 经测试 SnowFlake 每秒能够产生 26 万个自增可排序 ID
  • 分布式系统内不会产生 ID 碰撞（由 datacenter 和 workerId 做区分），并且生成效率较高
  • SnowFlake 算法生成 ID 的结果是一个 64 bit 大小的整数，刚好为一个 Long 型，转换成字符串后长度最多是 19

5.2、结构

SnowFlake 算法的特性是有序、全局唯一、高性能、低延迟（响应时间在 2ms 以内），可在分布式环境（多集群，跨机房）下使用，因此使用 SnowFlake 算法得到的 ID 是分段组成的：

  • 与指定日期的时间差（毫秒级），41 位，够用 69 年
  • 集群 ID + 机器 ID，一共 10 位，包括 5 位 datacenterId 和 5 位 workerId，最多支持 1024 台机器
  • 序列号，12 位，每台机器每毫秒内最多产生 4096 个序列号

snowflake-1

  • 1bit：符号位，固定是 0，表示全部 ID 都是正整数
  • 41bit：时间戳（毫秒数时间差），从指定的日期算起，够用 69 年，用 Long 类型表示的时间戳是从 1970-01-01 00:00:00 开始算起的
  • 10bit：机器 ID，有异地部署，多集群的也可以配置，需要线下规划好各地机房，各集群，各实例 ID 的编号
  • 12bit：序列号，前面都相同的话，最多可以支持到 4096 个

5.3、优缺点

优点：

  • 可以根据自身业务特性分配 bit 位，非常灵活
  • 毫秒数在高位，自增序列在低位，整个 ID 都是趋势递增的
  • 不依赖数据库等三方系统，以服务的方式部署，稳定性更高，生成 ID 的效率也是非常高，低延迟

缺点：

  • 强依赖机器时钟，如果机器的时钟回拨了，会导致生成重复的 ID
  • 若生成环境中使用了容器化技术，实例的个数随时有变化，那么 SnowFlake 需要一定的改造才能更好地应用到生产环境中
  • 在单机上是递增的，但是由于涉及到分布式环境，每台机器上的时钟不可能完全同步（如时钟回拨），有时候可能会出现不是全局递增的情况（此缺点可认为无所谓，一般分布式 ID 只是要求趋势递增，并不会严格要求递增，90% 的业务需求都只需要趋势递增）

适用场景：

  • 分布式应用环境的数据主键

5.4、Java 版实现

Java 版的代码实现来自这里，在企业的项目开发中，一般可以直接使用封装好 SnowFlake 算法的 Java 工具库（如 Hutools 工具库），不再需要自己实现一遍，完整的代码如下：

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/**
 * twitter的snowflake算法 -- java实现
 *
 * @author beyond
 * @date 2016/11/26
 */
public class SnowFlake {

    /**
     * 起始的时间戳
     */
    private final static long START_STMP = 1480166465631L;

    /**
     * 每一部分占用的位数
     */
    private final static long SEQUENCE_BIT = 12; //序列号占用的位数
    private final static long MACHINE_BIT = 5;   //机器标识占用的位数
    private final static long DATACENTER_BIT = 5;//数据中心占用的位数

    /**
     * 每一部分的最大值
     */
    private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);

    /**
     * 每一部分向左的位移
     */
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;

    private long datacenterId;  //数据中心
    private long machineId;     //机器标识
    private long sequence = 0L; //序列号
    private long lastStmp = -1L;//上一次时间戳

    public SnowFlake(long datacenterId, long machineId) {
        if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
            throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
        }
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0");
        }
        this.datacenterId = datacenterId;
        this.machineId = machineId;
    }

    /**
     * 产生下一个ID
     *
     * @return
     */
    public synchronized long nextId() {
        long currStmp = getNewstmp();
        if (currStmp < lastStmp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }

        if (currStmp == lastStmp) {
            //相同毫秒内，序列号自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //同一毫秒的序列数已经达到最大
            if (sequence == 0L) {
                currStmp = getNextMill();
            }
        } else {
            //不同毫秒内，序列号置为0
            sequence = 0L;
        }

        lastStmp = currStmp;

        return (currStmp - START_STMP) << TIMESTMP_LEFT //时间戳部分
                | datacenterId << DATACENTER_LEFT       //数据中心部分
                | machineId << MACHINE_LEFT             //机器标识部分
                | sequence;                             //序列号部分
    }

    private long getNextMill() {
        long mill = getNewstmp();
        while (mill <= lastStmp) {
            mill = getNewstmp();
        }
        return mill;
    }

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

    public static void main(String[] args) {
        SnowFlake snowFlake = new SnowFlake(2, 3);

        for (int i = 0; i < (1 << 12); i++) {
            System.out.println(snowFlake.nextId());
        }

    }
}

上面的代码基本上通过位移操作，将每段含义的数值，移到相应的位置上。如机器 ID 这里由数据中心 + 机器标识组成，所以，机器标识向左移 12 位，就是它的位置，数据中心的编号向左移 17 位，时间戳的值向左移 22 位，每部分占据自己的位置，各不干涉，由此组成一个完整的 ID 值。

了解 SnowFlake 的基本实现原理，可以通过提前规划好机器标识来实现，但目前的分布式生产环境，借用了多种云计算、容器化技术，实例的个数随时有变化，而且还需要处理服务器实例的时钟回拨问题，固定规划 ID 然后通过配置来使用 SnowFlake 的场景可行性不高。一般是自动启停，增减机器，这样就需要对 SnowFlake 进行一些改造才能更好地应用到生产环境中。