7 Use case: LRU Cache
This chapter covers
- Solving a problem: avoid computing things twice
- Introducing caching as a solution
- Describing different types of caches
- Designing an efficient solution for LRU cache
- Discussing MFU and other choices to handle priority
- Discussing caching strategies
- Reasoning about concurrency and synchronization
- Describing how caches can be applied in a sentiment analyzer’s pipeline
This chapter is going to be different with respect to what you have seen so far in this book. We are not going to introduce a new data structure, but instead we will use the ones described in chapters 2 to 5 to create a more complex data structure; by using lists, queues, hash tables etc… as building blocks, we will be able to create an advanced data structure that can be used to quickly access values/computed results that were recently accessed – although one could argue that a cache is more than just a data structure, it’s already a sophisticated component with several moving parts: in its simplest form, it can just be implemented as an associative array, but we will see during the course of this chapter that it can become as complex as a web service.
In this chapter we are going to delve into the details of how caches of increasing complexity work, so that, after reading it, you should be able to articulate an informed opinion on whether the topic.