分布式全局ID生成器原理剖析及非常齐全开源方案应用示例

妖气游戏网

分布式全局ID生成器原理剖析及非常齐全开源方案应用示例

首页冒险解谜Didi demo更新时间：2024-08-01
为何需要分布式ID生成器

**拿我们系统常用Mysql数据库来说，在之前的单体架构基本是单库结构，每个业务表的ID一般从1增，通过 **AUTO_INCREMENT=1设置自增起始值，随着系统（比如互联网电商、外卖）用户数据日渐增长，单库性能无法满足业务系统，在这之后我们会使用基于主从同步的读写分离，但当用户量规模连主从模式都无法应对时，我们会采用分库分表（当然现在还有其他解决方案比如分布式关系型数据库如TiDB）的方案，这样对数据分库分表后需要有一个唯一 ID 来标识一条数据或消息，数据库的自增 ID 显然不能满足需求，在复杂分布式系统中，往往还有很多场景需要对大量的数据和消息进行唯一标识，这就迫使我们需要用到分布式系统中全局ID生成器。

我们本篇文章只是介绍一些常用实现方案，而大部分的开源分布式ID生成器基本都是基于号段模式和雪花算法为基础，可以根据不同业务场景需要选择，不做详细说明

分布式ID满足要求常用解决方案UUID

全局ID在Java中们可以简单使用来UUID生成，输出的41c9b76fc5ac4265939cd5b27bdacdf1这种结果的字符串数据，可以看生成的是36位长度的16进制的字符串，然后将中划线-替换为空字符串**

public static void main(String[] args) { String uuid = UUID.randomUUID().toString().replaceAll("-",""); System.out.println(uuid); }

优点

缺点

数据库自增ID

这样方式就是单独使用一个数据库来生成ID，业务程序通过这个数据库获取ID，表结构可以简单设计如下，--然后再通过事务通过插入等操作数据触发ID自增，这个数据库层级性能比较高，你也可以采用表级别插入返回数据的主键

CREATE DATABASE `SEQ_ID`; CREATE TABLE SEQID.SEQUENCE_ID ( id bigint(20) unsigned NOT NULL auto_increment, id_value char(10) NOT NULL default '', PRIMARY KEY (id), UNIQUE KEY id_value(id_value) ) ENGINE=MyISAM;

begin replace into SEQUENCE_ID(id_value) values('xxx'); SELECT LAST_INSERT_ID(); commit; end

优点

缺点

数据库集群模式

上面单个数据库有弊端，那么可以采用数据库集群，数据库集群常用主从和主主，我们使用主主模式，每个数据库通过设置不同起始值和相同自增步长来实现，比如三台mysql主主模式，mysql1从1开始自增步长为3，序号1、4、7...，mysql2从2开始自增步长为3，序号2、5、8...，mysql3从3开始自增步长为3，序号3、6、9....,每个业务系统可以通过这三台中获取到ID

set @@auto_increment_offset = 1; -- mysql1起始值 set @@auto_increment_increment = 3; -- mysql1自增步长 set @@auto_increment_offset = 2; -- mysql2起始值 set @@auto_increment_increment = 3; -- mysql2自增步长 ​ set @@auto_increment_offset = 3; -- mysql3起始值 set @@auto_increment_increment = 3; -- mysql3自增步长

优点

缺点

号段模式

号段模式几乎是目前所有开源分布式ID生成器的主流实现方式之一，号段模式比如每次从数据库取出一个号段范围，例如 (1,1000] 代表1000个ID，具体的业务服务将本号段，生成1~1000的自增ID并加载到内存，不强依赖于数据库，不会频繁的访问数据库，对数据库的压力小很多。简易版本的表结构如下：

CREATE TABLE id_generator ( id int(10) NOT NULL, max_id bigint(20) NOT NULL COMMENT '当前最大id', step int(20) NOT NULL COMMENT '号段的步长', biz_type int(20) NOT NULL COMMENT '业务类型', version int(20) NOT NULL COMMENT '版本号', PRIMARY KEY (`id`) )

biz_type ：代表不同业务类型

max_id ：当前最大的可用id

step ：代表号段的长度

version ：是一个乐观锁，每次都更新version，保证并发时数据的正确性

每次申请一个号段，通过乐观锁的机制对 max_id字段做一次 update操作，update成功则说明新号段获取成功，新的号段范围是 (max_id ,max_id step]

update id_generator set max_id = #{max_id step}, version = version 1 where version = # {version} and biz_type = XXX Redis实现

Redis也同样可以实现，原理就是利用 redis**的 **incr命令实现ID的原子性自增，redis持久化也支持基于每条命令持久化方式，且redis自身有高可用集群模式

192.168.3.117:6379> set seq_id 1 // 初始化自增ID为1 OK 192.168.3.117:6379> incr seq_id // 增加1，并返回递增后的数值 (integer) 2 雪花算法（SnowFlake）

雪花算法（Snowflake）是twitter公司内部分布式项目采用的ID生成算法，开源后广受国内大厂的好评，在该算法影响下各大公司相继开发出各具特色的分布式生成器。SnowFlake算法用来生成64位的ID，刚好可以用long整型存储，能够用于分布式系统中生产唯一的ID， 并且生成的ID有序

Snowflake生成的是Long类型的ID，一个Long类型占8个字节，每个字节占8比特，也就是说一个Long类型占64个比特。

Snowflake ID组成结构：正数位（占1比特） 时间戳（占41比特） 机器ID（占5比特） 数据中心（占5比特） 自增值（占12比特），总共64比特组成的一个Long类型。

雪花算法比较依赖于时间，会出现时钟回拨的问题，所以尽量保证时间同步，大部分开源分布式ID生成器大都有优化解决时钟回拨的问题

雪花算法Java实现源码Gitub地址

下面是基于Twitter的雪花算法SnowFlake，使用Java语言实现，封装成工具方法，各个业务应用可以直接使用该工具方法来获取分布式ID，只需保证每个业务应用有自己的工作机器id即可，而不需要单独去搭建一个获取分布式ID的应用

0 - 41位时间戳 - 5位数据中心标识 - 5位机器标识 - 12位序列号

5位数据中心标识跟5位机器标识这样的分配仅仅是当前实现中分配的，如果业务有其实的需要，可以按其它的分配比例分配，如10位机器标识，不需要数据中心标识。

/** * twitter的snowflake算法 -- java实现 * * @author beyond * @date 2016/11/26 */ public class SnowFlake { ​ /** * 起始的时间戳 */ private final static long START_STMP = 1480166465631L; ​ /** * 每一部分占用的位数 */ private final static long SEQUENCE_BIT = 12; //序列号占用的位数 private final static long MACHINE_BIT = 5; //机器标识占用的位数 private final static long DATACENTER_BIT = 5;//数据中心占用的位数 ​ /** * 每一部分的最大值 */ private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT); private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT); private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT); ​ /** * 每一部分向左的位移 */ private final static long MACHINE_LEFT = SEQUENCE_BIT; private final static long DATACENTER_LEFT = SEQUENCE_BIT MACHINE_BIT; private final static long TIMESTMP_LEFT = DATACENTER_LEFT DATACENTER_BIT; ​ private long datacenterId; //数据中心 private long machineId; //机器标识 private long sequence = 0L; //序列号 private long lastStmp = -1L;//上一次时间戳 ​ public SnowFlake(long datacenterId, long machineId) { if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) { throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0"); } if (machineId > MAX_MACHINE_NUM || machineId < 0) { throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0"); } this.datacenterId = datacenterId; this.machineId = machineId; } ​ /** * 产生下一个ID * * @return */ public synchronized long nextId() { long currStmp = getNewstmp(); if (currStmp < lastStmp) { throw new RuntimeException("Clock moved backwards. Refusing to generate id"); } ​ if (currStmp == lastStmp) { //相同毫秒内，序列号自增 sequence = (sequence 1) & MAX_SEQUENCE; //同一毫秒的序列数已经达到最大 if (sequence == 0L) { currStmp = getNextMill(); } } else { //不同毫秒内，序列号置为0 sequence = 0L; } ​ lastStmp = currStmp; ​ return (currStmp - START_STMP) << TIMESTMP_LEFT //时间戳部分 | datacenterId << DATACENTER_LEFT //数据中心部分 | machineId << MACHINE_LEFT //机器标识部分 | sequence; //序列号部分 } ​ private long getNextMill() { long mill = getNewstmp(); while (mill <= lastStmp) { mill = getNewstmp(); } return mill; } ​ private long getNewstmp() { return System.currentTimeMillis(); } ​ public static void main(String[] args) { SnowFlake snowFlake = new SnowFlake(2, 3); ​ for (int i = 0; i < (1 << 12); i ) { System.out.println(snowFlake.nextId()); } ​ } } 百度 （Uidgenerator）概述

官方GitHub地址** **https://github.com/baidu/uid-generator

UidGenerator是Java实现的, 基于Snowflake算法的唯一ID生成器。UidGenerator以组件形式工作在应用项目中, 支持自定义workerId位数和初始化策略, 从而适用于docker等虚拟化环境下实例自动重启、漂移等场景。 在实现上, UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐，避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。

依赖版本：Java8及以上版本, MySQL(内置WorkerID分配器, 启动阶段通过DB进行分配; 如自定义实现, 则DB非必选依赖）

[](https://github.com/baidu/uid-generator/blob/master/doc/snowflake.png)

Snowflake算法描述：指定机器 & 同一时刻 & 某一并发序列，是唯一的。据此可生成一个64 bits的唯一ID（long）。默认采用上图字节分配方式：

UidGenerator是基于 Snowflake算法实现的，与原始的 snowflake算法不同在于，UidGenerator支持自 定义时间戳、工作机器ID和 序列号 等各部分的位数，而且 UidGenerator中采用用户自定义 workId的生成策略。

UidGenerator需要与数据库配合使用，需要新增一个 WORKER_NODE表。当应用启动时会向数据库表中去插入一条数据，插入成功后返回的自增ID就是该机器的 workId数据由host，port组成。

提供了两种生成器: DefaultUidGenerator、CachedUidGenerator，如对UID生成性能有要求则使用CachedUidGenerator。

CachedUidGenerator

RingBuffer环形数组，数组每个元素成为一个slot。RingBuffer容量，默认为Snowflake算法中sequence最大值，且为2^N。可通过 boostPower配置进行扩容，以提高RingBuffer 读写吞吐量。

Tail指针、Cursor指针用于环形数组上读写slot：

CachedUidGenerator采用了双RingBuffer，Uid-RingBuffer用于存储Uid、Flag-RingBuffer用于存储Uid状态(是否可填充、是否可消费)

由于数组元素在内存中是连续分配的，可最大程度利用CPU cache以提升性能。但同时会带来「伪共享」FalseSharing问题，为此在Tail、Cursor指针、Flag-RingBuffer中采用了CacheLine 补齐方式。

RingBuffer填充时机

简单使用

官方源码导入idea

建立数据库和导入表WORKER_NODE.sql

创建一个SpringBoot启动类，在application-dev.yml文件配置数据库信息，启动类配置Mybatis扫描com.baidu.fsg.uid的mapper文件注解，创建一个UidControoler提供一个获取单个uid的接口，启动SpringBoot程序

访问提供接口地址：http://localhost:8080/uid/snowflake** ，返回uid结果，每次刷新 1**

数据库表WORKER_NODE当我们每次启动程序会重新生成新的记录

美团（Leaf）概述

官方GitHub地址** **https://github.com/Meituan-Dianping/Leaf

There are no two identical leaves in the world. 世界上没有两片完全相同的树叶。

— 莱布尼茨

Leaf 最早期需求是各个业务线的订单ID生成需求。在美团早期，有的业务直接通过DB自增的方式生成ID，有的业务通过redis缓存来生成ID，也有的业务直接用UUID这种方式来生成ID。以上的方式各自有各自的问题，因此我们决定实现一套分布式ID生成服务来满足需求。

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

当然，为了追求更高的性能，需要通过RPC Server来部署Leaf 服务，那仅需要引入leaf-core的包，把生成ID的API封装到指定的RPC框架中即可。

Leaf Server 是一个spring boot的程序，提供HTTP服务来获取ID。

Leaf 提供两种生成的ID的方式（号段模式和snowflake模式），你可以同时开启两种方式，也可以指定开启某种方式（默认两种方式为关闭状态）

配置

Leaf Server的配置都在leaf-server/src/main/resources/leaf.properties中

配置项

含义

默认值

leaf.name

leaf 服务名

leaf.segment.enable

是否开启号段模式

false

leaf.jdbc.url

mysql 库地址

leaf.jdbc.username

mysql 用户名

leaf.jdbc.password

mysql 密码

leaf.snowflake.enable

是否开启snowflake模式

false

leaf.snowflake.zk.address

snowflake模式下的zk地址

leaf.snowflake.port

snowflake模式下的服务注册端口

简单使用

INSERT INTO leaf_alloc(biz_tag, max_id, step, DESCRIPTION) VALUES('itxs', 1, 2000, 'Test leaf Segment Mode Get Id')

配置application.properties中的数据库信息，将leaf.segment.enable设置为true或者注释；配置zookeeper信息，leaf.snowflake.enable设置为true或者注释；启动leaf-server Spring Boot启动类

访问号段模式http接口地址：http://localhost:8080/api/segment/get/itxs

访问雪花算法的http接口地址:http://localhost:8080/api/snowflake/get/test

访问监控页面地址：http://localhost:8080/cache

我们再使用上一小节的工程项目先简单通过将leaf的core模块源码工程引入，使用号段模式，通过@Autowired SegmentIDGenImpl主动注入leaf号段模式实现类，并完成http getSegment测试接口的controller

package com.itxs.uiddemo.controller; import javax.annotation.Resource; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.web.bind.annotation.GetMapping; import org.springframework.web.bind.annotation.PathVariable; import org.springframework.web.bind.annotation.RequestMapping; import org.springframework.web.bind.annotation.RestController; import com.baidu.fsg.uid.UidGenerator; import com.sankuai.inf.leaf.Result; import com.sankuai.inf.leaf.segment.SegmentIDGenImpl; @RestController @RequestMapping(value="/uid") public class UidController { @Resource(name = "cachedUidGenerator") private UidGenerator cachedUidGenerator; @Autowired private SegmentIDGenImpl idGen; @GetMapping("/snowflake") public String snowflake() { return String.valueOf(this.cachedUidGenerator.getUID()); } @GetMapping(value = "/segment/{key}") public Result<Long> getSegment(@PathVariable("key") String key) throws Exception { return this.idGen.get(key); } }

启动Spring Boot程序，访问http://localhost:8080/uid/segment/itxs，返回data字段就是uid值，每次刷新 1

重新启动后，再次访问http://localhost:8080/uid/segment/itxs，返回data字段1001，也即是新的号段的起始值，数据库的maxid也变为1001

当然也可以采用Spring Boot Startser方式使用，官网也有相关的说明

我们自己下载leaf-starter 整合Spring Boot 制作启动器starter源码进行编译

编译好leaf-boot-starter后我们新建一个Spring Boot demo工程，由于原来封装是基于Spring Boot早期的版本，高版本不兼容，所以用早期版本,由于leaf-boot-starter里面使用zookeeper的客户端curator，我们直接运行是出现curator的某些类找不到，因此我们简单就直接在工程加入curator-framework和curator-recipes的依赖。

pom文件

<?xml version="1.0" encoding="UTF-8"?> <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"> <modelVersion>4.0.0</modelVersion> <groupId>com.itxs</groupId> <artifactId>leaf-spring-boot-demo</artifactId> <version>1.0-SNAPSHOT</version> <parent> <artifactId>spring-boot-starter-parent</artifactId> <groupId>org.springframework.boot</groupId> <version>2.0.3.RELEASE</version> </parent> <properties> <maven.compiler.source>8</maven.compiler.source> <maven.compiler.target>8</maven.compiler.target> </properties> <dependencies> <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-web</artifactId> </dependency> <dependency> <groupId>com.sankuai.inf.leaf</groupId> <artifactId>leaf-boot-starter</artifactId> <version>1.0.1-RELEASE</version> </dependency> <dependency> <groupId>org.apache.curator</groupId> <artifactId>curator-framework</artifactId> <version>5.2.0</version> </dependency> <dependency> <groupId>org.apache.curator</groupId> <artifactId>curator-recipes</artifactId> <version>5.2.0</version> </dependency> </dependencies> </project>

在class path也即是resource根目录下新建leaf.properties文件，同时开启号段模式和雪花算法，配置信息如下

leaf.name=com.sankuai.leaf.opensource.test leaf.segment.enable=true leaf.segment.url=jdbc:mysql://192.168.3.117:3306/leaf?autoReconnect=true&useUnicode=true&characterEncoding=UTF-8 leaf.segment.username=leaf leaf.segment.password=leaf123 leaf.snowflake.enable=true leaf.snowflake.address=192.168.3.117 leaf.snowflake.port=2181

新建一个controller用于测试，提供号段和雪花算法测试接口

package com.itxs.controller; import com.sankuai.inf.leaf.common.Result; import com.sankuai.inf.leaf.service.SegmentService; import com.sankuai.inf.leaf.service.SnowflakeService; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.web.bind.annotation.GetMapping; import org.springframework.web.bind.annotation.PathVariable; import org.springframework.web.bind.annotation.RequestMapping; import org.springframework.web.bind.annotation.RestController; @RestController @RequestMapping(value="/uid") public class LeafUidController { @Autowired private SegmentService segmentService; @Autowired private SnowflakeService snowflakeService; @GetMapping("/snowflake") public String snowflake() { return String.valueOf(this.snowflakeService.getId("test")); } @GetMapping(value = "/segment/{key}") public Result getSegment(@PathVariable("key") String key) throws Exception { return this.segmentService.getId(key); } }

新建Spring Boot启动类，在启动类上标注@EnableLeafServer开启LeafServer的注解,启动Spring Boot程序，默认是使用8080端口

package com.itxs; import com.sankuai.inf.leaf.plugin.annotation.EnableLeafServer; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; @SpringBootApplication @EnableLeafServer public class LeafApplication { public static void main(String[] args) { SpringApplication.run(LeafApplication.class,args); } }

访问号段uid获取接口:http://localhost:8080/uid/segment/itxs，放回id结果如下

访问雪花算法uid获取接口:http://localhost:8080/uid/snowflake,返回id结果如下

滴滴（TinyID）概述

官方GitHub地址** **https://github.com/didi/tinyid/

Tinyid是用Java开发的一款分布式id生成系统，基于数据库号段算法实现，关于这个算法可以参考美团leaf或者tinyid原理介绍。Tinyid扩展了leaf-segment算法，支持了多db(master)，同时提供了java-client(sdk)使id生成本地化，获得了更好的性能与可用性。Tinyid在滴滴客服部门使用，均通过tinyid-client方式接入，每天生成亿级别的id。

适用场景:只关心id是数字，趋势递增的系统，可以容忍id不连续，有浪费的场景**
**不适用场景:类似订单id的业务(因为生成的id大部分是连续的，容易被扫库、或者测算出订单量)

推荐使用方式原理和架构

简单使用

cd tinyid/tinyid-server/ && create table with db.sql (mysql)

cd tinyid-server/src/main/resources/offline vi application.properties

datasource.tinyid.names=primary datasource.tinyid.primary.driver-class-name=com.mysql.jdbc.Driver datasource.tinyid.primary.url=jdbc:mysql://ip:port/databaseName?autoReconnect=true&useUnicode=true&characterEncoding=UTF-8 datasource.tinyid.primary.username=root datasource.tinyid.primary.password=123456

cd tinyid-server/ sh build.sh offline java -jar output/tinyid-server-xxx.jar

或者将tinyid源码导入idea中，同样配置db,然后启动tinyid-server

通过初始化sql脚本中的授权码和biz_type，访问本地的RestApi接口测试，结果如下

接下来我们使用基于java客户端的方式，这也是官方推荐的，性能最好，我们这里就直接使用客户端源码工程的测试代码

<dependency> <groupId>com.xiaoju.uemc.tinyid</groupId> <artifactId>tinyid-client</artifactId> <version>${tinyid.version}</version> </dependency>

tinyid.server=localhost:9999 tinyid.token=0f673adf80504e2eaa552f5d791b644c #(tinyid.server=localhost:9999/gateway,ip2:port2/prefix,...)

Long id = TinyId.nextId("test"); List<Long> ids = TinyId.nextId("test", 10);

我们再看数据库表的信息，发现max_id已经变为200001,也即是每个客户端通过步长申请号段放在内存中，然后更新数据库表为下一次申请id段的起始值

看到这里，以后如果遇到需要使用分布式ID的场景，你会选择和使用了吗？

查看全文
大家还看了
也许喜欢
更多游戏

Copyright © 2024 妖气游戏网 www.17u1u.com All Rights Reserved