Building an FTP and HTTP Server - Part 2

The first version of the camera server became unusably slow when loaded with more than a couple of thousand images and I wanted it to support far more than that. Pictured below insertion CPU usage would quickly grow proportional to the number of files in the file system.

I wrote a script to load an instance of the server with multiple copies of a test file.

Using the script to simulate load I used Instruments to measure statistics and find the performance bottleneck. The first version of the virtual file system used CFTreeRef as a structure to store and retrieve data, an implementation of which is available from opensource.apple.com. Looking at the implementation we can see that children are kept in a linked list, making random access problematic especially when using CFTreeGetChildAtIndex inside a loop the size of the children list. I could have changed the loops to use a cursor and CFTreeGetNextSibling to improve the enumeration performance, but looking at what these two loops do I decided it would be better to change the structure instead.

The first loop looks for a child node with a specific name in the children of a given node; the worst case is that it has to check the names of all child nodes to produce a negative result. Changing the loop to use a cursor isn’t going to improve its worst case time, it will still have to consider all children. Here we can exploit the fact that for any node in the hierarchy, the names of that node’s children must be unique.

The second loop simply enumerates all children; its performance will be limited by the time taken to enumerate the structure used to store the nodes. One change I’ve considered is whether to enumerate the node’s children structure while holding the lock to avoid having to copy the children structure, or whether to simply take a copy while locked and then unlock. I haven’t profiled the difference between these two approaches yet.

The first change I made was to replace the CFTreeRef structure with a custom tree structure whose nodes use a hash table to store their children. I also hinted a high capacity for the tables to alleviate realloc costs as the table grows.

The second change I made was to replace the uses of the Objective-C runtime synchronisation functions, which are recursive mutexes, with a per-node pthread rwlock. I didn’t replace them because of any overhead, but because I wanted to change the lock type. While this doesn’t directly affect performance yet, when I get around to finishing the libdispatch support in CoreNetworking and client connections are each independently serialised opposed to now where they are globally serialised, the file system will be able to serve multiple reads concurrently.

After completing the performance improvement changeset I ran the stress test script again. With two versions of the file system to compare I used time to measure how long the test script took to run.

At low file numbers the difference between runs is negligible, but when there are multiple thousands the new implementation is an order of magnitude faster.

With the new file system in place I updated the server and left it to run. I got bored waiting for the file system to get sufficiently loaded so that I could see how many images it would hold, I decreased the snapshot interval on the camera to its minimum of 200ms and waited some more. It capped out at 254,426 images and just over 60GB of virtual memory at which point OS X started to complain visibly to the user, requesting that you terminate a running application to free up memory.

For a more reasonable snapshot interval of every second this would last about 3 days. If I want to keep the image history for any longer than that I’ll write a virtual file system that uses permanent storage, and I’ll probably change the file system API to be asynchronous so that vfs subclasses can do non-blocking I/O to their store.