memory-efficiency benchmarks across multiple data structures

# Memory-efficiency benchmarks across data structures

## Goal

Characterize and continuously track Dragonfly's **memory efficiency** across the
major data structures, using a reproducible, Python-based benchmark harness.
Establish baseline "bytes per logical unit" numbers so that memory regressions
surface across releases, and so we have defensible real-world efficiency figures.

## Metric

Bytes per logical unit, always reported **two ways**:

- **logical** — `used_memory / units`
- **physical (RSS)** — `used_memory_rss / units` (the real footprint, includes
allocator overhead + fragmentation)

Unit depends on the type:

- **per key** — Strings, JSON
- **per element** (+ per-key container overhead) — Sets, Hashes, Lists, Sorted
sets

### Overhead per element (required output)

For container types, the headline number is **overhead per element**, not just
total bytes/entry. It is measured against an **empty-database baseline** — a
single load, no two-point differencing. The loader records the exact count of
logical elements written, and the metric step computes:

```
B0 = empty-server baseline (used_memory / used_memory_rss right after FLUSHALL)

Ce = (mem(K, M) - B0) / (K * M) # overhead per element (headline)
```

where `K` = number of keys and `M` = elements per key. Per-key footprint is
`(mem(K, M) - B0) / K` (= `Ce * M`, the container plus its elements).

Report `Ce` for every container type at a realistic element count, once with a
**small (compact/listpack)** container and once with a **large** one — the
encoding transition is the most interesting and most often-missed memory result.

## Data structures (v1)

- Strings
- JSON
- Sets
- Hashes
- Lists
- Sorted sets

## Real-world workloads

Beyond synthetic per-type fills, simulate traffic patterns of **real frameworks**
so the numbers reflect production usage, not just microbenchmarks:

- **Celery** — list-backed broker queues holding JSON task messages
(~300–800 B each) at a fixed queue depth.
- **Sidekiq** — list job queues of JSON jobs, plus scheduled/retry sorted sets.
- **Other frameworks / patterns** — session stores (hashes), caches (strings with
TTL), rate limiters (sorted sets), feed/timeline fan-out (lists/sorted sets).

Report total footprint for each named scenario at a realistic dataset size.

## Coverage that matters

- **Both encoding regimes** per container type: a *small* load below the compact
(listpack/intset) threshold, and a *large* load well above it .
- **Element size & content matrix**: ints vs short strings vs blobs; realistic
(less-compressible) JSON documents.
- **Default encoding thresholds** — reflect the honest real-world footprint;
record the actual `CONFIG GET` values in the appendix rather than tuning them.
- Always report **used_memory AND RSS** — the allocator materially affects the
resident footprint.
- Reloaded data from a snapshot shouldn't consume more memory.

## Tooling

- A **shared, deterministic Python loader** driven purely over the RESP protocol
(so it runs identically against any RESP-compatible server). Parameters:
`type, num_keys, elements_per_key, element_size, value_kind (int|str|json),
pipeline, seed`. Deterministic (fixed seed), pipelined, and prints the exact
count of logical elements written.
- Works against an **already-running database** — pass `--host`/`--port` (default
`127.0.0.1:6379`), or let the tool start a throwaway server per data point via
- A metrics step that consumes an `INFO memory` snapshot + `DBSIZE` + the loader's
element count and emits per-key / per-element overhead (logical and RSS)
measured against the empty-database baseline.

## Measurement protocol (per data point)

1. Start a fresh server with persistence **off** and eviction **off** (maxmemory
well above the dataset). Record the empty-server baseline `INFO memory`.
2. `FLUSHALL`, then run the loader deterministically.
3. Wait for completion; quiesce (`MEMORY PURGE` / idle settle).
4. Snapshot `DBSIZE`, `INFO memory` (used_memory, used_memory_rss, maxmemory),
the loaded element count, server version, and thread/shard count.
5. Compute bytes-per-unit and per-element overhead (baseline-subtracted).
Cross-check with `MEMORY USAGE` on sampled keys.
6. Repeat each data point **≥3×**; `used_memory` should be stable, RSS may vary —
investigate any significant run-to-run divergence.

## Deliverables

- The shared Python loader + metrics script.
- Per-type baseline tables: bytes/key, **per-element overhead**, per encoding
regime.
- Real-world scenario footprints (Celery, Sidekiq, and others).
- A tracked baseline so regressions are visible over releases.

## Later (out of scope for v1)

- Vector storage / index memory.
- Sparse indexed-array workload.