Skip to content

[Testing] Add deterministic concurrent-join repair regression test #45

Description

@thep2p

Summary

Once the lock-free join and periodic backpointer repair land, we need a deterministic regression test that reproduces the concurrent-join partition and proves repair heals it. The partition is a transient break of the backpointer invariant (if y is x's right neighbor at a level, x must be y's left neighbor, and symmetrically): for four nodes A < B < C < D with A and D already linked at a level, B and C joining concurrently between them can fragment the level list into A<->B and C<->D — each side keeping only half of the splice, reachable with no node failures — which the paper's periodic repair (Aspnes & Shah, arXiv:cs/0306043) heals in a bounded number of rounds.

This issue adds a scheduler-driven test that inserts N nodes concurrently, drives repair rounds deterministically, then asserts the correctness and consistency (backpointer) invariants. It also de-flakes the existing concurrentInsertions test (currently marked flakey) and fixes MvpTest, which is pinned to 5 nodes because it fails when the node count grows.

Scope

  • src/test/java/skipnode/SkipNodeTest.java
    • Add a new deterministic test (e.g. concurrentJoinRepairRegression) that builds N nodes via LocalSkipGraph, inserts all of them concurrently, steps message delivery and repair rounds through the deterministic test scheduler until quiescent, then runs tableCorrectnessCheck and tableConsistencyCheck (lines 27-42 and 46-62) across every node.
    • De-flake concurrentInsertions (method spans lines 149-192): delete the // TODO: this test is flakey; fix it! marker at line 148 (immediately above the @Test) and make correctness depend on scheduler-driven delivery and repair rather than a timed await.
  • src/test/java/integration/MvpTest.java
    • Remove the hardcoded NODES = 5 cap and the // TODO: this test fails if number of nodes increased marker (lines 30-31); raise/parameterize NODES and drive insertion plus repair deterministically so full-connectivity searches pass at larger sizes.

Acceptance Criteria

  • A new deterministic test in SkipNodeTest inserts N nodes concurrently (N large enough to exercise concurrent splices, e.g. the existing NODES = 20), drives repair rounds via the test scheduler, and passes tableCorrectnessCheck and tableConsistencyCheck for every node with no wall-clock sleeps.
  • The test reproduces concurrent-join partitions and, after a bounded number of repair rounds, tableConsistencyCheck holds for all nodes.
  • The test is repeatable: it passes deterministically across repeated runs (seeded / scheduler-driven), with no reliance on timed await for correctness.
  • concurrentInsertions no longer carries the flakey TODO and passes deterministically.
  • MvpTest no longer hardcodes NODES = 5 or carries the scaling TODO; MVP_TEST passes full-connectivity searches at a larger node count (e.g. >= 20).
  • Total change is <= 200 lines including test code, and ships in this issue.

Dependencies

Requires these capabilities to land first:

  • An accept-or-forward table write primitive: verify the current slot, then set-or-forward atomically under the table's own lock, with a relink variant that additionally reports already-consistent (no-op) and evicted-neighbor.
  • The join/repair message types: an order-verification link request that a neighbor either accepts or forwards to the correct neighbor, and the relink request used by repair.
  • The lock-free insert/join rewrite (Algorithm 2) that splices a joining node into each level's doubly-linked list via order-verification forwarding.
  • Removal of the pessimistic multi-level neighbor locking and random-backoff retry, so concurrent joins no longer serialize.
  • A deterministic test scheduler that can step message delivery and trigger repair rounds on demand (no wall-clock timing).
  • The periodic backpointer repair / self-stabilization (Algorithm 8, Section 5.2.1) that re-links neighbors to restore the invariant.

Related: #12.


Part of #33. Depends on: #35, #41, #44

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions