雪花算法

为什么要使用雪花算法？？？

首先 数据库的主键采用自增是不好的 因为如果遇到分库分表 就会出现多条数据主键id一致的问题

那么这个时候我们就会想到UUID 来保证主键的随机性 但这时候就又会碰到两个问题

聚集索引的B+树的叶子节点是有序的 如果使用了UUID作为主键 因为她是无序的 每次插入都有可能插入到任意位置的叶子节点 那么B+树就会在每次插入时进行重排序 如果页满了 还会导致页分类 降低性能我们如果采用UUID作为主键 就会导致占用的空间比较大 而导致存储同样大小的数据需要更多的Page 最后导致索引树高度变高 增加磁盘IO 降低性能

雪花算法结构

第一部分：1个bit0 固定的 没有什么意义

第二部分：41个bit 表示当前时间戳

表示毫秒级的时间 能保证在69年不重复(时钟不回滚的情况下)

第三部分：10个bit 表示工作机器id

该工作机器id又可分为5bit的数据中心id与5bit的机器id(不重要)

第四部分：12个bit 表示自增序列号(同一毫秒内生成了几个id 从0开始往后排)

每毫秒每台机器可以生成4095个不重复id

雪花算法实现

/**

* 雪花算法 ID 生成器（Spring Boot 工具类）

* 生成趋势递增的唯一 Long 型 ID

*/

@Component

public class SnowflakeIdGenerator {

// ======================= 配置参数 =======================

private static final int TIMESTAMP_BITS = 41; // 时间戳占用的位数

private static final int DATA_CENTER_ID_BITS = 5; // 数据中心占用的位数

private static final int MACHINE_ID_BITS = 5; // 机器id占用的位数

private static final int SEQUENCE_BITS = 12; // 序列号占用的位数

private static final int MACHINE_ID_SHIFT = SEQUENCE_BITS; // 机器id左移位数

private static final int DATA_CENTER_ID_SHIFT = SEQUENCE_BITS + MACHINE_ID_BITS; // 数据中心id左移位数

private static final int TIMESTAMP_SHIFT = SEQUENCE_BITS + MACHINE_ID_BITS + DATA_CENTER_ID_BITS; // 时间戳左移位数

private static final long MAX_DATA_CENTER_ID = ~(-1L << DATA_CENTER_ID_BITS); // 数据中心id最大值31

private static final long MAX_MACHINE_ID = ~(-1L << MACHINE_ID_BITS); // 机器id最大值31

private static final long MAX_SEQUENCE = ~(-1L << SEQUENCE_BITS); // 序列号最大值4095

// 自定义纪元时间（毫秒）：2020-01-01 00:00:00 UTC

// 也就是从自定义的这里计算时间戳

private static final long EPOCH = 1577836800000L;

// ======================= 实例变量 =======================

private final long dataCenterId; // 数据中心id

private final long machineId; // 机器id

private long lastTimestamp = -1L; // 上一次时间戳

private long sequence = 0L; // 序列号

// 构造函数构造机器id 并做权限校验

@Autowired

public SnowflakeIdGenerator(SnowflakeProperties snowflakeProperties) {

if (snowflakeProperties.getDatacenterId() > MAX_DATA_CENTER_ID || snowflakeProperties.getDatacenterId() < 0) {

throw new IllegalArgumentException("dataCenterId必须在0到" + MAX_DATA_CENTER_ID);

}

if (snowflakeProperties.getMachineId() > MAX_MACHINE_ID || snowflakeProperties.getMachineId() < 0) {

throw new IllegalArgumentException("machineId必须在0到" + MAX_MACHINE_ID);

}

this.dataCenterId = snowflakeProperties.getDatacenterId();

this.machineId = snowflakeProperties.getMachineId();

}

// ======================= 核心方法 =======================

@Bean

public synchronized long nextId() {

// 首先获取当前时间戳

long timestamp = timeGen();

// 当前时间戳如果小于上一次生成ID的时间戳，说明系统时钟回退过 这个时候应当抛出异常

if (timestamp < lastTimestamp) {

throw new RuntimeException("时钟回退！！！");

}

// 当前时间戳如果等于上一次生成ID的时间戳 处理同一毫秒内的多次请求（序列号递增）

if (timestamp == lastTimestamp) {

// 序列号递增 最多能达到4095 如果再递增到4096 就会清0

sequence = (sequence + 1) & MAX_SEQUENCE;

// 序列号清0后 调用tilNextMillis方法 等待下一毫秒生成时间戳

if (sequence == 0) {

timestamp = tilNextMillis(lastTimestamp);

}

// 当前时间戳不等于上一次生成id的时间戳 说明时间前进了 此时可以重新开始计数 所以把sequence重置为0

} else {

sequence = 0L;

}

// 记录这次生成id生成的时间戳

lastTimestamp = timestamp;

// 组合并返回最终id

return ((timestamp - EPOCH) << TIMESTAMP_SHIFT) |

(dataCenterId << DATA_CENTER_ID_SHIFT) |

(machineId << MACHINE_ID_SHIFT) |

sequence;

}

// 一直获取新的时间戳直到进入下一毫秒

protected long tilNextMillis(long lastTimestamp) {

long timestamp = timeGen();

while (timestamp <= lastTimestamp) {

timestamp = timeGen();

}

return timestamp;

}

protected long timeGen() {

return System.currentTimeMillis();

}

}

SnowflakeProperties：用于从配置文件中获取机器id

@ConfigurationProperties(prefix = "snowflake")

@Configuration

@Data

public class SnowflakeProperties {

private Long machineId = 1L; // 默认值

private Long datacenterId = 1L; // 默认值

}

雪花算法出现的问题

时间回退

雪花算法依赖机器时间 如果系统时间发生更改(改成过去的时间) 就会导致id不是趋势递增的了 甚至导致id重复

解决这个问题很简单 如果监测到当前时间戳 < 上一次的时间戳 直接报错

机器id(回来再讲)

序列号大幅为0(只在并发量不高的情况下会出现)

因为并发量不高 所以每次生成新的id都会是新的时间戳 那么就会导致序列号一直是0 但如果在未来我们要取模进行分库分表时怎么办呢 会导致严重的数据偏移(偶数表中有数据 奇数表中没有数据)

为了解决这个问题我们可以修改一行代码(TODO位置)：我们在判断上一次时间戳与当前时间戳不同后 不把序列号设置为0 而是设置成当前时间戳的最后一位 因为当前时间戳是一直在变的 所以就不用担心一直是0的问题了

// 当前时间戳如果等于上一次生成ID的时间戳 处理同一毫秒内的多次请求（序列号递增）

if (timestamp == lastTimestamp) {

// 序列号递增 最多能达到4095 如果再递增到4096 就会清0

sequence = (sequence + 1) & MAX_SEQUENCE;

// 序列号清0后 调用tilNextMillis方法 等待下一毫秒生成时间戳

if (sequence == 0) {

timestamp = tilNextMillis(lastTimestamp);

}

// 当前时间戳不等于上一次生成id的时间戳 说明时间前进了 此时可以重新开始计数 所以把sequence重置为0

} else {

// TODO

sequence = timestamp & 1;

}