集群高并发情况下如何保证分布式唯一全局Id生成
1、为什么需要分布式全局唯一Id,以及分布式Id的业务需求
在复杂分布式系统中,往往需要对大量的数据和消息进行唯一标识
如在美团点评的金融、支付、餐饮、酒店;
猫眼电影等产品的系统中数据日渐增长,对数据分库分表后需要有一个唯一Id来标识一条数据或消息;
特别一点的如订单、骑手、优惠券也都需要有唯一Id坐标是.
此时一个能够生成全局唯一Id的系统是非常必要的
全局唯一
趋势递增
在Mysql的InnoDB引擎中使用的是聚集索引,由于多数RDBMS使用Btree的数据结构来存储索引数据,在主键的选择上面我们应该尽量使用有序的主键来保证写入性能
- 单调递增
尽量保证下一个Id一定大于上一个Id,例如事务版本号、IM增量消息、排序等特殊需求
- 信息安全
如果Id是连续的,恶意用户的扒取工作就非常容易做了,直接按照顺序下载指定URL即可;如果是订单号就更危险了,竞对可以直接知道我们一天的单量.所以在一些应用场景下,需要Id无规则不规则,让竞争对手不好猜
- 含时间戳
这样就能够在开发中快速了解这个分布式Id的生成时间
发一个获取分布式Id的请求,服务器就要保证99.999%的情况下给我创建一个唯一分布式Id
发一个获取分布式Id的请求,服务器要快,极速
例如并发一口气10万个创建分布式Id请求同时杀过来,服务器要顶得住且一下子成功创建10万个分布式Id
是什么: 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
5、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位可以表示241-1个数字;如果只用来表示正整数(计算机中正数包含0),可以表示的数值范围是:0至241-1,减1是因为可表示的数值范围是从0开始算的,而不是1′也就是说41位可以表示241-1个毫秒的值,转化成单位年则是241-1/(1000606024365)=69年(够用到2039-09-07)
10bit-工作机器id: 用来记录工作机器的id.可以部署在210=1024个节点,包括5位datacenterId和5位workerId;5位(bit)可以表示的最大正整数是25-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
优点:
毫秒数在高位,自增序列在低位,整个ID都是趋势递增的.不依赖数据库等第三方系统,以服务的方式部署,稳定性更高,生成的Id的性能也是非常高的.可以根据自身业务特性分配bit位,非常灵活.
缺点:
依赖机器时钟,如果机器时钟回拨,会导致重复ID生成.在单机上是递增的,但是由于设计到分布式环境,每台机器上的时钟不可能完全同步,有时候会出现不是全局递增的情况(此缺点可以认为无所谓,一般分布式id只要求趋势递增,而不会严格要求递增,90%的需求都只要求趋势递增)!
版权声明：本文由[SinceMay]发表于
https://www.jianshu.com/p/3b75c254a7c8
