smol

README

smol

smol is a key-value database written in Go, based on copy-on-write B+ tree.

Status

This project is currently under active development. But the kv package is ready for use.

kv Package

The kv package provides a disk-based key-value store with:

• Ordered Storage: Keys maintained in lexicographic order via cow B+ tree
• MVCC Snapshots: Concurrent reads and writes with snapshot isolation
• Transactions: Read Committed isolation level with rollback support
• Flexible Size: No hard limit on key/value sizes (recommended: keys < 3258 bytes, values < 13092 bytes)
• File Size: Minimum 32 KiB, theoretical maximum 64 TiB

The file format specification is defined in the ksy directory and can be visualized with Kaitai Struct.

Installation

go get github.com/dacapoday/smol/kv

Get Started

package main

import (
    "fmt"
    "log"

    "github.com/dacapoday/smol/kv"
)

func main() {
    // Open or create a database file
    db, err := kv.Open("my-data.kv")
    if err != nil {
        log.Fatal(err)
    }
    defer db.Close()

    // Write a key-value pair
    err = db.Set([]byte("hello"), []byte("world"))
    if err != nil {
        log.Fatal(err)
    }

    // Read the value back
    value, err := db.Get([]byte("hello"))
    if err != nil {
        log.Fatal(err)
    }
    fmt.Printf("hello: %s\n", value)

    // Delete a key by setting value to nil
    err = db.Set([]byte("hello"), nil)
    if err != nil {
        log.Fatal(err)
    }
}

Using Transactions

// Begin a transaction
tx := db.Begin()

// Make multiple changes
tx.Set([]byte("user:1:name"), []byte("dacapoday"))
tx.Set([]byte("user:1:email"), []byte("dacapoday@gmail.com"))

// Read within transaction (sees uncommitted changes)
name, _ := tx.Get([]byte("user:1:name"))
fmt.Printf("Name: %s\n", name)

// Commit atomically applies all changes
err = tx.Commit()
if err != nil {
    log.Fatal(err)
}

// Or use Rollback() to discard all changes

File Format Visualization

The database file format can be visualized and inspected using the Kaitai Struct IDE:

Documentation

Overview

Package smol defines basic interfaces for building key-value database components.

Index

• Variables
• type Block
• type BlockID
• type Checkpoint
• type File
• type ReadOnly
• type ReadWrite

Variables

var (
	ErrOpened              = errors.New("opened")
	ErrClosed              = errors.New("closed")
	ErrFileEmpty           = errors.New("empty file")
	ErrFileTruncated       = errors.New("file truncated")
	ErrUnknownMagicCode    = errors.New("unknown magic code")
	ErrUnsupported         = errors.New("unsupported version")
	ErrInvalidBlockSize    = errors.New("invalid block size")
	ErrInvalidChecksum     = errors.New("invalid checksum")
	ErrInvalidMeta         = errors.New("invalid meta")
	ErrInvalidFreelist     = errors.New("invalid freelist")
	ErrReadOnly            = errors.New("read only")
	ErrOutOfRange          = errors.New("out of range")
	ErrOutOfSpace          = errors.New("out of space")
	ErrInvalidOverflowHead = errors.New("invalid OverflowHead")
	ErrInvalidOverflowPage = errors.New("invalid OverflowPage")
	ErrAllocateFailed      = errors.New("allocate BlockID failed")
)

var CastagnoliCrcTable = crc32.MakeTable(crc32.Castagnoli)

Types

type Block

type Block[C Checkpoint] interface {
	// Close releases the underlying storage.
	// Uncommitted changes are discarded.
	// All Checkpoints must be released before Close.
	// Accessing Block after Close causes undefined behavior.
	Close() error

	// Rollback discards all uncommitted changes.
	Rollback() error

	// Commit persists all changes atomically and returns a Checkpoint.
	// The entry is metadata persisted with the commit.
	Commit(entry []byte) (C, error)

	ReadWrite
}

Block divides storage into fixed-size blocks indexed by BlockID. Requires copy-on-write data structures to work with Commit and Rollback.

type BlockID

type BlockID = uint32

BlockID identifies a block, starting from 2(0 and 1 are reserved).

type Checkpoint

type Checkpoint interface {
	// Acquire increments the reference count.
	Acquire()

	// Release decrements the reference count.
	Release()
}

Checkpoint is reference to commit snapshot.

type File

type File interface {
	io.ReaderAt
	io.WriterAt
	io.Closer

	// Truncate changes the size of the file.
	Truncate(size int64) error

	// Sync commits the current contents of the file to stable storage.
	// Typically, this means flushing the file system's in-memory copy
	// of recently written data to disk.
	Sync() error
}

File provides access to a storage backend for the key-value database. The File interface is the minimum implementation required.

The *os.File type satisfies this interface.

type ReadOnly

type ReadOnly interface {
	// LoadBlock reads a block and returns its content buffer.
	// Equivalent to AllocateBuffer followed by ReadBlock, but the returned buffer
	// is read-only and must not be modified.
	// The buffer must be recycled via RecycleBuffer when no longer needed.
	LoadBlock(blockID BlockID) (buffer []byte, err error)

	// AllocateBuffer allocates a buffer for reading and writing blocks.
	// The buffer must be recycled via RecycleBuffer when no longer needed.
	AllocateBuffer() []byte

	// ReadBlock reads a block using buffer.
	// When reader is provided, access data via reader; otherwise data is copied to buffer.
	// Data received by reader is read-only and only valid during callback execution.
	ReadBlock(blockID BlockID, buffer []byte, reader func(block []byte)) error

	// RecycleBuffer ends the lifecycle of a buffer from AllocateBuffer or LoadBlock.
	// After recycling, do not hold references to the buffer or reuse it.
	// Recycling the same buffer multiple times causes undefined behavior.
	RecycleBuffer(buffer []byte)
}

ReadOnly is a subset of Block interface for reading blocks. Provides buffer for block reading operations. All buffers from AllocateBuffer or LoadBlock must be recycled via RecycleBuffer.

type ReadWrite

type ReadWrite interface {
	ReadOnly

	// PageSize returns the readable and writable range within a block.
	// Buffer read and write operations must stay within PageSize bytes.
	PageSize() int

	// AllocateBlock allocates a new block and returns its BlockID.
	// Blocks allocated by AllocateBlock should be recycled via RecycleBlock when no longer needed.
	//
	// Error Detection:
	// Check that returned BlockID > 1, otherwise an error has occurred.
	// Implementations may optionally provide Error() error method to return the error details.
	//
	// Example:
	//   blockID := block.AllocateBlock()
	//   if blockID < 2 {
	//     if err, ok := block.(interface{ Error() error }); ok {
	//       return err.Error()
	//     }
	//     return errors.New("allocation failed")
	//   }
	AllocateBlock() BlockID

	// RecycleBlock marks a BlockID as no longer needed, paired with AllocateBlock.
	// Recycling the same BlockID multiple times causes undefined behavior.
	RecycleBlock(BlockID)

	// WriteBlock writes buffer to storage at blockID.
	// Like io.WriterAt, but buffer may be modified after return (e.g., encryption).
	// Do not rely on buffer content after writing.
	WriteBlock(blockID BlockID, buffer []byte) error
}

ReadWrite provides a set of methods for reading and writing blocks. It embeds ReadOnly and extends it with write operations and block allocation.