It seems that GC of Array and Object is not working properly.

[dc7303]

I am currently implementing GC of Text and RichText.
However, there was a problem with the implementation.

The problem is that container objects such as root and element are copied and used inside Yorkie.
So using objects in 'operation.Execute' and the object used by the client are different ones.
(Here, the object used by the client means the object returned to root.GetXXX () in the callback of 'document.Update')

And for this reason, it is difficult to track the garbage nodes to be collected.

In this process, I wondered if the GC previously implemented in Array and Object is working properly.
So I analyzed it.

For the modifications below, refer to the changes marked with ####. And you can test with the modified code.

The changes below were made to keep a history.
You can check it more quickly by referring to my work branch. This branch may be removed later.

#### Add doc.Update in last line of 'garbage collection test'
+++ b/pkg/document/document_test.go
@@ -126,6 +126,14 @@ func TestDocument(t *testing.T) {
 
 		assert.Equal(t, 4, doc.GarbageCollect(time.MaxTicket))
 		assert.Equal(t, 0, doc.GarbageLen())
+		fmt.Println("-------- delete array and garbage collect ---------")
+
+		err = doc.Update(func(root *proxy.ObjectProxy) error {
+			arr := root.GetArray("2")
+			fmt.Printf("[Test.arr] %p | %s \n", arr, arr.Marshal())
+			root.Delete("1")
+			return nil
+		}, "deletes 2")
 	})
 
 	t.Run("garbage collection test 2", func(t *testing.T) {
 	
 	


#### Node.isRemoved() check logic comment processing in '(rht *RHTPriorityQueueMap) Get()' function
#### Fix not to check isRemove() in '(rht *RHTPriorityQueueMap) Elements()'
+++ b/pkg/document/json/rht_pq_map.go
@@ -81,9 +81,9 @@ func (rht *RHTPriorityQueueMap) Get(key string) Element {
 	}
 
 	node := queue.Peek().(*RHTPQMapNode)
-	if node.isRemoved() {
-		return nil
-	}
+	//if node.isRemoved() {
+	//	return nil
+	//}
 	return node.elem
 }
 
@@ -141,9 +141,11 @@ func (rht *RHTPriorityQueueMap) Elements() map[string]Element {
 		if queue.Len() == 0 {
 			continue
 		}
-		if node := queue.Peek().(*RHTPQMapNode); !node.isRemoved() {
-			members[node.key] = node.elem
-		}
+		//if node := queue.Peek().(*RHTPQMapNode); !node.isRemoved() {
+		//	members[node.key] = node.elem
+		//}
+		node := queue.Peek().(*RHTPQMapNode)
+		members[node.key] = node.elem
 	}
 
 	return members




#### Add code to check address and status of removedElementPair elements in 'GarbageCollecㅅ()'
+++ b/pkg/document/json/root.go
@@ -17,6 +17,8 @@
 package json
 
 import (
+	"fmt"
+
 	"github.com/yorkie-team/yorkie/pkg/document/time"
 )
 
@@ -96,6 +98,8 @@ func (r *Root) GarbageCollect(ticket *time.Ticket) int {
 
 	for _, pair := range r.removedElementPairMapByCreatedAt {
 		if pair.elem.RemovedAt() != nil && ticket.Compare(pair.elem.RemovedAt()) >= 0 {
+			fmt.Printf("[root.GarbageCollect.parent] %p | %s\n", pair.parent, pair.parent.Marshal())
+			fmt.Printf("[root.GarbageCollect.elem] %p | %s\n", pair.elem, pair.elem.Marshal())
 			pair.parent.Purge(pair.elem)
 			count += r.garbageCollect(pair.elem)
 		}




#### Add output code to check parent and element address and status when Edit Operation is executed
+++ b/pkg/document/operation/remove.go
@@ -17,6 +17,8 @@
 package operation
 
 import (
+	"fmt"
+
 	"github.com/yorkie-team/yorkie/pkg/document/json"
 	"github.com/yorkie-team/yorkie/pkg/document/time"
 )
@@ -46,6 +48,8 @@ func (o *Remove) Execute(root *json.Root) error {
 	case *json.Object:
 		elem := parent.DeleteByCreatedAt(o.createdAt, o.executedAt)
 		root.RegisterRemovedElementPair(parent, elem)
+		fmt.Printf("[remove.Execute.parent] %p | %s\n", parent, parent.Marshal())
+		fmt.Printf("[remove.Execute.elem] %p | %s\n", elem, elem.Marshal())
 	case *json.Array:
 		elem := parent.DeleteByCreatedAt(o.createdAt, o.executedAt)
 		root.RegisterRemovedElementPair(parent, elem)
 		
 		
 		
 		
#### After calling'GarbageCollect()', it is necessary to check the state of the object used by the client,
#### so add the code to the'GetArray()' function
+++ b/pkg/document/proxy/object_proxy.go
@@ -17,6 +17,7 @@
 package proxy
 
 import (
+	"fmt"
 	time2 "time"
 
 	"github.com/yorkie-team/yorkie/pkg/document/change"
@@ -174,6 +175,7 @@ func (p *ObjectProxy) GetObject(k string) *ObjectProxy {
 }
 
 func (p *ObjectProxy) GetArray(k string) *ArrayProxy {
+	fmt.Printf("[object_proxy.GetArray.Object] %p | %s\n", p.Object, p.Object.Marshal())
 	elem := p.Object.Get(k)
 	if elem == nil {
 		return nil

If you run the 'garbage collection test' test of 'document_test.go' after modification, the following log is displayed.

[remove.Execute.parent] 0xc00000fb20 | {"1":1,"2":[1,2,3],"3":3}
[remove.Execute.elem] 0xc00000fec0 | [1,2,3]
[root.GarbageCollect.parent] 0xc00000fb20 | {"1":1,"2":[1,2,3],"3":3}
[root.GarbageCollect.elem] 0xc00000fec0 | [1,2,3]
-------- delete array and garbage collect ---------
[object_proxy.GetArray.Object] 0xc00000fba0 | {"1":1,"2":[1,2,3],"3":3}
[Test.arr] 0xc0002d4910 | [1,2,3] 
[remove.Execute.parent] 0xc00000fb20 | {"1":1,"3":3}
[remove.Execute.elem] 0xc000223530 | 1
....

The important thing in this log is after 'delete array and garbage collect' is printed.
Object_proxy.GetArray.Object and Test.arr are objects used by the client.
The object used by the client still has a value of "2".
However, for the object used in the remove operation, you can see that the value "2" has been removed by the garbage collector.

I don't know if it's intended to behave like this.
However, it doesn't seem like a complete garbage collection.
I'm curious about your opinion.

[hackerwins]

@dc7303
Thank you for the detailed explanation. I probably missed what you said when implementing GC. I observed that the memory does not actually decrease after GC, and it seems to be caused by the situation you mentioned.