雪花算法(Snowflake)
概述
雪花算法(Snowflake)是twitter把存储系统从MySQL迁移到Cassandra (Facebook开发的开源分布式NoSQL数据库，但Cassandra没有顺序ID生成机制) 开发出来的一套全局唯一ID生成服务。
Twitter分布式雪花算法(snowflake),经过测试每秒能够生成约26万个自增可排序的ID
1、twitter的snowflake生成ID能够按照时间有序生成
2、snowflake算法生成ID的结果是一个64bit大小的整数，为一个Long类型(转换成字符串后长度最多19位)
3、分布式系统内部不会产生ID碰撞，(datacenter和workerld作区分)并且效率较高
前述
现在的服务基本是分布式、微服务形式的，而且大数据量也导致分库分表的产生，对于水平分表就需要保证表中 id 的全局唯一性。
对于 MySQL 而言，一个表中的主键 id 一般使用自增的方式，但是如果进行水平分表之后，多个表中会生成重复的 id 值。那么如何保证水平分表后的多张表中的 id 是全局唯一性的呢？
如果还是借助数据库主键自增的形式，那么可以让不同表初始化一个不同的初始值，然后按指定的步长进行自增。例如有3张拆分表，初始主键值为1，2，3，自增步长为3。
当然也有人使用 UUID 来作为主键，但是 UUID 生成的是一个无序的字符串，对于 MySQL 推荐使用增长的数值类型值作为主键来说不适合。
也可以使用 Redis 的自增原子性来生成唯一 id，但是这种方式业内比较少用。
当然还有其他解决方案，不同互联网公司也有自己内部的实现方案。雪花算法是其中一个用于解决分布式 id 的高效方案，也是许多互联网公司在推荐使用的。
在分布式系统的中，有一些需要使用全局唯一ID的场景，生成ID的基本要求
1、在分布式的环境下必须全局且唯一。
2、一般都需要单调递增，因为一般唯一性ID都会存储到数据库，而Innodb内核的MySQL数据库就是将内容存储到逐渐索引树上的叶子结点，而且是从左到右递增，所以考虑到数据库的性能，一般生成的ID最好是单调递增；为了放着ID冲突可以使用36位的UUID，但是UUID有很明显的缺点，首先它相对比较长，另外一般是无序的。
3、可能还会需要无规则，因为如果使用唯一ID作为订单号，这种情况会被别人知道一天的订单量，所有此时就需要ID是无规则的。
原理
雪花算法的原理
雪花算法的原理就是生成一个的 64 位比特位的 long 类型的唯一 id。
- 最高 1 位固定值 0，因为生成的 id 是正整数，如果是 1 就是负数了。
- 接下来 41 位存储毫秒级时间戳，2^41/(1000606024365)=69，大概可以使用 69 年。
- 再接下 10 位存储机器码，包括 5 位 datacenterId 和 5 位 workerId。最多可以部署 2^10=1024 台机器。
- 最后 12 位存储序列号。同一毫秒时间戳时，通过这个递增的序列号来区分。即对于同一台机器而言，同一毫秒时间戳下，可以生成 2^12=4096 个不重复 id。
可以将雪花算法作为一个单独的服务进行部署，然后需要全局唯一 id 的系统，请求雪花算法服务获取 id 即可。
对于每一个雪花算法服务，需要先指定 10 位的机器码，这个根据自身业务进行设定即可。例如机房号+机器号，机器号+服务号，或者是其他可区别标识的 10 位比特位的整数值都行。
优缺点
优点
- 高性能高可用：高并发分布式环境下生成不重复 id，每秒可生成百万个不重复 id。
- ID有序自增：基于时间戳，以及同一时间戳下序列号自增，基本保证 id 有序递增。
- 无耦合性：不依赖第三方库或者中间件。
- 内存级算法：算法简单，在内存中进行，效率高。
缺点
雪花算法严重依赖时间，所以当发生服务器时钟回拨的问题是会导致可能产生重复的id。当然几乎没有公司会修改服务器时间，修改以后会导致各种问题，公司宁愿新加一台服务器也不愿意修改服务器时间，但是不排除特殊情况。
如何解决时钟回拨的问题？可以对序列化的初始值设置步长，每次触发时钟回拨事件，则其初始步长就加1w，可以在下面代码的第85行来实现，将sequence的初始值设置为10000。
代码实现
/**
* 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===========================================
/** 工作机器ID(0~31) */
private long workerId;
/** 数据中心ID(0~31) */
private long datacenterId;
/** 毫秒内序列(0~4095) */
private long sequence = 0L;
/** 上次生成ID的时间截 */
private long lastTimestamp = -1L;
/** 开始时间截 (2020-01-01) */
private final long twepoch = 1577808000000L;
/** 机器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);
//==============================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 < 100; i++) {
long id = idWorker.nextId();
System.out.println(id);
}
}
}
扩展
唯一ID可以标识数据的唯一性，在分布式系统中生成唯一ID的方案有很多，常见的方式大概有以下四种：
- 依赖数据库，使用如MySQL自增列或Oracle序列等。
- UUID随机数
- snowflake雪花算法
- Redis 的自增原子性来生成唯一 id
采用数据库自增序列
读写分离时，只有主节点可以进行写操作，可能有单点故障的风险分表分库，数据迁移合并等比较麻烦。
Redis 的自增原子性来生成唯一 id
Redis生成唯一ID，需要搭建集群；所有不能因为一个人，而要建一个厂，成本太高。
