分布式系统中的唯一ID生成策略

本文参考资源:

大型互联网公司分布式ID方案总结 - 悟能之能 - 博客园

Java技术 | 细谈Java中UUID的简单了解与使用 - 林深时觉寒 - 博客园

在应用程序中,经常需要全局唯一的ID作为数据库主键。分库分表后,每个表中的数据都会按自己的节奏进行自增,很有可能出现ID冲突。这时就需要一个单独的机制来负责生成唯一ID,生成出来的ID也可以叫做分布式ID,或全局ID。

UUID

UUID 是通用唯一识别码(Universally Unique Identifier)的缩写,其目的,是让分布式系统中的所有元素,都能有唯一的辨识信息,UUID的标准格式:

xxxxxxxx-xxxx-Axxx-Bxxx-xxxxxxxxxxxx

它是由32个16进制数字所构成,理论上的总数为16^32 = 2^128,若每纳秒产生1兆个UUID,要花100亿年才会将所有UUID用完。

  • A那个位置,代表版本号,由于UUID的标准实现有5个版本,所以只会是1,2,3,4,5
    • 1: 基于时间戳、机器MAC地址生成。由于使用MAC地址,可以保证全球范围的唯一性。
    • 2: 只基于时间戳,不常用。
    • 3: 基于namespace和一个自定义字符串,不常用。
    • 4: 只基于随机数,最常用,但不推荐,重复几率不太能让人接受。
    • 5: 只基于namespace,不常用。
  • B那个位置,只会是8,9,a,b

java中可以在java.util包下找到UUID相关的实现:

UUID.randomUUID()

它产生的UUID形式类似于:6edd24a3-a863-4f59-9231-fbe900ebbdcb。可见java使用的UUID实现是版本4,只基于随机数,虽然重复概率很低,但没有可靠的措施来保证不重复。

UUID通常用作标识分布式系统中的某个资源,如果用作主键会有以下问题:

  • 不是数字类型,并且数据长度大,占用空间
  • 完全随机,没有递增规律

数据库多主自增id

如果我们两个数据库组成一个主从模式集群,正常情况下可以解决数据库可靠性问题,但是如果主库挂掉后,数据没有及时同步到从库,这个时候会出现ID重复的现象。我们可以使用双主模式集群,也就是两个Mysql实例都能单独的生产自增ID,这样能够提高效率,但是如果不经过其他改造的话,这两个Mysql实例很可能会生成同样的ID。需要单独给每个Mysql实例配置不同的起始值和自增步长。

第一台Mysql实例配置:

set @@auto_increment_offset = 1;     -- 起始值
set @@auto_increment_increment = 2;  -- 步长

第二台Mysql实例配置:

set @@auto_increment_offset = 2;     -- 起始值
set @@auto_increment_increment = 2;  -- 步长

经过上面的配置后,这两个Mysql实例生成的id序列如下:

  • mysql1,起始值为1,步长为2,ID生成的序列为:1,3,5,7,9,...
  • mysql2,起始值为2,步长为2,ID生成的序列为:2,4,6,8,10,...

对于这种生成分布式ID的方案,需要单独新增一个生成分布式ID应用,比如DistributIdService,该应用提供一个接口供业务应用获取ID,业务应用需要一个ID时,通过rpc的方式请求DistributIdService,DistributIdService随机去上面的两个Mysql实例中去获取ID。

实行这种方案后,就算其中某一台Mysql实例下线了,也不会影响DistributIdService,DistributIdService仍然可以利用另外一台Mysql来生成ID。

但是这种方案的扩展性不太好,如果两台Mysql实例不够用,需要新增Mysql实例来提高性能时,这时就会比较麻烦。

现在如果要新增一个实例mysql3,要怎么操作呢?

第一,mysql1、mysql2的步长肯定都要修改为3,而且只能是人工去修改,这是需要时间的。
第二,因为mysql1和mysql2是不停在自增的,对于mysql3的起始值我们可能要定得大一点,以给充分的时间去修改mysql1,mysql2的步长。
第三,在修改步长的时候很可能会出现重复ID,要解决这个问题,可能需要停机才行。

Zookeeper/Redis

Zookeeper

之前在Zookeeper应用场景和各种分布式锁的实现 中提到,可以利用zookeeper提供命名服务,即全局唯一的ID,并且可以保证ID的递增性。

无论是数据库/Zookeeper,实现唯一ID的原理都是把所有 ID 集中放在一个地方进行管理,对每个 ID 序列独立管理,每台机器上使用 ID 时就从这个 ID 生成器中取。但也都会导致性能问题:每次都远程取 ID 会有资源损耗。一种改进方案是一次取一段 ID,然后缓存在本地,这样就不需要每次都去远程的生成器上取 ID 了。但是也会带来问题,如果应用取了一段 ID,正在用时完全宕机了,那么一些 ID 号就浪费不可用了。

Redis

redis产生自增ID就是使用了incr命令:

127.0.0.1:6379> set seq_id 1     // 初始化自增ID为1
OK
127.0.0.1:6379> incr seq_id      // 增加1,并返回
(integer) 2
127.0.0.1:6379> incr seq_id      // 增加1,并返回
(integer) 3

从redis获取id的效率较高,但要考虑持久化的问题。

雪花算法

我们可以换个角度来对分布式ID进行思考,只要能让负责生成分布式ID的每台机器在每毫秒内生成不一样的ID就行了。

snowflake是twitter开源的分布式ID生成算法,是一种算法,可以在机器本地生成,效率很高。

核心思想是:分布式ID固定是一个long型的数字,一个long型占8个字节,也就是64个bit,原始snowflake算法中对于bit的分配如下图:

分布式系统中的唯一ID生成策略
  • 第一个bit位是标识部分,在java中由于long的最高位是符号位,正数是0,负数是1,一般生成的ID为正数,所以固定为0。
  • 时间戳部分占41bit,这个是毫秒级的时间,一般实现上不会存储当前的时间戳,而是时间戳的差值(当前时间-固定的开始时间),这样可以使产生的ID从更小值开始;41位的时间戳可以使用69年,(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年
  • 工作机器id占10bit,这里比较灵活,比如,可以使用前5位作为数据中心机房标识,后5位作为单机房机器标识,可以部署1024个节点。
  • 序列号部分占12bit,支持同一毫秒内同一个节点可以生成4096个ID

根据这个算法的逻辑,只需要将这个算法用Java语言实现出来,封装为一个工具方法,那么各个业务应用可以直接使用该工具方法来获取分布式ID,只需保证每个业务应用有自己的工作机器id即可,而不需要单独去搭建一个获取分布式ID的应用。

由于工作机器的id较难管理,也需要不能重复,又可以变成UUID的问题,可以使用Zookeeper/Redis等技术来生成。

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%88%86%e5%b8%83%e5%bc%8f%e7%b3%bb%e7%bb%9f%e4%b8%ad%e7%9a%84%e5%94%af%e4%b8%80id%e7%94%9f%e6%88%90%e7%ad%96%e7%95%a5/