Removed /v4 suffix from module path and all internal imports.
Go module is now github.com/luxfi/zapdb (no major version suffix).
Import as: import "github.com/luxfi/zapdb"
No code changes — only module path and import rewrite.
- Rename module from github.com/dgraph-io/badger/v4 to github.com/luxfi/zapdb/v4
- Update all internal imports to use new module path
- Preserve all ZAP enhancements from badger fork
**Description**
Correct an incorrect comment on the value size in skl.node.
Background: the PR https://github.com/dgraph-io/badger/pull/880 changed
the value size from uint16 to uint32, but the did not update the
comment.
**Checklist**
- [X] Code compiles correctly and linting passes locally
- [X] Tests added for new functionality, or regression tests for bug
fixes added as applicable
Signed-off-by: Benjamin Wang <benjamin.ahrtr@gmail.com>
This PR significantly improves Badger's disk usage behavior.
Breaking: This PR increases the magic version from 7 to 8. So, no older Badger directories would work with this change.
With this PR, we no longer use value log as write-ahead log. Instead, each MemTable has its own WAL. Value logs now only write values which are greater than ValueThreshold, while MemTable WAL only writes smaller values and value pointers.
On a crash and restart, the MemTable WALs are replayed to apply updates to Skiplist. When MemTables are flushed to L0, the corresponding WALs are deleted.
This PR makes big changes to how value log GC works:
- Discard stats are now stored in a separate file, instead of within the LSM tree.
- GC only picks up value logs based off discard stats.
- GC no longer does sampling, it uses discard stats to inform when a value log needs to be GCed.
- Value log would now no longer grow indefinitely, because of the shift to MemTable WAL.
- Removed the `badger gc` tool.
- Value Log Head pointer tracking is removed.
- Only the last value log file is replayed on every start, and truncated as necessary.
This PR also makes a bunch of other changes:
- Removes ValueLogLoadingMode (always uses mmap now).
- Removes TableLoadingMode (always uses mmap now).
- Removes Truncate option.
- Removes KeepL0InMemory option.
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)
```
* Have block based on size.
* Implementation of binary search inside block.
* Support for checksum at block level
* Update table benchmarks
* Support for max value size of uint32
As explained in https://discuss.dgraph.io/t/go-modules-on-badger-and-dgraph/4662,
Go Modules force an import path rename that currently breaks support for most other
dependency management systems, including dep.
It seems an effort is being made to add support for this import path renaming by
patching the go tool itself, but until the community hasn't settled and Go Modules
is an easier option to adopt, we are simply not supporting them.
For those willing to use badger v2 from Go modules it is still very simple, you might
notice that once you set the version to be v2.0.0 a +incompatible will be added to it
indicating the dependency has not opted-in into Go Modules. That's normal and not to
be a concern.
Keep ValueThreshold to below uint16, because that value size limit is
baked into the header of the key-value pairs in SSTable. Keeps most of
the simplifications of the previous change by Andy Kimball, while
bringing the uint16 limits back. In fact, this change enforces that
limit by returning an explicit error for invalid ValueThreshold.
Currently, inline skiplist values are limited to a length of 16 bits.
This commit increases that limit to 32 bits. It does this by making
node.value a uint64, and then packing the value offset and size into
it, as two uint32 values.
Because node.value is accessed with atomic.LoadUint64, it must be
aligned on a 64-bit boundary. This is guaranteed by Arena.putNode,
which is changed to always align on a 64-bit boundary rather than
on a pointer boundary (which would incorrectly align on 32-bit
boundary on a 32-bit machine).
This change fixes segmentation faults on Arm v7.
From https://golang.org/pkg/sync/atomic/:
> On both ARM and x86-32, it is the caller's responsibility to arrange
for 64-bit alignment of 64-bit words accessed atomically. The first word
in a variable or in an allocated struct, array, or slice can be relied
upon to be 64-bit aligned.
Had to modify a couple of tests to get them to pass.
Fixes#311.
* Add test for value log replay, iteration
* Fix seek during reverse iteration
* Throw error if user tries to get empty key.
* If user tries to seek for empty key, then rewind
LSM Get checks in all levels if key is not found in memtable or level 0 to find latest version.
Fix parseItem. Breakage caused by how we store key in KVItem.
Fix storing/reading readTs from badger head
- Move all errors into a new file: errors.go.
- Remove all public APIs from kv.go. All the public APIs now flow through transactions.
- Remove SetIfAbsent, CompareAndSet, etc. They should all be done via transactions now.
- Remove CAS counter from everywhere.
- Simplify serialization/deserialization of various structs.
- Move them into new structs.go file (currently only contains value.go structs).
- Logic to handle transaction boundaries when replaying value log.
- Enable versioning in Badger.
- Implement SSI (serializable snapshot isolation) based transactions, which can
be run concurrently, based on Yabandeh's paper: A critique of snapshot isolation
(with modifications). Using a map of committed rows -> timestamp to detect
conflicts.
What works:
- Transactions: Concurrency, Conflict detection, Read snapshots, Versioning, etc.
- Get, Set, Commit
- Iteration within transactions.
- All the transaction logic works. The effect on other components needs to be done.
[WIP]
- The replay logic needs to be updated to understand txn boundaries and init
readTs at start.
- Existing APIs need to be removed.
* Allocate nodes from the arena.
The skiplist allocates keys and values from the arena, but not nodes.
This change begins allocating nodes from the arena. Links between
nodes at the same level are now offsets into the arena rather than
pointers. The "tower" of links is allocated as extra bytes appended
to the end of the node rather than a separate array.
Together, these changes significantly speed up skiplist writes and
reads. It also reduces overall memory usage (by using next offsets
rather than next pointers), as well as GC pressure (nodes do not
use pointers to reference one another).
* Allocate full tower in node struct.
The current code allocates the first tower entry in the node struct
and then allocates additional entries beyond the end of the node.
This change instead allocates all the tower entries as part of the
node struct, and then allocates only a subset of those entries in
the arena. This makes the code slightly simpler (no unsafeTower).
The skiplist benchmark was using the global random number generator,
which is guarded by a mutex. This causes contention on multi-core
machines and skews the benchmark results in a material way. Instead,
use a separate random number generator per benchmark goroutine.
Update the README results.
We ended up implementing it with an atomic variable.
!badger!head is used to store a sufficiently large CAS value that,
after replaying the value log, it is accurately greater than or equal
to the previously used CAS values.
Refactor compaction logic to be in-line with how RocksDB does things.
This refactoring now allows multiple compactions to happen
simultaneously, even at the same level; ensuring that the ranges being
compacted are not overlapping.
We no longer ask for verbosity of output, because all logging has now
been switched over to trace package. We use trace.Trace for compactions,
and trace.EventLog for KV and ValueLog.
The following is a log of all the individual commits.
commit 746c5118a3463483ccb41126d34a7bf35a19c686
Author: Manish R Jain <manish@dgraph.io>
Date: Tue Jun 6 15:43:07 2017 +1000
Address comments
commit 3957d6b5d2b39b93fcd901b45ae09c5d2d04752c
Author: Manish R Jain <manish@dgraph.io>
Date: Tue Jun 6 15:29:01 2017 +1000
Keep more events per compaction
commit e79c87f0502a6bd2ad0ba48c162d47a71e05e9e3
Author: Manish R Jain <manish@dgraph.io>
Date: Tue Jun 6 15:22:11 2017 +1000
Remove y.Printf entirely, along with verbose mode. All logging is done via event log and tracing.
commit b0452d8c1bdd511a7bb088489637a7da035acfaa
Author: Manish R Jain <manish@dgraph.io>
Date: Tue Jun 6 15:04:47 2017 +1000
Move compaction logs entirely to tracer
commit 28bb7cfeec1fbf59301428845cb9aa14d15cb94e
Author: Manish R Jain <manish@dgraph.io>
Date: Tue Jun 6 04:53:26 2017 +0000
Use tracers for each compaction.
commit 71462ceaa433b9d96bab267101f4df560afa7ef5
Author: Manish R Jain <manish@dgraph.io>
Date: Tue Jun 6 11:08:17 2017 +1000
Switch compactions to trace.Trace
commit c982b4ec81710b7ab1cbc389800a379a59ceb92b
Author: Manish R Jain <manish@dgraph.io>
Date: Mon Jun 5 09:58:52 2017 +0000
Move stuff to elog
commit f1883fc5594e979803cb4b9639d20bb698ad2fae
Author: Manish R Jain <manish@dgraph.io>
Date: Fri Jun 2 19:31:41 2017 +1000
Move compaction logs to event log
commit e86865802929e6fc996fb04f3bb8a9995a6b85fe
Author: Manish R Jain <manish@dgraph.io>
Date: Fri Jun 2 16:21:12 2017 +1000
Double check in compareandadd if we really need a compactino.
commit a4cf25515249188c5a16b60648b909a2cc61629c
Author: Manish R Jain <manish@dgraph.io>
Date: Fri Jun 2 16:09:09 2017 +1000
Try other levels if can't run compaction.
commit 3f34dca250f612557d8e17337bf5efec73c4214f
Author: Manish R Jain <manish@dgraph.io>
Date: Thu Jun 1 18:40:38 2017 +1000
Keep track of tables being currently compacted.
commit e9c895a64a7e942aef53300b2f605bfd91c859b9
Author: Manish R Jain <manish@dgraph.io>
Date: Thu Jun 1 18:23:22 2017 +1000
Run 3 compactors simultaneously
commit 9e3dfc101ac9dfb644b36d13a026062d178effe5
Author: Manish R Jain <manish@dgraph.io>
Date: Thu Jun 1 13:52:53 2017 +1000
Kinda works with compaction using key ranges to determine overlap.
commit c767a55ab9b30c55c0eda10e6606460bf5bac317
Author: Manish R Jain <manish@dgraph.io>
Date: Wed May 31 19:47:09 2017 +1000
Allow multiple compactions to happen concurrently.
Hanzo AI