CN112000467A - Data tilt processing method and device, terminal equipment and storage medium - Google Patents

Abstract

The invention discloses a data inclination processing method, device, terminal equipment and storage medium, including sampling data based on a preset sampling algorithm to obtain equal-probability sample data, and obtaining the value of each value by accumulating the data. The size of the space occupied; the sample data is divided into oblique data and non-oblique data by using a data oblique detection model; the non-oblique data is allocated to a preset Hash partition, and the oblique data is dynamically allocated based on a dynamic allocation algorithm to each bucket to balance the Spark load. In the embodiment of the present invention, a variable weight is added to predict the partition size, after sampling the data, the data is classified into oblique data and non-slanted data by using a data skew detection model, the size of the Reduce partition is predicted by using the non-slanted data, and the skewed data is Balanced distribution to each partition can make Spark load more balanced.

Description

A data tilt processing method, device, terminal device and storage medium

technical field

The invention relates to the technical field of computer applications, in particular to a data tilt processing method.

Background technique

With the advent of the era of big data and the rise of various network technologies, information data has expanded rapidly. Traditional processing and storage systems have been unable to cope with massive data, and for currently popular big data analysis platforms such as Hadoop and Spark, data skew has a serious impact on their performance. At present, most of the research on solving the data skew problem is based on the Hadoop platform, and there is relatively little research on Spark's data skew problem. In Spark, the stage before Shuffle is called the Map stage, and the stage after it is called the Reduce stage. However, when the data distribution is uneven, the default Spark partitioning algorithm will skew the data after performing the Shuffle operation. The existing partition algorithm idea is to distribute the overloaded tasks to additional split or merge partitions, and these additional operations in turn hinder the performance of the system.

SUMMARY OF THE INVENTION

The present invention provides a data skew processing method to solve the technical problem that the existing partition algorithm has additional operations hindering the system performance. By adding a variable weight to predict the partition size, after sampling the data, the data skew detection model is used to analyze the data. It is classified into slanted data and non-slanted data. Using the non-slanted data to predict the size of the Reduce partition, and evenly assigning the slanted data to each partition, can make the Spark load more balanced.

In order to solve the above technical problems, in a first aspect, an embodiment of the present invention provides a data skew processing method, including the following steps:

Based on the preset sampling algorithm, the data is sampled to obtain equal probability sample data, and the size of the space occupied by each value is obtained through the cumulative calculation of the data;

Using a data skew detection model to divide the sample data into skewed data and non-slanted data;

The non-inclined data is allocated to a preset Hash partition, and the skewed data is dynamically allocated to each storage partition based on a dynamic allocation algorithm to balance the Spark load.

In one embodiment of the present invention, the preset sampling algorithm includes:

Extract K sample data from the intermediate data with a total amount of A; among them, K is less than A;

Putting the extracted 1st to Kth sample data into the sample array;

The K+1th data in the intermediate data is traversed in sequence, so that the selection probability of the xth element in the sample array is k/x, and the elements in the sample array are replaced with an equal probability of 1/k.

In one of the embodiments of the present invention, the skewed data is dynamically allocated to each storage partition based on a dynamic allocation algorithm, specifically:

After identifying the tilt data using the data tilt detection model, assigning the tilt data to a map task;

Split and generate intermediate output data through the map task process;

The intermediate output data is allocated to at least one reduce task based on the dynamic allocation algorithm.

In one embodiment of the present invention, the dynamic allocation algorithm is configured to allocate the skew data detected by the data skew detection module to the Reducer with the smallest current load.

Sort the keys in the bucket in descending order and mark the largest key as 1 and the rest as 0.

In one of the embodiments of the present invention, the use of a data tilt detection model to divide the sample data into tilted data and non-skewed data is specifically:

表示负载大小，

表示的第j个value值，则Assume

represents the load size,

represents the jth value of the value, then

The load average is:

Measure the standard deviation of the overall load balance level:

Load balance is measured by the coefficient of deviation:

Compute the standard deviation used to reflect the skewed range of the data for the initial set of clusters:

Measure the overall deviation of all cluster sets:

The degree of inclination of the data is determined based on the comparison result between the preset intermediate value w and the FoD, so that the sample data is divided into oblique data and non-oblique data; wherein, w is the preset intermediate value.

In a second aspect, an embodiment of the present invention further provides a data tilt processing device, including:

The data sampling module is used to sample the data to obtain equal probability sample data based on the preset sampling algorithm, and obtain the size of the space occupied by each value through the cumulative calculation of the data;

a data division module, configured to use a data skew detection model to divide the sample data into skewed data and non-slanted data;

A data allocation module, configured to allocate the non-inclined data to a preset Hash partition, and dynamically allocate the skewed data to each storage partition based on a dynamic allocation algorithm to balance Spark loads.

In one embodiment of the present invention, the preset sampling algorithm includes:

Extract K sample data from the intermediate data with a total amount of A; among them, K is less than A;

Putting the extracted 1st to Kth sample data into the sample array;

The K+1th data in the intermediate data is traversed in sequence, so that the selection probability of the xth element in the sample array is k/x, and the elements in the sample array are replaced with an equal probability of 1/k.

In one of the embodiments of the present invention, the data distribution module is further configured to:

After identifying the tilt data using the data tilt detection model, assigning the tilt data to a map task;

Split and generate intermediate output data through the map task process;

The intermediate output data is allocated to at least one reduce task based on the dynamic allocation algorithm.

In one embodiment of the present invention, the dynamic allocation algorithm is configured to allocate the skew data detected by the data skew detection module to the Reducer with the smallest current load.

In one embodiment of the present invention, the data division module is used for:

表示负载大小，

表示的第j个value值，则Assume

represents the load size,

represents the jth value of the value, then

The load average is:

Measure the standard deviation of the overall load balance level:

Load balance is measured by the coefficient of deviation:

Compute the standard deviation used to reflect the skewed range of the data for the initial set of clusters:

Measure the overall deviation of all cluster sets:

The degree of inclination of the data is determined based on the comparison result between the preset intermediate value w and the FoD, so that the sample data is divided into oblique data and non-oblique data; wherein, w is the preset intermediate value.

In a third aspect, the present invention further provides a terminal device, including a processor, a memory, and a computer program stored in the memory and configured to be executed by the processor, and the processor implements the computer program when the processor executes the computer program. The data skew processing method as described above.

In a fourth aspect, the present invention also provides a computer-readable storage medium, where the computer-readable storage medium includes a stored computer program, wherein, when the computer program runs, the device where the computer-readable storage medium is located is controlled to execute as above The data skew processing method.

Compared with the prior art, an embodiment of the present invention provides a data tilt processing method, device, terminal device, and storage medium, an embodiment of which has the following beneficial effects:

The algorithm predicts the size of the storage partition by using the preset sampling algorithm. After sampling the data, the data skew detection model is used to classify the data into skewed data and non-skewed data, and the non-skewed data is used to predict the size of the Reduce partition and balance the skewed data. Distributed to each partition, this mechanism can make Spark load more balanced.

Description of drawings

In order to illustrate the technical solutions of the present invention more clearly, the following will briefly introduce the accompanying drawings used in the embodiments. Obviously, the drawings in the following description are only some embodiments of the present invention, which are common in the art. As far as technical personnel are concerned, other drawings can also be obtained based on these drawings without any creative effort.

Fig. 1 is the step flow chart of the data skew processing method in the embodiment of the present invention;

FIG. 2 is a general framework diagram of SP-IRS in the data skew processing method in the embodiment of the present invention.

Detailed ways

The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only a part of the embodiments of the present invention, rather than all the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative efforts shall fall within the protection scope of the present invention.

Nowadays, with the rapid development of informatization and digitization, the scale of data is growing exponentially. Therefore, Gartner gives the definition of 3V according to the definition of big data, specifically Volume, Variety and Velocity. On this basis, the International Data Corporation (IDC) developed the 4V definition. He believes that the definition of big data should also have value, so the processing of big data has great research value.

In theory, the data generated by many application scenarios are skewed, and the law is consistent with Pareto's "28 law": in anything, the most important only accounts for a small part of about 20% of it , while the remaining part accounts for as high as 80%. Mass production of data and a large amount of hot data lead to uneven data distribution, resulting in data skew.

An existing algorithm called SCID (Split and Combine Algorithm for Skewed Intermediate Data Blocks) is used to make the load more balanced on the Reducers in Spark. In this method, a sampling job based on reservoir sampling must be run first, then the cluster size is estimated by sampling, multiple clusters are identified, and in the next step, the algorithm attempts to split the multiple clusters. The reservoir sampling algorithm adds extra steps, which increases the running time of the Spark platform, and the extra splitting and aggregation wastes the resources of the cluster.

In view of this, the present invention takes the data skew problem in Spark as the research object, and focuses on how to reduce the total completion time of the application program through partition load balancing. As shown in Figure 2, the execution framework of the entire model is shown in Figure 2, which consists of two independent jobs. First, the original input data is sampled using an improved reservoir sampling algorithm. The output of this stage is a matrix that records the size and key-value distribution of the current input data to determine the allocation of reduce tasks. Before running the tasks, the assignment of reduce tasks is done according to this matrix. In this way, most of the data processed by the reduce task is localized as much as possible, which saves traffic costs and improves the performance of the reduce task.

First input data is loaded into one or more distributed file systems (such as HDFS), where each file is divided into smaller chunks called input splits. The data are sampled with the reservoir sampling algorithm, and then the skewed data is identified by the improved data skew detection model, and the skewed data is assigned to a map task. The map task process splits and generates intermediate outputs, and then these outputs are dynamically partitioned. Algorithms are assigned to one or more reduce tasks. Specifically, as shown in FIG. 1, an embodiment of the present invention provides a data skew processing method, including the following steps:

S1. Based on the preset sampling algorithm, the data is sampled to obtain equal probability sample data, and the size of the space occupied by each value is obtained through the cumulative calculation of the data, which can conveniently count which keys correspond to the most value values;

In this embodiment, the preset sampling algorithm includes:

Extract K sample data from the intermediate data with a total amount of A; among them, K is less than A;

Putting the extracted 1st to Kth sample data into the sample array;

The K+1th data in the intermediate data is traversed in sequence, so that the selection probability of the xth element in the sample array is k/x, and the elements in the sample array are replaced with an equal probability of 1/k.

As an example, the load balancing mechanism based on the improved reservoir sampling algorithm: SP-IRS (Spark loadbalancing mechanism based on Improved Reservoir Sampling algorithm). After adding a variable weight to the traditional reservoir sampling algorithm to predict the size of the partition, the data skew detection model is used to classify the data into skewed data and non-slanted data, and finally the skewed data is dynamically allocated to each partition in a balanced manner.

The idea of the reservoir sampling algorithm is to assume that k samples are drawn from the data of the total amount of intermediate data A, and the first k samples extracted are put into the array, and then traversed from the k+1th data in turn, in the process of traversal can ensure that the selection probability of the xth element is k/x, and then replace the elements in the sample array 1/k. The reservoir sampling algorithm can extract sample data with equal probability in the case of unknown data volume. The improved reservoir sampling algorithm accumulates the amount of intermediate data while sampling. In this embodiment, by adding a variable weight to the above-mentioned reservoir sampling algorithm, the partition size can be predicted. The improved sampling algorithm is as follows:

This embodiment uses an improved reservoir sampling algorithm, which specifically uses the algorithm to calculate the size of the space occupied by each value during the sampling process. This added step can not only save the amount of data, but also allocate space for the next step. Save necessary work.

S2, using a data skew detection model to divide the sample data into skewed data and non-slanted data;

In the present embodiment, the improved data detection model is used to divide the data obtained by the improved reservoir sampling algorithm into two parts, for example, the original RDD_1 is divided into RDD_11 and RDD_12, wherein RDD_11 represents the inclined key, and RDD_12 represents the key without inclination; The data skew model of this embodiment is:

表示k_i的第j个value，其Reducer负载大小为

其中key对应的所有value值，可表示为

Assumption

Represents the jth value of k _i , and its Reducer load size is

All the value values corresponding to the key can be expressed as

Therefore, the number of <key, value> pairs contained in the Reducer is shown in formula (1):

According to the above description, the average load of each Reducer can be calculated according to formula (2):

After the average load of each Reducer is calculated, it is necessary to uniformly quantify the difference between the obtained averages. The standard deviation std used to measure the overall load balance level of the Reducer is specifically defined, which can be represented by formula (3):

Since the standard deviation std is usually used to reflect the range of sequence fluctuations, we can use the metric FoS (coefficient of deviation) to measure the load balance of all Reducers, as shown in Equation (4):

On the basis of FoS, for the same reason, the standard deviation is used to reflect the data skew range of the initial cluster set, as shown in Equation (5):

The FoD metric is used to measure the overall deviation of all cluster sets, as shown in Equation (6):

In the later stage, the intermediate value w is determined according to relevant experiments. When the condition is met, the data skew degree of FoD≤w is slightly skewed. When this condition FoD≥w is satisfied, the skewness of the data will be great.

The idea of the traditional reservoir sampling algorithm is to assume that k samples are drawn from the data of the total amount of intermediate data A, put the first k samples extracted into the array, and then traverse from the k+1th data in turn. In the process of , it can ensure that the selection probability of the xth element is k/x, and then replace the elements in the sample array by 1/k. The reservoir sampling algorithm can extract sample data with equal probability in the case of unknown data volume. The improved reservoir sampling algorithm accumulates the amount of intermediate data while sampling.

Next, in order to make the data in each Reducer roughly the same, a dynamic allocation algorithm is proposed. The keys in the partition are sorted in descending order, marking the largest key as 1 and the rest as 0. After the allocation of each cluster is completed, according to the partition size predicted by the improved reservoir sampling algorithm, sort again in descending order, and repeat the above cluster allocation process. The details are shown in step S3.

S3. Allocate the non-inclined data to a preset Hash partition, and dynamically allocate the skewed data to each storage partition based on a dynamic allocation algorithm to balance Spark loads.

In this embodiment, the skewed data is dynamically allocated to each storage partition based on a dynamic allocation algorithm, specifically:

After identifying the tilt data using the data tilt detection model, assigning the tilt data to a map task;

Split and generate intermediate output data through the map task process;

The intermediate output data is allocated to at least one reduce task based on the dynamic allocation algorithm.

The data statistics are obtained by improving the sampling algorithm of the reservoir. The main idea of the dynamic allocation algorithm is to allocate the skew data detected by the skew detection algorithm to the Reducer with the smallest current load. The keys in the partition are sorted in descending order, marking the largest key as 1 and the rest as 0. After the allocation of each cluster is completed, according to the current remaining capacity of all Reducers, sort them in descending order again, and repeat the above cluster allocation process. As an example, the dynamic allocation algorithm is:

To sum up, the embodiments of the present invention provide a data skew processing method. First, in some data skew models proposed by other scholars, in order to better measure the skew degree of the data, an improved data skew model is defined to measure the intermediate The skewness of the data can be defined more accurately and the job running time of the application can be reduced; then a reservoir sampling algorithm is proposed. A variable weight is added to the sampling algorithm to predict the partition size. After sampling the data, the data skew detection model is used to classify the data into skewed data and non-skewed data, and the non-skewed data is used to predict the size of the Reduce partition and balance the skewed data. Distributed to each partition, this mechanism can make Spark load more balanced.

The present invention also provides a data tilt processing device, comprising:

The data sampling module is used to sample data to obtain equal probability sample data based on a preset sampling algorithm;

a data division module, configured to use a data skew detection model to divide the sample data into skewed data and non-slanted data;

The data allocation module is configured to predict the size of the storage partition according to the non-inclined data, and dynamically allocate the skewed data to each storage partition based on the dynamic allocation algorithm to balance the Spark load.

In one embodiment of the present invention, the preset sampling algorithm includes:

Extract K sample data from the intermediate data with a total amount of A; among them, K is less than A;

Putting the extracted 1st to Kth sample data into the sample array;

The K+1th data in the intermediate data is traversed in sequence, so that the selection probability of the xth element in the sample array is k/x, and the elements in the sample array are replaced with an equal probability of 1/k.

In one of the embodiments of the present invention, the data distribution module is further configured to:

After identifying the tilt data using the data tilt detection model, assigning the tilt data to a map task;

Split and generate intermediate output data through the map task process;

The intermediate output data is allocated to at least one reduce task based on the dynamic allocation algorithm.

In one embodiment of the present invention, the data division module is used for:

表示负载大小，

表示的第j个value值，则Assume

represents the load size,

represents the jth value of the value, then

The load average is:

Measure the standard deviation of the overall load balance level:

Load balance is measured by the coefficient of deviation:

Compute the standard deviation used to reflect the skewed range of the data for the initial set of clusters:

Measure the overall deviation of all cluster sets:

The degree of inclination of the data is determined based on the comparison result between the preset intermediate value w and the FoD, so that the sample data is divided into oblique data and non-oblique data; wherein, w is the preset intermediate value.

The present invention also provides a terminal device, including a processor, a memory, and a computer program stored in the memory and configured to be executed by the processor, when the processor executes the computer program, the above-mentioned computer program is implemented Data skew processing method.

Exemplarily, the computer program may be divided into one or more modules/units, and the one or more modules/units are stored in the memory and executed by the processor to accomplish the present invention. The one or more modules/units may be a series of computer program instruction segments capable of performing specific functions, and the instruction segments are used to describe the execution process of the computer program in the terminal device.

The terminal device may be a computing device such as a desktop computer, a notebook, a palmtop computer, and a smart tablet. The terminal device may include, but is not limited to, a processor and a memory. Those skilled in the art can understand that the above components are only examples of terminal equipment, and do not constitute a limitation to the terminal equipment, and may include more or less components than the above, or combine some components, or different components, such as all The terminal device may also include input and output devices, network access devices, buses, and the like.

The processor may be a central processing unit (Central Processing Unit, CPU), other general-purpose processors, digital signal processors (Digital Signal Processor, DSP), application specific integrated circuits (Application Specific Integrated Circuit, ASIC), off-the-shelf processors Programmable Gate Array (Field-Programmable Gate Array, FPGA) or other programmable logic devices, discrete gate or transistor logic devices, discrete hardware components, etc. The general-purpose processor can be a microprocessor or the processor can also be any conventional processor, etc. The processor is the control center of the terminal device, and uses various interfaces and lines to connect various parts of the entire terminal device.

The memory can be used to store the computer program and/or module, and the processor implements the terminal by running or executing the computer program and/or module stored in the memory and calling the data stored in the memory various functions of the device. The memory may mainly include a stored program area and a stored data area, wherein the stored program area may store an operating system, an application program required for at least one function (such as a sound playback function, an image playback function, etc.), etc.; the storage data area may store Data (such as audio data, phonebook, etc.) created according to the usage of the mobile phone, etc. In addition, the memory may include high-speed random access memory, and may also include non-volatile memory such as hard disk, internal memory, plug-in hard disk, Smart Media Card (SMC), Secure Digital (SD) card , a flash memory card (Flash Card), at least one magnetic disk storage device, flash memory device, or other volatile solid-state storage device.

Wherein, if the modules/units integrated in the terminal device are implemented in the form of software functional units and sold or used as independent products, they may be stored in a computer-readable storage medium. Based on this understanding, the present invention can implement all or part of the processes in the methods of the above embodiments, and can also be completed by instructing relevant hardware through a computer program, and the computer program can be stored in a computer-readable storage medium. When the program is executed by the processor, the steps of the foregoing method embodiments can be implemented. Wherein, the computer program includes computer program code, and the computer program code may be in the form of source code, object code, executable file or some intermediate form, and the like. The computer-readable medium may include: any entity or device capable of carrying the computer program code, a recording medium, a U disk, a removable hard disk, a magnetic disk, an optical disk, a computer memory, a read-only memory (ROM, Read-Only Memory) , Random Access Memory (RAM, Random Access Memory), electric carrier signal, telecommunication signal and software distribution medium, etc. It should be noted that the content contained in the computer-readable media may be appropriately increased or decreased according to the requirements of legislation and patent practice in the jurisdiction, for example, in some jurisdictions, according to legislation and patent practice, the computer-readable media Electric carrier signals and telecommunication signals are not included.

It should be noted that the device embodiments described above are only schematic, wherein the units described as separate components may or may not be physically separated, and the components displayed as units may or may not be physical unit, that is, it can be located in one place, or it can be distributed over multiple network units. Some or all of the modules may be selected according to actual needs to achieve the purpose of the solution in this embodiment. In addition, in the drawings of the apparatus embodiments provided by the present invention, the connection relationship between the modules indicates that there is a communication connection between them, which may be specifically implemented as one or more communication buses or signal lines. Those of ordinary skill in the art can understand and implement it without creative effort.

The above are the preferred embodiments of the present invention. It should be pointed out that for those skilled in the art, without departing from the principles of the present invention, several improvements and modifications can also be made, and these improvements and modifications may also be regarded as It is the protection scope of the present invention.

Claims (10)

1. A data skew processing method, comprising the steps of:

based on a preset sampling algorithm, sampling data to obtain sample data with equal probability, and obtaining the size of the space occupied by each value through the accumulative calculation of the data;

dividing the sample data into oblique data and non-oblique data by using a data oblique detection model;

and distributing the non-tilting data to a preset Hash partition, and dynamically distributing the tilting data to each storage partition based on a dynamic distribution algorithm so as to balance Spark load.

2. The data skew processing method of claim 1, wherein the predetermined sampling algorithm comprises:

extracting K sample data from the intermediate data with the total amount of A; wherein K is less than A;

putting the extracted sample data from the 1 st to the Kth sample data into a sample array;

and sequentially traversing the K +1 th data in the intermediate data to enable the selected probability of the x-th element in the sample array to be K/x, and replacing the elements in the sample array with equal probability of 1/K.

3. The data skew processing method of claim 1, wherein the dynamically allocating the skew data to each memory partition based on a dynamic allocation algorithm is specifically:

after identifying the tilt data using the data tilt detection model, assigning the tilt data to a map task;

splitting and generating intermediate output data through the map task process;

allocating the intermediate output data into at least one reduce task based on the dynamic allocation algorithm.

4. The data skew processing method of claim 1 or 3, wherein the dynamic allocation algorithm is configured to allocate the skew data detected by the data skew detection module to a Reducer with a minimum current load.

5. The data skew processing method of claim 1, wherein the dividing the sample data into skewed data and non-skewed data by using the data skew detection model specifically comprises:

is provided with

The magnitude of the load is represented by,

the jth value of the representation, then

The average load value is:

standard deviation of the total load balancing level was measured:

load balancing is measured by the bias coefficients:

calculating a standard deviation reflecting a data tilt range of the initial cluster set:

measure the overall deviation of all cluster sets:

judging the inclination degree of the data according to the comparison result of preset intermediate values w and FoD, thereby dividing the sample data into inclined data and non-inclined data; wherein w is a preset intermediate value.

6. A data skew processing apparatus, comprising:

the data sampling module is used for sampling the data based on a preset sampling algorithm to obtain sample data with equal probability, and the size of the space occupied by each value is obtained through the accumulative calculation of the data;

the data dividing module is used for dividing the sample data into oblique data and non-oblique data by using a data oblique detection model;

and the data distribution module is used for distributing the non-tilting data to a preset Hash partition, and dynamically distributing the tilting data to each storage partition based on a dynamic distribution algorithm so as to balance Spark load.

7. The data skew processing apparatus of claim 6 wherein the predetermined sampling algorithm comprises:

extracting K sample data from the intermediate data with the total amount of A; wherein K is less than A;

putting the extracted sample data from the 1 st to the Kth sample data into a sample array;

and sequentially traversing the K +1 th data in the intermediate data to enable the selected probability of the x-th element in the sample array to be K/x, and replacing the elements in the sample array with equal probability of 1/K.

8. The data tilt processing apparatus of claim 6, wherein the data allocation module is further configured to:

after identifying the tilt data using the data tilt detection model, assigning the tilt data to a map task;

splitting and generating intermediate output data through the map task process;

allocating the intermediate output data into at least one reduce task based on the dynamic allocation algorithm.

9. A terminal device comprising a processor, a memory, and a computer program stored in the memory and configured to be executed by the processor, the processor implementing the data tilt processing method according to any one of claims 1 to 5 when executing the computer program.

10. A computer-readable storage medium, comprising a stored computer program, wherein the computer program, when executed, controls an apparatus in which the computer-readable storage medium is located to perform the data tilt processing method according to any one of claims 1 to 5.

Images