Java实现Twitter的分布式自增ID算法snowflake

概述

分布式系统中，有一些需要使用全局唯一ID的场景，这种时候为了防止ID冲突可以使用36位的UUID，但是UUID有一些缺点，首先他相对比较长，另外UUID一般是无序的。

有些时候我们希望能使用一种简单一些的ID，并且希望ID能够按照时间有序生成。

而twitter的snowflake解决了这种需求，最初Twitter把存储系统从MySQL迁移到Cassandra，因为Cassandra没有顺序ID生成机制，所以开发了这样一套全局唯一ID生成服务。

结构

snowflake的结构如下(每部分用-分开):

0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

第一位为未使用，接下来的41位为毫秒级时间(41位的长度可以使用69年)，然后是5位datacenterId和5位workerId(10位的长度最多支持部署1024个节点），最后12位是毫秒内的计数（12位的计数顺序号支持每个节点每毫秒产生4096个ID序号）

一共加起来刚好64位，为一个Long型。(转换成字符串后长度最多19)

snowflake生成的ID整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞（由datacenter和workerId作区分），并且效率较高。经测试snowflake每秒能够产生26万个ID。

源码

(JAVA版本的源码)


public class SnowflakeIdWorker {

  // ==============================Fields===========================================
  
  private final long twepoch = 1420041600000L;

  
  private final long workerIdBits = 5L;

  
  private final long datacenterIdBits = 5L;

  
  private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

  
  private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

  
  private final long sequenceBits = 12L;

  
  private final long workerIdShift = sequenceBits;

  
  private final long datacenterIdShift = sequenceBits + workerIdBits;

  
  private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

  
  private final long sequenceMask = -1L ^ (-1L << sequenceBits);

  
  private long workerId;

  
  private long datacenterId;

  
  private long sequence = 0L;

  
  private long lastTimestamp = -1L;

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

  
  protected long tilNextMillis(long lastTimestamp) {
    long timestamp = timeGen();
    while (timestamp <= lastTimestamp) {
      timestamp = timeGen();
    }
    return timestamp;
  }

  
  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);
    }
  }
}

参考

https://github.com/twitter/snowflake

到此这篇关于Java实现Twitter的分布式自增ID算法snowflake的文章就介绍到这了,更多相关Java 自增ID算法snowflake内容请搜索考高分网以前的文章或继续浏览下面的相关文章希望大家以后多多支持考高分网！

Java实现Twitter的分布式自增ID算法snowflake

Java相关栏目本月热门文章