gertjan/bodega
1
0
Fork 0
Code Issues 13 Pull requests Projects Releases Packages Wiki Activity Actions

correlation_refresh: O(N²) peak memory exceeds host RAM at current universe size (~24k symbols) #75

New issue
Closed
opened 2026-07-07 08:25:21 +00:00 by gertjan · 2 comments
gertjan commented 2026-07-07 08:25:21 +00:00
Owner
Copy link

Summary

correlation_refresh peak memory scales O(N²) with the post-filter universe size N, and N has grown past the point where the nightly snapshot fits in host RAM. The task now either OOM-crashes (pre-swap) or swap-thrashes to a multi-hour runtime (post-swap). The mitigations already shipped (#73, #74) keep the box alive but do not address the footprint — they are stopgaps. This issue tracks the durable fix: reduce correlation's peak memory so it fits comfortably in RAM at the current and projected universe size.

Impact / symptoms

  • Last successful snapshot: 2026-06-17 (universe_size = 23,529). Since late June the job has been failing most nights.
  • task_runs history for correlation_refresh:
    • Repeated interrupted (container killed mid-run) on Jun 23/24/27/28, Jul 3/4.
    • One success on Jun 25 (4288s / 71 min — the run just fit in RAM).
    • timeout on Jul 7 at 8865s (~2h28m) — the first swap-backed run: no longer crashes, but thrashes and exceeds the old 7200s limit.
  • Kernel OOM kills (dmesg) of the analytics python process on Jun 22, 24, 25, 28, Jul 4, 5, anon-rss ≈ 39 GB each. Note docker inspect … OOMKilled=false: the cgroup 48 GB limit was never reached — the host ran out of RAM and the kernel killed the biggest process. This means a bad night can take down an unrelated host process (e.g. bodega-timescaledb), not just analytics.
  • Downstream: correlation's synchronous compute blocking the event loop also caused momentum_refresh to misfire and skip (addressed in #74 via asyncio.to_thread).

Root cause

The universe is far larger than the docstring's illustrative "5 000-symbol" figure:

  • 27,214 active assets today; 23,529 passed min_history_days=252 in the last good snapshot (and climbing — active grew ~16% since mid-June).
  • At N = 23,529, a single N×N float32 matrix is 23529² × 4 B ≈ **2.2 GB**. At today's ~27k it is ~2.9 GB (+31%).

The pipeline holds ~10–15 simultaneous N×N matrices, peaking during the lead-lag pass:

  • src/analytics/correlation_discovery.py
    • _corr_two_windows (L55) / compute_corr_matrix (L101): cosum, sqsum_x, sqsum_y, counts, corr — ~5 × N×N.
    • find_lead_lag_pairs (L280): persistent best_improvement, best_lag, best_corr, best_overlap, abs_sync plus per-lag temporaries from compute_lagged_corr (L247) — corr_k, counts_k, improvement_k, valid — allocated for each of max_lag=5 iterations.
    • hierarchical_clusters (L173): full N×N dist matrix + scipy linkage, which is itself O(N²) memory (condensed distance ≈ N(N-1)/2 floats ≈ 1.1 GB at 23.5k) and O(N² log N) time.

5 × 2.2 GB (base corr) + ~8 × 2.2 GB (lead-lag f32/int variants, including transient compute_lagged_corr temporaries) ≈ 30–40 GB peak — matching the observed 39 GB. Because the cost is quadratic in N, the ~16% universe growth since mid-June inflated peak memory ~35% and pushed it over the host ceiling.

Current mitigations (stopgaps — do not fix the footprint)

  • #73 — staggered the analytics window so heavy jobs don't overlap; bumped scores/ranging timeouts. Removed the acute concurrent pile-up.
  • #74 — moved the correlation math onto a worker thread (asyncio.to_thread) so it no longer blocks the scheduler event loop; raised correlation_refresh timeout 7200 → 14400 s (4h); erp_refresh 1800 → 2400 s.
  • Ops: 48 GB swap added to the host (converts hard OOM into slow swap-thrash).

These keep the host stable and let the snapshot eventually complete, but correlation still runs swap-bound for hours and the footprint keeps growing with the universe.

Proposed fixes (in rough priority)

  1. Tile/block the neighbour search so the full N×N corr matrix never materialises. top_k_neighbors only needs, per symbol, its top-k by correlation. Compute correlations in row-blocks (e.g. 1–2k rows × N), extract top-k for those rows, discard the block. Peak drops from O(N²) → O(block × N). Results unchanged. Biggest win.
  2. Restrict the lead-lag pass to candidate pairs. Lead-lag is only meaningful for already-correlated pairs; computing it over all N² is wasteful. Limit find_lead_lag_pairs to each symbol's lag-0 top-k neighbours (≈ 25·N pairs vs N²). Massive memory + time reduction; negligible quality loss.
  3. Tile hierarchical_clusters / avoid the dense N×N dist matrix — cluster within the correlation candidate graph, or use a memory-bounded clustering that doesn't require the full condensed distance array at 23.5k+.
  4. Cap / tier the universe — apply a liquidity/volume/market-cap floor (or run a smaller "core" variant nightly + full universe weekly) to bound N. Simplest lever; at N = 12k, N×N f32 ≈ 0.6 GB → ~8 GB peak. Changes coverage, so a product decision.
  5. Memory hygiene — already float32 (good). Free intermediates promptly, reuse buffers (out= args), and consider del corr_k between lag iterations.

Recommended approach

Do (1) + (2) — tiling the neighbour search and restricting lead-lag to candidate pairs together take peak memory from O(N²) to roughly O(block × N) while preserving full-universe coverage and results. Revisit (3)/(4) only if clustering remains the ceiling afterwards. Once peak is safely under RAM, revert the 4h correlation_refresh timeout to something tight (~90 min) and consider moving momentum back to a slot adjacent to correlation.

Acceptance criteria

  • correlation_refresh peak RSS stays under a safe fraction of host RAM (target: < 20 GB) at N ≥ 30k, verified via docker stats / /proc sampling on a full run.
  • Nightly run completes in RAM (no swap) within a tight timeout (target: ≤ 90 min).
  • Snapshot output (peers/clusters/lead-lag) is equivalent to the pre-change result on a fixed universe (diff peers within tolerance).
  • correlation_refresh timeout reverted from 14400 s to the new headroom; momentum overlap risk retired.
  • Headroom validated against projected universe growth (N → ~35k).

References

  • Task orchestrator: src/scheduler/tasks/correlation_refresh.py:52
  • Compute kernels: src/analytics/correlation_discovery.py (_corr_two_windows L55, compute_corr_matrix L101, top_k_neighbors L124, hierarchical_clusters L173, compute_lagged_corr L247, find_lead_lag_pairs L280)
  • Prior mitigations: #73, #74
  • Evidence: last good snapshot universe_size=23,529 (2026-06-17); OOM kills in dmesg Jun 22–Jul 5 (~39 GB anon-rss); correlation_refresh timeout 8865 s on 2026-07-07.
## Summary `correlation_refresh` peak memory scales **O(N²)** with the post-filter universe size `N`, and `N` has grown past the point where the nightly snapshot fits in host RAM. The task now either OOM-crashes (pre-swap) or swap-thrashes to a multi-hour runtime (post-swap). The mitigations already shipped (#73, #74) keep the box alive but do **not** address the footprint — they are stopgaps. This issue tracks the durable fix: reduce correlation's peak memory so it fits comfortably in RAM at the current and projected universe size. ## Impact / symptoms - **Last successful snapshot: 2026-06-17** (`universe_size = 23,529`). Since late June the job has been failing most nights. - `task_runs` history for `correlation_refresh`: - Repeated `interrupted` (container killed mid-run) on Jun 23/24/27/28, Jul 3/4. - One `success` on Jun 25 (4288s / 71 min — the run just fit in RAM). - `timeout` on Jul 7 at **8865s (~2h28m)** — the first swap-backed run: no longer crashes, but thrashes and exceeds the old 7200s limit. - Kernel OOM kills (`dmesg`) of the analytics python process on **Jun 22, 24, 25, 28, Jul 4, 5**, `anon-rss ≈ 39 GB` each. Note `docker inspect … OOMKilled=false`: the cgroup 48 GB limit was never reached — the **host** ran out of RAM and the kernel killed the biggest process. This means a bad night can take down an *unrelated* host process (e.g. `bodega-timescaledb`), not just analytics. - Downstream: `correlation`'s synchronous compute blocking the event loop also caused `momentum_refresh` to misfire and skip (addressed in #74 via `asyncio.to_thread`). ## Root cause The universe is far larger than the docstring's illustrative "5 000-symbol" figure: - **27,214** active assets today; **23,529** passed `min_history_days=252` in the last good snapshot (and climbing — active grew ~16% since mid-June). - At `N = 23,529`, a single `N×N` float32 matrix is `23529² × 4 B ≈ **2.2 GB**`. At today's ~27k it is ~2.9 GB (+31%). The pipeline holds **~10–15 simultaneous `N×N` matrices**, peaking during the lead-lag pass: - `src/analytics/correlation_discovery.py` - `_corr_two_windows` (L55) / `compute_corr_matrix` (L101): `cosum`, `sqsum_x`, `sqsum_y`, `counts`, `corr` — ~5 × N×N. - `find_lead_lag_pairs` (L280): persistent `best_improvement`, `best_lag`, `best_corr`, `best_overlap`, `abs_sync` **plus** per-lag temporaries from `compute_lagged_corr` (L247) — `corr_k`, `counts_k`, `improvement_k`, `valid` — allocated for **each of `max_lag=5` iterations**. - `hierarchical_clusters` (L173): full `N×N` `dist` matrix + scipy `linkage`, which is itself O(N²) memory (condensed distance ≈ `N(N-1)/2` floats ≈ 1.1 GB at 23.5k) and O(N² log N) time. `5 × 2.2 GB` (base corr) `+ ~8 × 2.2 GB` (lead-lag f32/int variants, including transient `compute_lagged_corr` temporaries) `≈ 30–40 GB` peak — matching the observed 39 GB. Because the cost is **quadratic in N**, the ~16% universe growth since mid-June inflated peak memory ~35% and pushed it over the host ceiling. ## Current mitigations (stopgaps — do not fix the footprint) - **#73** — staggered the analytics window so heavy jobs don't overlap; bumped `scores`/`ranging` timeouts. Removed the acute concurrent pile-up. - **#74** — moved the correlation math onto a worker thread (`asyncio.to_thread`) so it no longer blocks the scheduler event loop; raised `correlation_refresh` timeout 7200 → **14400 s (4h)**; `erp_refresh` 1800 → 2400 s. - **Ops:** 48 GB swap added to the host (converts hard OOM into slow swap-thrash). These keep the host stable and let the snapshot eventually complete, but correlation still runs swap-bound for hours and the footprint keeps growing with the universe. ## Proposed fixes (in rough priority) 1. **Tile/block the neighbour search so the full `N×N` corr matrix never materialises.** `top_k_neighbors` only needs, per symbol, its top-k by correlation. Compute correlations in row-blocks (e.g. 1–2k rows × N), extract top-k for those rows, discard the block. Peak drops from **O(N²) → O(block × N)**. Results unchanged. *Biggest win.* 2. **Restrict the lead-lag pass to candidate pairs.** Lead-lag is only meaningful for already-correlated pairs; computing it over all `N²` is wasteful. Limit `find_lead_lag_pairs` to each symbol's lag-0 top-k neighbours (≈ `25·N` pairs vs `N²`). Massive memory + time reduction; negligible quality loss. 3. **Tile `hierarchical_clusters` / avoid the dense `N×N` dist matrix** — cluster within the correlation candidate graph, or use a memory-bounded clustering that doesn't require the full condensed distance array at 23.5k+. 4. **Cap / tier the universe** — apply a liquidity/volume/market-cap floor (or run a smaller "core" variant nightly + full universe weekly) to bound `N`. Simplest lever; at `N = 12k`, `N×N` f32 ≈ 0.6 GB → ~8 GB peak. Changes coverage, so a product decision. 5. **Memory hygiene** — already float32 (good). Free intermediates promptly, reuse buffers (`out=` args), and consider `del corr_k` between lag iterations. ## Recommended approach Do **(1) + (2)** — tiling the neighbour search and restricting lead-lag to candidate pairs together take peak memory from O(N²) to roughly O(block × N) while preserving full-universe coverage and results. Revisit (3)/(4) only if clustering remains the ceiling afterwards. Once peak is safely under RAM, revert the 4h `correlation_refresh` timeout to something tight (~90 min) and consider moving `momentum` back to a slot adjacent to correlation. ## Acceptance criteria - [ ] `correlation_refresh` peak RSS stays under a safe fraction of host RAM (target: < 20 GB) at `N ≥ 30k`, verified via `docker stats` / `/proc` sampling on a full run. - [ ] Nightly run completes in RAM (no swap) within a tight timeout (target: ≤ 90 min). - [ ] Snapshot output (peers/clusters/lead-lag) is equivalent to the pre-change result on a fixed universe (diff peers within tolerance). - [ ] `correlation_refresh` timeout reverted from 14400 s to the new headroom; `momentum` overlap risk retired. - [ ] Headroom validated against projected universe growth (N → ~35k). ## References - Task orchestrator: `src/scheduler/tasks/correlation_refresh.py:52` - Compute kernels: `src/analytics/correlation_discovery.py` (`_corr_two_windows` L55, `compute_corr_matrix` L101, `top_k_neighbors` L124, `hierarchical_clusters` L173, `compute_lagged_corr` L247, `find_lead_lag_pairs` L280) - Prior mitigations: #73, #74 - Evidence: last good snapshot `universe_size=23,529` (2026-06-17); OOM kills in `dmesg` Jun 22–Jul 5 (~39 GB anon-rss); `correlation_refresh` timeout 8865 s on 2026-07-07.
gertjan commented 2026-07-07 10:02:41 +00:00
Author
Owner
Copy link

The durable fix is merged and deployed in #76 (squash of two commits: tiled corr build + load hygiene, screened lead-lag scan + stopgap reverts).

Status against acceptance criteria:

  • Snapshot output equivalent on a fixed universe — verified old-vs-new on a synthetic 300-symbol universe: identical top-k buckets, identical cluster partition, identical ordered lead-lag lists (6497/6497 pairs; values within 8e-7). Note: the sync-correlation candidate screen proposed here as fix (2) was measured and rejected — it lost 13/20 injected genuine pure-lag pairs. The merged implementation screens by lagged improvement itself in a tiled sweep, which is provably output-identical to the full N² scan while staying O(block × N).
  • Timeout reverted: 14400 → 5400 s. Analytics mem_limit also lowered 48g → 24g so a regression OOM-kills the container, not a host-picked victim.
  • Peak RSS < 20 GB at real N, verified by sampling a full run — projected ~10–11 GB at N≈24k from an N=6000 benchmark (1.95 → 1.23 GB full-pipeline peak), with scipy's linkage (float64 condensed + internal copy) now the ceiling. Needs docker stats//proc confirmation on tonight's 01:00 UTC run.
  • Nightly completes in RAM ≤ 90 min — observe tonight's run duration in task_runs.
  • Headroom at N → 35k — projected ~17–19 GB (clustering-dominated); revisit fix (3) (kNN-graph clustering) only if real numbers disagree.
  • Momentum overlap risk: with correlation projected well under an hour, consider moving momentum_refresh from 03:00 back adjacent — after a few clean runs.

Leaving this open until tonight's run confirms the RSS/duration criteria; then it can close.

🤖 Posted by Claude Code — https://claude.ai/code/session_01JRnthdVhGGt5FeSQ8m3aUA

The durable fix is merged and deployed in #76 (squash of two commits: tiled corr build + load hygiene, screened lead-lag scan + stopgap reverts). **Status against acceptance criteria:** - [x] Snapshot output equivalent on a fixed universe — verified old-vs-new on a synthetic 300-symbol universe: identical top-k buckets, identical cluster partition, identical ordered lead-lag lists (6497/6497 pairs; values within 8e-7). Note: the sync-correlation candidate screen proposed here as fix (2) was measured and **rejected** — it lost 13/20 injected genuine pure-lag pairs. The merged implementation screens by lagged improvement itself in a tiled sweep, which is provably output-identical to the full N² scan while staying O(block × N). - [x] Timeout reverted: 14400 → 5400 s. Analytics `mem_limit` also lowered 48g → 24g so a regression OOM-kills the container, not a host-picked victim. - [ ] **Peak RSS < 20 GB at real N, verified by sampling a full run** — projected ~10–11 GB at N≈24k from an N=6000 benchmark (1.95 → 1.23 GB full-pipeline peak), with scipy's linkage (float64 condensed + internal copy) now the ceiling. Needs `docker stats`/`/proc` confirmation on tonight's 01:00 UTC run. - [ ] **Nightly completes in RAM ≤ 90 min** — observe tonight's run duration in `task_runs`. - [ ] Headroom at N → 35k — projected ~17–19 GB (clustering-dominated); revisit fix (3) (kNN-graph clustering) only if real numbers disagree. - [ ] Momentum overlap risk: with correlation projected well under an hour, consider moving `momentum_refresh` from 03:00 back adjacent — after a few clean runs. Leaving this open until tonight's run confirms the RSS/duration criteria; then it can close. 🤖 Posted by Claude Code — https://claude.ai/code/session_01JRnthdVhGGt5FeSQ8m3aUA
gertjan commented 2026-07-09 07:43:14 +00:00
Author
Owner
Copy link

Validated on production, 2026-07-09 01:00 UTC nightly run — closing.

Acceptance criteria:

  • Completes in RAM within a tight timeout: 18.8 min wall (was 71 min best-case / 148-min swap-bound timeout), inside the reverted 5400 s budget. No OOM, no swap; the analytics container now runs under a 24 GB cgroup cap that the run never hit — peak is bounded well under the old ~39 GB (a docker stats sample on a future run can pin the exact figure; projections say ~10–11 GB).
  • Snapshot output equivalent: proven exactly in #76 (identical top-k buckets, cluster partition, and ordered lead-lag lists vs the old implementation).
  • Timeout reverted 14400 → 5400 s; analytics mem_limit 48g → 24g; momentum/erp overlap retired (erp succeeded at 04:00 for the first time since the #73 stagger — 11.5 min).
  • Headroom: at N=23,504 the run uses ~21 % of its time budget; screen/tile temporaries scale O(block × N), and clustering (the current ceiling) stays under the cap through the projected N≈35k.

Also fixed en route (#78, discovered because this issue's fix made the nightly fast enough to reach persistence): correlation snapshot persistence had been failing silently since 2026-06-25 — destructive delete-then-insert save, event-loop starvation cancelling the Mongo handshake, task_runs recording success for failed runs, and a dependency-gate freshness window that deadlocked the 03:00/04:00 tasks. All landed in #78; peers/clusters/lead-lag are restored and stamped (55,239 docs, snapshot_ts 2026-07-09).

Remaining follow-ups tracked separately: momentum_refresh now surfaces a real failure (previously masked as green) and needs its own investigation; mongo healthcheck timeout bump still open as a suggestion.

🤖 Posted by Claude Code — https://claude.ai/code/session_01JRnthdVhGGt5FeSQ8m3aUA

Validated on production, 2026-07-09 01:00 UTC nightly run — closing. **Acceptance criteria:** - [x] Completes in RAM within a tight timeout: **18.8 min** wall (was 71 min best-case / 148-min swap-bound timeout), inside the reverted 5400 s budget. No OOM, no swap; the analytics container now runs under a 24 GB cgroup cap that the run never hit — peak is bounded well under the old ~39 GB (a `docker stats` sample on a future run can pin the exact figure; projections say ~10–11 GB). - [x] Snapshot output equivalent: proven exactly in #76 (identical top-k buckets, cluster partition, and ordered lead-lag lists vs the old implementation). - [x] Timeout reverted 14400 → 5400 s; analytics mem_limit 48g → 24g; momentum/erp overlap retired (erp succeeded at 04:00 for the first time since the #73 stagger — 11.5 min). - [x] Headroom: at N=23,504 the run uses ~21 % of its time budget; screen/tile temporaries scale O(block × N), and clustering (the current ceiling) stays under the cap through the projected N≈35k. **Also fixed en route** (#78, discovered because this issue's fix made the nightly fast enough to reach persistence): correlation snapshot persistence had been failing silently since 2026-06-25 — destructive delete-then-insert save, event-loop starvation cancelling the Mongo handshake, task_runs recording success for failed runs, and a dependency-gate freshness window that deadlocked the 03:00/04:00 tasks. All landed in #78; peers/clusters/lead-lag are restored and stamped (55,239 docs, snapshot_ts 2026-07-09). Remaining follow-ups tracked separately: momentum_refresh now surfaces a real failure (previously masked as green) and needs its own investigation; mongo healthcheck timeout bump still open as a suggestion. 🤖 Posted by Claude Code — https://claude.ai/code/session_01JRnthdVhGGt5FeSQ8m3aUA
Sign in to join this conversation.
No Branch/Tag specified
Branches Tags
main
0.17.2
Labels
Clear labels   
bug

   
documentation

   
duplicate

   
enhancement

   
wontfix
No labels
bug
documentation
duplicate
enhancement
wontfix
Milestone
Clear milestone
No items
No milestone
Projects
Clear projects
No items
No project
Assignees
Clear assignees
No assignees
1 participant
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference
gertjan/bodega#75
No description provided.