深度思考：雪花算法snowflake分布式id生成原理详解

2024-04-18 13:18:21

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

雪花算法snowflake是一种优秀的分布式ID生成方案，其优点突出：它能生成全局唯一且递增的ID，确保了数据的一致性和准确性；同时，该算法灵活性强，可自定义各部分bit位，满足不同业务场景的需求；此外，雪花算法生成ID的速度快，效率高，能有效应对高并发场景，是分布式系统中不可或缺的组件。

前言

分布式ID的基本特性

在分布式系统的复杂环境下，数据量的持续激增对数据库架构提出了新的挑战。

传统的垂直与水平分库分表策略虽然能有效应对数据存储和扩展的问题，但却引出了一个新的需求：需要一个全局唯一标识符（ID）来标定每条数据或消息队列（MQ）中的消息。

在这种情况下，依赖数据库自身的ID自增功能显然已经无法满足需求，因此，必须设计出符合以下要求的分布式ID生成策略：

1、全局唯一性，所生成的ID必须在全局范围内是独一无二的，以确保数据的精准标识，避免任何可能的ID冲突。

2、趋势递增，鉴于多数关系型数据库管理系统（RDBMS）如MySQL的InnoDB引擎使用B树结构来存储索引数据，并依赖聚集索引进行优化，最好择有序的ID以保证高效的写入性能，因此生成的ID应具备整体递增的趋势。

3、单调递增，在特定场景下，如分布式事务的版本控制、即时通讯的增量消息传递或数据排序等，需要确保每个新生成的ID都严格大于前一个ID，从而实现数据的线性顺序增长。

4、信息安全，针对某些敏感业务，如订单处理等，生成的分布式ID必须是无规则的，以防止外部通过解析ID获取到流量信息或其他商业机密，这就需要ID生成策略在保持唯一性和递增性的同时，还要具备足够的信息隐匿性。

分布式ID常见的算法

在分布ID生成的领域，目前市面上主要流行几种算法，这些算法也是众多开源项目进行优化和实现的基础：

1、UUID方式，UUID由于是在本地生成，因此具有极高的性能，然而，它生成的ID长度较长，达到16字节128位，通常需要使用字符串类型进行存储。

此外，UUID是无序的，这使得它在许多场景中并不适用，尤其是在作为MySQL数据库的主键和索引时。MySQL官方建议主键应尽可能短，而对于InnoDB引擎来说，索引的无序性可能会导致数据位置频繁变动，从而严重影响性能。

2、数据库自增ID方式，这种方法的缺点是每次获取ID都需要进行数据库IO操作，给数据库带来较大压力，且性能较低。如果数据库发生宕机，对依赖其服务的外部系统将是毁灭性的打击。

尽管可以通过部署数据库集群来提高可用性，但问题并未从根本上解决。

3、数据库号段算法，这是对数据库自增ID的一种优化方法。通过每次获取一个号段的值，可以大大减少与数据库的交互次数，从而显著降低数据库的压力。号段越长，性能越高。即使数据库发生宕机，只要号段未用完，系统仍能在短时间内继续提供服务。

美团的Leaf和滴滴的TinyId就是采用这种算法的典型例子。

4、雪花算法，Twitter开源的snowflake算法，以时间戳、机器标识和递增序列为基础生成ID。这种算法生成的ID基本呈趋势递增，且性能很高。然而，由于它强烈依赖于机器时钟，因此需要考虑时钟回拨问题。即当机器上的时间因校正而发生倒退时，可能会导致生成的ID重复。

目前，百度的uid-generator和美团的Leaf也都在使用或优化这种算法。

雪花算法snowflake

snowflake定义

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

Snowflake算法的原理相对直观，它负责生成一个64位（long型）的全局唯一ID，这个ID的构成包括：1位无用的符号位、41位的时间戳、10位的机器ID以及12位的序列号，除了固定的1位符号位之外，其余的三个部分都可以根据实际需求进行调整：

1、41位时间戳：这部分能够表示的时间跨度为（1L<<41）/(1000L*3600*24*365)，即大约69年。

2、10位机器ID：可以唯一标识最多1024台机器，如果需要对互联网数据中心（IDC）进行划分，可以将这10位拆分为两部分，例如各5位，这样，系统就能够表示最多32个IDC，且每个IDC下可以容纳32台机器。

3、12位自增序列号：用于在同一毫秒内生成多个ID，最多可以表示2^12个不同的ID，因此，理论上，Snowflake算法能够达到的每秒查询率（QPS）约为409.6万。

snowflake优缺点

优点：

  • 毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。
  • 可以不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也非常高。
  • 可以根据自身业务特性分配bit位，非常灵活。

缺点：

  • 强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务处于不可用状态。

Java代码实现snowflake

1、不考虑时间戳回拨


/**
 * Twitter_Snowflake<br>
 * SnowFlake的结构如下(每部分用-分开):<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
 * 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0<br>
 * 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)
 * 得到的值），这里的的开始时间截，一般是的id生成器开始使用的时间，由程序来指定的（如下下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
 * 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId<br>
 * 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号<br>
 * 加起来刚好64位，为一个Long型。<br>
 * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。
 */
public class SnowflakeIdWorkerV1 {

    // ==============================Fields===========================================
    /** 开始时间截 (2015-01-01) */
    private final long twepoch = 1420041600000L;

    /** 机器id所占的位数 */
    private final long workerIdBits = 5L;

    /** 数据标识id所占的位数 */
    private final long datacenterIdBits = 5L;

    /** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /** 支持的最大数据标识id，结果是31 */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    /** 序列在id中占的位数 */
    private final long sequenceBits = 12L;

    /** 机器ID向左移12位 */
    private final long workerIdShift = sequenceBits;

    /** 数据标识id向左移17位(12+5) */
    private final long datacenterIdShift = sequenceBits + workerIdBits;

    /** 时间截向左移22位(5+5+12) */
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    /** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /** 工作机器ID(0~31) */
    private long workerId;

    /** 数据中心ID(0~31) */
    private long datacenterId;

    /** 毫秒内序列(0~4095) */
    private long sequence = 0L;

    /** 上次生成ID的时间截 */
    private long lastTimestamp = -1L;

    //==============================Constructors=====================================
    /**
     * 构造函数
     * @param workerId 工作ID (0~31)
     * @param datacenterId 数据中心ID (0~31)
     */
    public SnowflakeIdWorkerV1(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;
    }

    // ==============================Methods==========================================
    /**
     * 获得下一个ID (该方法是线程安全的)
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();

        //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
        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;
        }

        //上次生成ID的时间截
        lastTimestamp = timestamp;

        //移位并通过或运算拼到一起组成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (datacenterId << datacenterIdShift) //
                | (workerId << workerIdShift) //
                | sequence;
    }

    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 返回以毫秒为单位的当前时间
     * @return 当前时间(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }

    //==============================Test=============================================
    /** 测试 */
    public static void main(String[] args) {
        SnowflakeIdWorkerV1 idWorker = new SnowflakeIdWorkerV1(0, 0);
        for (int i = 0; i < 1000; i++) {
            long id = idWorker.nextId();
            System.out.println(Long.toBinaryString(id));
            System.out.println(id);
        }
    }
}

2、考虑时间戳回拨

/**
 * Twitter_Snowflake<br>
 * SnowFlake的结构如下(每部分用-分开):<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
 * 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0<br>
 * 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)
 * 得到的值），这里的的开始时间截，一般是的id生成器开始使用的时间，由程序来指定的（如下下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T =
 * (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
 * 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId<br>
 * 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号<br>
 * 加起来刚好64位，为一个Long型。<br>
 * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。
 */
public class SnowflakeIdWorkerV2 {

  // ==============================Fields===========================================
  /** 开始时间截 (2015-01-01) */
  private final long twepoch = 1420041600000L;

  /** 机器id所占的位数 */
  private final long workerIdBits = 5L;

  /** 数据标识id所占的位数 */
  private final long datacenterIdBits = 5L;

  /** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
  private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

  /** 支持的最大数据标识id，结果是31 */
  private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

  /** 序列在id中占的位数 */
  private final long sequenceBits = 12L;

  /** 机器ID向左移12位 */
  private final long workerIdShift = sequenceBits;

  /** 数据标识id向左移17位(12+5) */
  private final long datacenterIdShift = sequenceBits + workerIdBits;

  /** 时间截向左移22位(5+5+12) */
  private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

  /** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */
  private final long sequenceMask = -1L ^ (-1L << sequenceBits);

  /** 工作机器ID(0~31) */
  private long workerId;

  /** 数据中心ID(0~31) */
  private long datacenterId;

  /** 毫秒内序列(0~4095) */
  private long sequence = 0L;

  /** 上次生成ID的时间截 */
  private long lastTimestamp = -1L;

  private long startTimestamp = -1L;

  // ==============================Constructors=====================================
  /**
   * 构造函数
   *
   * @param workerId 工作ID (0~31)
   * @param datacenterId 数据中心ID (0~31)
   */
  public SnowflakeIdWorkerV2(long workerId, long datacenterId, long startTimestamp) {
    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;
    this.startTimestamp = startTimestamp;
  }

  // ==============================Methods==========================================
  /**
   * 获得下一个ID (该方法是线程安全的)
   *
   * @return SnowflakeId
   */
  public synchronized long nextId() {
    long sequenceTmp = sequence;
    sequence = (sequence + 1) & sequenceMask;
    if (sequence == 0 && sequenceTmp >= 0) {
      // sequence自增到最大了，时间戳自增1
      startTimestamp += 1;
    }

    // 移位并通过或运算拼到一起组成64位的ID
    return ((startTimestamp - twepoch) << timestampLeftShift) //
        | (datacenterId << datacenterIdShift) //
        | (workerId << workerIdShift) //
        | sequence;
  }

  /**
   * 返回以毫秒为单位的当前时间
   *
   * @return 当前时间(毫秒)
   */
  protected static long timeGen() {
    return System.currentTimeMillis();
  }

  // ==============================Test=============================================
  /** 测试 */
  public static void main(String[] args) {
    SnowflakeIdWorkerV2 idWorker = new SnowflakeIdWorkerV2(0, 0, timeGen());
    for (int i = 0; i < 1000; i++) {
      long id = idWorker.nextId();
      System.out.println(Long.toBinaryString(id));
      System.out.println(id);
    }
  }
}

3、逻辑实现流程

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

组装生成id

生成id的过程，就是把每一种标识（时间、机器、序列号）移到对应位置，然后相加，如下：

long id = (deltaTime << TIMESTAMP_LEFT_SHIFT) | (this.dataCenterId << DATA_CENTER_ID_SHIFT) | (this.workerId << WORKER_ID_SHIFT) | this.sequence;
  • deltaTime向左移22位（IDC-bit+机器bit+序列号bit）。
  • dataCenterId向左移17位（机器bit+序列号bit）。
  • workerId向左移12位（序列号bit）。
  • sequence不用移，中间的|以运算规律就相当于+求和（1 | 1 = 1，1 | 0 = 1，0 | 1 = 1，0 | 0 = 0）。

计算最大值的几种方式

代码中分别对每个标识的最大值做了计算：

//序列掩码，用于限定序列最大值为4095 ((2^12)-1) ，从0开始算就有4096个序列
private static final long SEQUENCE_MASK =  -1L ^ (-1L << SEQUENCE_BITS);

//最大支持机器节点数0~31，一共32个  (2^5)-1
private static final long MAX_WORKER_ID = -1L ^ (-1L << WORKER_ID_BITS);

//最大支持数据中心节点数0~31，一共32个   (2^5)-1
private static final long MAX_DATA_CENTER_ID = -1L ^ (-1L << DATA_CENTER_ID_BITS);

//最大时间戳 2199023255551   (2^41)-1
private static final long MAX_DELTA_TIMESTAMP = -1L ^ (-1L << TIME_STAMP_BITS);

上方的计算就是利用二进制的运算逻辑，拿-1L ^ (-1L << SEQUENCE_BITS)举例：

先看看从哪个方向开始计算：-1L ^ (-1L << 12)，-1L和(-1L <<12)做^按位异或运算（1 ^ 1 = 0，1 ^ 0 = 1，0 ^ 1 = 1，0 ^ 0 = 0）。

  • -1L的二进制为64个1：1111111111111111111111111111111111111111111111111111111111111111。
  • -1L左移12位得到：1111111111111111111111111111111111111111111111111111 000000 000000。
  • 最后1111111111111111111111111111111111111111111111111111111111111111和1111111111111111111111111111111111111111111111111111 000000 000000做^运算得到0000000000000000000000000000000000000000000000000000 111111 111111（前面有52个0），这就得到序列号的最大值（4095）了，也可以说是掩码。

反解析ID

（1）通过已经生成的ID解析出时间、机器和序列号：

public long getSequence(long id) {
    return id & ~(-1L << SEQUENCE_BITS);
}

public long getWorkerId(long id) {
    return id >> WORKER_ID_SHIFT & ~(-1L << WORKER_ID_BITS);
}

public long getDataCenterId(long id) {
    return id >> DATA_CENTER_ID_SHIFT & ~(-1L << DATA_CENTER_ID_BITS);
}

public long getGenerateDateTime(long id) {
    return (id >> TIMESTAMP_LEFT_SHIFT & ~(-1L << 41L)) + twepoch;
}

因为sequence本身就在低位，所以不需要移动，其他机器和时间都是需要将id向右移动，使得自己的有效位置在低位，至于和自己的最大值做&运算，是为了让不属于自己bit的位置无效，即都转为0。

例如：生成的id为1414362783486840832，转为二进制1001110100000110100110111010100111101010001000001000000000000，想解析出workerId，workerId有效位为[13, 17]，那就将id向右移12位，移到低位得到0000000000001001110100000110100110111010100111101010001000001，workerId有5-bit，那么除了低位5-bit，其他位置都是无效bit，转为0。0000000000001001110100000110100110111010100111101010001000001和11111做&运算得到1（左边都是0可以省掉）。

（2）不过还有一种解析的思路更易于理解，就是运用两次移位运算，把无效位置移除：

1bit-sign + 41bit-time + 5bit-IDC + 5bit-workerId + 12bit-sequence

/**
 * 通过移位解析出sequence，sequence有效位为[0,12]
 * 所以先向左移64-12，然后再像右移64-12，通过两次移位就可以把无效位移除了
 * @param id
 * @return
 */
public long getSequence2(long id) {
    return (id << (TOTAL_BITS - SEQUENCE_BITS)) >>> (TOTAL_BITS - SEQUENCE_BITS);
}
/**
 * 通过移位解析出workerId，workerId有效位为[13,17], 左右两边都有无效位
 * 先向左移 41+5+1，移除掉41bit-时间，5bit-IDC、1bit-sign，
 * 然后右移回去41+5+1+12，从而移除掉12bit-序列号
 * @param id
 * @return
 */
public long getWorkerId2(long id) {
    return (id << (TIME_STAMP_BITS + DATA_CENTER_ID_BITS + SIGN_BITS)) >>> (TIME_STAMP_BITS + DATA_CENTER_ID_BITS + SEQUENCE_BITS + SIGN_BITS);
}
/**
 * 通过移位解析出IDC_ID，dataCenterId有效位为[18,23]，左边两边都有无效位
 * 先左移41+1，移除掉41bit-时间和1bit-sign
 * 然后右移回去41+1+5+12，移除掉右边的5bit-workerId和12bit-序列号
 * @param id
 * @return
 */
public long getDataCenterId2(long id) {
    return (id << (TIME_STAMP_BITS + SIGN_BITS)) >>> (TIME_STAMP_BITS + WORKER_ID_BITS + SEQUENCE_BITS + SIGN_BITS);
}
/**
 * 41bit-时间，左边1bit-sign为0，可以忽略，不用左移，所以只需要右移，并加上起始时间twepoch即可。
 * @param id
 * @return
 */
public long getGenerateDateTime2(long id) {
    return (id >>> (DATA_CENTER_ID_BITS + WORKER_ID_BITS + SEQUENCE_BITS)) + twepoch;
}

ID生成器使用方式

在分布式ID生成的策略中，通常采用两种方式：一是基于发号器的方案，二是本地生成方案。

1、发号器方案

该方案将雪花算法ID的生成逻辑封装成一个独立的服务，并部署在多个服务器上，外部系统通过请求发号器服务来获取ID，此方案的优势在于，无需部署大量的服务器，仅需确保服务器数量满足需求即可，默认的1024台已经足够。

但是，由于ID的获取涉及到远程请求，因此会受到网络波动的影响，其性能自然无法与直接从本地生成相比，同时，发号器服务的稳定性至关重要，一旦服务出现故障，将影响到许多依赖其的外部服务。为了确保发号器的高可用性，需要采取多实例部署、异地容灾等策略。

此外，发号器在设计时还可以考虑一次性发布一段时间内的ID供服务本地缓存，这样既能提升性能，减少对发号器的频繁请求，也能在一定程度上降低发号器故障所带来的风险。

2、本地生成方案

在此方案中，ID是在本地直接生成的，因此不存在网络延迟问题，性能极高。但是，为了确保生成的ID具有全局唯一性，需要依赖机器ID来进行区分。因此每台机器以及机器上部署的每个服务都需要分配不同的机器ID。

此外，服务重启后也需要重新分配新的机器ID，这种特性使得机器ID具有“用后即弃”的性质，为了满足对大量机器ID的需求，不得不减少时间戳和序列号的位数，这样做虽然会牺牲一部分ID的丰富性，但却是保证本地生成方案可行性的必要妥协。

运算符相关概念

运算符&

"&"表示按位与操作，它用于操作整数类型的位模式，并将每个操作数中的每一位进行与操作，它会将两个整数的二进制表示进行按位与运算，只有当两个数的相应位都为1时，结果的相应位才为1，否则为0。这种运算符通常用于低级位操作，如设置、清除或翻转二进制位。

int a = 60;  // 60 = 0011 1100  
int b = 13;  // 13 = 0000 1101  
int c = a & b;  // c will be 12 = 0000 1100

运算符|

"|"表示按位或操作，它用于操作整数类型的位模式，并将每个操作数中的每一位进行或操作，它会将两个整数的二进制表示进行按位或运算，只要两个数的相应位中有一个为1，结果的相应位就为1，否则为0。

int a = 60;  // 60 = 0011 1100  
int b = 13;  // 13 = 0000 1101  
int c = a | b;  // c will be 61 = 0011 1101

上一篇：解释组合模式和外观模式


下一篇：如何定位&预防死锁