分布式ID算法
1、为什么需要分布式ID算法?2、常见的分布式ID算法实现3、开源框架对分布式ID算法的实现3.1、Mybatis Plus 分布式ID3.2、MyCat 分布式ID4、我的分布式ID代码
目录
1、为什么需要分布式ID算法?
在复杂分布式系统中,往往需要对大量的数据进行唯一标识。如在电商系统中对订单号需要一个唯一标识ID,在分库分表的场景中,数据库的自增ID显然不能满足需求;此时一个能够生成全局唯一ID的系统是非常必要的。
- 1.全局唯一性:不能出现重复的ID号,既然是唯一标识,这是最基本的要求。
- 2.趋势递增:在MySQL InnoDB引擎中使用的是聚集索引,由于多数RDBMS使用B-tree的数据结构来存储索引数据,在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
- 3.单调递增:保证下一个ID一定大于上一个ID,例如事务版本号、IM增量消息、排序等特殊需求。
- 4.信息安全:如果ID是连续的,恶意用户的扒取工作就非常容易做了,直接按照顺序下载指定URL即可;如果是订单号就更危险了,竞对可以直接知道我们一天的单量。所以在一些应用场景下,会需要ID无规则、不规则。
- 5.分布式id里面最好包含时间戳,这样就能够在开发中快速了解这个分布式id的生成时间
2、常见的分布式ID算法实现
2.1 Java 的UUID方案
UUID是经由一定的算法机器生成的,为了保证UUID的唯一性,规范定义了包含网卡,MAC地址,时间戳,名字空间(nameSpace)、随机或伪随机数,时序等元素,以及从这些元素生成UUID的算法。UUID只能由计算机生成。
一个UUID是16字节长的数字,一共128位。转换成字符串后,它会变成一个36字节的字符串。使用的时候可以把中间的-分隔符给去掉,剩下32字节的字符串。
优点:
UUID的优点是本地生成ID,不需要进行远程调用,时效好,性能高。
缺点:
16字节共128位,通常以36字节长的字符串来表示,在很多应用场景不适应。UUID没有统一的排序,无法保证趋势递增,因此用于数据库索引字段的效率很低,添加记录存储入库性能差。
对于高并发和大数据量的系统,不建议使用UUID。
2.2 Twitter的SnowFlake算法
整个结构是64位,所以我们在Java中可以使用long来进行存储。 该算法实现基本就是二进制操作,单机每秒内理论上最多可以生成1024*(2^12),也就是409.6万个ID(1024 X 4096 = 4194304)。
0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
- 1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0
- 41位时间截(毫秒级),注意,41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截 - 开始时间截) 得到的值),这里的的开始时间截,一般是我们的id生成器开始使用的时间,由我们程序来指定的(如下下面程序IdWorker类的startTime属性)。41位的时间截,可以使用69年,年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69
- 10位的数据机器位,可以部署在1024个节点,包括5位datacenterId和5位workerId。10-bit机器可以分别表示1024台机器。如果我们对IDC划分有需求,还可以将10-bit分5-bit给IDC,分5-bit给工作机器。这样就可以表示32个IDC,每个IDC下可以有32台机器,可以根据自身需求定义。
- 12位序列,毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号。12个自增序列号可以表示2^12个ID,理论上snowflake方案的QPS约为409.6w/s,这种分配方式可以保证在任何一个IDC的任何一台机器在任意毫秒内生成的ID都是不同的。
优点:
1.生成ID时不依赖于数据库,完全在内存生成,高性能和高可用。
2.容量大,每秒可以生成几百万个ID
3.ID呈现趋势递增,后续插入数据库的所引述时,性能较高。
缺点:
1.依赖于系统时钟的一致性,如果某台机器的系统时钟回拨了,有可能造成ID冲突,或者ID乱序。
2.启动之前,如果这台机器的系统时间回拨过,那么有可能出现ID重复的危险。
美团做出了改进:https://github.com/Meituan-Dianping/Leaf
2.3 基于Redis生成ID
利用Redis客户端的INCR命令实现了序列号的递增操作。实现方案,利用分布式的Redis客户端Redisson中的RAtomicLong类,参考:Redisson之RAtomicLong
优点:
1.因为Redis是直接写内存,获取ID的性能比较高。
2.可以利用Redis集群实现HA。
缺点:
1.依赖Redis第三方组件,每次获取ID,需要访问Redis,存在一定的网络开销
2.4 基于DataBase【号段模式】生成ID
参考:https://www.cnblogs.com/kiko2014551511/p/13129239.html
号段模式是当下分布式ID生成器的主流实现方式之一 ,号段模式可以理解成从数据库批量获取ID。将ID缓存在本地,提升效率。
比如每次从数据库获取ID时,就获取一个号段,如(1,1000],这个范围表示1000个ID,业务应用在请求提供ID时,只需要在本地从1开始自增并返回,而不需要每次去请求数据库,一直到本地自增到1000时,也就是当前号段已经用完了,
才去数据库重新获取下一号段。
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`)
)
- biz_type : 代表不同业务类型
- max_id : 当前最大的可用id
- step : 代表号段的长度
- version : 是一个乐观锁,每次都更新version,保证并发时数据的正确性
等这批号段ID用完,再次向数据库申请新号段,对max_id字段做一次update操作 , update max_id = max_id + step ,update成功则说明新号段获取成功,新的号段范围是(max_id,max_id+step)。
update id_generator set max_id = #{max_id+step}, version = version + 1 where version = # {version} and biz_type = XXX
由于多业务端可能同时操作,所以采用的版本号version乐观锁方式更新,这种分布式ID生成方式不强依赖于数据库,不会频繁的访问数据库,对数据库的压力小很多
优点:
1.对ID号的批量获取提高了ID生成的性能与效率。
2.对传统数据库进行了支持,实施比较简单。
缺点:
1.对数据库有依赖,存在数据库单点故障的问题。
2. ID存在不连号的情况,当客户端未完成使用一个号段资源,并且中途宕机时,会丢失ID号。
2.5 基于Zookeeper生成ID
利用zookeeper集群来保证分布式ID生成组件的高可用HA,每个zookeeper节点存储对应的业务的当前ID值。
实现方案参考:基于zookeeper的分布式主键生成
优点:
1.利用zookeeper集群可以实现比较好的HA
缺点:
1.每个ID的生成都需要访问Zookeeper,在性能上会有一定的瓶颈。
2.依赖了zookeeper第三方组件。
3、开源框架对分布式ID算法的实现
3.1、MybatisPlus分布式ID
3.2、MyCat分布式ID
MyCat对全局序列号的支持主要有:本地文件方式、数据库方式、本地时间戳方式、分布式ZK ID生成器、ZK递增方式、自增长主键方式。具体参考《MyCat权威指南》第9章。
4、我的分布式ID代码
代码下载:单元测试用例
package com.autocoding.snowflake;
import org.junit.Test;
public class SnowFlakeUtilTest {
@Test
public void snowFlakeId() {
SnowFlakeUtil snowFlake = SnowFlakeUtil.getInstance(DefaultWorkerIdStrategy.getInstance(31L, 31L));
long start = System.currentTimeMillis();
for (int i = 0; i < 10; i++) {
SnowFlakeId snowFlakeId = snowFlake.next();
System.out.println("原始:id:" + snowFlakeId.id() + "|idString:" + snowFlakeId.idString());
SnowFlakeId parseSnowFlakeId = SnowFlakeId.parse(snowFlakeId.id());
System.out.println("解析:id:" + parseSnowFlakeId.id() + "|idString:" + parseSnowFlakeId.idString());
}
System.out.println("耗时(ms):" + (System.currentTimeMillis() - start));
}
}
算法思想源于SnowFlake算法,重点在于提供了一个抽象层的workId生成策略,可以让用户进行自定义实现:
package com.autocoding.snowflake;
/**
* workId生成策略
*
* @ClassName: WorkerIdStrategy
* @author: QiaoLi
* @date: Oct 21, 2020 11:11:59 AM
*/
public interface WorkerIdStrategy {
/**
*
* 返回数据中心Id,范围为0-31
*
* @return long
*/
public long getDataCenterId();
/**
*
* 机器Id ,范围为0-31
*
* @return long
*/
public long getMachineId();
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)