Unable to erase previously inserted key

[geoffxy]

I've encountered some strange behavior where I cannot erase a key that was previously inserted into ALEX.

I've put together a self-contained program that reproduces the problem along with a trace. The program can be compiled by placing it under src in this repository (and adding an add_executable() to the CMakeLists.txt file). To reproduce, just run the compiled program with the provided trace.

The program and trace will bulk load ALEX with 9000 64-bit keys and then run a series of inserts and deletes. The delete of the last key in the trace (347892347588) appears to fail because erase() returns 0. However, the key should exist in ALEX because it was inserted earlier (line 16694 in the trace) and was not deleted afterwards.

I was able to reproduce the problem in both Debug and Release mode. I tried compiling on machines with g++ v9.3.0 and v11.1.0 and was able to reproduce this problem with both compiler versions.

Trace: alex_remove_not_found.log

Program:

#include <cstdint>
#include <fstream>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

#include "core/alex.h"

namespace {

int LoadAndReplay(const std::string& path) {
  alex::Alex<uint64_t, uint64_t> index;
  std::vector<std::pair<uint64_t, uint64_t>> entries;

  std::ifstream trace(path);
  uint64_t lineno = 0;
  std::string type;
  uint64_t key;

  bool load_phase = true;

  while (trace >> type >> key) {
    lineno++;

    if (type == "L") {
      entries.emplace_back(key, lineno);
      continue;
    }

    // Done reading keys that should be bulk loaded.
    if (load_phase) {
      index.bulk_load(entries.data(), entries.size());

      // Validate the bulk load.
      size_t i = 0;
      for (const auto& rec : index) {
        if (rec.first != entries[i].first) {
          std::cerr << "After the bulk load, ALEX is missing the key ("
                    << entries[i].first << ")." << std::endl;
          return 3;
        }
        ++i;
      }

      load_phase = false;
    }

    if (type == "I") {
      const auto res = index.insert(key, lineno);
      if (!res.second) {
        std::cerr << "Failed to insert key (" << key << "). Line " << lineno
                  << std::endl;
        return 2;
      }
    }
    if (type == "R") {
      const auto num_erased = index.erase(key);
      if (num_erased == 0) {
        std::cerr << "Failed to erase key that should exist (" << key
                  << "). Line " << lineno << std::endl;
        return 1;
      }
    }
  }
  std::cerr << "Trace replayed successfully." << std::endl;
  return 0;
}

}  // namespace

int main(int argc, char* argv[]) {
  if (argc != 2) {
    std::cerr << "Usage: " << argv[0] << " path/to/trace.log" << std::endl;
    return 1;
  }
  return LoadAndReplay(argv[1]);
}

Expected output:

Trace replayed successfully.

Actual output:

Failed to erase key that should exist (347892347588). Line 36813

[jialinding]

Should be fixed now. Let me know if you still see issues.

[geoffxy]

Thanks @jialinding!