分布式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;

例如，步长是等于数据库的数量，例如有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生成项目每次使用下面这条语句从数据库获取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位是业务序列号

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

优点

效率高

生成id是比较快，

不依赖其他组件

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