分布式 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。

美团的 Leaf

Github

V1: DB 预分发

DB 之上挂 N 个 Server，每个 Server 启动时，都会去 DB 拿固定长度的 ID List。这样就做到了完全基于分布式的架构，同时因为 ID 是由内存分发，所以也可以做到很高效。接下来是数据持久化问题，Leaf 每次去 DB 拿固定长度的 ID List，然后把最大的 ID 持久化下来，也就是并非每个 ID 都做持久化，仅仅持久化一批 ID 中最大的那一个。

用户通过 Round-robin 的方式调用 Leaf Server 的各个服务，所以某一个 Client 获取到的 ID 序列可能是：1，1001，2001，2，1002，2002……也可能是：1，2，1001，2001，2002，2003，3，4……当某个 Leaf Server 号段用完之后，下一次请求就会从 DB 中加载新的号段，这样保证了每次加载的号段是递增的。

Begin
UPDATE table SET max_id=max_id+step WHERE biz_tag=xxx
SELECT tag, max_id, step FROM table WHERE biz_tag=xxx
Commit

生成环境的问题：

  • 在更新 DB 的时候会出现耗时尖刺，系统最大耗时取决于更新 DB 号段的时间。
  • 当更新 DB 号段的时候，如果 DB 宕机或者发生主从切换，会导致一段时间的服务不可用。

V2: 双 Buffer 优化

Leaf 采用了异步更新的策略，同时通过双 Buffer 的方式，保证无论何时 DB 出现问题，都能有一个 Buffer 的号段可以正常对外提供服务，只要 DB 在一个 Buffer 的下发的周期内恢复，就不会影响整个 Leaf 的可用性。

MongoDB 的 ObjectId

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

微信的 seqsvr

百度的 UidGenerator