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
A New Concept of Consistency in Distributed Dat...
Search
UENISHI Kota
November 28, 2013
Technology
10
3.6k
A New Concept of Consistency in Distributed Database and Implementation in Riak
Web+DB forum 技術報告 by Basho
UENISHI Kota
November 28, 2013
Tweet
Share
More Decks by UENISHI Kota
See All by UENISHI Kota
Metadata Management in Distributed File Systems
kuenishi
2
450
Behind The Scenes: Cloud Native Storage System for AI
kuenishi
2
310
Apache Ozone behind Simulation and AI Industries
kuenishi
0
270
Distributed Deep Learning with Chainer and Hadoop
kuenishi
3
1.1k
A Few Ways to Accelerate Deep Learning
kuenishi
0
960
Introducing Retz
kuenishi
5
1k
Introducing Retz and how to develop practical frameworks
kuenishi
3
650
Formalization and Proof of Distributed Systems (ja)
kuenishi
10
6.2k
Mesos Frameworkの作り方 (How to Make Mesos Framework)
kuenishi
7
2.3k
Other Decks in Technology
See All in Technology
「認証認可」という体験をデザインする ~Nekko Cloud認証認可基盤計画
logica0419
2
440
たった1人からはじめる【Agile Community of Practice】~ソース原理とFearless Changeを添えて~
ktc_corporate_it
1
480
リアルお遍路+SORACOM IoT
ozk009
1
140
DroidKaigi 2024 たすけて!ViewModel
mhidaka
5
940
AIで変わるテスト自動化:最新ツールの多様なアプローチ/ 20240910 Takahiro Kaneyama
shift_evolve
0
230
なにもしてないのにNew Relicのデータ転送量が増えていたときに確認したこと
tk3fftk
2
230
o1のAPIで実験してみたが 制限きつすぎて辛かった話
pharma_x_tech
0
190
Mocking in Rust Applications
taiki45
1
410
AI活用したくてもできなかった不動産SaaSの今とこれから
nealle
0
330
とあるOSSを継続可能にするための取り組みについて / OSS Refactoring Process
bun913
1
210
開発者の定量・定性データを組み合わせて開発者体験を把握するための取り組み
ham0215
1
130
Technical Writing Meetup vol.35
soracom
PRO
2
120
Featured
See All Featured
[RailsConf 2023] Rails as a piece of cake
palkan
48
4.6k
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
0
120
KATA
mclloyd
27
13k
Keith and Marios Guide to Fast Websites
keithpitt
408
22k
jQuery: Nuts, Bolts and Bling
dougneiner
61
7.4k
A designer walks into a library…
pauljervisheath
201
24k
Embracing the Ebb and Flow
colly
83
4.4k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
26
2k
Happy Clients
brianwarren
96
6.6k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
190
16k
Mobile First: as difficult as doing things right
swwweet
221
8.8k
Building an army of robots
kneath
302
42k
Transcript
ࢄσʔλϕʔεʹ͓͚Δ ৽͍͠߹ੑϞσϧͱ Riakʹ͓͚Δ࣮ 2013 / 11 / 28 WebDB Forum
Basho ্߁ଠ
ࢄσʔλϕʔεʹ͓͚Δ ݹͯ͘৽͍͠߹ੑϞσϧͱ Riakʹ͓͚Δ࣮ 2013 / 11 / 28 WebDB Forum
Basho ্߁ଠ
BashoͱRiak •ࢄσʔλϕʔεʁ •RiakΛ͍ͬͯΔʁ •BashoΛ͍ͬͯΔʁ
CAPఆཧͱཧͷDB •ͲΜͳނোʹରͯ͠ (partition tolerance) •σʔλৗʹ߹͓ͯ͠Γ (consistency) •γεςϜ͕ࢭ·Δ͜ͱͳ͍ (availability) ͜ͷ3ͭΛಉ࣌ʹຬͨ͢γεςϜଘࡏ͠ͳ͍
•Մ༻ੑ (Availability) ͕ಛͷσʔλ ϕʔε •ӡ༻͍͢͠ɺେ͖ͳσʔλͰೖΔ •҆ఆੑɺ༧ଌՄೳੑ •ʮσʔλΛઈରʹͳ͘͞ͳ͍ʯ
͜Μͳͱ͜ΖͰ ಈ͍͍ͯ·͢Riak •Rovio (Angry Birds) •Yahoo!JAPAN ͷΫϥυετϨʔδ •NHS (ΠΪϦε ࠃຽอݥαʔϏε)
•Bump (=>Google) •ۜߦɺήʔϜɺখചɺηϯαʔɺetc…
How Riak Works
Consistent Hashing • 160-bit Ωʔۭؒ • ۭؒΛ͢Δ • ύʔςΟγϣϯϊʔ υ͕ݸผཧ
• ϨϓϦΧNݸͷύʔ ςΟγϣϯʹίϐʔ͞ ΕΔ OPEF OPEF OPEF OPEF hash(“meetups/spamham”) N=3
Consistency͍͠ •ߋ৽ΛࢭΊΔʢAvailabilityΛԼ͛Δʣ͔ɺߋ৽ͷ্ॻ͖Λ ڐ͢ʢσʔλΛࣦ͏ʣ͔͔͠બࢶ͕ͳ͍ Server2 Server1 Server3 PUT V=42 PUT V=0
V=?
ConsistencyͷΘΓʹ •ͱΓ͋͑ͣෳͷόʔδϣϯͷڞଘΛڐ͢ •Ͳͷόʔδϣϯ͕ਖ਼͍͔͠ɺ͘͠Ϛʔδ͢Δ͔Λ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]
ෳόʔδϣϯΛ ڐ͢͜ͱͷ •ϓϩάϥϛϯά͕͍͠ʢτϥϯβΫγϣϯૉ Β͍͠ʣ •ݱ࣮ੈքγϣοϐϯάΧʔτͱΧϯλʔ͚ͩ Ͱͳ͍ •҆શͳMerge, update͕Ͱ͖ΔσʔλߏΛຖճ ߟ͑ͳ͚ΕͳΒͳ͍ •͍ͬͯΔ͏ͪʹࣅͨΑ͏ͳϥΠϒϥϦ͕͋ͪ͜
ͪͰग़དྷ্͕Δ
ͳ͍ͥ͠ͷ͔ʁ •σʔλͷWriteͱWrite͕ೖΕସΘΓ͏ ΔʹSerializableͲ͜Ζ͔WriteҰ؏ ͨ͠ঢ়ଶʹͰ͖ͳ͍ Server2 Server1 Server3 w1 w2 w1
w2 w2 (w1 lost)
Logical Monoticity •σʔλʹର͢ΔՄͳૢ࡞ͷΈΛڐ͢ʂ Data = update(w2, update(w1, Data0)) = update(w1,
update(w2, Data0)) Data = merge(update(w2, Data0), Data)
͑: CRDT •ʮෳՄೳͳՄσʔλܕʯ •Conflict-Free Replicated Data Types •Commutative Replicated Data
Types •… •(Going to be included in Riak 2.0) ) CRDTͷ࡞ऀLogical Monotinicy ͱ͍͏ݴ༿͍ͬͯͳ͍
CRDT in Riak 2.0 •KVSͷVʹʮܕʯΛ࣋ͨͤͯɺܕʹΑͬͯ UpdateͱMergeͷϩδοΫΛܾΊΔ •Read࣌ʹMerge͕αʔόʔଆͰࣗಈతʹ࣮ ߦ͞ΕΔ •ΞϓϦέʔγϣϯܕΛࢦఆ͢Δ͚ͩͰΑ͘ɺ ෳόʔδϣϯͷϋϯυϦϯά͕ෆཁʹͳΔ
CRDT example •PN-Counter •Set •OR-sets •LWW-register •Graph…
PN-Counter •σϞ
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}}
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}}
OR-Sets •σϞ
Ϣʔεέʔε •ΫϦοΫͷΧϯτ (G-counter) • riak-server/types/counters/buckets/likes/datatypes/basho.com -d 1 •γϣοϐϯάΧʔτ (OR-sets) •ϩάΠϯϢʔβʔ
(PN-counter) •͜ΕΒͷΈ߹Θͤ (map & LWW-register, boolean) •{ name : “basho.com”, likes: 20000, users: 3000, links: [ “basho.co.jp”, “basho.co.uk” ], cool: true }
Ͱ͖ͳ͍͜ͱ •ʮ0Ҏ্ʯͷPN-counter •ϢχʔΫͳIDൃߦ •ͦͷଞCAS͕ඞཁͳσʔλߏͱૢ࡞
·ͱΊ •RiakՄ༻ੑͷ͋Δࢄσʔλϕʔε •ෳͷόʔδϣϯΛಉ࣌ʹอ࣋͢ΔͷΛ ڐ͢͜ͱͰՄ༻ੑΛ୲อ •ΞϓϦ։ൃͷқ͕՝ •CRDTͱ͍͏ܕͷಋೖʹΑΓ؆୯͔ͭ σʔλͷͳ͘ͳΒͳ͍ΈΛ࡞ͬͨ
Questions? •Riak 2.0 Λָ͠Έʹ͍ͯͩ͘͠͞ •Web: http://basho.co.jp •Twitter: @BashoJapan •Me:
[email protected]
•ML:
[email protected]
Useful links http://hal.upmc.fr/docs/00/55/55/88/PDF/techreport.pdf http://arxiv.org/pdf/1210.3368.pdf https://gist.github.com/russelldb/f92f44bdfb619e089a4d http://gsd.di.uminho.pt/members/cbm/ps/scadt3.pdf http://arxiv.org/abs/1011.5808