Opensource internals

ClickHouse's LRU Cache Keeps Its Order in a Linked List

20 min read Jay Hubbert

ClickHouse's LRU cache is a hash map of cells pointing into a singly linked list: a lookup is a splice, and eviction is a pop from the front.

TL;DR: The cache is two containers: an unordered_map from key to cell, and a std::list of keys in recency order. Each cell stores an iterator into that list. A lookup is splice (move the node to the back), eviction is pop_front. No timestamps, no heap, no re-sorting — and the weight of every entry is tracked so the cache evicts by bytes, not by count.

Every cache in every database has the same skeleton: a map from key to value, and a rule for what to throw away when the map gets too big. The rule is the interesting part, because the obvious implementations are all bad in one of two ways.

The obvious LRU implementation stores a timestamp with each entry and, on eviction, scans the whole map for the oldest timestamp. That is O(n) per eviction, on the critical path of a request that just missed the cache. The obvious clock implementation stores a “referenced” bit and sweeps a hand over the map. That is O(1) amortised, but it needs the map to be traversable in a stable order, which a hash map is not.

ClickHouse’s answer is the classic one, and the classic one is worth studying because the details are unusually carefully done. Two containers:

text 
        unordered_map<Key, Cell>                std::list<Key>
        ┌───────────────────────┐               ┌──────────────────────────┐
        │  Key ──► Cell         │               │ [A] [B] [C] [D] [E]      │
        │           │           │               │  ↑                      │
        │           └───────────┼──iterator───►│  front = least recent   │
        │                       │               │  back  = most recent   │
        └───────────────────────┘               └──────────────────────────┘

The map gives you the value and a handle; the handle points at the node’s position in the list; the list is the eviction order. A hit is a pointer swap; an eviction is a pop from the front.

This article walks through the whole thing: the policy interface, the cell layout, the splice, the byte-weighted eviction loop, the metrics, and the thread-safe wrapper on top, including the cache-stampede protection that getOrSet() provides.

The policy interface

The cache machinery is split in two. A policy knows how to pick a victim and how to order the entries. A wrapper (CacheBase) adds a mutex, hit/miss counters, and the getOrSet dance. The policy is the interesting part, so it starts with a small abstract interface.

cpp 
// src/Common/ICachePolicy.h:22
template <typename TKey, typename TMapped, typename HashFunction = std::hash<TKey>, typename WeightFunction = EqualWeightFunction<TMapped>>
class ICachePolicy
{
public:
    using Key = TKey;
    using Mapped = TMapped;
    using MappedPtr = std::shared_ptr<Mapped>;
    using OnRemoveEntryFunction = std::function<void(size_t, const MappedPtr &)>;  /// For per-item callback

    struct KeyMapped
    {
        Key key;
        MappedPtr mapped;
    };

Two things in that header are worth pausing on.

The value is a shared_ptr. Not a unique_ptr, not a value. This is deliberate: the cache hands out a reference to the stored value, and the caller may hold on to it for as long as it likes. If the cache evicts the entry, the value stays alive as long as somebody is using it. std::shared_ptr<Mapped> in the interface is the whole reason.

The default weight function counts entries, not bytes. If you do not supply a weight function, every entry weighs exactly one:

cpp 
// src/Common/ICachePolicy.h:13
template <typename T>
struct EqualWeightFunction
{
    size_t operator()(const T &) const
    {
        return 1;
    }
};

So “max_size_in_bytes” with the default weight function really means “max number of entries”. Every real cache in the tree supplies a weight function instead — the mark cache weighs a file’s marks, the query result cache weighs the bytes a result actually allocated.

There is also an interface subtlety that matters a lot in practice: contains() is explicitly not an access.

cpp 
// src/Common/ICachePolicy.h:55
    /// Like `get(key) != nullptr`, but doesn't consider it an "access".
    /// E.g. doesn't move it to the front of LRU list.
    /// Not allowed to allocate memory (see PageCache::contains).
    virtual bool contains(const Key & key) const = 0;

A cache that answers “is this key resident?” must not, as a side effect, reorder its eviction order. If it did, a monitoring loop that polls system.mark_cache would silently reshuffle the LRU list under the workload’s feet. And it must not allocate, because some callers use it on a path where allocation is not allowed.

The cell: the whole trick in nine words

Here is the entire data structure:

cpp 
// src/Common/LRUCachePolicy.h:203
private:
    using LRUQueue = std::list<Key>;
    using LRUQueueIterator = typename LRUQueue::iterator;

    LRUQueue queue;

    struct Cell
    {
        MappedPtr value;
        size_t size{};
        LRUQueueIterator queue_iterator;
    };

    using Cells = std::unordered_map<Key, Cell, HashFunction>;

    Cells cells;

That is it. The entire “recency ordering” mechanism is the third field of Cell: an iterator into the linked list.

The design decision that makes it work is that the list stores keys, not cells. The list node is therefore just a Key (plus two list pointers), and the map holds the cell which points back into the list. The alternative — a list of cells, with the map storing pointers to cells — would be equivalent in asymptotics but would allocate the cell on the heap and require the map to store pointers, making the map’s values unstable under rehashing.

Storing the key in the list has one visible cost: the key is stored twice, once in the map and once in the list node. For a cache with a 16-byte key, that is 16 bytes of pure overhead per entry. ClickHouse accepts that trade because it buys a very cheap hit path.

Note also that size is cached in the cell rather than recomputed. The WeightFunction is documented as a pure function of the value:

cpp 
// src/Common/LRUCachePolicy.h:11
/// Cache policy LRU evicts entries which are not used for a long time. Also see cache policy SLRU for reference.
/// WeightFunction is a functor that takes Mapped as a parameter and returns "weight" (approximate size) of that value.
/// Cache starts to evict entries when their total weight exceeds max_size_in_bytes.
/// Value weight should not change after insertion.

“Value weight should not change after insertion” is a contract on the user of the cache. Because the weight is snapshotted at insert time, a value that grows afterwards will be mis-accounted. That is why the query result cache weighs an entry by the bytes its chunks actually allocated, not by some estimate that might drift.

The hit path: one splice

Here is get() in full:

cpp 
// src/Common/LRUCachePolicy.h:123
    MappedPtr get(const Key & key) override
    {
        auto it = cells.find(key);
        if (it == cells.end())
            return {};

        Cell & cell = it->second;

        /// Move the key to the end of the queue. The iterator remains valid.
        queue.splice(queue.end(), queue, cell.queue_iterator);

        return cell.value;
    }

Three lines of work:

  1. cells.find(key) — a hash lookup.
  2. queue.splice(queue.end(), queue, cell.queue_iterator) — move the node representing this key to the back of the list.
  3. Return the shared_ptr, bumping its refcount.

The splice is the interesting call. std::list::splice relinks nodes without allocating, copying, or moving any elements. It is O(1). The comment “The iterator remains valid” is the load-bearing part: after the splice, the cell’s stored queue_iterator still points at the (now moved) node, so a subsequent splice on the same cell works.

The list’s invariant is therefore:

text 
   front ............................................... back
   [oldest access] ... [newest access]

   get(k)  ==>  move k's node to the back
   set(k)  ==>  move k's node to the back
   evict   ==>  pop the front

Front is the least-recently-used entry; back is the most recent. Eviction pops the front.

Note what get() does not do: it does not touch cell.size, does not recompute the weight, and does not update any metric. A hit is a hash lookup and a pointer relink. That is the entire cost of an LRU hit.

The insert path

set() is a little longer because it has to handle the case where the key is already resident (an update rather than an insert):

cpp 
// src/Common/LRUCachePolicy.h:156
    void set(const Key & key, const MappedPtr & mapped) override
    {
        const size_t old_size_in_bytes = current_size_in_bytes;
        const size_t old_size = cells.size();

        auto [it, inserted] = cells.emplace(std::piecewise_construct,
            std::forward_as_tuple(key),
            std::forward_as_tuple());

        Cell & cell = it->second;

        if (inserted)
        {
            try
            {
                cell.queue_iterator = queue.insert(queue.end(), key);
            }
            catch (...)
            {
                cells.erase(it);
                throw;
            }
        }
        else
        {
            current_size_in_bytes -= cell.size;
            queue.splice(queue.end(), queue, cell.queue_iterator);
        }

        cell.value = mapped;
        cell.size = cell.value ? weight_function(*cell.value) : 0;
        current_size_in_bytes += cell.size;

        CurrentMetrics::add(current_size_in_bytes_metric, static_cast<Int64>(current_size_in_bytes) - old_size_in_bytes);
        CurrentMetrics::add(count_metric, static_cast<Int64>(cells.size()) - old_size);

        removeOverflow();
    }

Several details are worth calling out.

piecewise_construct with a tuple. This is the standard way to insert into an unordered_map without constructing a Cell you are about to throw away. emplace with piecewise_construct constructs the key and the mapped value in place in the node, so an update does not allocate a temporary Cell and then move it.

The try/catch around queue.insert. If the list insertion throws (bad alloc), the map entry is erased so the two containers stay consistent. If the list insert succeeded but the map insert had thrown, you would have a list node with no cell pointing at it — an entry that could never be evicted, and a permanent leak of its weight. The invariant is “the map and the list agree”, and this is where it is defended.

The update path subtracts the old weight. current_size_in_bytes -= cell.size before the new weight is computed. The new weight may be completely different (the value was replaced), and the total has to reflect that. Only after the new weight is known is the old one removed and the new one added — the two lines are separated by the weight_function call so that the subtraction never double-counts.

weight_function(*cell.value) is called on the dereferenced pointer. The dereference is deliberate: the weight function takes the value, not the pointer, and the null check cell.value ? ... : 0 guards the case where the policy is asked to store a null pointer.

Metrics are updated by delta, not by absolute value. CurrentMetrics::add takes the difference between the new and old totals, and this pattern is used everywhere in ClickHouse’s metrics code: the metric is a global counter shared by every instance of a cache, so each instance adds its own delta.

Eviction is triggered at the end of the insert, not lazily at the next lookup. The cache is always (just) within its limit, never over.

The eviction loop

cpp 
// src/Common/LRUCachePolicy.h:231
    void removeOverflow()
    {
        const size_t old_size_in_bytes = current_size_in_bytes;
        const size_t old_size = cells.size();

        size_t current_weight_lost = 0;
        size_t queue_size = cells.size();

        while ((current_size_in_bytes > max_size_in_bytes || (max_count != 0 && queue_size > max_count)) && (queue_size > 0))
        {
            const Key & key = queue.front();

            auto it = cells.find(key);
            if (it == cells.end())
                std::terminate(); // Queue became inconsistent

            const auto & cell = it->second;

            current_size_in_bytes -= cell.size;
            current_weight_lost += cell.size;
            /// Update cache-specific metrics.
            if (on_remove_entry_function)
                on_remove_entry_function(cell.size, cell.value);

            cells.erase(it);
            queue.pop_front();
            --queue_size;
        }

        if (current_size_in_bytes > (1ull << 63))
            std::terminate(); // Queue became inconsistent

        CurrentMetrics::sub(current_size_in_bytes_metric, old_size_in_bytes - current_size_in_bytes);
        CurrentMetrics::sub(count_metric, old_size - cells.size());
    }

Note the eviction condition: bytes over the limit OR count over the limit. max_count == 0 means “no count limit”, which is why the check is max_count != 0 && queue_size > max_count. Most ClickHouse caches pass max_count = 0 and are bounded purely by bytes, because the byte cost of a cached object varies by orders of magnitude (one mark file versus one query result).

The eviction loop is a while, not an if: a single insert can push a cache over its limit by more than one entry’s weight, and the loop evicts until it fits again.

Two std::terminate() calls guard the invariant. If the list’s front key is not in the map, the two containers have diverged and continuing would corrupt the cache; terminating loudly is the right response to a bug that should be impossible. The second one — current_size_in_bytes > (1ull << 63) — catches weight accounting underflow: if the accounting ever went negative it would wrap around to a huge positive number and the cache would stop evicting entirely.

The on_remove_entry_function callback is where per-entry eviction accounting happens. The mark cache uses it to count evicted files and evicted marks:

cpp 
// src/Storages/MarkCache.h:88
    void onEntryRemoval(const size_t weight_loss, const MappedPtr & mapped_ptr) override
    {
        /// File is the key of MarkCache, each removal means eviction of 1 file from the cache.
        ProfileEvents::increment(ProfileEvents::MarkCacheEvictedFiles);
        ProfileEvents::increment(ProfileEvents::MarkCacheEvictedBytes, weight_loss);

        const auto * marks_in_compressed_file = static_cast<const MarksInCompressedFile *>(mapped_ptr.get());
        ProfileEvents::increment(ProfileEvents::MarkCacheEvictedMarks, marks_in_compressed_file->getNumberOfMarks());
    }

That is a genuinely useful design: the policy knows when it evicts and what it evicted, but not what an eviction means. The subclass decides. And it means the eviction is observable from SQL:

sql 
SELECT sum(value) AS evicted_files
FROM system.events
WHERE event LIKE 'MarkCacheEvicted%';

The thread-safe wrapper

The policy is not thread-safe — it has no lock at all. Thread safety comes from CacheBase, which wraps a policy in a std::mutex:

cpp 
// src/Common/CacheBase.h:103
    MappedPtr get(const Key & key)
    {
        std::lock_guard lock(mutex);
        auto res = cache_policy->get(key);
        if (res)
            ++hits;
        else
            ++misses;
        return res;
    }

One mutex for the whole cache. That is a coarse lock, and it is the right choice here: the critical section is a hash lookup and a list splice, both nanoseconds, and a fine-grained lock would cost more in bookkeeping than the operation it protects. The values themselves are shared_ptrs and are not protected — a caller holding a pointer to an evicted value can keep using it safely, because the value’s lifetime is managed by the refcount, not by the cache’s mutex.

CacheBase also selects the policy by name, which is how the server setting mark_cache_policy reaches the cache:

cpp 
// src/Common/CacheBase.h:63
    /// Use this ctor if the user should be able to configure the cache policy and cache sizes via settings. Supports only general-purpose policies LRU, SLRU and SIEVE.
    explicit CacheBase(
        std::string_view cache_policy_name,
        CurrentMetrics::Metric size_in_bytes_metric,
        CurrentMetrics::Metric count_metric,
        size_t max_size_in_bytes,
        size_t max_count,
        double size_ratio)
    {
        auto on_remove_entry_function = makeOnRemoveEntryFunction();

        if (cache_policy_name.empty())
        {
            cache_policy_name = DEFAULT_CACHE_POLICY;
        }

        if (cache_policy_name == "LRU")
        {
            using LRUPolicy = LRUCachePolicy<TKey, TMapped, HashFunction, WeightFunction>;
            cache_policy = std::make_unique<LRUPolicy>(size_in_bytes_metric, count_metric, max_size_in_bytes, max_count, on_remove_entry_function);
        }
        else if (cache_policy_name == "SLRU")
        {
            using SLRUPolicy = SLRUCachePolicy<TKey, TMapped, HashFunction, WeightFunction>;
            cache_policy = std::make_unique<SLRUPolicy>(size_in_bytes_metric, count_metric, max_size_in_bytes, max_count, size_ratio, on_remove_entry_function);
        }
        else if (cache_policy_name == "SIEVE")
        {
            using SIEVEPolicy = SIEVECachePolicy<TKey, TMapped, HashFunction, WeightFunction>;
            cache_policy = std::make_unique<SIEVEPolicy>(size_in_bytes_metric, count_metric, max_size_in_bytes, max_count, on_remove_entry_function);
        }
        else
            throw Exception(ErrorCodes::BAD_ARGUMENTS, "Unknown cache policy name: {}", cache_policy_name);
    }

The default is not LRU:

cpp 
// src/Common/CacheBase.h:45
    static constexpr auto NO_MAX_COUNT = 0uz;
    static constexpr auto DEFAULT_SIZE_RATIO = 0.5l;
    static constexpr auto DEFAULT_CACHE_POLICY = "SLRU";

SLRU, with a protected-queue ratio of 0.5 — half the cache is reserved for entries that have been hit at least twice. That is a whole separate article, but the reason to mention it here is that LRU is the exception, not the rule. Every default in the tree is SLRU:

cpp 
// src/Core/Defines.h:106
/// Default maximum (total and entry) sizes and policies of various caches
static constexpr auto DEFAULT_UNCOMPRESSED_CACHE_POLICY = "SLRU";
static constexpr auto DEFAULT_UNCOMPRESSED_CACHE_MAX_SIZE = 0_MiB;
static constexpr auto DEFAULT_UNCOMPRESSED_CACHE_SIZE_RATIO = 0.5l;
static constexpr auto DEFAULT_MARK_CACHE_POLICY = "SLRU";
static constexpr auto DEFAULT_MARK_CACHE_MAX_SIZE = 5_GiB;
static constexpr auto DEFAULT_MARK_CACHE_SIZE_RATIO = 0.5l;

You can see it from SQL, because the policy names are server settings:

sql 
SELECT name, value, default
FROM system.server_settings
WHERE name IN ('mark_cache_policy', 'mark_cache_size', 'mark_cache_size_ratio');
text 
┌─name──────────────────┬─value─────────┬─default─────────┐
│ mark_cache_policy     │ SLRU          │ SLRU            │
│ mark_cache_size      │ 5368709120    │ 5368709120      │
│ mark_cache_size_ratio│ 0.5           │ 0.5             │
└──────────────────────┴───────────────┴─────────────────┘

(mark_cache_size is a UInt64, so it prints as a byte count: 5368709120 is 5 GiB, the default from DEFAULT_MARK_CACHE_MAX_SIZE.)

And you can change it:

sql 
SYSTEM RELOAD CONFIG;

with mark_cache_policy set to LRU, SLRU or SIEVE in the server config. The setting’s own documentation spells out the three choices:

cpp 
// src/Core/ServerSettings.cpp:653
    DECLARE(String, mark_cache_policy, DEFAULT_MARK_CACHE_POLICY, R"(Mark cache eviction policy name. Possible values: `LRU`, `SLRU`, `SIEVE`.)", 0) \

Cache stampede: the insert token

There is one more thing CacheBase does that is worth its own section, because it is the most subtle code in the file.

Consider a cache in front of an expensive resource — a DNS resolver, a mark file on disk, an S3 object. Ten threads all miss at the same moment. Without protection, all ten call the loader, all ten do the expensive work, and all ten try to insert. That is a cache stampede, and it is exactly what happens when a popular key expires.

CacheBase::getOrSet() prevents it with a per-key insert token:

cpp 
// src/Common/CacheBase.h:185
    template <typename LoadFunc>
    std::pair<MappedPtr, bool> getOrSet(const Key & key, LoadFunc && load_func)
    {
        InsertTokenHolder token_holder;
        {
            std::lock_guard cache_lock(mutex);
            auto val = cache_policy->get(key);
            if (val)
            {
                ++hits;
                return std::make_pair(val, false);
            }

            auto & token = insert_tokens[key];
            if (!token)
                token = std::make_shared<InsertToken>(*this);

            token_holder.acquire(&key, token, cache_lock);
        }

        InsertToken * token = token_holder.token.get();

        std::lock_guard token_lock(token->mutex);

        token_holder.cleaned_up = token->cleaned_up;

        if (token->value)
        {
            /// Another thread already produced the value while we waited for token->mutex.
            ++hits;
            return std::make_pair(token->value, false);
        }

        ++misses;
        token->value = load_func();

        std::lock_guard cache_lock(mutex);

        /// Insert the new value only if the token is still in present in insert_tokens.
        /// (The token may be absent because of a concurrent clear() call).
        bool result = false;
        auto token_it = insert_tokens.find(key);
        if (token_it != insert_tokens.end() && token_it->second.get() == token)
        {
            cache_policy->set(key, token->value);
            result = true;
        }

        if (!token->cleaned_up)
            token_holder.cleanup(token_lock, cache_lock);

        return std::make_pair(token->value, result);
    }

The protocol, in order:

  1. Under the cache mutex, look up the key. Hit? Return it.
  2. Still under the cache mutex, find or create an InsertToken for this key. Because this happens under the mutex, exactly one token exists per key.
  3. Release the cache mutex. The loader will be called without the cache lock held — this is essential, because the loader might itself touch the cache, or might block for a long time (a network read), and holding the cache lock through it would serialise the entire cache.
  4. Take the token’s own mutex. This is a different lock, per key. All threads that missed on this key are now queued on this one lock.
  5. Check token->value. If another thread already loaded it while we were waiting, return that value. We counted a hit, not a miss.
  6. Otherwise call load_func(). Because we hold the token’s mutex, exactly one thread runs the loader for this key.
  7. Re-take the cache mutex and insert, but only if our token is still the one registered for this key. A concurrent clear() may have wiped insert_tokens, in which case we do not insert (the value would be orphaned in a cleared cache).

The token itself:

cpp 
// src/Common/CacheBase.h:374
    /// Represents pending insertion attempt.
    struct InsertToken
    {
        explicit InsertToken(CacheBase & cache_) : cache(cache_) {}

        std::mutex mutex;
        bool cleaned_up TSA_GUARDED_BY(mutex) = false;
        MappedPtr value TSA_GUARDED_BY(mutex);

        CacheBase & cache;
        size_t refcount = 0; /// Protected by the cache mutex
    };

And the holder that makes sure the token gets removed from the map:

cpp 
// src/Common/CacheBase.h:389
    /// This class is responsible for removing used insert tokens from the insert_tokens map.
    /// Among several concurrent threads the first successful one is responsible for removal. But if they all
    /// fail, then the last one is responsible.
    struct InsertTokenHolder
    {
        const Key * key = nullptr;
        std::shared_ptr<InsertToken> token;
        bool cleaned_up = false;

        InsertTokenHolder() = default;

        void acquire(const Key * key_, const std::shared_ptr<InsertToken> & token_, std::lock_guard<std::mutex> & /* cache_lock */)
            TSA_NO_THREAD_SAFETY_ANALYSIS // disabled only because we can't reference the parent-level cache mutex from here
        {
            key = key_;
            token = token_;
            ++token->refcount;
        }

The refcount is the interesting bit. Suppose ten threads miss on key K. They all get the same token, all increment its refcount to 10. One of them runs the loader, inserts the value, and erases the token from insert_tokens. The other nine are waiting on the token’s mutex; when they wake up they see token->value is set and return it. Then each of them, as its InsertTokenHolder goes out of scope, decrements the refcount. Only the last one (refcount reaches zero) removes the token from the map.

Wait — the first thread already erased it. So why the refcount? Because of the failure path: if load_func() throws, the exception propagates out of getOrSet before the cleanup code runs. The InsertTokenHolder’s destructor is the backstop:

cpp 
// src/Common/CacheBase.h:416
        ~InsertTokenHolder()
        {
            if (!token)
                return;

            if (cleaned_up)
                return;

            std::lock_guard token_lock(token->mutex);

            if (token->cleaned_up)
                return;

            std::lock_guard cache_lock(token->cache.mutex);

            --token->refcount;
            if (token->refcount == 0)
                cleanup(token_lock, cache_lock);
        }

The destructor runs on the exception path. It takes the token lock (so it does not race with a thread that is currently loading), then the cache lock, and only removes the token if it was the last reference. If ten threads all had the loader throw, the token survives until the tenth one unwinds, and the next thread that misses on K gets a fresh token and retries the load. The comment says it exactly: “Among several concurrent threads the first successful one is responsible for removal. But if they all fail, then the last one is responsible.”

So the guarantees are:

  • At most one thread runs the loader per key, at a time.
  • A failed load does not poison the cache — the next caller retries.
  • The token map does not leak entries.

The price is a per-key std::mutex allocation on the miss path and a fair amount of subtle lock ordering. Note the lock order is always token mutex → cache mutex, never the reverse. The cache mutex is released before the token mutex is taken, so there is no path that holds the cache mutex while waiting for a token mutex. That is what makes the ordering deadlock-free.

Callers use it like this:

cpp 
// src/Common/DNSResolver.cpp:321
    auto [result, _ ] = impl->cache_host.getOrSet(host, [&host, this]() {return std::make_shared<DNSResolver::CacheEntry>(getResolvedIPAddressesWithFiltering(host), std::chrono::system_clock::now());});

The loader runs outside the cache lock, which is why the page cache can release a memory-tracker blocker before loading:

cpp 
// src/Common/PageCache.cpp:103
        std::tie(result, miss) = shard.getOrSet(key_hash, [&]() -> MappedPtr
        {
            /// At this point CacheBase is not holding the mutex, so it's ok to let MemoryTracker
            /// call autoResize.
            blocker.reset();

Trade-offs

What the linked list buys you. An O(1) hit that is also an O(1) recency update, with no allocation, no timestamp comparison, and no separate eviction structure to keep in sync. The cost of the hit is one pointer relink — a few nanoseconds — which is why the design tolerates doing it on every single lookup, including on paths that only wanted to check residency.

What it costs. The key is stored twice (map + list node), so a cache with a large key has a noticeable per-entry overhead. The whole cache is behind one mutex, so a cache used by many threads is a contention point — but the critical section is tiny.

Why the weight is snapshotted. It makes eviction O(1) per victim instead of O(size of value). The price is a contract: values must not change size after insertion. In practice ClickHouse works around this by weighing entries by their allocated size and by treating the cached object as immutable.

Why contains is not get. Because a residency check must not be an access. This is a small thing that shows up in real code: the page cache’s contains is used on paths where reordering the LRU list would be actively harmful.

Why SLRU is the default and LRU is not. Because a scan is the common case, not the exception. A query that touches ten thousand mark files will, under plain LRU, evict every mark file that the other queries were relying on. LRU is optimal for a workload where the access pattern is stationary; it is catastrophic for a workload with one dominant sequential scan. That is the next article.

Wrapping up

The one thing to remember: the cache is not “a map with timestamps”. It is a map of cells, and each cell holds an iterator into a linked list of keys. The recency order is not a property you compute; it is a property you maintain with one splice.

The part people get wrong: the weight is captured at insert time. If you put a value into the cache and then grow it, the cache’s byte accounting is wrong from that moment on, and it will evict the wrong things.

What to go do about it: look at SELECT metric, value FROM system.metrics WHERE metric LIKE '%Cache%' and compare the cache’s byte usage to its configured size. If a cache is chronically at its limit and its hit rate is low, that is usually a scan problem, not an LRU problem — and the fix is the policy setting, not the implementation.

ClickhouseInternalsCachingPerformanceData structures