雪花算法完全解读

特点

SnowFlake算法是Twitter开源的分布式ID生成算法。核心思想就是：使用一个64 bit的 long 型的数字作为全局唯一ID。算法中还引入了时间戳，基本上保证了自增特性。

其特点是将64位的long型ID分为四个部分，分别为：时间戳、机器ID和序列号，详情查看结构图

原理

SnowFlake算法生成ID的结果是一个64bit大小的整数，结构如下图：雪花算法

解析

第一个部分：1个bit，无意义，固定为0。二进制中最高位是符号位，1表示负数，0表示正数。ID都是正整数，所以固定为0。
第二个部分：41个bit，表示时间戳，精确到毫秒，2^41/(1000_60_60_24_365)=69，大概可以使用 69 年。时间戳带有自增属性。
第三个部分：10个bit，表示10位的机器标识，最多支持2^10=1024个节点。此部分也可拆分成5位datacenterId和5位workerId，datacenterId表示机房ID，workerId表示机器ID。
第四部分：12个bit，表示序列号，同一毫秒时间戳时，通过这个递增的序列号来区分。即对于同一台机器而言，同一毫秒时间戳下，可以生成 2^12=4096 个不重复 id。

特点

由于在Java中64bit的整数是long类型，所以在Java中SnowFlake算法生成的id就是long来存储的。
对于每一个雪花算法服务，需要先指定 10 位的机器码，这个根据自身业务进行设定即可。例如机房号+机器号，机器号+服务号，或者是其他可区别标识的 10 位比特位的整数值都行。

优点

高并发分布式环境下生成不重复 id，每秒可生成百万个不重复 id。
基于时间戳，以及同一时间戳下序列号自增，基本保证 id 有序递增。
不依赖第三方库或者中间件。
算法简单，在内存中进行，效率高。

缺点

依赖服务器时间，服务器时钟回拨时可能会生成重复 id。算法中可通过记录最后一个生成 id 时的时间戳来解决，每次生成 id 之前比较当前服务器时钟是否被回拨，避免生成重复 id。

注意

雪花算法每一部分占用的比特位数量并不是固定死的。例如你的业务可能达不到 69 年之久，那么可用减少时间戳占用的位数，雪花算法服务需要部署的节点超过1024 台，那么可将减少的位数补充给机器码用。
雪花算法中 41 位比特位不是直接用来存储当前服务器毫秒时间戳的，而是需要当前服务器时间戳减去某一个初始时间戳值，一般可以使用服务上线时间作为初始时间戳值。
对于机器码，可根据自身情况做调整，例如机房号，服务器号，业务号，机器 IP 等都是可使用的。对于部署的不同雪花算法服务中，最后计算出来的机器码能区分开来即可。

实现

public class SnowFlake {

	/**
	 * 起始的时间戳（可设置当前时间之前的邻近时间）
	 */
	private final static long START_STAMP = 1480166465631L;

	/**
	 * 序列号占用的位数
	 */
	private final static long SEQUENCE_BIT = 12;
	/**
	 * 机器标识占用的位数
	 */
	private final static long MACHINE_BIT = 5;
	/**
	 * 数据中心占用的位数
	 */
	private final static long DATA_CENTER_BIT = 5;

	/**
	 * 每一部分的最大值
	 */
	private final static long MAX_DATA_CENTER_NUM = ~(-1L << DATA_CENTER_BIT);
	private final static long MAX_MACHINE_NUM = ~(-1L << MACHINE_BIT);
	private final static long MAX_SEQUENCE = ~(-1L << SEQUENCE_BIT);

	/**
	 * 每一部分向左的位移
	 */
	private final static long MACHINE_LEFT = SEQUENCE_BIT;
	private final static long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
	private final static long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT;

	/**
	 * 数据中心ID(0~31)
	 */
	private final long dataCenterId;
	/**
	 * 工作机器ID(0~31)
	 */
	private final long machineId;
	/**
	 * 毫秒内序列(0~4095)
	 */
	private long sequence = 0L;
	/**
	 * 上次生成ID的时间截
	 */
	private long lastStamp = -1L;

	public SnowFlake(long dataCenterId, long machineId) {
		if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) {
			throw new IllegalArgumentException("dataCenterId can't be greater than MAX_DATA_CENTER_NUM or less than " +
					"0");
		}
		if (machineId > MAX_MACHINE_NUM || machineId < 0) {
			throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0");
		}
		this.dataCenterId = dataCenterId;
		this.machineId = machineId;
	}

	/**
	 * 产生下一个ID
	 */
	public synchronized long nextId() {
		long currStamp = getNewStamp();
		if (currStamp < lastStamp) {
			throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
		}

		if (currStamp == lastStamp) {
			//相同毫秒内，序列号自增
			sequence = (sequence + 1) & MAX_SEQUENCE;
			//同一毫秒的序列数已经达到最大
			if (sequence == 0L) {
				//阻塞到下一个毫秒,获得新的时间戳
				currStamp = getNextMill();
			}
		} else {
			//不同毫秒内，序列号置为0
			sequence = 0L;
		}

		lastStamp = currStamp;

		// 移位并通过或运算拼到一起组成64位的ID
		return (currStamp - START_STAMP) << TIMESTAMP_LEFT //时间戳部分
				| dataCenterId << DATA_CENTER_LEFT       //数据中心部分
				| machineId << MACHINE_LEFT             //机器标识部分
				| sequence;                             //序列号部分
	}

	private long getNextMill() {
		long mill = getNewStamp();
		while (mill <= lastStamp) {
			mill = getNewStamp();
		}
		return mill;
	}

	private long getNewStamp() {
		return System.currentTimeMillis();
	}

	public static void main(String[] args) {
		SnowFlake snowFlake = new SnowFlake(11, 11);

		long start = System.currentTimeMillis();
		for (int i = 0; i < 10; i++) {
			System.out.println(snowFlake.nextId());
		}

		System.out.println(System.currentTimeMillis() - start);
	}
}

开源项目

美团 Leaf

介绍

Leaf——美团点评分布式ID生成系统 Leaf：美团分布式ID生成服务开源

特点

Leaf-segment,利用数据库自增的原理
Leaf-snowflake,利用zookeeper的顺序节点原理

Leaf-segment

优点

Leaf 服务可以很方便的线性扩展，性能完全能够支撑大多数业务场景。
ID 号码是趋势递增的8byte的64位数字，满足上述数据库存储的主键要求。
容灾性高：Leaf 服务内部有号段缓存，即使DB宕机，短时间内Leaf仍能正常对外提供服务。
可以自定义 max_id 的大小，非常方便业务从原有的ID方式上迁移过来。

缺点

ID号码不够随机，能够泄露发号数量的信息，不太安全。
TP999数据波动大，当号段使用完之后还是会hang在更新数据库的I/O上，tg999数据会出现偶尔的尖刺。
DB宕机会造成整个系统不可用。

Leaf-snowflake

特点

对Zookeeper生成机器号做了弱依赖处理，即使Zookeeper有问题，也不会影响服务。
Leaf在第一次从Zookeeper拿取workerID后，会在本机文件系统上缓存一个workerID文件。即使ZooKeeper出现问题，同时恰好机器也在重启，也能保证服务的正常运行。这样做到了对第三方组件的弱依赖，一定程度上提高了SLA。

百度UidGenerator

介绍

GitHub - baidu/uid-generator: UniqueID generator

特点

UidGenerator是Java实现的, 基于Snowflake算法的唯一ID生成器。UidGenerator以组件形式工作在应用项目中, 支持自定义workerId位数和初始化策略, 从而适用于docker等虚拟化环境下实例自动重启、漂移等场景。在实现上, UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐，避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。

百度雪花算法

Snowflake算法描述：指定机器 & 同一时刻 & 某一并发序列，是唯一的。据此可生成一个64 bits的唯一ID（long）。默认采用上图字节分配方式：

sign(1bit) 固定1bit符号标识，即生成的UID为正数。
delta seconds (28 bits) 当前时间，相对于时间基点"2016-05-20"的增量值，单位：秒，最多可支持约8.7年
worker id (22 bits) 机器id，最多可支持约420w次机器启动。内置实现为在启动时由数据库分配，默认分配策略为用后即弃，后续可提供复用策略。
sequence (13 bits) 每秒下的并发序列，13 bits可支持每秒8192个并发。

以上参数均可通过Spring进行自定义

和美团对比

百度的worker id的生成策略和美团的生成策略不太一样
美团的snowflake主要利用本地配置的port和IP来唯一确定一个workid，美团的这种生成方式还是可以由于手工配置错误造成port重复，最终产生重复ID的风险
百度的这种生成方式每次都是新增的，可能会一段时间后worker id用完的情况，人工配置错误的可能性很小了

特点

原理

解析​

特点​

优点​

缺点​

注意​

实现​

开源项目​

美团 Leaf​

介绍​

特点​

Leaf-segment​

优点​

缺点​

Leaf-snowflake​

特点​

百度UidGenerator​

介绍​

特点​

和美团对比​

解析

特点

优点

缺点

注意

实现