栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

10.算法进阶之分布式篇——分布式环境下如何生成唯一ID——UUID

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

10.算法进阶之分布式篇——分布式环境下如何生成唯一ID——UUID

UUID——全局唯一ID——universally unique identifie。

一般来说常用的基于时间进行排序,因为时间是自然递增的。但是全局唯一ID的两个核心要求是:

  1. 全局唯一
  2. 粗略有序

在分布式环境下,很有可能多台机器同时产生了同一个ID,这样就无法唯一的标识某项业务。

引入单点ID生成器

我们可以独立部署一个服务,专门用于生成ID。其他需要ID的服务,都调用这一个接口,这样在一台机器上我们就可以利用本地的时钟或者计数器来分发ID。

问题一:时钟回拨
计算机底层的时钟,主要依靠石英钟,本身是有一定的误差的,计算机定期请求NTP服务,来同步当前时间,这期间其实可能会产生时钟跳跃。

问题二:计数器消失
我们将计数器保存在内存中,一旦这台机器发生断电或者故障,我们就无法知道之前的ID生成到多少了。
即使我们引入Raft协议和Mapreduce的相关备份服务,提高了计数器的可用性,但是这样又会出现主服务和备用服务如何同步的问题。
即使解决了上述问题,单点服务的最大限制在于性能不佳,每个请求都要持久化连接,并发量很容易到瓶颈

基于数据库实现ID生成器

我们知道数据库中主键是绝对唯一的,如果设置主键为auto_increment,数据库可以帮助我们生成唯一的全局ID。
但是单点的数据库仍然和上述问题一样,有性能瓶颈。

水平扩展
我们想用多个数据库同时分配ID,那么怎么保证ID不冲突呢。

比如两个数据库,一个持有所有偶数 ID,一个持有所有奇数 ID。其他业务系统只需要轮询两个数据库,就可以得到粗略有序的全局唯一 ID 了。

为什么是粗略有序,因为没办法保证需求的业务会不断的规律的轮询两个数据库,但是能保证的是随着时间的推移,只要负载均衡算法比较合理,他得到的ID绝对是递增的。

数据库写入瓶颈问题
利用单点思路,把生成ID的响应服务,和存储ID的服务拆开,单点对外提供ID,但是将ID状态记录在数据里

具体来说,每次单点服务向数据库批量申请N个ID,在本地用内存维护这一段ID,并把数据库中已经用过的ID+N,直到这N个被服务申请完,再重复。
这样即使单点服务挂了,我们重启之后直接向数据库申请,也能保证获得的ID是自然递增的,无非就是中间少了存在单点服务的那一小段而已。
这样设计,可以大大减少数据库写入次数,把每次申请变成了每次压力只有1/N,往往可以承受10w级的QPS。

UUID

UUID实现不同于远程调用单点服务,而是直接在业务本地产生,被封装成一个库用以调用。
UUID 一共包含 32 位 16 进制数,也就是相当于 128 位二进制数,显示的时候被分为 8-4-4-4-12 几个部分,看一个例子:

0725f9ac-8cc1-11ec-a8a3-0242ac120002

实现版本一:
用name(一段二进制)计算,保证不同空间不同name得到唯一UUID,而相同空间相同名字UUID相同。
对其做MD5+位运算,最终得到ID。

实现版本二:
基于随机性进行计算,因为 UUID 非常长,所以其重复概率可以忽略不计。
但 UUID 过于冗长,且主流版本完全无序,对数据库存储非常不利,这点我们之后介绍 B+ 树的时候也会展开讨论。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/957190.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号