Skip to content

Key the backup key-existence cache by raw hash rather than hex string #430

Description

@rmanibus

Context

KeyCacheStore (internal/storelayer/keycache.go) holds knownKeys as a
map[string]struct{} over full object keys — chunk/<64 hex chars> and
friends. BackupManager preloads it with every key under chunk/, content/
and node/, so the set is the size of the repository's object count.

Measured at 500k entries:

structure per entry
map[string]struct{} with hex keys 136 B
map[[32]byte]struct{} 84 B

A 10M-object repository therefore spends ~1.4 GB on the existence set alone
during a backup. Beyond the 38% size cut, [32]byte carries no pointer, so
the garbage collector stops scanning millions of string headers during the phase
where backup is already allocating hardest — likely the larger effect of the
two.

This is not a blind type swap. listedPrefixes and isContentAddressed both do
string-prefix matching to decide whether a key is immutable (and therefore
whether a Put may be elided). That logic has to keep working, and getting it
wrong in the permissive direction means skipping a write for an object that does
not exist.

See docs/caching.md for why this cache is not redundant with PackStore's
catalog — it is the only one that answers negatively.

Goal

The existence set costs materially less memory and GC time on a large
repository, with the content-addressed/mutable distinction preserved exactly.

Scope

  • Decode the hex suffix once and key the set by the raw 32-byte digest, carrying
    the prefix separately — either a map per preloaded prefix, or a tagged
    fixed-size key.
  • Preserve isContentAddressed semantics: mutable keys such as index/latest
    must still be written through unconditionally.
  • Keep the singleflight write-deduplication behaviour unchanged.
  • Handle keys whose suffix is not a 64-char hex digest by falling back to the
    current behaviour rather than mis-filing them.
  • Add a benchmark quantifying the allocation and GC change at a realistic object
    count.
  • Update docs/caching.md's inventory table.

Acceptance Criteria

  • Exists, Put elision and Delete behaviour are unchanged, including the
    negative-answer path for a listed prefix
  • a test covers a non-hex key under a listed prefix
  • benchmark output in the PR shows the allocation reduction
  • go test -race ./internal/storelayer ./internal/engine passes
  • golangci-lint run ./internal/storelayer/... ./internal/engine/... passes

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions