博文精选 |分布式唯一 ID 解决方案 - 雪花算法

2021-07-13 10:27:41

F5小安

行业:互联网

 

关键字:单体架构、ID 生成器、数据库、安全编码

 

摘要:全局唯一 ID 几乎是所有设计系统时都会遇到的,全局唯一 ID 在存储和检索中有至关重要的作用。

 

 

阅读时长:5分钟


以下文章来源于InfoQ!作者:JavaPub


以上是针对ID  的介绍,希望对大家有帮助!




前言


单体架构的服务的日子已经一去不复返了。


当前系统业务和数据存储的复杂度都在提升,分布式系统是目前使用非常普遍的解决方案。


全局唯一 ID 几乎是所有设计系统时都会遇到的,全局唯一 ID 在存储和检索中有至关重要的作用。


ID 生成器


在应用程序中,经常需要全局唯一的 ID 作为数据库主键。如何生成全局唯一 ID?


首先,需要确定全局唯一 ID 是整型还是字符串?如果是字符串,那么现有的 UUID 就完全满足需求,不需要额外的工作。缺点是字符串作为 ID 占用空间大,索引效率比整型低。


如果采用整型作为 ID,那么首先排除掉 32 位 int 类型,因为范围太小,必须使用 64 位 long 型。


采用整型作为ID时,如何生成自增、全局唯一且不重复的ID?


数据库自增


数据库自增 ID 是我们在数据量较小的系统中经常使用的,利用数据库的自增 ID,从 1 开始,基本可以做到连续递增。Oracle 可以用 SEQUENCE,MySQL 可以用主键的 AUTO_INCREMENT,虽然不能保证全局唯一,但每个表唯一,也基本满足需求。


数据库自增 ID 的缺点是数据在插入前,无法获得 ID。数据在插入后,获取的 ID 虽然是唯一的,但一定要等到事务提交后,ID 才算是有效的。有些双向引用的数据,不得不插入后再做一次更新,比较麻烦。


在我们开发过程中,遇到一种 主主数据库同步(简单可以理解为,同样的 sql 再另一台数据库再执行一次)的场景,如果使用数据库自增 ID,就会出现主键不一致、或主键冲突问题。


分布式 ID 生成器

方案一:UUID


分布式环境不推荐使用


uuid 是我们比较先想到的方法,在 java.util;包中就有对应方法。这是一个具有 rfc 标准的 uuid:https://www.ietf.org/rfc/rfc4122.txt


uuid 有很好的性能(本地调用),没有网络消耗。


但是,uuid 不易存储(生成了字符串、存储过长、很多场景不适用);信息不安全(基于 MAC 地址生成、可能会造成泄露,这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。

);无法保证递增(或趋势递增);其他博主反馈,截取前 20 位做唯一 ID ,在大数量(大概只有 220w)情况下会有重复问题。


UUID.randomUUID().toString()


方案二:snowflake(雪花算法)


这是目前使用较多分布式 ID 解决方案,推荐使用


背景 Twitter 云云就不介绍了,就是前段时间封了懂王账号的 Twitter。


算法介绍


SnowFlake 算法生成 id 的结果是一个 64bit 大小的整数,它的结构如下图:



  • 1 位,不用。二进制中最高位为 1 的都是负数,但是我们生成的 id 一般都使用整数,所以这个最高位固定是 0


  • 41 位,用来记录时间戳(毫秒)。

- 41 位可以表示 2^{41}-1 个数字,

- 如果只用来表示正整数(计算机中正数包含 0),可以表示的数值范围是:0 至 2^{41}-1,减 1 是因为可表示的数值范围是从 0 开始算的,而不是 1。

- 也就是说 41 位可以表示 2^{41}-1 个毫秒的值,转化成单位年则是 (2^{41}-1) / (1000 60 60 * 24 * 365) = 69 年

  • 10 位,用来记录工作机器 id。

- 可以部署在 2^{10} = 1024 个节点,包括 5 位 datacenterId 和 5 位 workerId

- 5 位(bit)可以表示的最大正整数是 2^{5}-1 = 31 ,即可以用 0、1、2、3、....31 这 32 个数字,来表示不同的 datecenterId 或 workerId

  • 12 位,序列号,用来记录同毫秒内产生的不同 id。

- 12 位(bit)可以表示的最大正整数是 2^{12}-1 = 4095 ,即可以用 0、1、2、3、....4094 这 4095 个数字,来表示同一机器同一时间截(毫秒)内产生的 4095 个 ID 序号。

由于在 Java 中 64bit 的整数是 long 类型,所以在 Java 中 SnowFlake 算法生成的 id 就是 long 来存储的。


SnowFlake 可以保证


  1. 同一台服务器所有生成的 id 按时间趋势递增

  2. 整个分布式系统内不会产生重复 id(因为有 datacenterId 和 workerId 来做区分)


存在的问题:

  1. 机器 ID(5 位)和数据中心 ID(5 位)配置没有解决,分布式部署的时候会使用相同的配置,任然有 ID 重复的风险。

  2. 使用的时候需要实例化对象,没有形成开箱即用的工具类。

  3. 强依赖机器时钟,如果机器上时钟回拨,会导致发号重复或者服务会处于不可用状态。(这点在正常情况下是不会发生的)


针对上面问题,这里提供一种解决思路,workId 使用服务器 hostName 生成,dataCenterId 使用 IP 生成,这样可以最大限度防止 10 位机器码重复,但是由于两个 ID 都不能超过 32,只能取余数,还是难免产生重复,但是实际使用中,hostName 和 IP 的配置一般连续或相近,只要不是刚好相隔 32 位,就不会有问题,况且,hostName 和 IP 同时相隔 32 的情况更加是几乎不可能的事,平时做的分布式部署,一般也不会超过 10 台容器。


生产上使用 docker 配置一般是一次编译,然后分布式部署到不同容器,不会有不同的配置。这种情况就对上面提到的出现了不确定情况,这个在评论中会再出一篇参考文章。


源码


Java 版雪花 ID 生成算法




 






 

 

阅读原文 

声明:本文章版权归原作者及原出处所有 。凡本社区注明来源:XXX或转自:XXX”的作品均转载自其它媒体,转载目的在于传递分享更多知识,内容为作者个人观点,仅供参考,并不代表本社区赞同其观点和对其真实性负责。本社区转载的文章,我们已经尽可能的对作者和来源进行了注明,若因故疏忽,造成漏注,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本社区拥有对此声明的最终解释权。

 

 

 

你还不能错过:

 

IDC最新报告:F5在中国软件安全网关市场份额稳居前三

发布评论 加入社群

发布评论

相关文章

博文精选 |如何让开发人员接受 DevSecOps

F5小安

2021-07-13 10:00:21 37

博文精选 |一份处理宕机的应急响应入门指南

F5小安

2021-07-07 13:47:38 42

博文精选 | DevSecOps 安全检查清单

F5小安

2021-06-24 16:55:15 45

Login

手机号
验证码
© 2019 F5 Networks, Inc. 版权所有。京ICP备16013763号-1