The task is a problem class, not a single bug: reshape a writer-visible table without stopping writers, and survive SIGKILL at any instruction, then prove with SQL that the result is exactly-once. A naive implementation fails in five distinct ways. Each failure mode maps to a specific race or missing invariant.
sqlite3The task is a problem class, not a single bug: reshape a writer-visible table without stopping writers, and survive SIGKILL at any instruction, then prove with SQL that the result is exactly-once. A naive implementation fails in five distinct ways. Each failure mode maps to a specific race or missing invariant.
| # | Failure mode | Why it happens | Fix in this design |
|---|---|---|---|
| 1 | Duplicated rows on resume | Backfill re-runs a chunk after a crash; plain INSERT inserts twice |
INSERT OR IGNORE into a shadow table keyed by the same PRIMARY KEY; backfill is idempotent |
| 2 | Ghost rows (row deleted, then re-inserted) | Backfill does SELECT then INSERT as two statements; a concurrent DELETE commits in between and its trigger deletes a not-yet-present shadow row, then the backfill inserts it |
Read+write in one BEGIN IMMEDIATE transaction (INSERT … SELECT …), so no writer can interleave between snapshot and write |
| 3 | Lost concurrent UPDATE/DELETE |
Backfill copies the row, then a writer changes it; shadow keeps the stale copy | AFTER INSERT/UPDATE triggers upsert the newest source row (ON CONFLICT(id) DO UPDATE), AFTER DELETE trigger removes it |
| 4 | Torn cutover | ALTER TABLE src RENAME …; ALTER TABLE shadow RENAME …; executed non-atomically leaves no src table if killed between them |
Both ALTERs (plus reconciliation, snapshot, trigger drop, phase flip) run in one transaction. SQLite's transactional DDL rolls the whole thing back on SIGKILL; a defensive resume path also completes a persisted partial swap |
| 5 | No resumable state | A restart does not know which phase/chunk it reached | Durable state machine in _migration(key,value) with phase, hwm (high-water mark) and batches_run; every step is idempotent (IF NOT EXISTS, OR IGNORE, INSERT OR REPLACE) |
The central correctness argument is that cutover is a full reconciliation under a write lock. BEGIN IMMEDIATE serialises the migration against the application writer, the shadow is upserted from the source and pruned, a _cutover_snapshot of the exact boundary is frozen, then the two ALTERs and the phase='done' flip commit atomically. Therefore:
new accounts == transform(_cutover_snapshot) (exactly-once, no loss, no mutation)
_cutover_snapshot == seed overlaid by committed writer_expected (concurrent writes survive)
Both are machine-checked by verify.sql.
The instrumentation trick that makes "killed between the two statements" testable: the cutover is streamed to sqlite3 through a pipe, and at the mid-transaction point we emit the dot-command .shell kill -9 $PPID. $PPID is the sqlite3 process, so sqlite3 itself is SIGKILLed while the transaction is open — the OS then rolls it back on the next open. A bash-level note_point provides the other ~260 interruption points.
Four files. Verified working on bash 5.3, sqlite3 3.53, with jq.
migrate.sh#!/usr/bin/env bash
# =============================================================================
# migrate.sh -- crash-safe ONLINE schema migration for SQLite, using only the
# sqlite3 CLI. Resumable after SIGKILL at any interruption point.
#
# Reshapes:
# accounts(id, owner, balance, memo)
# into:
# accounts(id, owner, balance_cents, memo, fingerprint)
#
# Env:
# MIG_DB path to the database (required)
# MIG_BATCH backfill chunk size (default 25)
# KILL_AT interruption point name to force-kill at (default none)
# POINTS_FILE append every point name to this file (default none)
# =============================================================================
set -u
DB="${MIG_DB:?MIG_DB is required}"
BATCH="${MIG_BATCH:-25}"
KILL_AT="${KILL_AT:-}"
POINTS_FILE="${POINTS_FILE:-}"
# ---- instrumentation --------------------------------------------------------
register_point() { # record only, never kill
[[ -n "$POINTS_FILE" ]] && printf '%s\n' "$1" >>"$POINTS_FILE"
}
note_point() { # record and (maybe) kill *this* shell
register_point "$1"
if [[ -n "$KILL_AT" && "$KILL_AT" == "$1" ]]; then
echo "[migrate] FORCED KILL at point '$1'" >&2
kill -9 "$$"
fi
}
q() { sqlite3 -cmd ".timeout 10000" "$DB" "$@"; }
# Run one SQL payload (may contain many statements) guarded by two kill points.
step() {
local point="$1" sql="$2"
note_point "${point}_before"
q "$sql" >/dev/null \
|| { echo "[migrate] sqlite3 failed at ${point}" >&2; exit 1; }
note_point "${point}_after"
}
get_meta() { q "SELECT value FROM _migration WHERE key='$1';"; }
set_meta() { q "INSERT OR REPLACE INTO _migration(key,value) VALUES('$1','$2');" >/dev/null; }
set_meta_p() { step "$1" "INSERT OR REPLACE INTO _migration(key,value) VALUES('$2','$3');"; }
table_exists() { [[ -n "$(q "SELECT 1 FROM sqlite_master WHERE type='table' AND name='$1';")" ]]; }
# fingerprint is the deterministic, auditable mapping of a source row.
FP="owner || '|' || CAST(balance AS TEXT) || '|' || COALESCE(memo,'')"
ensure_meta() {
q "PRAGMA journal_mode=WAL;" >/dev/null
q "CREATE TABLE IF NOT EXISTS _migration(key TEXT PRIMARY KEY, value TEXT);" >/dev/null
q "INSERT OR IGNORE INTO _migration(key,value) VALUES
('phase','init'),('hwm','0'),('batch','$BATCH'),
('cutover_seq','0'),('batches_run','0');" >/dev/null
q "CREATE TABLE IF NOT EXISTS writer_expected(
id INTEGER PRIMARY KEY, present INTEGER NOT NULL DEFAULT 1,
owner TEXT, balance INTEGER, memo TEXT, seq INTEGER NOT NULL DEFAULT 0);" >/dev/null
q "CREATE TABLE IF NOT EXISTS writer_log(seq INTEGER PRIMARY KEY, op TEXT, id INTEGER);" >/dev/null
}
# ---- phase: init ------------------------------------------------------------
init_target_sql() {
cat <<'SQL'
CREATE TABLE IF NOT EXISTS accounts_new(
id INTEGER PRIMARY KEY,
owner TEXT NOT NULL,
balance_cents INTEGER NOT NULL,
memo TEXT,
fingerprint TEXT NOT NULL
);
CREATE TABLE IF NOT EXISTS _cutover_snapshot(
id INTEGER PRIMARY KEY, owner TEXT, balance INTEGER, memo TEXT
);
SQL
}
triggers_sql() {
cat <<'SQL'
CREATE TRIGGER IF NOT EXISTS _mig_acc_ai AFTER INSERT ON accounts BEGIN
INSERT INTO accounts_new(id,owner,balance_cents,memo,fingerprint)
VALUES(NEW.id,NEW.owner,NEW.balance*100,NEW.memo,
NEW.owner || '|' || CAST(NEW.balance AS TEXT) || '|' || COALESCE(NEW.memo,''))
ON CONFLICT(id) DO UPDATE SET
owner=excluded.owner, balance_cents=excluded.balance_cents,
memo=excluded.memo, fingerprint=excluded.fingerprint;
END;
CREATE TRIGGER IF NOT EXISTS _mig_acc_au AFTER UPDATE ON accounts BEGIN
INSERT INTO accounts_new(id,owner,balance_cents,memo,fingerprint)
VALUES(NEW.id,NEW.owner,NEW.balance*100,NEW.memo,
NEW.owner || '|' || CAST(NEW.balance AS TEXT) || '|' || COALESCE(NEW.memo,''))
ON CONFLICT(id) DO UPDATE SET
owner=excluded.owner, balance_cents=excluded.balance_cents,
memo=excluded.memo, fingerprint=excluded.fingerprint;
END;
CREATE TRIGGER IF NOT EXISTS _mig_acc_ad AFTER DELETE ON accounts BEGIN
DELETE FROM accounts_new WHERE id=OLD.id;
END;
SQL
}
# ---- phase: backfill --------------------------------------------------------
do_backfill() {
local n=0 hwm remain
while :; do
hwm=$(get_meta hwm)
remain=$(q "SELECT count(*) FROM accounts WHERE id > COALESCE(CAST('$hwm' AS INTEGER),0);")
[[ "$remain" == "0" ]] && break
n=$((n+1))
# The read and the write live in ONE write transaction, so a concurrent
# delete can never leave a "ghost" row that the backfill re-inserts.
step "backfill_batch_${n}" "
BEGIN IMMEDIATE;
CREATE TEMP TABLE IF NOT EXISTS _batch(
id INTEGER PRIMARY KEY, owner TEXT, balance INTEGER, memo TEXT);
DELETE FROM _batch;
INSERT INTO _batch
SELECT id,owner,balance,memo FROM accounts
WHERE id > COALESCE(CAST('$hwm' AS INTEGER),0)
ORDER BY id LIMIT $BATCH;
INSERT OR IGNORE INTO accounts_new(id,owner,balance_cents,memo,fingerprint)
SELECT id,owner,balance*100,memo, $FP FROM _batch;
UPDATE _migration
SET value = COALESCE((SELECT CAST(max(id) AS TEXT) FROM _batch), value)
WHERE key='hwm';
UPDATE _migration
SET value = CAST(COALESCE(CAST(value AS INTEGER),0)+1 AS TEXT)
WHERE key='batches_run';
COMMIT;
"
done
set_meta_p "phase_to_cutover" phase cutover
}
# ---- phase: cutover ---------------------------------------------------------
do_cutover() {
# Defensive detection of an already/partially completed swap. With SQLite's
# transactional DDL a SIGKILL between the two ALTERs is rolled back, but a
# real non-transactional engine could persist the intermediate state.
if table_exists accounts_old && table_exists accounts && ! table_exists accounts_new; then
set_meta phase done; return
fi
if table_exists accounts_old && table_exists accounts_new && ! table_exists accounts; then
step "cutover_complete_partial" "
BEGIN IMMEDIATE;
ALTER TABLE accounts_new RENAME TO accounts;
COMMIT;"
set_meta phase done; return
fi
step "cutover_prep" "$(init_target_sql)$(triggers_sql)"
local kill_line=""
register_point "cutover_between" # always enumerated
if [[ -n "$KILL_AT" && "$KILL_AT" == "cutover_between" ]]; then
kill_line='.shell kill -9 $PPID' # kills sqlite3 mid-transaction
fi
note_point "cutover_swap_before"
{
echo "BEGIN IMMEDIATE;"
# Full reconciliation: newest source wins, deleted source rows removed.
echo "INSERT INTO accounts_new(id,owner,balance_cents,memo,fingerprint)
SELECT id,owner,balance*100,memo, $FP FROM accounts WHERE 1
ON CONFLICT(id) DO UPDATE SET
owner=excluded.owner, balance_cents=excluded.balance_cents,
memo=excluded.memo, fingerprint=excluded.fingerprint;"
echo "DELETE FROM accounts_new WHERE id NOT IN (SELECT id FROM accounts);"
# Freeze the exact cutover boundary for post-hoc proof.
echo "DELETE FROM _cutover_snapshot;"
echo "INSERT INTO _cutover_snapshot(id,owner,balance,memo)
SELECT id,owner,balance,memo FROM accounts;"
echo "UPDATE _migration
SET value=COALESCE((SELECT CAST(max(seq) AS TEXT) FROM writer_expected),'0')
WHERE key='cutover_seq';"
echo "DROP TRIGGER IF EXISTS _mig_acc_ai;"
echo "DROP TRIGGER IF EXISTS _mig_acc_au;"
echo "DROP TRIGGER IF EXISTS _mig_acc_ad;"
echo "ALTER TABLE accounts RENAME TO accounts_old;"
[[ -n "$kill_line" ]] && echo "$kill_line"
echo "ALTER TABLE accounts_new RENAME TO accounts;"
echo "UPDATE _migration SET value='done' WHERE key='phase';"
echo "COMMIT;"
} | sqlite3 "$DB"
local rc=${PIPESTATUS[1]}
if [[ "$rc" -ne 0 ]]; then
echo "[migrate] cutover interrupted (sqlite3 rc=$rc)" >&2
exit "$rc"
fi
note_point "cutover_swap_after"
}
# ---- phase: done ------------------------------------------------------------
finalize() {
step "finalize_drop_old" "DROP TABLE IF EXISTS accounts_old;"
step "finalize_drop_triggers" "
DROP TRIGGER IF EXISTS _mig_acc_ai;
DROP TRIGGER IF EXISTS _mig_acc_au;
DROP TRIGGER IF EXISTS _mig_acc_ad;"
}
# ---- driver -----------------------------------------------------------------
main() {
ensure_meta
local phase
phase=$(get_meta phase)
case "$phase" in
init)
step "init_target" "$(init_target_sql)"
step "init_triggers" "$(triggers_sql)"
set_meta_p "phase_to_backfill" phase backfill
;&
backfill)
do_backfill
;&
cutover)
do_cutover
;&
done)
finalize
;;
*)
echo "[migrate] unknown phase '$phase'" >&2; exit 2 ;;
esac
}
main "$@"
writer.sh (concurrent application traffic)#!/usr/bin/env bash
# Concurrent writer. Runs ONLY while phase='backfill'; stops at cutover.
# Every mutation touches accounts and writer_expected in the SAME IMMEDIATE
# transaction, so the writer's committed state is always well defined.
set -u
DB="${1:?db}"
SEED_ROWS="${2:-200}"
seq=0
while :; do
phase=$(sqlite3 -cmd ".timeout 10000" "$DB" \
"SELECT value FROM _migration WHERE key='phase';" \
2>/dev/null || true)
case "$phase" in
backfill) : ;; # keep writing
init|"") sleep 0.01; continue ;; # migration not ready yet
*) break ;; # cutover / done -> application stops
esac
seq=$((seq+1))
op=$(( seq % 7 ))
target=$(( (seq * 31) % SEED_ROWS + 1 ))
newid=$(( 100000 + seq ))
bal=$(( seq * 3 % 1000 ))
case "$op" in
0|1) # INSERT a brand-new row
sqlite3 -cmd ".timeout 10000" "$DB" " BEGIN IMMEDIATE;
INSERT INTO accounts(id,owner,balance,memo) VALUES($newid,'w$seq',$bal,'m$((seq%7))');
INSERT INTO writer_expected(id,present,owner,balance,memo,seq)
VALUES($newid,1,'w$seq',$bal,'m$((seq%7))',$seq)
ON CONFLICT(id) DO UPDATE SET present=1,owner=excluded.owner,
balance=excluded.balance,memo=excluded.memo,seq=excluded.seq;
INSERT INTO writer_log(seq,op,id) VALUES($seq,'insert',$newid);
COMMIT;" 2>/dev/null || true
;;
2|3|4) # UPDATE an existing row
sqlite3 -cmd ".timeout 10000" "$DB" " BEGIN IMMEDIATE;
UPDATE accounts SET balance=balance+1 WHERE id=$target;
INSERT INTO writer_expected(id,present,owner,balance,memo,seq)
SELECT id,1,owner,balance,memo,$seq FROM accounts WHERE id=$target
ON CONFLICT(id) DO UPDATE SET present=1,owner=excluded.owner,
balance=excluded.balance,memo=excluded.memo,seq=excluded.seq;
INSERT INTO writer_log(seq,op,id) VALUES($seq,'update',$target);
COMMIT;" 2>/dev/null || true
;;
*) # DELETE a row
sqlite3 -cmd ".timeout 10000" "$DB" " BEGIN IMMEDIATE;
DELETE FROM accounts WHERE id=$target;
INSERT INTO writer_expected(id,present,seq) VALUES($target,0,$seq)
ON CONFLICT(id) DO UPDATE SET present=0,seq=excluded.seq;
INSERT INTO writer_log(seq,op,id) VALUES($seq,'delete',$target);
COMMIT;" 2>/dev/null || true
;;
esac
done
verify.sql (invariant queries)WITH expected(id, owner, balance, memo) AS (
SELECT s.id, s.owner, s.balance, s.memo
FROM _seed s
WHERE s.id NOT IN (SELECT id FROM writer_expected)
UNION ALL
SELECT w.id, w.owner, w.balance, w.memo
FROM writer_expected w WHERE w.present = 1
)
SELECT
-- 1. exactly-once: no duplicate ids
(SELECT count(*) FROM accounts) AS n_new,
(SELECT count(DISTINCT id) FROM accounts) AS n_distinct,
(SELECT count(*) FROM _cutover_snapshot) AS n_snapshot,
-- 3. no loss / no mutation: every snapshot row maps correctly
(SELECT count(*) FROM (
SELECT s.id FROM _cutover_snapshot s
LEFT JOIN accounts a ON a.id = s.id
WHERE a.id IS NULL
OR a.owner IS NOT s.owner
OR a.balance_cents IS NOT s.balance * 100
OR a.memo IS NOT s.memo
OR a.fingerprint IS NOT (s.owner || '|' || CAST(s.balance AS TEXT) || '|' || COALESCE(s.memo,''))
)) AS n_mismatch,
-- 4. no extra rows
(SELECT count(*) FROM (
SELECT a.id FROM accounts a
LEFT JOIN _cutover_snapshot s ON s.id = a.id WHERE s.id IS NULL
)) AS n_extra,
-- 5. snapshot == committed writer state (seed overlaid)
(SELECT count(*) FROM (
SELECT e.id FROM expected e
LEFT JOIN _cutover_snapshot s ON s.id = e.id
WHERE s.id IS NULL OR s.owner IS NOT e.owner
OR s.balance IS NOT e.balance OR s.memo IS NOT e.memo
)) AS n_snap_mismatch,
-- 6. every op committed before the cutover boundary survives
(SELECT count(*) FROM (
SELECT l.id FROM writer_log l
LEFT JOIN writer_expected w ON w.id = l.id
LEFT JOIN _cutover_snapshot s ON s.id = l.id
WHERE l.seq <= COALESCE((SELECT CAST(value AS INTEGER) FROM _migration WHERE key='cutover_seq'),0)
AND ((w.present = 1 AND (s.id IS NULL OR s.owner IS NOT w.owner
OR s.balance IS NOT w.balance OR s.memo IS NOT w.memo))
OR (w.present = 0 AND s.id IS NOT NULL))
)) AS n_boundary_mismatch,
(SELECT count(*) FROM writer_log
WHERE seq <= COALESCE((SELECT CAST(value AS INTEGER) FROM _migration WHERE key='cutover_seq'),0))
AS n_boundary_ops,
-- 7. artefacts cleaned up
(SELECT count(*) FROM sqlite_master
WHERE type='trigger' AND name IN ('_mig_acc_ai','_mig_acc_au','_mig_acc_ad')) AS n_triggers,
(SELECT count(*) FROM sqlite_master WHERE type='table' AND name='accounts_old') AS n_old,
(SELECT count(*) FROM sqlite_master WHERE type='table' AND name='accounts_new') AS n_new_shadow;
harness.sh (kill injection + ledger)#!/usr/bin/env bash
# Kill-injection harness: for every interruption point, kill, resume, verify,
# and append one JSONL ledger record.
set -u
HERE=$(cd "$(dirname "$0")" && pwd)
WORK=${WORK:-$(mktemp -d)}
SEED_ROWS=${SEED_ROWS:-200}; BATCH=${BATCH:-20}
LEDGER=${LEDGER:-$HERE/ledger.jsonl}; MAX_POINTS=${MAX_POINTS:-0}; KEEP=${KEEP:-0}
cleanup() { [[ "$KEEP" == "1" ]] || rm -rf "$WORK"; }
trap cleanup EXIT
log() { printf '[harness] %s\n' "$*" >&2; }
val() { sqlite3 -cmd ".timeout 10000" "$1" "$2" 2>/dev/null || true; }
texists() { [[ "$(val "$1" "SELECT count(*) FROM sqlite_master WHERE type='table' AND name='$2';")" != "0" ]]; }
TEMPLATE=$WORK/template.db
make_template() {
rm -f "$TEMPLATE" "$TEMPLATE-wal" "$TEMPLATE-shm"
sqlite3 "$TEMPLATE" "PRAGMA journal_mode=WAL;
CREATE TABLE accounts(id INTEGER PRIMARY KEY, owner TEXT NOT NULL,
balance INTEGER NOT NULL DEFAULT 0, memo TEXT);
CREATE TABLE _seed(id INTEGER PRIMARY KEY, owner TEXT, balance INTEGER, memo TEXT);
WITH RECURSIVE c(i) AS (SELECT 1 UNION ALL SELECT i+1 FROM c WHERE i < $SEED_ROWS)
INSERT INTO accounts(id,owner,balance,memo)
SELECT i, 'owner_'||i, (i*37)%1000,
CASE WHEN i%5=0 THEN NULL ELSE 'memo_'||i END FROM c;
INSERT INTO _seed SELECT id,owner,balance,memo FROM accounts;
PRAGMA wal_checkpoint(TRUNCATE);" >/dev/null
}
discover_points() {
local db=$WORK/discover.db pf=$WORK/points.txt
cp "$TEMPLATE" "$db"; rm -f "$db-wal" "$db-shm"; : > "$pf"
MIG_DB="$db" MIG_BATCH="$BATCH" POINTS_FILE="$pf" "$HERE/migrate.sh" >/dev/null 2>&1 || true
mapfile -t POINTS < <(awk '!seen[$0]++' "$pf")
}
run_point() {
local pt="$1" run_db=$WORK/run.db
cp "$TEMPLATE" "$run_db"; rm -f "$run_db-wal" "$run_db-shm"
"$HERE/writer.sh" "$run_db" "$SEED_ROWS" >/dev/null 2>&1 & local wpid=$!
# sh -c wrapper keeps bash from printing "Killed" job noise
sh -c 'MIG_DB="$1" MIG_BATCH="$2" KILL_AT="$3" timeout -k 5 180 "$4"' \
sh "$run_db" "$BATCH" "$pt" "$HERE/migrate.sh" >"$WORK/kill_$pt.log" 2>&1
local kill_rc=$?
local s_phase s_hwm s_batches s_accounts s_target s_old s_trig
s_phase=$(val "$run_db" "SELECT COALESCE(value,'') FROM _migration WHERE key='phase';")
s_hwm=$(val "$run_db" "SELECT COALESCE(value,'0') FROM _migration WHERE key='hwm';")
s_batches=$(val "$run_db" "SELECT COALESCE(value,'0') FROM _migration WHERE key='batches_run';")
s_accounts=$(val "$run_db" "SELECT count(*) FROM accounts;" 2>/dev/null); s_accounts=${s_accounts:-0}
if texists "$run_db" accounts_new; then s_target=$(val "$run_db" "SELECT count(*) FROM accounts_new;"); else s_target=-1; fi
if texists "$run_db" accounts_old; then s_old=1; else s_old=0; fi
s_trig=$(val "$run_db" "SELECT count(*) FROM sqlite_master WHERE type='trigger' AND name LIKE '_mig_acc_%';"); s_trig=${s_trig:-0}
sh -c 'MIG_DB="$1" MIG_BATCH="$2" timeout -k 5 180 "$3"' \
sh "$run_db" "$BATCH" "$HERE/migrate.sh" >"$WORK/resume_$pt.log" 2>&1
local resume_rc=$?
local i; for i in $(seq 1 200); do kill -0 "$wpid" 2>/dev/null || break; sleep 0.05; done
kill -9 "$wpid" 2>/dev/null || true; wait "$wpid" 2>/dev/null || true
local e_phase e_hwm e_batches e_rows
e_phase=$(val "$run_db" "SELECT COALESCE(value,'') FROM _migration WHERE key='phase';")
e_hwm=$(val "$run_db" "SELECT COALESCE(value,'0') FROM _migration WHERE key='hwm';")
e_batches=$(val "$run_db" "SELECT COALESCE(value,'0') FROM _migration WHERE key='batches_run';")
e_rows=$(val "$run_db" "SELECT count(*) FROM accounts;" 2>/dev/null); e_rows=${e_rows:-0}
local vj n_new n_distinct n_snapshot n_mismatch n_extra n_snap_mismatch \
n_boundary_mismatch n_boundary_ops n_triggers n_old n_shadow
vj=$(sqlite3 -json "$run_db" <"$HERE/verify.sql" 2>/dev/null || echo '[]')
n_new=$(jq '.[0].n_new // 0' <<<"$vj")
n_distinct=$(jq '.[0].n_distinct // 0' <<<"$vj")
n_snapshot=$(jq '.[0].n_snapshot // 0' <<<"$vj")
n_mismatch=$(jq '.[0].n_mismatch // 0' <<<"$vj")
n_extra=$(jq '.[0].n_extra // 0' <<<"$vj")
n_snap_mismatch=$(jq '.[0].n_snap_mismatch // 0' <<<"$vj")
n_boundary_mismatch=$(jq '.[0].n_boundary_mismatch // 0' <<<"$vj")
n_boundary_ops=$(jq '.[0].n_boundary_ops // 0' <<<"$vj")
n_triggers=$(jq '.[0].n_triggers // 0' <<<"$vj")
n_old=$(jq '.[0].n_old // 0' <<<"$vj")
n_shadow=$(jq '.[0].n_new_shadow // 0' <<<"$vj")
local exactly_once no_loss no_extra snapshot_ok boundary_ok clean_ok result
[[ "$n_new" != "0" && "$n_new" == "$n_distinct" ]] && exactly_once=true || exactly_once=false
[[ "$n_mismatch" == "0" ]] && no_loss=true || no_loss=false
[[ "$n_extra" == "0" ]] && no_extra=true || no_extra=false
[[ "$n_snap_mismatch" == "0" ]] && snapshot_ok=true || snapshot_ok=false
[[ "$n_boundary_mismatch" == "0" ]] && boundary_ok=true || boundary_ok=false
[[ "$n_triggers" == "0" && "$n_old" == "0" && "$n_shadow" == "0" ]] && clean_ok=true || clean_ok=false
if [[ "$resume_rc" == "0" && "$exactly_once" == "true" && "$no_loss" == "true" \
&& "$no_extra" == "true" && "$snapshot_ok" == "true" \
&& "$boundary_ok" == "true" && "$clean_ok" == "true" ]]; then
result=PASS
else
result=FAIL
fi
jq -nc --arg point "$pt" --argjson kill_rc "${kill_rc:-0}" \
--arg s_phase "$s_phase" --argjson s_hwm "${s_hwm:-0}" \
--argjson s_batches "${s_batches:-0}" --argjson s_accounts "${s_accounts:-0}" \
--argjson s_target "${s_target:-0}" --argjson s_old "${s_old:-0}" --argjson s_trig "${s_trig:-0}" \
--argjson resume_rc "${resume_rc:-0}" --arg e_phase "$e_phase" --argjson e_hwm "${e_hwm:-0}" \
--argjson e_batches "${e_batches:-0}" --argjson e_rows "${e_rows:-0}" \
--argjson exactly_once "$exactly_once" --argjson no_loss "$no_loss" \
--argjson no_extra "$no_extra" --argjson snapshot_ok "$snapshot_ok" \
--argjson boundary_ok "$boundary_ok" --argjson clean_ok "$clean_ok" \
--argjson n_new "$n_new" --argjson n_distinct "$n_distinct" \
--argjson n_snapshot "$n_snapshot" --argjson n_boundary_ops "$n_boundary_ops" \
--arg result "$result" \
'{point:$point, killed:($kill_rc==137), kill_rc:$kill_rc,
resume_start:{phase:$s_phase, hwm:$s_hwm, batches_run:$s_batches,
accounts_rows:$s_accounts, target_rows:$s_target,
old_exists:($s_old==1), triggers:$s_trig},
replayed:{resume_rc:$resume_rc, final_phase:$e_phase, final_hwm:$e_hwm,
batches_run:$e_batches, batches_replayed:($e_batches-$s_batches),
final_rows:$e_rows, cutover_replayed:($s_phase=="cutover")},
invariants:{exactly_once:$exactly_once, no_loss:$no_loss, no_extra:$no_extra,
snapshot_matches_committed:$snapshot_ok,
boundary_preserved:$boundary_ok, artefacts_clean:$clean_ok,
boundary_ops:$n_boundary_ops, new_rows:$n_new,
distinct_ids:$n_distinct, snapshot_rows:$n_snapshot},
result:$result}' >>"$LEDGER"
printf '%-34s %-4s kill=%s resume=%s rows=%s replayed=%s\n' \
"$pt" "$result" "$kill_rc" "$resume_rc" "$e_rows" "$((e_batches-s_batches))" >&2
[[ "$result" == "PASS" ]]
}
main() {
make_template; discover_points
log "discovered ${#POINTS[@]} interruption points (SEED_ROWS=$SEED_ROWS BATCH=$BATCH)"
local selected=("${POINTS[@]}")
if [[ "$MAX_POINTS" -gt 0 && "${#POINTS[@]}" -gt "$MAX_POINTS" ]]; then
selected=(); local step=$(( ${#POINTS[@]} / MAX_POINTS )) i
for ((i=0; i<${#POINTS[@]}; i+=step)); do selected+=("${POINTS[$i]}"); done
fi
log "testing ${#selected[@]} points"; : >"$LEDGER"
local fails=0 pt
for pt in "${selected[@]}"; do run_point "$pt" || fails=$((fails+1)); done
log "RESULT: $(( ${#selected[@]} - fails )) pass, $fails fail -- ledger $LEDGER"
[[ "$fails" == "0" ]]
}
main "$@"
cd ~/online-migration
chmod +x migrate.sh writer.sh harness.sh
# quick suite (~25 points)
SEED_ROWS=60 BATCH=15 ./harness.sh
# full "hundreds of points" suite
SEED_ROWS=1000 BATCH=8 LEDGER=./ledger-big.jsonl ./harness.sh
migrate.sh can also be used standalone (no harness/writer):
MIG_DB=my.db MIG_BATCH=1000 ./migrate.sh
The full run used SEED_ROWS=1000, BATCH=8 (125 backfill chunks), with a concurrent writer doing inserts/updates/deletes throughout. Interruption points scale with the number of chunks: 2·batches + 2·init + 4·cutover + 4·finalize + 1.
$ jq -s '{points:length, pass:(map(select(.result=="PASS"))|length),
fail:(map(select(.result=="FAIL"))|length),
killed:(map(select(.killed))|length)}' ledger-big.jsonl
{
"points": 267,
"pass": 267,
"fail": 0,
"killed": 267
}
Every run was a genuine SIGKILL (kill_rc==137), including the mid-transaction case. Resume-start phases covered the whole state machine:
resume_start.phase |
points | meaning |
|---|---|---|
init |
5 | killed during/around shadow-table + trigger setup |
backfill |
252 | killed before/after every chunk; high-water mark resumed |
cutover |
5 | killed before cutover, after cutover, and between the two ALTERs |
done |
5 | killed during old-table/trigger cleanup |
cutover_between is the hard case. It was killed by sqlite3 executing .shell kill -9 $PPID after ALTER TABLE accounts RENAME TO accounts_old and before ALTER TABLE accounts_new RENAME TO accounts. Transactional DDL rolled it back; resume detected phase='cutover', replayed the swap, and passed:
{"point":"cutover_between","killed":true,"kill_rc":137,
"resume_start":{"phase":"cutover","hwm":100176,"batches_run":129,
"accounts_rows":1000,"target_rows":1000,"old_exists":false,"triggers":3},
"replayed":{"resume_rc":0,"final_phase":"done","final_hwm":100176,
"batches_run":129,"batches_replayed":0,"final_rows":1000,
"cutover_replayed":true},
"invariants":{"exactly_once":true,"no_loss":true,"no_extra":true,
"snapshot_matches_committed":true,"boundary_preserved":true,
"artefacts_clean":true,"boundary_ops":180,
"new_rows":1000,"distinct_ids":1000,"snapshot_rows":1000},
"result":"PASS"}
Concurrent writes really were in flight at the boundary: per run there were 180–215 writer operations committed at or before the cutover (cutover_seq), and all are reflected in _cutover_snapshot (n_boundary_mismatch == 0). batches_replayed_total = 17 515 shows actual work was redone after kills, not vacuous re-runs.
Column in verify.sql |
Must be | Proves |
|---|---|---|
n_new == n_distinct |
equal, non-zero | no duplicate/no missing id |
n_mismatch |
0 | every snapshot row present, correct balance_cents & fingerprint — no loss, no mutation |
n_extra |
0 | no row in the new table that was not committed at cutover |
n_snap_mismatch |
0 | frozen snapshot equals seed overlaid by writer_expected |
n_boundary_mismatch |
0 | every writer op with seq <= cutover_seq survives cutover |
n_triggers, n_old, n_new_shadow |
0 | cleanup complete (accounts_old, shadow, triggers gone) |
clean: n_new=40 n_mismatch=0 n_extra=0
mutate id=1: n_new=40 n_mismatch=1 n_extra=0
delete id=2: n_new=39 n_mismatch=2 n_extra=0
insert extra row: n_new=40 n_mismatch=2 n_extra=1
Break the migration — removing the capture triggers and the cutover reconciliation makes the harness fail every point (17/17 FAIL), while the intact code passes 267/267. This confirms the assertions are sensitive to real correctness bugs, not just cosmetic differences.
Mid-transaction kill is real — a standalone check confirmed .shell kill -9 $PPID yields sqlite3 rc=137 and leaves the pre-cutover table state intact (the transaction rolls back), so the "between the two statements" test exercises the actual atomicity guarantee rather than a no-op.
One JSON object per interruption point (JSONL), e.g.:
{"point":"backfill_batch_1_before","killed":true,"kill_rc":137,
"resume_start":{"phase":"backfill","hwm":0,"batches_run":0,"accounts_rows":1001,
"target_rows":12,"old_exists":false,"triggers":3},
"replayed":{"resume_rc":0,"final_phase":"done","final_hwm":100204,
"batches_run":129,"batches_replayed":129,"final_rows":999,
"cutover_replayed":false},
"invariants":{"exactly_once":true,"no_loss":true,"no_extra":true,
"snapshot_matches_committed":true,"boundary_preserved":true,
"artefacts_clean":true,"boundary_ops":209,"new_rows":999,
"distinct_ids":999,"snapshot_rows":999},
"result":"PASS"}
It records exactly what the task asks for: the state the resume started from (resume_start), the work replayed (replayed.batches_replayed, cutover_replayed, final_hwm), and the invariants verified (invariants).
# Evidence - Problem class: bash-sqlite-online-schema-backfill-exactly-once-cutover - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-25T22:29:59.376Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a crash-safe online schema migration in bash driving only the sqlite3 CLI: reshape a writer-visible table through a shadow table, a chunked idempotent backfill that records resumable high-water marks, trigger-based capture of concurrent writer changes, and a final atomic cutover, with the whole migration resumable after an arbitrary SIGKILL at any instruction. The harness must inject forced kills at hundreds of instrumented interruption points, resume each run, and then prove via SQL invariant queries that every committed source row appears exactly once in the new table with the target schema, that no row was lost, duplicated or mutated, and that concurrent writes committed before the cutover boundary survive it, including the case where the cutover itself is interrupted between its two statements. Emit a per-interruption-point JSONL ledger recording the state the resume started from, the work it replayed, and the invariants verified.", "environment": "bash", "language": "shell", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "bash-sqlite-online-schema-backfill-exactly-once-cutover", "provider": "openrouter", "solved_at": "2026-09-25T22:29:59.377Z", "version": "5.2"}sqlite3The task is a problem class, not a single bug: reshape a writer-visible table without stopping writers, and survive SIGKILL at any instruction, then prove with SQL that the result is exactly-once. A naive implementation fails in five distinct ways. Each failure mode maps to a specific race or missing invariant.
| # | Failure mode | Why it happens | Fix in this design |
|---|---|---|---|
| 1 | Duplicated rows on resume | Backfill re-runs a chunk after a crash; plain INSERT inserts twice |
INSERT OR IGNORE into a shadow table keyed by the same PRIMARY KEY; backfill is idempotent |
| 2 | Ghost rows (row deleted, then re-inserted) | Backfill does SELECT then INSERT as two statements; a concurrent DELETE commits in between and its trigger deletes a not-yet-present shadow row, then the backfill inserts it |
Read+write in one BEGIN IMMEDIATE transaction (INSERT … SELECT …), so no writer can interleave between snapshot and write |
| 3 | Lost concurrent UPDATE/DELETE |
Backfill copies the row, then a writer changes it; shadow keeps the stale copy | AFTER INSERT/UPDATE triggers upsert the newest source row (ON CONFLICT(id) DO UPDATE), AFTER DELETE trigger removes it |
| 4 | Torn cutover | ALTER TABLE src RENAME …; ALTER TABLE shadow RENAME …; executed non-atomically leaves no src table if killed between them |
Both ALTERs (plus reconciliation, snapshot, trigger drop, phase flip) run in one transaction. SQLite's transactional DDL rolls the whole thing back on SIGKILL; a defensive resume path also completes a persisted partial swap |
| 5 | No resumable state | A restart does not know which phase/chunk it reached | Durable state machine in _migration(key,value) with phase, hwm (high-water mark) and batches_run; every step is idempotent (IF NOT EXISTS, OR IGNORE, INSERT OR REPLACE) |
The central correctness argument is that cutover is a full reconciliation under a write lock. BEGIN IMMEDIATE serialises the migration against the application writer, the shadow is upserted from the source and pruned, a _cutover_snapshot of the exact boundary is frozen, then the two ALTERs and the phase='done' flip commit atomically. Therefore:
new accounts == transform(_cutover_snapshot) (exactly-once, no loss, no mutation)
_cutover_snapshot == seed overlaid by committed writer_expected (concurrent writes survive)
Both are machine-checked by verify.sql.
The instrumentation trick that makes "killed between the two statements" testable: the cutover is streamed to sqlite3 through a pipe, and at the mid-transaction point we emit the dot-command .shell kill -9 $PPID. $PPID is the sqlite3 process, so sqlite3 itself is SIGKILLed while the transaction is open — the OS then rolls it back on the next open. A bash-level note_point provides the other ~260 interruption points.
Four files. Verified working on bash 5.3, sqlite3 3.53, with jq.
migrate.sh#!/usr/bin/env bash
# =============================================================================
# migrate.sh -- crash-safe ONLINE schema migration for SQLite, using only the
# sqlite3 CLI. Resumable after SIGKILL at any interruption point.
#
# Reshapes:
# accounts(id, owner, balance, memo)
# into:
# accounts(id, owner, balance_cents, memo, fingerprint)
#
# Env:
# MIG_DB path to the database (required)
# MIG_BATCH backfill chunk size (default 25)
# KILL_AT interruption point name to force-kill at (default none)
# POINTS_FILE append every point name to this file (default none)
# =============================================================================
set -u
DB="${MIG_DB:?MIG_DB is required}"
BATCH="${MIG_BATCH:-25}"
KILL_AT="${KILL_AT:-}"
POINTS_FILE="${POINTS_FILE:-}"
# ---- instrumentation --------------------------------------------------------
register_point() { # record only, never kill
[[ -n "$POINTS_FILE" ]] && printf '%s\n' "$1" >>"$POINTS_FILE"
}
note_point() { # record and (maybe) kill *this* shell
register_point "$1"
if [[ -n "$KILL_AT" && "$KILL_AT" == "$1" ]]; then
echo "[migrate] FORCED KILL at point '$1'" >&2
kill -9 "$$"
fi
}
q() { sqlite3 -cmd ".timeout 10000" "$DB" "$@"; }
# Run one SQL payload (may contain many statements) guarded by two kill points.
step() {
local point="$1" sql="$2"
note_point "${point}_before"
q "$sql" >/dev/null \
|| { echo "[migrate] sqlite3 failed at ${point}" >&2; exit 1; }
note_point "${point}_after"
}
get_meta() { q "SELECT value FROM _migration WHERE key='$1';"; }
set_meta() { q "INSERT OR REPLACE INTO _migration(key,value) VALUES('$1','$2');" >/dev/null; }
set_meta_p() { step "$1" "INSERT OR REPLACE INTO _migration(key,value) VALUES('$2','$3');"; }
table_exists() { [[ -n "$(q "SELECT 1 FROM sqlite_master WHERE type='table' AND name='$1';")" ]]; }
# fingerprint is the deterministic, auditable mapping of a source row.
FP="owner || '|' || CAST(balance AS TEXT) || '|' || COALESCE(memo,'')"
ensure_meta() {
q "PRAGMA journal_mode=WAL;" >/dev/null
q "CREATE TABLE IF NOT EXISTS _migration(key TEXT PRIMARY KEY, value TEXT);" >/dev/null
q "INSERT OR IGNORE INTO _migration(key,value) VALUES
('phase','init'),('hwm','0'),('batch','$BATCH'),
('cutover_seq','0'),('batches_run','0');" >/dev/null
q "CREATE TABLE IF NOT EXISTS writer_expected(
id INTEGER PRIMARY KEY, present INTEGER NOT NULL DEFAULT 1,
owner TEXT, balance INTEGER, memo TEXT, seq INTEGER NOT NULL DEFAULT 0);" >/dev/null
q "CREATE TABLE IF NOT EXISTS writer_log(seq INTEGER PRIMARY KEY, op TEXT, id INTEGER);" >/dev/null
}
# ---- phase: init ------------------------------------------------------------
init_target_sql() {
cat <<'SQL'
CREATE TABLE IF NOT EXISTS accounts_new(
id INTEGER PRIMARY KEY,
owner TEXT NOT NULL,
balance_cents INTEGER NOT NULL,
memo TEXT,
fingerprint TEXT NOT NULL
);
CREATE TABLE IF NOT EXISTS _cutover_snapshot(
id INTEGER PRIMARY KEY, owner TEXT, balance INTEGER, memo TEXT
);
SQL
}
triggers_sql() {
cat <<'SQL'
CREATE TRIGGER IF NOT EXISTS _mig_acc_ai AFTER INSERT ON accounts BEGIN
INSERT INTO accounts_new(id,owner,balance_cents,memo,fingerprint)
VALUES(NEW.id,NEW.owner,NEW.balance*100,NEW.memo,
NEW.owner || '|' || CAST(NEW.balance AS TEXT) || '|' || COALESCE(NEW.memo,''))
ON CONFLICT(id) DO UPDATE SET
owner=excluded.owner, balance_cents=excluded.balance_cents,
memo=excluded.memo, fingerprint=excluded.fingerprint;
END;
CREATE TRIGGER IF NOT EXISTS _mig_acc_au AFTER UPDATE ON accounts BEGIN
INSERT INTO accounts_new(id,owner,balance_cents,memo,fingerprint)
VALUES(NEW.id,NEW.owner,NEW.balance*100,NEW.memo,
NEW.owner || '|' || CAST(NEW.balance AS TEXT) || '|' || COALESCE(NEW.memo,''))
ON CONFLICT(id) DO UPDATE SET
owner=excluded.owner, balance_cents=excluded.balance_cents,
memo=excluded.memo, fingerprint=excluded.fingerprint;
END;
CREATE TRIGGER IF NOT EXISTS _mig_acc_ad AFTER DELETE ON accounts BEGIN
DELETE FROM accounts_new WHERE id=OLD.id;
END;
SQL
}
# ---- phase: backfill --------------------------------------------------------
do_backfill() {
local n=0 hwm remain
while :; do
hwm=$(get_meta hwm)
remain=$(q "SELECT count(*) FROM accounts WHERE id > COALESCE(CAST('$hwm' AS INTEGER),0);")
[[ "$remain" == "0" ]] && break
n=$((n+1))
# The read and the write live in ONE write transaction, so a concurrent
# delete can never leave a "ghost" row that the backfill re-inserts.
step "backfill_batch_${n}" "
BEGIN IMMEDIATE;
CREATE TEMP TABLE IF NOT EXISTS _batch(
id INTEGER PRIMARY KEY, owner TEXT, balance INTEGER, memo TEXT);
DELETE FROM _batch;
INSERT INTO _batch
SELECT id,owner,balance,memo FROM accounts
WHERE id > COALESCE(CAST('$hwm' AS INTEGER),0)
ORDER BY id LIMIT $BATCH;
INSERT OR IGNORE INTO accounts_new(id,owner,balance_cents,memo,fingerprint)
SELECT id,owner,balance*100,memo, $FP FROM _batch;
UPDATE _migration
SET value = COALESCE((SELECT CAST(max(id) AS TEXT) FROM _batch), value)
WHERE key='hwm';
UPDATE _migration
SET value = CAST(COALESCE(CAST(value AS INTEGER),0)+1 AS TEXT)
WHERE key='batches_run';
COMMIT;
"
done
set_meta_p "phase_to_cutover" phase cutover
}
# ---- phase: cutover ---------------------------------------------------------
do_cutover() {
# Defensive detection of an already/partially completed swap. With SQLite's
# transactional DDL a SIGKILL between the two ALTERs is rolled back, but a
# real non-transactional engine could persist the intermediate state.
if table_exists accounts_old && table_exists accounts && ! table_exists accounts_new; then
set_meta phase done; return
fi
if table_exists accounts_old && table_exists accounts_new && ! table_exists accounts; then
step "cutover_complete_partial" "
BEGIN IMMEDIATE;
ALTER TABLE accounts_new RENAME TO accounts;
COMMIT;"
set_meta phase done; return
fi
step "cutover_prep" "$(init_target_sql)$(triggers_sql)"
local kill_line=""
register_point "cutover_between" # always enumerated
if [[ -n "$KILL_AT" && "$KILL_AT" == "cutover_between" ]]; then
kill_line='.shell kill -9 $PPID' # kills sqlite3 mid-transaction
fi
note_point "cutover_swap_before"
{
echo "BEGIN IMMEDIATE;"
# Full reconciliation: newest source wins, deleted source rows removed.
echo "INSERT INTO accounts_new(id,owner,balance_cents,memo,fingerprint)
SELECT id,owner,balance*100,memo, $FP FROM accounts WHERE 1
ON CONFLICT(id) DO UPDATE SET
owner=excluded.owner, balance_cents=excluded.balance_cents,
memo=excluded.memo, fingerprint=excluded.fingerprint;"
echo "DELETE FROM accounts_new WHERE id NOT IN (SELECT id FROM accounts);"
# Freeze the exact cutover boundary for post-hoc proof.
echo "DELETE FROM _cutover_snapshot;"
echo "INSERT INTO _cutover_snapshot(id,owner,balance,memo)
SELECT id,owner,balance,memo FROM accounts;"
echo "UPDATE _migration
SET value=COALESCE((SELECT CAST(max(seq) AS TEXT) FROM writer_expected),'0')
WHERE key='cutover_seq';"
echo "DROP TRIGGER IF EXISTS _mig_acc_ai;"
echo "DROP TRIGGER IF EXISTS _mig_acc_au;"
echo "DROP TRIGGER IF EXISTS _mig_acc_ad;"
echo "ALTER TABLE accounts RENAME TO accounts_old;"
[[ -n "$kill_line" ]] && echo "$kill_line"
echo "ALTER TABLE accounts_new RENAME TO accounts;"
echo "UPDATE _migration SET value='done' WHERE key='phase';"
echo "COMMIT;"
} | sqlite3 "$DB"
local rc=${PIPESTATUS[1]}
if [[ "$rc" -ne 0 ]]; then
echo "[migrate] cutover interrupted (sqlite3 rc=$rc)" >&2
exit "$rc"
fi
note_point "cutover_swap_after"
}
# ---- phase: done ------------------------------------------------------------
finalize() {
step "finalize_drop_old" "DROP TABLE IF EXISTS accounts_old;"
step "finalize_drop_triggers" "
DROP TRIGGER IF EXISTS _mig_acc_ai;
DROP TRIGGER IF EXISTS _mig_acc_au;
DROP TRIGGER IF EXISTS _mig_acc_ad;"
}
# ---- driver -----------------------------------------------------------------
main() {
ensure_meta
local phase
phase=$(get_meta phase)
case "$phase" in
init)
step "init_target" "$(init_target_sql)"
step "init_triggers" "$(triggers_sql)"
set_meta_p "phase_to_backfill" phase backfill
;&
backfill)
do_backfill
;&
cutover)
do_cutover
;&
done)
finalize
;;
*)
echo "[migrate] unknown phase '$phase'" >&2; exit 2 ;;
esac
}
main "$@"
writer.sh (concurrent application traffic)#!/usr/bin/env bash
# Concurrent writer. Runs ONLY while phase='backfill'; stops at cutover.
# Every mutation touches accounts and writer_expected in the SAME IMMEDIATE
# transaction, so the writer's committed state is always well defined.
set -u
DB="${1:?db}"
SEED_ROWS="${2:-200}"
seq=0
while :; do
phase=$(sqlite3 -cmd ".timeout 10000" "$DB" \
"SELECT value FROM _migration WHERE key='phase';" \
2>/dev/null || true)
case "$phase" in
backfill) : ;; # keep writing
init|"") sleep 0.01; continue ;; # migration not ready yet
*) break ;; # cutover / done -> application stops
esac
seq=$((seq+1))
op=$(( seq % 7 ))
target=$(( (seq * 31) % SEED_ROWS + 1 ))
newid=$(( 100000 + seq ))
bal=$(( seq * 3 % 1000 ))
case "$op" in
0|1) # INSERT a brand-new row
sqlite3 -cmd ".timeout 10000" "$DB" " BEGIN IMMEDIATE;
INSERT INTO accounts(id,owner,balance,memo) VALUES($newid,'w$seq',$bal,'m$((seq%7))');
INSERT INTO writer_expected(id,present,owner,balance,memo,seq)
VALUES($newid,1,'w$seq',$bal,'m$((seq%7))',$seq)
ON CONFLICT(id) DO UPDATE SET present=1,owner=excluded.owner,
balance=excluded.balance,memo=excluded.memo,seq=excluded.seq;
INSERT INTO writer_log(seq,op,id) VALUES($seq,'insert',$newid);
COMMIT;" 2>/dev/null || true
;;
2|3|4) # UPDATE an existing row
sqlite3 -cmd ".timeout 10000" "$DB" " BEGIN IMMEDIATE;
UPDATE accounts SET balance=balance+1 WHERE id=$target;
INSERT INTO writer_expected(id,present,owner,balance,memo,seq)
SELECT id,1,owner,balance,memo,$seq FROM accounts WHERE id=$target
ON CONFLICT(id) DO UPDATE SET present=1,owner=excluded.owner,
balance=excluded.balance,memo=excluded.memo,seq=excluded.seq;
INSERT INTO writer_log(seq,op,id) VALUES($seq,'update',$target);
COMMIT;" 2>/dev/null || true
;;
*) # DELETE a row
sqlite3 -cmd ".timeout 10000" "$DB" " BEGIN IMMEDIATE;
DELETE FROM accounts WHERE id=$target;
INSERT INTO writer_expected(id,present,seq) VALUES($target,0,$seq)
ON CONFLICT(id) DO UPDATE SET present=0,seq=excluded.seq;
INSERT INTO writer_log(seq,op,id) VALUES($seq,'delete',$target);
COMMIT;" 2>/dev/null || true
;;
esac
done
verify.sql (invariant queries)WITH expected(id, owner, balance, memo) AS (
SELECT s.id, s.owner, s.balance, s.memo
FROM _seed s
WHERE s.id NOT IN (SELECT id FROM writer_expected)
UNION ALL
SELECT w.id, w.owner, w.balance, w.memo
FROM writer_expected w WHERE w.present = 1
)
SELECT
-- 1. exactly-once: no duplicate ids
(SELECT count(*) FROM accounts) AS n_new,
(SELECT count(DISTINCT id) FROM accounts) AS n_distinct,
(SELECT count(*) FROM _cutover_snapshot) AS n_snapshot,
-- 3. no loss / no mutation: every snapshot row maps correctly
(SELECT count(*) FROM (
SELECT s.id FROM _cutover_snapshot s
LEFT JOIN accounts a ON a.id = s.id
WHERE a.id IS NULL
OR a.owner IS NOT s.owner
OR a.balance_cents IS NOT s.balance * 100
OR a.memo IS NOT s.memo
OR a.fingerprint IS NOT (s.owner || '|' || CAST(s.balance AS TEXT) || '|' || COALESCE(s.memo,''))
)) AS n_mismatch,
-- 4. no extra rows
(SELECT count(*) FROM (
SELECT a.id FROM accounts a
LEFT JOIN _cutover_snapshot s ON s.id = a.id WHERE s.id IS NULL
)) AS n_extra,
-- 5. snapshot == committed writer state (seed overlaid)
(SELECT count(*) FROM (
SELECT e.id FROM expected e
LEFT JOIN _cutover_snapshot s ON s.id = e.id
WHERE s.id IS NULL OR s.owner IS NOT e.owner
OR s.balance IS NOT e.balance OR s.memo IS NOT e.memo
)) AS n_snap_mismatch,
-- 6. every op committed before the cutover boundary survives
(SELECT count(*) FROM (
SELECT l.id FROM writer_log l
LEFT JOIN writer_expected w ON w.id = l.id
LEFT JOIN _cutover_snapshot s ON s.id = l.id
WHERE l.seq <= COALESCE((SELECT CAST(value AS INTEGER) FROM _migration WHERE key='cutover_seq'),0)
AND ((w.present = 1 AND (s.id IS NULL OR s.owner IS NOT w.owner
OR s.balance IS NOT w.balance OR s.memo IS NOT w.memo))
OR (w.present = 0 AND s.id IS NOT NULL))
)) AS n_boundary_mismatch,
(SELECT count(*) FROM writer_log
WHERE seq <= COALESCE((SELECT CAST(value AS INTEGER) FROM _migration WHERE key='cutover_seq'),0))
AS n_boundary_ops,
-- 7. artefacts cleaned up
(SELECT count(*) FROM sqlite_master
WHERE type='trigger' AND name IN ('_mig_acc_ai','_mig_acc_au','_mig_acc_ad')) AS n_triggers,
(SELECT count(*) FROM sqlite_master WHERE type='table' AND name='accounts_old') AS n_old,
(SELECT count(*) FROM sqlite_master WHERE type='table' AND name='accounts_new') AS n_new_shadow;
harness.sh (kill injection + ledger)#!/usr/bin/env bash
# Kill-injection harness: for every interruption point, kill, resume, verify,
# and append one JSONL ledger record.
set -u
HERE=$(cd "$(dirname "$0")" && pwd)
WORK=${WORK:-$(mktemp -d)}
SEED_ROWS=${SEED_ROWS:-200}; BATCH=${BATCH:-20}
LEDGER=${LEDGER:-$HERE/ledger.jsonl}; MAX_POINTS=${MAX_POINTS:-0}; KEEP=${KEEP:-0}
cleanup() { [[ "$KEEP" == "1" ]] || rm -rf "$WORK"; }
trap cleanup EXIT
log() { printf '[harness] %s\n' "$*" >&2; }
val() { sqlite3 -cmd ".timeout 10000" "$1" "$2" 2>/dev/null || true; }
texists() { [[ "$(val "$1" "SELECT count(*) FROM sqlite_master WHERE type='table' AND name='$2';")" != "0" ]]; }
TEMPLATE=$WORK/template.db
make_template() {
rm -f "$TEMPLATE" "$TEMPLATE-wal" "$TEMPLATE-shm"
sqlite3 "$TEMPLATE" "PRAGMA journal_mode=WAL;
CREATE TABLE accounts(id INTEGER PRIMARY KEY, owner TEXT NOT NULL,
balance INTEGER NOT NULL DEFAULT 0, memo TEXT);
CREATE TABLE _seed(id INTEGER PRIMARY KEY, owner TEXT, balance INTEGER, memo TEXT);
WITH RECURSIVE c(i) AS (SELECT 1 UNION ALL SELECT i+1 FROM c WHERE i < $SEED_ROWS)
INSERT INTO accounts(id,owner,balance,memo)
SELECT i, 'owner_'||i, (i*37)%1000,
CASE WHEN i%5=0 THEN NULL ELSE 'memo_'||i END FROM c;
INSERT INTO _seed SELECT id,owner,balance,memo FROM accounts;
PRAGMA wal_checkpoint(TRUNCATE);" >/dev/null
}
discover_points() {
local db=$WORK/discover.db pf=$WORK/points.txt
cp "$TEMPLATE" "$db"; rm -f "$db-wal" "$db-shm"; : > "$pf"
MIG_DB="$db" MIG_BATCH="$BATCH" POINTS_FILE="$pf" "$HERE/migrate.sh" >/dev/null 2>&1 || true
mapfile -t POINTS < <(awk '!seen[$0]++' "$pf")
}
run_point() {
local pt="$1" run_db=$WORK/run.db
cp "$TEMPLATE" "$run_db"; rm -f "$run_db-wal" "$run_db-shm"
"$HERE/writer.sh" "$run_db" "$SEED_ROWS" >/dev/null 2>&1 & local wpid=$!
# sh -c wrapper keeps bash from printing "Killed" job noise
sh -c 'MIG_DB="$1" MIG_BATCH="$2" KILL_AT="$3" timeout -k 5 180 "$4"' \
sh "$run_db" "$BATCH" "$pt" "$HERE/migrate.sh" >"$WORK/kill_$pt.log" 2>&1
local kill_rc=$?
local s_phase s_hwm s_batches s_accounts s_target s_old s_trig
s_phase=$(val "$run_db" "SELECT COALESCE(value,'') FROM _migration WHERE key='phase';")
s_hwm=$(val "$run_db" "SELECT COALESCE(value,'0') FROM _migration WHERE key='hwm';")
s_batches=$(val "$run_db" "SELECT COALESCE(value,'0') FROM _migration WHERE key='batches_run';")
s_accounts=$(val "$run_db" "SELECT count(*) FROM accounts;" 2>/dev/null); s_accounts=${s_accounts:-0}
if texists "$run_db" accounts_new; then s_target=$(val "$run_db" "SELECT count(*) FROM accounts_new;"); else s_target=-1; fi
if texists "$run_db" accounts_old; then s_old=1; else s_old=0; fi
s_trig=$(val "$run_db" "SELECT count(*) FROM sqlite_master WHERE type='trigger' AND name LIKE '_mig_acc_%';"); s_trig=${s_trig:-0}
sh -c 'MIG_DB="$1" MIG_BATCH="$2" timeout -k 5 180 "$3"' \
sh "$run_db" "$BATCH" "$HERE/migrate.sh" >"$WORK/resume_$pt.log" 2>&1
local resume_rc=$?
local i; for i in $(seq 1 200); do kill -0 "$wpid" 2>/dev/null || break; sleep 0.05; done
kill -9 "$wpid" 2>/dev/null || true; wait "$wpid" 2>/dev/null || true
local e_phase e_hwm e_batches e_rows
e_phase=$(val "$run_db" "SELECT COALESCE(value,'') FROM _migration WHERE key='phase';")
e_hwm=$(val "$run_db" "SELECT COALESCE(value,'0') FROM _migration WHERE key='hwm';")
e_batches=$(val "$run_db" "SELECT COALESCE(value,'0') FROM _migration WHERE key='batches_run';")
e_rows=$(val "$run_db" "SELECT count(*) FROM accounts;" 2>/dev/null); e_rows=${e_rows:-0}
local vj n_new n_distinct n_snapshot n_mismatch n_extra n_snap_mismatch \
n_boundary_mismatch n_boundary_ops n_triggers n_old n_shadow
vj=$(sqlite3 -json "$run_db" <"$HERE/verify.sql" 2>/dev/null || echo '[]')
n_new=$(jq '.[0].n_new // 0' <<<"$vj")
n_distinct=$(jq '.[0].n_distinct // 0' <<<"$vj")
n_snapshot=$(jq '.[0].n_snapshot // 0' <<<"$vj")
n_mismatch=$(jq '.[0].n_mismatch // 0' <<<"$vj")
n_extra=$(jq '.[0].n_extra // 0' <<<"$vj")
n_snap_mismatch=$(jq '.[0].n_snap_mismatch // 0' <<<"$vj")
n_boundary_mismatch=$(jq '.[0].n_boundary_mismatch // 0' <<<"$vj")
n_boundary_ops=$(jq '.[0].n_boundary_ops // 0' <<<"$vj")
n_triggers=$(jq '.[0].n_triggers // 0' <<<"$vj")
n_old=$(jq '.[0].n_old // 0' <<<"$vj")
n_shadow=$(jq '.[0].n_new_shadow // 0' <<<"$vj")
local exactly_once no_loss no_extra snapshot_ok boundary_ok clean_ok result
[[ "$n_new" != "0" && "$n_new" == "$n_distinct" ]] && exactly_once=true || exactly_once=false
[[ "$n_mismatch" == "0" ]] && no_loss=true || no_loss=false
[[ "$n_extra" == "0" ]] && no_extra=true || no_extra=false
[[ "$n_snap_mismatch" == "0" ]] && snapshot_ok=true || snapshot_ok=false
[[ "$n_boundary_mismatch" == "0" ]] && boundary_ok=true || boundary_ok=false
[[ "$n_triggers" == "0" && "$n_old" == "0" && "$n_shadow" == "0" ]] && clean_ok=true || clean_ok=false
if [[ "$resume_rc" == "0" && "$exactly_once" == "true" && "$no_loss" == "true" \
&& "$no_extra" == "true" && "$snapshot_ok" == "true" \
&& "$boundary_ok" == "true" && "$clean_ok" == "true" ]]; then
result=PASS
else
result=FAIL
fi
jq -nc --arg point "$pt" --argjson kill_rc "${kill_rc:-0}" \
--arg s_phase "$s_phase" --argjson s_hwm "${s_hwm:-0}" \
--argjson s_batches "${s_batches:-0}" --argjson s_accounts "${s_accounts:-0}" \
--argjson s_target "${s_target:-0}" --argjson s_old "${s_old:-0}" --argjson s_trig "${s_trig:-0}" \
--argjson resume_rc "${resume_rc:-0}" --arg e_phase "$e_phase" --argjson e_hwm "${e_hwm:-0}" \
--argjson e_batches "${e_batches:-0}" --argjson e_rows "${e_rows:-0}" \
--argjson exactly_once "$exactly_once" --argjson no_loss "$no_loss" \
--argjson no_extra "$no_extra" --argjson snapshot_ok "$snapshot_ok" \
--argjson boundary_ok "$boundary_ok" --argjson clean_ok "$clean_ok" \
--argjson n_new "$n_new" --argjson n_distinct "$n_distinct" \
--argjson n_snapshot "$n_snapshot" --argjson n_boundary_ops "$n_boundary_ops" \
--arg result "$result" \
'{point:$point, killed:($kill_rc==137), kill_rc:$kill_rc,
resume_start:{phase:$s_phase, hwm:$s_hwm, batches_run:$s_batches,
accounts_rows:$s_accounts, target_rows:$s_target,
old_exists:($s_old==1), triggers:$s_trig},
replayed:{resume_rc:$resume_rc, final_phase:$e_phase, final_hwm:$e_hwm,
batches_run:$e_batches, batches_replayed:($e_batches-$s_batches),
final_rows:$e_rows, cutover_replayed:($s_phase=="cutover")},
invariants:{exactly_once:$exactly_once, no_loss:$no_loss, no_extra:$no_extra,
snapshot_matches_committed:$snapshot_ok,
boundary_preserved:$boundary_ok, artefacts_clean:$clean_ok,
boundary_ops:$n_boundary_ops, new_rows:$n_new,
distinct_ids:$n_distinct, snapshot_rows:$n_snapshot},
result:$result}' >>"$LEDGER"
printf '%-34s %-4s kill=%s resume=%s rows=%s replayed=%s\n' \
"$pt" "$result" "$kill_rc" "$resume_rc" "$e_rows" "$((e_batches-s_batches))" >&2
[[ "$result" == "PASS" ]]
}
main() {
make_template; discover_points
log "discovered ${#POINTS[@]} interruption points (SEED_ROWS=$SEED_ROWS BATCH=$BATCH)"
local selected=("${POINTS[@]}")
if [[ "$MAX_POINTS" -gt 0 && "${#POINTS[@]}" -gt "$MAX_POINTS" ]]; then
selected=(); local step=$(( ${#POINTS[@]} / MAX_POINTS )) i
for ((i=0; i<${#POINTS[@]}; i+=step)); do selected+=("${POINTS[$i]}"); done
fi
log "testing ${#selected[@]} points"; : >"$LEDGER"
local fails=0 pt
for pt in "${selected[@]}"; do run_point "$pt" || fails=$((fails+1)); done
log "RESULT: $(( ${#selected[@]} - fails )) pass, $fails fail -- ledger $LEDGER"
[[ "$fails" == "0" ]]
}
main "$@"
cd ~/online-migration
chmod +x migrate.sh writer.sh harness.sh
# quick suite (~25 points)
SEED_ROWS=60 BATCH=15 ./harness.sh
# full "hundreds of points" suite
SEED_ROWS=1000 BATCH=8 LEDGER=./ledger-big.jsonl ./harness.sh
migrate.sh can also be used standalone (no harness/writer):
MIG_DB=my.db MIG_BATCH=1000 ./migrate.sh
The full run used SEED_ROWS=1000, BATCH=8 (125 backfill chunks), with a concurrent writer doing inserts/updates/deletes throughout. Interruption points scale with the number of chunks: 2·batches + 2·init + 4·cutover + 4·finalize + 1.
$ jq -s '{points:length, pass:(map(select(.result=="PASS"))|length),
fail:(map(select(.result=="FAIL"))|length),
killed:(map(select(.killed))|length)}' ledger-big.jsonl
{
"points": 267,
"pass": 267,
"fail": 0,
"killed": 267
}
Every run was a genuine SIGKILL (kill_rc==137), including the mid-transaction case. Resume-start phases covered the whole state machine:
resume_start.phase |
points | meaning |
|---|---|---|
init |
5 | killed during/around shadow-table + trigger setup |
backfill |
252 | killed before/after every chunk; high-water mark resumed |
cutover |
5 | killed before cutover, after cutover, and between the two ALTERs |
done |
5 | killed during old-table/trigger cleanup |
cutover_between is the hard case. It was killed by sqlite3 executing .shell kill -9 $PPID after ALTER TABLE accounts RENAME TO accounts_old and before ALTER TABLE accounts_new RENAME TO accounts. Transactional DDL rolled it back; resume detected phase='cutover', replayed the swap, and passed:
{"point":"cutover_between","killed":true,"kill_rc":137,
"resume_start":{"phase":"cutover","hwm":100176,"batches_run":129,
"accounts_rows":1000,"target_rows":1000,"old_exists":false,"triggers":3},
"replayed":{"resume_rc":0,"final_phase":"done","final_hwm":100176,
"batches_run":129,"batches_replayed":0,"final_rows":1000,
"cutover_replayed":true},
"invariants":{"exactly_once":true,"no_loss":true,"no_extra":true,
"snapshot_matches_committed":true,"boundary_preserved":true,
"artefacts_clean":true,"boundary_ops":180,
"new_rows":1000,"distinct_ids":1000,"snapshot_rows":1000},
"result":"PASS"}
Concurrent writes really were in flight at the boundary: per run there were 180–215 writer operations committed at or before the cutover (cutover_seq), and all are reflected in _cutover_snapshot (n_boundary_mismatch == 0). batches_replayed_total = 17 515 shows actual work was redone after kills, not vacuous re-runs.
Column in verify.sql |
Must be | Proves |
|---|---|---|
n_new == n_distinct |
equal, non-zero | no duplicate/no missing id |
n_mismatch |
0 | every snapshot row present, correct balance_cents & fingerprint — no loss, no mutation |
n_extra |
0 | no row in the new table that was not committed at cutover |
n_snap_mismatch |
0 | frozen snapshot equals seed overlaid by writer_expected |
n_boundary_mismatch |
0 | every writer op with seq <= cutover_seq survives cutover |
n_triggers, n_old, n_new_shadow |
0 | cleanup complete (accounts_old, shadow, triggers gone) |
clean: n_new=40 n_mismatch=0 n_extra=0
mutate id=1: n_new=40 n_mismatch=1 n_extra=0
delete id=2: n_new=39 n_mismatch=2 n_extra=0
insert extra row: n_new=40 n_mismatch=2 n_extra=1
Break the migration — removing the capture triggers and the cutover reconciliation makes the harness fail every point (17/17 FAIL), while the intact code passes 267/267. This confirms the assertions are sensitive to real correctness bugs, not just cosmetic differences.
Mid-transaction kill is real — a standalone check confirmed .shell kill -9 $PPID yields sqlite3 rc=137 and leaves the pre-cutover table state intact (the transaction rolls back), so the "between the two statements" test exercises the actual atomicity guarantee rather than a no-op.
One JSON object per interruption point (JSONL), e.g.:
{"point":"backfill_batch_1_before","killed":true,"kill_rc":137,
"resume_start":{"phase":"backfill","hwm":0,"batches_run":0,"accounts_rows":1001,
"target_rows":12,"old_exists":false,"triggers":3},
"replayed":{"resume_rc":0,"final_phase":"done","final_hwm":100204,
"batches_run":129,"batches_replayed":129,"final_rows":999,
"cutover_replayed":false},
"invariants":{"exactly_once":true,"no_loss":true,"no_extra":true,
"snapshot_matches_committed":true,"boundary_preserved":true,
"artefacts_clean":true,"boundary_ops":209,"new_rows":999,
"distinct_ids":999,"snapshot_rows":999},
"result":"PASS"}
It records exactly what the task asks for: the state the resume started from (resume_start), the work replayed (replayed.batches_replayed, cutover_replayed, final_hwm), and the invariants verified (invariants).
# Evidence - Problem class: bash-sqlite-online-schema-backfill-exactly-once-cutover - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-25T22:29:59.376Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a crash-safe online schema migration in bash driving only the sqlite3 CLI: reshape a writer-visible table through a shadow table, a chunked idempotent backfill that records resumable high-water marks, trigger-based capture of concurrent writer changes, and a final atomic cutover, with the whole migration resumable after an arbitrary SIGKILL at any instruction. The harness must inject forced kills at hundreds of instrumented interruption points, resume each run, and then prove via SQL invariant queries that every committed source row appears exactly once in the new table with the target schema, that no row was lost, duplicated or mutated, and that concurrent writes committed before the cutover boundary survive it, including the case where the cutover itself is interrupted between its two statements. Emit a per-interruption-point JSONL ledger recording the state the resume started from, the work it replayed, and the invariants verified.", "environment": "bash", "language": "shell", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "bash-sqlite-online-schema-backfill-exactly-once-cutover", "provider": "openrouter", "solved_at": "2026-09-25T22:29:59.377Z", "version": "5.2"}