[concurrency-interest] An Eventually Consistent highly scalable K-V Store/HashMap

Boehm, Hans hans.boehm at hp.com
Wed Apr 10 13:40:25 EDT 2013

What are you going to put into these stores?  If thread 1 puts in a reference to an object P, and thread 2 retrieves P from the store, is thread 2 guaranteed to be able to see all of P's fields, including the non-final ones changed after construction?  Does communicating the object through the KV store ensure visibility?  If not, this seems like a very limited facility that requires extremely careful documentation.


From: concurrency-interest-bounces at cs.oswego.edu [mailto:concurrency-interest-bounces at cs.oswego.edu] On Behalf Of Ruslan Cheremin
Sent: Wednesday, April 10, 2013 9:20 AM
To: Nathan Reynolds
Cc: concurrency-interest at cs.oswego.edu
Subject: Re: [concurrency-interest] An Eventually Consistent highly scalable K-V Store/HashMap

Eventually consistent cache can be easy created based on open-addressing hash map, and immutable entries -- without any sync-ing, just like String.hashCode does. It works if value (which cached) evaluated as f(key), and f() is pure: JMM guarantee for immutable objects, + atomicity of stores for references, + OoTA guaranteed by JMM makes it work.

 But I doubt it'll be much faster than precisely implemented sych-ed map. Seems like (at least on x86) for reads sync-ed and EC versions will differ only in compiler barriers.

2013/4/10 Nathan Reynolds <nathan.reynolds at oracle.com<mailto:nathan.reynolds at oracle.com>>
What kind of transactions are you talking about?  Software transactional memory?  Hardware transactional memory?  Database-like transactions?

Eventually consistent HashMaps/KV stores could definitely be useful for caches.  Application servers have many caches with a lot of threads hitting them rapidly.  Simply replacing the lock with a slower concurrent path isn't going help.
Nathan Reynolds<http://psr.us.oracle.com/wiki/index.php/User:Nathan_Reynolds> | Architect | 602.333.9091
Oracle PSR Engineering<http://psr.us.oracle.com/> | Server Technology
On 4/9/2013 7:24 PM, Mudit Verma wrote:
Hello All,

I am new to the group. For past few months I have been working on Concurrent Data Structures for my master thesis. My work is motivated by the assumption that in future, with growing number of cores per machine, we might need to give up strong semantics in order to achieve better performance.
For example, we have come up with a sequentially consistent version of Queue which is 50-70 times faster than the original linearized  ConcurrentLinkedQueue under very high contention. In our synthetic benchmarks we have found that in ConcurrentLinkedQueue one operation (enqueue/dequeue) can take as high as 3,00,000 cycles  where ThinkTime/Delay between two operations (work done between two ops)  is in order of 200,000-300,000 cycles.
With the same approach of relaxing the semantics, we want to implement a KV (hashmap/hashset) which will be designed just keeping in mind the very high scalability.  Obviously, we are giving up on stronger semantics but we think that there are applications which can bear with it.
We did some scalability testing on ConcurrentHashMap but I just now found out that a new implementation is planned for Java 8 which has better scalability.
We want to use CRDTs (conflict free replicated data types) techniques used in distributed systems [1] where operations commute (add followed by remove or remove followed by add converge to same state eventually).
We also think that transactions can be implemented on top KV  where multiples puts/gets are grouped and applied by workers and have atomic (all or none) effect on underneath KV store/hashMap.

Since people in this group work actively on Concurrent Data Structures, I am looking for comments and suggestions on

a. Eventually Consistent HashMaps/KV Stores for multicores.
b. Transactions on top of HashMaps/KV Stores in multicores.
What are your take on these two ideas, will it be useful?  If yes, do you have some applications in mind?
Mudit Verma


Concurrency-interest mailing list

Concurrency-interest at cs.oswego.edu<mailto:Concurrency-interest at cs.oswego.edu>


Concurrency-interest mailing list
Concurrency-interest at cs.oswego.edu<mailto:Concurrency-interest at cs.oswego.edu>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20130410/dfa7bd29/attachment.html>

More information about the Concurrency-interest mailing list