当前位置：首页 > news >正文

分布式ID生成方案之雪花算法

news 来源：原创 2024/9/30 5:35:09

前言

1、什么是分布式ID?

2、雪花算法结构

3、雪花算法的优势

4、雪花算法的实现

5、总结

前言

当我首次接触到这个算法时，便被其富有诗意的名字所吸引。雪花，亦称未央花,"未央"意味着永恒与无限，象征着希望与未来，代表着光明与前行的道路。言归正传,自然界中存在一种现象：据说不存在两片完全相同的雪花，每一片在形成时都会展现出其独特的形态与纹路。雪花算法这个名字，象征该算法能生成一个全局唯一且不重复的标识符。

1、什么是分布式ID?

在分布式系统中，数据一般都被分散存储在不同的节点上，由于数据被分散存储在不同的节点上，为了确保每个数据项的唯一性，就需要这样一套机制来生成不会重复的ID。这个不会重复的ID就是分布式ID。

分布式ID不仅仅是一个简单的数字序列，它还涉及到多个维度的需求和特性，主要包括：

全局唯一性：这是最基本也是最重要的要求，确保在分布式系统中产生的每一个ID都是独一无二的。
高性能：在高并发场景下，ID生成服务需要快速响应，减少生成ID的延迟，不影响系统的整体性能。
高可用性：ID生成服务需要设计成高可用的，即使部分组件发生故障，也能确保ID的正常生成，不影响业务连续性。
趋势递增（非严格要求）：在某些场景下，如数据库索引优化，可能需要生成的ID具有趋势递增的特性，以便提升数据库插入性能。
安全性：虽然不是所有场景都需要，但在一些敏感或有特殊要求的系统中，ID的生成还应考虑信息安全性，避免通过ID泄露系统敏感信息。

常见的分布式ID生成策略有Snowflake算法（就是我们今天的主角）、基于数据库的生成方式、基于Zookeeper或Redis等中间件的方案，以及使用UUID等。

接下来我们就一起解开雪花算法的面纱吧。

2、雪花算法结构

雪花算法是Twitter开源的分布式ID生成算法，其生成的ID是一个64位的长整型数字。每个ID按时间顺序生成，并保证在分布式系统中的唯一性。雪花算法生成的ID结构如下：

| 1位符号位 | 41位时间戳 | 10位机器ID | 12位序列号 |

1位符号位：固定为0，表示生成的ID为正数。
41位时间戳：以毫秒为单位的时间戳，表示从某个固定时间（Twitter Epoch）起的毫秒数，41位可以表示69年的时间。
10位机器ID：用来表示不同的机器，5位数据中心ID和5位机器ID，最多支持1024个节点。
12位序列号：同一毫秒内生成的不同ID的序列号，最多支持每毫秒产生4096个不同的ID。

3、雪花算法的优势

高效性：雪花算法在本地生成ID，不需要依赖数据库等外部系统，生成速度极快。
全局唯一性：通过时间戳、机器ID和序列号的组合，保证了ID的唯一性。
有序性：生成的ID大致按照时间顺序排列，方便数据的排序和查询。
分布式支持：支持大规模分布式系统，每秒可以生成大量唯一ID。

4、雪花算法的实现

public class SnowflakeIdWorker {// 起始时间戳（2020-01-01）private final long twepoch = 1577836800000L;// 机器ID所占的位数private final long workerIdBits = 5L;private final long datacenterIdBits = 5L;// 支持的最大机器IDprivate final long maxWorkerId = -1L ^ (-1L << workerIdBits);private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);// 序列号所占的位数private final long sequenceBits = 12L;// 机器ID左移位数private final long workerIdShift = sequenceBits;private final long datacenterIdShift = sequenceBits + workerIdBits;private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;// 序列号掩码private final long sequenceMask = -1L ^ (-1L << sequenceBits);private long workerId;private long datacenterId;private long sequence = 0L;private long lastTimestamp = -1L;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;}public synchronized long nextId() {long timestamp = timeGen();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;}lastTimestamp = timestamp;return ((timestamp - twepoch) << timestampLeftShift) |(datacenterId << datacenterIdShift) |(workerId << workerIdShift) |sequence;}protected long tilNextMillis(long lastTimestamp) {long timestamp = timeGen();while (timestamp <= lastTimestamp) {timestamp = timeGen();}return timestamp;}protected long timeGen() {return System.currentTimeMillis();}
}