分布式 ID 之雪花算法实现

发表于 2020-03-24 更新于 2024-11-15

雪花算法介绍

雪花算法（Snowflake）是 Twitter 提出来的一个算法，其目的是生成一个 64 bit 的二进制数：

Snowflake

转换为十进制和十六进制分别如下图。其中十进制的最大长度为 19 位：

该二进制数分解如下：

42 bit：用来记录时间戳，表示自 1970-01-01T00:00:00Z 之后经过的毫秒数（millisecond），其中 1 bit 是符号位。由于精确到毫秒（millisecond），相比有符号 32 bit 所存储的精度为秒（second）的时间戳需要多 10 bit 来记录毫秒数（0-999）。42 bit 可以记录 69 年，如果设置好起始时间例如 2018 年，那么可以用到 2087 年。42 bit 时间戳范围如下：

// 0
long a = 0b00_00000000_00000000_00000000_00000000_00000000L;
// 999
long b = 0b00_00000000_00000000_00000000_00000011_11100111L;
// 2^41-1, 2199023255551
long c = 0b01_11111111_11111111_11111111_11111111_11111111L;

// 1970-01-01T00:00:00.000Z
Instant.ofEpochMilli(a).atZone(ZoneOffset.of("-00:00")).toLocalDateTime();
// 1970-01-01T00:00:00.999Z
Instant.ofEpochMilli(b).atZone(ZoneOffset.of("-00:00")).toLocalDateTime();
// 2039-09-07T15:47:35.551Z
Instant.ofEpochMilli(c).atZone(ZoneOffset.of("-00:00")).toLocalDateTime();

10 bit：用来记录机器 ID，最多可以记录 2^10-1=1023 台机器，一般用前 5 位代表数据中心，后面 5 位是某个数据中心的机器 ID
12 bit：循环位，用来对同一个毫秒之内产生的 ID，12 位最多可以记录 2^12-1=4095 个，也就是在同一个机器同一毫秒最多记录 4095 个，多余的需要进行等待下个毫秒。

上面只是一个将 64 bit 划分的标准，当然也不一定这么做，可以根据不同业务的具体场景来划分，比如下面给出一个业务场景：

服务目前 QPS10 万，预计几年之内会发展到百万。
当前机器三地部署，上海，北京，深圳都有。
当前机器 10 台左右，预计未来会增加至百台。

这个时候我们根据上面的场景可以再次合理的划分 64 bit，QPS几年之内会发展到百万，那么每毫秒就是千级的请求，目前10台机器那么每台机器承担百级的请求（100 W / 1000 ms / 10 台）。为了保证扩展，后面的循环位可以限制到 1024，也就是 2^10，那么循环位 10 位就足够了。

机器三地部署我们可以用 3 bit 总共 8 来表示机房位置；当前机器 10 台，为了保证能够扩展到百台那么可以用 7 bit 总共 128 来表示；时间位依然是 42 bit。那么还剩下 64-10-3-7-42 = 2 bit，剩下 2 bit 可以用来进行扩展。

雪花算法实现

下面是我的对雪花算法的实现，涉及几点思考：

为了节省空间、提升运算性能，主要使用到位运算，而不是字符串操作。
为了提高可配置性，将每一部分的位数抽取成了常量，以便自定义。
解决时间回拨问题：
- 如果回拨时长较短（可配置，代码中配了 5 ms），线程等待并重试即可；
- 如果回拨时长较长，则利用扩展位避免生成重复 ID（扩展位可配，代码中配置了 3 位，即最多支持 3 次回拨，超出则抛异常）。

import lombok.SneakyThrows;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import java.time.Instant;
import java.time.LocalDateTime;
import java.time.ZoneId;
import java.util.HashSet;
import java.util.Set;

import static org.junit.Assert.assertEquals;

@Slf4j
public class IdGeneratorTest {

    @Test
    public void test() {
        int initialCapacity = 1000;
        Set<Long> ids = new HashSet<>(initialCapacity);
        IdGenerator idGenerator = new IdGenerator(3, 31);
        
        for (int i = 0; i < initialCapacity; i++) {
            long id = idGenerator.nextId();
            ids.add(id);

            IdGenerator.log(id);
        }
        assertEquals(ids.size(), initialCapacity);
    }

}

@Slf4j
class IdGenerator {

    // 时间戳
    private long timestamp;
    // 数据中心
    private int dataCenterNo;
    // 机器
    private int workerNo;
    // 序列号
    private int seqNo;
    // 扩展位
    private int ext;

    // 数据中心 取值范围（十进制）：0~3
    private static final int DATA_CENTER_NO_BITS = 2;
    // 机器 取值范围（十进制）：0~31
    private static final int WORKER_NO_BITS = 5;
    // 序列号 取值范围（十进制）：0~4095
    private static final int SEQ_NO_BITS = 12;
    // 扩展位 取值范围（十进制）：0~7
    private static final int EXT_BITS = 3;

    // 数据中心 最大值（十进制）：3
    private static final int MAX_DATA_CENTER_NO = (1 << DATA_CENTER_NO_BITS) - 0B1;
    // 机器 最大值（十进制）：31
    private static final int MAX_WORKER_NO = (1 << WORKER_NO_BITS) - 0B1;
    // 序列号 最大值（十进制）：4095
    private static final int MAX_SEQ_NO = (1 << SEQ_NO_BITS) - 0B1;
    // 扩展位 最大值（十进制）：7
    private static final int MAX_EXT = (1 << EXT_BITS) - 0B1;
  
    // 时间戳 左移 22 位
    private static final int TIMESTAMP_SHIFT = DATA_CENTER_NO_BITS + WORKER_NO_BITS + SEQ_NO_BITS + EXT_BITS;
    // 数据中心 左移 20 位
    private static final int DATA_CENTER_NO_SHIFT = WORKER_NO_BITS + SEQ_NO_BITS + EXT_BITS;
    // 机器 左移 15 位
    private static final int WORKER_NO_SHIFT = SEQ_NO_BITS + EXT_BITS;
    // 序列号 左移 3 位
    private static final int SEQ_NO_SHIFT = EXT_BITS;

    // 最大回拨毫秒数
    private static final int MAX_BACKWARD_MILLIS = 5;

    /**
     *
     * @param dataCenterNo 数据中心编号
     * @param workerNo 机器编号
     */
    public IdGenerator(int dataCenterNo, int workerNo) {
        if (Integer.toBinaryString(dataCenterNo).length() > DATA_CENTER_NO_BITS) {
            throw new IllegalArgumentException(String.format("当前数据中心编号 %s 超限，最大支持 %s", dataCenterNo, MAX_DATA_CENTER_NO));
        } else if (Integer.toBinaryString(workerNo).length() > WORKER_NO_BITS) {
            throw new IllegalArgumentException(String.format("当前机器编号 %s 超限，最大支持 %s", workerNo, MAX_WORKER_NO));
        }
        this.dataCenterNo = dataCenterNo;
        this.workerNo = workerNo;
    }

    /**
     * 生成分布式 ID
     * @return 分布式 ID
     */
    public synchronized long nextId() {
        long now = System.currentTimeMillis();
        // init or reset
        if (timestamp == 0 || timestamp < now) {
            timestamp = now;
            seqNo = 0;
        }
        // seqNo increment
        else if (timestamp == now) {
            if (seqNo < MAX_SEQ_NO) {
                seqNo++;
            } else {
                log.warn("序列号已耗尽，等待重新生成。seqNo = {}, MAX_SEQ_NO = {}", seqNo, MAX_SEQ_NO);
                return sleepAndNextId(1);
            }
        }
        // clock backward
        else {
            return nextIdForBackward(now);
        }

        return timestamp << TIMESTAMP_SHIFT
                | dataCenterNo << DATA_CENTER_NO_SHIFT
                | workerNo << WORKER_NO_SHIFT
                | seqNo << SEQ_NO_SHIFT
                | ext;
    }

    private long nextIdForBackward(long now) {
        log.warn("发生时间回拨，timestamp = {}, now = {}", timestamp, now);

        long duration = timestamp - now;
        // 回拨不多，直接等待并重试
        if (duration <= MAX_BACKWARD_MILLIS) {
            return sleepAndNextId(duration);
        }
        // 回拨过多，则使用扩展位
        else {
            if (ext < MAX_EXT) {
                // 将时间戳修正为回拨时间，为防止重复生成 ID，扩展位加一，并重试
                ext++;
                timestamp = now;
                return nextId();
            } else {
                throw new IllegalStateException(String.format("扩展位已耗尽。ext = %s, MAX_EXT = %s", ext, MAX_EXT));
            }
        }
    }

    @SneakyThrows
    private long sleepAndNextId(long millis) {
        Thread.sleep(millis);
        return nextId();
    }

    public static void log(long id) {
        long timestamp = id >> TIMESTAMP_SHIFT;
        long dataCenterNo = id >> DATA_CENTER_NO_SHIFT & MAX_DATA_CENTER_NO;
        long workerNo = id >> WORKER_NO_SHIFT & MAX_WORKER_NO;
        long seqNo = id >> SEQ_NO_SHIFT & MAX_SEQ_NO;
        long ext = id & MAX_EXT;

        log.info("Binary is {}, id is {}", Long.toBinaryString(id), id);
        log.info("Binary is {}, time is {}", Long.toBinaryString(timestamp), getLocalDateTime(timestamp));
        log.info("Binary is {}, dataCenterNo is {}", Long.toBinaryString(dataCenterNo), dataCenterNo);
        log.info("Binary is {}, workerNo is {}", Long.toBinaryString(workerNo), workerNo);
        log.info("Binary is {}, seqNo is {}", Long.toBinaryString(seqNo), seqNo);
        log.info("Binary is {}, ext is {}", Long.toBinaryString(ext), ext);
    }

    private static LocalDateTime getLocalDateTime(long timestamp) {
        return Instant.ofEpochMilli(timestamp).atZone(ZoneId.systemDefault()).toLocalDateTime();
    }

}

输出结果：

Binary is 110000011011010011001111001101001100000111000011000000000100000, id is 6979004485312020512
Binary is 11000001101101001100111100110100110000011, time is 2022-09-23T17:12:12.931
Binary is 10, dataCenterNo is 2
Binary is 11, workerNo is 3
Binary is 100, seqNo is 4
Binary is 0, ext is 0

位运算过程如下：

timestamp = id >> TIMESTAMP_SHIFT

1 2	01100000 11011010 01100111 10011010 01100000 11100001 10000000 00100000 >> 01100000 11011010 01100111 10011010 01100000 11

dataCenterNo = id >> DATA_CENTER_NO_SHIFT & MAX_DATA_CENTER_NO

   01100000 11011010 01100111 10011010 01100000 11100001 10000000 00100000
>> 01100000 11011010 01100111 10011010 01100000 1110
 &                                                11
 =                                                10

workerNo = id >> WORKER_NO_SHIFT & MAX_WORKER_NO

   01100000 11011010 01100111 10011010 01100000 11100001 10000000 00100000
>> 01100000 11011010 01100111 10011010 01100000 11100001 1
 &                                                  1111 1
 =                                                     1 1

seqNo = id >> SEQ_NO_SHIFT & MAX_SEQ_NO

   01100000 11011010 01100111 10011010 01100000 11100001 10000000 00100000
>> 01100000 11011010 01100111 10011010 01100000 11100001 10000000 00100
 &                                                        1111111 11111
 =                                                                  100

ext = id & MAX_EXT

1
2
3

  01100000 11011010 01100111 10011010 01100000 11100001 10000000 00100000
&                                                                     111
=                                                                       0

延伸阅读

位运算

位运算符如下：

&：按位与
|：按位或
~：按位非
^：按位异或
<<：左位移（M << n = M * 2^n）
>>：右位移（M >> n = M / 2*n）
>>>：无符号右移

例如，Java 中求 key 应当放到散列表的哪个位置（offset）：

static final int getOffset(Object key, int length) 
    int hashcode;
    int hash = (hashcode = key.hashCode()) ^ (hashcode >>> 16);
    int offset = hash & (length - 1);
    log.info("key: {}, hashcode: {}, hash: {}, offset: {}", key, Integer.toBinaryString(hashcode), Integer.toBinaryString(hash), offset);
    return offset;
}

参考：

《Java 位运算符 &、|、^、~、<<、>>、>>>》
《按位异或的用途》
《按位与的用途：子网划分（IP 地址与子网掩码做与运算求子网地址）》

UNIX 时间戳

参考：UNIX 时间戳总结