您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

你可能听说过雪花算法

时间:2023-11-10 14:30:36  来源:微信公众号  作者:沐雨花飞蝶

雪花算法介绍

雪花算法(Snowflake)是一种分布式唯一ID生成算法,用于生成全局唯一的ID。它的设计目标是在分布式系统中生成ID,保证ID的唯一性、有序性和趋势递增。雪花算法的核心思想是将一个64位的ID分成多个部分,分别表示不同的信息。

雪花算法的优点是生成的ID具有趋势递增的特性,可以保证在分布式系统中生成的ID的有序性。同时,由于使用了时间戳,可以根据ID的时间戳信息进行排序和查询。

使用雪花算法生成的ID通常是一个64位的整数,可以根据需要进行转换和展示。在JAVA编程语言中,可以使用相应的库或工具来生成雪花算法的ID。

雪花算法组成

  1. 时间戳(Timestamp):使用41位来表示,精确到毫秒级别。可以使用一个起始时间,然后每个毫秒自增生成唯一的时间戳。
  2. 机器ID(machine ID):使用10位来表示,可以根据需要分配给不同的机器或节点。这样可以保证每个节点生成的ID都是唯一的。
  3. 序列号(Sequence Number):使用12位来表示,每个节点每毫秒可以生成4096个不同的序列号。当同一毫秒内生成的序列号超过4096时,会等待下一毫秒再继续生成。

通过将时间戳、机器ID和序列号组合在一起,就可以生成一个全局唯一的ID。这种算法可以在分布式系统中生成唯一的ID,保证了高并发环境下的唯一性和有序性。

雪花算法实现

雪花算法(Snowflake)是一种分布式唯一ID生成算法,它可以在分布式系统中生成全局唯一的ID。Snowflake算法的核心思想是将一个64位的ID分成多个部分,每个部分表示不同的信息。

Snowflake算法的ID结构如下:

0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

其中,第一部分是1位的标识位,表示正负数,一般为0。接下来的41位是时间戳,表示生成ID的时间戳(毫秒级),可以使用当前时间减去一个固定的起始时间戳。然后是10位的工作机器ID,表示机器的唯一标识,可以根据机器的IP地址或其他方式生成。最后是12位的序列号,表示同一毫秒内生成的多个ID的序号。

Snowflake算法Java实现:

public class SnowflakeIdGenerator {
    // 起始的时间戳
    private final static long START_TIMESTAMP = 1609459200000L; // 2021-01-01 00:00:00

    // 每部分占用的位数
    private final static long SEQUENCE_BIT = 12; // 序列号占用的位数
    private final static long WORKER_BIT = 10; // 工作机器ID占用的位数
    private final static long TIMESTAMP_BIT = 41; // 时间戳占用的位数

    // 每部分的最大值
    private final static long MAX_SEQUENCE = ~(-1L << SEQUENCE_BIT);
    private final static long MAX_WORKER_ID = ~(-1L << WORKER_BIT);

    // 每部分向左的位移
    private final static long WORKER_LEFT = SEQUENCE_BIT;
    private final static long TIMESTAMP_LEFT = SEQUENCE_BIT + WORKER_BIT;

    private long workerId; // 工作机器ID
    private long sequence = 0L; // 序列号
    private long lastTimestamp = -1L; // 上次生成ID的时间戳

    public SnowflakeIdGenerator(long workerId) {
        if (workerId > MAX_WORKER_ID || workerId < 0) {
            throw new IllegalArgumentException("Worker ID can't be greater than " + MAX_WORKER_ID + " or less than 0");
        }
        this.workerId = workerId;
    }

    public synchronized long nextId() {
        long timestamp = System.currentTimeMillis();

        if (timestamp < lastTimestamp) {
            throw new RuntimeException("Clock moved backwards. Refusing to generate ID");
        }

        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & MAX_SEQUENCE;
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }

        lastTimestamp = timestamp;

        return ((timestamp - START_TIMESTAMP) << TIMESTAMP_LEFT)
                | (workerId << WORKER_LEFT)
                | sequence;
    }

    private long tilNextMillis(long lastTimestamp) {
        long timestamp = System.currentTimeMillis();
        while (timestamp <= lastTimestamp) {
            timestamp = System.currentTimeMillis();
        }
        return timestamp;
    }
}

使用SnowflakeIdGenerator类生成唯一的ID,示例代码如下:

public class MAIn {
    public static void main(String[] args) {
        SnowflakeIdGenerator idGenerator = new SnowflakeIdGenerator(1);
        long id = idGenerator.nextId();
        System.out.println("Generated ID: " + id);
    }
}

雪花算法优缺点

「优点」

  1. 唯一性:雪花算法可以生成全局唯一的ID,每个ID都是独一无二的,不会重复。
  2. 高性能:雪花算法生成ID的速度非常快,可以在短时间内生成大量的ID。
  3. 可排序:雪花算法生成的ID是按照时间顺序递增的,可以根据ID的大小来判断生成的时间先后顺序。
  4. 分布式:雪花算法可以在分布式系统中使用,不同的节点可以独立生成ID,不会产生冲突。

「缺点」

  1. 依赖系统时钟:雪花算法的唯一性依赖于系统时钟的准确性,如果系统时钟发生回拨或者不同步,可能会导致生成的ID重复。
  2. 时钟回拨问题:如果系统时钟发生回拨,可能会导致生成的ID比之前生成的ID小,这会破坏ID的递增顺序。
  3. 时钟同步问题:在分布式系统中,不同节点的系统时钟可能存在不同步的情况,这可能会导致生成的ID不是全局唯一的。
  4. 有限的并发性:雪花算法中的每个部分(时间戳、机器ID、序列号)都有一定的位数限制,这限制了并发生成ID的数量。

雪花算法是一种简单高效的分布式唯一ID生成算法,但在特定情况下可能会存在一些问题,需要根据具体的应用场景来选择合适的ID生成算法。



Tags:算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
诱导付费、自动扣费……微短剧被质疑借助算法精准“围猎”老年人
诱导付费、自动扣费、重复收费&hellip;&hellip;聚焦身边的消费烦心事⑦丨一些微短剧被质疑借助算法精准“围猎”老年人中工网北京3月31日电(工人日报&mdash;中工网记者刘兵)...【详细内容】
2024-04-01  Search: 算法  点击:(5)  评论:(0)  加入收藏
分析网站SEO快速排名算法对网站具体的影响效果
亲爱的朋友们,今天我想和大家分享一个我们都关心的话题&mdash;&mdash;网站SEO快速排名算法对网站我们身处一个信息爆炸的时代,如何在海量的信息中脱颖而出,成为了一个我们不得...【详细内容】
2024-03-28  Search: 算法  点击:(11)  评论:(0)  加入收藏
当prompt策略遇上分治算法,南加大、微软让大模型炼成「火眼金睛」
近年来,大语言模型(LLMs)由于其通用的问题处理能力而引起了大量的关注。现有研究表明,适当的提示设计(prompt enginerring),例如思维链(Chain-of-Thoughts),可以解锁 LLM 在不同领域的...【详细内容】
2024-03-12  Search: 算法  点击:(12)  评论:(0)  加入收藏
谷歌宣布更新搜索算法:打击AI生成内容,提高搜索结果质量
IT之家 3 月 6 日消息,谷歌于当地时间 5 日发文宣布,针对用户对搜索结果质量下降的反馈,将对算法进行调整,旨在打击 AI 生成的内容以及内容农场等垃圾信息,使用户能够看到更多“...【详细内容】
2024-03-06  Search: 算法  点击:(36)  评论:(0)  加入收藏
小红书、视频号、抖音流量算法解析,干货满满,值得一看!
咱们中国现在可不是一般的牛!网上的网友已经破了十个亿啦!到了这个互联网的新时代,谁有更多的人流量,谁就能赢得更多的掌声哦~抖音、小红书、、视频号,是很多品牌必争的流量洼地...【详细内容】
2024-02-23  Search: 算法  点击:(12)  评论:(0)  加入收藏
雪花算法详解与Java实现:分布式唯一ID生成原理
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2024-02-03  Search: 算法  点击:(49)  评论:(0)  加入收藏
简易百科之什么是搜索引擎的PageRank算法?
简易百科之什么是搜索引擎的PageRank算法?在互联网时代,搜索引擎是我们获取信息的重要工具。而PageRank算法则是搜索引擎的核心技术之一,它决定了网页在搜索结果中的排名。那么...【详细内容】
2024-01-24  Search: 算法  点击:(49)  评论:(0)  加入收藏
PageRank算法揭秘:搜索引擎背后的魔法师的工作原理
PageRank(PR)算法是由谷歌创始人之一的拉里&middot;佩奇LarryPage命名的一种衡量网站页面重要性的方法。根据谷歌的说法,PageRank通过计算页面链接的数量和质量来粗略估计分...【详细内容】
2024-01-23  Search: 算法  点击:(44)  评论:(0)  加入收藏
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  Search: 算法  点击:(43)  评论:(0)  加入收藏
百度最新的搜索引擎算法是什么样的?
百度搜索引擎算法是百度用来决定网页排名的算法。它是百度搜索技术的核心,也是百度作为全球最大的中文搜索引擎的基石。随着互联网的发展和用户需求的不断变化,百度搜索引擎算...【详细内容】
2024-01-10  Search: 算法  点击:(85)  评论:(0)  加入收藏
▌简易百科推荐
小红书、视频号、抖音流量算法解析,干货满满,值得一看!
咱们中国现在可不是一般的牛!网上的网友已经破了十个亿啦!到了这个互联网的新时代,谁有更多的人流量,谁就能赢得更多的掌声哦~抖音、小红书、、视频号,是很多品牌必争的流量洼地...【详细内容】
2024-02-23  二手车小胖说    Tags:流量算法   点击:(12)  评论:(0)  加入收藏
雪花算法详解与Java实现:分布式唯一ID生成原理
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2024-02-03   一安未来  微信公众号  Tags:雪花算法   点击:(49)  评论:(0)  加入收藏
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  架构师老卢  今日头条  Tags:算法   点击:(43)  评论:(0)  加入收藏
百度推荐排序技术的思考与实践
本文将分享百度在推荐排序方面的思考与实践。在整个工业界的推广搜场景上,特征设计通常都是采用离散化的设计,需要保证两方面的效果,一方面是记忆,另一方面是泛化。特征都是通过...【详细内容】
2024-01-09  DataFunTalk  微信公众号  Tags:百度推荐   点击:(73)  评论:(0)  加入收藏
什么是布隆过滤器?如何实现布隆过滤器?
以下我们介绍了什么是布隆过滤器?它的使用场景和执行流程,以及在 Redis 中它的使用,那么问题来了,在日常开发中,也就是在 Java 开发中,我们又将如何操作布隆过滤器呢?布隆过滤器(Blo...【详细内容】
2024-01-05  Java中文社群  微信公众号  Tags:布隆过滤器   点击:(87)  评论:(0)  加入收藏
面向推荐系统的深度强化学习算法研究与应用
随着互联网的快速发展,推荐系统在各个领域中扮演着重要的角色。传统的推荐算法在面对大规模、复杂的数据时存在一定的局限性。为了解决这一问题,深度强化学习算法应运而生。本...【详细内容】
2024-01-04  数码小风向    Tags:算法   点击:(89)  评论:(0)  加入收藏
非负矩阵分解算法:从非负数据中提取主题、特征等信息
非负矩阵分解算法(Non-negativeMatrixFactorization,简称NMF)是一种常用的数据分析和特征提取方法,主要用于从非负数据中提取主题、特征等有意义的信息。本文将介绍非负矩阵分解...【详细内容】
2024-01-02  毛晓峰    Tags:算法   点击:(62)  评论:(0)  加入收藏
再谈前端算法,你这回明白了吗?
楔子 -- 青蛙跳台阶一只青蛙一次可以跳上一级台阶,也可以跳上二级台阶,求该青蛙跳上一个n级的台阶总共需要多少种跳法。分析: 当n=1的时候,①只需要跳一次即可;只有一种跳法,即f(...【详细内容】
2023-12-28  前端爱好者  微信公众号  Tags:前端算法   点击:(107)  评论:(0)  加入收藏
三分钟学习二分查找
二分查找是一种在有序数组中查找元素的算法,通过不断将搜索区域分成两半来实现。你可能在日常生活中已经不知不觉地使用了大脑里的二分查找。最常见的例子是在字典中查找一个...【详细内容】
2023-12-22  小技术君  微信公众号  Tags:二分查找   点击:(78)  评论:(0)  加入收藏
强化学习算法在资源调度与优化中的应用
随着云计算和大数据技术的快速发展,资源调度与优化成为了现代计算系统中的重要问题。传统的资源调度算法往往基于静态规则或启发式方法,无法适应动态变化的环境和复杂的任务需...【详细内容】
2023-12-14  职场小达人欢晓    Tags:算法   点击:(164)  评论:(0)  加入收藏
站内最新
站内热门
站内头条