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
210
CRDT 101
Sergey Arkhipov
December 09, 2014
Tweet
Share
More Decks by Sergey Arkhipov
See All by Sergey Arkhipov
Fingerprinting
9seconds
0
150
Concurrency Models
9seconds
0
200
Probablistic Data Structures
9seconds
0
240
Own Mustache
9seconds
0
320
Daemonize
9seconds
0
300
Stuff That Works
9seconds
0
320
Evidence
9seconds
0
86
Redneck Monads
9seconds
1
91
Latency
9seconds
0
110
Other Decks in Programming
See All in Programming
“いい感じ“な定量評価を求めて - Four Keysとアウトカムの間の探求 -
nealle
0
470
なぜ「共通化」を考え、失敗を繰り返すのか
rinchoku
1
620
AIエージェントはこう育てる - GitHub Copilot Agentとチームの共進化サイクル
koboriakira
0
480
PHPでWebSocketサーバーを実装しよう2025
kubotak
0
240
スタートアップの急成長を支えるプラットフォームエンジニアリングと組織戦略
sutochin26
0
300
エンジニア向け採用ピッチ資料
inusan
0
180
Kotlin エンジニアへ送る:Swift 案件に参加させられる日に備えて~似てるけど色々違う Swift の仕様 / from Kotlin to Swift
lovee
1
260
今ならAmazon ECSのサービス間通信をどう選ぶか / Selection of ECS Interservice Communication 2025
tkikuc
20
3.8k
#kanrk08 / 公開版 PicoRubyとマイコンでの自作トレーニング計測装置を用いたワークアウトの理想と現実
bash0c7
1
660
Team topologies and the microservice architecture: a synergistic relationship
cer
PRO
0
1.2k
第9回 情シス転職ミートアップ 株式会社IVRy(アイブリー)の紹介
ivry_presentationmaterials
1
260
新メンバーも今日から大活躍!SREが支えるスケールし続ける組織のオンボーディング
honmarkhunt
1
330
Featured
See All Featured
Being A Developer After 40
akosma
90
590k
GitHub's CSS Performance
jonrohan
1031
460k
A better future with KSS
kneath
239
17k
A Modern Web Designer's Workflow
chriscoyier
694
190k
Fireside Chat
paigeccino
37
3.5k
How To Stay Up To Date on Web Technology
chriscoyier
790
250k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
26
2.9k
GraphQLの誤解/rethinking-graphql
sonatard
71
11k
The Cult of Friendly URLs
andyhume
79
6.5k
Writing Fast Ruby
sferik
628
62k
How GitHub (no longer) Works
holman
314
140k
Scaling GitHub
holman
459
140k
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