分布式唯一ID方案

背景

　　在复杂的分布式系统中，往往需要对大量的数据和消息进行唯一标识。

　　如对大量的订单做分库分表后，需要有一个唯一的ID来标识一条数据或消息，数据库的自增ID显然不能满足需求。

　　业务系统对分布式唯一ID的要求：

　　　　①：全局唯一性，不能重复

　　　　②：趋势递增，在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDMS使用B-tree的数据结构来存储索引数据，在主键的选择上面应该尽量使用有序的主键保证写入性能

　　　　③：单调递增，保证下一个ID一定大于上一个ID

　　　　④：信息安全，如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，会需要ID无规则、不规则

常用方案

　1、UUID

　　优点：生成简单，本地生成，没有网络消耗，性能非常高

　　缺点：

　　　　1）每次生成的ID是无序的，无法保证趋势递增，不能作为数据库主键，否则会引起索引数据位置频繁变动，严重影响性能

　　　　2）UUID的字符串存储，查询效率慢

　　　　3）存储空间大

　　　　4）ID本身无业务含义，不可读

　2、Redis 

　　利用redis的原子性自增，具体实现为：

　　年份 + 当天距当年第多少天 + 天数 + 小时 + redis自增

　　优点：

　　　　有序递增，可读性强

　　缺点：

　　　　占用带宽，每次要向redis进行请求

　3、雪花snowflake算法

　　snowflake是Twitter开源的分布式ID生成算法，结果是一个long型的ID。

　　其核心思想是：使用41bit作为毫秒数，10bit作为work ID（5个bit是数据中心，5个bit的机器ID），12bit作为毫秒内的流水号（意味着每个节点在每毫秒可以产生 4096 个 ID），最后还有一个符号位，永远是0。

　　snowflake算法生成64位的二进制正整数，然后转换成10进制的数。

　　64位二进制数组成部分如下：

　　优点：

　　　　1）此方案每秒能够产生409.6万个ID，性能快

　　　　2）时间戳在高位，自增序列在低位，整个ID是趋势递增的，按照时间有序递增

　　　　3）灵活度高，可以根据业务需求，调整bit位的划分，满足不同的需求

　　缺点：

　　　　只能保证work id相同的情况下生成的id是递增的

　　　　依赖机器的时钟，如果服务器时钟回拨，会导致重复ID生成　　

　　时钟回拨问题的解决方案：

　　　　1）回拨之后更换work id

　　　　2）等时间追上来再去生成id

  Mongo的ObjectId与snowflake类似，12 字节的ObjectId包括：

    一个 4 字节的时间戳，表示 ObjectId 的创建，以 Unix 纪元以来的秒数为单位。

    每个进程生成一次的 5 字节随机值。这个随机值对于机器和过程是唯一的。

    一个 3 字节递增计数器，初始化为随机值

　4、美团Leaf

 https://tech.meituan.com/2017/04/21/mt-leaf.html

  Snowflake代码：

  1）系统时钟 SystemClock：

import java.sql.Timestamp;
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;
/**
 * 系统时钟

 * 高并发场景下System.currentTimeMillis()的性能问题的优化
 * System.currentTimeMillis()的调用比new一个普通对象要耗时的多（具体耗时高出多少我还没测试过，有人说是100倍左右）
 * System.currentTimeMillis()之所以慢是因为去跟系统打了一次交道
 * 后台定时更新时钟，JVM退出时，线程自动回收
 *
 * see： http://git.oschina.net/yu120/sequence
 * @author lry,looly
 */
public class SystemClock {
	/** 时钟更新间隔，单位毫秒 */
	private final long period;
	/** 现在时刻的毫秒数 */
	private volatile long now;
	/**
	 * 构造
	 * @param period 时钟更新间隔，单位毫秒
	 */
	public SystemClock(long period) {
		this.period = period;
		this.now = System.currentTimeMillis();
		scheduleClockUpdating();
	}
	/**
	 * 开启计时器线程
	 */
	private void scheduleClockUpdating() {
		ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor(runnable -> {
			Thread thread = new Thread(runnable, "System Clock");
			thread.setDaemon(true);
			return thread;
		});
		scheduler.scheduleAtFixedRate(() -> now = System.currentTimeMillis(), period, period, TimeUnit.MILLISECONDS);
	}
	/**
	 * @return 当前时间毫秒数
	 */
	private long currentTimeMillis() {
		return now;
	}
	//------------------------------------------------------------------------ static
	/**
	 * 单例
	 * @author Looly
	 *
	 */
	private static class InstanceHolder {
		public static final SystemClock INSTANCE = new SystemClock(1);
	}
	/**
	 * @return 当前时间
	 */
	public static long now() {
		return InstanceHolder.INSTANCE.currentTimeMillis();
	}
	/**
	 * @return 当前时间字符串表现形式
	 */
	public static String nowDate() {
		return new Timestamp(InstanceHolder.INSTANCE.currentTimeMillis()).toString();
	}
}

  Snowflake：

import java.io.Serializable;
import java.util.Date;
/**
 * Twitter的Snowflake 算法
 * 分布式系统中，有一些需要使用全局唯一ID的场景，有些时候我们希望能使用一种简单一些的ID，并且希望ID能够按照时间有序生成。
 *
 * snowflake的结构如下(每部分用-分开):
 *
 * 符号位（1bit）- 时间戳相对值（41bit）- 数据中心标志（5bit）- 机器标志（5bit）- 递增序号（12bit）
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
 *
 * 第一位为未使用(符号位表示正数)，接下来的41位为毫秒级时间(41位的长度可以使用69年)
 * 然后是5位datacenterId和5位workerId(10位的长度最多支持部署1024个节点)
 * 最后12位是毫秒内的计数（12位的计数顺序号支持每个节点每毫秒产生4096个ID序号）
 *
 * 并且可以通过生成的id反推出生成时间,datacenterId和workerId
 *
 * 参考：http://www.cnblogs.com/relucent/p/4955340.html

 * 关于长度是18还是19的问题见：https://blog.csdn.net/unifirst/article/details/80408050
 *
 * @author Looly
 * @since 3.0.1
 */
public class Snowflake implements Serializable {
    private static final long serialVersionUID = 1L;
    /**
     * 默认的起始时间，为Thu, 04 Nov 2010 01:42:54 GMT
     */
    public static long DEFAULT_TWEPOCH = 1288834974657L;
    /**
     * 默认回拨时间，2S
     */
    public static long DEFAULT_TIME_OFFSET = 2000L;
    private static final long WORKER_ID_BITS = 5L;
    // 最大支持机器节点数0~31，一共32个
    @SuppressWarnings({"PointlessBitwiseExpression", "FieldCanBeLocal"})
    private static final long MAX_WORKER_ID = -1L ^ (-1L > WORKER_ID_SHIFT & ~(-1L > DATA_CENTER_ID_SHIFT & ~(-1L > TIMESTAMP_LEFT_SHIFT & ~(-1L