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.8k
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
Storage Systems in Preferred Networks
kuenishi
0
27
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
370
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
730
Formalization and Proof of Distributed Systems (ja)
kuenishi
10
6.4k
Other Decks in Technology
See All in Technology
(非公式) AWS Summit Japan と 海浜幕張 の歩き方 2025年版
coosuke
PRO
1
320
Amazon Q Developer for GitHubとAmplify Hosting でサクッとデジタル名刺を作ってみた
kmiya84377
0
3.5k
米国国防総省のDevSecOpsライフサイクルをAWSのセキュリティサービスとOSSで実現
syoshie
2
630
讓測試不再 BB! 從 BDD 到 CI/CD, 不靠人力也能 MVP
line_developers_tw
PRO
0
1k
從四件事帶你見識見識 事件驅動架構設計 (EDA)
line_developers_tw
PRO
0
920
[TechNight #90-1] 本当に使える?ZDMの新機能を実践検証してみた
oracle4engineer
PRO
3
110
ローカルLLMでファインチューニング
knishioka
0
110
ハノーバーメッセ2025座談会.pdf
iotcomjpadmin
0
140
A2Aのクライアントを自作する
rynsuke
1
110
監視のこれまでとこれから/sakura monitoring seminar 2025
fujiwara3
10
2.6k
IIWレポートからみるID業界で話題のMCP
fujie
0
620
Azure AI Foundryでマルチエージェントワークフロー
seosoft
0
130
Featured
See All Featured
Product Roadmaps are Hard
iamctodd
PRO
53
11k
Keith and Marios Guide to Fast Websites
keithpitt
411
22k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
31
2.4k
Fantastic passwords and where to find them - at NoRuKo
philnash
51
3.3k
The World Runs on Bad Software
bkeepers
PRO
68
11k
Connecting the Dots Between Site Speed, User Experience & Your Business [WebExpo 2025]
tammyeverts
4
190
Being A Developer After 40
akosma
90
590k
Rails Girls Zürich Keynote
gr2m
94
14k
4 Signs Your Business is Dying
shpigford
184
22k
Site-Speed That Sticks
csswizardry
10
640
Measuring & Analyzing Core Web Vitals
bluesmoon
7
480
Understanding Cognitive Biases in Performance Measurement
bluesmoon
29
1.8k
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