README
¶
voidDB
voidDB is a memory-mapped key-value store: simultaneously in-memory and persistent on disk. An embedded database manager, it is meant to be integrated into application software to eliminate protocol overheads and achieve zero-copy performance. This library supplies interfaces for storage and retrieval of arbitrary bytes on 64-bit computers running Linux and macOS.
voidDB features Put, Get, and Del operations as well as forward and backward iteration over self-sorting data in ACID (atomic, consistent, isolated, and durable) transactions. Readers retain a consistent view of the data throughout their lifetime, even as newer transactions are being committed: only pages freed by transactions older than the oldest surviving reader are actively recycled.
voidDB employs a copy-on-write strategy to maintain data in a multi-version concurrency-controlled (MVCC) B+ tree structure. It allows virtually any number of concurrent readers, but only one active writer at any given moment. Readers (and the sole writer) neither compete nor block one another, even though they may originate from and operate within different threads and processes.
voidDB is resilient against torn writes. It automatically restores a database to its last stable state in the event of a mid-write crash. Once a transaction is committed and flushed to disk it is safe, but even if not it could do no harm to existing data in storage. Applications need not be concerned about broken lockfiles or lingering effects of unfinished transactions should an uncontrolled shutdown occur; its design guarantees automatic and immediate release of resources upon process termination.
Benchmarks
voidDB outperforms well-known key-value stores available to Go developers that are based on B+ trees (LMDB, bbolt) and log-structured merge(LSM)-trees (LevelDB, BadgerDB), in preliminary performance tests conducted on x86-64 and AArch64 instances.
x86-64/amd64
AMD EPYC "Milan"
Amazon EC2 r6a, EBS gp3:
goos: linux
goarch: amd64
pkg: test
cpu: AMD EPYC 7R13 Processor
BenchmarkPopulateKeyVal-8 131072 14407 ns/op
BenchmarkVoidPut-8 131072 49785 ns/op
BenchmarkVoidGet-8 131072 1371 ns/op
BenchmarkVoidGetNext-8 131072 444.1 ns/op
BenchmarkLMDBPut-8 131072 76957 ns/op
BenchmarkLMDBGet-8 131072 1603 ns/op
BenchmarkLMDBGetNext-8 131072 879.3 ns/op
BenchmarkBoltPut-8 131072 229226 ns/op
BenchmarkBoltGet-8 131072 2414 ns/op
BenchmarkBoltGetNext-8 131072 452.2 ns/op
BenchmarkLevelPut-8 131072 152578 ns/op
BenchmarkLevelGet-8 131072 30373 ns/op
BenchmarkLevelGetNext-8 131072 4196 ns/op
BenchmarkBadgerPut-8 131072 89332 ns/op
BenchmarkBadgerGet-8 131072 20421 ns/op
BenchmarkBadgerGetNext-8 131072 2731 ns/op
BenchmarkNothing-8 131072 0.2787 ns/op
R6a instances are powered by 3rd generation AMD EPYC processors ... and are an ideal fit for memory-intensive workloads, such as SQL and NoSQL databases; distributed web scale in-memory caches, such as Memcached and Redis; in-memory databases and real-time big data analytics, such as Apache Hadoop and Apache Spark clusters; and other enterprise applications.
Intel Xeon Platinum "Sapphire Rapids"
Amazon EC2 r7i, EBS gp3:
goos: linux
goarch: amd64
pkg: test
cpu: Intel(R) Xeon(R) Platinum 8488C
BenchmarkPopulateKeyVal-8 131072 10750 ns/op
BenchmarkVoidPut-8 131072 56492 ns/op
BenchmarkVoidGet-8 131072 1227 ns/op
BenchmarkVoidGetNext-8 131072 377.2 ns/op
BenchmarkLMDBPut-8 131072 73205 ns/op
BenchmarkLMDBGet-8 131072 1563 ns/op
BenchmarkLMDBGetNext-8 131072 691.0 ns/op
BenchmarkBoltPut-8 131072 417657 ns/op
BenchmarkBoltGet-8 131072 2091 ns/op
BenchmarkBoltGetNext-8 131072 271.7 ns/op
BenchmarkLevelPut-8 131072 97302 ns/op
BenchmarkLevelGet-8 131072 28205 ns/op
BenchmarkLevelGetNext-8 131072 3799 ns/op
BenchmarkBadgerPut-8 131072 90613 ns/op
BenchmarkBadgerGet-8 131072 15375 ns/op
BenchmarkBadgerGetNext-8 131072 3033 ns/op
BenchmarkNothing-8 131072 0.3990 ns/op
R7i instances are ... powered by custom 4th Generation Intel Xeon Scalable processors (code named Sapphire Rapids) ... and ideal for all memory-intensive workloads (SQL and NoSQL databases), distributed web scale in-memory caches (Memcached and Redis), in-memory databases (SAP HANA), and real-time big data analytics (Apache Hadoop and Apache Spark clusters).
AArch64/arm64
Ampere Altra
Google Cloud Compute Engine t2a, SSD persistent disk:
goos: linux
goarch: arm64
pkg: test
BenchmarkPopulateKeyVal-8 131072 13850 ns/op
BenchmarkVoidPut-8 131072 41688 ns/op
BenchmarkVoidGet-8 131072 1803 ns/op
BenchmarkVoidGetNext-8 131072 460.4 ns/op
BenchmarkLMDBPut-8 131072 48451 ns/op
BenchmarkLMDBGet-8 131072 2267 ns/op
BenchmarkLMDBGetNext-8 131072 892.3 ns/op
BenchmarkBoltPut-8 131072 192896 ns/op
BenchmarkBoltGet-8 131072 3566 ns/op
BenchmarkBoltGetNext-8 131072 451.0 ns/op
BenchmarkLevelPut-8 131072 59104 ns/op
BenchmarkLevelGet-8 131072 42006 ns/op
BenchmarkLevelGetNext-8 131072 4860 ns/op
BenchmarkBadgerPut-8 131072 47798 ns/op
BenchmarkBadgerGet-8 131072 27400 ns/op
BenchmarkBadgerGetNext-8 131072 3127 ns/op
BenchmarkNothing-8 131072 0.4184 ns/op
Apple M1 Pro chip
Ubuntu VM in Multipass for macOS, MacBook Pro, Apple NVMe SSD:
goos: linux
goarch: arm64
pkg: test
BenchmarkPopulateKeyVal-2 131072 9069 ns/op
BenchmarkVoidPut-2 131072 14520 ns/op
BenchmarkVoidGet-2 131072 1018 ns/op
BenchmarkVoidGetNext-2 131072 243.0 ns/op
BenchmarkLMDBPut-2 131072 24132 ns/op
BenchmarkLMDBGet-2 131072 1455 ns/op
BenchmarkLMDBGetNext-2 131072 583.5 ns/op
BenchmarkBoltPut-2 131072 75558 ns/op
BenchmarkBoltGet-2 131072 2089 ns/op
BenchmarkBoltGetNext-2 131072 243.0 ns/op
BenchmarkLevelPut-2 131072 40225 ns/op
BenchmarkLevelGet-2 131072 27412 ns/op
BenchmarkLevelGetNext-2 131072 2870 ns/op
BenchmarkBadgerPut-2 131072 15450 ns/op
BenchmarkBadgerGet-2 131072 21309 ns/op
BenchmarkBadgerGetNext-2 131072 13626 ns/op
BenchmarkNothing-2 131072 0.3249 ns/op
Native macOS, MacBook Pro, Apple NVMe SSD:
goos: darwin
goarch: arm64
pkg: test
cpu: Apple M1 Pro
BenchmarkPopulateKeyVal-10 131072 4598 ns/op
BenchmarkVoidPut-10 131072 10755 ns/op
BenchmarkVoidGet-10 131072 852.8 ns/op
BenchmarkVoidGetNext-10 131072 224.9 ns/op
BenchmarkLMDBPut-10 131072 6280 ns/op
BenchmarkLMDBGet-10 131072 1707 ns/op
BenchmarkLMDBGetNext-10 131072 754.7 ns/op
BenchmarkBoltPut-10 131072 61757 ns/op
BenchmarkBoltGet-10 131072 1807 ns/op
BenchmarkBoltGetNext-10 131072 439.5 ns/op
BenchmarkLevelPut-10 131072 97582 ns/op
BenchmarkLevelGet-10 131072 40275 ns/op
BenchmarkLevelGetNext-10 131072 3687 ns/op
BenchmarkBadgerPut-10 131072 7126 ns/op
BenchmarkBadgerGet-10 131072 13894 ns/op
BenchmarkBadgerGetNext-10 131072 2622 ns/op
BenchmarkNothing-10 131072 0.3366 ns/op
AWS Graviton4
Amazon EC2 r8g, EBS gp3:
goos: linux
goarch: arm64
pkg: test
BenchmarkPopulateKeyVal-8 131072 10807 ns/op
BenchmarkVoidPut-8 131072 49006 ns/op
BenchmarkVoidGet-8 131072 1225 ns/op
BenchmarkVoidGetNext-8 131072 422.0 ns/op
BenchmarkLMDBPut-8 131072 71656 ns/op
BenchmarkLMDBGet-8 131072 1470 ns/op
BenchmarkLMDBGetNext-8 131072 749.5 ns/op
BenchmarkBoltPut-8 131072 119710 ns/op
BenchmarkBoltGet-8 131072 2158 ns/op
BenchmarkBoltGetNext-8 131072 354.1 ns/op
BenchmarkLevelPut-8 131072 77564 ns/op
BenchmarkLevelGet-8 131072 27252 ns/op
BenchmarkLevelGetNext-8 131072 3379 ns/op
BenchmarkBadgerPut-8 131072 90776 ns/op
BenchmarkBadgerGet-8 131072 15028 ns/op
BenchmarkBadgerGetNext-8 131072 1746 ns/op
BenchmarkNothing-8 131072 0.3586 ns/op
R8g instances, powered by the latest-generation AWS Graviton4 processors, ... are ideal for memory-intensive workloads, such as databases, in-memory caches, and real-time big data analytics.
Getting Started
Install Go to begin developing with voidDB.
$ go version
go version go1.24.0 linux/arm64
Then, import voidDB in your Go application. The following would result in the creation of a database file and its reader table in the working directory. Set the database capacity to any reasonably large value to make sufficient room for the data you intend to store, even if it exceeds the total amount of physical memory; neither memory nor disk is immediately consumed to capacity.
package main
import (
"errors"
"os"
"github.com/voidDB/voidDB"
)
func main() {
const (
capacity = 1 << 40 // 1 TiB
path = "void"
)
void, err := voidDB.NewVoid(path, capacity)
if errors.Is(err, os.ErrExist) {
void, err = voidDB.OpenVoid(path, capacity)
}
if err != nil {
panic(err)
}
defer void.Close()
}
Use *Void.View (or *Void.Update only when modifying data) for convenience
and peace of mind. Ensure all changes are safely synced to disk with mustSync
set to true if even the slightest risk of losing those changes is a concern.
mustSync := true
err = void.Update(mustSync,
func(txn *voidDB.Txn) error {
return txn.Put(
[]byte("greeting"),
[]byte("Hello, World!"),
)
},
)
if err != nil {
panic(err)
}
Open a cursor if more than one keyspace is required. An application can map different values to the same key so long as they reside in separate keyspaces. The transaction handle doubles as a cursor in the default keyspace.
cur0, _ := txn.OpenCursor([]byte("hello"))
cur0.Put([]byte("greeting"),
[]byte("Hello, World!"),
)
cur1, _ := txn.OpenCursor([]byte("goodbye"))
cur1.Put([]byte("greeting"),
[]byte("さらばこの世、わらわはもう寝るぞよ。"),
)
if val, err := cur0.Get([]byte("greeting")); err == nil {
log.Printf("%s", val) // Hello, World!
}
if val, err := cur1.Get([]byte("greeting")); err == nil {
log.Printf("%s", val) // さらばこの世、わらわはもう寝るぞよ。
}
To iterate over a keyspace, use *cursor.Cursor.GetNext/GetPrev. Position
the cursor with *cursor.Cursor.Get/GetFirst/GetLast.
for {
key, val, err := cur.GetNext()
if errors.Is(err, common.ErrorNotFound) {
break
}
log.Printf("%s -> %s", key, val)
}
Author
voidDB builds upon ideas in the celebrated Lightning Memory-Mapped Database Manager on several key points of its high-level design, but otherwise it is implemented from scratch to break free of limitations in function, performance, and clarity.
voidDB is a cherished toy, a journey into the Unknown, a heroic struggle, and a work of love. It is the “Twee!” of a bird; a tree falling in the forest; yet another programmer pouring their drop into the proverbial [bit] bucket. Above all, it is a shrine unto simple, readable, and functional code; an assertion that the dichotomy between such aesthetics and practical performance is mere illusion.
Copyright 2024 Joel Ling
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Txn ¶
A Txn is a transaction handle necessary for interacting with a database. A transaction is the sum of the state of the database as at the beginning of that transaction and any changes made within it. See *Void.BeginTxn for more information.
func (*Txn) Abort ¶
Abort discards all changes made in a read-write transaction, and releases the exclusive write lock. In the case of a read-only transaction, Abort ends the moratorium on recycling of pages constituting its view of the dataset. For this reason, applications should not be slow to abort transactions that have outlived their usefulness lest they prevent effective resource utilisation. Following an invocation of Abort, the transaction handle must no longer be used.
func (*Txn) Commit ¶
Commit persists all changes to data made in a transaction. The state of the database is not really updated until Commit has been invoked. If it returns a nil error, effects of the transaction would be perceived in subsequent transactions, whereas pre-existing transactions will remain oblivious as intended. Whether Commit waits on *os.File.Sync depends on the mustSync argument passed to *Void.BeginTxn. The transaction handle is not safe to reuse after the first invocation of Commit, regardless of the result.
func (*Txn) OpenCursor ¶
OpenCursor returns a handle on a cursor associated with the transaction and a particular keyspace. Keyspaces allow multiple datasets with potentially intersecting (overlapping) sets of keys to reside within the same database without conflict, provided that all keys are unique within their respective keyspaces. Argument keyspace must not be simultaneously non-nil and of zero length, or otherwise longer than node.MaxKeyLength. Passing nil as the argument causes OpenCursor to return a cursor in the default keyspace.
CAUTION: An application utilising keyspaces should avoid modifying records within the default keyspace, as it is used to store pointers to all the other keyspaces. There is virtually no limit on the number of keyspaces in a database.
Unless multiple keyspaces are required, there is usually no need to invoke OpenCursor because the transaction handle embeds a *cursor.Cursor associated with the default keyspace.
func (*Txn) SerialNumber ¶ added in v0.1.1
SerialNumber returns a serial number identifying a particular state of the database as at the beginning of the transaction. All transactions beginning from the same state share the same serial number.
type Void ¶
type Void struct {
// contains filtered or unexported fields
}
A Void is a handle on a database. To interact with the database, enter a transaction through *Void.BeginTxn.
func NewVoid ¶
NewVoid creates and initialises a database file and its reader table at path and path.readers respectively, and returns a handle on the database, or os.ErrExist if a file already exists at path. See also OpenVoid for an explanation of the capacity parameter.
func OpenVoid ¶
OpenVoid returns a handle on the database persisted to the file at path.
The capacity argument sets a hard limit on the size of the database file in number of bytes, but it applies only to transactions entered into via the database handle returned. The database file never shrinks, but it will not be allowed to grow if its size already exceeds capacity as at the time of invocation. A transaction running against the limit would incur common.ErrorFull on commit.
func (*Void) BeginTxn ¶
BeginTxn begins a new transaction. The resulting transaction cannot modify data if readonly is true: any changes made are isolated to the transaction and non-durable; otherwise it is a write transaction. Since there cannot be more than one ongoing write transaction per database at any point in time, the function may return syscall.EAGAIN or syscall.EWOULDBLOCK (same error, “resource temporarily unavailable”) if an uncommitted/unaborted incumbent is present in any thread/process in the system.
Setting mustSync to true ensures that all changes to data are flushed to disk when the transaction is committed, at a cost to write performance; setting it to false empowers the filesystem to optimise writes at a risk of data loss in the event of a crash at the level of the operating system or lower, e.g. hardware or power failure. Database corruption is also conceivable, albeit only if the filesystem does not preserve write order. TL;DR: set mustSync to true if safety matters more than speed; false if vice versa.
BeginTxn returns common.ErrorResized if the database file has grown beyond the capacity initially passed to OpenVoid. This can happen if another database handle with a higher capacity has been obtained via a separate invocation of OpenVoid in the meantime. To adapt to the new size and proceed, close the database handle and replace it with a new invocation of OpenVoid.
func (*Void) Close ¶
Close closes the database file and releases the corresponding memory map, rendering both unusable to any remaining transactions already entered into using the database handle. These stranded transactions could give rise to undefined behaviour if their use is attempted, which could disrupt the application, but in any case they pose no danger whatsoever to the data safely jettisoned.
func (*Void) Update ¶ added in v0.1.1
Update is a convenient wrapper around *Void.BeginTxn, *Txn.Commit, and *Txn.Abort, to help applications ensure timely termination of writers. If operation is successful (in that it returns a nil error), the transaction is automatically committed and the result of *Txn.Commit is returned. Otherwise, the transaction is aborted and the output of errors.Join wrapping the return values of operation and *Txn.Abort is returned. IMPORTANT: See also *Void.BeginTxn for an explanation of the mustSync parameter.
func (*Void) View ¶ added in v0.1.1
View is similar to *Void.Update, except that it begins and passes to operation a read-only transaction. If operation results in a non-nil error, that error is errors.Join-ed with the result of *Txn.Abort; otherwise only the latter is returned.
Source Files
Directories