目录

1、为什么需要分布式ID算法？

2、常见的分布式ID算法实现

2.1 Java 的UUID方案

2.2 SnowFlake算法

2.3 基于Redis生成ID

2.4 基于DataBase生成ID

2.5 基于Zookeeper生成ID

3、开源框架对分布式ID算法的实现

3.1、Mybatis Plus 分布式ID

3.2、MyCat 分布式ID

4、我的分布式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();

}