This document is a description of my implementation for the Sigmod 2009 Programming Contest. You can download here the full code source. The full description of the task is available on the Sigmod website.
My solution is an dynamic hash table with a hash function that preserves the order. The transactions are handled with a one-at-a-time strategy and allocators are pool-allocators with an optimized strategy for strings. Elizabeth did a brillant analysis of the pos and cons of this approach in her master thesis. Basically it is a very dedicated approach to the problem, that performs very well for uniform key distributions.
I would like to thank Pierre Senellart, my supervisor on this project, he was really cool !
The index data structure is a dynamic hash table. The hash function preserves the order on the keys. Collisions are handled with lists. The hash table size doubles every time the number of keys in the table is bigger than the hash table size.
Since the index can support multiple records with the same key, but not the same payload, it is as if the payload is part of the key. It is exactly what is done in my implementation. Therefore in the rest of this document, I will only speak of keys, payloads being just a part of the key.
I maintain the number of elements in the hash table, and also the number of cases actually used by the data. The number of elements divided by the number of cases is a good approximation of the average number of collisions. If this number is too high, the next time I will double the table, I will compute the average of keys and a kind of deviation in order to remap the keys with a new hash funtion, to reduce collisions.
Locks are put on the whole index. There is one mutex per index. There is one journal per index. When the transaction is committed, the memory used by the deleted elements is freed. When the transaction is aborted, the deleted elements are reinserted and the inserted elements are deleted, in reverse order.
Multiple index transactions are handled with a dedicated system. The wait-for graph is maintained. The number of simultaneous threads is limited in order to avoid dead-locks. This number has a big impact on performance and has been carefully studied.
There are two types of allocators.
The first one is for string keys (and payloads). This allocator is a pool allocator where all the strings are stored. Strings are stored with their final '\0' to identify their length. I maintained as many lists as there are possible lengths. Each list contains all the strings of a specific length that has been deleted.
This allocator makes an insertion/deletion in the pool in O(1) but the loss in space is roughly 10% instead of 50% with a trivial pool allocator.
The second one is a typical pool allocator for the structure that embeds the keys. This structure has a pointer to the key, a hash of the key, a pointer to the payload, and a pointer to the next element if there is one.
I tried as much as possible to reduce duplication without decreasing performance. The architecture I used is the following. The index is a template class. The template parameter is the type of key used. This index can be casted to a single interface so that all indexes are stored in the same place. There is still some duplication that I kept for performance reasons: the three different keys have methods that are pretty much the same but at this very low level (comparison of keys for instance) too many function calls would have decreased performance.
I tried several possible optimizations. Here are the mains that I tried with the results.