Documentation
¶
Overview ¶
Package radix implements an in-memory compressed radix tree (Patricia trie) over full S3 object keys, providing filesystem-style navigation by '/' boundary together with precomputed per-directory aggregates.
Index ¶
- Variables
- type Aggregate
- type Batch
- type ClassByte
- type ClassBytes
- type Entry
- type Iterator
- type NodeKind
- type NodeView
- type Object
- type StorageClass
- type Tree
- func (t *Tree) AddBatch(b Batch) error
- func (t *Tree) ChildrenOf(cid uint32) []NodeView
- func (t *Tree) Export(yield func(Object) bool)
- func (t *Tree) ListDirectory(prefix string) ([]Entry, error)
- func (t *Tree) NewIterator(startAfter string) *Iterator
- func (t *Tree) RootAggregate() Aggregate
- func (t *Tree) RootView() NodeView
- func (t *Tree) Save(w io.Writer) error
- func (t *Tree) SaveFile(path string) (err error)
- func (t *Tree) Stats() TreeStats
- type TreeStats
Constants ¶
This section is empty.
Variables ¶
var ( // ErrSnapshotMagic is returned by Load when the file does not begin with // the expected magic identifier. ErrSnapshotMagic = errors.New("radix: snapshot magic mismatch") // ErrSnapshotVersion is returned by Load when the snapshot's format // version is not supported by this build. ErrSnapshotVersion = errors.New("radix: snapshot version unsupported") // ErrSnapshotCorrupt is returned by Load when a record's ID is out of // range or repeats one already seen. ErrSnapshotCorrupt = errors.New("radix: snapshot corrupt") )
Functions ¶
This section is empty.
Types ¶
type Aggregate ¶
type Aggregate struct {
Objects int64
Bytes ClassBytes
}
Aggregate is a recursive summary over a subtree of the radix tree.
type Batch ¶
Batch is a contiguous range of S3 objects to ingest.
The caller guarantees that no object exists in the bucket whose key lies in (StartFrom, Objects[last].Key] other than those in Objects. Empty StartFrom means the beginning of the bucket. Objects must be sorted ascending by Key.
type ClassByte ¶
type ClassByte struct {
Class StorageClass
Size int64
}
ClassByte is one (storage class, byte-count) pair. It does double duty: as a single file's metadata (storage class + size in bytes) and as one entry in a sparse aggregate over many files of the same class.
type ClassBytes ¶
type ClassBytes []ClassByte
ClassBytes is a sparse, unsorted accumulator keyed by StorageClass. The number of distinct classes per node is small (S3 has roughly a dozen classes, real buckets typically use 1–3), so linear scans beat ordered lookups while keeping per-node memory minimal.
func (*ClassBytes) Add ¶
func (c *ClassBytes) Add(class StorageClass, n int64)
Add adds n bytes (possibly negative) to the bucket for class. Buckets that reach zero are removed; a new bucket with n == 0 is not appended.
func (ClassBytes) NonZero ¶
func (c ClassBytes) NonZero() []ClassByte
NonZero returns the populated buckets. The receiver already excludes zero buckets, so the return value is the slice itself.
func (ClassBytes) Total ¶
func (c ClassBytes) Total() int64
Total returns the sum of Size across every bucket. It is the byte counterpart to Aggregate.Objects for callers that have already drilled down to a ClassBytes value.
type Entry ¶
type Entry struct {
Name string
IsDir bool
Class StorageClass
Size int64
Aggregate Aggregate
}
Entry is one element of a ListDirectory result. Either a subdirectory (IsDir true, Aggregate populated) or a direct file (IsDir false, Class+Size set).
type Iterator ¶
type Iterator struct {
// contains filtered or unexported fields
}
Iterator is a forward, single-pass cursor over the alive objects of a Tree, walked in strict ascending lex order of full keys. Suitable for any "give me keys > X" loop — see sim.Bucket.List for the S3 emulation.
Iterator is read-only: tree mutations while iterating are not supported (same constraint as the existing rangeCursor it wraps).
func (*Iterator) Next ¶
Next advances the cursor and returns the next Object plus true. When the tree is exhausted it returns the zero Object plus false; subsequent calls keep returning false.
func (*Iterator) SkipTo ¶
SkipTo raises the iterator's exclusive lower bound so subsequent Next calls emit only keys strictly greater than skipKey. Cannot retreat — values less than or equal to the current bound are ignored. Useful for the delimiter='/'-style "jump past a CommonPrefix's subtree" pattern, where the caller computes a key that bounds the just-emitted subtree from above and uses SkipTo to advance the cursor past it.
func (*Iterator) Walk ¶
func (it *Iterator) Walk(yield func(key []byte, class StorageClass, size int64) bool)
Walk yields every remaining (key, class, size) triple in ascending lex order, invoking yield exactly once per object. key is a VIEW into the iterator's internal path buffer and is INVALIDATED as soon as yield returns — callers that need to retain it must copy the bytes (e.g. string(key) once, outside the hot loop).
Returning false from yield stops the walk. Walk is the zero-alloc-per- object alternative to Next; it is what sim.Bucket uses to avoid 50 M string allocations during a full bucket sweep.
type NodeView ¶
type NodeView struct {
// CID is the tagged child reference as it appears in a parent's
// children slice. The root internal carries CID=0 (no tag, no parent).
CID uint32
Kind NodeKind
Edge string
// Internal-only fields.
NumChildren int
HasDirMarker bool
DirMarker ClassByte
Aggregate Aggregate
// Leaf-only fields.
Class StorageClass
Size int64
}
NodeView is a read-only snapshot of one radix node, suitable for debug or visualisation tools. Both internals and leaves share this type. Fields not applicable to the node's Kind are left at their zero values.
type Object ¶
type Object struct {
Key string
Size int64
Class StorageClass
}
Object is a single S3 object record.
type StorageClass ¶
type StorageClass uint8
StorageClass enumerates the S3 storage classes returned by ListObjectsV2. Encoding as a uint8 keeps per-node memory tight; ClassByte.Class is one byte rather than the 16 bytes of a string header.
const ( ClassUnknown StorageClass = iota ClassStandard ClassStandardIA ClassOneZoneIA ClassIntelligentTier ClassGlacierIR ClassGlacier ClassDeepArchive ClassReducedRedundancy ClassExpressOneZone ClassSnow )
func ParseClass ¶
func ParseClass(s string) StorageClass
ParseClass maps an S3 storage-class string to a StorageClass. Unknown strings (and the empty string) collapse to ClassUnknown.
func (StorageClass) String ¶
func (c StorageClass) String() string
String returns the canonical S3 identifier for c.
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree is an in-memory compressed radix tree over S3 object keys.
Branch nodes (with children and per-subtree aggregates) and terminal leaves (single objects with no children) live in two separate chunked arenas. Each chunk is a fixed-size slab whose backing array never moves, so any pointer obtained from [Tree.atInternal] / [Tree.atLeaf] stays valid for the lifetime of the Tree. Children reference one another by uint32 ID: the high bit (leafTag) selects the arena and the low 31 bits index into it.
The root is an internal at ID 0 and is never released. A freelist per arena reuses slots vacated by deletes.
Concurrency: not safe for concurrent use. Callers must externally serialise AddBatch / ListDirectory calls.
func Load ¶
Load reads a snapshot previously produced by Save (or any prior v1 writer) and reconstructs the two-arena in-memory tree.
Each record is classified into the internal or leaf arena as it is read (a record is a leaf iff disk-ID != 0, file != nil, no children, no agg). Children references are stored temporarily as disk IDs and rewritten in a second pass via diskToCID once every record has been placed.
Memory cost during load: arenas + diskToCID (4 B × maxID+1). At 50 M objects diskToCID is ~300 MB, an order of magnitude smaller than the tree itself.
func LoadFile ¶
LoadFile is a convenience wrapper around Load that opens path, parses the snapshot, and returns the resulting tree. The file is closed before returning regardless of success.
func (*Tree) AddBatch ¶
AddBatch ingests a contiguous range of objects. See Batch for the range-ownership contract. Behavior:
- keys in the existing tree in (StartFrom, Objects[last].Key] but not in Objects are deleted.
- keys present in both with differing size/class are updated.
- keys only in Objects are inserted.
An empty Objects slice is a no-op (range deletion via an empty batch is not supported yet).
Implementation: a rangeCursor streams existing leaves in (StartFrom, hi] lock-step against the incoming batch via a three-way merge. The merge does not mutate the tree directly; it accumulates conflict-free insert/update/ delete groups. Pure-insert batches (the dominant case during first-scan import) skip allocation entirely by handing the input slice straight to [Tree.insertBatch].
func (*Tree) ChildrenOf ¶
ChildrenOf returns the children of an internal node addressed by the tagged child ID cid. Returns nil for leaf cids (they have no children). Order matches the in-tree storage: ascending by first byte of child edge.
func (*Tree) Export ¶
Export walks every alive object (regular leaves plus S3 directory-marker dir-marker files held on internals) in lex order, calling yield with each Object. Returning false from yield stops iteration early.
func (*Tree) ListDirectory ¶
ListDirectory returns the immediate children of the logical directory identified by prefix. The prefix must be either "" (root) or end with '/'. Entries are sorted lexicographically.
func (*Tree) NewIterator ¶
NewIterator returns a fresh iterator positioned at the first key strictly greater than startAfter. Pass "" to start from the very beginning.
func (*Tree) RootAggregate ¶
RootAggregate returns the aggregate over the whole tree (the radix root's aggregate). O(1) — the aggregate is maintained incrementally on every insert. Callers that just need the total object count or the per-class bytes should use this instead of walking Export.
func (*Tree) RootView ¶
RootView returns the root internal as a NodeView. The root's CID is 0 (it has no parent and is the always-allocated entry point into the tree).
func (*Tree) Save ¶
Save writes the tree's binary snapshot to w.
The on-disk format is unchanged from v1: a single contiguous ID space, one record per alive node, internals expressed as nodes-with-children, leaves expressed as nodes-with-file-and-no-children. Internals serialise first (so the root keeps disk ID 0), leaves second. Child references in internal records are rewritten via per-arena disk-ID mappings.
To skip free slots without allocating O(nextX) presence bitmaps, Save makes a sorted copy of each freelist (typically tiny — only grows on prune-heavy deletes) and walks it in lock-step with the slot iteration.
func (*Tree) SaveFile ¶
SaveFile is a convenience wrapper around Tree.Save that writes to path atomically: the snapshot is first written to path+".tmp" and renamed into place on success, so an interrupted run never leaves a half-written file at the destination. Parent directories are created with mode 0755.
type TreeStats ¶
type TreeStats struct {
AliveNodes int64
AliveInternals int64 // count from the internal arena
AliveLeaves int64 // count from the leaf arena
Leaves int64 // alias of AliveLeaves (kept for output compatibility)
Internals int64 // internals with children, no dir-marker file
InternalsWithFile int64 // internals carrying an S3 dir-marker file
Empty int64 // root or detached internals with no children and no file
NodesWithAgg int64
ClassBytePtrs int64 // == count of nodes with file != nil (each is one *ClassByte heap alloc)
ClassBytesLen int64 // sum of len(agg.Bytes)
ClassBytesCap int64 // sum of cap(agg.Bytes)
EdgeBytes int64 // sum of len(edge)
ChildrenSlots int64 // sum of cap(children)
MaxEdgeLen int
MaxChildrenCount int
EdgeLenHist [9]int64 // 0,1,2,3-4,5-8,9-16,17-32,33-64,65+
ChildrenHist [9]int64 // 0,1,2,3,4,5-7,8-15,16-31,32+
EstHeapInternals int64 // AliveInternals * sizeof(internal)
EstHeapLeaves int64 // AliveLeaves * sizeof(leaf)
EstHeapNodes int64 // EstHeapInternals + EstHeapLeaves
EstHeapEdges int64 // sum over edges of sizeClass(len(edge))
EstHeapChildren int64 // sum over internals of sizeClass(cap(children)*4)
EstHeapClassBytes int64 // ClassBytePtrs * sizeClass(sizeof(ClassByte))
EstHeapAggHeaders int64 // NodesWithAgg * sizeClass(sizeof(Aggregate))
EstHeapAggBytes int64 // sum over aggs of sizeClass(cap(Bytes)*sizeof(ClassByte))
EstHeapTotal int64
}
TreeStats is a memory-accounting snapshot of the tree's in-arena state. All counters are derived by a single linear walk over the chunked arena; no allocations beyond the freelist copy.
EstHeap* fields are best-effort: edge / children-slice / agg-bytes sizes are rounded up to the nearest Go small-object size class so the totals reflect what the allocator actually charged, not the raw byte count.
Source Files