分布式唯一ID方案之雪花算法Snowflake
对于数据量庞大且需要考虑有序性时，那么可以使用雪花算法，当然既然要使用高性能工具，肯定是需要付出代价的，代价就是需要维护多个系统组件来保证高效生成有序的唯一ID。 下面从概念到实践一一介绍：
分布式唯一ID
-
使用RocketMQ时，需要使用到分布式唯一ID
-
消息可能会发生重复，所以要在消费端做幂等性，为了达到业务的幂等性，生产者必须要有一个唯一ID。
需要满足以下条件:
- 同一业务场景要全局唯一
- 该ID必须是在消息的发送方进行生成发送到MQ
- 消费端根据该ID进行判断是否重复,确保幂等性
-
在哪里产生以及消费端进行判断做幂等性与该ID无关，此ID需要保证的特性:
- 局部甚至全局唯一
- 趋势递增
Snowflake算法
-
Snowflake是Twitter开源的分布式ID生成算法, 结果是一个Long型的ID,核心思想是:
-
使用1位作为符号位,确定为0, 表示正
-
使用41位作为毫秒数
-
使用10位作为机器的ID : 高5位是数据中心ID, 低5位是机器ID
-
使用12位作为毫秒内的序列号，意味着每个节点每秒可以产生4096(212)个ID；该算法通过二进制的操作进行实现,单机每秒内理论上最多可以生成1000*(2^12)，即409.6万个ID。
-
SnowflakeIdWorker
- Snowflake算法Java实现SnowflakeIdWorker:
/** * Twitter_Snowflake<br> * SnowFlake的结构如下(每部分用-分开):<br> * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br> * 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0<br> * 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截) * 得到的值），这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br> * 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId<br> * 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号<br> * 加起来刚好64位，为一个Long型。<br> * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。 */ public class SnowflakeIdWorker { // ==============================Fields=========================================== /** 开始时间截 (2015-01-01) */ private final long twepoch = 142****600000L; /** 机器id所占的位数 */ private final long workerIdBits = 5L; /** 数据标识id所占的位数 */ private final long datacenterIdBits = 5L; /** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */ private final long maxWorkerId = -1L ^ (-1L << workerIdBits); /** 支持的最大数据标识id，结果是31 */ private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); /** 序列在id中占的位数 */ private final long sequenceBits = 12L; /** 机器ID向左移12位 */ private final long workerIdShift = sequenceBits; /** 数据标识id向左移17位(12+5) */ private final long datacenterIdShift = sequenceBits + workerIdBits; /** 时间截向左移22位(5+5+12) */ private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; /** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */ private final long sequenceMask = -1L ^ (-1L << sequenceBits); /** 工作机器ID(0~31) */ private long workerId; /** 数据中心ID(0~31) */ private long datacenterId; /** 毫秒内序列(0~4095) */ private long sequence = 0L; /** 上次生成ID的时间截 */ private long lastTimestamp = -1L; //==============================Constructors===================================== /** * 构造函数 * @param workerId 工作ID (0~31) * @param datacenterId 数据中心ID (0~31) */ public SnowflakeIdWorker(long workerId, long datacenterId) { if (workerId > maxWorkerId || workerId < 0) { throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId)); } if (datacenterId > maxDatacenterId || datacenterId < 0) { throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId)); } this.workerId = workerId; this.datacenterId = datacenterId; } // ==============================Methods========================================== /** * 获得下一个ID (该方法是线程安全的) * @return SnowflakeId */ public synchronized long nextId() { long timestamp = timeGen(); //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常 if (timestamp < lastTimestamp) { throw new RuntimeException( String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp)); } //如果是同一时间生成的，则进行毫秒内序列 if (lastTimestamp == timestamp) { sequence = (sequence + 1) & sequenceMask; //毫秒内序列溢出 if (sequence == 0) { //阻塞到下一个毫秒,获得新的时间戳 timestamp = tilNextMillis(lastTimestamp); } } //时间戳改变，毫秒内序列重置 else { sequence = 0L; } //上次生成ID的时间截 lastTimestamp = timestamp; //移位并通过或运算拼到一起组成64位的ID return ((timestamp - twepoch) << timestampLeftShift) // | (datacenterId << datacenterIdShift) // | (workerId << workerIdShift) // | sequence; } /** * 阻塞到下一个毫秒，直到获得新的时间戳 * @param lastTimestamp 上次生成ID的时间截 * @return 当前时间戳 */ protected long tilNextMillis(long lastTimestamp) { long timestamp = timeGen(); while (timestamp <= lastTimestamp) { timestamp = timeGen(); } return timestamp; } /** * 返回以毫秒为单位的当前时间 * @return 当前时间(毫秒) */ protected long timeGen() { return System.currentTimeMillis(); } //==============================Test============================================= /** 测试 */ public static void main(String[] args) { SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0); for (int i = 0; i < 1000; i++) { long id = idWorker.nextId(); System.out.println(Long.toBinaryString(id)); System.out.println(id); } } }
-
优点:
- 生成速度快
- 实现简单,没有多余的依赖
- 可以根据实际情况调整各个位段,方便灵活
-
缺点:
- 只能趋势递增
- 依赖机器时间. 如果发生时钟回拨可能会造成生成的ID重复
SnowFlake算法时间回拨问题:
-
时间回拨产生原因:
- 由于业务需要,机器需要同步时间服务器
-
时间回拨问题解决办法:
- 当回拨时间小于15ms,可以等待时间追上来以后再继续生成
- 当回拨时间大于15ms时可以通过更换workId来产生之前都没有产生过的Id来解决回拨问题
-
步骤:
- 首先将workId的位数进行调整至15位
- 首先将workId的位数进行调整至15位
* 然后将SnowflakeIdWorker实现调整位段 * 使用**1**位作为**符号位,** 即生成的分布式I唯一d为正数 * 使用**38**位作为**时间戳,** 表示当前时间相对于初始时间的增量值,单位为毫秒 * 使用**15**位作为**机器ID,** 最多可支持3.28万个节点 * 使用**10**位作为**毫秒内的序列号,** 理论上可以生成210个序列号 * 因为服务的无状态关系,正常情况下workId不会配置在具体配置文件中,这里可以选择集中式的Redis作为中央存储: * **将workId调整位数后得到的多余的3万多个workId放置到一个基于Redis的队列中,用来集中管理workId** * **每次当节点启动的时候,先查看本地是否有workId,如果有那么就作为workId.如果没有,就在队列中取出一个当workId来使用,并从队列中删除** * **当发现时间回拨太多的时候,就再去队列中去一个来当新的workId使用,将刚刚那个使用回拨的情况的workId存到队列里. 因为队列每次都是从头取出,从尾部插入,这样可以避免刚刚A机器使用的workId又被B机器获取的可能性**
如果使用redis又会遇到新的小问题: redis一致性如何保证?redis挂了怎么办?怎么同步?
-
从基础组件的使用角度来说,对于SnowflakeIdWorker算法当遇到时间回拨问题，只需要抛出异常即可，这样可以保证算法实现的简单性。
-
也可以参考百度的 uid-generator 方案 : 每次取一批workId, 集中之后批取,这样可以解决各个节点访问集中机器的性能问题.
-
或者参考美团的 Leaf 方案：基于zk的顺序id来生成的，每个应用在启动时都会在zk生成一个顺序id,相当于一个机器对应一个顺序节点。Leaf-snowflake对Zookeeper是一种弱依赖关系，除了每次会去ZK拿数据以外，也会在本机文件系统上缓存一个workerID文件。一旦ZooKeeper出现问题，恰好机器出现故障需重启时，依然能够保证服务正常启动。
