Abstract:
In this blog post, we will focus on “how to generate globally unique and trending increasing order numbers in high concurrency, such as seckilling business scenarios”. We will introduce two methods: one is the traditional random number generation method. The other is to use the current more popular “distributed unique ID generation algorithm – snowflake algorithm” to achieve.
Content:
In the last blog post, we completed the code practice of the second kill business logic. In this code, we also realized the function “when the user succeeds in the second kill, he needs to generate a second kill order record in the database table”. The corresponding code is as follows:
/ / after the success of the general method to record user seconds kill generated orders - and asynchronous message to inform private void commonRecordKillSuccessInfo (ItemKillkill, Integer userId) throws Exception{//TODO: Records the second kill order record generated after the successful purchase ItemKillSuccess Entity = New ItemKillSuccess(); OrderNo = string.valueof (snowFlake. NextId ()); // orderNo= String.valueof (snowFlake. //entity.setCode(RandomUtil.generateOrderCode()); // Traditional timestamp +N bits random number entity.setCode(orderNo); // Entity. SetItemId (kill.getitemId ()); entity.setKillId(kill.getId()); entity.setUserId(userId.toString()); entity.setStatus(SysConstant.OrderStatus.SuccessNotPayed.getCode().byteValue()); entity.setCreateTime(DateTime.now().toDate()); //TODO: double check lock writing modelled on singleton patternif(itemKillSuccessMapper.countByKillUserId(kill.getId(),userId) <= 0){ int res=itemKillSuccessMapper.insertSelective(entity); }}Copy the codeIn this implementation logic, the core point is “how to efficiently generate order numbers in a high-concurrency environment”, so what is efficient? Debug considers that the following two points should be met:
(1) Ensure that the generation logic of order number is fast and stable, and reduce delay
(2) Ensure that the generated order number is globally unique, non-repetitive, trend increasing, and time-series
Below, we use two ways to generate “order number”, and write a multithreaded program to simulate whether the generated order number meets the conditions.
It is worth mentioning that, in order to intuitively observe whether the order number generated concurrently by multiple threads has a unique and increasing trend, Debug uses a database table random_code to store the generated order number, and its DDL is as follows:
CREATE TABLE `random_code` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`code` varchar(255) DEFAULT NULL,
PRIMARY KEY (`id`),
UNIQUE KEY `idx_code` (`code`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;Copy the codeAs you can see from the database table data structure definition statement, we set the order number field code as unique! Therefore, if the order number generated by high concurrency multithreading is repeated, an error will inevitably occur when inserting the database table
Let’s start with our first method: generating order numbers based on random numbers
(1) The first step is to establish a Thread class. The execution logic of its RUN method is to generate order numbers and insert the generated order numbers into the database table. The code is as follows:
/** * Random number generation -Thread * @author :debug (SteadyJack) * @date: 2019/7/11 10:30 **/ public class CodeGenerateThread implements Runnable{ private RandomCodeMapper randomCodeMapper; public CodeGenerateThread(RandomCodeMapper randomCodeMapper) { this.randomCodeMapper = randomCodeMapper; } @Override public voidrun() {// Generate order number and insert database RandomCode entity=new RandomCode(); entity.setCode(RandomUtil.generateOrderCode()); randomCodeMapper.insertSelective(entity); }}Copy the code. Among them, the RandomUtil generateOrderCode () the generation of the logic is implemented using ThreadLocalRandom, its complete source code as shown below:
/** * @author :debug (SteadyJack) * @date: 2019/6/20 21:05 **/ public class RandomUtil { private static final SimpleDateFormat dateFormatOne=new SimpleDateFormat("yyyyMMddHHmmssSS"); private static final ThreadLocalRandom random=ThreadLocalRandom.current(); // Generate order number - method 1 public static StringgenerateOrderCode(){//TODO: timestamp +N is a random number sequence numberreturndateFormatOne.format(DateTime.now().toDate()) + generateNumber(4); } public static String generateNumber(final Int num){StringBuffer sb=new StringBuffer();for(int i=1; i<=num; i++){ sb.append(random.nextInt(9)); }returnsb.toString(); }}Copy the code(2) Followed by the development of a request method in the BaseController controller, the purpose is to simulate the front-end high concurrency trigger to generate multithreading and generate order number logic, here we temporarily use 1000 threads to simulate, its source code is as follows:
@Autowired private RandomCodeMapper randomCodeMapper; RequestMapping(value =); // Test how to generate order numbers in multiple threads under high concurrency - traditional random number generation method @requestMapping (value =)"/code/generate/thread",method = RequestMethod.GET)
public BaseResponse codeThread(){
BaseResponse response=new BaseResponse(StatusCode.Success);
try {
ExecutorService executorService=Executors.newFixedThreadPool(10);
for(int i=0; i<1000; i++){ executorService.execute(new CodeGenerateThread(randomCodeMapper)); } }catch (Exception e){ response=new BaseResponse(StatusCode.Fail.getCode(),e.getMessage()); }return response;
}Copy the code(3) After that, you can run the whole project and system in external Tomcat, then open Postman and initiate an Http Get request, the request link is: http://127.0.0.1:8092/kill/base/code/generate/thread, carefully observe the console output information, can see something his restlessness:
“Duplicate order number generated” appears unexpectedly! Furthermore, if you open the database table and look at it, you will see that “there are only 900 records out of 1000 fucking threads generating order numbers”, which indicates that there are “duplicate order numbers” during the execution of the logic generating order numbers by so many threads! As shown below:
Therefore, this method of generating unique ID or order number based on random number can be passed (of course, in the case of not very high concurrency, this method is still widely used, because it is simple and easy to understand ah!).
In view of this “random number generation” method does not meet our requirements in high concurrency scenarios, we will introduce another popular and typical method, namely “distributed unique ID generation algorithm – Snowflake algorithm” to achieve.
For the introduction of “snow algorithm”, each friend can refer to making on this link, I think to speak is pretty clear: https://github.com/souyunku/SnowFlake, detailed the Debug will not go into here, description of intercepting the sections below:
SnowFlake can efficiently generate unique ids in a distributed environment. I think one of the most important aspects of SnowFlake is that the underlying implementation of the algorithm is “bit-computing”. In short, it works directly with the machine! The underlying data storage structure (64-bit) is shown below:
Below, we are directly based on the snowflake algorithm to generate second kill system in the need of the order number!
(1) Similarly, we first define a Thread class, and the implementation logic of its RUN method is to generate order numbers and insert them into the database with the help of the snowflake algorithm.
* @author :debug (SteadyJack) * @date: 2019/7/11 10:30 **/ public class CodeGenerateSnowThread implements Runnable{ private static final SnowFlake SNOW_FLAKE = new SnowFlake (2, 3); private RandomCodeMapper randomCodeMapper; public CodeGenerateSnowThread(RandomCodeMapper randomCodeMapper) { this.randomCodeMapper = randomCodeMapper; } @Override public voidrun() { RandomCode entity=new RandomCode(); Entity.setcode (string.valueof (snow_fla.nextid ()))); randomCodeMapper.insertSelective(entity); }}Copy the codeThe snow_fla.nextid () method uses the snowflake algorithm to generate globally unique order number logic, its complete source code is as follows:
/** * zhonglinsen algorithm * @author: zhonglinsen * @date: 2019/5/20 */ public class SnowFlake {private final static long START_STAMP = 1480166465631L; Private final static long SEQUENCE_BIT = 12; Private final static long MACHINE_BIT = 5; Private final static long DATA_CENTER_BIT = 5; Private final static Long MAX_DATA_CENTER_NUM = -1L ^ (-1L << DATA_CENTER_BIT); private Final static long MAX_DATA_CENTER_NUM = -1L ^ (-1L << DATA_CENTER_BIT); private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT); private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT); Private final static long MACHINE_LEFT = SEQUENCE_BIT; private final static long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT; private final static long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT; private long dataCenterId; // Private long machineId; Private long sequence = 0L; Private long lastStamp = -1l; Public SnowFlake(long dataCenterId, long machineId) {if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) {
throw new IllegalArgumentException("dataCenterId can't be greater than MAX_DATA_CENTER_NUM or less than 0");
}
if (machineId > MAX_MACHINE_NUM || machineId < 0) {
throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0"); } this.dataCenterId = dataCenterId; this.machineId = machineId; } // Generate the next ID public synchronized longnextId() {
long currStamp = getNewStamp();
if (currStamp < lastStamp) {
throw new RuntimeException("Clock moved backwards. Refusing to generate id");
}
if(currStamp == lastStamp) {sequence = (sequence + 1) &max_sequence; // The number of sequences in the same millisecond has reached the maximumif(sequence == 0L) { currStamp = getNextMill(); }}else{// Set the sequence number to 0 sequence = 0L in different milliseconds; } lastStamp = currStamp;return(currStamp - START_STAMP) < < TIMESTAMP_LEFT / / part timestamp | dataCenterId < < DATA_CENTER_LEFT/part/data center | machineId < < MACHINE_LEFT / / machine identifier portion | sequence; } private longgetNextMill() {
long mill = getNewStamp();
while (mill <= lastStamp) {
mill = getNewStamp();
}
return mill;
}
private long getNewStamp() {
returnSystem.currentTimeMillis(); }}Copy the code(2) Next, we develop a request method in BaseController, which is used to simulate the scenario where the front end triggers high concurrency and produces multi-thread order scrambling.
/** * Test multithreaded order number generation under high concurrency - Snowflake algorithm * @return
*/
@RequestMapping(value = "/code/generate/thread/snow",method = RequestMethod.GET)
public BaseResponse codeThreadSnowFlake(){
BaseResponse response=new BaseResponse(StatusCode.Success);
try {
ExecutorService executorService=Executors.newFixedThreadPool(10);
for(int i=0; i<1000; i++){ executorService.execute(new CodeGenerateSnowThread(randomCodeMapper)); } }catch (Exception e){ response=new BaseResponse(StatusCode.Fail.getCode(),e.getMessage()); }return response;
}Copy the code(3) After completion, we use Postman to initiate an Http Get request, the request link is as follows: http://127.0.0.1:8092/kill/base/code/generate/thread/snow, to observe the output information of the console, you can see a enron’s sight “, “again observe a database table records, can be found, 1000 threads successfully triggered the generation of 1000 corresponding order numbers, as shown in the figure below:
In addition, you can adjust the number of threads from 1000 to 10000, 100000, or 1000000, and then watch the console output, database table records, and so on.
– Debug tests 1W and 10W scenarios, there is no problem, 100W thread count test is left to you to try. At this point, we can generate the snowflakes algorithm globally unique order number application logic to our “seconds kill processing logic”, namely the code (in KillService commonRecordKillSuccessInfo method) as shown below:
ItemKillSuccess entity=new ItemKillSuccess(); String orderNo=String.valueOf(snowFlake.nextId()); // Entity. SetCode (orderNo); // Other code omittedCopy the code