Оффлайн
- Регистрация
- 1 Мар 2015
- Сообщения
- 1,481
- Баллы
- 155
Author Notes:
I'm not an expert - just a developer trying to learn by doing. Over the past few months, I've been juggling Python, DSA, System Design, and AWS, and I've realized something: I don't truly understand anything until I hit a wall and fix it. That's how I learn by breaking, debugging, and rebuilding. This article is part of a series of notes I'm publishing for my future self and anyone else who learns like me: through roadblocks, hands-on problems, and curiosity.
Disclaimer:
This post reflects my personal experience and experimentation while learning. Code is original unless otherwise stated. Edge case testing is still in progress and will update the code if any changes. This article was written with the assistance of AI tools for grammar and spell checking.
Motivation:
For a website tracking system, which I am building as a hobby project, where we can track the websites visited and time spent on each, I needed to use a cache to retrieve data about the websites. Instead of querying this data repeatedly, we can use an LRU (Least Recently Used) cache to store and update visit counts efficiently, reducing overhead and improving performance. This simulation reflects a real-world system design problem - managing limited memory while ensuring responsiveness in a user-focused application.
Topics covered: Python, Threading, Cache(LRU), DLL, HashMap
What is Cache?
The cache is a temporary storage system that stores data based on specific rules. Different cache strategies exist depending on application or product design requirements. This article focuses on the LRU (Least Recently Used) cache strategy, where the least recently accessed data is removed first when the cache reaches its capacity limit.
How to build an LRU cache?
An efficient LRU cache can be implemented using a combination of a doubly linked list (DLL) and a hashmap (dictionary) with a time complexity of O(1) for both retrieval and addition.
A dictionary where each key points to a node containing the required value. Three main cases handle cache operations:
Key doesn't exist in cache: Add the item if the cache has space
Key exists in cache: Remove the previous node and add a new node at the end
Cache is full: Remove the least recently used item (head of DLL) before adding new data
Why not OrderedDict?
Python's OrderedDict can implement LRU, but building it manually helps you:
Understand how hash maps and pointers work together.
Debug performance bottlenecks.
First, build a DLL with add and remove methods where we add a new node and delete a given node.
Second, create a cache where a dictionary can store only 4 values ie, cache limit, and if it exceeds, remove from the first of the DLL, and if anything is accessed again, then remove it from the dll, and add it to the start of the DLL again. DLL is used to maintain order, whereas the dictionary helps in maintaining key-value pairs, helping in O(1) retrieval.
Everything should be good now, but I tested 100 dummy URL caching it took almost the same time, so no practical use of caching as it can only store 4 URLs and their information, it slowed down the process. To address this performance, I used threads.
I hit a couple of roadblocks there, I assumed that since Python uses GIL, I need not take care of concurrent thread execution, which in turn leads to inconsistent caching. The impact was that it was taking more time, and sometimes I was not getting the new values, and though the URL was in cache, I could not hit the cache.
So I explored a bit more and learned that I had to use thread locking, although GIL ensures only one thread executes Python bytecode at a time, it doesn't stop threads from interleaving operations on shared data. Without locks, threads corrupt the DLL's pointers or return stale data. The thread locks helped here, finally the LRUCache with multithreading made sense, and below is the final version of the code:
I'm not an expert - just a developer trying to learn by doing. Over the past few months, I've been juggling Python, DSA, System Design, and AWS, and I've realized something: I don't truly understand anything until I hit a wall and fix it. That's how I learn by breaking, debugging, and rebuilding. This article is part of a series of notes I'm publishing for my future self and anyone else who learns like me: through roadblocks, hands-on problems, and curiosity.
Disclaimer:
This post reflects my personal experience and experimentation while learning. Code is original unless otherwise stated. Edge case testing is still in progress and will update the code if any changes. This article was written with the assistance of AI tools for grammar and spell checking.
Motivation:
For a website tracking system, which I am building as a hobby project, where we can track the websites visited and time spent on each, I needed to use a cache to retrieve data about the websites. Instead of querying this data repeatedly, we can use an LRU (Least Recently Used) cache to store and update visit counts efficiently, reducing overhead and improving performance. This simulation reflects a real-world system design problem - managing limited memory while ensuring responsiveness in a user-focused application.
Topics covered: Python, Threading, Cache(LRU), DLL, HashMap
What is Cache?
The cache is a temporary storage system that stores data based on specific rules. Different cache strategies exist depending on application or product design requirements. This article focuses on the LRU (Least Recently Used) cache strategy, where the least recently accessed data is removed first when the cache reaches its capacity limit.
How to build an LRU cache?
An efficient LRU cache can be implemented using a combination of a doubly linked list (DLL) and a hashmap (dictionary) with a time complexity of O(1) for both retrieval and addition.
A dictionary where each key points to a node containing the required value. Three main cases handle cache operations:
Key doesn't exist in cache: Add the item if the cache has space
Key exists in cache: Remove the previous node and add a new node at the end
Cache is full: Remove the least recently used item (head of DLL) before adding new data
Why not OrderedDict?
Python's OrderedDict can implement LRU, but building it manually helps you:
Understand how hash maps and pointers work together.
Debug performance bottlenecks.
First, build a DLL with add and remove methods where we add a new node and delete a given node.
Second, create a cache where a dictionary can store only 4 values ie, cache limit, and if it exceeds, remove from the first of the DLL, and if anything is accessed again, then remove it from the dll, and add it to the start of the DLL again. DLL is used to maintain order, whereas the dictionary helps in maintaining key-value pairs, helping in O(1) retrieval.
Everything should be good now, but I tested 100 dummy URL caching it took almost the same time, so no practical use of caching as it can only store 4 URLs and their information, it slowed down the process. To address this performance, I used threads.
I hit a couple of roadblocks there, I assumed that since Python uses GIL, I need not take care of concurrent thread execution, which in turn leads to inconsistent caching. The impact was that it was taking more time, and sometimes I was not getting the new values, and though the URL was in cache, I could not hit the cache.
So I explored a bit more and learned that I had to use thread locking, although GIL ensures only one thread executes Python bytecode at a time, it doesn't stop threads from interleaving operations on shared data. Without locks, threads corrupt the DLL's pointers or return stale data. The thread locks helped here, finally the LRUCache with multithreading made sense, and below is the final version of the code: