十种分布式ID生成方法
什么是分布式ID
以MySQL为例,数据量不大的时候,单库单表可以支撑现有业务,再大一点主从同步读写分离也可以。
但数据是不断增加的,当主从同步也不行了,就需要分库分表了。分库分表需要一个全局唯一ID做标识,这就是分布式ID。一个能生成分布式ID的系统是十分有必要的。
分布式ID特点
- 全局唯一:基本要求
- 高性能:高可用低延时,ID生成相应快,否则成为业务瓶颈;
- 高可用:不能有单点故障
- 好接入:在系统设计和实现上尽可能地简单;
- 趋势递增:在MySQL InnoDB引擎中使用的是聚集索引,由于多数RDBMS使用B-tree的数据结构来存储索引数据,我们应该尽量使用有序的主键保证写入性能;
- 单调递增:保证下一个ID一定大于上一个ID,例如事务版本号、IM增量消息、排序。
- 信息安全:在一些应用场景下,会需要ID无规则、不规则生成,例如订单号。
- 分片支持:可以控制ShardingId。比如某一个用户的文章要放在同一个分片内,这样查询效率高,修改也容易。
- 长度适中
生成方式
- UUID
- 数据库自增ID
- 数据库多主模式
- 数据库号段模式
- Redis
- 雪花算法(SnowFlake)
- 滴滴出品(TinyID)
- 百度(Uidgenerator)
- 美团(Leaf)
- zookeeper
1.UUID
UUID uuid=UUID.randomUUID();
UUID的标准形式包含32个16进制数字,以连字号分为五段,形式为8-4-4-4-12的36个字符,示例:550e8400-e29b-41d4-a716-446655440000。这种ID每个都是独一无二的,不用担心冲突问题。
优点:
- 生成简单,本地生成无网络消耗,有唯一性
缺点:
- 无序字符串,不具备趋势递增的特性;
- 没有具体含义;
- 长度过长对MySQL性能消耗较大;
- 基于MAC地址生成的UUID可能造成MAC地址泄露
2.数据库自增ID
基于数据库的auto_increment自增ID完全可以充当分布式ID,需要一个单独的MySQL实例用来生成ID,建表结构如下:
CREATE DATABASE `SEQ_ID`;
CREATE TABLE SEQID.SEQUENCE_ID (
id bigint(20) unsigned NOT NULL auto_increment,
value char(10) NOT NULL default '',
PRIMARY KEY (id),
) ENGINE=MyISAM;
insert into SEQUENCE_ID(value) VALUES ('values');
当我们需要一个ID的时候,向表中插入一条记录返回主键ID
优点:
- 简单,利用数据库系统功能实现,成本小,有DBA专业维护
- ID号单调递增
缺点:
- 太依赖DB,当DB异常时整个系统不可用,属于致命问题。
- 配置主从复制可以尽可能的增加可用性,但是数据一致性在特殊情况下难以保证。主从切换时的不一致可能会导致重复发号。
- ID发号性能瓶颈限制在单台MySQL的读写性能
- 访问量激增时MySQL本身就是系统的瓶颈,用它来实现分布式服务风险比较大
3.数据库多主模式
对上边的方式做一些高可用优化,换成主从模式集群。再增加多几个Mysql实例,那就是多主模式集群了。
设置起始值和自增步长来解决重复ID的问题,例如:
MySQL_1起始值为1,步长为2,生成ID:1,3,5…
MySQL_2起始值为2,步长为2,生成ID:2,4,6…
当添加多一个MySQL_3时,起始值为3,步长统一改为3,那么就是
1,4,7…
2,5,8…
3,6,9…
优点:解决DB单点问题
缺点:不利于后续扩容,而且实际上单个数据库自身压力还是大,依旧无法满足高并发场景
4.数据库号段模式
从数据库批量的获取自增ID,每次从数据库取出一个号段范围,例如 (1,1000] 代表1000个ID,具体的业务服务将本号段,生成1~1000的自增ID并加载到内存。表结构如下:
CREATE TABLE id_generator (
id int(10) NOT NULL,
max_id bigint(20) NOT NULL COMMENT '当前最大id',
step int(20) NOT NULL COMMENT '号段的长度',
biz_type int(20) NOT NULL COMMENT '业务类型',
version int(20) NOT NULL COMMENT '版本号',
PRIMARY KEY (`id`)
)
不是很依赖于数据库,不会频繁的访问数据库,对数据库的压力小很多。
5.Redis
当使用数据库来生成ID性能不够要求的时候,我们可以尝试使用Redis来生成ID。这主要依赖于Redis是单线程的,所以也可以用生成全局唯一的ID。可以用Redis的原子操作 INCR和INCRBY来实现。
比较适合使用Redis来生成日切流水号。比如订单号=日期+当日自增长号。可以每天在Redis中生成一个Key,使用INCR进行累加。
127.0.0.1:6379> set seq_id 1 // 初始化自增ID为1
OK
127.0.0.1:6379> incr seq_id // 增加1,并返回递增后的数值
(integer) 2
用redis实现需要注意一点,要考虑到redis持久化的问题。redis有两种持久化方式RDB和AOF:
- RDB会定时打一个快照进行持久化,假如连续自增但redis没及时持久化,而这会Redis挂掉了,重启Redis后会出现ID重复的情况。
- AOF会对每条写命令进行持久化,即使Redis挂掉了也不会出现ID重复的情况,但由于incr命令的特殊性,会导致Redis重启恢复的数据时间过长。
优点:
- 不依赖于数据库,灵活方便,且性能优于数据库
- 数字ID天然排序,对分页或者需要排序的结果很有帮助
缺点:
- 如果系统中没有Redis,还需要引入新的组件,增加系统复杂度
- 需要编码和配置的工作量比较大
- Redis单点故障,影响序列服务的可用性
6.雪花算法(SnowFlake)
是twitter公司内部分布式项目采用的ID生成算法,开源后广受国内大厂的好评,在该算法影响下各大公司相继开发出各具特色的分布式生成器。
组成结构:正数位(占1比特)+ 时间戳(占41比特)+ 机器ID(占5比特)+ 数据中心(占5比特)+ 自增值(占12比特),总共64比特组成的一个Long类型。
- 第一个bit位(1bit):Java中long的最高位是符号位代表正负,正数是0,负数是1,一般生成ID都为正数,所以默认为0。
- 时间戳部分(41bit):毫秒级的时间,不建议存当前时间戳,而是用(当前时间戳 -固定开始时间戳)的差值,可以使产生的ID从更小的值开始;
- 工作机器id(10bit):也被叫做workId,这个可以灵活配置,机房或者机器号组合都可以。
- ***部分(12bit),自增值支持同一毫秒内同一个节点可以生成4096个ID
根据这个算法的逻辑,只需要将这个算法用Java语言实现出来,封装为一个工具方法,那么各个业务应用可以直接使用该工具方法来获取分布式ID,只需保证每个业务应用有自己的工作机器id即可,而不需要单独去搭建一个获取分布式ID的应用。
/**
* Twitter的SnowFlake算法,使用SnowFlake算法生成一个整数,然后转化为62进制变成一个短地址URL
*
* https://github.com/beyondfengyu/SnowFlake
*/
public class SnowFlakeShortUrl {
//起始的时间戳
private final static long START_TIMESTAMP = 1480166465631L;
//每一部分占用的位数
private final static long SEQUENCE_BIT = 12; //***占用的位数
private final static long MACHINE_BIT = 5; //机器标识占用的位数
private final static long DATA_CENTER_BIT = 5; //数据中心占用的位数
//每一部分的最大值
private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
private final static long MAX_DATA_CENTER_NUM = -1L ^ (-1L << DATA_CENTER_BIT);
//每一部分向左的位移
private final static long MACHINE_LEFT = SEQUENCE_BIT;
private final static long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
private final static long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT;
private long dataCenterId; //数据中心
private long machineId; //机器标识
private long sequence = 0L; //***
private long lastTimeStamp = -1L; //上一次时间戳
private long getNextMill() {
long mill = getNewTimeStamp();
while (mill <= lastTimeStamp) {
mill = getNewTimeStamp();
}
return mill;
}
private long getNewTimeStamp() {
return System.currentTimeMillis();
}
/**
* 根据指定的数据中心ID和机器标志ID生成指定的***
*
* @param dataCenterId 数据中心ID
* @param machineId 机器标志ID
*/
public SnowFlakeShortUrl(long dataCenterId, long machineId) {
if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) {
throw new IllegalArgumentException("DtaCenterId can't be greater than MAX_DATA_CENTER_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
public synchronized long nextId() {
long currTimeStamp = getNewTimeStamp();
if (currTimeStamp < lastTimeStamp) {
throw new RuntimeException("Clock moved backwards. Refusing to generate id");
}
if (currTimeStamp == lastTimeStamp) {
sequence = (sequence + 1) & MAX_SEQUENCE;//相同毫秒内,***自增
if (sequence == 0L) //同一毫秒的序列数已经达到最大
{
currTimeStamp = getNextMill();
}
}
else
{
sequence = 0L;//不同毫秒内,***置为0
}
lastTimeStamp = currTimeStamp;
return (currTimeStamp - START_TIMESTAMP) << TIMESTAMP_LEFT //时间戳部分
| dataCenterId << DATA_CENTER_LEFT //数据中心部分
| machineId << MACHINE_LEFT //机器标识部分
| sequence; //***部分
}
public static void main(String[] args) {
SnowFlakeShortUrl snowFlake = new SnowFlakeShortUrl(2, 3);
for (int i = 0; i < (1 << 4); i++) {
//10进制
System.out.println(snowFlake.nextId());
}
}
}
7.滴滴出品(TinyID)
先附上项目地址:https://github.com/didi/tinyid
Tinyid是用Java开发的一款分布式id生成系统,扩展了leaf-segment算法,支持了多db(master),同时提供了java-client(sdk)使id生成本地化,获得了更好的性能与可用性。Tinyid在滴滴客服部门使用,均通过tinyid-client方式接入,每天生成亿级别的id。
特性:
- 全局唯一的long型id
- 趋势递增
- 非连续性
- 提供http和java client方式接入
- 支持批量获取id
- 支持生成1,3,5,7,9…序列的id
- 支持多个db的配置,无单点
tinyid的原理:
- tinyid是基于数据库发号算法实现的
- 可用号段在第一次获取id时加载,如当前号段使用达到一定量时,会异步加载下一可用号段,保证内存中始终有可用号段。
- 当使用到一定百分比时,如20%(默认),即200时,会异步加载下一可用号段到内存。
8.百度 (Uidgenerator)
先附上项目地址:https://github.com/baidu/uid-generator
uid-generator是基于Snowflake算法实现的,但uid-generator支持自定义时间戳、工作机器ID和 *** 等各部分的位数,而且采用用户自定义workId的生成策略。
uid-generator需要与数据库配合使用,需要新增一个WORKER_NODE表。当应用启动时会向数据库表中去插入一条数据,插入成功后返回的自增ID就是该机器的workId数据由host,port组成。
ID组成结构:
workId,占用了22个bit位,时间占用了28个bit位,序列化占用了13个bit位,需要注意的是,和snowflake不太一样,时间的单位是秒,而不是毫秒,workId也不一样,而且同一应用每次重启就会消费一个workId。
9.美团(Leaf)
先附上项目地址https://github.com/zhuzhong/idleaf
Leaf同时支持号段模式和snowflake算法模式,可以切换使用。
Leaf的snowflake模式依赖于ZooKeeper,不同于原始snowflake算法也主要是在workId的生成上,Leaf中workId是基于ZooKeeper的顺序Id来生成的,每个应用在使用Leaf-snowflake时,启动时都会都在Zookeeper中生成一个顺序Id,相当于一台机器对应一个顺序节点,也就是一个workId。
10.zookeeper
zookeeper主要通过其znode数据版本来生成***,可以生成32位和64位的数据版本号,客户端可以使用这个版本号来作为唯一的***。
很少会使用zookeeper来生成唯一ID。主要是由于需要依赖zookeeper,并且是多步调用API,如果在竞争较大的情况下,需要考虑使用分布式锁。因此,性能在高并发的分布式环境下,也不甚理想。