网站备案,兰州网站建设设计,做网站找哪家公司,建立企业网站的流程文章目录 本系列前言UUIDDB自增主键Redis incr命令号段模式雪花算法 本系列
漫谈分布式唯一ID#xff08;本文#xff09;分布式唯一ID生成#xff08;二#xff09;#xff1a;leaf分布式唯一ID生成#xff08;三#xff09;#xff1a;uid-generator#xff08;待完… 文章目录 本系列前言UUIDDB自增主键Redis incr命令号段模式雪花算法 本系列
漫谈分布式唯一ID本文分布式唯一ID生成二leaf分布式唯一ID生成三uid-generator待完成分布式唯一ID生成四tinyid待完成
前言
在大多数业务场景中需要对每条数据分配一个唯一ID作为标识。大部分关系型数据库提供了自增主键功能来支持该需求
但若数据量较大需要分库分表时就不能使用每个数据库实例提供的自增键功能因为不能保证在所有表中唯一分布式全局唯一ID的需求应运而生
分布式唯一ID有以下功能需求
全局唯一性在某个业务场景下唯一避免数据冲突这是最基本的要求高性能生成速度快不能阻塞业务流程趋势递增通常会将该ID作为数据库主键由于mysql innoDB采用聚集索引若新增的记录主键无序可能造成 叶分裂 和 空间利用率不高 的问题降低写入性能严格单调递增适用于需要这种特性的场景例如IM场景中需要根据此生成消息ID用于给消息排序并判断是否有消息丢失安全性防止泄露业务信息若生成的ID严格递增在电商场景可根据一段时间的id差算出订单量方便追踪例如在ID融入时间戳就能知道是什么时间范围生成的
上述45需求是互斥的无法同时满足。不同业务场景根据需求选择
还有一些非功能需求 高可用可用性至少5个9 低延迟生成速度一定要快TP50和TP99.9都要非常快不能因为这个导致业务接口响应变慢 高并发假如一下来10w个生成分布式 ID 的请求要能扛得住
接下来介绍一些常见的分布式ID生成方案 UUID
UUIDUniversally unique identifier一般包含32个十六进制的字符128位通过一定的算法计算出来通常基于时间戳mac地址随机数等
优点为
性能好本地生成无网络消耗唯一性可以认为不会发生冲突 某些版本基于命名空间能保证唯一性某些版本基于随机数生成不保证唯一性但出现相同UUID的概率非常小根据百度百科的说法以java.util.UUID为例每秒产生10亿笔UUID100年后只产生一次重复的机率是50% 缺点
没有趋势递增特性作为数据库主键时插入性能不高会导致叶分裂数据较宽通常UUID为128bit不能用mysql的bigint存储需使用字符串类型对性能有一定影响信息不安全基于mac生成的uuid可能造成mac地址泄露
应用生成traceId或logId DB自增主键
以mysql为例我们可以专门建一张表利用其自增键来生成唯一ID
表结构如下
CREATE TABLE unique_id (id bigint(20) unsigned NOT NULL auto_increment, value char(20) NOT NULL default ,PRIMARY KEY (id),UNIQUE KEY unique_v(value)
) ENGINEMyISAM;使用以下sql获取id
begin;
replace into unique_id (value) VALUES (placeword);
select last_insert_id();
commit;这里 使用replace而不是insert 是为了保证整个表只有一条记录因为不需要多余的记录也能生成自增id
这种方式利用数据库的自增主键保证生成id的唯一性严格单调递增。缺点为
性能问题每次生成id需要一次数据库远程IO发号器的瓶颈取决于db的读写性能可用性问题只用到一台db实例存在单点问题可用性没有保障 针对上面两个问题可以引入多台mysql每台实例的表使用不同的初始值
以2台mysql实例为例分别做如下配置
mysql1
set auto_increment_offset 1; -- 起始值 set auto_increment_increment 2; -- 步长mysql2
set auto_increment_offset 2; -- 起始值 set auto_increment_increment 2; -- 步长mysql1从 1 开始发号mysql2从 2 开始发号每次发号后递增2 这样mysql1生成的id序列为
1,3,5,7,9....mysql2为
2,4,6,8....当请求到来时采用随机或轮询的方式请求这些实例这样得到的id序列总体为趋势递增既减少了单台实例的访问压力也提高了可用性。缺点为
从单调递增变为趋势递增性能问题 每次生成ID还是有一次远程数据库IO对DB的压力还是大伸缩性问题当需要扩展更多的机器时需要调整之前所有实例的步长且需要保证再次期间生成ID不冲突实现起来较麻烦 Redis incr命令
为了解决数据库自增键遇到的性能问题可以利用 redis的incr 命令来生成不重复的递增ID。该策略相较于数据库方案优点为
从远程磁盘IO变为为远程内存IO性能有一定提升毕竟redis号称10w qps
但为了保证唯一性需要费一番功夫依次讨论redis的各种持久化策略
若不开启 redis 持久化则redis宕机后会丢失已生成的ID再生成会导致ID重复若开启 RDB 或 AOF 中非AOF_FSYNC_ALWAYS模式的持久化可能丢失最近一段时间的ID一样会出现ID重复若开启 AOF 中AOF_FSYNC_ALWAYS模式的持久化能保证即使在宕机的情况下也不会出现ID重复但性能会下降相较于数据库方案没有太大的优势 号段模式
号段模式是为了解决数据库自增主键和redis incr方案中每次获取ID都需要远程请求的问题
即每次从db获取一个ID范围作为一个号段加载到内存这样生成唯一ID时不需要每次都从数据库获取而是从本地内存里获取大大提高性能。本地缓存的号段用完时才请求db获取下一批号段
以mysql为例数据库表结构如下
CREATE TABLE unique_id ( id bigint(20) NOT NULL, max_id bigint(20) NOT NULL COMMENT 下个号段从哪开始分配, step int(10) NOT NULL COMMENT 一批ID的数量, PRIMARY KEY (id) ) ENGINEInnoDB DEFAULT每次获取一个号段时执行如下sql
update unique_id set max_id {max_id} step where max_id {max_id} 当执行成功后判断 affectRows等于1就能保证只有当前实例获得了 [max_id,max_id step) 这个区间的号段就能愉快地在内存发号了
若affectRows不等于1说明有其他实例获取了这个号段需要重试再次获取
号段模式的优点如下
性能很高大部分情况下直接在内存发号无需远程请求号段范围越大远程请求的比例越低可用性较高若数据库宕机可以使用之前获取的号段进行发号号段范围越大能撑的时间越久趋势递增
缺点如下 号段浪费若某实例在号段没用完时就重启或宕机则其号段剩余的ID就浪费了。解决方案为较小号段长度但根据优点中的描述这会降低性能和可用性因此需要选择一个适中的号段长度 不够平滑当号段用完时会请求一次数据库如果此时网络抖动会使得该次请求响应较慢 为了解决这种情况可以在号段即将用完时就异步请求数据库获取下一个号段而不是等到要用完再请求 可用性问题和数据库自增键策略一样的单点问题 如何解决上面提到的可用性问题呢使用多台实例。这里还是以2台实例为例进行说明
每次生获取完号段后将max_id增加 号段长度 * 实例数量
例如初始化时mysql1.max_id0mysql2.max_id1000。step都是1000
第一次访问mysql1获取[0:1000)的号段将mysql1.max_id更新成2000第二次访问mysql2获取[1000:2000)的号段将mysql2.max_id更新成3000第三次访问mysql1获取[2000:3000)的号段将mysql1.max_id更新成4000第四次访问mysql2获取[3000:4000)的号段将mysql2.max_id更新成5000
这样既降低了单台数据库实例的访问压力又提高了可用性
buffer数量设为多大峰值qps的600倍这样db宕机还能提供至少10分钟的服务容灾性高 优点
id位64bit的数字趋势递增对db的压力小可以很方便线性扩展按照bizkey分库分表即可高可用内部有缓存如果数量为峰值qps的600倍那么db宕机10分钟内都可用id可以做到几乎单调递增可自定义maxId大小方便原有业务迁移
缺点
TP999波动大其他时候查本地缓存但当号段用完时要查读写一次db 解决双buffer例如当第一个buffer用到10%时就异步请求第二个buffer的号段 id不够随机泄露发号数量 雪花算法
雪花算法使用一个64位的数字来表示唯一ID而这64位中的每一位怎么用就是其精髓所在
标准的雪花算法每一位含义如下 [0:0] 1位符号位ID一般为正数所以该位为0[1:41] 41位时间通常用来表示 当前时间 - 业务开始时间 的时间差而不是相对于1970年的时间戳这样能支持的时间更久若41位时间戳的单位为毫秒则能支持大约(1 41) / (1000 * 60 * 60 * 24 * 365) 69年[42:51] 10位机器一般机器数没那么多可以将 10位中分5位给机房分5位给机器。这样就可以表示32个机房每个机房下可以有32台机器[52:63] 12位自增序列号表示某台机器上在某一毫秒如果表示时间的单位为毫秒内的生成的ID序列号每毫秒支持112 4096个ID按照 qps算有409.6万
位的分配可以根据业务的不同进行调整例如若机器数没那么多不需要10位表示可增大时间位以支持更长的时间范围。或者业务并发量不高时可将时间单位改为秒将节省出来的位用于表示其他含义
只要每个实例的机器ID不同则不同机器间生成的ID一定不同因为其[42:51]位不一样
这样划分后在一毫秒内一个数据中心的一台机器上可以产生4096个的不重复的ID
其优点为
不依赖数据库性能和可用性非常好如果时间戳在高位能保证ID趋势递增理论上支持超高的并发因为qps有409万基本不可能有业务的写操作能达到这个qps
缺点为
ID的生成强依赖于服务器时钟如果发生时钟回拨则可能和以前生成过的ID产生冲突 时钟回拨硬件时钟可能会因为各种原因发生不准的情况网络中提供了ntp服务来做时间校准做校准的时候就会发生时钟的跳跃或者回拨的问题 10位的机器号较难指定最好不要手工指定而是实例去自动获取 针对时钟回拨问题可分两种情况讨论
实例运行过程中发生时钟回拨此时可以在内存中 记录上次时间戳若这次获取的时间戳比上次小说明发生了时钟回拨可以等待一段时间再进行ID生成若回拨幅度较大则可选择继续等待或给上层报错因为在短时间内无法生成正确的ID 也可以完全不依赖系统时间例如百度的uid-generator使用一个原子变量每次加一来生成下一个时间 实例重启过程中发生时钟回拨此时没办法从内存中获取上次的时间戳因此需要将上次时间戳放到外部存储中。美团leaf的方案为每3s往zookeeper上报一次当前时间戳这样在实例重启时也能判断出是否发生了时钟回拨
但存在外部不能完全避免时钟回拨例如在t时刻将t保存在zk在 t1 时刻分配了一个ID在 t2 时刻宕机时钟回退了1s到t1此时检测 t1 zk 中的时间t没问题。但依然会产生 t1 时刻的重复ID
因此最保险的办法时宕机后sleep一段时间再重启这段时间要超过时钟回退的时间 针对机器号生成困难问题有以下几种解决方案 使用zookeeper每次实例启动时都去zookeeper下创建一个节点利用其节点编号当做机器idzookeeper保证每次生成的节点编号唯一 使用mysql也可以在实例启动时去数据库的表插入一条记录利用自增主键当做机器ID同样能保证机器ID的唯一性
适用场景订单中不想让别人根据早上和晚上的订单id号猜到销量的场景
