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

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

文章共2,144字 · 阅读需要大约8分钟

一键AI生成摘要，助你高效阅读

问答

一叶飘零_sweet_

4923人浏览 · 2023-06-08 14:40:06

一叶飘零_sweet_ · 2023-06-08 14:40:06 发布

在分布式系统中，唯一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的过程包括以下几个步骤：

获取当前时间戳，精确到毫秒级别。
判断当前时间戳是否小于上次生成ID的时间戳，如果是，则说明系统时钟回退过，需要等待时钟追上来。
如果是同一毫秒内生成的ID，则需要增加序列号，否则序列号重置为0。
将时间戳、数据中心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生成方案，具有以下优缺点：

优点

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

缺点

依赖时钟：雪花算法的实现依赖于系统时钟的准确性，如果系统时钟回退或者发生了跳跃，会导致生成的ID不唯一。
数据中心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的场景。

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