Leaf

Leaf——美团点评分布式ID生成系统
美团开源的分布式 ID 生成系统，支持号段模式（Segment）和雪花模式（Snowflake）。

号段模式

号段模式基于数据库的“号段”思想来生成 ID。

号段模式 - 核心思想

从数据库中批量获取一个“号段”（例如 1-1000），缓存在本地内存中。
每次生成 ID 时，直接从内存中递增返回，避免频繁访问数据库。
当本地号段快用完时（比如剩余 10%），异步地向数据库申请下一个号段，保证连续性。

数据库中维护一张表 leaf_alloc，记录每个业务的当前最大 ID 和步长。
服务启动时，通过 UPDATE … SET max_id = max_id + step WHERE biz_tag = ‘order’ 获取一个号段 [max_id + 1, max_id + step]。
本地使用原子计数器在这个区间内递增生成 ID。

号段模式 - 特点

• 优点：
  性能高：大部分操作在内存中完成，数据库压力小。
  ID 有序：生成的 ID 是递增的，有利于数据库索引性能。
  容灾能力强：即使数据库暂时不可用，本地缓存的号段仍可继续使用一段时间。
• 缺点：
  强依赖数据库：初始号段获取依赖 DB，DB 宕机可能导致无法获取新号段（但有缓存缓冲）。
  存在“跳跃”：每次换号段时 ID 会有跳跃（如从 999 跳到 2000），不完全连续。
  需要管理多个业务的号段分配。

号段模式 - 适用场景

对 ID 有序性有要求的场景（如 MySQL 主键、时间序列数据）。
高并发、低延迟要求的业务（如订单号、支付流水号）。
可接受 ID 不完全连续，但希望整体趋势递增。

雪花模式

雪花模式 - 原理

雪花模式源自 Twitter 的 Snowflake 算法，是一种基于时间戳和机器标识的分布式 ID 生成算法。

一个 64 位的 Long 型 ID 被划分为几个部分：
| 1 bit | 41 bits | 10 bits | 12 bits |
| 符号位 | 时间戳 | 机器ID | 序列号 |

符号位：固定为 0，保证 ID 为正数。
时间戳（41位）：毫秒级时间戳，可使用约 69 年（从自定义纪元开始）。
机器ID（10位）：支持最多 1024 个节点（可拆分为数据中心 ID + 机器 ID）。
序列号（12位）：同一毫秒内的自增序列，支持每毫秒最多 4096 个 ID。
示例：5920134567890123456

雪花模式 - 特点

• 优点：
  完全去中心化：无需依赖数据库，纯内存计算。
  高性能：每秒可生成数十万 ID。
  趋势递增：时间维度上递增，有利于索引。
• 缺点：
  依赖系统时钟：如果服务器时间回拨（NTP 同步或手动调整），可能导致 ID 冲突。
  ID 过长且“不友好”：看起来像随机数，不利于排查。
  机器 ID 需要配置或注册中心分配。

雪花模式 - 适用场景

完全去中心化的微服务架构。
不希望依赖数据库的轻量级部署。
对性能要求极高，且能容忍时钟回拨风险的场景。
日志 trace ID、消息 ID、缓存 key 等。

雪花模式 - 解决时钟回拨问题

启动时解决 - 双重校验机制

• 持久化节点对比：服务启动时，首先检查在 ZooKeeper 的 leaf_forever节点下是否注册过持久顺序节点。如果存在，则比较节点中记录的上次上报时间和当前系统时间，如果当前时间更小，那么证明发生了回拨，服务会启动失败并触发报警。
• 集群时间校准：经过持久化节点通过第一步校验的节点，会获取 leaf_temporary 节点的所有临时节点，通过RPC查询节点的系统时间，计算平均时间作为集群时间，如果自身时间与平均值超过设定与之，则认定为时钟漂移，服务会启动失败。

运行时解决 - 三级回拨策略

• 轻度回拨（< 5ms）：采用等待策略，让当前线程睡眠两倍的回拨时间差后再次检查，如果仍旧存在问题则抛出异常。
• 中度回拨（> 5ms 且 < 100ms）：采用随机序号策略。直接使用随机数重置序列号，利用12位序列号的随机性来降低重复ID的概率，保证服务可用。
• 严重回拨（> 100ms)：服务直接拒绝生成ID并抛出异常，同事触发高级别告警。

依赖ZooKeeper问题

在本地文件系统缓存WorkerID，当ZooKeeper不可用时，通过本地缓存启动服务。

安装MySQL数据库

Rocky Linux安装MySQL

创建数据库和用户

-- 创建数据库
CREATE DATABASE IF NOT EXISTS leaf_db CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci;

-- 创建用户并授权（允许从任意主机连接）
CREATE USER 'leaf_user'@'%' IDENTIFIED BY 'BE1Mw1&@&7J3@p';
GRANT ALL PRIVILEGES ON leaf_db.* TO 'leaf_user'@'%';
FLUSH PRIVILEGES;

初始化 Leaf 表结构

USE leaf_db;

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(1024) DEFAULT NULL,
  `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
  PRIMARY KEY (`biz_tag`)
) ENGINE=InnoDB;

-- 插入测试业务标签
INSERT INTO leaf_alloc(biz_tag, max_id, step, description) VALUES('user_id', 1, 1000, '用户ID');
INSERT INTO leaf_alloc(biz_tag, max_id, step, description) VALUES('order_id', 1, 1000, '订单ID');

配置防火墙

sudo firewall-cmd --permanent --add-port=3306/tcp
sudo firewall-cmd --reload

构建 Leaf 的 Docker 镜像

git clone https://github.com/Meituan-Dianping/Leaf.git

安装git

sudo dnf install git -y

安装 ZooKeeper

配置对应的目录

# 创建用于 ZooKeeper 数据存储的目录
sudo mkdir -p /opt/zookeeper/data-{0..2}

# 设置权限（ZooKeeper 容器以非 root 用户运行，UID 通常为 1000）
sudo chown -R 1000:1000 /opt/zookeeper
sudo chmod -R 755 /opt/zookeeper

使用PV挂载到对应目录上

ggVG"+y

apiVersion: v1
kind: PersistentVolume
metadata:
  name: zk-data-0-pv
  labels:
    app: zookeeper
    ordinal: "0"
spec:
  capacity:
    storage: 1Gi
  accessModes:
    - ReadWriteOnce
  persistentVolumeReclaimPolicy: Retain
  hostPath:
    path: /opt/zookeeper/data-0
  nodeAffinity:
    required:
      nodeSelectorTerms:
      - matchExpressions:
        - key: kubernetes.io/hostname
          operator: In
          values:
          - k8s-node01  # 替换为实际节点名，如 k8s-node1
---
apiVersion: v1
kind: PersistentVolume
metadata:
  name: zk-data-1-pv
  labels:
    app: zookeeper
    ordinal: "1"
spec:
  capacity:
    storage: 1Gi
  accessModes:
    - ReadWriteOnce
  persistentVolumeReclaimPolicy: Retain
  hostPath:
    path: /opt/zookeeper/data-1
  nodeAffinity:
    required:
      nodeSelectorTerms:
      - matchExpressions:
        - key: kubernetes.io/hostname
          operator: In
          values:
          - k8s-node02   # 同上
---
apiVersion: v1
kind: PersistentVolume
metadata:
  name: zk-data-2-pv
  labels:
    app: zookeeper
    ordinal: "2"
spec:
  capacity:
    storage: 1Gi
  accessModes:
    - ReadWriteOnce
  persistentVolumeReclaimPolicy: Retain
  hostPath:
    path: /opt/zookeeper/data-2
  nodeAffinity:
    required:
      nodeSelectorTerms:
      - matchExpressions:
        - key: kubernetes.io/hostname
          operator: In
          values:
          - k8s-node01  # 同上