aws/aws-cli — pull request #355 by jamesls (2013-09-16 20:33:04+00:00)
Title: Reduce CPU utilization for multipart uploads

Fixes #333.

This change also pulls in #350 and #349 as they're all touching similar code and will result in merge conflicts (those changes have already been reviewed in their respective pull requests).

This change is a rework how multipart uploads works.

### Before

The multipart upload was added as a **single** task to the task queue. When the actual code for processing the task was invoked, it would then submit additional tasks to the end of the task queue. You'd end up with something like this:

```
# Originally

Queue: mpu1, mpu2, mpu3, mpu4, mpu5, mpu6, mpu7, mpu8

# After the first 3 tasks are in progress:
Queue: mpu4, mpu5, mpu6, mpu7, mpu8, mpu1-1, mpu1-2, mpu1-3, mpu1-4, mpu2-1, mpu2-2, mpu2-3, ...
```

The problem was that you could deadlock if you started too many multipart uploads because the worker threads would wait until all the parts (`mpuN-*` in the section above) would finish, but you could tie up all the threads in the thread pool where they're all waiting on parts. This is easy to think about if you have a thread pool size of one.

To account for this, the original code would check to see if it's task was a multipart upload task and put it back on the queue if it knew it would deadlock. This would mean:

```
Queue: mpu4, mpu5, mpu6, mpu7, mpu8, mpu1-1, mpu1-2, mpu1-3, mpu1-4, mpu2-1, mpu2-2, mpu2-3, ...
| | | | |
-------------------------
|
|
Take off the queue and put back at the end of queue

Queue: mpu1-1, mpu1-2, mpu1-3, mpu1-4, mpu2-1, mpu2-2, mpu2-3, mpu4, mpu5, mpu6, mpu7, mpu8
```

If you imagine instead of 8 multi part uploads we instead have thousands, you can see how we'd create a lot of spin loops for threads, each cycle of multipart uploads would cycle through the entire queue.

### New

Instead we break out the part tasks to begin with:

```
Queue: mpu1-start, mpu1-1, mpu1-2, mpu1-3, mpu1-4, mpu1-end, mpu2-start, mpu2-1, mpu2-2, ...
```

And each multipart upload sequence (`mpuN-*`) is passed a context object that has condition variables for the dependencies between tasks (`upload_id` and the `parts` list).

### Results

In the worst case scenario where we have a large IO pipe, there's a big reduction in CPU utilization:

![newmulti](https://f.cloud.github.com/assets/368057/1152444/36822e3a-1f0d-11e3-996e-7c14ffb5cf38.png)

In the case where you're IO bound (in this test, capped bandwidth to 10Mbps), the CPU utilization is even lower:

![newmulti-iobound](https://f.cloud.github.com/assets/368057/1152459/6ec6611c-1f0d-11e3-9615-5eb01d009a10.png)

### Remaining Work

I still can't rip out all of the old multipart code because I need to port this over to the download tasks (will do shortly). Would like to get this code in first though.