vBolt

vBolt is a low latency database layer with an exclusively programmatic interface and explicit-only indexing

https://pkg.go.dev/go.hasen.dev/vbolt

Introduction

vBolt is a data persistence and retrieval engine (database system) based on the concept of persisted data structures.

Instead of issuing textual query strings to a database server, you call functions to read from and write to a persisted bucket or index.

For example, to save user data:

vbolt.Write(tx, UserBucket, user.Id, &user)

You can think of UserBucket here as it as if it was a persisted map[int]User, and the line above has having a similar effect to the statement: UserBucket[user.Id] = user, with the addition that the mapping is persisted to storage.

To read user data by id:

found := vbolt.Read(tx, UserBucket, userId, &user)

This would be like user, found := UserBucket[userId], except it queries from storage.

There's no implicit indexing, instead we provide an index as a persisted data structure that you explicitly use.

More will be explained below.

vBolt is not an ORM

It's important to note that vBolt is not an ORM. There's no textual query language underneath.

The only "mapping" vbolt performs is binary serialization and deserialization. Everything else is just based on persisted b-trees powered by BoltDB.

Here's a rough outline of what the Write function does:

There are no network requests; only reading and writing to/from the local filesystem.

We do not believe in adding more layers on top of a complex system to make it look simple. We try instead to simplify the system by collapsing layers.

A typical ORM-like library has to perform the following steps to mimic the above Write function:

Our approach radically reduces the amount of work the computer has to do at runtime. The only thing we really do is the last part: "execute the plan".

There's no introspection, no generation and parsing of a text string, no validation, no compilation, no planning. The execution plan is already known at compile time!

As a result, vBolt significantly outperforms most database engines. Simple data retrieval is completed in microseconds, and complicated data queries with large objects take < 10ms.

Disclaimer: we would never claim raw performance as one vBolt's strongest suits. It just happens to perform better than many other alternatives because it does not do a lot of the unnecessary work they tend to carry out.

Credits

vBolt is a thin layer on top of BoltDB, that turns it from a raw key-value store into a versatile storage engine with indexing capabilities.

It's only a few hundred lines of code, compared to bolt itself, which is about 4000 lines (excluding comments, whitespace, and tests).

vBolt relies on vPack for the serialization scheme, which itself is also merely a few hundred lines of code.

Basic concepts

Here's a list of basic concepts you need to understand to start using this package:

Database & Transactions

The database (DB) and transaction (Tx) are carried over from BoltDB as-is.

Database

The database is a single file, which you open during the initialization of your application.

We provide a helper function that takes the filename and returns the DB handle. It panics if opening the database fails, for example, if another process is already using it.

vbolt.Open(filename string) *DB

The expected usage pattern is that you will have a global variable that will get initialized at some point during the initialization process of the application.

var db *vbolt.DB

....

func initDB(...) {
	db = vbolt.Open(dbFilename)
}

If you want more control over the behavior, you can use the Open function from boltdb directly: import "github.com/boltdb/bolt" and call bolt.Open(...)

Transactions

Transactions are required to read or write data.

As with the DB, you can use boltdb function directly to obtain a transaction, but we provide some helper functions for doing that.

The main difference is our API is structured as functions, not methods bound to a type.

func ReadTx(db *DB) *Tx
func WriteTx(db *DB) *Tx
func TxClose(tx *Tx)
func TxCommit(tx *Tx)

If you use ReadTx(db) or WriteTx(db), you must immediately add a defer statement to TxClose(tx)

tx := ReadTx(db)
defer TxClose(tx)

tx := WriteTx(db)
defer TxClose(tx)

Generally speaking, when using a WriteTx, you should not defer TxCommit. Commit explicitly at the end of the function after you've done all the writing you need. This ensures that if you return early or a panics occur half way through your code, nothing will be committed.

func WithReadTx(db *DB, fn func(tx *Tx))
func WithWriteTx(db *DB, fn func(tx *Tx))

We also provide some helpers to automatically close the transaction. The only "benefit" of these is so you don't have to worry about forgetting to defer TxClose(tx)

Important: WithWriteTx does not auto commit at the end. You have to commit explicitly at the end of your own code.

Notes:

Binary Serialization

Binary serialization is provided via vPack. Refer to its documentation. Essentially, a serialization function takes a pointer to the object you want to serialize/deserialize, and a pointer to a buffer. You serialize the fields of the object in order. The same function serves both as a serialization AND deserialization.

Bucket

A bucket is a one-to-one mapping that's persisted to storage. The key is typically an integer or a uuid, and the value is an arbitrary object.

To use a bucket, you first have to declare it

var Info vbolt.Info // define once

// int => User
// maps user id to user
var UserBucket = vbolt.Bucket(&Info, "user", vpack.FInt, PackUser)

// int => []byte
// maps userid to bcrypt hashed password
var PasswordBucket = vbolt.Bucket(&Info, "passwords", vpack.FInt, vpack.ByteSlice)

// string => int
// maps username to userid
var UsernameBucket = vbolt.Bucket(&Info, "username", vpack.StringZ, vpack.Int)

// declare as many buckets as you want ...

You declare your buckets by calling vbolt.Bucket. The return value is *vbolt.BucketInfo, which will be used for reading from the bucket and writing to it.

Bucket declarations are bound to a vbolt.Info object for introspection purposes.

Unlike a regular map in Go, a bucket is not just about mapping a key to value; it's primarily about persisting data to disk, so the key and value parameters are not given as types, but as packing functions.

The packing function implies the type, so we don't need to provide it separately.

In the example above:

var UserBucket = vbolt.Bucket(&Info, "user", vpack.FInt, PackUser)

PackUser is a packing function compatible with vpack.PackFn[User], in other words, it would look something like this:

func PackUser(user *User, buf *vpack.Buffer) {
	var version = vpack.Version(2)
	vpack.Int(&user.Id, buf)
	vpack.String(&user.Name, buf)
	vpack.String(&user.Email, buf)
	vpack.Bool(&user.IsAdmin, buf)
	if version >= 2 {
		vpack.Bool(&user.EmailVerified, buf)
	}
}

Since the underlying storage is a B-Tree, you might want to give some consideration regarding which serialization function you want to use for the key.

If you want to be able to iterate on the items in the bucket in order, use the vpack.FInt serialization function, because it stores integers as 8 bytes (in big endian), guaranteeing that the order of keys in the bucket matches the numeric order of the ids.

Similarly, if you want to iterate on a bucket in order where the key is a string, use vpack.StringZ instead of vpack.String. The former uses c-style null terminated encoding for the strings, making it suitable for sorted iteration, while the later places the length of the string (in varint encoding) before the string, which while useful when encoding a string field as part of an object, does not have any particular advantage when used as the serialization function for the key of a bucket.

Reading

func Read[K comparable, T any](tx *Tx, info *BucketInfo[K, T], id K, item *T) bool

To read from a bucket, you need a transaction.

The api is designed to take a pointer to the variable that will be filled with the data read. The return value is a boolean indicating success or failure.

Example:

// assume tx and userId are given
var user User
vbolt.Read(tx, UserBucket, userId, &user)

Since the bucket has the packing functions for both keys and values, the Read function makes use of them to locate the data in the tree (using the key) and unpacking the data (from the value that maps to the key) into a user struct.

We also provide helper functions to read a list of object ids into a slice or a map:

func ReadSlice[K comparable, T any](tx *Tx, info *BucketInfo[K, T], ids []K, list *[]T) int
func ReadSliceToMap[K comparable, T any](tx *Tx, info *BucketInfo[K, T], ids []K, itemsMap map[K]T) int

The return value is the number of objects loaded, which maybe smaller than the number ids given.

This is useful to load related objects. For example, suppose you have an Article object and it belongs to a list of Categories. How do you model this relationship? Well it's simple: the Article struct has a CategoryIds []int field, and after you load the article, you can load the categories:

var article Article
var categories []Category
vbolt.Read(tx, ArticleBucket, articleId, &article)
vbolt.ReadSlice(tx, CategoryBucket, article.CategoryIds, &categories)

To get the list of articles in the given category, you use the index, which is explained in the next section.

Writing

To write to a bucket, you need a read-write transaction.

func Write[K comparable, T any](tx *Tx, info *BucketInfo[K, T], id K, item *T)

If id is the zero value for its type, nothing will be written.

Example usage:

vbolt.Write(tx, UserBucket, userId, &user)
vbolt.Write(tx, UserNameBucket, user.Name, &userId)
vbolt.Write(tx, PasswordBucket, userId, &passwdHash)

NOTE: if writing fails, the Write function will panic.

It will not return an error. It will panic.

Why not return errors? Because there's nothing you can do in the error recovery other than abort the operation and report to the user that an error has occurred.

A write error here is not much different than trying to access data behind a null pointer, or access an element outside array bounds.

They really are exceptions, and it's not wise to litter your code with checks against those errors.

Instead, you should write the code so that such "errors" never happen.

All the conditions under which a write error occurs (other than OS level I/O errors) are avoidable programmer mistakes:

Your serialization functions should never fail. You should never use a read-only transaction to write data. Your keys should never be invalid.

The only reasonable course of action is to recover from the panic at a central top level function, report the error to the user, and let the program continue normally (waiting for user requests to do other operations).

Sequential Ids

If the key for your bucket is an int, you can leverage this function:

func NextIntId[K, T any](tx *Tx, info *BucketInfo[K, T]) int

It's wrapper around BoltDB's bucket.NextSequence but it panics on failure instead of returning an error.

Example:

userId := vbolt.NextIntId(tx, UserBucket)

Index

An index is a bidirectional multi-map, or a many-to-many map. The expected usecase for an index is to map a term to a target.

"Term" refers to a query term, while a target is usually an object id.

Conceptually you have a bunch of [target, term] pairs that are maintained such that you can quickly find the list of targets given a term, or the list of terms given a target.

Think of an index on the back of a book. You have some key words and the pages they appear in. The word is the term, while the page number is the target.

// int => int
// term: keyword id, target: object id
var KeywordsIndex = vbolt.Index(&Info, "keywords-idx", vpack.StringZ, vpack.FInt)

How would you build such an index? A simple way is to iterate on the pages in the book. For each page, you can collect all the important words that appear on it, and update the index by setting the "terms" that point to the "target" (page number) on the index.

This is the API we provide to update the index: set target terms. Given an index, and given a target, set the terms for it.

Now, it gets a little bit more complicated.

Target Priority

Each [term, target] pair has a priority to sort the targets relative to the term. If you don't need a priority to sort the targets by, then you can ignore this feature, but if you do want targets to be sortable, you need to give the matter some consideration.

You need to come up with a scheme to produce a priority number for each term, without considering anything outside the target object.

In the keyword <-> page number example (for the book's index section), we need a scheme that computes the priority without having to check all the other pages that the term appears on.

A simple but effective scheme in this case would be to give more weight to the term if it appears in a header (or a subheader) on the page, and less weight if it appears in the footnotes.

We can count how many times the word appears, and multiply each occurrence by a weight associated with the type of block it appears in. Example weights:

Why this scheme? Well consider some term T that appears in a header on page 100 but merely in the footnotes on page 10. Assuming people looking in the index want to learn more about topic represented by the term T, it makes sense for us to point them to page 100 first, before we tell them about page 10.

Now, in the current version of vBolt, the priority is stored as FUint16, meaning it's 16bit integer sorted in ascending order. So the lower priority will appear first. We can convert a weight to a priority by first capping the weight at some ceiling value, say, 1000, and then subtract the weight from that ceiling value to produce the priority.

The key is composed of the "term" bytes, followed by the priority bytes, followed by the target bytes. You can visualize it like this:

[B | T | T | T | T | T | T | P | P | K | K | K | K | K]

Where B is a special byte value, T, K and P are flexible because they are user-provided. The priority number needs to be chosen so that the sort order is meaningful when priorities are in ascending ordered.

The default priority type is uint16, but you can vbolt.IndexExt when defining the index to provide a serializaton function for the priority as well.

Hypothetical example:

// SubscribedEmailsIdx maps mailing list id to list of subscribed emails
var SubscribedEmailsIdx = vbolt.IndexExt(&dbInfo, "email-sub-idx",
	  vpack.Int,      // term: list id
    vpack.UnixTime, // priority: subscription date
    vpack.String,   // target: subscribed email address
)

Index APIs

Set Target Terms

func SetTargetTerms[K, T, P comparable](tx *Tx, indexInfo *IndexInfo[K, T, P], target K, terms map[T]P)

This sets the terms that should map to the given target.

The terms parameter is a map because it maps the term to its priority.

If there are already targets in the index that map to this object but are not present in the request set of terms here, they will be removed.

If a term already exists but has a different priority, the priority will be updated. If a term is new, it will be added.

If all the terms have the same priority (i.e. the priority depends on the target itself and not on the term), you can use this helper function:

func SetTargetTermsUniform[K, T, P comparable](tx *Tx, indexInfo *IndexInfo[K, T, P], target K, terms []T, priority P)

and if you don't care about priorities at all, you can use:

func SetTargetTermsPlain[K, T, P comparable](tx *Tx, indexInfo *IndexInfo[K, T, P], target K, terms []T)

Example usage:

// collect the terms-priority mapping somehow from the text on the current page
terms := collectPageKeywordPriorities(page.Content)
// update the keywords index
vbolt.SetTargetTerms(tx, KeywordsIndex, page.Number, terms)

Iterate targets for a term

Given a term, we want to read the targets ordered by priority, with the option of starting at an offset, or a specific key, and the option of limiting the number of targets loaded

type Window struct {
	Limit     int // 0 means unlimited
	Offset    int // if both offset and cursor are set, cursor is used
	Cursor    []byte
	Direction IterationDirection
}

type IterationDirection uint8

const IterateRegular = IterationDirection(0)
const IterateReverse = IterationDirection(1)

func ReadTermTargets[K, T, P comparable](tx *Tx, indexInfo *IndexInfo[K, T, P], term T, targets *[]K, window Window) []byte

If we expect the term to not have many targets and we can load all of them at once, then we don't have to worry about the window. However, the reason we do have the concept of an index in the first place is that we expect the list of targets to be large, so we need some method of controlling its pagination.

The simplest way is using an offset, limit pair. But a more robust way is to use a start key. Because the Index relies on the B-Tree implementation, and because the keys are sorted such that all targets for a term appear in sequence in the B-Tree, we can have faster iteration by remember the literal byte key we stopped at in the previous pagination step.

Note that if the supplied window.StartByte is not valid for the given term, the function will exit early and nothing will be added to targets.

The return value from ReadTermTargets is a []byte representing the starting point for the iteration cursor if we want to load the next page quickly.

In the context of a web application, this []byte can be encoded to base64 to be sent to the client as an opaque "cursor".

Example usage:

// assuming query.Cursor represents the query parameter "cursor" from the http request
var startKey = base64.RawURLEncoding.DecodeString(query.Cursor)
var window = vbolt.Window{ StartKey: startKey, Limit: 10 }
var pageNumbers = make([]int, 0, 10)
var nextKey = vbolt.ReadTermTargets(tx, KeywordsIndex, query.Term, &pageNumbers, window)
var nextCursor = base64.RawURLEncoding.EncodeToString(nextKey)

// load pages via pageNumbers
var pages []Page
vbolt.ReadSlice(tx, PagesBucket, pageNumbers, &pages)

Counts

The index automatically keeps track of "counts": how many targets are currently assigned to a specific term

func ReadTermCount[K, T, P comparable](tx *Tx, indexInfo *IndexInfo[K, T, P], term *T, count *int) bool

Example usage (continuing with the keywords example)

var pagesCount int
vbolt.ReadTermCount(tx, KeywordsIndex, query.Term, &pagesCount)

Notes

You should not use indices to store "source of truth" kind of data. The data you store in the index should be deriveable from the source object.

The next section should clarify this point.

Modeling relationships

Below we discuss some of the most common use cases and how to model them.

Modeling one to many relationships

Suppose an instance of type A refers to many instance of type B, such that it's not many-to-many. That is, if some instance b0 of type B is referred to by an instance a0 of A, then there's no other instance of A that also refers to b0.

How do we model such a thing in vBolt?

You have a few choices, but the most obvious are:

Modeling many to many relationships

For many to many relationships, both A and B refer to each other without limit, however, usually one of them will have fewer references than the other. For example, imagine a blog website: each article belongs to one or more categories, but there are far more articles than there are categories, and while an article might belong to three categories, a category can have hundreds or thousands of articles. So it makes sense to store the categoryIds on the article and use the index to get from the category to the articles.

Your first job is to identify which object id constitutes the term to the index, and which constitutes the target, based on the criteria explained above.

In this case, the Article is the target and the Category is the term.

type Category struct {
	Id int
	Name string
	...
}

type Article struct {
	Id name
	...
	CategoryIds []int
}

var ArticleBucket = vbolt.Bucket(&info, "article", vpack.FInt, PackArticle)
var CategoryBucket = vbolt.Bucket(&info, "category", vpack.FInt, PackArticle)
var CategoryArticles = vbolt.Index(&info, "cat=>art", vpack.FInt, vpack.FInt)

// when saving an article
vbolt.Write(tx, ArticleBucket, article.Id, &article)
vbolt.SetTargetTermsPlain(tx, CategoryArticles, article.Id, article.CategoryIds)

// when reading categories from article
var categories []Category
vbolt.ReadSlice(tx, CategoryBucket, article.CategoryIds, &categories)

// when reading articles from category
var window = vbolt.Window { ... }
var articleIds []int
vbolt.ReadTermTargets(tx, CategoryArticles, category.Id, &articleIds, window)

var articles []Article
vbolt.ReadSlice(tx, ArticleBucket, articleIds, &articles)

Pre-Computation

When designing a low latency system, pre-computation is an important component. You sacrifice disk space to gain computation time.

Index is for acceleration, not a source of truth

Notice that we only use the index as an acceleration structure. We never store the source data on the index.

For example, to model the relationships between articles and categories, we stored the categoryIds on the Article. In theory, we can retrive all articles ids associated with a category id by iterate all articles and checking the categoryIds field, but that would be very inefficient, so we use the index to store the reverse relationship.

vbolt.SetTargetTermsPlain(tx, CategoryArticles, article.Id, article.CategoryIds)

What this line does is essentially facilitate the pre-computation of the list of article ids associated with category ids.

If the index data is gone for some reason, we can rebuild it by iterating on all articles and calling SetTargetTerms

Summary Objects

Suppose you're viewing the paginated view of the articles included in a certain category, and the list contains, say, 30 articles per page.

You probably don't want to load the entire article each time and send it over the network to the client. They probably won't even read them. It's a lot of wasted resources for both the server, the network bandwidth, and the client.

Instead you want some kind of ArticleSummary object, that just contains the title, the subtitle, a short summary, and the publication date.

Should you produce the article summary after you load the object? Remember in the sample code above, we did this:

var articles []Article
vbolt.ReadSlice(tx, ArticleBucket, articleIds, &articles)

We could call a function to summerize each article at this point.

var summaries []ArticleSummary
for _, article := range articles {
	summaries = append(summaries, SummerizeArticle(article))
}

This would limit the wasted resource for the network and the client, but not for the server: the server now has even more work, first load the entire article, then produce a summary for it.

It would be much better if the summary was pre-computed, and we just loaded the summary.

// type and bucket definitions
type ArticleSummary struct {
	Id int // same as article id
	....
}

var ArticleSummaryBucket = vbolt.Bucket(&info, "article_summary", vpack.FInt, PackArticleSummary)

// when saving an article
var summary = SummerizeArticle(article)
vbolt.Write(tx, ArticleSummaryBucket, article.Id, &summary)

// when loading category articles:
var summaries []ArticleSummary
vbolt.ReadSlice(tx, ArticleSummaryBucket, articleIds, &summaries)

Pre-Compute everything

So much of the resource waste and performance problems in the relational paradigm come from the desire to normalize all data and the obsession with the querying capabilities of the SQL database engine.

The truth is, while the flexibility of SQL is useful when inspecting the data as a user, they are not that useful when operating on the data as a program.

SQL was initially designed as a UI, not as an API.

Which brings me to why I even created this package in the first place.

Motivation & Philosophy

I created this package because I wanted a storage engine that does not suffer from impedance mismatch between the way application code thinks about data and the way the database thinks about it.

As a bonus, I also wanted a system that does not do a lot of needless paper shuffling busy work.

Consider what happens when you use an ORM to load a simple flat object from an SQL based relational database.

Almost all of the above work is pointless busy work that does not need to happen. Here's what I actually want to happen:

Now consider what has to happen if your data is not simply flat, and does not neatly fit into the format of a table with columns. Consider a structure like the following:


type A struct {
	....
	BItems []B
	X_Ids  []uint64

}

type B struct {
	....
	CItems []C
	Y_Ids  []uint64
}

type C struct {
	.....
	Z_Ids []uint64
}

If you want to handle this kind of data layout through a relational database, you have to write additional code, often very complicated, to map your data back and forth into and from relational tables.

What's worse, you have to do this mapping three times:

Because the shape of the query for each type of operation is totally different. Insert statements are totally different from update statements, and totally different from select statements.

Now, you might say that your ORM library handles it for you, but does it really? I've seen quite a number of ORMs and I don't think any of them handles nested objects really well beyond one level, even in dynamically typed languages.

Even if some ORM can do it, this is still a lot of pointless work that relational databases force your program to do, and a lot of complexity in the ORM code that frankly should not need to exist.

Now it gets worse: what if the nested data (structs B and C in the example above) are almost never loaded as independent units of data by themselves ever? They are always loaded as part of their container object A, and are always updated along with their container object A. Ideally you want to bundle the whole object together even in the storage system, but relational databases don't let you do that.

What we want out of a database layer

We want data storage and retrieval to have a proper programmatic interface (API), not a textual query language.

We want to have complete control over how we store data: whether we bundle all nested objects together with their parent or spread them apart.

We want querying and indexing to be explicit. There are only two types of queries:

To make the index queryable, we build and populate it explicitly.

Although the automatic indexing of SQL sounds appealing, the lack of control, and the imposition of object-relational impedance mismatch, combine to negate (nay, eradicate) all the supposed gains.

This notion of the database engine as "magic" that automatically figures out how to perform queries efficiently is a source of many performance problems. So many dev teams in the industry waste countless hours fire fighting performance problems that arise from such mis-use of the database.

❀ ✒ ❀