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
640
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
134
6.5k
Elixir and Ecto
vanstee
5
780
Bootstrap
vanstee
8
690
HTTP API Design for iOS Applications
vanstee
11
520
Consensus: An Introduction to Raft
vanstee
22
2.7k
Pour Over Brewing Method
vanstee
1
270
Celluloid & DCell
vanstee
4
440
Map Reduce & Ruby
vanstee
10
660
Other Decks in Programming
See All in Programming
Polarsの成長: v0.14からv1.0までの変遷と今後の展望
zerebom
1
350
CSC307 Lecture 06
javiergs
PRO
0
360
入社1ヶ月でここまでやった!Findy Toolsインフラ支援の最適化
rvirus0817
6
1.4k
英語
s_shimotori
1
220
初心者がおさえておきたいAWS CDKのベストプラクティス 2024
konokenj
15
7.3k
유연한 Composable 설계
l2hyunwoo
0
380
Rust.Nagoya #1
codemountains
0
170
HMSコンペ 11th Solution (team : kansai-kaggler)
t88
1
680
Javaの現状2024夏 / Java current status 2024 summer
kishida
4
1.4k
SRE チーム立ち上げ前に考えたこと・取り組んだこと / Considerations and Preparations Before Establishing an SRE Team
mackey0225
3
320
Introduction of Happy Eyeballs Version 2 (RFC8305) to the Socket library
coe401_
1
220
12年前の『型システム入門』翻訳の思い出話
mame
11
1.2k
Featured
See All Featured
Producing Creativity
orderedlist
PRO
340
39k
Testing 201, or: Great Expectations
jmmastey
33
6.9k
Pencils Down: Stop Designing & Start Developing
hursman
118
11k
Large-scale JavaScript Application Architecture
addyosmani
506
110k
No one is an island. Learnings from fostering a developers community.
thoeni
17
2.8k
Visualization
eitanlees
139
14k
GitHub's CSS Performance
jonrohan
1026
450k
Scaling GitHub
holman
458
140k
KATA
mclloyd
20
13k
Designing with Data
zakiwarfel
96
5k
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
149
45k
Principles of Awesome APIs and How to Build Them.
keavy
124
16k
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