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.