关于分布式系统:分布式ID生成方案选型详细解析雪花算法Snowflake

应用 RocketMQ 时, 须要应用到分布式惟一ID
音讯可能会产生反复, 所以要在生产端做幂等性, 为了达到业务的幂等性, 生产者必须要有一个惟一ID, 须要满足以下条件:
- 同一业务场景要全局惟一
- 该 ID 必须是在音讯的发送方进行生成发送到 MQ
- 生产端依据该 ID 进行判断是否反复, 确保幂等性
在哪里产生以及生产端进行判断做幂等性与该 ID 无关, 此 ID 须要保障的个性:
- 部分甚至全局惟一
- 趋势递增
  
  Snowflake 算法
Snowflake 是 Twitter 开源的分布式 ID 生成算法, 后果是一个 Long 型的 ID, 核心思想是:
- 应用 1 位作为符号位, 确定为 0, 示意正
- 应用 41 位作为 毫秒数
- 应用 10 位作为机器的 ID : 高 5 位是 数据中心 ID, 低 5 位是 机器 ID
- 应用 12 位作为 毫秒内的序列号, 意味着每个节点每秒能够产生 4096(2^12^) 个 ID
  
  该算法通过二进制的操作进行实现, 单机每秒内实践上最多能够生成 1000*(2^12), 即409.6 万个 ID
  
  SnowflakeIdWorker

Snowflake 算法 Java 实现 SnowflakeIdWorker:

/**
 * 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 SnowflakeIdWorker {

  // ==============================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 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;
  }

  // ==============================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) {SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
      for (int i = 0; i < 1000; i++) {long id = idWorker.nextId();
          System.out.println(Long.toBinaryString(id));
          System.out.println(id);
      }
  }
}

长处:
- 生成速度快
- 实现简略, 没有多余的依赖
- 能够依据理论状况调整各个位段, 不便灵便
毛病:
- 只能趋势递增
- 依赖机器工夫. 如果产生回拨可能会造成生成的 ID 反复
  SnowFlake 算法工夫回拨问题:
  - 工夫回拨产生起因:
    - 因为业务须要, 机器须要同步工夫服务器
  - 工夫回拨问题解决办法:
    - 当回拨工夫小于 15ms, 能够等待时间追上来当前再持续生成
    - 当回拨工夫大于 15ms 时能够通过更换 workId 来产生之前都没有产生过的 Id 来解决回拨问题
  - 步骤:
    - 首先将 workId 的位数进行调整至 15 位
    - 而后将 SnowflakeIdWorker 实现调整位段
      
      应用 1 位作为 符号位, 即生成的分布式 I 惟一 d 为负数
      
      应用 38 位作为 工夫戳, 示意以后工夫绝对于初始工夫的增量值, 单位为毫秒
      
      应用 15 位作为 机器 ID, 最多可反对 3.28 万个节点
      
      应用 10 位作为 毫秒内的序列号, 实践上能够生成 2^10^ 个序列号
    - 因为服务的无状态关系, 失常状况下 workId 不会配置在具体配置文件中, 这里能够抉择集中式的 Redis 作为地方存储:
      
      将 workId 调整位数后失去的多余的 3 万多个 workId 搁置到一个基于 Redis 的队列中, 用来集中管理 workId
      
      每次当节点启动的时候, 先查看本地是否有 workId, 如果有那么就作为 workId. 如果没有, 就在队列中取出一个当 workId 来应用, 并从队列中删除
      
      当发现工夫回拨太多的时候, 就再去队列中去一个来当新的 workId 应用, 将刚刚那个应用回拨的状况的 workId 存到队列里. 因为队列每次都是从头取出, 从尾部插入, 这样能够防止刚刚 A 机器应用的 workId 又被 B 机器获取的可能性
      
      如果应用 redis 又会遇到新的小问题: redis 一致性如何保障?redis 挂了怎么办? 怎么同步?
从根底组件的应用角度来说, 对于 SnowflakeIdWorker 算法当遇到工夫回拨问题, 只须要抛出异样即可, 这样能够保障算法实现的简略性
也能够参考 uid-generator 办法: 每次取一批workId, 集中之后批取, 这样能够解决各个节点拜访集中机器的性能问题.

分布式惟一 ID

Snowflake 算法

SnowflakeIdWorker