集群高并发情况下如何保证分布式唯一全局Id生成
为什么需要分布式全局唯一Id,以及分布式Id的业务需求
在复杂分布式系统中,往往需要对大量的数据和消息进行唯一标识
如在美团点评的金融、支付、餐饮、酒店;
猫眼电影等产品的系统中数据日渐增长,对数据分库分表后需要有一个唯一Id来标识一条数据或消息;
特别一点的如订单、骑手、优惠券也都需要有唯一Id坐标是.
此时一个能够生成全局唯一Id的系统是非常必要的
Id生成规则部分硬性要求
- 全局唯一
- 趋势递增
在Mysql的InnoDB引擎中使用的是聚集索引,由于多数RDBMS使用Btree的数据结构来存储索引数据,在主键的选择上面我们应该尽量使用有序的主键来保证写入性能
- 单调递增
尽量保证下一个Id一定大于上一个Id,例如事务版本号、IM增量消息、排序等特殊需求
- 信息安全
如果Id是连续的,恶意用户的扒取工作就非常容易做了,直接按照顺序下载指定URL即可;如果是订单号就更危险了,竞对可以直接知道我们一天的单量.所以在一些应用场景下,需要Id无规则不规则,让竞争对手不好猜
- 含时间戳
这样就能够在开发中快速了解这个分布式Id的生成时间
Id号生成系统的可用性要求
- 高可用
发一个获取分布式Id的请求,服务器就要保证99.999%的情况下给我创建一个唯一分布式Id
- 低延迟
发一个获取分布式Id的请求,服务器要快,极速
- 高QPS
例如并发一口气10万个创建分布式Id请求同时杀过来,服务器要顶得住且一下子成功创建10万个分布式Id
一般通用方案
- UUID
是什么: UUID(Univesally Unique Identifler)的标准型包含32个16进制数字,以连字号分为五段,形式为8-4-4-4-12的36个字符
性能非常高: 本地生成,没有网络消耗
如果只是考虑唯一性:OK,关键是他无序,入数据库性能比较差
为什么无序的UUID会导致入库性能变差呢?
- 无序,无法预测他的生成顺序,不能生成递增有序的数字.首先分布式Id一般都会作为主键,但是按照mysql官方推荐的主键尽量越短越好,UUID每一个都很长,所以不是很推荐
- 主键,ID作为主键时在特定的环境会存在一些问题.比如做DB主键的场景下,UUID就非常不适用MySQL官方有明确的建议主键尽量越短越好36个字符长度的UUID不符合要求
- 索引,B+树索引的分裂.既然分布式Id是主键,然后主键是包含索引的,然后mysql的索引是通过B+树来实现的,每一次新的UUID数据的插入,为了查询的优化,都会对索引底层的B+树进行修改,因为UUID是无序的,所以每一次UUID数据的插入都会对主键地城的B+树进行很大的修改,这一点很不好.插入完全无序,不但会导致一些中间节点产生分裂,也会白白创造出很多不饱和的节点,这样大大降低了数据库插入的性能
- 数据库自增主键(小公司)
在分布式里面,数据库的自增Id机制的主要原理是:数据库自增Id和mysql数据库的replace into实现的
这里的replace into跟insert功能类似
不同点在于: replace into首先尝试插入数据列表中,如果发现表中已经有此行数据(根据主键或唯一索引判断)则先删除,再插入,否则直接插入新数据.
REPLACE INTO 的含义是插入一条记录,如果表中唯一索引的值遇到冲突,则替换老数据
例: REPLACE INTO 表 (列..) values ('value'..)
那数据库自增ID机制适合做分布式ID吗?答案是不太合适
- 系统水平扩展比较困难,比如定义好了步长和机器台数之后,如果要添加机器该怎么做?假设现在只有一台机器发号是1.2.3.4.5(步长是1),这个时候需要扩容机器一台.可以这样做;把第二台机器的初始值设置的比第一台超过很多,貌似还好,现在想象一下如果我们线上有100台机器,这个时候要扩容该怎么做?简直是噩梦.所以系统水平扩展方案复杂难以实现
- 数据库压力还是很大,每次获取ID都得读写一次数据库,非常影响性能,不符合分布式ID里面的延迟低和高QPS的规则(在高并发下,如果都去数据库里面获取ID,那是非常影响性能的)
- Reids生成全局Id策略(部署麻烦)
因为Redis是单线的天生保证原子性,可以使用原子操作INCR和INCRBY来实现
注意: 在Redis集群情况下,同样和Mysql一样需要设置不同的增长步长,同时key一定要设置有效期
可以使用Redis集群来获取更高的吞吐量.
例如一个集群中有5台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
雪花算法
Twitter的分布式自增Id算法snowflake
最初Twitter把存储系统从Mysql迁移到Cassandra(由Facebook开发一套开源分布式NoSQL数据库系统)因为Cassandra没有顺序ID生成机制,所以开发了一套全局唯一ID生成服务
Twitter的分布式雪花算法SnowFlake,经测试每秒能够产生26万个自增可排序ID
- twitter的SnowFlake生成ID能够按照时间有序生成
- SnowFlake算法生成id的结果是一个64bit大小的整数,为一个Long型(转换成字符串后长度为19)
- 分布式系统内不会产生ID碰撞(由datacenter和workerId作区分)并且效率较高
雪花算法组成
号段解析
- 1bit: 不用,因为二进制中最高位是符号位,1表示负数,0表示正数,生成的id一般都是用整数,所以最高位固定为0.
- 41bit-时间戳: 用来记录时间戳,毫秒级.41位可以表示2(41)-1个数字;如果只用来表示正整数(计算机中正数包含0),可以表示的数值范围是:0至2(41)-1,减1是因为可表示的数值范围是从0开始算的,而不是1'也就是说41位可以表示2(41)-1个毫秒的值,转化成单位年则是2(41)-1/(1000606024365)=69年(够用到2039-09-07)
- 10bit-工作机器id: 用来记录工作机器的id.可以部署在2(10)=1024个节点,包括5位datacenterId和5位workerId;5位(bit)可以表示的最大正整数是2(5)-1=31,即可以用0,1,2,3,...31这32个数字,来表示不同的datacenterId和workerId
- 12bit-序列号: 用来记录同一毫秒内产生的不同id.12位(bit)可以表示最大正整数是2^{12}-1=4095,即可以用0,1,2,3...4094这4095个数字,来表示同一时间戳内产生的4095个ID序号
SnowFlake可以保证: 所有声称的id按时间趋势递增,整个分布式系统内不会产生重复id(因为有datacenterId和workerId来区分)
源码
目前雪花算法已经开源了,除非自己想手动配置机器码和唯一识别码等,不用刻意去了解底层机制,感兴趣的可以去github翻阅源码
gitHub
使用
Hutool工具包 官网
有一定经验的同学应该都用过,非常爽,例如官网的说法比如要计算MD5为例:
[以前] 打开搜索引擎->搜"java MD5加密"->打开某篇博客->复制粘贴->改改好用
[现在] 引入Hutool-> SecureUtil.md5()
SpringBoot项目的同学,可以参考我整理的封装工具类,拿去用就好了
package com.mac.zimu.util;
import cn.hutool.core.lang.Snowflake;
import cn.hutool.core.net.NetUtil;
import cn.hutool.core.util.IdUtil;
import lombok.extern.slf4j.Slf4j;
import javax.annotation.PostConstruct;
import java.util.concurrent.Executor;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.stream.Stream;
/**
* @PROJECT_NAME: 杭州品茗信息技术有限公司
* @DESCRIPTION: 获取雪花算法Id
* @author: 徐子木
* @DATE: 2020/12/15 8:29 下午
*/
@Slf4j
public class SnowFlakeUtil {
private static long workerId = 0;
private static long dataCenterId = 1;
private static Snowflake snowflake = IdUtil.createSnowflake(workerId,dataCenterId);
@PostConstruct
public void init() {
try {
workerId = NetUtil.ipv4ToLong(NetUtil.getLocalhostStr());
log.info("当前机器的workId: {}", workerId);
} catch (Exception e) {
e.printStackTrace();
log.error("当前机器的workId获取失败", e);
workerId = NetUtil.getLocalhostStr().hashCode();
}
}
public static synchronized long snowflakeId() {
return snowflake.nextId();
}
public static synchronized long snowflakeId(long workerId, long dataCenterId) {
Snowflake snowflake = IdUtil.createSnowflake(workerId, dataCenterId);
return snowflake.nextId();
}
public static void main(String[] args) {
ExecutorService executorService = Executors.newFixedThreadPool(5);
Stream.iterate(0,x->x+1).
limit(20).
forEach(x->{
executorService.submit(()->{
long id = SnowFlakeUtil.snowflakeId();
System.out.println(id);
});
});
executorService.shutdown();
}
}
优缺点
- 优点:
毫秒数在高位,自增序列在低位,整个ID都是趋势递增的.不依赖数据库等第三方系统,以服务的方式部署,稳定性更高,生成的Id的性能也是非常高的.可以根据自身业务特性分配bit位,非常灵活.
- 缺点:
依赖机器时钟,如果机器时钟回拨,会导致重复ID生成.在单机上是递增的,但是由于设计到分布式环境,每台机器上的时钟不可能完全同步,有时候会出现不是全局递增的情况(此缺点可以认为无所谓,一般分布式id只要求趋势递增,而不会严格要求递增,90%的需求都只要求趋势递增)!
