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
700
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.7k
Elixir and Ecto
vanstee
5
870
Bootstrap
vanstee
8
740
HTTP API Design for iOS Applications
vanstee
11
570
Consensus: An Introduction to Raft
vanstee
22
2.9k
Pour Over Brewing Method
vanstee
1
320
Celluloid & DCell
vanstee
4
500
Map Reduce & Ruby
vanstee
10
730
Other Decks in Programming
See All in Programming
なまけものオバケたち -PHP 8.4 に入った新機能の紹介-
tanakahisateru
1
140
Cloudflare MCP ServerでClaude Desktop からWeb APIを構築
kutakutat
1
630
Androidアプリのモジュール分割における:x:commonを考える
okuzawats
1
260
iOS開発におけるCopilot For XcodeとCode Completion / copilot for xcode
fuyan777
1
1.2k
ISUCON14感想戦で85万点まで頑張ってみた
ponyo877
1
190
見えないメモリを観測する: PHP 8.4 `pg_result_memory_size()` とSQL結果のメモリ管理
kentaroutakeda
0
890
CloudflareStack でRAGに入門
asahiiwm
0
140
선언형 UI에서의 상태관리
l2hyunwoo
0
250
開発者とQAの越境で自動テストが増える開発プロセスを実現する
92thunder
1
220
コンテナをたくさん詰め込んだシステムとランタイムの変化
makihiro
1
180
Go の GC の不得意な部分を克服したい
taiyow
3
970
CQRS+ES の力を使って効果を感じる / Feel the effects of using the power of CQRS+ES
seike460
PRO
0
230
Featured
See All Featured
Performance Is Good for Brains [We Love Speed 2024]
tammyeverts
7
550
The Art of Programming - Codeland 2020
erikaheidi
53
13k
How GitHub (no longer) Works
holman
312
140k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
49k
It's Worth the Effort
3n
183
28k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
356
29k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
507
140k
Producing Creativity
orderedlist
PRO
343
39k
Into the Great Unknown - MozCon
thekraken
34
1.6k
Product Roadmaps are Hard
iamctodd
PRO
50
11k
Site-Speed That Sticks
csswizardry
2
220
Fontdeck: Realign not Redesign
paulrobertlloyd
82
5.3k
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