为什么需要分布式全局唯一ID以及分布式ID的业务需求

在复杂分布式系统中,往往需要对大量的数据和消息进行唯一标识。

如在美团点评的金融、支付、餐饮、酒店

猫眼电影等产品的系统中数据日渐增长,对数据分库分表后需要有一个唯一D来标识一条数据或消息;

特别一点的如订单、骑手、优惠券也都需要有唯一ID做标识。

此时一个能够生成全局唯一ID的系统是非常必要的。

ID生成规则部分硬性要求

  1. 全局唯一

    不能出现重复的ID号，既然是唯一标识，这是最基本的要求

  2. 趋势递增

    在MySQL的InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用Btree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能

  3. 单调递增

    保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求

  4. 信息安全

    如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，需要ID无规则不规则，让竞争对手不好猜

  5. 含时间戳

    这样就能够在开发中快速了解这个分布式id的生成时间

ID号生成系统的可用性要求

  1. 高可用

    发一个获取分布式ID的请求，服务器就要保证99.999%的情况下给我创建一个唯一分布式ID

  2. 低延迟

    发一个获取分布式ID的请求，服务器就要快，极速

  3. 高QPS

    假如并发一口气10万个创建分布式ID请求同时杀过来，服务器要顶的住且一下子成功创建10万个分布式ID

一般通用方案

UUID

❌ 只满足全局唯一，其余要求都不满足。

UUID.randomUUID().toString()

UUID（Universally Unique ldentifier）的标准型式包含32个16进制数字，以连字号分为五段，形式为8-4-4-4-12的36个字符， 示例:550e8400-e29b-41d4-a716-446655440000

性能非常高:本地生成，没有网络消耗

如果只考虑唯一性是完全够用的，但是它入数据库性能比较差，具体如下：

  1. 无序，无法预测他的生成顺序，不能生成递增有序的数字。

    首先分布式id一般都会作为主键，但是安装mysql官方推荐主键要尽量越短越好，UUID每一个都很长，所以不是很推荐。

  2. 主键，ID作为主键时在特定的环境会存在一些问题。

    比如做DB主键的场景下，UUID就非常不适用MySQL官方有明确的建议主键要尽量越短越好36个字符长度的UUID不符合要求

  3. 索引，B+ 树索引的分裂

    既然分布式id是主键，然后主键是包含索引的，然后mysql的索引是通过b+树来实现的，每一次新的UUID数据的插入，为了查询的优化，都会对索引底层的b+树进行修改，因为UUID数据是无序的，所以每一次UUID数据的插入都会对主键地域的b+树进行很大的修改，这一点很不好。 插入完全无序，不但会导致一些中间节点产生分裂，也会白白创造出很多不饱和的节点，这样大大降低了数据库插入的性能。

数据库自增主键

单机情况下

❌ 只满足唯一性和趋势递增，适用于并发量不高的情况下。

在分布式里面,数据库的自增ID机制的主要原理是:数据库自增ID和 mysql 数据库的 replace into实现的。

  • 这里的 replace intoinsert跟功能类似。
  • 不同点在于: replace into首先尝试插入数据列表中,如果发现表中已经有此行数据(根据主键或唯一索引判断)则先删除,再插入。否则直接插入新数据。
  • REPLACE INTO的含义是插入一条记录如果表中唯一索引的值遇到冲突,则替换老数据。
CREATE TABLE t_test(
	id BIGINT(20) UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
  stub CHAR(1) NOT NULL DEFAULT '',
  UNIQUE KEY stub (stub) -- 在stub字段上创建唯一性索引，索引名为stub
)
SELECT * FROM t_test;

REPLACE INTO t_test (stub) VALUES('b');
SELECT LAST_INSERT_ID(); --得到刚 insert 进去记录的主键值，只适用与自增主键

集群分布式

那数据库自增ID机制适合作分布式ID吗? 答案是不太适合 ❌

  1. 系统水平扩展比较困难，比如定义好了步长和机器台数之后，如果要添加机器该怎么做？假设现在只有一台机器发号是1，2，3，4，5 步长是1），这个时候需要扩容机器一台。 可以这样做；把第二台机器的初始值设置得比第一台超过很多， 貌似还好，现在想象一下如果我们线上有100台机器，这个时候要扩容该怎么做？简直是噩梦。所以系统水平扩展方案复杂难以实现。
  2. 数据库压力还是很大，每次获取ID都得读写一次数据库， 非常影响性能，不符合分布式ID里面的延迟低和要高QPS的规则（在高并发下，如果都去数据库里面获取id，那是非常影响性能的）

基于Redis生成全局id策略

可落地，但是配置维护起来麻烦。

因为Redis是单线的天生保证原子性，可以使用原子操作INCR和INCRBY来实现

在Redis集群情况下，同样和MySQL一样需要设置不同的增长步长，同时key一定要设置有效期可以使用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

雪花算法 snowflake

概述

最初Twitter把存储系统从MySQL迁移到Cassandra（由Facebook开发一套开源分布式NoSQL数据库系统）因为Cassandra没有顺序ID生成机制，所以开发了这样一套全局唯一ID生成服务。

Twiter的分布式雪花算法SnowFlake，经测试snowflake每秒能够产生26万个自增可排序的ID

  1. twitter的SnowFlake 生成ID能够按照时间有序生成
  2. SnowFlake 算法生成id的结果是一个64bit大小的整数，为一个Long 型（转换成字符串后长度最多19）
  3. 分布式系统内不会产生ID碰撞（由datacenter和workerld作区分）并且效率较高。

分布式系统中，有一些需要使用全局唯一ID的场景， 生成ID的基本要求

  1. 在分布式的环境下必须全局且唯一 。

  2. 一般都需要单调递增，因为一般唯一 ID都会存到数据库，而Innodb的特性就是将内容存储在主键索引树上的叶子节点，而且是从左往右，递增的，所以考虑到数据库性能， 一般生成的id也最好是单调递增。为了防止ID冲突可以使用36位的UUID，但是UUID有一些缺点，首先他相对比较长，另外UUID般是无序的。

  3. 可能还会需要无规则，因为如果使用唯一ID作为订 单号这种，为了不然别人知道一天的订单量是多少，就需要这个规则。

核心组成部分

image-20201201202502598

号段解析：

  • 1 bit符号位：不用，因为二进制中最高位是符号位，1表示负数，0表示正数。生成的id一般都是用整数，所以最高位固定为0。
  • 41bit时间戳位：表示可使用的时间范围，毫秒级别。
  • 10bit工作进程位：工作机器id，用来记录工作机器id，可以部署在2^10=1024个节点，包括5位datacenterId（机房id）和workerId。5位bit可以表示最大的正整数是31，可以用0、1、2…31这32个数字来表示不同的datacenterId和woekerId。
  • 12bit序列号：序列号,用来记录同毫秒内产生的不同id。表示同一机器同一时间戳（毫秒）内产生的4095个ID序号。

小结

SnowFlake可以保证:

所有生成的id按时间趋势递增

整个分布式系统内不会产生重复id （因为有datacenterld和workerld来做区分）

工程落地经验

糊涂工具包

springboot整合雪花算法

1.POM:

<dependency>
    <groupId>cn.hutool</groupId>
    <artifactId>hutool-captcha</artifactId>
    <version>5.5.1</version>
</dependency>

2.核心代码IdGeneratorSnowflake

@Component
@Slf4j
public class IdGeneratorSnowflake {

    private long workerId = 0;
    private long datacenterId = 1;
    private Snowflake snowflake = IdUtil.createSnowflake(workerId, datacenterId);

    /**
     * @description: Java中该注解的说明：@PostConstruct该注解被用来修饰一个非静态的void（）方法。
     * 被@PostConstruct修饰的方法会在服务器加载Servlet的时候运行，并且只会被服务器执行一次。
     * <p>
     * 该注解的方法在整个Bean初始化中的执行顺序:
     * Constructor(构造方法) -> @Autowired(依赖注入) -> @PostConstruct(注释的方法)
     */
    @PostConstruct
    public void init() {
        try {
            workerId = NetUtil.ipv4ToLong(NetUtil.getLocalhostStr()); // 获取主机id
            log.info("当前机器的workerId: {}", workerId);
        } catch (Exception e) {
            e.printStackTrace();
            log.warn("当前机器的workerId 获取失败", e);
            workerId = NetUtil.getLocalhostStr().hashCode(); // 不能让这个串是空的
        }
    }

    public synchronized long snowflakeID() {
        return snowflake.nextId();
    }

    public synchronized long snowflakeID(long workerId, long datacenterId) {
        Snowflake snowflake = IdUtil.createSnowflake(workerId, datacenterId);
        return this.snowflake.nextId();
    }

}

优缺点

优点:

  • 毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。
  • 不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的。
  • 可以根据自身业务特性分配bit位，非常灵活。

缺点:

  • 依赖机器时钟，如果机器时钟回拨，会导致重复ID生成
  • 在单机上是递增的，但是由于设计到分布式环境，每台机器上的时钟不可能完全同步，有时候会出现不是全局递增的情况（此缺点可以认为无所谓，一般分布式ID只要求趋势递增，并不会严格要求递增，90%的需求都只要求趋势递增）

其他补充

解决了时钟同步的缺陷：

  • 百度开源的分布式唯一ID生成器UidGenerator

  • 美团点评分布式ID生成系统Leaf