这篇文章主要讲解了“Snowflake算法的实现原理”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“Snowflake算法的实现原理”吧！Snowflake（雪花）是Twitter开源的高性能ID生成算法（服务）。上图是Snowflake的Github仓库，master分支中的REAEMDE文件中提示：初始版本于2010年发布，基于Apache Thrift，早于Finagle（这里的Finagle是Twitter上用于RPC服务的构建模块）发 香港云主机布，而Twitter内部使用的Snowflake是一个完全重写的程序，在很大程度上依靠Twitter上的现有基础架构来运行。而2010年发布的初版Snowflake源码是使用Scala语言编写的，归档于scala_28分支。换言之，大家目前使用的Snowflake算法原版或者改良版已经是十年前（当前是2020年）的产物，不得不说这个算法确实比较厉害。scala_28分支中有介绍该算法的动机和要求，这里简单摘录一下：动机：Cassandra中没有生成顺序ID的工具，Twitter由使用MySQL转向使用Cassandra的时候需要一种新的方式来生成ID（印证了架构不是设计出来，而是基于业务场景迭代出来）。要求：高性能：每秒每个进程至少产生10K个ID，加上网络延迟响应速度要在2ms内。顺序性：具备按照时间的自增趋势，可以直接排序。紧凑性：保持生成的ID的长度在64 bit或更短。高可用：ID生成方案需要和存储服务一样高可用。下面就Snowflake的源码分析一下他的实现原理。Snowflake在初版设计方案是：时间：41 bit长度，使用毫秒级别精度，带有一个自定义epoch，那么可以使用大概69年。可配置的机器ID：10 bit长度，可以满足1024个机器使用。序列号：12 bit长度，可以在4096个数字中随机取值，从而避免单个机器在1 ms内生成重复的序列号。但是在实际源码实现中，Snowflake把10 bit的可配置的机器ID拆分为5 bit的Worker ID（这个可以理解为原来的机器ID）和5 bit的Data Center ID（数据中心ID），详情见IdWorker.scala：也就是说，支持配置最多32个机器ID和最多32个数据中心ID：由于算法是Scala语言编写，是依赖于JVM的语言，返回的ID值为Long类型，也就是64 bit的整数，原来的算法生成序列中只使用了63 bit的长度，要返回的是无符号数，所以在高位补一个0（占用1 bit），那么加起来整个ID的长度就是64 bit：其中：41 bit毫秒级别时间戳的取值范围是：[0, 2^41 - 1] => 0 ~ 2199023255551，一共2199023255552个数字。5 bit机器ID的取值范围是：[0, 2^5 - 1] => 0 ~ 31，一共32个数字。5 bit数据中心ID的取值范围是：[0, 2^5 - 1] => 0 ~ 31，一共32个数字。12 bit序列号的取值范围是：[0, 2^12 - 1] => 0 ~ 4095，一共4096个数字。那么理论上可以生成2199023255552 * 32 * 32 * 4096个完全不同的ID值。Snowflake算法还有一个明显的特征：依赖于系统时钟。41 bit长度毫秒级别的时间来源于系统时间戳，所以必须保证系统时间是向前递进，不能发生时钟回拨（通说来说就是不能在同一个时刻产生多个相同的时间戳或者产生了过去的时间戳）。一旦发生时钟回拨，Snowflake会拒绝生成下一个ID。Snowflake算法中使用了大量的位运算。由于整数的补码才是在计算机中的存储形式，Java或者Scala中的整型都使用补码表示，这里稍微提一下原码和补码的知识。原码用于阅读，补码用于计算。正数的补码与其原码相同。负数的补码是除最高位其他所有位取反，然后加1（反码加1），而负数的补码还原为原码也是使用这个方式。+0的原码是0000 0000，而-0的原码是1000 0000，补码只有一个0值，用0000 0000表示，这一点很重要，补码的0没有二义性。简单来看就是这样：使用原码、反码在计算的时候得到的不一定是准确的值，而使用补码的时候计算结果才是正确的，记住这个结论即可，这里不在举例。由于Snowflake的ID生成方案中，除了最高位，其他四个部分都是无符号整数，所以四个部分的整数使用补码进行位运算的效率会比较高，也只有这样才能满足Snowflake高性能设计的初衷。Snowflake算法中使用了几种位运算：异或（^）、按位与（&）、按位或（|）和带符号左移（）。异或的运算规则是：0^0=0 0^1=1 1^0=1 1^1=0，也就是位不同则结果为1，位相同则结果为0。主要作用是：特定位翻转，也就是一个数和N个位都为1的数进行异或操作，这对应的N个位都会翻转，例如0100 & 1111，结果就是1011。与0项异或，则结果和原来的值一致。两数的值交互：a=a^b b=b^a a=a^b，这三个操作完成之后，a和b的值完成交换。这里推演一下最后一条：按位与的运算规则是：0&0=0 0&1=0 1&0=0 1&1=1，只有对应的位都为1的时候计算结果才是1，其他情况的计算结果都是0。主要作用是：清零，如果想把一个数清零，那么和所有位为0的数进行按位与即可。取一个数中的指定位，例如要取X中的低4位，只需要和zzzz...1111进行按位与即可，例如取1111 0110的低4位，则11110110 & 00001111即可得到00000110。按位与的运算规则是：0|0=0 0|1=1 1|0=1 1|1=1，只要有其中一个位存在1则计算结果是1，只有两个位同时为0的情况下计算结果才是0。主要作用是：对一个数的部分位赋值为1，只需要和对应位全为0的数做按位或操作就行，例如1011 0000如果低4位想全部赋值为1，那么10110000 | 00001111即可得到1011 1111。带符号左移的运算符是，一般格式是：M 。作用如下：M的二进制数（补码）向左移动n位。左边（高位）移出部分直接舍弃，右边（低位）移入部分全部补0。移位结果：相当于M的值乘以2的n次方，并且0、正、负数通用。移动的位数超过了该类型的最大位数，那么编译器会对移动的位数取模，例如int移位33位，实际上只移动了33 % 2 = 1位。推演过程如下（假设n = 2）：可以写个main方法验证一下：利用上面提到的三个位运算符，相互组合可以实现一些高效的计算方案。计算n个bit能表示的最大数值：Snowflake算法中有这样的代码：这里的算子是-1L ^ (-1L ，整理运算符的顺序，再使用这样就能计算出64 bit的二进制数推演计算过程如下：5 bit能表示的最大数值n，n为整数并且0 ，即用固定位的最大值作为Mask避免溢出：0、1、2、3...31。Worker ID和Data Center ID部分的最大值就是使用这种组合运算得出的。Snowflake算法中有这样的代码：最后这个算子其实就是sequence = (sequence + 1) & 4095，假设sequence当前值为4095，推演一下计算过程：可以编写一个main方法验证一下：也就是x = (x + 1) & (-1L ^ (-1L 能保证最终得到的x值不会超过N，这是利用了按位与中的"取指定位"的特性。Snowflake虽然用Scala语言编写，语法其实和Java差不多，当成Java代码这样阅读就行，下面阅读代码的时候会跳过一些日志记录和度量统计的逻辑。先看IdWorker.scala的属性值：接着看算法的核心代码逻辑：最后一段逻辑的位操作比较多，但是如果熟练使用位运算操作符，其实逻辑并不复杂，这里可以画个图推演一下：四个部分的整数完成左移之后，由于空缺的低位都会补充了0，基于按位或的特性，所有低位只要存在1，那么对应的位就会填充为1，由于四个部分的位不会越界分配，所以这里的本质就是：四个部分左移完毕后最终的数字进行加法计算。Snowflake算法有几个比较大的问题：低并发场景会产生连续偶数，原因是低并发场景系统时钟总是走到下一个毫秒值，导致序列号重置为0。依赖系统时钟，时钟回拨会拒绝生成新的ID（直接抛出异常）。Woker ID和Data Center ID的管理比较麻烦，特别是同一个服务的不同集群节点需要保证每个节点的Woker ID和Data Center ID组合唯一。这三个问题美团开源的Leaf提供了解决思路，下图截取自com.sankuai.inf.leaf.snowflake.SnowflakeIDGenImpl：对应的解决思路是（不进行深入的源码分析，有兴趣可以阅读以下Leaf的源码）：序列号生成添加随机源，会稍微减少同一个毫秒内能产生的最大ID数量。时钟回拨则进行一定期限的等待。使用Zookeeper缓存和管理Woker ID和Data Center ID。Woker ID和Data Center ID的配置是极其重要的，对于同一个服务（例如支付服务）集群的多个节点，必须配置不同的机器ID和数据中心ID或者同样的数据中心ID和不同的机器ID（简单说就是确保Woker ID和Data Center ID的组合全局唯一），否则在高并发的场景下，在系统时钟一致的情况下，很容易在多个节点产生相同的ID值，所以一般的部署架构如下：管理这两个ID的方式有很多种，或者像Leaf这样的开源框架引入分布式缓存进行管理，再如笔者所在的创业小团队生产服务比较少，直接把Woker ID和Data Center ID硬编码在服务启动脚本中，然后把所有服务使用的Woker ID和Data Center ID统一登记在团队内部知识库中。如果完全不考虑性能的话，也不考虑时钟回拨、序列号生成等等问题，其实可以把Snowflake的位运算和异常处理部分全部去掉，使用Long.toBinaryString()方法结合字符串按照Snowflake算法思路拼接出64 bit的二进制数，再通过Long.parseLong()方法转化为Long类型。编写一个main方法如下：然后把代码规范一下，编写出一个简版Snowflake算法实现的工程化代码：通过字符串拼接的写法虽然运行效率低，但是可读性会比较高，工程化处理后的代码可以在实例化时候直接指定Worker ID和Data Center ID等值，并且这个简易的Snowflake实现没有第三方库依赖，拷贝下来可以直接运行。上面的方法使用字符串拼接看起来比较低端，其实最后那部分的按位或，可以完全转化为加法：这样看起来整个算法都变得简单，不过这里涉及到指数运算和加法运算，效率会比较低。感谢各位的阅读，以上就是“Snowflake算法的实现原理”的内容了，经过本文的学习后，相信大家对Snowflake算法的实现原理这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是开发云，小编将为大家推送更多相关知识点的文章，欢迎关注！
本篇内容主要讲解“Git使用技巧实例分析”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“Git使用技巧实例分析”吧!在安装好git后，你第一件该做的事是设置你的名字和电子邮箱，因为每次提交都要用到这些信息：保存在gi…
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
