System Design Topics

A service is scalable if increasing the resources in a system, results in increased performance proportionally to resources added.

Generally, increasing performance means serving more units of work, or larger units of work, such as when datasets grow.

• Scalability is the capability of a system, process, or a network to grow and manage increased demand. Any distributed system that can continuously evolve in order to support the growing amount of work is considered to be scalable.
• A system may have to scale because of many reasons like increased data volume or increased amount of work, e.g., number of transactions. A scalable system would like to achieve this scaling without performance loss.
• Generally, the performance of a system, although designed (or claimed) to be scalable, declines with the system size due to the management or environment cost. For instance, network speed may become slower because machines tend to be far apart from one another. More generally, some tasks may not be distributed, either because of their inherent atomic nature or because of some flaw in the system design. At some point, such tasks would limit the speed-up obtained by distribution. A scalable architecture avoids this situation and attempts to balance the load on all the participating nodes evenly.

• By definition, reliability is the probability a system will fail in a given period.
• In simple terms, a distributed system is considered reliable if it keeps delivering its services even when one or several of its software or hardware components fail. Reliability represents one of the main characteristics of any distributed system, since in such systems any failing machine can always be replaced by another healthy one, ensuring the completion of the requested task.
• Take the example of a large electronic commerce store (like Amazon), where one of the primary requirement is that any user transaction should never be canceled due to a failure of the machine that is running that transaction. For instance, if a user has added an item to their shopping cart, the system is expected not to lose it. A reliable distributed system achieves this through redundancy of both the software components and data. If the server carrying the user’s shopping cart fails, another server that has the exact replica of the shopping cart should replace it.
• Obviously, redundancy has a cost and a reliable system has to pay that to achieve such resilience for services by eliminating every single point of failure.

• By definition, availability is the time a system remains operational to perform its required function in a specific period. It is a simple measure of the percentage of time that a system, service, or a machine remains operational under normal conditions.
• An aircraft that can be flown for many hours a month without much downtime can be said to have a high availability. Availability takes into account maintainability, repair time, spares availability, and other logistics considerations. If an aircraft is down for maintenance, it is considered not available during that time.
• Reliability is availability over time considering the full range of possible real-world conditions that can occur. An aircraft that can make it through any possible weather safely is more reliable than one that has vulnerabilities to possible conditions.

• To understand how to measure the efficiency of a distributed system, let’s assume we have an operation that runs in a distributed manner and delivers a set of items as result. Two standard measures of its efficiency are the response time (or latency) that denotes the delay to obtain the first item and the throughput (or bandwidth) which denotes the number of items delivered in a given time unit (e.g., a second). The two measures correspond to the following unit costs:
• Number of messages globally sent by the nodes of the system regardless of the message size.
• Size of messages representing the volume of data exchanges.
• The complexity of operations supported by distributed data structures (e.g., searching for a specific key in a distributed index) can be characterized as a function of one of these cost units.
• Generally speaking, the analysis of a distributed structure in terms of ‘number of messages’ is over-simplistic. It ignores the impact of many aspects, including the network topology, the network load, and its variation, the possible heterogeneity of the software and hardware components involved in data processing and routing, etc. However, it is quite difficult to develop a precise cost model that would accurately take into account all these performance factors; therefore, we have to live with rough but robust estimates of the system behavior.

• Another important consideration while designing a distributed system is how easy it is to operate and maintain. Serviceability or manageability is the simplicity and speed with which a system can be repaired or maintained; if the time to fix a failed system increases, then availability will decrease.
• Things to consider for manageability are the ease of diagnosing and understanding problems when they occur, ease of making updates or modifications, and how simple the system is to operate (i.e., does it routinely operate without failure or exceptions?).

Early detection of faults can decrease or avoid system downtime. For example, some enterprise systems can automatically call a service center (without human intervention) when the system experiences a system fault.

• Horizontal scaling means that you scale by adding more servers into your pool of resources whereas Vertical scaling means that you scale by adding more power (CPU, RAM, Storage, etc.) to an existing server.
• With horizontal-scaling it is often easier to scale dynamically by adding more machines into the existing pool; Vertical-scaling is usually limited to the capacity of a single server and scaling beyond that capacity often involves downtime and comes with an upper limit.
• Good examples of horizontal scaling are Cassandra and MongoDB as they both provide an easy way to scale horizontally by adding more machines to meet growing needs.
• Similarly, a good example of vertical scaling is MySQL as it allows for an easy way to scale vertically by switching from smaller to bigger machines. However, this process often involves downtime.

Vertical scaling vs. Horizontal scaling

• If a system is reliable, it is available. However, if it is available, it is not necessarily reliable. In other words, high reliability contributes to high availability, but it is possible to achieve a high availability even with an unreliable product by minimizing repair time and ensuring that spares are always available when they are needed.
• Let’s take the example of an online retail store that has 99.99% availability for the first two years after its launch. However, the system was launched without any information security testing. The customers are happy with the system, but they don’t realize that it isn’t very reliable as it is vulnerable to likely risks. In the third year, the system experiences a series of information security incidents that suddenly result in extremely low availability for extended periods of time. This results in reputational and financial damage to the customers.

• you can only have two out of the following three guarantees across a write/read pair:

In other words a distributed system only support two of the following guarantees:

• Failover and Replication

Calculating Availability

Availability (Total) = Availability (Foo) * Availability (Bar)

Availability (Total) = 1 - (1 - Availability (Foo)) * (1 - Availability (Bar))

• a single unit of logic or work, sometimes made up of multiple operations.
• Example: a transfer from one bank account to another: the complete transaction requires subtracting the amount to be transferred from one account and adding that same amount to the other.

• Consistency over availability

MySQL, Oracle, MS SQL Server, SQLite, Postgres, and MariaDB

• availability over consistency.

• Explanation of base terminology
• NoSQL databases a survey and decision guidance
• Scalability
• Introduction to NoSQL
• NoSQL patterns

• SQL stores data in tables where each row represents an entity and each column represents a data point about that entity; for example, if we are storing a car entity in a table, different columns could be ‘Color’, ‘Make’, ‘Model’, and so on.
• NoSQL databases have different data storage models. The main ones are key-value, document, graph, and columnar. We will discuss differences between these databases below.

• In SQL, each record conforms to a fixed schema, meaning the columns must be decided and chosen before data entry and each row must have data for each column. The schema can be altered later, but it involves modifying the whole database and going offline.
• In NoSQL, schemas are dynamic. Columns can be added on the fly and each ‘row’ (or equivalent) doesn’t have to contain data for each ‘column.’

• SQL databases use SQL (structured query language) for defining and manipulating the data, which is very powerful. In a NoSQL database, queries are focused on a collection of documents. Sometimes it is also called UnQL (Unstructured Query Language). Different databases have different syntax for using UnQL.

• In most common situations, SQL databases are vertically scalable, i.e., by increasing the horsepower (higher Memory, CPU, etc.) of the hardware, which can get very expensive. It is possible to scale a relational database across multiple servers, but this is a challenging and time-consuming process.
• On the other hand, NoSQL databases are horizontally scalable, meaning we can add more servers easily in our NoSQL database infrastructure to handle a lot of traffic. Any cheap commodity hardware or cloud instances can host NoSQL databases, thus making it a lot more cost-effective than vertical scaling. A lot of NoSQL technologies also distribute data across servers automatically.

• The vast majority of relational databases are ACID compliant. So, when it comes to data reliability and safe guarantee of performing transactions, SQL databases are still the better bet.Most of the NoSQL solutions sacrifice ACID compliance for performance and scalability.

• Structured, relational data
• If your business is not experiencing massive growth that would require more servers and if you’re only working with data that is consistent, then there may be no reason to use a system designed to support a variety of data types and high traffic volume.
• Static or Strict schema
• Relational data
• Need for complex joins
• Transactions
• Clear patterns for scaling
• More established: developers, community, code, tools, etc
• Lookups by index are very fast

for e-commerce and financial applications, an ACID-compliant database remains the preferred option.

• Semi-structured, non relational data, lots of it
• Dynamic or flexible schema
• No need for complex joins
• Store many TB (or PB) of data
• Very data intensive workload
• Very high throughput for IOPS
• Making the most of cloud computing and storage. Cloud-based storage is an excellent cost-saving solution but requires data to be easily spread across multiple servers to scale up. Many NoSQL data bases like Cassandra come out ready to scale right out of the box
• Rapid development. NoSQL is extremely useful for rapid development as it doesn’t need to be prepped ahead of time. If you’re working on quick iterations of your system which require making frequent updates to the data structure without a lot of downtime between versions, a relational database will slow you down.

• Rapid ingest of clickstream and log data
• Leaderboard or scoring data
• Temporary data, such as a shopping cart
• Frequently accessed (‘hot’) tables
• Metadata/lookup tables

• Scaling up to your first 10 million users
• SQL vs NoSQL differences

Source: Transitioning from RDBMS to NoSQL

• It is a technique to break up a big database (DB) into many smaller parts. It is the process of splitting up a DB/table across multiple machines to improve the manageability,

The justification for data partitioning is that, after a certain scale point, it is cheaper and more feasible to scale horizontally by adding more machines than to grow it vertically by adding beefier servers.

‣

Horizontal Partitioning (Sharding)

‣

What is database sharding? What are the tradeoffs when sharding a database? How is it usually implemented?

• In this scheme, we put different rows into different tables.
• Sharding distributes data across different databases such that each database can only manage a subset of the data.
• For example, if we are storing different places in a table, we can decide that locations with ZIP codes less than 10000 are stored in one table and places with ZIP codes greater than 10000 are stored in a separate table. This is also called a range based partitioning as we are storing different ranges of data in separate tables.

‣

Taking a users database as an example, as the number of users increases, more shards are added to the cluster.

Source: Scalability, availability, stability, patterns

‣

👍Advantage(s): sharding

• Similar to the advantages of federation, sharding results in less read and write traffic, less replication, and more cache hits.
• Index size is also reduced, which generally improves performance with faster queries.
• If one shard goes down, the other shards are still operational, although you’ll want to add some form of replication to avoid data loss.
• Like federation, there is no single central master serializing writes, allowing you to write in parallel with increased throughput.

‣

👎Disadvantage(s): sharding

• The key problem with this approach is that if the value whose range is used for partitioning isn’t chosen carefully, then the partitioning scheme will lead to unbalanced servers. In the previous example, splitting location based on their zip codes assumes that places will be evenly distributed across the different zip codes. This assumption is not valid as there will be a lot of places in a thickly populated area like Manhattan as compared to its suburb cities.
• I.O.W. Data distribution can become lopsided in a shard. For example, a set of power users on a shard could result in increased load to that shard compared to others.
• Rebalancing adds additional complexity. A sharding function based on consistent hashing can reduce the amount of transferred data.
• You’ll need to update your application logic to work with shards, which could result in complex SQL queries.
• Joining data from multiple shards is more complex.
• Sharding adds more hardware and additional complexity.

• Common ways to shard a table (of users) is either through the user’s last name initial or the user’s geographic location.

‣

Source: Horizontally Partitioning data based on a partition key

In this example, product inventory data is divided into shards based on the product key. Each shard holds the data for a contiguous range of shard keys (A-G and H-Z), organized alphabetically. Sharding spreads the load over more computers, which reduces contention and improves performance.

‣

Source(s) and further reading: sharding

• The coming of the shard
• Shard database architecture
• Consistent hashing

‣

Functional Partitioning (Federation)

‣

What is a federated database? What are some tradeoffs with a federated database?

• Federation (or functional partitioning) splits up databases by function.

‣

For example, instead of a single, monolithic database, you could have three databases: forums, users, and products.

Source: Scaling up to your first 10 million users

‣

👍Advantage(s): federation

• Results in less read and write traffic to each database and therefore less replication lag.
• Smaller databases result in more data that can fit in memory, which in turn results in more cache hits due to improved cache locality.
• With no single central master serializing writes you can write in parallel, increasing throughput.

‣

👎Disadvantage(s): federation

• Federation is not effective if your schema requires huge functions or tables.
• You’ll need to update your application logic to determine which database to read and write.
• Joining data from two databases is more complex with a server link.
• Federation adds more hardware and additional complexity.

‣

Source(s) and further reading: federation

• Scaling up to your first 10 million users

Solutions

On a partitioned database, there are certain extra constraints on the different operations that can be performed. Most of these constraints are due to the fact that operations across multiple tables or multiple rows in the same table will no longer run on the same server. Below are some of the constraints and additional complexities introduced by partitioning:

• In most systems, reads can heavily outnumber writes 100:1 or even 1000:1. So a read resulting in a complex database join can be very expensive, spending a significant amount of time on disk operations.
• Denormalization attempts to improve read performance at the expense of some write performance. Redundant copies of the data are written in multiple tables to avoid expensive joins.

In practice, RDBMS such as PostgreSQL and Oracle support materialized views which handle the work of storing redundant information and keeping redundant copies consistent.

• SQL tuning is a broad topic and many books have been written as reference.

‣

What are some SQL tuning techniques?

‣

Use good indices

• One of the very first things you should turn to when that (when db performance is no longer satisfactory) happens is database indexing.
• The goal of creating an index on a particular table in a database is to make it faster to search through the table and find the row or rows that we want. Indexes can be created using one or more columns of a database table, providing the basis for both rapid random lookups and efficient access of ordered records.

‣

Example: A library catalog

A library catalog is a register that contains the list of books found in a library. The catalog is organized like a database table generally with four columns: book title, writer, subject, and date of publication.

There are usually two such catalogs: one sorted by the book title and one sorted by the writer name.

That way, you can either think of a writer you want to read and then look through their books or look up a specific book title you know you want to read in case you don’t know the writer’s name.

These catalogs are like indexes for the database of books. They provide a sorted list of data that is easily searchable by relevant information.

Simply saying, an index is a data structure that can be perceived as a table of contents that points us to the location where actual data lives. So when we create an index on a column of a table, we store that column and a pointer to the whole row in the index.

Let’s assume a table containing a list of books, the following diagram shows how an index on the ‘Title’ column looks like:

‣

Just like a traditional relational data store, we can also apply this concept to larger datasets. The trick with indexes is that we must carefully consider how users will access the data.

In the case of data sets that are many terabytes in size, but have very small payloads (e.g., 1 KB), indexes are a necessity for optimizing data access.

Finding a small payload in such a large dataset can be a real challenge, since we can’t possibly iterate over that much data in any reasonable time. Furthermore, it is very likely that such a large data set is spread over several physical devices—this means we need some way to find the correct physical location of the desired data. Indexes are the best way to do this.

• Columns that you are querying (SELECT, GROUP BY, ORDER BY, JOIN) could be faster with indices.
• Indices are usually represented as self-balancing B-tree that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time.
• Placing an index can keep the data in memory, requiring more space.
• Writes could also be slower since the index also needs to be updated.
• When loading large amounts of data, it might be faster to disable indices, load the data, then rebuild the indices.

‣

How do Indexes decrease write performance?

An index can dramatically speed up data retrieval but may itself be large due to the additional keys, which slow down data insertion & update.

When adding rows or making updates to existing rows for a table with an active index, we not only have to write the data but also have to update the index. This will decrease the write performance. This performance degradation applies to all insert, update, and delete operations for the table. For this reason, adding unnecessary indexes on tables should be avoided and indexes that are no longer used should be removed. To reiterate, adding indexes is about improving the performance of search queries. If the goal of the database is to provide a data store that is often written to and rarely read from, in that case, decreasing the performance of the more common operation, which is writing, is probably not worth the increase in performance we get from reading.

For more details, see Database Indexes.

‣

Tighten up the schema

• MySQL dumps to disk in contiguous blocks for fast access.
• Use CHAR instead of VARCHAR for fixed-length fields.
• CHAR effectively allows for fast, random access, whereas with VARCHAR, you must find the end of a string before moving onto the next one.
• Use TEXT for large blocks of text such as blog posts. TEXT also allows for boolean searches. Using a TEXT field results in storing a pointer on disk that is used to locate the text block.
• Use INT for larger numbers up to 2^32 or 4 billion.
• Use DECIMAL for currency to avoid floating point representation errors.
• Avoid storing large BLOBS, store the location of where to get the object instead.
• VARCHAR(255) is the largest number of characters that can be counted in an 8 bit number, often maximizing the use of a byte in some RDBMS.
• Set the NOT NULL constraint where applicable to improve search performance.

‣

Partition tables

• Break up a table by putting hot spots in a separate table to help keep it in memory.

‣

Tune the query cache

• In some cases, the query cache could lead to performance issues.

‣

Avoid expensive joins

• Denormalize where performance demands it.

‣

Source(s) and further reading: SQL tuning

• Tips for optimizing MySQL queries
• Is there a good reason i see VARCHAR(255) used so often?
• How do null values affect performance?
• Slow query log

• You need all of the data to arrive intact
• You want to automatically make a best estimate use of the network throughput

• You need the lowest latency
• Late data is worse than loss of data
• You want to implement your own error correction

• Networking for game programming
• Key differences between TCP and UDP protocols
• Difference between TCP and UDP
• Transmission control protocol
• User datagram protocol
• Scaling memcache at Facebook

• A basic HTTP request consists of a verb (method) + a resource (endpoint).

‣

PUT vs. PATCH request?

Long-Polling, WebSockets, and Server-Sent Events are popular communication protocols between a client like a web browser and a web server. First, let’s start with understanding what a standard HTTP web request looks like.

‣

HTTP Long-Polling

• This is a variation of the traditional polling technique that allows the server to push information to a client whenever the data is available.
• With Long-Polling, the client requests information from the server exactly as in normal polling, but with the expectation that the server may not respond immediately.
• That’s why this technique is sometimes referred to as a “Hanging GET”.
• If the server does not have any data available for the client, instead of sending an empty response, the server holds the request and waits until some data becomes available.
• Once the data becomes available, a full response is sent to the client. The client then immediately re-request information from the server so that the server will almost always have an available waiting request that it can use to deliver data in response to an event.

‣

The life cycle of an application using HTTP Long-Polling is as follows:

1. The client makes an initial request using regular HTTP and then waits for a response.
2. The server delays its response until an update is available or a timeout has occurred.
3. When an update is available, the server sends a full response to the client.
4. The client typically sends a new long-poll requst, either immediately upon receiving a response or after a pause to allow an acceptable latency period.
5. Each Long-Poll request has a timeout. The client has to reconnect periodically after the connection is closed due to timeouts.

Caption: Long Polling Protocol

‣

WebSockets

• WebSocket is a computer communications protocol that provides Full duplex communication channels over a single persistent TCP connection.
• It provides a persistent connection between a client and a server that both parties can use to start sending data at any time.
• 👍 The WebSocket protocol enables communication between a client and a server with lower overheads, facilitating real-time data transfer from and to the server.
• This is made possible by providing a standardized way for the server to send content to the browser without being asked by the client and allowing for messages to be passed back and forth while keeping the connection open.
• In this way, a two-way (bi-directional) ongoing conversation can take place between a client and a server.

‣

How do WebSockets work?

• The client establishes a WebSocket connection through a process known as the WebSocket handshake.
• If the process succeeds, then the server and client can exchange data in both directions at any time.

Caption: WebSockets Protocol

‣

WebSocket Handshake

‣

1. Client handshake request

• The client sends a regular HTTP request with some special headers like so:

What do these headers in a Client handshake request mean?

‣

Connection: Upgrade

• signals that the client would like to change the protocol.

‣

Upgrade: websocket

• the requested protocol is “websocket"

‣

Sec-WebSocket-Key:

• a random browser-generated key for security.

‣

Sec-WebSocket-Version:

• WebSocket protocol version, 13 is the current one.

‣

2. Server handshake response

• The server will respond with an HTTP Response like below.
• The response code should be 101

‣

3. Success

After the client receives the server response, the WebSocket connection is open to start transmitting data.

‣

Server-Sent Events (SSEs)

• Server-Sent Events (SSE) is a server push technology enabling a client to receive automatic updates from a server via HTTP connection.
• Under SSEs the client establishes a persistent and long-term connection with the server. The server uses this connection to send data to a client.
• 👎 If the client wants to send data to the server, it would require the use of another technology/protocol to do so.

‣

The flow of events of SSE

1. Client requests data from a server using regular HTTP.
2. The requested webpage opens a connection to the server.
3. The server sends the data to the client whenever there’s new information available.

• SSEs are best when we need real-time traffic from the server to the client or if the server is generating data in a loop and will be sending multiple events to the client.

Caption: Server Sent Events Protocol

• Do you really know why you prefer REST over RPC
• When are RPC-ish approaches more appropriate than REST?
• REST vs JSON-RPC
• Debunking the myths of RPC and REST
• What are the drawbacks of using REST
• Crack the system design interview
• Thrift
• Why REST for internal use and not RPC

• DNS is the phone book of the internet. A Domain Name System (DNS) translates a domain name such as www.espn.com to an IP address.

• hierarchical
• authoritative

Source: DNS security presentation

1. Browser checks if the domain is in its cache. (to see the DNS Cache in Chrome, go to chrome://net-internals/#dns).
2. If not found, the browser calls gethostbyname library function (varies by OS) to do the lookup.
3. gethostbyname checks if the hostname can be resolved by reference in the local hosts file (whose location varies by OS) before trying to resolve the hostname through DNS.
4. If gethostbyname does not have it cached nor can find it in the hosts file then it makes a request to the DNS server configured in the network stack.
• This is typically the local router or the ISP's caching DNS server.
5. If the DNS server is on the same subnet the network library follows the ARP process below for the DNS server.
6. If the DNS server is on a different subnet, the network library follows the ARP process below for the default gateway IP.

• Services such as CloudFlare and Route 53 provide managed DNS services

• Latency-based
• Geolocation-based

• Accessing a DNS server introduces a slight delay, although mitigated by caching described above.
• DNS server management could be complex and is generally managed by governments, ISPs, and large companies.
• DNS services have recently come under DDoS attack, preventing users from accessing websites such as Twitter without knowing Twitter’s IP address(es).
• Lower level DNS servers cache mappings, which could become stale due to DNS propagation delays.

• DNS architecture
• Wikipedia
• DNS articles
• https://en.wikipedia.org/wiki/List_of_DNS_record_types#Resource_records

Source: OSI 7 layer model

• Load balancing makes it easier for system administrators to handle incoming requests while decreasing wait time for users.
• System administrators experience fewer failed or stressed components. Instead of a single device performing a lot of work, load balancing has several devices perform a little bit of work.

• Decrypt incoming requests and encrypt server responses so backend servers do not have to perform these potentially expensive operations
• Removes the need to install X.509 certificates on each server

Issue cookies and route a specific client’s requests to same instance if the web apps do not keep track of sessions

• Round robin or weighted round robin
• NGINX architecture
• HAProxy architecture guide
• Scalability
• Wikipedia
• Layer 4 load balancing
• Layer 7 load balancing
• ELB listener config
• Round Robin vs Weight Round Robin
• Following links have some good discussion about load balancers: [1] What is load balancing [2] Introduction to architecting systems [3] Load balancing

• improves performance and availability.
• Scaling out using commodity machines is more cost efficient and results in higher availability than scaling up a single server on more expensive hardware, called Vertical Scaling.
• It is also easier to hire for talent working on commodity hardware than it is for specialized enterprise systems.

• Scaling horizontally introduces complexity and involves cloning servers
• Servers should be stateless: they should not contain any user-related data like sessions or profile pictures
• Sessions can be stored in a centralized data store such as a database (SQL, NoSQL) or a persistent cache (Redis, Memcached)
• Downstream servers such as caches and databases need to handle more simultaneous connections as upstream servers scale out

Source: Scalable system design patterns

• Web servers can also cache requests from clients, returning responses without having to contact application servers.

• Placing a cache directly on a request layer node enables the local storage of response data.
• Each time a request is made to the service, the node will quickly return local cached data if it exists.
• If it is not in the cache, the requesting node will query the data from disk.
• The cache on one request layer node could also be located both in memory (which is very fast) and on the node’s local disk (faster than going to network storage).

• There are three types of database caches
1. Database Integrated Caches: Like Postgres' "Shared Buffer Cache" or "Amazon Aurora"
• Many databases usually have some caching configuration by default, which optimized for a generic use case.
• Tweaking these settings for specific usage patterns can boost performance.
2. Local Caches: A local cache stores your frequently used data within your application.
3. Remote Caches: Caches stored on dedicated servers built upon NoSQL stores (Redis, Memcached)

• While caching is fantastic, it does require some maintenance for keeping cache coherent with the source of truth (e.g., database). If the data is modified in the database, it should be invalidated in the cache; if not, this can cause inconsistent application behavior.
• Solving this problem is known as cache invalidation; there are three main schemes that are used:

‣

What are some different cache invalidation/update strategies?

‣

Cache-aside (AKA: Lazy Loading): How does it work? Explain it with a diagram. What are the advantages and disadvantages?

Source: From cache to in-memory data grid

• 🔑 The application is responsible for reading and writing from storage.
• So the cache does not interact with storage directly.
• AKA lazy-loading

‣

👍 Advantage(s): cache-aside

• Subsequent reads of data added to cache are fast.
• Only requested data is cached, which avoids filling up the cache with data that isn’t requested.

‣

👎 Disadvantage(s): cache-aside

• Each cache miss results in three trips, which can cause a noticeable delay.
• Data can become stale if it is updated in the database.
• This issue is mitigated by setting a time-to-live (TTL) which forces an update of the cache entry, or by using write-through.
• When a node fails, it is replaced by a new, empty node, increasing latency.

‣

Algorithm & Python Implementation: Cache Aside

1. Look for entry in cache, resulting in a cache miss
2. Load entry from the database
3. Add entry to cache
4. Return

‣

Implementation

Copy

def get_user(self, user_id):
    user = cache.get("user.{0}", user_id)
    if user is None:
        user = db.query("SELECT * FROM users WHERE user_id = {0}", user_id)
        if user is not None:
            key = "user.{0}".format(user_id)
            cache.set(key, json.dumps(user))
    return user

‣

What technology can be used to do this?

Memcached is generally used in this manner.

‣

Write-through: How does it work? Explain it with a diagram. What are the advantages and disadvantages?

Source: Scalability, availability, stability, patterns

• 🔑 The cache is responsible for reading and writing to storage.
• Under this scheme, data is written into the cache and the corresponding database at the same time.
• The cached data allows for fast retrieval and, since the same data gets written in the permanent storage, we will have complete data consistency between the cache and the storage. Also, this scheme ensures that nothing will get lost in case of a crash, power failure, or other system disruptions.

‣

👍 Advantage(s): write-through

• Write-through is a slow overall operation due to the write operation, but subsequent reads of just written data are fast.
• Users are generally more tolerant of latency when updating data than reading data.
• Data in the cache is not stale.

‣

👎 Disadvantage(s): write-through

• Write-through is a slow overall operation due to the write operation, since every write operation must be done twice before returning success to the client, this scheme has the disadvantage of higher latency for write operations.
• When a new node is created due to failure or scaling, the new node will not cache entries until the entry is updated in the database.
• Cache-aside in conjunction with write through can mitigate this issue.
• Most data written to the cache might never be read, which can be minimized with a TTL.

‣

Algorithm & Python Implementation: Write-through

1. Application adds/updates entry in cache
• The application uses the cache as the main data store, reading and writing data to it.
2. Cache is responsible for reading and synchronously writing to the database:
3. Return

‣

Implementation

Application code:

Copy

set_user(12345, {"foo":"bar"})

Cache code:

Copy

def set_user(user_id, values):
    user = db.query("UPDATE Users WHERE id = {0}", user_id, values)
    cache.set(user_id, user)

‣

Write-around cache: How does it work? Explain it with a diagram.

• This technique is similar to write through cache, but data is written directly to permanent storage, bypassing the cache.

‣

👍 Advantages(s):

• This can reduce or prevent the cache being flooded with write operations that will not subsequently be re-read,

‣

👎 Disadvantage(s):

• But has the disadvantage that a read request for recently written data will create a “cache miss” and must be read from slower back-end storage and experience higher latency.

‣

Write-behind (Write back): How does it work? Explain it with a diagram. What are the advantages and disadvantages?

Source: Scalability, availability, stability, patterns

• Under this scheme, data is written to cache alone and completion is immediately confirmed to the client.

In write-behind, the application does the following:

• Add/update/lookup entry in cache

‣

Asynchronously write entry to the data store, improving write performance

• The write to the permanent storage is done after specified intervals or under certain conditions.

‣

👍 Advantage(s): write-behind

• results in low latency and high throughput for write-intensive applications,

‣

👎 Disadvantage(s): write-behind

• however, this speed comes with the risk of data loss in case of a crash or other adverse event because the only copy of the written data is in the cache.
• It is more complex to implement write-behind than it is to implement cache-aside or write-through.

‣

Refresh-ahead: How does it work? Explain it with a diagram. What are the disadvantages?

Source: From cache to in-memory data grid

You can configure the cache to automatically refresh any recently accessed cache entry prior to its expiration.

‣

👍 Advantage(s): refresh-ahead

Refresh-ahead can result in reduced latency vs read-through if the cache can accurately predict which items are likely to be needed in the future.

‣

👎 Disadvantage(s): refresh-ahead

• Not accurately predicting which items are likely to be needed in the future can result in reduced performance than without refresh-ahead.

• Row level
• Query-level
• Fully-formed serializable objects
• Fully-rendered HTML

Whenever you query the database, hash the query as a key and store the result to the cache.

See your data as an object, similar to what you do with your application code. Have your application assemble the dataset from the database into a class instance or a data structure(s):

• Remove the object from cache if its underlying data has changed
• Allows for asynchronous processing: workers assemble objects by consuming the latest cached object

• receive, hold, and deliver messages.

Source: Intro to architecting systems for scale

• The user is not blocked and the job is processed in the background. During this time, the client might optionally do a small amount of processing to make it seem like the task has completed.
• For example, if posting a tweet, the tweet could be instantly posted to your timeline, but it could take some time before your tweet is actually delivered to all of your followers.

• Redis is useful as a simple message broker but messages can be lost.
• RabbitMQ is popular but requires you to adapt to the AMQP protocol and manage your own nodes.
• Amazon SQS is hosted but can have high latency and has the possibility of messages being delivered twice.

• receive tasks and their related data, runs them, then delivers their results.
• It support scheduling and can be used to run computationally-intensive jobs in the background.

• Celery has support for scheduling and primarily has python support.

• If queues start to grow significantly, the queue size can become larger than memory, resulting in cache misses, disk reads, and even slower performance.
• Back pressure can help by limiting the queue size, thereby maintaining a high throughput rate and good response times for jobs already in the queue. Once the queue fills up, clients get a server busy or HTTP 503 status code to try again later. Clients can retry the request at a later time, perhaps with exponential backoff.

1. It is NOT horizontally scalable. Whenever a new cache host is added to the system, all existing mappings are broken. It will be a pain point in maintenance if the caching system contains lots of data. Practically, it becomes difficult to schedule a downtime to update all caching mappings.
2. It may NOT be load balanced, especially for non-uniformly distributed data. In practice, it can be easily assumed that the data will not be distributed uniformly. For the caching system, it translates into some caches becoming hot and saturated while the others idle and are almost empty.

• Related to this discussion (of the application layer) are microservices, which can be described as a suite of independently deployable, small, modular services.
• Each service runs a unique process and communicates through a well-defined, lightweight mechanism to serve a business goal.

• Systems such as Consul, Etcd, and Zookeeper can help services find each other by keeping track of registered names, addresses, and ports.
• Health checks help verify service integrity and are often done using an HTTP endpoint.
• Both Consul and Etcd have a built in key-value store that can be useful for storing config values and other shared data.

• API security checklist
• Security guide for developers
• OWASP top ten