skip to content

A session cache std::unordered_map keyed by user id and device id slows down under load although load_factor() looks normal; how do you diagnose and fix it?

level: seniorimportance: should knowfreq 40%

answer

  1. an average hides one bucket
  2. bucket(key) and bucket_size(n)
  3. integer hashes are the identity
  4. symmetric combine collapses keys
  5. attacker-chosen keys

basics

~20 s

Suspect the hash, not the table size: load_factor() is an average that hides one overloaded bucket. Measure bucket_size(bucket(key)) and the largest bucket, then replace a weak combine such as user ^ device with one that mixes every field.

solid answer

~50 s

`load_factor()` is `size() / bucket_count()`, so a table can report a healthy 0.78 while one bucket holds every element. When keys collide, each lookup walks the whole chain: the standard's worst case for `find` is O(`size()`), and building the table becomes quadratic. Diagnose with the bucket interface: `bucket(key)` for a slow key, `bucket_size(n)` for its chain, a scan for the largest bucket, and `begin(n)`/`end(n)` to see which keys share it. In the code example a hash of `user_id ^ device_id` put all 20,000 sessions with `user_id == device_id` in one bucket. Fix the combine so every field is mixed, remembering that libc++ and libstdc++ hash integers to themselves. If keys come from untrusted clients, assume collisions can be forced: the standard string hashes in those libraries are deterministic, with no per-process seed, so add a per-process secret seed or cap the input.

code

cpp · 23 lines
cpp
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <unordered_map>

struct SessionKey {
    std::uint64_t user_id, device_id;
    bool operator==(const SessionKey&) const = default;  // C++20
};
struct XorHash {  // looks reasonable, but every key with user_id == device_id hashes to 0
    std::size_t operator()(const SessionKey& k) const noexcept { return k.user_id ^ k.device_id; }
};

int main() {
    std::unordered_map<SessionKey, int, XorHash> cache;
    for (std::uint64_t i = 0; i < 20000; ++i) cache.emplace(SessionKey{i, i}, 0);

    std::size_t worst = 0;
    for (std::size_t b = 0; b < cache.bucket_count(); ++b) worst = std::max(worst, cache.bucket_size(b));

    std::cout << "size " << cache.size() << ", buckets " << cache.bucket_count()
              << ", load_factor " << cache.load_factor() << ", largest bucket " << worst << '\n';
}

go deeper

for a junior

Know that std::unordered_map lookups slow down when many keys share a bucket, and that a good hash spreads keys across buckets.

for a middle

Use bucket, bucket_size and local iterators to inspect collisions, and explain why load_factor alone cannot reveal them.

for a senior

Diagnose a degraded cache from bucket statistics, replace weak combines, and seed or bound hashing when clients control the keys.

for a principal

Decide which tables face untrusted keys and require seeded hashing or a worst-case-bounded container there, trading speed for predictability.

## Why the averages lie A `std::unordered_map` has one global statistic, `load_factor() == size() / bucket_count()`, and keeps it under `max_load_factor()` by adding buckets. That bounds the **average** chain length; it says nothing about the **distribution**. If the hash sends many keys to one bucket, the average stays fine while every lookup for those keys compares against the whole chain. The standard's complexity clauses reflect this: `find` is O(1) on average and O(`size()`) in the worst case, and inserting n colliding keys costs O(n^2) in total. The symptoms in a session cache look like a capacity problem: p99 latency climbs with traffic, CPU goes to `operator==` calls inside the container, and adding memory does nothing. ## Measuring with the bucket interface Unordered containers expose their layout through standard members: - `bucket_count()` and `load_factor()`: the global numbers. - `bucket(k)`: the index of the bucket key `k` maps to. - `bucket_size(n)`: how many elements bucket `n` holds, costing O(`bucket_size(n)`). - `begin(n)` and `end(n)`: **local iterators** over one bucket, to see which keys collide. A diagnostic that loops over all buckets and reports the largest `bucket_size`, plus `bucket_size(bucket(slow_key))` for keys from slow requests, distinguishes a collision problem from a size problem in one run. In the code example the result was `load_factor 0.777696, largest bucket 20000`: a normal-looking load factor over a table that is effectively a linked list. ## How hashes fail in practice 1. **Symmetric or cancelling combines.** `user_id ^ device_id` maps `(a, b)` and `(b, a)` together and sends every key with equal fields to 0. Sum-based combines have similar structure. 2. **Identity integer hashes.** `std::hash<int>` and `std::hash<std::uint64_t>` return the value itself in both libc++ and libstdc++, so a combine that only adds or XORs ids inherits every pattern in the id space. 3. **Partial keys.** Hashing only `user_id` is legal, because equal keys still hash equal, but one heavy user with thousands of devices becomes one long chain. 4. **Adversarial input.** When clients choose key material (session tokens, headers, user names), they can search offline for many keys with the same hash. The string hashes in libc++ (based on CityHash or MurmurHash2, depending on `size_t` width) and libstdc++ (`_Hash_bytes` with a fixed seed) are deterministic, unseeded per process, so such collisions are reusable against every process. The standard's own wording is a quality goal at *should* strength: the probability that two different values hash equal should be very small. Meeting it is the hasher author's job. ## Fixing the session cache 1. **Replace the combine.** Hash each field, then mix: multiply by a large odd constant and fold with shifts, or apply a known 64-bit finalizer to each step, so that field order and every bit of each id affect the result. 2. **Verify with the same diagnostic.** The largest bucket should drop to a small number, close to what a random hash gives at that load factor. 3. **Seed when keys are attacker-controlled.** Give the hasher a secret per-process seed mixed into every hash, generated at startup; the key-equality rule still holds because the seed is constant for the program's run. 4. **Bound the damage.** Cap how many sessions one client can create, and reject absurd key sizes before hashing. 5. **Consider a guaranteed bound.** If worst-case latency matters more than the average, an ordered `std::map` gives O(log n) per lookup whatever the keys. ## Keeping it fixed - Export the **largest bucket size** and the load factor from long-lived caches alongside latency metrics, so a hash regression shows up as a number rather than as a mystery. - Add a **regression test** that inserts the key patterns that once collided, equal fields and many devices for one user, and asserts a small largest bucket. - Review every new key type's hasher with the same checklist: all compared fields mixed, no bare XOR, `noexcept`, seeded where clients choose the input. ## What does not help - Lowering `max_load_factor` or calling `reserve`: more buckets do not separate keys whose hashes are identical. - Rebuilding the table: identical hashes land together again. - Switching hash map libraries without fixing the hash: open-addressing tables usually degrade *faster* under clustered hashes, because collisions also occupy neighbouring slots.

  • Why does a per-process random seed in the hasher not break the rule that equal keys hash equal?
    The rule is about one execution: the standard requires a hash value to depend only on the argument for the duration of the program. A seed fixed at startup is the same for every call in that run, so equal keys still hash equal. It only changes values between runs, which is the point: an attacker cannot precompute collisions for a seed they do not know.
  • How do you find which keys share an overloaded bucket?
    Take the index from `bucket(slow_key)` or from a scan for the largest `bucket_size(n)`, then iterate that bucket with the local iterators `begin(n)` and `end(n)` and log the keys. Patterns jump out quickly: equal fields, one user id, ids that differ only in high bits. Then test the new hash on those exact keys.

  • A normal load_factor proves there are no collision problems
  • Calling reserve or rehash fixes slow lookups caused by collisions
  • std::hash<int> scrambles its input, so plain ids are well distributed
  • Hash collisions can corrupt the map's contents
  • libstdc++ and libc++ randomize their string hashes per process