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
39
Metadata Management in Distributed File Systems
kuenishi
2
520
Behind The Scenes: Cloud Native Storage System for AI
kuenishi
2
410
Apache Ozone behind Simulation and AI Industries
kuenishi
0
380
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.2k
Introducing Retz and how to develop practical frameworks
kuenishi
3
740
Formalization and Proof of Distributed Systems (ja)
kuenishi
10
6.4k
Other Decks in Technology
See All in Technology
努力家なスクラムマスターが陥る「傍観者」という罠と乗り越えた先に信頼があった話 / 20250830 Takahiro Sasaki
shift_evolve
PRO
2
120
カミナシ社の『ID管理基盤』製品内製 - その意思決定背景と2年間の進化 #AWSUnicornDay / Kaminashi ID - The Big Whys
kaminashi
3
660
AI時代に非連続な成長を実現するエンジニアリング戦略
sansantech
PRO
3
850
実践アプリケーション設計 ③ドメイン駆動設計
recruitengineers
PRO
13
3.8k
ソフトウェア エンジニアとしての 姿勢と心構え
recruitengineers
PRO
24
12k
ZOZOマッチのアーキテクチャと技術構成
zozotech
PRO
2
540
攻撃と防御で実践するプロダクトセキュリティ演習~導入パート~
recruitengineers
PRO
3
1.6k
AI時代にPdMとPMMはどう連携すべきか / PdM–PMM-collaboration-in-AI-era
rakus_dev
0
200
LLM翻訳ツールの開発と海外のお客様対応等への社内導入事例
gree_tech
PRO
0
380
Kubernetes における cgroup v2 でのOut-Of-Memory 問題の解決
pfn
PRO
0
420
そのコンポーネント、サーバー?クライアント?App Router開発のモヤモヤを可視化する補助輪
makotot
4
770
オブザーバビリティが広げる AIOps の世界 / The World of AIOps Expanded by Observability
aoto
PRO
0
120
Featured
See All Featured
Typedesign – Prime Four
hannesfritz
42
2.8k
[RailsConf 2023] Rails as a piece of cake
palkan
56
5.8k
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
48
9.7k
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
15
1.6k
The Straight Up "How To Draw Better" Workshop
denniskardys
236
140k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
50k
Navigating Team Friction
lara
189
15k
Designing for Performance
lara
610
69k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
53
2.9k
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
51
5.6k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
36
2.5k
How to train your dragon (web standard)
notwaldorf
96
6.2k
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?