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

Commit d5b510a

Browse files
robfrankrobfrank
committed
fix(#10302): a lightweight edge delete read through a stale edge list is a conflict, not a lost delete (#10316)
(cherry picked from commit 0762d99)
1 parent c978255 commit d5b510a

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
@@ -1130,9 +1130,17 @@ public void deleteEdge(final Edge edge, final RID skipEndpoint, final Vertex.DIR
11301130
*/
11311131
private void disconnectEndpoint(final Edge edge, final Vertex.DIRECTION direction, final RID skipEndpoint,
11321132
final Vertex.DIRECTION skipDirection) {
1133+
final boolean lightweight = edge instanceof LightEdge || edge.getIdentity().getPosition() < 0;
11331134
if (skipEndpoint != null && (skipDirection == null || skipDirection == direction) && skipEndpoint.equals(
1134-
direction == Vertex.DIRECTION.OUT ? edge.getOut() : edge.getIn()))
1135+
direction == Vertex.DIRECTION.OUT ? edge.getOut() : edge.getIn())) {
1136+
if (lightweight && skipDirection != null)
1137+
// THE ITERATOR REMOVES THE ENTRY ITSELF (#9779): IT IS A REMOVAL BY THIS TRANSACTION ALL THE SAME (#10302). It walks
1138+
// the transaction's own view, so the entry is there to remove; the one way it finds none is a delete listener or
1139+
// trigger that took it out first, through this transaction. Counting it then over-counts by one, which can only
1140+
// hide a stale view (the delete lost, as before #10302), never invent a conflict
1141+
lightEdgeEntriesRemoved(skipEndpoint, direction, edge, 1);
11351142
return;
1143+
}
11361144

11371145
final VertexInternal endpoint = resolveEndpointToDisconnect(edge, direction);
11381146
if (endpoint == null)
@@ -1157,17 +1165,25 @@ private void disconnectEndpoint(final Edge edge, final Vertex.DIRECTION directio
11571165
edge.getIdentity(), direction, endpoint.getIdentity());
11581166
return;
11591167
}
1160-
if (list != null && list.removeEdge(edge))
1168+
final int removed = list == null ? 0 : list.removeEdge(edge);
1169+
if (removed > 0) {
1170+
if (lightweight)
1171+
// ONE PER CHAIN THAT HELD A TWIN: A STRIPED LIST CAN REMOVE ONE IN EACH GENERATION (#10314)
1172+
lightEdgeEntriesRemoved(endpoint.getIdentity(), direction, edge, removed);
11611173
return;
1174+
}
11621175

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

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

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

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

@@ -1325,6 +1425,17 @@ private boolean committedEdgeListHolds(final VertexInternal vertex, final Vertex
13251425
return committedChainHolds(headRID, edge.getIdentity());
13261426
}
13271427

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