Upgrade to Pro — share decks privately, control downloads, hide ads and more …

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

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

ichirin2501

July 09, 2016
Tweet

More Decks by ichirin2501

Other Decks in Technology

Transcript

  1. ΋͘͡ • ܭࢉྔʹ͍ͭͯ
 - ܭࢉྔͱ๻
 - σʔλαΠζ͔Βݟੵ΋Γ • MySQL(InnoDB)ͷΫΤϦվળ
 -

    group by / distinct ͷ໎͍ • RedisͷઃఆΛݟͯࢥͬͨ͜ͱ(খωλ)
 - ϝϞϦѹॖ΁ͷ͍ٙ 
  2. GROUP BY / DISTINCT ͷ໎͍ ͓୊ͱͳΔςʔϒϧఆٛ $3&"5&5"#-&AVTFS@GSJFOEA  AJEACJHJOU 

    VOTJHOFE/05/6--  AVTFS@JEACJHJOU  VOTJHOFE/05/6--  AGSJFOE@JEACJHJOU  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΋࣮ݱͰ͖Δ͜ͱ͸ಉ͡ 
  3. A b c d B a c f user_id friend_id

    ΠϝʔδͷΑ͏ͳ΋ͷ C a e  icon: http://www.flaticon.com/packs/multimedia-collection
  4. 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
  5. 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ඵͱ͔͔͔Δ) ͳΜͰ΍ʂ ฏ࿨ͳ͋Δ೔ͷ͜ͱ.... 
  6. 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 
  7. 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 
  8. 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)ͷ؆қ൛
  9. 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'
  10. ࿩Λ໭ͦ͏ 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 ͷΠϯσοΫεͰݕࡧͯ͠Δʁ 
  11. 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') 
  12. 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')
  13. σʔλ͕૿͑ͨͱ͖ͷSecondaryIndex(friend_id) SPPU B B B B B B C C

    d d d d d d d d user_idΛݕࡧ৚݅ʹfriend_idͷΠϯσοΫεͰ
 ݕࡧ͢Δͷ͸໌Β͔ʹແବ 
  14. Redisͱ͸ ΩʔόϦϡʔΛجຊͱ͢Δσʔλߏ଄ܕNoSQL
 List, Set, Sorted Sets,etcͷσʔλߏ଄͕͋ͬͯେมศར SFEJTDPOG [TFUNBY[JQMJTUFOUSJFT [TFUNBY[JQMJTUWBMVF ઃఆͷҰ෦

    Redis 2.2͔ΒϝϞϦ࠷దԽͷ࢓૊Έ͕ग़དྷͨ ύϥϝʔλʔΛݟͨॠؒʹ
 |'-')oO( CPUͱtrade-offͰ΋ѹॖͷͨΊʹಛघͳΤϯίʔσΟϯάͯ͠Δ ͱσʔλߏ଄͔Βͯ͠ҧ͍ͦ͏ͩ͠ɺΦʔμʔ͕શ͘ҧ͏ͷͰ͸ʁ) 
  15. ո͍͠ͷͰ࣮ࡍʹࢼ͢(2/2) UJNFDBSUPOFYFDQFSMSSQMD DBSUPOFYFDQFSMSSQMDTVTFSTTZTUFNDQVUPUBM UJNFDBSUPOFYFDQFSMSSQMD DBSUPOFYFDQFSMSSQMDTVTFSTTZTUFNDQVUPUBM ͳΒ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