Simple Least-Recently-Used Cache
Today I needed to add in an LRU cache to my archive server because we have some number of files loaded - each with about 10MB of messages from the exchange feeds. We don't want to have an infinite number, but we don't want to dump them prematurely. After all, they are immutable, so as long as we can keep them in memory, we should keep them in memory - just in case the next client asks for the data that happens to be in that chunk.
So I decided on a two-step memory management scheme - simple aging, and an LRU for times of very high load. The simple aging is that - simple. Every minute, or so, I'll look at all the chunks loaded into the cache, and see the last time it was accessed by a client. If
that time ever exceeds, say, an hour, we'll drop it. That just says that at the end of the day there's no reason to be a pig about the machine.
The LRU is pretty simple, in theory: every time we go to add a new chunk, we look to see how many we have, and if we have too many, we drop the one with the oldest access time, and continue until we get below the threshold so we can add the new one.
The question is about the determination of the oldest. You can make a list of keys, and each time the chunk is accessed, move it's key to the start of the list, and then take the last element on the list, but that's a lot of list accessing (adds, finds, deletes) when we might not be hitting the cache limit very often at all. So I took a simpler approach: just find the oldest one when I need to delete it.
bool ArchiveSvr::dropOldestChunk_nl() { bool error = false; // first, find the one to delete… uint64_t when = 0; std::string what; for (cmap::iterator i = cache.begin(); i != cache.end(); ++i) { if ((when == 0) || (when > it->second.lastAccessTime)) { when = it->second.lastAccessTime; what = it->second.filename; } } // if we have anything to delete - do it if (!what.empty()) { cache.erase(what); } else { error = true; // we were supposed to delete SOMETHING… } return !errror; }
Now, in the code, I can simply do:
while (cache.size() >= MAX_SIZE) { if (!dropOldestChunk_nl()) { error = true; cLog.error("can't delete what we need to… Bad!"); break; } }
and we're good to go! Not bad at all. Simple, but effective.