README
¶
Badger 
An embeddable, persistent, simple and fast key-value (KV) store, written natively in Go.
About
Badger is written out of frustration with existing KV stores which are either natively written in Go and slow, or fast but require usage of Cgo. Badger aims to provide an equal or better speed compared to industry leading KV stores (like RocksDB), while maintaining the entire code base in Go natively.
You can read more about Badger in our blog post.
Installation and Usage
go get -v github.com/dgraph-io/badger
If you want to run tests, also get testing dependencies by passing in -t flag.
go get -t -v github.com/dgraph-io/badger
From here, follow docs for usage.
Design Goals
Badger has these design goals in mind:
- Write it natively in Go.
- Use latest research to build the fastest KV store for data sets spanning terabytes.
- Keep it simple, stupid. No support for transactions, versioning or snapshots -- anything that can be done outside of the store should be done outside.
- Optimize for SSDs (more below).
Non-Goals
- Try to be a database.
Video Tutorials
Users
Badger is currently being used by Dgraph.
Design
Badger is based on WiscKey paper by University of Wisconsin, Madison.
In simplest terms, keys are stored in LSM trees along with pointers to values, which would be stored in write-ahead log files, aka value logs. Keys would typically be kept in RAM, values would be served directly off SSD.
Optimizations for SSD
SSDs are best at doing serial writes (like HDD) and random reads (unlike HDD). Each write reduces the lifecycle of an SSD, so Badger aims to reduce the write amplification of a typical LSM tree.
It achieves this by separating the keys from values. Keys tend to be smaller in size and are stored in the LSM tree. Values (which tend to be larger in size) are stored in value logs, which also double as write ahead logs for fault tolerance.
Only a pointer to the value is stored along with the key, which significantly reduces the size of each KV pair in LSM tree. This allows storing lot more KV pairs per table. For e.g., a table of size 64MB can store 2 million KV pairs assuming an average key size of 16 bytes, and a value pointer of 16 bytes (with prefix diffing in Badger, the average key sizes stored in a table would be lower). Thus, lesser compactions are required to achieve stability for the LSM tree, which results in fewer writes (all writes being serial).
Nature of LSM trees
Because only keys (and value pointers) are stored in LSM tree, Badger generates much smaller LSM trees. Even for huge datasets, these smaller trees can fit nicely in RAM allowing for lot quicker accesses to and iteration through keys. For random gets, keys can be quickly looked up from within RAM, giving access to the value pointer. Then only a single pointed read from SSD (random read) is done to retrieve value. This improves random get performance significantly compared to traditional LSM tree design used by other KV stores.
Comparisons
| Feature | Badger | RocksDB | BoltDB |
|---|---|---|---|
| Design | LSM tree with value log | LSM tree only | B+ tree |
| High RW Performance | Yes | Yes | No |
| Designed for SSDs | Yes (with latest research 1) | Not specifically 2 | No |
| Embeddable | Yes | Yes | Yes |
| Sorted KV access | Yes | Yes | Yes |
| Go Native (no Cgo) | Yes | No | Yes |
| Transactions | No (but provides compare and set operations) | Yes (but non-ACID) | Yes, ACID |
| Snapshots | No | Yes | Yes |
1 Badger is based on a paper called WiscKey by University of Wisconsin, Madison, which saw big wins with separating values from keys, significantly reducing the write amplification compared to a typical LSM tree.
2 RocksDB is an SSD optimized version of LevelDB, which was designed specifically for rotating disks. As such RocksDB's design isn't aimed at SSDs.
Crash Consistency
Badger is crash resistent. Any update which was applied successfully before a crash, would be available after the crash. Badger achieves this via its value log.
Badger's value log is a write-ahead log (WAL). Every update to Badger is written to this log first, before being applied to the LSM tree. Badger maintains a monotonically increasing pointer (head) in the LSM tree, pointing to the last update offset in the value log. As and when LSM table is persisted, the head gets persisted along with. Thus, the head always points to the latest persisted offset in the value log. Every time Badger opens the directory, it would first replay the updates after the head in order, bringing the updates back into the LSM tree; before it allows any reads or writes. This technique ensures data persistence in face of crashes.
Furthermore, Badger can be run with SyncWrites option, which would open the WAL with O_DSYNC flag, hence syncing the writes to disk on every write.
Frequently Asked Questions
- My writes are really slow. Why?
You're probably doing writes serially, using Set. To get the best write performance, use BatchSet, and call it
concurrently from multiple goroutines.
- I don't see any disk write. Why?
If you're using Badger with SyncWrites=false, then your writes might not be written to value log
and won't get synced to disk immediately. Writes to LSM tree are done inmemory first, before they
get compacted to disk. The compaction would only happen once MaxTableSize has been reached. So, if
you're doing a few writes and then checking, you might not see anything on disk. Once you Close
the store, you'll see these writes on disk.
Documentation
¶
Overview ¶
Package badger implements an embeddable, simple and fast key-value store, written natively in Go. It is designed to be highly performant for both reads and writes simultaneously. Badger uses LSM tree, along with a value log, to separate keys from values, hence reducing both write amplification and the size of the LSM tree. This allows LSM tree to be served entirely from RAM, while the values are served from SSD. As values get larger, this results in increasingly faster Set() and Get() performance than top of the line KV stores in market today.
Example ¶
package main
import (
"fmt"
"io/ioutil"
"github.com/dgraph-io/badger"
)
func main() {
opt := badger.DefaultOptions
dir, _ := ioutil.TempDir("/tmp", "badger")
opt.Dir = dir
opt.ValueDir = dir
kv, _ := badger.NewKV(&opt)
key := []byte("hello")
kv.Set(key, []byte("world"))
fmt.Printf("SET %s world\n", key)
var item badger.KVItem
if err := kv.Get(key, &item); err != nil {
fmt.Printf("Error while getting key: %q", key)
}
fmt.Printf("GET %s %s\n", key, item.Value())
if err := kv.CompareAndSet(key, []byte("venus"), 100); err != nil {
fmt.Println("CAS counter mismatch")
} else {
if err = kv.Get(key, &item); err != nil {
fmt.Printf("Error while getting key: %q", key)
}
fmt.Printf("Set to %s\n", item.Value())
}
if err := kv.CompareAndSet(key, []byte("mars"), item.Counter()); err == nil {
fmt.Println("Set to mars")
} else {
fmt.Printf("Unsuccessful write. Got error: %v\n", err)
}
}
Output: SET hello world GET hello world CAS counter mismatch Set to mars
Index ¶
- Constants
- Variables
- type Entry
- type Iterator
- type IteratorOptions
- type KV
- func (s *KV) BatchSet(entries []*Entry) error
- func (s *KV) BatchSetAsync(entries []*Entry, f func(error))
- func (s *KV) Close() (err error)
- func (s *KV) CompareAndDelete(key []byte, casCounter uint16) error
- func (s *KV) CompareAndDeleteAsync(key []byte, casCounter uint16, f func(error))
- func (s *KV) CompareAndSet(key []byte, val []byte, casCounter uint16) error
- func (s *KV) CompareAndSetAsync(key []byte, val []byte, casCounter uint16, f func(error))
- func (s *KV) Delete(key []byte) error
- func (s *KV) DeleteAsync(key []byte, f func(error))
- func (s *KV) Exists(key []byte) (bool, error)
- func (s *KV) Get(key []byte, item *KVItem) error
- func (s *KV) NewIterator(opt IteratorOptions) *Iterator
- func (s *KV) Set(key, val []byte) error
- func (s *KV) SetAsync(key, val []byte, f func(error))
- func (s *KV) SetIfAbsent(key, val []byte) error
- type KVItem
- type Options
Examples ¶
Constants ¶
const ( BitDelete byte = 1 // Set if the key has been deleted. BitValuePointer byte = 2 // Set if the value is NOT stored directly next to key. BitCompressed byte = 4 // Set if the key value pair is stored compressed in value log. BitSetIfAbsent byte = 8 // Set if the key is set using SetIfAbsent. M int64 = 1 << 20 )
Values have their first byte being byteData or byteDelete. This helps us distinguish between a key that has never been seen and a key that has been explicitly deleted.
Variables ¶
var CasMismatch error = errors.New("CompareAndSet failed due to counter mismatch.")
var Corrupt error = errors.New("Unable to find log. Potential data corruption.")
var DefaultIteratorOptions = IteratorOptions{ PrefetchSize: 100, FetchValues: true, Reverse: false, }
var DefaultOptions = Options{ DoNotCompact: false, LevelOneSize: 256 << 20, LevelSizeMultiplier: 10, MapTablesTo: table.LoadToRAM, MaxLevels: 7, MaxTableSize: 64 << 20, NumCompactors: 3, NumLevelZeroTables: 5, NumLevelZeroTablesStall: 10, NumMemtables: 5, SyncWrites: false, ValueCompressionMinRatio: 2.0, ValueCompressionMinSize: math.MaxInt32, ValueGCRunInterval: 10 * time.Minute, ValueGCThreshold: 0.5, ValueLogFileSize: 1 << 30, ValueThreshold: 20, }
DefaultOptions sets a list of recommended options for good performance. Feel free to modify these to suit your needs.
var ErrInvalidDir error = errors.New("Invalid Dir, directory does not exist")
var ErrNoRoom = errors.New("No room for write")
var ErrValueLogSize error = errors.New("Invalid ValueLogFileSize, must be between 1MB and 1GB")
var KeyExists error = errors.New("SetIfAbsent failed since key already exists.")
Functions ¶
This section is empty.
Types ¶
type Entry ¶
type Entry struct {
Key []byte
Meta byte
Value []byte
CASCounterCheck uint16 // If nonzero, we will check if existing casCounter matches.
Error error // Error if any.
// contains filtered or unexported fields
}
Entry provides Key, Value and if required, CASCounterCheck to kv.BatchSet() API. If CASCounterCheck is provided, it would be compared against the current casCounter assigned to this key-value. Set be done on this key only if the counters match.
func EntriesDelete ¶
EntriesDelete adds a Del to the list of entries.
func EntriesSet ¶
EntriesSet adds a Set to the list of entries. Exposing this so that user does not have to specify the Entry directly.
type Iterator ¶
type Iterator struct {
// contains filtered or unexported fields
}
Iterator helps iterating over the KV pairs in a lexicographically sorted order.
func (*Iterator) Close ¶
func (it *Iterator) Close()
Close would close the iterator. It is important to call this when you're done with iteration.
func (*Iterator) Item ¶
Item returns pointer to the current KVItem. This item is only valid until it.Next() gets called.
func (*Iterator) Next ¶
func (it *Iterator) Next()
Next would advance the iterator by one. Always check it.Valid() after a Next() to ensure you have access to a valid it.Item().
func (*Iterator) Rewind ¶
func (it *Iterator) Rewind()
Rewind would rewind the iterator cursor all the way to zero-th position, which would be the smallest key if iterating forward, and largest if iterating backward. It does not keep track of whether the cursor started with a Seek().
func (*Iterator) Seek ¶
Seek would seek to the provided key if present. If absent, it would seek to the next smallest key greater than provided if iterating in the forward direction. Behavior would be reversed is iterating backwards.
func (*Iterator) ValidForPrefix ¶
ValidForPrefix returns false when iteration is done or when the current key is not prefixed by the specified prefix.
type IteratorOptions ¶
type KV ¶
type KV struct {
sync.RWMutex // Guards list of inmemory tables, not individual reads and writes.
// contains filtered or unexported fields
}
KV provides the various functions required to interact with Badger. KV is thread-safe.
func (*KV) BatchSet ¶
BatchSet applies a list of badger.Entry. Errors are set on each Entry individually.
for _, e := range entries {
Check(e.Error)
}
func (*KV) BatchSetAsync ¶
BatchSetAsync is the asynchronous version of BatchSet. It accepts a callback function which is called when all the sets are complete. Any error during execution is passed as an argument to the callback function.
Example ¶
package main
import (
"fmt"
"io/ioutil"
"sync"
"github.com/dgraph-io/badger"
)
func main() {
opt := badger.DefaultOptions
dir, _ := ioutil.TempDir("/tmp", "badger")
opt.Dir = dir
opt.SyncWrites = true
opt.ValueDir = dir
kv, _ := badger.NewKV(&opt)
wg := new(sync.WaitGroup)
wb := make([]*badger.Entry, 0, 100)
wg.Add(1)
// Async writes would be useful if you want to write some key-value pairs without waiting
// for them to be complete and perform some cleanup when they are written.
// In Dgraph we keep on flushing posting lists periodically to badger. We do it an async
// manner and provide a callback to it which can do the cleanup when the writes are done.
f := func(err error) {
defer wg.Done()
if err != nil {
// At this point you can retry writing keys or send error over a channel to handle
// in some other goroutine.
fmt.Printf("Got error: %+v\n", err)
}
// Check for error in entries which could be non-nil if the user supplies a CasCounter.
for _, e := range wb {
if e.Error != nil {
fmt.Printf("Got error: %+v\n", e.Error)
}
}
// You can do cleanup now. Like deleting keys from cache.
fmt.Println("All async sets complete.")
}
for i := 0; i < 100; i++ {
k := []byte(fmt.Sprintf("%09d", i))
wb = append(wb, &badger.Entry{
Key: k,
Value: k,
})
}
kv.BatchSetAsync(wb, f)
fmt.Println("Finished writing keys to badger.")
wg.Wait()
}
Output: Finished writing keys to badger. All async sets complete.
func (*KV) Close ¶
Close closes a KV. It's crucial to call it to ensure all the pending updates make their way to disk.
func (*KV) CompareAndDelete ¶
CompareAndDelete deletes a key ensuring that it has not been changed since last read. If existing key has different casCounter, this would not delete the key and return an error.
func (*KV) CompareAndDeleteAsync ¶
CompareAndDeleteAsync is the asynchronous version of CompareAndDelete. It accepts a callback function which is called when the CompareAndDelete completes. Any error encountered during execution is passed as an argument to the callback function.
func (*KV) CompareAndSet ¶
CompareAndSet sets the given value, ensuring that the no other Set operation has happened, since last read. If the key has a different casCounter, this would not update the key and return an error.
func (*KV) CompareAndSetAsync ¶
CompareAndSetAsync is the asynchronous version of CompareAndSet. It accepts a callback function which is called when the CompareAndSet completes. Any error encountered during execution is passed as an argument to the callback function.
func (*KV) Delete ¶
Delete deletes a key. Exposing this so that user does not have to specify the Entry directly. For example, BitDelete seems internal to badger.
func (*KV) DeleteAsync ¶
DeleteAsync is the asynchronous version of Delete. It calls the callback function after deletion is complete. Any error encountered during the execution is passed as an argument to the callback function.
func (*KV) Exists ¶
Exists looks if a key exists. Returns true if the key exists otherwises return false. if err is not nil an error occurs during the key lookup and the existence of the key is unknown
func (*KV) NewIterator ¶
func (s *KV) NewIterator(opt IteratorOptions) *Iterator
NewIterator returns a new iterator. Depending upon the options, either only keys, or both key-value pairs would be fetched. The keys are returned in lexicographically sorted order. Usage:
opt := badger.DefaultIteratorOptions
itr := kv.NewIterator(opt)
for itr.Rewind(); itr.Valid(); itr.Next() {
item := itr.Item()
key := item.Key()
val := item.Value() // This could block while value is fetched from value log.
// For key only iteration, set opt.FetchValues to false, and don't call
// item.Value().
// Remember that both key, val would become invalid in the next iteration of the loop.
// So, if you need access to them outside, copy them or parse them.
}
itr.Close()
func (*KV) Set ¶
Set sets the provided value for a given key. If key is not present, it is created. If it is present, the existing value is overwritten with the one provided.
func (*KV) SetAsync ¶
SetAsync is the asynchronous version of Set. It accepts a callback function which is called when the set is complete. Any error encountered during execution is passed as an argument to the callback function.
func (*KV) SetIfAbsent ¶
SetIfAbsent sets value of key if key is not present. If it is present, it returns the KeyExists error.
type KVItem ¶
type KVItem struct {
// contains filtered or unexported fields
}
KVItem is returned during iteration. Both the Key() and Value() output is only valid until iterator.Next() is called.
func (*KVItem) Key ¶
Key returns the key. Remember to copy if you need to access it outside the iteration loop.
func (*KVItem) Value ¶
Value returns the value, generally fetched from the value log. This call can block while the value is populated asynchronously via a disk read. Remember to parse or copy it if you need to reuse it. DO NOT modify or append to this slice; it would result in internal data overwrite.
type Options ¶
type Options struct {
Dir string // Directory to store the data in. Should exist and be writable.
ValueDir string // Directory to store the value log in. Can be the same as Dir.
// The following affect all levels of LSM tree.
MaxTableSize int64 // Each table (or file) is at most this size.
LevelSizeMultiplier int // Equals SizeOf(Li+1)/SizeOf(Li).
MaxLevels int // Maximum number of levels of compaction.
ValueThreshold int // If value size >= this threshold, only store value offsets in tree.
MapTablesTo int // How should LSM tree be accessed.
NumMemtables int // Maximum number of tables to keep in memory, before stalling.
// The following affect how we handle LSM tree L0.
// Maximum number of Level 0 tables before we start compacting.
NumLevelZeroTables int
// If we hit this number of Level 0 tables, we will stall until L0 is compacted away.
NumLevelZeroTablesStall int
// Maximum total size for L1.
LevelOneSize int64
// Run value log garbage collection if we can reclaim at least this much space. This is a ratio.
ValueGCThreshold float64
// How often to run value log garbage collector.
ValueGCRunInterval time.Duration
// Size of single value log file.
ValueLogFileSize int64
// The following affect value compression in value log. Note that compression
// can significantly slow down the loading and lookup time.
ValueCompressionMinSize int32 // Minimal size in bytes of KV pair to be compressed.
ValueCompressionMinRatio float64 // Minimal compression ratio of KV pair to be compressed.
// Sync all writes to disk. Setting this to true would slow down data loading significantly.
SyncWrites bool
// Number of compaction workers to run concurrently.
NumCompactors int
// Flags for testing purposes.
DoNotCompact bool // Stops LSM tree from compactions.
// contains filtered or unexported fields
}
Options are params for creating DB object.
Source Files
Directories