分佈式 id 實現方案，選 leaf 嗎？

本文介紹了分佈式 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，會返回負數。

好了，今天就分享到這裏。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/B9rc6Q4aVovIptCFDaWKog