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
220
Probablistic Data Structures
9seconds
0
240
Own Mustache
9seconds
0
330
Daemonize
9seconds
0
320
Stuff That Works
9seconds
0
330
Evidence
9seconds
0
92
Redneck Monads
9seconds
1
98
Latency
9seconds
0
120
Other Decks in Programming
See All in Programming
CSC305 Lecture 05
javiergs
PRO
0
210
高度なUI/UXこそHotwireで作ろう Kaigi on Rails 2025
naofumi
4
3.7k
Back to the Future: Let me tell you about the ACP protocol
terhechte
0
130
非同期jobをtransaction内で 呼ぶなよ!絶対に呼ぶなよ!
alstrocrack
0
570
Building, Deploying, and Monitoring Ruby Web Applications with Falcon (Kaigi on Rails 2025)
ioquatix
3
1.3k
CSC509 Lecture 01
javiergs
PRO
1
440
Swift Concurrency - 状態監視の罠
objectiveaudio
2
490
Model Pollution
hschwentner
1
190
The Past, Present, and Future of Enterprise Java
ivargrimstad
0
120
(Extension DC 2025) Actor境界を越える技術
teamhimeh
1
240
uniqueパッケージの内部実装を支えるweak pointerの話
magavel
0
940
XP, Testing and ninja testing ZOZ5
m_seki
3
400
Featured
See All Featured
A Tale of Four Properties
chriscoyier
160
23k
Building an army of robots
kneath
306
46k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
252
21k
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
114
20k
Measuring & Analyzing Core Web Vitals
bluesmoon
9
610
Connecting the Dots Between Site Speed, User Experience & Your Business [WebExpo 2025]
tammyeverts
9
580
The Invisible Side of Design
smashingmag
301
51k
Automating Front-end Workflow
addyosmani
1371
200k
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
9
970
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
26
3.1k
The MySQL Ecosystem @ GitHub 2015
samlambert
251
13k
Unsuck your backbone
ammeep
671
58k
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