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
770
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
139
7.1k
Elixir and Ecto
vanstee
5
950
Bootstrap
vanstee
8
790
HTTP API Design for iOS Applications
vanstee
11
640
Consensus: An Introduction to Raft
vanstee
21
3k
Pour Over Brewing Method
vanstee
1
360
Celluloid & DCell
vanstee
4
560
Map Reduce & Ruby
vanstee
10
820
Other Decks in Programming
See All in Programming
株式会社 Sun terras カンパニーデック
sunterras
0
190
Your Perfect Project Setup for Angular @BASTA! 2025 in Mainz
manfredsteyer
PRO
0
110
Current States of Java Web Frameworks at JCConf 2025
kishida
0
590
XP, Testing and ninja testing ZOZ5
m_seki
2
240
iOSDC.pdf
chronos2500
2
650
高度なUI/UXこそHotwireで作ろう Kaigi on Rails 2025
naofumi
4
3.1k
CSC305 Lecture 04
javiergs
PRO
0
230
育てるアーキテクチャ:戦い抜くPythonマイクロサービスの設計と進化戦略
fujidomoe
1
150
ポスターセッション: 「まっすぐ行って、右!」って言ってラズパイカーを動かしたい 〜生成AI × Raspberry Pi Pico × Gradioの試作メモ〜
komofr
0
900
2分台で1500examples完走!爆速CIを支える環境構築術 - Kaigi on Rails 2025
falcon8823
3
2.8k
Reduxモダナイズ 〜コードのモダン化を通して、将来のライブラリ移行に備える〜
pvcresin
2
670
どの様にAIエージェントと 協業すべきだったのか?
takefumiyoshii
1
570
Featured
See All Featured
RailsConf 2023
tenderlove
30
1.2k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
333
22k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
26
3.1k
Writing Fast Ruby
sferik
629
62k
Building a Modern Day E-commerce SEO Strategy
aleyda
43
7.7k
It's Worth the Effort
3n
187
28k
Context Engineering - Making Every Token Count
addyosmani
4
160
Dealing with People You Can't Stand - Big Design 2015
cassininazir
367
27k
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
48
9.7k
No one is an island. Learnings from fostering a developers community.
thoeni
21
3.5k
Helping Users Find Their Own Way: Creating Modern Search Experiences
danielanewman
30
2.9k
Designing for Performance
lara
610
69k
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