Realizing graph processing based on the mapreduce architecture

A device of realizing graph processing based on MapReduce architecture, comprising:

• one or more computer processors;
• a memory including a program which, when executed by the one or more computer processors is configured to execute:
• a receiving module that, in operation, receives an input file of a submitted graph processing job;
• a predicting module that is communicatively coupled to the receiving module and that, in operation, predicts a MapReduce task execution time distribution of the submitted graph processing job using an obtained MapReduce task degree-execution time relationship distribution and a degree distribution of the graph processing job, wherein the MapReduce task degree-execution time relationship distribution is a Reduce task degree-execution time relationship distribution and a Map task degree-execution time relationship distribution both of which may be obtained from historical records of MapReduce task processing;
• and
• a dividing module that is communicatively coupled to the predicting module and that, in operation, divides the input file of the submitted graph processing job into input data splits of MapReduce tasks according to the predicted MapReduce task execution time distribution of the submitted graph processing job, wherein dividing the input file of the graph processing job into input data splits of MapReduce tasks according to the predicted MapReduce task execution time distribution of the graph processing job includes:
• detecting whether key-value pairs of nodes in the input file of the graph processing job are constructed with degrees of the nodes;
• responsive to detecting that the key-value pairs of nodes in the input file are constructed with degrees of the nodes, sorting the key-value pairs of the nodes according to the degrees of the nodes;
• and
• dividing, by the processor, the sorted key-value pairs of the nodes into input data splits of MapReduce tasks according to the predicted MapReduce task execution time distribution of the graph processing job, wherein the processor is further configured to:
• divide equally the sorted key-value pairs of the nodes into input data splits of Reduce tasks according to the predicted Reduce task execution time distribution;
• divide equally the sorted key-value pairs of the nodes into input data splits of Map tasks according to the predicted Map task execution time distribution;
• input the input data splits of the Reduce tasks into a Reduce task partitioner;
• input the input data splits of the Map tasks into a Map task partitioner;
• assign, by a Job Tracker, the input data splits outputted from the Reduce task partitioner to Reduce Task Trackers to execute and input data splits outputted from the Map Task partitioner to Reduce Task Trackers to execute;
• execute, by the Map Task Trackers, the input data splits of the assigned Map tasks;
• and
• execute, by the Reduce Task Trackers, the input data splits of the assigned Reduce Tasks.