The Map Dropped a Key When Two Expiry Times Matched

A C++ map can drop a live cache entry. One <= in a comparator is enough. I forced a timestamp tie and watched a key vanish. Would you have caught that in review?

This is a debugging retrospective. It is not a product tour. The artifact is a comparator audit you can run locally.

The symptom

I reconstructed a small TTL cache. Insert looked fine. Lookup looked fine. Unit tests stayed green.

Then two entries shared the same expiry second. One key disappeared. No throw. No log line. Just a hole.

Does that sound like a data race? It was not a race.

False leads I chased first

I blamed std::string moves. I blamed allocator reuse. I blamed hashing, even though this was a map.

I printed sizes after each insert. The size sometimes stayed flat. That was the real clue. A new key had been treated as equivalent to an old one.

Have you ever trusted a green test because keys looked unique? I had.

Reconstructed example

This example is labeled and compact. Do not ship it.

#include <cstdint>
#include <iostream>
#include <map>
#include <string>

struct CacheKey {
    std::int64_t expiry_s;
    std::string id;
};

struct ByExpiry {
    bool operator()(const CacheKey& a, const CacheKey& b) const {
        // Agent assumption: expiry values never collide.
        return a.expiry_s <= b.expiry_s;
    }
};

using Cache = std::map<CacheKey, std::string, ByExpiry>;

int main() {
    Cache cache;
    CacheKey a{1'700'000'000, "user:1"};
    CacheKey b{1'700'000'000, "user:2"}; // same second
    cache.emplace(a, "alpha");
    cache.emplace(b, "beta");
    std::cout << "size=" << cache.size() << "\n";
    std::cout << "has user:1 " << (cache.count(a) ? "yes" : "no") << "\n";
    std::cout << "has user:2 " << (cache.count(b) ? "yes" : "no") << "\n";
}

Compile it. Run it. Ask what size should be. Then look at what you got.

Three assumptions that stacked

The helper treated wall time as a unique sort key. It used <= because English likes inclusive bounds. It used second resolution because time() is familiar.

Which assumption fails first? All three can fail together.

std::map requires a strict weak ordering. comp(x, x) must be false. comp(x, y) and comp(y, x) must not both be true.

Equal expiry with only that comparator makes distinct ids equivalent. The second insert can be dropped. Or the tree can go sick without a loud crash.

Is std::multimap the fix? No. You still need a valid order. You still need a real identity.

Probe both directions

Do not stare at the tree. Probe the predicate. Add this beside the inserts.

ByExpiry cmp{};
std::cout << std::boolalpha
          << "aa=" << cmp(a, a)
          << " ab=" << cmp(a, b)
          << " ba=" << cmp(b, a) << "\n";

If you see aa=true, stop. Irreflexivity is already dead. If ab and ba are both true, stop again. The container is now fiction.

Would a code review catch <=? Maybe. A two-line probe is cheaper.

Reproduction steps

Follow this sequence. Do not skip the forced tie.

1. Save the example as tie_cache.cpp.
2. Compile with checks: g++ -std=c++17 -O1 -g -D_GLIBCXX_DEBUG -fsanitize=undefined,address tie_cache.cpp -o tie_cache
3. Run ./tie_cache and record size.
4. Change the comparator to < on expiry_s only. Rebuild. Run again.
5. Insert a third key with a later expiry. Confirm later keys still insert.
6. Print comp(a,b) and comp(b,a) for the tied pair.
7. Add a unique id to the order. Rebuild. Confirm size == 2.

Step 6 is the whole lesson. Two true results mean the order is broken. Do not argue with the container after that.

Decision table

I use this table before I trust a cache key.

Read the middle column twice. That column is the bug.

Notice the second row. Switching to < feels like a fix. It is not. Different users with one timestamp still collapse. The map thinks they are the same key.

Root cause, in plain words

The container did not lose memory. It obeyed a lie. The lie said two different keys were one key.

Wall-clock seconds collide under load. Local debug prints can hide that. A tight loop on another machine can reveal it. The clock was coarse. The comparator was coarser.

Why did tests pass? My first tests slept between inserts. Sleep is not uniqueness. Sleep is luck.

std::time(nullptr) jumps once per second. A burst of inserts shares one bucket. Your laptop may feel slow. A quiet compile box may not. The bug is not the server. The bug is the bucket.

Should expiry live in the key? Usually no. Identity belongs in the key. Expiry belongs in the value. Then std::map cannot collapse two users.

The fix I actually want

Use a total order on identity. Use expiry only as data. Or compare expiry, then a stable id.

struct ByExpiryThenId {
    bool operator()(const CacheKey& a, const CacheKey& b) const {
        if (a.expiry_s != b.expiry_s) {
            return a.expiry_s < b.expiry_s;
        }
        return a.id < b.id;
    }
};

Prefer std::chrono::steady_clock for TTL math. Prefer monotonic ticks over time(). Never use <= or >= in a container comparator. Never.

A cleaner shape drops the clever key entirely.

struct Entry {
    std::string value;
    std::chrono::steady_clock::time_point expires_at;
};

using Cache = std::map<std::string, Entry>;

Lookup by id. Expire with a scan or a side heap. Boring. Correct. Boring is the point.

Would an agent prefer one clever comparator? Yes. Clever is how the key vanished.

Eviction should scan values, not abuse key order. Want oldest first? Put a heap beside the map. Do not overload the map's < with policy.

Reusable debugging checklist

I now run this list on every custom comparator.

1. Write comp(x,x) and demand false.
2. Write both directions for one tied pair.
3. Force collisions in the test. Do not wait for production.
4. Enable _GLIBCXX_DEBUG on libstdc++ builds.
5. Add -fsanitize=undefined even if the tree looks fine.
6. Kill sleeps that accidentally uniquify timestamps.
7. Separate identity from priority. Two concepts. Two structures.

Would a linter have saved me? Maybe. A forced-tie test is cheaper. It also survives a tool change.

I also keep one more habit. I name the comparator after the full order. ByExpiry was a lie. ByExpiryThenId cannot hide the second key.

What I still do not trust

Sanitizers do not always trap comparator UB. Debug mode is implementation specific. libc++ and libstdc++ can disagree on the crash. Passing on one host is not a proof.

This method will not certify a lock-free cache. It will not certify a distributed TTL. It only answers one question. Are two keys ever treated as one?

Clock choice still matters after the fix. system_clock can jump. steady_clock cannot. If your TTL math uses wall time, a jump can expire live rows. That is a different bug. Do not mix it into the comparator story.

Where a model and a remote compile fit

I used a free-model pass to draft the first helper. It looked tidy. It compiled. It still encoded those three assumptions.

Disclosure: This article was prepared as part of MonkeyCode's product outreach.

I then ran the same binary shape on a free server compile box. Local runs had extra logging. Logging spaced the timestamps. The remote run did not. Ties appeared. That was useful noise, not magic.

After that I stopped relying on the machine. I wrote the forced-tie test above. The test is the artifact. MonkeyCode's free model access and free server option only helped me draft and recompile. You can skip both and still run the steps.

The lesson is not "remote boxes catch bugs." The lesson is "never let luck uniquify your keys." Force the collision on purpose.

Who should not use this workflow

Do not use a shared free server as production evidence. Do not treat model output as a container specification. Do not skip the tie test because a cloud box went green.

If you cannot read std::map ordering rules, stop. Learn those rules first. The tool will not do that reading for you.

If your cache is concurrent, this article is incomplete. A valid comparator does not give you thread safety. Put a mutex around the map, or pick a different structure. Do not bolt atomics onto a sick order.

Closing

The cache did not fail at scale. It failed at equality. Force the tie. Print both directions. Fix the order.

If you want the same draft-and-recompile loop I used, MonkeyCode's free model and free server path is optional. The comparator table is not.