一文读懂“Snowflake(雪花)”算法 |
您所在的位置:网站首页 › 不会重复的符号是什么 › 一文读懂“Snowflake(雪花)”算法 |
🚕 一、了解Snowflake🛵 1.1 何为Snowflake算法 Snowflake 中文的意思为雪花,所以 Snowflake算法 常被称为 雪花算法,是 Twitter(现“X”)开源的分布式 ID 生成算法,是一种分布式主键ID生成的解决方案。 雪花算法生成后是一个 64bit 的 long 型的数值,组成部分引入了时间戳,基本保持了自增。 🚐 1.2 为何要使用雪花算法在讲解雪花(Snowflake)算法前,让我们先思考下面的场景: 现在的服务基本是分布式、微服务形式的,而且大数据量也导致分库分表的产生,对于水平分表就需要保证表中 id 的全局唯一性。 对于 MySQL 而言,一个表中的主键 id 一般使用自增的方式,但是如果进行水平分表之后,多个表中会生成重复的 id 值。那么如何保证水平分表后的多张表中的 id 是全局唯一性的呢? 有多种方案,如: 1、数据库主键自增 可以让不同表初始化一个不同的初始值,然后按指定的步长进行自增。例如有3张拆分表,初始主键值为1,2,3,自增步长为3。 2、UUID 用 UUID 来作为主键,但是 UUID 生成的是一个无序的字符串,对于 MySQL 推荐使用增长的数值类型值作为主键来说不适合。 3、Redis 使用 Redis 的自增原子性来生成唯一 id,但是这种方式业内比较少用。 当然还有其他解决方案,不同互联网公司也有自己内部的实现方案。雪花算法是其中一个用于解决分布式 id 的高效方案,也是许多互联网公司在推荐使用的。 🥯 1.3 雪花优缺点优点: 优点 解释 高性能高可用 生成时不依赖于数据库,完全在内存中生成 高吞吐 每秒钟能生成数百万的自增 ID ID 自增 存入数据库中,索引效率高 缺点: 依赖服务器时间,服务器时间回拨时可能会生成重复 id。 在获取时间的时候,可能会出现时间回拨的问题,什么是时间回拨问题呢?就是服务器上的时间突然倒退到之前的时间。 人为原因,把系统环境的时间改了;有时候不同的机器上需要同步时间,可能不同机器之间存在误差,那么可能会出现时间回拨问题。小小的解决方案:算法中可通过记录最后一个生成 id 时的时间戳来解决,每次生成 id 之前比较当前服务器时钟是否被回拨,避免生成重复 id。 由于时间回拨导致的生产重复的ID的问题,其实百度和美团都有自己的解决方案了,有兴趣可以去看看。 🍌 二、深入雪花🥗 2.1 雪花算法组成雪花结构如下图所示: ![]() 上面有说过雪花算法会生成 64bit 的 long 型的数值,而这64bit 可以分为四个组成部分: 固定值: 1bit,最高位是符号位,0 表示正,1 表示负,固定为 0,如果是 1 就是负数了。 时间戳: 41bit,存储毫秒级时间戳(41 位的长度可以使用 69 年)。 标识位(存储机器码): 10bit,上面中的 机器id(5bit)和 服务id(5bit)统一叫作“标识位”,两个标识位组合起来最多可以支持部署 1024 个节点。 序列号: 12bit,用于表示在同一毫秒内生成的多个ID的序号。如果在同一毫秒内生成的ID超过了4096个(2的12次方),则需要等到下一毫秒再生成ID。 默认的雪花算法是 64 bit,具体的长度可以自行配置。 如果希望运行更久,增加时间戳的位数;如果需要支持更多节点部署,增加标识位长度;如果并发很高,增加序列号位数。 总结:雪花算法并不是一成不变的,可以根据系统内具体场景进行定制。 🍱 2.2 雪花算法适用场景因为雪花算法有序自增,保障了 MySQL 中 B+ Tree 索引结构插入高性能。 所以,日常业务使用中,雪花算法更多是被应用在数据库的主键 ID 和业务关联主键。 🍧 三、分析雪花🥯 3.1 生成 ID 重复问题假设场景: 一个订单微服务,通过雪花算法生成 ID,共部署三个节点,标识位一致。此时有 200 并发,均匀散布三个节点,三个节点同一毫秒同一序列号下生成 ID,那么就会产生重复 ID。 通过上述假设场景,可以知道雪花算法生成 ID 冲突存在一定的前提条件: 服务通过集群的方式部署,其中部分机器标识位一致;业务存在一定的并发量,没有并发量无法触发重复问题;生成 ID 的时机:同一毫秒下的序列号一致。解决方案:如果能保证标识位不重复,那么雪花 ID 也不会重复,有三种方案: 预分配: 应用上线前,统计当前服务的节点数,人工去申请标识位。这种方案,没有代码开发量,在服务节点固定或者项目少可以使用,但是解决不了服务节点动态扩容性问题。 动态分配: 通过将标识位存放在 Redis、Zookeeper、MySQL 等中间件,在服务启动的时候去请求标识位,请求后标识位更新为下一个可用的。 统一分配ID: 启动一个专门分配ID的服务,它来统一分配各个业务或服务需要的ID。 🍷 3.2 第一位为什么不使用在雪花算法中,第一位是符号位,0表示整数,第一位如果是1则表示负数,我们用的ID默认就是正数,所以默认就是0,那么这一位默认就没有意义。 🍬 3.3 标识位怎么用标识位一共10 bit,如果全部表示机器,那么可以表示1024台机器,如果拆分,5 bit 表示机房,5bit表示机房里面的机器,那么可以有32个机房,每个机房可以用32台机器。 🌹 四、开源分布式 ID 框架Leaf 和 Uid 都有实现雪花算法,Leaf 额外提供了号段模式生成 ID。 美团 Leaf:https://github.com/Meituan-Dianping/Leaf 百度 Uid:https://github.com/baidu/uid-generator 雪花算法 可以满足大部分场景,如无必要,不建议引入开源方案增加系统复杂度。 🍗 五、总结雪花算法依赖于时间的一致性,如果发生时间回拨,可能会导致问题。为了解决这个问题,通常会使用拓展位来扩展时间戳的位数。原本雪花算法只能支持69年的时间范围,但根据实际需求,可以增加时间戳的位数来延长可使用的年限,比如使用42位可以支持139年的时间范围。然而,对于很多公司来说,首要任务是生存下来,因此可能会权衡取舍,不过度追求时间戳位数的增加。 需要注意的是,雪花算法也有一些缺点。在单机上,生成的ID是递增的,但在多台机器上,只能大致保持递增趋势,并不能严格保证递增。这是因为多台机器之间的时钟不一定完全同步。因此,在多机器环境下,对于严格的递增需求,需要考虑其他解决方案。 总而言之,雪花算法是一种常用的分布式唯一ID生成算法,但并非完美解决方案。在使用时,需要根据实际需求和限制条件进行权衡和选择,以寻找适合自己情况的解决方案。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |