分布式ID生成方式与SnowFlake算法

文章目录 隐藏
1 分布式ID生成特性
2 分布式ID生成方式
2.1 雪花算法（SnowFlake）
2.1.1 生成方式
2.1.2 拓展
2.2 UUID
2.3 数据库自增ID
2.4 数据库多主模式
2.5 号段模式
2.6 Redis
2.7 开源项目

分布式ID生成特性

  1. 全局唯一
    必须保证ID是全局性唯一

  2. 高可用低延时
    ID生成响应要快，能够扛住高并发，延时足够低不至于成为业务瓶颈

  3. 数字类型趋势递增
    从MySQL存储引擎考虑，后面的ID必须必前面的大，并需要保证写入数据的性能

  4. 长度短
    能够提高查询效率，从MySQL数据库规范考虑，尤其是ID作为主键

  5. 信息安全
    如果ID连续生成，会导致被猜出从而泄漏业务信息，所以需要无规则

分布式ID生成方式

雪花算法（SnowFlake）

分布式id生成算法的有很多种，Twitter的SnowFlake就是其中经典的一种。
SnowFlake算法生成id的结果是一个64bit大小的整数，它的结构如下图：

  1. 1bit，不用，因为二进制中最高位是符号位，1表示负数，0表示正数。生成的id一般都是用整数，所以最高位固定为0。

  2. 41位，用来记录时间戳（毫秒）。

    • 41位可以表示个241-1数字。
    • 如果只用来表示正整数（计算机中正数包含0），可以表示的数值范围是：0 至241-1 ，减1是因为可表示的数值范围是从0开始算的，而不是1
    • 也就是说41位可以表示241-1个毫秒的值，转化成单位年则是$(2^{41}-1)/(1000\ast60\ast60\ast24\ast365)=69$年。

  3. 10位，用来记录工作机器id。

    • 可以部署在$2^{10}-1$个节点，包括5位datacenterId和5位workerId
    • 5位（bit）可以表示的最大正整数是$2^5-1=31$，即可以用0、1、2、3、….31这32个数字，来表示不同的datecenterId或workerId

  4. 12位，序列号，用来记录同毫秒内产生的不同id。

    • 12位（bit）可以表示的最大正整数是$2^{12}-1=4095$，即可以用0、1、2、3、….4094这4095个数字，来表示同一机器同一时间截（毫秒)内产生的4095个ID序号

由于在Java中64bit的整数是long类型，所以在Java中SnowFlake算法生成的id就是long来存储的。
SnowFlake可以保证：

  • 所有生成的id按时间趋势递增
  • 整个分布式系统内不会产生重复id（因为有datacenterId和workerId来做区分）

生成方式

Twitter官方原版

  • java实现
public class SnowflakeIdWorker {
    // ==============================Fields===========================================
    /**
     * 开始时间截 (2015-01-01)
     */
    private final long twepoch = 1489111610226L;

    /**
     * 机器id所占的位数
     */
    private final long workerIdBits = 5L;

    /**
     * 数据标识id所占的位数
     */
    private final long dataCenterIdBits = 5L;

    /**
     * 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数)
     */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /**
     * 支持的最大数据标识id，结果是31
     */
    private final long maxDataCenterId = -1L ^ (-1L << dataCenterIdBits);

    /**
     * 序列在id中占的位数
     */
    private final long sequenceBits = 12L;

    /**
     * 机器ID向左移12位
     */
    private final long workerIdShift = sequenceBits;

    /**
     * 数据标识id向左移17位(12+5)
     */
    private final long dataCenterIdShift = sequenceBits + workerIdBits;

    /**
     * 时间截向左移22位(5+5+12)
     */
    private final long timestampLeftShift = sequenceBits + workerIdBits + dataCenterIdBits;

    /**
     * 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095)
     */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /**
     * 工作机器ID(0~31)
     */
    private long workerId;

    /**
     * 数据中心ID(0~31)
     */
    private long dataCenterId;

    /**
     * 毫秒内序列(0~4095)
     */
    private long sequence = 0L;

    /**
     * 上次生成ID的时间截
     */
    private long lastTimestamp = -1L;

    //==============================Constructors=====================================

    /**
     * 构造函数
     *
     * @param workerId     工作ID (0~31)
     * @param dataCenterId 数据中心ID (0~31)
     */
    public SnowflakeIdWorker(long workerId, long dataCenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("workerId can't be greater than %d or less than 0", maxWorkerId));
        }
        if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
            throw new IllegalArgumentException(String.format("dataCenterId can't be greater than %d or less than 0", maxDataCenterId));
        }
        this.workerId = workerId;
        this.dataCenterId = dataCenterId;
    }

    // ==============================Methods==========================================

    /**
     * 获得下一个ID (该方法是线程安全的)
     *
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();

        //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
        if (timestamp < 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;
            //毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        //时间戳改变，毫秒内序列重置
        else {
            sequence = 0L;
        }

        //上次生成ID的时间截
        lastTimestamp = timestamp;

        //移位并通过或运算拼到一起组成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (dataCenterId << dataCenterIdShift) //
                | (workerId << workerIdShift) //
                | sequence;
    }

    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     *
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 返回以毫秒为单位的当前时间
     *
     * @return 当前时间(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }

    //==============================Test=============================================

    /**
     * 测试
     */
    public static void main(String[] args) {
        System.out.println(System.currentTimeMillis());
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(1, 1);
        long startTime = System.nanoTime();
        for (int i = 0; i < 50000; i++) {
            long id = idWorker.nextId();
            System.out.println(id);
        }
        System.out.println((System.nanoTime() - startTime) / 1000000 + "ms");
    }

}

拓展

在理解了这个算法之后，其实还有一些扩展的事情可以做：

  1. 根据自己业务修改每个位段存储的信息。算法是通用的，可以根据自己需求适当调整每段的大小以及存储的信息。
  2. 解密id，由于id的每段都保存了特定的信息，所以拿到一个id，应该可以尝试反推出原始的每个段的信息。反推出的信息可以帮助我们分析。比如作为订单，可以知道该订单的生成日期，负责处理的数据中心等等。

UUID

UUID具有全球唯一的特性，可以做分布式ID，但不推荐。
UUID不适用于实际的业务需求，像用作订单号UUID这样的字符串没有丝毫意义，看不出和订单相关的有用信息；而对于数据库来说用作业务主键ID，它不仅太长而且还是字符串，存储性能差查询也很耗时。

  • 生成方式
    public static void main(String[] args) {
        String uuid = UUID.randomUUID().toString().replaceAll("-", "");
        System.out.println(uuid);
    }
//output
2fc762f4d07f4a4bb37ee54652e4b53f
  • 优点
    生成简单，本地生成无网络消耗，具有全球唯一性。
  • 缺点
    长度过长16 字节128位，36位长度的字符串，存储以及查询对MySQL的性能消耗较大，MySQL官方明确建议主键要尽量越短越好，作为数据库主键 UUID 的无序性会导致数据位置频繁变动，严重影响性能。

数据库自增ID

基于数据库的auto_increment自增ID完全可以充当分布式ID，具体实现：需要一个单独的MySQL实例用来生成ID。
当需要一个ID的时候，向表中插入一条记录返回主键ID，但存在致命缺点，访问量激增时MySQL本身就是系统瓶颈，不推荐。

  • 生成方式
  CREATE DATABASE `SEQ_ID`;
  CREATE TABLE SEQID.SEQUENCE_ID (
      id bigint(20) unsigned NOT NULL auto_increment
      PRIMARY KEY (id),
  ) ENGINE=InnoDB;

  insert into SEQUENCE_ID  VALUES ();
  • 优点
    实现简单，ID单调自增，数值类型查询速度快。
  • 缺点
    DB单点存在宕机风险，无法扛住高并发场景。

数据库多主模式

此方式是对上面数据库自增ID的高可用优化，采用主从模式集群。也就是两个MySQL实例都能单独生产自增ID，需要设置起始值和自增步长，避免生成重复ID。

  • 生成方式
  1. MySQL_1配置
  set @@auto_increment_offset = 1; --起始值
  set @@auto_increment_increment = 2; --步长
  1. MySQL_2配置
  set @@auto_increment_offset = 2; --起始值
  set @@auto_increment_increment = 2; --步长

两个MySQL实例的自增ID分别是：
1、3、5、7、9
2、4、6、8、10

  • 优点
    解决DB单点问题。
  • 缺点
    如果集群后的性能还是扛不住高并发，就要进行MySQL扩容增加节点水平扩展数据库集群，同时为了ID生成特性，需要将自增步长按照机器数量来设置，如此不利于后续扩容。

号段模式

号段模式是当下分布式ID生成器的主流实现方式之一，号段模式可以理解为从数据库批量的获取自增ID，每次从数据库取出一个号段范围，例如 (1,1000] 代表1000个ID，具体的业务服务将本号段，生成1~1000的自增ID并加载到内存。

  • 生成方式
  CREATE TABLE id_generator (
    id int(10) NOT NULL,
    max_id bigint(20) NOT NULL COMMENT '当前最大id',
    step int(20) NOT NULL COMMENT '号段的布长',
    biz_type	int(20) NOT NULL COMMENT '业务类型',
    version int(20) NOT NULL COMMENT '版本号',
    PRIMARY KEY (`id`)
  )
  • 分析
    该批号段ID用完，再次向数据库申请新号段，对max_id字段做一次update操作，update max_id= max_id + step，update成功则说明新号段获取成功，新的号段范围是(max_id ,max_id +step]
  update id_generator set max_id = #{max_id+step}, version = version + 1 where version = # {version} and biz_type = XXX
  • 优点
  1. 扩张灵活，性能强能够撑起大部分业务场景。
  2. ID号码是趋势递增的，满足数据库存储和查询性能要求。
  3. 可用性高，即使ID生成服务器不可用，也能够使得业务在短时间内可用，为排查问题争取时间。
  4. 可以自定义max_id的大小，方便业务迁移，方便机器横向扩张。
  • 缺点
  1. ID号码不够随机，完整的顺序递增可能带来安全问题。
  2. DB宕机可能导致整个系统不可用，仍然存在这种风险，因为号段只能撑一段时间。
  3. 可能存在分布式环境各节点同一时间争抢分配ID号段的情况，需要采用版本号version乐观锁方式更新。

Redis

Redis也同样可以实现，原理就是利用redis的 incr命令实现ID的原子性自增。

  • 实现方式
  set seq_id 1     // 初始化自增ID为1
  incr seq_id      // 增加1，并返回递增后的数值
  • 分析
    用redis实现需要注意一点，要考虑到redis持久化的问题。redis有两种持久化方式RDB和AOF：
  1. RDB会定时打一个快照进行持久化，假如连续自增但redis没及时持久化，而这会Redis挂掉了，重启Redis后会出现ID重复的情况。
  2. AOF会对每条写命令进行持久化，即使Redis挂掉了也不会出现ID重复的情况，但由于incr命令的特殊性，会导致Redis重启恢复的数据时间过长。
  • 优点
    有序递增，可读性强。
    能够满足一定性能。
  • 缺点
    强依赖于Redis，可能存在单点问题。
    占用宽带，而且需要考虑网络延时等问题带来地性能冲击。

开源项目

0 0 投票数
Article Rating
订阅评论
提醒
guest
0 评论
最旧
最新 最多投票
内联反馈
查看所有评论
0
希望看到您的想法，请您发表评论x