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

oleksandr otenko oleksandr.otenko at oracle.com
Wed Apr 10 09:47:50 EDT 2013


I'd start with defining "eventually" and "consistent".

Alex


On 10/04/2013 03:24, 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/394a1e92/attachment.html>


More information about the Concurrency-interest mailing list