GC error when referencing nodes deleted by detached client

[chacha912]

What happened:

When performing garbage collection (GC), an error occurs if we use minVersionVector.minLamport() for detached clients whose lamport is not present in the minimum version vector (minVV). This leads to a node reference error when other clients haven't yet acknowledged the detach operation.

Current Behavior

1. When calculating minVV, lamports from detached clients are filtered out
2. If a client's lamport is missing from minVV, we currently use minVersionVector.minLamport()
3. This assumes all clients have synced up to the minimum lamport in minVV
4. However, this assumption breaks when dealing with detached clients since their lamports are filtered out

How to reproduce it (as minimally and precisely as possible):

t.Run("detach gc test", func(t *testing.T) {
	clients := activeClients(t, 3)
	c1, c2, c3 := clients[0], clients[1], clients[2]
	defer deactivateAndCloseClients(t, clients)
	ctx := context.Background()
	d1 := document.New(helper.TestDocKey(t))
	d2 := document.New(helper.TestDocKey(t))
	d3 := document.New(helper.TestDocKey(t))

	assert.NoError(t, c1.Attach(ctx, d1))
	assert.NoError(t, c2.Attach(ctx, d2))
	assert.NoError(t, c3.Attach(ctx, d3))
	assert.NoError(t, c3.Sync(ctx))
	assert.NoError(t, c2.Sync(ctx))
	assert.NoError(t, c2.Sync(ctx))
	assert.NoError(t, c1.Sync(ctx))
	assert.NoError(t, c1.Sync(ctx))

	assert.Equal(t, true, checkVV(d1.VersionVector(), versionOf(d1.ActorID(), 3), versionOf(d2.ActorID(), 1), versionOf(d3.ActorID(), 1)))
	assert.Equal(t, true, checkVV(d2.VersionVector(), versionOf(d1.ActorID(), 1), versionOf(d2.ActorID(), 3), versionOf(d3.ActorID(), 1)))
	assert.Equal(t, true, checkVV(d3.VersionVector(), versionOf(d1.ActorID(), 1), versionOf(d2.ActorID(), 1), versionOf(d3.ActorID(), 3)))

	err := d1.Update(func(root *json.Object, p *presence.Presence) error {
		root.SetNewText("text").Edit(0, 0, "a").Edit(1, 1, "b").Edit(2, 2, "c") // abc
		return nil
	}, "insert abc")
	assert.NoError(t, err)

	assert.NoError(t, c1.Sync(ctx))
	assert.NoError(t, c2.Sync(ctx))
	assert.NoError(t, c2.Sync(ctx))
	assert.NoError(t, c3.Sync(ctx))
	assert.NoError(t, c3.Sync(ctx))

	assert.Equal(t, true, checkVV(d1.VersionVector(), versionOf(d1.ActorID(), 4), versionOf(d2.ActorID(), 1), versionOf(d3.ActorID(), 1)))
	assert.Equal(t, true, checkVV(d2.VersionVector(), versionOf(d1.ActorID(), 4), versionOf(d2.ActorID(), 5), versionOf(d3.ActorID(), 1)))
	assert.Equal(t, true, checkVV(d3.VersionVector(), versionOf(d1.ActorID(), 4), versionOf(d2.ActorID(), 1), versionOf(d3.ActorID(), 5)))

	err = d3.Update(func(root *json.Object, p *presence.Presence) error {
		root.GetText("text").Edit(1, 3, "") // delete bc
		return nil
	}, "delete bc")
	assert.NoError(t, err)

	// 😃 c1, c2 actively edit and sync, increasing their lamports
	err = d1.Update(func(root *json.Object, p *presence.Presence) error {
		root.GetText("text").Edit(0, 0, "1") // 1abc
		return nil
	}, "insert 1")
	assert.NoError(t, err)
	err = d1.Update(func(root *json.Object, p *presence.Presence) error {
		root.GetText("text").Edit(0, 0, "2") // 21abc
		return nil
	}, "insert 2")
	assert.NoError(t, err)
	err = d1.Update(func(root *json.Object, p *presence.Presence) error {
		root.GetText("text").Edit(0, 0, "3") // 321abc
		return nil
	}, "insert 3")
	assert.NoError(t, err)
	err = d2.Update(func(root *json.Object, p *presence.Presence) error {
		root.GetText("text").Edit(3, 3, "x") // abcx
		return nil
	}, "insert x")
	assert.NoError(t, err)
	err = d2.Update(func(root *json.Object, p *presence.Presence) error {
		root.GetText("text").Edit(4, 4, "y") // abcxy
		return nil
	}, "insert y")
	assert.NoError(t, err)

	assert.NoError(t, c1.Sync(ctx))
	assert.NoError(t, c2.Sync(ctx))
	assert.NoError(t, c2.Sync(ctx))
	assert.NoError(t, c1.Sync(ctx))
	assert.NoError(t, c1.Sync(ctx))

	assert.Equal(t, "321abcxy", d1.Root().GetText("text").String())
	assert.Equal(t, "321abcxy", d2.Root().GetText("text").String())
	assert.Equal(t, true, checkVV(d1.VersionVector(), versionOf(d1.ActorID(), 9), versionOf(d2.ActorID(), 7), versionOf(d3.ActorID(), 1)))
	assert.Equal(t, true, checkVV(d2.VersionVector(), versionOf(d1.ActorID(), 7), versionOf(d2.ActorID(), 10), versionOf(d3.ActorID(), 1)))
	assert.Equal(t, true, checkVV(d3.VersionVector(), versionOf(d1.ActorID(), 4), versionOf(d2.ActorID(), 1), versionOf(d3.ActorID(), 6)))

	// c3 detach
	assert.NoError(t, c3.Detach(ctx, d3))
	err = d2.Update(func(root *json.Object, p *presence.Presence) error {
		root.GetText("text").Edit(5, 5, "z") // 321abzcxy
		return nil
	}, "insert z")
	assert.NoError(t, err)
	assert.Equal(t, "321abzcxy", d2.Root().GetText("text").String())

	assert.NoError(t, c1.Sync(ctx))
	assert.Equal(t, "321axy", d1.Root().GetText("text").String())
	// 🚨 gc run !
	assert.Equal(t, 0, d1.GarbageLen())

	assert.NoError(t, c2.Sync(ctx))
	// 🚨 When c1 receives d2's update, an error occurs: the node of the given id should be found
	assert.NoError(t, c1.Sync(ctx))
})

The following sequence demonstrates the issue:

1. Clients A, B, and C are attached to a document
2. A and B actively edit and sync, increasing their lamports
3. C deletes some nodes without syncing and then detaches
4. B makes edits within the range that C will delete
5. A receives C's changes first
   • Since C is detached, their value is filtered from minVV
   • minVV's minimum value is used (e.g., 7)
   • GC runs because removedAt(6@C) < minVV(7)
6. A receives B's changes
   • Error occurs because B's edits reference nodes that C deleted and were garbage collected

Anything else we need to know?:

Proposed Solutions

Note by @JOOHOJANG : https://codepair.yorkie.dev/jooho/6751b5989b55661e0466876c/share?token=rwat6

Solution 1: Keep Detached Users' Lamports

1. Don't filter out lamports of detached users from minVV
2. Pros: Simple implementation, Guarantees data safety by preserving complete version history
3. Cons: Version vector size continues to grow

Solution 2: Track Detach Acknowledgment

1. Stop relying on DB.VV table for detached user lamport filtering
2. Store detached user data as {actorID: lamport} in a separate table
3. Only remove from minVV when minVV[detachedClientID] === detachedClientLamport
   (This indicates all users have received the detach change)
4. Considerations: Before removing detached clients from VV, we need to verify proper operation in both GC and maxCreatedAt scenarios

Environment:

• Operating system:
• Browser and version:
• Yorkie version (use yorkie version): 0.5.6
• Yorkie JS SDK version: