Caching | System Design Interview Concept

What is Caching?

A cache is a generic term commonly referring to a high-speed data storage layer which stores a subset of underlying data (the data to be "cached") to efficiently reuse previously retrieved or computed data. Depending on the context, caching can be different things. For example, modern CPUs typically have 3 layers of cache called L1, L2, and L3 to speedup accessing data in memory. Operating system also use free memory as cache for local file system. Memoization

In system design, caching normally means database caching and sometimes web caching. You can read about more caching use cases in this AWS's article.

Database Caching

Databases caching, such as Redis and Memcached, are mainly to reduce the frequency of database reads. Especially in the past when databases are stored on hard drive disks, random reading is slow and SSD or in-memory caching is very important.

Reading Cache

  • Cache-aside is the most common and simple way to use database cache. The web server will first try to read data from cache. If data does not exists in cache, the server will fetch data from the the database and save data to cache. But this method cannot handle data updates.

https://kroki.io/mermaid/svg/eNpLy8kvT85ILCpR8AniCk4tKkst0tW1qzHUUygpqlQoyVcoSk1MqXFOTM5IRZI20lPITFPIyy9RSMsvzUvRAatSSCvKz1VISapxSSxJTEosTo3WgLE0Y5E0G-spFCeWpYIMTwaZCzEdAKsnLxk=

  • Read-Through cache sits between the application and the database. The application does not interact with database directly. When there is a cache miss, cache fetches with the database itself. A real-world example of a Real-Through cache is Amazon's DynamoDB Accelerator (DAX)

https://kroki.io/mermaid/svg/eNpLy8kvT85ILCpR8AniCk4tKkst0tW1qzHUUyhKTUypcU5MzkjlApM2IHEjPYXMNIW8_BKFtPzSvBQdsCqFtKL8XIWUJIXEvBSF4sSy1BqXxJLEpMTi1GgNGEszFgB4hCQm

Updating Cache

  • Write-Through is a method that keeps data consistency between the cache and the database. Then for any data updates, the server updates the data in cache and database synchronously. This method keeps data consistency but may sacrifice writing performance.
  • Write-Back is similar to Write-Through, but updates the data in cache and database asynchronously to improve write performance. However, there might be data loss when the server crashes before the writing to database is done.

Redis/SQLite Demo

We will use a Flask app with SQLite as database and Redis as cache for this example. This is a Cache-aside demo and does not involve any writing.

First, let's generate some random data.

1# init.py
2import sqlite3
3import random
4
5con = sqlite3.connect('data.db')
6cur = con.cursor()
7size = 1000000
8
9# Create table
10cur.execute('''CREATE TABLE comments
11              (domain text, page int, content text)''')
12
13# Insert data
14for i in range(size):
15    cur.execute("insert into comments values (?, ?, ?)", ("algo.monster",
16                random.randint(0, size // 10), f'Comment number {i}'))
17
18con.commit()
19con.close()

Then write a flask server to query and return the data directly from SQLite.

1# server.py
2from datetime import time
3from flask import Flask, Response
4import time
5import sqlite3
6
7app = Flask('cache')
8
9con = sqlite3.connect('data.db', check_same_thread=False)
10
11@app.route('/')
12def hello_world():
13    return 'Hello!\n'
14
15@app.route('/<id>')
16def page(id):
17    content = f'Comments from page {id}:\n'
18    start = time.time()
19
20    cur = con.cursor()
21    cur.execute("select * from comments where page=?", (id,))
22    comments = cur.fetchall()
23    for comment in comments:
24        content += comment[2] + '\n'
25
26    cost = time.time() - start
27    content += f'Time cost: {cost}\n'
28    return Response(content, mimetype='text/plain')
29
30if __name__ == '__main__':
31    app.run(host='127.0.0.1', port=5000)

Without cache, the flask web server would query SQLite database every request, which takes about 0.06 second for now. This is not very slow, but now ideal if our dataset will grow later.

1Comments from page 0:
2Comment number 20016
3Comment number 22854
4Comment number 126622
5Comment number 231155
6Comment number 248396
7Comment number 387808
8Time cost: 0.06520414352416992

Now, let's add Redis to save the queries from SQLite in the cache, and indicate whether we hit the cache in the response.

1# server.py
2from datetime import time
3import json
4from flask import Flask, Response
5import time
6import sqlite3
7import redis
8
9app = Flask('cache')
10
11r = redis.Redis(host='localhost', port=6379, db=0)
12con = sqlite3.connect('data.db', check_same_thread=False)
13
14@app.route('/')
15def hello_world():
16    return 'Hello!\n'
17
18@app.route('/<id>')
19def page(id):
20    content = f'Comments from page {id}:\n'
21    start = time.time()
22    comments = []
23
24    if r.exists(id):
25        content += 'Cache: hit\n'
26        comments = json.loads(r.get(id))
27    else:
28        content += 'Cache: miss\n'
29        cur = con.cursor()
30        cur.execute("select * from comments where page=?", (id,))
31        comments = cur.fetchall()
32        r.set(id, json.dumps(comments))
33
34    for comment in comments:
35        content += comment[2] + '\n'
36
37    cost = time.time() - start
38    content += f'Time cost: {cost}\n'
39    return Response(content, mimetype='text/plain')
40
41if __name__ == '__main__':
42    app.run(host='127.0.0.1', port=5000)

The response of the first request still takes about 0.06 second since our cache is empty at the beginning.

1Comments from page 0:
2Cache: miss
3Comment number 20016
4Comment number 22854
5Comment number 126622
6Comment number 231155
7Comment number 248396
8Comment number 387808
9Time cost: 0.06280922889709473

For future requests, the flask server will use Redis directly without accessing the SQLite server, and it only takes about 0.001 second, which is a huge improvement on performance. (Duh! Reading from memory is much faster than reading from Disk).

1Comments from page 0:
2Cache: hit
3Comment number 20016
4Comment number 22854
5Comment number 126622
6Comment number 231155
7Comment number 248396
8Comment number 387808
9Time cost: 0.0015978813171386719

HTTP caching | Content Delivery Network (CDN)

For web sites and applications, many resources like JavaScript files and CSS files are static and can be reused, so HTTP caching can improved web performance.

There are 2 kinds of HTTP caches.

  • A shared cache, indicated by header Cache-Control: public, is the cache used by CDN and can be used by more than one user.
  • A private cache, indicated by header Cache-Control: private, is the cache used by user's browser that can be used by only one user.

https://algomonster.s3.us-east-2.amazonaws.com/system_design/http_cache_type.png

You can read more about HTTP caching on MDN.