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
Notes on Eventual Consistency
Search
UENISHI Kota
December 11, 2014
Technology
5
4.2k
Notes on Eventual Consistency
結果整合性などの復習
UENISHI Kota
December 11, 2014
Tweet
Share
More Decks by UENISHI Kota
See All by UENISHI Kota
Storage Systems in Preferred Networks
kuenishi
0
22
Metadata Management in Distributed File Systems
kuenishi
2
500
Behind The Scenes: Cloud Native Storage System for AI
kuenishi
2
390
Apache Ozone behind Simulation and AI Industries
kuenishi
0
360
Distributed Deep Learning with Chainer and Hadoop
kuenishi
3
1.2k
A Few Ways to Accelerate Deep Learning
kuenishi
0
1.1k
Introducing Retz
kuenishi
5
1.1k
Introducing Retz and how to develop practical frameworks
kuenishi
3
720
Formalization and Proof of Distributed Systems (ja)
kuenishi
10
6.4k
Other Decks in Technology
See All in Technology
名刺メーカーDevグループ 紹介資料
sansan33
PRO
0
740
コードの考古学 〜労務システムから発掘した成長の糧〜
kenta_smarthr
1
1.2k
SmartHRの複数のチームにおけるMCPサーバーの活用事例と課題
yukisnow1823
2
1.2k
MCP で繋ぐ Figma とデザインシステム〜LLM を使った UI 実装のリアル〜
kimuson
2
1.3k
Java 30周年記念! Javaの30年をふりかえる
skrb
1
980
2025advance01
minamizaki
0
130
Redmineの意外と知らない便利機能 (Redmine 6.0対応版)
vividtone
0
1.2k
エンジニアが組織に馴染むために勉強会を主催してチームの壁を越える
ohmori_yusuke
2
120
All About Sansan – for New Global Engineers
sansan33
PRO
1
1.2k
Introduction to Sansan, inc / Sansan Global Development Center, Inc.
sansan33
PRO
0
2.6k
やさしいClaude Code入門
minorun365
PRO
32
25k
Cursor Meetup Tokyo
iamshunta
2
680
Featured
See All Featured
The Psychology of Web Performance [Beyond Tellerrand 2023]
tammyeverts
47
2.8k
Adopting Sorbet at Scale
ufuk
76
9.4k
Code Reviewing Like a Champion
maltzj
523
40k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
507
140k
The Pragmatic Product Professional
lauravandoore
35
6.7k
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
PRO
180
53k
The Art of Programming - Codeland 2020
erikaheidi
54
13k
Imperfection Machines: The Place of Print at Facebook
scottboms
267
13k
How to Think Like a Performance Engineer
csswizardry
23
1.6k
Why You Should Never Use an ORM
jnunemaker
PRO
56
9.4k
YesSQL, Process and Tooling at Scale
rocio
172
14k
Rails Girls Zürich Keynote
gr2m
94
13k
Transcript
݁Ռ߹ੑͳͲͷ෮श 2014/12/11 Ϗοάσʔλج൫ษڧձ @NTTଂ௨ݚ Bashoδϟύϯɹ্
ࣗݾհ • @kuenishi • Github, Twitter, etc • ࢄγεςϜྺ6 •
Bashoδϟύϯͷํ͔Βདྷ·ͨ͠ • Riak CSͷ։ൃ • ͦͷଞຊͷ͜ͱ • msgpack-erlang ϝϯςφ
BashoͱRiak •ࢄσʔλϕʔεʁ •RiakΛ͍ͬͯΔʁ •BashoΛ͍ͬͯΔʁ
͋Β͢͡ •݁Ռ߹ੑڧ߹ੑͷྼԽ൛Ͱͳ͘ɺ ผछͷΛղͨ͘ΊͷҟͳΔఆٛ •ผछͷ is Մ༻ੑ •ηϚϯςΟΫε͕ҟͳΔͷͰΞϓϦͷઃܭ ͷํ͕ͪΐͬͱมΘΔ
݁Ռ߹ੑ͏ݹ͍ʁ •2006ͷٕज़Ͱ͠ΐ •Ϗοάσʔλؔͳ͘Ͷʁ •DynamoDBڧ߹ੑΛఏڙ͍ͯ͠Δ •ωοτϫʔΫΕͳ͍Ͱ͠ΐʁ •ͦΜͳͷͬͯΔਓ͍Δͷʁ •ΞϓϦ͕࡞Γʹ͍͘…
Ϗοάσʔλج൫ݚڀձͱ ݁Ռ߹ੑ •ϏοάσʔλΛѻ͏େنͳγεςϜʹͳ ΕͳΔ΄ͲյΕΔ෦ଟ͍ •͕͔͔͍ۚͬͯΔͷͰɺٻΊΒΕΔՄ༻ੑ ߴ͍ •ӡ༻ָ͕
None
݁Ռ߹ੑͷ࣮༻ྫʢۙʣ •σʔλϕʔεͷόοΫΞοϓ •rsyncͰͷϑΝΠϧͷόοΫΞοϓ •Google Wave aaaa bbbb y x
CAP Theorem • Consistent: ෳͷAtomic Objectʹର͢Δ ࿈ଓͨ͠ૢ࡞ (w1, w3, w4,
….) ͕શͯಉҰ Ͱ͋Δ͜ͱ (linearizable) • Available: Atomic Objectʹૢ࡞ w1, w2, …Λ࣮ߦͯ͠Ϩεϙϯε͕ಘΒΕΔ͜ͱ • Partition Tolerant: ૹͬͨϝοηʔδ͕ ࣦͯ͠ਖ਼͍͠ʢatomicʣͳϨεϙϯε͕ ಘΒΕΔ͜ͱ G1 G2 write read Gilbert and Lynch, Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services
CAPఆཧ͕ఆٛ͢Δ߹ੑ •CAPఆཧ͕ఆٛ͢Δ߹ੑ㲈Linearizability •શͯͷෳͰɺશͯͷʢߋ৽ʣૢ࡞͕ॱ൪௨Γ ϦϓϨΠ͞ΕΔ͜ͱΛอো͢Δ •ACIDͷͦΕͱͪΐͬͱҧ͏
ͳͥڧ߹ੑͷ࣮ݱ͕͍͠ͷ͔ • ଟܾͱ͔ atomic broadcast Λ͏ͱͯ͠ύ ϑΥʔϚϯεͷϖφϧςΟ͕͋Δ • asynchrony +
partial failureͷ͠͞ • ࢮ׆ࢹ is hard => Downtime • ӡ༻ੑ • Γସ͑ɺΓ͠ɺ༳Ε·͢༳Ε·͢
Consistency͍͠ •ߋ৽ΛࢭΊΔʢAvailabilityΛԼ͛Δʣ͔ɺߋ৽ͷ্ॻ͖Λ ڐ͢ʢσʔλΛࣦ͏ʣ͔͔͠બࢶ͕ͳ͍ Server2 Server1 Server3 PUT V=42 PUT V=0
V=?
Atomic Broadcasting is Difficult • ϨϓϦέʔγϣϯॱ൪͕ೖΕସΘΔ • CPUͷΞτΦϒΦʔμʔ࣮ߦͱಉ͡ w1 w1
w1 w2 w2 w2 Actor 0 Actor 1 Actor 2 w2 w2 w1
Consensus Based Replication • ϨϓϦέʔγϣϯͷϦʔμʔΛଟܾͰબग़ • or ϨϓϦέʔγϣϯຖʹଟܾ w1 w1
w1 w2 w2 w2 Actor 0 Actor 1 Actor 2 w2 w2 w1
݁Ռ߹ੑ •Eventual Consistency •Ͳ͏͍͏ܦ࿏ΛḷΔʹͤΑɺෳ͕ ࠷ऴతʹಉ͡ঢ়ଶʹऩଋ͢Δ͜ͱ •Read Repair •AAE •CRDT v0
v1 •(Vector Clocks)
Siblings •ͱΓ͋͑ͣෳͷόʔδϣϯͷڞଘΛڐ͢ •Ͳͷόʔδϣϯ͕ਖ਼͍͔͠ɺ͘͠Ϛʔδ͢Δ͔ΛRead࣌ʹܾఆ Server2 Server1 Server3 PUT V=42 PUT V=0
V=0 or 42 V=0 V=0 or 42 V=42
APΛ࣮ݱ •ωοτϫʔΫஅ͕ى͖͍ͯͯͱΓ͋͑ͣॻ͖ࠐΈΛڐ͢ Server2 Server1 Server3 PUT V=42 PUT V=0 Server4
෮چͨ͠Βॻ͖͢ ྆ํ͓࣋ͬͯ͘
γϣοϐϯάΧʔτͷྫ •UnionΛͱΕΑ͍ Server2 Server1 Server3 PUT cart=[a,b,d] PUT cart=[a,b,c] union([a,b,c],
[a,b,d]) => [a,b,c,d] [a,b,c] [a,b,c] or [a,b,d] [a,b,d]
Read Repair v2 v2 get(“conferences/thoughtworks”) Get Handler (FSM) client Riak
Coordinating node Cluster 6 7 8 9 10 11 12 13 14 15 16 R=2 v1 v2 v2 v1 v2 v1 v1 v2 v2
Active Anti Entropy • APࢦͷDBͷσʔλྼԽΛ͙ ͨΊͷόοΫάϥϯυॲཧ • Merkle-TreeΛͬͯύʔςΟγϣ ϯຖͷʮνΣοΫαϜʯΛܭࢉ •
ࠩΛݟ͚ͭͨΒͦ͜ΛRead Repair͢Δ hash(vnode=0, pid=0) hash(vnode=1, pid=0) hash(vnode=2, pid=0)
CRDT • ॱ൪͕ೖΕସΘͬͯ݁Ռ͕มΘΒͳ͍ܕ • update(w1, update(w2, Data0) = update(w2, update(w1,
Data0) = Data w1 w1 w1 w2 w2 w2 Actor 0 Actor 1 Actor 2 w1(w2(Data0)) => Data w1(w2(Data0)) => Data w2(w1(Data0)) => Data
CRDT: PN-Counter • merge • {a: {1,-1}, b: {1,0}, c:
{2,0}} • {a: {0,0}, b: {2, 0}, c: {0, -2}} • => {a: {1,-1}, b:{2,0}, c:{2,-2}} => 2 • update • a͕ {increment, 3} Λड͚͚Δͱ • {a: {4,-1}, b: {1,0}, c: {2,0}}
CRDT: OR-Sets • merge • {a:{“foo”:true}, b:{“bar”:false}} • + {a:{“foo”:true},
b:{“foo”:false, “bar”:false}} • => {a:{“foo”:true}, b:{“foo”:false, “bar”:true}} • => [“bar”] • update • add: {a:{}} => +”foo” => {a:{“foo”:false}} • remove: {a: {“foo”:false}} => {a: {“foo”:true}}
ӡ༻ָ͕ • ΧδϡΞϧʹϊʔυωοτϫʔΫΛ্͛Լ͛Ͱ͖Δ • ߹ੑΛอͭͨΊͷϚελʔ͕୭͔Λؾʹ͢Δඞཁ͕ͳ͍ • ڧ߹ੑΛอͭͨΊͷΦϖϨʔγϣϯ͕μϯλΠϜʹͳ Βͳ͍ • ߹ੑνΣοΫɺϦΧόϦɺόοΫΞοϓ
• ނো࣌ͷΦϖϨʔγϣϯ͕͔ͳΓ୯७
݁Ռ߹ੑΛ࠾༻ͨ͠ ߹ͷ՝ •;ͭ͏ͷϓϩάϥϛϯάͱҟͳΔηϚϯςΟ ΫεʹͳΔ •ΞϓϦέʔγϣϯʹ͜Ε·ͰͱҟͳΔલఏΛཁ ٻ͢Δ͜ͱʹͳΔ •CRDTͰҰ෦ղܾɺ͚ͩͲ…
Ԡ༻ྫ
League of Legends •MMORPGͷνϟοτՄ༻ੑͱϨε ϙϯελΠϜ໋͕ •10ms ͕ੜࢮΛ͚Δ (C) Riot Games
•Riak্Ͱಈ͘ “ߴՄ༻” Ϋϥυ ετϨʔδ •ΦϒδΣΫτͷϝλσʔλ݁Ռ ߹తσʔλߏ •: 5GBͷσʔλ͕Concurrentʹ Ξοϓϩʔυ͞Ε͖ͯͨΒʁ •:
͔ͦ͠Ε͕ผͷେͷ ΞοϓϩʔυͩͬͨΒʁ /foo.bar
σʔληϯλʔؒϨϓϦέʔγϣϯ •DCؒωοτϫʔΫଓੑ ଳҬ·ͰؚΊͯৗʹਖ਼͘͠ӡ ༻͢Δͷ͕͍͠ •CAPఆཧͷཁ͔Βɺಉظత ϨϓϦέʔγϣϯ͍͠ •Մ༻ੑΛอͭͨΊʹɺ݁Ռ ߹͢ΔσʔλϞσϧΛ࠾༻
·ͱΊ •݁Ռ߹ੑڧ߹ੑͷྼԽ൛Ͱͳ͘ɺผछͷ Λղͨ͘ΊͷҟͳΔఆٛ •ผछͷ is Մ༻ੑ •ηϚϯςΟΫε͕ҟͳΔͷͰΞϓϦͷઃܭͷํ͕ ͪΐͬͱมΘΔ •݁Ռ߹ੑΛอͭͨΊͷ͍͔ͭ͘ͷٕज़Λհ
We are hiring. •࣮ੈքͷࢄγεςϜͷ ʹڵຯ͋Δਓʂ •@BashoJapan •
[email protected]
Questions?