CN104317738B - A Method of Incremental Computing Based on MapReduce - Google Patents

Abstract

The invention discloses a method for incremental calculation based on MapReduce. The method includes: creating an incremental processing model for caching different historical processing results, including: a model for caching combiner results, a model for caching intermediate results, and direct reuse of results model; when the input data is obtained, select the corresponding incremental processing model for data processing according to the data characteristics of the input data, and when the incremental data arrives, call the corresponding incremental processing model for data processing and cache Incremental data calculation is performed on historical processing results. The method disclosed by the invention can save a large amount of unnecessary repeated calculations by selecting a model suitable for data characteristics for calculation, thereby improving the efficiency of data processing.

Description

A Method of Incremental Computing Based on MapReduce

technical field

The invention relates to the field of computer technology, in particular to a MapReduce-based incremental calculation method.

Background technique

With the development of the information age, more and more data are generated, and the types and scale of data are growing at an unprecedented rate. How to better manage and utilize big data has become a topic of general concern. The increase in data scale has brought great challenges to data storage, management, and data analysis. Google proposed the MapReduce model to process big data, and Microsoft also proposed a similar model, Dryad. Hadoop big data processing platform was developed on the basis of Google's open distributed file system, MapReduce model and other technical central ideas, and then the academic and business circles proposed a series of improvements around these model framework systems or proposed some new model frameworks and system.

In big data processing, more and more applications are related to incremental data, that is, data increases rapidly or changes slightly over time. In order to deal with this type of problem, it is necessary to design a system that only handles increased data without requiring Recalculate all data. At present, for the MapReduce computing model, the system improved on it is relatively complex, and the efficiency improvement is limited. Most of them are designed for a specific type of problem and lack versatility.

Contents of the invention

The purpose of the present invention is to provide a MapReduce-based incremental calculation method, which can save a lot of unnecessary repeated calculations by selecting a model suitable for data characteristics for calculation, thereby improving the efficiency of data processing.

The purpose of the present invention is achieved through the following technical solutions:

A method for incremental computing based on MapReduce, the method comprising:

Create an incremental processing model for caching different historical processing results, including: a model for caching combiner results, a model for caching intermediate results, and a model for direct reuse of results;

When the input data is obtained, the corresponding incremental processing model is selected for data processing according to the data characteristics of the input data, and when the incremental data arrives, the corresponding incremental processing model is called for historical processing cached during data processing The results are computed on incremental data.

Further, the selecting the corresponding incremental processing model according to the data characteristics of the input data includes:

When the input data is obtained, determine the data characteristics of the input data;

If it is statistical data, the selection result can be directly reused for model processing;

If it is time series data, choose to cache the model processing of intermediate results;

If it is not the above two types of data, use the model that caches the combiner result to process the data.

Further, when the input data is obtained, the corresponding incremental processing model is selected for data processing according to the data characteristics of the input data, and when the incremental data arrives, the corresponding incremental processing model is called for data processing Incremental data calculations for historical processing results cached in real time include:

If the model that caches the combiner result is selected for processing when the input data is obtained, then map operation, combiner operation, and reduce operation are performed on the input data in sequence, and the combiner operation result C1 is cached; where the map operation result is used as the result of the combiner operation Input data, the combiner operation result C1 is used as the input data of the reduce operation;

When the incremental data arrives, the map operation and the combiner operation are performed sequentially, and the combiner operation result C2 is cached; then the previously cached combiner operation result C1 and the current combiner operation result C2 are called as the input data of the reduce operation, and the reduce operation is performed .

Further, when the input data is obtained, the corresponding incremental processing model is selected for data processing according to the data characteristics of the input data, and when the incremental data arrives, the corresponding incremental processing model is called for data processing Incremental data calculations for historical processing results cached in real time include:

If the model that caches the intermediate results is selected for processing when the input data is obtained, the input data is divided according to a predetermined method and then two stages of MapReduce operations are performed; wherein, the divided data are respectively subjected to map operations and reduce operations in sequence Complete the first stage MapReduce operation, obtain the intermediate result divided according to the predetermined method; use the intermediate result divided according to the predetermined method as the input data of the map operation, perform the map operation respectively, and cache the map operation result M1, and then use the The map operation result M1 is used as the input data of the reduce operation to complete the second stage MapReduce operation;

When the incremental data arrives, divide the incremental data according to a predetermined method, and perform two-stage MapReduce operations on the divided data blocks separately; wherein, for the first processed data block, perform the second During the second-stage MapReduce operation, the map operation result M2 is cached, and the previously cached map operation result M1 and the current map operation result M2 are used as the input data of the reduce operation to perform the reduce operation; for subsequent data blocks, the second During the stage MapReduce operation, the map operation result is cached, and the previously cached map operation result M1, the second-stage map operation result of all data blocks before the data block, and the second-stage map operation result of the data block are used as the input of the reduce operation Data, perform reduce operation.

Further, when the input data is obtained, the corresponding incremental processing model is selected for data processing according to the data characteristics of the input data, and when the incremental data arrives, the corresponding incremental processing model is called for data processing Incremental data calculations for historical processing results cached in real time include:

If when obtaining the input data, select a model for direct reuse of the result, then perform a MapReduce operation, obtain the calculation result R1 and cache it; the calculation result R1 includes the operation result of the data and information that can be used for subsequent operations and can be directly called;

When the incremental data arrives, perform MapReduce operations on the incremental data to obtain the calculation result R2 and cache it; use the previously cached calculation result R1 and the current settlement result R2 as inputs for the merge operation, and perform integration processing to obtain the final result .

It can be seen from the technical solution provided by the present invention above that, according to different data characteristics, different models are selected, and different historical data are cached. When incremental calculation is started, incremental data is directly processed according to the obtained historical calculation results. The calculation avoids unnecessary repeated calculation, thereby improving the efficiency of data processing.

Description of drawings

In order to more clearly illustrate the technical solutions of the embodiments of the present invention, the following will briefly introduce the accompanying drawings that need to be used in the description of the embodiments. Obviously, the accompanying drawings in the following description are only some embodiments of the present invention. For Those of ordinary skill in the art can also obtain other drawings based on these drawings on the premise of not paying creative work.

Fig. 1 is a flow chart of a method for incremental calculation based on MapReduce provided by an embodiment of the present invention;

Fig. 2 is a schematic diagram of a processing flow of a MapReduce-based incremental calculation method provided by an embodiment of the present invention;

FIG. 3 is a schematic diagram of model data processing of cache combiner results provided by an embodiment of the present invention;

FIG. 4 is a schematic diagram of model data processing for caching intermediate results provided by an embodiment of the present invention;

FIG. 5 is a schematic diagram of model data processing for direct result reuse provided by an embodiment of the present invention.

detailed description

The technical solutions in the embodiments of the present invention will be clearly and completely described below in conjunction with the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some of the embodiments of the present invention, not all of them. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

Example

Fig. 1 is the flow chart of a kind of incremental calculation method based on MapReduce that the embodiment of the present invention provides; As shown in Fig. 1, this method mainly comprises the following steps:

Step 11. Create an incremental processing model for caching different historical processing results, including: a model for caching combiner results, a model for caching intermediate results, and a model for direct reuse of results;

Step 12. When the input data is obtained, select the corresponding incremental processing model for data processing according to the data characteristics of the input data, and when the incremental data arrives, call the corresponding incremental processing model for data processing cache Incremental data calculation is performed on historical processing results.

Wherein, the selection of the corresponding incremental processing model according to the data characteristics of the input data for data processing may refer to the following rules: when the input data is obtained, judge the data characteristics of the input data; if it is statistical data, select the result Directly reuse model processing; if it is time series data (that is, the data can be divided according to certain standards and does not affect each other), then choose the model processing of caching intermediate results; if it is not the above two types of data, use the model processing of caching combiner results data. In addition, since the model for caching combiner results is a general model, the model for caching combiner results can also be used to process statistical data and time series data according to actual conditions or needs.

According to the selected incremental processing model, this step can have the following three processing methods:

1) If the model that caches the combiner result is selected for processing when the input data is obtained, then the input data is sequentially performed with map (mapping) operation, combine (local merge) operation and reduce (reduce) operation, and caches the combiner The operation result C1; where, the map operation result is used as the input data of the combiner operation, and the combiner operation result C1 is used as the input data of the reduce operation;

When the incremental data arrives, the map operation and the combiner operation are performed sequentially, and the combiner operation result C2 is cached; then the previously cached combiner operation result C1 and the current combiner operation result C2 are called as the input data of the reduce operation, and the reduce operation is performed .

2) If the model of caching intermediate results is selected for processing when the input data is obtained, the input data is divided according to a predetermined method and then two stages of MapReduce operations are performed; wherein, the divided data are respectively subjected to map operations and The reduce operation completes the first stage of the MapReduce operation, and obtains the intermediate result divided according to the predetermined method; uses the intermediate result divided according to the predetermined method as the input data of the map operation, respectively performs the map operation, and caches the map operation result M1, and then Using the map operation result M1 as the input data of the reduce operation to complete the second stage MapReduce operation;

When the incremental data arrives, divide the incremental data according to a predetermined method, and perform two-stage MapReduce operations on the divided data blocks separately; wherein, for the first processed data block, perform the second During the second-stage MapReduce operation, the map operation result M2 is cached, and the previously cached map operation result M1 and the current map operation result M2 are used as the input data of the reduce operation to perform the reduce operation; for subsequent data blocks, the second During the stage MapReduce operation, the map operation result is cached, and the previously cached map operation result M1, the second-stage map operation result of all data blocks before the data block, and the second-stage map operation result of the data block are used as the input of the reduce operation Data, perform reduce operation.

3) If the model that directly reuses the result is selected when the input data is obtained, the MapReduce operation is performed, and the calculation result R1 is obtained and cached; the calculation result R1 includes the calculation result of the data and the data used for subsequent calculations that can be directly called information;

When the incremental data arrives, perform MapReduce operations on the incremental data to obtain the calculation result R2 and cache it; use the previously cached calculation result R1 and the current settlement result R2 as inputs for the merge operation, and perform integration processing to obtain the final result .

In addition, the overall processing flow of the above solution can also refer to FIG. 2 .

Compared with the prior art, the technical solutions provided by the embodiments of the present invention have the following beneficial effects:

1) Based on the MapReduce data processing model, the incremental processing function is expanded to improve the efficiency of incremental data processing;

2) Sufficiently reduce unnecessary calculations in the process of incremental data processing, saving storage space and computing time;

3) Integrate three incremental calculation models for users to choose, so as to improve calculation efficiency as much as possible according to the data situation.

In order to facilitate the understanding of the present invention, the data processing process of the cache combiner result model, the cache intermediate result model and the result direct reuse model will be described in detail below with reference to the accompanying drawings 3-5.

1. A model that caches combiner results.

FIG. 3 is a schematic diagram of data processing when selecting a model for caching combiner results provided by an embodiment of the present invention. The letter M represents the map operation stage, C represents the combiner operation stage, and R represents the reduce operation stage. As shown in Figure 3, the method mainly includes the following steps:

Step 1. When the incremental data calculation task is started, the model performs a map operation on the initial data to obtain a result in the form of <key-value>, and uses the result as the input of the combiner operation stage, and the combiner operation stage performs the <key-value> output from the map stage. The value> data is simply merged on each machine and the result is cached, and then sent to the reduce operation stage for operation to obtain the operation result of the initial data.

Among them, map, combiner, and reduce are the operation process of the model MapReduce. The new incremental processing model caches the results of the combiner operation stage in MapReduce for subsequent incremental calculations. Compared with the original data, the results of the combiner operation stage are greatly reduced. Delete raw data to save storage space.

Step 2: Use the combined result cached in step 1 to calculate the incremental data.

Among them, the map and combiner stages are normal MapReduce model operations, but when the reduce stage is reached, the combiner operation results of the cached historical data and the combiner operation results of the newly added data need to be used as the input of the reduce stage, and the reduce stage is calculated After that, the final result of historical data and new data can be obtained.

Further, explain the principle of the model:

The map stage of the MapReduce model in Hadoop (a distributed system infrastructure) generates intermediate results in the form of <key, value> and inputs them into the combiner function to preprocess the data. What needs to be explained here is that the combiner function of each node is only for The map result of this node is processed, and each node is not related. The data processed by the combiner can be compressed and output to the Reduce stage in the form of <key, value> for integration and calculation to obtain the final result. Generally, the map stage divides the data in units of behaviors to obtain <key, value>. The combiner stage preprocesses and compresses the results of the map stage. The combiner function only processes the map results of this node, so the combiner stage operation and new addition of historical input data The data combiner operation process and results are irrelevant and the results are deterministic. All the results generated in the combiner stage of historical data and new data are input into the reduce stage, which is equivalent to performing map and combiner operations on all data and then performing reduce operations to obtain the final result. The results are consistent with recalculations for all data.

2. A model that caches intermediate results.

FIG. 4 is a schematic diagram of data processing when selecting a cached intermediate result model according to an embodiment of the present invention. The letter M represents the map operation stage, and R represents the reduce operation stage.

This model extends MapReduce to two consecutive MapReduce operations. It should be noted that this model can usually only be used for a specific class of problems, which can divide data according to content and calculate the results of each division block separately, and the results of each division block can be integrated as the final result. For example, to calculate the last login time of a user, you can use days as the data division unit, and the intermediate result is the last login time of the user every day. After the second stage of mapreduce calculation, the last login time of the end user can be obtained. As shown in Figure 4, the method mainly includes the following steps:

Step 1. When the data calculation task is started, in the first stage, the original input data (time series data) is divided according to the preset method, for example, divided into different data blocks according to the time period, and the data is obtained after MapReduce operation. For the intermediate results of time segment division, it is necessary to change the output of the reduce phase of this stage so that the intermediate results are in the form of <key, value>. In the second stage, the map operation is performed on the intermediate results, the result obtained by the map operation is cached, and the reduce operation is continued to obtain the final result.

Among them, the map operation and the reduce in the second stage are the operation process of the model MapReduce. The reduce in the first stage needs to change the output data format. In addition, in order to process the incremental data, the map operation results in the second stage need to be cached for later use. For incremental calculations, the results of the map process in the second stage are greatly reduced compared to the original data, and the original data can be deleted to save storage space.

Step 2: Use the second-stage map operation results cached in step 1 to calculate incremental data.

When the new data arrives, divide the data according to the preset method in step 1 (for example, in step 1, it is divided according to the time period, and at this time it is also divided according to the time period). Segment data are added individually as new inputs to the incremental model. For incremental data, it is processed according to the method of step 1. When performing the reduce process of the second stage, the result of the map operation of the second stage cached after the operation of step 1 and the result of the map operation of the second stage of step 2 are used together as The input of the reduce stage, and the latest result is obtained after the reduce operation. The cache content used here is all the cache content in all operations, that is, the intermediate result of each operation cached with the increase of data. In addition, the map operation result of the intermediate result in step 2 is also cached for future calculation of incremental data.

Further, explain the principle of the model:

The model calculates after dividing the data, and the parameters correspond to the intermediate results of each division block, and then performs map operation on the intermediate results, and caches the operation results of the map. When new data comes, the new data can be gradually added to the system by division for calculation. The operation result generated by the map of the intermediate result generated by the new data is irrelevant to the map result of the intermediate result of the historical data. The two operations do not affect each other and have no effect on the operation of the reduce stage. The reduce phase integrates the results of all the map phases to obtain the latest calculation results, which are consistent with the calculation results after Mapreduce processing of all intermediate results.

3. Models that result in direct reuse.

FIG. 5 is a schematic diagram of data processing when selecting a model for direct reuse of results provided by an embodiment of the present invention. The letter M represents the map phase operation, and R represents the reduce phase operation. It should be noted that this model is usually applied to statistical data, that is, when the data operation results can be easily integrated with the historical operation results. For example, the average value on the statistical time series, the average value of the newly added data obtained by calculation can be easily combined with the historical operation results to calculate the latest average of all data when the number of new data and the number of historical data are known value. As shown in Figure 5, the method mainly includes the following steps:

Step 1. When the data calculation task is started, the model performs normal MapReduce calculations on the initial data to obtain the calculation results of the initial data and cache them. The cache content includes the calculation results of the data and information that can be directly called for subsequent calculations, such as data Number, data maximum and minimum values, etc.

Step 2: Use the cached data in Step 1 to calculate incremental data. When the new incremental data needs to be calculated, the calculation is performed according to the normal MapReduce model to obtain the result of the new data, and then the new calculation result and the cached result of step 1 are integrated through the user-controlled merge operation to obtain the overall The end result of the data.

Some examples can illustrate the feasibility of the model, such as statistical maximum, average, minimum, etc., only need to know the calculation results and historical results of the latest data plus some other data-related information (such as the number of data, etc.) to get all The end result of the data.

According to the above scheme of the embodiment of the present invention, different models are selected according to different data characteristics, and different historical data are cached. When the incremental calculation is started, the calculation of the incremental data is directly performed according to the obtained historical calculation results, avoiding the Unnecessary repeated calculations, thereby improving the efficiency of data processing.

The above is only a preferred embodiment of the present invention, but the scope of protection of the present invention is not limited thereto. Any person familiar with the technical field can easily conceive of changes or changes within the technical scope disclosed in the present invention. Replacement should be covered within the protection scope of the present invention. Therefore, the protection scope of the present invention should be determined by the protection scope of the claims.

Claims (4)

1. A method for incremental calculation based on MapReduce, characterized in that the method comprises: Create an incremental processing model for caching different historical processing results, including: a model for caching combiner results, a model for caching intermediate results, and a model for direct reuse of results; When the input data is obtained, the corresponding incremental processing model is selected for data processing according to the data characteristics of the input data, and when the incremental data arrives, the corresponding incremental processing model is called for historical processing cached during data processing The results are calculated for incremental data; Wherein, the selection of the corresponding incremental processing model according to the data characteristics of the input data includes: When the input data is obtained, determine the data characteristics of the input data; If it is statistical data, the selection result can be directly reused for model processing; If it is time series data, choose to cache the model processing of intermediate results; If it is not the above two types of data, use the model that caches the combiner result to process the data. 2. The method according to claim 1, wherein when the input data is obtained, the corresponding incremental processing model is selected according to the data characteristics of the input data for data processing, and when the incremental data arrives, Invoking the corresponding incremental processing model for data processing and performing incremental data calculation on cached historical processing results includes: If the model that caches the combiner result is selected for processing when the input data is obtained, then map operation, combiner operation, and reduce operation are performed on the input data in sequence, and the combiner operation result C1 is cached; where the map operation result is used as the result of the combiner operation Input data, the combiner operation result C1 is used as the input data of the reduce operation; When the incremental data arrives, the map operation and the combiner operation are performed sequentially, and the combiner operation result C2 is cached; then the previously cached combiner operation result C1 and the current combiner operation result C2 are called as the input data of the reduce operation, and the reduce operation is performed . 3. The method according to claim 1, wherein when the input data is obtained, a corresponding incremental processing model is selected for data processing according to the data characteristics of the input data, and when the incremental data arrives, Invoking the corresponding incremental processing model for data processing and performing incremental data calculation on cached historical processing results includes: If the model that caches the intermediate results is selected for processing when the input data is obtained, the input data is divided according to a predetermined method and then two stages of MapReduce operations are performed; wherein, the divided data are respectively subjected to map operations and reduce operations in sequence Complete the first stage MapReduce operation, obtain the intermediate result divided according to the predetermined method; use the intermediate result divided according to the predetermined method as the input data of the map operation, perform the map operation respectively, and cache the map operation result M1, and then use the The map operation result M1 is used as the input data of the reduce operation to complete the second stage MapReduce operation; When the incremental data arrives, divide the incremental data according to a predetermined method, and perform two-stage MapReduce operations on the divided data blocks separately; wherein, for the first processed data block, perform the second During the second-stage MapReduce operation, the map operation result M2 is cached, and the previously cached map operation result M1 and the current map operation result M2 are used as the input data of the reduce operation to perform the reduce operation; for subsequent data blocks, the second During the stage MapReduce operation, the map operation result is cached, and the previously cached map operation result M1, the second-stage map operation result of all data blocks before the data block, and the second-stage map operation result of the data block are used as the input of the reduce operation Data, perform reduce operation. 4. The method according to claim 1, wherein when the input data is obtained, a corresponding incremental processing model is selected for data processing according to the data characteristics of the input data, and when the incremental data arrives, Invoking the corresponding incremental processing model for data processing and performing incremental data calculation on cached historical processing results includes: If when obtaining the input data, select a model for direct reuse of the result, then perform a MapReduce operation, obtain the calculation result R1 and cache it; the calculation result R1 includes the operation result of the data and information that can be used for subsequent operations and can be directly called; When the incremental data arrives, the incremental data is processed by MapReduce to obtain the calculation result R2 and cached; the previously cached calculation result R1 and the current calculation result R2 are used as the input of the merge operation for integration processing to obtain the final result.