KR101772955B1 - Record processing method using index data structure in distributed processing system based on mapreduce - Google Patents

Abstract

A method of processing a record using an index in a distributed processing system based on MapReduce includes the steps of classifying records to be analyzed in an input file by a distributed node of the distributed processing system, Generating a data structure having a plurality of indexes indicating a plurality of indexes in the data structure, accessing the plurality of indexes in the order of the keys in the data structure, Generating a new index data structure having a new index indicating an identifier of the new data structure, storing the new data structure in the new data structure, To a stored record based on the identifier of And a step.

Description

TECHNICAL FIELD [0001] The present invention relates to a method of processing records using indexes in a distributed processing system based on MapReduce,

The techniques described below relate to techniques for processing records in the MapReduce framework.

At the OSDI conference in 2004, Google will publish a paper called "MapReduce: Simplified Data Processing on Large Clusters." Various systems based on MapReduce have been developed since then. The Apache Foundation's Apache Hadoop (Hadoop) is getting attention as a distributed processing platform for big data processing.

However, the conventional MapReduce framework uses merge sorting in Map functions and Reduce functions. As is known, merge sorting is a technique utilizing physical storage devices, which inevitably requires access to the storage device several times.

The technique described below is intended to provide a MapReduce framework using an index-based data structure.

A method of processing a record using an index in a distributed processing system based on MapReduce includes the steps of classifying records to be analyzed in an input file by a distributed node of the distributed processing system, The distributed node accessing the index in the order of the keys in the data structure and transmitting the records stored in the storage location indicated by the accessed index, And the node performing a reduce operation on the transmitted records.

The techniques described below use index based data structures to reduce the number of accesses to storage devices. Therefore, the technique described below can shorten the execution time of the big data application using the MapReduce framework.

1 shows an example of a configuration of a Hadoop framework.
2 shows an example of a record processing process in a distributed processing system based on map reduction.
3 is an example of a process of processing a record using an index in a distributed processing system based on map reduction.
4 is another example of a process of processing a record using an index in a distributed processing system based on map reduction.

The following description is intended to illustrate and describe specific embodiments in the drawings, since various changes may be made and the embodiments may have various embodiments. However, it should be understood that the following description does not limit the specific embodiments, but includes all changes, equivalents, and alternatives falling within the spirit and scope of the following description.

The terms first, second, A, B, etc., may be used to describe various components, but the components are not limited by the terms, but may be used to distinguish one component from another . For example, without departing from the scope of the following description, the first component may be referred to as a second component, and similarly, the second component may also be referred to as a first component. And / or < / RTI > includes any combination of a plurality of related listed items or any of a plurality of related listed items.

As used herein, the singular " include "should be understood to include a plurality of representations unless the context clearly dictates otherwise, and the terms" comprises & , Parts or combinations thereof, and does not preclude the presence or addition of one or more other features, integers, steps, components, components, or combinations thereof.

Before describing the drawings in detail, it is to be clarified that the division of constituent parts in this specification is merely a division by main functions of each constituent part. That is, two or more constituent parts to be described below may be combined into one constituent part, or one constituent part may be divided into two or more functions according to functions that are more subdivided. In addition, each of the constituent units described below may additionally perform some or all of the functions of other constituent units in addition to the main functions of the constituent units themselves, and that some of the main functions, And may be carried out in a dedicated manner.

Also, in performing a method or an operation method, each of the processes constituting the above method may occur in a different order than that described in the context without explicitly specifying a specific order in the context. That is, each process may occur in the same order as described, may be performed substantially concurrently, or may be performed in the opposite order.

The technique described below relates to a method for processing records (data) input in a distributed processing system using the MapReduce framework. A typical distributed processing system based on MapReduce is Hadoop. Hadoop provides a very efficient system architecture for big data processing. Although the technique described below is not applied only to Hadoop, it will be described on the basis of Hadoop for convenience of explanation.

1 shows an example of a configuration of a Hadoop framework. The Hadoop framework comprises a Hadoop Distributed File System (HDFS) 101, which is a distributed file system for storing data, and a MapReduce framework 102, which performs data analysis.

The HDSF 101 is composed of a master node 110 and a slave node 120 like a general distributed file system.

The master node 110 is called a name node and manages the operation state of the slave node 120 called a data node in real time and stores the meta data Manage data.

The data is divided into a plurality of blocks, and a plurality of slave nodes 120 are distributedly stored in such a manner that one block is duplicated and stored. The master node 110 can know whether a specific block is stored in which slave node 120 using the metadata.

The HDFS 101 is designed to process large volumes of data, ranging from tens of PBs, to thousands of servers. Compared to other distributed file systems, HDFS (101) is designed to speed up the throughput of data read operations at a time, instead of sacrificing latency in accessing or changing metadata . For example, the size of one block in the HDFS 101 is basically set to 64 MB. This is significantly different from the typical block size of a file system, which is several tens of KB. Hadoop is a platform optimized for batch processing of collected data. The HDFS (101) is designed so that once written data can not be modified and only write-once is possible. The simplicity of data storage simplifies the management of the entire system, enabling clusters of thousands of servers to run smoothly. The implementation of the MapReduce described below is also simplified.

MapReduce 102 is a data analysis framework that operates on the HDFS 101. MapReduce provides a data-driven programming model that differs from traditional programming methods. Programming in a typical distributed environment requires many considerations, such as scheduling of distributed work, breakdown of some servers, and network configuration between servers, unlike programming on a single server, which most programmers are familiar with. In MapReduce, these complex problems are simplified at the platform level, so programmers are only required to write mapper and reducer functions for batch processing of data. The MapReduce framework processes data through the Map step using the map sum and the Reduce step using the Reduce function.

In the master node 110, a job tracker performs scheduling of a task to be performed by a task tracker of the slave node 120. The task tracker of the slave node 120 performs a certain task and reports the progress to the job tracker. The tasks performed by the task tracker correspond to the map step and the reduce step.

The MapReduce framework uses a record consisting of a key and a value to represent data. A map step is a process of sorting data that is related to data in the form of records having keys and values. The Reduce step applies the Reduce function to a record with the same key to generate a key and value with the final result. The Reduce step generally removes redundant data and extracts the desired data or information.

The map function processes the data loaded from the HDFS 101 and outputs a new set of < key, value >. In the MapReduce system, we create a set of new <key, value> pairs of <key, (value 1, value 2, ...)> expressions by grouping values with the same key. The Reduce function performs an aggregation operation on it to create another set of <key, value> pairs and stores them in HDFS.

Hadoop basically operates in fully distributed mode, which consists of several servers. Furthermore, Hadoop can operate in pseudo-distributed mode, where all processes run on a single server. In the latter case, the entire process is performed physically on one server.

FIG. 2 shows an example of a record processing process in a distributed processing system based on MapReduce. 2 is a flowchart illustrating a process of performing a map step and a re-de-step step in a conventional maple deuce framework. 2 shows an example of the Hadoop framework. In Hadoop framework, a device that performs map de-miss corresponds to each slave node 120. The slave node 120 refers to a computer device (server or the like) that processes certain data and can transmit and receive data through a communication network. Hereinafter, it will be explained that the computer apparatus performs MapReduce. In the following description, parts denoted by (a) to (e) are denoted by the same reference numerals in the drawings.

First, the computer device receives input data from the Hadoop file system (HDFS). The computer device applies the map function to the input data and stores it in a buffer. If there are multiple redo operations, the partition is saved. Fig. 2 assumes that there are two reduction tasks. When the size of the buffer exceeds a predetermined size, the computer device arranges the buffer using a quick sort, stores the buffer in a local storage device, and empties the buffer (step a). The files that the computer device stores on the local storage device are called spill files. The computer device stores the spill file on the local storage device until it has processed all of the input data assigned to the map job.

If multiple spill files are created, they are merged into a single file (step b). The merged and sorted file corresponds to the map output of the map process. The generated files are partitioned by the number of redo operations.

The computer device generates shuffle files to pass the map's output file (merge-aligned records) to the redess task (step c). This process is called shuffling. If there are multiple redo operations, the data is sent to the corresponding redo operations for each partition. Shuffling collects the result of the map sum and transfers it to the reduction function.

The computer device receives data from multiple map operations and performs merge sorting again (step d). Files created by merge sorting (denoted by Reduce input) are used for redescing operations.

The computer device applies the Reduce function to the file generated in step d, creates the final result, and stores the result in the HDFS (step e).

Outer merge sorting is performed in the process of generating the map output data and generating the reduce input for the reduction. In this process, several READ / WRITE occur. When creating a spill file, a WRITE occurs. In the process of generating a map output, a READ for the spill file occurs to perform the merge sort, and a WRITE for storing the map output occurs.

In the shuffle file creation process, READ and WRITE occur to read map output, send it to the redo job, and save it. In addition, during the process of generating the reduce input for the redo operation, a READ accessing the shuffle file occurs again for merge sorting. Generally, READ 3 times, WRITE 3 times. In addition, in the process of generating map output and generating reduce input for redundancy, if there are many files that need to be merged, they are merged several times, so READ / WRITE And more.

In particular, since the merge sorting is used in the mapping process, the number of accesses to the storage device increases, resulting in a delay in data processing. The technique described below tries to use an index data structure instead of merge sorting in the conventional maple deuce process. Thereby reducing the number of times a computer device accesses a local storage device.

If the size of the key is much smaller than the record size, indexed sorting can significantly reduce disk access times compared to external merge sorting. Records to be sorted are stored in the disk as input data, and only the storage location and key value are managed in an index structure. Then, when the sort result is needed, the records are accessed in key order through the index structure to obtain the sort result. Various data structures are available at this time. For example, using an index data structure such as a B-tree or a B + -type tree, results naturally sorted in key order can be obtained.

FIG. 3 shows an example of a process of processing a record using an index in a distributed processing system based on MapReduce. FIG. 3 shows an example using an index data structure in the process of generating map output data.

A computer device receives input data from a file system (HDFS). The computer device applies the map function to the input data and stores it in a buffer. If there are multiple redo operations, the partition is saved. FIG. 3 assumes that there are two redundancy operations. When the size of the buffer exceeds a certain size, the computer device sorts the buffer, stores it in the local storage device, and empties the buffer (step a). The files that the computer device stores on the local storage device are called spill files. The computer device stores the spill file on the local storage device until it has processed all of the input data assigned to the map job. The spill file is currently unsorted. Alternatively, you can use the quick sort to perform the sort when you save each spill file. In this case, however, it is necessary to combine several spill files.

At this time, the computer device manages the index value of the key value and the disk storage location for each record (step b). For example, an index data structure can use a B + tree that is easy to process sequential keys. The computer device manages the index data structure in memory.

When the computer device sends the result of the map operation as a redisplay operation, it sequentially accesses the indexes in the order of the keys to find the disk storage location for each record. Then, the computer device sends the record stored in the corresponding position to the reuse process (step c). This process corresponds to the generation of the shuffle file in Fig.

The computer device receives data from multiple map operations and performs merge sorting again (step d). Files created by merge sorting (Reduce input) are used for resume operations.

The computer device applies the Reduce function to the file generated in step d, creates the final result, and stores the result in the HDFS (step e).

In FIG. 3, a WRITE occurs in a process of storing an initial spill file, a READ occurs in a process c for transferring a file to be input to a redess based on the index, and a WRITE occurs for processing in a redess operation. And a READ occurs for the merge alignment of the reduction step. Comprehensively, READ 2 and WRITE 2 occur less frequently than the method of FIG. 2.

4 is another example of a process of processing a record using an index in a distributed processing system based on MapReduce. FIG. 4 shows an example in which an index data structure is used in the process of generating map output data and reduce input data.

A computer device receives input data from a file system (HDFS). The computer device applies the map function to the input data and stores it in a buffer. If there are multiple redo operations, the partition is saved. FIG. 3 assumes that there are two redundancy operations. When the size of the buffer exceeds a certain size, the computer device sorts the buffer, stores it in the local storage device, and empties the buffer (step a). The files that the computer device stores on the local storage device are called spill files. The computer device stores the spill file on the local storage device until it has processed all of the input data assigned to the map job. The spill file is currently unsorted. Alternatively, you can use the quick sort to perform the sort when you save each spill file. In this case, however, it is necessary to combine several spill files.

At this time, the computer device manages the index value of the key value and the disk storage location for each record (step b). For example, an index data structure can use a B + tree that is easy to process sequential keys. The computer device manages the index data structure in memory. Index data structures can be created in the spill file, one by one. In FIG. 4, two index data structures (I ₁ , I ₂ , I ₃ , I ₄ ) are generated in one partition.

When a computer device performs a redox operation, it receives the results of several map operations and combines them to produce a Reduce input. To do this, we take an index created from several map operations and create a new large index (c). In this case, the shuffle file of Fig. 2 is not generated because only the index is transferred to the redo job node.

The process of creating a new index is performed in memory. The process of creating a large index is as follows. (1) The indexes of the map are sequentially accessed to find the key and disk storage location. (2) Manage the key, disk storage location, and map identifier in a new index. Generally, multiple map output data is used, so a new entry called map identifier is used. The new index indicates the key, the storage location, and the identifier of the map. The identifier of the map corresponds to the identifier of the index data structure for the map output data. For example, I ₁ , I ₂ , I ₃ , and I ₄ shown in FIG. ₄ may correspond to a map identifier (an identifier of an index data structure). (3) Repeat steps (1) and (2) for all records in all maps. FIG. 4 shows an example in which two new indexes I ₅ and I ₆ are generated through this process.

The computer device sequentially accesses the newly created large indexes and fetches the records having the same key value. In this case, since the actual data is stored in the node performing the map operation, the record having the same key value is accessed using the map identifier and the disk storage location (step d).

The computer device applies the reduction function to the records having the same key value, creates the final result, and stores it in the HDFS (e process).

In FIG. 4, a WRITE occurs in a process of storing an initial spill file, and a READ is generated in a process of transferring a file to be input to a redisplay based on an index. Comprehensively, it is possible to perform the map and the reduction step by accessing only the READ 1 and WRITE 1 discs.

In FIG. 3 or 4, the computer device sequentially accesses the index based on the key value to fetch the record. It is therefore desirable that the computer device store the spill file in a storage device such as an SSD that can handle random access. In addition, indexes can be used to determine disk access locations ahead of time, so asynchronous methods such as libAIO can be used to fetch data faster.

In the foregoing description, it has been explained that B-tree or B + -tree is used as the index data structure. However, index data structures do not necessarily have to use a B-tree. Basically, you can use a variety of data structures that can be sequentially accessed based on keys in memory.

In Figures 3 and 4, the computer device has been described as generating a spill file. However, if the input data for the map operation exists in the HDFS of the same node and is accessible by record, there is no need to perform a WRITE operation for data storage. The computer device reads the input data, finds the key value and storage location, and manages this information as an index.

The computer device can apply statistical functions such as count, sum, min / max, etc. to a record in the process of creating an index data structure from a spill file. That is, when a computer device reads a record based on an index, it is possible to generate an index that further indicates the result of the operation when a particular operation is immediately possible. In this case, the index data structure includes the key, the storage location, and the operation result. If you use only these statistical functions in the Reduce function, you can get the result of the calculation from the index without having to read the actual data of the record.

The above-described map identifier is used for determining from which node data is to be read. When the computer device creates an index from the spill data, the map identifier may be managed by including it in the index.

The present embodiment and drawings attached hereto are only a part of the technical idea included in the above-described technology, and it is easy for a person skilled in the art to easily understand the technical idea included in the description of the above- It will be appreciated that variations that may be deduced and specific embodiments are included within the scope of the foregoing description.

101: HDSF
102: MapReduce Framework
110: master node
120: Slave node

Claims (10)

A distributed node of a distributed processing system based on MapReduce classifies input data into records to be analyzed using a map function and stores the classified data in a storage device of the distributed node; The records are each composed of a pair of a key and a value,
Generating an index structure in which the distributed node is configured with indices that together indicate the key and the storage location in which each record is stored in the storage device; The indices corresponding to the records, respectively,
The distributed node accesses the indices according to the order of the keys in the index structure to identify each storage location for the records, and stores the records stored in each identified storage location in a partition ; And
Wherein the distributed node performs the redesing operation on the records classified by the partition by using a reduce function, and in the distributed processing system based on MapReduce, How to process. The method according to claim 1,
Wherein the index structure is located in a memory of the distributed node and is sequentially accessible based on the key. delete The method according to claim 1,
The performing of the reduction operation may include performing a merge sort on the sorted records, and removing redundant data based on the merge sorted records. In the distributed processing system based on the MapReduce, How to process records using. delete The method according to claim 1,
In the step of creating the index structure
Wherein the distributed node generates the index structure further including a result of calculating a value of a record based on the key, in a distributed processing system based on MapReduce. The method according to claim 6,
Wherein the calculation is performed using at least one of a summation for a key having the same value, a number of keys having the same value, a minimum value among values for the keys having the same value, and a maximum value among the values for the key having the same value, A method for processing a record using an index in a distributed processing system based on XML. A distributed node in a distributed processing system based on MapReduce is provided with a first key for each first record and a first index indicating a first storage location of each first record in the storage device of the distributed node Generating a first index structure comprising a plurality of index structures;
A second index structure consisting of second indexes for indicating, for the second records, a key of each second record and a storage location in which each second record is stored in the storage device of the distributed node, &Lt; / RTI &gt;
Wherein the distributed node accesses the first indexes in the order of the keys in the first index structure and accesses the second indexes in the order of keys in the second index structure, Generating a third index structure including all of the indexes included in the second index structure, the third indexes indicating the keys of the respective records, the storage locations of the respective records, and third indexes indicating the identifiers of the index structures to which the respective records belong; ; And
The distributed node accesses the third indexes according to the order of the keys in the third index structure and accesses the storage nodes based on the storage location of the record indicated by the third index having the same key value and the identifier of the data structure A method for processing a record using an index in a distributed processing system based on a MapReduce, the method comprising: applying a reduction function to a record. delete delete

Images