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

Nathan Reynolds nathan.reynolds at oracle.com
Wed Apr 10 12:03:55 EDT 2013

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?
> Thanks,
> Mudit Verma
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

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

More information about the Concurrency-interest mailing list