关于分布式:讲分布式唯一id这篇文章很实在

28次阅读

共计 8830 个字符,预计需要花费 23 分钟才能阅读完成。

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

又比方,革新无序性,比方 NHibernateComb 算法,把 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:

对立步长:3
V1 起始值:1
V2 起始值:2
V3 起始值: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,每台步长 3000
V1:1-1000,3001-4000,
V2:1001-2000,4001-5000
V3: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 1
OK
127.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 源码解析JDBCMybatisSpringredis 分布式 剑指 OfferLeetCode等,认真写好每一篇文章,不喜爱题目党,不喜爱花里胡哨,大多写系列文章,不能保障我写的都完全正确,然而我保障所写的均通过实际或者查找材料。脱漏或者谬误之处,还望斧正。

剑指 Offer 全副题解 PDF

2020 年我写了什么?

开源编程笔记

正文完
 0