Erasure-Coded Redundancy, Health Monitoring & Self-Repair (RS k/n + Bloom-Gossip)

Summary Add an opt-in erasure coding layer to increase durability and availability across peers, plus lightweight inventory gossip and automatic repair. Each encrypted chunk is encoded into n fragments with recovery threshold k (Reed-Solomon). Fragments are distributed across peers with placement policies; background health checks trigger re-encoding/repair when availability dips below a target.

---

Motivation

Current replication relies on who happens to have which blocks. With churny or sparse swarms, restores can stall even though the data exists somewhere. Erasure coding:

• Improves durability with less overhead than full replication.
• Enables parallel multi-source restore (higher throughput).
• Allows self-healing when peers churn (target availability SLO).

---

Goals

• Chunk → RS fragments after encryption; store n fragments, any k reconstruct.
• Placement policies (random, rack/region-aware hints, min-distance).
• Inventory gossip via Bloom filters to avoid chatty per-hash announces.
• Health monitor & repair: detect missing fragments and proactively heal.
• Parallel restore: fetch best k fragments concurrently; resume on failure.
• Backwards compatibility: legacy fully-replicated chunks still supported.

---

Non-Goals

• Global coordinator; keep decentralized and opportunistic.
• Strong topology awareness beyond simple hints (advanced topology can follow).

---

Design Overview

1) Encoding Pipeline (write path)

1. Encrypt chunk (AES-256-GCM) as today → ciphertext, nonce, tag.

2. Erasure code ciphertext into n fragments with RS(k, n)

   • Library: github.com/klauspost/reedsolomon (pure Go, SIMD-aware).
   • Fragment size roughly ceil(len(ciphertext)/k).

3. Fragment IDs & integrity

   • Keep the existing chunk hash = SHA-256 of ciphertext.
   • Each fragment gets frag_id = SHA-256(chunk_hash || idx || n || k) and GCM-auth covered by the original tag (we store auth_ctx: {chunk_hash,n,k,idx}).

4. Metadata

   • Snapshot stores {chunk_hash, n, k, fragments: [peer_hint?, frag_id…]}.

2) Placement & Discovery

• Placement: for each fragment, pick peers using:

  • random (default), or
  • min_distance (avoid same IP / CIDR / region hint), or
  • user-provided allow/deny lists.

• Gossip: peers broadcast Bloom filters summarizing frag_ids they hold.

  • Reduces pubsub volume vs per-fragment announces.
  • Params tunable: m bits, k hashes, rotate every T minutes and on deltas.

3) Health & Repair

• Local health worker periodically:

  • Samples snapshot indices; checks that each chunk maintains ≥ target_availability (e.g., 80% of n visible via Bloom matches + probe).
  • If below threshold, re-encode or re-distribute missing fragments to suitable peers (respecting placement).

• Peers may pull-repair on restore if fewer than k fragments are reachable (ask holders to replicate to additional peers).

4) Restore (read path)

• For each needed chunk:

  • Query Bloom inventories → choose peers for up to n fragments.
  • Download until k verified fragments arrive; stream RS decode.
  • Verify GCM tag against ciphertext, then decrypt; write file data.

5) Wire & Storage Changes

Protobuf (new/extended)

• ErasureParams { uint32 k; uint32 n; string policy; }
• FragmentRef { bytes frag_id; string peer_hint; }
• In SnapshotMetadata.FileEntry: optional ErasureParams and repeated FragmentRef.
• New gossip message: BloomInventory { bytes filter; uint32 m; uint32 k; uint64 epoch; string peer_id; }.

CAS layout

• Store fragments under objects/<first2>/<frag_id> (value = fragment bytes).
• Local index maps chunk_hash → {n,k,frag_ids[]}.

Config (config.yaml)

erasure:
  enabled: true
  k: 12
  n: 18
  target_availability: 0.8   # trigger repair if below
  placement: "min_distance"  # random|min_distance
  bloom:
    bits: 262144             # m
    hashes: 6                # k
    rotate_seconds: 300
repair:
  interval_seconds: 900
  max_parallel_repairs: 2
restore:
  max_inflight_fragments: 8

---

Security & Integrity

• Encrypt-then-encode preserves confidentiality; fragments reveal nothing.
• GCM tag covers the full ciphertext; RS decode must reproduce the exact bytes or tag fails.
• Fragment IDs derive from the chunk hash, preventing mix-and-match poisoning.
• Sign snapshot metadata as today; include n,k and fragment refs.

---

Migration

• Erasure coding is opt-in per repo (or even per snapshot).
• Legacy snapshots (no ErasureParams) continue to read/write unchanged.
• Mixed repos: both styles can coexist; health/repair only applies to erasure-coded snapshots.

---

CLI / UX

Create snapshot with EC

./bin/backup-agent snapshot /data \
  -c config.yaml -p "pass" --ec --ec-k 12 --ec-n 18 --placement min_distance

Show health

./bin/peerctl health --show-missing --sample 1000

Force repair

./bin/peerctl repair --chunk <hash> --to-peers <peerA,peerB>

---

Acceptance Criteria

• Write path can produce RS(k,n) fragments after encryption; metadata recorded.
• Restore succeeds with any k fragments; throughput scales with concurrency.
• Bloom-filter gossip reduces announce traffic (>10× fewer messages in tests).
• Health worker detects under-replicated chunks and repairs to meet target.
• Placement policy enforces simple distance rule (avoid same /24 by default).
• Backwards compatibility validated (legacy snapshots operate unchanged).
• Integration tests: churn scenarios, partial outages, randomized failure seeds.
• Docs: README section “Erasure Coding & Self-Repair”, config examples, sizing guide.

---

Implementation Plan

• Core: RS encode/decode module (klauspost/reedsolomon), streaming API.
• Metadata: extend protobufs; add local index for chunk_hash → fragments.
• Gossip: Bloom inventory producer/consumer; periodic rotate & delta publish.
• Placement: peer scoring (IP/CIDR/region hints via PeerInfo), selection.
• Repair worker: scheduler, backpressure (max_parallel_repairs), audit logs.
• Restore: multi-source fetch with fallback/retry; partial timeouts.
• CLI: flags, peerctl health|repair; metrics hooks.
• Tests/bench: unit + soak (RS correctness, false-positive rates, repair latency).
• Docs & examples; migration notes.

---

Risks & Mitigations

• CPU/IO overhead: RS is CPU-bound; mitigate with SIMD lib, tune k/n, and cap fragment size.
• Gossip FP: Bloom false positives cause occasional wasted probes; pick sane m,k, rotate filters.
• Repair storms: Stagger repairs with jitter and rate limits; prefer local replication first.