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
750
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
7k
Elixir and Ecto
vanstee
5
930
Bootstrap
vanstee
8
780
HTTP API Design for iOS Applications
vanstee
11
630
Consensus: An Introduction to Raft
vanstee
22
2.9k
Pour Over Brewing Method
vanstee
1
340
Celluloid & DCell
vanstee
4
540
Map Reduce & Ruby
vanstee
10
790
Other Decks in Programming
See All in Programming
データの民主化を支える、透明性のあるデータ利活用への挑戦 2025-06-25 Database Engineering Meetup#7
y_ken
0
270
今ならAmazon ECSのサービス間通信をどう選ぶか / Selection of ECS Interservice Communication 2025
tkikuc
11
2.7k
関数型まつり2025登壇資料「関数プログラミングと再帰」
taisontsukada
2
840
Javaのルールをねじ曲げろ!禁断の操作とその代償から学ぶメタプログラミング入門 / A Guide to Metaprogramming: Lessons from Forbidden Techniques and Their Price
nrslib
3
2k
Haskell でアルゴリズムを抽象化する / 関数型言語で競技プログラミング
naoya
17
4.8k
Benchmark
sysong
0
220
Claude Codeの使い方
ttnyt8701
1
130
C++20 射影変換
faithandbrave
0
500
コードの90%をAIが書く世界で何が待っているのか / What awaits us in a world where 90% of the code is written by AI
rkaga
41
27k
2度もゼロから書き直して、やっとブラウザでぬるぬる動くAIに辿り着いた話
tomoino
0
160
GoのWebAssembly活用パターン紹介
syumai
3
10k
地方に住むエンジニアの残酷な現実とキャリア論
ichimichi
2
560
Featured
See All Featured
No one is an island. Learnings from fostering a developers community.
thoeni
21
3.3k
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
8
790
What's in a price? How to price your products and services
michaelherold
245
12k
Writing Fast Ruby
sferik
628
61k
Sharpening the Axe: The Primacy of Toolmaking
bcantrill
43
2.4k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
120k
Connecting the Dots Between Site Speed, User Experience & Your Business [WebExpo 2025]
tammyeverts
4
200
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
130
19k
Why You Should Never Use an ORM
jnunemaker
PRO
56
9.4k
A better future with KSS
kneath
239
17k
Build The Right Thing And Hit Your Dates
maggiecrowley
36
2.8k
Embracing the Ebb and Flow
colly
86
4.7k
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