【Spring Cloud系列】 雪花算法原理及实现

【Spring Cloud系列】 雪花算法原理及实现

一、概述

分布式高并发的环境下，常见的就是12306节日订票，在大量用户同是抢购一个方向的票，毫秒级的时间下可能生成数万个订单，此时为确保生成订单ID的唯一性变得至关重要。此时秒杀环境下，不仅要保障ID唯一性，还得确保ID生成的优先度。

二、生成ID规则部分硬性要求

1. 全局唯一：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。
2. 趋势递增：在MySQL的InnoDB引擎中适用的是聚集索引，由于多数RDBMS使用B+Tree的数据结构来存储索引数据，在主键的选择上我们尽量使用有序的主键保证写入性能。
3. 单调递增：保证下一个ID一定大于上一个ID，如事务版本号、排序等特殊需求。
4. 信息安全：如果ID是连续的，恶意用户的抓取工作就非常容易，直接按照顺序下载指定URL即可；如果是订单号就危险。
5. 含有时间戳：生成的ID包含完整的时间戳信息。

三、ID号生成系统可用性要求

1. 高可用：发一个获取分布式ID的请求，服务器就是保证99.9999%的情况下给我创建一个唯一分布式ID。
2. 低延迟：发一个获取分布式ID的请求，服务器要快，极速。
3. 高QPS：如果一次请求10万个分布式ID，服务器要顶住并成功创建10万个分布式ID。

四、解决分布式ID通用方案

4.1 UUID

UUID（Universally Unique Identifier）的标准型式包含32个16进制数字，以连字号分为五段，形式为：8-4-4-4-12的36个字符，示例：1E785B2B-111C-752A-997B-3346E7495CE2；UUID性能非常高，不依赖网络，本地生成。

UUID缺点：

1. 无序，无法预测它的生成顺序，不能生成递增有序的数字。在MySql官方推荐主键约短越好，UUID是一个32位的字符串，所以不推荐使用。

2. 索引，B+Tree索引的分裂

   分布式Id是主键，主键是聚簇索引。Mysql的索引是B+Tree来实现的，每次新的UUID数据的插入，为了新的UUID数据的插入，为了查询的优化，都会对索引底部的B+Tree进行修改；因为UUID数据是无序的，所以每一次UUID数据的插入都会对主键的聚簇索引做很大的修改，在做数据Insert时，会插入主键是无序的，会导致一些中间节点的产生分裂，会导致大量不饱和的节点。这样大大降低了数据库插入的性能。

4.2 数据库自增主键

单机

在分布式里面，数据库的自增ID机制的主要原理是：数据库自增ID和MySql数据库的replace into实现的。

Replace into的含义是插入一条纪录，如果表中唯一索引的值遇到冲突，则替换老数据。

在单体应用的时候，自增长ID使用，但是在集群分布式应用中单体应用就不适合。

1. 系统水平扩展比较困难，比如定义好了增长步长和机器台数之后，在大量添加服务器时，需要重新设置初始值，这样可操作性差，所以系统水平扩展方案复杂度高难以实现。
2. 数据库压力大，每次获取ID都需要读写一次数据库，非常影响性能，不符合分布式ID里面的延迟低和要高QPS的规则（在高并发下，如果都去数据库里面获取Id，非常影响性能的。）

4.3 基于Redis生成全局id策略

在Redis集群情况下，同样和MySql一样需要设置不同的增长步长，同时key一定要设置有效期。可以使用Redis集群来获取更高的吞吐量。

五、SnowFlake（雪花算法）

而Twitter的SnowFlake解决了这种需求，最初Twitter把存储系统从MySQL迁移到Cassandra(由Facebook开发一套开源分布式NoSQL数据库系统) 因为Cassandra没有顺序ID生成机制，所以开发了这样一套全局唯一ID生成服务。SnowFlake每秒能产生26万个自增可排序的ID。

5.1 SnowFlake特点

1. Twitter的SnowFlake生成ID能够按照时间有序生成。
2. SnowFlake算法生成Id的结果是一个64bit大小的整数，为一个Long型（转换成字符串后长度最多19）。
3. 分布式系统内不会产生ID碰撞（由datacenter和workerid作为区分）并且效率较高。

5.2 SnowFlake结构

5.3 雪花算法原理

雪花算法的原理就是生成一个的64位比特位的long类型的唯一id

1. 最高1位固定值0，因为生成的id是正整数，如果是1就是负值。
2. 紧接着是41位存储毫秒级时间戳，2^41/(1000 * 60 * 24 * 365) = 69 ，大概可以使用69年。
3. 接下来10位存储机器码，包括5位DataCenterId和5位WorkerId,最多可以部署2^10=1024台机器。
4. 最后12位存储序列号，同一毫秒时间戳时，通过这个递增的序列号来区分，即对于同一台机器而言，同一毫秒级时间戳下，可以生成2^12=4096个不重复id。

可以将雪花算法作为一个单独的服务进行部署，然后需要全局唯一id的系统，请求雪花算法服务获取id即可。

对于每一个雪花算法服务，需要先指定10位的机器码，这个根据自身业务进行设定即可。例如机房号+机器号，机器号+服务号，或者时其他区别标识的10位比特位的整数都行。

5.4 算法实现

package com.goyeer;
import java.util.Date;/*** @ClassName: SnowFlakeUtil* @Author: goyeer* @Date: 2023/09/09 19:34* @Description:*/
public class SnowFlakeUtil {private static SnowFlakeUtil snowFlakeUtil;static {snowFlakeUtil = new SnowFlakeUtil();}// 初始时间戳(纪年)，可用雪花算法服务上线时间戳的值//private static final long INIT_EPOCH = 1694263918335L;// 时间位取&private static final long TIME_BIT = 0b1111111111111111111111111111111111111111110000000000000000000000L;// 记录最后使用的毫秒时间戳，主要用于判断是否同一毫秒，以及用于服务器时钟回拨判断private long lastTimeMillis = -1L;// dataCenterId占用的位数private static final long DATA_CENTER_ID_BITS = 5L;// dataCenterId占用5个比特位，最大值31// 0000000000000000000000000000000000000000000000000000000000011111private static final long MAX_DATA_CENTER_ID = ~(-1L << DATA_CENTER_ID_BITS);// dataCenterIdprivate long dataCenterId;// workId占用的位数private static final long WORKER_ID_BITS = 5L;// workId占用5个比特位，最大值31// 0000000000000000000000000000000000000000000000000000000000011111private static final long MAX_WORKER_ID = ~(-1L << WORKER_ID_BITS);// workIdprivate long workerId;// 最后12位，代表每毫秒内可产生最大序列号，即 2^12 - 1 = 4095private static final long SEQUENCE_BITS = 12L;// 掩码（最低12位为1，高位都为0），主要用于与自增后的序列号进行位与，如果值为0，则代表自增后的序列号超过了4095// 0000000000000000000000000000000000000000000000000000111111111111private static final long SEQUENCE_MASK = ~(-1L << SEQUENCE_BITS);// 同一毫秒内的最新序号，最大值可为 2^12 - 1 = 4095private long sequence;// workId位需要左移的位数 12private static final long WORK_ID_SHIFT = SEQUENCE_BITS;// dataCenterId位需要左移的位数 12+5private static final long DATA_CENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS;// 时间戳需要左移的位数 12+5+5private static final long TIMESTAMP_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATA_CENTER_ID_BITS;/*** 无参构造*/public SnowFlakeUtil() {this(1, 1);}/*** 有参构造* @param dataCenterId* @param workerId*/public SnowFlakeUtil(long dataCenterId, long workerId) {// 检查dataCenterId的合法值if (dataCenterId < 0 || dataCenterId > MAX_DATA_CENTER_ID) {throw new IllegalArgumentException(String.format("dataCenterId 值必须大于 0 并且小于 %d", MAX_DATA_CENTER_ID));}// 检查workId的合法值if (workerId < 0 || workerId > MAX_WORKER_ID) {throw new IllegalArgumentException(String.format("workId 值必须大于 0 并且小于 %d", MAX_WORKER_ID));}this.workerId = workerId;this.dataCenterId = dataCenterId;}/*** 获取唯一ID* @return*/public static Long getSnowFlakeId() {return snowFlakeUtil.nextId();}/*** 通过雪花算法生成下一个id，注意这里使用synchronized同步* @return 唯一id*/public synchronized long nextId() {long currentTimeMillis = System.currentTimeMillis();System.out.println(currentTimeMillis);// 当前时间小于上一次生成id使用的时间，可能出现服务器时钟回拨问题if (currentTimeMillis < lastTimeMillis) {throw new RuntimeException(String.format("可能出现服务器时钟回拨问题，请检查服务器时间。当前服务器时间戳：%d，上一次使用时间戳：%d", currentTimeMillis,lastTimeMillis));}if (currentTimeMillis == lastTimeMillis) {// 还是在同一毫秒内，则将序列号递增1，序列号最大值为4095// 序列号的最大值是4095，使用掩码（最低12位为1，高位都为0）进行位与运行后如果值为0，则自增后的序列号超过了4095// 那么就使用新的时间戳sequence = (sequence + 1) & SEQUENCE_MASK;if (sequence == 0) {currentTimeMillis = getNextMillis(lastTimeMillis);}} else { // 不在同一毫秒内，则序列号重新从0开始，序列号最大值为4095sequence = 0;}// 记录最后一次使用的毫秒时间戳lastTimeMillis = currentTimeMillis;// 核心算法，将不同部分的数值移动到指定的位置，然后进行或运行// <<：左移运算符, 1 << 2 即将二进制的 1 扩大 2^2 倍// |：位或运算符, 是把某两个数中, 只要其中一个的某一位为1, 则结果的该位就为1// 优先级：<< > |return// 时间戳部分((currentTimeMillis - INIT_EPOCH) << TIMESTAMP_SHIFT)// 数据中心部分| (dataCenterId << DATA_CENTER_ID_SHIFT)// 机器表示部分| (workerId << WORK_ID_SHIFT)// 序列号部分| sequence;}/*** 获取指定时间戳的接下来的时间戳，也可以说是下一毫秒* @param lastTimeMillis 指定毫秒时间戳* @return 时间戳*/private long getNextMillis(long lastTimeMillis) {long currentTimeMillis = System.currentTimeMillis();while (currentTimeMillis <= lastTimeMillis) {currentTimeMillis = System.currentTimeMillis();}return currentTimeMillis;}/*** 获取随机字符串,length=13* @return*/public static String getRandomStr() {return Long.toString(getSnowFlakeId());}/*** 从ID中获取时间* @param id 由此类生成的ID* @return*/public static Date getTimeBySnowFlakeId(long id) {return new Date(((TIME_BIT & id) >> 22) + INIT_EPOCH);}public static void main(String[] args) {SnowFlakeUtil snowFlakeUtil = new SnowFlakeUtil();long id = snowFlakeUtil.nextId();System.out.println(id);Date date = SnowFlakeUtil.getTimeBySnowFlakeId(id);System.out.println(date);long time = date.getTime();System.out.println(time);System.out.println(getRandomStr());}}

5.4 雪花算法优点

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

5.5 雪花算法缺点：

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

六、总结

其实雪花算法每一部分占用的比特位数量并不是固定死的。例如你的业务可能达不到 69 年之久，那么可用减少时间戳占用的位数，雪花算法服务需要部署的节点超过1024 台，那么可将减少的位数补充给机器码用。

注意，雪花算法中 41 位比特位不是直接用来存储当前服务器毫秒时间戳的，而是需要当前服务器时间戳减去某一个初始时间戳值，一般可以使用服务上线时间作为初始时间戳值。

对于机器码，可根据自身情况做调整，例如机房号，服务器号，业务号，机器 IP 等都是可使用的。对于部署的不同雪花算法服务中，最后计算出来的机器码能区分开来即可。