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
740
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
540
Map Reduce & Ruby
vanstee
10
780
Other Decks in Programming
See All in Programming
実践Webフロントパフォーマンスチューニング
cp20
45
10k
「理解」を重視したAI活用開発
fast_doctor
0
300
個人開発の学生アプリが企業譲渡されるまで
akidon0000
2
1.2k
Vibe Coding の話をしよう
schroneko
14
3.8k
Boost Your Performance and Developer Productivity with Jakarta EE 11
ivargrimstad
0
880
開発者フレンドリーで顧客も満足?Platformの秘密
algoartis
0
220
By the way Google Cloud Next 2025に行ってみてどうだった
ymd65536
0
130
大LLM時代にこの先生きのこるには-ITエンジニア編
fumiyakume
8
3.4k
VibeCoding時代のエンジニアリング
daisuketakeda
0
200
私のRubyKaigi 2025 Kaigi Effect / My RubyKaigi 2025 Kaigi Effect
chobishiba
1
110
Cursorを活用したAIプログラミングについて 入門
rect
0
200
知識0からカンファレンスやってみたらこうなった!
syossan27
5
250
Featured
See All Featured
Rebuilding a faster, lazier Slack
samanthasiow
81
9k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
194
16k
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
120
52k
A Tale of Four Properties
chriscoyier
159
23k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
34
2.2k
Intergalactic Javascript Robots from Outer Space
tanoku
271
27k
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
656
60k
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
45
9.5k
Agile that works and the tools we love
rasmusluckow
329
21k
[RailsConf 2023] Rails as a piece of cake
palkan
54
5.5k
Designing Experiences People Love
moore
142
24k
Java REST API Framework Comparison - PWX 2021
mraible
31
8.6k
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