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

[Jan Kotek]

Hi,

not sure how much it is related, but I wrote BTreeMap and HTreeMap which have 
transactions. It uses embedded db to store tree nodes, but could be easily 
altered to use keep node instances in heap, this way it would work as any 
other heap based collection.

https://github.com/jankotek/mapdb

Jan

On Wednesday 10 April 2013 04:24:14 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






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