externalsort

README

external-sort

external-sort performs bounded external sorting of fixed-size opaque records while encrypting every temporary record with AES-256-GCM. It is intended for large reconciliation and migration datasets that cannot safely be retained in memory or written to plaintext temporary files.

Installation

go get github.com/faustbrian/go-external-sort@v1

Quick start

See the compiler-checked package example for a complete runnable setup that creates a store, adds fixed-width records, consumes them in sorted order, and closes all owned resources.

The parent directory must already exist, must not be a symlink, and must have no group or other permission bits. Existing ancestor links are resolved when the factory is created. Opening a store binds the resolved directory to a rooted handle and revalidates its recorded identity and permissions; subsequent storage and cleanup remain relative to that handle. The key must contain exactly 32 bytes.

Module and package map

This repository contains one Go module, github.com/faustbrian/go-external-sort, with the sole public root package externalsort. It has no subpackages or optional adapter modules.

Guarantees

• fixed record size and explicit total-record limit;
• bounded contiguous in-memory chunks;
• at most 64 files in one merge;
• lexicographic byte ordering with duplicates preserved;
• a random-seeded process-unique nonce domain, a retry-safe record counter, and AES-256-GCM authentication for every temporary record;
• authentication of store identity, format version, chunk, ordinal, and record size;
• exact owner-only temporary modes (0700 directories and 0600 files), independent of process umask;
• descriptor-relative storage and cleanup that cannot be redirected by a renamed or replaced parent pathname ancestor; and
• complete temporary-directory removal after a successful Close.

Stores permit one active lifecycle operation. While open, overlapping or reentrant calls fail with ErrConcurrentUse; callers can retry after the active operation returns. Once closing begins, input and iteration return ErrClosed. A record passed to the iteration callback is valid only until that callback returns. Copy it when retention is required.

When to use this package

Use this module when the data is fixed-width, sorting must be bounded, and plaintext spill files are unacceptable. Prefer an in-memory sort for small, public datasets. This implementation deliberately rejects configurations that need more than 64 chunks instead of hiding an unbounded or multi-pass merge. Increase the chunk size within the declared byte ceiling or partition the dataset at a higher semantic layer.

Close removes process-owned artifacts, but no process can guarantee cleanup after abrupt termination or host loss. Operators should place the parent on an encrypted ephemeral filesystem and apply the descriptor-relative ownership and age checks in the operations guide before removing stale directories.

Documentation

For shared package selection, ownership, and lifecycle guidance, see the versioned Golib ecosystem index and its Integration and data movement family.

• API and lifecycle
• Architecture and file format
• Adoption and migration
• Compatibility
• Threat model
• Performance
• Operations and Kubernetes
• FAQ
• Support
• Security policy
• Release notes

Development

Use Go 1.27.2 for development; the public minimum remains Go 1.27.0. Ordinary go test ./... works in a standalone checkout. make check and make ci use bounded local checks with the public pinned verifier and a focused race selection for lifecycle exclusion, cancellation and reader cleanup. make check-full retains online specification checks and full configured assurance. See CONTRIBUTING.md for focused two-second fuzzing, optional root-package mutation and selected release checks.

License

MIT. See LICENSE.

Documentation navigation

Complete documentation map · Current source package map

Use the versioned ecosystem entry for package selection. The frozen compatibility cohort is separate from current package releases and unpublished source changes. Adopting them does not silently update that cohort.

Documentation

Overview

Package externalsort sorts fixed-size records in lexicographic byte order using bounded chunks encrypted with AES-256-GCM in owner-only temporary storage. Start with NewFactory and Factory.Open, add records, iterate once with Store.ForEachSorted, and close every non-nil Store, even after a failed Open. Callback records are borrowed plaintext and must be copied before retention.

The package owns per-store storage and cleanup, not record encoding, key derivation, atomic output publication or crash recovery. Callers must protect process memory, isolate a trusted parent directory and coordinate shutdown. Context cancellation is cooperative; it cannot interrupt synchronous IO, entropy reads, sorting or a blocked callback. No goroutines, external service or cgo are introduced. Factory.Open refuses js and plan9 because rooted filesystem containment is unavailable there.

Example

package main

import (
	"bytes"
	"context"
	"fmt"
	"os"

	externalsort "github.com/faustbrian/go-external-sort"
)

func main() {
	parent, err := os.MkdirTemp("", "external-sort-example-")
	if err != nil {
		panic(err)
	}
	defer func() {
		if err := os.RemoveAll(parent); err != nil {
			panic(err)
		}
	}()

	factory, err := externalsort.NewFactory(externalsort.Config{
		ParentDirectory: parent,
		RecordBytes:     2,
		ChunkRecords:    2,
		MaximumRecords:  3,
	})
	if err != nil {
		panic(err)
	}
	store, err := factory.Open(
		context.Background(),
		bytes.Repeat([]byte{1}, externalsort.AES256KeyBytes),
	)
	if store != nil {
		defer func() {
			if err := store.Close(); err != nil {
				panic(err)
			}
		}()
	}
	if err != nil {
		panic(err)
	}

	for _, record := range [][]byte{{3, 3}, {1, 1}, {2, 2}} {
		if err := store.Add(context.Background(), record); err != nil {
			panic(err)
		}
	}
	if err := store.ForEachSorted(
		context.Background(),
		func(record []byte) error {
			fmt.Printf("%x\n", record)

			return nil
		},
	); err != nil {
		panic(err)
	}

}

Output:
0101
0202
0303

Index

• Constants
• Variables
• type Config
• type Factory
  • func NewFactory(config Config) (*Factory, error)
  • func (Factory) GoString() string
  • func (Factory) LogValue() slog.Value
  • func (Factory) MarshalJSON() ([]byte, error)
  • func (factory *Factory) Open(ctx context.Context, key []byte) (*Store, error)
  • func (Factory) String() string
• type Store
  • func (store *Store) Add(ctx context.Context, record []byte) error
  • func (store *Store) Close() error
  • func (store *Store) ForEachSorted(ctx context.Context, yield func([]byte) error) (result error)
  • func (Store) GoString() string
  • func (Store) LogValue() slog.Value
  • func (Store) MarshalJSON() ([]byte, error)
  • func (Store) String() string

Examples

• Package

Constants

const (
	// AES256KeyBytes is the exact key size accepted by Factory.Open.
	AES256KeyBytes = 32
	// MaximumMergeFiles is the hard upper bound for one merge fan-in.
	MaximumMergeFiles = 64
	// MaximumRecordBytes bounds one fixed-size record.
	MaximumRecordBytes = 1 << 20
	// MaximumChunkRecords bounds the number of records held in memory.
	MaximumChunkRecords = 1_000_000
	// MaximumChunkBytes bounds the contiguous in-memory sort buffer.
	MaximumChunkBytes = 256 << 20
)

Variables

var (
	// ErrInvalidConfiguration reports invalid bounds, nil required inputs or an
	// unconstructed Factory/Store.
	ErrInvalidConfiguration = errors.New(
		"external sort configuration is invalid",
	)
	// ErrUnsafeParent reports a missing, replaced or insufficiently restricted
	// parent directory, or a platform without supported rooted containment.
	ErrUnsafeParent = errors.New(
		"external sort parent is not an owner-only directory",
	)
	// ErrInvalidKey reports a key whose length is not AES256KeyBytes.
	ErrInvalidKey = errors.New("external sort key is invalid")
	// ErrInvalidRecord reports a record whose length differs from Config.RecordBytes.
	ErrInvalidRecord = errors.New("external sort record is invalid")
	// ErrRecordLimit reports an Add beyond Config.MaximumRecords.
	ErrRecordLimit = errors.New("external sort record limit reached")
	// ErrConcurrentUse reports overlap with an active store lifecycle operation.
	ErrConcurrentUse = errors.New("external sort store is already in use")
	// ErrClosed reports input or iteration attempted after closing begins,
	// including cleanup-only handles returned by a failed Open.
	ErrClosed = errors.New("external sort store is closed")
	// ErrFinalized reports input or iteration attempted after finalization.
	ErrFinalized = errors.New("external sort store is finalized")
	// ErrEntropy reports failed randomness or exhausted nonce uniqueness state.
	ErrEntropy = errors.New("external sort entropy failed")
	// ErrStorage reports owned IO or cleanup failure without exposing paths
	// or wrapping underlying filesystem errors.
	ErrStorage = errors.New("external sort storage failed")
	// ErrCorrupt reports invalid encrypted framing or authentication,
	// including unexpected truncation or trailing bytes.
	ErrCorrupt = errors.New("external sort chunk is corrupt")
)

Types

type Config

type Config struct {
	// ParentDirectory is an existing absolute directory with no group/other
	// permission bits. Its final component must not be a symlink; ancestor
	// links are resolved at construction. The caller must exclude hostile writers.
	ParentDirectory string
	// RecordBytes is the exact positive record width, at most MaximumRecordBytes.
	RecordBytes int
	// ChunkRecords is the positive in-memory record capacity, at most
	// MaximumChunkRecords. RecordBytes * ChunkRecords must fit MaximumChunkBytes.
	ChunkRecords int
	// MaximumRecords is the total input ceiling, at least ChunkRecords.
	// The rounded-up chunk count must not exceed MaximumMergeFiles.
	MaximumRecords int
}

Config declares per-store storage and buffer bounds. There are no defaults; the zero value is invalid. These bounds do not limit process-wide memory, caller copies, cryptographic scratch or the number of concurrent stores.

type Factory

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

Factory holds a validated reusable policy and parent-directory identity. Obtain it from NewFactory; its zero value cannot Open a store. It is safe for concurrent Open calls, which create independent stores. The factory owns no open directory handle or Close obligation; every store owns its own resources.

func NewFactory

func NewFactory(config Config) (*Factory, error)

NewFactory copies config after validating its bounds and existing absolute parent directory. The final parent component must not be a symlink and its group/other permission bits must be clear. Existing ancestor links are resolved once; Open revalidates the resolved directory's identity and permissions. Invalid bounds return nil and ErrInvalidConfiguration; filesystem/parent validation failures return nil and ErrUnsafeParent without revealing paths. No OS-owner or hostile-writer isolation check is performed.

func (Factory) GoString

func (Factory) GoString() string

GoString prevents configuration and temporary paths from entering debug representations.

func (Factory) LogValue

func (Factory) LogValue() slog.Value

LogValue prevents configuration and temporary paths from entering slog.

func (Factory) MarshalJSON

func (Factory) MarshalJSON() ([]byte, error)

MarshalJSON prevents configuration and temporary paths from entering JSON.

func (*Factory) Open

func (factory *Factory) Open(
	ctx context.Context,
	key []byte,
) (*Store, error)

Open creates an independent store with a rooted parent handle, owner-only work directory and bounded plaintext buffer. ctx must be non-nil and key must have AES256KeyBytes bytes; nil/zero factories return ErrInvalidConfiguration. Key bytes are consumed during cipher construction, not retained as the input slice. Do not mutate key during Open. The caller owns its lifetime; cipher schedules are not securely erased. Use an independently derived key per dataset across processes/restarts.

Open checks cancellation cooperatively and returns context errors directly. Parent validation, entropy and storage failures use ErrUnsafeParent, ErrEntropy and ErrStorage. On js/plan9, rooted storage returns ErrUnsafeParent. These errors do not wrap sensitive underlying IO values.

The caller must Close every non-nil Store, including one returned with an error: failed construction cleanup can leave an owned cleanup-only handle. Such a handle rejects Add/ForEachSorted with ErrClosed and retries removal through Close. A nil Store transfers no resource ownership.

func (Factory) String

func (Factory) String() string

String prevents configuration and temporary paths from entering text logs.

type Store

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

Store owns encrypted temporary chunks for one sort; obtain it from Factory.Open. Its zero value is invalid. Copies of Store share the same lifecycle and resources; they are not independent sorts. The caller owns Close.

One lifecycle operation is admitted at a time. While open, overlap/reentry returns ErrConcurrentUse; input/iteration after closing begins returns ErrClosed. Close also rejects overlap and does not interrupt active work. No store lock is held across IO or callbacks and no goroutine starts. Callback records are borrowed plaintext, cleared when the callback returns.

func (*Store) Add

func (store *Store) Add(ctx context.Context, record []byte) error

Add copies one exact Config.RecordBytes record into the bounded chunk. The caller may reuse the slice after return, but must not mutate it during Add. A full chunk is sorted and encrypted to disk before Add returns. Nil store or context returns ErrInvalidConfiguration; wrong width returns ErrInvalidRecord, and exceeding MaximumRecords returns ErrRecordLimit. Lifecycle errors are ErrConcurrentUse, ErrClosed and ErrFinalized.

A failed Add does not accept the new record and preserves previously accepted records. It may be retried after cancellation, entropy or storage failure unless partial-file cleanup fails, which permits only Close. Spill retries consume new nonce counters rather than reusing a failed attempt's nonce. Context errors pass through; owned IO failures use payload-free sentinels.

func (*Store) Close

func (store *Store) Close() error

Close clears buffered plaintext, removes the work directory and releases the rooted handle. A nil Store succeeds; an unconstructed zero Store returns ErrInvalidConfiguration. Close rejects active operations with ErrConcurrentUse instead of waiting or interrupting them. It has no context and can block in IO.

Once closing begins, Add/ForEachSorted return ErrClosed. A removal failure returns ErrStorage and leaves only Close retryable. After successful removal, state is finalized even if rooted-handle closure reports ErrStorage; later Close calls return nil without retrying that handle. Otherwise repeated Close is idempotent. Dropping cipher references is not secure key-memory erasure, and process death can bypass cleanup entirely.

func (*Store) ForEachSorted

func (store *Store) ForEachSorted(
	ctx context.Context,
	yield func([]byte) error,
) (result error)

ForEachSorted finalizes input and calls yield synchronously for every record in ascending full-record byte order, preserving duplicates. There is no custom comparator or key-only stable-sort contract. Empty input succeeds without a callback. A nil store, context or yield returns ErrInvalidConfiguration.

Each callback slice is cleared on return, including panic; copy before retaining it. Callback errors and context errors pass through unchanged and callback panics propagate after plaintext is cleared and reader closure is attempted. A blocked callback can delay cancellation; reentrant lifecycle calls on this store are rejected, not awaited. Cancellation after the final checkpoint need not turn otherwise successful iteration into an error.

Output is not atomic: corruption, storage, cancellation or callback failure can follow records already yielded. Reader-close failure can return ErrStorage even after complete output; it does not override an earlier iteration error. Once pending input is spilled, the store remains finalized even on failure, including empty input. Further Add/ForEachSorted calls return ErrFinalized. A pre-finalization failure is retryable only if cleanup has not sealed the store. The caller must Close on every path; iteration does not delete chunks.

func (Store) GoString

func (Store) GoString() string

GoString prevents records, cipher state, and temporary paths from entering debug representations.

func (Store) LogValue

func (Store) LogValue() slog.Value

LogValue prevents records, cipher state, and temporary paths from entering slog.

func (Store) MarshalJSON

func (Store) MarshalJSON() ([]byte, error)

MarshalJSON prevents records, cipher state, and temporary paths from entering JSON.

func (Store) String

func (Store) String() string

String prevents records, cipher state, and temporary paths from entering text logs.