Sunrise Data Dictionary for C
C library for lock-free hash table storage of arbitrary data
The Sunrise Data Dictionary is a library for lock-free hash table storage of arbitrary data objects with built-in reference counting and guaranteed order iteration for the C programming language. It can be used with the Boehm garbage collector, participate in external reference counting systems or use its own built-in reference counting. It comes with a variety of built-in hash functions and allows the use of runtime supplied hash functions via callback.
The library is released under the Sunrise Open Source License, an MIT style license. It is license compatible with GPL2 and proprietary licenses. The source code is well documented.
For the lock-free algorithms used in the library to work properly, architecture specific inline assembly macros for atomic operations are required. OS supplied macros have proven unsuitable as they are for use within the kernel only. A new operating system independent atomic operations macro library is now under development. The macros for IA32 and PPC (download) are under peer review and will be added in the next revision of the library. Further refactoring in conjunction with lock-free operation is in progress.
The Sunrise Data Dictionary was specifically designed for use within the Afelio and Callweaver telephony servers, the implementation focuses on reliability, performance and scalability.
These design objectives are achieved through ...
The API design is strictly based on the concept of data encapsulation and information hiding. That is to say the library only exports opaque datatypes in order to hide all implementation details. All data structures are private, they are never exposed and can only be accessed and manipulated through accessor and mutator functions provided by the API's public interface.
All objects stored in a hash table created and managed by the library are reference counted internally within the hash table itself. Objects cannot be replaced in or removed from a table for as long as there are any tasks which hold references to them. A hash table cannot be deleted for as long as there are any tasks which hold references to objects stored in it.
The built-in reference counting system can be used as the sole point of management, where objects will be automatically deallocated by the hash table when they are removed. Alternatively it can be used in conjunction with an external reference counting system, where objects will be automatically released when they are removed from the table. Last but not least, the library can be configured to work with and use the Boehm garbage collector.
Lock-free lookup, insert and removal
Lookup and insert operations are lock-free and wait-free, removal operations and iteration are lock-free but not wait-free whilst the disposal of a table is neither lock-free nor wait-free. However, table disposal will only inhibit new lookups and inserts while waiting for all outstanding lookups and inserts to complete. It does not block lookups and inserts.
As a result, concurrent lookups and inserts do not cause any bottlenecks as would be the case with mutual exclusion or r/w locks. This means vastly improved scalability in multi-threaded and symmetric multi-processing environments. Further, lock-free operations execute faster and require fewer system resources than operations that need to acquire locks.
As a benevolent side effect of lock-free removal, dynamically allocated data structures previously holding entries which have been removed from the table are recycled and used again by subsequent inserts into the same bucket. This is more efficient than deallocating and reallocating those data structures and it keeps memory fragmentation at bay.
Hash table dimensioning and resizing strategies
The Sunrise Data Dictionary provides two different hash table implementations with different dimensioning/resizing strategies. The default implementation uses a high-water marking and tuning strategy, which guarantees fast, near constant response times. An alternative implementation for large tables with unpredictable capacity requirements uses a cluster prone bucket resizing strategy which minimises the performance impact of a resize operation in progress. The two strategies and their rationales are described in more detail below.
High-water marking and tuning
Resizing a hash table while it is in use is an expensive operation which generally slows down lookups and inserts significantly while resize is in progress. Performance will improve after a table has been resized but for real-time applications such as telephony, the periodically occuring sudden increase in latency of lookup and insert operations during resize is highly undesirable as it can lead to distorted audio, dropped audio frames and even dropped telephone calls. For real-time applications, predictable response times are generally more important than regaining the performance characteristics of a sparsely populated table.
In many cases the maximum table capacity required can be estimated. For example, in a telephony server, the required table size is typically a function of the maximum number of concurrent telephone calls the server can process. In such cases it is a good strategy for a hash table implementation to record and report the table load high-water mark and then dimension the table appropriately upon restart. Once the server's required table capacity at full load has been determined, no further tuning will be necessary and response times for lookup and insert operations will remain constant.
Resizing of cluster prone buckets
In cases where the required table capacity is very large but unpredictable, dynamic resizing may be unavoidable. However, a good resizing strategy will aim to minimise the performance impact on ongoing lookups and inserts. In order to devise a strategy that can achieve this it is helpful to understand what causes the performance of a hash table to drop as it gets more densely populated, further, what causes a resize operation to slow down the entire table.
When inserts produce collisions, multiple entries get stored in the same bucket. Linear search is then required to find a given entry within the bucket. This gradually leads to a loss of performance. For very large data sets a good strategy is to avoid or at least postpone this performance slow down in the first place.
Since the slow down is caused by linear search, the solution is surprisingly obvious: use a secondary hash table to store multiple entries in a bucket and thereby avoid or at least postpone linear search. This leads to a two-dimensional hash table, a hash table of hash tables, that is to say there is one secondary hash table for each bucket in the primary hash table. Different hash functions need to be used for primary and secondary hash tables and there are always two lookups for each lookup and insert operation. This constitutes slightly more overhead but the response times are again nearly constant even with a very high table load. Performance does not begin to degrade until inserts start to produce collisions in the secondary hash tables.
A two dimensional hash table can take advantage of an effect called clustering, that is, collisions in a hash table are never evenly distributed, they tend to cluster around certain buckets. In a two-dimensional hash table, secondary hash tables which produce more collisions than others represent clusters. They can be identified and dynamically resized. This is far more efficient than reszing a larger one-dimensional table. First, the resize is limited to a fraction of the table and less copying and rehashing needs to be carried out. Second, lookups and inserts into other buckets are not affected by an ongoing resize operation at all. Third, only those parts of the table where collisions occur are resized, in other words, resizing is limited to areas where it really matters.
Latest developer snapshot: version 1.00 revision 28.
Please note that this snapshot does not yet implement all of the features described.
API in detail
Common type definitions used by this library. · View dd_types.h
Convenience macros. · View dd_macros.h
Factory default settings for this library. This file is intended for compile-time customisation by library users. · View dd_settings.h
API to query version number and default settings at runtime. · View dd_lib_info.h
Status codes returned by various functions of this library. · View dd_status_codes.h
Default hash functions for case sensitive and case insensitive hashing.
API to calculate the size of hashtables.
API to create and iterate alphabetically ordered lists of keys. · View dd_sorted_keys.h
API to create, use and destroy simple symbol lookup tables supporting forward and reverse symbol lookup such as frequently used in lexers and parsers. · View dd_symbol_table.h
API to create, use, iterate and destroy data dictionaries for storage and retrieval of arbitrary data objects, with built-in reference counting and guaranteed order iteration.