目录
1)为什么要要同步ID
2)同步ID生成方式有哪些
3)游戏中ID需求及代码实现
1、为什么要同步ID
在游戏服务器中,id往往是我们唯一的标识,它有可能是我们存入map容器中的key,有可能是我们存入数据库中的唯一索引,甚至更过分的是,落入数据库中也是唯一的,也就是希望数据落入到数据库中记录永远是唯一性记录,哪怕是不同的数据库,我们知道游戏服务器往往是分很多组,不同组之间往往数据是割裂开来,有时我们需要对数据库进行合并(或合服),那么合并是d的唯一性就至关重要,并且这是一个很容易出错的工程。账号、道具、任务等ID,这些关键数据的ID有可能牵扯到N张数据表格,对数据库数据一一修改就非常的繁琐。有时我们希望玩家获得物品能够全服交易,没有全服同步id这种交易就不是那么好实现。
2、同步id生成的方式有哪些:
1、数据库特性实现 ID
2、ID生成中心
3、Java唯一uuid
4、雪花算法及变种
1)数据库特性实现
通过数据库的特性实现,数据库可是设置字段自增,利用数据库特性,这种方式实现方式需要数据库的配合,并且需要自增成功的返回。当然也可能通过redis的分布式锁来实现也是可以的。不管以上两种利用那种情况它们的平均速度都取决于数据库本身并发能力
2)ID生成中心
ID生成中心是通过单独进程来确定唯一性,由单独的进程来生成ID,这种生成方式是性能比较高,分配ID的效率取决网络延迟,当然可以批量分配来解决减少与ID中心的交互。开始就为某个需要ID的进程分配一个可用的ID区间,当需要ID进程快将ID耗尽时在一次分配,如此重复。ID中心会把每次分配ID数据落入到数据库或能够持久化的缓存,这样即使进程宕机也不会出现ID冲突问题
3)java uuid生成
Java原生API提供UUID生成方法,全球唯一标识,uuid 生成是16个字节,Java UUID代码如下:
package java.util; import java.io.Serializable; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; import java.security.SecureRandom; import jdk.internal.misc.JavaLangAccess; import jdk.internal.misc.SharedSecrets; public final class UUID implements Serializable, Comparable{ private static final long serialVersionUID = -4856846361193249489L; private final long mostSigBits; private final long leastSigBits; private static final JavaLangAccess jla = SharedSecrets.getJavaLangAccess(); private UUID(byte[] data) { long msb = 0L; long lsb = 0L; assert data.length == 16 : "data must be 16 bytes in length"; int i; for(i = 0; i < 8; ++i) { msb = msb << 8 | (long)(data[i] & 255); } for(i = 8; i < 16; ++i) { lsb = lsb << 8 | (long)(data[i] & 255); } this.mostSigBits = msb; this.leastSigBits = lsb; } public UUID(long mostSigBits, long leastSigBits) { this.mostSigBits = mostSigBits; this.leastSigBits = leastSigBits; } public static UUID randomUUID() { SecureRandom ng = UUID.Holder.numberGenerator; byte[] randomBytes = new byte[16]; ng.nextBytes(randomBytes); randomBytes[6] = (byte)(randomBytes[6] & 15); randomBytes[6] = (byte)(randomBytes[6] | 64); randomBytes[8] = (byte)(randomBytes[8] & 63); randomBytes[8] = (byte)(randomBytes[8] | 128); return new UUID(randomBytes); } public static UUID nameUUIDFromBytes(byte[] name) { MessageDigest md; try { md = MessageDigest.getInstance("MD5"); } catch (NoSuchAlgorithmException var3) { throw new InternalError("MD5 not supported", var3); } byte[] md5Bytes = md.digest(name); md5Bytes[6] = (byte)(md5Bytes[6] & 15); md5Bytes[6] = (byte)(md5Bytes[6] | 48); md5Bytes[8] = (byte)(md5Bytes[8] & 63); md5Bytes[8] = (byte)(md5Bytes[8] | 128); return new UUID(md5Bytes); } public static UUID fromString(String name) { int len = name.length(); if (len > 36) { throw new IllegalArgumentException("UUID string too large"); } else { int dash1 = name.indexOf(45, 0); int dash2 = name.indexOf(45, dash1 + 1); int dash3 = name.indexOf(45, dash2 + 1); int dash4 = name.indexOf(45, dash3 + 1); int dash5 = name.indexOf(45, dash4 + 1); if (dash4 >= 0 && dash5 < 0) { long mostSigBits = Long.parseLong(name, 0, dash1, 16) & 4294967295L; mostSigBits <<= 16; mostSigBits |= Long.parseLong(name, dash1 + 1, dash2, 16) & 65535L; mostSigBits <<= 16; mostSigBits |= Long.parseLong(name, dash2 + 1, dash3, 16) & 65535L; long leastSigBits = Long.parseLong(name, dash3 + 1, dash4, 16) & 65535L; leastSigBits <<= 48; leastSigBits |= Long.parseLong(name, dash4 + 1, len, 16) & 281474976710655L; return new UUID(mostSigBits, leastSigBits); } else { throw new IllegalArgumentException("Invalid UUID string: " + name); } } } public long getLeastSignificantBits() { return this.leastSigBits; } public long getMostSignificantBits() { return this.mostSigBits; } public int version() { return (int)(this.mostSigBits >> 12 & 15L); } public int variant() { return (int)(this.leastSigBits >>> (int)(64L - (this.leastSigBits >>> 62)) & this.leastSigBits >> 63); } public long timestamp() { if (this.version() != 1) { throw new UnsupportedOperationException("Not a time-based UUID"); } else { return (this.mostSigBits & 4095L) << 48 | (this.mostSigBits >> 16 & 65535L) << 32 | this.mostSigBits >>> 32; } } public int clockSequence() { if (this.version() != 1) { throw new UnsupportedOperationException("Not a time-based UUID"); } else { return (int)((this.leastSigBits & 4611404543450677248L) >>> 48); } } public long node() { if (this.version() != 1) { throw new UnsupportedOperationException("Not a time-based UUID"); } else { return this.leastSigBits & 281474976710655L; } } public String toString() { return jla.fastUUID(this.leastSigBits, this.mostSigBits); } public int hashCode() { long hilo = this.mostSigBits ^ this.leastSigBits; return (int)(hilo >> 32) ^ (int)hilo; } public boolean equals(Object obj) { if (null != obj && obj.getClass() == UUID.class) { UUID id = (UUID)obj; return this.mostSigBits == id.mostSigBits && this.leastSigBits == id.leastSigBits; } else { return false; } } public int compareTo(UUID val) { return this.mostSigBits < val.mostSigBits ? -1 : (this.mostSigBits > val.mostSigBits ? 1 : (this.leastSigBits < val.leastSigBits ? -1 : (this.leastSigBits > val.leastSigBits ? 1 : 0))); } private static class Holder { static final SecureRandom numberGenerator = new SecureRandom(); private Holder() { } } }
从代码可以看到 UUID.randomUUID() 获得了一个UUID对象,它有两个long类型成员变量
private final long mostSigBits; private final long leastSigBits;
我们可以通过hashcode获得它int类型值作为唯一的标识,但是发现有很小概率撞衫,
public String toString() {
return jla.fastUUID(this.leastSigBits, this.mostSigBits);
}
有任何撞衫的情况都是不应许的;或者通过将UUID.randomUUID().toString()作为字符算唯一,这可以保证唯一性,但是生成的比较长字符串标识,对于在游戏服务器业务开发实际运用中并不友好。
通过以上代码我们看出UUID获得的是两个long类型,或者生成字符串,计算机所能表达基础类型最大类型是8个字节(long类型),两个long没有与之所匹配的基础数据类型,字符串是倒是唯一的,但是使用起来非常的不方便。那么有没有能够用一个long类型就能表达的全服唯一的id呢?答案肯定是有的,雪花算法就孕育而生
雪花算法
雪花算法是Twitter公司发明的一种算法,主要目的是解决在分布式环境下,ID怎样生成的问题
1,分布式ID生成规则硬性要求:全局唯一:不能出现重复的ID号,既然是唯一标识,这是最基本的要求
雪花算法中通过41位时间戳 10位进程ID,生成序号12位,1位高位组合成一个64long类型,从上图我们可以看到,1秒钟可以生成409.6万个id一个进程,在实际运用中远远满足我们的业务需求。不过仔细的朋友会发现,进程ID很关键,如果进程id与其他进程相同,那么有可能有很小概率会出现撞衫,所以在实际运用中进程id一定要保证其唯一性。
基于此雪花算法给我提供了一个很好的思路获得用一个Long类型获得全球唯一id总体思路,那就是将时间戳和进程id等信息存入到一个Long中。雪花算法的好处在于并没有利用第三方工具的手段实现ID在本地生成,保证生成的ID完全全局同步,同时可以用一个长整形就可以表达我们所需要ID,便于我们对于数据操作的,这符合游戏开发中的需要。
3、在游戏开发中,我们有如下几个需求
1)希望有一个在线程安全的唯一id
因为我们有大量的需要大量的容器来满足我们的业务需求,key值的唯一性就很关键
它包含:
(38位time+25位seq+1位最高标记位)=64位,线程同步,但非进程同步
2)希望进程之间是同步的id(类雪花算法)
道具ID生成,角色ID,帮会ID等都需要有一个唯一标识,便于存储和查询。
它包含:
(进程间唯一ID 14位processId+位+29位time+20位seq+1位最高标记位)=64
3)账号id
游戏可能有多个服务器组,希望每个id中也包含组(groupId)信息,并且是全球唯一,在特 殊运用场景中需要,比如登录时,SDK的登入openId与账号唯一绑定时需要用到,它的生成 可以没有进程同步ID效率高,但是也是进程间同步的。
它包含:
(进程间唯一ID 14位processId+位+29位time+12位groupId+8位seq+1位最高标记位)=64
这三个ID生都有一个共同的特点,利用时间戳和序号以及时间自旋来生成我们的ID,线程ID效率最高,进程ID次之,账号ID最低
1和2这两个需求很容易满足,3的需要需要特殊处理
实现代码如下:
创建id接口
public interface IIdGenerator {
long nextID();
}
创建对象类基类
import java.util.Calendar;
public abstract class AbstractIdGenerator implements IIdGenerator{
//进程ID 最大1024*16-1
protected static final int PROCESS_BITS = 14;
private volatile long seq = 0L;
protected volatile long lastTime = 0L;
public AbstractIdGenerator()
{
this.lastTime = getNowWorldTimeSec();
}
protected long nextSeq(long currentTime)
{
if (lastTime>currentTime) {
this.lastTime = this.enterNextSec();
this.seq = 1L;
}
else{
++this.seq;
//如果当前秒ID没有耗尽,那么就不跳秒表
if (this.seq >= getMaxSeq()) {
lastTime++;
if(lastTime>currentTime) {
lastTime = this.enterNextSec();
}
seq = 1;
}
}
return lastTime;
}
private long enterNextSec() {
long sec = getNowWorldTimeSec();
while (sec <= this.lastTime) {
sec = getNowWorldTimeSec();
}
return sec;
}
abstract long getMaxSeq();
protected long getSeq()
{
return seq;
}
private static volatile long wordTimeSec = 0;
public static long getDefaultWordTimeSec() {
if(wordTimeSec ==0)
{
synchronized ( AbstractIdGenerator.class) {
Calendar instance = Calendar.getInstance();
instance.set(Calendar.YEAR, 2022);
instance.set(Calendar.MONTH, 1);
instance.set(Calendar.DAY_OF_MONTH, 1);
instance.set(Calendar.HOUR_OF_DAY, 0);
instance.set(Calendar.MINUTE, 0);
instance.set(Calendar.SECOND, 0);
instance.set(Calendar.MILLISECOND, 0);
wordTimeSec = instance.getTimeInMillis() / 1000L;
}
}
return wordTimeSec;
}
public static long currentTimeMillis()
{
return System.currentTimeMillis();
}
public static long currentTimeSeconds()
{
return System.currentTimeMillis()/1000L;
}
public static long getNowWorldTimeSec()
{
return (currentTimeSeconds()-getDefaultWordTimeSec());
}
}
ObjectIDGenerator (38位time+25位seq+1位最高标记位)线程同步,但非进程同步
public class ObjectIDGenerator extends AbstractIdGenerator{
private static int SEQ_BITS = 25;
public ObjectIDGenerator()
{
super();
}
@Override
public synchronized long nextID() {
long nowTime = nextSeq(getNowWorldTimeSec());
return (((nowTime<
SyncIdGenerator(进程间唯一ID 14位processId+位+29位time+20位seq+1位最高标记位)=64
进程安全
public class SyncIdGenerator extends AbstractIdGenerator{
private volatile long processID = 0L;
private static int SEQ_BITS = 20;
public SyncIdGenerator(int processID) {
super();
this.processID = processID;
if (this.processID >= ((1<UserIdGenerator (进程间唯一ID 14位processId+位+29位time+12位groupId+8位seq+1位最高标记位)=64
public class UserIdGenerator extends AbstractIdGenerator{
private static int GROUP_ID_BITS = 12;
private static int TIME_BITS = 29;
private static int SEQ_BITS = 8;
private long processID;
private long groupID;
public UserIdGenerator(int processID,int groupID)
{
super();
if(groupID>getMaxGroupID())
{
int value = getMaxGroupID();
throw new IllegalArgumentException("invalid groupID must less than MaxGroupID(= " +value+" groupID = "+groupID);
}
if(processID>getMaxProcessID())
{
int value = getMaxProcessID();
throw new IllegalArgumentException("invalid processID must less than ProcessID= " +value+" processID = "+processID);
}
//先预借100*256个ID
lastTime = getNowWorldTimeSec()-100;
this.processID = processID;
this.groupID = groupID;
}
@Override
public synchronized long nextID() {
long nowTime = nextSeq(getNowWorldTimeSec());
long id = 0L;
id = (groupID <<(63-GROUP_ID_BITS));
id |= (processID <<(63-PROCESS_BITS-GROUP_ID_BITS));
id |= (nowTime<>(63-GROUP_ID_BITS));
return (int)a;
}
public static int getProcessID(long userID)
{
//将前面数据清空
long a = (0x7FFFFFFFFFFFFFFFL & userID);
a = a<>(63-PROCESS_BITS));
return (int)a;
}
}
对于SyncIdGenerator和UserIdGenerator ID做了特殊处理,这样可以id生成是平滑,尽可能减少ID生成瓶颈的概率
protected long nextSeq(long currentTime)
{
if (lastTime>currentTime) {
this.lastTime = this.enterNextSec();
this.seq = 1L;
}
else{
++this.seq;
//如果当前秒ID没有耗尽,那么就不跳秒表
if (this.seq >= getMaxSeq()) {
lastTime++;
if(lastTime>currentTime) {
lastTime = this.enterNextSec();
}
seq = 1;
}
}
return lastTime;
}



