分布式唯一ID生成算法设计之snowflake方案

原创 码农  2019-12-14 11:40:44  阅读 647 次 评论 0 条

snowflake 是什么

snowflake单词原意为雪花,是 twitter开源的一种分布式 ID 生成算法。该算法可以保证在不借助第三方服务或者说工具的情况下,在多台机器上持续生成保证唯一性的 64 位整型 ID。雪花算法生成64位的二进制正整数,然后转换成10进制的数。snowflake 将 ID 的 64 位划分为四块区域,分别填入的是当前服务实例的数据中心 ID,节点 ID,时间戳,以及相同时间戳下的递增序号。64位二进制数由如下部分组成:

分布式唯一ID生成算法设计之snowflake方案 架构 第1张


  • 1位标识符:始终是0

  • 41位时间戳:41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截 - 开始时间截 )得到的值,这里的的开始时间截,一般是我们的id生成器开始使用的时间,由我们程序来指定的

  • 10位机器标识码:可以部署在1024个节点,如果机器分机房(IDC)部署,这10位可以由 5位机房ID + 5位机器ID 组成

  • 12位序列:毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号

优点:

1、此方案每秒能够产生409.6万个ID,性能快

2、时间戳在高位,自增序列在低位,整个ID是趋势递增的,按照时间有序递增

3、灵活度高,可以根据业务需求,调整bit位的划分,满足不同的需求

缺点:

1、依赖机器的时钟,如果服务器时钟回拨,会导致重复ID生成

在分布式场景中,服务器时钟回拨会经常遇到,一般存在10ms之间的回拨;小伙伴们就说这点10ms,很短可以不考虑吧。但此算法就是建立在毫秒级别的生成方案,一旦回拨,就很有可能存在重复ID。

优化思路

雪花算法的问题就是时钟回拨导致,那我们能不能尽量避免回拨呢?思路就是:我们在系统中监控每台时钟是否回拨?如果回拨了,我们作一下调整就行了。

分布式唯一ID生成算法设计之snowflake方案 架构 第2张


上图是整体架构,利用zookeeper中间件的特性

一个ID服务就是一个生成ID的应用,多个可以保证高可用

我们先看持久化节点的作用:就是保存各个ID服务的节点信息,并保存时钟

启动场景的整体流程

1、ID服务启动,注册到zookeeper

2、检查是否之前注册过,如果没有注册过,就把此服务注册到zookeeper中

3、节点的信息利用顺序节点,保证唯一。ID服务再把此生成的顺序ID当作workID,保存到本地文件系统中,这样以后再次启动时,就拿着此workId到zk上面去查找,是否之前注册过(其实这个逻辑,就实现了自动发workId的功能,不需要人为到每个ID服务去配置,极大的减少运维成本)

4、如果之前没有注册过,生成了ID服务的zk节点,并把本地的时钟保存到此zk节点中。(保存时需要判断检测,此时钟是否正常?如何做呢?留一个思考点)。

5、如果在注册的时候,发现已经注册了,要去比较一下本地时钟 和 zk节点上面的时钟,如果本地时钟 大于 zk上的,表示正常,启动成功否则表示本地的时钟发生了回拨,启动不成功,启动报警机制。

服务运行中的流程

1、ID服务启动成功,提供ID服务

2、ID服务会每隔3秒,把本地时钟上报到zk节点上面

临时节点的作用

小伙伴们还记得老顾留下的思考点,如何判断本地时钟是否正确?就是利用临时节点。

1、遍历所有正在提供服务的ID服务器(IP + port),获取所有的ID服务器当地时钟,求平均值sum(time)/nodeSize。

2、如abs( 本地系统时间-sum(time)/nodeSize ) < 阈值,认为当前系统时间准确,正常启动服务,同时写临时节点leaf_temporary/${self} 维持租约

3、如大于阈值,认为时钟不正确,启动不成功,报警

总结

snowflake 雪花算法核心思想,就介绍到这里,希望能够帮助小伙伴。如果需要源码,可以去github中leaf-snowflake。算法值得一看。整体实现逻辑比较清晰。

也许小伙伴们用不到,不过最主要的是了解他们的设计思想、思路及解决方案。


本文地址:https://www.itcodeit.com/post/16.html
版权声明:本文为原创文章,版权归 码农 所有,欢迎分享本文,转载请保留出处!

发表评论


表情

还没有留言,还不快点抢沙发?