Recent Posts

1

General Discussion about just::thread / Re: MVCC

« Last post by sodapop on March 05, 2014, 07:42:12 PM »

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.

2

General Discussion about just::thread / Re: iterator invalidation on insert and erase

« Last post by Anthony Williams on March 05, 2014, 05:34:46 PM »

Here as well, we could use some more documentation and explaination of how to handle this situation while iterating several million records such that we can skip the node if it has beeen deleted.

Iteration automatically skips deleted nodes. If you hang on to your iterator for too long, then another thread might delete the element, but the iterator will still remain valid, can still be dereferenced and still used as a normal iterator. The following code "just works":

Code: [Select]

jss::concurrent_map<int,unsigned> map;
for(jss::concurrent_map<int,unsigned>::iterator it=map.begin();end=map.end();it!=end;++it){
  do_something_with(*it);
}

If the element is deleted after you obtained an iterator to it then you can detect this by calling it->is_deleted_node() but in most cases this isn't necessary --- just proceeding as normal will behave as-if the iteration was done immediately prior to the delete.

3

General Discussion about just::thread / Re: MVCC

« Last post by Anthony Williams on March 05, 2014, 05:27:37 PM »

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?

4

General Discussion about just::thread / Re: iterator invalidation on insert and erase

« Last post by sodapop on March 05, 2014, 05:05:33 PM »

Here as well, we could use some more documentation and explaination of how to handle this situation while iterating several million records such that we can skip the node if it has beeen deleted.

5

General Discussion about just::thread / Re: MVCC

« Last post by sodapop on March 05, 2014, 05:03:17 PM »

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.

6

General Discussion about just::thread / Re: 200 concurrent accessors limit?

« Last post by sodapop on March 05, 2014, 05:00:37 PM »

Well as of Now We do not need more than 200. However it is imperative that we do not design a piece of software knowing that there is a scalability restriction that cannot be overcome if and when needed.

7

General Discussion about just::thread / Re: iterator invalidation on insert and erase

« Last post by Anthony Williams on March 05, 2014, 09:20:37 AM »

Does the jss::concurrent_map handle the issue with iterator invalidation upon calling insert or erase?

Yes. Iterators remain valid until they are destroyed. If you compare an iterator to a deleted node to another iterator then you get a jss::concurrent_modification exception thrown unless you anchored one of the iterators (by calling anchor() on it).

8

General Discussion about just::thread / Re: MVCC

« Last post by Anthony Williams on March 05, 2014, 09:18:30 AM »

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.

9

General Discussion about just::thread / Re: 200 concurrent accessors limit?

« Last post by Anthony Williams on March 05, 2014, 09:14:19 AM »

I read through the justthread documentation for the jss::concurrent_map and it said that it can allow concurrent access from 200 connections. What imposes the 200 limit? Can that be increased?

The 200 accessor limit is due to the size of the required data structure. Increasing the limit will increase the size of the data structure, and in turn increase the time spent checking it during erase.

It is just a constant in the header, and could in principle be changed, or even made configurable via a macro.

Why do you need more than 200 concurrent accesses?

10

General Discussion about just::thread / iterator invalidation on insert and erase

« Last post by sodapop on March 04, 2014, 07:24:44 PM »

Does the jss::concurrent_map handle the issue with iterator invalidation upon calling insert or erase?