Opensource internals

ClickHouse Recycles Small Objects Through Per-Size Free Lists

18 min read Jay Hubbert

ClickHouse's ArenaWithFreeLists keeps fourteen free lists, one per power-of-two size class, and threads the free-list link through the freed block itself - so recycling a string costs a pointer write.

TL;DR: A plain arena can allocate but not free. ArenaWithFreeLists adds fourteen free lists — one per power-of-two size class from 8 to 65536 bytes — and stores the “next free block” pointer inside the freed block itself, using a union. Recycling a 20-byte string is: find its size class, unlink the head of the list, done. No malloc, no free, no metadata.

Memory management in a database is a fight between two contradictory requirements. You want to allocate millions of tiny objects quickly — strings, keys, small arrays — without paying the general-purpose allocator’s price on every one. And you want to give some of them back when they become garbage, without the bookkeeping that makes a general-purpose allocator general-purpose.

ClickHouse’s answer is a pair of classes. Arena is the classic bump allocator: allocate fast, never free, release everything at once. ArenaWithFreeLists is the interesting one: it adds per-size-class free lists so that individual allocations can be recycled.

The trick that makes it work is in the details, and the details are where all the good stuff is.

The problem: an arena cannot free

Arena is a list of memory chunks with a bump pointer:

cpp 
// src/Common/Arena.h:23
/** Memory pool to append something. For example, short strings.
  * Usage scenario:
  * - put lot of strings inside pool, keep their addresses;
  * - addresses remain valid during lifetime of pool;
  * - at destruction of pool, all memory is freed;
  * - memory is allocated and freed by large MemoryChunks;
  * - freeing parts of data is not possible (but look at ArenaWithFreeLists if you need);
  */
class Arena : private boost::noncopyable

That comment is a complete specification, including the limitation. The allocation path is a pointer bump:

cpp 
// src/Common/Arena.h:213
    /// Get piece of memory, without alignment.
    /// Note: we expect it will return a non-nullptr even if the size is zero.
    char * alloc(size_t size)
    {
        used_bytes += size;
        if (unlikely(head.empty() || size > head.remaining()))
            addMemoryChunk(size);

        char * res = head.pos;
        head.pos += size;
        ASAN_UNPOISON_MEMORY_REGION(res, size + pad_right);
        return res;
    }

Two things to notice.

The pad_right padding. pad_right is PADDING_FOR_SIMD - 1, which is 63 bytes:

cpp 
// src/Common/Arena.h:34
    static constexpr size_t pad_right = PADDING_FOR_SIMD - 1;

Every allocation is followed by 63 bytes of untouched (and ASAN-poisoned) padding. That exists so that SIMD code can read 64 bytes starting at any allocation boundary without reading out of bounds. ClickHouse’s string functions and hash functions read in 64-byte blocks, and without the padding every SIMD loop would need a tail-handling branch. This is a real, measurable trade: 63 bytes of slack per allocation, in exchange for branch-free SIMD.

The used_bytes accounting. The arena tracks two numbers: allocated_bytes (how much it took from the OS) and used_bytes (how much it handed out). The difference is the slack.

The chunk list. Chunks are never reused or returned individually:

cpp 
// src/Common/Arena.h:36
    /// Contiguous MemoryChunk of memory and pointer to free space inside it. Member of single-linked list.
    struct alignas(16) MemoryChunk : private Allocator<false>    /// empty base optimization
    {
        char * begin = nullptr;
        char * pos = nullptr;
        char * end = nullptr; /// does not include padding.

        std::unique_ptr<MemoryChunk> prev;

Note alignas(16) and the Allocator<false> base — the false is clear_memory_, meaning the arena does not zero the memory it hands out. Arena memory is assumed to be written before it is read.

The growth policy is where the arena gets interesting, because the naive version of “double the chunk size” has a pathological case:

cpp 
// src/Common/Arena.h:103
    /// Uses exponential buffer growth below `linear_growth_threshold` and linear growth above it
    /// to limit unused capacity.
    template <typename Size>
    Size nextSize(Size min_next_size) const
    {
        Size size_after_grow = 0;

        if (head.empty())
        {
            size_after_grow = std::max<Size>(min_next_size, initial_size);
        }
        else if (head.size() < linear_growth_threshold)
        {
            size_after_grow = std::max(min_next_size, Size(head.size()) * growth_factor);
        }
        else
        {
            /// With `allocContinue`, appending small amounts can repeatedly copy the accumulated data
            /// into a new `MemoryChunk`. Growing by similarly small amounts would make the number of
            /// copies proportional to the serialized size, resulting in quadratic work. Rounding the
            /// next size up to `linear_growth_threshold` makes these copies less frequent.
            size_after_grow = ((min_next_size + linear_growth_threshold - 1)
                    / linear_growth_threshold) * linear_growth_threshold;
        }

        chassert(size_after_grow >= min_next_size);
        return roundUpToPageSize(size_after_grow, page_size);
    }

Exponential growth (doubling, growth_factor = 2) up to linear_growth_threshold (128 MiB by default), and linear growth above it. The reason is allocContinue, which appends to the last allocation and sometimes has to copy the whole thing into a new chunk. Under exponential growth, repeatedly appending small amounts would copy the accumulated data O(log n) times, which is fine — but under a regime where each copy is proportional to the total size, the copies become quadratic. Rounding the next chunk size up to a multiple of the threshold makes the copies rare.

Both sizes are finally rounded up to a page boundary, because the underlying allocator wants page-aligned memory.

The free-list arena

Now the interesting class. ArenaWithFreeLists wraps an Arena and adds free lists:

cpp 
// src/Common/ArenaWithFreeLists.h:16
/** Unlike Arena, allows you to release (for later re-use)
  *  previously allocated (not necessarily just recently) chunks of memory.
  * For this, the requested size is rounded up to the power of two
  *  (or up to 8, if less, or using memory allocation outside Arena if the size is greater than 65536).
  * When freeing memory, for each size (14 options in all: 8, 16 ... 65536),
  *  a single-linked list of free blocks is kept track.
  * When allocating, we take the head of the list of free blocks,
  *  or, if the list is empty - allocate a new block using Arena.
  */
class ArenaWithFreeLists : private Allocator<false>, private boost::noncopyable
{
private:
    /// If the block is free, then the pointer to the next free block is stored at its beginning, or nullptr, if there are no more free blocks.
    /// If the block is used, then some data is stored in it.
    union Block
    {
        Block * next;
        char data[0];
    };

    /// The maximum size of a piece of memory that is allocated with Arena. Otherwise, we use Allocator directly.
    static constexpr size_t max_fixed_block_size = 65536;

    /// Get the index in the freelist array for the specified size.
    static size_t findFreeListIndex(const size_t size)
    {
        return size <= 8 ? 2 : bitScanReverse(size - 1);
    }

    /// Arena is used to allocate blocks that are not too large.
    Arena pool;

    /// Lists of free blocks. Each element points to the head of the corresponding list, or is nullptr.
    /// The first two elements are not used, but are intended to simplify arithmetic.
    Block * free_lists[16] {};

Four ideas in thirty lines.

cpp 
// src/Common/ArenaWithFreeLists.h:30
    union Block
    {
        Block * next;
        char data[0];
    };

A freed block’s first eight bytes are reinterpreted as a pointer to the next free block. The block’s own payload is dead — nothing will read it again — so its storage is free to hold the list link.

This is the reason the whole scheme is cheap. A conventional free list needs a separate node per block (extra allocation, extra memory) or a side table. Here, the free block is the node. The free list is a singly linked list threaded through the memory it manages.

char data[0] is a zero-length array, a C89-ism that GCC and Clang accept as “a pointer to where the payload would start”. The union guarantees that data and next alias the same address, so free_block_ptr->data is the payload pointer and free_block_ptr->next is the list link.

2. Size classes: fourteen buckets

free_lists[16] is an array of 16 list heads. The comment says “The first two elements are not used, but are intended to simplify arithmetic.” Indices 2 through 15 are the fourteen real size classes: 8, 16, 32, …, 65536 bytes.

The mapping from a requested size to a class is:

cpp 
// src/Common/ArenaWithFreeLists.h:40
    static size_t findFreeListIndex(const size_t size)
    {
        return size <= 8 ? 2 : bitScanReverse(size - 1);
    }

bitScanReverse(x) is the “find the highest set bit” operation:

cpp 
// src/Common/BitHelpers.h:66
/** Returns log2 of number, rounded down.
  * Compiles to single 'bsr' instruction on x86.
  * For zero argument, result is unspecified.
  */
template <typename T>
inline uint32_t bitScanReverse(T x)
{
    return (std::max<size_t>(sizeof(T), sizeof(unsigned int))) * 8 - 1 - getLeadingZeroBitsUnsafe(x);
}

So findFreeListIndex(size) is floor(log2(size - 1)) for size > 8. Let’s check it against the size classes:

requested sizesize - 1bitScanReverseindexblock size
8——28
983316
16153316
17164432
6553665535151565536

The size - 1 is the classic “round up to a power of two” trick: for size = 16, size - 1 = 15 has its highest bit at position 3, so the index is 3, and the block is 1 << (3 + 1) = 16 bytes. For size = 17, size - 1 = 16 has its highest bit at position 4, index 4, block 1 << 5 = 32 bytes.

The index is one less than the log of the block size because index 2 is special-cased to mean “8 bytes” — the size <= 8 branch — and 8 is 2^3, so index 3 would be 16 bytes if the arithmetic were 1 << index. With 1 << (index + 1): index 2 → 8, index 3 → 16, index 15 → 65536. Correct.

The cost of rounding up is internal fragmentation: a 17-byte request occupies 32 bytes. For a dictionary with millions of short keys, that is the price of being able to recycle.

3. The freelist array is a fixed-size array on the stack

Block * free_lists[16] {} — 128 bytes, value-initialised to null. No allocation, no hash map, no indirection. The size class of a request is computed with one instruction (bsr), and the resulting list head is at a fixed offset in an array. That is about as cheap as a size class lookup can get.

4. Big allocations bypass the arena entirely

cpp 
// src/Common/ArenaWithFreeLists.h:37
    static constexpr size_t max_fixed_block_size = 65536;

Requests above 64 KiB go straight to Allocator<false>::alloc — the general purpose allocator — and are freed back to it. The arena only handles the small stuff, where the recycling machinery pays for itself. A 64 KiB block is big enough that the malloc overhead is negligible relative to the block size.

The allocation path

cpp 
// src/Common/ArenaWithFreeLists.h:60
    char * alloc(const size_t size)
    {
        if (size > max_fixed_block_size)
            return static_cast<char *>(Allocator<false>::alloc(size));

        /// find list of required size
        const auto list_idx = findFreeListIndex(size);

        /// If there is a free block.
        if (auto & free_block_ptr = free_lists[list_idx])
        {
            /// Let's take it. And change the head of the list to the next
            /// item in the list. We poisoned the free block before putting
            /// it into the free list, so we have to unpoison it before
            /// reading anything.
            ASAN_UNPOISON_MEMORY_REGION(free_block_ptr,
                                        std::max(size, sizeof(Block)));

            auto * const res = free_block_ptr->data;
            free_block_ptr = free_block_ptr->next;
            return res;
        }

        /// no block of corresponding size, allocate a new one
        return pool.alloc(1ULL << (list_idx + 1));
    }

Read it as four steps.

  1. Too big? Hand it to the general allocator.
  2. Find the class. One bsr.
  3. Is there a free block? If the list head is non-null:
    • Unpoison the memory (see below).
    • res = free_block_ptr->data — the payload pointer.
    • free_block_ptr = free_block_ptr->next — pop the head. The list is threaded through the block, so popping it means reading the next pointer out of the block we are about to hand out.
  4. No free block? Ask the arena for a new one, of exactly the class size: pool.alloc(1ULL << (list_idx + 1)).

Step 3’s third line is the elegant bit: because the list link is stored in the block, popping the head and getting the payload pointer are the same memory read. There is no separate list node to free.

Note the size passed to pool.alloc is the rounded size, so the arena hands out a block that exactly matches the class. The arena’s own padding still applies (the pool is an Arena, whose alloc adds pad_right).

The free path

cpp 
// src/Common/ArenaWithFreeLists.h:87
    void free(char * ptr, const size_t size)
    {
        if (size > max_fixed_block_size)
        {
            Allocator<false>::free(ptr, size);
            return;
        }

        /// find list of required size
        const auto list_idx = findFreeListIndex(size);

        /// Insert the released block into the head of the list.
        auto & free_block_ptr = free_lists[list_idx];
        auto * const old_head = free_block_ptr;
        free_block_ptr = reinterpret_cast<Block *>(ptr);
        free_block_ptr->next = old_head;

        /// The requested size may be less than the size of the block, but
        /// we still want to poison the entire block.
        /// Strictly speaking, the free blocks must be unpoisoned in
        /// destructor, to support an underlying allocator that doesn't
        /// integrate with asan. We don't do that, and rely on the fact that
        /// our underlying allocator is Arena, which does have asan integration.
        ASAN_POISON_MEMORY_REGION(ptr, 1ULL << (list_idx + 1));
    }

The free path is the mirror image: compute the class, write the old head into the block’s next field, and make the block the new head.

Two subtleties:

The caller must pass the size. free(ptr, size) needs the size to recompute the class. If the caller passes a different size than it allocated with, the block goes into the wrong list and will later be handed out for a size it does not fit. Every caller in the tree passes the same size it allocated with.

The ASAN poisoning is over the whole block, not the requested size. The comment explains why: the block in the free list is bigger than the request (the rounded-up size), and the unused tail must also be poisoned, or ASAN would not catch a use-after-free that reads into the tail.

And the poisoning creates an obligation on the allocation path: you cannot read the next pointer out of a poisoned block, because ASAN would report a read of poisoned memory. That is why alloc unpoisons before reading free_block_ptr->next:

cpp 
// src/Common/ArenaWithFreeLists.h:75
            ASAN_UNPOISON_MEMORY_REGION(free_block_ptr,
                                        std::max(size, sizeof(Block)));

std::max(size, sizeof(Block)) — unpoison at least size bytes (the caller’s payload) and at least sizeof(Block) (8 bytes, so the next pointer can be read). The two constraints are different: the payload must be unpoisoned for the caller to write to, and the link must be unpoisoned for us to read.

The comment about the destructor admits a real limitation: strictly, the free blocks should be unpoisoned when the arena is destroyed, so that an underlying allocator without ASAN integration does not receive poisoned memory. The code relies on the underlying Arena having ASAN integration, which it does because Arena::alloc unpoisons on allocation and Arena’s destructor hands the chunk back to Allocator, which… let me check.

Actually, this matters: ArenaWithFreeLists inherits privately from Allocator<false>, and the Arena member’s destructor frees the chunks back to Allocator<false>::free, which calls __real_free. If the chunks contain poisoned free-list blocks, ASAN would complain when the memory is freed. Let me look at how the arena handles this.

cpp 
// src/Common/Arena.h:68
        ~MemoryChunk()
        {
            if (empty())
                return;

            /// We must unpoison the memory before returning to the allocator,
            /// because the allocator might not have asan integration, and the
            /// memory would stay poisoned forever. If the allocator supports
            /// asan, it will correctly poison the memory by itself.
            ASAN_UNPOISON_MEMORY_REGION(begin, size());

            Allocator<false>::free(begin, size());
        }

There it is — the arena’s chunk destructor unpoisons the whole chunk before handing it back. That is the guarantee the free-list arena relies on, and the comment in ArenaWithFreeLists::free is pointing exactly at it.

Who uses it

The interesting users are the ones that need to replace keys, not just accumulate them.

The cache dictionary

CacheDictionary keeps a fixed-size array of cells, each holding a key and its attributes. When an entry is updated with a different key, the old key’s string has to be released:

cpp 
// src/Dictionaries/CacheDictionaryStorage.h:447
                if (cell.key != key)
                {
                    if constexpr (std::is_same_v<KeyType, std::string_view>)
                    {
                        char * data = const_cast<char *>(cell.key.data());
                        arena.free(data, cell.key.size());
                        cell.key = copyStringInArena(arena, key);
                    }
                    else
                        cell.key = key;
                }

arena.free then copyStringInArena — the recycle-then-allocate pair. The string view is const, so the const_cast is needed to hand the pointer back to the arena. The cell.key.size() is the size the string was originally allocated with, which is what makes the size class lookup work.

Space-Saving, which powers topK

The topK aggregate function keeps the K most frequent elements and needs to free the strings of the ones it drops:

cpp 
// src/Common/SpaceSaving.h:420
            const UInt64 alpha_mask = alpha_map.size() - 1;
            for (size_t i = requested_capacity; i < counter_list.size(); ++i)
            {
                size_t pos = counter_list[i].hash & alpha_mask;
                alpha_map[pos] = std::min(alpha_map[pos] + counter_list[i].count - counter_list[i].error, MAX_ALPHA_VALUE);
                arena.free(counter_list[i].key);
            }

And SpaceSaving has a whole arena adapter for the string_view specialisation:

cpp 
// src/Common/SpaceSaving.h:50
/*
 * Specialized storage for std::string_view with a freelist arena.
 * Keys of this type that are retained on insertion must be serialized into local storage,
 * otherwise the reference would be invalid after the processed block is released.
 */
template <>
struct SpaceSavingArena<std::string_view>
{
    std::string_view emplace(std::string_view key)
    {
        if (!key.data())
            return key;

        return copyStringInArena(arena, key);
    }

    void free(std::string_view key)
    {
        if (key.data())
            arena.free(const_cast<char *>(key.data()), key.size());
    }

private:
    ArenaWithFreeLists arena;
};

Note the comment: “Keys of this type that are retained on insertion must be serialized into local storage, otherwise the reference would be invalid after the processed block is released.” The arena’s job is to make the string_view stable for as long as the aggregate state lives, and the free list makes the replacement cheap.

The generic helper that does the copying:

cpp 
// src/Common/ArenaUtils.h:10
template <typename Arena>
inline std::string_view copyStringInArena(Arena & arena, std::string_view value)
{
    size_t value_size = value.size();
    char * place_for_key = arena.alloc(value_size);
    memcpy(reinterpret_cast<void *>(place_for_key), reinterpret_cast<const void *>(value.data()), value_size);
    return std::string_view{place_for_key, value_size};
}

It is a template over the arena type, so it works with both Arena and ArenaWithFreeLists. The std::string_view{place_for_key, value_size} constructor takes the pointer and the length explicitly, so the string is not NUL-terminated — which is fine for a view, and saves a byte.

Seeing it from SQL

The topK aggregate function is the most visible user:

sql 
SELECT topK(3)(AirlineID) AS res
FROM VALUES('AirlineID UInt32', (19393), (19393), (19393), (19393), (19790), (19790), (19790), (19805), (19805), (20304));
text 
┌─res─────────────────┐
│ [19393,19790,19805] │
└─────────────────────┘

If the same query runs repeatedly with changing keys, the free list is what keeps the aggregate state’s memory flat instead of growing. And you can watch the state grow with:

sql 
SELECT
    query,
    formatReadableSize(memory_usage) AS state_size
FROM system.query_log
WHERE type = 'QueryFinish' AND memory_usage > 100000000
ORDER BY memory_usage DESC
LIMIT 10;

The point is not that topK uses an arena — the point is that the arena’s memory is recycled, so a long-running topK over a stream of changing keys does not accumulate garbage.

Trade-offs

What the free list buys you. Recycling a small object costs a class computation and a pointer write, instead of a free() call into the general allocator (which typically means a lock, a free-list walk, and a coalescing step). For the dictionary workload — millions of short keys, replaced individually — that difference is the whole point.

What it costs. Internal fragmentation: a 17-byte request occupies 32 bytes. The class list only has fourteen buckets, so the worst case is nearly 2x wasted. And the size must be tracked by the caller, since free needs it.

What the union buys you. The free list costs zero extra memory and zero extra allocation. There is no side table, no per-block header, no node to allocate. The price is that the block’s contents are destroyed on free — which is exactly what you want, since they were garbage anyway.

What the union costs you. You cannot read the first eight bytes of a free block (they hold the link), and you cannot distinguish a free block from a live one by looking at it. ASAN needs to be told which is which, which is why the poisoning is deliberate and the unpoisoning is explicit. A bug that frees the same pointer twice will silently corrupt the free list rather than crashing — the second free would write a new next pointer over the first one, and the list would then contain a cycle or a duplicate.

The part people get wrong. The free must be given the same size that was allocated. Passing a different size puts the block in the wrong class and the corruption is silent and delayed: the block is handed out later for a size it may not fit, and the overflow is a heap buffer overrun in somebody else’s code.

What to go do about it. If you are writing a ClickHouse-side component that holds many short-lived strings and has to replace them individually, ArenaWithFreeLists is the right tool. If you only ever append and never free, plain Arena is simpler and has no fragmentation. If the objects are large, neither is worth it — use the general allocator.

Wrapping up

The one thing to remember: the free-list link lives inside the freed block. That is why there is no per-block metadata, no side table, and no allocation on the free path. It is also why the block’s contents are unrecoverable after a free.

The part people get wrong: the size class is derived from the size you pass to free, not from anything stored in the block. A mismatch is silent corruption.

What to go do about it: look at where ArenaWithFreeLists is used in the tree — the cache dictionary and SpaceSaving — and notice that both use it in the same shape: allocate a string, store a view to it, and free the view when the entry is replaced. If your component has that shape, this class is already written for you.

ClickhouseInternalsMemoryPerformanceData structures