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

[Ruslan Cheremin]

Eventually consistent cache can be easy created based on open-addressing
hash map, and immutable entries -- without any sync-ing, just like
String.hashCode does. It works if value (which cached) evaluated as f(key),
and f() is pure: JMM guarantee for immutable objects, + atomicity of stores
for references, + OoTA guaranteed by JMM makes it work.

 But I doubt it'll be much faster than precisely implemented sych-ed map.
Seems like (at least on x86) for reads sync-ed and EC versions will differ
only in compiler barriers.




2013/4/10 Nathan Reynolds <nathan.reynolds at oracle.com>

>  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/76253eae/attachment.html>