分布式id实现方案，选leaf吗？

田哥 Java后端技术全栈

你好，我是田哥

最近，大部分时间都是在给小伙伴们做简历优化、模拟面试以及面试辅导。

如果想跳槽，这里给你推荐一篇文章，便于找到更好的工作：

Java后端面试复习规划表，5万字

本文介绍了分布式ID的几种实现方式，及其优缺点。最后深入聊聊美团开源的Leaf组件，展示了它的实现亮点。

一、引入

1.1 为什么需要分布式ID

以数据库为例，业务数据量不大时，单库单表完全够用，或者搞个主从同步、读写分离来提高性能。当业务迅速扩张，需要对数据库进行分库分表时，ID生成就不能简单依靠数据库表主键自增了。因为这时需要保证数据库表ID全局唯一。

1.2 分布式ID需要满足的条件

全局唯一：不能出现重复ID；
高性能、高可用：生成ID速度快，接近于100%的可用，不会成为业务瓶颈；
趋势递增：由于大多数数据库使用B-tree按索引有序存储数据，主键ID递增能保证新增记录时不会发生页分裂，保证写入性能；
信息安全：如果ID连续或规则明显，恶意用户或竞争对手爬取信息就非常方便。因此一些场景比如订单，会要求ID不规则。

二、分布式ID的实现

2.1 UUID

UUID (Universally Unique IDentifier) 是一个128位数字的全球唯一标识，标准型式包含32个16进制数字，用连字号分为五段，形式为8-4-4-4-12。它生成时用到了网卡地址（即MAC address）、纳秒级时间等。以Java语言为例，生成UUID使用java.util.UUID即可，使用非常简单。

import java.util.UUID;

public class UniqueId {
  public static void main(String[] args) {
    String uuid = UUID.randomUUID().toString();
    // 结果示例：2e55beed-6a65-47f8-b269-00b518d7da6a
    System.out.println(uuid);
    String uuid2 = uuid.replaceAll("-", "");
    // 结果示例：2e55beed6a6547f8b26900b518d7da6a
    System.out.println(uuid2);
  }
}

优点：本地生成，性能非常高，使用简单缺点：

太长不易存储：去掉连字号后的16进制有32字符，太长了，作为表主键应当越短越好；
信息不安全：可能会造成MAC地址泄漏；这个漏洞曾被用于寻找“梅丽莎病毒”的作者；
无序性：用UUID做表主键，在新增记录时页分裂更加频繁，严重影响写入性能。

2.2 数据库自增ID

用一个专门的表生成自增ID，提供给其他表使用。以MySQL为例，创建下面的这张表，当需要一个ID时，向表中插入一条记录返回主键id即可。

CREATE TABLE generate_id {
 id BIGINT(20) UNSIGNED NOT NULL AUTO_INCREMENT,
 content CHAR(1) NOT NULL DEFAULT '' COMMENT '无实际意义',
 PRIMARY KEY (id),
} ENGINE=INNODB;

缺点是依赖于数据库服务，存在单点故障，且性能瓶颈明显。解决这个不足，通常有两种方式：一是使用数据库集群；二是采用号段模式。

2.2.1 数据库集群

还是以MySQL为例，我们可以搭建集群，提高可用性。给各个节点的auto_increment设置不同的起始值和自增步长。假设MySQL集群有3个节点，可以做下面的设置，这样每个节点都能生成唯一ID。

节点1生成的ID：1、4、7、10......
节点2生成的ID：2、5、8、11......
节点3生成的ID：3、6、9、12......

-- 对节点1
SET @auto_increment_offset = 1; -- 起始值
SET @auto_increment_increment =3; -- 步长

-- 对节点2
SET @auto_increment_offset = 2;
SET @auto_increment_increment =3;

-- 对节点3
SET @auto_increment_offset = 3;
SET @auto_increment_increment =3;

2.2.2 号段模式

号段模式下，一次请求将从数据库获取一批自增ID，减小访库次数，降低数据库读写压力。

CREATE TABLE `segment_id` (
  `biz_tag` VARCHAR(32) NOT NULL DEFAULT '' COMMENT '业务类型',
  `max_id` BIGINT(20) NOT NULL DEFAULT '1' COMMENT '当前最大id',
  `step` INT(11) NOT NULL COMMENT '号段步长',
  `version` INT(20) NOT NULL COMMENT '版本号',
  `update_time` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
  PRIMARY KEY (`biz_tag`)
) ENGINE=INNODB DEFAULT CHARSET=utf8;

比如使用下面的SQL，当需要ID时，先发起查询，然后更新max_id，更新成功则表示获取到新号段[max_id, max_id+step)。

UPDATE segment_id SET max_id=max_id+step, VERSION = VERSION + 1 WHERE VERSION = #{version} and biz_tag = #{biz_tag};

2.3 基于Redis生成唯一ID

利用Redis的 incr命令，实现ID的原子性自增。需注意Redis持久化对可靠性的影响。

RDB持久化方式：定时保存当前数据快照，假如ID自增但Redis没及时持久化就挂掉了，重启Redis后会出现ID重复；
AOF持久化方式：会对每条写命令进行持久化，即使Redis挂掉了也不会出现ID重复的情况，但是Redis重启恢复数据时间较长。

下面是一个简单实现。

import org.springframework.data.redis.core.StringRedisTemplate;

public class RedisIdWorker {
  private StringRedisTemplate stringRedisTemplate;

  public RedisIdWorker(StringRedisTemplate stringRedisTemplate) {
    this.stringRedisTemplate = stringRedisTemplate;
  }

  public long nextId(String bizTag) {
    return stringRedisTemplate.opsForValue().increment("id:" + bizTag);
  }
}

此外，我们还可以给ID加上毫秒级时间戳前缀，即使使用RDB持久化，Redis故障时也不会出现ID重复。下面是不考虑时钟回拨时的一个实现。

public class RedisIdWorker {
  // 开始时间戳
  private static final long BEGIN_TIMESTAMP = 1705221450434L;
  // id位数
  private static final int COUNT_BITS = 24;

  private StringRedisTemplate stringRedisTemplate;

  public RedisIdWorker(StringRedisTemplate stringRedisTemplate) {
    this.stringRedisTemplate = stringRedisTemplate;
  }

  public long nextId(String bizTag) {
    // 生成时间戳
    LocalDateTime now = LocalDateTime.now();
    long nowSecond = now.toEpochSecond(ZoneOffset.UTC);
    long timestamp = nowSecond - BEGIN_TIMESTAMP;

    // 2.2.自增长
    long count = stringRedisTemplate.opsForValue().increment("id:" + bizTag);
    return timestamp << COUNT_BITS | count;
  }
}

2.4 雪花算法

雪花算法（SnowFlake）是Twitter公司采用并开源的一种算法，能在分布式系统中产生全局唯一且趋势递增的ID。规则如下：

第一部分：占用1bit，其值始终是0，没有实际作用；
第二部分：时间戳，占用41bit，精确到毫秒，总共可以容纳约69年的时间；
第三部分：工作机器id，占用10bit；可以分配高位几个bit表示数据中心ID，剩余bit表示机器节点ID，最多可以容纳1024个节点；
第四部分：序列号，占用12bit，每个节点每毫秒从0开始累加，最大到4095。

理论上snowflake方案的QPS约为409.6w/s。网上有不少实现，不再赘述。优点：生成的ID趋势递增；本地生成且不依赖第三方系统，性能极高。缺点：强依赖于机器时钟，如果发生时钟回拨，将导致发号重复或服务不可用。

三、开源组件——美团Leaf

Leaf是美团基础研发平台推出的一个分布式ID生成服务，具备高可靠、低延迟、全局唯一等特点，支持号段、雪花算法两种模式。感兴趣的小伙伴，可以访问官网了解更多信息。

官网：tech.meituan.com/2019/03/07/… github：github.com/Meituan-Dia…

3.1 号段模式

整体结构如图，强依赖于数据库，使用前先创建表。

CREATE DATABASE leaf;
CREATE TABLE `leaf_alloc` (
  `biz_tag` varchar(128)  NOT NULL DEFAULT '', -- 区分业务，如订单、商品等
  `max_id` bigint(20) NOT NULL DEFAULT '1', -- 号段的起始值
  `step` int(11) NOT NULL, -- 步长
  `description` varchar(256)  DEFAULT NULL,
  `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
  PRIMARY KEY (`biz_tag`)
) ENGINE=InnoDB;

核心接口com.sankuai.inf.leaf.IDGen有三个实现，号段模式实现是SegmentIDGenImpl，有两大特点：

// key是biz_tag
private Map<String, SegmentBuffer> cache = new ConcurrentHashMap<String, SegmentBuffer>();

public boolean init() {
    logger.info("Init ...");
    // 首次加载所有biz_tag记录，并更新缓存
    updateCacheFromDb();
    initOK = true;
    // 启动定时任务，每分钟更新缓存
    updateCacheFromDbAtEveryMinute();
    return initOK;
}

@Override
public Result get(final String key) {
    if (!initOK) {
        return new Result(EXCEPTION_ID_IDCACHE_INIT_FALSE, Status.EXCEPTION);
    }
    if (cache.containsKey(key)) {
        SegmentBuffer buffer = cache.get(key);
        // 双重检查
        if (!buffer.isInitOk()) {
            synchronized (buffer) {
                if (!buffer.isInitOk()) {
                    try {
                        // 当前线程亲自加载第一个Segment
                        updateSegmentFromDb(key, buffer.getCurrent());
                        logger.info("Init buffer. Update leafkey {} {} from db", key, buffer.getCurrent());
                        buffer.setInitOk(true);
                    } catch (Exception e) {
                        logger.warn("Init buffer {} exception", buffer.getCurrent(), e);
                    }
                }
            }
        }
        // 获取ID
        return getIdFromSegmentBuffer(cache.get(key));
    }
    return new Result(EXCEPTION_ID_KEY_NOT_EXISTS, Status.EXCEPTION);
}

3.1.1 双buffer

当获取ID的并发很高时，如果在当前号段用完时，才去数据库获取下一个号段，此时耗时将明显增加。为此，Leaf采用了双Buffer异步更新的策略，保证无论何时，都能有一个Buffer的号段可以正常对外提供服务。

3.1.2 动态调整Step

假设服务QPS为Q，号段长度为L，号段更新周期为T，那么Q * T = L。如果L固定不变，QPS增长时，T会越来越小，即更新库表越来越频繁，且DB故障时缓存的号段能够支撑服务正常运行的时间更短了。所以，Leaf每次更新号段的时候，会根据与上一次更新更新号段的间隔T和号段长度step，来决定这次的号段长度nextStep：

T < 15min，nextStep = step * 2，对应高QPS
15min < T < 30min，nextStep = step，对应正常QPS
T > 30min，nextStep = step / 2，对应低QPS

总之，QPS越高，号段长度将变大；QPS越低，号段长度将变小。（有上下限限制）

3.2 雪花算法

美团Leaf的雪花算法，ID构成与前面提到的一致，机器号占10个bit。使用时需要的配置如下：


leaf.name=unique-id
leaf.snowflake.enable=true
leaf.snowflake.zk.address=192.168.43.105:2181
# 不是服务端口或zk端口，是Leaf在zk上注册时的端口
leaf.snowflake.port=8870

现在，我们关注以下两个方面，并从源码中寻找答案：

如何高效分配workId？
如何解决时钟回拨导致ID重复？

3.2.1 workId分配

当分布式ID服务集群节点数量较小时，完全可以手动配置workId。Leaf中使用ZooKeeper发号。代码实现是com.sankuai.inf.leaf.snowflake.SnowflakeIDGenImpl。

// SnowflakeZookeeperHolder中
public boolean init() {
    try {
        CuratorFramework curator = createWithOptions(connectionString, new RetryUntilElapsed(1000, 4), 10000, 6000);
        curator.start();
        Stat stat = curator.checkExists().forPath(PATH_FOREVER);
        if (stat == null) {
            //不存在根节点,机器第一次启动,创建/snowflake/ip:port-000000000,并上传数据
            zk_AddressNode = createNode(curator);
            // 将workerID保存到本地文件
            updateLocalWorkerID(workerID);
            //定时上报本机时间给forever节点
            ScheduledUploadData(curator, zk_AddressNode);
            return true;
        } else {
            // ......省略
        } catch(Exception e){
            LOGGER.error("Start node ERROR {}", e);
            try {
                // 异常时（包括zooeeperk故障）从本地文件加载workId
                Properties properties = new Properties();
                properties.load(new FileInputStream(new File(PROP_PATH.replace("{port}", port + ""))));
                workerID = Integer.valueOf(properties.getProperty("workerID"));
                LOGGER.warn("START FAILED ,use local node file properties workerID-{}", workerID);
            } catch (Exception e1) {
                LOGGER.error("Read file error ", e1);
                return false;
            }
        }
        return true;
    }
}

可见，Leaf依靠zookeeper为各节点生成递增的workerId：

当Leaf节点首次启动时，连接zookeeper并在/snowflake/{leaf.name}/forever下创建永久有序节点，节点序号就是workId；key格式为ip:prot-序号，value格式如下;
不是首次启动时，连接zookeeper读取/snowflake/{leaf.name}/forever下所有节点，用ip:prot查找Leaf实例对应的key，从key中截取workId；
一旦获取到workId，将保存到本地文件中；当启动Leaf节点时zookeeper故障了，将会从本地文件读取workId。

{
  "ip" : "192.168.43.16",
  "port" : "8870",
  "timestamp" : 1705323905246
}

注意，所有Leaf实例，应该配置相同的leaf.name、leaf.snowflake.zk.address，否则Leaf集群中workId将出现重复。

3.2.2 应对时钟回拨

启动时检查

在Leaf实例启动后，会隔3秒更新zookeeper节点数据，上报当前服务器时间。该时间将被用于Leaf启动时，与机器本地时间进行比较。

假设Leaf节点宕机需要重启，此时将检查机器本地时间，是否小于zookeeper节点保存的时间戳；如果是则说明发生了时钟回拨，此时抛出异常、启动失败。

public boolean init() {
    // ......省略
    if (workerid != null) {
        //有自己的节点,zk_AddressNode=ip:port
        zk_AddressNode = PATH_FOREVER + "/" + realNode.get(listenAddress);
        workerID = workerid;
        // 比较本地时间与zk节点中的时间戳，如果本地时间更小，则抛出异常
        if (!checkInitTimeStamp(curator, zk_AddressNode)) {
            throw new CheckLastTimeException("init timestamp check error,forever node timestamp gt this node time");
        }
        // 启动定时任务，每隔3秒上报本地时间
        doService(curator);
        // 更新本地workerID文件
        updateLocalWorkerID(workerID);
        LOGGER.info("[Old NODE]find forever node have this endpoint ip-{} port-{} workid-{} childnode and start SUCCESS", ip, port, workerID);
    }
    // ......省略
}

此外，我们在官网（https://tech.meituan.com/2017/04/21/mt-leaf.html）上，看到了下面这张图。图中圈出的部分，在源码中并没有找到对应实现。猜测，开源版本和美团真正使用的版本间可能存在差异。

运行时检查

Leaf服务运行中，每生成一个id，会先比较当前时间与上一个id的timestamp；如果当前时间更小，说明发生了时钟回拨。回拨小于5毫秒时，则计时等待两倍的回拨时间；如果回拨超过5毫秒，则返回负数。

总结

虽然做了一些努力，但是Leaf并没有完全解决时钟回拨问题。

我们看下面两个场景：

启动前，服务器时间进行了回拨；启动时连接Zookeeper失败，会使用本地文件中保存的workerId，此时跳过了时间检查将启动成功，可能会造成ID重复；
Leaf节点上报给zookeeper的时间戳是2024-01-16 08:15:00.000，最后一次生成的ID时间戳是2024-01-16 08:15:02.999，还没来得及再次上报zk本地时间，该节点宕机了。在启动之前，发生了时钟回拨，该节点重启时本地时间为2024-01-16 08:15:01.000；大于zookeeper中记录的时间戳，允许启动。但是，接下来两秒内生成的ID，都可能是之前已经生成过的。
Leaf运行中发现回拨超过5ms，会返回负数。

好了，今天就分享到这里。

回复77，免费获取《面试小抄》

回复电子书，免费获取《200本后端必读书籍》