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
750
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
7k
Elixir and Ecto
vanstee
5
920
Bootstrap
vanstee
8
780
HTTP API Design for iOS Applications
vanstee
11
620
Consensus: An Introduction to Raft
vanstee
22
2.9k
Pour Over Brewing Method
vanstee
1
340
Celluloid & DCell
vanstee
4
540
Map Reduce & Ruby
vanstee
10
780
Other Decks in Programming
See All in Programming
Agent Rules as Domain Parser
yodakeisuke
1
350
複数アプリケーションを育てていくための共通化戦略
irof
2
700
Practical Domain-Driven Design - Workshop at NDC 2025
mufrid
0
130
當開發遇上包裝:AI 如何讓產品從想法變成商品
clonn
0
2.6k
Cursor Meetup Tokyo ゲノミクスとCursor: 進化と制約のあいだ
koido
1
310
JVM の仕組みを理解して PHP で実装してみよう
m3m0r7
PRO
1
250
ワンバイナリWebサービスのススメ
mackee
10
7.5k
Doma で目指す ORM 最適解
nakamura_to
1
160
衛星の軌道をWeb地図上に表示する
sankichi92
0
250
事業戦略を理解してソフトウェアを設計する
masuda220
PRO
7
1.2k
Devinで実践する!AIエージェントと協働する開発組織の作り方
masahiro_nishimi
6
2.6k
💎 My RubyKaigi Effect in 2025: Top Ruby Companies 🌐
yasulab
PRO
1
130
Featured
See All Featured
How STYLIGHT went responsive
nonsquared
100
5.6k
Reflections from 52 weeks, 52 projects
jeffersonlam
349
20k
KATA
mclloyd
29
14k
YesSQL, Process and Tooling at Scale
rocio
172
14k
Scaling GitHub
holman
459
140k
Visualization
eitanlees
146
16k
Building Adaptive Systems
keathley
41
2.6k
Designing Experiences People Love
moore
142
24k
Learning to Love Humans: Emotional Interface Design
aarron
273
40k
XXLCSS - How to scale CSS and keep your sanity
sugarenia
248
1.3M
Cheating the UX When There Is Nothing More to Optimize - PixelPioneers
stephaniewalter
280
13k
Facilitating Awesome Meetings
lara
54
6.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