Caching data means storing a copy of the data in a quickly accessible location to speedup future accesses of that data. The key trade-off is that the faster storage locations for data tend to be smaller and thus hold less data. For example, accessing data from RAM is much faster than reading it off a hard drive, but RAM is both smaller and more expensive per-unit of storage. By caching data that is used often, you can greatly speed up a program.
The Library of Alexandria is still famous to this day for the size and breadth of its collection. However, few people know that the true magic of the library was the librarian’s ability to find relevant resources with amazing speed. Within a few seconds he could often locate the canonical reference to answer a patron’s question.
For young Peter, this magical ability had always been a thing of wonder. He had grown up in a small house four blocks from the library and had spent many afternoons sitting at the tables listening to the librarian answer questions. “What should I feed my new pet yak?” “Where can I find the sweetest prunes in Alexandria?” The scope of knowledge commanded by the librarian was almost legendary. Peter dreamed of one day learning the magic. And, after ten years of training, Peter got his wish: he was accepted as the librarian’s apprentice.
On the first day of his apprenticeship, Peter arrived three hours early. As the librarian took him on a tour of the library, Peter eagerly followed him around, scribbling notes into his new notebook. Although Peter knew the public areas by heart, he soaked in every word. After the tour was complete, the librarian and his new apprentice took their places behind the reference desk and waited for the first patron of the day.
The first question came from a small man holding a rather large rock. “I’m trying to build a wheel. And, well … I’m not sure what shape to go with. Do you have any good references?”
The librarian disappeared into the stacks, only to reappear a few seconds later with a scroll entitled “Wheels and How to Design Them.” The patron was delighted. He took the scroll over to a nearby desk and started to quickly skim through it.
“Oh … I see … a circle … hmm … brilliant,” the patron quietly mumbled to himself.
“How did you do that?” The apprentice asked. “How did you find the scroll so quickly? Please teach me the magic of the library.”
“Magic?” The librarian asked. “I’m not sure about that, but I can show you my system.”
The librarian led Peter into the back room. The room was dimly lit by two small oil lamps. At the back was a single door leading to the vaults where the thousands of scrolls were kept. The librarian walked over to the a small table that held a coffee pot and a small stack of scrolls. He pointed at the scrolls. “I usually find the answers in one of these.”
Peter was confused. “Twenty scrolls? The library has tens of thousands of scrolls. How does having twenty in the back room help? Are they magic?”
“Not at all,” chuckled the librarian. “It turns out that people are pretty boring. They all ask the same types of questions. In fact, I’ve found that 95% of the questions in a single day can be answered with only twenty scrolls.”
“Is that all?” Peter asked, visibly disappointed.
“Yes,” replied the librarian. “What did you hope for?”
“I’m not sure. But I was certainly expecting something magical. Maybe you were summoning the scrolls or could teleport yourself to the correct shelf. But … this seems like cheating.”
“Cheating?” The librarian laughed. “Do you realize how much effort goes into making this efficient enough to appear magical? You can’t pick any twenty scrolls. They have to be the right twenty scrolls.”
At the news of this challenge, the apprentice perked up a bit. “And how do you pick them? Telepathy?”
“When I first started, I kept the most frequently read scrolls in my cache. Every time someone read a scroll, I would note that. I kept a count for each scroll.”
“I see why that would work,” said the apprentice, sounding slightly bored.
“Aha! But it didn’t work!” exclaimed the librarian. “Everything seemed to be going fine, until the same scrolls got stuck in my cache. Remember that massive flood we had two years ago? During the entire flood, I still had three scrolls on how to survive a drought. It was a disaster.”
“Then I had a new idea,” he continued. “I could keep more data and use statistics. I meticulously kept track of which scrolls people were viewing and correlated it to the season, weather, and fads of the day. I created complex predictive models of which scrolls would be most requested on a given day. I could pre-fill my shelf every morning!”
“Did that work?” asked Peter.
“Yes. But was a lot of work. So I stopped doing it.”
Peter stared at the floor. Disappointment flowed through him. He wondered if he should have become a blacksmith instead.
“Eventually, I got lazy and left the most recent scrolls on the shelf. When I needed to go down to the stacks, I’d grab whatever scroll had been used least recently and put it back. It turned out to be a pretty good system.”
“Really? So the magic behind the Library of Alexandria is that you keep the twenty most recently viewed scrolls on a shelf in the back room?”
“Yes. It allows me to answer 95% of people’s questions without going past this room.
The apprentice nodded numbly. Now he was certain that he should have become a blacksmith.
