前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >架构设计——ID生成器「建议收藏」

架构设计——ID生成器「建议收藏」

作者头像
全栈程序员站长
发布2022-07-02 15:15:29
6120
发布2022-07-02 15:15:29
举报

大家好,又见面了,我是你们的朋友全栈君。

一、分布式ID发号器

要求很明确:不同机器同一时间生成不同ip;同一机器不同时间生成不同IP;

所以根据需求,可选变量有: 机器(网卡、IP)+时间,随机数

二、Why not UUID?

UUID的实现:算法的核心思想是结合机器的网卡、当地时间、一个随机数来生成UUID。

优势:保证唯一性;本地调用,不需要rpc

UUID的缺陷:

1.UUID较长,占用内存空间;往往用字符串表示,作为主键建立索引查询效率低,常见优化方案为“转化为两个uint64整数存储”或者“折半存储”(折半后不能保证唯一性)

2.不具有有序性,无法保证趋势递增

三、依赖DB自增可行么?

实现:自增+设定步长;8个服务节点8个实例(类似取模);

缺陷:

1.不利于服务节点扩充;服务节点固定,步长固定,难以进行水平服务节点的扩展。

2.依赖DB,对数据库造成额外压力

四.全局唯一ID生成器如何设计?考量因素有哪些

1.全局唯一;有序性(不一定连续,但趋势递增);可反解信息;

2.业务性能要求:高性能、高可用

3.接入方式:嵌入式、中心服务发布、rest发布模式

设计一 :ID数据结构

架构设计——ID生成器「建议收藏」
架构设计——ID生成器「建议收藏」

64位

1.机器ID 10位;2的10次方最多可支持1k+台机器;如果每台机器TPS为1W/s,10台服务器则可以有10W/s的TPS,基本满足大部分业务要求。

2.序列号 10位或20位;同理,计算2的20次方,每秒平均可产生百万个ID

3.时间戳 30或40位(分别对应秒级、毫秒级)-时间保证趋势递增

其他可根据业务特点,加上定制的不同生产方式(pom、rest)或版本信息

设计二 并发

为支持大量并发的网络请求,ID生成服务一般采用多线程支持,对于竞争时间和序列(time sequence)采用juc中ReentrantLock或synchronized或atomic变量支持(推荐)

实现

1.定义id实体结构(机器+时间+种子(生成随机数))

代码语言:javascript
复制
//时间戳
private Long time;
//序列号
private Integer sequence;
//生成随机数的种子
private Integer seed;
//机器ip
private Integer clusterIp;

2.根据结构获取对应请求数据,组装实体数据(获取时间戳(毫秒或秒级)os获取本机ip、mac等数据),生成一个不重复的id

代码语言:javascript
复制
//synch保证线程安全
public synchronized long getId()

计算(左移拼装,)【时间戳-初始时间】左移两位集群ip-sequence

3.解析ip,获取对应机器ip、时间戳等信息,则右移取指定位即可

五、Twitter的snowflake算法

Twitter 利用 zookeeper 实现了一个全局ID生成的服务 Snowflake:https://github.com/twitter-archive/snowflake

  • 1位符号位:

由于 long 类型在 java 中带符号的,最高位为符号位,正数为 0,负数为 1,且实际系统中所使用的ID一般都是正数,所以最高位为 0。

  • 41位时间戳(毫秒级):

需要注意的是此处的 41 位时间戳并非存储当前时间的时间戳,而是存储时间戳的差值(当前时间戳 – 起始时间戳),这里的起始时间戳一般是ID生成器开始使用的时间戳,由程序来指定,所以41位毫秒时间戳最多可以使用 (1 << 41) / (1000x60x60x24x365) = 69年

  • 10位数据机器位:

包括5位数据标识位和5位机器标识位,这10位决定了分布式系统中最多可以部署 1 << 10 = 1024 s个节点。超过这个数量,生成的ID就有可能会冲突。

  • 12位毫秒内的序列:

这 12 位计数支持每个节点每毫秒(同一台机器,同一时刻)最多生成 1 << 12 = 4096个ID

加起来刚好64位,为一个Long型。

  • 优点:高性能,低延迟,按时间有序,一般不会造成ID碰撞
  • 缺点:需要独立的开发和部署,依赖于机器的时钟

实现:

代码语言:javascript
复制
public class IdWorker {
    /**
     * 起始时间戳 2017-04-01
     */
    private final long epoch = 1491004800000L;
    /**
     * 机器ID所占的位数
     */
    private final long workerIdBits = 5L;
    /**
     * 数据标识ID所占的位数
     */
    private final long dataCenterIdBits = 5L;
    /**
     * 支持的最大机器ID,结果是31
     */
    private final long maxWorkerId = ~(-1L << workerIdBits);
    /**
     * 支持的最大数据标识ID,结果是31
     */
    private final long maxDataCenterId = ~(-1 << 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(12+5+5)位
     */
    private final long timestampShift = sequenceBits + workerIdBits + dataCenterIdBits;
    /**
     * 生成序列的掩码,这里为4095 (0b111111111111=0xfff=4095)
     */
    private final long sequenceMask = ~(-1L << sequenceBits);
    /**
     * 数据标识ID(0~31)
     */
    private long dataCenterId;
    /**
     * 机器ID(0~31)
     */
    private long workerId;
    /**
     * 毫秒内序列(0~4095)
     */
    private long sequence;
    /**
     * 上次生成ID的时间戳
     */
    private long lastTimestamp = -1L;

    public IdWorker(long dataCenterId, long workerId) {
        if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
            throw new IllegalArgumentException(String.format("dataCenterId can't be greater than %d or less than 0", maxDataCenterId));
        }
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        this.dataCenterId = dataCenterId;
        this.workerId = workerId;
    }

    /**
     * 获得下一个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 (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & sequenceMask;
            //毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一个毫秒,获得新的时间戳
                timestamp = nextMillis(lastTimestamp);
            }
        } else {//时间戳改变,毫秒内序列重置
            sequence = 0L;
        }
        lastTimestamp = timestamp;
        //移位并通过按位或运算拼到一起组成64位的ID
        return ((timestamp - epoch) << timestampShift) |
                (dataCenterId << dataCenterIdShift) |
                (workerId << workerIdShift) |
                sequence;
    }

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

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

实现注意点:

1.由于存在对时进行修改,snowflake算法应对时钟回拨的做法是直接抛出异常。

2.其次是12位序列号溢出的问题,即1ms内请求生成的ID个数超过了2的12次方=4096个id。snowflake算法对此的做法是,等到下一ms再生成ID。

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/148260.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、分布式ID发号器
  • 二、Why not UUID?
  • 三、依赖DB自增可行么?
  • 四.全局唯一ID生成器如何设计?考量因素有哪些
  • 五、Twitter的snowflake算法
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档