c-relay-pg/plans/backfill_redesign_plan.md

Backfill Redesign: Per-Author Until-Cursor Drain (Option B)

Problem

The current window-expansion backfill (caching/src/backfill.c) has four compounding structural defects that make cache coverage unacceptably poor (~10-28% of upstream availability even for a 7-pubkey follow set):

1. Overlapping windows re-fetch the same events. Window N+1's time range fully contains window N's range. The only dedup is a 4096-entry in-memory ring + inbox ON CONFLICT DO NOTHING, which overflows for high-volume authors, wasting query budget on duplicates.
2. Broken saturation detection. When a relay caps at 500 events, the code retries with limit=5000, still gets 500, compares 500 == 5000 (false), and incorrectly concludes the page was not saturated — marking the author complete without paginating.
3. until-cursor walk-back never triggers because it's gated on the broken saturation check.
4. Window 4 (full history) was skipped for 5/7 pubkeys and the loop won't retry once current_window_index advances past the last window.

Solution

Replace the window-expansion model with a per-author until-cursor drain: each followed author has a single persistent cursor (starting at now). Each backfill tick queries since=0&until=cursor&limit=500 for one author, publishes the page, and sets cursor = oldest_event_created_at - 1. Repeat until a page returns fewer than the relay's cap (beginning of history reached). The live subscriber stays as-is (it's already correct).

Architecture

flowchart TD
    A[cr_follow_resolve] --> B[caching_followed_pubkeys table]
    B --> C[Backfill tick: pick next incomplete author]
    C --> D[Query since=0 and until=cursor and limit=500]
    D --> E{ev_count == relay_cap?}
    E -- yes --> F[Publish page, set cursor = oldest - 1]
    F --> D
    E -- no < relay_cap --> G[Publish page, mark backfill_complete = true]
    G --> H{More incomplete authors?}
    H -- yes --> C
    H -- no --> I[Steady state: live sub only]
    J[Live subscriber] --> K[caching_event_inbox]
    K --> L[c-relay-pg inbox poller]
    L --> M[events table]

Changes

1. New table: caching_followed_pubkeys

Replaces both the ephemeral in-memory cr_pubkey_set_t (for persistence) and the window-coupled caching_backfill_progress (for cursor state).

Schema (add to src/pg_schema.sql):

CREATE TABLE IF NOT EXISTS caching_followed_pubkeys (
    pubkey           TEXT PRIMARY KEY,
    is_root          BOOLEAN NOT NULL DEFAULT FALSE,
    until_cursor     BIGINT NOT NULL DEFAULT 0,
    backfill_complete BOOLEAN NOT NULL DEFAULT FALSE,
    events_fetched   INTEGER NOT NULL DEFAULT 0,
    first_seen       BIGINT NOT NULL DEFAULT EXTRACT(EPOCH FROM NOW())::BIGINT,
    last_seen        BIGINT NOT NULL DEFAULT EXTRACT(EPOCH FROM NOW())::BIGINT,
    updated_at       BIGINT NOT NULL DEFAULT EXTRACT(EPOCH FROM NOW())::BIGINT
);

CREATE INDEX IF NOT EXISTS idx_caching_followed_incomplete
    ON caching_followed_pubkeys(backfill_complete, last_seen)
    WHERE backfill_complete = FALSE;

• until_cursor: the until timestamp for the next backfill query. 0 means "not started yet" (treat as now on first query). After each page, set to oldest_event_created_at - 1.
• backfill_complete: set true when a page returns fewer than the relay cap (we've reached the beginning of the author's history).
• is_root: true for root/admin npubs (used to apply admin_kinds).
• events_fetched: cumulative count for diagnostics.
• last_seen: updated each follow-graph refresh (prune stale follows).

Migration: On startup, if caching_followed_pubkeys is empty but caching_backfill_progress has rows, migrate: for each distinct author_pubkey in the old table, insert a row with until_cursor = 0, backfill_complete = FALSE (re-backfill from scratch — the old data was incomplete anyway). Drop caching_backfill_progress after migration.

2. Follow graph resolver: persist to caching_followed_pubkeys

File: caching/src/follow_graph.c + caching/src/pg_inbox.c

After cr_follow_resolve() builds the in-memory set, sync it to the table:

/* For each pubkey in the followed set: */
/*   INSERT INTO caching_followed_pubkeys (pubkey, is_root, last_seen)
 *   VALUES ($1, $2, now)
 *   ON CONFLICT (pubkey) DO UPDATE SET
 *     is_root = EXCLUDED.is_root,
 *     last_seen = EXCLUDED.last_seen;
 *
 * Mark follows not seen this refresh as stale (for pruning / diagnostics).
 * Do NOT touch until_cursor or backfill_complete on existing rows. */

New function: pg_inbox_sync_followed_pubkeys(cr_pubkey_set_t *followed, cr_config_t *cfg) — upserts all followed pubkeys, updates last_seen, sets is_root based on cr_follow_is_root().

New function: pg_inbox_prune_stale_follows(long threshold_seconds) — optionally deletes follows not seen in threshold_seconds (e.g. 24h). This is off by default; stale follows just stop getting backfilled.

The in-memory cr_pubkey_set_t followed stays as the runtime working set (used by the live subscriber). The table is the durable source of truth for backfill iteration.

3. Rewrite cr_backfill_tick — per-author until-cursor drain

File: caching/src/backfill.c

Replace the entire window-expansion logic. New cr_backfill_tick:

int cr_backfill_tick(cr_backfill_t *bf, cr_config_t *cfg,
                     nostr_relay_pool_t *upstream,
                     cr_sink_t *sink, const cr_relay_map_t *relay_map) {
    if (!cfg->backfill.enabled) return -2;

    /* Throttle: one query per tick_interval. */
    time_t now = time(NULL);
    if (bf->last_tick && (now - bf->last_tick) < cfg->backfill.tick_interval_seconds)
        return 0;
    bf->last_tick = now;

    /* Pick the next incomplete author from the DB (round-robin via
     * last_seen ordering, or a cursor we persist in bf). */
    char pk[CR_HEX_LEN];
    long until_cursor = 0;
    int is_root = 0;
    if (pg_inbox_pick_next_backfill_author(pk, &until_cursor, &is_root,
                                            &bf->author_round_cursor) != 0) {
        /* No incomplete authors — steady state. */
        bf->in_progress = 0;
        return -2;
    }

    /* First-time: cursor 0 means start from now. */
    if (until_cursor == 0) until_cursor = (long)now;

    int page_size = 500;  /* matches typical relay cap */
    int ev_count = 0;
    cJSON **events = query_author(upstream, relay_map, cfg, pk,
                                  0 /* since=0 full history */,
                                  until_cursor, page_size, &ev_count);

    if (!events || ev_count == 0) {
        /* No events at all (or no more) — author is complete. */
        pg_inbox_update_backfill_progress(pk, 0, 1 /* complete */, 0);
        free(events);
        return 1;
    }

    /* Find oldest timestamp BEFORE publishing. */
    long oldest_ts = 0;
    find_oldest_created_at(events, ev_count, &oldest_ts);

    /* Publish all events. */
    cr_sink_set_source_class(sink, CR_SINK_CLASS_BACKFILL);
    for (int k = 0; k < ev_count; k++) {
        cr_sink_publish(sink, events[k]);
        cJSON_Delete(events[k]);
    }
    free(events);
    bf->events_total += ev_count;

    /* Saturation check: if we got exactly page_size, the page may be
     * truncated. Set cursor = oldest - 1 and keep going next tick.
     * If we got fewer than page_size, we've reached the beginning. */
    if (ev_count >= page_size) {
        /* Saturated — more history likely exists. Advance cursor. */
        long next_cursor = (oldest_ts > 0) ? oldest_ts - 1 : 0;
        pg_inbox_update_backfill_progress(pk, next_cursor, 0 /* not complete */,
                                          ev_count);
    } else {
        /* Not saturated — beginning of history reached. */
        pg_inbox_update_backfill_progress(pk, until_cursor, 1 /* complete */,
                                          ev_count);
    }

    return 1;
}

Key differences from the old code:

• No windows. Single since=0 query per author, always full history.
• Saturation check compares against page_size (500), not max_cap (5000). This fixes Defect 2 — if the relay returns 500, we paginate.
• Cursor persisted per-author in caching_followed_pubkeys.until_cursor, not in a window-coupled table. This fixes Defect 4 — no window to skip.
• No overlapping queries. Each event is fetched exactly once as the cursor walks backwards. This fixes Defect 1.
• pg_inbox_pick_next_backfill_author selects the next backfill_complete = FALSE author, round-robin, so all authors get fair backfill time.

4. New PG inbox functions

File: caching/src/pg_inbox.c + caching/src/pg_inbox.h

/* Sync the followed set to the DB (upsert + update last_seen).
 * Does NOT touch until_cursor or backfill_complete on existing rows. */
int pg_inbox_sync_followed_pubkeys(const cr_pubkey_set_t *followed,
                                    const cr_config_t *cfg);

/* Pick the next incomplete author for backfill (round-robin).
 * Sets out_pk, out_until_cursor, out_is_root.
 * Returns 0 on success, -1 if no incomplete authors remain. */
int pg_inbox_pick_next_backfill_author(char *out_pk,
                                        long *out_until_cursor,
                                        int *out_is_root,
                                        int *round_cursor);

/* Update backfill progress for an author. */
int pg_inbox_update_backfill_progress(const char *pk,
                                       long until_cursor,
                                       int complete,
                                       int events_this_page);

/* Migrate old caching_backfill_progress rows to caching_followed_pubkeys.
 * Called once on startup if the new table is empty and the old one has rows. */
int pg_inbox_migrate_backfill_progress(void);

/* Reset all backfill progress (set until_cursor=0, backfill_complete=FALSE
 * for all followed pubkeys). Used by the "Reset Backfill" API button. */
int pg_inbox_reset_backfill_progress(void);

5. Simplify cr_backfill_t and cr_config_t state

File: caching/src/backfill.h, caching/src/config.h

Remove from cr_backfill_t:

• window_index, current_window_s, events_this_window, window_started
• author_complete, blocked, blocked_until_ts

Keep:

• cursor (now: round-robin index into followed set, for fair scheduling)
• until_cursor (transient, per-tick — not persisted here, read from DB)
• in_progress (1 if any incomplete authors remain)
• events_total (cumulative diagnostic)
• last_tick (throttle)

Remove from cr_config_t state:

• state.backfilled_until (no longer meaningful)
• state.current_window_index (no windows)

Remove from cr_config_t backfill config:

• backfill.window_schedule_seconds[], backfill.window_count
• backfill.window_cooldown_seconds
• backfill.events_per_tick → rename to backfill.page_size (default 500)

Keep:

• backfill.enabled
• backfill.page_size (was events_per_tick)
• backfill.tick_interval_seconds

6. Update caching_service_state table

File: src/pg_schema.sql

The current_window_index and backfill_cursor columns are no longer meaningful. Replace with:

ALTER TABLE caching_service_state
    DROP COLUMN IF EXISTS current_window_index,
    DROP COLUMN IF EXISTS backfill_cursor,
    ADD COLUMN IF NOT EXISTS backfill_authors_complete INTEGER NOT NULL DEFAULT 0,
    ADD COLUMN IF NOT EXISTS backfill_authors_total INTEGER NOT NULL DEFAULT 0;

Update pg_inbox_update_status() to report backfill_authors_complete / backfill_authors_total instead of current_window_index / backfill_cursor. The API status panel shows this as a progress bar (e.g. "Backfill: 3/7 authors complete").

7. Update main loop

File: caching/src/main.c

• Remove advance_window calls (no windows).
• After cr_follow_resolve(), call pg_inbox_sync_followed_pubkeys().
• On startup, call pg_inbox_migrate_backfill_progress() if needed.
• cr_backfill_init just sets in_progress = 1 (check if any incomplete authors exist in the DB).
• The follow-graph refresh at main.c:378 now also calls pg_inbox_sync_followed_pubkeys() so new follows get backfilled and unfollowed pubkeys stop getting backfilled.

8. Update API status display

File: api/index.js, src/config.c (caching_status handler)

• Show "Backfill: X/Y authors complete" instead of "Window N, cursor M".
• The "Reset Backfill Progress" button now calls pg_inbox_reset_backfill_progress() which sets until_cursor=0, backfill_complete=FALSE for all rows in caching_followed_pubkeys.

9. Config changes

File: src/pg_schema.sql (default config inserts), caching/src/pg_config.c

Remove config keys:

• caching_backfill_windows (no window schedule)
• caching_backfill_window_cooldown_seconds (no windows)

Add config key:

• caching_backfill_page_size already exists (value 500) — repurpose as the per-query limit (was already used this way, just rename in docs).

Keep:

• caching_backfill_enabled
• caching_backfill_tick_interval_ms (throttle between queries)
• caching_backfill_page_size (per-query limit, default 500)

Implementation Order

1. Schema: Add caching_followed_pubkeys table + alter caching_service_state in src/pg_schema.sql.
2. PG inbox functions: Add pg_inbox_sync_followed_pubkeys, pg_inbox_pick_next_backfill_author, pg_inbox_update_backfill_progress, pg_inbox_migrate_backfill_progress, pg_inbox_reset_backfill_progress in caching/src/pg_inbox.c + .h.
3. Follow graph sync: Call pg_inbox_sync_followed_pubkeys() after cr_follow_resolve() in caching/src/main.c.
4. Rewrite backfill: Replace cr_backfill_tick in caching/src/backfill.c. Simplify cr_backfill_t in backfill.h.
5. Config cleanup: Remove window config from caching/src/pg_config.c and caching/src/config.c. Update defaults in src/pg_schema.sql.
6. State reporting: Update pg_inbox_update_status() in caching/src/pg_inbox.c to report authors complete/total.
7. API status: Update api/index.js and src/config.c status handler to show backfill author progress.
8. Migration: Implement pg_inbox_migrate_backfill_progress() and call on startup.
9. Test: Rebuild, restart with --reset-backfill, verify 100% coverage for all 7 followed pubkeys via nak req comparison against upstream.

Risk and Mitigation

• Relays that don't honor until: If a relay ignores the until filter, the cursor won't advance and we'll re-fetch the same page. Mitigation: detect when oldest_ts doesn't decrease between consecutive pages for the same author and mark the author complete (or skip to a different relay).
• High-volume authors take many ticks: At 500 events/tick and 5s tick_interval, a 10,000-event author takes ~100s. This is acceptable — the live subscriber keeps you current, and the backfill makes steady progress. If faster backfill is needed later, Option C (parallel workers) can be added on top of this design.
• Follow graph churn: If follows change frequently, the sync upsert is O(N) per refresh (every 10 min). Fine for personal-scale (hundreds of follows). For thousands, batch the upsert.