雪花算法：分布式ID生成器

短命女 2024-03-16 14:57 45阅读 0赞

在分布式系统中，唯一ID的生成是一个非常重要的问题。传统的自增ID或UUID等方式都存在一些问题，比如自增ID在分布式系统中无法保证唯一性，而UUID虽然保证唯一性，但是过长的长度也带来了一些不便。而雪花算法则是一个解决这个问题的方案。

### 什么是雪花算法 ###

雪花算法是Twitter开源的分布式ID生成算法，它可以生成一个长度为64位的唯一ID，其中包含了时间戳、数据中心ID和机器ID等信息。雪花算法的核心思想是利用时间戳和机器ID生成一个唯一的序列号，从而保证生成的ID的唯一性。

### 雪花算法的结构 ###

雪花算法生成的ID包含了以下几个部分：

*  符号位：1位，固定为0，表示正数。
 *  时间戳：41位，精确到毫秒级别，可以使用69年。
 *  数据中心ID：5位，可以部署32个数据中心。
 *  机器ID：5位，可以部署32台机器。
 *  序列号：12位，每毫秒可以生成4096个ID。

下面是一个雪花算法生成的ID的二进制表示：

0 0001100 101000011010110011101111110011 10000 00001 000000000000

其中，第一位是符号位，固定为0；接下来的41位是时间戳，表示生成ID的时间；然后是5位数据中心ID和5位机器ID，用于标识生成ID的机器；最后是12位序列号，用于保证同一毫秒内生成的ID的唯一性。

### 雪花算法的实现 ###

雪花算法的实现比较简单，主要分为两个部分：生成ID和解析ID。

#### 生成ID ####

生成ID的过程包括以下几个步骤：

1.  获取当前时间戳，精确到毫秒级别。
2.  判断当前时间戳是否小于上次生成ID的时间戳，如果是，则说明系统时钟回退过，需要等待时钟追上来。
3.  如果是同一毫秒内生成的ID，则需要增加序列号，否则序列号重置为0。
4.  将时间戳、数据中心ID、机器ID和序列号按照规定的位数组合成一个64位的ID。

下面是一个Java实现的示例代码：

public class SnowflakeIdGenerator {
        // 起始的时间戳
        private final static long START_TIMESTAMP = 1623175200000L; // 2021-06-09 00:00:00
    
        // 每一部分占用的位数
        private final static long SEQUENCE_BIT = 12; // 序列号占用的位数
        private final static long MACHINE_BIT = 5; // 机器标识占用的位数
        private final static long DATACENTER_BIT = 5; // 数据中心占用的位数
    
        // 每一部分的最大值
        private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
        private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
        private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
    
        // 每一部分向左的位移
        private final static long MACHINE_LEFT = SEQUENCE_BIT;
        private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
        private final static long TIMESTAMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;
    
        private long datacenterId; // 数据中心ID
        private long machineId; // 机器ID
        private long sequence = 0L; // 序列号
        private long lastTimestamp = -1L; // 上次生成ID的时间戳
    
        public SnowflakeIdGenerator(long datacenterId, long machineId) {
            if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
                throw new IllegalArgumentException("Datacenter ID can't be greater than " + MAX_DATACENTER_NUM + " or less than 0");
            }
            if (machineId > MAX_MACHINE_NUM || machineId < 0) {
                throw new IllegalArgumentException("Machine ID can't be greater than " + MAX_MACHINE_NUM + " or less than 0");
            }
            this.datacenterId = datacenterId;
            this.machineId = machineId;
        }
    
        public synchronized long nextId() {
            long timestamp = timeGen();
    
            if (timestamp < lastTimestamp) {
                throw new RuntimeException("Clock moved backwards. Refusing to generate id");
            }
    
            if (timestamp == lastTimestamp) {
                sequence = (sequence + 1) & MAX_SEQUENCE;
                if (sequence == 0) {
                    timestamp = tilNextMillis(lastTimestamp);
                }
            } else {
                sequence = 0L;
            }
    
            lastTimestamp = timestamp;
    
            return ((timestamp - START_TIMESTAMP) << TIMESTAMP_LEFT) |
                    (datacenterId << DATACENTER_LEFT) |
                    (machineId << MACHINE_LEFT) |
                    sequence;
        }
    
        private long tilNextMillis(long lastTimestamp) {
            long timestamp = timeGen();
            while (timestamp <= lastTimestamp) {
                timestamp = timeGen();
            }
            return timestamp;
        }
    
        private long timeGen() {
            return System.currentTimeMillis();
        }
    }

#### 解析ID ####

解析ID的过程比较简单，只需要将ID转换为二进制表示，然后按照规定的位数拆分成各个部分即可。下面是一个Java实现的示例代码：

public class SnowflakeIdParser {
        // 每一部分占用的位数
        private final static long SEQUENCE_BIT = 12; // 序列号占用的位数
        private final static long MACHINE_BIT = 5; // 机器标识占用的位数
        private final static long DATACENTER_BIT = 5; // 数据中心占用的位数
    
        // 每一部分的最大值
        private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
        private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
        private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
    
        // 每一部分向左的位移
        private final static long MACHINE_LEFT = SEQUENCE_BIT;
        private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
        private final static long TIMESTAMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;
    
        public static Map<String, Long> parse(long id) {
            String binaryId = Long.toBinaryString(id);
            binaryId = String.format("%64s", binaryId).replace(' ', '0');
    
            Map<String, Long> result = new HashMap<>();
            result.put("timestamp", Long.parseLong(binaryId.substring(0, 41), 2) + START_TIMESTAMP);
            result.put("datacenterId", Long.parseLong(binaryId.substring(41, 46), 2));
            result.put("machineId", Long.parseLong(binaryId.substring(46, 51), 2));
            result.put("sequence", Long.parseLong(binaryId.substring(51), 2));
    
            return result;
        }
    }

### 雪花算法的优缺点 ###

雪花算法作为一种分布式ID生成方案，具有以下优缺点：

#### 优点 ####

1.  唯一性：雪花算法生成的ID是唯一的，可以满足分布式系统中唯一ID的需求。
2.  时间戳有序：雪花算法生成的ID包含了时间戳，可以根据ID的大小来判断生成ID的时间顺序。
3.  高性能：雪花算法的实现简单，生成ID的速度非常快。

#### 缺点 ####

1.  依赖时钟：雪花算法的实现依赖于系统时钟的准确性，如果系统时钟回退或者发生了跳跃，会导致生成的ID不唯一。
2.  数据中心ID和机器ID需要手动分配：雪花算法需要手动分配数据中心ID和机器ID，如果分配不当或者出现了故障，会导致生成的ID不唯一。

### 使用场景 ###

雪花算法适用于需要在分布式系统中生成唯一ID的场景，比如订单号、用户ID等。由于雪花算法生成的ID是有序的，可以根据ID的大小来判断生成ID的时间顺序，因此也适用于需要按照时间顺序进行排序的场景。

#### 在MyBatis中使用雪花算法生成自增主键 ####

在MyBatis中使用雪花算法生成自增主键比较简单，我们只需要在插入数据时手动设置ID即可。以下是一个示例：

public interface UserMapper {
        @Insert("INSERT INTO user(id, name) VALUES(#{id}, #{name})")
        void insert(User user);
    }
    
    public class UserService {
        private UserMapper userMapper;
    
        public void addUser(User user) {
            user.setId(SnowflakeIdGenerator.nextId());
            userMapper.insert(user);
        }
    }

这段代码中，我们手动设置了User对象的ID，然后调用`userMapper.insert(user)`方法插入数据。MyBatis会自动将ID设置为自增主键。

#### 在MyBatis Plus中使用雪花算法生成自增主键 ####

在MyBatis Plus中使用雪花算法生成自增主键也比较简单，我们只需要定义一个实体类，并在主键字段上添加`@TableId`注解即可。以下是一个示例：

@Data
    public class User {
        @TableId(type = IdType.INPUT)
        private Long id;
        private String name;
    }
    
    public class UserService {
        private UserServiceMapper userServiceMapper;
    
        public void addUser(User user) {
            user.setId(SnowflakeIdGenerator.nextId());
            userServiceMapper.insert(user);
        }
    }

这段代码中，我们定义了一个User实体类，并在主键字段上添加了`@TableId`注解。在插入数据时，我们手动设置了ID，并调用`userServiceMapper.insert(user)`方法插入数据。MyBatis Plus会自动将ID设置为自增主键。

**补充:**

MybatisPlus 的主键策略 ASSIGN\_ID 是指手动指定主键，而不是自动生成主键。如果你想要使用自增主键，可以将主键策略配置为 IDENTITY，然后在数据库中将主键设置为自增即可。

具体来说，你可以在实体类中使用 @TableId 注解指定主键，并将其设置为 IDENTITY，如下所示：

@TableId(type = IdType.AUTO)
    private Long id;

这样，当你插入一条新的数据时，数据库会自动生成一个主键，并将其赋值给实体类中的 id 属性。注意，这需要数据库支持自增主键功能，例如 MySQL 中的 AUTO\_INCREMENT。

### 总结 ###

雪花算法是一种分布式ID生成方案，它可以生成一个长度为64位的唯一ID，其中包含了时间戳、数据中心ID和机器ID等信息。雪花算法的核心思想是利用时间戳和机器ID生成一个唯一的序列号，从而保证生成的ID的唯一性。雪花算法的优点包括唯一性、时间戳有序和高性能，缺点包括依赖时钟和数据中心ID和机器ID需要手动分配。雪花算法适用于需要在分布式系统中生成唯一ID的场景。

**公众号请关注 "果酱桑", 一起学习,一起进步!**