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
大規模Webサービス入門 5回目 / Introduction to large scale ...
Search
muttan
August 11, 2017
Technology
0
97
大規模Webサービス入門 5回目 / Introduction to large scale web service 5
muttan
August 11, 2017
Tweet
Share
More Decks by muttan
See All by muttan
さわやか待ち時間LINE botを作った話 / Sawayaka LINE bot
bath_poo_
0
97
コンテナ開発入門 1回目/Introduction to Container Development 1
bath_poo_
0
130
ISUCONってなんだ / What is ISUCON
bath_poo_
0
310
Web技術の基本 8回目 / Introduction to Web technologies 8th class
bath_poo_
0
160
Web技術の基本 7回目 / Introduction to Web technologies 7th class
bath_poo_
0
140
Web技術の基本 6回目 / Introduction to Web technologies 6th class
bath_poo_
1
230
Web技術の基本 5回目 / Introduction to Web technologies 5th class
bath_poo_
0
110
Web技術の基本 4回目 / Introduction to Web technologies 4th class
bath_poo_
0
190
Web技術の基本 3回目 / Introduction to Web technologies 3rd class
bath_poo_
0
230
Other Decks in Technology
See All in Technology
学術機関におけるID連携とOpenID Connect
fujie
0
250
OCI で始める!! Red Hat OpenShift / Get Started OpenShift on OCI
oracle4engineer
PRO
1
180
開発生産性を始める前に開発チームができること / optim-improve-development-productivity.pdf
optim
0
110
技術的負債解消の取り組みと専門チームのお話
bengo4com
0
330
PdMはどのように全てのスピードを上げられるか ~ 非連続進化のための具体的な取り組み ~
sansantech
PRO
4
1.3k
リアルお遍路+SORACOM IoT
ozk009
1
140
「自動テストのプラクティスを効果的に学ぶためのカードゲーム」 ( #sqip2024 )
teyamagu
PRO
2
180
watsonx.ai Dojo 環境準備について
oniak3ibm
PRO
0
300
アプリをリリースできる状態に保ったまま 段階的にリファクタリングするための 戦略と戦術 / Strategies and tactics for incremental refactoring
yanzm
6
1.4k
たった1人からはじめる【Agile Community of Practice】~ソース原理とFearless Changeを添えて~
ktc_corporate_it
1
480
Envoy External AuthZとgRPC Extensionを利用した「頑張らない」Microservices認証認可基盤
andoshin11
0
250
再考 アクターモデル/ reconsider actor model
ytake
0
360
Featured
See All Featured
Reflections from 52 weeks, 52 projects
jeffersonlam
346
20k
Rebuilding a faster, lazier Slack
samanthasiow
78
8.6k
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
28
8.9k
XXLCSS - How to scale CSS and keep your sanity
sugarenia
246
1.3M
The World Runs on Bad Software
bkeepers
PRO
64
11k
A designer walks into a library…
pauljervisheath
201
24k
How to Think Like a Performance Engineer
csswizardry
16
960
RailsConf 2023
tenderlove
28
810
The Pragmatic Product Professional
lauravandoore
31
6.2k
Java REST API Framework Comparison - PWX 2021
mraible
PRO
27
7.4k
WebSockets: Embracing the real-time Web
robhawkes
59
7.3k
What the flash - Photography Introduction
edds
67
11k
Transcript
େنαʔϏεٕज़ೖ ୈ5ճ ISUCONରࡦษڧձ 2017/8/11
ୈ5ճ େنσʔλॲཧ[࣮ફ]ೖ - ΞϓϦέʔγϣϯ։ൃͷצॴ -
େنσʔλॲཧΞϓϦέʔγϣϯͷ ߟ͑ํͱରࡦ • ࠓ·Ͱ, େྔͷσʔλ͕͋ͬͯϋʔυΣ ΞͷߏΛݟ͢ʢہॴੑΛ׆͔͢ʣ͜ͱͰ ͳΜͱ͔ΓΖ͏ͱ͍͏ߟ͑. • Ͳ͏ͯ͠େྔͷσʔλʹΞΫηε͠ͳ͍ͱ ͍͚ͳ͍ͱ͖ͷରࡦΛߟ͑Δ.
େنσʔλॲཧΞϓϦέʔγϣϯͷ ߟ͑ํͱରࡦ • ຊͷ༰ • Lesson14 ༻్ಛԽܕΠϯσΫγϯά • Lesson15 ཧͱ࣮ફͷ྆ଆ͔Β߈ΊΔ
Lesson14 ༻్ಛԽܕΠϯσΫγϯά
ΠϯσοΫεͱγεςϜߏ • େنσʔλΛѻ͏ྫ • શจݕࡧ • ྨࣅจॻܥ୳ࡧ • σʔλϚΠχϯά
ΠϯσοΫεͱγεςϜߏ • ઌఔڍ͛ͨγεςϜͰRDBMSͰ͠ΜͲ͍ • ͳΒRDBMSΛΘͳ͚Ε͍͍͡Όͳ͍ • શ͘RDBMSΛΘͳ͍ͱ͍͏Ͱͳ͍
ΠϯσοΫεͱγεςϜߏ • σʔλRDBMSʹอଘ͓ͯ͘͠ • ͦͷσʔλΛఆظతʹநग़͠, ผ్ΠϯσοΫ εαʔόͷΑ͏ͳͷΛ࡞Δ • ͦ͜ʹWebΞϓϦ͔ΒRPCͳͲͰΞΫηε͢ Δํ๏Λ͏
ʲ෮शʳRDBMS • Relational DataBase Management System • ؔσʔλϕʔεΛӡ༻͢ΔͨΊͷιϑτΣ Ξͷू߹ମ •
MySQL, PostgreSQL, SQLite, etc…
ʲ෮शʳRPC • Remote Procedure Call • ωοτϫʔΫʹଓ͞Εͨଞͷίϯϐϡʔλ ্ͷϓϩάϥϜΛ࣮ߦ͢Δ • ͦͷ݁ՌΛडऔΔ
ΠϯσοΫεͱγεςϜߏ ΠϯσοΫε αʔό ᶃఆظతʹ σʔλΛநग़ cron job NPE@QFSM "1TFSWFS ᶄΠϯσοΫεΛ࡞Δ
ᶅRPCͰΞΫηε ᶆσʔλऔಘ
ΠϯσοΫεͱγεςϜߏ2 ΠϯσοΫε αʔό ᶃఆظతʹ σʔλΛநग़ cron job NPE@QFSM "1TFSWFS ᶄΠϯσοΫεΛ࡞Δ
ᶅRPCͰΞΫηε ᶇσʔλऔಘ httpd ᶆݕࡧͯ͠JSON Λฦ͢ΞϓϦ
ͳͥAPαʔόʹΠϯσοΫεΛ ࣋ͨͤͳ͍ͷ͔ • ઌ΄Ͳͷਤͷmod_perlͷ෦ • ेͳϝϞϦ͕ͳ͍ • ΞʔΩςΫνϟతʹେྔͷσʔλΛ୳͢Α͏ ͳͷʹ͍͍ͯͳ͍
ͳͥAPαʔόʹΠϯσοΫεΛ ࣋ͨͤͳ͍ͷ͔ • APαʔόશͯʹΠϯσοΫεΛͨͤΔͷ େมʢࠓޙ૿͑ΔՄೳੑ͕͋Δʣ • ΠϯσοΫεαʔόʹूͯ͠ཧ͢Δ
RPCͬͯͬͯΔʁ • ͔ͭͯRPCΛͬͯΠϯσοΫεαʔό͔Β ݁ՌΛऔಘ͍ͯͨ͠.ʢࠓ͋Δʣ • ࠓͰJSON+HTTP͕ओྲྀ • զʑೃછΈ͕ਂ͍
༻్ಛԽܕͷΠϯσΫγϯά • ࠓ·Ͱհͨ͠ߏʮ༻్ಛԽܕΠϯσΫ γϯάʯͱݺΕ͍ͯΔ • ͜ΕʹΑͬͯ, RDBMSͰ͔ͬͨ͜͠ͱ͕ ࣮ݱՄೳʹʂ
༻్ಛԽܕͷΠϯσΫγϯά • RDBMS൚༻తʹ͑ΔΑ͏༷ʑͳػೳ͕උ Θ͍ͬͯΔ • ౷ܭॲཧ, ݁߹, ιʔτ • ཉ͍͠ػೳ͚ͩʹಛԽʢνϡʔχϯάʣ͢Δ
ͨΊૣ͘ͳΔ
༻్ಛԽܕͷΠϯσΫγϯά • σʔλΛఆظతʹॻ͖ग़ͯ͠ΠϯσοΫεʢσʔλ ߏʣΛߏங͢Δ • ߏԽͨ͠σʔλΛอ࣋ͨ͠αʔόΛC++Ͱ࡞Γ, RPCͰΞΫηε͢ΔͳͲ • ThriftͬͯͷͰଟݴޠRPC͕Մೳʹ •
ௐͯΈΔͱݕࡧΤϯδϯܥͰΑ͋͘ΔߏͬΆ͍
ʲྫʳͯͳΩʔϫʔυʹΑΔϦϯΫ
ʲྫʳͯͳΩʔϫʔυʹΑΔϦϯΫ • ΩʔϫʔυϦϯΫΛੜ͢ΔॲཧΛߟ͑Δ Լઢ෦͕ϦϯΫ
ʲྫʳͯͳΩʔϫʔυʹΑΔϦϯΫ • Ωʔϫʔυͷ͕20ສϫʔυڧ͋Δ • ͜ΕΛ͍͍ͪͪൺֱ͍ͯ͘͠ͱաෛՙʹͳͬ ͯDBαʔό͕མͪͯ͠·͏ • Ͳ͏ͨ͠Β͍͍ͩΖ͏͔ʁ
ʲྫʳͯͳΩʔϫʔυʹΑΔϦϯΫ • લʹͬͨΑ͏ʹ, όονॲཧͰΩʔϫʔυΛ ͯ͢औΓग़͓ͯ͘͠ • ͔ͭͯڊେͳਖ਼نදݱΛ༻͍ͯνΣοΫ͠ ͍ͯͨ • OR݅ʹΑΓόοΫτϥοΫ͕ͨ͘͞Μൃ
ੜͯ͘͠ͳͬͨ
ʲྫʳͯͳΩʔϫʔυʹΑΔϦϯΫ • ݱࡏCommon Prefix Searchʢڞ௨಄ࣙݕࡧʣͱ TrieΛͬͯϚονϯά͍ͯ͠Δ • Common Prefix Searchʹ,
Aho-Corasick๏ʢΤΠ ϗʔίϥγοΫʣDouble Array TrieͳͲ • ࣗવݴޠॲཧാͩͱԦಓͳํ๏Β͍͠ • Aho-Corasickؤுͬͯௐ͍ͯͩ͘͞
Trieͱ • Ωʔू߹Λѻ͏ͨΊͷσʔλߏͷҰछ • ࠓճͷΑ͏ͳ୯ޠͷू߹ͱ͔ • ݕࡧαΠζ͕ͷେ͖͞Ͱͳ͘୯ޠͷ͞ ʹґଘ͢Δ • ऩ݅ʹґଘ͠ͳ͍
Trieͱ t e a n o i n n w
e keys: tea, ten, to, i, in, inn, we
ʲྫʳͯͳΩʔϫʔυʹΑΔϦϯΫ • հͨ͠Α͏ͳσʔλߏΛ༧Ίߏங͓ͯ͠ ͘͜ͱͰߴԽग़དྷΔ • 7ճͰৄ͘͠આ໌
ʲྫʳͯͳϒοΫϚʔΫͷ ςΩετྨث
ʲྫʳͯͳϒοΫϚʔΫͷ ςΩετྨث • ͯͳϒοΫϚʔΫͷΧςΰϦࣗಈྨ, Complement Naive Bayesͱ͍͏ΞϧΰϦζϜ ΛͬͯػցֶशΛߦ͍ྨ͍ͯ͠Δ. • ৄׂ͘͠Ѫ͢Δ͕,
ग़ݱසΛසൟʹٻΊΔ ͜ͱʹͳΔͷͰ, ͦΕ͚ͩΛฦ͢αʔό͕ଘࡏ ͍ͯ͠Δ
Lesson15 ཧͱ࣮ફͷ྆ํ͔ΒऔΓΉ
ٻΊΒΕΔٕज़తͳཁ݅ΛݟۃΊΔ • ཧ • ίϨΛ͜ͷ༷ʹ͢Δͱಈ͘Αͱ͍ͬͨΑ͏ͳ ࣝ • ࣮ફ • ࣮ࡍʹखΛಈ͔ͨ͠Γӡ༻্͍ͯ͘͠Ͱඞཁ
ʹͳͬͯ͘Δϊϋ
େنΞϓϦʹ͓͚Δཧͱ࣮ફ • ཧͱ࣮ફΛόϥϯεྑ͘Βͳ͍ͱμϝ • ͲͪΒ͔Ұํ͚ͩʹภ͍͚ͬͯͳ͍ • ཧ͚͍͍࣮ͩͬͯͯ͟ग़དྷΔ͔ͱ͍͏ͱ, ࣮ ͷͨΊͷόουϊϋ͕… •
࣮ફΛ͜ͳ͍ͯͯ͠, Θ͔Βͳ͍͜ͱʢࣝෆʣ Ͱͯ͘Δ
ܭࢉػͷͱͯ͠ಓےΛݟ͚ͭΔ • ઌͷΩʔϫʔυΛݟ͚ͭΔॲཧͰ, Double array Trieͱ͍͏͕ग़͖ͯͨ • ͜ͷΑ͏ͳΞϧΰϦζϜΛ͍ͬͯΔ͔Β ͳ͍͔Ͱେ͖͘มΘͬͯ͘Δ •
ʲ࠶ܝʳΞϧΰϦζϜେࣄ
2ճ͔Β5ճ·Ͱͷখ·ͱΊ
ୈ2ճʙୈ5ճͷখ·ͱΊ 1. ΪΨόΠτ୯Ґͷσʔλॲཧ ςϥ, ϖλόΠτͷσʔλΛѻ͏ʹͲ͏͢Δ͔. 2. ϝϞϦॏཁ ϝϞϦʹࡌΔͳΒϝϞϦʹ. Ωϟογϡ͕ฉ͖͍͢ߏʹ͢Δ. 3.
ࢄΛҙࣝͨ͠ӡ༻ దͳεΩʔϚͷઃఆ, ύʔςΟγϣχϯά, JOINΛආ͚Δ. 4. దͳΞϧΰϦζϜͱσʔλߏ Trie, Double Array Trie, Common Prefix Search