[concurrency-interest] An Eventually Consistent highly scalable K-V Store/HashMap
cheremin at gmail.com
Wed Apr 10 12:20:01 EDT 2013
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
> 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
> We want to use CRDTs (conflict free replicated data types) techniques
> used in distributed systems  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?
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Concurrency-interest