Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Convergent Replicated Data Types
Search
Patrick Van Stee
December 14, 2012
Programming
4
710
Convergent Replicated Data Types
Patrick Van Stee
December 14, 2012
Tweet
Share
More Decks by Patrick Van Stee
See All by Patrick Van Stee
Raft: Consensus for Rubyists
vanstee
137
6.8k
Elixir and Ecto
vanstee
5
890
Bootstrap
vanstee
8
750
HTTP API Design for iOS Applications
vanstee
11
590
Consensus: An Introduction to Raft
vanstee
22
2.9k
Pour Over Brewing Method
vanstee
1
320
Celluloid & DCell
vanstee
4
520
Map Reduce & Ruby
vanstee
10
750
Other Decks in Programming
See All in Programming
Grafana Cloudとソラカメ
devoc
0
170
color-scheme: light dark; を完全に理解する
uhyo
3
310
Conform を推す - Advocating for Conform
mizoguchicoji
3
690
GoとPHPのインターフェイスの違い
shimabox
2
190
社内フレームワークとその依存性解決 / in-house framework and its dependency management
vvakame
1
560
2024年のkintone API振り返りと2025年 / kintone API look back in 2024
tasshi
0
220
『GO』アプリ データ基盤のログ収集システムコスト削減
mot_techtalk
0
120
Djangoアプリケーション 運用のリアル 〜問題発生から可視化、最適化への道〜 #pyconshizu
kashewnuts
1
250
Open source software: how to live long and go far
gaelvaroquaux
0
630
Multi Step Form, Decentralized Autonomous Organization
pumpkiinbell
1
740
Boost Performance and Developer Productivity with Jakarta EE 11
ivargrimstad
0
270
仕様変更に耐えるための"今の"DRY原則を考える / Rethinking the "Don't repeat yourself" for resilience to specification changes
mkmk884
0
160
Featured
See All Featured
Thoughts on Productivity
jonyablonski
69
4.5k
The Straight Up "How To Draw Better" Workshop
denniskardys
232
140k
[RailsConf 2023] Rails as a piece of cake
palkan
53
5.2k
Facilitating Awesome Meetings
lara
52
6.2k
Build The Right Thing And Hit Your Dates
maggiecrowley
34
2.5k
Building a Scalable Design System with Sketch
lauravandoore
461
33k
"I'm Feeling Lucky" - Building Great Search Experiences for Today's Users (#IAC19)
danielanewman
226
22k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
49
2.3k
Become a Pro
speakerdeck
PRO
26
5.1k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
33
2.8k
Why You Should Never Use an ORM
jnunemaker
PRO
55
9.2k
Writing Fast Ruby
sferik
628
61k
Transcript
Convergent Replicated Data Types
@vanstee
[email protected]
Patrick Van Stee
“Structuring data so conflict resolution is automatic”
Dynamo Trade consistency for availability and partition tolerance
Node 1 Node 2 { a: “200” } { a:
“-3000” } :(
Node 1 Node 2 { a: “200” } { a:
“-3000” } { a: “200”, a: “-3000” } Riak
CRDT •Counter •Set •Graph •List •Tree
CRDT •Counter •Set •Graph •List •Tree
Counter •Can only be increased •Merge: use largest value
Chat Room Karma Fault-Tolerant Distributed
Serious Business { SB[PVS]: 0} Serious Coding { SB[PVS]: 1}
# PVS++ { SC[PVS]: 0} { SC[PVS]: 5} # PVS += 5 { SB[PVS]: 2} # PVS++ Merge { SB[PVS]: 2, SC[PVS]: 5} { SB[PVS]: 1, SC[PVS]: 5} { SB[PVS]: 2, SC[PVS]: 5} { PVS: 7}
What about decrements? Use separate counters for positive and negative.
Take the difference for the result.
Serious Business { SB[PVS+]: 0, SB[PVS-]: 0 } Serious Coding
{ SB[PVS+]: 1, SB[PVS-]: 0 } # PVS++ { SB[PVS+]: 0, SB[PVS-]: 0 } { SB[PVS+]: 5, SB[PVS-]: 0 } # PVS += 5 { SB[PVS+]: 1, SB[PVS-]: 1 } # PVS-- Merge { PVS+: 6, PVS-: 1 } { PVS+: 6, PVS-: 0 } { PVS+: 6, PVS-: 1 } { PVS: 5 }
Set •Can only be added to •Merge: take the union
Serious Business { PVS: [ ] } Serious Coding {
PVS: [] } { PVS: [] } { PVS: [ ] } Merge { PVS: [ , ] } { PVS: [ , ] } { PVS: [ , , ] } { PVS: [ , , ] }
Hold on, Can we remove stuff? Use separate sets for
added and removed elements.
Serious Business { PVS+: [ ], PVS-: [] } Serious
Coding { PVS+: [], PVS-: [] } { PVS+: [], PVS-: [] } { PVS+: [ ], PVS-: [] } Merge { PVS+: [ , ], PVS-: [ ] } { PVS+: [ ], PVS-: [ ] } { PVS+: [ , ], PVS-: [] } { PVS+: [ , ], PVS-: [ ] } { PVS: [ ] }
But wait, we can only remove once?
U-Set •Append unique values to all set members •Garbage collection
becomes an issue
basho/riak_dt Demo
Use Cases •Like button •Page Views •Shopping Cart
Reference •INRIA paper •basho/riak_dt •RICON talk
Beginning Ruby on Rails Course bignerdranch.com/classes/beginning_ruby_on_rails