MVCC

[sodapop]

Is there any documentation on how to implement MVCC in a jss::concurrent_map? The whole idea is to not lock the map for writing when there might be multiple threads reading from the map.

[Anthony Williams]

Is there any documentation on how to implement MVCC in a jss::concurrent_map? The whole idea is to not lock the map for writing when there might be multiple threads reading from the map.

jss::concurrent_map does not lock the map for writing whilst a read is taking place. The whole thing is lock-free, except it uses new and delete, which might therefore use a lock.

[sodapop]

Is there anyplace I can read more about how the map internally handle concurrency? We are trying to implement multi version concurrency control. Without looking at the internal implementation of how the data structure implements lock free writing, it would be impossible for us to try and implement MVCC. Your thoughts on this will be very helpful. Let me know if this is something we can discuss offline.

[Anthony Williams]

Is there anyplace I can read more about how the map internally handle concurrency? We are trying to implement multi version concurrency control. Without looking at the internal implementation of how the data structure implements lock free writing, it would be impossible for us to try and implement MVCC. Your thoughts on this will be very helpful. Let me know if this is something we can discuss offline.

Underneath it all, the hash-map is a linked-list with bucket markers.

Inserts are done by a simple atomic compare-exchange on the relevant entry.

Deletes are done by adding a flag to the "next" pointer of the node being deleted, doing a CAS on the next pointer of the previous node to remove it from the list, and then putting the node aside to be collected later by the clean-up code.

Replaces are done by creating a new node for the required value, copying the next pointer from the existing node for that value into the new node, and then doing a compare-exchange to set the next pointer in the node being replaced with a pointer to the new node marked with the "node deleted" flag. The old value is now marked as deleted and the new node is in the list. The delete clean up code is now run to finish the job.

So, values are either in the map and visible to all, marked as deleted and thus ignored by all, or not in the map.

What do you need for MVCC?

[sodapop]

MVCC at the simplest form should work as follows:
1) All threads/accessors should be able to read the map concurrently at any given time with seperate isolation levels (read_committed, dirty_read etc)
2) Nodes do not ever get physically deleted unless it is done by a cleanup operation.
3) When a node is modified, technically the code simply inserts a new node with a timestamp. the timestamp is what tells which node is an older version of another node (i.e. technically deleted).
4) When an accessor is trying to read while another operation is inserting a newer version on an existing node, depending on the isolation level the older version gets read if the isolation level is dirty else the accessor should block until the write operation completes i.e. if the reader is using a read_committed isolation level.

I am open to discussing offline to help me achieve this using the concurrent map in the just::thread library.