The growth of web services and big data calls for a modification in how data is stored and processed. Traditional relational databases fall out of fashion in "big data" companies because of its complexity and rigid structure. Amazon noticed that when using SQL, 70% percent of their operations were using only <key,value> data, where a primary key is called to obtain a value in one row. In other words, most of their operations did not utilize the benefits of relational data, while updating such databases becomes more expensive as the amount of data scales.

With that context, in the first half of our independent project, we explored DynamoDB, Amazon's NoSQL database which stores data in <key,value> form. DynamoDB is built on a network structure to maintain data where many storage nodes communicate with each other, suitable for the data storage architecture of big data companies.

Working based upon this architecture, the MapReduce model is a simple and elegant solution to data processing that captures many applications in the real world.

Based on the assumption that if we have uneven input files, the performance would be suboptimal, we implemented a basic load balancer. The idea is that the load balancer splits input files into even sized chunks, so that each worker can take up similar amounts of work. In this way, the situation where a few workers are waiting for one should be less frequent.

Chunking implementation:

• scan the total input files, calculate the sum of the bytes of the input files.

• split the files into chunks with start offset and chunk size.

• pass that chunk info as part of a Task. When the worker receives the task, the worker only processes the chunk using the offset and chunksize.

When running MapReduce without a load balancer, runtime varies between different file size distributions. At the most evenly sized input (4), the program takes the least amount of time, while unevenness of 150,300,400 tend to be the local maxima in runtime. We hypothesize that this is due to when file sizes are unbalanced, workers assigned shorter files have to wait for workers assigned longer files. When file sizes are naturally balanced, no worker is idle for too long and each will end up finishing the task around the same time.

When we add load balancing, the runtime of the program decreases significantly. With each successive increase in chunk size, the runtime of MapReduce decreases until around 5.01 seconds at chunk size of 32000 byte, where no more improvement can be made. At the optimal chunk size, we are able to cut down up to four times the runtime of MapReduce without load balancing.

Runtime also becomes uniform across all file size distributions with load balancing. As the total amount of data is the same in all cases, chunking successfully distributed work evenly across all workers. This experiment shows that load balancing by chunking input files is a good strategy to optimize a distributed system.