细说雪花算法

这篇具有很好参考价值的文章主要介绍了细说雪花算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


背景

需要选择合适的方案去应对数据规模的增长,以应对逐渐增长的访问压力和数据量。
数据库的扩展方式主要包括:业务分库、主从复制,数据库分表。


一、介绍

雪花算法:Twitter的分布式自增ID算法,Snowflake(雪花算法是由Twitter公布的分布式主键生成算法,它能够保证不同表的主键的不重复性,以及相同表的主键的有序性。)

最初Twitter把存储系统从MySQL迁移到Cassandra(由Facebook开发一套开源分布式NoSQL数据库系统)因为Cassandra没有顺序ID生成机制,所有开发了这样一套全局唯一ID生成服务。Twitter的分布式雪花算法SnowFlake,经测试SnowFlake每秒可以产生26万个自增可排序的ID

  • twitter的SnowFlake生成ID能够按照时间有序生成
  • SnowFlake算法生成ID的结果是一个64Bit大小的整数,为一个Long型(转换成字符串后长度最多19)
  • 分布式系统内不会产生ID碰撞(由datacenter 和 workerID做区分)并且效率较高

分布式系统中,有一些需要全局唯一ID的场景,生成ID的基本要求

  • 在分布式环境下,必须全局唯一性
  • 一般都需要单调递增,因为一般唯一ID都会存在数据库,而InnoDB的特性就是将内容存储在主键索引上的叶子节点,而且是从左往右递增的,所有考虑到数据库性能,一般生成ID也最好是单调递增的。为了防止ID冲突可以使用36位UUID,但是UUID有一些缺点,首先是它相对比较长,并且另外UUID一般是无序的
  • 可能还会需要无规则,因为如果使用唯一ID作为订单号这种,为了不让别人知道一天的订单量多少,就需要这种规则

二、结构

雪花算法的几个核心组成部分:
细说雪花算法,MyBatisPlus,算法,spring boot,底层原理,mybatisplus
在Java中64bit的证书是long类型,所以在SnowFlake算法生成的ID就是long类存储的。

  • 第一部分:二进制中最高位是符号位,1表示负数,0表示正数。生成的ID一般都是用整数,所以最高位固定为0。
  • 第二部分:是41bit时间戳位,用来记录时间戳,毫秒级,41位可以表示 2^41 -1 个数字。如果只用来表示正整数,可以表示的范围是:0 - 2^41 -1,减1是因为可以表示的数值范围是从0开始计算的,而不是从1,也就是说41位可以表示 2^41 - 1 毫秒的值,转换成单位年则是 69.73年。
  • 第三部分:工作机器ID,10Bit用来记录工作机器ID,可以部署在2^10 = 1024个节点,包括5位 datacenterId(数据中心,机房) 和 5位 workerID(机器码),5位可以表示的最大正整数是 2 ^ 5 = 31个数字,来表示不同的数据中心 和 机器码。
  • 第四部分:12位bit可以用来表示的正整数是 2^12 = 4095,即可以用0 1 2 … 4094 来表示同一个机器同一个时间戳内产生的4095个ID序号。

SnowFlake可以保证所有生成的ID按时间趋势递增,整个分布式系统内不会产生重复ID,因为有datacenterId 和 workerId来做区分。雪花算法是由scala算法编写的,有人使用java实现:github地址

三、数据库分表

将不同业务数据分散存储到不同的数据库服务器,能够支撑百万甚至千万用户规模的业务,但如果业务继续发展,同一业务的单表数据也会达到单台数据库服务器的处理瓶颈。例如,淘宝的几亿用户数据,如果全部存放在一台数据库服务器的一张表中,肯定是无法满足性能要求的,此时就需要对单表数据进行拆分。

单表数据拆分有两种方式:垂直分表和水平分表。示意图如下:
细说雪花算法,MyBatisPlus,算法,spring boot,底层原理,mybatisplus

1.垂直分表

垂直分表适合将表中某些不常用且占了大量空间的列拆分出去。

例如,前面示意图中的 nickname 和 description 字段,假设我们是一个婚恋网站,用户在筛选其他用户的时候,主要是用 age 和 sex 两个字段进行查询,而 nickname 和 description 两个字段主要用于展示,一般不会在业务查询中用到。description 本身又比较长,因此我们可以将这两个字段独立到另外一张表中,这样在查询 age 和 sex 时,就能带来一定的性能提升。

2.水平分表

水平分表适合表行数特别大的表,有的公司要求单表行数超过 5000 万就必须进行分表,这个数字可以作为参考,但并不是绝对标准,关键还是要看表的访问性能。对于一些比较复杂的表,可能超过 1000万就要分表了;而对于一些简单的表,即使存储数据超过 1 亿行,也可以不分表。
但不管怎样,当看到表的数据量达到千万级别时,作为架构师就要警觉起来,因为这很可能是架构的性能瓶颈或者隐患。

水平分表相比垂直分表,会引入更多的复杂性,例如要求全局唯一的数据id该如何处理:

(1)主键自增

①以最常见的用户 ID 为例,可以按照 1000000 的范围大小进行分段,1 ~ 999999 放到表 1中,
1000000 ~ 1999999 放到表2中,以此类推。
②复杂点:分段大小的选取。分段太小会导致切分后子表数量过多,增加维护复杂度;分段太大可能会导致单表依然存在性能问题,一般建议分段大小在 100 万至 2000 万之间,具体需要根据业务选取合适的分段大小。
③优点:可以随着数据的增加平滑地扩充新的表。例如,现在的用户是 100 万,如果增加到 1000 万,只需要增加新的表就可以了,原有的数据不需要动。
④缺点:分布不均匀。假如按照 1000 万来进行分表,有可能某个分段实际存储的数据量只有 1 条,而另外一个分段实际存储的数据量有 1000 万条。

(2)取模

①同样以用户 ID 为例,假如我们一开始就规划了 10 个数据库表,可以简单地用 user_id % 10 的值来表示数据所属的数据库表编号,ID 为 985 的用户放到编号为 5 的子表中,ID 为 10086 的用户放到编号为 6 的子表中。
②复杂点:初始表数量的确定。表数量太多维护比较麻烦,表数量太少又可能导致单表性能存在问题。
③优点:表分布比较均匀。
④缺点:扩充新的表很麻烦,所有数据都要重分布。

(3)雪花算法(主角登场)

雪花算法是由Twitter公布的分布式主键生成算法,它能够保证不同表的主键的不重复性,以及相同表的主键的有序性。(具体上诉已讲解)


总结

雪花算法优缺点:
优点

  • 毫秒数在高维,自增序列在低位,整个ID都是趋势递增的
  • 不依赖数据库等第三方系统,以服务的方式部署,稳定性更高,生成ID的性能也是非常高的
  • 可以根据自身业务特性分配bit位,非常灵活

缺点

  • 依赖机器时钟,如果机器时钟回拨,会导致重复ID生成
  • 在单机上是递增的,但由于涉及到分布式环境,每台机器上的时钟不可能完全同步,有时候会出现不是全局递增的情况,此缺点可以认为无所谓,一般分布式ID只要求趋势递增,并不会严格要求递增,90%的需求只要求趋势递增。

其它补充
为了解决时钟回拨问题,导致ID重复,后面有人专门提出了解决的方案文章来源地址https://www.toymoban.com/news/detail-723839.html

  • 百度开源的分布式唯一ID生成器 UidGenerator
  • Leaf - 美团点评分布式ID生成系统

到了这里,关于细说雪花算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Spring Boot(Vue3+ElementPlus+Axios+MyBatisPlus+Spring Boot 前后端分离)【二】

    😀前言 本篇博文是关于Spring Boot(Vue3+ElementPlus+Axios+MyBatisPlus+Spring Boot 前后端分离)【二】的,希望你能够喜欢 🏠个人主页:晨犀主页 🧑个人简介:大家好,我是晨犀,希望我的文章可以帮助到大家,您的满意是我的动力😉😉 💕欢迎大家:这里是CSDN,我总结知识的地方,

    2024年02月11日
    浏览(53)
  • Spring Boot(Vue3+ElementPlus+Axios+MyBatisPlus+Spring Boot 前后端分离)【三】

    😀前言 本篇博文是关于Spring Boot(Vue3+ElementPlus+Axios+MyBatisPlus+Spring Boot 前后端分离)【三】的分享,希望你能够喜欢 🏠个人主页:晨犀主页 🧑个人简介:大家好,我是晨犀,希望我的文章可以帮助到大家,您的满意是我的动力😉😉 💕欢迎大家:这里是CSDN,我总结知识的地

    2024年02月11日
    浏览(60)
  • Spring Boot(Vue3+ElementPlus+Axios+MyBatisPlus+Spring Boot 前后端分离)【一】

    😀前言 本篇博文是关于Spring Boot(Vue3+ElementPlus+Axios+MyBatisPlus+Spring Boot 前后端分离)【一】,希望你能够喜欢 🏠个人主页:晨犀主页 🧑个人简介:大家好,我是晨犀,希望我的文章可以帮助到大家,您的满意是我的动力😉😉 💕欢迎大家:这里是CSDN,我总结知识的地方,欢

    2024年02月11日
    浏览(54)
  • Spring Boot(Vue3+ElementPlus+Axios+MyBatisPlus+Spring Boot 前后端分离)【六】

    😀前言 本篇博文是关于Spring Boot(Vue3+ElementPlus+Axios+MyBatisPlus+Spring Boot 前后端分离)【六】,希望你能够喜欢 🏠个人主页:晨犀主页 🧑个人简介:大家好,我是晨犀,希望我的文章可以帮助到大家,您的满意是我的动力😉😉 💕欢迎大家:这里是CSDN,我总结知识的地方,欢

    2024年02月11日
    浏览(54)
  • 企业电子招标采购系统源码Spring Cloud + Spring Boot + MybatisPlus + Redis + Layui

      项目说明 随着公司的快速发展,企业人员和经营规模不断壮大,公司对内部招采管理的提升提出了更高的要求。在企业里建立一个公平、公开、公正的采购环境,最大限度控制采购成本至关重要。符合国家电子招投标法律法规及相关规范,以及审计监督要求;通过电子化

    2024年02月10日
    浏览(47)
  • 企业电子招标采购系统源码Spring Cloud + Spring Boot + MybatisPlus + 前后端分离 + 二次开发

       项目说明 随着公司的快速发展,企业人员和经营规模不断壮大,公司对内部招采管理的提升提出了更高的要求。在企业里建立一个公平、公开、公正的采购环境,最大限度控制采购成本至关重要。符合国家电子招投标法律法规及相关规范,以及审计监督要求;通过电子化

    2024年02月12日
    浏览(67)
  • java 企业工程管理系统软件源码+Spring Cloud + Spring Boot +二次开发+ MybatisPlus + Redis

      工程项目管理软件(工程项目管理系统)对建设工程项目管理组织建设、项目策划决策、规划设计、施工建设到竣工交付、总结评估、运维运营,全过程、全方位的对项目进行综合管理    工程项目各模块及其功能点清单 一、系统管理     1、数据字典:实现对数据字典

    2024年02月10日
    浏览(56)
  • Java版企业电子招标采购系统源码Spring Cloud + Spring Boot +二次开发+ MybatisPlus + Redis

    功能描述 1、门户管理:所有用户可在门户页面查看所有的公告信息及相关的通知信息。主要板块包含:招标公告、非招标公告、系统通知、政策法规。 2、立项管理:企业用户可对需要采购的项目进行立项申请,并提交审批,查看所有的立项信息。主要功能包含:招标立项申

    2024年02月09日
    浏览(56)
  • java 企业工程管理系统软件源码+Spring Cloud + Spring Boot +二次开发+ MybatisPlus + Redis em

     工程项目管理软件(工程项目管理系统)对建设工程项目管理组织建设、项目策划决策、规划设计、施工建设到竣工交付、总结评估、运维运营,全过程、全方位的对项目进行综合管理    工程项目各模块及其功能点清单 一、系统管理     1、数据字典:实现对数据字典标

    2024年02月14日
    浏览(63)
  • Java版企业电子招标采购系统源码Spring Cloud + Spring Boot +二次开发+ MybatisPlus + Redis tbms

    ​   功能描述 1、门户管理:所有用户可在门户页面查看所有的公告信息及相关的通知信息。主要板块包含:招标公告、非招标公告、系统通知、政策法规。 2、立项管理:企业用户可对需要采购的项目进行立项申请,并提交审批,查看所有的立项信息。主要功能包含:招标

    2024年02月12日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包