benbjohnson / benbjohnson/litestream

Sync() can decode O(db-size) bytes, delaying checkpoints after large L0 snapshot

Open
#1,508 1 comment 0 reactions 0 assignees View on GitHub
bug
Dominant language
Go
Stars
14.4k
Forks
414
Avg merge
7d 1h
Merged PRs (30d)
21

Description

## Bug Description

An incremental sync may linearly scan the last-synced level-0 LTX file to verify a single page. When that L0 is large — a DB-sized snapshot, or a single large transaction that the size cap could not split — this is an O(L0 size) read on the checkpoint's critical path, holding the DB's single sync lock for its whole duration. The most dramatic case is the first sync after a snapshot (an O(database size) scan), but the same cost recurs in steady state whenever the previous L0 was large.

### Where it happens

`(*DB).syncLocked` → `verifyAndSyncWithExecutor` → `verifyWithExecutor` → `lastPageMatch` opens the last-synced level-0 LTX file and calls `ltx.Decoder.DecodePage` in a loop until it finds the last WAL page's page number (or hits EOF):

```go
// lastPageMatch (db.go): find the last WAL page in the last LTX file
buf := make([]byte, dec.Header().PageSize)
for {
var hdr ltx.PageHeader
if err := dec.DecodePage(&hdr, buf); errors.Is(err, io.EOF) {
return false, nil // page not found in LTX file
} else if err != nil {
return false, fmt.Errorf("decode ltx page: %w", err)
}
if pgno != hdr.Pgno {
continue // page number doesn't match
}
if !bytes.Equal(data, buf) {
continue // page data doesn't match
}
return true, nil
}
```

### Why the scanned file can be large

The scan target is `db.LTXPath(0, exec.pos.TXID, exec.pos.TXID)` — the L0 the *previous* sync sealed. The scan cost is therefore bounded by **the size of the largest recent L0**, and there are two independent ways an L0 grows far past the incremental norm:

**1. Snapshots.** A fresh generation seeds its base this way: the first full capture is a level-0 file at TXID 1 containing every page

**2. A single large transaction.** Even with no snapshot, the `MaxSyncWALBytes` cap can only stop the WAL scan at a transaction commit boundary.

### When `lastPageMatch` runs (and when it doesn't)

`verifyWithExecutor` has several early returns before `lastPageMatch`. It runs only on an incremental sync that **continues an in-progress WAL**, specifically when all of the following are false:

- first sync (`exec.pos.TXID == 0`);
- the WAL is shorter than where the last sync ended, i.e. it was truncated since (`info.offset > walFileSize`) — this is the escape after a checkpoint-truncation;
- the last LTX ended at the WAL header, or the last sync advanced fewer than two frames.

The expensive case: the first incremental sync after a snapshot, when the WAL has not been truncated in between. We hit this on every server startup (each of our tasks replicates to a unique backup location).

## Environment

**Litestream version:**

```text
v0.5.17
```

**Operating system & version:**
Linux (container), arm64

**Installation method:**
Built from source (Docker image)

**Storage backend:**
S3 (S3-compatible). The hot path is local LTX file I/O during verify, so it reproduces with any backend.

## Steps to Reproduce

1. Replicate a large database (ours is ~125 GB) so that its base snapshot L0 is large.
2. Let replication start (which writes the DB-sized snapshot L0 at TXID 1) and keep the DB under write load.
3. Observe that the first incremental sync after the snapshot spends its time in `lastPageMatch` scanning the entire snapshot L0, holding the sync lock, before it can produce the next L0.

**Expected behavior:**
Per-sync verification cost is independent of database/LTX size (a bounded, ~O(1) page lookup), so the first sync after a snapshot completes promptly regardless of DB size. It that's not possible, at least faster than it takes to decode the full DB, e.g. by decoding the index to find the page.

**Actual behavior:**
The first sync after a snapshot scans the entire DB-sized snapshot L0. On a large DB this takes minutes, holding the sync lock the whole time and stalling any concurrent `Sync()`.

## Evidence

```text
# One generation's L0 objects (level 0000/), size in bytes:
02:37:08 64553795762 .../0000/0000000000000001-0000000000000001.ltx # base snapshot L0 (~64 GB)
02:51:34 1916565538 .../0000/0000000000000002-0000000000000002.ltx # first incremental L0
02:51:47 7411385 .../0000/0000000000000003-0000000000000003.ltx
02:51:56 1885787 .../0000/0000000000000005-0000000000000005.ltx
... ~50 MB .../0000/ ... # steady-state incrementals
```

The 14m26s gap between TXID 1 (02:37:08) and TXID 2 (02:51:34) is the first post-snapshot `verify` scanning the 64 GB base L0. Once the position advances onto the small incremental L0s, subsequent verifies are fast.

(TXID 2 is itself ~1.9 GB — far above the 64 MB cap — because it is a single large transaction that the cap could not split, illustrating source #2 above.)

A goroutine dump captured mid-scan on a separate ~125 GB deployment (4 KB pages) shows the background `monitor → Sync` goroutine `[runnable]`, mid `read()` syscall, inside `DecodePage → lastPageMatch`, while **21 other `Sync()` callers were blocked in `execSem.Acquire`** behind it (the scan holds the single sync lock for its entire duration).

Goroutine dump (sync mid-scan; single sync lock held by the scan)

```text
# Background monitor sync, actively decoding L0 pages inside verify.
# DecodePage(..., {buf, 0x1000, 0x1000}) -> 0x1000 = 4096 = page size
# lastPageMatch(..., 0x2b8cd8dc8, 0x1018) -> prevWALOffset ~11.7 GB, frameSize 0x1018 = 4120
goroutine 52 [runnable]:
syscall.read(...)
os.(*File).Read(...) # unbuffered, per-page
io.ReadFull(...)
github.com/superfly/ltx.(*Decoder).DecodePage(...)
github.com/benbjohnson/litestream.(*DB).lastPageMatch(...)
github.com/benbjohnson/litestream.(*DB).verifyWithExecutor(...)
github.com/benbjohnson/litestream.(*DB).verifyAndSyncWithExecutor(...)
github.com/benbjohnson/litestream.(*DB).syncLocked(...)
github.com/benbjohnson/litestream.(*DB).syncOnce(...)
github.com/benbjohnson/litestream.(*DB).Sync(...)
github.com/benbjohnson/litestream.(*DB).monitor(...)
```

The scan's throughput matches this access pattern rather than a bulk read: ~64 GB in ~14 min ≈ 74 MB/s, doing (per 4 KB page) three small (unbuffered) `io.ReadFull` syscalls + an LZ4 decompress + a CRC64 over every byte, single-threaded — ~29 µs/page over ~30 M pages. (`ltx.NewDecoder` wraps the bare `*os.File` with no buffering, so a buffered reader here would independently speed the fallback scan.)

## Additional Context

**Suggested fix:** locate the page via the LTX page index instead of scanning. Each LTX file already stores a page index at the tail (`PageIndexElem{Offset, Size}` per page number), so `lastPageMatch` could look up the target `pgno` and read just that one page — O(1) instead of O(LTX size). This needs a "load the page index without a full sequential scan" path plus a "read a single page at a known offset" path on the ltx decoder, which don't exist today (the index is currently only obtainable via a full stream + `Decoder.Close()`, and `DecodePage` is sequential-only). An alternative that avoids ltx random access is to retain the last-synced LTX's page identity in memory when it is written (the encoder already holds its index) and consult that during verify.

**Degradation under sustained writes.** The scan is paid on the first sync after every snapshot and takes `≈ snapshot_L0_size / scan_rate` (local read + LZ4 decompress). While it runs, the WAL keeps growing at the write rate, so the sync falls behind by `write_rate × scan_time`. Because a sufficiently large/overwritten WAL is itself what forces the next full snapshot, the snapshot-sized L0 — and its scan — can recur and compound. There is effectively a write-rate ceiling of `scan_rate`: below it the scan is a bounded one-time cost per snapshot (the 14-minute gap above); above it each cycle falls further behind and re-snapshots, and replication cannot keep up. This ceiling is *lower on larger databases*, since a bigger snapshot L0 takes proportionally longer to scan. An O(1) page-index lookup removes the scan — and the ceiling — regardless of DB size or write rate.

Contributor guide

Open the contributing guide

Research direction

Read db.go's lastPageMatch and the verifyWithExecutor path first, then inspect the ltx decoder's page-index handling, including DecodePage and Decoder.Close. Trace how the page index is written and determine how the target page can be located without a full sequential scan. Done means post-snapshot verification avoids decoding the entire L0 while preserving the existing page-match check.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sqlite
Domain
backend, databases, performance
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.