計算量と僕とWeb開発 / computational complexity and I and Web

1. ܭࢉྔͱ๻ͱWeb։ൃ גࣜձࣾ͸ͯͳ ichirin2501  ͸ͯͳɾϖύϘٕज़େձʙΠϯϑϥٕज़ج൫
2. ࣗݾ঺հ • ੢઒ ݩߊ ( @ichirin2501 ) • ͸ͯͳͷWebΦϖϨʔγϣϯΤϯδχΞ(໿1೥)
 ݩΞϓϦέʔγϣϯΤϯδχΞ(໿2೥൒)͔Βస৬ ڵຯ 
3. ஫ҙࣄ߲ • (ΏΔ;Θ)ܭࢉྔͱ๻ͷࡏΓํͷ࿩Λ͠·͢
 “ܭࢉྔ”ࣗମʹ͍ͭͯ͸(΄ͱΜͲ)࿩͠·ͤΜ • Web։ൃͰࠓ͸ίʔυΛॻ͔ͳ͘ͳͬͨ
 WebΦϖϨʔγϣϯΤϯδχΞͰ͢ʂ
 ϛυϧ΢ΣΞͱ͸஥ྑ͘͢Δػձ͸ଟ͍ 
4. ΋͘͡ • ܭࢉྔʹ͍ͭͯ
 - ܭࢉྔͱ๻
 - σʔλαΠζ͔Βݟੵ΋Γ • MySQL(InnoDB)ͷΫΤϦվળ
 - group by / distinct ͷ໎͍ • RedisͷઃఆΛݟͯࢥͬͨ͜ͱ(খωλ)
 - ϝϞϦѹॖ΁ͷ͍ٙ 
5. ܭࢉྔʹ͍ͭͯ ͋Δ໰୊Λղ͘େม͞ͷࢦඪͷ͜ͱ 
   ҎԼͷٖࣅίʔυ͸
   0 O?
   GPS
   ʜO

   
   
   
   GPS
   ʜO

   
   
   
   
   
   
   
   QSJOU
   IPHF ܎਺͸ແࢹ͢Δ Ұ൪େ͖͍ن໛͚ͩ࢒͢ 
6. ܭࢉྔͱ๻ • ֶੜ࣌୅ʹڝٕϓϩάϥϛϯάΛগ͠(ICPCͱ͔)
 ܭࢉྔ, σʔλߏ଄/ΞϧΰϦζϜʹ޲͖߹͏ػձ͕ଟ͔ͬͨ • ܭࢉྔͱ࣌ؒʹج४/ײ֮Έ͍ͨͳ΋ͷ͕͋Δ • ྫ͑͹ CPU 2.4 GHz, 1ίΞ ͩͱ
 ~ ͙Β͍Ͱ1ඵ͔͔Δ(ࡶ) 
7. σʔλαΠζ͔Βݟੵ΋Γ Ծʹ1ඵΛσουϥΠϯͱ͢Δͱɺ ͙Β͍·Ͱ 
8. ͦͷײ͕֮໾ʹཱͬͯΔ ͱײͨ͡࠷ۙͷ࿩ ௗ्ٔը੡࡞ηοτ: http://gigamaker.jimdo.com/ 
9. MySQLͷΫΤϦվળ 
10. GROUP BY / DISTINCT ͷ໎͍ ͓୊ͱͳΔςʔϒϧఆٛ $3&"5&
    5"#-&
    AVTFS@GSJFOEA
    
    
    
    AJEA
    CJHJOU 
    VOTJHOFE
    /05
    /6--
    
    
    AVTFS@JEA
    CJHJOU 
    VOTJHOFE
    /05
    /6--
    
    
    AGSJFOE@JEA
    CJHJOU 
    VOTJHOFE
    /05
    /6--
    
    
    13*."3:
    ,&:
    AJEA
    
    
    6/*26&
    ,&:
    AVTFS@JEA
    AVTFS@JEA AGSJFOE@JEA
    
    
    ,&:
    AGSJFOE@JEA
    AGSJFOE@JEA
    
    &/(*/&*OOP%#
    %&'"6-5
    $)"34&5VUGNC
    SELECT friend_id
 FROM user_friend
 WHERE (user_id = '785595' OR
 user_id = '3291611' OR.....)
 GROUP BY friend_id
 LIMIT 1000; ΍Γ͍ͨ͜ͱ ͋Δuserͷ෦෼ू߹͔Βॏෳͳ͠Ͱfriend_id͕1000݅΄͍͠
 GROUP BY΋DISTINCT΋࣮ݱͰ͖Δ͜ͱ͸ಉ͡ 
11. A b c d B a c f user_id friend_id ΠϝʔδͷΑ͏ͳ΋ͷ C a e  icon: http://www.flaticon.com/packs/multimedia-collection
12. A b c d B a c f C a e user_id friend_id userͷ෦෼ू߹(A,B,C)ͷfriend_idΛॏෳͳ͠Ͱ5݅ ΍Γ͍ͨ͜ͱ͸
 ͜Ε͚ͩ  icon: http://www.flaticon.com/packs/multimedia-collection
13. SELECT friend_id
 FROM user_friend
 WHERE (user_id = '785595' OR
 user_id = '3291611' OR.....)
 GROUP BY friend_id
 LIMIT 1000; OR۟ͷuser_id͕ଟ͘ͳͬͯ͘Δͱ
 ٸʹҟৗʹ஗͘ͳͬͨ(50ඵͱ͔͔͔Δ) ͳΜͰ΍ʂ ฏ࿨ͳ͋Δ೔ͷ͜ͱ.... 
14. ௗ्ٔը੡࡞ηοτ: http://gigamaker.jimdo.com/ ͲͷΑ͏ʹݕࡧͯ͠Δʁ 
15. MySQL(InnoDB)ͷΠϯσοΫεߏ଄ ΠϯσοΫεͷσʔλߏ଄͸B+tree ओΩʔͷΠϯσοΫεΛClustered Index ͦΕҎ֎ͷΠϯσοΫεΛSecondary Index ؆୯ͳB+treeͷྫͷਤ*1 ਤ: 1͔Β7ͷΩʔͱσʔλ஋d1-d7ͷߏ੒ ੺Ͱࣔ͞ΕͯΔͷ͸࿈݁Ϧετ Clusteredʹ࣮σʔλ(Ϩίʔυ)ɺ Secondaryʹ͸PK͕σʔλ஋ͱͯ֨͠ೲ XJLJQFEJBΑΓ
    IUUQTDPNNPOTXJLJNFEJBPSHXJLJ'JMF#USFFTWH 
16. user_friendͷ(؆қ)Clustered Index SPPU         Clustered Index (id) 
    "
    C 
    #
    B 
    "
    D 
    $
    B 
    #
    D 
    #
    G 
    "
    E 
    $
    F SecondaryIndex
 (user_id, friend_id) SecondaryIndex
 (friend_id) icon: https://www.iconfinder.com/icons/174603/deciduous_tree_icon#size=256 
17. SecondaryIndex(user_id,friend_id)ͷ؆қ൛ SPPU "
    C "
    D "
    E #
    B #
    D #
    G $
    B $
    F SecondaryIndex (user_id, friend_id)         Clustered Index
 (id) SecondaryIndex
 (friend_id) icon: https://www.iconfinder.com/icons/174603/deciduous_tree_icon#size=256 
18. SPPU B B C D D E F G SecondaryIndex (friend_id)         Clustered Index
 (id) SecondaryIndex
 (user_id, friend_id) icon: https://www.iconfinder.com/icons/174603/deciduous_tree_icon#size=256  SecondaryIndex(friend_id)ͷ؆қ൛
19. SPPU "
    C "
    D "
    E #
    B SecondaryIndex (user_id, friend_id)     Clustered Index (id)  SPPU     
    "
    C 
    #
    B 
    "
    D 
    $
    B SecondaryIndex(user_id,friend_id)Λར༻ͯ͠ݕࡧ ྫ: WHERE user_id = 'A' AND friend_id = 'c'
20. ࿩Λ໭ͦ͏ SELECT friend_id
 FROM user_friend
 WHERE (user_id = '785595' OR
 user_id = '3291611' OR.....)
 GROUP BY friend_id
 LIMIT 1000; (user_id, friend_id)ʹΑΔݕࡧ͕࠷దͷ͸ͣͰɺ
 ܭࢉྔతʹ΋ٸܹʹ஗͘ͳΔͷ͸͓͔͍͠ͷͰ͸ʁ ΋͔ͯ͠͠ friend_id ͷΠϯσοΫεͰݕࡧͯ͠Δʁ 
21. SPPU "
    C "
    D "
    E #
    B #
    D #
    G $
    B $
    F d d d d d d d d SecondaryIndex(user_id,friend_id)Λ࢖ͬͨݕࡧ(1/2) WHERE (user_id = 'A' OR user_id = 'C') 
22. SPPU "
    C "
    D "
    E #
    B #
    D #
    G $
    B $
    F d d d d d d d d SecondaryIndex(user_id,friend_id)Λ࢖ͬͨݕࡧ(2/2)  WHERE (user_id = 'A' OR user_id = 'C')
23. σʔλ͕૿͑ͨͱ͖ͷSecondaryIndex(friend_id) SPPU B B B B B B C C d d d d d d d d user_idΛݕࡧ৚݅ʹfriend_idͷΠϯσοΫεͰ
 ݕࡧ͢Δͷ͸໌Β͔ʹແବ 
24. ݁࿦͔Βݴ͏ͱͦ͏ͩͬͨ EXPLAINͰ֬ೝ͢Δͱ࢖༻͢ΔΠϯσοΫε͕friend_id MySQLͷΦϓςΟϚΠβ͕ؒҧͬͨ൑அΛ͍ͯͨ͠ DISTINCTʹ͢Δͱؒҧͬͨ൑அΛ͠ͳ͘ͳͬͨͷͰͻͱ·ͣղܾ ΦϓςΟϚΠβ͕൑அΛؒҧ͏ͷ͸͋Δ͋ΔҊ݅
 ͚ͩͲɺͦͷܦݧଇ΍EXPLAINΛ࢖Θͳͯ͘΋ܭࢉྔͱ࣌ؒͷ
 ײ֮Ͱϛυϧ΢ΣΞͷ"Ͳ͜"͕·ͣͦ͏ͳͷ͔͸ਪଌͰ͖ͨΓ͢Δ 
25. RedisͷઃఆΛݟͯࢥͬͨ͜ͱ 
26. Redisͱ͸ ΩʔόϦϡʔΛجຊͱ͢Δσʔλߏ଄ܕNoSQL
 List, Set, Sorted Sets,etcͷσʔλߏ଄͕͋ͬͯେมศར 
    SFEJTDPOG
    [TFUNBY[JQMJTUFOUSJFT
    
    [TFUNBY[JQMJTUWBMVF
    
    
    ઃఆͷҰ෦ Redis 2.2͔ΒϝϞϦ࠷దԽͷ࢓૊Έ͕ग़དྷͨ ύϥϝʔλʔΛݟͨॠؒʹ
 |'-')oO( CPUͱtrade-offͰ΋ѹॖͷͨΊʹಛघͳΤϯίʔσΟϯάͯ͠Δ ͱσʔλߏ଄͔Βͯ͠ҧ͍ͦ͏ͩ͠ɺΦʔμʔ͕શ͘ҧ͏ͷͰ͸ʁ) 
27. ո͍͠ͷͰ࣮ࡍʹࢼ͢(1/2) Sorted Setsܕ scoreͰιʔτࡁΈͷσʔλू߹ ಺෦࣮૷͸SkipList&Hashͷ૊Έ߹Θͤ ͲͪΒͷ৚݅΋ຬͨ͢ݶΓ͸ϝϞϦѹॖͯ͘͠ΕΔ 
    SFEJTDPOG
    [TFUNBY[JQMJTUFOUSJFT
    
    
    EFGBVMU
    
    [TFUNBY[JQMJTUWBMVF
    
    ֬ೝ͍ͨ͜͠ͱ: Φʔμʔ͸ίϚϯυͷυΩϡϝϯτ௨Γʁ ಛఆͷίϚϯυΛద౰ʹ܁Γฦ࣮͠ߦ͢Ε͹Θ͔Γͦ͏ 
28. ո͍͠ͷͰ࣮ࡍʹࢼ͢(2/2) 
    UJNF
    DBSUPO
    FYFD
    QFSM
    SSQM
    D
    
    DBSUPO
    FYFD
    QFSM
    SSQM
    D
    
    
    T
    VTFS
    T
    TZTUFN
    
    DQV
    
    UPUBM 
    UJNF
    DBSUPO
    FYFD
    QFSM
    SSQM
    D
    
    DBSUPO
    FYFD
    QFSM
    SSQM
    D
    
    
    T
    VTFS
    T
    TZTUFN
    
    DQV
    
    UPUBM ͳΒ10^4Ͱ1ඵΛ௒͑ͳ͍ؾ͕͢Δʁ zset-max-ziplist-entries = 128 (default ZADDίϚϯυΛ10000ճൃߦ͢Δ ίϚϯυͷ࣌ؒܭࢉྔ: , n͸SortedSetsͷཁૉ਺ zset-max-ziplist-entries = 10000 ྲྀੴʹ͓͔͍͠ͷͰ͸ͳ͍͔ʁͱؾ෇͘͜ͱ͕Ͱ͖Δ  rr.pl: https://gist.github.com/ichirin2501/21e9ef8540086650fec85c3e0ccf7da5
29. ΍͸Γσʔλߏ଄͕ҧͬͨ • ίʔυΛಡΉͱσʔλߏ଄ͷ࣮૷͕ҧ͏ • ࣮͸υΩϡϝϯτʹ data structure
 ͱॻ͔ΕͯΔʢޙͰؾ෇͍ͨ • ઃఆΛݟ͚ͨͩͰʮ·ͣͦ͏ʯͱΞλϦ͕ͭ ͘͜ͱ͕͋Δ(͔΋͠Εͳ͍) 
30. ·ͱΊ • ܭࢉྔͱ࣌ؒʹج४͕͋Δͱศར
 ίʔυ͸ॻ͔ͳ͘ͳ͚ͬͨͲ໾ʹཱͭ৔໘͸͋Δ • (ܭࢉྔͱ࣌ؒ)ج४Λײ͕֮͋Δ͔Βؾ෇͚Δ
 ஌͚ࣝͩͩͱؾ෇͚ͳ͍͔΋͠Εͳ͍