Help us shape the future of Go! Take the 2026 Go Developer Survey

capledger

package
v0.23.2 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Oct 25, 2026 License: Apache-2.0 Imports: 14 Imported by: 0

Documentation

Overview

Package capledger is the cap ledger of docs/design/untrusted-content-and-amount-caps.md, section 6.5: dense, insert-once slots in a reserved journal run, one ledger per window, each slot a reserve or a release carrying cum_after, the window's total after it. It is the code of model 17 (spec/tla/caps), whose actions the protocol:caps regions name, and it holds nothing the model does not: a reservation reads the cap-intent (or writes it, after the clock check and the index insert), reads the ledger, looks for a live slot of the attempt, checks the limit and inserts slot n+1, and a loser of the insert reads again.

It sits over a small Store, not over agent's Journal, so the stores' own test suites (the nested modules store/sqlite and store/postgres) can run it across real processes; the agent package adapts a Journal to it (agent/capledger.go). Nothing outside the tests calls it yet: no exported API of bide reaches it.

The ledger relies on two things of the store, and nothing else (model 17's A1 and A2): an Insert of a taken name fails and returns the entry that holds the name (one winner per name), and a Scan returns a prefix of the run in commit order, so a slot is never visible before the one below it. It never relies on a lease, a clock agreement between processes, or a process staying alive. A store that fails is a failure of the call: every error is returned, so a cap is fail closed.

Index

Constants

View Source
const RunPrefix = "@cap/"

RunPrefix starts the ID of every ledger and index run (agent's capRunPrefix is the same string).

Variables

View Source
var (
	// ErrClock is a first intent refused by the clock bound: the driver's window is earlier than the
	// newest recorded one, or later by more than the bound.
	ErrClock = errors.New("capledger: the window is outside the clock bound")
	// ErrOverLimit is a reservation that would take the window over its limit, with no waiver.
	ErrOverLimit = errors.New("capledger: the reservation would exceed the limit")
	// ErrCorrupt is a ledger that breaks its own shape (a gap, a slot out of order, an undecodable
	// slot): a writer that is not this package has been at it. The call fails; nothing is repaired.
	ErrCorrupt = errors.New("capledger: the ledger is corrupt")
	// ErrIntentMismatch is a resume whose request differs from the cap-intent already written for the
	// attempt (another rule, currency, key or amount): the attempt's arguments changed after the decision.
	ErrIntentMismatch = errors.New("capledger: the request differs from the attempt's cap-intent")
	// ErrNotSealed is a release without the proof that the tool never began.
	ErrNotSealed = errors.New("capledger: a release needs the call's began word sealed")
	// ErrUnmarked is a release of the slot of an attempt that is not marked: a retry-safe attempt is
	// never released.
	ErrUnmarked = errors.New("capledger: only a marked attempt is released")
	// ErrContention is a reservation that lost the insert race more often than MaxRetries.
	ErrContention = errors.New("capledger: too many lost slot inserts")
	// ErrInvalid is a request the ledger refuses before it reads or writes anything: a non-positive
	// amount, a negative limit, a currency that is not three upper-case ASCII letters, a name left empty.
	// The caller treats an amount it could not parse, or parsed as negative, as not assessable (the
	// rule's strictest action applies), and never reserves zero.
	ErrInvalid = errors.New("capledger: invalid request")
)

Errors. A store error is returned as it came (wrapped with what was being done); these are the ledger's own refusals.

Functions

func KeyDigest

func KeyDigest(normalized string) string

KeyDigest is the digest of a normalized key: a SHA-256 over a domain tag and the key, so a customer ID is not a run name in a store listing.

func WindowID

func WindowID(k Kind, t time.Time, root string) (string, error)

WindowID is the id of the window of kind k that holds t; for Run it is root, the tree root's run ID.

Types

type Config

type Config struct {
	// Store is the journal the ledger writes.
	Store Store
	// Encode maps a free-text name to a key segment that carries none of the characters run IDs are
	// built with (agent's encodeID).
	Encode func(string) string
	// Clock reads now. It is read at a first intent only.
	Clock func() time.Time
	// Bound is how many windows later than the newest recorded one a first intent's window may be
	// (default one).
	Bound int
	// MaxRetries bounds the lost slot inserts of one reservation or release (default 1000): a loser
	// reads again, so contention costs a retry, and past the bound the call fails closed.
	MaxRetries int
	// MaxViews bounds the ledger runs whose reads are cached (default 256): the least recently used is
	// dropped, and read again from the store when next needed. The cache is a hint, so dropping one costs a read.
	MaxViews int
}

Config configures a Ledger.

type Item

type Item struct {
	Seq  int64
	Name string
	Data []byte
}

Item is one entry of a run: its position, name and bytes.

type Kind

type Kind string

Kind is the kind of window of a rule.

const (
	// Run is one window per run tree: the window id is the root run's ID, and there is no clock.
	Run Kind = "run"
	// Hour is a UTC hour, "2006-01-02T15".
	Hour Kind = "hour"
	// Day is a UTC day, "2006-01-02".
	Day Kind = "day"
)

type Ledger

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

Ledger reserves and releases against cap ledgers in one store. A Ledger is safe for concurrent use; its read cache is a hint and never a source of truth (every write is an insert that the store decides).

func New

func New(cfg Config) *Ledger

New returns a Ledger over cfg.

func (*Ledger) AttemptKey

func (l *Ledger) AttemptKey(run, root, toolUse, attempt string) string

AttemptKey is the attempt's identity as the ledger records it: the run that holds the call's journal (and so its cap-intent), the root of its run tree, the tool-use ID and the attempt ID, each encoded and joined by "/". The encoding carries no "/", so two attempts share a key only if all four parts are equal. The run is part of it because tool-use IDs are unique only within a run: a sub-agent, a programmatic sub-run or a session turn of one tree can reuse the parent's ("call_0"), and without the run the second call would find the first's slot and count nothing.

func (*Ledger) IndexRun

func (l *Ledger) IndexRun(r Rule) string

IndexRun is the ID of the index run of a rule and currency.

func (*Ledger) LedgerRun

func (l *Ledger) LedgerRun(r Rule, window, keyDigest string) string

LedgerRun is the ID of the ledger run of a rule, a window and a key digest. The index run has four segments and a ledger run five, so no ledger run is an index run.

func (*Ledger) Live

func (l *Ledger) Live(ctx context.Context, run string) ([]Slot, error)

Live returns the live reserve slots of a ledger run (those no release voids), in slot order: for an audit of what a window holds.

func (*Ledger) Reconcile

func (l *Ledger) Reconcile(ctx context.Context, run string, voided func(ctx context.Context, s Slot) (bool, error)) ([]string, error)

Reconcile releases the live slots of marked attempts that voided reports as recorded not started (it is given the slot: its Run, Tool and Att find the attempt marker): the slots a void left counted (a void written without a release, a handler that reserved after the call was sealed). voided reads the run journals, which the ledger does not know. An attempt that is not voided is left alone, as is every unmarked attempt and a call resolved by ResolveHalt: a window only over-counts. It returns the attempts it released.

func (*Ledger) Release

func (l *Ledger) Release(ctx context.Context, t Target, s Seal) (bool, error)

Release releases the live slot of the attempt in the ledger its cap-intent names, once the call's began word is sealed (s must be the seal of this attempt), and reports whether it wrote a release (false when there is no intent, so nothing was ever reserved, or the attempt holds no live slot, or is already released). The caller voids the attempt afterwards (recordNotStarted), never before: a void without its release would leave the slot counted until Reconcile.

Only a marked attempt is released. A retry-safe attempt is shared by any number of drivers of one tool-use ID, so one driver's proof says nothing about the others; its slot stays counted, which is the safe direction (model 17, findings/release-unmarked).

func (*Ledger) Reserve

func (l *Ledger) Reserve(ctx context.Context, r Request) (Outcome, error)

Reserve reserves r.Amount for the attempt and returns the slot that holds it. It is idempotent: an attempt that already holds a live slot gets that slot, whoever asks and however often. When the reservation would take the window over its limit and the call has no waiver it returns an error that is ErrOverLimit and writes nothing.

A crash at any point leaves the window counting the attempt (a slot is inserted) or not (nothing was), and a later Reserve of the same attempt finds the same ledger through the intent.

func (*Ledger) Slots

func (l *Ledger) Slots(ctx context.Context, run string) ([]Slot, error)

Slots returns every slot of a ledger run, in order: for an audit and for tests.

func (*Ledger) WindowOf

func (l *Ledger) WindowOf(ctx context.Context, s Slot) (kind Kind, window string, ok bool, err error)

WindowOf is the kind and id of the window a live slot's attempt reserved in, as its cap-intent (in the run the slot names) fixed it: the structured record, not anything parsed out of the ledger run's name. ok is false when the run holds no such intent.

type Outcome

type Outcome struct {
	Ledger string // the ledger run
	Window string
	Slot   Slot
	// Resumed says the attempt already held a live slot (a retry, a resume or a second driver).
	Resumed bool
}

Outcome is where a reservation landed.

type OverLimitError

type OverLimitError struct {
	Cum, Amount, Limit int64
}

OverLimitError is the detail of ErrOverLimit.

func (*OverLimitError) Error

func (e *OverLimitError) Error() string

Error describes the reservation and the window it would overflow.

func (*OverLimitError) Is

func (e *OverLimitError) Is(target error) bool

Is reports ErrOverLimit.

type Request

type Request struct {
	Rule Rule
	// KeyDigest is KeyDigest of the normalized key the rule is by ("" digests as the unkeyed total).
	KeyDigest string
	// RunID is the run whose journal holds the attempt's cap-intent and cap-reserve: the run that made the call.
	RunID string
	// RootRunID is the root of the run's tree: the window id of a Run window.
	RootRunID string
	// ToolUseID and AttemptID identify the attempt with RootRunID. The ledger encodes and joins them
	// itself (AttemptKey), so no choice of the three can make one attempt's key another's. A retry of
	// the same attempt, a resume, a second driver and a middleware's second next carry the same three.
	ToolUseID string
	AttemptID string
	// Marked says the attempt has an exclusive claim (a tool that is not retry-safe). Only a marked
	// attempt is ever released.
	Marked bool
	// Amount is what the attempt reserves, in minor units: positive. Reserving zero counts nothing and
	// a negative amount would give room back, so both are refused (ErrInvalid); the call site treats an
	// amount it cannot assess as the rule's strictest action and never calls Reserve for zero.
	Amount int64
	// Limit is the rule's limit, not negative.
	Limit int64
	// Clock, if set, reads now for this request's first intent in place of the ledger's own clock: the
	// clock of the run being driven (WithClock). It is read at a first intent only.
	Clock func() time.Time
	// Waiver says the call carries an approved waiver for the rule: a reservation over the limit is
	// written, marked over.
	Waiver bool
	// contains filtered or unexported fields
}

Request is one reservation: an attempt of a call asks for amount against rule's window.

type Rule

type Rule struct {
	Namespace string
	Name      string
	Currency  string
	Kind      Kind
}

Rule names a cap rule's ledger: the deployment's namespace, the rule, its currency and its kind of window.

type Seal

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

Seal is the proof that one attempt's tool never began and never will: the began word of its call, shared by every invocation of its handler, moved from none to sealed. Only NewSeal makes one, from the word itself, and Release takes one for the attempt it names, so a release is written only by a caller that sealed that attempt's word (model 17's LoopSeal). A handler's own "I did not begin" is not a Seal, because a second invocation of the handler can find the word set by the first (errReinvoked), and a retry-safe attempt has no word at all; and a Seal of one attempt, copied, releases no other.

func NewSeal

func NewSeal(attempt string, word *atomic.Int32, none, sealed int32) (Seal, bool)

NewSeal moves word, the began word of attempt's call, from none to sealed with a compare and swap that the ledger performs itself, and returns the Seal if the swap won. A word that says the tool began (or is already sealed by another) makes no Seal: a Seal is never made for a call that began.

func NewSeals

func NewSeals(attempts []string, word *atomic.Int32, none, sealed int32) ([]Seal, bool)

NewSeals is NewSeal for a call that holds several attempts on one began word (one per cumulative rule it reserved under): one compare and swap of the word, and a Seal bound to each attempt if it won.

type Slot

type Slot struct {
	N        int    `json:"n"`
	Kind     string `json:"kind"` // "reserve" or "release"
	Attempt  string `json:"attempt"`
	Amount   int64  `json:"amount"`
	Currency string `json:"currency"`
	Ref      int    `json:"ref,omitempty"` // for a release, the slot it voids
	CumAfter int64  `json:"cum_after"`
	Limit    int64  `json:"limit"`
	Over     bool   `json:"over,omitempty"` // cum_after exceeds the limit, and a waiver covered it
	Marked   bool   `json:"marked,omitempty"`
	// Run, Tool and Att are the identity the Attempt joins, unencoded: the run whose journal holds the
	// call's attempt marker, the tool-use ID and the attempt ID, so a reconcile pass can find the marker.
	Run  string `json:"run,omitempty"`
	Tool string `json:"tool,omitempty"`
	Att  string `json:"att,omitempty"`
}

Slot is one entry of a ledger.

type Store

type Store interface {
	// Insert stores data under (run, name) if no entry has that name, and returns the entry the name
	// holds (the caller's, or the one already there) and whether this call stored it (A1).
	Insert(ctx context.Context, run, name string, data []byte) (stored []byte, inserted bool, err error)
	// Get returns the entry of run named name, if there is one.
	Get(ctx context.Context, run, name string) (data []byte, ok bool, err error)
	// Scan yields the entries of run whose Seq is greater than after (-1 for all), in ascending Seq:
	// a prefix of the run in commit order (A2). It yields an error at most once, as its last element.
	Scan(ctx context.Context, run string, after int64) iter.Seq2[Item, error]
}

Store is what the ledger needs of a journal.

type Target

type Target struct {
	Rule                 Rule
	KeyDigest            string
	RunID, RootRunID     string
	ToolUseID, AttemptID string
}

Target names an attempt whose slot is released: the rule, the key, the run that made the call and the attempt's three parts, as in the Request that reserved it. The ledger is not named: the window is read from the attempt's cap-intent, as Reserve reads it, so a release cannot land in another ledger.

Directories

Path Synopsis
Package capledgerproc runs the cap ledger across real worker processes (re-executions of a store's test binary) for the tests of bide's stores.
Package capledgerproc runs the cap ledger across real worker processes (re-executions of a store's test binary) for the tests of bide's stores.
Package capledgertest gives the tests of bide's stores a cap ledger over a Journal on their store: they run it across real processes (store/sqlite, store/postgres) and under an audited store, which the unexported ledger cannot be reached for from another module.
Package capledgertest gives the tests of bide's stores a cap ledger over a Journal on their store: they run it across real processes (store/sqlite, store/postgres) and under an audited store, which the unexported ledger cannot be reached for from another module.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL