1. 9IM首页
  2. 热点

分布式ID生成方案简介

在日常的业务开发中,通常需要对一些数据做唯一标识,例如为大量抓取的文章入库时分配一个唯一的id,为用户下的订单分配订单号等等。并发量小的时候,通常会使用数据库自增的主键id作为唯一id。并发量大的时候就会考虑使用一些分布式ID的生成方案来生成id。由于一些特殊的业务需求,我们的业务中也使用到了分布式ID的生成,对分布式ID的各种方案进行了调研。也对开源的分布式ID框架进行了一些优化和改造。本文主要分为以下三个部分:

一.常见的分布式ID生成方案的简单介绍。

二.对当前开源的分布式ID框架实现原理进行分析,例如美团的Leaf和百度的uid-generator。

三.Leaf和uid-generator存在的一些问题及如何进行优化改进。

目前常用的分布式ID生成方案主要由以下几种:

1.使用UUID算法生成唯一id。

2.利用单机数据库主键自增来生成唯一id。

3.多数据库主键自增生成唯一id。(设置步长区分不同数据库)

4.数据库分段发号生成唯一id。(例如美团的Leaf框架中的segement模式)

5.基于snowflake算法生成唯一id(例如美团的Leaf框架中的snowflake模式,百度的uid-generator)

1.UUID

简单的来说,UUID是服务器在不需要任何外界依赖(像类Snowflake算法的方案都需要注册中心)的情况下,基于当前时间、计数器(counter)和硬件标识等等信息生成的唯一ID。

优点

无任何依赖

其他的技术方案都是有依赖的,比如单机数据库主键自增生成ID强依赖数据库,类Snowflake算法的方案至少启动时都需要注册中心,Leaf框架Snowflake模式需要定时上传时间戳到注册中心,的UUID生成不需要任何外界依赖,

缺点

ID太长,且不是数字类型

当然为了唯一性,带来的牺牲就是生成的结果一般是32位的字符串。由于字符串太长,并且不是数字类型,所以不适合作为数据库的主键。

(字符串作为主键id,插入数据时会是在聚集索引中是随机插入,容易造成页分离。而且字符串的比较比数字类型的开销更大,字符串作为主键id查询效率会低于数字类型的主键。)

适用场景

通常可以作为一些临时性唯一标识,例如用户登陆后,生成一个UUID作为登录的会话ID,作为key存储在Redis中,Value是用户相关的信息。

2.单机数据库主键自增

业务量不大时普遍采用这种方案来生成id。

优点

方便接入

因为一般的项目不一定会用到Zookeeper等这些组件,但是基本都会用到数据库,所以项目接入会比较简单,也没有增加额外的维护成本。

单调递增

是绝对的单调递增的,就是从时间线上看,后面生成的id肯定比前面生成的id要大。

缺点

强依赖于数据库

一旦单机数据库发生宕机,就没法生成id,导致整个系统不可用。如果数据库是主从架构的,主库发生故障,切换成从库,如果从库还没来得及收到主库最新的插入id的更新,就有可能导致从库当前的自增id不是最新的,从而生成出重复的id。

id是连续的

id是连续的有可能会成为缺点,竞争对手在当天12点下一个订单,然后在第二天12点下一个订单,可能根据订单id的差就可以推测出每天的订单量。像猫眼电影就使用了这种方法来生成电影的id。一般我们日常使用时,其实为了让我们生成id的方式更难被竞争对手猜测出,一般是不会从1开始的,但是猫眼电影这里是从1开始的,而且是连续的,所以我们使用二分法很快就确定了8875是最大的值,也就是总共有8875部电影,而且由于是连续的,爬取也会比较方便。 猫眼电影的id——也是使用单机数据库生成的,连续自增的

https://maoyan.com/films/1
https://maoyan.com/films/2
https://maoyan.com/films/8874
https://maoyan.com/films/8875
https://maoyan.com/films/8876
(1到8875可以请求到数据,8876及后面的id
请求不到数据,没有这些id对应的电影,说明总共有8875部电影)

除非去做额外的处理(例如定时去获取当前的自增起始值a,然后生成一个随机数b,使用alter table users AUTO_INCREMENT=a+b;命令对自增起始值修改,也就是跳过一些id。)

适用场景

适用于并发量不高的业务。

3.多数据库主键自增生成唯一id。(设置步长区分不同数据库)

可以使用以下命令设置MySQL中表每次自增时的步长,通过将不同数据库的步长设置为一样,可以让不同数据库生成的id进行区分。

CREATE TABLE table (...) AUTO_INCREMENT = n;
alter table <table name> auto_increment=2;
分布式ID生成方案简介

例如,步长是等于数据库的数量,例如有N台数据库, 第一台数据库的起始值是0,那么生成的id就是0,N,2N,3N等等。

第一台数据库的起始值是1,那么生成的id就是1,N+1,2N+1,3N+1等等。 这样各个数据库生成的id就不会冲突,并且每个数据库可以单独生成id。

优点

生成id的效率比单台数据库要高,因为可以多台数据库同时发号。

缺点

是解决了每次自增是1的问题,缺点是一旦设置了步长,就不方便扩容了,因为分库分表的表的数量已经定下来了。

使用场景

在没有分库分表的框架以前,那些分库分表就是使用这种方案来实现的。

4.数据库分段发号生成唯一id。(例如美团的Leaf框架中的segement模式)

简单来说,就是想下图一样,用一个数据库表来充当发号器, 表中字段介绍如下:

biz_tag字段用于区分每种id应用的业务,
max_id字段记录了当前已生成的最大的id,
step字段代表每次可以获取id的数量
分布式ID生成方案简介

id生成项目每次使用下面这条语句从数据库获取step数量的id,并且更新max_id的值,将step数量的id存储在内存中,供业务方通过HTTP,RPC,Client等方式来获取。

UPDATE leaf_alloc SET max_id = max_id + step WHERE biz_tag = #{tag}

优点

效率高

生成id的效率取决于step的大小,不会像主键自增生成id那样再受限于数据库的数量。

缺点

强依赖于数据库

还是强依赖于数据库,数据库宕机后,虽然id生成系统靠内存中还未使用完id,可以维持系统正常运行一段时间,但是数据库不可用还是会导致整个系统不可用。

5.基于snowflake算法生成唯一id

snowflake是推特开源分布式ID生成算法,一共有64位,

第一位是0,标志位

接下来41位是13位的毫秒时间戳,最大可以到2039年9月

接下来10个二进制位是服务器的id

后面12位是业务序列号

分布式ID生成方案简介

 意味着每毫秒最大可以生成2的12次方个id,4096个,支持每个机器每毫秒生成4096个id,每秒可以生成400多万的id

优点

效率高

生成id是比较快,

不依赖其他组件

生成id的过程中,可以做到不额外依赖其他组件。

原创文章,作者:9IM,如若转载,请注明出处:https://www.9im.cn/811.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注