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
730
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
330
Celluloid & DCell
vanstee
4
530
Map Reduce & Ruby
vanstee
10
770
Other Decks in Programming
See All in Programming
Preact、HooksとSignalsの両立 / Preact: Harmonizing Hooks and Signals
ssssota
1
1.5k
AIコードエディタの基盤となるLLMのFlutter性能評価
alquist4121
0
210
AWSで雰囲気でつくる! VRChatの写真変換ピタゴラスイッチ
anatofuz
0
150
エンジニア未経験が最短で戦力になるためのTips
gokana
0
270
Signal-Based Data FetchingWith the New httpResource
manfredsteyer
PRO
0
170
State of Namespace
tagomoris
4
1.1k
5年間継続して開発した自作OSSの記録
bebeji_nappa
0
190
生成AIを使ったQAアプリケーションの作成 - ハンズオン補足資料
oracle4engineer
PRO
3
210
Amazon CloudWatchの地味だけど強力な機能紹介!
itotsum
0
130
Defying Front-End Inertia: Inertia.js on Rails
skryukov
0
470
リアルタイムレイトレーシング + ニューラルレンダリング簡単紹介 / Real-Time Ray Tracing & Neural Rendering: A Quick Introduction (2025)
shocker_0x15
1
300
大LLM時代にこの先生きのこるには-ITエンジニア編
fumiyakume
6
2.5k
Featured
See All Featured
A Tale of Four Properties
chriscoyier
158
23k
Building a Scalable Design System with Sketch
lauravandoore
462
33k
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
30
2k
XXLCSS - How to scale CSS and keep your sanity
sugarenia
248
1.3M
Documentation Writing (for coders)
carmenintech
69
4.7k
Thoughts on Productivity
jonyablonski
69
4.6k
How GitHub (no longer) Works
holman
314
140k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
233
17k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
30
2.3k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
194
16k
The Language of Interfaces
destraynor
157
24k
Measuring & Analyzing Core Web Vitals
bluesmoon
7
390
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