Search code examples
multithreadingalgorithmdata-structureskey-valuelockless

Lock Less Key Value data structure

I need a data structure to store 500k keys, each one with some associated data. 150 Threads will be running concurrently & accessing the keys. Once in a day I need to update the data structure since there may be some manipulation operation, say the key is deleted, new key is added or the data is changed. When the data structure updation is in progress I can not block any of the 150 threads from accessing it. I don't want to use current hash implementations like memcache or redis since the number of keys may grow in future & I want in-memory access for faster lookup? Instead will prefer some data structure implementation in C/C++.

Solution

  • The Userspace RCU library contains a set of concurrent data structures implemented with the help of RCU. Among those a lock-free resizable hash table based on the articles

    • Ori Shalev and Nir Shavit. Split-ordered lists: Lock-free extensible hash tables. J. ACM 53, 3 (May 2006), 379-405.
    • Michael, M. M. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, ACM Press, (2002), 73-82.

    For more information you can see the comments in the implementation at http://git.lttng.org/?p=userspace-rcu.git;a=blob;f=rculfhash.c