本文的重点主要是身份变送器的相关知识,介绍了雪花算法和他的基本原理和实现。 以下是本节的重点内容,也是面试中的重点考点。
什么是ID变送器,为什么需要ID变送器,使用ID变送器常见的集中实现方法雪花算法的基本原理和实现(PS:实现的过程没有重点,可以理解)雪花算法进行增长请简单了解一下Vesta;一、前言
前面的常见脸书“如何将长URL转换为短URL”介绍了如何将长地址URL转换为短地址URL。 其中,理想的解决方案是使用变送器生成唯一的整数ID,并将其转换为短地址URL的62进制数字。
其中使用了ID变送器,但很多合作伙伴可能还不知道什么是ID变送器,以及如何实现。 今天一起讨论一下什么是身份变送器吧。 ID变送器的原理是什么? 实现ID变送器等的方法。
二、从数据库主键ID说起
1、单机数据库
如果我们的业务访问量不是很大,我们可以使用一台数据库服务器来满足我们的业务需求。 我们通常在设计数据库时,主键ID使用bigint类型,并设置为自递增、无符号,如下所示:
这种方法完全能够满足我们的业务需求,并且生成全局唯一的增量ID是数据库提供的一种功能,具有以下优点
)1)可以保证唯一性
)2)能保证增加性
)3)固定步长
但是,当我们的业务逐渐扩大,我们需要进行将数据库分类和分表等操作时,这种方式已经没有办法了
想想看。 如果我们有业务,每个省都有自己的数据库,而用户表用于记录当前省的用户信息,那么有一天,我们会将每个省用户表的所有用户信息集成到中央数据库的用户表中进行统计这是因为每个省的用户表的ID都从1主键开始增加。
2、数据库集群、分库分表
当我们的数据库达到一定规模时,就需要将其分割成表。 分割表化时,很难保证主键ID的唯一性。 这一点我很理解。 之所以这么说,是因为我们的表被划分为不同机器上的数据库,依靠数据库中的自我增加功能可以保证ID的唯一性。 如下图所示。
User表中的100W数据分为两个数据库,每个数据库中的主键ID都是自增长的,但不能保证全局主键ID是自增长的。 这显然是错误的。 怎么解决这个问题?
(1) UUID
最简单和最容易思考的是使用UUID。 众所周知,根据UUID的特性,可以创建唯一的字符串。 由于uid是本地生成的,所以相对性能高、时延低、可扩展性强,完全不受库分区表的影响!
但是,使用UUID有点问题,主要表现在:
uid不能保证趋势的增加; uID太长,经常用32位字符串表示,占用数据库空间很大,创建主键时索引中主键id占用空间大的uID作为主键索引的查询效率不高,是常见的优化方案uID保证全局主键ID的唯一性,但UUID不规则,写入b树索引时随机写入过多(连续ID生成部分顺序写入),写入时顺序auid 需要进行insert操作,读取整个b树节点并添加到内存中,插入此记录后将整个节点写回磁盘的操作在记录占用空间较大的情况下性能下降明显。
)2) ID组
in-left:0pt;">虽然,UUID很方便,但由于他的一些弊端我们无法接受,所以在很多对一些性能要求较高的业务场景中,我们是很少使用UUID的,那我们还有没有什么其他方法哪?接下来让我们看一下ID分组的使用:如上图所述,由1个数据库变成4个库,每个数据库设置不同的auto_increment初始值int,以及相同的增长步长step,以保证每个数据库生成的ID是不同的,改进后的架构保证了可用性,但缺点是:
丧失了ID生成的“绝对递增性”,但这个问题不大,我们的目标是趋势递增,不是绝对递增;数据库的写压力依然很大,每次生成ID都要访问数据库;可扩展性差;我们可以想象的是,目前虽然我们的机器只有4台,然后由不同的int和不同的step,但是如果我们需要在其中再加一台机器的话,可想而知我们需要手动更新int和step,这是一件比较繁琐的事情!但有人可能会说了,我们可以直接把 step设置大一些,假如,我们预期数据最大规模的时候用100台数据库服务器就可以了,那我们就可以设置step为100。尽管如此,扩展性还不是很高!
3、还有什么操作哪?
上述我们讨论了一个一个的优缺点,当然,还有很多其他的主键ID生成方案。但总的来说,我们讨论问题的关键浮出水面:如何高效生成趋势有序的全局唯一ID,兼顾有序性、高性能、可扩展等因素!
这就需要我们今天的主角登场了,他就是:ID发号器!ID发号器的主要思想大致相同,但不同平台的实现方式可能会有所不同,本文主要介绍一下:Twitter公司的SnowFlake、如何自己实现一个ID发号器、Vesta框架。
三、SnowFlake简介
Twitter公司的SnowFlake算法就是著名的《雪花算法》,SnowFlake是通过Scala语言实现的,目前GitHub上已经看不到源代码了,只有一个2010年的版本,地址为:
https://github.com/twitter/snowflake/releases/tag/snowflake-2010,因此很难在我们实际的项目中真正的使用到 ,我们更多的是采用雪花算法的思想,去构建自己属于自己的ID发号器。
1、SnowFlake原理
SnowFlake产生的ID是一个64位的整型,结构如下(每一部分用“-”符号分隔):
(1)1位:标识部分,在java中由于long的最高位是符号位,正数是0,负数是1,一般生成的ID为正数,所以为0;
(2)41位:时间戳部分,这个是毫秒级的时间,一般实现上不会存储当前的时间戳,而是时间戳的差值(当前时间-固定的开始时间),这样可以使产生的ID从更小值开始;41位的时间戳可以使用69年,(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年;
(3)10位:节点部分,Twitter实现中使用前5位作为数据中心标识,后5位作为机器标识,可以部署1024个节点;
(4)12位:序列号部分,支持同一毫秒内同一个节点可以生成4096个ID;
SnowFlake算法生成的ID大致上是按照时间递增的,用在分布式系统中时,需要注意数据中心标识和机器标识必须唯一,这样就能保证每个节点生成的ID都是唯一的!
2、SnowFlake算法如何实现
SnowFlake算法的实现在GitHub或者码云上有各种实现版本!SnowFlake算法为我们提供了一个可行的思路,但是我们不一定都需要像上面那样使用5位作为数据中心标识,5位作为机器标识,可以根据我们业务的需要,灵活分配节点部分,如:若不需要数据中心,完全可以使用全部10位作为机器标识;若数据中心不多,也可以只使用3位作为数据中心,7位作为机器标识。所以,我们可以看出SnowFlake算法只是一种指导思想,我们下边自己简单的实现一个一下!
四、如何自己实现一个ID发号器
注意这里只有生成ID的部分,没有Client也没有Server!
写个测试用例如下:
五、Vesta框架简介
Vesta是一款通用的ID产生器,互联网俗称统一发号器,它具有全局唯一、粗略有序、可反解和可制造等特性,它支持三种发布模式:嵌入发布模式、中心服务器发布模式、REST发布模式,根据业务的性能需求,它可以产生最大峰值型和最小粒度型两种类型的ID,它的实现架构使其具有高性能,高可用和可伸缩等互联网产品需要的质量属性,是一款通用的高性能的发号器产品。
码云:https://gitee.com/robertleepeak/vesta-id-generator
GitHub:https://github.com/cloudatee/vesta-id-generator
由于Vesta的设计与实现较为复杂,一小节不足以说明清楚,这里不再详细的介绍,有兴趣的参考上述仓库地址文档!