Caching

A fundamental rule about computers is that the farther the data is from your computer, the longer it takes for your computer to retrieve it. For example, you can open a file that’s local to your computer more quickly than you can download information from the Internet. This is because the Internet consists of servers that are outside your computer, and it takes more time for your computer to obtain those servers’ data.

Let’s take a look at an example of how this can be a major deal for the software we write.

Imagine that we’re building an app that searches the web for the cheapest price available for various physical products. The user enters something like “Vroom-Master Vacuum Cleaner 3000,” and our app scours the Internet to find whichever online retailer is selling it for the cheapest price. Note that we’re not building a massive database that stores a gazillion products and their prices. Instead, our software is searching the web each time the user searches for a particular product. In a sense, the web is our “database.”

Now, say that the Vroom-Master’s latest model is becoming a hot fad; everyone you know is buying one. Suddenly, our app finds itself repeatedly searching the web for the best bargain for the Vroom-Master 3000. Assuming that stores are not constantly changing their prices at a rapid clip, it’s kind of a shame that our software has to search the web each and every time someone asks for the Vroom-Master 3000. Searching the web takes time! Wouldn’t it be nice if the app could remember information the first time it finds it and then not have to search the web again and again for the same information?

Luckily for us, that’s exactly what a cache does.

What Is a Cache?

A cache (pronounced “cash”) is simply a data container that takes data that was retrieved from a faraway source and stores it locally. (The word “cache” can also be used as a verb. That is, our computer can cache data it gets from the web.) Because the data is more local, we’ll be able to retrieve it more quickly in the future. The definition of “local” can change based on context, but for now, let’s say that data that lives on our computer is considered local, while data retrieved from the Internet is “far away.”

In theory, we can create our own code-based cache for the app we’re building. That is, our app will take data it gets from the web and store it on the computer, tablet, or smartphone that the software is operating on. We may, for example, have our code initialize some data structure and store the data in it.

So, the first time someone searches for the Vroom-Master 3000, our app will search the web for it and then save the desired information in the user’s local data structure, which serves as our cache. This way, the next time someone asks for this information, our app doesn’t have to search the web again; it can instead retrieve the data from the cache.

Now, this behavior may not be desirable for websites that are constantly changing. In this case, the cache can become what is known as stale. That is, the website may have been updated with new information, but the app is pulling up the outdated info saved in the cache. But for websites that don’t update often, the local cache can save us a lot of time.

Code Implementation: A Hash-Table Cache

We have a variety of options as to which data structure we might choose to serve as our cache. However, a hash table is a natural fit for housing a cache since data can be stored and retrieved from a hash table in O(1) time. The following sample code demonstrates how we might use a hash table to serve as a cache:

	import time


	cache = {}

	def lowest_price(product):
	if product in cache:
	return cache.get(product)
	else:
	return search_web_for(product)

	def search_web_for(product):
	# Actual web-searching code goes here. Since we're not
	# actually going to search the web, we'll just use mock
	# data about the price and online shop:
	data_from_web = [799, "Jupiter Electronics"]
	# To mimic the time it takes to search the web, we'll pause for
	# one quarter of a second:
	time.sleep(0.25)
	# Cache the retrieved data:
	cache[product] = data_from_web

	return data_from_web

Here, the main function is lowest_price, which tells the app to first check the cache to see if it already contains data for that product. Only if the cache does not contain that data does the app fetch the data from the web.

In the search_web_for function, the app mimics searching the Internet by sleeping for a quarter of a second. In addition, the code uses the mock data [799, "Jupiter Electronics"] to indicate the product’s lowest price and the online shop where the product is sold for that price. In this example, the product costs $799 and can be found at that price at a store called Jupiter Electronics.

Now, suppose that our software searches for products using the following commands:

	print(lowest_price("Vroom-Master 3000"))
	print(lowest_price("Dustpan Deluxe"))
	print(lowest_price("Vroom-Master 3000"))
	print(lowest_price("Vroom-Master 3000"))
	print(lowest_price("Dustpan Deluxe"))
	print(lowest_price("Vroom-Master 3000"))

The first time we search for "Vroom-Master 3000" and "Dustpan Deluxe", it’ll take a quarter of a second to obtain the data for each. However, in all subsequent requests, we’ll pull the data from the cache, enabling these requests to occur much more quickly.

Out of Space

Now that you know how awesome caching is, I could end the chapter here. However, there’s one itty-bitty teeny-tiny little problem. If our cache keeps saving more and more information from the outside world, our computer (or tablet or smartphone) is going to run out of space quickly. After all, we can’t expect our cache to store the entire Internet!

To manage these space constraints, we need to ensure that our cache is not storing all data we’ve retrieved from the web. To do this, at some point we’ll have to remove some data from our cache—or at least prevent new data from entering. This, then, is the tricky part of caching. Somehow, we need to figure out what information we want to keep and what information to get rid of.