Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
Notes on Eventual Consistency
Search
Sponsored
·
Ship Features Fearlessly
Turn features on and off without deploys. Used by thousands of Ruby developers.
→
UENISHI Kota
December 11, 2014
Technology
4.2k
5
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
Notes on Eventual Consistency
結果整合性などの復習
UENISHI Kota
December 11, 2014
Transcript
32 slides
݁Ռ߹ੑͳͲͷ෮श 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?
More Decks by UENISHI Kota
See All by UENISHI Kota
Storage Systems in Preferred Networks
kuenishi
0
120
Metadata Management in Distributed File Systems
kuenishi
2
590
Behind The Scenes: Cloud Native Storage System for AI
kuenishi
2
490
Apache Ozone behind Simulation and AI Industries
kuenishi
0
520
Distributed Deep Learning with Chainer and Hadoop
kuenishi
3
1.4k
A Few Ways to Accelerate Deep Learning
kuenishi
0
1.3k
Introducing Retz
kuenishi
5
1.3k
Introducing Retz and how to develop practical frameworks
kuenishi
3
870
Formalization and Proof of Distributed Systems (ja)
kuenishi
10
6.6k
Other Decks in Technology
See All in Technology
契約書SaaSにAIエージェントを組み込む
sansantech
PRO
0
180
AIネイティブ組織の作り方。1人のPOとAIから始める、自社での実験
ama_ch
2
1.2k
人間+AIを「チーム」としてプロセスを再設計する
littlehands
4
3.4k
田んぼの見回りをIoTで減らしたい!水位監視から電池駆動カメラまでの試行錯誤
itosoft
1
270
マネージャーをエスパーにしない マネジメントされる側から始める、働きやすい現場づくり
comi190327
1
760
Datadog の権限統制 〜Org 統合に向けて調べた注意点 / JDDUG-Meetup_24
visional_engineering_and_design
1
180
【Oracle AI SPOTLIGHT ウェビナー】【特別開催:日本語で解説!】Oracle AI World 2026 最新情報フィードバック
oracle4engineer
PRO
1
280
属人化したISMS運用をGitHubとAIで仕組み化した1年間の記録
sioncojp
4
2.8k
PHPで家庭用ゲーム機の専用コントローラーをMIDIデバイスとして扱ってみる
wind111
0
140
re:Inventを楽しむために、 1日1つ「これが楽しみ」を決めよう
beli68
0
110
AI時代における医療情報システムのセキュリティ / Security of Healthcare IT Systems in the AI Era
henryofficial
0
190
アラートを見直していたら営業組織への理解にちょっとだけ繋がった話
z63d
1
210
Featured
See All Featured
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
25
2.2k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
141
35k
Lightning talk: Run Django tests with GitHub Actions
sabderemane
0
320
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
PRO
203
77k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
254
23k
My Coaching Mixtape
mlcsv
0
390
B2B Lead Gen: Tactics, Traps & Triumph
marketingsoph
1
300
The AI Search Optimization Roadmap by Aleyda Solis
aleyda
2
6.4k
Chrome DevTools: State of the Union 2024 - Debugging React & Beyond
addyosmani
10
1.4k
KATA
mclloyd
PRO
35
16k
Pawsitive SEO: Lessons from My Dog (and Many Mistakes) on Thriving as a Consultant in the Age of AI
davidcarrasco
1
300
What's in a price? How to price your products and services
michaelherold
247
13k