专业IM即时通讯软件开发,值得信赖!

ID生成策略——SnowFlake

未分类 云聊IM 39℃

一、遇到问题

某个项目采用了数据库(MySQL)自增ID作为主要业务数据的主键。数据库自增ID使用简单,自动编号,速度快,而且是增量增长,按顺序存放,对于检索非常有利。

单库环境下,数据库自增ID问题不大。但在分布式环境或分库分表环境下,数据库自增ID逐渐暴露出一些问题。例如,分库分表的情况下保证ID唯一变得困难;订单号等业务数据如果用数据库自增ID,竞对很容易算出大概的业务量。

二、常见的ID生成策略

1、数据库自增ID(前面提到了)

2、UUID

算法的核心思想是结合机器的网卡、当地时间、一个随记数来生成UUID。

优点:本地生成,生成简单,性能好,没有高可用风险

缺点:长度过长,存储冗余,且无序不可读,查询效率低

3、Redis生成ID

Redis生成ID可以看做数据库自增ID的升级版。Redis的所有命令操作都是单线程的,本身提供像 incr 和 increby 这样的自增原子命令,所以能保证生成的 ID 肯定是唯一有序的。

优点:不依赖于数据库,灵活方便,且性能优于数据库;数字ID天然排序,对分页或者需要排序的结果很有帮助。

缺点:如果系统中没有Redis,还需要引入新的组件,增加系统复杂度;需要编码和配置的工作量比较大。

考虑到单节点的性能瓶颈,可以使用 Redis 集群来获取更高的吞吐量。假如一个集群中有5台 Redis。可以初始化每台 Redis 的值分别是1, 2, 3, 4, 5,然后步长都是 5。各个 Redis 生成的 ID 为

4、Twitter的snowflake算法。

三、snowflake算法

snowflake算法,采用64位二进制整数。二进制具体位数含义如下图。

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

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

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

也就是说41位可以表示241−1个毫秒的值,转化成单位年则是(241−1)/(1000∗60∗60∗24∗365)=69年

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

可以部署在1024个节点,包括5位datacenterId和5位workerId

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

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

大多数人都知道这个算法,但Twitter 利用 zookeeper 还做了很多工程上的实现,感兴趣可以看https://github.com/twitter/snowflake

截取git上该工程的主要文件目录, 

git工程README.md文件中有这么一段话

We have retired the initial release of Snowflake and working on open sourcing the next version based on Twitter-server, in a form that can run anywhere without requiring Twitter’s own infrastructure services.

Twitter几年前就停止了对这个项目的维护,新的版本也没见着放出来。好在现有版本的核心算法已经能够满足常规的需求。

当然,snowflake有众多优点的同时也是有缺点的。

优点:

毫秒数在高位,自增序列在低位,整个ID都是趋势递增的。

不依赖数据库等第三方系统,以服务的方式部署,稳定性更高,生成ID的性能也是非常高的。

可以根据自身业务特性分配bit位,非常灵活。

缺点:

强依赖机器时钟,如果机器上时钟回拨,会导致发号重复或者服务会处于不可用状态。

强依赖时钟在有些情况下很致命,我个人就遇到过服务器刚重启的短时间内时间没有同步,造成生成ID出问题的情况!

四、一些改进策略

1、美团Leaf比较完美的方案

美团Leaf比较好的解决了这些问题,参看《Leaf——来自美团点评的分布式ID生成系统》

美团Leaf的方案核心有两点

(1)依靠zookeeper实现workerId的自动化租用

(2)通过算法解决了时钟回拨问题

美团Leaf目前是开源软件,可以在https://github.com/weizhenyi/leaf-snowflake下载

2、一个候选人不严谨但成本很低的实现

我在面试中,一个候选人提出的方法也比较有意思(尽管这个方法不严谨)。

在redis中设置一个整数变量workerNum,初始值为0,snowflake id生成客户端每次启动时读取redis中的变量,用workerNum%1024作为worker的值,然后把redis中的workerNum+1。

在idworker数量不多的情况下,这个方案一般不会出现workerId重复(因为随着业务的迭代,一般情况下idworker过一段时间都会因为业务部署而重启)。如果研发资源特别有限,又想使用snowflake可以考虑一下这个办法。 

3、个人项目中hash分库的解决办法

实际使用中,有时候ID需要支持分库分表,snowflake的默认实现对这块支持得不够。在业务量不大的情况下,snowflake生成的id序列号部分大多都是0,转换为十进制会是偶数。用这个id通过取模hash分库,显然不平均。

万一有这样的需求怎么办呢?可以考虑借助ID时间戳部分实现均匀分布

(1)分库分表逻辑使用ID中时间戳部分做取模。这个方法需要把10进制ID转成2进制,然后移位,再进行计算。比较麻烦

(2)生成ID的时候把序列号部分尾数用时间戳对应的位置覆盖。截段代码,这段代码的取值能保证ID除以128的余数均匀分布。 

喜欢 (0)
仿微信聊天软件开发