Based on Java code the game server generates global unique ID method summary

Data on the server system development, in order to adapt to the big concurrent requests, we often need to asynchronous data storage, especially in a distributed system, this time can't waiting to be inserted into the database automatically id returned to pick it up, but need to be inserted into the database to generate a global only 1 id, using a global only 1 id, in game server, global id only 1 can be used for future us take easy, there will be no conflict. In the case of future business growth, the sub-database sub-table can also be realized. For example, the items of a certain user should be placed in the same shard, and this shard segment may be determined according to the range value of user id, for example, users with id greater than 1000 and less than 100,000 are in the same shard. Currently, the following are commonly used:

1. Java comes with UUID.

UUID.randomUUID ().toString (), which can be generated locally by the service program, and ID, which does not depend on the implementation of the database.

Advantage:

Generate ID locally, without the need for a remote call.

Global only 1 does not repeat.

Horizontal expansion is very good.

Disadvantage:

ID has 128 bits, which takes up a large amount of space and needs to be stored as a string type. The indexing efficiency is extremely low.

There is no Timestamp in the generated ID, so it is impossible to guarantee the increasing trend, and it is not easy to rely on the database sub-database sub-table

2. incr method based on Redis

While Redis itself is single-threaded, incr guarantees an atom-incrementing operation. It also supports setting the increment step size.

Advantage:

Easy to deploy, easy to use, just need to call 1 redis api.

Multiple servers can share one redis service, reducing the development time of Shared data.

Redis can be deployed in clusters to resolve a single point of failure.

Disadvantage:

If the system is too large, multiple n services are requesting redis at the same time, causing performance bottlenecks.

3. Solution from Flicker

This solution is based on database augmentation of id, which USES a single database dedicated to generating id. Detailed you can look for on the net, the individual feels to use quite troublesome, do not suggest to use.

4, Twitter Snowflake

snowflake is an open source distributed ID generation algorithm of twitter. Its core idea is to produce one long type ID, in which 41bit is used as the number of milliseconds, 10bit as the machine number, and 12bit as the serial number within milliseconds. This algorithm can theoretically generate up to 1000*(2^12) units per second per machine, which is about 400W ID, fully meeting the needs of the business.

According to the idea of snowflake algorithm, we can generate our own global only 1ID according to our own business scenarios. Since the length of type long in Java is 64bits, our designed ID needs to be controlled at 64bits.

Advantages: high performance, low latency; Independent applications; In chronological order.

Cons: independent development and deployment is required.

For example, ID designed by us contains the following information:

| 41 bits: Timestamp | 3 bits: zone | 10 bits: machine number | 10 bits: serial number |

Generate the Java code only 1ID:

/**
*  The custom  ID  The generator 
* ID  Generate rules : ID As long as  64 bits
*
* | 41 bits: Timestamp ( ms ) | 3 bits:  Area (machine room)  | 10 bits:  The machine number  | 10 bits:  The serial number  |
*/
public class GameUUID{
//  Reference time 
private long twepoch = 1288834974657L; //Thu, 04 Nov 2010 01:42:54 GMT
//  Area marker number 
private final static long regionIdBits = 3L;
//  Machine identification number 
private final static long workerIdBits = 10L;
//  The serial number knows the number of digits 
private final static long sequenceBits = 10L;
//  Regional flag ID The maximum 
private final static long maxRegionId = -1L ^ (-1L << regionIdBits);
//  The machine ID The maximum 
private final static long maxWorkerId = -1L ^ (-1L << workerIdBits);
//  The serial number ID The maximum 
private final static long sequenceMask = -1L ^ (-1L << sequenceBits);
//  The machine ID Move to the left 10 position 
private final static long workerIdShift = sequenceBits;
//  business ID Move to the left 20 position 
private final static long regionIdShift = sequenceBits + workerIdBits;
//  Milliseconds to the left 23 position 
private final static long timestampLeftShift = sequenceBits + workerIdBits + regionIdBits;
private static long lastTimestamp = -1L;
private long sequence = 0L;
private final long workerId;
private final long regionId;
public GameUUID(long workerId, long regionId) {
//  Throw an exception if it is out of range 
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0");
}
if (regionId > maxRegionId || regionId < 0) {
throw new IllegalArgumentException("datacenter Id can't be greater than %d or less than 0");
}
this.workerId = workerId;
this.regionId = regionId;
}
public GameUUID(long workerId) {
//  Throw an exception if it is out of range 
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0");
}
this.workerId = workerId;
this.regionId = 0;
}
public long generate() {
return this.nextId(false, 0);
}
/**
*  That actually generates the code 
*
* @param isPadding
* @param busId
* @return
*/
private synchronized long nextId(boolean isPadding, long busId) {
long timestamp = timeGen();
long paddingnum = regionId;
if (isPadding) {
paddingnum = busId;
}
if (timestamp < lastTimestamp) {
try {
throw new Exception("Clock moved backwards. Refusing to generate id for " + (lastTimestamp - timestamp) + " milliseconds");
} catch (Exception e) {
e.printStackTrace();
}
}
// If the last build time is the same as the current time , In the same 1 milliseconds 
if (lastTimestamp == timestamp) {
//sequence It increases because sequence only 10bit , so, sequenceMask ol 1 Next, get rid of the high position 
sequence = (sequence + 1) & sequenceMask;
// Determine if there is an overflow , That's more than one millisecond 1024 When to 1024 with sequenceMask To compete, sequence Is equal to 0
if (sequence == 0) {
// Spin wait down 1 ms 
timestamp = tailNextMillis(lastTimestamp);
}
} else {
//  If it was generated at a different time than last time , reset sequence , it is under 1 The milliseconds start, sequence Count from 0 Began to accumulate ,
//  In order to ensure greater randomness of mantissa 1 some , The last 1 A set 1 A random number 
sequence = new SecureRandom().nextInt(10);
}
lastTimestamp = timestamp;
return ((timestamp - twepoch) << timestampLeftShift) | (paddingnum << regionIdShift) | (workerId << workerIdShift) | sequence;
}
//  The time to prevent the occurrence is even less than the time before (due to NTP Dial back and so on) , Maintain the incremental trend .
private long tailNextMillis(final long lastTimestamp) {
long timestamp = this.timeGen();
while (timestamp <= lastTimestamp) {
timestamp = this.timeGen();
}
return timestamp;
}
//  Gets the current timestamp 
protected long timeGen() {
return System.currentTimeMillis();
}
}

A few things to note when using this custom method:

In order to maintain the growth trend, to avoid some servers early time, some server time late, need to control the time of all servers, and to avoid NTP time server back to the server time; When the serial number is across milliseconds, it will always return to 0, which will make ID with serial number of 0 more. As a result, the generated ID will not be uniform after taking modules. Therefore, the serial number will not return to 0 every time, but to a random number from 0 to 9.

We can choose these ways according to our own needs. In the development of game server, according to the choice of their own game types, such as mobile games, you can use the simple way of redis, simple and not easy to make mistakes, because this kind of game single-server concurrent creation of id is not too large, it can completely meet the needs. For the large-scale world game server, which itself is mainly distributed, snowflake can be used. The above snowflake code is just one example, which needs to be customized according to its own needs. Therefore, there is an extra amount of development.