arc

README

Arc: Space-Optimized Database

Arc is a lightweight key-value database optimized for storage efficiency. It combines a Radix tree for space-efficient key indexing with content-aware blob storage that stores only unique content. While implemented in Go, Arc's simple file format is designed to be platform-agnostic and easily usable from any programming language.

🚧 Arc is currently in active development. We plan to announce its readiness for general availability when appropriate. Stay tuned for updates.

Design Principles

Arc is designed on two core principles: space efficiency and universal accessibility. The space efficiency goal is achieved through prefix compression in the Radix tree, content-aware blob storage that stores only unique content, and lazy-loading to reduce memory footprint. The accessibility goal is tackled through a simple, platform-agnostic file format that any programming language can read and write without special bindings.

Concurrency Model

The Go implementation of Arc employs a single-writer, multi-reader concurrency model. This allows concurrent read access without locking, while ensuring data consistency by serializing write operations. Other implementations of Arc may adopt different concurrency models to better support certain performance characteristics.

Persistence Model

Arc employs a dual-representation persistence model. It can maintain a complete in-memory representation of the Radix tree for fast operations, while also supporting lazy-loading from its platform-agnostic file format. The goal for the initial version is to persist in-memory changes by writing the entire tree to disk in a single operation. Future versions will support in-place and partial flushing while maintaining backwards compatibility with the existing file format.

Data Integrity

Arc ensures data integrity using IEEE CRC32 checksums. These checksums detect potential corruption in both the in-memory Radix tree structure and the persisted data. The verification occurs during regular operations and data persistence, providing comprehensive coverage across all tree nodes. While CRC32 is robust for detecting accidental corruption, it is not designed to detect deliberate tampering.

Contributing

Contributions of any kind are welcome. If you're submitting a PR, please follow Go's commit message structure.

Documentation

Overview

Package arc implements a key-value database based on a Radix tree data structure and deduplication-enabled blob storage. The Radix tree provides space-efficient key management through prefix compression, while the blob storage handles values with automatic deduplication.

Index

• Variables
• type Arc
  • func New() *Arc
  • func (a *Arc) Add(key []byte, value []byte) error
  • func (a *Arc) DebugPrint()
  • func (a *Arc) Delete(key []byte) error
  • func (a *Arc) Get(key []byte) ([]byte, error)
  • func (a *Arc) Len() int
  • func (a *Arc) Put(key []byte, value []byte) error

Variables

var (
	// ErrCorrupted is returned when a database corruption is detected.
	ErrCorrupted = errors.New("database corruption detected")

	// ErrDuplicateKey is returned when an insertion is attempted using a
	// key that already exists in the database.
	ErrDuplicateKey = errors.New("cannot insert duplicate key")

	// ErrInvalidChecksum is returned when the node checksum is invalid.
	ErrInvalidChecksum = errors.New("invalid checksum detected")

	// ErrKeyNotFound is returned when the key does not exist in the index.
	ErrKeyNotFound = errors.New("key not found")

	// ErrKeyTooLarge is returned when the key size exceeds the 64KB limit.
	ErrKeyTooLarge = errors.New("key is too large")

	// ErrNilKey is returned when an insertion is attempted using a nil key.
	ErrNilKey = errors.New("key cannot be nil")

	// ErrNodeCorrupted is returned when an index node corruption is detected.
	ErrNodeCorrupted = errors.New("index node corruption detected")

	// ErrValueTooLarge is returned when the value size exceeds the 4GB limit.
	ErrValueTooLarge = errors.New("value is too large")
)

Types

type Arc

type Arc struct {
	// contains filtered or unexported fields
}

Arc represents the API interface of a space-efficient key-value database that combines a Radix tree for key indexing and a space-optimized blob store.

func New

func New() *Arc

New returns an empty Arc database handler.

func (*Arc) Add

func (a *Arc) Add(key []byte, value []byte) error

Add inserts a new key-value pair in the database. It returns ErrDuplicateKey if the key already exists.

func (*Arc) DebugPrint

func (a *Arc) DebugPrint()

DebugPrint prints the Arc index structure in a directory tree format. Use this function only for development and debugging purposes.

func (*Arc) Delete

func (a *Arc) Delete(key []byte) error

Delete removes a record that matches the given key.

func (*Arc) Get

func (a *Arc) Get(key []byte) ([]byte, error)

Get retrieves the value that matches the given key. Returns ErrKeyNotFound if the key does not exist.

func (*Arc) Len

func (a *Arc) Len() int

Len returns the number of records.

func (*Arc) Put

func (a *Arc) Put(key []byte, value []byte) error

Put inserts or updates a key-value pair in the database.