高并发下分布式ID生成方案

发布于七月 09, 2019

在我们的开发过程中，只要你是涉及到高并发的领域，那么”怎么为你的系统生成一个高效、可靠、友好的ID”就是你的一个永远绕不开的问题。

本文档部分内容非原创，借鉴了网上的一些资源。涉及出处将在本文的最后部分列出。

一.分布式ID原则

唯一性
高效性
可用性
有序性

此处主要介绍为什么ID生成需要有序性

写性能

在MySQL InnoDB引擎中使用的是聚集索引，
由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
聚簇索引的数据的物理存放顺序与索引顺序是一致的，即：只要索引是相邻的，那么对应的数据一定也是相邻地存放在磁盘上的。
如果主键不是自增id，那么可以想象，它会干些什么，不断地调整数据的物理地址、分页，当然也有其他一些措施来减少这些操作，
但却无法彻底避免。但，如果是自增的，那就简单了，它只需要一页一页地写，索引结构相对紧凑，磁盘碎片少，效率也高。
读性能

来感受下以下两个sql的性能吧，即使created_at字段也有索引：
1.select from table order by created_at
2.select from table order by id
ps: 根据磁盘预读的特性，如果第一次读取“1”，那么如果你是顺序存储，那么“2，3，4，5”也会被读取进内存中。
（当然一般ID就是你的聚簇索引，已经帮你排好序了）

二.实现方案

1. 数据库方案(auto_increment、Ticket Servers)

auto_increment

优点：

1.简单，代码方便，性能可以接受。
2.数字ID天然排序，对分页或者需要排序的结果很有帮助。

缺点：

1.可读性，容易暴露出库信息（今天下个订单，第二天同时间下个订单，其实就可以推测出该系统一天的订单量）。
2.在性能达不到要求的情况下，比较难于扩展。
3.如果遇见多个系统需要合并或者涉及到数据迁移会相当痛苦。
4.在单个数据库或读写分离或一主多从的情况下，只有一个主库可以生成。有单点故障的风险。

优化方案

针对主库单点，如果有多个Master库，则每个Master库设置的起始数字不一样，步长一样，
可以是Master的个数。
比如：
Master1 生成的是 1,4,7,10，
Master2生成的是2,5,8,11
Master3生成的是 3,6,9,12。
这样就可以有效生成集群中的唯一ID，也可以大大降低ID生成数据库操作的负载。但是仔细想想，这样的
方案生成ID的有序性就要靠着路由的极度均衡负载才能给出保证吧。

Flickr Ticket Servers

全局通用库，实现思路(auto_increment + replace into + MyISAM)：

1). 创建64位的自增id：


CREATE TABLE `uid_sequence` (

`id` bigint(20) unsigned NOT NULL auto_increment,

`stub` char(1) NOT NULL default '',

PRIMARY KEY  (`id`),

UNIQUE KEY `stub` (`stub`)

) ENGINE=MyISAM;



SELECT * from uid_sequence：



+-------------------+------+

| id                | stub |

+-------------------+------+

| 72157623227190423 |    a |

2.如果我需要一个全局的唯一的64位uid，则执行：

1 2	REPLACE INTO uid_sequence (stub) VALUES ('a'); SELECT LAST_INSERT_ID();

用 REPLACE INTO 代替 INSERT INTO 的好处是避免表行数太大，还要另外定期清理。
stub 字段要设为唯一索引，这个 sequence 表只有一条纪录，但也可以同时为多张表生成全局主键，
例如 user_ship_id。除非你需要表的主键是连续的，那么就另建一个 user_ship_id_sequence 表。
经过实际对比测试，使用 MyISAM 比 Innodb 有更高的性能。

3.这里flickr使用两台数据库作为自增序列生成，通过这两台机器做主备和负载均衡。

TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1

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

优点：

1.简单，逻辑容易理解。
2.数字ID天然排序，对分页或者需要排序的结果很有帮助。
3.即使为多个服务生成ID，数据也只有一条。
4.即使遇见多个系统(通过同样ID生成器生成)合并，也不会出现冲突。
5.双库生成，没有单点故障的风险。

缺点：

1.可读性，容易暴露出库信息。(当然如果你为多个服务生成ID，则没有该问题)
2.数据库性能瓶颈

2. UUID

常见的方式。一般来说全球唯一。


UUID uuid = UUID.randomUUID();



// 23e15798-f8e6-44f3-90e5-11c43aeb5f36

优点：

1）简单，代码方便。
2）生成ID性能非常好，基本不会有性能问题。
3）全球唯一，在遇见数据迁移，系统数据合并，或者数据库变更等情况下，可以从容应对。

缺点：

1）没有排序，无法保证趋势递增。
2）UUID往往是使用字符串存储，查询的效率比较低。
3）存储空间比较大，如果是海量数据库，就需要考虑存储量的问题。
4）传输数据量大
5）不可读。

优化方案

1.UUID to Int64（解决了不可读、传输数据量大）
2.转成13位长整型（现公司商品库ID方案，这种方案我隐隐觉得在一定量级情况下，会有重复ID问题）


/**

* Generate unique ID from UUID in positive space

*

* @return long value representing UUID

*/

public static Long generateLongUId() {

  long val;

  do {

      final UUID uid = UUID.randomUUID();

      final ByteBuffer buffer = ByteBuffer.wrap(new byte[16]);

      buffer.putLong(uid.getLeastSignificantBits());

      buffer.putLong(uid.getMostSignificantBits());

      final BigInteger bi = new BigInteger(buffer.array());

      val = bi.longValue();

  } while (val < 0);

  return val;

}



/**

* Generate 13 Digits unique ID from UUID in positive space

* @return 13 Digits long value representing UUID

*/

public static Long get13DigitsUId() {

  Long uniqueIdentity = generateLongUId();

  String s = String.valueOf(uniqueIdentity);

  s = s.substring(0, 13);

  return Long.valueOf(s);

}

3. redis生成方案

原理：可以用Redis的原子操作 INCR和INCRBY来实现

优点：

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

缺点：

1）如果系统中没有Redis，还需要引入新的组件，增加系统复杂度。
2）需要编码和配置的工作量比较大。

4. snowflake

信息说明：

1位：暂没有使用，二进制中最高位为1的都是负数，但是我们生成的id一般都使用整数，所以这个最高位固定是0

41位：时间戳数据区，用来记录时间戳（毫秒）
41位可以表示241−1个数字，
如果只用来表示正整数（计算机中正数包含0），可以表示的数值范围是：0 至 241−1，减1是因为可表示的数值范围是从0开始算的，而不是1。
也就是说41位可以表示241−1个毫秒的值，转化成单位年则是(241−1)/(1000∗60∗60∗24∗365)=69年

10位：机器数据区，用来记录工作机器id
可以部署在210=1024个节点，包括 5位datacenterId 和 5位workerId
5位（bit）可以表示的最大正整数是25−1=31，即可以用0、1、2、3、….31这32个数字，来表示不同的datecenterId或workerId

12位：序列号数据区，用来记录同毫秒内产生的不同id
12位（bit）可以表示的最大正整数是212−1=4096，即可以用0、1、2、3、….4095这4096个数字，来表示同一机器同一时间截（毫秒)内产生的4096个ID序号

优点：

1) 所有生成的ID都是按时间趋势递增
2) 整个分布式系统内不会产生重复ID
3) 每个ID中都可以解读出，该ID是在哪个数据中心的哪台工作机器上产生
4) 数值型的分布式ID（替换了UUID）
5) 高性能的ID生成器（超高400w/s的超高性能）(实测：限于代码以及机器性能，实际每秒生成ID在20万。

缺点：

1).在分布式部署的情况下，如果各个机器的时间出现偏离，那么就会出现顺序问题。
2).时间出现回拨，ID生成可能会出现重复。(在代码中的实现会缓存上一次ID生成的时间戳进行比对，避免了重复ID的风险，当然也让ID生成器上抛异常)

三.项目代码

dearnero/nero-snowflake-demo

来源：http://nero.life/2018/08/24/%E9%AB%98%E5%B9%B6%E5%8F%91%E4%B8%8B%E5%88%86%E5%B8%83%E5%BC%8FID%E7%94%9F%E6%88%90%E6%96%B9%E6%A1%88/

搜索此博客

KTSee.eu.org