分布式ID生成方案选型!详细解析雪花算法Snowflake

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
云解析 DNS,旗舰版 1个月
简介: 本篇文章中和大家分享了分布式项目中的全局唯一ID生成算法的雪花算法。首先从分布式项目中的ID需要满足的条件引入问题,然后详细解析了雪花算法Snowflake生成唯一ID的具体方式,最后通过一个具体实例SnowflakeIdWorker介绍了雪花算法的具体使用。

分布式唯一ID

  • 使用RocketMQ时,需要使用到分布式唯一ID
  • 消息可能会发生重复,所以要在消费端做幂等性,为了达到业务的幂等性,生产者必须要有一个唯一ID, 需要满足以下条件:

    • 同一业务场景要全局唯一
    • 该ID必须是在消息的发送方进行生成发送到MQ
    • 消费端根据该ID进行判断是否重复,确保幂等性
  • 在哪里产生以及消费端进行判断做幂等性与该ID无关,此ID需要保证的特性:

    • 局部甚至全局唯一
    • 趋势递增

Snowflake算法

  • Snowflake是Twitter开源的分布式ID生成算法, 结果是一个Long型的ID,核心思想是:

    • 使用1位作为符号位,确定为0, 表示
    • 使用41位作为毫秒数
    • 使用10位作为机器的ID :5位是数据中心ID,5位是机器ID
    • 使用12位作为毫秒内的序列号, 意味着每个节点每秒可以产生4096(2^12^) 个ID

在这里插入图片描述
该算法通过二进制的操作进行实现,单机每秒内理论上最多可以生成1000*(2^12),409.6万个ID

SnowflakeIdWorker

  • Snowflake算法Java实现SnowflakeIdWorker:
/**
 * Twitter_Snowflake<br>
 * SnowFlake的结构如下(每部分用-分开):<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
 * 1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0<br>
 * 41位时间截(毫秒级),注意,41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截 - 开始时间截)
 * 得到的值),这里的的开始时间截,一般是我们的id生成器开始使用的时间,由我们程序来指定的(如下下面程序IdWorker类的startTime属性)。41位的时间截,可以使用69年,年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
 * 10位的数据机器位,可以部署在1024个节点,包括5位datacenterId和5位workerId<br>
 * 12位序列,毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号<br>
 * 加起来刚好64位,为一个Long型。<br>
 * SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分),并且效率较高,经测试,SnowFlake每秒能够产生26万ID左右。
 */
public class SnowflakeIdWorker {

    // ==============================Fields===========================================
    /** 开始时间截 (2015-01-01) */
    private final long twepoch = 1420041600000L;

    /** 机器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("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));
        }
        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) {
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
        for (int i = 0; i < 1000; i++) {
            long id = idWorker.nextId();
            System.out.println(Long.toBinaryString(id));
            System.out.println(id);
        }
    }
}
  • 优点:

    • 生成速度快
    • 实现简单,没有多余的依赖
    • 可以根据实际情况调整各个位段,方便灵活
  • 缺点:

    • 只能趋势递增
    • 依赖机器时间. 如果发生回拨可能会造成生成的ID重复

SnowFlake算法时间回拨问题:

  • 时间回拨产生原因:

    • 由于业务需要,机器需要同步时间服务器
  • 时间回拨问题解决办法:

    • 当回拨时间小于15ms,可以等待时间追上来以后再继续生成
    • 当回拨时间大于15ms时可以通过更换workId来产生之前都没有产生过的Id来解决回拨问题
  • 步骤:

    • 首先将workId的位数进行调整至15位

    在这里插入图片描述

    • 然后将SnowflakeIdWorker实现调整位段

      • 使用1位作为符号位, 即生成的分布式I唯一d为正数
      • 使用38位作为时间戳, 表示当前时间相对于初始时间的增量值,单位为毫秒
      • 使用15位作为机器ID, 最多可支持3.28万个节点
      • 使用10位作为毫秒内的序列号, 理论上可以生成2^10^个序列号
    • 因为服务的无状态关系,正常情况下workId不会配置在具体配置文件中,这里可以选择集中式的Redis作为中央存储:

      • 将workId调整位数后得到的多余的3万多个workId放置到一个基于Redis的队列中,用来集中管理workId
      • 每次当节点启动的时候,先查看本地是否有workId,如果有那么就作为workId.如果没有,就在队列中取出一个当workId来使用,并从队列中删除
      • 当发现时间回拨太多的时候,就再去队列中去一个来当新的workId使用,将刚刚那个使用回拨的情况的workId存到队列里. 因为队列每次都是从头取出,从尾部插入,这样可以避免刚刚A机器使用的workId又被B机器获取的可能性
      • 如果使用redis又会遇到新的小问题: redis一致性如何保证?redis挂了怎么办?怎么同步?
  • 从基础组件的使用角度来说,对于SnowflakeIdWorker算法当遇到时间回拨问题,只需要抛出异常即可,这样可以保证算法实现的简单性
  • 也可以参考uid-generator 方法: 每次取一批workId, 集中之后批取,这样可以解决各个节点访问集中机器的性能问题.
相关文章
|
18天前
|
存储 算法 安全
.NET 平台 SM2 国密算法 License 证书生成深度解析
授权证书文件的后缀通常取决于其编码格式和具体用途。本文档通过一个示例程序展示了如何在 .NET 平台上使用国密 SM2 算法生成和验证许可证(License)文件。该示例不仅详细演示了 SM2 国密算法的实际应用场景,还提供了关于如何高效处理大规模许可证文件生成任务的技术参考。通过对不同并发策略的性能测试,开发者可以更好地理解如何优化许可证生成流程,以满足高并发和大数据量的需求。 希望这段描述更清晰地传达了程序的功能和技术亮点。
89 13
.NET 平台 SM2 国密算法 License 证书生成深度解析
|
7天前
|
存储 监控 算法
关于员工上网监控系统中 PHP 关联数组算法的学术解析
在当代企业管理中,员工上网监控系统是维护信息安全和提升工作效率的关键工具。PHP 中的关联数组凭借其灵活的键值对存储方式,在记录员工网络活动、管理访问规则及分析上网行为等方面发挥重要作用。通过关联数组,系统能高效记录每位员工的上网历史,设定网站访问权限,并统计不同类型的网站访问频率,帮助企业洞察员工上网模式,发现潜在问题并采取相应管理措施,从而保障信息安全和提高工作效率。
23 7
|
1月前
|
监控 算法 安全
内网桌面监控软件深度解析:基于 Python 实现的 K-Means 算法研究
内网桌面监控软件通过实时监测员工操作,保障企业信息安全并提升效率。本文深入探讨K-Means聚类算法在该软件中的应用,解析其原理与实现。K-Means通过迭代更新簇中心,将数据划分为K个簇类,适用于行为分析、异常检测、资源优化及安全威胁识别等场景。文中提供了Python代码示例,展示如何实现K-Means算法,并模拟内网监控数据进行聚类分析。
42 10
|
25天前
|
存储 监控 算法
探秘员工泄密行为防线:基于Go语言的布隆过滤器算法解析
在信息爆炸时代,员工泄密行为对企业构成重大威胁。本文聚焦布隆过滤器(Bloom Filter)这一高效数据结构,结合Go语言实现算法,帮助企业识别和预防泄密风险。通过构建正常操作“指纹库”,实时监测员工操作,快速筛查可疑行为。示例代码展示了如何利用布隆过滤器检测异常操作,并提出优化建议,如调整参数、结合日志分析系统等,全方位筑牢企业信息安全防线,守护核心竞争力。
|
2月前
|
存储 算法 安全
控制局域网上网软件之 Python 字典树算法解析
控制局域网上网软件在现代网络管理中至关重要,用于控制设备的上网行为和访问权限。本文聚焦于字典树(Trie Tree)算法的应用,详细阐述其原理、优势及实现。通过字典树,软件能高效进行关键词匹配和过滤,提升系统性能。文中还提供了Python代码示例,展示了字典树在网址过滤和关键词屏蔽中的具体应用,为局域网的安全和管理提供有力支持。
60 17
|
2月前
|
存储 人工智能 算法
解锁分布式文件分享的 Java 一致性哈希算法密码
在数字化时代,文件分享成为信息传播与协同办公的关键环节。本文深入探讨基于Java的一致性哈希算法,该算法通过引入虚拟节点和环形哈希空间,解决了传统哈希算法在分布式存储中的“哈希雪崩”问题,确保文件分配稳定高效。文章还展示了Java实现代码,并展望了其在未来文件分享技术中的应用前景,如结合AI优化节点布局和区块链增强数据安全。
|
13天前
|
机器学习/深度学习 自然语言处理 算法
生成式 AI 大语言模型(LLMs)核心算法及源码解析:预训练篇
生成式 AI 大语言模型(LLMs)核心算法及源码解析:预训练篇
113 0
|
14天前
|
存储 算法 安全
基于 Go 语言的公司内网管理软件哈希表算法深度解析与研究
在数字化办公中,公司内网管理软件通过哈希表算法保障信息安全与高效管理。哈希表基于键值对存储和查找,如用户登录验证、设备信息管理和文件权限控制等场景,Go语言实现的哈希表能快速验证用户信息,提升管理效率,确保网络稳定运行。
26 0
|
3月前
|
物联网 调度 vr&ar
鸿蒙HarmonyOS应用开发 |鸿蒙技术分享HarmonyOS Next 深度解析:分布式能力与跨设备协作实战
鸿蒙技术分享:HarmonyOS Next 深度解析 随着万物互联时代的到来,华为发布的 HarmonyOS Next 在技术架构和生态体验上实现了重大升级。本文从技术架构、生态优势和开发实践三方面深入探讨其特点,并通过跨设备笔记应用实战案例,展示其强大的分布式能力和多设备协作功能。核心亮点包括新一代微内核架构、统一开发语言 ArkTS 和多模态交互支持。开发者可借助 DevEco Studio 4.0 快速上手,体验高效、灵活的开发过程。 239个字符
265 13
鸿蒙HarmonyOS应用开发 |鸿蒙技术分享HarmonyOS Next 深度解析:分布式能力与跨设备协作实战
|
2月前
|
算法 搜索推荐 Java
【潜意识Java】深度解析黑马项目《苍穹外卖》与蓝桥杯算法的结合问题
本文探讨了如何将算法学习与实际项目相结合,以提升编程竞赛中的解题能力。通过《苍穹外卖》项目,介绍了订单配送路径规划(基于动态规划解决旅行商问题)和商品推荐系统(基于贪心算法)。这些实例不仅展示了算法在实际业务中的应用,还帮助读者更好地准备蓝桥杯等编程竞赛。结合具体代码实现和解析,文章详细说明了如何运用算法优化项目功能,提高解决问题的能力。
84 6