A beautiful interviewer sat opposite me , Luminescence logo Of MacBook Nor can she stop her round and lovely face .
Program yuan is rare , Beautiful interviewers are even harder to find . What does it look like ？ It looks like this ：
Such a gentle and lovely interviewer , It should not embarrass me . Um. , Should be yes , After all, I am so handsome , The interview may just be a formality . Is the beauty interviewer single ？ After all, programmers are not good at communicating , Because I am also single , Is my marriage doomed here . I have all the names of the children in mind . A piece of ice ！ Good name .
interviewer ： Young man , Why are you smiling with your head down . The interview started , You know the order ID How was it generated ？
what ？ Order ID How to generate ？ Why don't beautiful women play cards according to the routine ！HashMap Realization principle , I have learned it backwards , You don't ask . Ask about orders ID.
I ： How can I generate ？ Use the database primary key to automatically increase .
interviewer ： That's not going to work . The database primary key sequence increases automatically , The number of orders per day is clearly seen by competitors , Trade secrets have been exposed .
Besides, single machine MySQL Only a few hundred levels of concurrency can be supported , Our company orders tens of millions of goods every day ,hold I can't live .
I ： Um. , Then use the database cluster , Self increasing ID Starting value by machine number , The step size is equal to the number of machines .
For example, there are two machines , Generated by the first machine ID yes 1、3、5、7, Generated by the second machine ID yes 2、4、6、8. If the performance is not good, add the machine , This concurrency der I went up in a minute .
interviewer ： Young man , You have a good idea . Have you ever thought about achieving million level concurrency , Probably 2000 Taiwan machine , You are only using it to generate orders ID, No matter how rich the company is, it can't afford to do this .
I ： since MySQL The concurrency of is not good , Is it possible for us to MySQL Obtain a batch of auto increment ID, Load into local memory , Then it fetches from memory concurrently , This concurrency performance is not a lever drop .
interviewer ： You're pretty good , This call segment mode . The concurrency is increasing , But self increasing ID Still not as an order ID Of .
I ： use Java Bring their own UUID What about? ？
import java.util.UUID;
/**
* @author yideng
* @apiNote UUID Example
*/
public class UUIDTest {
public static void main(String[] args) {
String orderId = UUID.randomUUID().toString().replace("-", "");
System.out.println(orderId);
}
}
Output results ：
58e93ecab9c64295b15f7f4661edcbc1
interviewer ： Not good either. .32 Bit strings take up more space , Unordered strings are used as database primary keys , Every time you insert a database ,MySQL For maintenance B+ Tree structure , The node order needs to be adjusted frequently , Affect performance . Besides, the string is too long , Nor does it have any business implications ,pass.
Young man , You may not have participated in the e-commerce system , Let me talk about generating orders first ID What conditions should be met ：
Globally unique ： If order ID repeated , It must be over .
High performance ： To achieve high concurrency 、 Low latency . Generate order ID Have become a bottleneck , That's got it. .
High availability ： At least 4 individual 9, Don't be prone to downtime .
Ease of use ： If in order to meet the above requirements , Hundreds of servers , Complex and difficult to maintain , Not good either. .
Numerical and orderly increasing ： Values take up less space , Orderly increment ensures insertion MySQL Higher performance when .
Embedded business implications ： If order ID Business implications can be embedded in it , Can pass the order ID Know which business line generated it , Easy to troubleshoot .
I wipe , Generate a small order ID, Come up with so many rules , Can I play any more ？ Is today's interview to kneel , How is that possible? . I have been subscribing to Yideng articles , It's also hard for me , It's serious to play with beautiful programmers .
I ： I heard that there is a long-standing distributed in the circle 、 High performance 、 Highly available orders ID generating algorithm — Snowflake algorithm , Can fully meet your above requirements . Snow algorithm generation ID yes Long type , length 64 position .
The first 1 position ： Sign bit , Not for the time being .
The first 2~42 position ： common 41 position , Time stamp , In milliseconds , It can support about 69 year
The first 43~52 position ： common 10 position , machine ID, It can hold at most 1024 Taiwan machine
The first 53~64 position ： common 12 position , Serial number , It's self-improvement , It indicates that... Is generated in the same millisecond ID, A single machine can generate up to per millisecond 4096 Order per order ID
Code implementation ：
/**
* @author One light architecture
* @apiNote Snowflake algorithm
**/
public class SnowFlake {
/**
* Start timestamp , from 2021-12-01 To start generating
*/
private final static long START_STAMP = 1638288000000L;
/**
* The number of digits occupied by the serial number 12
*/
private final static long SEQUENCE_BIT = 12;
/**
* Number of digits occupied by machine identification
*/
private final static long MACHINE_BIT = 10;
/**
* Maximum number of machines
*/
private final static long MAX_MACHINE_NUM = ~(-1L << MACHINE_BIT);
/**
* Maximum serial number
*/
private final static long MAX_SEQUENCE = ~(-1L << SEQUENCE_BIT);
/**
* The displacement of each part to the left
*/
private final static long MACHINE_LEFT = SEQUENCE_BIT;
private final static long TIMESTAMP_LEFT = SEQUENCE_BIT + MACHINE_BIT;
/**
* Machine identification
*/
private long machineId;
/**
* Serial number
*/
private long sequence = 0L;
/**
* Last timestamp
*/
private long lastStamp = -1L;
/**
* Construction method
* @param machineId machine ID
*/
public SnowFlake(long machineId) {
if (machineId > MAX_MACHINE_NUM || machineId < 0) {
throw new RuntimeException(" The maximum number of machines is exceeded ");
}
this.machineId = machineId;
}
/**
* Produce the next ID
*/
public synchronized long nextId() {
long currStamp = getNewStamp();
if (currStamp < lastStamp) {
throw new RuntimeException(" Clock backward , Refuse to generate ID！");
}
if (currStamp == lastStamp) {
// In the same milliseconds , The serial number is increasing
sequence = (sequence + 1) & MAX_SEQUENCE;
// The number of sequences in the same millisecond has reached the maximum
if (sequence == 0L) {
currStamp = getNextMill();
}
} else {
// In different milliseconds , The serial number is set to 0
sequence = 0L;
}
lastStamp = currStamp;
return (currStamp - START_STAMP) << TIMESTAMP_LEFT // Time stamp part
| machineId << MACHINE_LEFT // Machine identification part
| sequence; // Serial number part
}
private long getNextMill() {
long mill = getNewStamp();
while (mill <= lastStamp) {
mill = getNewStamp();
}
return mill;
}
private long getNewStamp() {
return System.currentTimeMillis();
}
public static void main(String[] args) {
// Order ID Generate tests , machine ID Designate the 0 platform
SnowFlake snowFlake = new SnowFlake(0);
System.out.println(snowFlake.nextId());
}
}
Output results ：
6836348333850624
Access is very simple , There is no need to build a service cluster ,. The code logic is very simple ,, In the same millisecond , Order ID Your serial number is incremented . The synchronization lock only works on this machine , Machines do not affect each other , Four million orders can be generated per millisecond ID, Very strong .
Generation rules are not fixed , It can be adjusted according to its own business needs . If you don't need that much concurrency , You can remove a part of the machine identification bit , As a business identifier bit , Identify which business line generated the order ID.
interviewer ： Young man , There's something , It's hidden deep . Ask a more difficult question , Do you think there is room for improvement in the snowflake algorithm ？
You really broke the casserole and asked after all , If you don't ask me to get down, it won't end . Fortunately, I glanced at the article before I came here .
I ： yes , we have , The snowflake algorithm relies heavily on the system clock . If the clock goes back , A repetition is generated ID.
interviewer ： Is there a solution ？
I ： There are questions, there are answers . For example, meituan's Leaf（ Meituan has developed a distributed ID generating system ）, To solve the problem of clock back , Introduced zookeeper, The principle is also simple , This is to compare the current system time with the time of the generation node .
Some systems require higher concurrency , For example, double 11 seconds , Every millisecond 4 Millions of concurrency is not enough , You can use the combination of snowflake algorithm and segment pattern , For example, Baidu's UidGenerator、 Dripping TinyId. Wanting is also , Pre generation of segment pattern ID It must be a high-performance distributed order ID The ultimate solution .
interviewer ： Young man , I see your resume says that you have left . Come to work tomorrow , Salary double, That's all. .
Articles are constantly updated , You can search through wechat 「 One light architecture 」 Read more technical dry goods for the first time .
