luxfi/zapdb

Fork 0

mirror of https://github.com/luxfi/zapdb.git synced 2026-10-30 15:12:20 +00:00

Files

T

History

c2686b3752 Add missing commits to release/v2.0 branch (#1245 )

* Cast sz to uint32 to fix compilation on 32 bit (#1175)

`env GOOS=linux GOARCH=arm GOARM=7 go build` no longer fails with overflow.

Similar to commit c7b7ca38c4.

Signed-off-by: Christian Stewart <[email protected]>
(cherry picked from commit 04b944f813)

* Fix commit sha for WithInMemory in CHANGELOG. (#1172)

(cherry picked from commit d4d3b81eca)

* Fix windows build (#1177)

Fix windows build and some deepsource warnings

(cherry picked from commit 4235768d3d)

* Fix checkOverlap in compaction (#1166)

The overlap check in compaction would keep additional keys in case
the levels under compaction had overlap amongst themselves.
This commit fixes it.

This commit also fixes the `numVersionsToKeep` check. Without this
commit, we would end up keeping `2` versions of a key even when the
number of versions to keep was set to `1`. See
`level 0 to level 1 with lower overlap` test.

Fixes https://github.com/dgraph-io/badger/issues/1053

The following test fails on master but works with this commit
```go
func TestCompaction(t *testing.T) {
	t.Run("level 0 to level 1", func(t *testing.T) {
		dir, err := ioutil.TempDir("", "badger-test")
		require.NoError(t, err)
		defer removeDir(dir)

		// Disable compactions and keep single version of each key.
		opt := DefaultOptions(dir).WithNumCompactors(0).WithNumVersionsToKeep(1)
		db, err := OpenManaged(opt)
		require.NoError(t, err)

		l0 := []keyValVersion{{"foo", "bar", 3}, {"fooz", "baz", 1}}
		l01 := []keyValVersion{{"foo", "bar", 2}}
		l1 := []keyValVersion{{"foo", "bar", 1}}
		// Level 0 has table l0 and l01.
		createAndOpen(db, l0, 0)
		createAndOpen(db, l01, 0)
		// Level 1 has table l1.
		createAndOpen(db, l1, 1)

		// Set a high discard timestamp so that all the keys are below the discard timestamp.
		db.SetDiscardTs(10)

		getAllAndCheck(t, db, []keyValVersion{
			{"foo", "bar", 3}, {"foo", "bar", 2}, {"foo", "bar", 1}, {"fooz", "baz", 1},
		})
		cdef := compactDef{
			thisLevel: db.lc.levels[0],
			nextLevel: db.lc.levels[1],
			top:       db.lc.levels[0].tables,
			bot:       db.lc.levels[1].tables,
		}
		require.NoError(t, db.lc.runCompactDef(0, cdef))
		// foo version 2 should be dropped after compaction.
		getAllAndCheck(t, db, []keyValVersion{{"foo", "bar", 3}, {"fooz", "baz", 1}})
	})
}
```

(cherry picked from commit d930b60174)

* Remove the 'this entry should've caught' log from value.go (#1170)

Fixes - https://github.com/dgraph-io/badger/issues/1031
(There wasn't a bug to fix. The log statement shouldn't have been there)

This PR removes the warning message `WARNING: This entry should have
been caught.`. The warning message assumed that we will always find the
**newest key if two keys have the same version** This assumption is
valid in case of a normal key but it's **NOT TRUE** in case of
**move keys**.

Here's how we can end up fetching the older version of a move key if
two move keys have the same version.

```
It might be possible that the entry read from LSM Tree points to an
older vlog file. This can happen in the following situation. Assume DB
is opened with numberOfVersionsToKeep=1

Now, if we have ONLY one key in the system "FOO" which has been updated
3 times and the same key has been garbage collected 3 times, we'll have
3 versions of the movekey for the same key "FOO".
NOTE: moveKeyi is the moveKey with version i
Assume we have 3 move keys in L0.
- moveKey1 (points to vlog file 10),
- moveKey2 (points to vlog file 14) and
- moveKey3 (points to vlog file 15).

Also, assume there is another move key "moveKey1" (points to vlog
file 6) (this is also a move Key for key "FOO" ) on upper levels (let's
say level 3). The move key "moveKey1" on level 0 was inserted because
vlog file 6 was GCed.

Here's what the arrangement looks like
L0 => (moveKey1 => vlog10), (moveKey2 => vlog14), (moveKey3 => vlog15)
L1 => ....
L2 => ....
L3 => (moveKey1 => vlog6)

When L0 compaction runs, it keeps only moveKey3 because the number of
versions to keep is set to 1. (we've dropped moveKey1's latest version)

The new arrangement of keys is
L0 => ....
L1 => (moveKey3 => vlog15)
L2 => ....
L3 => (moveKey1 => vlog6)

Now if we try to GC vlog file 10, the entry read from vlog file will
point to vlog10 but the entry read from LSM Tree will point to vlog6.
The move key read from LSM tree will point to vlog6 because we've asked
for version 1 of the move key.

This might seem like an issue but it's not really an issue because the
user has set the number of versions to keep to 1 and the latest version
of moveKey points to the correct vlog file and offset. The stale move
key on L3 will be eventually dropped by compaction because there is a
newer version in the upper levels.
```

(cherry picked from commit 9b82bb4077)

* Avoid sync in inmemory mode (#1190)

This makes db.Sync() no-op when badger is running in in-memory mode.
The previous code would unnecessarily load up an atomic and
acquire locks.

(cherry picked from commit d007d96e8a)

* Use fastRand instead of locked-rand in skiplist (#1173)

The math/rand package (https://golang.org/src/math/rand/rand.go) uses
a global lock to allow concurrent access to the rand object.

The PR replaces `math.Rand` with `ristretto/z.FastRand()`. `FastRand`
is much faster than `math.Rand` and `rand.New(..)` generators.

The change improves concurrent writes to skiplist by ~30%
```go
func BenchmarkWrite(b *testing.B) {
	value := newValue(123)
	l := NewSkiplist(int64((b.N + 1) * MaxNodeSize))
	defer l.DecrRef()
	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		rng := rand.New(rand.NewSource(time.Now().UnixNano()))
		for pb.Next() {
			l.Put(randomKey(rng), y.ValueStruct{Value: value, Meta: 0, UserMeta: 0})
		}
	})
}
```
```
name      old time/op  new time/op  delta
Write-16   657ns ± 3%   441ns ± 1%  -32.94%  (p=0.000 n=9+10)
```

(cherry picked from commit 6ade9fc5c2)

* Add Jaegar to list of projects (#1192)


(cherry picked from commit 8577ab566b)

* Run all tests on CI (#1189)

This could possibly be a bug in `go test` command
https://github.com/golang/go/issues/36527 .

The `go test` command would skip tests in sub-packages if
the top-level package has a `custom flag` defined and the
sub-packages don't define it.

Issue https://github.com/golang/go/issues/36527#issue-548887632
has an example of this.

This PR also removes the code from the test that would unnecessary
start a web server. I see two problems here
1. An unnecessary web server running.
2. We cannot run multiple tests are the same time since the second
    run of the test would try to start a web server and
    crash saying `port already in use`.

(cherry picked from commit dd7888efdd)

* Improve write stalling on level 0 and 1

We don't need to stall writes if Level 1 does not have enough space.
Level 1 is stored on the disk and it should be okay to have more
number of tables (more size) on Level 1 than the `max level 1 size`.
These tables will eventually be compacted to lower levels.

This commit changes the following
- We no longer stall writes if L1 doesn't have enough space.
- We stall writes on level 0 only if `KeepL0InMemory` is true.
- Upper levels (L0, L1, etc) get priority in compaction (previously,
    level with higher priority score would get preference)

(cherry picked from commit 22bd329d25)

* Update ristretto to version  8f368f2 (#1195)

This commit pulls following changes from ristretto
```
git log c1f00be0418e...8f368f2 --oneline
```
```

8f368f2 (HEAD -> master) Fix DeepSource warnings
adb35f0 delete item immediately 
fce5e91 Support nil *Cache values in Clear and Close
4e224f9 Add .travis.yml 
8350826 Fix the way metrics are handled for deletions
99d1bbb (tag: v0.0.1) default to 128bit hashing for collision checks
1eea1b1 atomic Get-Delete operation for eviction
8d6a8a7 add cache test for identifying MaxCost overflows
ae09250 use the custom KeyToHash function if one is set
1dd5a4d #19 Fixes memory leak due to Oct 1st regression in processItems
```

(cherry picked from commit 0cef58737f)

* Support disabling the cache completely. (#1183) (#1185)

The cache can be disabled by setting `opt.MaxCacheSize=0`

(cherry picked from commit fae7479694)

* Fix L0/L1 stall test (#1201)

The test `TestL0Stall` and `TestL1Stall` would never fail
because of errors in the manifest file. This commit fixes it.

(cherry picked from commit 07f48fa3ee)

* Disable compression and set ZSTD Compression Level to 1 (#1191)

This PR
- Disables compression. By default, badger does not use any compression.
- Set default ZSTD compression level to 1
    Level 15 is very slow for any practical use of badger.

```
no_compression-16              10	 502848865 ns/op	 165.46 MB/s
zstd_compression/level_1-16     7	 739037966 ns/op	 112.58 MB/s
zstd_compression/level_3-16     7	 756950250 ns/op	 109.91 MB/s
zstd_compression/level_15-16    1	11135686219 ns/op	   7.47 MB/s
```

(cherry picked from commit d7dcc762d3)

* Add support for caching bloomfilters (#1204)

This PR adds support for caching bloom filters in ristretto.
The bloom filters and blocks are removed from the cache 
when the table is deleted.

(cherry picked from commit e7bd7d3839)

* Rework concurrency semantics of valueLog.maxFid (#1184) (#1187)

Move all access to `valueLog.maxFid` under `valueLog.filesLock`, while
all mutations happen either with writes stopped or sequentially under
valueLog.write.

Fixes a concurrency issue in `valueLog.Read` where the maxFid variable
and the `writableLogOffset` variable could point to two different log files.

(cherry picked from commit a1fb718648)

* Change else-if statements to idiomatic switch statements. (#1207)



(cherry picked from commit fe42d6af3a)

* Fix flaky TestPageBufferReader2 test (#1210)

Fixes https://github.com/dgraph-io/badger/issues/1197

The `TestPageBufferReader2` test would fail often because of an
`off-by-1` issue. The problem can be reproduced by setting `randOffset`
to the biggest number that randInt31n may return statically like:

```
    //randOffset := int(rand.Int31n(int32(b.length)))
    randOffset := int(int32(b.length-1))
```

This makes the problem reliably reproducible as the offset is now
pointing at EOF.

Thus changing the line to this should hopefully solve the problem:
`randOffset := int(rand.Int31n(int32(b.length-1

(cherry picked from commit 134fccb154)

* Replace t.Fatal with require.NoError in tests (#1213)

We are using the following pattern in tests that can be
replaced with `require.NoError(t, err)`.
```go
if err != nil {
    t.Fatal(err)
}
```

(cherry picked from commit 32e9cc40b6)

* Add missing package to README for badger.NewEntry (#1223)


(cherry picked from commit 7fb88f4c1c)

* Remove ExampleDB_Subscribe Test (#1214)

The test ExampleDB_Subscribe doesn't run reliably on appveyor.
This commit removes it.

(cherry picked from commit d704ffef18)

* Fix int overflow for 32bit (#1216)

- Fix tests for 32 bit systems
- Enable 32-bit builds on Travis

(cherry picked from commit 5cc3caede8)

* Update CHANGELOG for Badger 2.0.2 release. (#1230)

Co-authored-by: Ibrahim Jarif <[email protected]>
(cherry picked from commit 4de1f11d13)

* Fix changelog for v2.0.2

(cherry picked from commit a795c2dbeb093ed8b31badc39bb45d8e7ebb9b36)

Co-authored-by: Christian Stewart <[email protected]>
Co-authored-by: Leyla Galatin <[email protected]>
Co-authored-by: Damien Tournoud <[email protected]>
Co-authored-by: Martin Martinez Rivera <[email protected]>
Co-authored-by: Dieter Plaetinck <[email protected]>
Co-authored-by: Apoorv Vardhan <[email protected]>

2020-03-06 13:41:11 +05:30

arena.go

Update go.mod to v2 and add v2 import paths. (#1102 )

2019-10-25 17:45:10 -07:00

README.md

Removing support for Go Modules

2019-06-25 10:52:36 -07:00

skl_test.go

Add missing commits to release/v2.0 branch (#1245 )

2020-03-06 13:41:11 +05:30

skl.go

Add missing commits to release/v2.0 branch (#1245 )

2020-03-06 13:41:11 +05:30

README.md

This is much better than skiplist and slist.

BenchmarkReadWrite/frac_0-8         	 3000000	       537 ns/op
BenchmarkReadWrite/frac_1-8         	 3000000	       503 ns/op
BenchmarkReadWrite/frac_2-8         	 3000000	       492 ns/op
BenchmarkReadWrite/frac_3-8         	 3000000	       475 ns/op
BenchmarkReadWrite/frac_4-8         	 3000000	       440 ns/op
BenchmarkReadWrite/frac_5-8         	 5000000	       442 ns/op
BenchmarkReadWrite/frac_6-8         	 5000000	       380 ns/op
BenchmarkReadWrite/frac_7-8         	 5000000	       338 ns/op
BenchmarkReadWrite/frac_8-8         	 5000000	       294 ns/op
BenchmarkReadWrite/frac_9-8         	10000000	       268 ns/op
BenchmarkReadWrite/frac_10-8        	100000000	        26.3 ns/op

And even better than a simple map with read-write lock:

BenchmarkReadWriteMap/frac_0-8         	 2000000	       774 ns/op
BenchmarkReadWriteMap/frac_1-8         	 2000000	       647 ns/op
BenchmarkReadWriteMap/frac_2-8         	 3000000	       605 ns/op
BenchmarkReadWriteMap/frac_3-8         	 3000000	       603 ns/op
BenchmarkReadWriteMap/frac_4-8         	 3000000	       556 ns/op
BenchmarkReadWriteMap/frac_5-8         	 3000000	       472 ns/op
BenchmarkReadWriteMap/frac_6-8         	 3000000	       476 ns/op
BenchmarkReadWriteMap/frac_7-8         	 3000000	       457 ns/op
BenchmarkReadWriteMap/frac_8-8         	 5000000	       444 ns/op
BenchmarkReadWriteMap/frac_9-8         	 5000000	       361 ns/op
BenchmarkReadWriteMap/frac_10-8        	10000000	       212 ns/op

Node Pooling

Command used

rm -Rf tmp && /usr/bin/time -l ./populate -keys_mil 10

For pprof results, we run without using /usr/bin/time. There are four runs below.

Results seem to vary quite a bit between runs.

Before node pooling

1311.53MB of 1338.69MB total (97.97%)
Dropped 30 nodes (cum <= 6.69MB)
Showing top 10 nodes out of 37 (cum >= 12.50MB)
      flat  flat%   sum%        cum   cum%
  523.04MB 39.07% 39.07%   523.04MB 39.07%  github.com/dgraph-io/badger/skl.(*Skiplist).Put
  184.51MB 13.78% 52.85%   184.51MB 13.78%  runtime.stringtoslicebyte
  166.01MB 12.40% 65.25%   689.04MB 51.47%  github.com/dgraph-io/badger/mem.(*Table).Put
     165MB 12.33% 77.58%      165MB 12.33%  runtime.convT2E
  116.92MB  8.73% 86.31%   116.92MB  8.73%  bytes.makeSlice
   62.50MB  4.67% 90.98%    62.50MB  4.67%  main.newValue
   34.50MB  2.58% 93.56%    34.50MB  2.58%  github.com/dgraph-io/badger/table.(*BlockIterator).parseKV
   25.50MB  1.90% 95.46%   100.06MB  7.47%  github.com/dgraph-io/badger/y.(*MergeIterator).Next
   21.06MB  1.57% 97.04%    21.06MB  1.57%  github.com/dgraph-io/badger/table.(*Table).read
   12.50MB  0.93% 97.97%    12.50MB  0.93%  github.com/dgraph-io/badger/table.header.Encode

      128.31 real       329.37 user        17.11 sys
3355660288  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
   2203080  page reclaims
       764  page faults
         0  swaps
       275  block input operations
        76  block output operations
         0  messages sent
         0  messages received
         0  signals received
     49173  voluntary context switches
    599922  involuntary context switches

After node pooling

1963.13MB of 2026.09MB total (96.89%)
Dropped 29 nodes (cum <= 10.13MB)
Showing top 10 nodes out of 41 (cum >= 185.62MB)
      flat  flat%   sum%        cum   cum%
  658.05MB 32.48% 32.48%   658.05MB 32.48%  github.com/dgraph-io/badger/skl.glob..func1
  297.51MB 14.68% 47.16%   297.51MB 14.68%  runtime.convT2E
  257.51MB 12.71% 59.87%   257.51MB 12.71%  runtime.stringtoslicebyte
  249.01MB 12.29% 72.16%  1007.06MB 49.70%  github.com/dgraph-io/badger/mem.(*Table).Put
  142.43MB  7.03% 79.19%   142.43MB  7.03%  bytes.makeSlice
     100MB  4.94% 84.13%   758.05MB 37.41%  github.com/dgraph-io/badger/skl.newNode
   99.50MB  4.91% 89.04%    99.50MB  4.91%  main.newValue
      75MB  3.70% 92.74%       75MB  3.70%  github.com/dgraph-io/badger/table.(*BlockIterator).parseKV
   44.62MB  2.20% 94.94%    44.62MB  2.20%  github.com/dgraph-io/badger/table.(*Table).read
   39.50MB  1.95% 96.89%   185.62MB  9.16%  github.com/dgraph-io/badger/y.(*MergeIterator).Next

      135.58 real       374.29 user        17.65 sys
3740614656  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
   2276566  page reclaims
       770  page faults
         0  swaps
       128  block input operations
        90  block output operations
         0  messages sent
         0  messages received
         0  signals received
     46434  voluntary context switches
    597049  involuntary context switches