乐趣区

关于java:分布式id生成方案总结

jiezi

ID 是数据的惟一标识，传统的做法是利用 UUID 和数据库的自增 ID，在互联网企业中，大部分公司应用的都是 Mysql，并且因为须要事务反对，所以通常会应用 Innodb 存储引擎，UUID 太长以及无序，所以并不适宜在 Innodb 中来作为主键，自增 ID 比拟适合，然而随着公司的业务倒退，数据量将越来越大，须要对数据进行分表，而分表后，每个表中的数据都会按本人的节奏进行自增，很有可能呈现 ID 抵触。这时就须要一个独自的机制来负责生成惟一 ID，生成进去的 ID 也能够叫做 分布式 ID，或 全局 ID。上面来剖析各个生成分布式 ID 的机制。

这篇文章并不会剖析的特地具体，次要是做一些总结，当前再出一些具体某个计划的文章。

数据库自增 ID

第一种计划依然还是基于数据库的自增 ID，须要独自应用一个数据库实例，在这个实例中新建一个独自的表：

表构造如下：

CREATE DATABASE `SEQID`;

CREATE TABLE SEQID.SEQUENCE_ID (id bigint(20) unsigned NOT NULL auto_increment, 
    stub char(10) NOT NULL default '',
    PRIMARY KEY (id),
    UNIQUE KEY stub (stub)
) ENGINE=MyISAM;

能够应用上面的语句生成并获取到一个自增 ID

begin;
replace into SEQUENCE_ID (stub) VALUES ('anyword');
select last_insert_id();
commit;

stub 字段在这里并没有什么非凡的意义，只是为了不便的去插入数据，只有能插入数据能力产生自增 id。而对于插入咱们用的是 replace，replace 会先看是否存在 stub 指定值一样的数据，如果存在则先 delete 再 insert，如果不存在则间接 insert。

这种生成分布式 ID 的机制，须要一个独自的 Mysql 实例，尽管可行，然而基于性能与可靠性来思考的话都不够，业务零碎每次须要一个 ID 时，都须要申请数据库获取，性能低，并且如果此数据库实例下线了，那么将影响所有的业务零碎。

为了解决数据库可靠性问题，咱们能够应用第二种分布式 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，要解决这个问题，可能须要停机才行。

为了解决下面的问题，以及可能进一步提高 DistributIdService 的性能，如果应用第三种生成分布式 ID 机制。

号段模式

咱们能够应用号段的形式来获取自增 ID，号段能够了解成批量获取，比方 DistributIdService 从数据库获取 ID 时，如果能批量获取多个 ID 并缓存在本地的话，那样将大大提供业务利用获取 ID 的效率。

比方 DistributIdService 每次从数据库获取 ID 时，就获取一个号段，比方(1,1000]，这个范畴示意了 1000 个 ID，业务利用在申请 DistributIdService 提供 ID 时，DistributIdService 只须要在本地从 1 开始自增并返回即可，而不须要每次都申请数据库，始终到本地自增到 1000 时，也就是以后号段曾经被用完时，才去数据库从新获取下一号段。

所以，咱们须要对数据库表进行改变，如下：

CREATE TABLE id_generator (id int(10) NOT NULL,
  current_max_id bigint(20) NOT NULL COMMENT '以后最大 id',
  increment_step int(10) NOT NULL COMMENT '号段的长度',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

这个数据库表用来记录自增步长以及以后自增 ID 的最大值（也就是以后曾经被申请的号段的最初一个值），因为自增逻辑被移到 DistributIdService 中去了，所以数据库不须要这部分逻辑了。

这种计划不再强依赖数据库，就算数据库不可用，那么 DistributIdService 也能持续撑持一段时间。然而如果 DistributIdService 重启，会失落一段 ID，导致 ID 空洞。

为了进步 DistributIdService 的高可用，须要做一个集群，业务在申请 DistributIdService 集群获取 ID 时，会随机的抉择某一个 DistributIdService 节点进行获取，对每一个 DistributIdService 节点来说，数据库连贯的是同一个数据库，那么可能会产生多个 DistributIdService 节点同时申请数据库获取号段，那么这个时候须要利用乐观锁来进行管制，比方在数据库表中减少一个 version 字段，在获取号段时应用如下 SQL：

update id_generator set current_max_id=#{newMaxId}, version=version+1 where version = #{version}

因为 newMaxId 是 DistributIdService 中依据 oldMaxId+ 步长算进去的，只有下面的 update 更新胜利了就示意号段获取胜利了。

为了提供数据库层的高可用，须要对数据库应用多主模式进行部署，对于每个数据库来说要保障生成的号段不反复，这就须要利用最开始的思路，再在刚刚的数据库表中减少起始值和步长，比方如果当初是两台 Mysql，那么 mysql1 将生成号段（1,1001]，自增的时候序列为 1，3，5，7…. mysql1 将生成号段（2,1002]，自增的时候序列为 2，4，6，8，10…

更具体的能够参考滴滴开源的 TinyId：github.com/didi/tinyid…

在 TinyId 中还减少了一步来提高效率，在下面的实现中，ID 自增的逻辑是在 DistributIdService 中实现的，而实际上能够把自增的逻辑转移到业务利用本地，这样对于业务利用来说只须要获取号段，每次自增时不再须要申请调用 DistributIdService 了。

雪花算法

下面的三种办法总的来说是基于自增思维的，而接下来就介绍比拟驰名的雪花算法 -snowflake。

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

snowflake 是 twitter 开源的分布式 ID 生成算法，是一种算法，所以它和下面的三种生成分布式 ID 机制不太一样，它不依赖数据库。

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

  • 第一个 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 的利用。

snowflake 算法实现起来并不难，提供一个 github 上用 java 实现的：github.com/beyondfengy…

在大厂里，其实并没有间接应用 snowflake，而是进行了革新，因为 snowflake 算法中最难实际的就是工作机器 id，原始的 snowflake 算法须要人工去为每台机器去指定一个机器 id，并配置在某个中央从而让 snowflake 从此处获取机器 id。

然而在大厂里，机器是很多的，人力老本太大且容易出错，所以大厂对 snowflake 进行了革新。

百度（uid-generator）

github 地址：uid-generator

uid-generator 应用的就是 snowflake，只是在生产机器 id，也叫做 workId 时有所不同。

uid-generator 中的 workId 是由 uid-generator 主动生成的，并且思考到了利用部署在 docker 上的状况，在 uid-generator 中用户能够本人去定义 workId 的生成策略，默认提供的策略是：利用启动时由数据库调配。说的简略一点就是：利用在启动时会往数据库表 (uid-generator 须要新增一个 WORKER_NODE 表) 中去插入一条数据，数据插入胜利后返回的该数据对应的自增惟一 id 就是该机器的 workId，而数据由 host，port 组成。

对于 uid-generator 中的 workId，占用了 22 个 bit 位，工夫占用了 28 个 bit 位，序列化占用了 13 个 bit 位，须要留神的是，和原始的 snowflake 不太一样，工夫的单位是秒，而不是毫秒，workId 也不一样，同一个利用每重启一次就会生产一个 workId。

具体可参考 github.com/baidu/uid-g…

美团（Leaf）

github 地址：Leaf

美团的 Leaf 也是一个分布式 ID 生成框架。它十分全面，即反对号段模式，也反对 snowflake 模式。号段模式这里就不介绍了，和下面的剖析相似。

Leaf 中的 snowflake 模式和原始 snowflake 算法的不同点，也次要在 workId 的生成，Leaf 中 workId 是基于 ZooKeeper 的程序 Id 来生成的，每个利用在应用 Leaf-snowflake 时，在启动时都会都在 Zookeeper 中生成一个程序 Id，相当于一台机器对应一个程序节点，也就是一个 workId。

总结

总得来说，下面两种都是主动生成 workId，以让零碎更加稳固以及缩小人工胜利。

Redis

这里额定再介绍一下应用 Redis 来生成分布式 ID，其实和利用 Mysql 自增 ID 相似，能够利用 Redis 中的 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 的效率是十分高的，然而要思考长久化的问题。Redis 反对 RDB 和 AOF 两种长久化的形式。

RDB 长久化相当于定时打一个快照进行长久化，如果打完快照后，间断自增了几次，还没来得及做下一次快照长久化，这个时候 Redis 挂掉了，重启 Redis 后会呈现 ID 反复。

AOF 长久化相当于对每条写命令进行长久化，如果 Redis 挂掉了，不会呈现 ID 反复的景象，然而会因为 incr 命令过得，导致重启复原数据工夫过长。

退出移动版