分布式惟一ID介绍

分布式系统全局惟一的 id 是所有零碎都会遇到的场景，往往会被用在搜寻，存储方面，用于作为惟一的标识或者排序，比方全局惟一的订单号，优惠券的券码等，如果呈现两个雷同的订单号，对于用户无疑将是一个微小的bug。

在单体的零碎中，生成惟一的 id 没有什么挑战，因为只有一台机器一个利用，间接应用单例加上一个原子操作自增即可。而在分布式系统中，不同的利用，不同的机房，不同的机器，要想生成的 ID 都是惟一的，的确须要下点功夫。

一句话总结：

分布式惟一ID是为了给数据进行惟一标识。

分布式惟一ID的特色

分布式惟一ID的外围是唯一性，其余的都是附加属性，一般来说，一个优良的全局惟一ID计划有以下的特点，仅供参考：

  • 全局惟一：不能够反复，外围特点！
  • 大抵有序或者枯燥递增：自增的个性有利于搜寻，排序，或者范畴查问等
  • 高性能：生成ID响应要快，提早低
  • 高可用：要是只能单机，挂了，全公司依赖全局惟一ID的服务，全副都不可用了，所以生成ID的服务必须高可用
  • 方便使用：对接入者敌对，能封装到开箱即用最好
  • 信息安全：有些场景，如果间断，那么很容易被猜到，攻打也是有可能的，这得取舍。

分布式惟一ID的生成计划

UUID间接生成

写过 Java 的敌人都晓得，有时候咱们写日志会用到一个类 UUID，会生成一个随机的ID，去作为以后用户申请记录的惟一识别码,只有用以下的代码：

String uuid = UUID.randomUUID();

用法简略粗犷，UUID的全称其实是Universally Unique IDentifier,或者GUID(Globally Unique IDentifier),它实质上是一个 128 位的二进制整数，通常咱们会示意成为 32 个 16 进制数组成的字符串，简直不会反复，2 的 128 次方，那是无比宏大的数字。

以下是百度百科阐明：

UUID由以下几局部的组合：

（1）UUID的第一个局部与工夫无关，如果你在生成一个UUID之后，过几秒又生成一个UUID，则第一个局部不同，其余雷同。

（2）时钟序列。

（3）全局惟一的IEEE机器辨认号，如果有网卡，从网卡MAC地址取得，没有网卡以其余形式取得。

UUID的惟一缺点在于生成的后果串会比拟长。对于UUID这个规范应用最广泛的是微软的GUID(Globals Unique Identifiers)。在ColdFusion中能够用CreateUUID()函数很简略地生成UUID，其格局为：xxxxxxxx-xxxx- xxxx-xxxxxxxxxxxxxxxx(8-4-4-16)，其中每个 x 是 0-9 或 a-f 范畴内的一个十六进制的数字。而规范的UUID格局为：xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx (8-4-4-4-12)，能够从cflib 下载CreateGUID() UDF进行转换。 [2]

（4）在 hibernate（Java orm框架）中， 采纳 IP-JVM启动工夫-以后工夫右移32位-以后工夫-外部计数（8-8-4-8-4）来组成UUID

要想反复，两台完全相同的虚拟机，开机工夫统一，随机种子统一，同一时间生成uuid，才有极小的概率会反复，因而咱们可认为，实践上会反复，理论不可能反复！！！

uuid长处：

  • 性能好，效率高
  • 不必网络申请，间接本地生成
  • 不同的机器个干个的，不会反复

uuid 这么好，难不成是银弹？当然毛病也很突出：

  • 没方法保障递增趋势，没法排序
  • uuid太长了，存储占用空间大，特地落在数据库，对建设索引不敌对
  • 没有业务属性，这货色就是一串数字，没啥意义，或者说法则

当然也有人想要改良这家伙，比方不可读性革新，用uuid to int64，把它转成 long 类型：

byte[] bytes = Guid.NewGuid().ToByteArray();return BitConverter.ToInt64(bytes, 0);

又比方，革新无序性，比方 NHibernate 的 Comb 算法，把 uuid 的前 20 个字符保留下来，前面 12 个字符用 guid 生成的工夫,工夫是大抵有序的，是一种小改良。

点评：UUID不存在数据库当索引，作为一些日志，上下文的辨认，还是挺香的，然而要是这玩意用来当订单号，真是令人解体

数据库自增序列

单机的数据库

数据库的主键自身就领有一个自增的人造个性，只有设置ID为主键并且自增，咱们就能够向数据库中插入一条记录，能够返回自增的ID，比方以下的建表语句：

CREATE DATABASE `test`;use test;CREATE TABLE id_table (    id bigint(20) unsigned NOT NULL auto_increment,     value char(10) NOT NULL default '',    PRIMARY KEY (id),) ENGINE=MyISAM;

插入语句：

insert into id_table(value)  VALUES ('v1');

长处：

  • 单机，简略，速度也很快
  • 人造自增，原子性
  • 数字id排序，搜寻，分页都比拟无利

毛病也很显著：

  • 单机，挂了就要提桶跑路了
  • 一台机器，高并发也不可能

集群的数据库

既然单机高并发和高可用搞不定，那就加机器，搞集群模式的数据库，既然集群模式，如果有多个master，那必定不能每台机器本人生成本人的id，这样会导致反复的id。

这个时候，每台机器设置起始值和步长，就尤为重要。比方三台机器V1，V2，V3：

对立步长：3V1起始值：1V2起始值：2V3起始值：3

生成的ID：

V1：1, 4, 7, 10...V2：2, 5, 8, 11...V3：3, 6, 9, 12...

设置命令行能够应用：

set @@auto_increment_offset = 1;     // 起始值set @@auto_increment_increment = 3;  // 步长

这样的确在master足够多的状况下，高性能保障了，就算有的机器宕机了，slave 也能够补充上来，基于主从复制就能够，能够大大降低对单台机器的压力。然而这样做还是有毛病：

  • 主从复制提早了，master宕机了，从节点切换成为主节点之后，可能会反复发号。
  • 起始值和步长设置好之后，要是前面须要减少机器（程度拓展），要调整很麻烦，很多时候可能须要停机更新

批量号段式数据库

下面的拜访数据库太频繁了，并发量一上来，很多小概率问题都可能产生，那为什么咱们不间接一次性拿出一段id呢？间接放在内存里，以供应用，用完了再申请一段就能够了。同样也能够保留集群模式的长处，每次从数据库取出一个范畴的id，比方3台机器，发号：

每次取1000，每台步长3000V1：1-1000,3001-4000,V2：1001-2000,4001-5000V3：2001-3000,5001-6000

当然，如果不搞多台机器，也是能够的，一次申请10000个号码，用乐观锁实现，加一个版本号，

CREATE TABLE id_table (  id int(10) NOT NULL,  max_id bigint(20) NOT NULL COMMENT '以后最大id',  step int(20) NOT NULL COMMENT '号段的步长',  version int(20) NOT NULL COMMENT '版本号',  `create_time` datetime DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP,  `update_time` datetime DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP,  PRIMARY KEY (`id`))

只有用完的时候，才会从新去数据库申请，竞争的时候乐观锁保障只能一个申请胜利，其余的间接等着他人取出来放在利用内存外面，再取就能够了，取的时候其实就是一个update操作：

update id_table set max_id = #{max_id+step}, version = version + 1 where version = # {version}

重点：

  • 批量获取，缩小数据库申请
  • 乐观锁，保证数据精确
  • 获取只能从数据库中获取，批量获取能够做成异步定时工作，发现少于某个阈值，主动补充

Redis自增

redis有一个原子命令incr,原子自增，redis速度快，基于内存：

127.0.0.1:6379> set id 1OK127.0.0.1:6379> incr id      (integer) 2

当然，redis 如果单机有问题，也能够上集群，同样能够用初始值 + 步长，能够用 INCRBY 命令，搞几台机器根本能抗住高并发。

长处：

  • 基于内存，速度快
  • 人造排序，自增，有利于排序搜寻

毛病：

  • 步长确定之后，减少机器也比拟难调整

  • 须要关注长久化，可用性等，减少零碎复杂度

    redis长久化如果是RDB，一段时间打一个快照，那么可能会有数据没来得及被长久化到磁盘，就挂掉了，重启可能会呈现反复的ID，同时要是主从提早，主节点挂掉了，主从切换，也可能呈现反复的ID。如果应用AOF，一条命令长久化一次，可能会拖慢速度，一秒钟长久化一次，那么就可能最多失落一秒钟的数据，同时，数据恢复也会比较慢，这是一个取舍的过程。

Zookeeper生成惟一ID

zookeeper其实是能够用来生成惟一ID的，然而大家不必，因为性能不高。znode有数据版本，能够生成32或者64位的序列号，这个序列号是惟一的，然而如果竞争比拟大，还须要加分布式锁，不值得，效率低。

美团的Leaf

上面均来自美团的官网文档：https://tech.meituan.com/2019...

Leaf在设计之初就秉承着几点要求：

  1. 全局惟一，相对不会呈现反复的ID，且ID整体趋势递增。
  2. 高可用，服务齐全基于分布式架构，即便MySQL宕机，也能容忍一段时间的数据库不可用。
  3. 高并发低延时，在CentOS 4C8G的虚拟机上，近程调用QPS可达5W+，TP99在1ms内。
  4. 接入简略，间接通过公司RPC服务或者HTTP调用即可接入。

文档外面讲得很清晰，一共有两个版本：

  • V1：预散发的形式提供ID，也就是后面说的号段式散发，表设计也差不多，意思就是批量的拉取id

这样做的毛病就是更新号段的时候，耗时比拟高，还有就是如果这时候宕机或者主从复制，就不可用。

优化：

  • 1.先做了一个双Buffer优化，就是异步更新，意思就是搞两个号段进去，一个号段比方被耗费10%的时候，就开始调配下一个号段，有种提前调配的意思，而且异步线程更新
  • 2.下面的计划，号段可能固定，跨度可能太大或者太小，那就做成动态变化，依据流量来决定下一次的号段的大小，动静调整
  • V2：Leaf-snowflake，Leaf提供了Java版本的实现，同时对Zookeeper生成机器号做了弱依赖解决，即便Zookeeper有问题，也不会影响服务。Leaf在第一次从Zookeeper拿取workerID后，会在本机文件系统上缓存一个workerID文件。即便ZooKeeper呈现问题，同时恰好机器也在重启，也能保障服务的失常运行。这样做到了对第三方组件的弱依赖，肯定水平上进步了SLA。

snowflake(雪花算法）

snowflake 是 twitter 公司外部分布式我的项目采纳的 ID 生成算法,开源后广受欢迎，它生成的ID是 Long 类型，8个字节，一共64位，从左到右：

  • 1位：不应用，二进制中最高位是为1都是正数，然而要生成的惟一ID都是正整数，所以这个1位固定为0。
  • 41位：记录时间戳(毫秒)，这个位数能够用 $(2^{41}-1) / (1000 * 60 * 60 * 24 * 365) = 69$年
  • 10位：记录工作机器的ID，能够机器ID，也能够机房ID + 机器ID
  • 12位：序列号，就是某个机房某台机器上这一毫秒内同时生成的 id 序号

那么每台机器依照下面的逻辑去生成ID，就会是趋势递增的，因为工夫在递增，而且不须要搞个分布式的，简略很多。

能够看出 snowflake 是强依赖于工夫的，因为工夫实践上是一直往前的，所以这一部分的位数，也是趋势递增的。然而有一个问题，是工夫回拨，也就是工夫忽然间倒退了，可能是故障，也可能是重启之后工夫获取出问题了。那咱们该如何解决工夫回拨问题呢？

  • 第一种计划：获取工夫的时候判断，如果小于上一次的工夫戳，那么就不要调配，持续循环获取工夫，直到工夫符合条件。
  • 第二种计划：下面的计划只适宜时钟回拨较小的，如果距离过大，阻塞期待，必定是不可取的，因而要么超过肯定大小的回拨间接报错，拒绝服务，或者有一种计划是利用拓展位，回拨之后在拓展位上加1就能够了，这样ID仍然能够放弃惟一。

Java代码实现：

public class SnowFlake {    // 数据中心(机房) id    private long datacenterId;    // 机器ID    private long workerId;    // 同一时间的序列    private long sequence;    public SnowFlake(long workerId, long datacenterId) {        this(workerId, datacenterId, 0);    }    public SnowFlake(long workerId, long datacenterId, long sequence) {        // 非法判断        if (workerId > maxWorkerId || workerId < 0) {            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));        }        if (datacenterId > maxDatacenterId || datacenterId < 0) {            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));        }        System.out.printf("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",                timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);        this.workerId = workerId;        this.datacenterId = datacenterId;        this.sequence = sequence;    }    // 开始工夫戳    private long twepoch = 1420041600000L;    // 机房号，的ID所占的位数 5个bit 最大:11111(2进制)--> 31(10进制)    private long datacenterIdBits = 5L;    // 机器ID所占的位数 5个bit 最大:11111(2进制)--> 31(10进制)    private long workerIdBits = 5L;    // 5 bit最多只能有31个数字，就是说机器id最多只能是32以内    private long maxWorkerId = -1L ^ (-1L << workerIdBits);    // 5 bit最多只能有31个数字，机房id最多只能是32以内    private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);    // 同一时间的序列所占的位数 12个bit 111111111111 = 4095  最多就是同一毫秒生成4096个    private long sequenceBits = 12L;    // workerId的偏移量    private long workerIdShift = sequenceBits;    // datacenterId的偏移量    private long datacenterIdShift = sequenceBits + workerIdBits;    // timestampLeft的偏移量    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;    // 序列号掩码 4095 (0b111111111111=0xfff=4095)    // 用于序号的与运算，保障序号最大值在0-4095之间    private long sequenceMask = -1L ^ (-1L << sequenceBits);    // 最近一次工夫戳    private long lastTimestamp = -1L;    // 获取机器ID    public long getWorkerId() {        return workerId;    }    // 获取机房ID    public long getDatacenterId() {        return datacenterId;    }    // 获取最新一次获取的工夫戳    public long getLastTimestamp() {        return lastTimestamp;    }    // 获取下一个随机的ID    public synchronized long nextId() {        // 获取以后工夫戳，单位毫秒        long timestamp = timeGen();        if (timestamp < lastTimestamp) {            System.err.printf("clock is moving backwards.  Rejecting requests until %d.", lastTimestamp);            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds",                    lastTimestamp - timestamp));        }        // 去重        if (lastTimestamp == timestamp) {            sequence = (sequence + 1) & sequenceMask;            // sequence序列大于4095            if (sequence == 0) {                // 调用到下一个工夫戳的办法                timestamp = tilNextMillis(lastTimestamp);            }        } else {            // 如果是以后工夫的第一次获取，那么就置为0            sequence = 0;        }        // 记录上一次的工夫戳        lastTimestamp = timestamp;        // 偏移计算        return ((timestamp - twepoch) << timestampLeftShift) |                (datacenterId << datacenterIdShift) |                (workerId << workerIdShift) |                sequence;    }    private long tilNextMillis(long lastTimestamp) {        // 获取最新工夫戳        long timestamp = timeGen();        // 如果发现最新的工夫戳小于或者等于序列号曾经超4095的那个工夫戳        while (timestamp <= lastTimestamp) {            // 不合乎则持续            timestamp = timeGen();        }        return timestamp;    }    private long timeGen() {        return System.currentTimeMillis();    }    public static void main(String[] args) {        SnowFlake worker = new SnowFlake(1, 1);        long timer = System.currentTimeMillis();        for (int i = 0; i < 100; i++) {            worker.nextId();        }        System.out.println(System.currentTimeMillis());        System.out.println(System.currentTimeMillis() - timer);    }}

百度 uid-generator

换汤不换药，百度开发的，基于Snowflake算法，不同的中央是能够本人定义每局部的位数,也做了不少优化和拓展：https://github.com/baidu/uid-...

UidGenerator是Java实现的, 基于Snowflake算法的惟一ID生成器。UidGenerator以组件模式工作在利用我的项目中, 反对自定义workerId位数和初始化策略, 从而实用于docker等虚拟化环境下实例主动重启、漂移等场景。 在实现上, UidGenerator通过借用将来工夫来解决sequence人造存在的并发限度; 采纳RingBuffer来缓存已生成的UID, 并行化UID的生产和生产, 同时对CacheLine补齐，防止了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。

秦怀の观点

不论哪一种uid生成器，保障唯一性是外围，在这个外围上能力去思考其余的性能，或者高可用等问题，总体的计划分为两种：

  • 中心化：第三方的一个核心，比方 Mysql，Redis，Zookeeper

    • 长处：趋势自增
    • 毛病：减少复杂度，个别得集群，提前约定步长之类

  • 无中心化：间接本地机器上生成，snowflake，uuid

    • 长处：简略，高效，没有性能瓶颈
    • 毛病：数据比拟长，自增属性较弱

没有哪一种是完满的，只有合乎业务以及以后体量的计划，技术计划外面，没有最优解。

【作者简介】：
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使迟缓，驰而不息。集体写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜爱题目党，不喜爱花里胡哨，大多写系列文章，不能保障我写的都完全正确，然而我保障所写的均通过实际或者查找材料。脱漏或者谬误之处，还望斧正。

剑指Offer全副题解PDF

2020年我写了什么？

开源编程笔记