Visitar URL original
fix(#10302): a lightweight edge delete read through a stale edge list… · ArcadeData/arcadedb@0762d99 · GitHub
Skip to content

Commit 0762d99

Browse files
robfrankrobfrank
authored
fix(#10302): a lightweight edge delete read through a stale edge list is a conflict, not a lost delete (#10316)
1 parent 4b99e9b commit 0762d99

7 files changed

Lines changed: 455 additions & 20 deletions

File tree

‎engine/src/main/java/com/arcadedb/database/TransactionContext.java‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -174,6 +174,10 @@ public class TransactionContext implements Transaction {
174174
// allocated: only that corner ever fills it.
175175
private Map<RID, byte[]> snapshotRecordContents;
176176
private RidHashSet deletedRecordsInTx = new RidHashSet(DELETED_SET_CAPACITY);
177+
// #10302: per (vertex, direction, edge type bucket, neighbour), how many lightweight edge entries this transaction removed
178+
// from that vertex's list. A lightweight edge has no RID and its twins are indistinguishable, so a removal that finds
179+
// nothing is told from a stale list by counting. Lazily allocated: only a lightweight edge delete fills it.
180+
private Map<LightEdgeEntry, int[]> removedLightEdgeEntries;
177181
private Map<PageId, MutablePage> modifiedPages;
178182
private Map<PageId, MutablePage> newPages;
179183
// GRAPH_EDGE_APPEND_MERGE (super-node write contention): appends to an edge-list chunk commute, so a
@@ -3142,6 +3146,7 @@ public void reset() {
31423146
deletedRecordsInTx = new RidHashSet(DELETED_SET_CAPACITY);
31433147
else
31443148
deletedRecordsInTx.clear();
3149+
removedLightEdgeEntries = null;
31453150
newRecords.clear();
31463151
// Reached only with callbacks left when the transaction ends without running them (a failed commit, a rollback past the
31473152
// commit point): a commit that runs them takes them out first, see resetAndFireCallbacks()
@@ -3581,4 +3586,26 @@ public void addDeletedRecord(final RID rid) {
35813586
public boolean isDeletedInTransaction(final RID rid) {
35823587
return deletedRecordsInTx.contains(rid);
35833588
}
3589+
3590+
/**
3591+
* One lightweight edge entry of the edge list of {@code vertex} in direction OUT ({@code out}) or IN: the entries of
3592+
* one lightweight edge and of all its twins share it (#10302).
3593+
*/
3594+
public record LightEdgeEntry(RID vertex, boolean out, int edgeTypeBucketId, RID neighbour) {
3595+
}
3596+
3597+
/** Counts {@code removed} lightweight edge entries removed by this transaction from the edge list {@code entry} names (#10302). */
3598+
public void lightEdgeEntriesRemoved(final LightEdgeEntry entry, final int removed) {
3599+
if (removedLightEdgeEntries == null)
3600+
removedLightEdgeEntries = new HashMap<>();
3601+
removedLightEdgeEntries.computeIfAbsent(entry, k -> new int[1])[0] += removed;
3602+
}
3603+
3604+
/** How many lightweight edge entries this transaction removed from the edge list {@code entry} names (#10302). */
3605+
public int getLightEdgeEntriesRemoved(final LightEdgeEntry entry) {
3606+
if (removedLightEdgeEntries == null)
3607+
return 0;
3608+
final int[] removed = removedLightEdgeEntries.get(entry);
3609+
return removed == null ? 0 : removed[0];
3610+
}
35843611
}

‎engine/src/main/java/com/arcadedb/graph/EdgeLinkedList.java‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -548,9 +548,9 @@ public void addAll(final List<Pair<Identifiable, Identifiable>> entries) {
548548
/**
549549
* Removes the entry of {@code edge} from this list.
550550
*
551-
* @return true when an entry was removed, false when the list, as this transaction reads it, holds none
551+
* @return the number of entries removed: 1, or 0 when the list, as this transaction reads it, holds none
552552
*/
553-
public boolean removeEdge(final Edge edge) {
553+
public int removeEdge(final Edge edge) {
554554
final RID rid = edge.getIdentity();
555555
final boolean byEdgeRID = rid.getPosition() > -1;
556556
// A lightweight edge has no record to point at, so it is located by (edge type bucket, far endpoint) instead -
@@ -579,15 +579,15 @@ public boolean removeEdge(final Edge edge) {
579579
modifiable.removeLightEdge(edgeTypeBucketId, targetVertexRID);
580580
if (deleted > 0) {
581581
updateSegment(modifiable, prevBrowsedRID);
582-
return true;
582+
return 1;
583583
}
584584
}
585585

586586
prevBrowsedRID = current.getIdentity();
587587
final RID prevRID = previousRIDOf(current, guard);
588588
current = prevRID == null ? null : readChunk(prevRID);
589589
}
590-
return false;
590+
return 0;
591591
}
592592

593593
public void removeEdgeRID(final RID edge) {

‎engine/src/main/java/com/arcadedb/graph/EdgeSegment.java‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -69,6 +69,13 @@ int addManyAtEndDirect(int[] edgeBucketIds, long[] edgePositions,
6969
*/
7070
boolean containsLightEdge(int edgeTypeBucketId, RID vertexRID);
7171

72+
/**
73+
* How many lightweight edges of the given type reaching the given vertex this segment holds: the twins of one
74+
* lightweight edge are indistinguishable, so they can only be counted (#10302). See {@link #containsLightEdge} for the
75+
* match.
76+
*/
77+
int countLightEdges(int edgeTypeBucketId, RID vertexRID);
78+
7279
/**
7380
* Removes one lightweight edge of the given type reaching the given vertex. See {@link #containsLightEdge} for why
7481
* the match needs all three terms. Removes a single entry: duplicates of one lightweight edge are the same edge, so

‎engine/src/main/java/com/arcadedb/graph/GraphEngine.java‎

Lines changed: 124 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1128,9 +1128,17 @@ public void deleteEdge(final Edge edge, final RID skipEndpoint, final Vertex.DIR
11281128
*/
11291129
private void disconnectEndpoint(final Edge edge, final Vertex.DIRECTION direction, final RID skipEndpoint,
11301130
final Vertex.DIRECTION skipDirection) {
1131+
final boolean lightweight = edge instanceof LightEdge || edge.getIdentity().getPosition() < 0;
11311132
if (skipEndpoint != null && (skipDirection == null || skipDirection == direction) && skipEndpoint.equals(
1132-
direction == Vertex.DIRECTION.OUT ? edge.getOut() : edge.getIn()))
1133+
direction == Vertex.DIRECTION.OUT ? edge.getOut() : edge.getIn())) {
1134+
if (lightweight && skipDirection != null)
1135+
// THE ITERATOR REMOVES THE ENTRY ITSELF (#9779): IT IS A REMOVAL BY THIS TRANSACTION ALL THE SAME (#10302). It walks
1136+
// the transaction's own view, so the entry is there to remove; the one way it finds none is a delete listener or
1137+
// trigger that took it out first, through this transaction. Counting it then over-counts by one, which can only
1138+
// hide a stale view (the delete lost, as before #10302), never invent a conflict
1139+
lightEdgeEntriesRemoved(skipEndpoint, direction, edge, 1);
11331140
return;
1141+
}
11341142

11351143
final VertexInternal endpoint = resolveEndpointToDisconnect(edge, direction);
11361144
if (endpoint == null)
@@ -1155,17 +1163,25 @@ private void disconnectEndpoint(final Edge edge, final Vertex.DIRECTION directio
11551163
edge.getIdentity(), direction, endpoint.getIdentity());
11561164
return;
11571165
}
1158-
if (list != null && list.removeEdge(edge))
1166+
final int removed = list == null ? 0 : list.removeEdge(edge);
1167+
if (removed > 0) {
1168+
if (lightweight)
1169+
// ONE PER CHAIN THAT HELD A TWIN: A STRIPED LIST CAN REMOVE ONE IN EACH GENERATION (#10314)
1170+
lightEdgeEntriesRemoved(endpoint.getIdentity(), direction, edge, removed);
11591171
return;
1172+
}
11601173

11611174
if (direction == Vertex.DIRECTION.IN && edge.getType() instanceof EdgeType edgeType && !edgeType.isBidirectional())
11621175
// A UNIDIRECTIONAL EDGE IS NEVER IN THE IN LIST: NOTHING WAS MISSED
11631176
return;
11641177

1165-
if (edge instanceof LightEdge || edge.getIdentity().getPosition() < 0)
1178+
if (lightweight) {
11661179
// A LIGHTWEIGHT EDGE HAS NO RECORD TO OUTLIVE ITS ENTRY OR TO REUSE ITS RID, AND ITS TWINS (SAME TYPE, SAME NEIGHBOUR)
1167-
// ARE INDISTINGUISHABLE: AN ENTRY IN THE COMMITTED LIST CAN BE ONE THIS TRANSACTION HAS ALREADY REMOVED
1180+
// ARE INDISTINGUISHABLE: AN ENTRY IN THE COMMITTED LIST CAN BE ONE THIS TRANSACTION HAS ALREADY REMOVED, SO IT IS
1181+
// COUNTED INSTEAD (#10302)
1182+
checkLightEdgeListNotStale(endpoint, direction, edge);
11681183
return;
1184+
}
11691185

11701186
if (database.getTransactionIfExists() instanceof TransactionContext tx && tx.isDeletedInTransaction(edge.getIdentity()))
11711187
// THIS TRANSACTION HAS ALREADY DELETED THE EDGE, AND REMOVED THE ENTRY WITH IT: THE COMMITTED LIST STILL HOLDS IT
@@ -1184,6 +1200,98 @@ private void disconnectEndpoint(final Edge edge, final Vertex.DIRECTION directio
11841200
keepEdgeRecordPageOutOfSlotMerge(edge);
11851201
}
11861202

1203+
/**
1204+
* Refuses, with a retryable {@link ConcurrentModificationException}, the delete of a lightweight edge that the list
1205+
* this transaction reads does not hold while the committed list holds more of its entries than this transaction removed
1206+
* (#10302, the lightweight half of #10263). The transaction read the list before a concurrent commit appended the
1207+
* entry, so nothing was removed and no page was anchored: the commit would go through and the delete would be lost,
1208+
* one lightweight edge too many. A retry reads the list again.
1209+
* <p>
1210+
* The entries of a lightweight edge and of its twins (same type, same neighbour) are indistinguishable, so the two
1211+
* sides are counted rather than matched: an entry in the committed list that this transaction has itself removed is
1212+
* not a sign of a stale view, and deleting more twins than there are stays the no-op it always was.
1213+
* <p>
1214+
* Limit: twins this transaction CREATED and then removed count as removed, though they were never in the committed
1215+
* list. A transaction that creates twins and deletes more of them than it created can therefore miss a twin committed
1216+
* concurrently, and the delete is lost as before. Counting the creations too would cost a map entry per lightweight
1217+
* edge created, on the bulk-load path, for this corner (#10315). The removals are counted for the whole transaction,
1218+
* up to its commit or rollback: a removal undone by a part of the transaction failing and being retried within it stays
1219+
* counted. Both over-count, which can only hide a stale view, never invent a conflict.
1220+
* <p>
1221+
* Cost: only a removal that found nothing gets here, and it reads the committed vertex and walks the committed chain
1222+
* (one stripe chain per generation on a super-node), stopping as soon as it counts more than were removed. A delete
1223+
* of a lightweight edge that is not there at all walks the whole chain, as the regular-edge check does.
1224+
*/
1225+
private void checkLightEdgeListNotStale(final VertexInternal endpoint, final Vertex.DIRECTION direction, final Edge edge) {
1226+
if (!(database.getTransactionIfExists() instanceof TransactionContext tx))
1227+
return;
1228+
final RID neighbour = direction == Vertex.DIRECTION.OUT ? edge.getIn() : edge.getOut();
1229+
if (neighbour == null)
1230+
return;
1231+
final int removed = tx.getLightEdgeEntriesRemoved(lightEdgeEntry(endpoint.getIdentity(), direction, edge));
1232+
final int committed = committedLightEdgeCount(endpoint, direction, edge.getIdentity().getBucketId(), neighbour, removed + 1);
1233+
if (committed > removed)
1234+
throw new ConcurrentModificationException(
1235+
"Lightweight edge " + edge.getOut() + "->" + edge.getIn() + " of type " + edge.getTypeName() + " is in the committed "
1236+
+ direction + " edge list of vertex " + endpoint.getIdentity() + " but not in the one this transaction read: "
1237+
+ "the list changed after it was read");
1238+
}
1239+
1240+
private void lightEdgeEntriesRemoved(final RID vertex, final Vertex.DIRECTION direction, final Edge edge, final int removed) {
1241+
if (database.getTransactionIfExists() instanceof TransactionContext tx)
1242+
tx.lightEdgeEntriesRemoved(lightEdgeEntry(vertex, direction, edge), removed);
1243+
}
1244+
1245+
private static TransactionContext.LightEdgeEntry lightEdgeEntry(final RID vertex, final Vertex.DIRECTION direction,
1246+
final Edge edge) {
1247+
final boolean out = direction == Vertex.DIRECTION.OUT;
1248+
return new TransactionContext.LightEdgeEntry(vertex, out, edge.getIdentity().getBucketId(), out ? edge.getIn() : edge.getOut());
1249+
}
1250+
1251+
/**
1252+
* How many lightweight edges of the type of {@code edgeTypeBucketId} reaching {@code neighbour} the COMMITTED edge list
1253+
* of {@code vertex} in {@code direction} holds, read as {@link #committedEdgeListHolds} reads it, counting no further
1254+
* than {@code limit}: the caller only needs to know whether there are more than it removed.
1255+
*/
1256+
private int committedLightEdgeCount(final VertexInternal vertex, final Vertex.DIRECTION direction, final int edgeTypeBucketId,
1257+
final RID neighbour, final int limit) {
1258+
final RID headRID = committedEdgeListHead(vertex, direction);
1259+
if (headRID == null)
1260+
return 0;
1261+
1262+
final Binary headContent = committedRecordContent(headRID);
1263+
if (headContent == null)
1264+
return 0;
1265+
1266+
if (headContent.getByte(0) == StripeDirectory.RECORD_TYPE) {
1267+
final StripeDirectory directory = new StripeDirectory(database, headRID, headContent);
1268+
int count = 0;
1269+
for (int g = 0; g < directory.getGenerationCount() && count < limit; g++)
1270+
count += committedChainLightEdgeCount(directory.getHead(g, StripeDirectory.stripeOf(neighbour, directory.getStripes(g))),
1271+
edgeTypeBucketId, neighbour, limit - count);
1272+
return count;
1273+
}
1274+
return committedChainLightEdgeCount(headRID, edgeTypeBucketId, neighbour, limit);
1275+
}
1276+
1277+
private int committedChainLightEdgeCount(final RID headRID, final int edgeTypeBucketId, final RID neighbour, final int limit) {
1278+
final ChainCycleGuard guard = new ChainCycleGuard(headRID);
1279+
int count = 0;
1280+
RID chunkRID = headRID;
1281+
while (chunkRID != null && count < limit) {
1282+
final Binary content = committedRecordContent(chunkRID);
1283+
if (content == null || content.getByte(0) != EdgeSegment.RECORD_TYPE)
1284+
return count;
1285+
1286+
final EdgeSegment chunk = new MutableEdgeSegment(database, chunkRID, content);
1287+
count += chunk.countLightEdges(edgeTypeBucketId, neighbour);
1288+
1289+
final RID previousRID = chunk.getPreviousRID();
1290+
chunkRID = previousRID == null || previousRID.equals(chunkRID) || guard.revisits(previousRID) ? null : previousRID;
1291+
}
1292+
return count;
1293+
}
1294+
11871295
/**
11881296
* A removal that found no entry, in the list this transaction reads or in the committed one, leaves two readings: an
11891297
* edge whose entries are genuinely missing (an orphan record, which the delete has to be able to clear), or an edge
@@ -1295,15 +1403,7 @@ private static ConcurrentModificationException concurrentEdgeDelete(final RID ed
12951403
* too, head pointers included (#10304), see {@link LocalBucket#getRecordFromCommittedPage}.
12961404
*/
12971405
private boolean committedEdgeListHolds(final VertexInternal vertex, final Vertex.DIRECTION direction, final Edge edge) {
1298-
final RID vertexRID = vertex.getIdentity();
1299-
final Binary vertexContent = committedRecordContent(vertexRID);
1300-
if (vertexContent == null || vertexContent.getByte(0) != Vertex.RECORD_TYPE)
1301-
return false;
1302-
1303-
final ImmutableVertex committedVertex = new ImmutableVertex(database, vertex.getType(), vertexRID, vertexContent);
1304-
final RID headRID = direction == Vertex.DIRECTION.OUT ?
1305-
committedVertex.getOutEdgesHeadChunk() :
1306-
committedVertex.getInEdgesHeadChunk();
1406+
final RID headRID = committedEdgeListHead(vertex, direction);
13071407
if (headRID == null)
13081408
return false;
13091409

@@ -1323,6 +1423,17 @@ private boolean committedEdgeListHolds(final VertexInternal vertex, final Vertex
13231423
return committedChainHolds(headRID, edge.getIdentity());
13241424
}
13251425

1426+
/** The head of the edge list of {@code vertex} in {@code direction} in the COMMITTED vertex record, or null. */
1427+
private RID committedEdgeListHead(final VertexInternal vertex, final Vertex.DIRECTION direction) {
1428+
final RID vertexRID = vertex.getIdentity();
1429+
final Binary vertexContent = committedRecordContent(vertexRID);
1430+
if (vertexContent == null || vertexContent.getByte(0) != Vertex.RECORD_TYPE)
1431+
return null;
1432+
1433+
final ImmutableVertex committedVertex = new ImmutableVertex(database, vertex.getType(), vertexRID, vertexContent);
1434+
return direction == Vertex.DIRECTION.OUT ? committedVertex.getOutEdgesHeadChunk() : committedVertex.getInEdgesHeadChunk();
1435+
}
1436+
13261437
private boolean committedChainHolds(final RID headRID, final RID edgeRID) {
13271438
final ChainCycleGuard guard = new ChainCycleGuard(headRID);
13281439
RID chunkRID = headRID;

‎engine/src/main/java/com/arcadedb/graph/MutableEdgeSegment.java‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -399,6 +399,30 @@ public boolean containsLightEdge(final int edgeTypeBucketId, final RID vertexRID
399399
return false;
400400
}
401401

402+
@Override
403+
public int countLightEdges(final int edgeTypeBucketId, final RID vertexRID) {
404+
final int used = getUsed();
405+
if (used <= CONTENT_START_POSITION)
406+
return 0;
407+
408+
final int vertexBucketId = vertexRID.getBucketId();
409+
final long vertexPosition = vertexRID.getPosition();
410+
411+
int count = 0;
412+
buffer.position(CONTENT_START_POSITION);
413+
while (buffer.position() < used) {
414+
final int currEdgeBucketId = (int) buffer.getNumber();
415+
final long currEdgePosition = buffer.getNumber();
416+
final int currVertexBucketId = (int) buffer.getNumber();
417+
final long currVertexPosition = buffer.getNumber();
418+
419+
if (currEdgeBucketId == edgeTypeBucketId && currEdgePosition < 0 && currVertexBucketId == vertexBucketId
420+
&& currVertexPosition == vertexPosition)
421+
++count;
422+
}
423+
return count;
424+
}
425+
402426
@Override
403427
public int removeLightEdge(final int edgeTypeBucketId, final RID vertexRID) {
404428
int used = getUsed();

‎engine/src/main/java/com/arcadedb/graph/StripedEdgeList.java‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -552,11 +552,11 @@ public JSONArray toJSON() {
552552
}
553553

554554
@Override
555-
public boolean removeEdge(final Edge edge) {
555+
public int removeEdge(final Edge edge) {
556556
// The edge lives in the stripe of its neighbour (per generation); the non-owning candidate chains no-op.
557-
boolean removed = false;
557+
int removed = 0;
558558
for (final EdgeLinkedList chain : chainsForNeighbour(direction == Vertex.DIRECTION.OUT ? edge.getIn() : edge.getOut()))
559-
removed |= chain.removeEdge(edge);
559+
removed += chain.removeEdge(edge);
560560
return removed;
561561
}
562562

0 commit comments

Comments
 (0)