garbage-collecting on-disk object store, supporting higher level KV stores and databases.

Last update: Jun 11, 2022

marble

Garbage-collecting disk-based object-store. See examples/kv.rs for a minimal key-value store built on top of this.

Supports 4 methods:

  • read: designed for low-latency, concurrent reads of objects
  • write_batch: designed for bulky, high-throughput writes of large batches of objects, ideal for compacting write-ahead logs into a set of updates to specific objects. Does not block calls to read except for brief moments where metadata is being updated.
  • maintenance: compacts backing storage files that have become fragmented. Blocks concurrent calls to write_batch but does not block readers any more than write_batch does. Returns the number of successfully rewritten objects.
  • file_statistics: returns statistics about live and total objects in the backing storage files.

Defragmentation is always generational, and will group rewritten objects together. Written objects can be further sharded based on a configured partition_function which allows you to shard objects by ObjectId and the size of the object raw bytes.

Marble solves a pretty basic problem in database storage: storing arbitrary bytes on-disk, getting them back, and defragmenting files.

You can think of it as a KV where keys are non-zero u64's, and values are arbitrary blobs of raw bytes.

Writes are meant to be performed in bulk by some background process. Each call to Marble::write_batch creates at least one new file that stores the objects being written. Multiple calls to fsync occur for each call to write_batch. It is blocking. Object metadata is added to the backing wait-free pagetable incrementally, not atomically, so if you rely on batch atomicity, you should serve the batch's objects directly from a cache of your own until write_batch returns. However, upon crash, batches are recovered atomically.

Reads can continue mostly unblocked while batch writes and maintenance are being handled.

You are responsible for:

  • calling Marble::maintenance at appropriate intervals to defragment storage files.
  • choosing appropriate configuration tunables for your desired space and write amplification.
  • ensuring the Config.partition_function is set to a function that appropriately shards your objects based on their ObjectId and/or size. Ideally, objects that have expected death times will be colocated in a shard so that work spent copying live objects is minimized.
  • allocating and managing free ObjectId's.

If you want to create an industrial database on top of Marble, you will probably also want to add:

  • logging and a write cache for accumulating updates that occasionally get flushed to Marble via write_batch. Remember, each call to write_batch creates at least one new file and fsyncs multiple times, so you should batch calls appropriately. Once the log or write cache has reached an appropriate size, you can have a background thread write a corresponding batch of objects to its storage, and once write_batch returns, the corresponding log segments and write cache can be deleted, as the objects will be available via Marble::read.
  • an appropriate read cache. Marble::read always reads directly from disk.
  • for maximum SSD friendliness, your own log should be configurable to be written to a separate storage device, to avoid comingling writes that have vastly different expected death times.
  • dictionary-based compression for efficiently compressing objects that may be smaller than 64k.

Ideas for getting great garbage collection performance:

  • give certain kinds of objects a certain ObjectId range. for example, tree index nodes can be above 1<<63, and tree leaf nodes can be below that point. The Config.partition_function can return the shard 0 for leaf nodes, and 1 for index nodes, and they will always be written to separate files.
  • WiscKey-style sharding of large items from other items, based on the size of the object. Assign a shard ID based on which power of 2 the object size is.
  • Basically any sharding strategy that tends to group items together that exhibit some amount of locality in terms of expected mutations or overall lifespan.

In short, you get to focus on a bunch of the fun parts of building your own database, without so much effort spent on boring file garbage collection.

GitHub

https://github.com/komora-io/marble
You might also like...

Real-time CLI level meter built in Rust.

Real-time CLI level meter built in Rust.

Meter This is a very simple command line utility written in Rust for measuring the gain of a microphone. It displays the values in dBFS. This is usefu

Jun 19, 2022

Verified Rust for low-level systems code

See Goals for a brief description of the project's goals. Building the project The main project source is in source. tools contains scripts for settin

Jun 9, 2022

Warp is a blazingly fast, Rust-based terminal that makes you and your team more productive at running, debugging, and deploying code and infrastructure.

Warp is a blazingly fast, Rust-based terminal that makes you and your team more productive at running, debugging, and deploying code and infrastructure.

Warp is a blazingly fast, Rust-based terminal that makes you and your team more productive at running, debugging, and deploying code and infrastructure.

Jun 17, 2022

This is a simple lnd poller and web front-end to see and read boosts and boostagrams.

Helipad This package will poll a Lightning LND node for invoices related to Podcasting 2.0 and display them in a web interface. It's intended for use

Apr 7, 2022

Execution of and interaction with external processes and pipelines

subprocess The subprocess library provides facilities for execution of and interaction with external processes and pipelines, inspired by Python's sub

Jun 25, 2022

create and test the style and formatting of text in your terminal applications

 create and test the style and formatting of text in your terminal applications

description: create and test the style and formatting of text in your terminal applications docs: https://docs.rs/termstyle termstyle is a library tha

Jul 3, 2021

Command-Line program that takes images and produces the copy of the image with a thin frame and palette made of the 10 most frequent colors.

Command-Line program that takes images and produces the copy of the image with a thin frame and palette made of the 10 most frequent colors.

paleatra v.0.0.1 Command-Line program that takes an image and produces the copy of the image with a thin frame and palette made of the 10 most frequen

Feb 18, 2022

This is choose, a human-friendly and fast alternative to cut and (sometimes) awk

This is choose, a human-friendly and fast alternative to cut and (sometimes) awk

Choose This is choose, a human-friendly and fast alternative to cut and (sometimes) awk Features terse field selection syntax similar to Python's list

Jun 18, 2022
Related tags
Wrapper around atspi-code to provide higher-level at-spi Rust bindings

atspi Wrapper around atspi-codegen to provide higher-level at-spi Rust bindings. Contributions Take a look at our atspi-codegen crate, and try inpleme

Feb 7, 2022
Source code for our paper "Higher-order finite elements for embedded simulation"
Source code for our paper

Higher-order Finite Elements for Embedded Simulation This repository contains the source code used to produce the results for our paper: Longva, A., L

Dec 26, 2021
A mini paste bin and url shortener written in rust without databases.

pb Build $ cargo build --release Environment Variables PB_DATA: /some/path (Default: ./pb_data) PB_SITE: Url of your site. (Default: http://localhost:

May 15, 2022
Zenith - sort of like top or htop but with zoom-able charts, CPU, GPU, network, and disk usage
Zenith - sort of like top or htop but with zoom-able charts, CPU, GPU, network, and disk usage

Zenith - sort of like top or htop but with zoom-able charts, CPU, GPU, network, and disk usage

Jun 23, 2022
A library for loading and executing PE (Portable Executable) from memory without ever touching the disk

memexec A library for loading and executing PE (Portable Executable) from memory without ever touching the disk This is my own version for specific pr

Jun 17, 2022
Terminal disk space navigator 🔭
Terminal disk space navigator 🔭

Given a path on your hard-drive (which could also be the root path, eg. /). diskonaut scans it and indexes its metadata to memory so that you could explore its contents (even while still scanning!).

Jun 24, 2022
TUI input library supporting multiple backends
TUI input library supporting multiple backends

tui-input WARNING: Most of the functionality is only human tested. A TUI input library supporting multiple backends. This crate can be used with tui-r

Jun 16, 2022
My solutions for the 2021 edition of the Advent of Code, using Rust and SOM (Simple Object Machine)

Advent of Code 2021 These are my solutions for the 2021 edition of the Advent of Code. The solutions are all implemented using both Rust and SOM (Simp

Dec 23, 2021
Low-level Rust library for implementing terminal command line interface, like in embedded systems.

Terminal CLI Need to build an interactive command prompt, with commands, properties and with full autocomplete? This is for you. Example, output only

May 8, 2022
A low-level ncurses wrapper for Rust

ncurses-rs This is a very thin wrapper around the ncurses TUI lib. NOTE: The ncurses lib is terribly unsafe and ncurses-rs is only the lightest wrappe

Jun 11, 2022