Anthony4m

Posted on Feb 9

Dive Into Slotted Pages: Building Efficient Record Management in Go

Hey there, fellow developers! 👋 Ever wonder how databases and storage engines efficiently manage data? Today, we’re diving into a Go implementation of a slotted page a clever structure for organizing records inside fixed-size pages. It’s the secret sauce behind efficient data storage, fast lookups, and compact space management.

Let’s break it down, step by step! 🚀

What’s a Slotted Page? 🤔

A slotted page is a fixed-size container used to store variable-sized records (a.k.a. cells). It’s like a well-organized shelf with numbered slots pointing to items, ensuring efficient storage and retrieval. The core components are:

Header: Metadata like record count, free space, and offsets.
Slots: Array of pointers to records, sorted for fast binary search.
Free Space: Reserved area for storing new records.

+----------------+

The SlottedPage Structure in Go 📦

Here’s the basic structure for our SlottedPage:

type SlottedPage struct {
    *Page            // Base page functionality
    headerSize int   // Size of the header (includes slots)
    cellCount  int   // Number of records (cells)
    freeSpace  int   // Offset for new records
    slots      []int // Array of record offsets (sorted)
}

Key features include:

Embedded Page: Provides raw data storage.
Slots Array: Tracks where each record is located.
Thread Safety: (Inherited from the underlying page implementation.)

Creating a Slotted Page ✨

Here’s how we initialize a new SlottedPage:

func NewSlottedPage(pageSize int) *SlottedPage {
    if pageSize == 0 {
        pageSize = DefaultPageSize
    }

    sp := &SlottedPage{
        Page:       NewPage(pageSize),
        headerSize: PageHeaderSize,
        freeSpace:  pageSize,
        slots:      make([]int, 0),
    }

    // Initialize metadata
    sp.SetInt(0, pageSize)      // Page size
    sp.SetInt(4, PageHeaderSize) // Header size
    sp.SetInt(8, 0)              // Cell count
    sp.SetInt(12, pageSize)      // Free space pointer
    return sp
}

Metadata Initialization: We set up the page size, header size, record count, and free space.
Defaults: If no size is provided, we use a standard page size of 4KB.

Record Management in Action 🔧

Now for the fun part—how do we manage records? Let’s break it down:

Inserting Records 📝

Here’s how records are inserted:

func (sp *SlottedPage) InsertCell(cell *Cell) error {
    cellBytes := cell.ToBytes()
    cellSize := len(cellBytes)

    // Check available space
    if !cell.FitsInPage(sp.freeSpace) {
        return fmt.Errorf("not enough space for cell")
    }

    // Calculate the offset
    newOffset := sp.freeSpace - cellSize

    // Write the record to the calculated offset
    sp.SetBytes(newOffset, cellBytes)

    // Update slots
    insertPos := sp.findSlotPosition(cell.key)
    sp.slots = append(sp.slots[:insertPos], append([]int{newOffset}, sp.slots[insertPos:]...)...)

    // Update metadata
    sp.cellCount++
    sp.freeSpace = newOffset
    sp.SetInt(8, sp.cellCount)
    sp.SetInt(12, sp.freeSpace)
    return nil
}

Space Check: Ensures there’s enough room for the new record.
Offset Calculation: Finds where the record should go.
Slot Update: Inserts the record offset while maintaining sorted order.

Retrieving Records 🔍

You can find a record by key using binary search:

func (sp *SlottedPage) FindCell(key []byte) (*Cell, int, error) {
    low, high := 0, len(sp.slots)-1

    for low <= high {
        mid := (low + high) / 2
        cell, err := sp.GetCell(sp.slots[mid])
        if err != nil {
            return nil, -1, err
        }

        comp := bytes.Compare(key, cell.key)
        if comp == 0 {
            return cell, mid, nil
        } else if comp < 0 {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }

    return nil, -1, fmt.Errorf("key not found")
}

Binary search ensures fast lookups in the sorted slot directory.

Deleting Records 🗑️

When you delete a record, its slot is removed:

func (sp *SlottedPage) DeleteCell(slot int) error {
    if slot >= len(sp.slots) {
        return fmt.Errorf("invalid slot")
    }

    // Mark cell as deleted
    cell, err := sp.GetCell(sp.slots[slot])
    if err != nil {
        return err
    }
    cell.MarkDeleted()

    // Remove slot
    sp.slots = append(sp.slots[:slot], sp.slots[slot+1:]...)
    sp.cellCount--
    err = sp.SetInt(8, sp.cellCount)
    if err != nil {
        return err
    }
    return nil
}

Mark as Deleted: The slot is removed, and the record count is updated.

Compacting the Page 🧹

Over time, deleting records leaves gaps. Compaction reorganizes the page to reclaim space:

func (sp *SlottedPage) Compact() error {
    newPage := NewSlottedPage(len(sp.data))

    for _, offset := range sp.slots {
        cell, err := sp.GetCell(offset)
        if err != nil {
            return err
        }
        if !cell.IsDeleted() {
            newPage.InsertCell(cell)
        }
    }

    // Replace old page data
    sp.data = newPage.data
    sp.slots = newPage.slots
    sp.cellCount = newPage.cellCount
    sp.freeSpace = newPage.freeSpace

    return nil
}

Compaction:

Copies non-deleted records to a new page.
Defragments the free space.

Why Slotted Pages? 💡

This implementation shines in real-world applications:

Database Engines: Store and retrieve records efficiently.
File Systems: Manage disk blocks and defragmentation.
Caching Systems: Organize data into fixed-size chunks for quick access.
Custom Storage Layers: Build a foundation for structured data storage.

Wrapping Up 🎯

Slotted pages are a powerful yet elegant solution for managing variable-sized records in fixed-size pages. With efficient key-based lookups, space management, and support for deletion/compaction, this implementation can serve as the backbone of your next database or storage project.
Building a slotted page system is a fascinating journey into database internals. This implementation provides a solid foundation for building more complex database features like:

B-tree indexes
MVCC (Multi-Version Concurrency Control)
Transaction management

Ready to build your own database engine? This slotted page implementation is a great place to start! 💪

Next Steps:

Extend with Compression: Add support for compressed records.
Optimize Caching: Build a caching layer for frequently accessed pages.
Broaden Data Support: Add support for more complex types like floats or custom structs.

DEV Community