分布式:一文掌握分布式ID生成方案

目录

  • 背景
  • 1、UUID
  • 2、数据库自增ID
    • 2.1、主键表
    • 2.2、ID自增步长设置
  • 3、号段模式
  • 4、Redis INCR
  • 5、雪花算法
  • 6、美团(Leaf)
  • 7、百度(Uidgenerator)
  • 8、滴滴(TinyID)
  • 总结比较

背景

在复杂的分布式系统中,往往需要对大量的数据进行唯一标识,比如在对一个订单表进行了分库分表操作,这时候数据库的自增ID显然不能作为某个订单的唯一标识。除此之外还有其他分布式场景对分布式ID的一些要求:

  • 趋势递增: 由于多数RDBMS使用B-tree的数据结构来存储索引数据,在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
  • 单调递增: 保证下一个ID一定大于上一个ID,例如排序需求。
  • 信息安全: 如果ID是连续的,恶意用户的扒取工作就非常容易做了;如果是订单号就更危险了,可以直接知道我们的单量。所以在一些应用场景下,会需要ID无规则、不规则。

就不同的场景及要求,市面诞生了很多分布式ID解决方案。本文针对多个分布式ID解决方案进行介绍,包括其优缺点、使用场景及代码示例。

1、UUID

UUID(Universally Unique Identifier)是基于当前时间、计数器(counter)和硬件标识(通常为无线网卡的MAC地址)等数据计算生成的。包含32个16进制数字,以连字号分为五段,形式为8-4-4-4-12的36个字符,可以生成全球唯一的编码并且性能高效。

JDK提供了UUID生成工具,代码如下:

import java.util.UUID;public class Test {public static void main(String[] args) {System.out.println(UUID.randomUUID());}
}

输出如下

b0378f6a-eeb7-4779-bffe-2a9f3bc76380

UUID完全可以满足分布式唯一标识,但是在实际应用过程中一般不采用,有如下几个原因:

  • 存储成本高: UUID太长,16字节128位,通常以36长度的字符串表示,很多场景不适用。
  • 信息不安全: 基于MAC地址生成的UUID算法会暴露MAC地址,曾经梅丽莎病毒的制造者就是根据UUID寻找的。
  • 不符合MySQL主键要求: MySQL官方有明确的建议主键要尽量越短越好,因为太长对MySQL索引不利:如果作为数据库主键,在InnoDB引擎下,UUID的无序性可能会引起数据位置频繁变动,严重影响性能。

2、数据库自增ID

利用Mysql的特性ID自增,可以达到数据唯一标识,但是分库分表后只能保证一个表中的ID的唯一,而不能保证整体的ID唯一。为了避免这种情况,我们有以下两种方式解决该问题。

2.1、主键表

通过单独创建主键表维护唯一标识,作为ID的输出源可以保证整体ID的唯一。举个例子:

创建一个主键表

CREATE TABLE `unique_id`  (`id` bigint NOT NULL AUTO_INCREMENT,`biz` char(1) NOT NULL,PRIMARY KEY (`id`),UNIQUE KEY `biz` (`biz`)
) ENGINE = InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET =utf8;

业务通过更新操作来获取ID信息,然后添加到某个分表中。

BEGIN;REPLACE INTO unique_id (biz) values ('o') ;
SELECT LAST_INSERT_ID();COMMIT;

在这里插入图片描述

2.2、ID自增步长设置

我们可以设置Mysql主键自增步长,让分布在不同实例的表数据ID做到不重复,保证整体的唯一。

使用如下命令可以查看主键自增的属性

show variables like '%increment%'

在这里插入图片描述

缺点:这种方式在并发量比较高的情况下,如何保证扩展性其实会是一个问题。这种模式下需要一开始就要确认mysql的实例数和自增步长。

3、号段模式

号段模式是当下分布式ID生成器的主流实现方式之一。其原理如下:

  • 号段模式每次从数据库取出一个号段范围,加载到服务内存中。业务获取时ID直接在这个范围递增取值即可。
  • 等这批号段ID用完,再次向数据库申请新号段,对max_id字段做一次update操作,新的号段范围是(max_id ,max_id +step]。
  • 由于多业务端可能同时操作,所以采用版本号version乐观锁方式更新。

在这里插入图片描述

例如 (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 '版本号,是一个乐观锁,每次都更新version,保证并发时数据的正确性',PRIMARY KEY (`id`)
) 

这种分布式ID生成方式不强依赖于数据库,不会频繁的访问数据库,对数据库的压力小很多。但同样也会存在一些缺点比如:服务器重启,单点故障会造成ID不连续。

4、Redis INCR

基于全局唯一ID的特性,我们可以通过Redis的INCR命令来生成全局唯一ID。

在这里插入图片描述

Redis分布式ID的简单案例

/***  Redis 分布式ID生成器*/
@Component
public class RedisDistributedId {@Autowiredprivate StringRedisTemplate redisTemplate;private static final long BEGIN_TIMESTAMP = 1659312000l;/*** 生成分布式ID* 符号位    时间戳[31位]  自增序号【32位】* @param item* @return*/public long nextId(String item){// 1.生成时间戳LocalDateTime now = LocalDateTime.now();// 格林威治时间差long nowSecond = now.toEpochSecond(ZoneOffset.UTC);// 我们需要获取的 时间戳 信息long timestamp = nowSecond - BEGIN_TIMESTAMP;// 2.生成序号 --》 从Redis中获取// 当前当前的日期String date = now.format(DateTimeFormatter.ofPattern("yyyy:MM:dd"));// 获取对应的自增的序号Long increment = redisTemplate.opsForValue().increment("id:" + item + ":" + date);return timestamp << 32 | increment;}}

同样使用Redis也有对应的缺点:ID 生成的持久化问题,如果Redis宕机了怎么进行恢复?

5、雪花算法

Snowflake,雪花算法是有Twitter开源的分布式ID生成算法,以划分命名空间的方式将64bit位分割成了多个部分,每个部分都有具体的不同含义,在Java中64Bit位的整数是Long类型,所以在Java中Snowflake算法生成的ID就是long来存储的。具体如下:

在这里插入图片描述

  • 第一部分: 占用1bit,第一位为符号位,不适用
  • 第二部分: 41位的时间戳,41bit位可以表示241个数,每个数代表的是毫秒,那么雪花算法的时间年限是(241)/(1000×60×60×24×365)=69
  • 第三部分: 10bit表示是机器数,即 2^ 10 = 1024台机器,通常不会部署这么多机器
  • 第四部分: 12bit位是自增序列,可以表示2^12=4096个数,一秒内可以生成4096个ID,理论上snowflake方案的QPS约为409.6w/s

雪花算法案例代码:

public class SnowflakeIdWorker {// ==============================Fields===========================================/*** 开始时间截 (2020-11-03,一旦确定不可更改,否则时间被回调,或者改变,可能会造成id重复或冲突)*/private final long twepoch = 1604374294980L;/*** 机器id所占的位数*/private final long workerIdBits = 5L;/*** 数据标识id所占的位数*/private final long datacenterIdBits = 5L;/*** 支持的最大机器id,结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数)*/private final long maxWorkerId = -1L ^ (-1L << workerIdBits);/*** 支持的最大数据标识id,结果是31*/private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);/*** 序列在id中占的位数*/private final long sequenceBits = 12L;/*** 机器ID向左移12位*/private final long workerIdShift = sequenceBits;/*** 数据标识id向左移17位(12+5)*/private final long datacenterIdShift = sequenceBits + workerIdBits;/*** 时间截向左移22位(5+5+12)*/private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;/*** 生成序列的掩码,这里为4095 (0b111111111111=0xfff=4095)*/private final long sequenceMask = -1L ^ (-1L << sequenceBits);/*** 工作机器ID(0~31)*/private long workerId;/*** 数据中心ID(0~31)*/private long datacenterId;/*** 毫秒内序列(0~4095)*/private long sequence = 0L;/*** 上次生成ID的时间截*/private long lastTimestamp = -1L;//==============================Constructors=====================================/*** 构造函数**/public SnowflakeIdWorker() {this.workerId = 0L;this.datacenterId = 0L;}/*** 构造函数** @param workerId     工作ID (0~31)* @param datacenterId 数据中心ID (0~31)*/public SnowflakeIdWorker(long workerId, long datacenterId) {if (workerId > maxWorkerId || workerId < 0) {throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));}if (datacenterId > maxDatacenterId || datacenterId < 0) {throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));}this.workerId = workerId;this.datacenterId = datacenterId;}// ==============================Methods==========================================/*** 获得下一个ID (该方法是线程安全的)** @return SnowflakeId*/public synchronized long nextId() {long timestamp = timeGen();//如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过这个时候应当抛出异常if (timestamp < lastTimestamp) {throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));}//如果是同一时间生成的,则进行毫秒内序列if (lastTimestamp == timestamp) {sequence = (sequence + 1) & sequenceMask;//毫秒内序列溢出if (sequence == 0) {//阻塞到下一个毫秒,获得新的时间戳timestamp = tilNextMillis(lastTimestamp);}}//时间戳改变,毫秒内序列重置else {sequence = 0L;}//上次生成ID的时间截lastTimestamp = timestamp;//移位并通过或运算拼到一起组成64位的IDreturn ((timestamp - twepoch) << timestampLeftShift) //| (datacenterId << datacenterIdShift) //| (workerId << workerIdShift) //| sequence;}/*** 阻塞到下一个毫秒,直到获得新的时间戳** @param lastTimestamp 上次生成ID的时间截* @return 当前时间戳*/protected long tilNextMillis(long lastTimestamp) {long timestamp = timeGen();while (timestamp <= lastTimestamp) {timestamp = timeGen();}return timestamp;}/*** 返回以毫秒为单位的当前时间** @return 当前时间(毫秒)*/protected long timeGen() {return System.currentTimeMillis();}/*** 随机id生成,使用雪花算法** @return*/public static String getSnowId() {SnowflakeIdWorker sf = new SnowflakeIdWorker();String id = String.valueOf(sf.nextId());return id;}//=========================================Test=========================================/*** 测试*/public static void main(String[] args) {SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);for (int i = 0; i < 1000; i++) {long id = idWorker.nextId();System.out.println(id);}}
}

雪花算法强依赖机器时钟,如果机器上时钟回拨,会导致发号重复。 通常通过记录最后使用时间处理该问题。

在这里插入图片描述

6、美团(Leaf)

由美团开发,开源项目链接:

  • https://github.com/Meituan-Dianping/Leaf

Leaf同时支持号段模式和snowflake算法模式,可以切换使用。

snowflake模式依赖于ZooKeeper,不同于原始snowflake算法也主要是在workId的生成上,Leaf中workId是基于ZooKeeper的顺序Id来生成的,每个应用在使用Leaf-snowflake时,启动时都会都在Zookeeper中生成一个顺序Id,相当于一台机器对应一个顺序节点,也就是一个workId。

号段模式是对直接用数据库自增ID充当分布式ID的一种优化,减少对数据库的频率操作。相当于从数据库批量的获取自增ID,每次从数据库取出一个号段范围,例如 (1,1000] 代表1000个ID,业务服务将号段在本地生成1~1000的自增ID并加载到内存。

7、百度(Uidgenerator)

源码地址:

  • https://github.com/baidu/uid-generator

中文文档地址:

  • https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

UidGenerator是百度开源的Java语言实现,基于Snowflake算法的唯一ID生成器。它是分布式的,并克服了雪花算法的并发限制。单个实例的QPS能超过6000000。需要的环境:JDK8+,MySQL(用于分配WorkerId)。

百度的Uidgenerator对结构做了部分的调整,具体如下:

在这里插入图片描述

时间部分只有28位,这就意味着UidGenerator默认只能承受8.5年(2^28-1/86400/365),不过UidGenerator可以适当调整delta seconds、worker node id和sequence占用位数。

8、滴滴(TinyID)

由滴滴开发,开源项目链接:

  • https://github.com/didi/tinyid

Tinyid是在美团(Leaf)的leaf-segment算法基础上升级而来,不仅支持了数据库多主节点模式,还提供了tinyid-client客户端的接入方式,使用起来更加方便。但和美团(Leaf)不同的是,Tinyid只支持号段一种模式不支持雪花模式。Tinyid提供了两种调用方式,一种基于Tinyid-server提供的http方式,另一种Tinyid-client客户端方式。

总结比较

在这里插入图片描述

**参考:**https://mp.weixin.qq.com/s/VCuhmFV3KtczJxaeEYlbJw

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/174676.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python-函数

目录 一、函数的定义与调用 二、日期时间函数 1、时间戳 2、日历函数 三、随机数函数 1、random.random() 2、random.uniform(a,b) 3、random.randomint(a,b) 4、random.randrange(start,stop,step) 5、random.choice(sequence) 6、random.shuffle([random]) 7、ran…

2023年阿里云双11优惠来了,单笔最高可省2400元!

2023年阿里云双11活动终于来了&#xff0c;阿里云推出了金秋云创季活动&#xff0c;新用户、老用户、企业用户均可领取金秋上云礼包&#xff0c;单笔最高立减2400元&#xff01; 一、活动时间 满减券领取时间&#xff1a;2023年10月27日0点0分0秒-2023年11月30日23点59分59秒 …

BSTree二叉树讲解

二叉搜索树的概念&#xff1a; 二叉搜索树又称二叉排序树&#xff0c;它或者是一棵空树&#xff0c;或者是具有以下性质的二叉树: 若它的左子树不为空&#xff0c;则左子树上所有节点的值都小于根节点的值 若它的右子树不为空&#xff0c;则右子树上所有节点的值…

YOLOv5— Fruit Detection

&#x1f368; 本文为[&#x1f517;365天深度学习训练营学习记录博客 &#x1f366; 参考文章&#xff1a;365天深度学习训练营-第7周&#xff1a;咖啡豆识别&#xff08;训练营内部成员可读&#xff09; &#x1f356; 原作者&#xff1a;[K同学啊 | 接辅导、项目定制](https…

CentOS 安装 tomcat 并设置 开机自启动

CentOS 安装 tomcat 并设置 开机自启动 下载jdk和tomcat curl https://download.oracle.com/java/21/latest/jdk-21_linux-x64_bin.tar.gz curl https://dlcdn.apache.org/tomcat/tomcat-10/v10.1.15/bin/apache-tomcat-10.1.15.tar.gz解压jdk和tomcat并修改目录名称 tar -z…

homeassistant安装HACS应用商店

环境&#xff1a;iStoreOS&#xff0c;已在商店中安装homeassistant。 homeassistant在iStoreOS中是以docker容器运行的。 1、进入终端&#xff0c;输入账号和密码&#xff08;默认&#xff1a;root&#xff0c;password&#xff09; 查看容器&#xff1a;docker ps 进入容…

3.3每日一题(变量可分离方程)

1、判断类型选方法&#xff1a;等式中分别提一个x、y出来&#xff0c;形成了x与y相乘的等式&#xff1b;为变量可分离类型 2、不一定非得把y解出来&#xff0c;化成上述的等式即可&#xff08;为隐函数的方程解&#xff09; 注&#xff1a;等式不定积分后记得&#xff0b;一个…

大数据-Storm流式框架(七)---Storm事务

storm 事务 需求 storm 对于保证消息处理&#xff0c;提供了最少一次的处理保证。最常见的问题是如果元组可以被 重发&#xff0c;可以用于计数吗&#xff1f;不会重复计数吗&#xff1f; strom0.7.0 引入了事务性拓扑的概念&#xff0c;可以保证消息仅被严格的处理一次。因此可…

【电路笔记】-交流电感和感抗

交流电感和感抗 文章目录 交流电感和感抗1、概述1.1 电感1.2 电感器 2、频率特性2.1 电抗(Reactance)2.2 相移2.3 感应现象 3、RL滤波器4、总结 在之前有 交流电阻的文章中&#xff0c;我们已经看到电阻器在正常频率下的直流或交流状态下的行为是相同的。 然而&#xff0c;其他…

【机器学习合集】人脸表情分类任务Pytorch实现TensorBoardX的使用 ->(个人学习记录笔记)

人脸表情分类任务 注意&#xff1a;整个项目来自阿里云天池&#xff0c;下面是开发人员的联系方式&#xff0c;本人仅作为学习记录&#xff01;&#xff01;&#xff01;该文章原因&#xff0c;学习该项目&#xff0c;完善注释内容&#xff0c;针对新版本的Pytorch进行部分代码…

山东大学开发可解释深度学习算法 RetroExplainer,4 步识别有机物的逆合成路线

逆合成旨在找到一系列合适的反应物&#xff0c;以高效合成目标产物。这是解决有机合成路线的重要方法&#xff0c;也是有机合成路线设计的最简单、最基本的方法。 早期的逆合成研究多依赖编程&#xff0c;随后这一工作被 AI 接替。然而&#xff0c;现有的逆合成方法多关注单步逆…

机器学习第一周

一、概述 机器学习大致会被划分为两类&#xff1a;监督学习&#xff0c;无监督学习 1.1 监督学习 监督学习其实就是&#xff0c;给计算机一些输入x和正确的输出y&#xff08;训练数据集&#xff09;&#xff0c;让他总结x->y的映射关系&#xff0c;从而给他其他的输入x&a…

【算法】动态规划之LeetCode 53.最大子数组和

目录 文章目录 **目录**&#x1f4d1;前言1.题目描述2. 动态规划法 &#x1f4d1;文章末尾 &#x1f4d1;前言 本文主要是leetcode题解析&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是青衿&#x1f947; ☁…

ThreadLocal 会出现内存泄漏吗?

ThreadLocal ThreadLocal 是一个用来解决线程安全性问题的工具。它相当于让每个线程都开辟一块内存空间&#xff0c;用来存储共享变量的副本。然后每个线程只需要访问和操作自己的共享变量副本即可&#xff0c;从而避免多线程竞争同一个共享资源。它的工作原理很简单&#xff0…

基于Ubuntu20.04安装ROS系统

文章目录 一、ROS简介二、ROS安装三、ROS安装测试四、安装问题解决1. sudo rosdepc init&#xff1a;找不到命令2. ERROR: cannot download default sources list from...3. Command roscore not found...4. Resource not found: roslaunch... 一、ROS简介 ROS是用于编写机器人…

[ubuntu系统下的文本编辑器nano,vim,gedit,文件使用,以及版本更新问题]

文本编辑器概要 在Ubuntu系统下&#xff0c;有许多文本编辑器可供选择&#xff0c;每个编辑器都有其独特的特性和用途。以下是一些常见的文本编辑器&#xff1a; Gedit&#xff1a; 这是Ubuntu默认的文本编辑器&#xff0c;它简单易用&#xff0c;适合基本的文本编辑任务。 安…

取石子

每一堆数量都>1的话可以把合并操作和取石子看成一种操作&#xff0c;总操作数就是sumn-1&#xff0c;为奇数就是Alice先手必胜&#xff0c;哪怕有一堆是2&#xff0c;Bob取后变为1&#xff0c;Alice也可以通过合并操作让1变成>1的数 可以分成两大板块a、b, a中方石子个数…

haproxy高可用集群

高可用集群 Haproxy &#xff1a;他是常用的负载均衡软件 Nginx 支持四层转发&#xff0c;和七层转发 Haproxy 也可以四层和七层转发 LVS的DR发和nat是基于四层还是七层的转&#xff1f; 都基于是四层转发&#xff08…

[SHCTF 2023 校外赛道] pwn

有19道题这么多,不过基本是入门题,都是在骗新生,看这么容易快来PWN吧! week1 四则计算器 这里用危险函数gets读入有个溢出.而且PIE也没开,地址是固定的.而且有后门.直接溢出到ret写上后门即可. from pwn import *p remote(112.6.51.212, 31473) context(archamd64, log_lev…