Tuesday, May 2, 2017

System Design Practice



https://github.com/donnemartin/system-design-primer/blob/master/solutions/system_design/scaling_aws/README.md
Design a system that scales to millions of users on AWS

Step 1: Outline use cases and constraints

Gather requirements and scope the problem. Ask questions to clarify use cases and constraints. Discuss assumptions.

Use cases

Solving this problem takes an iterative approach of: 1) Benchmark/Load Test, 2) Profile for bottlenecks 3) address bottlenecks while evaluating alternatives and trade-offs, and 4) repeat, which is good pattern for evolving basic designs to scalable designs.
Unless you have a background in AWS or are applying for a position that requires AWS knowledge, AWS-specific details are not a requirement. However, much of the principles discussed in this exercise can apply more generally outside of the AWS ecosystem.

We'll scope the problem to handle only the following use cases

  • User makes a read or write request
    • Service does processing, stores user data, then returns the results
  • Service needs to evolve from serving a small amount of users to millions of users
    • Discuss general scaling patterns as we evolve an architecture to handle a large number of users and requests
  • Service has high availability

Constraints and assumptions

State assumptions

  • Traffic is not evenly distributed
  • Need for relational data
  • Scale from 1 user to tens of millions of users
    • Denote increase of users as:
      • Users+
      • Users++
      • Users+++
      • ...
    • 10 million users
    • 1 billion writes per month
    • 100 billion reads per month
    • 100:1 read to write ratio
    • 1 KB content per write

Calculate usage

Clarify with your interviewer if you should run back-of-the-envelope usage calculations.
  • 1 TB of new content per month
    • 1 KB per write * 1 billion writes per month
    • 36 TB of new content in 3 years
    • Assume most writes are from new content instead of updates to existing ones
  • 400 writes per second on average
  • 40,000 reads per second on average
Handy conversion guide:
  • 2.5 million seconds per month
  • 1 request per second = 2.5 million requests per month
  • 40 requests per second = 100 million requests per month
  • 400 requests per second = 1 billion requests per month

Step 2: Create a high level design

Outline a high level design with all important components.
Imgur

Step 3: Design core components

Dive into details for each core component.

Use case: User makes a read or write request

Goals

  • With only 1-2 users, you only need a basic setup
    • Single box for simplicity
    • Vertical scaling when needed
    • Monitor to determine bottlenecks

Start with a single box

Use Vertical Scaling:
  • Simply choose a bigger box
  • Keep an eye on metrics to determine how to scale up
    • Use basic monitoring to determine bottlenecks: CPU, memory, IO, network, etc
    • CloudWatch, top, nagios, statsd, graphite, etc
  • Scaling vertically can get very expensive
  • No redundancy/failover
Trade-offs, alternatives, and additional details:

Start with SQL, consider NoSQL

The constraints assume there is a need for relational data. We can start off using a MySQL Database on the single box.
Trade-offs, alternatives, and additional details:

Assign a public static IP

  • Elastic IPs provide a public endpoint whose IP doesn't change on reboot
  • Helps with failover, just point the domain to a new IP

Use a DNS

Add a DNS such as Route 53 to map the domain to the instance's public IP.
Trade-offs, alternatives, and additional details:

Secure the web server

  • Open up only necessary ports
    • Allow the web server to respond to incoming requests from:
      • 80 for HTTP
      • 443 for HTTPS
      • 22 for SSH to only whitelisted IPs
    • Prevent the web server from initiating outbound connections

Step 4: Scale the design

Identify and address bottlenecks, given the constraints.

Users+

Imgur

Assumptions

Our user count is starting to pick up and the load is increasing on our single box. Our Benchmarks/Load Tests and Profiling are pointing to the MySQL Database taking up more and more memory and CPU resources, while the user content is filling up disk space.
We've been able to address these issues with Vertical Scaling so far. Unfortunately, this has become quite expensive and it doesn't allow for independent scaling of the MySQL Database and Web Server.

Goals

  • Lighten load on the single box and allow for independent scaling
    • Store static content separately in an Object Store
    • Move the MySQL Database to a separate box
  • Disadvantages
    • These changes would increase complexity and would require changes to the Web Server to point to the Object Store and the MySQL Database
    • Additional security measures must be taken to secure the new components
    • AWS costs could also increase, but should be weighed with the costs of managing similar systems on your own

Store static content separately

  • Consider using a managed Object Store like S3 to store static content
    • Highly scalable and reliable
    • Server side encryption
  • Move static content to S3
    • User files
    • JS
    • CSS
    • Images
    • Videos

Move the MySQL database to a separate box

  • Consider using a service like RDS to manage the MySQL Database
    • Simple to administer, scale
    • Multiple availability zones
    • Encryption at rest

Secure the system

  • Encrypt data in transit and at rest
  • Use a Virtual Private Cloud
    • Create a public subnet for the single Web Server so it can send and receive traffic from the internet
    • Create a private subnet for everything else, preventing outside access
    • Only open ports from whitelisted IPs for each component
  • These same patterns should be implemented for new components in the remainder of the exercise

Users++

Imgur

Assumptions

Our Benchmarks/Load Tests and Profiling show that our single Web Server bottlenecks during peak hours, resulting in slow responses and in some cases, downtime. As the service matures, we'd also like to move towards higher availability and redundancy.

Goals

  • The following goals attempt to address the scaling issues with the Web Server
    • Based on the Benchmarks/Load Tests and Profiling, you might only need to implement one or two of these techniques
  • Use Horizontal Scaling to handle increasing loads and to address single points of failure
    • Add a Load Balancer such as Amazon's ELB or HAProxy
      • ELB is highly available
      • If you are configuring your own Load Balancer, setting up multiple servers in active-active or active-passive in multiple availability zones will improve availability
      • Terminate SSL on the Load Balancer to reduce computational load on backend servers and to simplify certificate administration
    • Use multiple Web Servers spread out over multiple availability zones
    • Use multiple MySQL instances in Master-Slave Failover mode across multiple availability zones to improve redundancy
  • Separate out the Web Servers from the Application Servers
    • Scale and configure both layers independently
    • Web Servers can run as a Reverse Proxy
    • For example, you can add Application Servers handling Read APIs while others handle Write APIs
  • Move static (and some dynamic) content to a Content Delivery Network (CDN) such as CloudFront to reduce load and latency
Trade-offs, alternatives, and additional details:
  • See the linked content above for details

Users+++

Imgur
Note: Internal Load Balancers not shown to reduce clutter

Assumptions

Our Benchmarks/Load Tests and Profiling show that we are read-heavy (100:1 with writes) and our database is suffering from poor performance from the high read requests.

Goals

  • The following goals attempt to address the scaling issues with the MySQL Database
    • Based on the Benchmarks/Load Tests and Profiling, you might only need to implement one or two of these techniques
  • Move the following data to a Memory Cache such as Elasticache to reduce load and latency:
    • Frequently accessed content from MySQL
      • First, try to configure the MySQL Database cache to see if that is sufficient to relieve the bottleneck before implementing a Memory Cache
    • Session data from the Web Servers
      • The Web Servers become stateless, allowing for Autoscaling
    • Reading 1 MB sequentially from memory takes about 250 microseconds, while reading from SSD takes 4x and from disk takes 80x longer.1
  • Add MySQL Read Replicas to reduce load on the write master
  • Add more Web Servers and Application Servers to improve responsiveness
Trade-offs, alternatives, and additional details:
  • See the linked content above for details

Add MySQL read replicas

  • In addition to adding and scaling a Memory CacheMySQL Read Replicas can also help relieve load on the MySQL Write Master
  • Add logic to Web Server to separate out writes and reads
  • Add Load Balancers in front of MySQL Read Replicas (not pictured to reduce clutter)
  • Most services are read-heavy vs write-heavy
Trade-offs, alternatives, and additional details:

Users++++

Imgur

Assumptions

Our Benchmarks/Load Tests and Profiling show that our traffic spikes during regular business hours in the U.S. and drop significantly when users leave the office. We think we can cut costs by automatically spinning up and down servers based on actual load. We're a small shop so we'd like to automate as much of the DevOps as possible for Autoscaling and for the general operations.

Goals

  • Add Autoscaling to provision capacity as needed
    • Keep up with traffic spikes
    • Reduce costs by powering down unused instances
  • Automate DevOps
    • Chef, Puppet, Ansible, etc
  • Continue monitoring metrics to address bottlenecks
    • Host level - Review a single EC2 instance
    • Aggregate level - Review load balancer stats
    • Log analysis - CloudWatch, CloudTrail, Loggly, Splunk, Sumo
    • External site performance - Pingdom or New Relic
    • Handle notifications and incidents - PagerDuty
    • Error Reporting - Sentry

Add autoscaling

  • Consider a managed service such as AWS Autoscaling
    • Create one group for each Web Server and one for each Application Server type, place each group in multiple availability zones
    • Set a min and max number of instances
    • Trigger to scale up and down through CloudWatch
      • Simple time of day metric for predictable loads or
      • Metrics over a time period:
        • CPU load
        • Latency
        • Network traffic
        • Custom metric
    • Disadvantages
      • Autoscaling can introduce complexity
      • It could take some time before a system appropriately scales up to meet increased demand, or to scale down when demand drops

Users+++++

Imgur
Note: Autoscaling groups not shown to reduce clutter

Assumptions

As the service continues to grow towards the figures outlined in the constraints, we iteratively run Benchmarks/Load Tests and Profiling to uncover and address new bottlenecks.

Goals

We'll continue to address scaling issues due to the problem's constraints:
  • If our MySQL Database starts to grow too large, we might considering only storing a limited time period of data in the database, while storing the rest in a data warehouse such as Redshift
    • A data warehouse such as Redshift can comfortably handle the constraint of 1 TB of new content per month
  • With 40,000 average read requests per second, read traffic for popular content can be addressed by scaling the Memory Cache, which is also useful for handling the unevenly distributed traffic and traffic spikes
    • The SQL Read Replicas might have trouble handling the cache misses, we'll probably need to employ additional SQL scaling patterns
  • 400 average writes per second (with presumably significantly higher peaks) might be tough for a single SQL Write Master-Slave, also pointing to a need for additional scaling techniques
SQL scaling patterns include:
To further address the high read and write requests, we should also consider moving appropriate data to a NoSQL Database such as DynamoDB.
We can further separate out our Application Servers to allow for independent scaling. Batch processes or computations that do not need to be done in real-time can be done Asynchronously with Queues and Workers:
  • For example, in a photo service, the photo upload and the thumbnail creation can be separated:
    • Client uploads photo
    • Application Server puts a job in a Queue such as SQS
    • The Worker Service on EC2 or Lambda pulls work off the Queue then:
      • Creates a thumbnail
      • Updates a Database
      • Stores the thumbnail in the Object Store
https://github.com/donnemartin/system-design-primer/blob/master/solutions/system_design/query_cache/README.md

http://www.meetqun.net/thread-25679-1-1.html
设计Tiny URL,数据结构,能够add(), remove(), randomremove() in O(1)复杂度

设计Amazon Product Page, 就是在SQL里面一个产品有多个图片多个价格的话怎么设计数据库。然后后台提取数值render到页面上得时候,class怎么设计,服务器怎么安排之类的, 中间也有讨论怎样给suggest product,我提到可以建一个Product weighted graph, 然后用BFS

设计一个系统,监测24小时之内top 500的exceptions

设计dashboard to monitor the top shared url in the last 5 minutes

设计: 对于key,value pairs, 在给定的文件系统中实现 put,get,delete 的方法。其中key比较小,全部key可以放在内存中,value有的会比较大。已知一个文件系统,可以create files, delete files, sequentially scan file content, read file content randomly, append file content.. 

设计:已知一个函数,输入用户ID,可以返回该用户的所有友好(degree 1 friends),按好友ID从小到大排序。要求实现函数来输出返回一个用户的所有好友的好友(degree 2 friends), 以及 degree 3 friends。

设计 LinkedIn. 
search功能里inverted index 和data of user , data of company 怎么存,分别用Nosql还是sql?然后设计timeline, 问我push/pull模型在哪儿看的
design the backend of linkedin, 讨论各个service如何实现

设计 a notebook application like Evernote or Onenote, it should support search, collaboration
社交网站上的文章转发,如何设计系统可以得到实时的转发量榜单和weekly digest,要求数据库的设计,有人转发一个文章时request是什么样的,如何快速得到实时的转发量榜单,如何得到weekly digest等。

设计 a system to block malicious IPs

设计 a restful server with 4GB,  
given a request such as: http://seq=4?len=60?xxxxdata
the system will store the binary data with that sequence number
given a request: http://startseq=3?maxLen=100, the system returns all data objects with sequence >= 3 with total data length less equal than 100.
multiple clients calling simutaneous.
what data structure, concurrency, locking, etc..

设计Delay Scheduler,能够把task schedule在特定的时间执行。


Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts