在分布式系统中,当数据库数据量达到一定量级后,需要进行数据拆分、分库分表操作,传统使用方式的数据库自有的自增特性产生的主键ID已不能满足拆分的需求,它只能保证在单个表中唯一,所以需要一个在分布式环境下都能使用的全局唯一ID。
应用场景
需求分析:
上面列举出11个需求点,已经足够多,当然也可以再增加。安全性和递增性之间存在一定的互斥,需要做取舍。递增性不强求绝对严格递增,即不需要满足+1递增。在做方案设计时,需要具体情况具体分析,前面几个是必须要满足。大体而言,首先确保满足前面几个需求点,即优先级更高,再考虑后面几个。能满足的需求点越多,则方案越复杂,需要加以权衡和取舍,不强求完全实现所有的需求点。
实现方案有很多,不是每种方案都能完美实现上面提到的各个需求点:
基于数据表auto increment
规则来生成全局唯一递增ID。
优点:简单,可保证唯一性、递增性,步长固定
缺点:
改进方法:冗余主库,避免写入单点;数据水平切分,保证各主库生成的ID不重复。
具体来说,比如可将1个写库变成N个写库,每个写库设置不同的auto increment
初始值,和相同的步长,以保证每个数据库生成的ID是不同的。
改进后方案可提高可用性,但拓展性差的问题依旧存在。数据库写压力有所缓解,但写压力依旧存在;可考虑一次性从DB里取出多个ID放在Redis缓存里。
Universally Unique Identifier,标准型式包含32个16进制字符,以连字号分为五段,其形式为8-4-4-4-12,到目前为止业界一共有5种方式生成UUID,参考IETF发布的UUID规范:
UUID-v1是通过使用主机MAC地址和当前日期和时间的组合生成的。之外还引入另一个随机组件,以确保其唯一性。但是如果使用同一台机器、同时时间生成UUID,会有很小的几率重复。
UUID-v1存在的问题是:
UUID-v2和v1很类似,是根据标识符(通常是组或用户ID)、时间和节点ID生成,区别在于v2将v1中的部分时间信息换成主机名, 存在隐私风险,未大规模使用。
UUID-v3通过MD5散列算法基于命名空间标识符和名称生成UUID。和v1、v2不同,v3不依赖与机器信息和时间信息,但v3要求输入命名空间+名称,命名空间本身也是一个UUID,用来标识应用环境,名称通常是用户账号、用户名之类的内容,通过命名空间+名称+三列算法算出UUID。
UUID-v5和v3类似,区别在于使用sha1散列算法。
基于随机数的算法。用SecureRandom生成16个随机的Byte,用2个long来存储。记得加-Djava.security.egd=file:/dev/./urandom
,
JDK里UUID.randomUUID
静态方法使用加密强度高的伪随机数生成器生成v4伪随机UUID:
public static UUID randomUUID() {
SecureRandom ng = Holder.numberGenerator;
byte[] randomBytes = new byte[16];
ng.nextBytes(randomBytes);
randomBytes[6] &= 0x0f; /* clear version */
randomBytes[6] |= 0x40; /* set to version 4 */
randomBytes[8] &= 0x3f; /* clear variant */
randomBytes[8] |= (byte) 0x80; /* set to IETF variant */
return new UUID(randomBytes);
}
JDK提供UUID.randomUUID
静态方法从字节数组生成基于名称的v3版本的UUID:
public static UUID nameUUIDFromBytes(byte[] name) {
MessageDigest md;
try {
md = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException nsae) {
throw new InternalError("MD5 not supported", nsae);
}
byte[] md5Bytes = md.digest(name);
md5Bytes[6] &= 0x0f; /* clear version */
md5Bytes[6] |= 0x30; /* set to version 3 */
md5Bytes[8] &= 0x3f; /* clear variant */
md5Bytes[8] |= (byte) 0x80; /* set to IETF variant */
return new UUID(md5Bytes);
}
基于hibernate-core-6.4.4.Final
版本的CustomVersionOneStrategy源码如下:
public class CustomVersionOneStrategy implements UUIDGenerationStrategy, UuidGenerator.ValueGenerator {
private final long mostSignificantBits;
public int getGeneratedVersion() {
return 1;
}
public CustomVersionOneStrategy() {
byte[] hiBits = new byte[8];
System.arraycopy(Helper.getAddressBytes(), 0, hiBits, 0, 4);
System.arraycopy(Helper.getJvmIdentifierBytes(), 0, hiBits, 4, 4);
hiBits[6] = (byte)(hiBits[6] & 15);
hiBits[6] = (byte)(hiBits[6] | 16);
this.mostSignificantBits = BytesHelper.asLong(hiBits);
}
public UUID generateUuid(SharedSessionContractImplementor session) {
long leastSignificantBits = generateLeastSignificantBits(System.currentTimeMillis());
return new UUID(this.mostSignificantBits, leastSignificantBits);
}
public UUID generateUUID(SharedSessionContractImplementor session) {
return this.generateUuid(session);
}
public long getMostSignificantBits() {
return this.mostSignificantBits;
}
public static long generateLeastSignificantBits(long seed) {
byte[] loBits = new byte[8];
short hiTime = (short)((int)(seed >>> 32));
int loTime = (int)seed;
System.arraycopy(BytesHelper.fromShort(hiTime), 0, loBits, 0, 2);
System.arraycopy(BytesHelper.fromInt(loTime), 0, loBits, 2, 4);
System.arraycopy(Helper.getCountBytes(), 0, loBits, 6, 2);
loBits[0] = (byte)(loBits[0] & 63);
loBits[0] = (byte)(loBits[0] | 128);
return BytesHelper.asLong(loBits);
}
}
解读:
MongoDB的bson-4.11.1
版本下ObjectId的源码:
public final class ObjectId implements Comparable<ObjectId>, Serializable {
private static final AtomicInteger NEXT_COUNTER = new AtomicInteger((new SecureRandom()).nextInt());
public ObjectId() {
this(new Date());
}
public ObjectId(Date date) {
this(dateToTimestampSeconds(date), NEXT_COUNTER.getAndIncrement() & 16777215, false);
}
private static int dateToTimestampSeconds(Date time) {
return (int)(time.getTime() / 1000L);
}
}
解读:
0xFFFFFF
。机器标识符是一个3字节的值,而16777215是3字节整数的最大值。这意味着机器标识符的范围是0到16777215,确保可以使用一个唯一的标识符来表示每台机器。ObjectId使用12字节的存储空间:
前9个字节保证同一秒钟不同机器不同进程产生的ObjectId的唯一性。后三个字节是一个自动增加的计数器(一个mongod进程需要一个全局的计数器),保证同一秒的ObjectId是唯一的。同一秒钟最多允许每个进程拥有(256^3=16777216)个不同的ObjectId。
ObjectId用于文档的主键_id
字段,_id
可在服务端、客户端生成,在客户端生成可以降低服务器端的压力。
缺点:
优点:性能非常高,本地生成,没有远程调用等网络消耗,时延低。
标准的UUID算法使用场景不多,改进版如MongoDB的ObjectId,可用于生产实践中。
参考GitHub。Twitter在把存储系统从MySQL迁移到Cassandra的过程中,由于Cassandra没有顺序ID生成机制,于是自己开发一套全局唯一ID生成服务。
共64位二进制:
如果序列号超过最大值,则会将程序阻塞到下一毫秒,然后序列号归零,继续生成ID。要想Snowflake生成全局唯一的ID,则ID生成器必须也是全局单例。
Snowflake对ZooKeeper的依赖性:集群节点启动时,从一个ZooKeeper集群获取,保证所有节点不会有重复的机器号
代码:
public class SnowflakeIdWorker {
/**
* 机器id所占的位数
*/
private final long workerIdBits = 5L;
/**
* 数据标识id所占的位数
*/
private final long datacenterIdBits = 5L;
/**
* 工作机器ID(0~31)
*/
private final long workerId;
/**
* 数据中心ID(0~31)
*/
private final long datacenterId;
/**
* 序列ID位数
*/
private static final long sequenceBits = 12L;
/**
* 毫秒内序列(0~4095)
*/
private long sequence = 0L;
/**
* 上次生成ID的时间截
*/
private long lastTimestamp = -1L;
/**
* 构造函数
*/
public SnowflakeIdWorker(long workerId, long datacenterId) {
// 支持的最大机器id,结果是31 (这个移位算法可以很快地计算出几位二进制数所能表示的最大十进制数)
long maxWorkerId = ~(-1L << workerIdBits);
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
}
// 支持的最大数据标识id,结果是31
long maxDatacenterId = ~(-1L << datacenterIdBits);
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(线程安全)
*/
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));
}
// 如果是同一时间生成的,则进行毫秒内序列
if (lastTimestamp == timestamp) {
// 生成序列的掩码,这里为4095 (0b111111111111=0xfff=4095)
long sequenceMask = ~(-1L << sequenceBits);
sequence = (sequence + 1) & sequenceMask;
// 毫秒内序列溢出
if (sequence == 0) {
// 阻塞到下一个毫秒,获得新的时间戳
timestamp = tilNextMillis(lastTimestamp);
}
} else {
// 时间戳改变,毫秒内序列重置
sequence = 0L;
}
// 上次生成ID的时间截
lastTimestamp = timestamp;
// 移位并通过或运算拼到一起组成64位的ID
// 开始时间截(2024-01-01)
long startEpoch = 1704038400000L;
// 数据标识id向左移17位(12+5)
long datacenterIdShift = sequenceBits + workerIdBits;
// 时间截向左移22位(5+5+12)
long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
return ((timestamp - startEpoch) << timestampLeftShift)
| (datacenterId << datacenterIdShift)
| (workerId << sequenceBits)
| sequence;
}
/**
* 阻塞到下一个毫秒,直到获得新的时间戳
*
* @param lastTimestamp 上次生成ID的时间截
* @return 当前时间戳
*/
protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
/**
* 返回以毫秒为单位的当前时间
*/
protected long timeGen() {
return System.currentTimeMillis();
}
}
如何分配datacenterId和workerId呢?
存在的问题:
时钟回拨问题
获取到的当前Timestamp比前一个已生成ID的Timestamp还要小。做法是while循环,继续获取当前机器的时间,直到获取到更大的Timestamp才能继续工作,在这个等待过程中不能分配出新的ID。
解决方法
使用NTP(Network Time Protocol)确保系统时钟是准确的。最好把NTP配置成不会向后调整的模式。即NTP纠正时间时,不会向后回拨机器时钟。
基于Redis的原子操作INCR和INCRBY来实现,与数据库改进版类似,Redis采用集群化部署方案,每个节点设置一个不同的初始值,步长保持一致。且可以预生成一批ID,提高性能。
业界最常用的解决方案是基于Snowflake的改进版。
Flake: A decentralized, k-ordered id generation service in Erlang
几点变化:
目的是用更多的位实现更小的冲突概率,且能支持更多的Worker同时工作,每毫秒能分配出更多的ID。
Instagram的分布式存储方案:
Instagram unique ID组成:
SN利用PostgreSQL表的自增序列(sequence)来生成:如果当前表上已经有5000条记录,则这个表的下一个自增序列就是5001(直接调用PG提供的方法可以获取到),然后把这个5001对1024取模就得到10位的SN。
优势在于:
美团-点评开源的Leaf。
百度开源的UidGenerator。
Flyway是一款开源的数据库版本管理工具,其源码里有对Snowflake的支持:
有待进一步研究。
https://github.com/zhuzhong/idleaf
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。