What causes "Expected occupied entry -- found it empty..." in microsoft/FASTER?

Retry — the algorithm continues; if failures correlate with user-visible issues, retry the user operation

Expected occupied entry -- found it empty...

Error message

Expected occupied entry -- found it empty...

What it means

The mirror-image failure of the relocation step: after moving the occupied entry into a free slot succeeded, FASTER tries to clear the original front entry via CAS but the entry was already changed by a concurrent thread (expected it occupied, found it empty/different). The relocation transaction is effectively aborted; internal logic continues scanning for another free entry.

Solutions

Retry — the algorithm continues; if failures correlate with user-visible issues, retry the user operation
Serialize heavy maintenance (Checkpoint/GrowIndex) away from peak write concurrency
Upgrade FASTER to a version with improved concurrent relocation handling
Ensure all index operations go through FASTER's epoch-protected APIs, not raw bucket manipulation

Example fix

null

Defensive patterns

Strategy: retry

Try / catch

Status s = ctx->Checkpoint(token, cb);
if (s != Status::Ok) {
  quiesce_writers();
  s = ctx->Checkpoint(token, cb);
  resume_writers();
}

Prevention

Run index maintenance (checkpoint/grow/GC) during low-write windows
Use epoch barriers around maintenance to reduce CAS races
Treat one-off occurrences as benign; investigate only if they recur with correctness symptoms
Keep FASTER version current for improved concurrent relocation logic

When it happens

Trigger: Concurrent deletion or relocation touching the same front bucket entry between the first successful CAS and the clearing CAS, during Checkpoint()/GC/GrowIndex under concurrent load.

Common situations: Same as the companion 'found it occupied' race: high thread counts doing RMW/delete on hot keys while index maintenance (checkpoint/grow) runs.

Understand the failure class

Background: "This is a bug, please report it": internal invariant violations, unreachable panics, and SNH errors explained — this error's family across 47 libraries.

Related errors

AI-assisted analysis of microsoft/FASTER@321d872eab (2026-09-15). Data as JSON: /api/errors/864c6de900287b5d. Report an issue: GitHub.

Appendix: source

Thrown at cc/src/index/mem_index.h:842

        if (front_bucket_entry.unused()) {
          if (next_free_entry == nullptr) {
            next_free_entry = front_atomic_entry;
            back_bucket = front_bucket;
            back_entry_idx = front_entry_idx;
          }
          continue;
        }
        // Entry is occupied!

        if (next_free_entry) {
          // Move occupied entry to closest (forward-wise) free entry
          HashBucketEntry empty_entry{ HashBucketEntry::kInvalidEntry };
          if (!next_free_entry->compare_exchange_strong(empty_entry, front_bucket_expected_entry)) {
            log_error("Expected empty entry -- found it occupied...");
          } else {
            if (!front_atomic_entry->compare_exchange_strong(front_bucket_expected_entry, empty_entry)) {
              log_error("Expected occupied entry -- found it empty...");
            }
          }
          next_free_entry = nullptr;

          // Try to find next available free entry
          AtomicHashBucketEntry* back_atomic_entry;
          do {
            for (; back_entry_idx < hash_bucket_t::kNumEntries; ++back_entry_idx) {
              back_atomic_entry = &(back_bucket->entries[back_entry_idx]);
              hash_bucket_entry_t back_bucket_entry{ back_atomic_entry->load() };
              if (back_bucket_entry.unused()) {
                // Found new available entry!
                next_free_entry = back_atomic_entry;
                break;
              }
              if (back_atomic_entry == front_atomic_entry) {
                break; // Reached front pointer!
              }

View on GitHub (pinned to 321d872eab)