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.8k
Elixir and Ecto
vanstee
5
900
Bootstrap
vanstee
8
770
HTTP API Design for iOS Applications
vanstee
11
600
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
760
Other Decks in Programming
See All in Programming
PHPUnit 高速化テクニック / PHPUnit Speedup Techniques
pinkumohikan
1
1.2k
CQRS+ES勉強会#1
rechellatek
0
390
新卒から4年間、20年もののWebサービスと 向き合って学んだソフトウェア考古学
oguri
7
6.5k
生産性アップのためのAI個人活用
kunoyasu
0
480
Gunma.web #55
tinykitten
0
130
コンテナでLambdaをデプロイするときに知っておきたかったこと
_takahash
0
140
データベースエンジニアの仕事を楽にする。PgAssistantの紹介
nnaka2992
9
4.1k
本当だってば!俺もTRICK 2022に入賞してたんだってば!
jinroq
0
230
アーキテクトと美学 / Architecture and Aesthetics
nrslib
12
2.9k
Compose Navigation実装の見通しを良くする
hiroaki404
0
180
Go1.24 go vetとtestsアナライザ
kuro_kurorrr
2
380
requirements with math
moony
0
520
Featured
See All Featured
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
28
9.4k
A better future with KSS
kneath
238
17k
Code Review Best Practice
trishagee
67
18k
A Modern Web Designer's Workflow
chriscoyier
693
190k
Become a Pro
speakerdeck
PRO
27
5.2k
Unsuck your backbone
ammeep
669
57k
BBQ
matthewcrist
88
9.5k
Bash Introduction
62gerente
611
210k
Writing Fast Ruby
sferik
628
61k
YesSQL, Process and Tooling at Scale
rocio
172
14k
It's Worth the Effort
3n
184
28k
GraphQLとの向き合い方2022年版
quramy
45
14k
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