架构视界
主页
企业架构
  • 方案总览
  • 业财一体
  • 企业中台
  • 组织与绩效
  • 流程治理
数据收集与分析
  • 转型总览
  • 信息化阶段
  • 数字化解决方案
  • 智数化解决方案
  • 智能化解决方案
  • 产品设计
  • 项目管理
全栈软件工程
AI 原生软件工程
方法论
博客
  • 资源导航
  • 效率工具
  • 展示专区
主页
企业架构
  • 方案总览
  • 业财一体
  • 企业中台
  • 组织与绩效
  • 流程治理
数据收集与分析
  • 转型总览
  • 信息化阶段
  • 数字化解决方案
  • 智数化解决方案
  • 智能化解决方案
  • 产品设计
  • 项目管理
全栈软件工程
AI 原生软件工程
方法论
博客
  • 资源导航
  • 效率工具
  • 展示专区
  • 标签索引
  • 2024年

    • 勇闯大A:美债与美元周期
    • 勇闯大A:交易纪律与自我管理
    • 勇闯大A:交易系统分层
    • 勇闯大A:买卖点与止损规则
    • 勇闯大A:债券与资金流向
    • 勇闯大A:微观、宏观与周期
    • Mac 开发环境:新机配置清单
    • 勇闯大A:内外盘与换手率
    • 会计管理:财报阅读与管理报表
    • 会计基础:记账原理与分录
    • 财务入门:财务体系全景
  • 2023年

    • 境外投资:泰国 BOI 申请实务
  • 2022年

    • 企业架构:故障管理与分级响应
    • 企业架构:技术债务的识别、度量与偿还
  • 2021年

    • Python 数据分析:员工分布可视化
    • Python 数据分析:IP 访问折线图
    • Python 数据分析:IP 词云图
    • Redis:RediSearch 全文检索
    • Rust 基础:第一个 CLI 程序
    • Rust 基础:所有权机制
    • Rust 基础:函数与控制流
    • Rust 基础:变量与数据类型
    • Rust 基础:入门与开发环境
    • 企业架构:分布式系统设计
    • 企业架构:编程式权限设计
    • JVM 调优:启动参数与 GC 日志
    • MyBatis 批量插入:三种写法对比
    • 测试:Spring Boot 分层 Mock
    • Redis:布隆过滤器判断元素存在
    • Jenkins:安装配置与应用部署
    • WebClient:非阻塞 HTTP 客户端
    • Drone:Docker 部署轻量 CI
    • Spring AOP:操作审计日志落库
    • Redisson:分布式锁与 RedLock
    • MyBatis 拦截器:雪花算法主键
    • Netty:线程模型与网络编程
    • Redis:SCAN 游标遍历大键空间
    • Jenkins:单机部署与升级脚本
    • Mac:Neo4j 与 Jupyter 安装
    • JavaFX:OpenJDK 11 环境配置
    • Mac:用 jenv 管理 JDK 版本
    • Redis:有序集合实现延时队列
    • Spring Boot 日志:MDC 串联链路
    • 定时任务:Spring 调度与 Cron
    • GoAccess:Nginx 日志分析
    • MyBatis 拦截器:慢 SQL 分析
    • Lucene:倒排索引与中文分词
    • 分布式锁:三种实现方案对比
    • 学习技巧:减少学习排斥心理
    • 动态数据源:多租户数据路由
    • Compose:Spring Boot 三件套
    • Java 阻塞队列:源码与用法
    • Redis:Docker Compose 哨兵
    • Redis:Docker Compose 主从
    • 网络通信:TCP/IP 与 HTTP 基础
  • 2020年

    • 延时队列:DelayQueue 与 Redis 实现
    • MySQL 基础:员工库导入实践
    • 雪花算法:分布式 ID 生成
    • Redis:地理位置查询
    • 抓包:Wireshark 与 Tcpdump
    • SPI:JDK 与 Spring 扩展机制
    • ZooKeeper:概念与集群搭建
    • Spring Boot:集成 JMH 基准测试
    • Wireshark:抓包工具入门
    • Compose:Redis 与 MySQL
    • CentOS 7:Docker 安装部署
    • Netty:源码阅读环境搭建
    • MySQL 基础:SQL 常见用法
    • CentOS 7:Selenium 运行环境
    • Nginx:HTTPS 证书配置
    • JMH:基准测试与 Spring Boot 集成
    • Spring Boot:指定 Tomcat 版本
    • Eureka:实例上下线告警
    • 钉钉告警:应用异常与实例上下线
    • JVM:内存布局、类加载与调优
    • Git:rebase 合并多次提交
    • CentOS 7:OpenResty 部署
  • 2019年

    • Redis CLI:macOS 安装与使用
    • Nginx:访问日志格式
    • 工程规范:可维护代码的写法
    • IntelliJ IDEA:常用插件
    • SkyWalking:源码阅读环境搭建
    • Spring Boot:Redis 超时配置
    • gRPC:ProtoBuf 定义与代码生成
    • Arthas:Java 线上问题诊断
    • Redis:缓存穿透与击穿防护
    • Docker 部署:Elasticsearch
    • Docker 部署:MySQL 5.7 单机
    • Spring Redis:字符串命令封装
    • Docker 部署:ZooKeeper 运行
    • Docker 部署:Redis 单机运行
    • Dubbo:Spring Boot 微服务集成
    • CentOS 7:CMake 源码编译安装
    • 性能度量:吞吐量与 QPS 指标
    • Java 递归:从笔试题到经典问题
    • CentOS 7:ELK 日志平台部署
    • CentOS 7:SonarQube 部署
    • Selenium:Chrome 浏览器自动化
    • JJWT:令牌生成与解析测试
    • Spring 源码:阅读环境搭建
    • JUnit 4:注解、断言与参数化
    • JWT:令牌结构与签名机制
    • FastDFS:架构与文件存取机制
    • XPath:XML 文档节点定位
    • Redis 基础:锁、队列与事务
    • Redis 基础:数据类型与命令
    • MyBatis:Slf4j 日志接入
    • MyBatis:H2 单元测试与 SQL 日志
    • 源码阅读:开源项目环境搭建
    • Git 配置:命令清单与作用域
    • Java 核心:面向对象与基础类型
    • Java 核心:关键字、异常与反射
    • Java 核心:多线程基础
    • Java 核心:同步关键字与线程池
    • Java 核心:锁与并发工具
    • Java 核心:语言基础与并发
    • Dubbo:远程调用与服务治理
    • Java 集合:框架总览与实现对比
    • Maven:生命周期与常用命令
    • MyBatis:执行流程与插件机制
    • Spring:IoC 容器与依赖注入
    • Spring:AOP 与自动装配
    • Spring:事务与启动流程
    • Spring:IoC、AOP 与事务
    • Spring MVC:请求分发与注解
    • MySQL:架构与索引
    • MySQL:事务、锁与 MVCC
    • MySQL:日志与 SQL 优化
    • MySQL:架构、事务与优化
    • Redis 基础:持久化与线程模型
  • 2018年

    • Java HashMap:扩容机制与哈希冲突
    • Java 集合:HashSet 去重原理
    • Java 基础:交换两个变量的值
    • Spring MVC:零 web.xml 改造
    • Mac 开发环境:新机配置清单
    • Log4j:日志分级与按业务拆分
    • Modbus:工业通信协议与 RTU 帧
    • MySQL 基础:子查询与连接查询
    • MySQL 基础:库与表操作
    • MySQL 基础:表操作与查询
    • MySQL 基础:约束、引擎与数据类型
    • MySQL 基础:库表、约束与类型
    • Java 集合:Vector 与 Stack
    • Java 集合:Vector 与 Stack
    • RabbitMQ:CentOS 7 单机部署
    • Redis:CentOS 7 单机部署
    • MongoDB:CentOS 7 单机部署
    • Linux:常用系统与运维命令
    • 注册中心:Eureka 与 ZooKeeper
    • MySQL:CentOS 7 单机部署
    • Git 分支:主分支与临时分支
    • CentOS 7:Java 开发环境部署
    • Java 集合:LinkedList 双向链表
    • Java 集合:ArrayList 动态数组
    • Spring AOP:注解方式实现切面
← 返回博客

雪花算法:分布式 ID 生成

2020年12月27日 #企业架构 #Java

Snowflake,雪花算法是由Twitter开源的分布式ID生成算法,以划分命名空间的方式将 64-bit位分割成多个部分,每个部分代表不同的含义。这种就是将64位划分为不同的段,每段代表不同的涵义,基本就是时间戳、机器ID和序列数,当然这种方案就是需要考虑时钟回拨的问题以及做一些 buffer的缓冲设计提高性能。

背景

Twitter 早期用 MySQL 存储数据,随着用户的增长,单一的 MySQL 实例没法承受海量的数据,开发团队就开始用 Cassandra 和 sharded MySQL 替代原有的系统。然而和 MySQL 不同的是,Cassandra 没有内置为每一条数据生成唯一 ID 的功能,因为在一个分布式环境下,很难有完美的 ID 生成方案。

  • 对于 Twitter 而言,这样的 ID 生成方案要满足两个基本的要求,一是每秒能生成几十万条 ID 用于标识不同的 tweet;二是这些 ID 应该可以有个大致的顺序,也就是说发布时间相近的两条 tweet,它们的 ID 也应当相近,这样才能方便各种客户端对 tweet 进行排序。
  • 第一个要求意味着 ID 生成要以一种非协作的(uncoordinated)的方式进行,例如不能有一个全局的原子变量。
  • 第二个要求使得 tweet 按 ID 排序后满足 k-sorted 条件。如果序列 A 要满足 k-sorted,当且仅当对于任意的 p, q,如果 1 <= p <= q - k (1 <= p <= q <= n),则有 A[p] <= A[q]。换句话说,如果元素 p 排在 q 前面,且相差至少 k 个位置,那么 p 必然小于或等于 q。如果 tweet 序列满足这个条件,要获取第 r 条 tweet 之后的消息,只要从第 r - k 条开始查找即可。
  • Twitter 解决这两个问题的方案非常简单高效:每一个 ID 都是 64 位数字,由时间戳、节点号和序列编号组成。其中序列编号是每个节点本地生成的序号,而节点号则由 ZooKeeper 维护。

  • 官网给出的代码是scala写出来的代码。
  • 1bit,不用,因为二进制中最高位是符号位,1表示负数,0表示正数。生成的id一般都是用整数,所以最高位固定为0。
  • 41bit-时间戳,用来记录时间戳,毫秒级。
    • 41位可以表示2^41-1个数字, - 如果只用来表示正整数(计算机中正数包含0),可以表示的数值范围是:0 至 2^41-1,减1是因为可表示的数值范围是从0开始算的,而不是1。 - 也就是说41位可以表示2^41-1个毫秒的值,转化成单位年则是(2^{41}-1) / (1000 * 60 * 60 * 24 *365) = 69年
  • 10bit-工作机器id,用来记录工作机器id。
    • 可以部署在2^{10} = 1024个节点,包括5位datacenterId和5位workerId
    • 5位(bit)可以表示的最大正整数是2^{5}-1 = 31,即可以用0、1、2、3、....31这32个数字,来表示不同的datecenterId或workerId
  • 12bit-序列号,序列号,用来记录同毫秒内产生的不同id。 - 12位(bit)可以表示的最大正整数是2^{12}-1 = 4095,即可以用0、1、2、3、....4094这4095个数字,来表示同一机器同一时间截(毫秒)内产生的4095个ID序号。

Java实现

由于在Java中64bit的整数是long类型,所以在Java中SnowFlake算法生成的id就是long来存储的。

  • 所有id生成按照时间趋势递增
  • 理论上分布式系统不会生产重复id(因为有datacenterId和workerId来做区分)

pom依赖

<dependencies>
        <!-- JMH基准测试 -->
        <dependency>
            <groupId>org.openjdk.jmh</groupId>
            <artifactId>jmh-core</artifactId>
            <version>1.21</version>
            <scope>test</scope>
        </dependency>
        <dependency>
            <groupId>org.openjdk.jmh</groupId>
            <artifactId>jmh-generator-annprocess</artifactId>
            <version>1.21</version>
            <scope>test</scope>
        </dependency>

        <!-- 单元测试 -->
        <dependency>
            <groupId>org.junit.jupiter</groupId>
            <artifactId>junit-jupiter-api</artifactId>
            <version>5.7.1</version>
            <scope>test</scope>
        </dependency>
        <dependency>
            <groupId>org.junit.jupiter</groupId>
            <artifactId>junit-jupiter-engine</artifactId>
            <version>5.7.1</version>
            <scope>test</scope>
        </dependency>
    </dependencies>

Java代码

package cn.z201.example;

import java.time.Clock;

/**
 * @author z201.coding@gmail.com
 **/
public class SnowflakeDistributeId {

    /**
     * 开始时间截,这里用系统的时间戳
     */
    private final long startTime = 1420041600000L;

    /**
     * 机器id所占的位数 5 位
     */
    private final static long WORKER_ID_BITS = 5L;
    /**
     * 序列在id中占的位数
     */
    private final static long SEQUENCE_BITS = 12L;
    /**
     * 数据标识id所占的位数
     */
    private final long DATA_CENTER_ID_BITS = 5L;

    /**
     * 数据中心最大数量。支持的最大机器id,结果是31 (这个移位算法可以很快计算出几位二进制数所能表示的最大十进制数)
     */
    private final long maxWorkerId = -1L ^ (-1L << WORKER_ID_BITS); //

    /**
     * 支持的最大数据标识id,结果是31
     */
    private final long maxDatacenterId = -1L ^ (-1L << DATA_CENTER_ID_BITS);

    /**
     * 机器ID向左移12位
     */
    private final long workerIdShift = SEQUENCE_BITS;

    /**
     * 数据标识id向左移17位(12+5)
     */
    private final long datacenterIdShift = SEQUENCE_BITS + WORKER_ID_BITS;

    /**
     * 时间截向左移22位(5+5+12)
     */
    private final long timestampLeftShift = SEQUENCE_BITS + WORKER_ID_BITS + DATA_CENTER_ID_BITS;

    /**
     * 生成序列的掩码,这里为4095 (0b111111111111=0xfff=4095)
     */
    private final long sequenceMask = -1L ^ (-1L << SEQUENCE_BITS);

    /**
     * 工作机器ID(0~31)
     */
    private long workerId;

    /**
     * 数据中心ID(0~31)
     */
    private long datacenterId;

    /**
     * 毫秒内序列(0~4095)
     */
    private long sequence = 0L;

    /**
     * 上次生成ID的时间截
     */
    private long lastTimestamp = -1L;

    /**
     * 禁止参的构造,规避创建对象时候使用默认的机器码
     */
    private SnowflakeDistributeId() {
    }

    /**
     * 构造函数
     *
     * @param workerId     工作ID (0~31)
     * @param datacenterId 数据中心ID (0~31)
     */
    public SnowflakeDistributeId(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;
    }

    /**
     * 获得下一个ID (该方法是线程安全的)
     *
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = Clock.systemDefaultZone().millis();
        //如果当前时间小于上一次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 - startTime) << timestampLeftShift) // 时间戳部分
                | (datacenterId << datacenterIdShift) // 数据中心部分
                | (workerId << workerIdShift) // 机器标识符部分
                | sequence; // 序列号部分
    }

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


}

JMH基准测试

package cn.z201.example;

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.results.format.ResultFormatType;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

import java.util.concurrent.TimeUnit;

public class SnowflakeDistributeIdTest {

    private final static Integer MEASUREMENT_ITERATIONS = 1;
    private final static Integer WARMUP_ITERATIONS = 10;

    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                // 设置类名正则表达式基准为搜索当前类
                .include("\\." + SnowflakeDistributeIdTest.class.getSimpleName() + "\\.")
                // 都是一些基本的参数,可以根据具体情况调整。一般比较重的东西可以进行大量的测试,放到服务器上运行。
                .warmupIterations(WARMUP_ITERATIONS) // 多少次预热
                .measurementIterations(MEASUREMENT_ITERATIONS) // 要做多少次测量m
                .timeUnit(TimeUnit.MILLISECONDS) // 毫秒
                // 不使用多线程
                .forks(1) // 进行 fork 的次数。如果 fork 数是2的话,则 JMH 会 fork 出两个进程来进行测试。
                .threads(1) // 每个进程中的测试线程,这个非常好理解,根据具体情况选择,一般为cpu乘以2。
                // Throughput 整体吞吐量,例如”1秒内可以执行多少次调用”。
                // AverageTime: 调用的平均时间,例如”每次调用平均耗时xxx毫秒”。
                // SampleTime: 随机取样,最后输出取样结果的分布,例如”99%的调用在xxx毫秒以内,99.99%的调用在xxx毫秒以内”
                // SingleShotTime: 以上模式都是默认一次 iteration 是 1s,唯有 SingleShotTime 是只运行一次。往往同时把 warmup 次数设为0,用于测试冷启动时的性能。
                // All(“all”, “All benchmark modes”);
                .mode(Mode.AverageTime)
                .shouldDoGC(true)
                .shouldFailOnError(true)             //
                .resultFormat(ResultFormatType.JSON) // 输出格式化
//                .result("/dev/null") // set this to a valid filename if you want reports
                .result("benchmark.log")
                .shouldFailOnError(true)
                .jvmArgs("-server")
                .build();
        new Runner(opt).run();
    }

    /**
     * Benchmark 方法级注解,表示该方法是需要进行 benchmark 的对象,用法和 JUnit 的 @Test 类似。
     */
    @Benchmark
    public void testSnowflakeDistributeId() {
        SnowflakeDistributeId idWorker = new SnowflakeDistributeId(0, 0);
        for (int i = 0; i < 1000000; i++) {
            long id = idWorker.nextId();
        }
    }
}
  • Console
[
    {
        "jmhVersion" : "1.21",
        "benchmark" : "cn.z201.example.SnowflakeDistributeIdTest.testSnowflakeDistributeId",
        "mode" : "avgt",
        "threads" : 1,
        "forks" : 1,
        "jvm" : "/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/bin/java",
        "jvmArgs" : [
            "-server"
        ],
        "jdkVersion" : "1.8.0_275",
        "vmName" : "OpenJDK 64-Bit Server VM",
        "vmVersion" : "25.275-b01",
        "warmupIterations" : 10,
        "warmupTime" : "10 s",
        "warmupBatchSize" : 1,
        "measurementIterations" : 1,
        "measurementTime" : "10 s",
        "measurementBatchSize" : 1,
        "primaryMetric" : {
            "score" : 244.1343217804878,
            "scoreError" : "NaN",
            "scoreConfidence" : [
                "NaN",
                "NaN"
            ],
            "scorePercentiles" : {
                "0.0" : 244.1343217804878,
                "50.0" : 244.1343217804878,
                "90.0" : 244.1343217804878,
                "95.0" : 244.1343217804878,
                "99.0" : 244.1343217804878,
                "99.9" : 244.1343217804878,
                "99.99" : 244.1343217804878,
                "99.999" : 244.1343217804878,
                "99.9999" : 244.1343217804878,
                "100.0" : 244.1343217804878
            },
            "scoreUnit" : "ms/op",
            "rawData" : [
                [
                    244.1343217804878
                ]
            ]
        },
        "secondaryMetrics" : {
        }
    }
]

  • 生成比较平稳。还没测试在多线程情况下的效果。

小结

64 位 ID 由 41 位毫秒时间戳、10 位机器标识与 12 位序列组成,单机每毫秒上限 4095 个,时间戳可用约 69 年。实现遇时钟回拨直接抛异常,百万次单线程约 244ms。

最近更新: 2026/11/20 22:16
Contributors: 庆峰
Prev
MySQL 基础:员工库导入实践
Next
Redis:地理位置查询