You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Skip Graph joins no longer take pessimistic locks. Under Aspnes & Shah, "Skip Graphs" (arXiv:cs/0306043), Algorithm 2 joins a node by splicing it into each level's doubly-linked list through order-verification message forwarding — no distributed locking, no lock ordering, no random backoff. With the lock-free join in place, the request/response machinery that coordinated the old pessimistic lock is dead weight.
This issue removes the lock-coordination RPCs (AcquireLock, ReleaseLock, IsAvailable) and the "locked -> back off and retry" transport path in the middle layer. Removing the retry loop also eliminates the code path that dereferences a possibly-null response, which is the subject of #30.
This is the first of two cleanup steps and strips every remote consumer of the node-level lock methods. After this change, SkipNode's tryAcquire / unlock / isLocked / isLockedBy overrides lose their remote callers but remain in place (they still delegate to InsertionLock); the InsertionLock class itself stays wired into SkipNode — its field, the constructor's startInsertion(), insert()'s endInsertion(), and isAvailable() — and is removed in the follow-up. Consumers must go before the class: deleting InsertionLock while these callers still reference it would not compile.
Scope
src/main/java/underlay/packets/RequestType.java — remove the AcquireLock, ReleaseLock, and IsAvailable enum constants. Leave the unrelated AcquireNeighbors constant untouched.
receive(): remove the AcquireLock, ReleaseLock, and IsAvailable cases and the now-unused AcquireLockRequest / ReleaseLockRequest / IsAvailableRequest imports.
Remove the client senders tryAcquire(...) and both unlock(...) overloads (their only callers live in the lock-based join path removed by the join rewrite), and both isAvailable(...) overloads (already dead — they have no caller anywhere in the current code).
send(): replace the do { ... } while (request.backoff && response.locked) backoff-retry loop (with its random Thread.sleep) with a single delivery of the request.
Remove the per-case routing gates: the !overlay.isAvailable() gate on the SearchByMembershipVector / SearchByMembershipVectorRecursive / SearchByIdentifier cases, and the overlay.isLocked() && !overlay.isLockedBy(...) gate on the UpdateLeftNode / UpdateRightNode / GetRightNode / GetLeftNode / FindLadder cases (each case now runs unconditionally and no longer returns a locked response).
Collapse each neighbor getter to a single method. getRightNeighborOf currently has three overloads — a dead getRightNeighborOf(String, int, int) with no caller, a getRightNeighborOf(String, int, Identifier, int) delegator that passes backoff = true, and the getRightNeighborOf(boolean, String, int, Identifier, int) implementation. Delete the dead 3-argument overload and merge the delegator and the implementation into a single getRightNeighborOf(String, int, Identifier, int) that sends the request once and returns the identity, dropping the boolean backoff parameter, the req.backoff = backoff plumbing, and the if (r.locked) return INVALID_NODE branch. Apply the same collapse to getLeftNeighborOf: merge its true-passing getLeftNeighborOf(String, int, Identifier, int) delegator and its getLeftNeighborOf(boolean, ...) implementation into one getLeftNeighborOf(String, int, Identifier, int) (there is no dead 3-argument left overload to remove). Dropping the boolean parameter without merging would leave two methods with identical signatures, so the merge must happen in the same change.
src/main/java/skipnode/SkipNode.java — in findLadder(...), update the getLeftNeighborOf / getRightNeighborOf call sites to the merged 4-argument form (drop the leading false argument) and remove the now-dead INVALID_NODE (locked) short-circuit that followed them.
Note: the Request.backoff and Response.locked fields are intentionally left in place in this issue — once nothing reads them they compile cleanly as unused fields — and are deleted in the follow-up, to keep this change reviewable and within its size budget.
Acceptance Criteria
AcquireLock, ReleaseLock, and IsAvailable no longer appear in RequestType, and the three request classes are deleted.
MiddleLayer.receive() has no AcquireLock / ReleaseLock / IsAvailable cases and no isAvailable / isLocked / isLockedBy routing gates; every remaining case performs its operation unconditionally.
MiddleLayer.send() delivers each request exactly once (no retry loop, no random sleep) and no longer dereferences a possibly-null response to decide on a locked-retry.
getLeftNeighborOf and getRightNeighborOf are each a single method that no longer branches on a locked response; the dead getRightNeighborOf(String, int, int) overload is gone; no code reads request.backoff or response.locked (the fields themselves are removed in the follow-up).
A repo-wide search finds no remaining references to AcquireLockRequest, ReleaseLockRequest, or IsAvailableRequest.
The project compiles and the existing test suite passes with no new failures (SkipNodeTest, MvpTest, ConcurrentLookupTableTest).
A new deterministic test (no sleeps) asserts that a request routed through the middle layer is delivered and answered in a single round-trip, with no locked/retry response involved.
Dependencies
Requires the lock-free join rewrite to have landed first, so the insertion path no longer acquires or releases neighbor locks; otherwise the removed tryAcquire / unlock senders are still called.
Must land before the follow-up cleanup that deletes the InsertionLock class and the node-level lock methods (those overrides become caller-less here but are only removed there).
Summary
Skip Graph joins no longer take pessimistic locks. Under Aspnes & Shah, "Skip Graphs" (arXiv:cs/0306043), Algorithm 2 joins a node by splicing it into each level's doubly-linked list through order-verification message forwarding — no distributed locking, no lock ordering, no random backoff. With the lock-free join in place, the request/response machinery that coordinated the old pessimistic lock is dead weight.
This issue removes the lock-coordination RPCs (
AcquireLock,ReleaseLock,IsAvailable) and the "locked -> back off and retry" transport path in the middle layer. Removing the retry loop also eliminates the code path that dereferences a possibly-null response, which is the subject of #30.This is the first of two cleanup steps and strips every remote consumer of the node-level lock methods. After this change,
SkipNode'stryAcquire/unlock/isLocked/isLockedByoverrides lose their remote callers but remain in place (they still delegate toInsertionLock); theInsertionLockclass itself stays wired intoSkipNode— its field, the constructor'sstartInsertion(),insert()'sendInsertion(), andisAvailable()— and is removed in the follow-up. Consumers must go before the class: deletingInsertionLockwhile these callers still reference it would not compile.Scope
src/main/java/underlay/packets/RequestType.java— remove theAcquireLock,ReleaseLock, andIsAvailableenum constants. Leave the unrelatedAcquireNeighborsconstant untouched.src/main/java/underlay/packets/requests/AcquireLockRequest.java,ReleaseLockRequest.java,IsAvailableRequest.java— delete.src/main/java/middlelayer/MiddleLayer.java:receive(): remove theAcquireLock,ReleaseLock, andIsAvailablecases and the now-unusedAcquireLockRequest/ReleaseLockRequest/IsAvailableRequestimports.tryAcquire(...)and bothunlock(...)overloads (their only callers live in the lock-based join path removed by the join rewrite), and bothisAvailable(...)overloads (already dead — they have no caller anywhere in the current code).send(): replace thedo { ... } while (request.backoff && response.locked)backoff-retry loop (with its randomThread.sleep) with a single delivery of the request.!overlay.isAvailable()gate on theSearchByMembershipVector/SearchByMembershipVectorRecursive/SearchByIdentifiercases, and theoverlay.isLocked() && !overlay.isLockedBy(...)gate on theUpdateLeftNode/UpdateRightNode/GetRightNode/GetLeftNode/FindLaddercases (each case now runs unconditionally and no longer returns alockedresponse).getRightNeighborOfcurrently has three overloads — a deadgetRightNeighborOf(String, int, int)with no caller, agetRightNeighborOf(String, int, Identifier, int)delegator that passesbackoff = true, and thegetRightNeighborOf(boolean, String, int, Identifier, int)implementation. Delete the dead 3-argument overload and merge the delegator and the implementation into a singlegetRightNeighborOf(String, int, Identifier, int)that sends the request once and returns the identity, dropping theboolean backoffparameter, thereq.backoff = backoffplumbing, and theif (r.locked) return INVALID_NODEbranch. Apply the same collapse togetLeftNeighborOf: merge itstrue-passinggetLeftNeighborOf(String, int, Identifier, int)delegator and itsgetLeftNeighborOf(boolean, ...)implementation into onegetLeftNeighborOf(String, int, Identifier, int)(there is no dead 3-argument left overload to remove). Dropping thebooleanparameter without merging would leave two methods with identical signatures, so the merge must happen in the same change.src/main/java/skipnode/SkipNode.java— infindLadder(...), update thegetLeftNeighborOf/getRightNeighborOfcall sites to the merged 4-argument form (drop the leadingfalseargument) and remove the now-deadINVALID_NODE(locked) short-circuit that followed them.Note: the
Request.backoffandResponse.lockedfields are intentionally left in place in this issue — once nothing reads them they compile cleanly as unused fields — and are deleted in the follow-up, to keep this change reviewable and within its size budget.Acceptance Criteria
AcquireLock,ReleaseLock, andIsAvailableno longer appear inRequestType, and the three request classes are deleted.MiddleLayer.receive()has noAcquireLock/ReleaseLock/IsAvailablecases and noisAvailable/isLocked/isLockedByrouting gates; every remaining case performs its operation unconditionally.MiddleLayer.send()delivers each request exactly once (no retry loop, no random sleep) and no longer dereferences a possibly-null response to decide on a locked-retry.getLeftNeighborOfandgetRightNeighborOfare each a single method that no longer branches on a locked response; the deadgetRightNeighborOf(String, int, int)overload is gone; no code readsrequest.backofforresponse.locked(the fields themselves are removed in the follow-up).AcquireLockRequest,ReleaseLockRequest, orIsAvailableRequest.SkipNodeTest,MvpTest,ConcurrentLookupTableTest).Dependencies
tryAcquire/unlocksenders are still called.InsertionLockclass and the node-level lock methods (those overrides become caller-less here but are only removed there).Part of #33. Depends on: #39