/**
 * 雪花算法相对来说如果思绪捋顺了实现起来比较简单，前提熟悉位运算。
 */
public class SnowFlake
{
 /**
  * 开始时间截 (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 << workerIdBits);

 /**
  * 支持的最大机房标识id，结果是31
  */
 private final long maxDataCenterId = ~(-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 << sequenceBits);

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

 /**
  * 机房中心ID(0~31)
  */
 private volatile long dataCenterId;

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

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

 //==============================Constructors=====================================

 /**
  * 构造函数
  *
  * @param workerId     工作ID (0~31)
  * @param dataCenterId 机房中心ID (0~31)
  */

 public SnowFlake(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 (该方法是线程安全的)
  * 如果一个线程反复获取Synchronized锁，那么synchronized锁将变成偏向锁。
  *
  * @return SnowflakeId
  */
 public synchronized long nextId() throws RuntimeException
 {
  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;
   //毫秒内序列溢出，一毫秒内超过了4095个
   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 当前时间戳
  */
 private long tilNextMillis(long lastTimestamp)
 {
  long timestamp = timeGen();
  while (timestamp <= lastTimestamp)
  {
   timestamp = timeGen();
  }
  return timestamp;
 }

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

SnowFlake算法的优点：

• 高性能高可用：生成时不依赖于数据库，完全在内存中生成。
• 容量大：每秒中能生成数百万的自增ID。
• ID自增：存入数据库中，索引效率高。

SnowFlake算法的缺点：

• 依赖与系统时间的一致性，如果系统时间被回调，或者改变，可能会造成id冲突或者重复。

实际中我们的机房并没有那么多，我们可以改进改算法，将10bit的机器id优化成业务表或者和我们系统相关的业务。

7. 百度uid-generator

项目GitHub地址：https://github.com/baidu/uid-generator，uid-generator是由百度技术部开发，基于Snowflake算法实现的，与原始的snowflake算法不同在于，uid-generator支持自定义时间戳、工作机器ID和 序列号等各部分的位数，而且uid-generator中采用用户自定义workId的生成策略。

uid-generator需要与数据库配合使用，需要新增一个WORKER_NODE表。当应用启动时会向数据库表中去插入一条数据，插入成功后返回的自增ID就是该机器的workId数据由host，port组成。[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OPXK8vqx-1624083769499)(data:image/gif;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABCAYAAAAfFcSJAAAADUlEQVQImWNgYGBgAAAABQABh6FO1AAAAABJRU5ErkJggg==)]由上图可知，UidGenerator的时间部分只有28位，这就意味着UidGenerator默认只能承受8.5年（2^28-1/86400/365）。当然，根据你业务的需求，UidGenerator可以适当调整delta seconds、worker node id和sequence占用位数。

接下来分析百度UidGenerator的实现。需要说明的是UidGenerator有两种方式提供：和DefaultUidGenerator和CachedUidGenerator。我们先分析比较容易理解的DefaultUidGenerator。

DefaultUidGenerator

delta seconds这个值是指当前时间与epoch时间的时间差，且单位为秒。epoch时间就是指集成UidGenerator生成分布式ID服务第一次上线的时间，可配置，也一定要根据你的上线时间进行配置，因为默认的epoch时间可是2016-09-20，不配置的话，会浪费好几年的可用时间。

worker id接下来说一下UidGenerator是如何给worker id赋值的，搭建UidGenerator的话，需要创建一个表：
UidGenerator会在集成用它生成分布式ID的实例启动的时候，往这个表中插入一行数据，得到的id值就是准备赋给workerId的值。由于workerId默认22位，那么，集成UidGenerator生成分布式ID的所有实例重启次数是不允许超过4194303次（即2^22-1），否则会抛出异常。

这段逻辑的核心代码来自DisposableWorkerIdAssigner.java中，当然，你也可以实现WorkerIdAssigner.java接口，自定义生成workerId。sequence核心代码如下，几个实现的关键点：

• synchronized保证线程安全。
• 如果时间有任何的回拨，那么直接抛出异常。
• 如果当前时间和上一次是同一秒时间，那么sequence自增。如果同一秒内自增值超过2^13-1，那么就-- 会自旋等待下一秒（getNextSecond）。
• 如果是新的一秒，那么sequence重新从0开始。

/**
     * Get UID
     *
     * @return UID
     * @throws UidGenerateException in the case: Clock moved backwards; Exceeds the max timestamp
     */
    protected synchronized long nextId() {
        long currentSecond = getCurrentSecond();
        // Clock moved backwards, refuse to generate uid
        if (currentSecond < lastSecond) {
            long refusedSeconds = lastSecond - currentSecond;
            throw new UidGenerateException("Clock moved backwards. Refusing for %d seconds", refusedSeconds);
        }
        // At the same second, increase sequence
        if (currentSecond == lastSecond) {
            sequence = (sequence + 1) & bitsAllocator.getMaxSequence();
            // Exceed the max sequence, we wait the next second to generate uid
            if (sequence == 0) {
                currentSecond = getNextSecond(lastSecond);
            }
        // At the different second, sequence restart from zero
        } else {
            sequence = 0L;
        }
        lastSecond = currentSecond;
        // Allocate bits for UID
        return bitsAllocator.allocate(currentSecond - epochSeconds, workerId, sequence);
    }

<property name="timeBits" value="28"/>
<property name="workerBits" value="22"/>
<property name="seqBits" value="13"/>
<property name="epochStr" value="2016-09-20"/>

DROP TABLE IF EXISTS `leaf_alloc`;
CREATE TABLE `leaf_alloc` (
  `biz_tag` varchar(128)  NOT NULL DEFAULT '' COMMENT '业务key',
  `max_id` bigint(20) NOT NULL DEFAULT '1' COMMENT '当前已经分配了的最大id',
  `step` int(11) NOT NULL COMMENT '初始步长，也是动态调整的最小步长',
  `description` varchar(256)  DEFAULT NULL COMMENT '业务key的描述',
  `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '数据库维护的更新时间',
  PRIMARY KEY (`biz_tag`)
) ENGINE=InnoDB;

leaf.name=com.sankuai.leaf.opensource.test
leaf.segment.enable=true
leaf.jdbc.url=jdbc:mysql://localhost:3306/leaf_test?useUnicode=true&characterEncoding=utf8&characterSetResults=utf8
leaf.jdbc.username=root
leaf.jdbc.password=root

leaf.snowflake.enable=false
#leaf.snowflake.zk.address=
#leaf.snowflake.port=

leaf.snowflake.enable=true
leaf.snowflake.zk.address=127.0.0.1
leaf.snowflake.port=2181