每日一问：今天我们来聊聊什么是雪花算法？

雪花算法（Snowflake Algorithm）是由Twitter公司开发的一种分布式ID ......

微信号：

联系QQ：

175

热度

其他信息

行业：网站开发
地区：未知
时间：2024-08-30
标签：

0次点赞
0个收藏

上一篇：吃了鱼大脑会罢工？还会危及生命？原来是它们下一篇：200-300价位喝什么酒？这10款酱香白酒，闭眼入不会错（建议保存）

内容详情

雪花算法（Snowflake Algorithm）是由Twitter公司开发的一种分布式ID生成算法。它的主要目的是在分布式环境中生成唯一、有序、可排序的ID。雪花算法生成的ID是一个64位的整数，按照时间戳、机器标识和序列号三部分来划分，确保了ID的唯一性和全局唯一性。

雪花算法的组成部分

64位的ID组成如下：

符号位：1位，始终为0，表示正数。

时间戳：41位，用来记录时间戳，可以精确到毫秒级别，可以使用约69年。

工作机器ID：5位，用来标识不同的工作机器，最大支持31（2^5-1）个工作机器。

数据中心ID：5位，用来标识不同的数据中心，最大支持31（2^5-1）个数据中心。

序列号：12位，用来在同一毫秒内生成的多个ID做自增计数，最大支持4095（2^12-1）个ID。

ID生成规则

时间戳：当前时间戳减去一个固定的起始时间戳（epoch），然后左移42位（时间戳位数加上序列号位数）。

数据中心ID：左移17位（序列号位数加上工作机器ID位数）。

工作机器ID：左移12位（序列号位数）。

序列号：保持原样。

最终的ID是上述四个部分的二进制位运算结果。

Java 实现示例

下面是一个简单的Java实现雪花算法的例子：

import java.util.concurrent.atomic.AtomicLong;

public class SnowFlake {
private static final long EPOCH = 1585644268888L; // 自定义的时间起点
private static final long WORKER_ID_BITS = 5L;
private static final long DATA_CENTER_ID_BITS = 5L;
private static final long SEQUENCE_BITS = 12L;

private static final long MAX_WORKER_ID = -1L ^ (-1L << WORKER_ID_BITS);
private static final long MAX_DATA_CENTER_ID = -1L ^ (-1L << DATA_CENTER_ID_BITS);

private static final long WORKER_ID_SHIFT = SEQUENCE_BITS;
private static final long DATA_CENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS;
private static final long TIMESTAMP_LEFT_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATA_CENTER_ID_BITS;

private static final long SEQUENCE_MASK = -1L ^ (-1L << SEQUENCE_BITS);

private AtomicLong lastTimestamp = new AtomicLong(-1L);
private long sequence = 0L;
private long workerId;
private long dataCenterId;

public SnowFlake(long workerId, long dataCenterId) {
if (workerId > MAX_WORKER_ID || workerId < 0) {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", MAX_WORKER_ID));
}
if (dataCenterId > MAX_DATA_CENTER_ID || dataCenterId < 0) {
throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", MAX_DATA_CENTER_ID));
}
this.workerId = workerId;
this.dataCenterId = dataCenterId;
}

public synchronized long nextId() {
long timestamp = timeGen();

// 如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过，此时应当抛出异常
if (timestamp < lastTimestamp.get()) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp.get() - timestamp));
}

// 如果是同一时间生成，则进行毫秒内序列
if (lastTimestamp.get() == timestamp) {
sequence = (sequence + 1) & SEQUENCE_MASK;
// 毫秒内序列溢出
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp.get());
}
} else { // 时间戳改变，毫秒内序列重置
sequence = 0;
}

// 上次生成ID的时间截
lastTimestamp.set(timestamp);

// 移位并通过或运算拼凑成最终的ID
return ((timestamp - EPOCH) << TIMESTAMP_LEFT_SHIFT)
| (dataCenterId << DATA_CENTER_ID_SHIFT)
| (workerId << WORKER_ID_SHIFT)
| sequence;
}

protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}

protected long timeGen() {
return System.currentTimeMillis();
}
}

使用示例

创建一个SnowFlake实例并生成ID：

public class Main {
public static void main(String[] args) {
SnowFlake snowFlake = new SnowFlake(1, 1); // 初始化数据中心ID和工作机器ID
for (int i = 0; i < 10; i++) {
System.out.println(snowFlake.nextId());
}
}
}

这段代码将生成10个唯一ID。

注意事项

时间戳回拨：如果系统时钟回拨（例如由于夏令时调整），会导致生成的ID出错。因此，在生产环境中，应确保系统时钟的稳定性。

序列号溢出：同一毫秒内生成的ID数量超过4095时，将阻塞直到下一毫秒。

参数设置：workerId和dataCenterId的设置应确保在不同的机器和数据中心中不会重复。

通过这种方式，雪花算法可以在分布式环境中生成唯一且有序的ID，适用于许多需要唯一标识符的场景。

雪花算法（Snowflake）是一种生成分布式唯一 ID 的算法。它可以在分布式系统中生成趋势递增的唯一 ID，并且具有高性能和高可用性。

一、雪花算法的原理

雪花算法生成的 ID 是一个 64 位的整数，其结构如下：

首位：符号位，固定为 0，表示正数。

接下来的 41 位：时间戳，表示生成 ID 的时间。时间戳的单位可以是毫秒或微秒，具体取决于系统的需求。通过时间戳可以保证生成的 ID 是趋势递增的。

再接下来的 10 位：工作机器 ID，表示生成 ID 的机器。在分布式系统中，可以通过配置不同的工作机器 ID 来区分不同的机器。