分布式惟一ID

应用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

分布式惟一ID

Snowflake算法

SnowflakeIdWorker

评论

发表回复取消回复

更多文章

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

深入解析：基于Delta的线性数据结构模型，打造高效富文本编辑器

轻松管理社交媒体：使用Automa插件实现一键拉黑功能

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

分布式惟一ID

Snowflake算法

SnowflakeIdWorker

评论

发表回复 取消回复

更多文章

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

深入解析：基于Delta的线性数据结构模型，打造高效富文本编辑器

轻松管理社交媒体：使用Automa插件实现一键拉黑功能

发表回复取消回复