分布式 ID 生成系统 Leaf 的设计思路，源码解读-六虎

本文正在参与「金石计划 . 瓜分6万现金大奖」

小伙伴们好呀，我是 4ye，今日来分享下最近研究的分布式 ID 生成体系 —— Leaf ，一起来思考下这个分布式ID的规划吧

什么是分布式ID？

ID 最大的特点是仅有

而分布式 ID，便是指分布式体系下的 ID，它是 大局仅有 的。

为啥需求分布式ID呢？

这就和仅有休戚相关了。

比方咱们用 MySQL 存储数据，一开端数据量不大，但是事务经过一段时刻的发展，单表数据每日剧增，终究突破 1000w，2000w …… 体系开端变慢了，此刻咱们已经尝试了 优化索引， 读写分离 ，升级硬件，升级网络 等操作，但是 单表瓶颈 仍是来了，咱们只能去 分库分表 了。

而问题也随着而来了，分库分表后，假如还用 数据库自增ID 的办法的话，那么在用户表中，就会出现 两个不同的用户有相同的ID 的情况，这个是不能承受的。

而 分布式ID大局仅有 的特点，正是咱们所需求的。

分布式ID的生成办法

UUID
数据库自增ID （MySQL，Redis）
雪花算法

基本就上面几种了，UUID 的最大缺陷便是太长，36个字符长度，并且无序，不适合。

而其他两种的缺陷还有办法弥补，或许这也是 Leaf 提供这两种生成 ID 办法的原因。

项目简介

Leaf ，分布式 ID 生成体系，有两种生成 ID 的办法：

号段形式
Snowflake形式

号段形式

在 数据库自增ID 的基础上进行优化

增加一个 segement ，削减访问数据库的次数。
双 Buffer 优化，提前缓存下一个 Segement，降低网络恳求的耗时（降低体系的TP999指标）

biz_tag用来区分事务，max_id表明该biz_tag目前所被分配的ID号段的最大值，step表明每次分配的号段长度

没优化前，每次都从 db 获取，现在获取的频率和 step 字段相关。

双 Buffer 优化思路

号段形式源码解读

SegmentService 构造办法

效果

配置 dataSource
设置 MyBatis
实例化 SegmentIDGenImpl
履行 init 办法

这段代码我也忘了哈哈，已经多久没直接用 mybatis 了，仍是重新去官网翻看的。

实例化 SegmentIDGenImpl 时，其中有两个变量要留心下

SEGMENT_DURATION，智能调理 step 的要害
cache ，其中 SegmentBuffer 是双 Buffer 的要害规划。

这儿先不打开，看看 init 办法先。

SegmentIDGenImpl init 办法

效果

履行 updateCacheFromDb 办法
开后台线程，每分钟履行一次 updateCacheFromDb() 办法

明显，中心在 updateCacheFromDb

updateCacheFromDb 办法

这儿就直接看源码和我加的注释

private void updateCacheFromDb() {
    logger.info("update cache from db");
    StopWatch sw = new Slf4JStopWatch();
    try {
      // 履行 SELECT biz_tag FROM leaf_alloc 句子，获取所有的 事务字段。
      List<String> dbTags = dao.getAllTags();
      if (dbTags == null || dbTags.isEmpty()) {
        return;
       }
      // 缓存中的 biz_tag
      List<String> cacheTags = new ArrayList<String>(cache.keySet());
      // 要插入的 db 中的 biz_tag
      Set<String> insertTagsSet = new HashSet<>(dbTags);
      // 要移除的缓存中的 biz_tag 
      Set<String> removeTagsSet = new HashSet<>(cacheTags);

      // 缓存中有的话，不必再插入，从 insertTagsSet 中移除
      for (int i = 0; i < cacheTags.size(); i++) {
        String tmp = cacheTags.get(i);
        if (insertTagsSet.contains(tmp)) {
          insertTagsSet.remove(tmp);
         }
       }
      
      // 为新增的 biz_tag 创立缓存 SegmentBuffer
      for (String tag : insertTagsSet) {
        SegmentBuffer buffer = new SegmentBuffer();
        buffer.setKey(tag);
        Segment segment = buffer.getCurrent();
        segment.setValue(new AtomicLong(0));
        segment.setMax(0);
        segment.setStep(0);
        cache.put(tag, buffer);
        logger.info("Add tag {} from db to IdCache, SegmentBuffer {}", tag, buffer);
       }

      
      // db中存在的，从要移除的 removeTagsSet 移除。
      for (int i = 0; i < dbTags.size(); i++) {
        String tmp = dbTags.get(i);
        if (removeTagsSet.contains(tmp)) {
          removeTagsSet.remove(tmp);
         }
       }
      
      // 从 cache 中移除不存在的 bit_tag。
      for (String tag : removeTagsSet) {
        cache.remove(tag);
        logger.info("Remove tag {} from IdCache", tag);
       }
     } catch (Exception e) {
      logger.warn("update cache from db exception", e);
     } finally {
      sw.stop("updateCacheFromDb");
     }
   }

履行完后，会出现这样的 log

Add tag leaf-segment-test from db to IdCache, SegmentBuffer SegmentBuffer{key='leaf-segment-test', segments=[Segment(value:0,max:0,step:0), Segment(value:0,max:0,step:0)], currentPos=0, nextReady=false, initOk=false, threadRunning=false, step=0, minStep=0, updateTimestamp=0}

最终 init 办法结束后，会将 initOk 设置为 true。

项目发动结束后，咱们就能够调用这个 API 了。

如图，访问 LeafController 中的 Segment API，能够获取到一个 id。

SegmentIDGenImpl get 办法

能够看到，init 不成功会报错。

以及会直接从 cache 中查找这个 key(biz_tag) , 没有的话会报错。

拿到这个 SegmentBuffer 时，还得看看它 init 了没有，没有的话用双查看锁的办法去更新

先来看下一眼 SegmentBuffer 的结构

SegmentBuffer 类

⭐updateSegmentFromDb 办法

这儿便是更新缓存的办法了，主要是更新 Segment 的 value ， max，step 字段。

能够看到有三个 if 分支，下面打开说

分支一：初始化

第一次，buffer 还没 init，如上图，履行完后会更新 SegmentBuffer 的 step 和 minStep 字段。

分支二：第二次更新

这儿主要是更新这个 updateTimestamp ，它的效果看分支三

分支三：剩余的更新

这儿就比较有意思了，便是说假如这个号段在 15分钟内用完了，那么它会扩展这个 step （不超越 10w），创立一个更大的 MaxId ，降低访问 DB 的频率。

那么，到这儿，咱们完成了 updateSegmentFromDb 办法，更新了 Segment 的 value ， max，step 字段。

但是，咱们不是每次 get 都走上面的流程，它还得走这个缓存办法

⭐getIdFromSegmentBuffer 办法

明显，这是另一个要点。

如图，在死循环中，先获取读锁，拿到当前的号段 Segment，进行判别

运用超越 10% 就开新线程去更新下一个号段
没超越则将 value （AtomicLong 类型）+1 ，小于 maxId 则直接返回。

这儿要要点留心 读写锁的运用 ，比方开新线程时，运用了这个写锁，里边的 nextReady 等变量运用了 volatile 修饰

这儿的中心便是切换 Segment。

至此，号段形式结束。

优缺陷

信息安全：假如ID是接连的，歹意用户的扒取作业就十分简单做了，直接按照次序下载指定URL即可；假如是订单号就更危险了，竞对能够直接知道咱们一天的单量。所以在一些应用场景下，会需求ID无规则、不规则。—— 《Leaf——美团点评分布式ID生成体系》

能够看到，这个号段形式的最大弊端便是信息不安全，所以在运用时得三思，能不能用到这些事务中去。

Snowflake形式

雪花算法，中心便是将 64bit 分段，用来表明时刻，机器，序列号等。

41-bit的时刻能够表明（1L<<41）/(1000L*3600*24*365)=69年的时刻，10-bit机器能够分别表明1024台机器。

12个自增序列号能够表明2^12个ID，理论上snowflake方案的QPS约为 2^12 * 1000 = 409.6w/s

这儿运用 Zookeeper 持久次序节点的特性自动对 snowflake 节点配置 wokerID，不必手动配置。

时钟回拨问题

Snowflake形式源码解读

这部分源码就不逐个打开了，直接展示中心代码

SnowflakeZookeeperHolder init 办法

这儿要注意调整这个 connectionTimeoutMs 和 sessionTimeoutMs ，否则两种形式都发动的话，这个 zk 的 session 或许会超时，形成发动失利。

图中流程

看看 zk 节点存不存在，不存在就创立
同时将 worker id 保存到本地。
创立定时使命，更新 znode。

SnowflakeIDGenImpl get 办法

这儿直接看代码和注释了

@Override
  public synchronized Result get(String key) {
    long timestamp = timeGen();
    //  发生了回拨，此刻时刻小于前次发号时刻
    if (timestamp < lastTimestamp) {
      long offset = lastTimestamp - timestamp;
      if (offset <= 5) {
        try {
          //时刻误差大小小于5ms，则等待两倍时刻
          wait(offset << 1);
          timestamp = timeGen();
          //仍是小于，抛异常并上报
          if (timestamp < lastTimestamp) {
            return new Result(-1, Status.EXCEPTION);
           }
         } catch (InterruptedException e) {
          LOGGER.error("wait interrupted");
          return new Result(-2, Status.EXCEPTION);
         }
       } else {
        return new Result(-3, Status.EXCEPTION);
       }
     }
    if (lastTimestamp == timestamp) {
      // sequenceMask = ~(-1L << 12 ) = 4095 二进制即 12 个1
      sequence = (sequence + 1) & sequenceMask;
      if (sequence == 0) {
        //seq 为0的时候表明是下一毫秒时刻开端对seq做随机
        sequence = RANDOM.nextInt(100);
        timestamp = tilNextMillis(lastTimestamp);
       }
     } else {
      //假如是新的ms开端
      sequence = RANDOM.nextInt(100);
     }
    lastTimestamp = timestamp;
    // timestampLeftShift = 22， workerIdShift = 12 
    long id = ((timestamp - twepoch) << timestampLeftShift) | (workerId << workerIdShift) | sequence;
    return new Result(id, Status.SUCCESS);
   }

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

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

API 效果

生成 ID

反解 ID

至此，这个 Snowflake 形式也了解结束了。

总结

看完上面两种形式，我觉得两种形式都有它适用的场景，号段形式更适合对内运用（比方用户ID），而假如你这个 ID 会被用户看到，暴露出去有其他危险（比方爬虫歹意爬取等），那就得多斟酌了，。而订单号就更适合用 snowflake 形式。

分布式ID 的特点

大局仅有
趋势递加（有序一向很重要，粗略有序仍是严格有序就看情况了）
可反解（可选）
信息安全（可选）

参考资料

Github 地址：github.com/Meituan-Dia…
Leaf——美团点评分布式ID生成体系：tech.meituan.com/2017/04/21/…
分布式id生成方案总结：www.cnblogs.com/javaguide/p…

分布式 ID 生成系统 Leaf 的设计思路，源码解读