分布式ID生成系统之雪花算法详解

修己xj

发布于 2024-03-04 11:45:09

4840

发布于 2024-03-04 11:45:09

文章被收录于专栏：修己xj

在当今的云计算和微服务架构盛行的时代，分布式系统已成为软件开发的重要组成部分。随着系统规模的扩大和业务的复杂化，对数据一致性和唯一性的要求也越来越高，尤其是在全局唯一标识符（ID）的生成上。因此，分布式ID生成系统应运而生，成为保证数据唯一性和提高系统可扩展性的关键技术之一。雪花算法（Snowflake）是Twitter开源的一种算法，用于生成64位的全局唯一ID，非常适用于分布式系统中生成唯一标识符。下面我们将深入探讨雪花算法的原理、结构和实现方式。

分布式ID的需求背景

在单体应用中，生成唯一ID相对简单，如数据库的自增ID、UUID等方法可以轻易满足需求。然而，在分布式系统中，由于数据可能分布在不同的节点上，传统的ID生成方法面临着多方面的挑战：

高可用性：系统任何一个部分的故障都不能影响ID的生成和使用。
高并发：在大规模并发的场景下，ID生成系统必须能够快速响应。
有序性：在某些业务场景中，需要ID具有一定的可排序性，以便于后续处理。
低延迟：ID生成的延迟必须足够低，以满足实时性要求。

推特的雪花系统

Twitter开源的Snowflake算法是目前最流行的分布式ID生成方案之一。它通过结合时间戳、机器标识和序列号来生成64位的长整型ID，既保证了全局唯一性，又具有良好的有序性，非常适合高并发的场景。

如下展示了一个64为ID的构成：

每个部分的含义如下：

符号位（1位）始终为0，预留位，将来有可能用来区分有符号数和无符号数。
时间戳（41位）它是纪元或者自定义纪元开始以来的毫秒数，Snowflake使用的是2010-11-04 01:42:54 的时间戳作为默认纪元的，我们也可以自定义。即时间戳为当前时间的毫秒数 - 自定义的纪元的毫秒数。
数据中心id(5位) 最多可以有个数据中心，取值范围为 0~31。
机器id(5位) 最多可以有台机器，取值范围为 0~31。
序列号（12位）对于某个服务，每一个毫秒内生成一个id,序列号就加1，这个数字在每毫秒开始时都会被重置为0。即一个毫秒内单个服务可以生成即4096个id。我们可以根据服务的具体情况调整下id各部分的长度，比如，对于并发量低，单次生成id数量大的应用，我们可以适当减少数据中心id和机器id的位数，增加序列号位数来提高每个毫秒内id的生成数量。

Java实现雪花雪花系统

使用Java语言实现雪花算法的ID生成器，可以参考以下代码。这个实现同样遵循了雪花算法的基本结构，包括1位符号位、41位时间戳、10位机器标识（5位数据中心ID和5位工作机器ID）以及12位序列号。我们将这些位数放在了配置文件中，家人们可以根据实际情况进行调整。在这个代码中，我们提供了单id生成接口和批量id生成接口。代码如下：

配置信息 application.yml

server:
  port: 8000

snowflake:
  #数据中心id位数
  datacenterBits: 5
  # 机器id位数
  workerBits: 5
  # 序列id所占位数
  sequenceBits: 12
  # 数据中心id,范围0-2^5-1
  datacenterId: 1
  # 机器id,范围0-2^5-1
  workerId: 1
  # 时间戳起始点（2024-01-01 00::00:00 的毫秒数）
  twepoch: 1704038400000
  #单次批量生成id的最大数量  默认10万
  maxBatchCount: 100000

SnowflakeProperties

import lombok.Data;
import org.springframework.boot.context.properties.ConfigurationProperties;
import org.springframework.stereotype.Component;

@Component
@ConfigurationProperties(prefix ="snowflake")
@Data
public class SnowflakeProperties {
    //数据中心id
    private Long datacenterId;
    //数据中心id位数
    private Long datacenterBits;
    //机器id
    private Long workerId;
    //机器id位数
    private Long workerBits;
    //序列id所占位数
    private Long sequenceBits;
    // 时间戳起始点（毫秒）
    private  Long twepoch;
    //单次批量生成id的最大数量
    private Integer maxBatchCount;
}

SnowflakeIdGenerator

package cn.xj.snowflake.generator;


import cn.xj.snowflake.config.SnowflakeProperties;
import org.springframework.stereotype.Component;

import java.util.ArrayList;
import java.util.List;

@Component
public class SnowflakeIdGenerator {


    //数据中心id
    private final long datacenterId;
    //数据中心id位数
    private final long datacenterBits;
    //机器id
    private final long workerId;
    //机器id位数
    private final long workerBits;
    //序列id所占位数
    private final  long sequenceBits;
    // 时间戳起始点（毫秒）
    private final long twepoch;

    //数据中心最大id
    private final long maxDatacenterId;
    //机器最大id
    private final long maxWorkerId;
    //最大序列号
    private final long maxSequence;

    //机器id左移位数
    private final long workerIdShift;
    //数据中心id左移位数
    private final long datacenterIdShift;
    //毫秒数左移位数
    private final long timestampLeftShift;

    //单次批量生成id的最大数量
    private final int maxBatchCount;

    // 序列号
    private long sequence = 0L;
    // 上一次时间戳
    private long lastTimestamp = -1L;

    public SnowflakeIdGenerator(SnowflakeProperties properties) {
        //数据中心id
        this.datacenterId = properties.getDatacenterId();
        //数据中心id位数
        this.datacenterBits = properties.getDatacenterBits();
        //机器id
        this.workerId = properties.getWorkerId();
        //机器id位数
        this.workerBits = properties.getWorkerBits();
        //序列id所占位数
        this.sequenceBits = properties.getSequenceBits();
        // 时间戳起始点（毫秒）
        this.twepoch = properties.getTwepoch();
        //数据中心最大id
        this.maxDatacenterId = -1L ^ (-1L << properties.getDatacenterBits());
        //机器最大id
        this.maxWorkerId = -1L ^ (-1L << properties.getWorkerBits());
        //最大序列号
        this.maxSequence = -1L ^ (-1L << properties.getSequenceBits());

        this.workerIdShift = properties.getSequenceBits();
        //数据中心id左移位数
        this.datacenterIdShift = properties.getSequenceBits() + properties.getWorkerBits();
        //毫秒数左移位数
        this.timestampLeftShift = properties.getSequenceBits() + properties.getWorkerBits() + properties.getSequenceBits();
        //单次批量生成id的最大数量
        this.maxBatchCount = properties.getMaxBatchCount();


        // 校验datacenterId和workerId是否超出最大值
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("数据中心Id不能大于%d或小于0", maxDatacenterId));
        }
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("机器Id不能大于%d或小于0", maxWorkerId));
        }
    }



    /**
     * id生成方法(单个)
     * @return
     */
    public synchronized long nextId() {
        //获取当前时间的毫秒数
        long timestamp = currentTime();

        //判断时钟是否回拨
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(String.format("时钟回拨，回拨毫秒数：%d", lastTimestamp - timestamp));
        }

        //设置序列号
        if (lastTimestamp == timestamp) {
            //设置序列号递增，如果当前毫秒内序列号已经达到最大值，则直到下一毫秒在重新从0开始计算序列号
            sequence = (sequence + 1) & maxSequence;
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }

        lastTimestamp = timestamp;

        //计算id
        return ((timestamp - twepoch) << timestampLeftShift) |
                (datacenterId << datacenterIdShift) |
                (workerId << workerIdShift) |
                sequence;
    }


    /**
     * id生成方法(批量)
     * @return
     */
    public synchronized List<Long> nextIds(int count) {
        if (count > maxBatchCount || count < 0) {
            throw new IllegalArgumentException(String.format("批量生成id的数量不能大于%d或小于0", maxBatchCount));
        }

        List<Long> ids = new ArrayList<>(count);
        for (int i = 0; i < count; i++) {
            ids.add(nextId());
        }
        return ids;
    }

    /**
     * 循环等待直至获取到新的毫秒时间戳
     * 确保生成的时间戳总是向前移动的，即使在相同的毫秒内请求多个ID时也能保持唯一性。
     */
    private long tilNextMillis(long lastTimestamp) {
        long timestamp = currentTime();
        // 循环等待直至获取到新的毫秒时间戳
        while (timestamp <= lastTimestamp) {
            timestamp = currentTime();
        }
        return timestamp;
    }

    /**
     * 获取当前时间的毫秒数
     */
    private long currentTime() {
        return System.currentTimeMillis();
    }

}

这个Java类SnowflakeIdWorker封装了雪花算法的核心逻辑。它允许通过构造函数指定数据中心ID和机器ID，并提供了nextId()和nextIds()方法用于生成唯一的ID。该方法通过同步关键字synchronized保证了线程安全。

SnowflakeApi


import cn.xj.snowflake.generator.SnowflakeIdGenerator;
import jakarta.annotation.Resource;
import org.springframework.web.bind.annotation.PostMapping;
import org.springframework.web.bind.annotation.RequestBody;
import org.springframework.web.bind.annotation.RestController;

import java.util.List;

@RestController
public class SnowflakeApi {


    @Resource
    private SnowflakeIdGenerator snowflakeIdGenerator;

    @PostMapping("/snowflake/api/nextId")
    public Long nextId(){
        return snowflakeIdGenerator.nextId();
    }

    @PostMapping("/snowflake/api/nextIds")
    public List<Long> nextIds(@RequestBody int count){
        return snowflakeIdGenerator.nextIds(count);
    }
}

接口调用详情

单个id生成接口nextId:

批量id生成接口nextIds:我们此处生成了10万条id,响应时长不到1s

雪花算法的开源代码或者优秀代码示例有很多，但思想基本是一样的。这有篇美团的文章，大家也可以参考下美团的leaf [Leaf——美团点评分布式ID生成系统： https://tech.meituan.com/2017/04/21/mt-leaf.html](https://tech.meituan.com/2017/04/21/mt-leaf.html)