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
120
大規模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
110
コンテナ開発入門 1回目/Introduction to Container Development 1
bath_poo_
0
170
ISUCONってなんだ / What is ISUCON
bath_poo_
0
360
Web技術の基本 8回目 / Introduction to Web technologies 8th class
bath_poo_
0
190
Web技術の基本 7回目 / Introduction to Web technologies 7th class
bath_poo_
0
160
Web技術の基本 6回目 / Introduction to Web technologies 6th class
bath_poo_
1
260
Web技術の基本 5回目 / Introduction to Web technologies 5th class
bath_poo_
0
140
Web技術の基本 4回目 / Introduction to Web technologies 4th class
bath_poo_
0
220
Web技術の基本 3回目 / Introduction to Web technologies 3rd class
bath_poo_
0
250
Other Decks in Technology
See All in Technology
IoTLT@ストラタシスジャパン_20251021
norioikedo
0
140
NLPコロキウム20251022_超効率化への挑戦: LLM 1bit量子化のロードマップ
yumaichikawa
3
540
ヘンリー会社紹介資料(エンジニア向け) / company deck for engineer
henryofficial
0
400
東京大学「Agile-X」のFPGA AIデザインハッカソンを制したソニーのAI最適化
sony
0
140
【SORACOM UG Explorer 2025】さらなる10年へ ~ SORACOM MVC 発表
soracom
PRO
0
160
OSSで50の競合と戦うためにやったこと
yamadashy
3
1k
AWS DMS で SQL Server を移行してみた/aws-dms-sql-server-migration
emiki
0
250
Zero Trust DNS でより安全なインターネット アクセス
murachiakira
0
110
Azure Well-Architected Framework入門
tomokusaba
1
140
Amazon Athena で JSON・Parquet・Iceberg のデータを検索し、性能を比較してみた
shigeruoda
1
150
webpack依存からの脱却!快適フロントエンド開発をViteで実現する #vuefes
bengo4com
4
3.6k
AI時代の開発を加速する組織づくり - ブログでは書けなかったリアル
hiro8ma
2
330
Featured
See All Featured
How to train your dragon (web standard)
notwaldorf
97
6.3k
Designing for humans not robots
tammielis
254
26k
How STYLIGHT went responsive
nonsquared
100
5.9k
A Modern Web Designer's Workflow
chriscoyier
697
190k
Building Adaptive Systems
keathley
44
2.8k
The Art of Programming - Codeland 2020
erikaheidi
56
14k
How to Think Like a Performance Engineer
csswizardry
27
2.1k
GitHub's CSS Performance
jonrohan
1032
470k
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
16
1.7k
Facilitating Awesome Meetings
lara
57
6.6k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
333
22k
Being A Developer After 40
akosma
91
590k
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