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
600
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
133
6.3k
Elixir and Ecto
vanstee
5
730
Bootstrap
vanstee
8
670
HTTP API Design for iOS Applications
vanstee
11
500
Consensus: An Introduction to Raft
vanstee
22
2.6k
Pour Over Brewing Method
vanstee
1
250
Celluloid & DCell
vanstee
4
410
Map Reduce & Ruby
vanstee
10
620
Other Decks in Programming
See All in Programming
#phpcon_odawara オープン・クローズドなテストフィクスチャを求めて / open closed test fixtures
77web
3
240
R言語の環境構築と基礎 Tokyo.R 112
bob3bob3
0
280
MicrosoftのPlatform Engineeringガイドを読んで実際になにかやってみた
ymd65536
1
500
PHP8.3の機能を振り返る / Review of PHP 8.3 features
seike460
PRO
1
120
StoreKit2によるiOSのアプリ内課金のリニューアル
kangnux
0
120
Micro Frontends for Java Microservices - Utah JUG 2024
mraible
PRO
1
110
Build Apps for iOS, Android & Desktop in 100% Kotlin With Compose Multiplatform (mDevCamp 2024)
zsmb
0
420
Git Lint
bkuhlmann
4
760
冗長なエラーログを削減し、スタックトレースを手に入れる / Reducing Verbose Error Logs and Obtaining Stack Traces
upamune
0
980
PHPはいつから死んでいるかの調査
chiroruxx
2
410
効率化に挑戦してみたらモバイル開発が少し快適になった話
ryunakayama
0
140
0→1と1→10の狭間で Javaという技術選定を振り返る/Reflecting on the Decision to Choose Java Between Scaling from 0 to 1 and 1 to 10
jaguar_imo
2
400
Featured
See All Featured
Documentation Writing (for coders)
carmenintech
61
4k
Building a Scalable Design System with Sketch
lauravandoore
457
32k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
126
32k
Making the Leap to Tech Lead
cromwellryan
125
8.5k
The MySQL Ecosystem @ GitHub 2015
samlambert
244
12k
Automating Front-end Workflow
addyosmani
1357
200k
Infographics Made Easy
chrislema
238
18k
Ruby is Unlike a Banana
tanoku
96
10k
Code Reviewing Like a Champion
maltzj
515
39k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
7
1.3k
Optimizing for Happiness
mojombo
370
69k
Done Done
chrislema
178
15k
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