Dotnet3.0下SnowFlake算法生成53位ID

  1. 云栖社区>
  2. 博客>
  3. 正文

Dotnet3.0下SnowFlake算法生成53位ID

xiaoma 2019-08-08 01:23:26 浏览405
展开阅读全文

世界上没有两片雪花是完全相同的。

为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的ID,这些id还需要一些大致的顺序(方便客户端排序),并且在分布式系统中不同机器产生的ID必须不同。Twitter公司提出了一种名为SnowFlake算法来生成唯一的ID作为系统中的key。

为何需要生成ID?

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

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

通常情况下,我们都会使用数据库的自增主键功能,从1开始,基本可以做到连续递增。Oracle可以用SEQUENCE,MySQL可以用表主键的AUTO_INCREMENT, 虽然不能保证全局唯一,但每个表唯一,也基本满足需求。

但是这样的做法有两个问题,第一个是每次生成都是先要插入数据库,让数据库去生成这个ID后返回。当需要插入关联数据的时候,必须先等数据库插入成功,然后才能插入关联数据。如果插入过程比较长,需要用队列操作的时候,就无法将相关操作放入队列做异步处理。第二个是生成的ID是连续的,很多ID是用于用户号,订单号等敏感信息,网站外部用户可以根据特定时间之间生成的ID差值来估算出业务量。

因此,可以在插入数据库之前,就先用Twitter提出的雪花算法,生成ID后再作为主键插入数据库。

SnowFlake算法

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。严格来说,应该每个进程都需要不同的workId。

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

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

SnowFlake算法生成53位长度整数

如果直接用网上的SnowFlake算法库生成的64位长度整数,在作为主键传递到Web前端的时候,就会碰到一个大坑。JavaScript里面没有64位整数,只有一种Number数据类型表示数字,采用IEEE754格式来表示数字,不区分整数和浮点数,JavaScript中的所有数字都用浮点数值表示,最大的数字精度只有53位,超过这个位数,JavaScript将丢失精度。因此,使用53位整数可以直接由JavaScript读取,而超过53位时,就必须转换成字符串才能保证JavaScript处理正确,这会给API接口带来额外的复杂度。

因此我根据网上的代码,做了一些修改,用c#语言改写SnowFlake算法生成53位长度整数。方法就是保留41位时间戳,加上2位机器编号,10位序列号组成一个53位的ID。对于小型的项目,4个生成器也够用了,每毫秒最多可以生成1024个序列号也足够满足使用。

源代码以MIT协议的方式开源,托管到github

banner_728x90.png

网友评论

登录后评论
0/500
评论
xiaoma
+ 关注