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
CRDT 101
Search
Sergey Arkhipov
December 09, 2014
Programming
0
220
CRDT 101
Sergey Arkhipov
December 09, 2014
Tweet
Share
More Decks by Sergey Arkhipov
See All by Sergey Arkhipov
Fingerprinting
9seconds
0
160
Concurrency Models
9seconds
0
210
Probablistic Data Structures
9seconds
0
240
Own Mustache
9seconds
0
320
Daemonize
9seconds
0
320
Stuff That Works
9seconds
0
330
Evidence
9seconds
0
90
Redneck Monads
9seconds
1
96
Latency
9seconds
0
120
Other Decks in Programming
See All in Programming
Android端末で実現するオンデバイスLLM 2025
masayukisuda
1
140
🔨 小さなビルドシステムを作る
momeemt
4
670
Swift Updates - Learn Languages 2025
koher
2
470
奥深くて厄介な「改行」と仲良くなる20分
oguemon
1
520
詳解!defer panic recover のしくみ / Understanding defer, panic, and recover
convto
0
230
OSS開発者という働き方
andpad
5
1.7k
print("Hello, World")
eddie
2
530
複雑なドメインに挑む.pdf
yukisakai1225
5
1.1k
プロポーザル駆動学習 / Proposal-Driven Learning
mackey0225
2
1.2k
私の後悔をAWS DMSで解決した話
hiramax
4
210
@Environment(\.keyPath)那么好我不允许你们不知道! / atEnvironment keyPath is so good and you should know it!
lovee
0
110
Introducing ReActionView: A new ActionView-compatible ERB Engine @ Rails World 2025, Amsterdam
marcoroth
0
670
Featured
See All Featured
Balancing Empowerment & Direction
lara
3
620
The World Runs on Bad Software
bkeepers
PRO
70
11k
Java REST API Framework Comparison - PWX 2021
mraible
33
8.8k
Build your cross-platform service in a week with App Engine
jlugia
231
18k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
34
3.1k
We Have a Design System, Now What?
morganepeng
53
7.8k
Testing 201, or: Great Expectations
jmmastey
45
7.7k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
507
140k
The Success of Rails: Ensuring Growth for the Next 100 Years
eileencodes
46
7.6k
Why Our Code Smells
bkeepers
PRO
339
57k
VelocityConf: Rendering Performance Case Studies
addyosmani
332
24k
Performance Is Good for Brains [We Love Speed 2024]
tammyeverts
12
1.1k
Transcript
CRDT 101 Архипов Сергей @9seconds 10.12.2014
Наши проблемы ← CRDT ― Network ― RAM ― Persistent
storage ― CPU
90е ← CRDT Web Server Application Database
90е ← CRDT Web Server Application Database
2000: Load Balancing ← CRDT
2000: Load Balancing ← CRDT
2002: Replication ← CRDT
2004: Caching ← CRDT
2004: Caching ← CRDT
2006: Web 2.0 + Amazon = Sharding ← CRDT
2008: NoSQL ← CRDT
2010: MapReduce ← CRDT
2000: CAP ← CRDT ― Consistency ― Availability ― Partition
Tolerance
2009: CRDT ← CRDT
2009: CRDT ← CRDT
2009: CRDT ← CRDT
2009: CRDT ← CRDT
2009: CRDT ← CRDT
2009: CRDT ← CRDT
2009: CRDT ← CRDT CmRDT — Commutative Replicated Data Type
Assuming causal delivery of updates and method termination, any op-based object that satisfies the commutativity property for all concurrent updates, and whose delivery precondition is satisfied by causal delivery, is strong eventual consistent.
LWW-element-Set ← CRDT
LWW-element-Set ← CRDT tweet = { id: "3b6730f1-50c7-4fad-ac47-ba8c2efadfc1", timestamp: 1416757099,
user: "9seconds" message: "Test message" } def tweet_to_lww(tweet): return tweet["timestamp"], tweet
LWW-element-Set ← CRDT A R A R
LWW-element-Set ← CRDT A R A R (t1, a)
LWW-element-Set ← CRDT A R A R (t1, a) (t1,
a)
LWW-element-Set ← CRDT A R A R (t2, b) (t1,
a) (t1, a)
LWW-element-Set ← CRDT A R A R (t1, a) (t1,
a) (t2, b)
LWW-element-Set ← CRDT A R A R (t3, c) (t1,
a) (t1, a) (t2, b)
LWW-element-Set ← CRDT A R A R (t1, a) (t1,
a) (t2, b) (t3, c) (t2, b) (t2, b) (t4, c)
LWW-element-Set ← CRDT A R A R (t1, a) (t1,
a) (t2, b) (t3, c) (t2, b) (t2, b) (t4, c) (t4, c)
LWW-element-Set ← CRDT A R A R (t1, a) (t1,
a) (t2, b) (t3, c) (t2, b) (t2, b) (t4, c) (t4, c) Synchronizer (SoundCloud Roshi)
LWW-element-Set ← CRDT A R (t1, a) (t1, a) (t3,
c) (t2, b) (t2, b) (t4, c) (t4, c)
LWW-element-Set ← CRDT A R (t1, a) (t3, c) (t2,
b) (t4, c)
LWW-element-Set ← CRDT (t1, a) (t2, b)
LWW-element-Set ← CRDT A R A R (t1, a) (t1,
a) (t2, b) (t3, c) (t2, b) (t4, c) (t4, c) Synchronizer (SoundCloud Roshi) (t3, c)
Many CRDTs! ← CRDT ― Op-based Counter ― G-Counter ―
State-based PN Counter ― LWW-Register ― MV-Register ― G-Set ― 2P-Set ― LWW-element-Set ― PN-Set ― OR Set ― Add-only monotonic DAG ― Add-Remove Partial Order data type ― RGA ― RHA ― TreeDoc ― Logoot ― WOOT ― WOOTH
(Not) Many implementations ← CRDT ― Apache Cassandra ― Apache
HBase ― Basho Riak ― SoundCloud Roshi ― Akka CRDT
Q/A ← CRDT @9seconds https://speakerdeck.com/9seconds/crdt-101