How ClickHouse Stores Dictionaries in Sharded Hash Tables

TL;DR: The HASHED dictionary layout is a hash table per attribute, sharded up to 128 ways so it can be loaded by 128 threads at once. A composite key is serialized into a bump allocator so that “the key” is one string_view and one hash, and the concrete hash table is chosen by measured RSS — 22 GiB vs 26 GiB for a billion entries — not by taste. The CACHE layout is the opposite trade: it keeps only the hot keys, in RAM, and refetches them on demand.

A dictionary in ClickHouse is a lookup table on a hot path. dictGet is called per row, in the middle of a SELECT or an INSERT, and it has to be fast enough not to matter.

That gives the design its shape. A dictionary has to be:

in memory, because the alternative is a round trip per row;
keyed by a cheap hash, because the lookup happens millions of times;
refreshable without downtime, because the source data changes;
loadable in parallel, because a dictionary with a hundred million rows takes a while to read and the server should not be unresponsive while it happens.

ClickHouse has two answers to this, and they are the two layouts that matter here.

The compact key

The first question is what a “key” is. A HASHED dictionary can have a simple key (UInt64) or a complex key (several columns). The naive implementation of a complex key is to make a tuple, hash the tuple, compare tuples. That is slow and it is allocation-heavy.

ClickHouse does something much more brutal: it serializes the key columns into an arena, contiguously, and uses the resulting string_view as the key.

cpp
// src/Dictionaries/DictionaryHelpers.h:522
        else
        {
            size_t allocated_size_for_columns = 0;
            const char * block_start = nullptr;

            for (const auto & column : key_columns)
            {
                std::string_view serialized_data = column->serializeValueIntoArena(current_key_index, *complex_key_arena, block_start, nullptr);
                allocated_size_for_columns += serialized_data.size();
            }

            ++current_key_index;
            current_complex_key = std::string_view{block_start, allocated_size_for_columns};
            return  current_complex_key;
        }

The trick is block_start. Every key column’s serialized form is written adjacently in the arena — allocContinue hands out the next bytes — so the whole key is one contiguous range, and the key is a string_view over it. One hash, one comparison, no tuple.

For a String column, the serialization writes the length and the bytes:

cpp
// src/Columns/ColumnString.cpp:335
std::string_view ColumnString::serializeValueIntoArena(size_t n, Arena & arena, char const *& begin, const IColumn::SerializationSettings * settings) const
{
    bool serialize_string_with_zero_byte = settings && settings->serialize_string_with_zero_byte;

    size_t string_size = sizeAt(n) + serialize_string_with_zero_byte;
    size_t offset = offsetAt(n);

    auto result_size = sizeof(string_size) + string_size;
    char * pos = arena.allocContinue(result_size, begin);
    memcpy(pos, &string_size, sizeof(string_size));
    memcpy(pos + sizeof(string_size), &chars[offset], string_size - serialize_string_with_zero_byte);

Note that begin is passed by reference and updated by allocContinue — that is the mechanism that makes the columns land next to each other.

The arena is a bump allocator with geometric growth, and it is per shard, so the keys of one shard are contiguous in memory and a lookup touches one cache line range rather than several.

The extractor also has a rollbackCurrentKey(), used by the loader to reclaim the arena space of a key that turned out to be a duplicate:

cpp
// src/Dictionaries/DictionaryHelpers.h:539
    void rollbackCurrentKey() const
    {
        if constexpr (key_type == DictionaryKeyType::Complex)
            complex_key_arena->rollback(current_complex_key.size());
    }

The shard trick

A dictionary with a hundred million rows takes seconds to load from MySQL. That is a long time to hold a lock, and it is a long time to be unresponsive.

The fix is the SHARDS layout parameter: the dictionary is not one hash table, it is up to 128 of them, and each shard is filled by its own thread.

cpp
// src/Dictionaries/registerHashedDictionary.cpp:61
        Int64 shards = config.getInt64(config_prefix + dictionary_layout_prefix + ".shards", 1);
        if (shards <= 0 || shards > 128)
            throw Exception(ErrorCodes::BAD_ARGUMENTS,"{}: SHARDS parameter should be within [1, 128]", full_name);

The shard of a key is a hash of the key modulo the shard count:

cpp
// src/Dictionaries/HashedDictionary.h:233
    template <bool sharded_>
    UInt64 getShard(UInt64 key) const
    {
        if constexpr (!sharded_)
            return 0;
        /// NOTE: function here should not match with the DefaultHash<> since
        /// it used for the HashMap/sparse_hash_map.
        return intHashCRC32(key) % configuration.shards;
    }

The comment is important: the sharding hash (intHashCRC32) is deliberately not the hash used inside the table (DefaultHash). If they were the same, the shard assignment would be correlated with the table’s bucket distribution and the shards would be unevenly loaded. Using a different hash means the shard assignment is independent of the bucket layout.

Note also the sharded_ template parameter. Sharding is a runtime property, not a compile-time one — making it a template parameter would instantiate the entire dictionary twice — but the lookup loops still dispatch on it once per call, so that the non-sharded fast path keeps a constant shard index and does not pay for the hash-and-modulo in the inner loop:

cpp
// src/Dictionaries/HashedDictionary.h:226
    /// Sharding is a runtime property (`SHARDS` layout parameter), not a template parameter:
    /// making it a template parameter would instantiate the whole dictionary twice.
    /// The per-key lookup loops still dispatch on it once per call (via the `sharded_`
    /// template parameter below), so that the non-sharded fast path keeps a constant
    /// shard index and the hash+modulo does not get inlined into the loop body.
    bool sharded() const { return configuration.shards > 1; }

Loading in parallel

The loader is a ThreadPool with one worker per shard, and one bounded queue per shard:

cpp
// src/Dictionaries/HashedDictionaryParallelLoader.h:63
        for (size_t shard = 0; shard < shards; ++shard)
        {
            shards_queues[shard].emplace(backlog);

            try
            {
                pool.scheduleOrThrowOnError([this, shard, thread_group = getCurrentThreadGroup()]
                {
                    ThreadGroupSwitcher switcher(thread_group, ThreadName::HASHED_DICT_LOAD);

The main thread reads the source and scatters each block into per-shard blocks:

cpp
// src/Dictionaries/HashedDictionaryParallelLoader.h:98
    void addBlock(Block block)
    {
        IColumn::Selector selector = createShardSelector(block, shards_slots);
        Blocks shards_blocks = splitBlock(selector, block);
        block.clear();

        for (size_t shard = 0; shard < shards; ++shard)
        {
            const auto & current_block = shards_blocks[shard];
            while (!shards_queues[shard]->tryPush(current_block, /* milliseconds= */ 100))
            {

and the selector is built by computing the shard of every key:

cpp
// src/Dictionaries/HashedDictionaryParallelLoader.h:245
        DictionaryKeysExtractor<dictionary_key_type> keys_extractor(key_columns, arena_holder.getComplexKeyArena());
        for (size_t i = 0; i < num_rows; ++i)
        {
            auto key = keys_extractor.extractCurrentKey();
            size_t shard = dictionary.getShard(key);
            selector[i] = slots[shard];
            keys_extractor.rollbackCurrentKey();
        }

The rollbackCurrentKey() here is what keeps the arena from growing without bound: the key is serialized into the arena to compute its shard, and then the space is given back, because the real copy is made later, into the shard’s own arena.

The bounded queue is what provides backpressure. The loader thread blocks (milliseconds at a time) when a shard’s queue is full, and while it is blocked it checks two things: whether the workers are still alive, and whether the load has timed out:

cpp
// src/Dictionaries/HashedDictionaryParallelLoader.h:112
                /// We need to check if some workers failed
                if (pool.active() != shards)
                {
                    LOG_DEBUG(dictionary.log, "Some workers for dictionary {} failed, stopping all workers", dictionary_name);
                    stop_all_workers = true;
                    pool.wait(); /// We expect exception to be thrown from the failed worker thread
                    throw Exception(ErrorCodes::LOGICAL_ERROR, "Worker threads for dictionary {} are not active", dictionary_name);
                }

                if (loading_timeout.count() && std::chrono::milliseconds(total_loading_time.elapsedMilliseconds()) > loading_timeout)
                {
                    stop_all_workers = true;
                    pool.wait();
                    throw Exception(ErrorCodes::TIMEOUT_EXCEEDED, "Timeout {} sec for dictionary {} loading is expired", loading_timeout.count(), dictionary_name);
                }

The backlog parameter (SHARD_LOAD_QUEUE_BACKLOG, default 10000 blocks) is how much the loader may run ahead of the slowest shard.

The hash table choice

The HASHED layout uses ClickHouse’s own HashMap; the SPARSE_HASHED layout picks between google::sparse_hash_map and PackedHashMap, and the criterion is not “which is faster” but “which uses less memory”. The comment in the source has actual numbers in it:

cpp
// src/Dictionaries/HashedDictionaryCollectionType.h:46
/// HashMap with packed structure is better than google::sparse_hash_map if the
/// <K, V> pair is small, for the sizeof(std::pair<K, V>) == 16, RSS for hash
/// table with 1e9 elements will be:
///
/// - google::sparse_hash_map             : 26GiB
/// - HashMap                             : 35GiB
/// - PackedHashMap                       : 22GiB
/// - google::sparse_hash_map<packed_pair>: 17GiB
///
/// Also note here sizeof(std::pair<>) was used since google::sparse_hash_map
/// uses it to store <K, V>, yes we can modify google::sparse_hash_map to work
/// with packed analog of std::pair, but the allocator overhead is still
/// significant, because of tons of reallocations (and those cannot be solved
/// with reserve() due to some internals of google::sparse_hash_map) and poor
/// jemalloc support of such pattern, which results in 33% fragmentation (in
/// comparison with glibc).

So sparse_hash_map is only used when the value type is not a POD layout — because then the pair cannot be packed and sparse_hash_map’s per-allocation overhead is the lesser evil:

cpp
// src/Dictionaries/HashedDictionaryCollectionType.h:69
template <typename K, typename V>
constexpr bool useSparseHashForHashedDictionary()
{
    if constexpr (!isPodLayout<K>())
        return true;
    if constexpr (!isPodLayout<V>())
        return true;
    /// NOTE: One should not use PackedPairNoInit<K, V> here since this will
    /// create instantion of this type, and it could be illformed.
    return sizeof(V) > 8;
}

and “POD layout” is defined by hand, because the standard trait changed meaning in clang 16:

cpp
// src/Dictionaries/HashedDictionaryCollectionType.h:30
template <typename V>
constexpr bool isPodLayout()
{
    if constexpr (std::is_same_v<V, UUID>)
        return false;
    if constexpr (std::is_same_v<V, DateTime64>)
        return false;
    if constexpr (std::is_same_v<V, Decimal32> || std::is_same_v<V, Decimal64> || std::is_same_v<V, Decimal128> || std::is_same_v<V, Decimal256>)
        return false;
    if constexpr (std::is_same_v<V, std::string_view>)
        return false;
    if constexpr (std::is_same_v<V, IPv6> || std::is_same_v<V, IPv4>)
        return false;
    return true;
}

The load factor is also tunable, and the grower is a custom one, because the standard HashTableGrower uses a 50% maximum load factor and dictionaries want a higher one:

cpp
// src/Dictionaries/HashedDictionaryCollectionType.h:81
/// Grower with custom fill limit/load factor (instead of default 50%).
///
/// Based on HashTableGrowerWithPrecalculation
template <size_t initial_size_degree = 8>
class alignas(CH_CACHE_LINE_SIZE) HashTableGrowerWithPrecalculationAndMaxLoadFactor
{
    UInt8 size_degree = initial_size_degree;
    size_t precalculated_mask = (1ULL << initial_size_degree) - 1;
    size_t precalculated_max_fill = 1ULL << (initial_size_degree - 1);
    float max_load_factor = 0.5;

with the max_load_factor parameter validated between 0.5 and 0.99 at dictionary creation time.

Lifetime: the jitter trick

A dictionary must be refreshed, but when is a subtle problem. If every server in a cluster refreshes at the same moment, the source database gets a thundering herd of identical queries.

So the refresh time is randomized, uniformly, between the configured minimum and maximum lifetime:

cpp
// src/Interpreters/ExternalLoader.cpp:1298
            if (!error_count)
            {
                std::uniform_int_distribution<UInt64> distribution{lifetime.min_sec, lifetime.max_sec};
                auto result = std::chrono::system_clock::now() + std::chrono::seconds{distribution(rnd_engine)};
                LOG_TRACE(log, "Supposed update time for '{}' is {} (loaded, lifetime [{}, {}], no errors)",
                    loaded_object->getLoadableName(), to_string(result), lifetime.min_sec, lifetime.max_sec);
                return result;
            }

LIFETIME(MIN 300 MAX 600) therefore means “refresh somewhere between five and ten minutes from now, chosen at random”. The lifetime is parsed from the DDL:

cpp
// src/Interpreters/IExternalLoadable.cpp:9
ExternalLoadableLifetime::ExternalLoadableLifetime(const Poco::Util::AbstractConfiguration & config,
                                                   const std::string & config_prefix)
{
    const auto & lifetime_min_key = config_prefix + ".min";
    const auto has_min = config.has(lifetime_min_key);

    min_sec = has_min ? config.getUInt64(lifetime_min_key) : config.getUInt64(config_prefix);
    max_sec = has_min ? config.getUInt64(config_prefix + ".max") : min_sec;
}

Note the two failure modes handled here: a lifetime of zero means “never reload”, and an error switches the schedule from the lifetime to an exponential backoff:

cpp
// src/Interpreters/ExternalLoader.cpp:1307
            auto result = std::chrono::system_clock::now() + std::chrono::seconds(calculateDurationWithBackoff(rnd_engine, error_count));
            LOG_TRACE(log, "Supposed update time for '{}' is {} (backoff, {} errors)", loaded_object->getLoadableName(), to_string(result), error_count);

The backoff itself is randomized too, up to ten minutes:

cpp
// src/Interpreters/IExternalLoadable.cpp:20
UInt64 calculateDurationWithBackoff(pcg64 & rnd_engine, size_t error_count)
{
    constexpr UInt64 backoff_initial_sec = 5;
    constexpr UInt64 backoff_max_sec = 10 * 60; /// 10 minutes

    /// max seconds is 600 and 2 ** 10 == 1024
    error_count = std::clamp<size_t>(error_count, 1, 11);

    std::uniform_int_distribution<UInt64> distribution(0, static_cast<UInt64>(std::exp2(error_count - 1)));
    return std::min<UInt64>(backoff_max_sec, backoff_initial_sec + distribution(rnd_engine));
}

Lazy loading

A server may have a hundred dictionary definitions and use two of them. Loading all of them at startup is wasteful — and for a dictionary whose source is a slow external database, it is a startup delay for nobody.

So dictionaries are loaded lazily, on first access. The loader keeps an Info per dictionary with a NOT_LOADED state, and the first dictGet triggers the load:

cpp
// src/Interpreters/ExternalDictionariesLoader.cpp:110
ExternalDictionariesLoader::DictPtr ExternalDictionariesLoader::getDictionary(const std::string & dictionary_name, ContextPtr local_context) const
{
    std::string resolved_dictionary_name = resolveDictionaryName(dictionary_name, local_context);

    /// Check if we have a cancellable query context
    QueryStatusPtr process_list_element;
    if (local_context->hasQueryContext())
        process_list_element = local_context->getProcessListElement();

    std::shared_ptr<const IDictionary> dictionary;
    if (process_list_element)
    {
        /// Wait with periodic cancellation checks
        while (true)
        {
            auto result = tryLoad<LoadResult>(resolved_dictionary_name, /* timeout = */ std::chrono::milliseconds(1000));

The wait loop is the interesting part: the load happens on a background thread, and the query that triggered it polls every second, checking its own timeout between polls. So a query that waits for a dictionary to load can still be killed.

The lazy flag is per-object and can be overridden:

cpp
// src/Interpreters/ExternalLoader.cpp:766
    bool isObjectLazy(const ObjectConfig & config) const
    {
        return external_loader.getObjectLazyLoadOverride(*config.config, config.key_in_config).value_or(!always_load_everything);
    }

The `CACHE` layout: the opposite trade

HASHED loads everything. CACHE loads nothing, and fetches on demand.

The CACHE layout keeps a fixed number of cells in RAM. A lookup that misses — or that hits an expired cell — triggers a fetch from the source for exactly the missing keys.

The flow is spelled out in the source:

cpp
// src/Dictionaries/CacheDictionary.cpp:147
    /**
    * Flow of getColumnsImpl
    * 1. Get fetch result from storage
    * 2. If all keys are found in storage and not expired
    *   2.1. If storage returns fetched columns in order of keys then result is returned to client.
    *   2.2. If storage does not return fetched columns in order of keys then reorder
    *    result columns and return result to client.
    * 3. If all keys are found in storage but some of them are expired and we allow to read expired keys
    * start async request to source and perform actions from step 2 for result returned from storage.
    * 4. If some keys are found and some are not, start sync update from source.
    * 5. Aggregate columns returned from storage and source, if key is not found in storage and in source
    * use default value.
    */

Step 3 is the interesting one. If every key was found but some are stale, and allow_read_expired_keys is set, the dictionary serves the stale values immediately and refreshes in the background:

cpp
// src/Dictionaries/CacheDictionary.cpp:225
    if (not_found_keys_size == 0 && expired_keys_size > 0 && configuration.allow_read_expired_keys)
    {
        /// Start async update only if allow read expired keys and all keys are found
        update_queue.tryPushToUpdateQueueOrThrow(update_unit);

Otherwise the update is synchronous and the query waits:

cpp
// src/Dictionaries/CacheDictionary.cpp:240
    /// Start sync update
    update_queue.tryPushToUpdateQueueOrThrow(update_unit);
    update_queue.waitForCurrentUpdateFinish(update_unit);

The “expired” test is per cell, and the deadline is randomized per cell, not per dictionary:

cpp
// src/Dictionaries/SSDCacheDictionaryStorage.h:1424
    void setCellDeadline(Cell & cell, TimePoint now)
    {
        if (configuration.lifetime.min_sec == 0 && configuration.lifetime.max_sec == 0)
        {
            auto deadline = std::chrono::time_point<std::chrono::system_clock>::max() - 2 * std::chrono::seconds(configuration.strict_max_lifetime_seconds);
            cell.deadline = std::chrono::system_clock::to_time_t(deadline);
            return;
        }

        size_t min_sec_lifetime = configuration.lifetime.min_sec;
        size_t max_sec_lifetime = configuration.lifetime.max_sec;

        std::uniform_int_distribution<UInt64> distribution{min_sec_lifetime, max_sec_lifetime};
        auto deadline = now + std::chrono::seconds(distribution(rnd_engine));
        cell.deadline = std::chrono::system_clock::to_time_t(deadline);
    }

This is a nicer version of the lifetime trick: instead of refreshing the whole dictionary at once (a stampede on the source), each cell expires on its own schedule, so the refresh load spreads out over the whole lifetime window. A dictionary with a million cells and LIFETIME(MIN 300 MAX 600) trickles into the source continuously rather than in one spike.

There is also a strict maximum, beyond which a cell is treated as missing entirely:

cpp
// src/Dictionaries/SSDCacheDictionaryStorage.h:1074
            if (unlikely(now > cell.deadline + strict_max_lifetime_seconds))
            {
                ++result.not_found_keys_size;
                continue;
            }

The update queue itself is a bounded queue with a thread pool, so a burst of misses cannot spawn an unbounded number of source queries:

cpp
// src/Dictionaries/CacheDictionaryUpdateQueue.h:90
struct CacheDictionaryUpdateQueueConfiguration
{
    /// Size of update queue
    const size_t max_update_queue_size;
    /// Size in thead pool of update queue
    const size_t max_threads_for_updates;
    /// Timeout for trying to push update unit into queue
    const size_t update_queue_push_timeout_milliseconds;
    /// Timeout during sync waititing of update unit
    const size_t query_wait_timeout_milliseconds;
};

with the defaults max_update_queue_size = 100000, max_threads_for_updates = 4, update_queue_push_timeout_milliseconds = 10 and query_wait_timeout_milliseconds = 60000.

And if the source fails, the dictionary backs off and recovers by cloning the source, because the failed source may be holding a broken connection:

cpp
// src/Dictionaries/CacheDictionary.h:180
    DictionarySourcePtr getSourceAndUpdateIfNeeded() const
    {
        std::lock_guard lock(source_mutex);
        if (error_count)
        {
            /// Recover after error: we have to clone the source here because
            /// it could keep connections which should be reset after error.
            auto new_source_ptr = source_ptr->clone();
            source_ptr = std::move(new_source_ptr);
        }

        return source_ptr;
    }

Trying it

sql
CREATE DICTIONARY dict_hashed
(
    `id`     UInt64,
    `name`   String,
    `region` String
)
PRIMARY KEY id
SOURCE(CLICKHOUSE(TABLE 'dim_users' DB 'db'))
LAYOUT(HASHED(SHARDS 16))
LIFETIME(MIN 300 MAX 600);

-- A composite key: the key columns are packed into one blob.
CREATE DICTIONARY dict_complex
(
    `country` String,
    `city`    String,
    `population` UInt64
)
PRIMARY KEY country, city
SOURCE(CLICKHOUSE(TABLE 'dim_cities'))
LAYOUT(COMPLEX_KEY_HASHED(SHARDS 8))
LIFETIME(MIN 300 MAX 600);

-- The cache layout: nothing is loaded until it is needed.
CREATE DICTIONARY dict_cache
(
    `id`   UInt64,
    `data` String
)
PRIMARY KEY id
SOURCE(CLICKHOUSE(TABLE 'cache_src'))
LIFETIME(MIN 0 MAX 900)
LAYOUT(CACHE(SIZE_IN_CELLS 1000));

-- Nothing is cached yet, so nothing comes back and the source is not queried.
SELECT count() FROM dict_cache WHERE id IN (1, 2, 3);
-- 0

-- Looking the keys up populates the cache.
SELECT dictGet('dict_cache', 'data', toUInt64(number + 1)) FROM numbers(3);

-- And now the same read sees them.
SELECT count() FROM dict_cache WHERE id IN (1, 2, 3);
-- 3

Trade-offs

What the hashed layout buys you:

A cheap key. One hash and one comparison per lookup, even for a multi-column key, because the key is one contiguous arena blob.
Parallel loading. 128 shards, 128 threads, and a source read that is scattered rather than duplicated.
A measured memory footprint. The choice between sparse_hash_map and PackedHashMap is made with RSS numbers in the source comment, not by intuition.
A tunable load factor. Dictionaries want to be denser than the default 50%, and the custom grower makes that possible.

What it costs:

Everything is in RAM. A HASHED dictionary with a hundred million rows will not fit on a small server, and there is no spill-to-disk option.
The shard hash is a second hash. Every lookup with SHARDS > 1 computes intHashCRC32(key) % shards in addition to the table’s own hash. That is deliberate — using the same hash would correlate shard load with bucket layout — but it is not free.
The arena is per shard and grows geometrically. A dictionary that is updated in place grows its arenas; there is no compaction.
Complex keys are bigger than they look. The serialized form of a String key is 8 bytes of length plus the bytes, so a 20-byte string key costs 28 bytes plus the hash table’s own overhead.

What the cache layout buys you:

Bounded memory. SIZE_IN_CELLS is a hard cap.
Fresh data, with a bounded staleness window. Each cell expires on its own randomized schedule.
No startup cost. Nothing is loaded until it is looked up.