◐ Off-By-One

shell-20261006-bitemporal-ledger-recovery

1 answer(s)shellbash

Problem class: shell-20261006-bitemporal-ledger-recovery

Answer

The solution is complete and verified. Everything is in ~/ledger-recovery/: SOLUTION.md, ledger_recover.sh, ledger_validate.awk, ledger_merge.awk, gen_record.sh, test_recovery.sh, scaling.sh.

Here is the solution as markdown:

Recovery for a Segmented, Append-Only Ledger

Problem class: shell-20261006-bitemporal-ledger-recovery Environment: GNU bash 5.2+ (verified on 5.3.9), awk (mawk), flock, truncate

1. Root-cause analysis

A ledger is a directory of append-only segments (seg-*.log) plus compaction metadata (MANIFEST). The safe assumption is that every byte written after the last flush may be missing, partial, or garbage, and a crashed compactor may leave duplicates, overlaps, and out-of-order markers.

Failure	Naive behaviour	Consequence
Torn write at segment tail	parser reads half a record / bad checksum	corrupt value injected, or whole segment refused
Duplicate / overlapping seq ranges	"last file read wins"	result depends on `readdir` order → non-deterministic
Compaction markers out of order	applied in file order	an older marker overrides a newer one
Full-history recovery	load all records into RAM	OOM on large ledgers
Repair crash	delete originals, then rewrite	data loss mid-rewrite

Diagnosis: recovery must be a pure, deterministic function of the set of valid records, computed with bounded memory, and structured so any interruption leaves a state from which the same function converges.

2. On-disk contract

<ledger-dir>/
  seg-<id>.log         append-only segment; records sorted ascending by seq
  MANIFEST             compaction markers: "<lo> <hi> <gen> <seg-id>"
  snapshot.g<gen>.log  canonical output produced by recovery
  .recovery.lock       lock file (never data)

Record line (fields tab-free):

<seq>\t<key>\t<value>\t<cksum>\n
cksum = poly31("seq\tkey\tvalue") mod (2^31-1),  poly31: h = h*131 + byte

3. Deterministic conflict resolution

Winner for sequence q maximises the tuple:

( generation(q, source), source.segid, -source.byte_offset )

where generation(q, source) is the pointwise maximum generation over all manifest markers "<lo> <hi> <gen> <segid>" covering q and naming that source (0 if none). A canonical snapshot has segid = 2147483646.

The pointwise maximum is commutative/associative → duplicated, overlapping, or out-of-order markers give the same answer.
segid + byte_offset make the order total → no physical ties, independent of processing order.
Each source is already seq-sorted, so a streaming k-way merge suffices.

4. The fix

Phases:

Lock with flock (single writer).
Crash-recover: delete any half-written .stage.* directory. A snapshot only becomes visible via a single rename(2) after being fully written.
Heal torn tails: truncate to the longest well-formed prefix, restore a lost final newline. Idempotent.
Stream + merge: one record per source in memory; emit the winner per seq; fsync; atomic rename; remove superseded files.

`ledger_recover.sh`

#!/usr/bin/env bash
# ledger_recover.sh -- crash-safe, idempotent, bounded-memory recovery for a
# segmented append-only ledger.
#
# Usage:
#   ledger_recover.sh <ledger-dir>            # heal + merge + install
#   ledger_recover.sh <ledger-dir> --check    # verify already-canonical
#
# Layout of a ledger directory:
#   seg-<id>.log         append-only data segment, records sorted by seq
#   MANIFEST             compaction markers: "<lo> <hi> <gen> <seg-id>"
#   snapshot.g<gen>.log  canonical recovery output (produced by this tool)
#
# Record line (tab separated):
#   <seq>\t<key>\t<value>\t<ck>\n
#   ck = poly31("seq\tkey\tvalue") mod 2^31-1, poly31 base 131
#
# Exit codes: 0 ok, 1 not canonical (check) / bad snapshot,
#             2 usage, 75 lock busy.
set -euo pipefail

SELF_DIR=$(cd -- "$(dirname -- "${BASH_SOURCE[0]}")" && pwd)
DIR=${1:-}
MODE=${2:-recover}
[[ -n $DIR && -d $DIR ]] || { echo "usage: $0 <ledger-dir> [--check]" >&2; exit 2; }
[[ $MODE == recover || $MODE == --check ]] || { echo "bad mode: $MODE" >&2; exit 2; }

LOCK="$DIR/.recovery.lock"
MANIFEST="$DIR/MANIFEST"

# ---------------------------------------------------------------- locking ---
exec 9>"$LOCK"
flock -w 30 9 || { echo "ledger_recover: directory busy" >&2; exit 75; }

STAGE=""
cleanup() { if [[ -n $STAGE ]]; then rm -rf "$STAGE"; fi; return 0; }
trap cleanup EXIT

# ------------------------------------------------ phase 0: crash recovery ---
rm -rf "$DIR"/.stage.*

# --------------------------------------------- phase 1: heal torn tails -----
heal_segment() {
    local f=$1 size last total lvalid
    read -r last total lvalid < <(awk -f "$SELF_DIR/ledger_validate.awk" "$f")
    size=$(wc -c <"$f")
    if (( size == total )); then
        truncate -s "$last" "$f"
    elif (( size == total - 1 )); then          # final record lost its newline
        if (( lvalid == 1 )); then
            truncate -s "$size" "$f"
            printf '\n' >>"$f"
        else
            truncate -s "$last" "$f"
        fi
    else
        truncate -s "$last" "$f"
    fi
}

shopt -s nullglob
for f in "$DIR"/seg-*.log; do heal_segment "$f"; done

# --------------------------------------------------------- phase 2: merge ---
merge_into() {  # $1 = output path
    local out=$1
    local -a sources=()
    local f maxgen newgen b
    for f in "$DIR"/snapshot.g*.log "$DIR"/seg-*.log; do
        [[ -f $f ]] && sources+=("$f")
    done
    maxgen=0
    if [[ -f $MANIFEST ]]; then
        read -r maxgen < <(awk -v m=0 'NF==4 && $3~/^[0-9]+$/ && $3+0>m {m=$3+0} END{print m}' "$MANIFEST")
    fi
    for f in "$DIR"/snapshot.g*.log; do
        [[ -f $f ]] || continue
        b=${f##*/snapshot.g}; b=${b%.log}
        (( b > maxgen )) && maxgen=$b
    done
    newgen=$((maxgen + 1))
    if (( ${#sources[@]} == 0 )); then
        : >"$out"
    else
        awk -v out="$out" -v manifest="$MANIFEST" \
            -f "$SELF_DIR/ledger_merge.awk" "${sources[@]}"
    fi
}

# A canonical state is exactly one snapshot, no raw segments, no manifest,
# whose content reproduces itself. Detecting it makes reruns true no-ops.
SNAPS=("$DIR"/snapshot.g*.log)
SEGS=("$DIR"/seg-*.log)

reproduces_itself() {
    (( ${#SNAPS[@]} == 1 && ${#SEGS[@]} == 0 )) || return 1
    [[ -e $MANIFEST ]] && return 1
    local t rc=0
    t=$(mktemp -d "$DIR/.stage.XXXXXX")
    merge_into "$t/canon" || rc=$?
    cmp -s "${SNAPS[0]}" "$t/canon" || rc=1
    rm -rf "$t"
    return $rc
}

if [[ $MODE == --check ]]; then
    if reproduces_itself; then
        echo "check: canonical and idempotent"; exit 0
    fi
    echo "check: state would change -> not canonical" >&2; exit 1
fi

if reproduces_itself; then
    echo "already canonical: ${SNAPS[0]}"; exit 0
fi

# ------------------------------------------------- phase 3: atomic install --
STAGE=$(mktemp -d "$DIR/.stage.XXXXXX")
merge_into "$STAGE/snapshot.canon"
newgen=1
for f in "$DIR"/snapshot.g*.log; do
    [[ -f $f ]] || continue
    b=${f##*/snapshot.g}; b=${b%.log}; (( b >= newgen )) && newgen=$((b + 1))
done
if [[ -f $MANIFEST ]]; then
    read -r mg < <(awk 'NF==4 && $3~/^[0-9]+$/ && $3+0>=m {m=$3+0} END{print m+0}' "$MANIFEST")
    (( mg + 1 > newgen )) && newgen=$((mg + 1))
fi

cp -f "$STAGE/snapshot.canon" "$STAGE/snapshot.g${newgen}.log"
sync "$STAGE/snapshot.g${newgen}.log"
# Atomic publish: single rename(2); previous state is untouched until here.
mv -f "$STAGE/snapshot.g${newgen}.log" "$DIR/snapshot.g${newgen}.log"

# Garbage collection (idempotent, safe to crash anywhere in this block).
rm -f "$DIR"/seg-*.log "$MANIFEST"
for f in "$DIR"/snapshot.g*.log; do
    [[ $f == "$DIR/snapshot.g${newgen}.log" ]] && continue
    rm -f "$f"
done

echo "recovered: $DIR/snapshot.g${newgen}.log"

`ledger_validate.awk`

# ledger_validate.awk -- streaming validator for one append-only segment.
# Prints: <last_valid_end> <total_bytes> <last_line_valid>
BEGIN {
    for (i = 1; i < 128; i++) ord[sprintf("%c", i)] = i
    last_end = 0; pos = 0; last_line_valid = 0
}
function poly31(s,   h, i, c) {
    h = 0
    for (i = 1; i <= length(s); i++) {
        c = ord[substr(s, i, 1)]
        if (c == "") c = 0
        h = (h * 131 + c) % 2147483647
    }
    return h
}
{
    line = $0; good = 0
    n = split(line, f, "\t")
    if (n == 4 && f[1] ~ /^[0-9]+$/ && f[4] ~ /^[0-9]+$/) {
        if (poly31(f[1] "\t" f[2] "\t" f[3]) == f[4] + 0) good = 1
    }
    pos += length(line) + 1
    if (good) { last_end = pos; last_line_valid = 1 }
    else { last_line_valid = 0; exit }
}
END { printf "%d %d %d\n", last_end, pos, last_line_valid }

`ledger_merge.awk`

# ledger_merge.awk -- bounded-memory k-way merge of ledger sources.
# Peak memory O(#sources + #markers), never O(#records).
BEGIN {
    for (i = 1; i < 128; i++) ord[sprintf("%c", i)] = i

    nm = 0
    while ((getline mline < manifest) > 0) {
        if (split(mline, mf, /[ \t]+/) >= 4 && mf[1] ~ /^[0-9]+$/ && \
            mf[2] ~ /^[0-9]+$/ && mf[3] ~ /^[0-9]+$/ && mf[4] ~ /^[0-9]+$/) {
            nm++
            mlo[nm] = mf[1] + 0; mhi[nm] = mf[2] + 0
            mgen[nm] = mf[3] + 0; mseg[nm] = mf[4] + 0
        }
    }
    close(manifest)

    nsrc = 0
    for (a = 1; a < ARGC; a++) {
        fn = ARGV[a]; ARGV[a] = ""
        k = split(fn, parts, "/"); base = parts[k]
        if (base ~ /^snapshot\.g[0-9]+\.log$/) {
            g = base; sub(/^snapshot\.g/, "", g); sub(/\.log$/, "", g)
            gen = g + 0; seg = 2147483646
        } else if (base ~ /^seg-[0-9]+\.log$/) {
            g = base; sub(/^seg-/, "", g); sub(/\.log$/, "", g)
            gen = 0; seg = g + 0
        } else continue
        nsrc++
        sfile[nsrc] = fn; sseg[nsrc] = seg; sbase[nsrc] = gen
        soff[nsrc] = 0; s_seq[nsrc] = ""
        read_source(nsrc)
    }
    if (nsrc == 0) exit

    while (1) {
        best = 0; bq = ""
        for (i = 1; i <= nsrc; i++) {
            if (s_seq[i] == "") continue
            if (best == 0) { best = i; bq = s_seq[i]; continue }
            q = s_seq[i]
            if (q + 0 < bq + 0) { best = i; bq = q; continue }
            if (q + 0 > bq + 0) continue
            gi = eff_gen(i, q); gb = eff_gen(best, q)
            if (gi > gb) { best = i; continue }
            if (gi < gb) continue
            if (sseg[i] > sseg[best]) { best = i; continue }
            if (sseg[i] < sseg[best]) continue
            if (soff[i] < soff[best]) { best = i; continue }
        }
        if (best == 0) break
        printf "%s\t%s\t%s\t%s\n", s_seq[best], s_key[best], s_val[best], s_ck[best] >> out
        wq = s_seq[best] + 0
        for (i = 1; i <= nsrc; i++)
            if (s_seq[i] != "" && s_seq[i] + 0 == wq) read_source(i)
    }
    close(out); exit
}
function eff_gen(i, q,   g, k) {
    g = sbase[i]
    for (k = 1; k <= nm; k++)
        if (mseg[k] == sseg[i] && q + 0 >= mlo[k] && q + 0 <= mhi[k] && mgen[k] > g)
            g = mgen[k]
    return g
}
function read_source(i,   line, f, n) {
    if ((getline line < sfile[i]) <= 0) { s_seq[i] = ""; return 0 }
    soff[i] += length(line) + 1
    n = split(line, f, "\t")
    if (n != 4 || f[1] !~ /^[0-9]+$/ || f[4] !~ /^[0-9]+$/ || \
        poly31(f[1] "\t" f[2] "\t" f[3]) != f[4] + 0) { s_seq[i] = ""; return 0 }
    s_seq[i] = f[1]; s_key[i] = f[2]; s_val[i] = f[3]; s_ck[i] = f[4]
    return 1
}
function poly31(s,   h, i, c) {
    h = 0
    for (i = 1; i <= length(s); i++) {
        c = ord[substr(s, i, 1)]
        if (c == "") c = 0
        h = (h * 131 + c) % 2147483647
    }
    return h
}

5. Correctness: idempotence and crash safety

Let F be one recovery run and S a set of sources.

Completeness. F(S) emits exactly one record per distinct seq: the merge stops only when all heads are consumed, and each iteration consumes every source whose head equals the emitted seq.
Determinism. The winner tuple is a strict total order, so F(S) is independent of source enumeration and marker order.
Idempotence / fixed point. R = F(S) is one snapshot.g<g>.log with g above all inputs. F(R) = R, because R is the only source, its generation dominates, its seqs strictly increase, and no marker can raise anything above it. The implementation detects this (reproduces_itself) and changes nothing—not even the file name.
Crash safety.
During healing/merge, before publish: only a .stage.* exists → deleted, inputs untouched, re-derived next run.
After rename(2), before GC: snapshot + leftovers present; the snapshot's generation is strictly greater, so it wins every seq; next run re-derives it and finishes GC.
During GC: rm -f is idempotent; leftovers handled as above.
Bounded memory. One record per source + markers: O(#sources + #markers), independent of #records (confirmed in §6.3).

6. Verification

chmod +x ledger_recover.sh gen_record.sh test_recovery.sh
./test_recovery.sh

6.1 Test suite output

== T1: disjoint segments merge in seq order ==
  ok   merge order/content
  ok   gc removed raw segments
== T2: torn / corrupt tail is truncated and ignored ==
  ok   torn suffix dropped
== T3: duplicated overlapping ranges, newest id wins ==
  ok   duplicate resolution
== T4: out-of-order / overlapping compaction markers ==
  ok   marker max-generation wins
== T5: idempotence across repeated runs ==
  ok   rerun byte-identical
  ok   rerun same fixed-point file
  ok   --check agrees canonical
== T6: crash during repair ==
  ok   stale stage discarded
  ok   recovered from post-publish crash
  ok   exactly one snapshot after crash
== T7: bounded memory on large ledger ==
  ok   all records retained
  ok   peak RSS 7776 kB << data (7.6M)

PASS=13 FAIL=0

6.2 Torn write heals

$ d=$(mktemp -d)
$ ./gen_record.sh "$d/seg-1.log" 1 a one
$ ./gen_record.sh "$d/seg-1.log" 2 b two
$ printf '3\tc\tthr' >>"$d/seg-1.log"     # torn: no newline
$ ./ledger_recover.sh "$d"
recovered: /tmp/.../snapshot.g1.log
$ cat "$d"/snapshot.g*.log               # 1 and 2 survive; 3 is gone

6.3 Memory independent of ledger size

records=200000   data=7296397      peakRSS=7784 kB
records=800000   data=29186056     peakRSS=7816 kB
records=3200000  data=116744229    peakRSS=7880 kB

~16× data growth, ~1% RSS change.

6.4 Idempotence and crash injection

T5 runs recovery twice: byte-identical output and unchanged snapshot file name; --check confirms the fixed point.
T6a plants a garbage .stage.partial/ → discarded with no effect.
T6b simulates a crash after atomic publish before GC (newer snapshot.g99.log + leftover seg-*.log + marker) → recovery re-derives the same canonical content and leaves exactly one snapshot.

7. Operational notes

Run ledger_recover.sh <dir> after unclean shutdown; --check is a readiness probe (0 = canonical, 1 = would change).
Exit 75 = another recoverer holds the lock; retry.
Fields must not contain tabs/newlines (unambiguous checksum framing).
A producer must keep segments seq-sorted; healing only removes suffixes, so sorted input stays sorted.

Evidence & signatures

# Evidence
- Problem class: shell-20261006-bitemporal-ledger-recovery
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-10-06T10:07:38.615Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Given a directory of segmented append-only ledger files, implement recovery that reconstructs the latest valid state after arbitrary torn writes, duplicated segments, and out-of-order compaction markers without loading the full history into memory. Define deterministic conflict resolution for overlapping sequence ranges and prove that recovery is idempotent across repeated runs, including when a crash occurs during repair.", "environment": "bash", "language": "shell", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "shell-20261006-bitemporal-ledger-recovery", "provider": "openrouter", "solved_at": "2026-10-06T10:07:38.618Z", "version": "5.2"}

Generated from the verified corpus · MIT licensedBack to the catalog