Caching in C++ Services: A Thread-Safe LRU+TTL Cache, Redis Cache-Aside and Stampede Protection [#50-8]

By 0xmote · Jun 18, 2026 · 16 min read · Updated Sep 24, 2026 Advanced Tutorial

What caching buys you, and what it costs

A cache trades freshness and memory for latency and load. A C++ service usually has two layers available: an in-process cache, which is a hash lookup under a lock, and a shared cache such as Redis or Memcached, which is a network round trip but is shared by every instance and survives restarts of your service. Behind both sits the source of truth, usually a database.

The cost side is what makes caching an engineering problem rather than a one-liner:

Every cached value is potentially stale, and you have to decide how stale is acceptable.
A cache that fails, or that expires many keys at once, can send more load to the database than having no cache at all.
An in-process cache is shared mutable state in a multi-threaded program, with all the usual locking and lifetime questions.

This article builds each layer in C++ with those costs in mind: an O(1) LRU cache with TTLs, a sharded wrapper for concurrency, a Redis cache-aside path with hiredis, and the protections that keep a cache from turning into an outage. For the theory of eviction policies beyond LRU (LFU, CLOCK, FIFO), see cache replacement policies.

Choosing a write strategy

Three patterns cover almost every service. They differ in who writes the cache and when.

Cache-aside (lazy loading). The application reads the cache; on a miss it loads from the database and fills the cache. Writes go to the database and then delete the cache key. This is the default for good reason: the cache only holds data someone asked for, and if the cache is down the service still works, just slower.

Write-through. Every write updates the database and the cache together. Reads are almost always hits and rarely stale, but every write pays for two updates, and the cache fills with data nobody may read. It fits read-heavy data with a small hot set, such as configuration or feature flags.

Write-behind (write-back). Writes go to the cache and are flushed to the database asynchronously. Writes are fast and can be batched, but anything not yet flushed is lost if the cache node dies, and the database lags the cache. Use it only for data you can afford to lose or rebuild, such as counters and view statistics.

Pattern	Staleness	Write cost	Failure mode
Cache-aside	Bounded by TTL and invalidation	Database write plus one delete	Cache down means more database load
Write-through	Low	Two writes on every update	Partial failure leaves the two stores different
Write-behind	Database lags the cache	Low, batched	Unflushed writes are lost on a crash

The rest of the article assumes cache-aside, since it is the pattern where the pitfalls are best understood.

An O(1) LRU cache with TTLs

The classic LRU layout is a doubly linked list ordered by recency plus a hash map from key to list node. std::list and std::unordered_map give you both, and the reason this combination works is a specific guarantee: list iterators stay valid when other elements are inserted, erased or moved with splice. The map can therefore store list iterators permanently.

template <class K, class V, class Hash = std::hash<K>>
class LruTtlCache {
public:
    using Clock = std::chrono::steady_clock;

    explicit LruTtlCache(std::size_t capacity) : capacity_(capacity) {}

    std::optional<V> get(const K& key) {
        std::lock_guard<std::mutex> lock(mu_);
        auto it = index_.find(key);
        if (it == index_.end()) return std::nullopt;
        auto node = it->second;
        if (node->expires <= Clock::now()) {          // lazy expiry
            items_.erase(node);
            index_.erase(it);
            return std::nullopt;
        }
        items_.splice(items_.begin(), items_, node);   // O(1), no iterator invalidated
        return node->value;                            // copy out while locked
    }

    void put(const K& key, V value, std::chrono::milliseconds ttl) {
        std::lock_guard<std::mutex> lock(mu_);
        auto expires = Clock::now() + ttl;
        if (auto it = index_.find(key); it != index_.end()) {
            it->second->value = std::move(value);
            it->second->expires = expires;
            items_.splice(items_.begin(), items_, it->second);
            return;
        }
        items_.push_front(Entry{key, std::move(value), expires});
        index_.emplace(key, items_.begin());
        if (index_.size() > capacity_) {               // evict least recently used
            index_.erase(items_.back().key);
            items_.pop_back();
        }
    }

    void erase(const K& key) {
        std::lock_guard<std::mutex> lock(mu_);
        if (auto it = index_.find(key); it != index_.end()) {
            items_.erase(it->second);
            index_.erase(it);
        }
    }

private:
    struct Entry {
        K key;
        V value;
        Clock::time_point expires;
    };

    std::size_t capacity_;
    std::list<Entry> items_;                                       // front = most recent
    std::unordered_map<K, typename std::list<Entry>::iterator, Hash> index_;
    std::mutex mu_;
};

Design notes, each of which corresponds to a bug I have seen in hand-written LRU caches:

splice, not erase plus push_front. Erasing and re-inserting frees and allocates a node on every hit, and the old iterator in the map is now dangling until you overwrite it. splice just relinks the node; the iterator in the map remains correct and there is no allocation.
Order of operations on eviction. index_.erase(items_.back().key) must run before items_.pop_back(), because the key lives inside the node that pop_back destroys.
Copy the value out under the lock. Returning const V& into the cache looks efficient, but another thread can evict that entry the moment the lock is released, leaving the caller with a dangling reference. For large values, store std::shared_ptr<const V> and return that: the copy is one atomic increment, and an evicted value stays alive while a caller still uses it.
steady_clock for expiry. system_clock can jump when NTP adjusts the wall clock, which can expire everything at once or keep entries alive far too long.
Lazy expiry has a cost. Expired entries are only removed when someone asks for them or when they reach the LRU tail. For bounded capacity that is fine, because eviction eventually reclaims them. If you need memory back promptly, run a periodic sweep from the tail.
The key is stored twice, once in the map and once in the node. For string keys that doubles key memory; if it matters, store the key only in the node and index by a std::string_view pointing into it; list nodes never move, so the view stays valid until the entry is erased.

Why a `shared_mutex` does not help here

It is tempting to make get take a shared lock so that readers do not block each other. For LRU that is incorrect: get moves the entry to the front of the list, which is a write to shared structure. Two readers splicing concurrently corrupt the list. A true LRU needs exclusive access on every hit.

The practical fix is sharding: split the key space across several independent caches, each with its own mutex, so that contention is divided by the shard count.

template <class K, class V, std::size_t Shards = 16>
class ShardedCache {
public:
    explicit ShardedCache(std::size_t capacity) {
        for (auto& s : shards_)
            s = std::make_unique<LruTtlCache<K, V>>(capacity / Shards + 1);
    }
    std::optional<V> get(const K& key) { return shard(key).get(key); }
    void put(const K& key, V value, std::chrono::milliseconds ttl) {
        shard(key).put(key, std::move(value), ttl);
    }
    void erase(const K& key) { shard(key).erase(key); }

private:
    LruTtlCache<K, V>& shard(const K& key) {
        return *shards_[std::hash<K>{}(key) % Shards];
    }
    std::array<std::unique_ptr<LruTtlCache<K, V>>, Shards> shards_;
};

The trade-off is that each shard evicts independently, so the cache as a whole is only approximately LRU: a cold key in a lightly used shard can outlive a warm key in a busy one. With a decent hash and many keys, the difference is small. The shards are held by unique_ptr because std::mutex makes the cache non-movable.

Redis cache-aside with hiredis

For a cache shared across instances, the synchronous hiredis API is enough for most services. Three things matter more than the happy path: binary-safe arguments, timeouts, and what happens to the connection after an error.

#include <hiredis/hiredis.h>

class RedisCache {
public:
    RedisCache(const char* host, int port, std::chrono::milliseconds timeout) {
        timeval tv{};
        tv.tv_sec = static_cast<long>(timeout.count() / 1000);
        tv.tv_usec = static_cast<long>((timeout.count() % 1000) * 1000);
        ctx_.reset(redisConnectWithTimeout(host, port, tv));
        if (!ctx_ || ctx_->err)
            throw std::runtime_error(ctx_ ? ctx_->errstr : "redis: allocation failed");
        redisSetTimeout(ctx_.get(), tv);             // bound every command, not only connect
    }

    std::optional<std::string> get(const std::string& key) {
        Reply r(static_cast<redisReply*>(
            redisCommand(ctx_.get(), "GET %b", key.data(), key.size())));
        if (!r) throw std::runtime_error(ctx_->errstr);   // context is now unusable
        if (r->type == REDIS_REPLY_NIL) return std::nullopt;
        if (r->type != REDIS_REPLY_STRING) throw std::runtime_error("redis: unexpected reply");
        return std::string(r->str, r->len);
    }

    void set(const std::string& key, const std::string& value, std::chrono::seconds ttl) {
        const std::string ex = std::to_string(ttl.count());
        Reply r(static_cast<redisReply*>(
            redisCommand(ctx_.get(), "SET %b %b EX %s",
                         key.data(), key.size(), value.data(), value.size(), ex.c_str())));
        if (!r) throw std::runtime_error(ctx_->errstr);
    }

    void del(const std::string& key) {
        Reply r(static_cast<redisReply*>(
            redisCommand(ctx_.get(), "DEL %b", key.data(), key.size())));
        if (!r) throw std::runtime_error(ctx_->errstr);
    }

private:
    struct CtxFree { void operator()(redisContext* c) const { redisFree(c); } };
    struct ReplyFree { void operator()(redisReply* r) const { freeReplyObject(r); } };
    using Reply = std::unique_ptr<redisReply, ReplyFree>;
    std::unique_ptr<redisContext, CtxFree> ctx_;
};

Use %b for keys and values, not %s. %s stops at the first zero byte, so a serialized binary value (Protobuf, MessagePack, compressed JSON) is silently truncated. %b takes a pointer and a length.
Set a command timeout. Without redisSetTimeout, a synchronous call blocks until the kernel gives up on the TCP connection, which can take minutes. If Redis stalls, every request thread piles up behind it. A timeout of tens of milliseconds, with a fallback to the database, turns a Redis stall into slower responses instead of a hung service.
A NULL reply means the context is broken. hiredis sets ctx->err, and the context cannot be used for further commands. Reconnect (hiredis 1.0 added redisReconnect) or discard it and create a new one.
One context per thread. A synchronous redisContext is not thread-safe. Give each worker thread its own, or check connections out of a small pool.
RAII for replies. freeReplyObject must run on every path, including exceptions; a unique_ptr with a custom deleter makes that automatic.

If you use Asio, the synchronous API blocks the event loop thread; use hiredis’s async API with an adapter, or a client library built on Asio, instead. Memcached via libmemcached follows the same structure: binary-safe memcached_get/memcached_set with explicit lengths, a timeout set through behaviors, and one memcached_st per thread (or memcached_pool). Redis is usually chosen when you also want its data structures, pub/sub or persistence; Memcached when you want a pure, multi-threaded key-value cache.

Failing open

The cache must never be the reason a request fails. Wrap cache access so that errors are counted and logged, then fall through to the database:

std::optional<std::string> cached_get(RedisCache& redis, const std::string& key) {
    try {
        return redis.get(key);
    } catch (const std::exception& e) {
        metrics.cache_errors.inc();          // visible, but not fatal
        log_warn("redis get failed: {}", e.what());
        return std::nullopt;                 // treat as a miss
    }
}

The catch is that “treat as a miss” sends every request to the database when Redis is down. If the database cannot absorb full traffic, which is common since the cache exists precisely because it cannot, you also need the protections in the next section and possibly a circuit breaker that sheds load instead.

Stampedes: when many misses arrive at once

A popular key expires. In the next few milliseconds, hundreds of requests miss, and every one of them runs the same expensive query. That is a cache stampede (or thundering herd), and it is how a cache turns a routine expiry into a database overload.

Single-flight loading

Within one process, collapse concurrent loads of the same key into one: the first caller loads, everyone else waits for its result.

template <class K, class V>
class SingleFlight {
public:
    template <class Load>
    V run(const K& key, Load&& load) {
        std::unique_lock<std::mutex> lock(mu_);
        if (auto it = inflight_.find(key); it != inflight_.end()) {
            auto fut = it->second;                  // someone is already loading
            lock.unlock();
            return fut.get();                       // wait; rethrows the leader's exception
        }
        std::promise<V> promise;
        auto fut = promise.get_future().share();
        inflight_.emplace(key, fut);
        lock.unlock();

        try {
            V value = load();
            promise.set_value(value);
            forget(key);
            return value;
        } catch (...) {
            promise.set_exception(std::current_exception());
            forget(key);
            throw;
        }
    }

private:
    void forget(const K& key) {
        std::lock_guard<std::mutex> lock(mu_);
        inflight_.erase(key);
    }
    std::mutex mu_;
    std::unordered_map<K, std::shared_future<V>> inflight_;
};

The in-flight entry is removed as soon as the load finishes, success or failure, so the map only ever holds keys currently being loaded. That matters: a common alternative, a std::unordered_map<std::string, std::mutex> of per-key locks, never shrinks and becomes a memory leak proportional to the number of distinct keys ever requested. Waiters block their thread in fut.get(), which is fine in a thread-per-request server; in an Asio server you would complete waiters through posted handlers instead of blocking.

Across many instances, single-flight in each process still leaves one load per instance. If that is too many, add a short Redis lock (SET lock:key token NX PX 5000): the winner loads, others briefly serve stale data or retry. The lock must expire on its own in case the winner crashes, and must be released only by the holder, which is why it carries a token.

TTL jitter

If a batch job fills ten thousand keys with the same TTL, they all expire in the same second. Randomizing the TTL by a small percentage spreads expiries out:

std::chrono::milliseconds jittered(std::chrono::milliseconds base, double spread = 0.1) {
    thread_local std::mt19937 rng{std::random_device{}()};
    std::uniform_real_distribution<double> factor(1.0 - spread, 1.0 + spread);
    return std::chrono::milliseconds(static_cast<long long>(base.count() * factor(rng)));
}

Negative caching

A request for a key that does not exist misses the cache, misses the database, and caches nothing, so the next request repeats it. If an attacker or a buggy client requests random IDs, every request goes straight to the database. Cache the absence too, with a much shorter TTL so that newly created rows appear quickly.

Putting it together

ShardedCache<std::string, std::optional<User>> users(10'000);
SingleFlight<std::string, std::optional<User>> flight;

std::optional<User> load_user(int id) {
    const std::string key = "user:" + std::to_string(id);
    if (auto hit = users.get(key)) return *hit;          // hit, possibly a cached "not found"

    return flight.run(key, [&] {
        if (auto hit = users.get(key)) return *hit;      // filled while we waited for the lock
        std::optional<User> user = db.find_user(id);
        users.put(key, user, user ? jittered(10min) : 30s);   // short TTL for misses
        return user;
    });
}

The cached type is std::optional<User>, so users.get returns std::optional<std::optional<User>>: the outer optional means “was it in the cache”, the inner one means “does the user exist”. In a test with 32 threads each loading the same existing and missing user concurrently, this issues exactly two database queries.

Invalidation: delete, and understand the remaining race

On a write, cache-aside deletes the key after updating the database. Updating the cached value instead looks more efficient, but two concurrent writers can apply their database updates in one order and their cache updates in the other, leaving the older value cached indefinitely.

Delete-after-write still has one well-known race:

Reader misses the cache and reads the old row from the database.
Writer updates the row and deletes the cache key.
Reader, delayed, writes the old value into the cache.

The cache now holds stale data until the TTL expires. The window is small, since the reader must be slower than an entire write, but under load it happens. The practical defenses, in increasing cost:

Keep a TTL on everything. It bounds how long any inconsistency can last, and it is the reason “never set a TTL” is a bad default even for rarely changing data.
Delete twice: delete immediately after the write, and again after a short delay that exceeds a typical read. It narrows the window rather than closing it.
Version the value. Store a row version (or updated_at) with the cached value and refuse to overwrite a newer version with an older one. With Redis this needs a small Lua script to compare and set atomically.
Invalidate from the change stream. Instead of the application deleting keys, a consumer of the database’s replication log or an outbox table deletes them. Writes cannot forget to invalidate, and every instance’s in-process cache can subscribe to the same events.

In-process caches add a layer: deleting the Redis key does not touch the copies in other instances’ memory. Either keep in-process TTLs short (seconds), or broadcast invalidations over pub/sub to every instance. The Node.js Redis caching article shows the pub/sub invalidation pattern in more detail; it is language-independent.

The stale-read race above is the one I would warn about first, because it survives code review. Each line of the cache-aside code is correct on its own, the tests pass, and the bug only appears as “a user changed their name and the old one came back for ten minutes”, reported days later with no way to reproduce it. Once I started thinking of every cache write as “this may be the old value”, TTLs stopped feeling optional.

Measuring whether the cache helps

Count hits, misses, errors and evictions per cache, and export them with your other metrics. A useful hit rate depends entirely on the workload, so rather than aiming for a fixed number, watch for changes: a hit rate that drops after a deploy usually means a key format changed, and a rising eviction count means the capacity is too small for the working set. Also measure the latency of the miss path, since that is what users experience when the cache is cold, for example right after a restart.

Two last habits pay off:

Namespace and version keys, such as user:v2:1000. Changing the serialization format then means bumping the version, not flushing the whole cache or deserializing old bytes as the new format.
Warm critical keys after a deploy, or roll out instances gradually, so that a fleet of empty in-process caches does not hit the database at the same moment.