Systems Design
What to look for in a cloud hosting solution
If IPs are blacklisted, i.e. by the company you work for
Encryption of sensitive data
SSDs vs HDDs
The traditional spinning hard drive is the basic non-volatile storage on a computer. That is, information on it doesn't "go away" when you turn off the system, unlike data stored in RAM. (source)
A hard drive is essentially a metal platter with a magnetic coating that stores your data (source)
A read/write head on an arm accesses the data while the platters are spinning. (source)
An SSD performs the same basic function as a hard drive, but data is instead stored on interconnected flash-memory chips that retain the data even when there's no power flowing through them. (source)
SSDs are more expensive than hard drives in terms of dollar per gigabyte. (source)
Consumer SSDs are rarely found in capacities greater than 2TB, and those are expensive. (source)
SSD vs. HDD Speed This is where SSDs shine. An SSD-equipped PC will boot in far less than a minute, often in just seconds. (source)
Because hard drives rely on spinning platters, there is a limit to how small they can be manufactured. (source)
SSDs have no such limitation, so they can continue to shrink as time goes on. (source)
The overall takeaway? Hard drives win on price and capacity. SSDs work best if speed, ruggedness, form factor, noise, or fragmentation (technically, a subset of speed) are important factors to you. If it weren't for the price and capacity issues, SSDs would be the hands-down winner. (source)
DNS
Typically cached, with a TTL of a few hours or a day
So that you don't need to do a DNS lookup for the same site over and over, unnecessarily
Load balancing
The load balancer can have a public IP address, and route to the individual servers, which can have private IP addresses
Round robin
Downside: one user could be using one server very heavily, and now the load might be uneven. Especially since round robin will keep sending users to that server, even though it's under a heavy load.
Need to be careful about session data, if you're using it -- don't want session data on multiple servers, that could potentially be mismatched
Algorithms: Least connection, Least response time, Least bandwidth, Round robin, Weighted round-robin, IP hash (source)
The smart client is a client that takes a pool of service hosts and balances load across them, detects downed hosts, and avoids sending requests their way (source)
Hardware load balancers are specialized hardware deployed in-between the server and the client. (source)
Software load balancers generally implement a combination of one or more scheduling algorithms. (source)
Most load balancer programs are also reverse proxy servers, which simplifies web application server architecture. (source)
It often makes sense to deploy a reverse proxy even with just one web server or application server. (source)
Scaling
Vertical scaling has an upper limit -- you can't just keep scaling up an individual machine
Horizontal scaling has the added benefit of adding redundancy, for better availability
But, it's simpler to vertically scale
Scalability is simply measured by the number of requests an application can handle successfully. Once the application can no longer handle any more simultaneous requests, it has reached its scalability limit. (source)
You can scale these resources through a combination of adjustments to network bandwidth, CPU and physical memory requirements, and hard disk adjustments. (source)
Vertical scaling allows data to live on a single node, and scaling spreads the load through CPU and RAM resources for your machines. (source)
Small- and mid-sized companies most often use vertical scaling for their applications because it allows businesses to scale relatively quickly compared to using horizontal scaling. (source)
One drawback of vertical scaling is that it poses a higher risk for downtime and outages than horizontal scaling. (source)
Correctly provisioning your resources is the best way to ensure that upgrading was worth it and that your business will not experience the negative effects of vertical scaling. (source)
Horizontal scaling means adding more machines to the resource pool, rather than simply adding resources by scaling vertically. (source)
Horizontal scaling is favored by DevOps experts because it is done dynamically automatically — scaling based on the load for optimal performance. (source)
Both vertical and horizontal scaling can be performed automatically, also known as auto-scaling, as the actual process of scaling is not particularly difficult. (source)
Caching
Take advantage of the locality of reference principle: recently requested data is likely to be requested again. (source)
Exist at all levels in architecture, but often found at the level nearest to the front end. (source)
Caching consists of 1. precalculating results (e.g. the number of visits from each referring domain for the previous day) 2. pre-generating expensive indexes (e.g. suggested stories based on a user’s click history) 3. storing copies of frequently accessed data in a faster backend (e.g. Memcache instead of PostgreSQL. (source)
Layers of caching
2.1 Client-side. Use case: Accelerate retrieval of web content from websites (browser or device) Tech: HTTP Cache Headers, Browsers (source)
2.2 DNS Use case: Domain to IP Resolution Tech: DNS Servers Solutions: Amazon Route 53 (source)
2.3 Web Server Use case: Accelerate retrieval of web content from web/app servers. Manage Web Sessions (server-side) Tech: HTTP Cache Headers, CDNs, Reverse Proxies, Web Accelerators, Key/Value Stores Solutions: Amazon CloudFront, ElastiCache for Redis, ElastiCache for Memcached, Partner Solutions (source)
2.4 Application Use case: Accelerate application performance and data access Tech: Key/Value data stores, Local caches Solutions: Redis, Memcached (source)
If horizontally scaled, the nodes are going to have different caches. Which has implications WRT cache misses
They also might be redundantly cached, since they could be cached on different servers
Solutions for these ^: Global caches, distributed caches
If the node doesn't have something in the cache, it'll go to e.g. the database directly
2.5 Database Use case: Reduce latency associated with database query requests Tech: Database buffers, Key/Value data stores Solutions: The database usually includes some level of caching in a default configuration, optimized for a generic use case. (source)
2.6 Content Distribution Network (CDN) CDN Use case: Take the burden of serving static media off of your application servers and provide a geographic distribution. (source)
Cache invalidation / write policies
There are majorly three kinds of caching systems: Write-through cache, Write-around cache, Write-back cache. (source)
Write through cache: Where writes go through the cache and write is confirmed as success only if writes to DB and the cache BOTH succeed.
Pro: Fast retrieval, complete data consistency, robust to system disruptions.
Con: Higher latency for write operations. (source)
Write around cache: Where write directly goes to the DB, bypassing the cache.
Pro: This may reduce latency.
Con: However, it increases cache misses because the cache system reads the information from DB in case of a cache miss. As a result, this can lead to higher read latency in the case of applications that write and re-read the information quickly. Read must happen from slower back-end storage and experience higher latency. (source)
Write back cache: Where the write is directly done to the caching layer and the write is confirmed as soon as the write to the cache completes. The cache then asynchronously syncs this write to the DB.
Pro: This would lead to a really quick write latency and high write throughput for the write-intensive applications.
Con: However, there is a risk of losing the data in case the caching layer dies because the only single copy of the written data is in the cache. We can improve this by having more than one replica acknowledging the write in the cache. (source)
Cache eviction policies
First In First Out (FIFO): The cache evicts the first block accessed first without any regard to how often or how many times it was accessed before. (source)
Last In First Out (LIFO): The cache evicts the block accessed most recently first without any regard to how often or how many times it was accessed before. (source)
Least Recently Used (LRU): Discards the least recently used items first. (source)
Most Recently Used (MRU): Discards, in contrast to LRU, the most recently used items first. (source)
Least Frequently Used (LFU): Counts how often an item is needed. Those that are used least often are discarded first. (source)
Random Replacement (RR): Randomly selects a candidate item and discards it to make space when necessary. (source)
Other
Global caches: All the nodes use the same single cache space (a server or file store). Each of the application nodes queries the cache in the same way it would a local one. However, it is very easy to overwhelm a single global cache system as the number of clients and requests increase but is very effective in some architectures. (source)
Distributed caches: The cache is divided up using a consistent hashing function and each of its nodes owns part of the cached data. (source)
Redundancy and Replication
Duplication of critical data or services with the intention of increased reliability and availability of the system. (source)
Remove single points of failure and provide backups (e.g. server failover). (source)
Shared-nothing architecture: Each node can operate independently of one another. No central service managing state or orchestrating activities. New servers can be added without special conditions or knowledge. No single point of failure. (source)
Standby redundancy, also known as Backup Redundancy is when you have an identical secondary unit to back up the primary unit. (source)
The standby unit is not usually kept in sync with the primary unit, so it must reconcile its input and output signals on the takeover of the Device Under Control (DUC) (source)
You also need a third party to be the watchdog, which monitors the system to decide when a switchover condition is met and command the system to switch control to the standby unit and a voter. (source)
In Standby redundancy, there are two basic types, Cold Standby and Hot Standby. (source)
N Modular Redundancy, also known as Parallel Redundancy, refers to the approach of having multiply units running in parallel. All units are highly synchronized and receive the same input information at the same time. (source)
1:N is a design technique used where you have a single backup for multiple systems (source)
This technique offers redundancy at a much lower cost than the other models by using one standby unit for several primary units. (source)
Database Redundancy: Have more than one copy of your data in a database system. It can be either at the table level or at the field level. Usually, the copies are called a replica. (source)
Locally Redundant Storage (LRS) LRS ensures that your data stays within a single data center in your chosen region. Data is replicated three times. LRS is cheaper than the other types of redundancy and doesn’t provide protection against data center failures. (source)
Zone-Redundant Storage (ZRS) Only available for block blobs, ZRS keeps three copies of your data across two or three data centers, either within your chosen region or across two regions. (source)
Geo-Redundant Storage (GRS) This is the type of redundancy that Microsoft recommends by default, and it keeps six copies of your data. Three copies stay in the primary region, and the remaining three are replicated to a secondary region. (source)
Sharding / Partitioning
Sharding is the practice of optimizing database management systems by separating the rows or columns of a larger database table into multiple smaller tables. (source)
The new tables are called “shards” (or partitions), and each new table either has the same schema but unique rows (as is the case for “horizontal sharding”) or has a schema that is a proper subset of the original table’s schema (as is the case for “vertical sharding”). (source)
Sharding is a common concept in scalable database architectures. By sharding a larger table, you can store the new chunks of data, called logical shards, across multiple nodes to achieve horizontal scalability and improved performance. Once the logical shard is stored on another node, it is referred to as a physical shard. (source)
With massively parallel processing, you can take advantage of all the compute resources across your cluster for every query. (source)
Because the individual shards are smaller than the logical table as a whole, each machine has to scan fewer rows when responding to a query. (source)
Horizontal sharding is effective when queries tend to return a subset of rows that are often grouped together. For example, queries that filter data based on short date ranges are ideal for horizontal sharding since the date range will necessarily limit querying to only a subset of the servers. (source)
Vertical sharding is effective when queries tend to return only a subset of columns of the data. For example, if some queries request only names, and others request only addresses, then the names and addresses can be sharded onto separate servers. (source)
Sharded databases can offer higher levels of availability. (source)
Sharding and partitioning are both about breaking up a large data set into smaller subsets. The difference is that sharding implies the data is spread across multiple computers while partitioning does not. Partitioning is about grouping subsets of data within a single database instance. (source)
In many cases, the terms sharding and partitioning are even used synonymously, especially when preceded by the terms “horizontal” and “vertical.” Thus, “horizontal sharding” and “horizontal partitioning” can mean the same thing. (source)
Consistency - Every read receives the most recent write or an error
Availability - Every request receives a response, without guarantee that it contains the most recent version of the information
Partition tolerance required, due to unreliable nature of a network
Weak consistency: Reads may not see it, but doesn't matter. i.e. phone calls, realtime apps, video games
Eventual consistency: Reads will see latest typically after a few milliseconds. i.e. DNS and email
Strong consistency: Immediately accurate. i.e. RDBMSes and file systems
Availability patterns
Fail-over
Active-passive: Heartbeat from active to passive, if heartbeat breaks, passive handles the load
Active-active: Both servers are active and handling traffic
Disadvantages:
Fail-over adds more hardware and additional complexity.
There is a potential for loss of data if the active system fails before any newly written data can be replicated to the passive.
Availability
Measured in 9's (i.e. 99.99% is 4 9s)
Notes
A systems design interview is as much about communication with the interviewer (source)
One thing you should avoid is "just memorizing" the approaches of the problems. (source)
Links
Last updated