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
140
7k
Elixir and Ecto
vanstee
5
930
Bootstrap
vanstee
8
780
HTTP API Design for iOS Applications
vanstee
11
630
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
790
Other Decks in Programming
See All in Programming
なんとなくわかった気になるブロックテーマ入門/contents.nagoya 2025 6.28
chiilog
1
190
Webの外へ飛び出せ NativePHPが切り拓くPHPの未来
takuyakatsusa
2
320
Using AI Tools Around Software Development
inouehi
0
1.3k
Rubyでやりたい駆動開発 / Ruby driven development
chobishiba
1
330
「Cursor/Devin全社導入の理想と現実」のその後
saitoryc
0
140
明示と暗黙 ー PHPとGoの インターフェイスの違いを知る
shimabox
2
280
LINEヤフー データグループ紹介
lycorp_recruit_jp
0
800
今ならAmazon ECSのサービス間通信をどう選ぶか / Selection of ECS Interservice Communication 2025
tkikuc
16
3.1k
Cursor AI Agentと伴走する アプリケーションの高速リプレイス
daisuketakeda
1
130
Gleamという選択肢
comamoca
6
760
PHPで始める振る舞い駆動開発(Behaviour-Driven Development)
ohmori_yusuke
2
170
VS Code Update for GitHub Copilot
74th
1
300
Featured
See All Featured
Embracing the Ebb and Flow
colly
86
4.7k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
138
34k
Helping Users Find Their Own Way: Creating Modern Search Experiences
danielanewman
29
2.7k
Java REST API Framework Comparison - PWX 2021
mraible
31
8.6k
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
107
19k
jQuery: Nuts, Bolts and Bling
dougneiner
63
7.8k
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
46
9.6k
Fireside Chat
paigeccino
37
3.5k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
130
19k
Bash Introduction
62gerente
614
210k
Building Flexible Design Systems
yeseniaperezcruz
328
39k
The Cost Of JavaScript in 2023
addyosmani
51
8.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