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
730
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.9k
Elixir and Ecto
vanstee
5
910
Bootstrap
vanstee
8
770
HTTP API Design for iOS Applications
vanstee
11
610
Consensus: An Introduction to Raft
vanstee
22
2.9k
Pour Over Brewing Method
vanstee
1
340
Celluloid & DCell
vanstee
4
530
Map Reduce & Ruby
vanstee
10
770
Other Decks in Programming
See All in Programming
メモリウォールを超えて:キャッシュメモリ技術の進歩
kawayu
0
1.9k
Cursor/Devin全社導入の理想と現実
saitoryc
20
14k
ウォンテッドリーの「ココロオドル」モバイル開発 / Wantedly's "kokoro odoru" mobile development
kubode
1
150
Enterprise Web App. Development (1): Build Tool Training Ver. 5
knakagawa
1
120
[NG India] Event-Based State Management with NgRx SignalStore
markostanimirovic
1
170
監視 やばい
syossan27
11
9.9k
Ruby's Line Breaks
yui_knk
2
1.3k
Vibe Codingをせずに Clineを使っている
watany
17
6.3k
On-the-fly Suggestions of Rewriting Method Deprecations
ohbarye
1
3.1k
AIコーディングエージェントを 「使いこなす」ための実践知と現在地 in ログラス / How to Use AI Coding Agent in Loglass
rkaga
4
600
AI Coding Agent Enablement - エージェントを自走させよう
yukukotani
14
6.2k
「影響が少ない」を自分の目でみてみる
o0h
PRO
2
1.2k
Featured
See All Featured
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
30
2.3k
The MySQL Ecosystem @ GitHub 2015
samlambert
251
12k
Speed Design
sergeychernyshev
29
900
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
19
1.1k
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
29
9.4k
Principles of Awesome APIs and How to Build Them.
keavy
126
17k
Adopting Sorbet at Scale
ufuk
76
9.3k
Optimising Largest Contentful Paint
csswizardry
36
3.2k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
49k
How to Ace a Technical Interview
jacobian
276
23k
Gamification - CAS2011
davidbonilla
81
5.2k
[RailsConf 2023] Rails as a piece of cake
palkan
54
5.4k
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