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

Mudit Verma mudit.f2004912 at gmail.com
Wed Apr 17 08:56:28 EDT 2013


Hello Everyone,

Thanks all for deep insight.  I will soon write in detail about our
approach and rationale behind it. However, one thing is for sure, as you
all mentioned, relaxation would not come for free. We'll have to give up on
some requirements in order to achieve some other such as better
performance.

Mudit


On Thu, Apr 11, 2013 at 9:08 AM, Jan Kotek <discus at kotek.net> wrote:

> **
>
> 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/20130417/5438a17d/attachment.html>


More information about the Concurrency-interest mailing list