Documentation
¶
Overview ¶
Package sim simulates an S3 bucket on top of a radix.Tree, implementing just enough of the ListObjectsV2 surface to drive discovery-strategy comparisons without round-tripping to AWS. Pagination, MaxKeys, delimiter grouping and StartAfter all match S3's documented semantics.
The simulator's headline metrics are exact (every Bucket.List call increments a single counter, and the keys-per-request ratio is therefore authoritative). The wall-clock metric is approximate — optional per-call latency is simulated via time.Sleep so real goroutine scheduling reproduces real worker contention, but SDK retries, throttling, and TCP head-of-line blocking are out of scope.
Index ¶
Constants ¶
const MaxKeysCap = 1000
MaxKeysCap mirrors S3's hard ceiling: any ListObjectsV2 call returns at most 1 000 entries (Contents + CommonPrefixes combined) per page.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Bucket ¶
type Bucket struct {
// contains filtered or unexported fields
}
Bucket is an in-memory S3 emulator backed by a radix.Tree. Safe for concurrent List calls.
func New ¶
New wraps tree as an S3-like bucket. latency is the synthetic per-call delay imposed on every List call to mirror real network latency; pass 0 to skip the sleep entirely (useful when only request counts matter).
func (*Bucket) List ¶
List runs one ListObjectsV2 against the simulated bucket and returns one page of results.
func (*Bucket) ObjectsServed ¶
ObjectsServed returns the cumulative number of Object entries returned across every List call so far. CommonPrefixes are not counted — they are references, not objects.
type CurrentProduction ¶
type CurrentProduction struct{}
CurrentProduction (S3) is the faithful port of scanner.go's algorithm as of this commit: probe with delimiter='/' to depth=opts.MaxDepth, then switch to delimiter-less recursive listing for everything beyond. Workers pull from a global non-blocking channel; producers fall back to inline recursion when the channel is full.
func (CurrentProduction) Name ¶
func (CurrentProduction) Name() string
type ListReq ¶
type ListReq struct {
Prefix string
Delimiter string // "" or "/"
StartAfter string
MaxKeys int // capped at MaxKeysCap
}
ListReq mirrors the subset of ListObjectsV2Input the simulator honours. StartAfter doubles as the continuation token: pass the previous response's NextContinuationToken to resume.
type ListResp ¶
type ListResp struct {
ContentsCount int // # of Contents entries this page would have returned
CommonPrefixes []string // CommonPrefix groupings, always materialised (small N per page)
NextContinuationToken string
IsTruncated bool
}
ListResp is a count-and-metadata projection of ListObjectsV2Output. The simulator never materialises individual Content keys — strategies under test only need the count, the discovered CommonPrefixes (for fan-out), and a continuation token, so paying for 50 M string allocations on a 50 M-object scan is wasteful. Per-content metadata (sizes, classes, per-storage-class rollups) belongs in dedicated future helpers if a strategy ever needs them.
type ProbeRootRecurseEach ¶
type ProbeRootRecurseEach struct{}
ProbeRootRecurseEach (S2) probes the root once with delimiter='/' (one or a few paginated calls), enqueues every returned CommonPrefix into a worker pool, and each worker runs a delimiter-less recursive scan over its assigned prefix.
This is the natural first step up from S1: parallelism equal to the branching factor at the root. Vulnerable to long-tail prefixes (one worker may inherit a 30 M-object subtree while peers finish small ones).
func (ProbeRootRecurseEach) Name ¶
func (ProbeRootRecurseEach) Name() string
type Result ¶
type Result struct {
StrategyName string
Workers int
Requests int64
ContentsCount int64
CommonPrefixes int64
Elapsed time.Duration
PerWorker []int64 // requests per worker
}
Result is the post-run summary. Counts and timings are exact (no sampling); PerWorker captures the per-worker request distribution so we can see whether a strategy actually parallelises or just appears to.
func (Result) AvgPerReq ¶
AvgPerReq is the headline cost metric: average entries (Contents + CommonPrefixes) per List call. Higher is cheaper.
func (Result) MaxPerWorker ¶
MaxPerWorker returns the largest per-worker request count. Under real S3 latency this is the critical-path proxy — the strategy can be no faster than max-per-worker × per-request latency, no matter how many workers exist.
func (Result) ReqsPerSec ¶
ReqsPerSec is the radix-tree's effective listing rate when the bucket has zero simulated latency. With non-zero latency it reflects the strategy's parallelism efficiency.
func (Result) String ¶
String renders one cost/speed line. Wall-clock is omitted — sim wall time is meaningless (latency=0 default; real S3 round-trips dominate). The two interpretable axes are total requests (= cost in USD) and max-per-worker (= critical path under any real latency model).
func (Result) WorkerLoadStats ¶
WorkerLoadStats summarises how evenly the strategy spread work across its workers. minMaxRatio of 1.0 = perfectly balanced; 0 = one worker did everything.
type RunOpts ¶
type RunOpts struct {
Workers int
MaxDepth int // S3-style probe-to-depth cap; ignored by strategies that don't probe
}
RunOpts holds the strategy-tunable knobs. Strategies are free to ignore fields that don't apply to them (e.g. S1 ignores Workers and MaxDepth).
type SingleRecursive ¶
type SingleRecursive struct{}
SingleRecursive (S1) is the simplest possible scan: one worker, one paginated ListObjectsV2 from prefix="" with no delimiter, pages until exhaustion. Establishes the floor of "1× S3 request per 1 000 keys" regardless of bucket shape.
func (SingleRecursive) Name ¶
func (SingleRecursive) Name() string
type Strategy ¶
type Strategy interface {
Name() string
Run(ctx context.Context, b *Bucket, opts RunOpts) (Result, error)
}
Strategy is one named discovery algorithm under test. Each strategy receives a fresh Bucket (so its request counter starts at 0) plus a RunOpts knob bag, and drives whatever workers/queues/recursion it chooses to drain the bucket.
type WorkStealingProbe ¶
type WorkStealingProbe struct{}
WorkStealingProbe (S4) is the proposed-but-not-yet-in-production algorithm: per-worker LIFO deques + random-victim work stealing, always-probe (no maxDepth fallback to recursive scan), pending counter for termination. The thesis is that:
- Always-probe maximises keys-per-list at the leaf level without trapping a single worker in a multi-minute paginated recursive scan.
- Per-worker deques expose every sub-prefix to stealing, so the tail of the scan has no idle workers.
Implementation knobs: random victim selection (uniform IntN), gosched then 100µs backoff when local empty and no victim has work.
func (WorkStealingProbe) Name ¶
func (WorkStealingProbe) Name() string
Source Files