Concurrent edge insertion into a super-node vertex drops edges (edge-list chunk-allocation race)

[lvca]

Summary

Under concurrent edge insertion into the same super-node (hot) vertex, the graph engine can drop edges and occasionally orphan an edge-list chunk. It is a data-loss race in the edge-list chunk allocation / head-pointer path, independent of query language or edge kind (reproduces with both regular and light edges).

It reproduces on main (26.7.2-SNAPSHOT) and is pre-existing - it is NOT caused by the commutative edge-append merge (arcadedb.graph.edgeAppendMerge): it reproduces identically with that feature disabled. (The merge actually reduces the loss, because it removes most of the full-transaction retries that widen the race window.)

Impact

• Silent edge loss: transactions report success but a few of the committed edges are missing from the hub vertex's edge list.
• Occasionally an orphaned chunk: the vertex's inEdgesHeadChunk/outEdgesHeadChunk points at a chunk that is then not found, logged as SEVERE and "repaired" by starting a fresh chunk - which orphans everything previously linked behind it.
• Directly relevant to the super-node write-contention workloads we are hardening (payments graph funnelling into a central account).

Severity: high (silent data loss under a realistic concurrent workload).

Reproduction

Many threads concurrently add an edge into one shared hub vertex. Spreading the per-transaction source vertices / edge records across many buckets makes the hub's edge-list append the dominant contention and makes the race fire reliably:

// 8 threads, each committing 4000 edges (Src -> Hub), retries handle MVCC conflicts.
// Src/LINK use 16 buckets so record insertion is not the bottleneck; Hub has 1 bucket.
for (int t = 0; t < 8; t++) new Thread(() -> {
  for (int i = 0; i < 4000; i++)
    db.transaction(() -> {
      final MutableVertex src = db.newVertex("Src");
      src.save();
      src.newEdge("LINK", hubRID);
    }, false, 10_000);
}).start();
// ... join, then:
long inDegree = hubRID.asVertex().countEdges(Vertex.DIRECTION.IN, "LINK"); // < 32000

Observed (append-merge DISABLED, i.e. baseline engine behaviour)

• hub IN-degree = 31863 for 32000 committed edges (137 lost). Repeats every run with a variable small deficit.
• With light edges at lower volume the deficit is smaller but still non-zero (e.g. 6407/6408).
• Occasional log line:

SEVERE [GraphEngine] Record #3:1 (inEdgesHeadChunk) not found on vertex #1:0@Hub. Creating a new one

(GraphEngine.createInEdgeChunk, engine/.../graph/GraphEngine.java:271)

A single-bucket source pattern with heavy insertion contention (which serialises the hub appends) hides the race - so it is timing/window dependent.

Root-cause hypothesis (needs confirmation)

When a hub's head chunk fills, EdgeLinkedList.add() allocates a new chunk, links newChunk.previous = oldHead, and updates the vertex record's head-chunk pointer (setInEdgesHeadChunk / setOutEdgesHeadChunk). Two transactions that concurrently fill the same head chunk each allocate their own new chunk pointing at the same predecessor and each rewrite the vertex head pointer. MVCC on the vertex record page should serialise this, but the observed loss + "chunk not found" suggests the chunk-chain relink and the head-pointer update are not being validated/serialised as one unit for all interleavings (e.g. a new chunk created in a transaction that later rolls back, while another transaction's head-pointer update referencing state around it survives; or a lost update on the previous link, orphaning a chunk and the edges behind it).

Key code:

• engine/src/main/java/com/arcadedb/graph/EdgeLinkedList.java - add() new-chunk branch (chunk full → new chunk + setInEdgesHeadChunk/setOutEdgesHeadChunk).
• engine/src/main/java/com/arcadedb/graph/GraphEngine.java - createInEdgeChunk / createOutEdgeChunk (head-chunk creation; the SEVERE "not found → create a new one" fallback that orphans the old chain).

Suggested direction

• Add a deterministic 2-thread reproduction that forces the concurrent chunk-full transition on one vertex.
• Ensure the new-chunk allocation + previous relink + vertex head-pointer update are covered by the MVCC page-version checks such that concurrent chunk-full transitions on the same vertex conflict and retry cleanly, with no orphaned chunk.
• Replace the SEVERE "not found → create a new one" fallback (which silently orphans edges) with a fail-loud/retry path once the race is fixed.

Notes

Found while building the super-node concurrent-append benchmark for the commutative edge-append merge work. The merge's own correctness is separately gated (green) by ConcurrentEdgeAppendMergeTest.