专栏首页程序员开发者社区如何保证 ID 的全局唯一性?

如何保证 ID 的全局唯一性?

如何保证 ID 的全局唯一性?

分库分表之后如何生成全局唯一的数据库主键呢?

数据库中的主键如何选择?

数据库中的每条记录都需要有一个唯一的标识,根据数据库第二范式,数据库中每个表都需要唯一主键,其他元素和主键一一对应。

一般有两种选择方式:

  • 使用业务字段作为主键,比如用户表来说,可以使用手机号, email ,或者身份证作为主键。
  • 使用唯一 ID 作为主键

如果使用唯一 ID 作为主键,就需要保证 ID 的全局唯一性,如何保证唯生成全局唯一性的ID ?

Snowflake 算法

Snowflake 算法思想是将 64bit 的二进制分成若干,每部分都存储有特定含义:41位时间戳,10位机器码,12位序列号。

pow(2,41) 这样一算,基本上可以使用69年了。

  • 1bit:一般是符号位,不做处理
  • 41bit:用来记录时间戳,这里可以记录69年,如果设置好起始时间比如今年是2018年,那么可以用到2089年,到时候怎么办?要是这个系统能用69年,我相信这个系统早都重构了好多次了。
  • 10bit:10bit用来记录机器ID,总共可以记录1024台机器,一般用前5位代表数据中心,后面5位是某个数据中心的机器ID
  • 12bit:循环位,用来对同一个毫秒之内产生不同的ID,12位可以最多记录4095个,也就是在同一个机器同一毫秒最多记录4095个,多余的需要进行等待下毫秒。
public class SnowflakeIdWorker {
 
    /**
     * 雪花算法解析 结构 snowflake的结构如下(每部分用-分开):
     * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
     * 第一位为未使用,接下来的41位为毫秒级时间(41位的长度可以使用69年),然后是5位datacenterId和5位workerId(10
     * 位的长度最多支持部署1024个节点) ,最后12位是毫秒内的计数(12位的计数顺序号支持每个节点每毫秒产生4096个ID序号)
     * 
     * 一共加起来刚好64位,为一个Long型。(转换成字符串长度为18) 
     * 
     */
 
    // ==============================Fields===========================================
    /** 开始时间截 (2015-01-01) */
    private final long twepoch = 1489111610226L;
 
    /** 机器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("workerId can't be greater than %d or less than 0", maxWorkerId));
        }
        if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
            throw new IllegalArgumentException(String.format("dataCenterId 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));
        }
 
        // 如果是同一时间生成的,则进行毫秒内序列
        // sequenceMask 为啥是4095  2^12 = 4096
        if (lastTimestamp == timestamp) {
            // 每次+1
            sequence = (sequence + 1) & sequenceMask;
            // 毫秒内序列溢出
            if (sequence == 0) {
                // 阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        // 时间戳改变,毫秒内序列重置
        else {
            sequence = 0L;
        }
 
        // 上次生成ID的时间截
        lastTimestamp = timestamp;
 
        // 移位并通过或运算拼到一起组成64位的ID
        // 为啥时间戳减法向左移动22 位 因为  5位datacenterid 
        // 为啥 datCenterID向左移动17位 因为 前面有5位workid  还有12位序列号 就是17位
        //为啥 workerId向左移动12位 因为 前面有12位序列号 就是12位 
        System.out.println(((timestamp - twepoch) << timestampLeftShift) //
                | (dataCenterId << dataCenterIdShift) //
                | (workerId << workerIdShift) //
                | sequence);
        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) {
        System.out.println(System.currentTimeMillis());
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(1, 1);
        long startTime = System.nanoTime();
        for (int i = 0; i < 50000; i++) {
            long id = idWorker.nextId();
            System.out.println(id);
        }
        System.out.println((System.nanoTime() - startTime) / 1000000 + "ms");
    }
}

Snowflake 工程化之后,会有两种实现方式:

  • 嵌入业务代码,也就是分布在业务服务器中,这种方案的好处是业务代码在使用的时候不需要网络调用,性能会比较好,但是这样有个问题, 随着业务服务器的数量变多,很难保证机器 ID 的唯一性。有的方案是采用 数据库自增id ,或者 zookeeper获取唯一的机器ID。
  • 另外一个部署方式是将信号发生器作为独立的服务部署,业务使用信号发生的时候需要多一次网络调用,存在对内网调用性能的损耗,发号器部署实例是有限的,一般可以将机器 ID卸载配置文件里,这样可以保证机器 ID的唯一性。通常单实例单 CPU 可以达到两万每秒。

snowflake 算法可能存在的问题:

依赖系统的时间戳,一旦系统时间不准,会产生重复的ID

如何解决这个问题呢?

  • 时间戳不记录毫秒而是记录秒,通一个时间区间里可以部署多个发号器,避免出现分库分表时分布不均匀。
  • 生成序列号可以使用随机的。

上面的方法主要是两种思路:

  • 让算法中的ID符合规则自己的业务特点
  • 解决时间回拨的问题。

本文分享自微信公众号 - 程序员开发者社区(gh_016ffe40d550),作者:猿星人

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 强引用,软引用,弱引用,幻象引用有什么区别?

    不同的引用类型,主要体现的是对象的不同的可达性(reachable)状态和对垃圾收集的影响。

    王小明_HIT
  • Java 自动拆箱装箱原理

    执行代码时系统为我们执行了 Integer total = Integer.valueOf(99);

    王小明_HIT
  • Java 中 Hashtable 、HashMap 、TreeMap 有什么不同?

    Hashtable 是扩展了 Dictonary 类,类结构上与 HashMap 之类不同,HashMap 继承的是 abstractMap

    王小明_HIT
  • 冷饭新炒:理解Snowflake算法的实现原理

    上图是Snowflake的Github仓库,master分支中的REAEMDE文件中提示:初始版本于2010年发布,基于Apache Thrift,早于Fina...

    Throwable
  • 最常用的分布式ID解决方案

    说起ID,特性就是唯一,在人的世界里,ID就是身份证,是每个人的唯一的身份标识。在复杂的分布式系统中,往往也需要对大量的数据和消息进行唯一标识。举个例子,数据库...

    java乐园
  • 分布式唯一ID生成器Twitter 的 Snowflake idworker java版本

    import java.lang.management.ManagementFactory; import java.net.InetAddress; impo...

    MonroeCode
  • 分布式唯一ID生成器Twitter 的 Snowflake idworker java版本

    import java.lang.management.ManagementFactory; import java.net.InetAddress; impo...

    MonroeCode
  • 漫画:什么是SnowFlake算法?

    UUID是通用唯一识别码 (Universally Unique Identifier),在其他语言中也叫GUID,可以生成一个长度32位的全局唯一识别码。

    用户5927304
  • JAVA:分布式业务系统中,全局ID生成策略

    在实际的开发中,几乎所有的业务场景产生的数据,都需要一个唯一ID作为核心标识,用来流程化管理。比如常见的:

    不会飞的小鸟
  • 架构设计 | 分布式业务系统中,全局ID生成策略

    在实际的开发中,几乎所有的业务场景产生的数据,都需要一个唯一ID作为核心标识,用来流程化管理。比如常见的:

    知了一笑

扫码关注云+社区

领取腾讯云代金券