分布式系列-分布式ID

2021年9月5日 4点热度 0条评论 来源: 码头工人

原创文章,转载请标注。https://www.cnblogs.com/boycelee/p/15227230.html

一、数据库自增(单实例)1、方案描述2、优点3、缺点二、数据库集群模式1、方案描述2、优点3、缺点三、Redis优点缺点四、UUID优点缺点五、号段模式优点缺点六、雪花算法(SnowFlake)优点缺点七、Leaf号段模式优化双Buffer解决时钟问题参考

一、数据库自增(单实例)

1、方案描述

基于数据库自增ID(auto_increment)利用其来充当分布式ID。实现方式就是用一张表来充当ID生成器,当我们需要ID时,向表中插入一条记录返回主键ID。

CREATE TABLE identity_table(
  `id` INT(11) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT '主键id',
  `value` VARCHAR(50NOT NULL DEFAULT '' COMMENT 'value',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='ID信息表';
<insert id="insertAndGetId" useGeneratedKeys="true" keyProperty="id">  
    insert into identity_table(value)  
    values(#{value})
</insert>

2、优点

(1)通过数据库保证唯一性,实现简单;

(2)数字ID,具备有序性。

3、缺点

(1)存在单点宕机风险;

(2)无法抗住高并发场景。

二、数据库集群模式

1、方案描述

基于多实例数据库主键自增,通过横向扩展机器,解决单点数据库的压力。实现方式就是在自增ID(auto_increment)的基础上,设置step增长步长,使得不同实例中的ID不会发生碰撞。

set @@auto_increment_offset = 0;     -- 起始值
set @@auto_increment_increment = 3;  -- 步长

1630223792570-3d087bcb-aa9d-4c22-88a8-b849e83a5282

2、优点

(1)利用水平扩展机器,解决单点问题;

3、缺点

(1)扩展实例,需要修改步长,操作复杂;

(2)产生ID需要依赖数据库,数据库的性能依然是瓶颈。

三、Redis

当使用数据库来生成ID性能不够要求的时候,我们可以尝试使用Redis来生成ID。通过Redis的原子操作 INCR和INCRBY来实现。

可以使用Redis集群来获取更高的吞吐量。假如一个集群中有3台Redis。可以初始化每台Redis的值分别是0,1,2,然后步长都是3。

1630338567842-e2b46247-1f39-4c9a-9745-76028cfb588f

优点

(1)不依赖于数据库,性能优于数据库;

(2)ID是有序的。

缺点

(1)强依赖于Redis,Redis宕机也会有风险;

(2)有I/O操作,网络抖动会影响服务响应速度。

四、UUID

UUID 是由一组32位数的16进制数字所构成,是故 UUID 理论上的总数为16^32=2^128,约等于3.4 x 10123。也就是说若每纳秒产生1百万个 UUID,要花100亿年才会将所有 UUID 用完。

UUID生成版本:

version 1date-time & MAC address
version 2date-time & group/user id
version 3, MD5 hash & namespace
version 4, pseudo-random number
version 5, SHA-1 hash & namespace

Java实现:

/**
     * Static factory to retrieve a type 4 (pseudo randomly generated) UUID.
     *
     * The {@code UUID} is generated using a cryptographically strong pseudo
     * random number generator.
     *
     * @return  A randomly generated {@code UUID}
     */

    public static UUID randomUUID() {
        SecureRandom ng = Holder.numberGenerator;

        byte[] randomBytes = new byte[16];
        ng.nextBytes(randomBytes);
        randomBytes[6]  &= 0x0f;  /* clear version        */
        randomBytes[6]  |= 0x40;  /* set to version 4     */
        randomBytes[8]  &= 0x3f;  /* clear variant        */
        randomBytes[8]  |= 0x80;  /* set to IETF variant  */
        return new UUID(randomBytes);
    }

碰撞概率:

Java中的UUID使用的是版本4进行实现,128bit中有122bit是随机产生的,产生的UUID重复概率非常低,所以在使用时可以不考虑此问题。

最终生成UUID:

123e4567-e89b-12d3-a456-426655440000

索引问题:

导致索引重排。

对于B+树的结构:
(1)孩子数和key的数目相同

1630337385867-35d40ea1-5bc3-4cd3-b3cc-af4e15f56787

优点

(1)实现简单;

(2)本地生成,无性能瓶颈;

(3)具备唯一性。

缺点

(1)ID是无序的;

(2)ID无特定含义;

(3)UUID是字符串且长度较长,存储与查询效率慢。

五、号段模式

号段模式可以理解为从数据库批量的获取自增ID,每次从数据库取出一个号段范围,例如 (1,1000] 代表1000个ID,具体的业务服务将本号段,生成1~1000的自增ID并加载到内存。

CREATE TABLE id_generator (
  id int(10NOT NULL,
  max_id bigint(20NOT NULL COMMENT '当前最大id',
  step int(20NOT NULL COMMENT '号段的布长',
  biz_type    int(20NOT NULL COMMENT '业务类型',
  version int(20NOT NULL COMMENT '版本号',
  PRIMARY KEY (`id`)

a. biz_type :代表不同业务类型

b. max_id :当前最大的可用id

c. step :代表号段的长度

d. version :是一个乐观锁,每次都更新version,保证并发时数据的正确性

img

等这批号段ID用完,再次向数据库申请新号段,对max_id字段做一次update操作,update max_id= max_id + step,update成功则说明新号段获取成功,新的号段范围是(max_id ,max_id +step]。

架构图:

1630289552285-6cfd8f45-b82e-46c1-a12a-e32eb0bbad5d

update id_generator set max_id = #{max_id+step}, version = version + 1 where version = # {version} and biz_type = XXX

由于多业务端可能同时操作,所以采用版本号version乐观锁方式更新,这种分布式ID生成方式不强依赖于数据库,不会频繁的访问数据库,对数据库的压力小很多,查询频率减小到1/step。

优点

(1)ID号码是趋势递增的,满足数据库存储和查询性能要求

(2)可用性高,即使ID生成服务器不可用,也能够使得业务在短时间内可用。

(3)可以自定义max_id的大小,方便业务迁移,方便机器横向扩张

缺点

(1)ID号码不够随机,完整的顺序递增可能带来安全问题;

(2)DB宕机可能导致整个系统不可用,仍然存在这种风险,因为号段只能撑一段时间。

六、雪花算法(SnowFlake)

SnowFlake算法是Twitter开源的分布式ID生成算法。生成长度为64bit的long型的数字作为全局唯一ID。

1630248359241-f223465b-d7b9-40cd-b4c2-bffca3673ae5

a. 1bit

第一个bit是符号位,生成的ID是正数,所以第一个bit是0。

**b. 41bit

**41bit可以表示2^41个毫秒值,相当于69年。

c. 10bit

10bit可以表示工作机器,5bit表示(2^5=32个)机房,剩余5bit表示(2^5=32台)机器。表示最多可以标识(2^10=1024台)机器

d. 12bit

用来标识同一毫秒内的(2^12 - 1 = 4095个)不同的id

优点

(1)高性能高可用:生成时不依赖于数据库,完全在内存中生成;

(2)容量大:每秒中能生成数百万的自增ID;

(3)ID自增:存入数据库中,索引效率高。

缺点

(1)依赖系统时钟,如果时间回调或改变,会造成ID冲突。

七、Leaf

号段模式优化

数据库的I/O操作(更新、查询)会是瓶颈,所以需要对此进行优化。

如果在号段消费完之后才从数据库获取新的号段,就会存在2个问题:

(1)查询DB过程出现网络抖动或慢查询会导致系统响应时间变长;

(2)DB的I/O操作本身耗时,如果请求进来但号段未取回就会造成阻塞。

双Buffer

为了能做到DB取号过程能做到无阻塞,当号段消费到某个点时异步吧下一个号段加载到内存中。异步更新,通过双Buffer的方式,保证在DB服务出现问题时,仍然能够有一个Buffer号段能够使用。

详细实现如下图:

1630294365846-2153fb4e-1859-4962-9fdd-deb2ff2e0c2b

采用双buffer的方式,Leaf服务内部有两个号段缓存区segment。当前号段已下发10%时,如果下一个号段未更新,则另启一个更新线程去更新下一个号段。当前号段全部下发完后,如果下个号段准备好了则切换到下个号段为当前segment接着下发,循环往复。

解决时钟问题

因为这种方案依赖时间,如果机器的时钟发生了回拨,那么就会有可能生成重复的ID号,需要解决时钟回退的问题。

1630296792707-97a82d32-b19d-430b-b5ee-2e301ca0ee3f
1630255764082-f4508b14-9252-425c-8801-0376db42fbf1

参见上图整个启动流程图

(1)服务启动时首先检查自己是否写过ZooKeeper leaf_forever节点:

(2)若写过,则用自身系统时间与leaf_forever/selfleafforever/{self}时间则认为机器时间发生了大步长回拨,服务启动失败并报警;

(3)若未写过,证明是新服务节点,直接创建持久节点leaf_forever/

(4)若abs( 系统时间-sum(time)/nodeSize ) < 阈值,认为当前系统时间准确,正常启动服务,同时写临时节点leaf_temporary/selfLeafleaftemporary(Leafsnowflake)IPPortRPCsum(time)/nodeSize4abs(sum(time)/nodeSize)<leaftemporary/{self} 维持租约;

(5)否则认为本机系统时间发生大步长偏移,启动失败并报警;

(6)每隔一段时间(3s)上报自身系统时间写入leaf_forever/${self};

参考

[1] B+树简历过程(https://www.jianshu.com/p/08fe11a5fbb9)

[2] 美团Leaf源码分析(https://www.jianshu.com/p/92d34144dcb7)

[3] 美团点评分布式ID生成系统(https://tech.meituan.com/2017/04/21/mt-leaf.html)

[4] 美团分布式ID生成服务开源(https://tech.meituan.com/2019/03/07/open-source-project-leaf.html)

原创文章,转载请标注。https://www.cnblogs.com/boycelee/p/15227230.html

    原文作者:码头工人
    原文地址: https://www.cnblogs.com/boycelee/p/15227230.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。