雪花 Id

雪花算法这一在分布式架构中很常见的玩意，但一般也不需要怎么去深入了解，一方面一般个人项目用不到分布式之类的大型架构，另一方面，就算要用到，市面上很多 ID 生成器也帮我们完成了这项工作。

1. 分布式 ID 的特点

• 全局唯一性：不能出现有重复的 ID 标识，这是基本要求；
• 递增性：确保生成 ID 对于用户或业务是递增的；
• 高可用性：确保任何时候都能生成正确的 ID；
• 高性能性：在高并发的环境下依然表现良好；

2. 分布式 ID 的常见解决方案

2.1. UUID

Java 自带的生成一串唯一随机 36 位字符串（32 个字符串 + 4 个 “-”）的算法。它可以保证唯一性，且据说够用 N 亿年，但是其业务可读性差，无法有序递增。

2.2. SnowFlake

今天的主角雪花算法，它是 Twitter 开源的由 64 位整数组成分布式 ID，性能较高，并且在单机上递增。具体参考：https://github.com/twitter-archive/snowflake

2.3. UidGenerator

UidGenerator 是百度开源的分布式 ID 生成器，其基于雪花算法实现。具体参考：https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

2.4. Leaf

Leaf 是美团开源的分布式 ID 生成器，能保证全局唯一，趋势递增，但需要依赖关系数据库、Zookeeper 等中间件。具体参考：https://tech.meituan.com/MT_Leaf.html

3. 雪花算法的概要

SnowFlake 是 Twitter 公司采用的一种算法，目的是在分布式系统中产生全局唯一且趋势递增的 ID。

3.1. 组成部分（64bit）

1. 第一位占用 1bit，其值始终是 0，没有实际作用；
2. 时间戳占用 41bit，精确到毫秒，总共可以容纳约 69 年的时间；
3. 工作机器 id 占用 10bit，其中高位 5bit 是数据中心 ID，低位 5bit 是工作节点 ID，做多可以容纳 1024 个节点；
4. 序列号占用 12bit，每个节点每毫秒 0 开始不断累加，最多可以累加到 4095，一共可以产生 4096 个 ID；

SnowFlake 算法在同一毫秒内最多可以生成多少个全局唯一 ID 呢：同一毫秒的 ID 数量 = 1024 X 4096 = 4194304

3.2. 雪花算法的实现

雪花算法的实现主要依赖于数据中心 ID 和数据节点 ID 这两个参数，具体实现如下：

• JAVA 实现

  public class SnowflakeIdWorker {
      /**
       * 开始时间截 (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;
      /**
       * 构造函数
       * @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;
      }
      /**
       * 获得下一个 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();
      }
  
      public static void main(String[] args) throws InterruptedException {
          SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
          for (int i = 0; i < 10; i++) {
              long id = idWorker.nextId();
              Thread.sleep(1);
              System.out.println(id);
          }
      }
  }

• Python 实现

  # coding: utf-8
  import time
  
  class InvalidSystemClock(Exception):
      """
      时钟回拨异常
      """
      pass
  
  # 64 位 ID 的划分
  WORKER_ID_BITS = 5
  DATACENTER_ID_BITS = 5
  SEQUENCE_BITS = 12
  
  # 最大取值计算
  MAX_WORKER_ID = -1 ^ (-1 << WORKER_ID_BITS)  # 2**5-1 0b11111
  MAX_DATACENTER_ID = -1 ^ (-1 << DATACENTER_ID_BITS)
  
  # 移位偏移计算
  WOKER_ID_SHIFT = SEQUENCE_BITS
  DATACENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS
  TIMESTAMP_LEFT_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATACENTER_ID_BITS
  
  # 序号循环掩码
  SEQUENCE_MASK = -1 ^ (-1 << SEQUENCE_BITS)
  
  # 开始时间截 (2015-01-01)
  TWEPOCH = 1420041600000
  
  class IdWorker(object):
      """
      用于生成 IDs
      """
      def __init__(self, datacenter_id, worker_id, sequence=0):
          """
          初始化
          :param datacenter_id: 数据中心（机器区域）ID
          :param worker_id: 机器 ID
          :param sequence: 其实序号
          """
          # sanity check
          if worker_id > MAX_WORKER_ID or worker_id < 0:
              raise ValueError('worker_id 值越界')
  
          if datacenter_id > MAX_DATACENTER_ID or datacenter_id < 0:
              raise ValueError('datacenter_id 值越界')
  
          self.worker_id = worker_id
          self.datacenter_id = datacenter_id
          self.sequence = sequence
  
          self.last_timestamp = -1  # 上次计算的时间戳
  
      def _gen_timestamp(self):
          """
          生成整数时间戳
          :return:int timestamp
          """
          return int(time.time() * 1000)
  
      def get_id(self):
          """
          获取新 ID
          :return:
          """
          timestamp = self._gen_timestamp()
  
          # 时钟回拨
          if timestamp < self.last_timestamp:
              raise InvalidSystemClock
  
          if timestamp == self.last_timestamp:
              self.sequence = (self.sequence + 1) & SEQUENCE_MASK
              if self.sequence == 0:
                  timestamp = self._til_next_millis(self.last_timestamp)
          else:
              self.sequence = 0
  
          self.last_timestamp = timestamp
  
          new_id = ((timestamp - TWEPOCH) << TIMESTAMP_LEFT_SHIFT) | (self.datacenter_id <<   DATACENTER_ID_SHIFT) | \
                   (self.worker_id << WOKER_ID_SHIFT) | self.sequence
          return new_id
  
      def _til_next_millis(self, last_timestamp):
          """
          等到下一毫秒
          """
          timestamp = self._gen_timestamp()
          while timestamp <= last_timestamp:
              timestamp = self._gen_timestamp()
          return timestamp
  
  if __name__ == '__main__':
      worker = IdWorker(0, 0)
      print(worker.get_id())

---

原文链接

分布式 ID 神器之雪花算法简介