Differences between revisions 29 and 30
Revision 29 as of 2013-05-07 05:37:37
Size: 3576
Editor: edwardyoon
Revision 30 as of 2013-12-28 10:45:02
Size: 2154
Editor: edwardyoon
Deletions are marked like this. Additions are marked like this.
Line 14: Line 14:
 * ''Instead of running a separate job, we inject a partitioning superstep before the first superstep of the job. (This has a dependency on the Superstep API) For graph jobs, we can configure this partitioning superstep class specific to graph partitioning class that partitions and loads vertices. - Suraj Menon''
  * ''Since scaling the number of BSP tasks between supersteps in single job, is not possible, the key is "how to launch the number of tasks differently with the number of file blocks". and Even though graph use own graph partitioning class, the fact that parsing vertex structure should be done at loadVertices() method hasn't changed to avoid unnecessary IO overheads. So, advantage is that additional job can be removed, and disadvantage is: we have to manage two BSP and Graph partitioning classes. - Edward J. Yoon''
 * ''The partitions instead of being written to HDFS, which is creating a copy of input files in HDFS Cluster (too costly I believe), should be written to local files and read from. - Suraj Menon''
  * ''If we want to run multiple jobs on same input, for example, friendship graph is input and want to run PageRank job and SSSP job, ...., etc., reuse of partitions should be considered. If partitions are written on local fs, metadata should be managed to reuse them. - Edward J. Yoon''

In NoSQLs table input case (which supports range or random access by sorted key), partitions doesn't need to be rewritten. In addition, Scanner instead of basic 'region' or 'tablet' splits can be used for forcing the number of processors.
In NoSQLs table input case (which supports range or random access by sorted key), pre-processing step will be skipped because they supports range scan.

Partition Function

In Hama BSP computing framework, the Partition function is used for obtaining scalability of a Bulk Synchronous Parallel processing, and determining how to distribute the slices of input data among BSP processors. Unlike Map/Reduce data processing model, many scientific algorithms based on Message-Passing Bulk Synchronous Parallel model often requires that a processor obtain “nearby or related” data from other processors in order to complete the computation. In this case, you can create your own Partition function for determining processor inter-communication and how to distribute the data.


Internally, File format input data partitioning works as following sequence:

  • If user specified partition function, internally, "partitioning job" is ran as a pre-processing step.
    • Each task of "partitioning job" reads its assigned data block and rewrite them to particular partition files.
    • Job Scheduler assigns partitions to proper task based on partition ID.
  • After pre-partitioning done, launch the BSP job.

In NoSQLs table input case (which supports range or random access by sorted key), pre-processing step will be skipped because they supports range scan.

  • Job Scheduler assigns Scanner or tablet with its partition ID to proper task, launch the BSP job.

Partitioning internals in Graph module

The internals of the Graph module implemented on top of BSP framework, are pretty simple. Input data partitioning will be done at BSP framework level. Each GraphJobRunner processors just reads assigned splits, and loads parsed vertices into vertices storage at loadVertices() method. If you want to learn details and internals about Graph job, Please see also Design of Graph Module.

Create your own Partitioner



  BSPJob job = new BSPJob(conf);

Specify the partition files and directories

If the input is already partitioned, you can skip pre-partitioning step as following configuration:


Partitioning (last edited 2013-12-28 10:45:02 by edwardyoon)