分布式 ID 设计

分布式 ID 设计

自己设计

ID 类型

  • QPS 高:那么粒度要粗一些
  • 粒度小:到达毫秒级,每个毫秒预留 10 位顺序号,所以 QPS 最高达到 1024。每毫秒最多产生 1000 多个 ID。

时间同步

使用 Linux 的 crontab 周期性核准服务器时间:

ntpupdate -u pool.ntp.orgpool.ntp.org

ReentrantLock 生成序列

long sequence = 0;
long lastTimestamp = -1;
Lock = new ReentrantLock();

public void populateId(Id id, IdMeta idMeta) {
    lock.lock();
    try {
        long timestamp = TimeUtils.genTime();
        if (timestamp == lastTimestamp) {
            sequence++;
            sequence &= idMeta.geSeqBitsMask(); // 比如最多 1024 个
            if (sequence == 0) {
                timestamp = TimeUtils.tillNextTimeUnit(lastTimestamp);
            }
        } else {
            lastTimestamp = timestamp;
            sequence = 0;
        }

        id.setSeq(sequence);
        id.setTime(timestamp);
    } finally {
        lock.unlock();
    }
}

序列号用光,就等待进入下一秒:

long tillNextTimeUnit(long lastTimestamp) {
    long timestamp = TimeUntils.genTime();
    
    // 自旋,而非 Thread.sleep 来减少线程切换
    // 因为我们认为等待的时间不会太长
    while (timestamp <= lastTimestamp) {
        timestamp = TimeUntils.genTime();
    }

    return timestamp;
}

CAS 生成序列

class Variant {
    private long sequence = 0;
    private long lastTimestamp = -1;
}

private AtomicReference<Variant> variant = new AtomicReference<Varient>(new Varient());

public void populateId(Id id, IdMeta idMeta) {
    Variant varOld, varNew;
    long timestamp, sequence;

    while (true) {
        varOld = variant.get();

        timestamp = TimeUntils.genTime();
        sequence = varOld.sequence;

        if (timestamp = varOld.lastTimestamp) {
            sequence++;
            sequence &= idMeta.getSeqBitsMask();

            if (sequence == 0) {
                timestamp = TimeUntils.tillNextTimeUnit(varOld.lastTimestamp);
            }
        } else {
            sequence = 0;
        }

        varNew = new Variant();
        varNew.sequence = sequence;
        varNew.lastTimestamp = timestamp;

        if (variant.compareAndSet(varOld, varNew)) {
            id.setSeq(sequence);
            id.setTime(timestamp);
            break;
        }
    }
}

参考的是 《可伸缩服务架构:框架与中间件》的第一章

Twitter Snowflake

整体长度通常是 64 (1 + 41 + 10+ 12 = 64)位,适合使用 Java 语言中的 long 类型来存储。头部是 1 位的正负标识位。紧跟着的高位部分包含 41 位时间戳,通常使用 System.currentTimeMillis()。后面是 10 位的 WorkerID,标准定义是 5 位数据中心 + 5 位机器 ID,组成了机器编号,以区分不同的集群节点。最后的 12 位就是单位毫秒内可生成的序列号数目的理论极限。

基于 Java 的实现有很多:Snowflake

MongoDB 的 ObjectId

提供了一个 12 byte(96 位)的 ID 定义,其中 32 位用于记录以秒为单位的时间,机器 ID 则为 24 位,16 位用作进程 ID,24 位随机起始的计数序列。

微信的 seqsvr

百度的 UidGenerator