BadgerDB

Badger started as a key-value store, so the goal was to use the latest research to build a key-value store. It uses a log-structured merge (LSM) tree based implementation, which has an advantage in throughput when compared to B+ tree since background (disk) writes in LSM maintain a sequential access pattern.

History

BadgerDB was initially a persistent key-value store intended to replace DgraphDB’s dependency on RocksDB, since RocksDB is written in C++ and requires the use of Cgo to be called via Go. It was a (side) project lead by Manish Rai Jain, a chief decision maker at Dgraph. As the project progressed, in 2017 the developers decided to expand the scope of the project to be a more full-featured database system.

Checkpoints

Non-Blocking

The user has the option to determine whether changes are immediately propagated to disk after an update. If this option is disabled, then writes may not sync to disk immediately. All writes will be flushed to disk when the application closes the database. In addition to changes being propagate to disk when the application closes the database, changes are also propagated when a max table size threshold (`MaxTableSize`) is reached.

Compression

Delta Encoding

BadgerDB uses delta encoding to reduce the size of keys, to further reduce the size of the LSMs. Also, during a read, a fingerprint of the key is stored rather than the key itself to also save space. The fingerprint of a key contains the information necessary to identify a unique key, but takes up less space. It is not a 100% accurate and can cause a false negative causing a transaction to abort (and requiring it to be restarted).

Concurrency Control

Multi-version Concurrency Control (MVCC) Two-Phase Locking (Deadlock Prevention)

Badger supports ACID transactions and Multi-Version Concurrency Control with Snapshot Isolation. Badger acquires locks on directories when accessing data, so multiple processes cannot open the same database at the same time. If the transaction is read-write, the transaction checks if there is a conflict and return and error if there is one.

Data Model

Key/Value

Badger’s underlying functionality is a key-value store. The user can choose to store additional meta-data with the key-value pair for use when processing that data.

Indexes

Log-Structured Merge Tree

BadgerDB supports a LSM tree, where keys are stored in the LSM and values are store in a write-ahead log called a value log. Since key tend to be smaller than values, this allows the system to maintain a smaller LSM tree. The LSM make sure to maintain a sorted order, making range queries easier to process, as well.

Isolation Levels

Serializable Snapshot Isolation

BadgerDB supports snapshot isolation. Badger also has read-only transactions (called Views), that ensures a consistent view of the database system, and that will not include changes made by an uncommitted transaction at the start of this transactions. With read-write transactions, if a conflict occurs, the transaction will written with an error notifying the user of a conflict, giving the user the option to retry the transaction.

Logging

Physical Logging

BadgerDB uses a write-ahead log to record changes.

Query Execution

Tuple-at-a-Time Model Vectorized Model

BadgerDB is inspired by the simplicity of LevelDB and supports Get, Set, Delete, and Iterate functions. Multiple updates can be batched-up into a single transaction, allowing the user to do a lot of writes at a time.

Query Interface

Custom API

The query interface for BadgerDB is in Go since the system was originally created to provide a key-value store that can easily be accessed through Go without having to go through Ggo.

Storage Architecture

Disk-oriented In-Memory

BadgerDB is an in-memory DBMS, that supports larger-than-memory databases by writing to disk. Disk is also used to make the BadgerDB persistent and resilient. BadterDB works in-memory until the `MaxTableSize` threshold is reached, at which point the data is propagated to disk.

Storage Model

N-ary Storage Model (Row/Record)

The LSM writes the initial in-memory updates in memtables. Once those are full, they are moved over to immutable memtables that are eventually written to disk.

Storage Organization

Log-structured Sorted Files

Badger uses LSMs, which were designed around hard drives, since random I/Os are slower than sequential ones, and LSMs allow for sequential background read/writes rather than random ones.

Stored Procedures

Not Supported

System Architecture

Embedded

BadgerDB is an embeddable database management system.

People Also Viewed

BadgerDB Logo
Website

https://github.com/dgraph-io/badger

Tech Docs

https://godoc.org/github.com/dgraph-io/badger

Developer

Dgraph

Country of Origin

US

Start Year

2017

Project Type

Open Source

Written in

Go

Derived From

DGraph

Inspired By

RocksDB

Compatible With

DGraph

Operating Systems

iOS, Linux, Windows

Licenses

Apache v2

People Also Viewed