Hadoop Processing Model

Note: These are preliminary results.

I've begun work on a application to perform various automatic statistical analyses of a large dataset (millions of records or more). It is implemented as a group of one-pass (or online) algorithms operating in a map-reduce topology. Technologically, the back-end uses Hadoop and the mrjob library. I haven't made technology choices for the front-end, but I'm leaning towards Django, Bootstrap, and D3.

One of the system engineering challenges for distributed processing is to scale the number of nodes to the workload. Eventually, I have to perform actual performance tests but for now I can approximate the resource requirements using an abstract model.

Abstract Model of Hadoop I/O Processing

The abstract model is a better approximation of a map-reduce conceptual model than Hadoop's actual architecture, but I hypothesize that it's sufficiently accurate for my purposes (and will later use test data to validate the model).

Input to the overall process is provided as a series of N records, with each record containing M columns or fields. (The M columns represent the number of columns processed/generated by the application; for simplicity we will assume the input's number of columns is one-to-one with the number of columns processed by the application.) Normally, N will be much greater than M. The input is divided between P map nodes and becomes the A datasets within each map node. The map process converts A into B. Likewise, the combine process converts B into C. At this point, the individual C records are merged, sorted by key, and transferred to Q reduce nodes where the records become D. The interim data is denoted as S. The D datasets are consumed by the reduce process and converted into E. Finally, E is merged into the final results of F.

Based on the algorithms, I can estimate the number of records in A through F and based on the current implementation estimate the size of records in each stage. Thus, I can calculate the total number of bytes that pass through the job from the origin to F. Setting M=10, I plotted the bytes (in terabytes) as a contour plot with N and P as the axes:



The plot is in Log2-Log2 form. The x-axis measures the number of records from a gigabyte (roughly a billion) to a terabyte (roughly a trillion). The y-axis varies from a single processor (2^0) to 128 processors (2^7). The ridges show that I/O is constant with doubling input and doubling the number of processors, so we are making effective use of the map-reduce framework. However, since the contour scale is measured in terabytes, the linear complexity has a large constant factor.

In the model, the I/O costs are concentrated in the B stage. Although the individual output of the Map process is small (when measured on a per-record level), the number of records in B is MN/P. The Combine process is necessary to immediately aggregate the results together and rid the N term from the later I/O steps. For comparison, F is proportional to M and, although each record will be in the 100s of kilobyte to megabyte range, the total size consumed can be a thousandth of B.

Confusion Matrix in Mathematica

A confusion matrix is an effective visualization technique to diagnose how a classification algorithm is behaving. You can create one easily in Mathematica given a list of 2-tuples, where the 2-tuple is of the form {ground truth category, predicted category}.

ConfusionMatrix[gndpre_List] :=
 With[
  {categories = Union[Flatten[gndpre]]},
  Partition[
   Flatten[
    Table[
     Count[gndpre, {row, col}],
     {row, categories},
     {col, categories}
     ]
    ],
   Length[categories]
   ]
  ]

Hide in Plain Sight add-on available

The Hide in Plain Sight add-on has passed preliminary review!

You can download it at: https://addons.mozilla.org/en-US/firefox/addon/hide-in-plain-sight/

Hide in Plain Sight add-on submitted for preliminary review

The add-on is now in the AMO's review queue, but is already available at: https://addons.mozilla.org/en-US/firefox/addon/hide-in-plain-sight/ !

Improving the performance of reversehuffman.encrypt, Part II

In the encrypt algorithm, one stage requires a scan of the frequency table to generate a list of potential next characters based off of the previous n-1 characters. In the previous versions of the algorithm, this was performed using a linear scan. Since the frequency table is sorted in string order, an obvious optimization is to use a binary search and terminate the linear scan early.

The results:

Implementation	User Time
(Baseline) String.indexOf(...) === 0	1m21.828s
String.beginsWith(...)	1m10.723s
beginsWith(str, prefix)	1m11.457s
Binary search	0m01.713s

Now, that's a nice result.

For completeness, my updated detailed profile results:

Statistical profiling result from /home/starr/svn/plainsight-addon/lib/v8.log, (1550 ticks, 0 unaccounted, 0 excluded).

 [Shared libraries]:
   ticks  total  nonlib   name
    433   27.9%    0.0%  /usr/lib/libv8.so.3.14.5
     16    1.0%    0.0%  /lib/x86_64-linux-gnu/libc-2.17.so
     13    0.8%    0.0%  7fff58bfe000-7fff58c00000
      1    0.1%    0.0%  /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.18
      1    0.1%    0.0%  /usr/bin/nodejs
      1    0.1%    0.0%  /lib/x86_64-linux-gnu/ld-2.17.so

 [JavaScript]:
   ticks  total  nonlib   name
    115    7.4%   10.6%  LazyCompile: Object.defineProperty.value /home/starr/svn/plainsight-addon/lib/reversehuffman.js:28
     83    5.4%    7.6%  LazyCompile: huffmantree /home/starr/svn/plainsight-addon/lib/textutils.js:220
     71    4.6%    6.5%  LazyCompile: *InsertionSort native array.js:764
     68    4.4%    6.3%  LazyCompile: *nextChars /home/starr/svn/plainsight-addon/lib/reversehuffman.js:170
     54    3.5%    5.0%  LazyCompile: *binaryInsertionPoint /home/starr/svn/plainsight-addon/lib/textutils.js:20
     53    3.4%    4.9%  Stub: CompareICStub
     47    3.0%    4.3%  Stub: FastNewClosureStub
     41    2.6%    3.8%  LazyCompile: *sort native array.js:741
     39    2.5%    3.6%  LazyCompile: *reduce native array.js:1381
     37    2.4%    3.4%  Stub: CompareICStub {2}
     35    2.3%    3.2%  LazyCompile: *self.push /home/starr/svn/plainsight-addon/lib/priority_queue.js:129
     35    2.3%    3.2%  LazyCompile: *QuickSort native array.js:793
     34    2.2%    3.1%  LazyCompile: *self.pop /home/starr/svn/plainsight-addon/lib/priority_queue.js:57
     31    2.0%    2.9%  Builtin: A builtin from the snapshot

The function nextChars is where I implemented the binary search.

Improving the performance of reversehuffman.encrypt, Part I

The Reverse Huffman encryption and decryption routines are the most expensive operations within the add-on. One of my beta testers reports that it took him 108 seconds to encrypt 116 words (of Lorem Ipsum) on his computer. Let's bring that down.

I created this script for profiling use:

 var fs = require("fs");  
 var rh = require("./reversehuffman");  
 var textutils = require("./textutils");  
 let source = fs.readFileSync("../doc/independence.txt", {encoding: "utf-8", flag: "r"});  
 let ft = textutils.frequencyTable(4, source);  
 for(let i = 0; i < 1000; i++) {  
      rh.encrypt("this is some plain text", ft);  
 }  

Running my initial implementation through the profiler, I get the following report (report cropped):

Statistical profiling result from /home/starr/svn/plainsight-addon/lib/v8.log, (77854 ticks, 0 unaccounted, 0 excluded).

 [Shared libraries]:
   ticks  total  nonlib   name
  31451   40.4%    0.0%  /usr/lib/libv8.so.3.14.5
     36    0.0%    0.0%  /lib/x86_64-linux-gnu/libc-2.17.so
     16    0.0%    0.0%  7fff2d9fe000-7fff2da00000
      3    0.0%    0.0%  /usr/bin/nodejs
      1    0.0%    0.0%  /lib/x86_64-linux-gnu/libpthread-2.17.so
      1    0.0%    0.0%  /lib/x86_64-linux-gnu/libm-2.17.so

 [JavaScript]:
   ticks  total  nonlib   name
  21179   27.2%   45.7%  LazyCompile: encrypt /home/starr/svn/plainsight-addon/lib/reversehuffman.js:60
   8920   11.5%   19.2%  LazyCompile: *indexOf native string.js:118
   5013    6.4%   10.8%  Stub: KeyedLoadElementStub
   3718    4.8%    8.0%  Stub: CEntryStub
    395    0.5%    0.9%  KeyedLoadIC: args_count: 0
    177    0.2%    0.4%  LazyCompile: huffmantree /home/starr/svn/plainsight-addon/lib/textutils.js:219
    128    0.2%    0.3%  Stub: FastNewClosureStub
     85    0.1%    0.2%  LazyCompile: *sort native array.js:741
     79    0.1%    0.2%  LazyCompile: *slice native string.js:510
     78    0.1%    0.2%  LazyCompile: *InsertionSort native array.js:764
     60    0.1%    0.1%  Builtin: A builtin from the snapshot
     58    0.1%    0.1%  Stub: FastCloneShallowObjectStub
     54    0.1%    0.1%  LazyCompile: *self.push /home/starr/svn/plainsight-addon/lib/priority_queue.js:129
     52    0.1%    0.1%  LazyCompile: *QuickSort native array.js:793
     51    0.1%    0.1%  LazyCompile: huffmanencodetoken /home/starr/svn/plainsight-addon/lib/textutils.js:179

Within the table, the 'ticks' represents the number of times the sampling profiler detected that the code was within that function. Overall, the baseline test takes 1 minute, 21.828 seconds of user time.

(By impact, I should focus on encrypt first,  but I'll go after indexOf first because the costs to improve are much smaller.)

A surprising amount of time is spent in indexOf, within the encryption algorithm, we are scanning the key value and extracting strings that start with a prefix. Mozilla provides a String.startsWith function, but it is implemented in terms of computing indexOf and comparing against zero.

As an alternative, I implement a beginsWith alternate function:

 if (!String.prototype.beginsWith) {  
   Object.defineProperty(String.prototype, 'beginsWith', {  
     enumerable: false,  
     configurable: false,  
     writable: false,  
     value: function (prefix) {  
       "use strict";  
       if(this.length < prefix.length) {  
         return false;  
       } else {  
         for(let i = 0; i < prefix.length; i++) {  
           if(this.charAt(i) != prefix.charAt(i)) {  
             return false;  
           }  
         }  
         return true;  
       }  
     }  
   });  
 }  

Re-running the tests, I get:

Implementation	User Time
(Baseline) String.indexOf(...) === 0	1m21.828s
String.beginsWith(...)	1m10.723s

That shows a nice gross improvement, but what do the more detailed results say?

Statistical profiling result from /home/starr/svn/plainsight-addon/lib/v8.log, (65316 ticks, 0 unaccounted, 0 excluded).

 [Shared libraries]:
   ticks  total  nonlib   name
   2253    3.4%    0.0%  /usr/lib/libv8.so.3.14.5
    524    0.8%    0.0%  /lib/x86_64-linux-gnu/libc-2.17.so
     57    0.1%    0.0%  7ffff93fe000-7ffff9400000
      2    0.0%    0.0%  /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.18
      1    0.0%    0.0%  /lib/x86_64-linux-gnu/libm-2.17.so

 [JavaScript]:
   ticks  total  nonlib   name
  28448   43.6%   45.5%  LazyCompile: Object.defineProperty.value /home/starr/svn/plainsight-addon/lib/reversehuffman.js:22
  18774   28.7%   30.0%  LazyCompile: encrypt /home/starr/svn/plainsight-addon/lib/reversehuffman.js:81
   4278    6.5%    6.8%  Stub: KeyedLoadElementStub
   3993    6.1%    6.4%  Stub: FastNewBlockContextStub
   3549    5.4%    5.7%  Stub: CompareICStub {1}
    774    1.2%    1.2%  Stub: CompareICStub {2}
    398    0.6%    0.6%  Stub: ToBooleanStub_Bool
    390    0.6%    0.6%  KeyedLoadIC: args_count: 0
    142    0.2%    0.2%  LazyCompile: huffmantree /home/starr/svn/plainsight-addon/lib/textutils.js:219
    137    0.2%    0.2%  Stub: FastNewClosureStub
     93    0.1%    0.1%  LazyCompile: *InsertionSort native array.js:764
     90    0.1%    0.1%  LazyCompile: *sort native array.js:741
     82    0.1%    0.1%  LazyCompile: *slice native string.js:510

The Object.defineProperty.value refers to the new beginsWith code. Why is that so expensive? To see if it is a one-time expense versus a high overhead, I incremented the iterations from 1000 to 10000 in my profiling script and re-ran. That run took 11m43.463s of user time (703.463 seconds), which is almost exactly ten times the previous amount of time. The detailed profiler results showed the same -- the number of ticks is scaling with the number of iterations, so it is not a setup expense.

Furthermore, making the function stand-alone is not helpful (although it does make the detailed results easier to understand since the actual function being executed isn't hiding behind Object.defineProperty.value):

Implementation	User Time
(Baseline) String.indexOf(...) === 0	1m21.828s
String.beginsWith(...)	1m10.723s
beginsWith(str, prefix)	1m11.457s

So, at this point, we've made a slight improvement in performance but we need to now work on the main algorithm rather than improving a subsidiary function.

Profiling Mozilla Add-ons (Stopgap)

There is currently no good way to profile Firefox JavaScript add-on code. For code that runs within the context of a web page, there are a number of options available (e.g. Firebug), but those solutions do not work for code that runs within the browser itself. For many add-ons, this is acceptable since they do not include any complex computations, but my add-on, Hide in Plain Sight, includes some expensive operations so I needed a profiler in order to perform evidence-based optimization.

My stopgap measure is to use the V8 JavaScript engine profiler. This is the JavaScript engine used in Chrome. Profiling code that will run in FireFox with the Chrome engine is not ideal, but I hypothesize that the two engines have similar gross performance characteristics.

Installation

In Ubuntu 13.10, using apt-get, I installed nodejs. (The version of nodejs installed with 12.04 many versions behind.)

Getting tools/linux-tick-processor (and the other functions necessary to parse the profiling output) was more involved.

Based on my history (i.e. I haven't double-checked these steps), this is what I did:

 $ apt-get source libv8  
 $ cd libv8-3.8.9.20  
 $ make dependencies  
 $ make native werror=no  

Running the Profiler
First, you need some code to profile. Not ideally, I wrote a driving script for frequencyTable, one of the functions I wanted to profile:

 var fs = require("fs");  
 var textutils = require("./textutils");  
   
 let source = fs.readFileSync("../doc/independence.txt", {encoding: "utf-8", flag: "r"});  
 
 for(let i = 0; i < 10000; i++) {  
      textutils.frequencyTable(4, source);  
 }

The "fs" library is provided by node.js.

Inside my add-ons lib/ directory, I ran the command:

 $ nodejs --harmony --use_strict --prof prof_frequencyTable.js  

The '--harmony' and '--use_strict' arguments are necessary to force node.js to allow "let" and other modern JavaScript features.

This command will run your script and create a "v8.log" file in your current directory.

To extract some useful data from v8.log, change directory to your libv8 directory and run:

 $ tools/linux-tick-processor path/to/your/v8.log  

This will write to stdout a profiling report.