Why do you need to study cross-library pagination?
Many services on the Internet have the need for paging and pulling data. For example:
(1) When there are too many wechat messages, pull the message on page N;
(2) If there are too many orders from JD, pull the order on page N;
(3) Browse 58.com to see the post on page N;
The message table, order table, and post table page pull requirements for these business scenarios all have the following characteristics in common:
(1) have a primary key id, msg_id, order_id, tiezi_id;
(2) Paging is sorted by non-business primary key ID, and business is often sorted by time order by;
How do you meet the need for cross-library paging when the amount of data is small?
(1) Create index on sorting field time;
(2) Use SQL to provide offset/limit can achieve;
Such as:
select * from t_msg order by time offset 200 limit 100;
select * from t_order order by time offset 200 limit 100;
select * from t_tiezi order by time offset 200 limit 100;
Voiceover: Here it is assumed that there are 100 pieces of data on one page, and all the data on page 3 are pulled.
Why is there a need for separate libraries?
In an Internet architecture with high concurrency and high traffic, databases are accessed through the service layer. As the amount of data increases, databases need to be horizontally divided and distributed to different database instances (even physical machines) to reduce the amount of data and increase the number of instances.
Once involved in database partitioning, can not escape the “database partitioning based on” patition key, which field to use to horizontally split the database?
In most business scenarios, the business primary key ID is used.
After determining the partition based on the partition key, how to determine the partition algorithm?
In most business scenarios, the business primary key ID modulo algorithm will be used to divide the library, which has the following benefits:
(1) To ensure that the data distribution of each library is uniform;
(2) To ensure that the request distribution of each library is uniform;
It’s a great way to simply implement load balancing, and it’s used a lot in Internet architectures.
A more specific example:
User database user, horizontally split into two libraries:
(1) Uid based on patition key;
(2) The library partition algorithm is the uid module: uid%2 remaining 0 data will fall to DB0, UID %2 remaining 1 data will fall to DB1;
After the database has been horizontally sharpened, if the business wants to query “recently registered page 3 users”, that is, cross-library paging query, how to achieve?
Single library, yes
select * from t_user order by time offset 200 limit 100;
The database layer loses the global view of time sorting. The data is distributed between the two libraries. What should we do now?
How to meet the query requirements of “splitting databases across multiple levels, and the database sorting basis and sorting basis are different attributes, and paging is required”, to achieve:
select * from T order by time offset X limit Y;
This type of cross-library paging SQL is a technical issue that will be discussed later.
Scheme 1: Global view method
As shown in the figure above, after the service layer distributes the data to the two libraries through the UID modulo, each database loses the global view. After the data is sorted locally by time, no matter which library is on the third page of the data, it is not necessarily the third page of the global sort.
So what data is page 3 of global sorting?
There are three cases to discuss.
(1) In the extreme case, the data of the two libraries is exactly the same
If the data of the two libraries is identical, you only need to take half of the offset of each library and take half of the page to get the desired data (as shown in the pink part of the figure above).
(2) In extreme cases, the resulting data comes from a library
For example, if the time of all data in DB0 is greater than that of all data in DB1, it may appear that the third page of data in a library is the third page of data after global sorting (as shown in the pink part of the figure above).
(3) In general, each library data contains a part
Normally, each library will contain a portion of the third page of global sorting data (as shown in the pink section above).
Since it is not clear which is the case, it is necessary to:
Each library returns 3 pages of data;
(2) The obtained 6 pages of data are sorted in memory at the service layer to get a global view of data;
(3) Then take the data on page 3, you can get the global paging data you want.
To summarize the steps of this solution:
(1) Rewrite the SQL statement, i.e
order by time offset X limit Y;
Rewrite into
order by time offset 0 limit X+Y;
(2) The service layer will send the rewritten SQL statement to each sub-library;
(3) Assuming that there are N libraries, the service layer will get N*(X+Y) pieces of data;
(4) The service layer will sort the memory of the obtained N*(X+Y) data;
(5) Y records after memory sorting and offset X are one page of data required for global view;
What are the advantages of the global view approach?
By modifying SQL statements in the service layer and expanding the amount of data recall, we can get a global view and accurately return the required data without any damage to the business.
The downside of the global view approach?
The drawbacks are obvious:
(1) Each sub-library needs to return more data, increasing the network transmission (network consumption);
(2) In addition to the database sorting by time, the service layer also needs to carry out a second sort, which increases the calculation of the service layer (CPU consumption);
(3) Most fatally, the algorithm’s performance deteriorates dramatically as the number of pages increases. This is because the SQL rewrite requires each partition to return X+Y rows of data: return page 3, offset X=200; If you want to return page 100, and the X in offset is 9900, that is, 100 pages of data are returned per repository, the amount of data and sorting will be greatly increased, and the performance square will be reduced.
Although the performance of the “global view method” is poor, its business is lossless and data is accurate. It can be regarded as a solution. Is there a solution with better performance?
“Any architecture design out of business is a rogue”, technical solutions need to compromise, in the case of technical difficulties, business requirements of the compromise can greatly simplify the technical solution.
Scheme two: prohibit page – hopping query method
When there is a large amount of data and a large number of page turns, many products do not provide the function of “jumping directly to the specified page”, but only provide the function of “next page”. This small business compromise can greatly reduce the complexity of technical solutions.
As shown above, you can only look up the first page the first time without skipping the page:
(1) Will query
order by time offset 0 limit 100;
Rewrite into
order by time where time>0 limit 100;
(2) The effect of offset 0 limit 100 is the same as that of offset 0 limit 100.
(3) The service layer gets 2 pages of data, which is sorted in memory, and the first 100 pieces of data are retrieved as the final first page of data. Generally, the first page of global data is contained in each sub-library (see the pink part in the figure above).
This solution also requires server memory ordering, just like the global view method. The first page is the same, but each “next page” is different.
When you click “Next Page”, you need to pull the data on the second page. Based on the data on the first page, you can find the maximum time of the data on the first page:
The time_max value of the previous record ** is used as the query condition for the second page ** :
(1) Will query
order by time offset 100 limit 100;
Rewrite into
order by time where time>$time_max limit 100;
(2) Instead of returning 2 pages of data (offset 0 limit 200), each library will return one page of data (as shown in the pink section above).
(3) The service layer gets 2 pages of data, memory sort, and the first 100 pieces of data are retrieved as the final second page of data. Generally, the second page of global data is also contained in each sub-library (see the pink part in the figure above).
When querying the data on page 100 of global view, instead of rewriting the query condition to
offset 0 limit 9900+100; (Return 100 pages of data)
I’m going to rewrite it as
time>$time_max99 limit 100; (Still returns one page of data)
To ensure that the amount of data being transferred and the amount of data being sorted does not degrade performance as pages are turned.
Scheme 3: Allowed data precision loss method
The “global view method” can return accurate data without loss to the business. When the number of pages queried is large, such as page 100, there will be performance problems. At this time, is it acceptable for the business to return 100 pages of accurate data and allow some data deviation?
First, to understand the database database – data balancing principle.
What is the database partition – data balancing principle?
In the case that the data volume is large and the data distribution is random enough, the statistical probability of data distribution on all non-patition key attributes of each sub-library is consistent in each sub-library.
For example, if the UID is random, use the uid module to divide two libraries, DB0 and DB1:
(1) Gender attribute: if the proportion of male users on DB0 library is 70%, then the proportion of male users on DB1 should also be 70%;
(2) Age attribute: if the proportion of girls aged 18-28 in DB0 library accounts for 15%, then the proportion of girls in DB1 should also be 15%;
(3) Time attribute: if the proportion of users who log in before 10:00 every day on DB0 library is 20%, then the same statistical rule should be observed on DB1;
…
To use this principle, to query global 100 pages of data, just:
offset 9900 limit 100;
to
offset 4950 limit 50;
In other words, half (4950) of each sub-database is offset (4950), and half a page of data (50 pieces) is obtained. The union of the obtained data sets can be basically considered as the data offset 9900 limit 100 of global data. Of course, this page of data is not accurate.
According to the actual business experience, users have to query the data of page 100, posts, emails, this page of data accuracy loss, business is often acceptable, but at this time the complexity of the technical solution is greatly reduced, neither need to return more data, nor need to conduct service memory sort.
Voiceover: If the service can accept this solution, the performance is the best, highly recommended.
Scheme four: the second query method
Is there a technical solution that meets the precise needs of the business, without business trade-offs, but with high performance? This is the ultimate weapon, the second lookup method.
For example, suppose there are only 5 pieces of data on a page, and the SQL statement on page 200 is as follows:
select * from T order by time offset 1000 limit 5;
Step 1: Query rewriting
select * from T order by time offset 1000 limit 5;
to
select * from T order by time offset 500 limit 5;
Note that this offset is 500, the total offset from the global offset is 1000, divided by the number of horizontal sharding databases by 2.
Voice: Because of the large amount of data and the strong randomness of the data, it may be assumed that it still conforms to the “database segmentation – data equilibrium theorem”.
If we have 3 sub-libraries, we can rewrite this as
select * from T order by time offset 333 limit 5;
Suppose the data (time, uid) returned by the three sub-libraries is as follows:
As you can see, each sub-library returns a page of data sorted by time.
Step 2: Find the minimum value for all 3 pages of data returned
In the first library, the minimum value of time for five pieces of data is 1487501123;
In the second library, the minimum time for five pieces of data is 1487501133;
For the third library, the minimum time for the five pieces of data is 1487501143;
Therefore, in the three pages of data, the minimum value of time is from the first library, time_min=1487501123. This process only needs to compare the first data of each sub-library, and the time complexity is very low.
Voiceover: This time_min is so important that you need to use it for each of the next steps.
Step 3: Query the secondary rewrite
The first SQL statement to be rewritten is
select * from T order by time offset 333 limit 5;
The next step is to write an between statement:
-
The starting point for between is time_min
-
The end point of between is the original maximum value of the data returned by each sub-database
For the first sub-library, the maximum value of the data returned the first time is 1487501523
So the query is rewritten as:
select * from T order by time where time between time_min and 1487501523;
For the second branch, the maximum value of the data returned the first time is 1487501323
So the query is rewritten as
select * from T order by time where time between time_min and 1487501323;
For the third branch, the maximum value of the data returned for the first time is 1487501553
So the query is rewritten as
select * from T order by time where time between time_min and 1487501553;
The second query condition is relaxed compared to the first query, so the second query will return more data than the first query result set. Suppose the data (time, uid) returned by the three sub-databases is as follows:
You can see:
(time_min = 1, time_min = 1, time_min = 1, time_min = 1, time_min = 1, time_min = 1, time_min = 1, time_min = 1, time_min = 1);
In the result set of sub-library 2, 1 more data is returned than in the first result set. The 1 record in the header (the record with the smallest time) is new (the pink record in the figure above).
In the result set of library 3, 2 more data are returned than in the first set. The 2 records in the header (the 2 records with the smallest time) are new (the pink records in the figure above).
Step 4: Virtual a time_min record in each result set and find the global offset of time_min
In the first library, the offset of time_min in the first library is 333;
In the second library, the offset of (1487501133, uid_aa) is 333 (based on the first query criteria), so the offset of virtual time_min in the second library is 331;
Voiceover: Deduce from 333.
In the third library, the offset of (1487501143, uid_aaa) is 333 (based on the first query criteria), so the virtual time_min offset in the third library is 330;
Voiceover: Deduce from 333.
The global offset of time_min is 333+331+330=994.
Step 5: Since the global offset of time_min is obtained, it is equivalent to the global view. According to the second result set, we can get the record of global offset 1000 limit 5
The second query returns an ordered set of results for each of the sub-libraries, and it is easy to know that the global offset of time_min is 994, so it is easy to know that the global offset 1000 limit 5 is one page (yellow).
The advantage of this method is that the data required by the business can be returned precisely, the amount of data returned each time is very small, and the amount of data returned will not increase with the page turning.
Handsome not handsome!!
conclusion
Today, we introduced four ways to solve the problem of “paging across N libraries” :
Method 1: global view method
(1) SQL rewrite, will
order by time offset X limit Y;
Rewrite into
order by time offset 0 limit X+Y;
(2) The service layer will sort the obtained N*(X+Y) data in memory, and then take the Y records after the offset X;
The performance of this approach gets worse and worse as the page turns.
Method 2: Prohibit page – hopping query
(1) use the normal method to get the first page data, and get the first page record time_max;
(2) Each turn of the page, will
order by time offset X limit Y;
Rewrite into
order by time where time>$time_max limit Y;
To ensure that only one page of data is returned at a time and the performance is constant.
Method three: allow fuzzy data method
(1) SQL query rewrite, will
order by time offset X limit Y;
Rewrite into
order by time offset X/N limit Y/N;
High performance, but the spliced result set is inaccurate.
Method four: the second query method
(1) SQL rewrite, will
order by time offset X limit Y;
Rewrite into
order by time offset X/N limit Y;
(2) Return multiple pages, find the minimum value time_min;
(3) Between Secondary query
order by time between
time_i_max;
(4) Set the virtual time_min, find the offset of time_min in each library, so as to get the global offset of time_min;
(5) The global offset of time_min is obtained, and the global offset X limit Y is obtained.
The article is long, I hope you have a harvest.
The thought is more important than the conclusion.
The architect’s path– Share technical ideas