Skip to content

[BUG] Duplicate external labels in HNSW cause load validation to fail #1282

Description

@BCathcart

Describe the bug
The validation code asserts that there are only unique external labels in the data_level0_memory_ slots. This is not always the case. I don't see any inherent problems with this state. The one place it can go wrong today is across a save/load. The load code rebuilds the label_lookup_ from the labels in data_level0_memory_. There can be one live slot and any number of tombstoned slots all carrying the same label. The label_lookup_ reconstruction code needs to check that it points to the live slot for that label. Otherwise the HNSW state won't properly reflect the keyspace. Future updates or deletes to the record will error as it will see the label already belonging to a tombstoned node.

To Reproduce
The HNSW modify record code first calls markDelete() on the record to tombstone the existing slot with the label and then calls addPoint() to add the new vector with the exact same label. Theoretically, std::unordered_set<tableint> deleted_elements makes no promises about which slot deleted_elements.begin() points to. In practice though, it's always the last added slot. In the normal case, the same slot will be updated and there will be no duplicate labels. The problem occurs when another document is deleted between markDelete() and addPoint(). It will put another tombstoned slot at the front of deleted_elements and the addPoint() for the modified record will use it, adding the label to a new slot and still keeping the same label in the old slot it just tombstoned.

Expected behavior
Let's not have the load-side validation enforce unique slots. It just needs to properly reconstruct the label_lookup_.

Environment
Search 1.0, 1.1, and 1.2 are all susceptible.

Additional context
Additional problems that make mitigation hard:

  • Inability to modify Dev configs outside debug-mode.
  • All load validation being is coupled under a single enabled/disabled config, regardless if it's protecting against OOB accesses with security implications or just surfaces a small correctness bug like this one.

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions