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

Mudit Verma mudit.f2004912 at gmail.com
Tue Apr 9 22:24:14 EDT 2013

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

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

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20130410/3835479d/attachment.html>

More information about the Concurrency-interest mailing list