This paper mainly describes the algorithm scheme of sub-database and sub-table, according to what rules. After a step-by-step comparison of the several regular approaches that have emerged so far, the fifth incremental migration solution is the one I envision and recommend. In the following chapters, we will talk about the problems caused by the technology selection and the classification of database and table.

background

With the increase of service volume and data volume, a table will store a large amount of data. When a table has 10 million rows of data, SQL optimization and machine performance improvement can also bear. For the long-term perspective of the future, we should divide the database into tables to a certain extent, such as database performance bottlenecks, adding fields need to take a long time. Solve the independent node to bear all the pressure of data, distribution of multiple nodes, provide fault tolerance, do not have to hang the entire system can not access.

purpose

In this paper, the scheme of dividing database and table is based on the case of horizontal segmentation, choosing different rules and comparing the advantages and disadvantages of rules. General online on the first three, a little bit normal will say the fourth, but not perfect, the first few kinds of migration data will have a great impact, I recommend a better plan five.

  • Scheme 1: Modulus the Key, and the divisor increases gradually
  • Plan 2: Divide by time
  • Scheme 3: according to the numerical range
  • Scheme 4: Consistent Hash concept — average distribution scheme (This is used by Dianping, 200G and achieved in one step)
  • Option 5: Consistent Hash concept — add nodes iteratively (to facilitate incremental migration)
  • Scheme 6: Consistent Hash concept — Separate libraries by scope (iterative migration)

The author

Hid in Kelvin

Public account: Dizang Thinking

Scheme selection

Scheme 1: Modulus the Key, and the divisor increases gradually

Key mod x (x is a natural number)

Key can be the primary Key, order number, or user ID. This depends on the scenario, which is used as the probability of query conditions.

Advantages:

  • Add libraries and tables as needed, step by step
  • Evenly distributed, with little variation in each piece

Disadvantages:

  • A lot of times you start with two libraries and then you start with three, four, five. For example, when mod 3 is changed to MOD 5, the result of most of the data will change. For example, when key=3, mod 3=0, suddenly changed to MOD 5=3, it will migrate from the 0 table to the 3 table, which will cause a lot of data to move positions repeatedly.
  • Data will be migrated repeatedly. When divided into 2, data A is in table 0; when divided into 3, data A goes to table 1; when divided into 4, data A will return to table 0

Plan 2: Divide by time

You can do it daily, monthly or quarterly.

Tb_20190101 tb_20190102 tb_20190103...Copy the code

This algorithm requires the order number and userId to add the year, month, date or time stamp, or query interface with the year, month, date, to locate the shard.

Advantages:

  • Data is continuous in time
  • It’s pretty straightforward to look at the growth

Disadvantages:

  • Considering that the order number of historical data does not have time stamp when the historical data is divided into database and table at the beginning and then is divided into database and table later, the historical data may be self-increasing or distributed primary key derived from custom algorithm, so the upstream system must transmit two fields of order number and creation time during query.
  • If the upstream system does not transmit the time, or the creation time of the upstream system is not the same day as the creation time of the corresponding order in the current system, the data record of the current database table must contain the time field. Because the upstream system only sends the order number, the creation time needs to be obtained. Therefore, the current system must have a master table to maintain the relationship between the order number and creation time. In addition, each query needs to check the current system master table first and then the specific table, which will consume performance.
  • The distribution is not necessarily uniform: monthly growth figures vary, and some months may be more than others

Recommended usage scenario: Log

Scheme 3: according to the numerical range

Table 0 [0 10000000) table 1 [10000000000,20000000) table 2 [20000000,30000000) table 3 [30000000,40000000)......Copy the code

Advantages:

  • Uniform distribution of

Disadvantages:

  • Because the maximum value is unknown, the timestamp cannot be used as the key. This method cannot use the increment primary key of the table because each increment is not uniformly maintained. Therefore, there needs to be a transmitter or transmitter system to do unified maintenance of the key increment.

In the following recommended solutions, we will briefly talk about consistency hash

Let’s talk about consistent hash. Some articles say that consistent hash is an algorithm. I think it is not a specific calculation formula, but a set of ideas.

1. Assume a circular Hash space with fixed maximum and minimum values on the ring, head to tail, forming a closed loop, such as the maximum and minimum values of int and long. Many articles assume 2^32 positions with a maximum value of 2^32-1 and a minimum value of 0, i.e., 0~(2^32)-1. They are just following the common hash algorithm example, not using this number in the case of real table and library, which is why I think the consistent hash algorithm is actually a concept, not a real calculation formula. The following figure

summary

This theory is not explained in detail here. It mainly means that if the maximum value is fixed, the range from maximum to minimum value will not be changed. Subsequently, only the position of nodes and nodes will be changed and added to reduce the data to be managed by each node, so as to reduce the pressure.

Note: * This parameter is not recommended for IP addresseshashBecause it may lead tohashThe result of (IP) is very large, such as 60, if there is no node in front of the node, the node at position 60 needs to handle most of the data. * The best way to generate keys is to use the snowFlake algorithm, at least if you don't duplicate numbers and don't increment them. * It is recommended to add user%64 to the end of the solution order number in Copper Plate StreetCopy the code

Scheme 4: Consistent Hash concept — evenly distributed scheme

Based on the consistent hash theory, the base formula for selecting hash(key) is value= key mod 64, the base formula for selecting hash(key) is value= key / 64 mod 64, and key is the main field that is frequently queried, such as order number or userId. (This formula will be changed later.) Assuming the above formula, we can divide 64 libraries with 64 tables per library, assuming a table with 10 million rows. Then the maximum data is 64 * 64 * 10 million. I believe this day will not come, so it is reasonable for us to take this as the maximum value, or even choose 32 * 32.

Since there is no need to use so many tables in the early stage, it would be a waste of machine to build so many tables and insert data into each table at the beginning. Therefore, when we know the maximum value, we start to use small numbers, so we will group the values calculated above.

Grouping formula: 64 = Number of count * groups Number of groups Data location in the ring (that is, in which library) : value = key mode 64 / count * countCopy the code

In this case, the formula of the library is value = key mode 64/4 * 4. After dividing by 4, the decimal place will be truncated to obtain an integer, and then * 4 times, which is the location of the data.

// Create a group of 4 tables
count = 4: Integer dbValue = userId %64 / count * count ;
Copy the code

hash(key) is between 0 and 3 in library 0hash(key) is between 4 and 7 in library 4hashBetween 8 and 11 in library no. 8...Copy the code

Note: in fact, a group of 64 libraries can be a library at the beginning, and the subsequent change of 32 libraries into a group is two libraries, from one library to two libraries, and then to 4 libraries, step by step.

Iteration of expansion starting from fen 1 library:

The example shown in the following figure is divided into 32 groups after 16 groups. Half of the data in each library needs to be migrated to the new data and expanded to 64 groups.

It can be seen that when doubling the capacity, half of the data volume needs to be migrated, increasing by 2^n, so the impact range is relatively large.

Advantages:

  • If you split the 32 groups, then the comparison is done for good
  • If the amount of data is relatively large, not excessive table can be used once and for all.
  • Uniform distribution of
  • There is no need to migrate data as in scheme 1, most of the data needs to be migrated and there are repeated migrations, only half of the data needs to be migrated

Disadvantages:

  • It can be extended, but the scope of influence is large.
  • The amount of data to be migrated is large, although not as large as in scenario 1, where half of the data is migrated for each table or library.
  • Once and for all, a total shutdown is required to migrate data

Scheme 5: Consistent Hash concept — add nodes iteratively

(I think the better plan)

The consistent hash scheme is combined with the comparison scope scheme, which is the combination of scheme 3 and Scheme 4.

Analyze the problem of plan 4

The fourth scheme is to set the maximum range of 64, and increase the number of libraries or tables from 1 in the form of 2^ N exponent, so that each split will affect 1/2 of the total data amount when migrating, so the influence range is relatively large, so either directly split to 32 groups, 64 groups once and for all, or each 1/2 migration.

Corresponding migration scheme of Scheme 4:

  1. The first is to stop and migrate data, and then restart the server after success. All users are affected for a long time.
  2. The second way is to switch the data source to the slave database and let the user read only. The master database migrates the data and then switches to the master database after the data is successfully migrated. Although the user can apply, the service increment is affected
  3. The third way is to set the data source according to the rules so that half of the users can read only, and the other half can read and write. Because plan 4 migration affects general data, this way can be achieved at most.

Detailed explanation of plan 5

Now, I’m going to keep the hash idea consistent, one node at a time, instead of two to the n minus n nodes at a time. But the code needs to determine the hash value of the data in the new node.

Let’s do the following iteration demonstration based on the case that two libraries have been split in one iteration. First, let’s look at the case that two libraries have been split:

Data falls into library 64 named DB64 and library 32 named DB32

Iteration 2: The difference is that two nodes are directly added in scheme 4. We only add one node, so that data migration will affect only one quarter of users instead of the original one half.

// Create a group of 16 libraries from 32 to 4
count = 16; Integer dbValue = userId %64 / count * count ;
if(dbValue<16) {// The data was stored in db32 in the last iteration. Now go to db16
    dbValue =  16;
    return dbValue;
} else {
    // Follow the original rules
    return dbValue;
}
Copy the code

Iteration 3:

You can go live before migration and add a switch code that asks the interface to handle order numbers or user numbers with a hash value less than 16, so that only 1/4 of the people are affected

// Add logic to the request interface
    public void doSomeService(Integer userId){
        if(Switch to see if migration is complete){// If not completed
            Integer dbValue = userId  % 64 / count * count ;
            if(dbValue<16) {// This part of the user can not go through the following logic
                return; }}returndbValue; }}Copy the code
// Divide the library into two libraries in a group of 32
count = 16; Integer dbValue = userId %64 / count * count ;
if(dbValue<16) {// In the last iteration, these data fell in DB32, and half of them need to go to the library named DB16
    if(Switch to see if migration is complete){// If done, go to db16's library
        dbValue =  16;
    }
    return dbValue;
} else {
    // Follow the original rules
    return dbValue;
}
Copy the code

And so on, with a total of eight nodes in the next round, only 1/8 of each migration is required.

In fact, the first iteration can be done without selecting dbValue less than 16. Directly divide them into a group of 8 and select only those with dbValue<8, so that the influence range of the first iteration will be smaller than that of the case. The above case is better demonstrated with 16

Advantages:

  • extensible
  • In the process of gradually increasing data, slowly add nodes
  • The number of users is small
  • Proceed iteratively to reduce risk
  • Short migration time, such as agile iterative thinking

Disadvantages:

  • Uneven for a period of time

Scheme 6: Consistent Hash concept — Separate libraries by scope (iterative migration)

Just as plan 5 is Plan 4 + Plan 1, which can achieve gradual data migration, there is another plan. It’s plan four plus plan three, except instead of taking modules and grouping them.

userId % 64 / count * count

Because of the above formula, the results may not be evenly distributed in every piece of data. In fact, we can take the module, according to the scope of the partition, the following formula.

First slice 0<userId % 64<15 second slice 16<userId % 64<31 third slice 32<userId % 64<47 fourth slice 48<userId % 64<63Copy the code

Of course, the range can be customized to see which value falls into a larger number after taking the module, just cut a certain piece of data, without drawing a graph, similar to plan 4.

Due to the reason of data migration, in plan 4, if the data volume reaches 10 million rows, a lot of data needs to be migrated each time, so many companies will divide the database and table as soon as possible.

But in the business-first case, iterating over the business all the time, we can use the idea of consistent hashing — splitting the repository by scope — when we get to a lot of data in 16 branches and a lot of data

Welcome to attention

My public account: Tibet thinking

Nuggets of gold: Hide Kelvin

Jane: Hide Kelvin

CSDN: Underground Collection of Kelvin

My Gitee: Underground Collection Kelvin gitee.com/dizang-kelv…