Understanding Python Cache

What is Caching in Python?

Caching is an optimization technique that stores or caches the result into a temporary data structure, which allows very fast data access, as compared to the underlying storage device like a hard disk, database, or web service. Using Python cache, a developer can boost an application's performance.

Caching is a technique used both at a hardware level and a software level. Python cache means implementing caching at a software level using the methods provided by the language. Python cache stores the data in the main memory (RAM) of the computer. It does not use dedicated memory like the L1 cache or the L2 cache to store the data, as used by many operating systems.

The data structure used for caching is called a cache. When the data needs to be accessed, the application searches for the result in this cache. In case, the data is found, the data is directly returned from the cache, without executing further instructions. This is known as a cache hit. If the data is not present in the cache (also known as a cache miss), the data is loaded from the underlying storage. The data is then populated into the cache for future queries. In this way, the cache keeps on updating with every cache miss.

A cache can also use expiration policies. This means, that after a certain time, the cache data is invalidated and refreshed by the application. This is done to avoid stale data in the cache.

A cache can also use eviction policies. This means, that when the cache is full and there is no more space, the cache needs to free up some memory. Cache eviction policies determine which data needs to be deleted from the cache to free space. Some of the commonly used policies are: Least recently used (LRU), Least Frequently used (LFU), etc. In this article, cache eviction policies are not discussed.

Python Cache Uses

Python cache is implemented using Python dictionaries and decorators. These methods can store the most recent and frequently accessed data in the main memory. This makes data access faster and requires less CPU usage. Python dictionaries use hashing that offers fast searching, with the average time complexity being $O(1)$.

In Python, the decorator @lru_cache uses the Least Recently Used cache eviction policy which is simple to understand and can be extended to complex functionality. It provides multiple methods to incorporate cache expirations based on space and time. These parameters can be modified based on the needs of the application.

Why Do We Need to Implement Caching?

Caching is an optimization technique that is used to boost the performance of the application. The application uses Python cache to reduce the time required in accessing data by reducing the need to access slow data storage systems like databases, web services, etc.

To understand the need for caching, consider the following example. Suppose there is a service that requires you to get the details of a product associated with an id. All the products are stored in a list. Consider the following function getDetailsWithId.

In this example, for each id, we iterate the whole list. Suppose, a few products are accessed more than others. In this case, if we cache those products into the Python cache, we will get a high amount of cache hits and few cache misses. This will increase the overall performance of the application. We, also, need to use a cache expiration policy in case, the product details get updated in the list.

Rules of Caching

Caching is a technique that makes the tradeoff between space and time. It should be noted that Python cache might not always be the solution to increasing the performance of an application. When a developer wants to implement caching in an application, the developer must identify the set of functions where caching can be useful. Caching should not be implemented when a function is called a few times or when it takes very less time to execute. Following guidelines can help you implement caching.

First Rule

The first rule is to find the performance bottleneck in your application.

An application consists of functions where some functions take more time than others. A developer should first identify the functions that have slower running times. This set of functions forms a bottleneck and should be optimized as much as possible. One way to find such functions is to go over the code and analyze the time taken by each line of a function. The art of finding the bottleneck in your code, just by looking at it, comes with practice and experience.

Let us understand this using an example. Consider the function below. The function getImageWithURL returns an image from the url given as a parameter.

In the above example, the following line forms a bottleneck as it requests the service URL to get an image.

In this example, if the same image is retrieved multiple times by the application, the cache can be used to increase the performance.

However, if there is a function whose value is updated every time, then the caching will be useless as you might end up giving the old data back to the application.

It is also necessary to know when to invalidate the cache and load the fresh data.

Second Rule

The second rule of caching is to verify that it is faster to get the data from the newly introduced cache than it takes to execute the original function directly.

Consider the example below. Suppose, in the function getImageWithURL we introduce a cache that stores the image URL as the key and the image as the value. For now, consider that we have a data structure cache that allows very fast read and write operations. Later we will look at how to implement caching in Python.

When the function is called, we will use this cache to retrieve the image. If the image is present in the cache (a.k.a cache hit), we will return the image directly. If the image is not present in the cache (a.k.a cache miss), we will request the image and store the result in the cache.

Now, suppose the time taken to check the cache and retrieve the image is comparable to the time for making the request directly, then introducing caching is not very beneficial, as you will not get the required performance boost in your application. This is implied by the second rule.

As a developer, you need to make sure that caching increases the performance of the application significantly.

Third Rule

The third rule is concerned with the amount of the main memory that is used by the application. This is known as the memory footprint of the application.

Python cache uses the main memory to cache the data. If we use a bigger cache or store unnecessary information in the cache that is not required by the application, the memory footprint will increase. As a developer, you should be aware of the data structures used by the cache and store only the necessary information required by the application.

Consider the following example.

Suppose, there is an academic website that shows articles on Computer Science. Each article will have three attributes: id, name, and author, as defined below.

However, the dashboard only shows the name of each article. When building an application, it makes sense to cache only the names of the articles, not the whole content of the articles. Below given is an implementation of the Python program we use to calculate the size of the container recursively.

Now, in the first implementation, we will only store the names of the articles in the cache and calculate the total size of the cache.

Output

We compare this to the implementation in Python when we cache the whole article.

Output

As we see the memory footprint increases if we store unnecessary information in the cache.

The third rule highlights that only relevant data should be cached as it will reduce the memory consumption of the application.

Adding Caching Expiration

When the data stored in the Python cache changes over time in the database, it is required to remove the stale data from the cache. This is termed cache expiration. The Python cache is invalidated and all the data is removed from the cache.

There are multiple methods for implementing cache expiration.

• One method is that the application can be notified of any changes in the database. On such notification, the application can invalidate the cache and refresh the data.
• The application can compare the last modified time of the data stored in the cache and the database. If the last modified time of the data stored in the database is after the last modified time of the data stored in the cache, then the application can invalidate the cache and refresh the data.
• The application can also choose to implement a timeout or TTL (Time to Live). This timeout acts like a timer for each entry stored in the cache. Data is refreshed at every timeout. The timeout can be implemented using a signaling library in Python.

Examples

Using Python Dictionary

Python Cache can be seen as a mapping data structure from a key to a value. This property can be simulated using a dictionary in Python.

Python cache can be implemented using a global dictionary for a function. On a function call, if the data is present inside the dictionary, then we do not need to execute the entire function. We can simply return the value. In case of a cache miss, we will execute the function, get the result and store it in the cache for the future query. For a dictionary, a key needs to be selected appropriately. This key needs to be unique. If the key is too long, then it is preferred to hash it using SHA or MD5, etc.

Consider the following example to calculate the N-th Fibonacci number. We use the following equations to calculate the N-th Fibonacci number, using recursion. $F(N) = F(N-1) + F(N-2)$ $F(0) = 0, F(1) = 1$

Output

In the above example, we use a dictionary cache to store the result of the function. The key is the value of the parameter N passed into the function. This key is unique and for a unique N, we have a unique Fibonacci number, hence there will not be any collisions. Before calling the recursive functions, we first check whether the value is present in the cache or not. If the value is present, we return the same value, else we calculate the result of the function and update our cache. The dictionary cache provides fast search queries as the time complexity for each query is $O(1)$.

Note that, in the example, we have not implemented any cache eviction policies. This means that the dictionary cache will keep on increasing in size. To avoid this, we can use a cache eviction policy, based on space or time.

Using @lru_cache Decorator

The decorator @lru_cache(max size, typed) is part of the functools module in Python. It accepts two parameters:

• max size is used to set the maximum size of the cache. It can be assigned to None in case the developer does not want to fix a size.
• typed can take the boolean value True or False. When it is set to True, it indicates that the cache will store different entries for different types of function arguments.

The decorator @lru_cache uses a dictionary to create a Python cache in the main memory. This decorator caches the result of the function using the key as the function call, along with the function parameters. This decorator is useful in case of recursion. This decorator implements memoization in the recursive function, making it faster.

Consider the following example to calculate the N-th Fibonacci number. In this case, we are going to use the decorator to speed up the process.

Output

This problem exhibits overlapping subproblems, hence memoization can be useful here. So we have decorated the function findNthFib with the decorator @lru_cache. This decorator stores the result of each function call, and when it encounters a recursive call whose result is present in the cache, it does not calculate the result of the recursive call again. It uses the result stored in the cache, making the time complexity from $O(2^{N})$ to $O(N)$.

This method is applied when memoization can speed up the application.

Using External Caching Services

There are multiple external in-memory cache services like Memcached, and Redis that can be integrated with Python to cache the data of the application.

These external caches are extremely powerful and offer a wide variety of features. The above two examples have constraints and are less flexible. These external caches take care of all the complications of creating and maintaining the cache.

Memcached in a popular external cache service. It can be integrated with Python using the package pymemcache.

Memcached is a simple, easy-to-use, and fast cache used across the industry.