大規模Webサービス入門 7回目 / Introduction to large scale web service 7

Transcript

1. େن໛αʔϏεٕज़ೖ໳ ୈ7ճ ISUCONରࡦษڧձ 2017/8/25
2. ୈ7ճ ΞϧΰϦζϜͷ࣮༻Խ - ਎ۙͳྫͰݟΔཧ࿦ɾݚڀͷ࣮ફ౤ೖ-
3. ΞϧΰϦζϜɾσʔλߏ଄ͷબ୒ • େن໛ͳ΢ΣϒαʔϏεʹ͓͍ͯ, ۪௚ʹσʔ λΛૢ࡞ɾ୳ࡧ͢Δͱܭࢉྔരൃ͕ى͜Δ.
4. ΞϧΰϦζϜɾσʔλߏ଄ͷબ୒ ʮϑΧγΪͷ਺͑ํʯ͓Ͷ͑͞Μͱ͍ͬ͠ΐʂΈΜͳͰ਺͑ͯΈΑ͏ʂ
 https://www.youtube.com/watch?v=Q4gTV4r0zRs
5. ΞϧΰϦζϜɾσʔλߏ଄ͷબ୒ • ద౰ͳΞϧΰϦζϜΛ༻͍Δ͜ͱͰ, େ෯ʹܭ ࢉྔΛݮΒ͢͜ͱ͕ग़དྷΔ.
7. ΞϧΰϦζϜɾσʔλߏ଄ͷબ୒ • ࠓճֶͿ͜ͱ ‣ ΞϧΰϦζϜͷॏཁ͞ - σʔλ͕େ͖͘ͳΕ͹ͳΔ΄ͲॏཁʹͳΔ ‣ ΞϧΰϦζϜબఆεςοϓ - Φʔμʔه๏ - ࣮ࡍʹ࢖ΘΕΔ·Ͱͷεςοϓ
8. Lesson 19 ΞϧΰϦζϜͱධՁ
9. σʔλͷن໛ͱܭࢉྔͷҧ͍ • σʔλ͕େ͖͘ͳΕ͹ͳΔ΄Ͳ, ΞϧΰϦζϜ ΍σʔλߏ଄ͷબ୒͕଎౓ͱͯ͠ݱΕΔ. αʔνํ๏ Φʔμʔ ઢܗ୳ࡧ ೋ෼୳ࡧ
10. σʔλͷن໛ͱܭࢉྔͷҧ͍ • n=1000ͷͱ͖ͷܭࢉྔͷҧ͍ αʔνํ๏ ܭࢉྔ ઢܗ୳ࡧ  ೋ෼୳ࡧ ͓Αͦ
11. σʔλͷن໛ͱܭࢉྔͷҧ͍ • n=1,000,000ͷͱ͖ αʔνํ๏ ܭࢉྔ ઢܗ୳ࡧ    ೋ෼୳ࡧ ͓Αͦ O(log2(n))͸σʔλͷ૿Ճʹڧ͍
12. σʔλͷن໛ͱܭࢉྔͷҧ͍ • σʔλྔ͕গͳ͍࣌͸, ઢܗ୳ࡧͰ΋ྑ͍. • ͔͠͠, ݱ࣮ͷେن໛ͳWebαʔϏεͰ͸, σʔ λྔ͕গͳ͍ͱ͍͏͜ͱ͸ߟ͑ʹ͍͘ • ઌఔͷΑ͏ʹ, σʔλ͕100ສ݅, 1000ສ݅ͱ૿Ճ ͍ͯ͘͠ͱ, σʔλͷ୳ࡧ͕ϘτϧωοΫͱͳͬͯ ͘Δ.ɹ→ ͳΔ΂͘ݮΒ͍ͨ͠
13. ΞϧΰϦζϜͱ͸ʁ • ͋Δ஋·ͨ͸஋ͷू߹Λೖྗ͠, ͋Δ஋·ͨ͸஋ͷ ू߹Λग़ྗ͢Δ, ໌֬ʹఆٛ͞Εͨܭࢉखଓ͖ͷ͜ ͱ. • ࣮ࡍʹ͸ڱٛͷҙຯͰͷΞϧΰϦζϜ, ޿ٛͷҙຯ ͰͷΞϧΰϦζϜ͕ଘࡏ͢Δ. • ຊ࣭తͳ͜ͱͰ͸ͳ͍ͷͰলུ
14. ΞϧΰϦζϜΛֶͿҙٛ • ܭࢉࢿݯ͸༗ݶͰ͋Δ ‣ ༗ݶͷϦιʔεͰ͍͔ʹޮ཰Α͘ॲཧ͢Δ͔ • ΞϧΰϦζϜ͸ΤϯδχΞͷʮڞ௨ݴޠʯ ‣ ΞϧΰϦζϜΛ஌͍ͬͯΔલఏͰ࿩Λ͢Δ • ஌͕ࣝ͋Ε͹৽͍͠໰୊ʹ΋ରॲͰ͖Δ
15. ΞϧΰϦζϜͷධՁ • ΞϧΰϦζϜΛධՁ͢ΔͨΊʹ, Φʔμʔදه ͱ͍͏΋ͷ͕࢖ΘΕΔ. • ೖྗͷαΠζΛnͱͨ͠ͱ͖ʹ, Ͳͷఔ౓ͷܭ ࢉྔ͕ඞཁʹͳΔ͔Λද͢΋ͷ. • O(n)ͱ͍͏දهΛ͢Δ.
16. ΞϧΰϦζϜͷධՁ • ྫ͑͹nͷେ͖͞ʹ͔͔ΘΒͣఆ਺࣌ؒͰॲཧ ͕ऴΘΔ৔߹ʢϋογϡͳͲʣ
 ɹ→ O(1)ͱදه͢Δ • ೖྗαΠζnʹΑͬͯ୳ࡧ͕࣌ؒมԽ͢Δ΋ͷ ʢઢܗ୳ࡧͳͲʣ
 ɹ→ O(n), O(nlogn), O(logn), etc…
17. ΞϧΰϦζϜͷධՁ • ΦʔμʔදهͰ͸ҎԼͷΑ͏ͳܭࢉྔ͕සग़͢Δ.
 • O(nlogn)͙Β͍·Ͱ͸͍͍͕, ͦΕҎ্ʹͳΔͱ ٸܹʹܭࢉྔ͕૿Ճ͢Δ. ‣ ࣮༻ʹת͑Δͷ͸O(nlogn)͙Β͍·Ͱͱߟ͑Δ.
18. ΞϧΰϦζϜͷධՁ • ΞϧΰϦζϜʹΑͬͯ͸, O(n^2)ͩͱͯ͠΋ߴ଎Ͱ ͋Δͱݴ͑Δ. • ݁ہͷͱ͜Ζ, ॲཧର৅ͷαΠζ(nͷαΠζ)ʹΑͬ ͯߴ଎͔Ͳ͏͔͸ܾ·ͬͯ͘Δ. • ۭؒ࢖༻ྔʢϝϞϦʣΛ࿦͡Δͱ͖ʹ΋Φʔμʔ දه͸࢖ΘΕ͍ͯΔ.
19. ΞϧΰϦζϜͱσʔλߏ଄ • σʔλߏ଄͸, ʮର৅ͱ͢ΔσʔλΛอ࣋͢Δ·ͨ͸ දݱ͢ΔͨΊͷߏ଄ʯ ‣ ഑ྻ΍໦ߏ଄͕Θ͔Γ΍͍͢ྫ • ΞϧΰϦζϜʹదͨ͠σʔλߏ଄Λ࢖͏͜ͱͰ, ΑΓ ޮ཰తʹॲཧ͢Δ͜ͱ͕ग़དྷΔ. • σʔλϕʔεͰ͸B+໦Λ࢖͍ͬͯΔ.
20. ܭࢉྔͱఆ਺߲ • ΦʔμʔදهͰ͸, ఆ਺߲͸ແࢹ͞ΕΔ. ‣ ܭࢉίετ͕3nͷ৔߹, O(n) ‣ ܭࢉίετ͕2n^2ͷ৔߹, O(n^2) • ؔ਺ݺͼग़͠, ஋Λฦ͢, ifͰ෼ذ౳͸ఆ਺߲ѻ͍ ͞Ε͍ͯΔ.
21. ܭࢉྔͱఆ਺߲ • Φʔμʔදه͸ΞϧΰϦζϜͦͷ΋ͷΛධՁɾൺ ֱ͢Δࡍʹ͸ศར. • ࣮ࡍͷ଎౓͸, ଞͷܭࢉػతͳཁҼʹࠨӈ͞ΕΔ. ‣ ΩϟογϡʹࡌΓ΍͍͔͢Ͳ͏͔ ‣ ෼ذ͕গͳ͍͔Ͳ͏͔
22. ܭࢉྔͱఆ਺߲ • ιʔτΞϧΰϦζϜͷԼݶ͸O(nlogn)Ͱ͋Δ ͱҰൠతʹݴΘΕ͍ͯΔ. • ಉ͡ΞϧΰϦζϜͰ΋, ΫΠοΫιʔτ͕࠷΋ ૣ͍ͱݴΘΕ͍ͯΔ. ‣ ΩϟογϡʹࡌΓ΍͍ͨ͢Ί.
23. ࠷దԽͷ஫ҙ఺ • ࠷దԽΛߦͳ͏ࡍʹ, ఆ਺ഒΛվળ͢ΔΑΓ΋ ΞϧΰϦζϜͦͷ΋ͷΛมߋ͠ܭࢉྔΛݮΒͤ ΔͷͳΒͦΕ͕ྑ͍. • O(n^2)ͷఆ਺ഒΛվળ͢ΔΑΓ΋, O(nlogn) ͷΞϧΰϦζϜ͕͋ΔͷͳΒͦͬͪΛ࠾༻͠ Α͏.
24. ΞϧΰϦζϜ׆༻ͷ࣮ࡍͷͱ͜Ζ • ཧ࿦্ߴ଎ͳΞϧΰϦζϜΑΓ΋, ݹయతͳΞ ϧΰϦζϜͷ΄͏͕ૣ͍͜ͱ΋͋Δ. • Α͘஌ΒΕ͍ͯΔΞϧΰϦζϜΑΓ΋, φΠʔ ϒͳΞϧΰϦζϜͷ΄͏͕͍͍͜ͱ΋͋Δ.
25. αʔυύʔςΟʔͷ࣮૷Λར༻͢Δ • ఆ൪ͷΞϧΰϦζϜʹؔͯ͠͸, ୈࡾऀ͕ར༻͠΍ ͍͢Α͏ͳܗͰެ։͞Ε͍ͯΔ͜ͱ͕ଟ͍. • PerlͰ͍͏ͱ͜ΖͷCPAN • ͨͩ͠, ࢓༷͕ࣗ෼ͨͪͷཧ૝ͱ͍͋ͬͯͳ͔ͬͨ ΓΦʔόʔεϖοΫͳ৔߹͸ࣗ෼ͨͪͰ࣮૷͢Δ ඞཁ΋͋Δ͔΋.
26. Lesson 20 ͸ͯͳμΠΞϦʔͷ
 ΩʔϫʔυϦϯΫ
27. ΩʔϫʔυϦϯΫͱ͸ʁ • ࣗಈతʹΩʔϫʔυͷϦϯΫΛੜ੒͢Δ΍ͭ ʢ5ճͷ಺༰Ͱग़͖ͯͨ΋ͷʣ Լઢ෦෼͕ϦϯΫ
28. αʔυύʔςΟʔͷ࣮૷Λར༻͢Δ • ೖྗ͞Εͨจষʹରͯ͠, 27ສ୯ޠೖ͍ͬͯΔࣙ ॻͱϚονϯά͢Δ. • ର৅ՕॴΛHTMLͷΞϯΧʔλάʹஔ͖׵͑Δ࡞ ۀΛߦ͏. ͸ͯͳμΠΞϦʔ͸ϒϩάͰ͢ <a href=“…”>͸ͯͳμΠΞϦʔ</a>͸<a href=“…”>ϒϩάͰ͢</a> ྫ
29. ౰ॳͷ࣮૷ • ౰ॳ͸ਖ਼نදݱΛ࢖ͬͨnaive algorithmΛ࠾ ༻͍ͯͨ͠. ‣ ࣙॻதʹؚ·ΕΔશ୯ޠΛORͰܨ͛Δ ‣ (foo|bar|baz|hoge|fuga|…)
30. ਖ਼نදݱϚονϯάͰͷ໰୊఺ • αʔϏε։࢝௚ޙ͸୯ޠ਺͕ͦΕ΄Ͳଟ͘ͳ ͍ͨΊ, DB͔Βͦͷ৔Ͱਖ਼نදݱΛੜ੒࣮͠ ݱ͍ͯͨ͠. • Ωʔϫʔυ͕૿Ճ͢Δͱਖ਼نදݱͷॲཧʹ࣌ ͕͔͔ؒͬͯ͘ΔͨΊ, ࣮༻ʹ଱͑ͳ͘ͳΔ.
31. ਖ਼نදݱϚονϯάͰͷ໰୊఺ • 2ͭͷՕॴʹ͕͔͔࣌ؒΔ 1. ਖ਼نදݱΛίϯύΠϧ͢Δॲཧ • ࣄલʹ࡞ͬͯΩϟογϡ͓ͯ͘͠ 2. ਖ਼نදݱͰύλʔϯϚον͢Δॲཧ • ղܾͰ͖ͣ…
32. ύλʔϯϚονͷ໰୊఺ • ΩʔϫʔυϦϯΫͷੜ੒ʹ͕͔͔࣌ؒΔݪҼ ͸, ਖ਼نදݱͷΞϧΰϦζϜ͕ݪҼ • ΦʔτϚτϯ͕࢖༻͞Ε͍ͯΔ. • ଟ͘͸NFAʢඇܾఆੑ༗ݶΦʔτϚτϯʣ
33. ύλʔϯϚονͷ໰୊఺ • (foo|bar|baz|…)ͱ͍͏ਖ਼نදݱ͕͋ͬͨͱ͖ foo | bar | baz | … text : d(^_^o) ෆҰக ͸ʁ
34. ύλʔϯϚονͷ໰୊఺ • ୯७ʹઌ಄͔Βݟ͍ͯͬͯ, Ұக͢Δ͔͠ͳ͍ ͔Λݟ͍ͯ͘. ‣ ୯ޠ਺͕ଟ͘ͳΔ΄Ͳॲཧ͕஗͘ͳΔ ‣ ୯ޠ਺͕গͳ͚Ε͹ͦΕͰ΋ಈ࡞͢Δ
35. ਖ਼نදݱˠTrie • ύλʔϯϚονͷܭࢉྔΛམͱͨ͢Ίʹਖ਼ن දݱ͔ΒTrie΁࣮૷Λ੾Γସ͑ͨ. • TireͬͯͳΜ͚ͩͬʁ
36. ʲ෮शʳTrie໦ͱ͸ • Ωʔू߹Λѻ͏ͨΊͷσʔλߏ଄ͷҰछ • ࠓճͷΑ͏ͳ୯ޠͷू߹ͱ͔ • ݕࡧαΠζ͕໦ͷେ͖͞Ͱ͸ͳ͘୯ޠͷ௕͞ ʹґଘ͢Δ • ऩ࿥݅਺ʹґଘ͠ͳ͍
37. ʲ෮शʳTrie໦ͱ͸ t e a n o i n n w e keys: tea, ten, to, i, in, inn, we
38. Trieߏ଄ͱύλʔϯϚον • Trieߏ଄Λ࢖͏ͱ, ਖ਼نදݱʹΑΔϚονΑΓ΋ܭࢉྔ Λ࡟ݮ͢Δ͜ͱ͕Ͱ͖Δ. • ೖྗจॻΛTrieʹೖྗͯ͠ΤοδΛḷΓ, ऴ୺͕ݟͭ ͔Ε͹ଘࡏ͢Δ. • ܭࢉྔͷαΠζ͕ೖྗͷ௕͞ʹґଘ͢Δ • ΦʔτϚτϯͬΆ͍
39. AC(Aho-Corasick)๏ • ࣙॻத͔ΒύλʔϯϚονϯάΛߴ଎ʹߦ͏ ख๏. ‣ ࣙॻαΠζʹґଘ͠ͳ͍ • ػձ͕͋Ε͹΍Γ͍͙ͨΒ͍ͷؾ࣋ͪ… • ຊ࣭৘ใͰ͸ͳͦ͞͏ͳͷͰεΩοϓ
40. ΩʔϫʔυϦϯΫ࣮૷ɺมભͱߟ࡯ • ڊେͳਖ਼نදݱˠAC๏ˠRegexp::List΁ͱม Խ͖ͯͨ͠. • ͲͷΑ͏ʹσʔλߏ଄ͱΞϧΰϦζϜΛબఆ ͍ͯ͘͠΂͖͔ʁ
41. ॳظஈ֊ • σʔλ਺΋͋·Γେ͖͘ͳ͘γϯϓϧͳ࣮૷ → γϯϓϧΏ͑޻਺΋গͳͯ͘ࡁΉ → ॊೈੑʹ෋Μ࣮ͩ૷ → ଞͷػೳͷ࣮૷΁࣌ؒΛׂ͘
42. ݱࡏ • σʔλ͕େ͖͘ͳΔ͜ͱͰ, େ෯ʹ࣮૷Λݟ௚ ͢ඞཁ͕ग़͖ͯͨ. → γϯϓϧͳ࣮૷+ΩϟογϡͰ͸ճආෆՄೳ → ΞϧΰϦζϜΛධՁ͠, ܭࢉྔͷ؍఺͔Βߟ ͑Δඞཁ͕͋Δ
43. ߟ࡯ • ॳظஈ֊Ͱ, ࠷ద(Ͱ͸͋Δ͕ෳࡶ)ͳ࣮૷Λ༻ ͍Δ͜ͱ͕ਖ਼͍͠ͱ͸ݶΒͳ͍. ‣ γϯϓϧͳ࣮૷͕ڐ͞ΕΔ • େن໛ʹͳͬͨͱ͖ʹඋ͑ͯ, ຊ࣭తͳղܾํ ๏Λ஌͓ͬͯ͘ඞཁ΋͋Δ.
44. Lesson 21 هࣄΧςΰϥΠζ
45. هࣄΧςΰϥΠζͱ͸ʁ • هࣄͷ಺༰ʹج͍ͮͯ, ద౰ͳΧςΰϦʹࣗಈ Ͱ෼ྨ͢Δ͜ͱ. • ϕΠδΞϯϑΟϧλΛ࢖ͬͯΧςΰϦ൑ఆΛ ߦ͍ͬͯΔ.
46. ϕΠδΞϯϑΟϧλͱ͸ʁ • φΠʔϒϕΠζ(Naive Bayes)ͱ͍͏ΞϧΰϦζϜΛར༻ ͯ͠, ֬཰తʹͲͷδϟϯϧʹ෼ྨ͞ΕΔ͔Λௐ΂Δํ๏. • աڈͷ෼ྨ৘ใΛ࢖ͬͯ, ݱࡏͷ(δϟϯϧ͕ະ஌ͷ)จॻ Λ෼ྨ͢Δ. ‣ ڭࢣ͋ΓֶशΛར༻͍ͯ͠Δ. ‣ ػցֶशɾύλʔϯೝࣝͷݚڀ੒ՌʹΑΔ΋ͷ
47. ϕΠδΞϯϑΟϧλͱ͸ʁ • ϕΠδΞϯϑΟϧλͷ֩ͱͳ͍ͬͯΔ΋ͷ͸, φΠʔ ϒϕΠζͱ͍͏ΞϧΰϦζϜ. ‣ ໊લ͔Β෼͔Δ௨Γ, ϕΠζͷఆཧΛϕʔεͱͨ͠ ΞϧΰϦζϜ. • ۩ମతͳ࣮૷ʹ͸౿Έࠐ·ͣ, ͲͷΑ͏ʹಈ͔͚ͩ͘ ղઆ͢Δ.
48. φΠʔϒϕΠζʹΑΔΧςΰϦਪఆ • ͋ΔจॻD͕༩͑ΒΕͨ࣌, ͦͷจॻ͕֬཰త ʹͲͷΧςΰϦCʹଐ͢Δͷ͕΋ͬͱ΋Β͍͠ ͔ΛٻΊΔ. • ͭ·Γ, จॻD͕༩͑ΒΕͨͱ͖ͷΧςΰϦC Ͱ͋Δ৚݅෇͖֬཰P(C|D)ΛٻΊΔ.
49. φΠʔϒϕΠζʹΑΔΧςΰϦਪఆ • P(C|D)Λ௚઀ܭࢉ͢Δͷ͸೉͍͠ ‣ ϕΠζͷఆཧΛ࢖͏ͱܭࢉՄೳʹ • ϕΠζͷఆཧ P(D|C), P(C), P(D)ΛٻΊΔ.
50. φΠʔϒϕΠζʹΑΔΧςΰϦਪఆ • ࠓճඞཁͳͷ͸֬཰ͦͷ΋ͷΑΓ΋, ͲͷΧς ΰϦ͕΋ͬͱ΋Β͍͔͠ͱ͍͏͜ͱ • ઌ΄Ͳͷࣜʹ͓͍ͯ, จॻD͕ੜى͢Δ֬཰ P(D)͸ҰఆͰ͋Δ. ‣ P(D|C), P(C)ͷΈΘ͔Ε͹ྑ͍ʂ
51. φΠʔϒϕΠζʹΑΔΧςΰϦਪఆ • P(D|C), P(C)ͷ஋Λֶशσʔλ͔Βࢉग़ͯ͠͠ ·͑͹ٻΊΔ͜ͱ͕Ͱ͖Δ. ‣ P(C)͸ͦͷΧςΰϦ͕ग़ݱ͢Δ֬཰ͳͷͰ, ෼ྨ͞Εͨճ਺͚͓͚֮ͩ͑ͯ͹͍͍. ‣ P(D|C)͸ଟগͷ޻෉͕ཉ͍͠.
52. φΠʔϒϕΠζʹΑΔΧςΰϦਪఆ • P(D|C)Λܭࢉ͢Δ. • DΛ೚ҙͷ୯ޠW͕࿈ଓͯ͠ग़ݱ͢Δͱߟ͑ • ҎԼͷΑ͏ͳࣜͰۙࣅ͢Δ. • DΛ୯ޠʹ෼ׂ͠, ͦΕ͝ͱʹͦͷ୯ޠ͕Ͳ͜ ʹ෼ྨ͞Εͨͷ͔Λอଘ͓ͯ͘͠.
53. طଘͷख๏ΛҾ͖ग़͠ʹೖΕ͓ͯ͘ • େن໛σʔλʹର͢ΔΞϧΰϦζϜతͳΞϓϩʔ νΛֶͿʹ౰ͨͬͯ͸, طଘͷख๏Λ͋Δఔ౓ ஌͍ͬͯΔ͜ͱ͕ॏཁ. ‣ σʔλϚΠχϯάɾύλʔϯೝࣝɾػցֶश ͷΑ͏ͳΞϧΰϦζϜ. ‣ ιʔτ΍୳ࡧɺѹॖ
54. طଘͷख๏ΛҾ͖ग़͠ʹೖΕ͓ͯ͘ • ྫɿTrie͸ΩʔϫʔυϦϯΫʹԠ༻Ͱ͖Δ
 ɹɹϕΠδΞϯϑΟϧλΛࣗಈ෼ྨʹ → ͲͪΒ΋ΞϧΰϦζϜΛ஌͍ͬͯΔ͜ͱͰ, ׆༻ Ͱ͖Δ͜ͱ͕Θ͔Δ. • ΞϧΰϦζϜΛ࣮૷ޙ΋௥Ճ࡞ۀ͕͋Δ͜ͱ΋஌ͬ ͓ͯ͘΂͖.