图解各路分布式ID生成算法( 二 )

同理可证 1+x*N=3+y*N和 2+x*N=3+y*N也是如此 。
优点

  • 性能显然高于基于数据库的 Flicker方案
  • ID递增
缺点
  • 水平扩展困难
  • Redis集群宕机可能会产生重复的id
  • 易破解
UUID
想必这个大家都熟悉 。UUID是通用唯一识别码(Universally Unique Identifier)的缩写,是一种软件建构的标准,亦为开放软件基金会组织在分布式计算环境领域的一部分 。
原理
图解各路分布式ID生成算法

文章插图
 
UUID是由一组32位数的16进制数字所构成,是故UUID理论上的总数为16^32 = 2^128,约等于3.4 x 10^38 。也就是说若每纳秒产生1兆个UUID,要花100亿年才会将所有UUID用完 。
UUID是利用同一时空中的所有机器都是唯一的这一规则来确保唯一性的 。
图解各路分布式ID生成算法

文章插图
 
具体外形为:
图解各路分布式ID生成算法

文章插图
 
通常由以下几部分组成:
  • 系统时间
  • 时钟序列
  • 全局唯一的IEEE机器识别,如网卡mac、机器SN等
生成方式多种多样,业界公认的是五种,分别是uuid1,uuid2,uuid3,uuid4,uuid5 。
目前使用最广泛的UUID是微软的 GUID 。
优点
  • 本地生成,性能极佳 。无网络消耗
  • 全局唯一
缺点
  • 存储麻烦 。16字节128位,通常以36长度的字符串表示,很多场景不适用
  • 通常是字符串,非自增,无序,不利于做主键 。每次插入都会对B+tree结构进行修改
  • 破解相对困难,但是也不安全 。参考"梅丽莎病毒事件,病毒作者制作的UUID包含Mac地址,被警方破解后,直接定位,抓捕归案"
snowflake
snowflake即雪花算法,Twitter发明的 。
原理
外形长这样:
图解各路分布式ID生成算法

文章插图
 
  • 1位不用 。二进制中最高位为1的都是负数,但是我们生成的id一般都使用整数,所以这个最高位固定是0 。
  • 41位,用来记录毫秒的时间戳 。41位可以表示的数值范围是:0 至 2^{41}-1,减1是因为可表示的数值范围是从0开始算的,而不是1,转化为年则是 2^{41}-1)/(1000*60*60*24*365)=69年 。
  • 10位,用来记录工作机器id 。最多可以部署在2^{10} = 1024个节点,我们可以根据具体的业务来定制具体分配的机器数量和每台机器1毫秒产生的id序号number数 。例如可以把10bit分5bit给IDC,分5bit给工作机器 。这样就可以表示32个IDC,每个IDC下可以有32台机器,可以将内容配置在配置文件中,服务去获取 。
  • 12位 。用来表示单台机器每毫秒生成的id序号,12位bit可以表示的最大正整数为2^12 - 1 = 4096,若超过4096,则重新从0开始 。即,每台机器1毫秒内最多产生4096个ID,足够用了 。
最后将上述4段bit通过位运算拼接起来组成64位bit.
由于是64位bit,所以完全可以用数字来表示ID 。
基本是根据:
图解各路分布式ID生成算法

文章插图
 
优点
  • ID为数字且时间位在高位,整个ID都是趋势递增的 。
  • 不依赖任何第三方库,完全可以自己写,且性能非常高 。
  • 可根据业务定制分配bit位,非常灵活 。得益于 10位机器IDbit位 。
  • 不太容易破解
缺点
  • 依赖机器的时间,如果机器时间不准或者回拨,可能导致重复
总结
在国内也得到了比较普遍的应用,各大厂根据其基本原理,生成了自己的规则:
  • 百度的uid-generator:https://github.com/baidu/uid-generator
  • 美团Leaf:https://github.com/zhuzhong/idleaf
请关注我的微信公众号 互联网技术窝,问题直接在公众号内留言即可
参考文献:
[flicker算法原文] http://code.flickr.com/blog/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/
[分布式唯一ID极简教程] https://mp.weixin.qq.com/s/cqIK5Bv1U0mT97C7EOxmnA
[分布式 ID 生成策略] https://mp.weixin.qq.com/s/UAvSUDFJ8Fr0a-Na2Vr22g
[分布式ID系列(2)——UUID适合做分布式ID吗] https://mp.weixin.qq.com/s/kZAnYzJj4aBrtsk8Q9wA
https://segmentfault.com/a/1190000011282426
https://juejin.im/post/5d6fc8eff265da03ef7a324b#comment
https://segmentfault.com/a/1190000010978305
[Leaf——美团点评分布式ID生成系统] https://tech.meituan.com/2017/04/21/mt-leaf.html


推荐阅读