Deletion with defensive behavior

[Antonov548]

Detect Deleted Nodes That Should Be Restored

The Core Issue:

When one client modifies children of a node and another client deletes the parent node (before seeing the modifications), the deletion operation will delete the parent, causing the children to become orphaned. This effectively loses the work made by the first client on those children.

Current Behavior

When apply_delete() is called:

• The deleted node is detached from its parent
• The node is marked as tombstoned
• Children of the deleted node remain in the tree but become orphaned (they still exist but have no parent reference)
• Any modifications made to these children before the deletion arrived are preserved in the tree structure, but the parent-child relationship is lost

Functional Requirements

1. Preserve User Work: Modifications made to children before parent deletion should not be lost
2. Maintain Tree Integrity: Parent-child relationships should be preserved when possible
3. Conflict Detection: System should detect when deletions conflict with modifications
4. CRDT Semantics: Solution must maintain eventual consistency across all replicas
5. Operation Ordering: Solution must handle out-of-order operation delivery correctly
6. Idempotency: Applying the same operation multiple times should have the same effect

Proposed Implementation

Implement algorithm to find nodes which should be restored in order to preserve work. This algorithm should return list of nodes to restore. Also need to implement restore function which restore last valid parent of node.

In this case responsibility to merge conflict can be delegated to client side.

[marcus-pousette]

"This algorithm should return list of nodes to restore"

which function are we talking about?

The current behaviour is that

apply function consumes op(s) and return nothing.

But the new behaviour would maybe be

apply function consume op(s) and return additional ops it did to counter-act unwanted deletion(s) (these ops have already been applied internally)

[Antonov548]

apply function consume op(s) and return additional ops it did to counter-act unwanted deletion(s) (these ops have already been applied internally)

I thought about totally seperate function. So that when apply function is called it doesn't modify implcitly internal state becides what was provided as input.

The question also if the new operations should be added just after delete which should be restored or can be just inserted. I think it might be important if you think about next deletes after restored one.

[marcus-pousette]

I thought about totally seperate function. So that when apply function is called it doesn't modify implcitly internal state becides what was provided as input.

Are we talking about

pseudo code

alternative 1.

append(ops, { deleteBehaviour: 'defensive' }) -> [new ops to broadcast ]

VS

alternative 2.

append(ops) -> { deleted: [nodes] }

revive(nodes, { behaviour: 'defensive' }) -> [new ops to broadcast]

[Antonov548]

append(ops) -> { deleted: [nodes] }

revive(nodes, { behaviour: 'defensive' }) -> [new ops to broadcast]

And maybe alternative 3:

append(ops) -> void
let nodes = protect_nodes(ops) -> [nodes]
revive(nodes) -> [new ops to broadcast]

I mean by all of this to not touch right now adding logic and maybe revisit it later and merge both this methods.

[marcus-pousette]

thought about that one too!

the main concern with method separation is if that it might lead to non-optimal performance where the first method call would do some tree, log traversal that in the next call would somehow redundantly repeat. (I am not 100% yet what actually will happen, but this is just a general thing)

[Antonov548]

non-optimal performance

Yes, this is definitely not optimal approach. But I think that if the algorithm would be simple enough it will be possible to merge it with append() method (from pseudo code). Or also as option append() can collect metadata which can be used in protect_nodes().

[marcus-pousette]

That is true! But nevertheless the metadata collection would still need some memory usage, or lookups later, though more efficient. However might be negligible.

Maybe for a V0 solution of this would be to first create a few tests that isolated the behaviour we want (that will fail in the codebase current state). And then try to write the simplest possible solution to figure out what data is needed? Specifically if ops need next pointers or not.

Then we can improve that solution!

[Antonov548]

@marcus-pousette

This is summary of research regarding this topic. I would appriciate your feedback.

Defensive Deletion

Problem Statement

In a sync engine tree a delete operation is ambiguous under concurrency:

• One client may delete a node intentionally (expecting the whole subtree to be removed).
• Another client may concurrently add or modify content under that node.
• When these operations synchronize, it is impossible to infer intent from the delete event alone.

This leads to the defensive deletion requirement:

A node should remain deleted only if the client who deleted it was aware of all changes made under that node.

---

Core Challenge

A delete event does not encode causal knowledge. Without additional metadata, a replica cannot determine whether:

• the delete was intentional and authoritative, or
• the delete was issued without knowledge of concurrent or later edits.

Two general approaches exist to resolve this.

---

Approach 1: Deleting Client Is Responsible for Recovery

Description

The client that issues a delete is responsible for restoring the node if it later discovers concurrent changes under the deleted subtree.

Characteristics

• Deletes are applied eagerly.
• If the deleting client later syncs and detects modifications under the node, it must:
  • explicitly recreate the node, or
  • emit a compensating “undelete” operation.

Pros

• Simple delete semantics.
• No additional metadata on delete operations.

Cons

• Requires post-hoc repair logic. O(depth) checks on every insert
• Breaks offline assumptions if the deleting client never reconnects.
• Recovery logic becomes client-specific and non-deterministic.
• Other replicas cannot independently decide correctness.

Conclusion

This approach scales poorly and is fragile in offline system. Also makes insertion heavy operation.
It will also require to generate new recovery operations and sends them back to the client who initiated deletion.

---

Approach 2: Receiving Client Resolves Delete via Causal Knowledge

Description

Deletes are treated as conditional operations.
A replica applies a delete only if the deleting client was causally aware of all changes under the node at the time of deletion.

Recovery is automatic and deterministic.

---

Minimal Metadata Scheme

id
parent_id 
last_change
deleted_at

Pseudocode of operations with recovery logic:

#insert/modify
node.last_change = max(node.last_change, op.timestamp)
parent.last_change = max(parent.last_change, op.timestamp)

#delete
if op.known_state < node.last_change:
    ignore delete  // deleter was unaware of changes
else:
    node.deleted_at = max(node.deleted_at, op.timestamp)


#check if node persist
node is visible if:
    deleted_at == null
    OR last_change > deleted_at

[marcus-pousette]

My comments

Approach 1.

I think this breaks good UX. Because one node might delete stuff, then go offline (sync with some sync-server before going offline). Then another node comes online receives the delete, becomes unhappy but can not do anything about it, until the first node (the deleter), comes back again?

I think you outlined it well in the cons

Breaks offline assumptions if the deleting client never reconnects.
Recovery logic becomes client-specific and non-deterministic.
Other replicas cannot independently decide correctness.

Approach 2.

Receiving Client Resolves Delete via Causal Knowledge

conceptually makes sense. But I wonder if deletes are not conditional but revival is.

Recovery is automatic and deterministic.

you maybe actually stated it here.

I am still not sure here if the casual knowledge you stated is enough. I wonder if you start with a test implementation you will very quickly figure out if there is causal knowledge that is missing?

But for the data model you provided.
id parent_id last_change deleted_at

What is parent_id and how is it used?

[Antonov548]

But for the data model you provided. id parent_id last_change deleted_at

What is parent_id and how is it used?

I just wanted to outline that last_change and deleted_at is part of data model of node with id and parent_id fields. But just ignore it please. The only important things are: last_change and deleted_at.

[marcus-pousette]

I am continuing our discussion here, regarding the challenges with Approach B.

Conceptually, explore this mental model one could have about defensive delete behaviour:

Imagine instead of talking about a graph, we are talking about two peers editing a picture.

Imagine at

t0 it is created for client A and B. The picture now shows a dog.

at

t1. client A draws a moustache on the dog. client B never sees this

t2. client B deletes the images (t2 > t1 !) thinking it was just a picture of a dog with no moustache

at

t3. client A receives the delete op from client B

Expectation, in defensive deletion, client A and client B would eventually converge on the state that the image should persist because client B did not see the picture edit before deletion. But
your pseudo code applied here gives the opposite result

#insert/modify
image.last_change = max(image.last_change, op.timestamp)


#delete
if op.known_state < image.last_change: 
    ignore delete  // deleter was unaware of changes
else: // t2 > t1 so we enter here
    image.deleted_at = max(image.deleted_at, op.timestamp) 


#check if node persist
image is visible if:
    deleted_at == null 
    OR last_change > deleted_at // this will evaluate to false

[Antonov548]

My wrong assumption was that it also might work with timestamp. But acutally inital idea which I not outlined in first comment that last_change and known_state should be time agnostic. Basically it should represent not time of deletion, but awareness of operations applied to node.

It could be simple counter. But I also found that for such cases version vector could be used. I didn't dive deep into this topic, but there is also different variants of such vector.

Let's assume for now that it's just counter and example with image.

• t0 it is created for client A and B. The picture now shows a dog.

• t1 client A draws a moustache on the dog. Client B never see it.

• then again for client B it's also t1 because client B is not aware of client A operation and counter is not updated.
  t1 client B deletes the image. At this point it just image of dog without moustache. For delete operation known_state will be t0 because at the moment of deletion counter on client B for image operations was t0.

Then client A received update from client B.

• t0 create image
• t1 draw moustache
• t2 delete image
  • we interested in deletion. At the moment of deletion last_change will be t1 and deletion known_state is t0. So, deletion should be ignored.

# insert/modify
# op.timestamp should be time agnostic. Let's assume it just counter of operations.
# this just should update version vector of node using maximum rule. Take the largest counter.
image.last_change = max(image.last_change, op.timestamp) 

# delete
# op.known_state = t0 
# image.last_change = t1
# t1 > t0 we ignore the deletion
if op.known_state < image.last_change: 
    ignore delete 
else: 
    image.deleted_at = max(image.deleted_at, op.timestamp) 

[marcus-pousette]

Where I’m still unsure about the current proposal is that it reduces that causal knowledge to a single scalar (last_change = max(...) and known_state < last_change). A single counter / max only really works in very constrained cases; with multiple replicas you generally need a partial-order structure (VV-like, and if knowledge can have holes then dotted/DVV-set or explicit dot sets), otherwise you can’t answer “did the deleter see replica X’s op Y?”.

Also, for our actual tree problem we need the check to be about any edit in the subtree, not just edits “on the parent node”. That implies we must define what counts as “subtree(P)” under moves, and maintain/query a subtree_context(P) summary (or equivalent) so delete(P) can be validated against descendant edits.

-------- partial bot analytics below

Metadata design (esp. deleting high up with huge subtrees)

If we want: “delete(P) should only stick if the deleter had seen all edits anywhere in subtree(P)”, then we need:

1. A causal known_state on the delete op (not time/lamport):

   • delete(P).known_state = deleter’s causal context at delete time
   • This likely needs to be VV-like, but if we can have holes (see A#5 without A#4), then a dotted VV / DVV-set (or explicit dot set as a first prototype) is the right shape.

2. A way to check ‘is there any unseen edit in subtree(P)?’ without enumerating the whole subtree at delete time.

   • The scalable approach is to maintain a derived index (not CRDT state) like subtree_context(P) that summarizes “ops that affected any node currently in subtree(P)”.
   • Then delete handling is just:

     if subtree_context(P) ⊄ delete.known_state: ignore/undo delete
     else: apply delete
     

   • For “delete very far up”: the whole point is subtree_context(P) must be cached/materialized so delete doesn’t do O(size_of_subtree) work. Maintaining it incrementally is the hard part (moves across the boundary are the worst case), but because it’s derived from the op log it can be recomputed/cached with whatever strategy we want (ancestor-propagation, periodic recompute, SQLite query + cache, etc).

What about partially synced subtrees?

This is the key limitation: if a replica hasn’t synced all ops under P, it literally cannot know whether there exists an unseen edit that should block the delete.

So in partial replication you get this behavior:

• Replica X may apply delete(P) because, locally, subtree_context(P) looks empty/old.
• Later, when X syncs more descendant ops, subtree_context(P) increases and X deterministically “flips” and revives/ignores the delete.
• If X never syncs that subtree at all, X may never revive — that’s not a CRDT bug, it’s an inherent property of partial replication. Convergence is only guaranteed among replicas that eventually receive the relevant ops/metadata for that scope.

Practical implication: if we want defensive deletes to be stable in a filtered view, that view must include enough info to compute subtree_context(P) (either the actual ops or some summary/index for that subtree). Otherwise deletes have to be treated as provisional until deeper sync happens.

[marcus-pousette]

if subtree_context(P) ⊄ delete.known_state: ignore/undo delete
else: apply delete

type Operation = {
  meta: { id: { replica: ReplicaId; counter: number }; lamport: number };
  kind:
    | { type: "insert"; ... }
    | { type: "move"; ... }
    | { type: "delete"; node: NodeId; knownState: CausalContext };
};

type CausalContext =
  // contiguous knowledge
  | { kind: "vv"; vv: Array<{ replica: ReplicaId; counter: number }> }
  // hole-aware knowledge (DVV-ish)
  | { kind: "dvv"; vv: Array<{ replica: ReplicaId; counter: number }>; dots: Array<{ replica: ReplicaId; counter: number }> };