Just because table paging/cross-library paging is hard to play doesn’t mean it isn’t

Cabbage Java self study room covers core knowledge

Cross-library/cross-instance Join does not have to rely on middleware

1. Data level segmentation

Many Internet services have the requirement of paging pull data, for example:

1. E-commerce mall system operator, paging pull order list view;
2. Post bar community system to see the post, paging pull post reply;
3. The small red dot in the upper right corner of the mobile phone APP opens and pulls the message list;

These business scenarios, if implemented with a database, often have the following commonalities:

1. The amount of data is often large;
2. Generally, the business primary key ID is designed.
3. Paging sort not by primary key, but by creation time;

When the amount of data is small, you can create an index on the sort field time, and use the offset/limit function provided by SQL to meet the demand of paging query:

SELECT * FROM `table` ORDER BY `time` LIMIT #{offset}, #{limit}
Copy the code

Requirement of separate database and table

When business data reaches a certain level (for example, the number of MySql records in a single table is more than 10 million), it is usually considered to split the data into different libraries or tables (horizontal partitioning of data), which can greatly improve read/write performance.

In the Internet architecture with high concurrency and heavy traffic, databases are generally accessed through the service layer. As the amount of data increases, databases need to be horizontally segmented and distributed to different database instances (even physical machines) to reduce the amount of data and increase the number of instances. When it comes to partitioning, there is no escape from the concept of “partitioning key”, which field is used to split the database horizontally: in most business scenarios, the business primary key ID is used.

After determining the partitioning key, the next step is to determine the partitioning algorithm: Most of the business scenarios will use the business primary key ID module algorithm to divide the library, so as to ensure that the data distribution of each library is uniform, and to ensure that the request distribution of each library is uniform, it is a simple load balancing method, this method is widely used in the Internet architecture.

SELECT * FROM table ORDER BY time LIMIT #{offset}, #{LIMIT} This article will discuss with you the new problem of “pagination” after dividing the database and table.

Note: this article mainly discusses the problem of “pagination” (data level segmentation scenario), the above is only the simplest example of the algorithm of library and table, the actual production environment will be much more complex, need to determine the library and table according to the specific business requirements.

2. Global vision

As shown in the figure, after the service layer distributes the data to two libraries by id module, each database loses its global view. After the data is sorted locally by time, the data on page 3 of any branch library may not be the data on page 3 of global sorting.

(1) In extreme cases, the data of the two libraries are exactly the same

If the two libraries have exactly the same data, just take half of each library offset and half of the page, which is the final desired data (as shown in the figure) :

(2) In extreme cases, the resulting data all come from the same library

For example, the time of all data of DB0 is greater than the time of all data of DB1. Then, the data on page 3 of a library may be the data on page 3 after global sorting (as shown in the figure) :

(3) In general, each library contains a part of the data

Normally, each library contains a portion of the global sorted page 3 data (see figure) :

Since it is not clear exactly what the case is, each library must return 3 pages of data, the resulting 6 pages of data are sorted in memory at the service layer to get a global view of the data, and the third page of data is fetched to get the desired global paging data.

To summarize the steps of this solution:

1. willorder by time offset X limit YRewrite intoorder by time offset 0 limit X+Y;
2. The service layer sends the rewritten SQL statement to each branch: 3 pages of data in each example;
3. Assuming a total of N libraries, the service layer will get N*(X+Y) pieces of data: 6 pages of data in the example;
4. The service layer sorts the N*(X+Y) data in memory, and then takes the Y records after the offset X, which is a page of data required by the global view.

Advantages of the scheme:

• Modify SQL statements through the service layer to expand the amount of data recall, so that the global view can be obtained, the business is not damaged, and the required data can be accurately returned.

Disadvantages of the scheme (obvious) :

• Each branch library needs to return more data, increasing the network transmission (network consumption);
• In addition to sorting databases by time, the service layer also needs to conduct secondary sorting, which increases the amount of computation (CPU consumption) of the service layer.
• Worst of all, the performance of this algorithm deteriorates dramatically as the page number increases, because the SQL rewrite returns X+Y rows for each branch: return page 3, X=200 in offset; If you want to return page 100, X=9900 in offset, that is, each branch library should return 100 pages of data, the amount of data and sorting will increase, and the performance will decrease in square order.

3. Business tradeoffs

Although the performance of “global vision method” is poor, but its business is not damaged, the data is accurate, can be regarded as a solution, is there a better solution? “Any architecture design divorced from the business is rogue”, technical solutions need to compromise, in the case of technical difficulties, business requirements compromise can greatly simplify the technical solution.

(1) Service compromise 1: prohibit page-hopping query

When there is a large amount of data and many pages to turn, many products do not provide the function of “jump directly to the specified page”, but only provide the function of “next page”. This small business compromise can greatly reduce the complexity of the technical solution.

As shown in the figure, skip page is not allowed, so the first time can only look up the first page:

1. The queryorder by time offset 0 limit 100Rewrite intoorder by time where time > 0 limit 100;
2. The above rewrite andoffset 0 limit 100Each branch returns a page of data (as shown in the figure).
3. The service layer gets 2 pages of data, sorts in memory, and takes out the first 100 pieces of data as the final first page of data, which is the global first page of data. Generally speaking, each branch library contains a part of data (as shown in the figure).

Question: this solution also requires server memory sorting, isn’t it the same as “global view method”? The first page of data is indeed pulled the same, but each “next page” pull scheme is different.

When clicking “Next page”, you need to pull the data of the second page. Based on the data of the first page, you can find the maximum value of time of the data of the first page:

The time_max of the previous page will be used as the query condition for the second page:

1. The queryorder by time offset 100 limit 100Rewrite intoorder by time where time > > $time_max limit 100;
2. Instead of returning 2 pages of data (” Global view method, will be rewritten asoffset 0 limit 200“), each branch library still returns a page of data (as shown in the figure);
3. The service layer gets 2 pages of data, sort in memory, and takes out the first 100 pieces of data as the final page 2 data. This global page 2 data is generally also a part of each branch library (as shown in the figure).
4. In this way, the query condition is not rewritten when the global view page 100 is queriedoffset 0 limit 9900+100(returns 100 pages of data), instead rewrite totime > $time_max99 limit 100(Each branch still returns one page of data) to ensure that the amount of data transferred and the amount of data sorted does not degrade as the page turns continue.

(2) Business compromise two: data accuracy loss is allowed

The “global view method” can return accurate data without damage to the service. When the number of pages is large, such as page 100, there may be performance problems. At this time, can the service accept that the returned 100 pages are not accurate data, but allow some data deviation?

Database branch – data balancing principle

When the data volume is large and the data distribution is random enough, the data distribution of all non-patition key attributes on each branch library is consistent in statistical probability.

For example, in the case of random uid, there are two libraries using uid, db0 and db1:

1. Gender attribute: if male users account for 70% of the db0 database, male users account for 70% of the DB1 database.
2. Age attribute: if the proportion of girls aged 18-28 in DB0 database is 15%, then the proportion of girls in DB1 database should also be 15%.
3. Time attribute. If 20% of users log in before 10:00 every day in THE DB0 library, the same statistical rule should be observed in DB1.

Using this principle, to query the global 100 pages of data, offset 9900 limit 100 to offset 4950 limit 50, offset 4950 limit 50 for each branch database (half), obtain 50 data (half page), and obtain the data set union. Is the global data offset 9900 limit 100 data, of course, this page of data accuracy, is not precise.

According to the actual business experience, users have to query the data of the webpage, post and email on the 100th page. The loss of the accuracy of the data on this page is usually acceptable in the business, but the complexity of the technical solution is greatly reduced. There is no need to return more data, and there is no need to conduct service memory sorting.

4. Secondary query method (recommended)

Is there a technical solution that can meet the precise needs of the business without compromising business performance? This is the ultimate weapon: the “quadratic query method”.

Select * from T order by time offset 1000 limit 5; select * from T order by time offset 1000 limit 5;

Step 1: Query SQL rewriting

Select * from T order by time offset 1000 limit 5 select * from T order by time offset 500 limit 5 This offset, 500, comes from the total offset of the global offset, 1000, divided by the number of horizontally shard databases, 2.

Select * from T order by time offset 333 limit 5 select * from T order by time offset 333 limit 5 And time is represented by a simple 8-digit number (see figure) :

As you can see, each branch returns a page of data sorted by time.

Step 2: Find the minimum value to return 3 pages of all data

1. In the first library, the minimum time value of 5 pieces of data is 10000123;
2. In the second library, the minimum time value of 5 pieces of data is 10000133;
3. In the third library, the minimum time value of 5 pieces of data is 10000143;

In these three pages of data, the minimum time value is from the first library, time_min = 10000123. This process only needs to compare the first data of each branch library, and the time complexity is very low.

Step 3: Query the SECONDARY rewriting of SQL

Select * from T order by time offset 333 LIMIT 5;

The second is to rewrite it into a “between” statement, where the starting point of “between” is time_min, and the ending point of “between” is the minimum value of data returned by each branch (” between “refers to >= and <=) :

1. The first branch, time_min is in the first branch, so you don’t need to query it.
2. The second branch library, rewrite asselect * from T order by time where time between time_min and 10000133;
3. The third branch library, I’ll rewrite it asselect * from T order by time where time between time_min and 10000143;

The second query assumes that the three branches return the following data (of course we only need to query two libraries) :

Step 4: Analyze the secondary query results

Leaving the time sort unchanged, we put together the result set of the second query to get the latest result set (as shown) :

Now let’s do a simple mental reasoning:

1. Our initial need is toselect * from T order by time offset 1000 limit 5;
2. And then because of the reason of the sub-library, we are divided into three sub-librariesselect * from T order by time offset 333 limit 5;
3. If time_min is smaller than time_min, 333 * 3 = 999 (offset = 0) Offset = 333 is the 34th result), so assume offset = 999 for time_min;
4. Without a second query, we can’t get offset = 1000 ~ 1004, because I’m not sure between time_min (10000123) and (10000133), Whether there are other results between time_min (10000123) and (10000143) does not give a global view;
5. Make a second query, the second branch library, rewrite asselect * from T order by time where time between time_min and 10000133, the third branch library, rewrite asselect * from T order by time where time between time_min and 10000143To get the global view, we can sort labels in memory;
6. Before the second query, it is assumed that there are 999 results smaller than time_min. Since the results of the second query are obtained, the three results (10000132,10000141,10000142) are counted in the 999 results assumed by us, that is, these three results need to be moved later. Offset of time_min = 996 = 999-3;

Step 5: Global view result label

The global offset of time_min is obtained, which is equivalent to the global view. According to the total quadratic result set, the records of global offset 1000 limit 5 can be obtained.

Advantages of the scheme:

• The data required by services can be returned precisely. The amount of data returned each time is very small, and the amount of data returned does not increase with page turning.

Disadvantages of the scheme:

• Two database queries are required, which has some consumption to the database, but less network and CPU consumption than the global view method.

Cross-library/cross-instance Join does not have to rely on middleware