分布式Id生成策略-美团Leaf

🕗 发布于 2024-09-22 04:54 分布式

之前在做物流相关的项目时候，需要在分布式系统生成运单的id。

1.需求：

1.全局唯一性：不能出现重复的ID。（基本要求）

2.递增：大多数关系型数据库（如 MySQL）使用 B+ 树作为索引结构。如果 ID 是递增的，新数据总是追加到索引的末尾，这样索引的维护成本较低，因为数据库不需要频繁调整树的结构。相反，如果 ID 是随机的，数据插入时可能需要频繁调整索引结构，导致写入性能下降。

3.业务性：对具体的场景的ID要具备业务的特性，比如顺丰运单ID为类似SF1000000000760

4.精简性：某些场景下的ID不宜过长，所以对位数/长度有所限制。

在分布式系统中我们还应该考虑：生成方案能子啊多节点正常工作，能够有一定的解决故障问题，有高可用性，生成ID的速率要快，能够随业务扩展进行水平拓展，比如在分库分表后也能兼容原来的ID。

2.方案

有几个方案可以考虑：

本地的UUID生成：它的优点的生成速度很快，产生的值也几乎达到不重复的要求，但是产生的ID值比较长，可以达到36个字符，可读性还非常差，而且ID完全随机，没有任何的顺序。因此这个方案不考虑。

依靠数据库自增特性：为不同业务模块建立一张自增表维护递增序列。这种方法比较简单，靠数据库保证自增机制。缺点也很明显，当数据库异常整个系统不可用，而且ID生成的性能瓶颈也限制在单台MYSQL数据库。单台数据库性能问题可以同过部署多态机器，每个机器设置不同初始值，并且步长和机器数相同来优化。但是也带来很多问题，比如扩容很是麻烦。

Redis实现：通过给不同业务设计不同的key，通过INCR命令，对key自增，得到全局唯一并有序的ID。Redis每秒支持10W的读写，所以性能问题得到解决，但是Redis依靠内存，虽然有持久化机制，但是它持久化是先写内存再异步刷盘，遇到没来得及持久化就宕机也是会出大问题的。

雪花算法： 是 Twitter 于 2010 年开源的一种分布式唯一 ID 生成算法，它可以在分布式系统中生成高效、有序的唯一 ID。雪花算法生成的 ID 是一个 64 位的长整型（long），在保证唯一性的同时，也确保了生成的 ID 按时间顺序递增。

在这里插入图片描述

全局唯一性：生成的 ID 保证全局唯一，雪花算法结合时间戳、机器 ID 和序列号确保在分布式系统中不会产生重复的 ID。
高效生成：雪花算法不依赖数据库，因此生成 ID 的过程非常高效，可以在本地的内存中生成，具有极高的性能。每台机器每秒钟可以生成上百万个 ID。
趋势递增：生成的 ID 是按时间顺序递增的，尤其是基于时间戳的部分，使得 ID 具有递增的特性。这对数据库插入数据时索引的维护非常友好（例如 B+ 树结构索引的维护成本较低）。
灵活可扩展：通过调整数据中心 ID 和机器 ID 的位数分配，可以根据业务的需要适当扩大集群规模或提升单机 ID 生成的并发能力。

雪花算法依赖 机器码 来保证不同机器生成的 ID 唯一性。如果在分布式环境中多台机器未能准确区分它们的机器码，可能导致多个机器在同一时间生成相同的 ID，造成 ID 冲突。因此，在分布式系统中，每台服务器、虚拟机或容器必须手动指定一个唯一的机器标识符。**

雪花算法的不足

依赖机器时间：由于 ID 的递增性依赖时间戳，一旦服务器的系统时钟发生回拨，可能会引发 ID 冲突或无法生成 ID 的问题。虽然有一些解决方案（如等待或借助其他算法生成 ID），但还是可能影响生成 ID 的稳定性。

3.美团Leaf

下面就将引入我选取的美团Leaf这个id生成策略。

其源码托管于GitHub：https://github.com/Meituan-Dianping/Leaf

这里有个美团的技术播客，专门介绍了Leaf：https://tech.meituan.com/2017/04/21/mt-leaf.html

目前Leaf覆盖了美团点评公司内部金融、餐饮、外卖、酒店旅游、猫眼电影等众多业务线。在4C8G VM基础上，通过公司RPC方式调用，QPS压测结果近5w/s，TP999 1ms。

Leaf 提供两种生成的ID的方式（segment模式和snowflake模式），我们采用segment模式（号段）来生成运单号。

号段模式

号段模式采用的是基于MySQL数据生成id的，它并不是基于MySQL表中的自增长实现的，因为基于MySQL的自增长方案对于数据库的依赖太大了，性能不好，Leaf的号段模式是基于一张表来实现，每次获取一个号段，生成id时从内存中自增长，当号段用完后再去更新数据库表，如下：

在这里插入图片描述

字段说明：

biz_tag：业务标签，用来区分业务
max_id：表示该biz_tag目前所被分配的ID号段的最大值
step：表示每次分配的号段长度。如果把step设置得足够大，比如1000，那么只有当1000个号被消耗完了之后才会去重新读写一次数据库。读写数据库的频率从1减小到了1/step。
description：描述
update_time：更新时间

架构图如下：

在这里插入图片描述

图片来源：https://tech.meituan.com/2017/04/21/mt-leaf.html

说明：test_tag在**第一台Leaf机器上是1_{1000的号段**，当这个号段用完时，会去加载另一个长度为step=1000的号段，假设另外两台号段都没有更新，这个时候第一台机器新加载的号段就应该是3001}4000。同时数据库对应的biz_tag这条数据的max_id会从3000被更新成4000，更新号段的SQL语句如下：

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

Leaf 取号段的时机是在号段消耗完的时候进行的，也就意味着号段临界点的ID下发时间取决于下一次从DB取回号段的时间，并且在这期间进来的请求也会因为DB号段没有取回来，导致线程阻塞。如果请求DB的网络和DB的性能稳定，这种情况对系统的影响是不大的，但是假如取DB的时候网络发生抖动，或者DB发生慢查询就会导致整个系统的响应时间变慢。Leaf服务内部有号段缓存，即使DB宕机，短时间内Leaf仍能正常对外提供服务。

双buffer优化

Leaf为此做了优化，增加了双buffer优化。

当号段消费到某个点时就异步的把下一个号段加载到内存中。而不需要等到号段用尽的时候才去更新号段。这样做就可以很大程度上的降低系统的TP999指标。
在这里插入图片描述

双buffer原理，来自：https://tech.meituan.com/2017/04/21/mt-leaf.html

采用双buffer的方式，**Leaf服务内部有两个号段缓存区segmen。**当前号段已下发10%时，如果下一个号段未更新，则另启一个更新线程去更新下一个号段。当前号段全部下发完后，如果下个号段准备好了则切换到下个号段为当前segment接着下发，循环往复。

每个biz-tag都有消费速度监控，通常推荐segment长度设置为服务高峰期发号QPS（秒处理事务数）的600倍（10分钟），这样即使DB宕机，Leaf仍能持续发号10-20分钟不受影响。
每次请求来临时都会判断下个号段的状态，从而更新此号段，所以偶尔的网络抖动不会影响下个号段的更新。

4.项目使用

我们只用到了号段的方式，并没有使用雪花方式，所以只需要创建数据库表即可

将其镜像运行：

docker run \
-d \
-v /hujx/meituan-leaf/leaf.properties:/app/conf/leaf.properties \
--name meituan-leaf \
-p 28838:8080 \
--restart=always \
registry.cn-hangzhou.aliyuncs.com/itheima/meituan-leaf:1.0.1

leaf.properties

leaf.name=leaf-server
leaf.segment.enable=true
leaf.jdbc.url=jdbc:mysql://192.168.150.101:3306/hjx_leaf?useUnicode=true&characterEncoding=utf8&autoReconnect=true&allowMultiQueries=true&useSSL=false
leaf.jdbc.username=root
leaf.jdbc.password=123

leaf.snowflake.enable=false
#leaf.snowflake.zk.address=
#leaf.snowflake.port=

创建sl_leaf数据库脚本：

CREATE TABLE `leaf_alloc` (
  `biz_tag` varchar(128) CHARACTER SET utf8mb4 COLLATE utf8mb4_0900_ai_ci NOT NULL DEFAULT '',
  `max_id` bigint NOT NULL DEFAULT '1',
  `step` int NOT NULL,
  `description` varchar(256) CHARACTER SET utf8mb4 COLLATE utf8mb4_0900_ai_ci DEFAULT NULL,
  `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
  PRIMARY KEY (`biz_tag`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;

-- 插入运单号生成规划数据
INSERT INTO `leaf_alloc` (`biz_tag`, `max_id`, `step`, `description`, `update_time`) VALUES ('transport_order', 1000000000001, 100, 'Test leaf Segment Mode Get Id', '2023-07-07 11:32:16');

封装服务

import cn.hutool.core.util.StrUtil;
import cn.hutool.http.HttpRequest;
import cn.hutool.http.HttpResponse;
import com.sl.transport.common.enums.IdEnum;
import com.sl.transport.common.exception.SLException;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.stereotype.Service;

/**
 * id服务，用于生成自定义的id
 */
@Service
public class IdService {

    @Value("${sl.id.leaf:}")
    private String leafUrl;

    /**
     * 生成自定义id
     *
     * @param idEnum id配置
     * @return id值
     */
    public String getId(IdEnum idEnum) {
        String idStr = this.doGet(idEnum);
        return idEnum.getPrefix() + idStr;
    }

    private String doGet(IdEnum idEnum) {
        if (StrUtil.isEmpty(this.leafUrl)) {
            throw new SLException("生成id，sl.id.leaf配置不能为空.");
        }
        //访问leaf服务获取id
        String url = StrUtil.format("{}/api/{}/get/{}", this.leafUrl, idEnum.getType(), idEnum.getBiz());
        //设置超时时间为10s
        HttpResponse httpResponse = HttpRequest.get(url)
                .setReadTimeout(10000)
                .execute();
        if (httpResponse.isOk()) {
            return httpResponse.body();
        }
        throw new SLException(StrUtil.format("访问leaf服务出错，leafUrl = {}, idEnum = {}", this.leafUrl, idEnum));
    }

}

public enum IdEnum implements BaseEnum {

    TRANSPORT_ORDER(1, "运单号", "transport_order", "segment", "SL");

    private Integer code;
    private String value;
    private String biz; //业务名称
    private String type; //类型：自增长（segment），雪花id（snowflake）
    private String prefix;//id前缀

    IdEnum(Integer code, String value, String biz, String type, String prefix) {
        this.code = code;
        this.value = value;
        this.biz = biz;
        this.type = type;
        this.prefix = prefix;
    }

    @Override
    public Integer getCode() {
        return this.code;
    }

    @Override
    public String getValue() {
        return this.value;
    }

    public String getBiz() {
        return biz;
    }

    public String getType() {
        return type;
    }

    public String getPrefix() {
        return prefix;
    }

    @Override
    public String toString() {
        final StringBuffer sb = new StringBuffer("IdEnum{");
        sb.append("code=").append(code);
        sb.append(", value='").append(value).append('\'');
        sb.append(", biz='").append(biz).append('\'');
        sb.append(", type='").append(type).append('\'');
        sb.append(", prefix='").append(prefix).append('\'');
        sb.append('}');
        return sb.toString();
    }
}

使用步骤：

在配置文件中进行配置sl.id.leaf为：地址:你的服务端口如：http://192.168.150.101:28838
pend(“, type='”).append(type).append(‘’‘);
sb.append(", prefix=’").append(prefix).append(‘’‘);
sb.append(’}');
return sb.toString();
}
}

使用步骤：

在配置文件中进行配置sl.id.leaf为：地址:你的服务端口如：http://192.168.150.101:28838
在Service中注入IdService，调用getId()方法即可，例如：idService.getId(IdEnum.TRANSPORT_ORDER)

原文地址：https://blog.csdn.net/weixin_61558375/article/details/142414205

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：深度学习之概率论预备知识点（3）
下一篇：分布式变电站电力监控系统

JACM23 - A New Algorithm for Euclidean Shortest Paths in the Plane
本文关注的问题为计算几何学中的经典问题，即「在平面上给定一组两两不相交的多边形障碍物，寻找两点之间避开所有障碍物的欧几里得最短路径」，简单理解就是「含多边形障碍物的两点最短路问题」。
阅读更多2024-09-22
linux如何对c++进行内存分析
linux如何对c++进行内存分析
阅读更多2024-09-22
Mina protocol - 体验教程
零知识证明是一种密码学协议，允许证明者在不泄露任何额外信息的情况下，向验证者证明自己知道某个特定的秘密或信息。：zkCircuits 处理初始状态（State0），接受公共和私有输入，生成交易证明（T
阅读更多2024-09-22
springMvc的初始配置
mapper层（另外创建DataSourceJavaConfig ）3.统一放入IOC容器中。controller层。
阅读更多2024-09-22
17【Protues单片机仿真】基于51单片机的太阳能智能谷物翻晒机器人
基于51单片机，避障，低于50CM报警，LED灯亮起，自动翻晒用光敏电阻，光照强度大，电机转动，相当于翻晒粮食，远程控制用按键代替，按下去电机就转动，相当于翻晒粮食，然后光照强度和超声波的距离都在LC
阅读更多2024-09-22
大数据新视界 --大数据大厂之 Node.js 与大数据交互：实现高效数据处理
本文深入阐释 Node.js 与大数据交互。介绍 Node.js 优势，包括高效事件驱动和非阻塞 I/O 及丰富模块生态。阐述与大数据存储系统连接、与处理框架集成方式，通过实时数据分析平台和可视化应用
阅读更多2024-09-22
【C++】—— string模拟实现
学习了string的使用，总感觉了解不是很深厚；自己模拟实现string类来帮助自己理解。
阅读更多2024-09-22
iPhone16，超先进摄像头系统？丝滑的相机控制
iPhone 16将于9月20号正式开售，这篇文章我们来看下iPhone 16 在影像方面，有哪些升级和新feature。芯片：采用第二代 3纳米芯片，A18。摄像头配置：iPhone 16前置：索尼
阅读更多2024-09-22
lora 微调3B模型微调前有5G 量化f16 后最后导出模型容量变小了只有2G了，为什么？
通过量化、LoRA微调、剪枝和存储格式优化等方法的组合，最终导出的模型容量通常会比原始模型显著减少。从5G减少到2G是这些多重因素共同作用的结果。如果你有特定的工具或框架，可以查看其文档了解详细的模型
阅读更多2024-09-22
互联网技术的持续演进：从现在到未来
互联网技术的发展在过去的十年里已经发生了翻天覆地的变化，未来的进展只会更加令人期待。从5G、人工智能到物联网、区块链，各种新兴技术将会继续推动社会的数字化转型。无论是个人、企业还是政府，都将从这些技术
阅读更多2024-09-22

分布式Id生成策略-美团Leaf

1.需求：

2.方案

3.美团Leaf

号段模式

双buffer优化

4.项目使用

相关文章