• 中文
    • English
  • 注册
  • 查看作者
  • 面试官:说说你平时都用过哪些分布式ID生成方案?

    1、为什么需要分布式ID?

    对于单体系统来说,主键ID可能会常用主键自动的方式进行设置,这种ID生成方法在单体项目是可行的,但是对于分布式系统,分库分表之后,就不适应了,比如订单表数据量太大了,分成了多个库,如果还采用数据库主键自增的方式,就会出现在不同库id一致的情况,虽然是不符合业务的

    面试官:说说你平时都用过哪些分布式ID生成方案?

    2、业务系统对分布式ID有什么要求?

    • 全局唯一性:ID是作为唯一的标识,不能出现重复

    • 趋势递增:互联网比较喜欢MySQL数据库,而MySQL数据库默认使用InnoDB存储引擎,其使用的是聚集索引,使用有序的主键ID有利于保证写入的效率

    • 单调递增:保证下一个ID大于上一个ID,这种情况可以保证事务版本号,排序等特殊需求实现

    • 信息安全:前面说了ID要递增,但是最好不要连续,如果ID是连续的,容易被恶意爬取数据,指定一系列连续的,所以ID递增但是不规则是最好的

    3、分布式ID生成方案

    • UUID

    • 数据库自增

    • 号段模式

    • Redis实现

    • 雪花算法(SnowFlake)

    • 百度Uidgenerator

    • 美团Leaf

    • 滴滴TinyID

    3.1 UUID

    UUID (Universally Unique Identifier),通用唯一识别码的缩写。UUID的标准型式包含32个16进制数字,以连字号分为五段,形式为8-4-4-4-12的36个字符,示例: 863e254b-ae34-4371-87da-204b71d46a7b 。UUID理论上的总数为1632=2128,约等于3.4 x 10^38。

    • 优点性能非常高,本地生成的,不依赖于网络

    • 缺点不易存储,16 字节128位,36位长度的字符串信息不安全,基于MAC地址生成UUID的算法可能会造成MAC地址泄露,暴露使用者的位置uuid的无序性可能会引起数据位置频繁变动,影响性能

    3.2、数据库自增

    在分布式环境也可以使用mysql的自增实现分布式ID的生成,如果分库分表了,当然不是简单的设置好 auto_increment_incrementauto_increment_offset 即可,在分布式系统中我们可以多部署几台机器,每台机器设置不同的初始值,且步长和机器数相等。比如有两台机器。设置步长step为2,Server1的初始值为1(1,3,5,7,9,11…)、Server2的初始值为2(2,4,6,8,10…)。这是Flickr团队在2010年撰文介绍的一种主键生成策略(Ticket Servers: Distributed Unique Primary Keys on the Cheap )

    假设有N台机器,step就要设置为N,如图进行设置:

    面试官:说说你平时都用过哪些分布式ID生成方案?

    这种实现的缺陷:

    • ID没有了单调递增的特性,只能趋势递增,有些业务场景可能不符合

    • 数据库压力还是比较大,每次获取ID都需要读取数据库,只能通过多台机器提高稳定性和性能

    3.3、号段模式

    这种模式也是现在生成分布式ID的一种方法,实现思路是会从数据库获取一个号段范围,比如 [1,1000], 生成1到1000的自增ID加载到内存中,建表结构如:

    • biz_type :不同业务类型

    • max_id :当前最大的id

    • step :代表号段的步长

    • version :版本号,就像MVCC一样,可以理解为乐观锁

    等ID都用了,再去数据库获取,然后更改最大值

    • 优点:有比较成熟的方案,像百度Uidgenerator,美团Leaf

    • 缺点:依赖于数据库实现

    3.4、 Redis实现

    Redis分布式ID实现主要是通过提供像 INCRINCRBY 这样的自增原子命令,由于Redis单线程的特点,可以保证ID的唯一性和有序性

    这种实现方式,如果并发请求量上来后,就需要集群,不过集群后,又要和传统数据库一样,设置分段和步长

    优缺点:

    • 优点:Redis性能相对比较好,又可以保证唯一性和有序性

    • 缺点:需要依赖Redis来实现,系统需要引进Redis组件

    3.4、 雪花算法(SnowFlake)

    Snowflake,雪花算法是由Twitter开源的分布式ID生成算法,以划分命名空间的方式将64-bit位分割成多个部分,每个部分代表不同的含义,64位,在java中Long类型是64位的,所以java程序中一般使用Long类型存储

    面试官:说说你平时都用过哪些分布式ID生成方案?

    • 第一部分:第一位占用1bit,始终是0,是一个符号位,不使用

    • 第二部分:第2位开始的41位是时间戳。41-bit位可表示241个数,每个数代表毫秒,那么雪花算法可用的时间年限是(241)/(1000 60 60 24 365)=69 年的时间

    • 第三部分:10-bit位可表示机器数,即2^10 = 1024台机器。通常不会部署这么多台机器

    • 第四部分:12-bit位是自增序列,可表示2^12 = 4096个数。觉得一毫秒个数不够用也可以调大点

    • 优点:雪花算法生成的ID是趋势递增,不依赖数据库等第三方系统,生成ID的效率非常高,稳定性好,可以根据自身业务特性分配bit位,比较灵活

    • 缺点:雪花算法强依赖机器时钟,如果机器上时钟回拨,会导致发号重复或者服务会处于不可用状态。如果恰巧回退前生成过一些ID,而时间回退后,生成的ID就有可能重复。

    3.5、 百度Uidgenerator

    百度的UidGenerator是百度开源基于Java语言实现的唯一ID生成器,是在雪花算法 snowflake 的基础上做了一些改进。引用官网的解释:

    详细的,可以参考官网解释,链接:https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

    3.6、 美团Leaf

    Leaf 提供两种生成的ID的方式:号段模式(Leaf-segment)和snowflake模式(Leaf-snowflake)。你可以同时开启两种方式,也可以指定开启某种方式,默认两种方式为关闭状态。

    • Leaf­segment数据库方案

      其实就是前面介绍的号段模式的改进,可以引用美团技术博客的介绍:

    表结构设计:

    • Leaf­snowflake方案

      Leafsnowflake是在雪花算法上改进来的,引用官网技术博客介绍:

    面试官:说说你平时都用过哪些分布式ID生成方案?

    这种方案解决了前面提到的雪花算法的缺陷,官网没解释,不过Leaf­snowflake对其进行改进,官网的流程图

    面试官:说说你平时都用过哪些分布式ID生成方案?

    详细介绍请看官网:https://tech.meituan.com/2017/04/21/mt-leaf.html

    3.7、 滴滴TinyID

    Tinyid是用Java开发的一款分布式id生成系统,基于数据库号段算法实现。Tinyid扩展了leaf-segment算法,支持了多数据库和tinyid-client

    Tinyid也是基于号段算法实现,系统实现图如下:

    面试官:说说你平时都用过哪些分布式ID生成方案?

    • 优点:方便集成,有成熟的方案和解决实现

    • 缺点:依赖 DB的稳定性,需要采用集群主从备份的方式提高 DB的可用性

    如果感觉本文对你有帮助,点赞关注支持一下,想要了解更多Java后端,大数据,算法领域最新资讯可以关注我公众号【架构师老毕】私信666还可获取更多Java后端,大数据,算法PDF+大厂最新面试题整理+视频精讲

  • 0
  • 0
  • 0
  • 68
  • 请登录之后再进行评论

    登录
  • 任务
  • 实时动态
  • 发布
  • 单栏布局 侧栏位置: