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

oleksandr otenko oleksandr.otenko at oracle.com
Wed Apr 10 13:52:06 EDT 2013

That is why it is important to start with the definition of consistency.

When you mean the results do not depend on the order of the operations, 
you mean two things:

1. state transition is linearizable (can be represented as a list of 
2. folding linearized state transitions is, in fact, a monoid 
homomorphism (applying updates is a mapping of free monoid (list of 
updates) to a domain-specific monoid)

You may find it difficult to marry a monoid and happens-before 
requirements of any kind (not even talking about visibility of X 
implying visibility of Y, when Y is outside HashMap).

So you will need to restrict the requirements of where the ordering 
doesn't matter.


On 10/04/2013 17:36, Mudit Verma wrote:
> 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 
> <http://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 <mailto: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 <tel: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 list
>>     Concurrency-interest at cs.oswego.edu  <mailto:Concurrency-interest at cs.oswego.edu>
>>     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>     _______________________________________________
>     Concurrency-interest mailing list
>     Concurrency-interest at cs.oswego.edu
>     <mailto:Concurrency-interest at cs.oswego.edu>
>     http://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/0bee8b10/attachment-0001.html>

More information about the Concurrency-interest mailing list