0
0

分布式系统中唯一ID的生成

四火 发表于 2017年06月30日 23:59 | Hits: 741
Tag: Distributed System | ID | Service | 分布式

分布式系统中唯一ID的生成其实老早就像写一点这个话题。几乎我见过的所有大型系统中,都需要一个唯一ID的生成逻辑。别看小小的ID,需求和场景还挺多:

  • 这个ID多数为数字,但有时候是数字字母的组合;
  • 可能随机,也可能要求随时间严格递增;
  • 有时ID的长度和组成并不重要,有时候却要求它严格遵循规则,或者考虑可读性而要求长度越短越好;
  • 某些系统要求ID可以预期,某些系统却要求ID随机性强,无法猜测(例如避免爬虫等等原因)。

独立的生成服务

比如数据库。最常见的一种,也是应用最多的一种,就是利用数据库的自增长序列。比如Oracle中的sequence的nextVal。有多台application的host,但是只有一个数据库。本质上这是耍了个小赖皮,把某分布式系统唯一ID的生成逻辑寄托到一个特定的数据库上,于是分布式系统存在中心节点了。

这个方法简单,而且可以严格保证单调递增。不过中心化带来的问题众所周知,比如单点故障,比如性能方面的扩展上限。有一种workaround,正如同数据库有主从库一样,可以给不同的数据库设置sequence范围(比如一个是从1~100000000,另一个是从100000001到200000000),或者是设置相同的步长(比如一个是1、3、5、7……另一个是2、4、6、8……),但是互相不重复,从而保证唯一性。不过这样不同sequence生成节点整体内的ID递增性就丢失了。

其它的生成服务也有很多,很多系统中设计的ticket server本质上也就是扮演这样一个角色,特点是这个ID生成服务系统必须独立于现有母系统(客户系统)。但是注意,单点service不代表一定会存在单点故障,单点service一样可以HA。因为这个service也可以是去中心化的。

既然说到这样的service,开源ID生成算法上,最最有名的是Twitter的snowflake,它正是重点考虑到high scale而设计的。64bit长度以下,无需节点间复杂的协作,ID有序。每一条snowflake生成的ID都包含三个部分:timestamp、节点编号,以及一个自增的子序列号。额外地,需要提及其中两个问题的处理:

  • timestamp冲突:timestamp本身是毫秒级的,如果出现冲突,那么其中的自增子序列号会自动+1从而保证生成的ID不会和上一条的冲突。
  • 节点编号的生成:这个其实是从Zookeeper去获取的,也是被诟病说它不够去中心化的原因之一(一个改进方案是Boundary Flake,不需要依赖于这个获取逻辑)。

本地生成器

这个也很常见,局限性也非常明显。通常必须满足这样的要求:在不同的host(分布式节点)之间没有关系保证(比如递增性)。

比如我见过这样的逻辑,用host的唯一编号来作前缀(保证环境中节点编号的唯一性即可),毫秒数来生成ID的主体部分。看似简单,一样可以解决唯一ID的问题。当然它的局限性也很多,如果使用当前毫秒数,无法对于不同host生成的ID进行先后比较(因为无法确保时间是严格一致的);而且只能一个毫秒最多只能生成一个ID,如果要生成两个就会产生冲突。这两个问题当中,对于后者有一个改进方案,就是使用一个AtomicLong来保证冲突情况下的自增序列。

既然提到了AtomicLong,有一些开源项目做到了对AtomicLong的分布式实现。比如Redisson(基于Redis)。但这不属于这里讨论的本地生成器范畴。

还有一种典型是UUID。UUID的全称叫做universally unique identifier,Java中一个UUID代表一个128bit的数。在分布式系统中,它比前面说的方案有更多优势,比如长度一致,比如没有一个毫秒内最多只能生成一个的要求。但是,尽管可以认为它是唯一的,基于随机数产生的UUID冲突却是理论上可能存在的。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

原文链接: http://www.raychase.net/4408

0     0

评价列表(0)