分布式全局唯一ID生成策略

为什么分布式系统需要用到ID生成系统

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

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

ID生成系统的需求

1.全局唯一性：不能出现重复的ID，最基本的要求。
2.趋势递增：MySQL InnoDB引擎使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应尽量使用有序的主键保证写入性能。
3.单调递增：保证下一个ID一定大于上一个ID。
4.信息安全：如果ID是连续递增的，恶意用户就可以很容易的窥见订单号的规则，从而猜出下一个订单号，如果是竞争对手，就可以直接知道我们一天的订单量。所以在某些场景下，需要ID无规则。

第3、4两个需求是互斥的，无法同时满足。

同时，在大型分布式网站架构中，除了需要满足ID生成自身的需求外，还需要ID生成系统可用性极高。想象以下，如果ID生成系统瘫痪，那么整个业务无法进行下去，那将是一次灾难。
因此，总结ID生成系统还需要满足如下的需求：

1.高可用，可用性达到5个9或4个9。
2.高QPS，性能不能太差，否则容易造成线程堵塞。
3.平均延迟和TP999(保证99.9%的请求都能成功的最低延迟)延迟都要尽可能低。

ID生成系统的类型

1、UUID

UUID是指在一台机器在同一时间中生成的数字在所有机器中都是唯一的。按照开放软件基金会(OSF)制定的标准计算，用到了以太网卡地址、纳秒级时间、芯片ID码和许多可能的数字.

UUID由以下几部分的组合：

（1）当前日期和时间。
（2）时钟序列。
（3）全局唯一的IEEE机器识别号，如果有网卡，从网卡MAC地址获得，没有网卡以其他方式获得。

标准的UUID格式为：xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx (8-4-4-4-12)，以连字号分为五段形式的36个字符，示例：550e8400-e29b-41d4-a716-446655440000 Java标准类库中已经提供了UUID的API。

UUID.randomUUID()

优点

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

缺点

不易存储：UUID太长，16字节128位，通常以36长度的字符串表示，很多场景不适用。
信息不安全：基于MAC地址生成UUID的算法可能会造成MAC地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。
ID作为主键时在特定的环境会存在一些问题，比如做DB主键的场景下，UUID就非常不适用。

2、SnowFlake雪花算法

雪花ID生成的是一个64位的二进制正整数，然后转换成10进制的数。64位二进制数由如下部分组成：

1位标识符：始终是0，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0。
41位时间戳：41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截 )得到的值，这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的。
10位机器标识码：可以部署在1024个节点，如果机器分机房（IDC）部署，这10位可以由 5位机房ID + 5位机器ID 组成。
12位序列：毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号

优点

简单高效，生成速度快。
时间戳在高位，自增序列在低位，整个ID是趋势递增的，按照时间有序递增。
灵活度高，可以根据业务需求，调整bit位的划分，满足不同的需求。

缺点

依赖机器的时钟，如果服务器时钟回拨，会导致重复ID生成。
在分布式环境上，每个服务器的时钟不可能完全同步，有时会出现不是全局递增的情况。
在多进程的情况下，需要指定不同进程的操作数，当集群达到一定程度，只有10位的机房ID和5位的机器ID将不够用。

工具类：Java版本实现SnowflakeIdUtil雪花算法

3、数据库自增ID机制

主要思路是采用数据库自增ID + replace_into实现唯一ID的获取。

create table t_global_id(
    id bigint(20) unsigned not null auto_increment,
    stub char(1) not null default '',
    primary key (id),
    unique key stub (stub)
) engine=MyISAM;

每次业务可以使用以下SQL读写MySQL得到ID号

replace into t_golbal_id(stub) values('a');
select last_insert_id();

replace into跟insert功能类似，不同点在于：replace into首先尝试插入数据列表中，如果发现表中已经有此行数据（根据主键或唯一索引判断）则先删除，再插入。否则直接插入新数据。
当然为了避免数据库的单点故障，最少需要两个数据库实例，通过区分auto_increment的起始值和步长来生成奇偶数的ID。如下：

Server1：
auto-increment-increment = 2
auto-increment-offset = 1
Server2：
auto-increment-increment = 2
auto-increment-offset = 2

优点

简单。充分借助数据库的自增ID机制，可靠性高，生成有序的ID。

缺点

ID生成依赖数据库单机的读写性能。
依赖数据库，当数据库异常时整个系统不可用。

对于MySQL的性能问题，可以用如下方案解决

在分布式环境中，我们可以部署N台数据库实例，每台设置成不同的初始值，自增步长为机器的台数。每台的初始值分别为1,2,3…N，步长为N。

以上方案虽然解决了性能问题，但是也存在很大的局限性：

系统水平扩容困难：系统定义好步长之后，增加机器之后调整步长困难。如果要添加机器怎么办？假设现在只有一台机器发号是1,2,3,4,5（步长是1），这个时候需要扩容机器一台。可以这样做：把第二台机器的初始值设置得比第一台超过很多，比如14（假设在扩容时间之内第一台不可能发到14），同时设置步长为2，那么这台机器下发的号码都是14以后的偶数。然后摘掉第一台，把ID值保留为奇数，比如7，然后修改第一台的步长为2。让它符合我们定义的号段标准，对于这个例子来说就是让第一台以后只能产生奇数。扩容方案看起来复杂吗？貌似还好，现在想象一下如果我们线上有100台机器，这个时候要扩容该怎么做？简直是噩梦。
数据库压力大：每次获取一个ID都必须读写一次数据库。当然对于这种问题，也有相应的解决方案，就是每次获取ID时都批量获取一个区间的号段到内存中，用完之后再来获取。数据库的性能提高了几个量级。

4、第三方软件生成（Redis）

Redis实现了一个原子操作INCR和INCRBY实现递增的操作。当使用数据库性能不够时，可以采用Redis来代替，同时使用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

优点

不依赖于数据库，灵活方便，且性能优于数据库。
数字ID天然排序，对分页或者需要排序的结果很有帮助。

缺点：

如果系统中没有Redis，还需要引入新的组件，增加系统复杂度。
需要编码和配置的工作量比较大。这个都不是最大的问题。

关于分布式全局唯一ID的生成，各个互联网公司有很多实现方案，比如美团点评的Leaf-snowflake，用zookeeper解决了各个服务器时钟回拨的问题，弱依赖zookeeper。以及Leaf-segment类似上面数据库批量ID获取的方案。

我的另一篇文章：论数据库设计选择一个有序的ID的方法和重要性

链接：https://www.jianshu.com/p/9d7ebe37215e