Repository: yorkie-team/yorkie
Pull request #55 (2020-05-23 12:50:17)

Add Document.GarbageCollect
<!--  Thanks for sending a pull request! -->

**What type of PR is this?**
> Uncomment only one ` /kind <>` line, hit enter to put that in a new line, and remove leading whitespace from that line:
>
> /kind api-change
> /kind bug
> /kind cleanup
> /kind deprecation
> /kind design
> /kind documentation
> /kind failing-test

/kind feature

**What this PR does / why we need it**:

Implement garbage collection

```
# Inserts 10000 integer elements with the tombstone

-----
mem.Alloc: 10.9 MiB
mem.TotalAlloc: 17.8 MiB
mem.HeapAlloc: 10.9 MiB
mem.NumGC: 4
-----

# After garbage collection

-----
mem.Alloc: 5.0 MiB
mem.TotalAlloc: 19.4 MiB
mem.HeapAlloc: 5.0 MiB
mem.NumGC: 5
```

**Which issue(s) this PR fixes**:
<!--
*Automatically closes linked issue when PR is merged.
Usage: `Fixes #<issue number>`, or `Fixes (paste link of issue)`.
-->
Address #3

**Special notes for your reviewer**:

**Does this PR introduce a user-facing change?**:
<!--
If no, just write "NONE" in the release-note block below.
If yes, a release note is required:
Enter your extended release note in the block below. If the PR requires additional action from users switching to the new release, include the string "action required".
-->
```release-note

```

**Additional documentation**:

<!--
This section can be blank if this pull request does not require a release note.

Please use the following format for linking documentation:
- [Usage]: <link>
- [Other doc]: <link>
-->
```docs

```


codecov[bot]: # [Codecov](https://codecov.io/gh/yorkie-team/yorkie/pull/55?src=pr&el=h1) Report
> Merging [#55](https://codecov.io/gh/yorkie-team/yorkie/pull/55?src=pr&el=desc) into [master](https://codecov.io/gh/yorkie-team/yorkie/commit/424298cf94d6b3f261f6efba436b96192a6b8f86&el=desc) will **decrease** coverage by `0.86%`.
> The diff coverage is `10.98%`.

[![Impacted file tree graph](https://codecov.io/gh/yorkie-team/yorkie/pull/55/graphs/tree.svg?width=650&height=150&src=pr&token=P6COB1ZNIC)](https://codecov.io/gh/yorkie-team/yorkie/pull/55?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master      #55      +/-   ##
==========================================
- Coverage   56.64%   55.77%   -0.87%     
==========================================
  Files          23       23              
  Lines        2507     2555      +48     
==========================================
+ Hits         1420     1425       +5     
- Misses        992     1035      +43     
  Partials       95       95              
```


| [Impacted Files](https://codecov.io/gh/yorkie-team/yorkie/pull/55?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pkg/document/json/array.go](https://codecov.io/gh/yorkie-team/yorkie/pull/55/diff?src=pr&el=tree#diff-cGtnL2RvY3VtZW50L2pzb24vYXJyYXkuZ28=) | `13.43% <0.00%> (-0.63%)` | :arrow_down: |
| [pkg/document/json/rga\_tree\_list.go](https://codecov.io/gh/yorkie-team/yorkie/pull/55/diff?src=pr&el=tree#diff-cGtnL2RvY3VtZW50L2pzb24vcmdhX3RyZWVfbGlzdC5nbw==) | `33.73% <0.00%> (-1.94%)` | :arrow_down: |
| [pkg/document/json/root.go](https://codecov.io/gh/yorkie-team/yorkie/pull/55/diff?src=pr&el=tree#diff-cGtnL2RvY3VtZW50L2pzb24vcm9vdC5nbw==) | `19.04% <6.66%> (-44.59%)` | :arrow_down: |
| [pkg/document/json/object.go](https://codecov.io/gh/yorkie-team/yorkie/pull/55/diff?src=pr&el=tree#diff-cGtnL2RvY3VtZW50L2pzb24vb2JqZWN0Lmdv) | `25.49% <10.00%> (-1.60%)` | :arrow_down: |
| [pkg/document/json/rht\_pq\_map.go](https://codecov.io/gh/yorkie-team/yorkie/pull/55/diff?src=pr&el=tree#diff-cGtnL2RvY3VtZW50L2pzb24vcmh0X3BxX21hcC5nbw==) | `53.33% <10.00%> (-5.93%)` | :arrow_down: |
| [pkg/document/internal\_document.go](https://codecov.io/gh/yorkie-team/yorkie/pull/55/diff?src=pr&el=tree#diff-cGtnL2RvY3VtZW50L2ludGVybmFsX2RvY3VtZW50Lmdv) | `20.77% <10.52%> (+4.77%)` | :arrow_up: |
| [pkg/document/json/rht.go](https://codecov.io/gh/yorkie-team/yorkie/pull/55/diff?src=pr&el=tree#diff-cGtnL2RvY3VtZW50L2pzb24vcmh0Lmdv) | `52.50% <50.00%> (ø)` | |
| [api/converter/to\_bytes.go](https://codecov.io/gh/yorkie-team/yorkie/pull/55/diff?src=pr&el=tree#diff-YXBpL2NvbnZlcnRlci90b19ieXRlcy5nbw==) | `94.59% <100.00%> (ø)` | |
| [pkg/document/document.go](https://codecov.io/gh/yorkie-team/yorkie/pull/55/diff?src=pr&el=tree#diff-cGtnL2RvY3VtZW50L2RvY3VtZW50Lmdv) | `42.85% <100.00%> (+3.83%)` | :arrow_up: |
| [pkg/llrb/llrb.go](https://codecov.io/gh/yorkie-team/yorkie/pull/55/diff?src=pr&el=tree#diff-cGtnL2xscmIvbGxyYi5nbw==) | `78.23% <0.00%> (+2.04%)` | :arrow_up: |
| ... and [1 more](https://codecov.io/gh/yorkie-team/yorkie/pull/55/diff?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/yorkie-team/yorkie/pull/55?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/yorkie-team/yorkie/pull/55?src=pr&el=footer). Last update [424298c...80cc1ed](https://codecov.io/gh/yorkie-team/yorkie/pull/55?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).


Patch:
diff --git a/api/converter/to_bytes.go b/api/converter/to_bytes.go
index 11368ff2..b921d3f0 100644
--- a/api/converter/to_bytes.go
+++ b/api/converter/to_bytes.go
@@ -154,7 +154,7 @@ func toRichTextNodes(textNodes []*json.RGATreeSplitNode) []*api.RichTextNode {
 		value := textNode.Value().(*json.RichTextValue)
 
 		attrs := make(map[string]*api.RichTextNodeAttr)
-		for _, node := range value.Attrs().AllNodes() {
+		for _, node := range value.Attrs().Nodes() {
 			attrs[node.Key()] = &api.RichTextNodeAttr{
 				Key:       node.Key(),
 				Value:     node.Value(),
diff --git a/pkg/document/document.go b/pkg/document/document.go
index ede147c3..9fef9dde 100644
--- a/pkg/document/document.go
+++ b/pkg/document/document.go
@@ -192,6 +192,11 @@ func (d *Document) ensureClone() {
 	}
 }
 
+// GarbageCollect purge elements that were removed before the given time.
+func (d *Document) GarbageCollect(ticket *time.Ticket) int {
+	return d.doc.GarbageCollect(ticket)
+}
+
 func messageFromMsgAndArgs(msgAndArgs ...interface{}) string {
 	if len(msgAndArgs) == 0 {
 		return ""
diff --git a/pkg/document/internal_document.go b/pkg/document/internal_document.go
index d20c8164..a0de5362 100644
--- a/pkg/document/internal_document.go
+++ b/pkg/document/internal_document.go
@@ -126,36 +126,9 @@ func (d *InternalDocument) ApplyChangePack(pack *change.Pack) error {
 	return nil
 }
 
-func (d *InternalDocument) applySnapshot(snapshot []byte, serverSeq uint64) error {
-	rootObj, err := converter.BytesToObject(snapshot)
-	if err != nil {
-		return err
-	}
-
-	d.root = json.NewRoot(rootObj)
-
-	if d.HasLocalChanges() {
-		for _, c := range d.localChanges {
-			if err := c.Execute(d.root); err != nil {
-				return err
-			}
-		}
-	}
-	d.changeID = d.changeID.SyncLamport(serverSeq)
-
-	return nil
-}
-
-// applyChanges applies remote changes to both the clone and the document.
-func (d *InternalDocument) applyChanges(changes []*change.Change) error {
-	for _, c := range changes {
-		if err := c.Execute(d.root); err != nil {
-			return err
-		}
-		d.changeID = d.changeID.SyncLamport(c.ID().Lamport())
-	}
-
-	return nil
+// GarbageCollect purge elements that were removed before the given time.
+func (d *InternalDocument) GarbageCollect(ticket *time.Ticket) int {
+	return d.root.GarbageCollect(ticket)
 }
 
 // Marshal returns the JSON encoding of this document.
@@ -199,3 +172,35 @@ func (d *InternalDocument) IsAttached() bool {
 func (d *InternalDocument) RootObject() *json.Object {
 	return d.root.Object()
 }
+
+func (d *InternalDocument) applySnapshot(snapshot []byte, serverSeq uint64) error {
+	rootObj, err := converter.BytesToObject(snapshot)
+	if err != nil {
+		return err
+	}
+
+	d.root = json.NewRoot(rootObj)
+
+	if d.HasLocalChanges() {
+		for _, c := range d.localChanges {
+			if err := c.Execute(d.root); err != nil {
+				return err
+			}
+		}
+	}
+	d.changeID = d.changeID.SyncLamport(serverSeq)
+
+	return nil
+}
+
+// applyChanges applies remote changes to both the clone and the document.
+func (d *InternalDocument) applyChanges(changes []*change.Change) error {
+	for _, c := range changes {
+		if err := c.Execute(d.root); err != nil {
+			return err
+		}
+		d.changeID = d.changeID.SyncLamport(c.ID().Lamport())
+	}
+
+	return nil
+}
diff --git a/pkg/document/json/array.go b/pkg/document/json/array.go
index 69072f46..5c7be1b1 100644
--- a/pkg/document/json/array.go
+++ b/pkg/document/json/array.go
@@ -37,6 +37,11 @@ func NewArray(elements *RGATreeList, createdAt *time.Ticket) *Array {
 	}
 }
 
+// Purge physically purge child element.
+func (a *Array) Purge(elem Element) {
+	a.elements.purge(elem)
+}
+
 // Add adds the given element at the last.
 func (a *Array) Add(elem Element) *Array {
 	a.elements.Add(elem)
@@ -147,15 +152,18 @@ func (a *Array) Len() int {
 	return a.elements.Len()
 }
 
-func (a *Array) Descendants(descendants chan Element) {
+func (a *Array) Descendants(callback func(elem Element, parent Container) bool) {
 	for _, node := range a.elements.Nodes() {
+		if callback(node.elem, a) {
+			return
+		}
+
 		switch elem := node.elem.(type) {
 		case *Object:
-			elem.Descendants(descendants)
+			elem.Descendants(callback)
 		case *Array:
-			elem.Descendants(descendants)
+			elem.Descendants(callback)
 		}
-		descendants <- node.elem
 	}
 }
 
diff --git a/pkg/document/json/element.go b/pkg/document/json/element.go
index e7607994..9f0893dd 100644
--- a/pkg/document/json/element.go
+++ b/pkg/document/json/element.go
@@ -20,6 +20,12 @@ import (
 	"github.com/yorkie-team/yorkie/pkg/document/time"
 )
 
+// Container represents Array or Object.
+type Container interface {
+	Element
+	Purge(child Element)
+}
+
 // Element represents JSON element.
 type Element interface {
 	// Marshal returns the JSON encoding of this element.
diff --git a/pkg/document/json/object.go b/pkg/document/json/object.go
index 74615387..6177c47b 100644
--- a/pkg/document/json/object.go
+++ b/pkg/document/json/object.go
@@ -37,6 +37,11 @@ func NewObject(memberNodes *RHTPriorityQueueMap, createdAt *time.Ticket) *Object
 	}
 }
 
+// Purge physically purge child element.
+func (o *Object) Purge(elem Element) {
+	o.memberNodes.purge(elem)
+}
+
 // Set sets the given element of the given key.
 func (o *Object) Set(k string, v Element) {
 	o.memberNodes.Set(k, v)
@@ -67,15 +72,18 @@ func (o *Object) Delete(k string, deletedAt *time.Ticket) Element {
 	return o.memberNodes.Delete(k, deletedAt)
 }
 
-func (o *Object) Descendants(descendants chan Element) {
-	for _, node := range o.memberNodes.AllNodes() {
+func (o *Object) Descendants(callback func(elem Element, parent Container) bool) {
+	for _, node := range o.memberNodes.Nodes() {
+		if callback(node.elem, o) {
+			return
+		}
+
 		switch elem := node.elem.(type) {
 		case *Object:
-			elem.Descendants(descendants)
+			elem.Descendants(callback)
 		case *Array:
-			elem.Descendants(descendants)
+			elem.Descendants(callback)
 		}
-		descendants <- node.elem
 	}
 }
 
@@ -88,7 +96,7 @@ func (o *Object) Marshal() string {
 func (o *Object) DeepCopy() Element {
 	members := NewRHTPriorityQueueMap()
 
-	for _, node := range o.memberNodes.AllNodes() {
+	for _, node := range o.memberNodes.Nodes() {
 		members.Set(node.key, node.elem.DeepCopy())
 	}
 
@@ -128,5 +136,5 @@ func (o *Object) Remove(removedAt *time.Ticket) bool {
 
 // RHTNodes returns the RHTPriorityQueueMap nodes.
 func (o *Object) RHTNodes() []*RHTPQMapNode {
-	return o.memberNodes.AllNodes()
+	return o.memberNodes.Nodes()
 }
diff --git a/pkg/document/json/rga_tree_list.go b/pkg/document/json/rga_tree_list.go
index a621178b..d0a61593 100644
--- a/pkg/document/json/rga_tree_list.go
+++ b/pkg/document/json/rga_tree_list.go
@@ -261,6 +261,19 @@ func (a *RGATreeList) FindPrevCreatedAt(createdAt *time.Ticket) *time.Ticket {
 	return node.elem.CreatedAt()
 }
 
+// purge physically purge child element.
+func (a *RGATreeList) purge(elem Element) {
+	node, ok := a.nodeMapByCreatedAt[elem.CreatedAt().Key()]
+	if !ok {
+		log.Logger.Fatalf(
+			"fail to find the given createdAt: %s",
+			elem.CreatedAt().Key(),
+		)
+	}
+
+	a.release(node)
+}
+
 func (a *RGATreeList) findByCreatedAt(prevCreatedAt *time.Ticket, createdAt *time.Ticket) *RGATreeListNode {
 	node, ok := a.nodeMapByCreatedAt[prevCreatedAt.Key()]
 	if !ok {
@@ -290,7 +303,9 @@ func (a *RGATreeList) release(node *RGATreeListNode) {
 	a.nodeMapByIndex.Delete(node.indexNode)
 	delete(a.nodeMapByCreatedAt, node.elem.CreatedAt().Key())
 
-	a.size--
+	if !node.isRemoved() {
+		a.size--
+	}
 }
 
 func (a *RGATreeList) insertAfter(prev *RGATreeListNode, element Element) {
diff --git a/pkg/document/json/rht.go b/pkg/document/json/rht.go
index aeddb50c..19963291 100644
--- a/pkg/document/json/rht.go
+++ b/pkg/document/json/rht.go
@@ -18,10 +18,11 @@ package json
 
 import (
 	"fmt"
-	"github.com/yorkie-team/yorkie/pkg/document/time"
-	"github.com/yorkie-team/yorkie/pkg/log"
 	"sort"
 	"strings"
+
+	"github.com/yorkie-team/yorkie/pkg/document/time"
+	"github.com/yorkie-team/yorkie/pkg/log"
 )
 
 type RHTNode struct {
@@ -143,9 +144,9 @@ func (rht *RHT) Elements() map[string]string {
 	return members
 }
 
-// AllNodes returns a map of elements because the map easy to use for loop.
+// Nodes returns a map of elements because the map easy to use for loop.
 // TODO If we encounter performance issues, we need to replace this with other solution.
-func (rht *RHT) AllNodes() []*RHTNode {
+func (rht *RHT) Nodes() []*RHTNode {
 	var nodes []*RHTNode
 	for _, node := range rht.nodeMapByKey {
 		nodes = append(nodes, node)
@@ -158,7 +159,7 @@ func (rht *RHT) AllNodes() []*RHTNode {
 func (rht *RHT) DeepCopy() *RHT {
 	instance := NewRHT()
 
-	for _, node := range rht.AllNodes() {
+	for _, node := range rht.Nodes() {
 		instance.Set(node.key, node.val, node.updatedAt)
 	}
 	return instance
diff --git a/pkg/document/json/rht_pq_map.go b/pkg/document/json/rht_pq_map.go
index 428f3bda..b475869d 100644
--- a/pkg/document/json/rht_pq_map.go
+++ b/pkg/document/json/rht_pq_map.go
@@ -18,11 +18,12 @@ package json
 
 import (
 	"fmt"
+	"sort"
+	"strings"
+
 	"github.com/yorkie-team/yorkie/pkg/document/time"
 	"github.com/yorkie-team/yorkie/pkg/log"
 	"github.com/yorkie-team/yorkie/pkg/pq"
-	"sort"
-	"strings"
 )
 
 type RHTPQMapNode struct {
@@ -145,9 +146,9 @@ func (rht *RHTPriorityQueueMap) Elements() map[string]Element {
 	return members
 }
 
-// AllNodes returns a map of elements because the map easy to use for loop.
+// Nodes returns a map of elements because the map easy to use for loop.
 // TODO If we encounter performance issues, we need to replace this with other solution.
-func (rht *RHTPriorityQueueMap) AllNodes() []*RHTPQMapNode {
+func (rht *RHTPriorityQueueMap) Nodes() []*RHTPQMapNode {
 	var nodes []*RHTPQMapNode
 	for _, queue := range rht.nodeQueueMapByKey {
 		for _, value := range queue.Values() {
@@ -158,6 +159,22 @@ func (rht *RHTPriorityQueueMap) AllNodes() []*RHTPQMapNode {
 	return nodes
 }
 
+// purge physically purge child element.
+func (rht *RHTPriorityQueueMap) purge(elem Element) {
+	node, ok := rht.nodeMapByCreatedAt[elem.CreatedAt().Key()]
+	if !ok {
+		log.Logger.Fatalf("fail to find " + elem.CreatedAt().Key())
+	}
+
+	queue, ok := rht.nodeQueueMapByKey[node.key]
+	if !ok {
+		log.Logger.Fatalf("fail to find queue of " + elem.CreatedAt().Key())
+	}
+
+	queue.Release(node)
+	delete(rht.nodeMapByCreatedAt, node.elem.CreatedAt().Key())
+}
+
 // Marshal returns the JSON encoding of this map.
 func (rht *RHTPriorityQueueMap) Marshal() string {
 	members := rht.Elements()
diff --git a/pkg/document/json/root.go b/pkg/document/json/root.go
index c8967ce1..77f30836 100644
--- a/pkg/document/json/root.go
+++ b/pkg/document/json/root.go
@@ -33,22 +33,17 @@ type Root struct {
 
 // NewRoot creates a new instance of Root.
 func NewRoot(root *Object) *Root {
-	elementMap := make(map[string]Element)
 	r := &Root{
-		object:                root,
-		elementMapByCreatedAt: elementMap,
+		elementMapByCreatedAt: make(map[string]Element),
 	}
 
+	r.object = root
 	r.RegisterElement(root)
 
-	descendants := make(chan Element)
-	go func() {
-		root.Descendants(descendants)
-		close(descendants)
-	}()
-	for descendant := range descendants {
-		r.RegisterElement(descendant)
-	}
+	root.Descendants(func(elem Element, parent Container) bool {
+		r.RegisterElement(elem)
+		return false
+	})
 
 	return r
 }
@@ -68,7 +63,49 @@ func (r *Root) RegisterElement(elem Element) {
 	r.elementMapByCreatedAt[elem.CreatedAt().Key()] = elem
 }
 
+// DeregisterElement deregister the given element from hash table.
+func (r *Root) DeregisterElement(elem Element) {
+	delete(r.elementMapByCreatedAt, elem.CreatedAt().Key())
+}
+
 // DeepCopy copies itself deeply.
 func (r *Root) DeepCopy() *Root {
 	return NewRoot(r.object.DeepCopy().(*Object))
 }
+
+// GarbageCollect purge elements that were removed before the given time.
+func (r *Root) GarbageCollect(ticket *time.Ticket) int {
+	count := 0
+
+	r.object.Descendants(func(elem Element, parent Container) bool {
+		shouldGC := elem.RemovedAt() != nil && ticket.After(elem.RemovedAt())
+		if shouldGC {
+			parent.Purge(elem)
+			count += r.garbageCollect(elem)
+		}
+
+		return shouldGC
+	})
+
+	return count
+}
+
+func (r *Root) garbageCollect(elem Element) int {
+	count := 0
+
+	callback := func(elem Element, parent Container) bool {
+		r.DeregisterElement(elem)
+		count++
+		return false
+	}
+
+	callback(elem, nil)
+	switch elem := elem.(type) {
+	case *Object:
+		elem.Descendants(callback)
+	case *Array:
+		elem.Descendants(callback)
+	}
+
+	return count
+}
diff --git a/pkg/pq/priority_queue.go b/pkg/pq/priority_queue.go
index 461d43b6..ec83e78a 100644
--- a/pkg/pq/priority_queue.go
+++ b/pkg/pq/priority_queue.go
@@ -16,7 +16,9 @@
 
 package pq
 
-import "container/heap"
+import (
+	"container/heap"
+)
 
 type PriorityQueue struct {
 	queue *internalQueue
@@ -44,6 +46,19 @@ func (pq *PriorityQueue) Push(value Value) {
 	heap.Push(pq.queue, item)
 }
 
+func (pq *PriorityQueue) Release(value Value) {
+	queue := &internalQueue{}
+	heap.Init(queue)
+
+	for _, item := range *pq.queue {
+		if item.value != value {
+			heap.Push(queue, item)
+		}
+	}
+
+	pq.queue = queue
+}
+
 func (pq *PriorityQueue) Values() []Value {
 	var values []Value
 	for _, item := range *pq.queue {


Test patch:
diff --git a/client/client_test.go b/client/client_test.go
index 095d2d93..40d852b9 100644
--- a/client/client_test.go
+++ b/client/client_test.go
@@ -692,7 +692,7 @@ func syncClientsThenAssertEqual(t *testing.T, pairs []clientAndDocPair) {
 	ctx := context.Background()
 	// Save own changes and get previous changes.
 	for i, pair := range pairs {
-		fmt.Printf("before doc%d: %s\n", i+1, pair.doc.Marshal())
+		fmt.Printf("before d%d: %s\n", i+1, pair.doc.Marshal())
 		err := pair.cli.Sync(ctx)
 		assert.NoError(t, err)
 	}
diff --git a/pkg/document/document_test.go b/pkg/document/document_test.go
index 5a0ab884..75b73d6d 100644
--- a/pkg/document/document_test.go
+++ b/pkg/document/document_test.go
@@ -23,9 +23,12 @@ import (
 
 	"github.com/stretchr/testify/assert"
 
+	"github.com/yorkie-team/yorkie/api/converter"
 	"github.com/yorkie-team/yorkie/pkg/document"
 	"github.com/yorkie-team/yorkie/pkg/document/checkpoint"
 	"github.com/yorkie-team/yorkie/pkg/document/proxy"
+	"github.com/yorkie-team/yorkie/pkg/document/time"
+	"github.com/yorkie-team/yorkie/testhelper"
 )
 
 var (
@@ -100,6 +103,72 @@ func TestDocument(t *testing.T) {
 		assert.Equal(t, expected, doc.Marshal())
 	})
 
+	t.Run("garbage collection test", func(t *testing.T) {
+		doc := document.New("c1", "d1")
+		assert.Equal(t, "{}", doc.Marshal())
+
+		err := doc.Update(func(root *proxy.ObjectProxy) error {
+			root.SetInteger("1", 1)
+			root.SetNewArray("2").AddInteger(1, 2, 3)
+			root.SetInteger("3", 3)
+			return nil
+		}, "sets 1,2,3")
+		assert.NoError(t, err)
+		assert.Equal(t, `{"1":1,"2":[1,2,3],"3":3}`, doc.Marshal())
+
+		err = doc.Update(func(root *proxy.ObjectProxy) error {
+			root.Delete("2")
+			return nil
+		}, "deletes 2")
+		assert.NoError(t, err)
+		assert.Equal(t, `{"1":1,"3":3}`, doc.Marshal())
+
+		assert.Equal(t, 4, doc.GarbageCollect(time.MaxTicket))
+	})
+
+	t.Run("garbage collection test 2", func(t *testing.T) {
+		size := 10_000
+
+		// 01. initial
+		doc := document.New("c1", "d1")
+		fmt.Println("-----Initial")
+		bytes, err := converter.ObjectToBytes(doc.RootObject())
+		assert.NoError(t, err)
+		testhelper.PrintBytesSize(bytes)
+		testhelper.PrintMemStats()
+
+		// 02. 10,000 integers
+		err = doc.Update(func(root *proxy.ObjectProxy) error {
+			root.SetNewArray("1")
+			for i := 0; i < size; i++ {
+				root.GetArray("1").AddInteger(i)
+			}
+
+			return nil
+		}, "sets big array")
+		assert.NoError(t, err)
+
+		// 03. deletes integers
+		err = doc.Update(func(root *proxy.ObjectProxy) error {
+			root.Delete("1")
+			return nil
+		}, "deletes the array")
+		assert.NoError(t, err)
+		fmt.Println("-----Integers")
+		bytes, err = converter.ObjectToBytes(doc.RootObject())
+		assert.NoError(t, err)
+		testhelper.PrintBytesSize(bytes)
+		testhelper.PrintMemStats()
+
+		// 04. after garbage collection
+		assert.Equal(t, size+1, doc.GarbageCollect(time.MaxTicket))
+		fmt.Println("-----After garbage collection")
+		bytes, err = converter.ObjectToBytes(doc.RootObject())
+		assert.NoError(t, err)
+		testhelper.PrintBytesSize(bytes)
+		testhelper.PrintMemStats()
+	})
+
 	t.Run("object test", func(t *testing.T) {
 		doc := document.New("c1", "d1")
 		err := doc.Update(func(root *proxy.ObjectProxy) error {
diff --git a/testhelper/testhelper.go b/testhelper/testhelper.go
index aac075c7..c5007abf 100644
--- a/testhelper/testhelper.go
+++ b/testhelper/testhelper.go
@@ -19,6 +19,7 @@ package testhelper
 import (
 	"fmt"
 	"log"
+	"runtime"
 	"time"
 
 	"github.com/yorkie-team/yorkie/pkg/document/change"
@@ -64,6 +65,35 @@ func TextChangeContext() *change.Context {
 	)
 }
 
+// PrintMemStats prints memory stats.
+func PrintMemStats() {
+	var mem runtime.MemStats
+	runtime.ReadMemStats(&mem)
+
+	fmt.Println("mem.Alloc:", ByteCountIEC(mem.Alloc))
+	fmt.Println("mem.TotalAlloc:", ByteCountIEC(mem.TotalAlloc))
+	fmt.Println("mem.HeapAlloc:", ByteCountIEC(mem.HeapAlloc))
+	fmt.Println("mem.NumGC:", mem.NumGC)
+}
+
+func PrintBytesSize(bytes []byte) {
+	byteSize := len(bytes)
+	fmt.Println("sna.Bytes:", ByteCountIEC(uint64(byteSize)))
+}
+
+func ByteCountIEC(b uint64) string {
+	const unit = 1024
+	if b < unit {
+		return fmt.Sprintf("%d B", b)
+	}
+	div, exp := uint64(unit), 0
+	for n := b / unit; n >= unit; n /= unit {
+		div *= unit
+		exp++
+	}
+	return fmt.Sprintf("%.1f %ciB", float64(b)/float64(div), "KMGTPE"[exp])
+}
+
 // TestYorkie is return Yorkie instance for testing.
 func TestYorkie() *yorkie.Yorkie {
 	y, err := yorkie.New(&yorkie.Config{