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
140
7.1k
Elixir and Ecto
vanstee
5
940
Bootstrap
vanstee
8
790
HTTP API Design for iOS Applications
vanstee
11
640
Consensus: An Introduction to Raft
vanstee
22
3k
Pour Over Brewing Method
vanstee
1
360
Celluloid & DCell
vanstee
4
550
Map Reduce & Ruby
vanstee
10
810
Other Decks in Programming
See All in Programming
Ruby×iOSアプリ開発 ~共に歩んだエコシステムの物語~
temoki
0
320
Cache Me If You Can
ryunen344
2
1.4k
OSS開発者という働き方
andpad
5
1.7k
実用的なGOCACHEPROG実装をするために / golang.tokyo #40
mazrean
1
280
ファインディ株式会社におけるMCP活用とサービス開発
starfish719
0
1.6k
「手軽で便利」に潜む罠。 Popover API を WCAG 2.2の視点で安全に使うには
taitotnk
0
860
Flutter with Dart MCP: All You Need - 박제창 2025 I/O Extended Busan
itsmedreamwalker
0
150
Swift Updates - Learn Languages 2025
koher
2
480
AWS発のAIエディタKiroを使ってみた
iriikeita
1
190
Oracle Database Technology Night 92 Database Connection control FAN-AC
oracle4engineer
PRO
1
450
今から始めるClaude Code入門〜AIコーディングエージェントの歴史と導入〜
nokomoro3
0
180
時間軸から考えるTerraformを使う理由と留意点
fufuhu
16
4.8k
Featured
See All Featured
Build The Right Thing And Hit Your Dates
maggiecrowley
37
2.9k
RailsConf 2023
tenderlove
30
1.2k
Designing Experiences People Love
moore
142
24k
The Psychology of Web Performance [Beyond Tellerrand 2023]
tammyeverts
49
3k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
162
15k
A Tale of Four Properties
chriscoyier
160
23k
Large-scale JavaScript Application Architecture
addyosmani
512
110k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
139
34k
Code Reviewing Like a Champion
maltzj
525
40k
Connecting the Dots Between Site Speed, User Experience & Your Business [WebExpo 2025]
tammyeverts
8
520
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
507
140k
Imperfection Machines: The Place of Print at Facebook
scottboms
268
13k
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