分布式 ID 分配:snowflake 雪花算法

前言

之前看一篇数据库自增 ID 可能溢出问题的文章。结果是如果只用单表,那么可以用 bigInt 类型;但一般不会这么做,因为数据量过大会导致查询很慢,所以就需要分库分表。那么分库分表后,各库及各表的 ID 如果识别,也就是说如何从某个变量来映射到指定的库和表,那么此时就需要一个分布式 ID 生成算法。正好就看到了 snowflake 雪花算法,还挺有名的,所以就写下相关的内容。

snowflake 雪花算法介绍

从网上来看,理解分布式id生成算法SnowFlake,这篇文章写的挺详细。我这篇主要写核心思想,及网友提到的一些问题来解答下,顺便把网上这篇需要纠正的地方纠正一下。相关 java 代码也是参考这篇博文的,如果自己想从 twitter scalar 源码上改写成 java 代码,应该也是不难的,为了省点事,就这么直接拿来用了,见笑。
这个twitter snowflake 是 twitter 在 github 的雪花算法源码,是用 scalar 写的,可以看下。接下来就详细讲讲雪花算法的核心思想。
分布式 ID 肯定有以下几个特点:

  1. ID 的唯一性,且正
  2. ID 的个数能满足分布式的需求
  3. 一对一的映射关系。比如查询等操作能找到相应的库和表

雪花算法的 ID 分配机制

file
上面这张是 64 位整数,在雪花算法中的各位数分配图。雪花算法产生的 ID 就是 64 位整数。
解释下图中的含义:
第 1 位:符号位,不用。ID 为正整数,所以此位可忽略。
第 2 位到第 42 位(共 41 位):用来记录时间戳,单位是毫秒,这是第一层的 ID。
第 43 位到第 52 位(共 10 位):工作机器的 ID,这是第二层的 ID。
第 53 位到第 64 位(共 12 位):序列号,这个可以理解为第三层的 ID。

第一层 ID 个数为 $ 2^{41} $,范围:0~$ 2^{41} - 1 $。我们可以算算它能表示几年。
1年 = 365 24 60 60 1000 毫秒,
第一层 ID 能表示的年数 = $\frac{2^{41} - 1}{365 * 24 * 60 * 60 * 1000} = 69.73057000098301 \approx 69$
第二层的 ID 个数为$ 2^{10} $,范围:0~$ 2^{10} - 1 $。它表示能部署的机器数(节点数)。
第三层的 ID 个数为$ 2^{12} $,范围:0~$ 2^{12} - 1 $。它表示一台机器上能能部署的应用数(这个可根据实际情况来确定使用在何处,比如微服务数 ID,水平切分的表 ID等)。

分布式 ID 分配代码

转自:理解分布式id生成算法SnowFlake

public class IdWorker{

    private long workerId;
    private long datacenterId;
    private long sequence;

    public IdWorker(long workerId, long datacenterId, long sequence){
        // sanity check for workerId
        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));
        }
        System.out.printf("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
                timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);

        this.workerId = workerId;
        this.datacenterId = datacenterId;
        this.sequence = sequence;
    }

    private long twepoch = 1288834974657L;

    private long workerIdBits = 5L;
    private long datacenterIdBits = 5L;
    private long maxWorkerId = -1L ^ (-1L << workerIdBits);
    private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
    private long sequenceBits = 12L;

    private long workerIdShift = sequenceBits;
    private long datacenterIdShift = sequenceBits + workerIdBits;
    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    private long sequenceMask = -1L ^ (-1L << sequenceBits);

    private long lastTimestamp = -1L;

    public long getWorkerId(){
        return workerId;
    }

    public long getDatacenterId(){
        return datacenterId;
    }

    public long getTimestamp(){
        return System.currentTimeMillis();
    }

    public synchronized long nextId() {
        long timestamp = timeGen();

        if (timestamp < lastTimestamp) {
            System.err.printf("clock is moving backwards.  Rejecting requests until %d.", 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 = 0;
        }

        lastTimestamp = timestamp;
        return ((timestamp - twepoch) << timestampLeftShift) |
                (datacenterId << datacenterIdShift) |
                (workerId << workerIdShift) |
                sequence;
    }

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

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

    //---------------测试---------------
    public static void main(String[] args) {
        IdWorker worker = new IdWorker(1,1,1);
        for (int i = 0; i < 30; i++) {
            System.out.println(worker.nextId());
        }
    }

}

在分库分表的应用

开篇提到过分库分表的 ID 溢出问题。那么如何使用雪花算法生成的ID应用到分库分表里面(以水平分库分表为例)?

我们知道一般分布式系统的ID映射关系采用一致性hash算法,那么现在要解决的问题就是用户的hash值映射到每个子库和子表中。
假设一个节点只有一个子库,子库中只包含水平切分的分量表,这也比较符合实际。
那么方案如下:

  1. 规定 long 型 ID 的前 41 位时间戳为 0,同时 10 位的机器 ID也为 0,即我们缩小了 ID 的表示范围;
  2. 12 位的工作 ID 就是我们现在的节点 ID,等价地也对应了 节点中的子库;
  3. 在查询时根据用户 IP,使用一致性 hash 算法,映射到相应的节点 ID,从而找到要操作的子库;
  4. 如果要查询某个用户的数据,而这些数据又分布在不同的子库中,那么就需要从机器 ID 从小到大分别到各子库中查询,然后把查询获得的数据进行统一处理。

水平分库分表时,肯定是表中的记录数已经达到了最大值,所以达到最大值的表不会再进行插入操作,而只做查询操作,故而根据机器 ID 从小到大分别到各子库查询出来的数据本身就是有序的(各表之间有序)。在数据库系统中,肯定是先做主从(这个是全量,主数据库用来插入,从数据库用来查询),然后再做分库分表(这个是分量)。分库分表时,不仅仅是主数据库分库,从数据库也要分库,从达到数据一致性。当然也可以不做主从,直接做分库分表,然后再对分库进行冗余配置,这也是一种方案。这里涉及到结构相同的多库时,时间延迟问题会影响数据一致性。

问题

最后解答下在网友提出的几个问题:
问:分布式系统中,不同机器的时间很可能是不一致的,如何保证ID的有序性?
答:可以规定使用某一台机器来生成 ID,即专用生成 ID 机器,做单个微服务。
问:所有生成的id按时间趋势递增?
答:这个应该是各集群之间的 ID 是时间递增的,集群内部 ID 只根据机器 ID 来区分。
问:请问微服务中怎么设计这个datacenterId和workId好?
答:这个就是雪花算法的 10 位和 12 位的数据,都给你设计好了。
问:请问 workid 具体怎么保证唯一呢?
答:如果单独使用 workid,那么就以单独 workid 的量作为前提来保证唯一性,此时需要修改雪花算法的代码。因为雪花算法是使用 64 位的 long 型数据,其实我们也可以改为 32 位 int 型数据,以符合我们的需求。

追求梦想,做最好的自己