Optimal strategy for creating a C ++ hash table, thread safe

Question

(I'm interested in the implementation design is NOT a ready-made design that will do all this.)

Suppose we have a HashTable class (not a hash map implemented as a tree, but a hash table) and they say that there are eight threads. Suppose the read-to-write ratio is around 100: 1 or even better than 1000: 1. Case A) Only one thread is a writer, and others, including the writer, can read from a HashTable (they can just iterate over the entire hash table) Case B ) All threads are identical, and all of them could read / write.

Can anyone suggest a better strategy to make a cool thread safe and then consider 1. The first priority for competition with the least blocking 2. The second priority is the least number of locks

My understanding so far is this: One BIG reader-writer lock (semaphore). Specialize the semaphore so that in case B there can be eight instances of the writer-resource resource, where each write resource blocks one row (or range, for that matter). (so I think 1 + 8 mutexes)

Please let me know if I am thinking of the right line and how we can improve this solution.

Answer 1

With such high read / write ratios, you should consider a lock-free solution, for example. nbds

EDIT:

In general, blocking algorithms work as follows:

• organize the data structures so that for each function that you intend to support, there is a point at which you can determine in one atomic operation whether its results are real (i.e. other threads do not change their inputs because they were read ) and pass them; no state changes visible to other threads if you do not commit. This will include the use of platform-specific features, such as Win32 kernel file comparison and exchange codes or operational cell cache line reservation codes.
• each supported function becomes a loop that reads inputs many times and tries to do the job until the commit completes successfully.

In cases of very low rivalry, this is a gain over blocking algorithms, since functions generally succeed for the first time without causing overhead to acquire a lock. As competition grows, winnings become more dubious.

As a rule, the amount of data that can be processed by an atom is small - 32 or 64 bits are common - therefore, for functions associated with many reads and writes, the resulting algorithms become complex and potentially very difficult to reason. For this reason, it is preferable to look for and accept mature, well-tested and well-understood third-party solutions that are free from blocking for your problem, rather than riding on your own.

Hashtable implementation details will depend on various aspects of the hash and table design. Do we expect the table to grow? If so, we need a way to copy bulk data from the old table to the new one safely. Are we expecting a hash clash? If so, we need some way of passing the counter data. How do we make sure that another thread does not delete the key / value pair between the search that returns it and the caller using it? Maybe some form of reference? - but who owns the link? - or just copying the value when searching? - but what if the values ​​are large?

Locked stacks are well understood and relatively easy to implement (to remove an element from the stack, get the current vertex, try replacing it with the next pointer until you succeed, return it to add an element, get the current vertex and set it as a pointer to the next element until you manage to write a pointer to the element as a new top; on architectures with reservation / conditional write semantics, this is enough so that on architectures that only support CAS, you need to add There is a nonce or version number for atomic data to avoid the problem of excellent presentation on a real approach that allows growth / collision. Others exist, Google quickly finds a lot of papers.

Blocking free and pending algorithms - exciting areas of research; I encourage the reader to google. However, naive locks, free implementations, can easily look reasonable and behave correctly most of the time, while in reality they are unsafe. Although it's important to adhere to the principles, I highly recommend using an existing, well-understood and proven implementation to turn your own.

Answer 2

You can look at the Java implementation of ConcurrentHashMap for one possible implementation.

The basic idea is NOT to block for each read operation, but only for writing. Since they specifically mentioned the extremely high reading / writing ratio in your interview, it makes sense to try to overlay as much recording overhead as possible.

ConcurrentHashMap divides the hash table into so-called “segments”, which are both readable hash tables and keep each individual segment in a consistent state to allow movement without blocking.

When reading, you basically have a regular hashmap get () with the difference that you have to worry about reading stale values, so things like the value of the correct node, the first node of the segment table and the next pointers should be unstable (with a non-existent C memory model ++, which you probably can't do with portability, C ++ 0x should help here, but haven't looked at it yet).

When you place a new item there, you get all the overhead, first of all, to block this segment. After locking it, basically the usual put () operation is done, but you must guarantee atomic writing when updating the next node pointer (pointing to a newly created node, the next pointer of which should correctly point to the old next node) or overwrite the value of node.

As the segment grows, you need to rephrase the existing nodes and place them in a new large table. The important part is to clone the nodes of the new table so as not to affect the old table (by changing their next pointers too soon) until the new table is complete and replaces the old one (they use some kind of smart trick there, which means that they only have to clone about 1/6 nodes - nice, but I'm not quite sure how they reach this number). Please note that garbage collection makes this a lot easier because you don’t have to worry about old nodes that have not been reused - once all readers are finished, they will automatically be GCed. It's solvable, though, but I'm not sure what the best approach would be.

Hopefully the basic idea is somewhat clear - obviously, there are a few points that are trivially not portable to C ++, but this should give you a good idea.

Answer 3

No need to lock the entire table, just a lock for each bucket. This immediately gives parallelism. Inserting a new node into the table requires locking on the bucket to resize the head of the node. New nodes are always added at the beginning of the table so that readers can go through the nodes without worrying about new nodes.

Each node has an r / w lock; iteration readers get a read lock lock. Modifying a node requires write lock.

An iteration without locking the bucket, leading to the removal of the node, requires an attempt to capture the bucket, and if it does not work, it must release the locks and try again to avoid deadlocks, since the locking order is different.

Short review.

Answer 4

You can try atomic_hashtable for c https://github.com/Taymindis/atomic_hashtable to read, write and delete without blocking with multithreading access to Simple and Stable data

API documents specified in README.