Skip to content

[Core] Add try_relink: single-lock repair primitive for LookupTable #93

Description

@thep2p

Summary

Add the try_relink primitive backing the backpointer-repair mechanism (docs/protocol/concurrent-insert.md, Section 6). Like try_link (#85), but with an "already consistent" no-op outcome and reporting the evicted neighbor on replacement (Section 4.3).

Files

  • src/core/lookup/mod.rsLookupTable trait gains try_relink; add the RelinkOutcome enum:
    • AlreadyConsistent — current entry already equals the claimant; no table write.
    • Forward(Identity)
    • Relinked { evicted: Option<Identity> }
  • src/core/lookup/array_lookup_table.rs — implement try_relink(level, direction, claimant: Identity) -> anyhow::Result<RelinkOutcome>, single write-lock critical section.
  • src/core/lookup/array_lookup_table_test.rs — tests per the criteria below.

Acceptance Criteria

  • try_relink never calls get_entry/update_entry as two separate lock acquisitions.
  • already-consistent → AlreadyConsistent, table unchanged.
  • forward → Forward, table unchanged.
  • relink from empty → Relinked { evicted: None }.
  • relink over an existing entry → Relinked { evicted: Some(_) }.
  • out-of-range level → error, matching get_entry/update_entry/remove_entry and try_link ([Core] Add try_link: atomic accept-or-forward slot decision #85).

Dependencies

None.

Dependency graph (unblocked first):
EPIC #81 -- local search & join protocol
  #67 [DONE] search_by_id            #71 [OPEN] search_by_mem_vec (independent)
  #74 [OPEN] search_by_id timeout fix   #76 [OPEN] delete/leave
  Concurrent join + repair (Algorithm 2 + Algorithm 8; supersedes closed #66, #77):
    L0 (no deps):         #84  #85  #93 <-- YOU ARE HERE  #86  #87
    L1:                   #94  #88  #89
    L2:                   #90  #91  #95  #96
    L3:                   #92
    L4 (acceptance gate): #97

Metadata

Metadata

Labels

No labels
No labels

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions