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
- Variables
- func IsIntentName(name string) bool
- func IsReleaseName(name string) bool
- func IsReserveName(name string) bool
- func KeyDigest(normalized string) string
- func LedgerSegments(run string) (ns, rule, currency, window, key string, ok bool)
- func WindowID(k Kind, t time.Time, root string) (string, error)
- type Config
- type Intent
- type Item
- type Kind
- type Ledger
- func (l *Ledger) AttemptKey(run, root, toolUse, attempt string) string
- func (l *Ledger) IndexRun(r Rule) string
- func (l *Ledger) IntentLedger(in Intent) string
- func (l *Ledger) IntentName(attempt string) string
- func (l *Ledger) LedgerRun(r Rule, window, keyDigest string) string
- func (l *Ledger) Live(ctx context.Context, run string) ([]Slot, error)
- func (l *Ledger) Reconcile(ctx context.Context, run string, ...) ([]string, error)
- func (l *Ledger) Release(ctx context.Context, t Target, s Seal) (bool, error)
- func (l *Ledger) ReleaseName(attempt string) string
- func (l *Ledger) Reserve(ctx context.Context, r Request) (Outcome, error)
- func (l *Ledger) ReserveName(attempt string) string
- func (l *Ledger) Segment(s string) string
- func (l *Ledger) Slots(ctx context.Context, run string) ([]Slot, error)
- func (l *Ledger) WindowOf(ctx context.Context, s Slot) (kind Kind, window string, ok bool, err error)
- type Outcome
- type OverLimitError
- type Release
- type Request
- type Reserve
- type Rule
- type Seal
- type Slot
- type Store
- type Target
Constants ¶
const ( // ReleaseWhyRefused: a cumulative cap refused the call after another rule's slot was reserved. ReleaseWhyRefused = "cap refusal" // ReleaseWhyNoCall: the chain returned without reaching the tool's Call after a reservation (a later // reservation the store failed). ReleaseWhyNoCall = "chain without a tool call" )
The reasons a cap-release record gives (package agent writes the record, in the run that made the call, before it releases the call's slot; bide audit caps reads it).
const RunPrefix = "@cap/"
RunPrefix starts the ID of every ledger and index run (agent's capRunPrefix is the same string).
Variables ¶
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 IsIntentName ¶ added in v0.24.0
IsIntentName reports whether an entry name is that of a cap-intent record.
func IsReleaseName ¶ added in v0.24.0
IsReleaseName reports whether an entry name is that of a cap-release record.
func IsReserveName ¶ added in v0.24.0
IsReserveName reports whether an entry name is that of a cap-reserve record.
func KeyDigest ¶
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 LedgerSegments ¶ added in v0.24.0
LedgerSegments splits a ledger run ID into its namespace, rule, currency, window and key-digest segments (each as encoded in the ID). ok is false for anything but a ledger run (an index run has four segments, not five).
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 Intent ¶ added in v0.24.0
type Intent struct {
Attempt string
Namespace string
Rule string
Currency string
Kind Kind
Key string
Amount int64
Marked bool
Window string
Floor string
}
Intent is the decoded cap-intent record of an attempt: what it reserves, and the window fixed for it once. Floor is the newest window the index held when the clock bound was checked ("" for a run window or an empty index).
func DecodeIntent ¶ added in v0.24.0
DecodeIntent decodes the data of a cap-intent record, strictly.
func (Intent) IntentRule ¶ added in v0.24.0
IntentRule is the rule an intent names.
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 (*Ledger) AttemptKey ¶
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) IntentLedger ¶ added in v0.24.0
IntentLedger is the ledger run an intent sends its attempt's slot to.
func (*Ledger) IntentName ¶ added in v0.24.0
IntentName is the name of the cap-intent record of attempt (an AttemptKey) in its call's run.
func (*Ledger) LedgerRun ¶
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 ¶
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 ¶
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) ReleaseName ¶ added in v0.24.0
ReleaseName is the name of the cap-release record of attempt (an AttemptKey) in its call's run: the same name package agent builds (capReleaseStep).
func (*Ledger) Reserve ¶
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) ReserveName ¶ added in v0.24.0
ReserveName is the name of the cap-reserve record of attempt (an AttemptKey) in its call's run.
func (*Ledger) Segment ¶ added in v0.24.0
Segment is s as the ledger's configured Encode writes it into a run ID, so a caller can match a namespace, a rule or a window against the segments of a ledger run.
func (*Ledger) Slots ¶
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.
type Release ¶ added in v0.24.0
Release is the decoded cap-release record: the loop writes one, in the run that made the call, before it releases the call's slot, saying why (the call never began).
func DecodeRelease ¶ added in v0.24.0
DecodeRelease decodes the data of a cap-release record, strictly.
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 Reserve ¶ added in v0.24.0
Reserve is the decoded cap-reserve record of a reservation: the ledger run it was written into, the slot's number and the window's total after it.
func DecodeReserve ¶ added in v0.24.0
DecodeReserve decodes the data of a cap-reserve record, strictly: a member it does not know, another format or data after the record is an error.
type Rule ¶
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 ¶
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.
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. |