分布式id解决方案

文章目录

• 1.分布式id实现方案
• • 1.1.uuid
  • 1.2 数据库主键自增
  • 1.3 Redis自增
  • 1.4 号段模式
  • 1.5 雪花算法（snowflake）
  • • 1.5.1 百度（uid-generator）
    • 1.5.2 美团（Leaf）

所谓id就是能够用作唯一标识的记号。
在我们日常的设计中，对于单体架构，我们一般使用数据库的自增Id来作为表的主键，但是对于一个分布式系统，就会出现ID冲突，所以对于分布式ID而言，也需要具备分布式系统的特点：高并发，高可用，高性能等特点。

1.分布式id实现方案

我们先看看常见的分布id解决方案以及各自特点的对比

• 1.UUID 这种方案复杂度最低，但是会影响存储空间和性能
• 2.利用单机数据库的自增主键，作为分布式ID的生成器，复杂度适中，ID长度较UUID更短，但是受到单机数据库性能的限制，并发量大的时候，该方案也不是最优方案。
• 3.利用redis,zookeeper的特性来生成id，如：redis的自增命令，zookeeper的顺序节点，这种方案和单机数据库（mysql）性能相比，性能会有所提高，可以适当选用。
• 4.雪花算法：一切问题如果能直接用算法解决，那是最合适的，利用雪花算法可以生成分布式Id,其底层原理就是通过某台机器在某一毫秒内对某一个数字自增，这种方案也能保证分布式架构中的系统id唯一，但是只能保证趋势递增。

下面我们具体看看这些方案的对比：

描述

优点

缺点

UUID

UUID是通用唯一标识码的缩写，其目的是上分布式系统中的所有元素都有唯一的辨识信息，而不需要通过中央控制器来指定唯一标识。

1. 降低全局节点的压力，使得主键生成速度更快；2. 生成的主键全局唯一；3. 跨服务器合并数据方便

1. UUID占用16个字符，空间占用较多；2. 不是递增有序的数字，数据写入IO随机性很大，且索引效率下降

数据库主键自增

MySQL数据库设置主键且主键自动增长

1. INT和BIGINT类型占用空间较小；2. 主键自动增长，IO写入连续性好；3. 数字类型查询速度优于字符串

1. 并发性能不高，受限于数据库性能；2. 分库分表，需要改造，复杂；3. 自增：数据量泄露

Redis自增

Redis计数器，原子性自增

使用内存，并发性能好

1. 数据丢失；2. 自增：数据量泄露

号段模式

依赖于数据库，但是区别于数据库主键自增的模式

较自增id性能有显著的提升

受限于数据库性能；

雪花算法（snowflake）

大名鼎鼎的雪花算法，分布式ID的经典解决方案

1. 不依赖外部组件；2. 性能好

时钟回拨

上面提到了五种解决方案，目前流行的分布式ID解决方案有两种：「号段模式」和「雪花算法」。

1.1.uuid

这种方式很简单，在每次需要新增数据的时候，先生成一个uuid

String id=UUID.randomUUID().toString();

1.2 数据库主键自增

我们需要专门创建一个表来存放id，
表可以设计成以下样子：

CREATE TABLE SEQID.SEQUENCE_ID ( 
    id bigint(20) unsigned NOT NULL auto_increment, 
    stub char(10) NOT NULL default '', 
    PRIMARY KEY (id), 
    UNIQUE KEY stub (stub) 
);

在每次新增的时候，先向该表新增一条数据，然后获取返回新增的主键作为要插入的主键Id，我们可以使用下面的语句生成并获取到一个自增ID

begin; 
replace into SEQUENCE_ID (stub) VALUES ('anyword'); 
select last_insert_id(); 
commit;

可能很多人读到这儿有些疑惑，stub是干嘛的？
stub字段在这里并没有什么特殊的意义，只是为了方便的去插入数据，只有能插入数据才能产生自增id。
而对于插入我们用的是replace，replace会先看是否存在stub指定值一样的数据，如果存在则先delete再insert，如果不存在则直接insert。
说这么多，可能大家还是感觉不是很直观，我们实际去操作一下。

我们去执行操作插入语句：

我们可以看到这条语句返回的是新增的主键id，我们在多执行几次这条语句。

我又执行了5次，把自增Id增加到了6，我们打开数据表看看里面长什么样子

可以看到数据库里面永远只有一条数据。

这种生成分布式ID的机制，需要一个单独的Mysql实例，虽然可行，但是基于性能与可靠性来考虑的话都不够，业务系统每次需要一个ID时，都需要请求数据库获取，性能低，并且如果此数据库实例下线了，那么将影响所有的业务系统。

1.3 Redis自增

因为Redis是单线程的，所以可以用来生成全部唯一ID，通过incr、incrby实现。
生产环境可能是Redis集群，假如有5个Redis实例，每个Redis的初始值是1,2,3,4,5，然后增长都是5
各个Redis生成的ID为：
A：1,6,11,16,21
B：2,7,12,17,22
C：3,8,13,18,23
D：4,9,14,19,24
E：5,10,15,20,25

这样的话，无论请求打到那个Redis上面，都可以获得不同的ID
下面我们实操一下，更直观的感受一下

使用redis的效率是非常高的，但是要考虑持久化的问题。Redis支持RDB和AOF两种持久化的方式。

• RDB持久化相当于定时打一个快照进行持久化，如果打完快照后，连续自增了几次，还没来得及做下一次快照持久化，这个时候Redis挂掉了，重启Redis后会出现ID重复。
• AOF持久化相当于对每条写命令进行持久化，如果Redis挂掉了，不会出现ID重复的现象，但是会由于incr命令过多，导致重启恢复数据时间过长。

1.4 号段模式

我们可以使用号段的方式来获取自增ID，号段可以理解成批量获取，比如DistributIdService从数据库获取ID时，如果能批量获取多个ID并缓存在本地的话，那样将大大提供业务应用获取ID的效率。

比如DistributIdService每次从数据库获取ID时，就获取一个号段，比如(1,1000]，这个范围表示了1000个ID，业务应用在请求DistributIdService提供ID时，DistributIdService只需要在本地从1开始自增并返回即可，而不需要每次都请求数据库，一直到本地自增到1000时，也就是当前号段已经被用完时，才去数据库重新获取下一号段。
下面我具体去尝试实现一下：

CREATE TABLE id_generator ( 
    id int(10) NOT NULL, 
    current_max_id bigint(20) NOT NULL COMMENT '当前最大id', 
    increment_step int(10) NOT NULL COMMENT '号段的长度', 
    PRIMARY KEY (`id`) 
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

这个数据库表用来记录自增步长以及当前自增ID的最大值（也就是当前已经被申请的号段的最后一个值），因为自增逻辑被移到DistributIdService中去了，所以数据库不需要这部分逻辑了。

这种方案不再强依赖数据库，就算数据库不可用，那么DistributIdService也能继续支撑一段时间。但是如果DistributIdService重启，会丢失一段ID，导致ID空洞。

为了提高DistributIdService的高可用，需要做一个集群，业务在请求DistributIdService集群获取ID时，会随机的选择某一个DistributIdService节点进行获取，对每一个DistributIdService节点来说，数据库连接的是同一个数据库，那么可能会产生多个
DistributIdService节点同时请求数据库获取号段，那么这个时候需要利用乐观锁来进行控制，比如在数据库表中增加一个version字段，在获取号段时使用如下SQL：

UPDATE id_generator
SET current_max_id = #{newMaxId},
version=version+1 
where version = #{version} 

因为newMaxId是DistributIdService中根据oldMaxId+步长算出来的，只要上面的update更新成功了就表示号段获取成功了。

为了提供数据库层的高可用，需要对数据库使用多主模式进行部署，对于每个数据库来说要保证生成的号段不重复，这就需要利用最开始的思路，再在刚刚的数据库表中增加起始值和步长，比如如果现在是两台Mysql，那么 mysql1将生成号段（1,1001]，自增的时候序列为1，3，5，7… mysql2将生成号段（2,1002]，自增的时候序列为2，4，6，8，10…

在TinyId中还增加了一步来提高效率，在上面的实现中，ID自增的逻辑是在DistributIdService中实现的，而实际上可以把自增的逻辑转移到业务应用本地，这样对于业务应用来说只需要获取号段，每次自增时不再需要请求调用DistributIdService了。

1.5 雪花算法（snowflake）

上面的三种方法总的来说是基于自增思想的，而接下来就介绍比较著名的雪花算法-snowflake
我们可以换个角度来对分布式ID进行思考，只要能让负责生成分布式ID的每台机器在每毫秒内生成不一样的ID就行了。

snowflake是twitter开源的分布式ID生成算法，是一种算法，所以它和上面的三种生成分布式ID机制不太一样，它不依赖数据库。

核心思想是：分布式ID固定是一个long型的数字，一个long型占8个字节，也就是64个bit，原始snowflake算法中对于bit的分配如下图：

• 符号位为0，0表示正数，ID为正数,所以固定为0。
• 时间戳位不用多说，用来存放时间戳，单位是ms,时间戳部分占41bit，这个是毫秒级的时间，一般实现上不会存储当前的时间戳，而是时间戳的差值（当前时间-固定的开始时间）,这样可以使产生的ID从更小值开始。
• 工作机器id位用来存放机器的id，通常分为5个区域位+5个服务器标识位。这里比较灵活，比如，可以使用前5位作为数据中心机房标识，后5位作为单机房机器标识，可以部署1024个节点。
• 序号位是自增。

雪花算法能存放多少数据？

• 时间范围：2^41 / (1000L * 60 * 60 * 24 * 365) = 69年
• 工作进程范围：2^10 = 1024
• 序列号范围：2^12 = 4096，表示1ms可以生成4096个ID。

根据这个算法的逻辑，只需要将这个算法用Java语言实现出来，封装为一个工具方法，那么各个业务应用可以直接使用该工具方法来获取分布式ID，只需保证每个业务应用有自己的工作机器id即可，而不需要单独去搭建一个获取分布式ID的应用。下面是推特版的Snowflake算法：

public class SnowFlake {

    /**
     * 起始的时间戳
     */
    private final static long START_STMP = 1480166465631L;

    /**
     * 每一部分占用的位数
     */
    private final static long SEQUENCE_BIT = 12; //序列号占用的位数
    private final static long MACHINE_BIT = 5;   //机器标识占用的位数
    private final static long DATACENTER_BIT = 5;//数据中心占用的位数

    /**
     * 每一部分的最大值
     */
    private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);

    /**
     * 每一部分向左的位移
     */
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;

    private long datacenterId;  //数据中心
    private long machineId;     //机器标识
    private long sequence = 0L; //序列号
    private long lastStmp = -1L;//上一次时间戳

    public SnowFlake(long datacenterId, long machineId) {
        if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
            throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
        }
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0");
        }
        this.datacenterId = datacenterId;
        this.machineId = machineId;
    }

    /**
     * 产生下一个ID
     *
     * @return
     */
    public synchronized long nextId() {
        long currStmp = getNewstmp();
        if (currStmp < lastStmp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }

        if (currStmp == lastStmp) {
            //相同毫秒内，序列号自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //同一毫秒的序列数已经达到最大
            if (sequence == 0L) {
                currStmp = getNextMill();
            }
        } else {
            //不同毫秒内，序列号置为0
            sequence = 0L;
        }

        lastStmp = currStmp;

        return (currStmp - START_STMP) << TIMESTMP_LEFT //时间戳部分
                | datacenterId << DATACENTER_LEFT       //数据中心部分
                | machineId << MACHINE_LEFT             //机器标识部分
                | sequence;                             //序列号部分
    }

    private long getNextMill() {
        long mill = getNewstmp();
        while (mill <= lastStmp) {
            mill = getNewstmp();
        }
        return mill;
    }

    private long getNewstmp() {
        return System.currentTimeMillis();
    }

    public static void main(String[] args) {
        SnowFlake snowFlake = new SnowFlake(2, 3);

        for (int i = 0; i < (1 << 12); i++) {
            System.out.println(snowFlake.nextId());
        }

    }
}

在实际的线上使用场景里，其实很少有直接使用snowflake，而是进行了改造，因为snowflake算法中最难实践的就是工作机器id，原始的snowflake算法需要人工去为每台机器去指定一个机器id，并配置在某个地方从而让snowflake从此处获取机器id。
尤其是机器是很多的时候，人力成本太大且容易出错，所以目前很多大厂对snowflake进行了改造。
下面我们一起看看别人都是怎么去做的

1.5.1 百度（uid-generator）

uid-generator使用的就是snowflake，只是在生产机器id，也叫做workId时有所不同。

uid-generator中的workId是由uid-generator自动生成的，并且考虑到了应用部署在docker上的情况，在uid-generator中用户可以自己去定义workId的生成策略，默认提供的策略是：应用启动时由数据库分配。

说的简单一点就是：应用在启动时会往数据库表(uid-generator需要新增一个WORKER_NODE表)中去插入一条数据，数据插入成功后返回的该数据对应的自增唯一id就是该机器的workId，而数据由host，port组成。

对于uid-generator中的workId，占用了22个bit位，时间占用了28个bit位，序列化占用了13个bit位，需要注意的是，和原始的snowflake不太一样，时间的单位是秒，而不是毫秒，workId也不一样，同一个应用每重启一次就会消费一个workId。

1.5.2 美团（Leaf）

美团的Leaf也是一个分布式ID生成框架。它非常全面，即支持号段模式，也支持snowflake模式。名字取自德国哲学家、数学家莱布尼茨的一句话：“There are no two identical leaves in the world.”Leaf具备高可靠、低延迟、全局唯一等特点。目前已经广泛应用于美团金融、美团外卖、美团酒旅等多个部门。
Leaf中的snowflake模式和原始snowflake算法的不同点，也主要在workId的生成，Leaf中workId是基于ZooKeeper的顺序Id来生成的，每个应用在使用Leaf-snowflake时，在启动时都会都在Zookeeper中生成一个顺序Id，相当于一台机器对应一个顺序节点，也就是一个workId。
Leaf特性如下：

• 全局唯一，绝对不会出现重复的ID，且ID整体趋势递增。
• 高可用，服务完全基于分布式架构，即使MySQL宕机，也能容忍一段时间的数据库不可用。
• 高并发低延时，在CentOS 4C8G的虚拟机上，远程调用QPS可达5W+，TP99在1ms内。
• 接入简单，直接通过公司RPC服务或者HTTP调用即可接入。

更详细的《美团Leaf介绍》点击此处查看
美团Leaf怎么使用呢，有兴趣的可以看看我的另一篇博文：《美团Leaf实战》

先自我介绍一下，小编13年上师交大毕业，曾经在小公司待过，去过华为OPPO等大厂，18年进入阿里，直到现在。深知大多数初中级java工程师，想要升技能，往往是需要自己摸索成长或是报班学习，但对于培训机构动则近万元的学费，着实压力不小。自己不成体系的自学效率很低又漫长，而且容易碰到天花板技术停止不前。因此我收集了一份《java开发全套学习资料》送给大家，初衷也很简单，就是希望帮助到想自学又不知道该从何学起的朋友，同时减轻大家的负担。添加下方名片，即可获取全套学习资料哦