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

Mudit Verma mudit.f2004912 at gmail.com
Wed Apr 10 12:36:32 EDT 2013


Data base like transactions. Main idea is to use community between the
operation. This will allow HashMap to converge eventually to deterministic
state, no matter in which order the operations are applied. Transaction
will give all or none kind of behavior + if a two operation X and Y are
committed in a transaction. Both object should be consistent. If I see the
effect of X, I should be able to see the effect of Y as well.

Conflict free replicated data tyes - CRDT
 pagesperso-systeme.lip6.fr/Marc.Shapiro/papers/RR-6956.pdf

Thanks,
Mudit




On Wed, Apr 10, 2013 at 6:03 PM, Nathan Reynolds <nathan.reynolds at oracle.com
> wrote:

>  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 listConcurrency-interest at cs.oswego.eduhttp://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
>
> _______________________________________________
> 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/73ebb401/attachment-0001.html>


More information about the Concurrency-interest mailing list