4 ms·

The Scalable Commutativity Rule

40 points by mad44 12y ago

ShaneWilton 12y ago
This sort of thing has been cropping up in distributed systems quite a bit recently, in the form of CRDTs: commutative replicated data-types. Essentially data structures whose operations commute. This offers a lot of powerful guarantees when it comes to dealing with consistency in a distributed system. They're an interesting concept, and I'd highly recommend reading more about them. The original paper: http://highscalability.com/blog/2010/12/23/paper-crdts-consistency-without-concurrency-control.html http://highscalability.com/blog/2010/12/23/paper-crdts-consi... Their use in League of Legends: http://highscalability.com/blog/2014/10/13/how-league-of-legends-scaled-chat-to-70-million-players-it-t.html http://highscalability.com/blog/2014/10/13/how-league-of-leg... How Riak uses them: http://aphyr.com/posts/285-call-me-maybe-riak http://aphyr.com/posts/285-call-me-maybe-riak
- seanmcdirmid 12y ago
  Glitch [1] is based on this to achieve eventual consistency through dependency tracking and replay. Its not exactly the same though: many operations commute (e.g. accumulation), but certain operations like cell assignment will never commute, so we have to dynamically disallow re-assignment. Another trick is to pair commutative operation order with transactional style rollback, which allows the repair of arbitrary executions (since you can rollback executions and redo them in any order!). [1] http://research.microsoft.com/pubs/211297/onward14.pdf http://research.microsoft.com/pubs/211297/onward14.pdf
tormeh 12y ago
Occam were heavy on this. In Occam you explicitly stated which parts of your program were sequential and which were parallel (i.e. commutative), sequentialism not assumed. Sadly, Occam is a dead language now; it was too far ahead of its time.
- sitkack 12y ago
  http://www.xmos.com/ http://www.xmos.com/ http://en.wikipedia.org/wiki/XC_(programming_language) http://en.wikipedia.org/wiki/XC_(programming_language) https://www.xmos.com/support/xkits?subcategory=Starter%20Kits&product=17441&component=17653&page=23 https://www.xmos.com/support/xkits?subcategory=Starter%20Kit...
sitkack 12y ago
The video presentation of this session is available by clicking through the ToC, or Source Materials http://dl.acm.org/citation.cfm?doid=2517349.2522712 http://dl.acm.org/citation.cfm?doid=2517349.2522712

40 points by mad44 12y ago

This sort of thing has been cropping up in distributed systems quite a bit recently, in the form of CRDTs: commutative replicated data-types. Essentially data structures whose operations commute. This offers a lot of powerful guarantees when it comes to dealing with consistency in a distributed system. They're an interesting concept, and I'd highly recommend reading more about them. The original paper: http://highscalability.com/blog/2010/12/23/paper-crdts-consistency-without-concurrency-control.html http://highscalability.com/blog/2010/12/23/paper-crdts-consi... Their use in League of Legends: http://highscalability.com/blog/2014/10/13/how-league-of-legends-scaled-chat-to-70-million-players-it-t.html http://highscalability.com/blog/2014/10/13/how-league-of-leg... How Riak uses them: http://aphyr.com/posts/285-call-me-maybe-riak http://aphyr.com/posts/285-call-me-maybe-riak

seanmcdirmid 12y ago
Glitch [1] is based on this to achieve eventual consistency through dependency tracking and replay. Its not exactly the same though: many operations commute (e.g. accumulation), but certain operations like cell assignment will never commute, so we have to dynamically disallow re-assignment. Another trick is to pair commutative operation order with transactional style rollback, which allows the repair of arbitrary executions (since you can rollback executions and redo them in any order!). [1] http://research.microsoft.com/pubs/211297/onward14.pdf http://research.microsoft.com/pubs/211297/onward14.pdf

tormeh 12y ago

Occam were heavy on this. In Occam you explicitly stated which parts of your program were sequential and which were parallel (i.e. commutative), sequentialism not assumed. Sadly, Occam is a dead language now; it was too far ahead of its time.

sitkack 12y ago
http://www.xmos.com/ http://www.xmos.com/ http://en.wikipedia.org/wiki/XC_(programming_language) http://en.wikipedia.org/wiki/XC_(programming_language) https://www.xmos.com/support/xkits?subcategory=Starter%20Kits&product=17441&component=17653&page=23 https://www.xmos.com/support/xkits?subcategory=Starter%20Kit...

sitkack 12y ago

The video presentation of this session is available by clicking through the ToC, or Source Materials http://dl.acm.org/citation.cfm?doid=2517349.2522712 http://dl.acm.org/citation.cfm?doid=2517349.2522712