Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
1 change: 1 addition & 0 deletions CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -40,6 +40,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
- A retract that removes several values of one attribute in one call now hides all of them (#371).
- Queries no longer lose or duplicate facts when more than 65,535 facts are waiting for a checkpoint (#445; also fixed in v2.0.3).
- **A file shorter than its meta page count is refused at open with `STG-044`** (#497). Open never compared the meta page's `page_count` with the file's length. A truncated file (an interrupted copy, a partial download) opened, and its queries and checkpoints then failed with `INT-049` after the WAL had accepted writes. A meta with a `page_count` far past the end opened too: its next checkpoint wrote at that page id, leaving a sparse file of up to 4 EiB, and `verify()` scanned to that count and never finished. Open now refuses both, read-write and read-only, without modifying the file. It does not fall back to the other meta page, because a valid newer meta means that checkpoint happened. A checkpoint now fails with `INT-049` instead of writing a meta that counts pages the backend does not hold, and `verify()` reports a `page_count` past the end as `STG-044` and stops its page scan at the end of the file. `BrowserDb` is not checked: it keeps only live pages (#440), so its store has no length to compare. New code `STG-044`.
- **A WAL from a later checkpoint is refused at open with `STG-047`** (#535). Opening an older `.graph` next to a `.wal` created after a later checkpoint, as happens when a backup is restored and the current WAL is left in place, replayed the WAL on top of the older file and reported success: the later transactions were applied and the ones between the two checkpoints were silently missing, and the next checkpoint made the gap permanent. The WAL's header records the generation it was created at; open now refuses, read-write and read-only, when that is newer than every meta page in the file, and leaves both files unmodified. A WAL with an older base (a crash between a checkpoint's commit and its WAL delete) replays as before. v2.x WALs record no generation, so v2.x cannot detect this.
- **A file shorter than one page is refused at open with `STG-045` unless it is a torn first write** (#506). Open treated any file under 4 KiB as a new database, because it holds no whole page, and a read-write open wrote a new empty database over it. A database cut below one page by an interrupted copy, or an unrelated file at the path, was silently replaced. Now such a file opens as a new database only when its bytes are zeros or a prefix of the first meta page a new database writes (what a crash during creation can leave, the rule a torn full page 0 already followed); anything else is `STG-045`, read-write and read-only, and the file is not modified. A zero-length file is still a new database. New code `STG-045`.
- **A failed checkpoint is never retried on the same handle** (#390). A checkpoint that failed after it may have written (a failed write, a full disk, a failed `fsync`) could be retried by the next checkpoint. After a failed `fsync` the operating system may have dropped the written pages, and the checkpoint's meta page may have reached the disk although the call failed; a retry could then overwrite pages that meta references, and a crash during the retry left a file that failed to read with `STG-029`. Now every later write, checkpoint and index rebuild through that handle fails with the new `STG-046`, queries keep working, and the close-time checkpoint is skipped. Reopening the database recovers everything committed: it is all in the WAL. A `rebuild_indexes()` refused with `STG-041` writes nothing and does not count as failed. A fault-injection matrix now covers EIO, torn and short writes, a full disk and failed fsyncs at every write and sync of transacts, checkpoints, the close-time checkpoint and index rebuilds.
- **A commit made after a torn WAL entry is no longer lost on recovery** (#513). Recovery replays the WAL up to its first partial or damaged entry, but the writer appended after the end of the file. After a crash during an append, the next session's commits went in after the partial entry, so a second crash before any checkpoint lost them, although each had been fsynced and reported as committed. A failed append (short write, full disk, I/O error) did the same to the next commit through that handle. Opening a database for writing now cuts the WAL back to the end of its last valid entry, and syncs it, before anything is appended. After a failed append, every later write through that handle fails with the new `WAL-007` until the database is reopened or a `checkpoint()` succeeds. The transaction whose append failed is not applied; after a reopen it is either there in full (its entry reached the disk) or not at all. Affected every release since v0.5.0.
Expand Down
2 changes: 1 addition & 1 deletion CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -201,7 +201,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are

## Test Coverage

**1428 tests** (1418 passing, 10 ignored; unit + integration + doc).
**1432 tests** (1422 passing, 10 ignored; unit + integration + doc).
See `docs/TEST_COVERAGE.md` for the full per-file breakdown.

**Testing conventions** — see the Testing Conventions section below before writing any tests.
Expand Down
2 changes: 1 addition & 1 deletion README.md
Original file line number Diff line number Diff line change
Expand Up @@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit

```bash
cargo run # interactive Datalog REPL
cargo test # run 1428 tests
cargo test # run 1432 tests
cargo run < demos/demo_recursive.txt # recursive rules demo
```

Expand Down
7 changes: 3 additions & 4 deletions docs/DURABILITY.md
Original file line number Diff line number Diff line change
Expand Up @@ -54,7 +54,7 @@ Batching is the other lever: `begin_write()`, several `execute()` calls and one
Opening a file-backed database:

1. Takes the file lock (see [Where a database can live](#where-a-database-can-live)). A lock held by a crashed process is released by the kernel when it dies, so there is never a stale lock to clean up.
2. Reads both meta pages and opens at the valid one with the higher generation. If only one is valid, the WAL's recorded base generation and the pages in the file are checked to make sure the damaged one did not hold a newer completed checkpoint; if it did, the open fails with `STG-033` instead of silently going back.
2. Reads both meta pages and opens at the valid one with the higher generation. If only one is valid, the WAL's recorded base generation and the pages in the file are checked to make sure the damaged one did not hold a newer completed checkpoint; if it did, the open fails with `STG-033` instead of silently going back. If the WAL was created at a later generation than the newest meta page, it belongs to a later state of the file and the open fails with `STG-047` (#535).
3. Checks the meta page against the file: unknown feature bits are `STG-034`, a file shorter than the meta page says is `STG-044`.
4. Replays the WAL into memory, skipping entries at or below the file's checkpointed transaction count, and stopping at the first truncated or damaged entry.
5. For a read-write open, cuts the WAL back to the end of its last valid entry and syncs it, so the next commit lands where replay will find it (#513).
Expand Down Expand Up @@ -134,7 +134,7 @@ A process that does not have the database open can do the same through a read-on

1. Stop every process that uses the database.
2. Move the current `app.graph` and `app.graph.wal` aside rather than deleting them.
3. **Make sure no `app.graph.wal` is left in the directory**, then copy in the backup's `app.graph`, and its `app.graph.wal` if the backup has one. A WAL from a later state of the database, next to an older `app.graph`, is replayed on top of it today and leaves a gap in the history without an error (#535).
3. **Make sure no `app.graph.wal` is left in the directory**, then copy in the backup's `app.graph`, and its `app.graph.wal` if the backup has one. A WAL from a later state of the database, next to an older `app.graph`, would leave a gap in the history; open refuses it with `STG-047` (#535). v2.x cannot detect it and replays it.
4. Open the database and run `verify()` (below).

## Checking and repairing a file
Expand Down Expand Up @@ -191,13 +191,12 @@ Every error has a code (`MinigrafError::code()`); the [error reference](https://
| **Use another library version.** The file is not modified | `STG-006` (format newer than this library), `STG-034` (feature bits from a newer v3.x), `STG-028` (format older than v7: open with v2.x first), `WAL-002` (WAL from another version: open with that version and `checkpoint()`) |
| **Repair.** Found by `verify()` | `STG-035`, `STG-038`, `STG-039` → `rebuild_indexes()`. `STG-036`, `STG-040` → restore |
| **Restore from backup.** The file is damaged or is not this database; a failed open leaves it unmodified | `STG-029`, `STG-030`, `STG-031` (a damaged page; inside an index, try `rebuild_indexes()` first), `STG-032`, `STG-033`, `STG-041`, `STG-044`, `STG-045`, `STG-002` (not a Minigraf file: check the path) |
| **Restore, or accept losing the WAL** | `WAL-001` (the `.wal` file is not a WAL). Copy both files first. Deleting the `.wal` opens the database without the transactions since the last checkpoint |
| **Restore, or accept losing the WAL** | `WAL-001` (the `.wal` file is not a WAL), `STG-047` (the `.wal` is from a later state than `app.graph`, usually a restore that left the current WAL in place: move the WAL aside, or restore the `app.graph` it belongs to). Copy both files first. Deleting the `.wal` opens the database without the transactions since the last checkpoint |

A write that returns an I/O error may still have committed (see [Failures while running](#failures-while-running)); check before writing it again.

## Known limitations

- **A WAL from a later checkpoint is replayed onto an older `.graph`** (#535, open). Restoring an old `app.graph` next to a newer `app.graph.wal` leaves a silent gap in the history. Workaround: remove every `.wal` before restoring, as in [Restoring](#restoring).
- **A damaged WAL entry ends replay.** Replay stops at the first entry whose CRC fails, and a read-write open then cuts the WAL there, so a bit flip in the middle of the WAL loses that entry and every later one without an error. With `SyncMode::Full` this needs damage after the sync; a torn entry from a crash is always the last one.
- **One writing process at a time.** A database is single-writer; a second process gets `STG-026`. Share one handle inside a process, or put one process in front of the database.
- **No online backup from another process.** A read-only open needs every read-write handle closed. Copy from inside the writing process (see [Backups](#backups)), or use a volume snapshot.
Expand Down
15 changes: 15 additions & 0 deletions docs/ERROR_REFERENCE.md
Original file line number Diff line number Diff line change
Expand Up @@ -158,6 +158,7 @@ with no `CodedError` anywhere in its chain.
| STG-044 | File shorter than its meta page count | Storage |
| STG-045 | File shorter than one page and not a new database | Storage |
| STG-046 | Earlier checkpoint failed on this handle | Storage |
| STG-047 | WAL is from a later checkpoint | Storage |
| WAL-001 | Invalid WAL magic number | WAL |
| WAL-002 | Unsupported WAL version | WAL |
| WAL-003 | Value size exceeds maximum | WAL |
Expand Down Expand Up @@ -2324,6 +2325,20 @@ Nothing committed is lost. Every committed transaction is still in the WAL, and

---

### STG-047 WAL is from a later checkpoint

**Error text**: `WAL is from a later checkpoint: it was created at generation {} but the file is at generation {}. Replaying it would leave a gap in the history (was an older .graph restored next to a newer .wal?)`

**Cause**: The `.wal` file's header records the generation of the checkpoint that was current when the WAL was created. A WAL is deleted after the next checkpoint commits, so it is never newer than the `.graph` file it belongs to. This WAL is newer than every meta page in the file: the `.graph` is an older copy of the database, such as a restored backup, and the WAL beside it came from the live database. Its entries start after a checkpoint this file does not have, so replaying them would apply the later transactions and silently skip the ones in between. Earlier versions did that. Neither file is modified, read-write or read-only. v2.x WALs record no generation, so v2.x cannot detect this.

**Resolution**:
- If you are restoring a backup: move the `.wal` aside and open again. The database opens at the backup.
- If the `.graph` was replaced by mistake: put back the `.graph` that the WAL belongs to.

**Scenario**: An operator copies last night's `app.graph` over the current one and leaves the current `app.graph.wal` in the directory.

---

## WAL — Write-Ahead Log Errors

WAL errors relate to the sidecar `.wal` file written alongside the `.graph` file.
Expand Down
2 changes: 1 addition & 1 deletion docs/TEST_COVERAGE.md

Large diffs are not rendered by default.

9 changes: 9 additions & 0 deletions src/error.rs
Original file line number Diff line number Diff line change
Expand Up @@ -190,6 +190,7 @@ pub(crate) enum ErrorCode {
Stg044,
Stg045,
Stg046,
Stg047,
Wal001,
Wal002,
Wal003,
Expand Down Expand Up @@ -1108,6 +1109,12 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[
"an earlier checkpoint failed on this handle and is not retried; reopen the database",
ErrorCategory::Storage,
),
(
ErrorCode::Stg047,
"STG-047",
"WAL is from a later checkpoint: it was created at generation {} but the file is at generation {}. Replaying it would leave a gap in the history (was an older .graph restored next to a newer .wal?)",
ErrorCategory::Storage,
),
(
ErrorCode::Wal001,
"WAL-001",
Expand Down Expand Up @@ -2030,6 +2037,7 @@ mod tests {
| ErrorCode::Stg044
| ErrorCode::Stg045
| ErrorCode::Stg046
| ErrorCode::Stg047
| ErrorCode::Wal001
| ErrorCode::Wal002
| ErrorCode::Wal003
Expand Down Expand Up @@ -2255,6 +2263,7 @@ mod tests {
ErrorCode::Stg044,
ErrorCode::Stg045,
ErrorCode::Stg046,
ErrorCode::Stg047,
ErrorCode::Wal001,
ErrorCode::Wal002,
ErrorCode::Wal003,
Expand Down
71 changes: 71 additions & 0 deletions src/storage/persistent_facts.rs
Original file line number Diff line number Diff line change
Expand Up @@ -199,6 +199,7 @@ impl<B: StorageBackend + 'static> PersistentFactStorage<B> {
{
bail_coded!(ErrorCode::Stg045, tail.len());
}
check_wal_not_later(1, wal_base)?;
return Ok(Opened::Fresh);
}
let page0 = backend.read_page(0)?;
Expand All @@ -211,9 +212,19 @@ impl<B: StorageBackend + 'static> PersistentFactStorage<B> {
match (slot_a, slot_b) {
(SlotState::Valid(a), SlotState::Valid(b)) => {
let m = if a.generation >= b.generation { a } else { b };
check_wal_not_later(m.generation, wal_base)?;
check_fits(&*backend, &m)?;
Ok(Opened::Meta(m))
}
(SlotState::Valid(m), SlotState::Empty) | (SlotState::Empty, SlotState::Valid(m)) => {
// The other slot was never written, so no later generation
// was committed to this file.
check_wal_not_later(m.generation, wal_base)?;
m.check_features()?;
check_fits(&*backend, &m)?;
check_single_valid(&*backend, m, wal_base)?;
Ok(Opened::Meta(m))
}
(SlotState::Valid(m), _) | (_, SlotState::Valid(m)) => {
// Refuse an unreadable file before probing its pages.
m.check_features()?;
Expand All @@ -223,6 +234,8 @@ impl<B: StorageBackend + 'static> PersistentFactStorage<B> {
}
_ => {
if let Some(h) = LegacyHeaderV7::detect(&page0)? {
// Migration opens at generation 1; a v2.x WAL reads as 1.
check_wal_not_later(1, wal_base)?;
return Ok(Opened::LegacyV7(h));
}
// A torn page-0 write while committing a migration: the backup
Expand All @@ -232,6 +245,7 @@ impl<B: StorageBackend + 'static> PersistentFactStorage<B> {
&& m.generation == 1
&& m.page_count == page_count
{
check_wal_not_later(1, wal_base)?;
m.check_features()?;
if !read_only {
backend.write_page(0, &m.encode())?;
Expand All @@ -240,6 +254,7 @@ impl<B: StorageBackend + 'static> PersistentFactStorage<B> {
return Ok(Opened::Meta(m));
}
if page_count <= 2 && is_torn_initial_meta(&*backend, &page0)? {
check_wal_not_later(1, wal_base)?;
return Ok(Opened::Fresh);
}
if page0.get(0..4) != Some(&crate::storage::MAGIC_NUMBER[..]) {
Expand Down Expand Up @@ -801,6 +816,19 @@ fn check_written(backend: &dyn StorageBackend, m: &MetaPage) -> Result<()> {
Ok(())
}

/// Fail with STG-047 if the WAL was created at a generation later than `g`,
/// the newest this file holds (#535). A WAL is created at the generation
/// active at the time and deleted after the next checkpoint commits, so its
/// base is never newer than the file it belongs to: the file is an older copy,
/// such as a restored backup. A base at or below `g` is fine (a crash between
/// a checkpoint's commit and its WAL delete leaves an older base, #457).
fn check_wal_not_later(g: u64, wal_base: Option<u64>) -> Result<()> {
match wal_base {
Some(b) if b > g => bail_coded!(ErrorCode::Stg047, b, g),
_ => Ok(()),
}
}

/// Exactly one meta slot is valid, at generation `g`. Fail with STG-033 if a
/// later commit `g + 1` completed and its meta was lost (spec §4.1.1 table).
fn check_single_valid(
Expand Down Expand Up @@ -1353,6 +1381,49 @@ mod tests {
assert_eq!(open_mem(&mem, Some(1)).unwrap().generation(), 2);
}

#[test]
fn wal_from_a_later_generation_is_stg_047() {
// Both slots valid (gens 2 and 3): a WAL created at gen 4 belongs to
// a later state of the file, such as the one this copy was taken from.
let mem = three_generations();
let before = snapshot(&mem);
assert_eq!(code(open_mem(&mem, Some(4)).err().unwrap()), "STG-047");
let ro = PersistentFactStorage::open_read_only(mem.clone(), 16, Some(4));
assert_eq!(code(ro.err().unwrap()), "STG-047");
assert!(
snapshot(&mem) == before,
"a failed open must not modify the file"
);
// A WAL at or below the chosen generation replays as before (#457).
for b in 1..=3 {
assert_eq!(open_mem(&mem, Some(b)).unwrap().generation(), 3);
}
}

#[test]
fn wal_later_than_a_single_generation_file_is_stg_047() {
// Gen 1 only: page 1 was never written as a meta page.
let mem = MemoryBackend::new();
assert_eq!(open_mem(&mem, None).unwrap().generation(), 1);
assert_eq!(open_mem(&mem, Some(1)).unwrap().generation(), 1);
assert_eq!(code(open_mem(&mem, Some(2)).err().unwrap()), "STG-047");
}

#[test]
fn wal_later_than_a_new_or_v7_file_is_stg_047() {
// An empty file next to a WAL from generation 2.
let mem = MemoryBackend::new();
assert_eq!(code(open_mem(&mem, Some(2)).err().unwrap()), "STG-047");
assert_eq!(mem.page_count().unwrap(), 0, "nothing initialised");
assert_eq!(open_mem(&mem, Some(1)).unwrap().generation(), 1);
// A v7 file migrates to generation 1; a v2.x WAL reads as base 1.
let v7 = v7_file(&sample_facts(3), 3);
let before = snapshot(&v7);
assert_eq!(code(open_mem(&v7, Some(2)).err().unwrap()), "STG-047");
assert!(snapshot(&v7) == before, "not migrated");
assert_eq!(open_mem(&v7, Some(1)).unwrap().generation(), 1);
}

#[test]
fn wal_newer_than_the_valid_meta_is_stg_033() {
let mut mem = three_generations();
Expand Down
Loading
Loading