如何保证 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符合规则自己的业务特点
- 解决时间回拨的问题。