分布式唯一 ID 之 Snowflake 算法

阿宝哥

发布于 2019-11-06 12:50:06

1.6K0

发布于 2019-11-06 12:50:06

一、Snowflake 简介

1.1 什么是 Snowflake

Snowflake is a service used to generate unique IDs for objects within Twitter (Tweets, Direct Messages, Users, Collections, Lists etc.). These IDs are unique 64-bit unsigned integers, which are based on time, instead of being sequential. The full ID is composed of a timestamp, a worker number, and a sequence number. When consuming the API using JSON, it is important to always use the field id_str instead of id. This is due to the way Javascript and other languages that consume JSON evaluate large integers. If you come across a scenario where it doesn’t appear that id and id_str match, it’s due to your environment having already parsed the id integer, munging the number in the process. —— developer.twitter.com

Snowflake（雪花）是一项服务，用于为 Twitter 内的对象（推文，直接消息，用户，集合，列表等）生成唯一的 ID。这些 IDs 是唯一的 64 位无符号整数，它们基于时间，而不是顺序的。完整的 ID 由时间戳，工作机器编号和序列号组成。当在 API 中使用 JSON 数据格式时，请务必始终使用 id_str 字段而不是 id，这一点很重要。这是由于处理JSON 的 Javascript 和其他语言计算大整数的方式造成的。如果你遇到 id 和 id_str 似乎不匹配的情况，这是因为你的环境已经解析了 id 整数，并在处理的过程中仔细分析了这个数字。

在 JavaScript 中，Number 基本类型可以精确表示的最大整数是 2^53。因此如果直接使用 Number 来表示 64 位的 Snowflake ID 肯定是行不通的。所以 Twitter 工程师们让我们务必使用 id_str 字段即通过字符串来表示生成的 ID。当然这个问题不仅仅存在于使用 Snowflake ID 的场景，为了解决 JavaScript 不能安全存储和操作大整数的问题，BigInt 这个救星出现了，它是一种内置对象，可以表示大于 2^53 的整数，甚至是任意大的整数。

BigInt 现在处在 ECMAScript 标准化过程中的 第三阶段 。当它进入第四阶段草案，也就是最终标准时， BigInt 将成为 Javacript 中的第二种内置数值类型。 BigInt 可能会成为自 ES2015 引入 Symbol 之后，增加的第一个新的内置类型。

1.2 Snowflake 算法

下图是 Snowflake 算法的 ID 构成图：

1 位标识部分，该位不用主要是为了保持 ID 的自增特性，若使用了最高位，int64_t 会表示为负数。在 Java 中由于 long 类型的最高位是符号位，正数是 0，负数是 1，一般生成的 ID 为正整数，所以最高位为 0；
41 位时间戳部分，这个是毫秒级的时间，一般实现上不会存储当前的时间戳，而是时间戳的差值（当前时间减去固定的开始时间），这样可以使产生的 ID 从更小值开始；41 位的时间戳可以使用 69 年，(1L << 41) / (1000L 60 60 24 365) = (2199023255552 / 31536000000) ≈ 69.73 年；
10 位工作机器 ID 部分，Twitter 实现中使用前 5 位作为数据中心标识，后 5 位作为机器标识，可以部署 1024 （2^10）个节点；
12 位序列号部分，支持同一毫秒内同一个节点可以生成 4096 （2^12）个 ID；

Snowflake 算法生成的 ID 大致上是按照时间递增的，用在分布式系统中时，需要注意数据中心标识和机器标识必须唯一，这样就能保证每个节点生成的 ID 都是唯一的。我们不一定需要像 Twitter 那样使用 5 位作为数据中心标识，另 5 位作为机器标识，可以根据我们业务的需要，灵活分配工作机器 ID 部分。比如：若不需要数据中心，完全可以使用全部 10 位作为机器标识；若数据中心不多，也可以只使用 3 位作为数据中心，7 位作为机器标识。

二、Snowflake 解惑

以下问题来源于漫漫路博客 - “Twitter-Snowflake，64 位自增ID算法详解” 评论区

2.1 既然是 64 位，为何第一位不使用？

首位不用主要是为了保持 ID 的自增特性，若使用了最高位，int64_t 会表示为负数。在 Java 中由于 long 类型的最高位是符号位，正数是 0，负数是 1，一般生成的 ID 为正整数，所以最高位为 0。

2.2 怎么生成 41 位的时间戳？

41 位的时间戳，这个是毫秒级的时间，一般实现上不会存储当前的时间戳，而是时间戳的差值（当前时间减去固定的开始时间）。41 位只是预留位（主要目的是约定使用年限，固定的开始时间），不用的位数填 0 就好了。

2.3 工作机器 id 如果使用 MAC 地址的话，怎么转成 10 bit？

网络中每台设备都有一个唯一的网络标识，这个地址叫 MAC 地址或网卡地址，由网络设备制造商生产时写在硬件内部。MAC 地址则是 48 位的（6 个字节），通常表示为 12 个 16 进制数，每 2 个 16 进制数之间用冒号隔开，如08：00：20：0A：8C：6D 就是一个 MAC 地址。

具体如下图所示，其前 3 字节表示OUI（Organizationally Unique Identifier），是 IEEE （电气和电子工程师协会）区分不同的厂家，后 3 字节由厂家自行分配。

（图片来源 - 百度百科）

很明显 Mac 地址是 48 位，而我们的工作机器 ID 部分只有 10 位，因此并不能直接使用 Mac 地址作为工作机器 ID。若要选用 Mac 地址的话，还需使用一个额外的工作机器 ID 分配器，用来实现 ID 与 Mac 地址间的唯一映射。

2.4 怎么生成 12 bit 的序列号？

序列号不需要全局维护，在 Java 中可以使用 AtomicInteger（保证线程安全）从 0 开始自增。当序列号超过了 4096，序列号在这一毫秒就用完了，等待下一个毫秒归 0 重置就可以了。

三、Snowflake 优缺点

理论上 Snowflake 方案的 QPS 约为 409.6w/s（1000 * 2^12），这种分配方式可以保证在任何一个 IDC 的任何一台机器在任意毫秒内生成的 ID 都是不同的。

3.1 优点

毫秒数在高位，自增序列在低位，整个 ID 都是趋势递增的。趋势递增的目的是：在 MySQL InnoDB 引擎中使用的是聚集索引，由于多数 RDBMS 使用 B-tree 的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成 ID 的性能也是非常高的。
可以根据自身业务特性分配 bit 位，非常灵活。

3.2 缺点

强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。

除了时钟回拨问题之外，Snowflake 算法会存在并发限制，当然对于这些问题，以本人目前的 Java 功力根本解决不了。但这并不影响我们使用它。在实际项目中我们可以使用基于 Snowflake 算法的开源项目，比如百度的 UidGenerator 或美团的 Leaf。下面我们简单介绍一下这两个项目，感兴趣的小伙伴可以自行查阅相关资料。

3.3 UidGenerator

UidGenerator 是 Java 实现的，基于 Snowflake 算法的唯一 ID 生成器。UidGenerator 以组件形式工作在应用项目中，支持自定义 workerId 位数和初始化策略，从而适用于 docker 等虚拟化环境下实例自动重启、漂移等场景。在实现上，UidGenerator 通过借用未来时间来解决 sequence 天然存在的并发限制；采用 RingBuffer 来缓存已生成的 UID，并行化 UID 的生产和消费，同时对 CacheLine 补齐，避免了由 RingBuffer 带来的硬件级「伪共享」问题。最终单机 QPS 可达 600 万。

依赖版本：Java8 及以上版本，MySQL (内置 WorkerID 分配器，启动阶段通过 DB 进行分配；如自定义实现，则 DB非必选依赖）。

3.4 Leaf

Leaf 最早期需求是各个业务线的订单 ID 生成需求。在美团早期，有的业务直接通过 DB 自增的方式生成 ID，有的业务通过 Redis 缓存来生成 ID，也有的业务直接用 UUID 这种方式来生成 ID。以上的方式各自有各自的问题，因此我们决定实现一套分布式 ID 生成服务来满足需求。具体 Leaf 设计文档见： Leaf 美团分布式ID生成服务。

目前 Leaf 覆盖了美团点评公司内部金融、餐饮、外卖、酒店旅游、猫眼电影等众多业务线。在 4C8G VM 基础上，通过公司 RPC 方式调用，QPS 压测结果近5w/s，TP999 1ms。

四、Snowflake 算法实现

在前面 Snowflake 知识的基础上，现在我们来分析一下 Github 上 beyondfengyu 大佬基于 Java 实现的 SnowFlake，完整代码如下：

/**
 * twitter的snowflake算法 -- java实现
 * 
 * @author beyond
 * @date 2016/11/26
 */
public class SnowFlake {

    /**
     * 起始的时间戳
     */
    private final static long START_STMP = 1480166465631L;

    /**
     * 每一部分占用的位数
     */
    private final static long SEQUENCE_BIT = 12; //序列号占用的位数
    private final static long MACHINE_BIT = 5;   //机器标识占用的位数
    private final static long DATACENTER_BIT = 5;//数据中心占用的位数

    /**
     * 每一部分的最大值
     */
    private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);

    /**
     * 每一部分向左的位移
     */
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;

    private long datacenterId;  //数据中心
    private long machineId;     //机器标识
    private long sequence = 0L; //序列号
    private long lastStmp = -1L;//上一次时间戳

    public SnowFlake(long datacenterId, long machineId) {
        if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
            throw new IllegalArgumentException(
              "datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
        }
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException(
              "machineId can't be greater than MAX_MACHINE_NUM or less than 0");
        }
        this.datacenterId = datacenterId;
        this.machineId = machineId;
    }

    /**
     * 产生下一个ID
     *
     * @return
     */
    public synchronized long nextId() {
        long currStmp = getNewstmp();
        if (currStmp < lastStmp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }

        if (currStmp == lastStmp) {
            //相同毫秒内，序列号自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //同一毫秒的序列数已经达到最大
            if (sequence == 0L) {
                currStmp = getNextMill();
            }
        } else {
            //不同毫秒内，序列号置为0
            sequence = 0L;
        }

        lastStmp = currStmp;

        return (currStmp - START_STMP) << TIMESTMP_LEFT //时间戳部分
                | datacenterId << DATACENTER_LEFT       //数据中心部分
                | machineId << MACHINE_LEFT             //机器标识部分
                | sequence;                             //序列号部分
    }

    private long getNextMill() {
        long mill = getNewstmp();
        while (mill <= lastStmp) {
            mill = getNewstmp();
        }
        return mill;
    }

    private long getNewstmp() {
        return System.currentTimeMillis();
    }

    public static void main(String[] args) {
        SnowFlake snowFlake = new SnowFlake(2, 3);

        for (int i = 0; i < (1 << 12); i++) {
            System.out.println(snowFlake.nextId());
        }

    }
}

在详细分析之前，我们先来回顾一下 Snowflake 算法的 ID 构成图：

4.1 ID 位分配

首位不用，默认为 0。41bit（第2-42位）时间戳，是相对时间戳，通过当前时间戳减去一个固定的历史时间戳生成。在 SnowFlake 类定义了一个 long 类型的静态变量 START_STMP，它的值为 1480166465631L：

/**
 * 起始的时间戳：Sat Nov 26 2016 21:21:05 GMT+0800 (中国标准时间)
 */
private final static long START_STMP = 1480166465631L;

接着继续定义三个 long 类型的静态变量，来表示序列号和工作机器 ID 的占用位数：

/**
 * 每一部分占用的位数
 */
private final static long SEQUENCE_BIT = 12; //序列号占用的位数
private final static long MACHINE_BIT = 5;   //机器标识占用的位数
private final static long DATACENTER_BIT = 5;//数据中心占用的位数

此外还定义了每一部分的最大值，具体如下：

/**
 * 每一部分的最大值
 */
private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT); // 31
private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT); // 31
private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT); // 4095

4.2 构造函数

SnowFlake 类的构造函数，该构造函数含有 datacenterId 和 machineId 两个参数，它们分别表示数据中心 id 和机器标识：

private long datacenterId;  //数据中心
private long machineId;     //机器标识

public SnowFlake(long datacenterId, long machineId) {
        if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
            throw new IllegalArgumentException(
              "datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
        }
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException(
              "machineId can't be greater than MAX_MACHINE_NUM or less than 0");
        }
        this.datacenterId = datacenterId;
        this.machineId = machineId;
}

4.3 生成 id

在 SnowFlake 类的实现中，在创建完 SnowFlake 对象之后，可以通过调用 nextId 方法来获取 ID。有的小伙伴可能对位运算不太清楚，这里先简单介绍一下 nextId 方法中，所用到的位运算知识。

按位与运算符（&）

参加运算的两个数据，按二进制位进行 “与” 运算，它的运算规则：

0&0=0;  0&1=0;  1&0=0;  1&1=1;

即两位同时为 1，结果才为 1，否则为 0。

清零：如果想将一个单元清零，只需要将它与一个各位都为零的数值相与即可。
取一个数指定位的值：若需获取某个数指定位的值，只需把该数与指定位为 1，其余位为 0 所对应的数相与即可。

按位或运算（|）

参加运算的两个对象，按二进制位进行 “或” 运算，它的运算规则：

0|0=0; 0|1=1; 1|0=1; 1|1=1;

即仅当两位都为 0 时，结果才为 0。

左移运算符 <<

将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补 0）。若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以 2。

在了解完位运算的相关知识后，我们再来看一下 nextId 方法的具体实现：

/**
 * 产生下一个ID
 *
 * @return
 */
public synchronized long nextId() {
  // 获取当前的毫秒数：System.currentTimeMillis()，该方法产生一个当前的毫秒，这个毫秒
  // 其实就是自1970年1月1日0时起的毫秒数。
  long currStmp = getNewstmp();
  
  // private long lastTimeStamp = -1L; 表示上一次时间戳
  // 检测是否出现时钟回拨
  if (currStmp < lastStmp) {
     throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
  }

  // 相同毫秒内，序列号自增
  if (currStmp == lastStmp) {
     // private long sequence = 0L; 序列号
     // MAX_SEQUENCE =      4095 111111111111
     // MAX_SEQUENCE + 1 = 4096 1000000000000
     sequence = (sequence + 1) & MAX_SEQUENCE;
     // 同一毫秒的序列数已经达到最大
       if (sequence == 0L) {
           // 阻塞到下一个毫秒，获得新的时间戳
           currStmp = getNextMill();
       }
     } else {
            //不同毫秒内，序列号置为0
            sequence = 0L;
   }

   lastStmp = currStmp;
   
   // MACHINE_LEFT = SEQUENCE_BIT; -> 12
   // DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT; -> 17
   // TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT; -> 22
   return (currStmp - START_STMP) << TIMESTMP_LEFT //时间戳部分
                | datacenterId << DATACENTER_LEFT       //数据中心部分
                | machineId << MACHINE_LEFT             //机器标识部分
                | sequence;                             //序列号部分
}

现在我们来看一下使用方式：

public static void main(String[] args) {
  SnowFlake snowFlake = new SnowFlake(2, 3);
  for (int i = 0; i < (1 << 12); i++) {
    System.out.println(snowFlake.nextId());
  }
}

现在我们已经可以利用 SnowFlake 对象生成唯一 ID 了，那这个唯一 ID 有什么用呢？这里举一个简单的应用场景，即基于 SnowFlake 的短网址生成器，其主要思路是使用 SnowFlake 算法生成一个整数，然后对该整数进行 62 进制编码最终生成一个短地址 URL。对短网址生成器感兴趣的小伙伴，可以参考 徐刘根 大佬在码云上分享的工具类。

最后我们来简单总结一下，本文主要介绍了什么是 Snowflake（雪花）算法、Snowflake 算法 ID 构成图及其优缺点，最后详细分析了 Github 上 beyondfengyu 大佬基于 Java 实现的 SnowFlake。在实际项目中，建议大家选用基于 Snowflake 算法成熟的开源项目，如百度的 UidGenerator 或美团的 Leaf。