When developing a server system, in order to adapt to large and concurrent data requests, we often need to store the data asynchronously, especially when working in a distributed system. At this time, we cannot wait for the insertion database to return the automatic id to be retrieved. Instead, we need to generate a global unique id before inserting the database, using the global unique id. In the game server, the global unique id can be used for future server combinations and there will be no key conflicts. In the future, in the event of business growth, the database and split table can be implemented. For example, a user's items must be placed in the same shard, and this shard may be determined based on the range value of the user id, such as a user id with a user id greater than 1000 and less than 100000 in a shard. Currently, the following are commonly used:
1. Java's own UUID.
UUID.randomUUID().toString() can be generated locally through the service program, and the generation of ID does not depend on the implementation of the database.
Advantages:
Generate ID locally and does not require remote calls.
The world is the only one that does not repeat.
The horizontal expansion ability is very good.
Disadvantages:
The ID has 128 bits, which takes up a large space and needs to be stored as a string type, and the indexing efficiency is extremely low.
The generated ID does not contain Timestamp, and the trend cannot be guaranteed to increase. It is difficult to rely on when dividing database databases.
2. Redis-based incr method
Redis itself is operated single-threaded, and incr ensures an atomically incremented operation. It also supports setting incremental step size.
Advantages:
It is easy to deploy and easy to use. You only need to call a redis API.
Multiple servers can share a redis service to reduce the development time of shared data.
Redis can be deployed in clusters to solve the problem of single point of failure.
Disadvantages:
If the system is too large, multiple services request to Redis at the same time will cause performance bottlenecks.
3. Solution from Flicker
This solution is based on the database's auto-increment id, which uses a separate database specifically for generating ids. You can find the details online. I personally think it is quite troublesome to use and it is not recommended to use it.
4. Twitter Snowflake
snowflake is a distributed ID generation algorithm that is open source on Twitter. Its core idea is to generate a long-type ID, using 41bit 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 1,000*(2^12) IDs per second per machine, which is about 400W, which can fully meet the needs of the business.
According to the idea of the snowflake algorithm, we can generate our own global unique ID based on our business scenarios. Because the length of the long type in Java is 64bits, the ID we designed needs to be controlled at 64bits.
Advantages: high performance, low latency; independent application; orderly by time.
Disadvantages: Independent development and deployment are required.
For example, the ID we designed contains the following information:
| 41 bits: Timestamp | 3 bits: Area | 10 bits: Machine number | 10 bits: Serial number |
Java code that generates a unique ID:
/*** Custom ID generator* ID generation rules: ID up to 64 bits** | 41 bits: Timestamp (ms) | 3 bits: Area (computer room) | 10 bits: Machine number | 10 bits: Serial number |*/public class GameUUID{// reference time private long twepoch = 1288834974657L; //Thu, 04 Nov 2010 01:42:54 GMT// Region flag digits private final static long regionIdBits = 3L;// Machine identification digits private final static long workerIdBits = 10L;// Serial number digits private final static long sequenceBits = 10L;// Maximum value of region flag ID private final static long maxRegionId = -1L ^ (-1L << regionIdBits);// Maximum value of machine ID private final static long maxWorkerId = -1L ^ (-1L << workerIdBits);// Maximum value of serial number ID private final static long sequenceMask = -1L ^ (-1L << sequenceBits);// The machine ID is shifted 10 bits to the left private final static long workerIdShift = sequenceBits;// The service ID is shifted left by 20 bits private final static long regionIdShift = sequenceBits + workerIdBits;// The time is shifted left by 23 bits 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) {// If out of range, an exception is thrown 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) {// If out of range is thrown 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);}/*** The actual code generated by @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) + " millionseconds");} catch (Exception e) {e.printStackTrace();}}//If the last generation time is the same as the current time, if (lastTimestamp == timestamp) within the same millisecond, if (lastTimestamp == timestamp) {//sequence increases by itself, because the sequence is only 10bit, it is combined with sequenceMask and remove the high-bit sequence = (sequence + 1) & sequenceMask;//Judge whether it overflows, that is, it exceeds 1024 in every millisecond. When it is 1024, it is combined with sequenceMask, and sequence is equal to 0if (sequence == 0) {//Spin waits until the next millisecond timestamp = tailNextMillis(lastTimestamp);}} else {// If the sequence is different from the last generation time, reset the sequence, which starts in the next millisecond, and the sequence count starts from 0 again. // In order to ensure that the mantissa is more random, set a random number in the last bit sequence = new SecureRandom().nextInt(10);}lastTimestamp = timestamp;return ((timestamp - twepoch) << timestampLeftShift) | (paddingnum << regionIdShift) | (workerId << workerIdShift) | sequence;}// Prevent the generation time being smaller than the previous time (due to problems such as NTP callback), and maintain the incremental trend.private long tailNextMillis(final long lastTimestamp) {long timestamp = this.timeGen();while (timestamp <= lastTimestamp) {timestamp = this.timeGen();}return timestamp;}// Get the current timestamp protected long timeGen() {return System.currentTimeMillis();}}Some things to note when using custom methods:
In order to maintain the growth trend, it is necessary to avoid the time of some servers early and some servers late, so the time of all servers needs to be controlled, and the time when the NTP time server calls back to the server is avoided; when crossing milliseconds, the serial number always reaches 0, which will make more IDs with serial number 0, resulting in uneven IDs after moduloing, so the serial number does not belong to 0 every time, but a random number from 0 to 9.
We can choose the methods mentioned above according to our needs. In game server development, you can choose according to your own game type, such as mobile games, and you can use the simple redis method, which is simple and not easy to make mistakes. Since the number of new ids created by single servers in this kind of game is not too large, it can completely meet the needs. For large world game servers, they are mainly distributed, so you can use snowflake. The above snowflake code is just an example and needs to be customized according to your needs, so there is additional development volume, and you should pay attention to the above precautions.
The above is a summary of the methods of using Java code to implement the game server to generate a global unique ID based on Java code. I hope it will be helpful to everyone. If you have any questions, please leave me a message and the editor will reply to everyone in time. Thank you very much for your support to Wulin.com website!