关于雪花
雪花(snowflake)在自然界中，是极具独特美丽，又变幻莫测的东西：
- 雪花属于六方晶系，它具有四个结晶轴，其中三个辅轴在一个基面上，互相以60度的角度相交，第四轴(主晶轴)与三个辅轴所形成的基面垂直；
- 雪花的基本形状是六角形，但是大自然中却几乎找不出两朵完全相同的雪花，每一个雪花都拥有自己的独有图案，就象地球上找不出两个完全相同的人一样。许多学者用显微镜观测过成千上万朵雪花，这些研究最后表明，形状、大小完全一样和各部分完全对称的雪花，在自然界中是无法形成的。
雪花算法
雪花算法的原始版本是scala版，用于生成分布式ID（纯数字，时间顺序）,订单编号,骑手,优惠券等。
- 自增ID：对于数据敏感场景不宜使用，且不适合于分布式场景。
- GUID：采用无意义字符串，数据量增大时造成访问过慢，且不宜排序。
ID生成规则部分硬性要求：
-
全局唯一：不能出现重复的ID号，既然是唯一-标识，这是最基本的要求 -
趋势递增：在MySQL的InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用Btree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。 -
单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求 -
信息安全：如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可。如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，需要ID无规则不规则，让竞争对手否好猜。 -
含时间戳：这样就能够在开发中快速了解这个分布式id的生成时间。
ID号生成系统的可用性要求：
-
高可用：发一个获取分布式ID的请求，服务器就要保证99.999%的情况下给我创建一个唯一分布式ID。 -
低延迟：发一个获取分布式ID的请求，服务器就要快，极速。 -
高QPS：假如并发一口气10万个创建分布式ID请求同时杀过来，服务器要顶的住且一下子成功创建10万个分布式ID。
一般通用方案：
方法1：
UUID(Universally Unique ldentifer)的标准型式包含32个16进制数字，以连字号分为五段，形式为8位-4位-4位-4位-12位的36个字符， 示例：550e8400-e29b-41d4-a716-446655440000
- 优点：性能非常高、本地生成，没有网络消耗，唯一性也是OK的。
- 缺点：入数据库性能差，生产环境下不适合使用。（此方法不可行，只满足了5个硬性要求里的1个要求：全局唯一要求）
无序，无法预测他的生成顺序，不能生成递增有序的数字。首先分布式ID一般都会作为主键， 但是MySQL官方推荐主键要尽量越短越好，UUID每一个都很长，所以不是很推荐。主键，ID作为主键时在特定的环境会存在一些问题。比如做DB主键的场景下，UUID就非常不适用MySQL官方有明确的建议主键要尽量越短越好，而36个字符长度的UUID不符合要求。索引，既然分布式ID是主键，然后主键是包含索引的，然后MySQL的索引是通过B+树来实现的，每一次新的UUID数据的插入，为了查询的优化，都会对索引底层的B+树进行修改，因为UUID数据是无序的，所以每一次UUID数据的插入都会对主键地械的B+树进行很大的修改，这一点很不好。插入完全无序，不但会导致一些中间节点产生分裂，也会白白创造出很多不饱和的节点，这样大大降低了数据库插入的性能。
方法2：
数据库自增主键方法，又分了2种形式：单机、集群分布式。
单机（此方法可行，生产规模不大的项目中可使用）：在单机里面，数据库的自增ID机制的主要原理是：数据库自增ID和MySQL数据库的replace into实现。REPLACE INTO的含义是插入一条记录，如果表中唯一索引的值遇到冲突，则替换就数据。
replace into跟inset功能类似，不同点在于：replace into首先尝试插入数据列表中，如果发现表中已经有此行数据（根据主键或唯一索引判断）则先删除，再插入。否则直接插入新数据。
-- 创建一张测试表，stub字段设置了唯一索引。
CREATE TABLE t_test(
id BIGINT(20) UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
stub CHAR(1) NOT NULL DEFAULT '',
UNIQUE KEY stub(stub)
)
-- 查询表数据
SELECT * FROMt_ test;
-- 第一次插入一条数据，主键索引的值是1，第二次再次执行会根据主键或唯一索引判断，是否存在，存在则先删除，再插入。
REPLACE INTO t_test (stub) VALUES('b');
-- 查询当前主键索引
SELECT LAST_INSERT_ID();
集群分布式（此方法不可行）：数据库自增ID机制不太适合作分布式ID，理由如下：
- 系统水平扩展比较困难，比如定义好了步长和机器台数之后，如果要添加机器该怎么做？假设现在只有一台机器发号是1，2，3，4，5（步长是1），这个时候需要扩容机器一台。可以这样做：把第二台机器的初始值设置得比第一台超过很多，貌似还好，现在想象一下如果我们线上有100台机器，这个时候要扩容该怎么做？简直是噩梦，所以系统水平扩展方案复杂难以实现。
- 数据库压力还是很大，每次获取ID都得读写一次数据库， 非常影响性能，不符合分布式ID里面的延迟低和要高QPS的规则（在高并发下，如果都去数据库里面获取id，那是非常影响性能的）。
方法3：
基于Redis生成全局ID策略，Redis是单线的天生保证原子性，可以使用原子操作INCR和INCRBY来实现。（此方法可行，但配置麻烦要依赖第三方来实现，中途某台redis服务宕机了，会出现不连号的现象）
注意：在Redis集群情况下，同样和MySQL一样需要设置不同的增长步长，同时key一定要设置有效期可以使用Redis集群来获取更高的吞吐量。
举例：一个集群中有5台Redis。可以初始化每台Redis的值分别是1,2,3,4,5，然后步长都是5。各个 Redis生成的ID为:
????????????????A台：1, 6, 11, 16, 21
????????????????B台：2, 7 , 12, 17, 22
????????????????C台：3, 8, 13, 18, 23
????????????????D台：4, 9, 14, 19, 24
????????????????E台：5, 10, 15, 20, 25
推荐方案：
雪花算法，它的起源snowflake中文的意思是 雪花，雪片，所以翻译成雪花算法。它最早是twitter内部使用的分布式环境下的唯一ID生成算法。在2014年开源，开源的版本由scala编写。
雪花算法产生的背景当然是twitter高并发环境下对唯一ID生成的需求，得益于twitter内部牛逼的技术，雪花算法流传至今并被广泛使用。它至少有如下几个特点：
能满足高并发分布式系统环境下ID不重复基于时间戳，可以保证基本有序递增（有些业务场景对这个有要求）不依赖第三方的库或者中间件生成效率极高
雪花算法原理：
算法产生的是一个Long型 64 bit位的值，转换成字符串长度最长19位。
算法描述：
- 最高位第一位是符号位，始终为0，不可用。因为二进制中最高位是符号位，1表示负数，0表示正数。生成的id一般都是用整数，所以最高位固定为0。
- 41位的时间序列，精确到毫秒级，41位的长度可以使用69年。时间位还有一个很重要的作用是可以根据时间进行排序。（2 ^ 41 / 1000 * 60 * 60 * 24 * 365 = 69 年）以为这个时间戳是相对于一个我们业务中指定的时间（一般是系统上线时间），而不是1970年。这里一定要注意。
- 10位的机器标识，10位的长度最多支持部署1024个节点。
- 12位的计数序列号，序列号即一系列的自增id，用来记录同毫秒内产生的不同id。可以支持同一节点同一毫秒生成多个ID序号，在毫秒的时间戳内计数，12位的计数序列号支持每个节点每毫秒产生4096个ID序号。所以最大可以支持单节点差不多四百万的并发量，这个妥妥的够用了。
SnowFlake可以保证：
- 所有生成的ID按时间趋势递增。
- 整个分布式系统内不会产生重复id（因为有DataCenterId和Workerld来做区分)
雪花算法java实现：
public class SnowflakeIdWorker {
/** 开始时间截 (这个用自己业务系统上线的时间) */
private final long twepoch = 1575365018000L;
/** 机器id所占的位数 */
private final long workerIdBits = 10L;
/** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
/** 序列在id中占的位数 */
private final long sequenceBits = 12L;
/** 机器ID向左移12位 */
private final long workerIdShift = sequenceBits;
/** 时间截向左移22位(10+12) */
private final long timestampLeftShift = sequenceBits + workerIdBits;
/** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */
private final long sequenceMask = -1L ^ (-1L << sequenceBits);
/** 工作机器ID(0~1024) */
private long workerId;
/** 毫秒内序列(0~4095) */
private long sequence = 0L;
/** 上次生成ID的时间截 */
private long lastTimestamp = -1L;
//==============================Constructors=====================================
/**
* 构造函数
* @param workerId 工作ID (0~1024)
*/
public SnowflakeIdWorker(long workerId) {
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("workerId can't be greater than %d or less than 0", maxWorkerId));
}
this.workerId = workerId;
}
// ==============================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) //
| (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();
}
/**
* 测试
*/
public static void main(String[] args) {
System.out.println("开始："+System.currentTimeMillis());
SnowflakeIdWorker idWorker = new SnowflakeIdWorker(1);
for (int i = 0; i < 50; i++) {
long id = idWorker.nextId();
System.out.println(id);
// System.out.println(Long.toBinaryString(id));
}
System.out.println("结束："+System.currentTimeMillis());
}
}
实际项目使用Snowflake操作：
<!-- Hutool糊涂工具-图片验证码（里面包含雪花算法）依赖 -->
<dependency>
<groupId>cn.hutool</groupId>
<artifactId>hutool-captcha</artifactId>
<version>4.6.8</version>
</dependency>
示例程序：
package com.king.springcloud.util;
import cn.hutool.core.lang.Snowflake;
import cn.hutool.core.net.NetUtil;
import cn.hutool.core.util.IdUtil;
import lombok.extern.slf4j.Slf4j;
import org.springframework.stereotype.Component;
import javax.annotation.PostConstruct;
@Slf4j
@Component
public class IdGeneratorSnowflake{
/**
* 工作机器ID，此值的区间值是0～31
*/
private long workerId = 0;
/**
* 数据中心ID，此值的区间值是0～31
*/
private long datacenterId = 1;
/**
* 通过糊涂工具包的IdUtill创建雪花对象
*/
private Snowflake snowflake = IdUtil.createSnowflake(workerId, datacenterId);
/**
* 使用默认参数获得全局ID
*/
public synchronized long snowflakeId(){
return snowflake.nextId();
}
/**
* 使用自定义参数获得全局ID
*/
public synchronized long snowflakeId(long workerId, long datacenterId){
Snowflake snowflake = IdUtil.createSnowflake(workerId, datacenterId);
return snowflake.nextId();
}
public static void main(String[] args){
IdGeneratorSnowflake idGenerator = new IdGeneratorSnowflake();
// 输出默认参数的全局ID
System.out.println(idGenerator.snowflakeId());
// 模拟多线程环境，创建5个线程池
ExecutorService threadPool = Executors.newFixedThreadPool(5);
// 线程池大小为5，但是要执行的线程是20个。
for (int i = 1; i <= 20; i++){
threadPool.submit(() -> {
System.out.print1n(idGenerator.snowflakeId());
});
}
// 关闭线程池
threadPool.shutdown();
}
}
优点：
-
毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。
-
不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的。
-
可以根据自身业务特性分配bit位，非常灵活。
缺点：
-
依赖机器时钟，如果机器时钟回拨，会导致重复ID生成。
-
在单机上是递增的，但是由于设计到分布式环境，每台机器上的时钟不可能完全同步，有时候会出现不是全局递增的情况。（此缺点可以认为无所谓，一般分布式ID只要求趋势递增，并不会严格要求递增，90%的需求都只要求趋势递增）
其他分布式唯一ID生成器补充：