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.

Quick start

factory, err := externalsort.NewFactory(externalsort.Config{
    ParentDirectory: "/run/private/reconciliation",
    RecordBytes:     32,
    ChunkRecords:    100_000,
    MaximumRecords:  5_000_000,
})
if err != nil {
    return err
}

store, err := factory.Open(ctx, derivedAES256Key)
if store != nil {
    defer store.Close()
}
if err != nil {
    return err
}

if err := store.Add(ctx, digest[:]); err != nil {
    return err
}
return store.ForEachSorted(ctx, func(record []byte) error {
    return consume(record)
})

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; each store binds the resolved directory to a rooted handle and rejects later identity or permission changes. The key must contain exactly 32 bytes.

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. Overlapping or reentrant calls fail with ErrConcurrentUse; callers can retry after the active operation returns. A record passed to the iteration callback is valid only until that callback returns. Copy it when retention is required.

Adoption and tradeoffs

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

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

License

MIT. See LICENSE.

Ecosystem

Use the Golib documentation portal to choose companion packages, supported stacks, recipes, and operations guidance.

Documentation

Overview

Package externalsort provides bounded external sorting for fixed-size records encrypted at rest in owner-only temporary storage.

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 = errors.New(
		"external sort configuration is invalid",
	)
	ErrUnsafeParent = errors.New(
		"external sort parent is not an owner-only directory",
	)
	ErrInvalidKey    = errors.New("external sort key is invalid")
	ErrInvalidRecord = errors.New("external sort record is invalid")
	ErrRecordLimit   = errors.New("external sort record limit reached")
	ErrConcurrentUse = errors.New("external sort store is already in use")
	ErrClosed        = errors.New("external sort store is closed")
	ErrFinalized     = errors.New("external sort store is finalized")
	ErrEntropy       = errors.New("external sort entropy failed")
	ErrStorage       = errors.New("external sort storage failed")
	ErrCorrupt       = errors.New("external sort chunk is corrupt")
)

Types

type Config

type Config struct {
	ParentDirectory string
	RecordBytes     int
	ChunkRecords    int
	MaximumRecords  int
}

Config declares every storage and memory bound before temporary storage is opened. MaximumRecords divided into ChunkRecords MUST fit one merge of at most MaximumMergeFiles.

type Factory

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

Factory validates a reusable external-sort storage policy. Factory is safe for concurrent use. Each Store permits one active lifecycle operation.

func NewFactory

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

NewFactory validates bounds and requires an existing non-symlink parent whose group and other permission bits are clear.

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 one owner-only temporary work directory. The caller provides an AES-256 key for immediate cipher construction. The caller MUST call Close whenever Open returns a non-nil Store, including together with an error; an error result can carry ownership of construction residue whose first removal attempt failed.

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. Overlapping or reentrant lifecycle calls return ErrConcurrentUse. A record passed to the ForEachSorted callback is valid only until that callback returns.

func (*Store) Add

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

Add copies one record into the bounded in-memory chunk. A failed Add does not retain the supplied record and may be retried unless temporary cleanup fails, in which case only Close is accepted.

func (*Store) Close

func (store *Store) Close() error

Close clears in-memory records and removes the complete work directory. It is idempotent. A storage failure leaves the store closable so cleanup can be retried, but no other operation is accepted after closing begins.

func (*Store) ForEachSorted

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

ForEachSorted finalizes input and yields every record in ascending byte order. Duplicate records are preserved. Once pending input is spilled, the store remains finalized even when merge iteration, authentication, cancellation, or the callback fails.

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.