crates/storage-git-gix/parked-gix-2/coldtier-archive/history.rs
//! **Superseded `gc` generations, kept as deltas against the live one.**
//!
//! `gunnar gc` consolidates a repository into one packfile and
//! [`ZnippyColdTier::seal`](crate::ZnippyColdTier::seal) writes that pack into
//! the repository's archive. That seal **rebuilds the archive from scratch**, so
//! until this module existed the pack the previous `gc` sealed was simply gone.
//! This is where it goes instead: a second archive beside the live one, holding
//! every generation `gc` has ever produced, with only the newest stored whole.
//!
//! # Direction, and why it is not a matter of taste
//!
//! `znippy_common::supersede_as_delta` stores the **superseded** generation as a
//! delta against the **live** one, never forward. The live generation is what
//! `P-001`'s `write_pack_copy` copies entries out of on every clone; putting it
//! behind a chain would move every fetch onto the entry-copy path, measured at
//! 18× the bytes and 221× the CPU. Backwards chaining keeps the newest
//! generation **whole at depth 0 for ever**, whatever the archive's history, and
//! pushes depth onto generations nothing on the serve path reads.
//!
//! Inside this file that argument is doubled: the live generation here is a
//! *copy* of what the live archive already holds whole, so even the archival
//! reader never walks a link to answer about the current repository.
//!
//! # Why a SECOND archive rather than the live one
//!
//! Because a delta chunk in the live archive would be destroyed by the push
//! path, and destroyed silently. MEASURED on oden 2026-08-05, on znippy
//! `ac2d4c7`:
//!
//! | path | `__znippy_delta__` after | a superseded 400 000-byte entry then reads as |
//! |---|---|---|
//! | `append_files_with_policy` | present, 1096 B | 400 000 bytes, exact |
//! | `HotArchive::open` + `seal` | **gone** | **10 bytes** — the delta instruction stream, handed back as content |
//!
//! `HotColdTier` is the push path ([`crate::hot`]), and a push re-heats whatever
//! archive it is given. So a delta chunk written into `gunnar-cold.znippy` would
//! survive exactly until the next push. Keeping the chain in a file no push ever
//! opens is not a workaround for that; it is also the right shape — the live
//! archive stays byte-for-byte what it was, and *therefore* the live
//! generation's read cannot regress, rather than being measured not to have.
//!
//! # Dead payload, and why this module compacts
//!
//! MEASURED, oden 2026-08-05, and it is the fact the writer's own numbers do not
//! state: **`supersede_as_delta` does not shrink the file.** It appends the delta
//! and drops the superseded entry's index rows; the superseded *blob* stays where
//! it was, unreferenced. A two-entry 8 056 624-byte archive went to 8 057 731
//! after a supersede that replaced 4 000 000 bytes with 11.
//!
//! So an archive fed one generation per `gc` and never rewritten grows by a whole
//! pack every time — exactly what storing them whole would cost, and the 5.26×
//! the writer measures is its *live* bytes, not its size on disk. [`compact`] is
//! what turns one into the other: `znippy_common::compact_archive` copies every
//! live chunk's on-disk bytes verbatim — delta chunks included, at the same
//! depth, with the same blake3 — into a fresh file and renames it over. It costs
//! one pass over the LIVE bytes, and [`GenerationHistory::retain`] triggers it on
//! a doubling so even that is paid about once per doubling rather than once per
//! `gc`.
//!
//! # Naming
//!
//! One directory per generation inside the archive:
//! `gen-0000000007/pack-<id>.pack`. The ordinal makes the order total and
//! explicit — pack ids are content addresses and say nothing about age — and the
//! original file names are kept under it so an unfolded generation is a
//! directory `git` can be pointed at.
use std::collections::BTreeMap;
use std::path::{Path, PathBuf};
use anyhow::{anyhow, bail, Context as _, Result};
use znippy_common::{
append_files_with_policy, compact_archive, create_archive, read_delta_map, supersede_as_delta,
SkipPolicy, SupersedeOutcome, ZnippyArchive, ZnippyReader as _, MAX_GENERATION_CHAIN,
};
use crate::{file_len, file_name, COMPRESSION_LEVEL};
/// Suffix of the history archive, beside the live one.
///
/// `gunnar-cold.znippy` → `gunnar-cold-history.znippy`. Beside rather than
/// inside, and inside the git directory rather than elsewhere, for the same
/// reason `archive_path` gives: a repository and everything derived from it are
/// one unit to move, back up and delete.
pub const HISTORY_SUFFIX: &str = "-history";
/// Sidecar holding the archive's size immediately after the last [`compact`].
///
/// A **performance** watermark and nothing else: losing it makes the next
/// `retain` compact once too early, which costs time and cannot cost a byte of
/// data. That is deliberately unlike a chain-depth counter, which is why the
/// depth is read out of the archive's own `__znippy_delta__` section on every
/// call instead of being cached here — a depth that drifts low walks the chain
/// past the cap `supersede_as_delta` exists to enforce.
const WATERMARK_SUFFIX: &str = ".compacted";
/// Compact once the file has grown past this multiple of its size after the last
/// compaction.
///
/// Two. Each `gc` leaves exactly one whole generation dead, so the file grows by
/// about one pack per `gc` while its live bytes grow by about one delta — the
/// measured ratio between those is 3–5× over 19 real repositories. A doubling
/// trigger therefore fires roughly every `live/pack` generations and keeps the
/// file inside 2× of steady state at all times, while paying the copy-over-live-
/// bytes rewrite about once per doubling instead of once per `gc`.
const COMPACT_AT: u64 = 2;
/// The retained generations of one repository.
#[derive(Debug, Clone)]
pub struct GenerationHistory {
archive: PathBuf,
}
/// One retained generation: its ordinal and the entry names under it.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Generation {
pub ordinal: u64,
/// `gen-NNNNNNNNNN/pack-<id>.pack`
pub pack: String,
/// `gen-NNNNNNNNNN/pack-<id>.idx`
pub index: String,
}
/// What one [`GenerationHistory::retain`] did. Applied outputs only: a `retain`
/// that appended and superseded nothing would otherwise be indistinguishable
/// from one that did the work (LAW 2).
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RetainOutcome {
pub archive: PathBuf,
/// Generations the archive holds after this call, this one included.
pub generations: usize,
/// What the writer did to the generation this one superseded. `None` on the
/// first `retain`, which supersedes nothing.
pub superseded: Option<Superseded>,
/// Chain depth of the deepest generation after this call.
pub deepest: usize,
/// Whether this call rewrote the archive to reclaim dead payload.
pub compacted: bool,
pub archive_bytes_before: u64,
pub archive_bytes_after: u64,
}
/// The pack half of a supersede, reported as the writer reported it.
///
/// A decline is a **correct outcome**, not an error: past
/// [`MAX_GENERATION_CHAIN`] the writer refuses so the superseded generation stays
/// whole and becomes the keyframe the next chain is built from, and a delta that
/// does not clearly beat the stored bytes is not worth a link that is paid on
/// every later read.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Superseded {
/// Stored as a delta against the generation that replaced it.
Delta {
stored_bytes: u64,
delta_bytes: u64,
chain_depth: usize,
},
/// The delta did not clear znippy's size cutoff; kept whole.
NotSmaller { delta_bytes: u64, stored_bytes: u64 },
/// The chain would have exceeded [`MAX_GENERATION_CHAIN`]; kept whole as a
/// keyframe.
ChainTooLong { at: usize },
}
impl From<SupersedeOutcome> for Superseded {
fn from(o: SupersedeOutcome) -> Self {
match o {
SupersedeOutcome::Delta {
stored_bytes,
delta_bytes,
chain_depth,
} => Superseded::Delta {
stored_bytes,
delta_bytes,
chain_depth,
},
SupersedeOutcome::NotSmaller {
delta_bytes,
stored_bytes,
} => Superseded::NotSmaller {
delta_bytes,
stored_bytes,
},
SupersedeOutcome::ChainTooLong => Superseded::ChainTooLong {
at: MAX_GENERATION_CHAIN,
},
}
}
}
impl GenerationHistory {
/// The history archive beside `live_archive`.
///
/// **Idempotent**: handed the history archive itself it returns that, rather
/// than a `…-history-history.znippy` nothing writes. Fixed by construction
/// because the failure it prevents is silent — `gunnar gc` reported
/// "0 generations retained" beside a file that was growing correctly,
/// because the caller passed the path this had already derived.
pub fn beside(live_archive: &Path) -> Self {
let live = live_archive.with_extension("znippy");
let stem = live
.file_stem()
.and_then(|s| s.to_str())
.unwrap_or("gunnar-cold");
if stem.ends_with(HISTORY_SUFFIX) {
return Self { archive: live };
}
let archive = live.with_file_name(format!("{stem}{HISTORY_SUFFIX}.znippy"));
Self { archive }
}
/// The one archive this holds.
pub fn archive(&self) -> &Path {
&self.archive
}
/// The generations the archive holds, oldest first.
pub fn generations(&self) -> Result<Vec<Generation>> {
if !self.archive.is_file() {
return Ok(Vec::new());
}
let entries = ZnippyArchive::open(&self.archive)
.map_err(|e| anyhow!("{}: {e}", self.archive.display()))?
.list_files()
.map_err(|e| anyhow!("{}: {e}", self.archive.display()))?;
generations_of(&entries)
}
/// How many links the deepest generation sits behind a whole one.
///
/// Read out of the archive's own `__znippy_delta__` section, which is the
/// only record of it — see [`WATERMARK_SUFFIX`] for why this one is never
/// cached in a sidecar.
pub fn deepest_chain(&self) -> Result<usize> {
if !self.archive.is_file() {
return Ok(0);
}
let map = read_delta_map(&self.archive)
.map_err(|e| anyhow!("{}: {e}", self.archive.display()))?;
Ok(self
.generations()?
.iter()
.map(|g| chain_length_ending_at(&map, &g.pack))
.max()
.unwrap_or(0))
}
/// One generation's pack bytes, reconstructed through however many links it
/// sits behind the live one.
pub fn read(&self, entry: &str) -> Result<Vec<u8>> {
ZnippyArchive::open(&self.archive)
.map_err(|e| anyhow!("{}: {e}", self.archive.display()))?
.extract_file(entry)
.map_err(|e| anyhow!("{}: {}: {e}", self.archive.display(), entry))
}
/// **Retain `pack`/`index` as the newest generation, and delta the one it
/// supersedes against it.**
///
/// Called from [`ColdTier::fold`](gunnar_store::ColdTier::fold) — that is,
/// from `gunnar gc` — immediately after the live archive is sealed. The pack
/// handed in is the one the seal just wrote, so this reads it off disk and
/// never out of the live archive: the live archive is not opened, not
/// re-read, and not written to by anything in this module.
pub fn retain(&self, pack: &Path, index: &Path) -> Result<RetainOutcome> {
let before = file_len(&self.archive);
let existing = self.generations()?;
let ordinal = existing.last().map(|g| g.ordinal + 1).unwrap_or(0);
let files = vec![
(
entry_name(ordinal, &file_name(pack)?),
std::fs::read(pack).with_context(|| format!("reading {}", pack.display()))?,
),
(
entry_name(ordinal, &file_name(index)?),
std::fs::read(index).with_context(|| format!("reading {}", index.display()))?,
),
];
if existing.is_empty() {
create_archive(&self.archive, &files, COMPRESSION_LEVEL)
.map_err(|e| anyhow!("creating {}: {e}", self.archive.display()))?;
let after = file_len(&self.archive);
write_watermark(&self.archive, after);
return Ok(RetainOutcome {
archive: self.archive.clone(),
generations: 1,
superseded: None,
deepest: 0,
compacted: false,
archive_bytes_before: before,
archive_bytes_after: after,
});
}
// The one this generation supersedes. It is whole right now — the
// previous `retain` left it that way — and it stops being whole below.
let head = existing.last().expect("non-empty, checked above").clone();
let new = Generation {
ordinal,
pack: files[0].0.clone(),
index: files[1].0.clone(),
};
append_files_with_policy(
&self.archive,
&files,
COMPRESSION_LEVEL,
// Exact, free and unoverrulable, the same policy every other write in
// this crate passes: a pack and a pack index are already-compressed
// by construction and this caller knows it for the whole batch.
SkipPolicy::already_compressed(),
)
.map_err(|e| {
anyhow!(
"appending generation {ordinal} to {}: {e}",
self.archive.display()
)
})?;
// The depth comes out of the archive's own delta map, read after the
// append and never cached: it is how many links already terminate at the
// entry about to be superseded, which is what decides whether this link
// would take the chain past the cap.
let map = read_delta_map(&self.archive)
.map_err(|e| anyhow!("reading the delta map of {}: {e}", self.archive.display()))?;
let depth = chain_length_ending_at(&map, &head.pack);
let pack_outcome: Superseded = supersede_as_delta(
&self.archive,
&head.pack,
&new.pack,
depth,
COMPRESSION_LEVEL,
)
.map_err(|e| anyhow!("superseding {}: {e}", head.pack))?
.into();
// The index travels with its pack and is superseded on the SAME decision:
// a generation whose `.pack` was kept whole and whose `.idx` was delta'd
// would sit at two different depths, and a keyframe that is only half a
// keyframe is not one.
if matches!(pack_outcome, Superseded::Delta { .. }) {
let idx_depth = chain_length_ending_at(
&read_delta_map(&self.archive).map_err(|e| anyhow!("{e}"))?,
&head.index,
);
supersede_as_delta(
&self.archive,
&head.index,
&new.index,
idx_depth,
COMPRESSION_LEVEL,
)
.map_err(|e| anyhow!("superseding {}: {e}", head.index))?;
}
let generations = existing.len() + 1;
let mut compacted = false;
let mut after = file_len(&self.archive);
if should_compact(&self.archive, after) {
match compact(&self.archive) {
Ok(()) => {
compacted = true;
after = file_len(&self.archive);
write_watermark(&self.archive, after);
}
Err(err) => tracing::warn!(
target: crate::STORE_TARGET,
archive = %self.archive.display(),
%err,
"the generation history could not be compacted; it keeps its dead payload and \
will be retried on the next gc"
),
}
}
let deepest = self.deepest_chain()?;
Ok(RetainOutcome {
archive: self.archive.clone(),
generations,
superseded: Some(pack_outcome),
deepest,
compacted,
archive_bytes_before: before,
archive_bytes_after: after,
})
}
}
/// `gen-NNNNNNNNNN/<name>`.
fn entry_name(ordinal: u64, file: &str) -> String {
format!("gen-{ordinal:010}/{file}")
}
/// Parse the entry list back into generations, oldest first.
///
/// An entry that does not fit the shape is an error rather than a skip: the only
/// writer of this archive is [`GenerationHistory::retain`], so anything else in
/// it means the file is not the file this thinks it is.
fn generations_of(entries: &[String]) -> Result<Vec<Generation>> {
let mut by_ordinal: BTreeMap<u64, (Option<String>, Option<String>)> = BTreeMap::new();
for e in entries {
let (dir, file) = e
.split_once('/')
.ok_or_else(|| anyhow!("'{e}' is not a `gen-<n>/<file>` history entry"))?;
let ordinal: u64 = dir
.strip_prefix("gen-")
.and_then(|n| n.parse().ok())
.ok_or_else(|| anyhow!("'{e}' is not a `gen-<n>/<file>` history entry"))?;
let slot = by_ordinal.entry(ordinal).or_default();
if file.ends_with(".pack") {
slot.0 = Some(e.clone());
} else if file.ends_with(".idx") {
slot.1 = Some(e.clone());
} else {
bail!("'{e}' is neither a pack nor a pack index");
}
}
by_ordinal
.into_iter()
.map(|(ordinal, (pack, index))| match (pack, index) {
(Some(pack), Some(index)) => Ok(Generation {
ordinal,
pack,
index,
}),
_ => bail!("generation {ordinal} is missing its pack or its index"),
})
.collect()
}
/// How many links already terminate at `entry` — i.e. how deep the deepest
/// generation behind it sits.
///
/// The delta map is `(entry, chunk_seq, base)`, so "who is a delta against
/// `entry`" is a lookup on the base column, and the chain is that walk repeated.
/// It stops at a generation nothing points at, which is either the oldest or a
/// keyframe the writer declined to chain.
fn chain_length_ending_at(map: &[(String, u32, String)], entry: &str) -> usize {
let mut depth = 0usize;
let mut cursor = entry.to_string();
// Bounded by the map: each step consumes a distinct row, so a cyclic map
// (which no writer produces) terminates instead of hanging.
for _ in 0..map.len() {
match map.iter().find(|(_, _, base)| *base == cursor) {
Some((dependant, _, _)) => {
depth += 1;
cursor = dependant.clone();
}
None => break,
}
}
depth
}
/// Whether the archive has grown past [`COMPACT_AT`] times its size after the
/// last compaction.
///
/// A missing watermark says "compact": it is the state a fresh checkout, a
/// restore, or a killed `gc` leaves, and compacting once for nothing is the
/// cheap side of that decision.
fn should_compact(archive: &Path, now: u64) -> bool {
match read_watermark(archive) {
Some(mark) if mark > 0 => now > mark.saturating_mul(COMPACT_AT),
_ => true,
}
}
fn watermark_path(archive: &Path) -> PathBuf {
let mut p = archive.as_os_str().to_owned();
p.push(WATERMARK_SUFFIX);
PathBuf::from(p)
}
fn read_watermark(archive: &Path) -> Option<u64> {
std::fs::read_to_string(watermark_path(archive))
.ok()?
.trim()
.parse()
.ok()
}
fn write_watermark(archive: &Path, bytes: u64) {
// Advisory. A failure here costs one unnecessary compaction later and
// nothing else, so it is not allowed to fail a `gc`.
let _ = std::fs::write(watermark_path(archive), bytes.to_string());
}
/// **Rewrite the archive so only live bytes remain.**
///
/// `znippy_common::compact_archive`, which copies every live chunk's on-disk
/// bytes verbatim — delta chunks included, at the same depth, with the same
/// blake3 — and carries `__znippy_delta__` across as its decoded rows. So the
/// chain comes out identical and the dead payload is gone.
///
/// # The one thing that does NOT work, recorded because it is the obvious try
///
/// Reading every generation out and rebuilding with `create_archive` +
/// `supersede_as_delta` **reproduces the problem it is meant to fix**: the
/// rebuild stores each generation whole and each supersede then leaves those
/// whole bytes dead again. Measured here on six synthetic generations: 2 480 249
/// bytes of archive for 2 468 400 bytes of generations, i.e. no saving at all.
/// A compaction has to copy the deltas rather than re-derive them, which is why
/// this is a znippy primitive and not a loop in this file.
pub fn compact(archive: &Path) -> Result<()> {
let report =
compact_archive(archive).map_err(|e| anyhow!("compacting {}: {e}", archive.display()))?;
tracing::debug!(
target: crate::STORE_TARGET,
archive = %archive.display(),
bytes_before = report.bytes_before,
bytes_after = report.bytes_after,
rows = report.rows,
delta_rows = report.delta_rows,
"reclaimed the superseded generations' dead payload"
);
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
/// The `gc` report said "0 generations retained" next to a file that held
/// four, because it derived the history path from the history path.
#[test]
fn beside_is_idempotent() {
let live = Path::new("/r/one.git/gunnar-cold.znippy");
let h = GenerationHistory::beside(live);
assert_eq!(
h.archive(),
Path::new("/r/one.git/gunnar-cold-history.znippy")
);
assert_eq!(
GenerationHistory::beside(h.archive()).archive(),
h.archive(),
"beside must not stack its own suffix"
);
// And the extensionless form the tier's own constructor takes.
assert_eq!(
GenerationHistory::beside(Path::new("/r/one.git/gunnar-cold")).archive(),
h.archive()
);
}
#[test]
fn generations_parse_in_ordinal_order_not_lexical() {
let entries = vec![
"gen-0000000010/pack-b.idx".to_string(),
"gen-0000000002/pack-a.pack".to_string(),
"gen-0000000010/pack-b.pack".to_string(),
"gen-0000000002/pack-a.idx".to_string(),
];
let gens = generations_of(&entries).unwrap();
assert_eq!(gens.len(), 2);
assert_eq!(gens[0].ordinal, 2);
assert_eq!(gens[1].ordinal, 10);
}
#[test]
fn a_half_generation_is_an_error_not_a_silent_skip() {
let entries = vec!["gen-0000000002/pack-a.pack".to_string()];
assert!(generations_of(&entries).is_err());
}
/// The depth walk is what decides whether the writer is allowed to add a
/// link, so it is asserted on a chain rather than on one hop.
#[test]
fn chain_length_counts_every_link_that_terminates_at_an_entry() {
let map = vec![
("g0".to_string(), 0u32, "g1".to_string()),
("g1".to_string(), 0, "g2".to_string()),
("g2".to_string(), 0, "g3".to_string()),
];
assert_eq!(chain_length_ending_at(&map, "g3"), 3);
assert_eq!(chain_length_ending_at(&map, "g2"), 2);
assert_eq!(chain_length_ending_at(&map, "g0"), 0);
// A keyframe stops the walk: nothing names it as a base.
assert_eq!(chain_length_ending_at(&map, "elsewhere"), 0);
}
/// A map that names itself would otherwise spin. No writer produces one; the
/// bound is here because the walk is fed a file rather than a value.
#[test]
fn a_cyclic_delta_map_terminates() {
let map = vec![
("a".to_string(), 0u32, "b".to_string()),
("b".to_string(), 0, "a".to_string()),
];
assert!(chain_length_ending_at(&map, "a") <= map.len());
}
}