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

Problems and Solutions for Two Billion Recommen...

Problems and Solutions for Two Billion Recommendations Per Day

Naoki Watanabe (hackmylife) (LINE / CRS dev team / Software engineer )

https://tech-verse.me/ja/sessions/13
https://tech-verse.me/en/sessions/13
https://tech-verse.me/ko/sessions/13

Tech-Verse2022

November 18, 2022
Tweet

More Decks by Tech-Verse2022

Other Decks in Technology

Transcript

  1. Gathers recommended contents from services Learning users preferences & use

    them to make the next selection Select best ones of the many contents Key function
  2. Peak Traffic - LINE’s peak traffic is New Year -

    Especially JP (GTM+9) - 250k request / second
  3. Peak Traffic - LINE’s peak traffic is New Year -

    Especially JP (GTM+9) - 250k request / second - Client side cache is effective
  4. Request with client-side cache TTL (seconds) Estimated RPS 0 250,000

    60 148,000 180 121,000 New Year Peek of 2018
  5. Request with client-side cache TTL (seconds) Estimated RPS 0 250,000

    60 148,000 180 121,000 300 107,000 New Year Peek of 2018
  6. Request with client-side cache TTL (seconds) Estimated RPS 0 250,000

    60 148,000 180 121,000 300 107,000 600 71,000 New Year Peek of 2018
  7. Request with client-side cache TTL (seconds) Estimated RPS 0 250,000

    60 148,000 180 121,000 300 107,000 600 71,000 1800 58,000 New Year Peek of 2018
  8. Request with client-side cache TTL (seconds) Estimated RPS 0 250,000

    60 148,000 180 121,000 300 107,000 600 71,000 1800 58,000 New Year Peek of 2018
  9. Redis Cluster Redis Cluster Key: User-A ID Node 3 Node

    2 Node 1 Value: Item-A ID, Item-B ID, ….
  10. Redis Cluster Redis Cluster Key: User-A ID Node 3 Node

    2 Node 1 Value: Item-A ID, Item-B ID, ….
  11. Redis Cluster Redis Cluster Key: User-A ID Node 3 Node

    2 Node 1 Value: Item-A ID, Item-B ID, …. + Service X
  12. Redis Cluster Redis Cluster Key: User-A ID Node 3 Node

    2 Node 1 Value: Item-A ID, Item-B ID, …. Key: User-A ID Value: Item-X ID, Item-Y ID, …. + Service X + Service Y
  13. Redis Cluster Redis Cluster Key: User-A ID Node 3 Node

    2 Node 1 Value: Item-A ID, Item-B ID, …. Key: User-A ID Value: Item-X ID, Item-Y ID, …. + Service X + Service Y
  14. Redis Cluster Redis Cluster Key: User-A ID Node 3 Node

    2 Node 1 Value: Item-A ID, Item-B ID, …. Key: User-A ID Value: Item-X ID, Item-Y ID, …. + Service X + Service Y
  15. Redis Cluster Redis Cluster Node 3 Node 2 Node 1

    Value: Item-A ID, Item-B ID, …. Value: Item-X ID, Item-Y ID, …. + Service X + Service Y Key: {User-A ID} Key: {User-A ID}
  16. Redis Cluster Redis Cluster Node 3 Node 2 Node 1

    Value: Item-A ID, Item-B ID, …. Value: Item-X ID, Item-Y ID, …. + Service X + Service Y Key: {User-A ID} Key: {User-A ID}
  17. Redis Cluster Redis Cluster Node 3 Node 2 Node 1

    Value: Item-A ID, Item-B ID, …. Value: Item-X ID, Item-Y ID, …. + Service X + Service Y Key: {User-A ID} Key: {User-A ID} Value: Item-C ID, Item-D ID, …. + Service X Key: {User-B ID}
  18. Data Modeling Type Data format Distribution Key Targeting Redis {User-A}:Service

    x => Item-A ID, Item-B ID, … {User-A}:Service Y => Item-X ID, Item-Y ID, … {User-B}:Service X => Item-C ID, Item-D, … User ID
  19. Data Modeling Type Data format Distribution Key Targeting Redis {User-A}:Service

    x => Item-A ID, Item-B ID, … {User-A}:Service Y => Item-X ID, Item-Y ID, … {User-B}:Service X => Item-C ID, Item-D, … User ID Information Redis Item ID
  20. Look before you leap - Release gradually - Always A/B

    test if anything is unclear - Measure performance per web server
  21. Fetch Information Process Hypothesis - 1 Fetch Target Process Targeting

    Redis Item a ID Item B ID Information Redis Node 1 Node 3 Node 2 Item A Item B Item C Item D Item E Item F
  22. Fetch Information Process Hypothesis - 1 Fetch Target Process Targeting

    Redis Item a ID Item B ID Information Redis Node 1 Node 3 Node 2 Item A Item B Item C Item D Item E Item F Lettuce (mget)
  23. Fetch Information Process Hypothesis - 1 Fetch Target Process Targeting

    Redis Item a ID Item B ID Information Redis Node 1 Node 3 Node 2 Item A Item B Item C Item D Item E Item F Lettuce (mget)
  24. Fetch Information Process Hypothesis - 1 Fetch Target Process Targeting

    Redis Item a ID Item B ID Item F ID Information Redis Node 1 Node 3 Node 2 Item A Item B Item C Item D Item E Item F Lettuce (mget)
  25. Fetch Information Process Hypothesis - 1 Fetch Target Process Targeting

    Redis Item a ID Item B ID Item F ID Information Redis Node 1 Node 3 Node 2 Item A Item B Item C Item D Item E Item F Lettuce (mget)
  26. Fetch Information Process Hypothesis - 1 Fetch Target Process Targeting

    Redis Item a ID Item B ID Item D ID Item C ID Item F ID Item e ID Information Redis Node 1 Node 3 Node 2 Item A Item B Item C Item D Item E Item F Lettuce (mget)
  27. Fetch Information Process Hypothesis - 1 Fetch Target Process Targeting

    Redis Item a ID Item B ID Item D ID Item C ID Item F ID Item e ID Information Redis Node 1 Node 3 Node 2 Item A Item B Item C Item D Item E Item F Lettuce (mget)
  28. Verification -1 1-9 items 10-19 items 20-29 items 30-39 items

    Over 40 items Execution time (99%tile)
  29. Verification -1 1-9 items 10-19 items 20-29 items 30-39 items

    Over 40 items Execution time (99%tile) Command count
  30. Verification -1 1-9 items 10-19 items 20-29 items 30-39 items

    Over 40 items Execution time (99%tile) Command count 1-9 items 10-19 items 20-29 items 30-39 items Over 40 items
  31. Information Redis Node 1 Node 3 Node 2 Item A

    Item B Item C Item D Item E Item F Targeting Fetch Information Process Hypothesis - 2 X Y Z
  32. Information Redis Node 1 Node 3 Node 2 Item A

    Item B Item C Item D Item E Item F Targeting Fetch Information Process Hypothesis - 2 Item a ID Item B ID X Y Z
  33. Information Redis Node 1 Node 3 Node 2 Item A

    Item B Item C Item D Item E Item F Targeting Fetch Information Process Hypothesis - 2 Item a ID Item B ID X Y Z
  34. Information Redis Node 1 Node 3 Node 2 Item A

    Item B Item C Item D Item E Item F Targeting Fetch Information Process Hypothesis - 2 Item a ID Item B ID Item a ID Item F ID X Y Z
  35. Information Redis Node 1 Node 3 Node 2 Item A

    Item B Item C Item D Item E Item F Targeting Fetch Information Process Hypothesis - 2 Item a ID Item B ID Item a ID Item F ID X Y Z
  36. Information Redis Node 1 Node 3 Node 2 Item A

    Item B Item C Item D Item E Item F Targeting Fetch Information Process Hypothesis - 2 Item a ID Item B ID Item a ID Item F ID Item D ID Item B ID X Y Z
  37. Information Redis Node 1 Node 3 Node 2 Item A

    Item B Item C Item D Item E Item F Targeting Fetch Information Process Hypothesis - 2 Item a ID Item B ID Item a ID Item F ID Item D ID Item B ID X Y Z
  38. Information Redis Node 1 Node 3 Node 2 Item A

    Item B Item C Item D Item E Item F Targeting Fetch Information Process Hypothesis - 2 Item a ID Item B ID Item a ID Item F ID Item D ID Item B ID X Y Z
  39. Problem & Solution # Issue Problem 1 Burst of MGET

    command • Recommend items increased • Need access to multiple Redis nodes to retrieve information
  40. Problem & Solution # Issue Problem 1 Burst of MGET

    command • Recommend items increased • Need access to multiple Redis nodes to retrieve information 2 Concentration of Targeting • There is content recommended by many people • Concentration of access to specific node
  41. Solution1 - Burst of MGET command Fetch Information Information Redis

    Information Targeting Redis Fetch Targeting Ranking
  42. Solution1 - Burst of MGET command Fetch Information Information Redis

    Information Targeting Redis Fetch Targeting Ranking
  43. Solution1 - Burst of MGET command Fetch Information Information Redis

    Information Targeting Redis Fetch Targeting Ranking Limit
  44. Solution1 - Burst of MGET command Fetch Information Information Redis

    Information Targeting Redis Fetch Targeting Ranking Limit ↓ Not Smart
  45. Solution1 - Burst of MGET command Fetch Information Information Redis

    Information Targeting Redis Fetch Targeting Ranking
  46. Solution1 - Burst of MGET command Fetch Information Information Redis

    Information Targeting Redis Fetch Targeting Ranking Smart Filter
  47. Smart Filter Information Fetch Targeting Ranking Information Filter Targeting Filter

    Limit Fetch Information Tier 1 (user log based) Tier 2 (user attribute based)
  48. Smart Filter Information Fetch Targeting Ranking Information Filter Targeting Filter

    Limit Fetch Information Tier 1 (user log based) Tier 2 (user attribute based) Limit N = 5
  49. Smart Filter Information Fetch Targeting Ranking Information Filter Targeting Filter

    Limit Fetch Information Tier 1 (user log based) Tier 2 (user attribute based) Limit N = 5 Item Item Item
  50. Smart Filter Information Fetch Targeting Ranking Information Filter Targeting Filter

    Limit Fetch Information Tier 1 (user log based) Tier 2 (user attribute based) Limit N = 5 Item Item Item Item Item Item Item Item Item
  51. Smart Filter Information Fetch Targeting Ranking Information Filter Targeting Filter

    Limit Fetch Information Tier 1 (user log based) Tier 2 (user attribute based) Limit N = 5 Item Item Item Item Item Item Item Item Item
  52. Smart Filter Information Fetch Targeting Ranking Information Filter Targeting Filter

    Limit Fetch Information Tier 1 (user log based) Tier 2 (user attribute based) Limit N = 5 Item Item Item Item Item Item Item Item Item
  53. Smart Filter Tier 1 (user log based) Tier 2 (user

    attribute based) Limit N = 5 Item Item Item Item Item Item Item Item Item Item Item Item Information Fetch Targeting Ranking Information Filter Targeting Filter Limit Fetch Information
  54. Smart Filter Tier 1 (user log based) Tier 2 (user

    attribute based) Limit N = 5 Item Item Item Item Item Item Item Item Item Item Item Item Information Fetch Targeting Ranking Information Filter Targeting Filter Limit Fetch Information
  55. Solution2 - Concentration of Targeting Information Redis Node 1 Node

    3 Node 2 Item A Item B Item C Item D Item E Item F Targeting Item a ID Item B ID Item a ID Item F ID Item D ID Item B ID X Y Z
  56. Solution2 - Concentration of Targeting Information Redis Node 1 Node

    3 Node 2 Item A Item B Item C Item D Item E Item F Targeting Item a ID Item B ID Item a ID Item F ID Item D ID Item B ID X Y Z
  57. Solution2 - Concentration of Targeting Information Redis Node 1 Node

    3 Node 2 Item A Item B Item C Item D Item E Item F Targeting Item a ID Item B ID Item a ID Item F ID Item D ID Item B ID Cache (size=4) X Y Z
  58. Solution2 - Concentration of Targeting Information Redis Node 1 Node

    3 Node 2 Item A Item B Item C Item D Item E Item F Targeting Item a ID Item B ID Item a ID Item F ID Item D ID Item B ID Cache (size=4) X Y Z
  59. Solution2 - Concentration of Targeting Information Redis Node 1 Node

    3 Node 2 Item A Item B Item C Item D Item E Item F Targeting Item a ID Item B ID Item a ID Item F ID Item D ID Item B ID Cache (size=4) X Y Z
  60. Solution2 - Concentration of Targeting Information Redis Node 1 Node

    3 Node 2 Item A Item B Item C Item D Item E Item F Targeting Item a ID Item B ID Item a ID Item F ID Item D ID Item B ID Cache (size=4) Item A Item B X Y Z
  61. Solution2 - Concentration of Targeting Information Redis Node 1 Node

    3 Node 2 Item A Item B Item C Item D Item E Item F Targeting Item a ID Item B ID Item a ID Item F ID Item D ID Item B ID Cache (size=4) Item A Item B X Y Z
  62. Solution2 - Concentration of Targeting Information Redis Node 1 Node

    3 Node 2 Item A Item B Item C Item D Item E Item F Targeting Item a ID Item B ID Item a ID Item F ID Item D ID Item B ID Cache (size=4) Item A Item B X Y Z
  63. Solution2 - Concentration of Targeting Information Redis Node 1 Node

    3 Node 2 Item A Item B Item C Item D Item E Item F Targeting Item a ID Item B ID Item a ID Item F ID Item D ID Item B ID Cache (size=4) Item A Item B Item F X Y Z
  64. Solution2 - Concentration of Targeting Information Redis Node 1 Node

    3 Node 2 Item A Item B Item C Item D Item E Item F Targeting Item a ID Item B ID Item a ID Item F ID Item D ID Item B ID Cache (size=4) Item A Item B Item F X Y Z
  65. Solution2 - Concentration of Targeting Information Redis Node 1 Node

    3 Node 2 Item A Item B Item C Item D Item E Item F Targeting Item a ID Item B ID Item a ID Item F ID Item D ID Item B ID Cache (size=4) Item A Item B Item F X Y Z
  66. Solution2 - Concentration of Targeting Information Redis Node 1 Node

    3 Node 2 Item A Item B Item C Item D Item E Item F Targeting Item a ID Item B ID Item a ID Item F ID Item D ID Item B ID Cache (size=4) Item A Item B Item F Item D X Y Z
  67. Solution2 - Concentration of Targeting Information Redis Node 1 Node

    3 Node 2 Item A Item B Item C Item D Item E Item F Targeting Item a ID Item B ID Item a ID Item F ID Item D ID Item B ID Cache (size=4) Item A Item B Item F Item D Caffeine Cache time: 5s Eviction: size-based X Y Z
  68. Solution2 - Concentration of Targeting Information Redis Node 1 Node

    3 Node 2 Item A Item B Item C Item D Item E Item F Targeting Item a ID Item B ID Item a ID Item F ID Item D ID Item B ID Cache (size=4) Item A Item B Item F Item D Caffeine Cache time: 5s Eviction: size-based X Y Z
  69. Results Percentile Response Time Before After 99.9 352ms 67ms 99.0

    176ms 29ms 95.0 126ms 22ms 75.0 92ms 16ms
  70. Results Percentile Response Time Before After 99.9 352ms 67ms 99.0

    176ms 29ms 95.0 126ms 22ms 75.0 92ms 16ms 80% faster
  71. Prioritized Delivery Fetch Information Information Fetch Targeting Ranking Prioritized Contents

    Information Disaster information threshold Japanese earthquake scale >= 6
  72. Prioritized Delivery Fetch Information Information Fetch Targeting Ranking Prioritized Contents

    Information Disaster information threshold Japanese earthquake scale >= 6 10/7 earthquake scale = 5+
  73. In the design - Be prepared for errors in assumptions

    and unexpected behavior that can be easily controlled - Define system requirements for the system in numerical terms
  74. In the design - Be prepared for errors in assumptions

    and unexpected behavior that can be easily controlled - The growth of the service sometimes be a problem. And it usually comes just when you’ve forgotten about it. - Define system requirements for the system in numerical terms
  75. In the trouble - Logs and metrics are very important.

    If they are missing, add them as needed.
  76. In the trouble - We have to make hypotheses and

    test them one by one. - Logs and metrics are very important. If they are missing, add them as needed.
  77. In the trouble - We have to make hypotheses and

    test them one by one. - The evolution of technology bring us another difficulty. There is no silver bullet yet. - Logs and metrics are very important. If they are missing, add them as needed.