程序员经验分享-hwhale

SnowFlake 算法

2023-11-09

SnowFlake 算法

1、介绍

  1. 是 Twitter 开源的分布式 id 生成算法。
  2. 核心思想：使用一个 64 bit 的 long 型的数字作为全局唯一 id。

2、结构

在这里插入图片描述

0 - 0001000000 0000010000 0001000100 0000100000 0 - 10001 - 11001 - 000000000000

2.1、第1部分：1bit

  1. 1 个 bit
  2. 这个是无意义的
无意义原因

因为二进制里第一个 bit 为如果是 1，那么都是负数，但是我们生成的 id 都是正数，所以第一个 bit 统一都是 0。

2.2、第2部分：41 bit

  1. 41 个 bit
  2. 表示时间戳。
  3. 单位是毫秒。
  4. 可以使用69年
可以使用69年的原因

41 bit 可以表示的数字多达 2^41 - 1，也就是可以标识 2 ^ 41 - 1 个毫秒值，换算成年就是表示 69 年的时间。

2.3、第3部分：10 bit

  1. 记录工作的机器 id，代表的是这个雪花算法服务最多可以部署在 2^10 台机器上，也就是 1024 台机器。

  2. 10 bit 里 5 个 bit 代表机房 id，5 个 bit 代表机器 id。意思就是最多代表 2 ^ 5 个机房（32 个机房），每个机房里可以代表 2 ^ 5 个机器（32 台机器），也可以根据自己公司的实际情况确定。

2.3.1、第1部分：5bit

  1. 5 个 bit
  2. 表示机房 id,如上面10001

2.3.2、第2部分：5bit

  1. 5 个 bit
  2. 表示机器id,如上面11001

2.4、第4部分：12 个 bit

  1. 12 个 bit：
  2. 表示序列号
    1. 表示10001机房11001机器上这一毫秒内同时生成的id 的序号
12 个 bit 可以生产多少序列号

12 bit 可以代表的最大正整数是 2 ^ 12= 4096，也就是同一个毫秒内可以生成 4096 个不同的 id。也就是0到4095。

3、总结

3.1、生成唯一 id的过程

假设你的某个服务假设要生成一个全局唯一 id，那么就可以发送一个请求给部署了 SnowFlake 算法的系统，由这个 SnowFlake 算法系统来生成唯一 id。

这个 SnowFlake 算法系统首先肯定是知道自己所在的机房和机器的，比如机房 id = 17，机器 id = 25。

接着 SnowFlake 算法系统接收到这个请求之后，首先就会用二进制位运算的方式生成一个 64 bit 的 long 型id

步骤1： 1bit

给1bit 设置为0

步骤2： 41bit

用当前时间戳（单位到毫秒）生成41bit

步骤3： 5bit

机房 id = 17,生成5bit

步骤4： 5bit

机器 id = 25,生成5bit

步骤5： 12bit

最后再判断一下，当前这台机房的这台机器上这一毫秒内，这是第几个请求，给这次生成 id 的请求累加一个序号，作为最后的 12 个 bit。

最终一个 64 个 bit 的 id 就出来了

这个算法可以保证说，一个机房的一台机器上，在同一毫秒内，生成了一个唯一的 id。可能一个毫秒内会生成多个 id，但是有最后 12 个 bit 的序号来区分开来。

3.2、小结

用一个 64 bit 的数字中各个 bit 位来设置不同的标志位，区分每一个 id。

4、代码

package com.example.snowflake.demo1;

public class SnowFlake {


    /**
     * 起始的时间戳 2016-11-26 21:21:05
     */
    private final static long START_STAMP = 1480166465631L;
    
    /**
     * 每一部分占用的位数
     */
    private final static long SEQUENCE_BIT = 12; // 序列号占用的位数
    private final static long MACHINE_BIT = 5; // 机器标识占用的位数
    private final static long DATA_CENTER_BIT = 5;// 数据中心占用的位数
    
    /**
     * 每一部分的最大值
     * MAX_DATA_CENTER_NUM的计算过程
     *  DATA_CENTER_BIT=5,对应的补码: 0000 0101
     *  -1L对应的补码: 1111 1111
     *  -1L <<5 后:1110 0000
     *  -1L ^ 1110 0000后 0001 1111
     *  0001 1111  等于31
     */

    // 机房的最大id,也就是机房的最大数量
    // 这里是31
    private final static long MAX_DATA_CENTER_NUM = -1L ^ (-1L << DATA_CENTER_BIT);
    // 机器的最大id,也就是机器的最大数量
    // 这里是31
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    // 序列号的最大值
    // 这里是 4095
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
    
    /**
     * 每一部分向左的位移
     */
    // 机器的二进制数据左位移  12位
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    // 机房的二进制数据左位移  17位
    private final static long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    // 时间戳的二进制数据左位移 22位
    private final static long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT;

    // 机房ID,5个bit,最大2^5=32,0到31,即(0000 0000-0001 1111)
    private long dataCenterId;
    // 机器ID,5个bit,最大2^5=32,0到31,即(0000 0000-0001 1111)
    private long machineId;
    // 序列号:12个bit,最大2^12=4096,0到4096,即(0000 0000 0000-1111 1111 1111)
    // 代表一毫秒内生成多少个序号,可以生成4096个,因为第1个0不需要生成。所以真正可以生成4095个
    private long sequence = 0L;
    // 上一次时间戳
    private long lastStamp = -1L;
    
    public SnowFlake(long dataCenterId, long machineId) {
        // 检查机房id是否超过31 不能小于0
        if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) {
            throw new IllegalArgumentException("机房id的id不能超过最大值,也不能为0");
        }
        // 检查机器id是否超过31 不能小于0
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException("机器id的id不能超过最大值,也不能为0");
        }
        // 设置当前机房id
        this.dataCenterId = dataCenterId;
        // 设置当前机器id
        this.machineId = machineId;
    }
    
    /**
     * 让当前这台机器上的snowflake算法程序生成一个全局唯一的id
     * @return
     */
    public synchronized long nextId() {
        // 获得当前时间的毫秒数
        long currStamp = getNewStamp();
        if (currStamp < lastStamp) {
            throw new RuntimeException("服务器的时钟向后移动,拒绝生成id");
        }

        // 假设在同一个毫秒内，又发送了一个请求生成一个id
        // 这个时候就得把seqence序号给递增1，最多就是4095
        if (currStamp == lastStamp) {
            // 相同毫秒内,序列号自增,且保证取值范围最大为MAX_SEQUENCE
            sequence = (sequence + 1) & MAX_SEQUENCE;
            // 同一毫秒的序列数已经达到最大，也就是产生的id数 超过4095，系统会进入等待，直到下一毫秒，系统继续产生ID
            if (sequence == 0L) { // 即：已经超出MAX_SEQUENCE 即：1 0000 0000 0000
                currStamp = getNextMill();
            }
        } else {
            // 不同毫秒内，序列号置为0
            sequence = 0L;
        }

        // 这儿记录一下最近一次生成id的时间戳，单位是毫秒
        lastStamp = currStamp;
        // 这儿就生成一个64bit id的二进制位运算操作

        System.out.println("时间戳:" + (currStamp - START_STAMP));
        System.out.println("时间戳左移位数:" + (TIMESTAMP_LEFT));
        System.out.println("机房id:" + (dataCenterId));
        System.out.println("机房id左移位数:" + (DATA_CENTER_LEFT));
        System.out.println("机器id:" + (machineId));
        System.out.println("机器id左移位数:" + (MACHINE_LEFT));
        System.out.println("序列号:" + (sequence));

        long id = (currStamp - START_STAMP) << TIMESTAMP_LEFT // 时间戳部分
                | dataCenterId << DATA_CENTER_LEFT // 数据中心部分
                | machineId << MACHINE_LEFT // 机器标识部分
                | sequence; // 序列号部分

        System.out.println("id的二进制是:" + Long.toBinaryString(id));
        return id;
    }
    
    /**
     * 获得下一个毫秒数，比lastStamp大的下一个毫秒数
     *
     * @return
     */
    private long getNextMill() {
        long mill = getNewStamp();
        while (mill <= lastStamp) {
            mill = getNewStamp();
        }
        return mill;
    }
    
    /**
     * 获得当前毫秒数
     *
     * @return
     */
    private long getNewStamp() {
        return System.currentTimeMillis();
    }
    
    public static void main(String[] args) {
        SnowFlake snowFlake = new SnowFlake(3L, 10L);
        System.out.println("snowFlake.nextId() = " + snowFlake.nextId());
    }
}

5、sequence = (sequence + 1) & MAX_SEQUENCE的逻辑

5.1、 相同毫秒内,序列号自增 原理

&公式
1&1=1
1&0=0
0&1=0
0&0=0
原理

MAX_SEQUENCE是2^12-1，即 1111 1111 1111。

根据 &公式，我们可以得到，x & 1111 1111 1111，那么结果就是x二进制从右到左的12位，内容都不变，因为1&1=1,0&1=0。

在这里插入图片描述

5.2、 sequence 保证取值范围最大为MAX_SEQUENCE的原理

x二进制从右到左的13位开始，和1111 1111 1111 的& 运算都是都是0，所以最大就是MAX_SEQUENCE

在这里插入图片描述

测试地址
https://www.23bei.com/tool-531.html

6、(currStamp - START_STAMP) << TIMESTAMP_LEFT | dataCenterId << DATA_CENTER_LEFT | machineId << MACHINE_LEFT | sequence 原理

6.1、 为什么要currStamp - START_STAMP) << TIMESTAMP_LEFT

TIMESTAMP_LEFT=22

在这里插入图片描述

6.2、 原理

t=currStamp - START_STAMP
t最大是:2^41-1

假设t=1000

1000的二进制如下(41bit)
0 0000 0000 0000 0000 0000 0000 0000 0011 1110 1000

假设dataCenterId=3

3的二进制如下(5bit)
0 0011

假设machineId=10

10的二进制如下(5bit)
0 1010

假设sequence=10

10的二进制如下(12bit)
0000 0000 0000

因为第1位是0，所以拼接起来id的二进制就是

0000000000000000000000000000000011111010000001101010000000000000
我们通过代码调试结果
时间戳:1000
时间戳左移位数:22
机房id:3
机房id左移位数:17
机器id:10
机器id左移位数:12
序列号:0
id的二进制是:11111010000001101010000000000000
snowFlake.nextId() = 4194738176

在这里插入图片描述

7、优缺点

7.1、优点

  1. 按照时间自增排序，在多个分布式系统内不会产生id碰撞（数据中心+机器id区分）
    1. 毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。
  2. 容量大：理论上QPS约为409.6w/s（1000*2^12）个自增ID。
  3. 高可用：生成时不依赖于数据库，完全在内存中生成。
  4. 灵活性高：可以根据自身业务情况调整分配bit位

7.2、缺点：

强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。
针对此，美团做出了改进：

https://github.com/Meituan-Dianping/Leaf
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

算法

SnowFlake 算法 的相关文章

  • 渲染函数render

    文章目录 节点 树以及虚拟 DOM 树 节点 虚拟 DOM vue中render函数的作用 render函数去创建子组件内容 createElement官方文档 参考 节点 树以及虚拟 DOM 在深入渲染函数之前 了解一些浏览器的工作原理是

  • 2016去哪儿编程题：5-血型遗传检测

    题目描述 血型遗传对照表如下 父母血型 子女会出现的血型 子女不会出现的血型 O与O O A B AB A与O A O B AB A与A A O B AB A与B A B AB O A与AB A B AB O B与O B O A AB B与

随机推荐

  • shell 数组（字符串下标）

    现在游戏开的服务器越来越多了 每次用ssh操作都要写ip地址 很烦 也容易出错 所以要自己搞个服务器名到ip的映射 map anahost count 0 temp cat home linwencai sh HOST while read

  • ubuntu18.04合并pdf文件

    以前使用pdftk比较常见 但是pdftk的更新似乎没有跟上 改用pdfunite轻松解决 pdftk原来使用apt安装 现在改成用snap安装pdftk sudo snap install pdftk pdftk合并命令为 pdftk p

  • 洛谷 P1200 [USACO1.1]你的飞碟在这儿Your Ride Is Here

    题目链接 https www luogu com cn problem P1200 include

  • C++函数基础

    一 函数的定义和使用 1 函数的定义 类型说明符 函数名 含类型说明的形参表 语句序列 如 int GetSum int a int b return a b 2 形式参数 形式参数的作用是实现主函数与被调函数之间的联系 3 函数的返回值和

  • 【ubuntu】ubuntu实体机与windows互传文件（两台电脑）

    先记录一些命令 dpkg list 查看软件列表 sudo apt get purge remove 包名 purge是可选项 写上这个属性是将软件及其配置文件一并删除 如不需要删除配置文件 可执行sudo apt get remove 包

  • Python列表操作中extend和append的区别

    1 用法 append 用于在列表末尾添加新的对象 输入参数为对象 extend 用于在列表末尾追加另一个序列中的多个值 输入对象为元素队列 2 相同点 两个都是对列表即list进行的操作 具体句法可以写为 list1 append obj

  • 解决EXPLORER应用程序错误，桌面出不来

    打开运行 输入CMD 输入for 1 in windir system32 dll do regsvr32 exe s 1 意思是注册所有DLL组件 一般都能解决问题 转载于 https blog 51cto com feifei888 4

  • word文件doc、docx转pdf

    综合类管理系统不管是自研还是外包项目都会被客户或者产品经理要求 实现word导出 excel导出 pdf导出等功能 其实pdf导出呢 有很多种方式 我实现过的就有两种 接下来呢 就说说其中的一种 就是当你已经实现了word导出 或有明确的要

  • 粉丝文化：抖音广告短视频美妆营销中，男明星比女明星更带货？

    1996年 木村拓哉为佳丽宝拍摄了一支口红广告 这条广告轰动一时 代言的口红两个月就卖出了300万支 从此 男明星就成了美妆品牌的宠儿 众多美妆品牌开始启用男明星代言人 男明星为何有如此强力的带货潜力 美妆品牌如何在短视频时代占得先机 抖音

  • 阿里天池比赛——街景字符编码识别

    文章目录 前言 一 街景字符编码识别 1 目标 2 数据集 3 指标 总结 前言 之前参加阿里天池比赛 好久了 一直没有时间整理 现在临近毕业 趁论文外审期间 赶紧把东西整理了 5月底学校就要让我们滚蛋了 哭哭哭 大运会的牺牲品 一 街景字

  • 赛马游戏的java设计_赛马游戏源码

    0 Intro pos g setClip 10 10 HorseMidlet imgIntro 0 getWidth HorseMidlet i mgIntro 0 getHeight g drawImage HorseMidlet im

  • 面试题记1

    希望各位看客们能积极提供答案 1 125874和它的两倍251748 包含着同样的数字 只是顺序不同 找出最小的正整数x 使得2x 3x 4x 5x 和6x都包含有相同的数字 2 求100 各位数之和 3 是用从1到9所有数字 将其任意的连

  • Notion?Roam?OneNote? 不要再用这些垃圾做笔记啦

    双向链接 最近因为Roam Research 双向链接在笔记圈子里火了起来 Notion也在准备做了 那么双向链接是什么呢 我用我的我关于管道的一则笔记给大家讲明白 管道的实现 Linux里 管道实现的原理是 Shell进程先调用pipe创

  • 浅谈 qmake 之 shadow build

    shadow build shadow build 是什么东西 就是将源码路径和构建路径分开 也就是生成的makefile文件和其他产物都不放到源码路径 以此来保证源码路径的清洁 这不是qmake独创的东西 cmake中早就使用这个东西了

  • 性能测试_Day_10（负载测试-获得最大可接受用户并发数）

    目录 如何理解负载测试 如何实现负载测试 jpgc Standard Set插件安装 jpgc Standard Set使用方法 负载测试分析指标 获得最大可接受用户并发数 区间值 负载测试分析指标 获得最大可接受用户并发数 真实值 负载测

  • 阅读论文《Deep Bilateral Learning for Real-Time Image Enhancement》

    这是2017 siggraph的一篇论文 寒假boss让我看这篇论文我没怎么看懂 最近在公司实习 发现该论文的成果已经移到手机端上了 效果还非常不错 这里我重新温习了一下这篇论文 发现有许多可以借鉴的地方 是一篇非常不错的论文 这里重新叙述

  • 我碰到avs错误

    1 写好的avs脚本用播发器不能播放 并且报unexpected chatacter 错误 解决办法 1 尽管avs支持汉语文件路径 但是仍要确认标点符号是否为英文状态下 2 将AVS脚本用记事本打开 重新存为并把编码格式修改成ASNI格式

  • 数值计算方法python实现

    包括 泰勒级数展开 差分逼近微分 二分法求解 试位法求解 迭代法求根 牛顿法求根 正割法 贝尔斯托法多项式求跟 多项式回归 牛顿差商插值 拉格朗日插值法 三次样条插值法 二次样条插值法 高斯消元法 求解线性代数方程组 代码在我的github

  • 事件循环与线程 一

    初次读到这篇文章 译者感觉如沐春风 深刻体会到原文作者是花了很大功夫来写这篇文章的 文章深入浅出 相信仔细读完原文或下面译文的读者一定会有收获 由于原文很长 原文作者的行文思路是从事件循环逐渐延伸到线程使用的讨论 译者因时间受限 暂发表有关

  • SnowFlake 算法

    SnowFlake 算法 1 介绍 是 Twitter 开源的分布式 id 生成算法 核心思想 使用一个 64 bit 的 long 型的数字作为全局唯一 id 2 结构 0 0001000000 0000010000 0001000100

热门标签