Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >算法:第一章:SnowFlake算法(分布式系统中生成唯一的ID的算法)SnowFlake每秒能够产生26万ID左右

算法:第一章:SnowFlake算法(分布式系统中生成唯一的ID的算法)SnowFlake每秒能够产生26万ID左右

作者头像
Java廖志伟
发布于 2022-09-28 09:09:33
发布于 2022-09-28 09:09:33
42900
代码可运行
举报
文章被收录于专栏:高级开发进阶高级开发进阶
运行总次数:0
代码可运行

不废话了,直接上代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
package cn.springboot.config.db.pk.local.impl;

/**
 * The class Snowflake id generator. Created by paascloud.net@gmail.com
 * Twitter雪花ID算法
 * 概述
 * - SnowFlake算法是Twitter设计的一个可以在分布式系统中生成唯一的ID的算法,它可以满足Twitter每秒上万条消息ID分配的请求,这些消息ID是唯一的且有大致的递增顺序
 * 
 * 原理
 * - SnowFlake算法产生的ID是一个64位的整型,结构如下(每一部分用“-”符号分隔):
 *    0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
 * - 1位标识部分,在java中由于long的最高位是符号位,正数是0,负数是1,一般生成的ID为正数,所以为0
 * - 41位时间戳部分,这个是毫秒级的时间,一般实现上不会存储当前的时间戳,而是时间戳的差值(当前时间-固定的开始时间),这样可以使产生的ID从更小值开始;41位的时间戳可以使用69年,(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年
 * - 10位节点部分,Twitter实现中使用前5位作为数据中心标识,后5位作为机器标识,可以部署1024个节点
 * - 12位序列号部分,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间戳)产生4096个ID序号,加起来刚好64位,为一个Long型
 *  
 * 优点
 * - SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分),并且效率较高,经测试,SnowFlake每秒能够产生26万ID左右
 * 
 * 使用
 * - SnowFlake算法生成的ID大致上是按照时间递增的,用在分布式系统中时,需要注意数据中心标识和机器标识必须唯一,这样就能保证每个节点生成的ID都是唯一的。
 *   或许我们不一定都需要像上面那样使用5位作为数据中心标识,5位作为机器标识,可以根据我们业务的需要,灵活分配节点部分,如:若不需要数据中心,完全可以使用全部10位作为机器标识;若数据中心不多,也可以只使用3位作为数据中心,7位作为机器标识
 */
public class SnowflakeIdGenerator {
    /**
     * 每一部分占用的位数
     */
    private final static long DATA_CENTER_ID_BITS = 5L; // 数据中心标识在ID中占用的位数
    private final static long MACHINE_ID_BITS = 5L; // 机器标识在ID中占用的位数
    private final static long SEQUENCE_BITS = 12L; // 序列号在ID中占用的位数

    /**
     * 每一部分的最大值
     */
    private final static long MAX_DATA_CENTER_ID = -1L ^ (-1L << DATA_CENTER_ID_BITS); // 支持的最大数据中心标识ID为31
    private final static long MAX_MACHINE_ID = -1L ^ (-1L << MACHINE_ID_BITS); // 支持的最大机器标识ID为31(这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数)
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BITS); // 支持的最大序列(掩码), 这里为4095 (0b111111111111=0xfff=4095)

    /**
     * 每一部分向左的位移
     */
    private final static long DATA_CENTER_ID_SHIFT = SEQUENCE_BITS + MACHINE_ID_BITS; // 数据中心标识ID向左移17位(12+5)
    private final static long MACHINE_ID_SHIFT = SEQUENCE_BITS; // 机器标识ID向左移12位
    private final static long TIMESTAMP_SHIFT = SEQUENCE_BITS + MACHINE_ID_BITS + DATA_CENTER_ID_BITS; // 时间戳向左移22位(5+5+12)

    /**
     * 批量获取的最大数目(10万)
     */
    private final static int MAX_BATCH_COUNT = 100_000;

    /**
     * 变量部分
     */
    private long dataCenterId; // 数据中心标识ID(0~31)
    private long machineId; // 机器标识ID(0~31)
    private long sequence = 0L; // 毫秒内序列(0~4095)
    private long startTimestamp = -1L; // 开始时间戳
    private long lastTimestamp = -1L; // 上次生成ID的时间戳

    /**
     * 构造方法
     * @param startTimestamp 开始时间戳,不可大于当前时间
     * @param dataCenterId 数据中心标识ID(0~31)
     * @param machineId 机器标识ID(0~31)
     */
    public SnowflakeIdGenerator(long startTimestamp, long dataCenterId, long machineId) {
        long currentTimestamp = getCurrentTimestamp();
        if (startTimestamp > currentTimestamp) {
            throw new RuntimeException(String.format("Start timestamp can't be greater than %d", currentTimestamp));
        }

        if (dataCenterId > MAX_DATA_CENTER_ID || dataCenterId < 0) {
            throw new RuntimeException(String.format("Data center id can't be greater than %d or less than 0", MAX_DATA_CENTER_ID));
        }

        if (machineId > MAX_MACHINE_ID || machineId < 0) {
            throw new RuntimeException(String.format("Machine id can't be greater than %d or less than 0", MAX_MACHINE_ID));
        }

        // 当初始时间跟当前时间相等,减1毫秒,否则会导致溢出
        this.startTimestamp = (startTimestamp == currentTimestamp ? startTimestamp - 1 : startTimestamp);
        this.dataCenterId = dataCenterId;
        this.machineId = machineId;
    }

    /**
     * 批量获取下一组ID
     * @param count 批量条数
     * @return
     */
    public String[] nextIds(int count) {
        if (count <= 0 || count > MAX_BATCH_COUNT) {
            throw new RuntimeException(String.format("Count can't be greater than %d or less than 0", MAX_BATCH_COUNT));
        }

        String[] ids = new String[count];
        for (int i = 0; i < count; i++) {
            ids[i] = nextId();
        }

        return ids;
    }

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

        // 如果当前时间小于上一次ID生成的时间戳, 说明系统时钟回退过这个时候应当抛出异常
        if (currentTimestamp < lastTimestamp) {
            throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - currentTimestamp));
        }

        // 如果是同一时间生成的, 则进行毫秒内序列自增
        if (lastTimestamp == currentTimestamp) {
            // 相同毫秒内,序列号自增
            sequence = (sequence + 1) &amp; MAX_SEQUENCE;
            // 同一毫秒的序列数已经达到最大,则毫秒内序列溢出
            if (sequence == 0) {
                // 阻塞到下一个毫秒,获得新的时间戳
                currentTimestamp = getNextTimestamp(lastTimestamp);
            }
        } else {
            // 不同毫秒内,序列号置为0
            sequence = 0L;
        }

        // 上次生成ID的时间戳
        lastTimestamp = currentTimestamp;

        // 移位并通过或运算拼到一起组成64位的ID
        long id = ((currentTimestamp - startTimestamp) << TIMESTAMP_SHIFT) // 时间戳部分
            | (dataCenterId << DATA_CENTER_ID_SHIFT) // 数据中心标识ID部分
            | (machineId << MACHINE_ID_SHIFT) // 机器标识ID部分
            | sequence; // 序列号部分

        return String.valueOf(id);
    }

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

        return currentTimestamp;
    }

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

    public static void main(String[] args) {
        SnowflakeIdGenerator generator = new SnowflakeIdGenerator(1483200000000L, 2, 3);

        for (int i = 0; i < 1000; i++) {
            System.out.println(generator.nextId());
        }
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021-04-28,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
浩鲸科技:为什么要用雪花ID替代数据库自增ID?
今天咱们来看一道数据库中比较经典的面试问题:为什么要使用雪花 ID 替代数据库自增 ID?同时这道题也出现在了浩鲸科技的 Java 面试中,下面我们一起来看吧。
磊哥
2023/11/30
5980
浩鲸科技:为什么要用雪花ID替代数据库自增ID?
分布式唯一ID生成器Twitter 的 Snowflake idworker java版本
import java.lang.management.ManagementFactory; import java.net.InetAddress; import java.net.NetworkInterface; /** * <p>名称:IdWorker.java</p> * <p>描述:分布式自增长ID</p> * <pre> * Twitter的 Snowflake JAVA实现方案 * </pre> * 核心代码为其IdWorker这个类实现,其原理结构如下,我分别用一个0
MonroeCode
2018/01/09
2.9K0
漫画:什么是SnowFlake算法?
UUID是通用唯一识别码 (Universally Unique Identifier),在其他语言中也叫GUID,可以生成一个长度32位的全局唯一识别码。
用户5927304
2019/07/31
1.1K0
分布式唯一 ID 之 Snowflake 算法
Snowflake(雪花) 是一项服务,用于为 Twitter 内的对象(推文,直接消息,用户,集合,列表等)生成唯一的 ID。这些 IDs 是唯一的 64 位无符号整数,它们基于时间,而不是顺序的。完整的 ID 由时间戳,工作机器编号和序列号组成。当在 API 中使用 JSON 数据格式时,请务必始终使用 id_str 字段而不是 id,这一点很重要。这是由于处理JSON 的 Javascript 和其他语言计算大整数的方式造成的。如果你遇到 id 和 id_str 似乎不匹配的情况,这是因为你的环境已经解析了 id 整数,并在处理的过程中仔细分析了这个数字。
阿宝哥
2019/11/06
1.9K0
分布式唯一 ID 之 Snowflake 算法
分布式唯一ID生成方案选型!详细解析雪花算法Snowflake
该算法通过二进制的操作进行实现,单机每秒内理论上最多可以生成1000*(2^12), 即409.6万个ID
攻城狮Chova
2022/01/22
9290
分布式唯一ID生成方案选型!详细解析雪花算法Snowflake
面试题108:如何生成分布式系统的唯一ID?
针对业务数据来说,通常都是需要唯一id的,比如学生的学号、订单的订单号,支付流水的流水号等等。那么,如果采用最简单的方式,就是插入时候设置主键auto increment的自增方式。那么插入表中的数据都是唯一的,不过方案虽然简单,但是弊端确实很多。比如通过这种自增的方式,用户很容易就会通过遍历id的方式,获得库中的业务数据,并且如果采用了分库分表的方式,那么就无法通过主键自增的方式来控制业务数据唯一性。那么如果采取MD5的方式呢,却失去了业务含义,并且不利于在分库分表的场景下,通过id快速确定数据在哪个库或
爪哇缪斯
2023/05/10
3750
面试题108:如何生成分布式系统的唯一ID?
聊聊PowerJob的IdGenerateService
tech/powerjob/server/core/uid/IdGenerateService.java
code4it
2024/01/10
1490
聊聊PowerJob的IdGenerateService
tech/powerjob/server/core/uid/IdGenerateService.java
code4it
2024/01/19
1400
聊聊PowerJob的IdGenerateService
springBoot 整合自定义的雪花算法
1 配置pom文件 # 雪花算法配置数据中心和机器编号,不同机器组合不能重复 snowflake: datacenterId: 1 machineId: 2 2 编写配置文件 SnowFlakeFactory.java package com.un.framework.snowflack; import java.util.Map; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.TimeUni
用户5927264
2020/05/28
5.1K0
6 种常见分布式唯一ID生成策略及它们的优缺点对比
全局唯一的 ID 几乎是所有系统都会遇到的刚需。这个 id 在搜索, 存储数据, 加快检索速度 等等很多方面都有着重要的意义。有多种策略来获取这个全局唯一的id,针对常见的几种场景,我在这里进行简单的总结和对比。
芋道源码
2021/04/20
2.3K0
雪花算法:分布式唯一ID生成利器
无论是在分布式系统中的ID生成,还是在业务系统中请求流水号这一类唯一编号的生成,都是软件开发人员经常会面临的一场景。而雪花算法便是这些场景的一个解决方案。
程序新视界
2022/05/06
1.2K0
雪花算法:分布式唯一ID生成利器
分布式ID生成之雪花(SnowFlake)算法
分布式 ID 生成算法的有很多种,Twitter 的 SnowFlake 就是其中经典的一种。
码之有理
2024/03/12
7270
java雪花算法实现
Java的雪花算法(Snowflake)是一种生成全局唯一ID的算法,它基于时间戳和节点ID生成一个64位的ID。
堕落飞鸟
2023/03/29
6410
Twitter的分布式自增ID算法-->雪花算法(snowflake)
通常我们在实际项目中很少使用AUTO_INCREMENT自增长,因为这样很容易被人遍历,从1循环到最大值,把所有的库都遍历一遍。
Cheng_Blog
2022/02/25
1.2K0
分布式ID生成系统之雪花算法详解
在当今的云计算和微服务架构盛行的时代,分布式系统已成为软件开发的重要组成部分。随着系统规模的扩大和业务的复杂化,对数据一致性和唯一性的要求也越来越高,尤其是在全局唯一标识符(ID)的生成上。因此,分布式ID生成系统应运而生,成为保证数据唯一性和提高系统可扩展性的关键技术之一。雪花算法(Snowflake)是Twitter开源的一种算法,用于生成64位的全局唯一ID,非常适用于分布式系统中生成唯一标识符。下面我们将深入探讨雪花算法的原理、结构和实现方式。
修己xj
2024/03/04
7290
分布式ID生成系统之雪花算法详解
分布式id生成算法SnowFlake
10位记录工作机器id;即datacenterId (5位数据id) + workerId (5位机器id)
chenchenchen
2019/09/03
9770
分布式id生成算法SnowFlake
分布式ID生成器
由于我们的数据库在生产环境中要分片部署(MyCat),所以我们不能使用数据库本身的自增功能来产生主键值,只能由程序来生成唯一的主键值。我们采用的是开源的 twitter 的 snowflake (雪花)算法。
名字是乱打的
2022/05/13
3210
分布式ID生成器
最常用的分布式ID解决方案
说起ID,特性就是唯一,在人的世界里,ID就是身份证,是每个人的唯一的身份标识。在复杂的分布式系统中,往往也需要对大量的数据和消息进行唯一标识。举个例子,数据库的ID字段在单体的情况下可以使用自增来作为ID,但是对数据分库分表后一定需要一个唯一的ID来标识一条数据,这个ID就是分布式ID。对于分布式ID而言,也需要具备分布式系统的特点:高并发,高可用,高性能等特点。
BUG弄潮儿
2020/12/17
6640
最常用的分布式ID解决方案
分布式全局唯一ID生成方案(附源码)
Java中 JDK自带的 UUID产生方式就是版本4根据随机数生成的 UUID 和版本3基于名字的 UUID,有兴趣的可以去看看它的源码。
小熊学Java
2023/07/16
1.4K0
分布式全局唯一ID生成方案(附源码)
PHP实现雪花算法生成唯一ID
雪花算法是Twitter开源的分布式ID生成算法,可以产生64位的ID。其中第一位是固定的正数标识,41位用于存储时间戳,剩下的为机器ID和序列号。通过时间戳、机器ID和序列号的组合,确保每个ID都是唯一的。
参谋带个长
2024/11/01
4000
相关推荐
浩鲸科技:为什么要用雪花ID替代数据库自增ID?
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验