zygaena / coral
|
Files Changesets Issues Pull Requests Releases
root / docs / MSGPACK_DATABASE_PLAN.md
MSGPACK_DATABASE_PLAN.md markdown 310 lines 8.1 KB
Raw

Implementation Plan: MsgPack Package Database Indexes

Date: 2026-01-29
Status: Planned
Target: Coral v0.2

Overview

Implement the MsgPack-based package database indexes that were planned as the key feature of Coral v0.2. Currently src/core/pkgdb.reef is entirely stubs that fall back to slow file scanning. This causes:

  • coral list - O(N) TOML file reads
  • coral owner - O(N*M) full scan of all packages' file lists (CRITICAL bottleneck)
  • coral info - O(1) but requires TOML parsing

Target Performance

Command Current With MsgPack
coral list (100 pkgs) ~500ms ~10ms
coral owner /usr/bin/vim (50K files) ~2000ms ~1ms
coral info vim ~50ms ~5ms

File Format Specifications

packages.db (MsgPack + Base64)

Structure:
{
  "version": 1,
  "generated": "2026-01-29T...",
  "package_count": N,
  "packages": [
    { "name": "vim", "version": "9.1", "release": 1,
      "description": "...", "installed_date": "...", "file_count": 423 },
    ...
  ]
}

files.db (MsgPack + Base64)

Structure:
{
  "version": 1,
  "generated": "2026-01-29T...",
  "file_count": M,
  "files": {
    "usr/bin/vim": "vim",
    "usr/lib/libz.so": "zlib",
    ...
  }
}

Note: Base64 encoding required because Reef's file.readFile()/file.writeFile() work with strings.

Implementation Phases

Phase 1: Foundation (in pkgdb.reef)

Add new types:

type PackagesIndex = struct
    version: int
    generated: string
    package_count: int
    entries: [PkgIndexEntry]
    loaded: bool
end PackagesIndex

type FilesIndex = struct
    version: int
    generated: string
    file_count: int
    file_paths: [string]    // Sorted for binary search
    owners: [string]        // Parallel array - owner at same index
    loaded: bool
end FilesIndex

Add helper functions:

  • base64_encode(buf: [int], length: int): string
  • base64_decode(encoded: string, buf: [int]): int
  • estimate_packages_buffer_size(pkg_count: int): int
  • estimate_files_buffer_size(file_count: int): int

Phase 2: Serialization

Implement MsgPack serialization:

fn serialize_packages_db(root: string): [int]
    // 1. Get list of installed packages from database module
    // 2. Allocate buffer based on count estimate
    // 3. Pack map header (4 keys: version, generated, package_count, packages)
    // 4. Pack array of package entries
    // Returns packed buffer
end serialize_packages_db

fn serialize_files_db(root: string): [int]
    // 1. Get all packages, collect all files with owners
    // 2. Sort file paths for binary search later
    // 3. Allocate buffer
    // 4. Pack map header + files map
    // Returns packed buffer
end serialize_files_db

Implement rebuild_indexes_rooted():

fn rebuild_indexes_rooted(root: string): bool
    // 1. Serialize packages.db, base64 encode, write file
    // 2. Serialize files.db, base64 encode, write file
    // 3. Return success
end rebuild_indexes_rooted

Phase 3: Deserialization

Implement loading functions:

fn load_packages_index(root: string): PackagesIndex
    // 1. Read base64 string from packages.db file
    // 2. Decode to binary buffer
    // 3. Unpack MsgPack structure
    // 4. Return populated PackagesIndex
end load_packages_index

fn load_files_index(root: string): FilesIndex
    // 1. Read base64 string from files.db file
    // 2. Decode to binary buffer
    // 3. Unpack MsgPack map into parallel arrays
    // 4. Return populated FilesIndex (already sorted from serialize)
end load_files_index

fn binary_search_file(index: FilesIndex, path: string): string
    // O(log N) binary search in sorted file_paths array
    // Return owner or empty string
end binary_search_file

Phase 4: Update Public API

Replace stub implementations:

fn list_packages(names: [string], versions: [string], max_count: int): int
    let index = load_packages_index("")
    if not index.loaded
        return fallback_list_packages(names, versions, max_count)
    end if
    // Copy from index to arrays
end list_packages

fn find_file_owner(file_path: string): string
    let index = load_files_index("")
    if not index.loaded
        return database.find_owner(file_path)  // Fallback
    end if
    return binary_search_file(index, normalize_path(file_path))
end find_file_owner

fn get_indexed_package(name: string): PkgIndexEntry
    let index = load_packages_index("")
    if not index.loaded
        return fallback_get_indexed_package(name)
    end if
    // Search index for package by name
end get_indexed_package

Add rooted variants:

  • find_file_owner_rooted(file_path: string, root: string): string

Phase 5: Command Integration

install.reef - After registering package:

// Rebuild indexes after install
pkgdb.rebuild_indexes_rooted(root_path)

remove.reef - After unregistering package:

// Rebuild indexes after remove
pkgdb.rebuild_indexes_rooted(root_path)

owner.reef - Use indexed lookup:

// Change from database.find_owner() to pkgdb.find_file_owner()

Files to Modify

File Changes
src/core/pkgdb.reef Main implementation - add types, serialization, deserialization, binary search
src/commands/install.reef Call rebuild_indexes_rooted() after registration
src/commands/remove.reef Call rebuild_indexes_rooted() after unregistration
src/commands/owner.reef Use pkgdb.find_file_owner() instead of database.find_owner()

Key Implementation Details

Base64 Encoding (required for file I/O)

Reef's encoding.base64 module exists in reef-stdlib. Use:

import encoding.base64
let encoded = base64.base64_encode(binary_string)
let decoded = base64.base64_decode(encoded)

Issue: base64 module works with strings, but MsgPack produces [int] buffer. Need conversion helpers.

MsgPack Usage (from reef-stdlib/encoding/msgpack.reef)

import encoding.msgpack

// Packing
let buf = msgpack.msgpack_alloc_buffer(size)
let pos = 0
pos = pos + msgpack.msgpack_pack_map_header(4, buf, pos)
pos = pos + msgpack.msgpack_pack_string("version", buf, pos)
pos = pos + msgpack.msgpack_pack_int(1, buf, pos)
// ... etc

// Unpacking
let map_len = msgpack.msgpack_unpack_map_len(buf, offset)
offset = offset + msgpack.msgpack_value_size(buf, offset)
// ... iterate through map entries

Buffer to String Conversion

Need helper to convert [int] buffer to string for base64:

fn buffer_to_string(buf: [int], length: int): string
    mut result = ""
    mut i = 0
    while i < length
        result = result + chr(buf[i])
        i = i + 1
    end while
    return result
end buffer_to_string

Verification

Test Commands

# Initialize database (should create packages.db and files.db)
sudo coral --root /tmp/coral-chroot db init
ls -la /tmp/coral-chroot/var/lib/coral/db/

# Verify files exist
file /tmp/coral-chroot/var/lib/coral/db/packages.db
file /tmp/coral-chroot/var/lib/coral/db/files.db

# Build and install a test package
coral build core/zlib
sudo coral --root /tmp/coral-chroot install zlib

# Verify index updated
sudo coral --root /tmp/coral-chroot db status

# Test fast list
time sudo coral --root /tmp/coral-chroot list

# Test fast owner lookup
time sudo coral --root /tmp/coral-chroot owner /usr/lib/libz.so

# Test rebuild from scratch
sudo rm /tmp/coral-chroot/var/lib/coral/db/*.db
sudo coral --root /tmp/coral-chroot db rebuild

Performance Validation

  • coral list with 100 packages should complete in <50ms
  • coral owner should complete in <10ms regardless of file count
  • Index files should be created after install/remove

Design Decisions

  1. Full Rebuild on Changes: Each install/remove triggers a complete index rebuild. Simpler, always consistent, acceptable performance for typical package counts (<500 packages).

  2. Trust the Index: Commands trust the index is correct. If indexes get out of sync (e.g., manual edits to installed/ directory), user runs coral db rebuild to fix.

  3. No Caching: Reload index from disk on each command invocation. Keeps implementation simple and avoids stale memory issues.