Deleting values and running GC doesn't reclaim space

[magik6k]

I was trying to get Badger GC in go-ipfs to reclaim space, but it didn't seem to work, so I've wrote this rather basic test case to see if it works in the simple case of keys being added, then deleted, and GC ran:

https://gist.github.com/magik6k/8c379cc02b443495e4809170fb8803a9

EDIT: gist / results updated as I discovered that I was calling Delete on wrong data...

These are my (reproducible) results:
DiscardRatio=0.5

non-deletable put: 101 MB(101 MB); sst: 0 B; vlog: 101 MB
data put: 3.1 GB(3.1 GB); sst: 0 B; vlog: 3.1 GB
put closed: 3.1 GB(3.1 GB); sst: 20 MB; vlog: 3.1 GB
del-open: 3.1 GB(3.1 GB); sst: 20 MB; vlog: 3.1 GB
after del: 3.2 GB(3.2 GB); sst: 20 MB; vlog: 3.1 GB
gc-step: 3.2 GB(3.2 GB); sst: 20 MB; vlog: 3.1 GB
gc: 3.2 GB(3.2 GB); sst: 20 MB; vlog: 3.1 GB
close-gc: 3.2 GB(3.2 GB); sst: 36 MB; vlog: 3.1 GB // expected ~100-120M

Cases below are wrong because of a bug in my code:

DiscardRatio=0.01

non-deletable put: 101 MB(101 MB); sst: 0 B; vlog: 101 MB //put 100M, looks good
data put: 3.1 GB(3.1 GB); sst: 0 B; vlog: 3.1 GB // put 3G, looks good
put closed: 3.1 GB(3.1 GB); sst: 20 MB; vlog: 3.1 GB // close DB, looks good
del-open: 3.1 GB(3.1 GB); sst: 20 MB; vlog: 3.1 GB // reopen db, looks good
after del: 9.1 GB(9.1 GB); sst: 3.0 GB; vlog: 6.1 GB // delete the 3G keys put before, sst explodes, vlog grows by 3G
gc-step: 9.1 GB(9.1 GB); sst: 3.0 GB; vlog: 6.1 GB // call RunValueLogGC, nothing changes
gc: 9.1 GB(9.1 GB); sst: 3.0 GB; vlog: 6.1 GB // ErrNoRewrite, even with 3 mostly rewritable vlogs
close-gc: 9.2 GB(9.2 GB); sst: 3.0 GB; vlog: 6.1 GB // closing doesn't change anything

DiscardRatio=0.5

non-deletable put: 101 MB(101 MB); sst: 0 B; vlog: 101 MB
data put: 3.1 GB(3.1 GB); sst: 0 B; vlog: 3.1 GB
put closed: 3.1 GB(3.1 GB); sst: 20 MB; vlog: 3.1 GB
del-open: 3.1 GB(3.1 GB); sst: 20 MB; vlog: 3.1 GB
after del: 9.1 GB(9.1 GB); sst: 3.0 GB; vlog: 6.1 GB
gc-step: 8.0 GB(8.0 GB); sst: 3.0 GB; vlog: 5.0 GB
gc-step: 7.0 GB(7.0 GB); sst: 3.0 GB; vlog: 4.0 GB
gc-step: 7.0 GB(7.0 GB); sst: 3.0 GB; vlog: 4.0 GB
gc: 7.0 GB(7.0 GB); sst: 3.0 GB; vlog: 4.0 GB
close-gc: 7.0 GB(7.0 GB); sst: 3.0 GB; vlog: 4.0 GB // definitely more than 100M

DiscardRatio=0.9

non-deletable put: 101 MB(101 MB); sst: 0 B; vlog: 101 MB
data put: 3.1 GB(3.1 GB); sst: 0 B; vlog: 3.1 GB
put closed: 3.1 GB(3.1 GB); sst: 20 MB; vlog: 3.1 GB
del-open: 3.1 GB(3.1 GB); sst: 20 MB; vlog: 3.1 GB
after del: 9.1 GB(9.1 GB); sst: 3.0 GB; vlog: 6.1 GB
gc-step: 8.0 GB(8.0 GB); sst: 3.0 GB; vlog: 5.0 GB
gc-step: 8.0 GB(8.0 GB); sst: 3.0 GB; vlog: 5.0 GB
gc: 8.0 GB(8.0 GB); sst: 3.0 GB; vlog: 5.0 GB
close-gc: 8.1 GB(8.1 GB); sst: 3.0 GB; vlog: 5.0 GB
```</s>

[jarifibrahim]

@magik6k Thanks for reporting this. I ran your test script and it looks like the GC didn't work (even with 0.01 discard ratio). Let me dig deeper and get back.

[jarifibrahim]

@magik6k Looks like we have a bug in the WriteBatch API due to which the GC cannot reclaim space. However, if you inserts entries using the txn API the GC should work. I made the following changes to your script and garbage collection was able to reclaim 2 GB of space.

diff --git a/main_test.go b/main_test.go
index 0d4099b..8759f9b 100644
--- a/main_test.go
+++ b/main_test.go
@@ -13,6 +13,7 @@ import (
 
 	"github.com/dustin/go-humanize"
 	ds "github.com/ipfs/go-datastore"
+	"github.com/stretchr/testify/require"
 
 	"github.com/dgraph-io/badger"
 )
@@ -44,25 +45,29 @@ func TestGc(t *testing.T) {
 
 	r := rand.New(rand.NewSource(555))
 
-	wb := db.NewWriteBatch()
+	txn := db.NewTransaction(true)
 
 	for i := 0; i < preC; i++ { // put non-deletable entries
 		b, err := ioutil.ReadAll(io.LimitReader(r, entryS))
 		if err != nil {
 			t.Fatal(err)
 		}
-		if err := wb.Set(ds.RandomKey().Bytes(), b, 0); err != nil {
+		if err := txn.Set(ds.RandomKey().Bytes(), b); err != nil {
 			t.Fatal(err)
 		}
+		if int64(i)%1000 == 0 {
+			require.NoError(t, txn.Commit())
+			txn = db.NewTransaction(true)
+		}
 	}
 
-	if err := wb.Flush(); err != nil {
+	if err := txn.Commit(); err != nil {
 		t.Fatal(err)
 	}
 
 	pds(t, "non-deletable put")
 
-	wb = db.NewWriteBatch()
+	txn = db.NewTransaction(true)
 	es := make([][]byte, entryC)
 	for i := 0; i < entryC; i++ { // put deletable entries
 		b, err := ioutil.ReadAll(io.LimitReader(r, entryS))
@@ -70,12 +75,19 @@ func TestGc(t *testing.T) {
 			t.Fatal(err)
 		}
 		es[i] = ds.RandomKey().Bytes()
-		if err := wb.Set(es[i], b, 0); err != nil {
+		if err := txn.Set(es[i], b); err != nil {
 			t.Fatal(err)
 		}
+
+		if int64(i)%1000 == 0 {
+			if err := txn.Commit(); err != nil {
+				t.Fatal(err)
+			}
+			txn = db.NewTransaction(true)
+		}
 	}
 
-	if err := wb.Flush(); err != nil {
+	if err := txn.Commit(); err != nil {
 		t.Fatal(err)
 	}
 
@@ -94,13 +106,24 @@ func TestGc(t *testing.T) {
 
 	pds(t, "del-open")
 
-	wb = db.NewWriteBatch()
-	for _, e := range es {
-		if err := wb.Delete(e); err != nil {
+	txn = db.NewTransaction(true)
+	for i, e := range es {
+		if err := txn.Delete(e); err != nil {
 			t.Fatal(err)
 		}
+		if int64(i)%1000 == 0 {
+			if err := txn.Commit(); err != nil {
+				t.Fatal(err)
+			}
+			txn = db.NewTransaction(true)
+		}
+	}
+	if err := txn.Commit(); err != nil {
+		t.Fatal(err)
 	}
-	if err := wb.Flush(); err != nil {
+	db.Close()
+	db, err = badger.Open(opts)
+	if err != nil {
 		t.Fatal(err)
 	}
 

NOTE - It is important that the db is closed and reopened. We perform compaction when the DB is closed. Without compaction the GC wouldn't be able to free up the space. Compaction happens automatically but in this case since the data isn't enough for compaction to be triggered, we force compaction by closing the DB.

This is what I get on running the script above

$ go test -v github.com/jarifibrahim/foo -run TestGc
=== RUN   TestGc
non-deletable put: 101 MB(101 MB); sst: 0 B; vlog: 101 MB
data put: 3.1 GB(3.1 GB); sst: 0 B; vlog: 3.1 GB
put closed: 3.1 GB(3.1 GB); sst: 20 MB; vlog: 3.1 GB
del-open: 3.1 GB(3.1 GB); sst: 20 MB; vlog: 3.1 GB
after del: 3.2 GB(3.2 GB); sst: 17 MB; vlog: 3.1 GB
gc-step: 2.2 GB(2.2 GB); sst: 17 MB; vlog: 2.2 GB
gc-step: 1.1 GB(1.1 GB); sst: 17 MB; vlog: 1.1 GB
gc-step: 1.1 GB(1.1 GB); sst: 17 MB; vlog: 1.1 GB
gc: 1.1 GB(1.1 GB); sst: 17 MB; vlog: 1.1 GB
close-gc: 1.1 GB(1.1 GB); sst: 17 MB; vlog: 1.1 GB
--- PASS: TestGc (38.71s)
PASS


$ du -lh /tmp/badger/*
1.1G	/tmp/badger/000002.vlog
7.6M	/tmp/badger/000003.vlog
17M	/tmp/badger/000006.sst
4.0K	/tmp/badger/MANIFEST

The 00002.vlog files wasn't removed because it might not have enough entries to discard (we have set the discard ratio to 0.5). The other file 00003.vlog was not removed because it is the latest in-use vlog file (it has the head marker). We never remove vlog file with the latest head marker.

[magik6k]

Is there a way to trigger compaction without closing the database?

[jarifibrahim]

Try running Flatten

badger/db.go

Lines 1185 to 1191 in 1fcc96e

	// Flatten can be used to force compactions on the LSM tree so all the tables fall on the same
	// level. This ensures that all the versions of keys are colocated and not split across multiple
	// levels, which is necessary after a restore from backup. During Flatten, live compactions are
	// stopped. Ideally, no writes are going on during Flatten. Otherwise, it would create competition
	// between flattening the tree and new tables being created at level zero.
	func (db *DB) Flatten(workers int) error {

[jarifibrahim]

@magik6k with #778, the script in https://gist.github.com/magik6k/8c379cc02b443495e4809170fb8803a9 would still produce similar results but the values would be removed eventually. The GC would reclaim space after some time.

[linxGnu]

Hello @jarifibrahim

I have the same problem and got disk leak while trying to delete keys/values using batch.

The commit: d98dd68#diff-42ea5667b327bb207485077410d5f499
revert your previous commit and problem still remains.

How about reopen this issue?

[jarifibrahim]

@linxGnu The value log GC isn't supposed to reclaim space immediately. The change in #778 was reverted because we had issues with it.

The issue here isn't with the GC, it's with the Write Batch API. You need not worry about GC. It will eventually clean up the space. There are multiple factors involved when it tries to find a vlog file to clean.

Take a look at the following script. It works perfectly fine https://gist.github.com/jarifibrahim/78621293e68dffbc30be860f3c9df549#file-main_test-go and it's output https://gist.github.com/jarifibrahim/78621293e68dffbc30be860f3c9df549#file-output-txt.

I am not sure if this is an actual bug. I mean the GC did reclaim space. It just didn't do it immediately.

[linxGnu]

@jarifibrahim Thank you very much for your details. I would take a look again and report if I still seeing disk not reclaim when using Write Batch API 👍

[jarifibrahim]

@linxGnu Just to help you understand how GC works --

1. We store Discard Stats which contains how much data can be discarded in each vlog file. The discard stats are built when compactions happen. (You can force compaction by closing and opening the DB)
2. In case the discard stats does not have information about a specific file, we perform sampling on the file and based on the sample we decide if it should be cleaned up.

Value Log GC is supposed to clean up space eventually. There might be cases when GC doesn't clean up the data, but it will be cleaned up eventually.

[ashish314]

Hello @jarifibrahim,

I have a couple of questions regarding BadgerDB's garbage collection and file deletion process:

Does BadgerDB delete files automatically, or do users need to call RunValueLogGC at intervals to delete discarded files after compaction?

Is there any way we can obtain information about which files will be deleted during the process of RunValueLogGC before they are actually deleted? This would be helpful if we want to store this data to a cheaper storage solution for backup or archiving purposes.

I would appreciate any insights or guidance you can provide on these topics. Thank you!

[mangalaman93]

Hi @ashish314,

If you want to take a backup of data in badger, you should use the Backup APIs in badger. You can see more details here https://dgraph.io/docs/badger/get-started/#database-backup/

I am not sure if you need to call RunValueLogGC periodically, it seems to me that you should.

[jarifibrahim]

HI @ashish314!

Does BadgerDB delete files automatically, or do users need to call RunValueLogGC at intervals to delete discarded files after compaction?

Badger will perform cleanup automatically. This means it will delete old data and files automatically.

Is there any way we can obtain information about which files will be deleted during the process of RunValueLogGC before they are actually deleted? This would be helpful if we want to store this data to a cheaper storage solution for backup or archiving purposes.

We don't expose this information but you shouldn't need to worry about this data. GC removes only deleted/expired/duplicate/stale data. All the useful data is kept as it is.

You can take periodic backups of your data if you'd like using the backup API.