Task: Implement triangulation/derivation
Table of Contents
This page documents a task in the Cross-rates matrix (CRM) story. It captures the goal, current status, acceptance, and any notes or results.
Goal
Implement the CRM's runtime rate engine on top of the crm_topology from
the previous task: a thread-safe (not multi-threaded), lock-free-on-the-
hot-path engine that ingests a continuous stream of driver_quote ticks
– possibly from a different thread than its readers – and serves
batched derived-rate reads by triangulation through the pivot, with
staleness propagated end to end from each contributing driver.
Status
| Field | Value |
|---|---|
| State | DONE |
| Parent story | Cross-rates matrix (CRM) |
| Now | Nothing. |
| Waiting on | Nothing. |
| Next | Nothing. |
| Last touched | 2026-07-12 |
Acceptance
domain::vertex_state,domain::rate_snapshot,domain::staleness_policy,domain::derived_rate,domain::rate_status– the runtime value types from the agreed design (see the parent task'sdesign/diagrams, reused here).service::rate_engineholds a fixedcrm_topology(never mutated) and animmer::atom<rate_snapshot>(per-vertex cumulative log-rate from the pivot, so any derived rate is one subtraction of two array entries).update(driver_quote): recomputes only the subtree hanging off the updated edge (not the whole matrix) into a new immutable snapshot via structural sharing, then atomically swaps it in. No internal threads; safe to call from any thread.rate(pair)/rates(pairs): exactly one atomic snapshot load per call (one for the whole batch in the plural form), then O(1)/O(N) pure arithmetic – no locking on the read path, so a batch of hundreds/ thousands of pairs is cheap.- Staleness: each
vertex_statecarries the timestamp of its oldest contributing input, propagated from its parent plus its own edge's timestamp on every update.rate()=/=rates()comparenow - oldest_contributing_timestampagainst a caller-suppliedstaleness_policyand returnrate_status(fresh/stale/unavailable) alongside the value. - A concurrent producer (
update) and concurrent readers (rate=/ =rates) never block each other and a reader never observes a torn mix of old/new values within one batch – verified with a test that interleaves updates and reads across threads. - Readable, correct triangulation: for a pair not directly on the tree,
the rate is computed via the pivot path (existing
crm_topology:: path_to_pivot), preferring the shorter of the two vertices' own paths (i.e. straightforward log-rate subtraction handles this without special casing, per the design).
Plan
(Implementation strategy. Written when work starts; key decisions
are distilled into the parent story's * Decisions at close, but the
plan itself stays — it is the historical record of what we did.)
Design already agreed (previous task's diagrams apply directly)
See class diagram and runtime sequence diagram from the topology
task – the rate_engine=/=rate_snapshot=/=vertex_state classes there
were designed together with topology_builder and crm_topology in the
same session; this task implements the parts that were deferred:
- Per-vertex cumulative "log-rate from pivot" representation: derived
rate for
(base, quote)isexp(log_rate[quote] - log_rate[base]), O(1) per pair. update()walks only the subtree below the changed edge (the tree structure bounds the blast radius of one tick).immer::atom<rate_snapshot>for the lock-free publish/read; a reader does oneload()for an entirerates(pairs)batch.- Staleness is a per-vertex timestamp, not a separate pass: it is carried
and propagated alongside
log_ratein the samevertex_state, updated by the same subtree walk.
Notes
Test Scenarios
Manual QA scenarios (scaffolded via compass add test_scenario, run
through the QA Validation Runner panel) that verify this task. Link
new ones here as they're created; the scenario doc itself links back
via its "Verifies task" field.
| Scenario | State | Notes |
|---|---|---|
PRs
| PR | Title |
|---|---|
| #1512 | [analytics.quant] Add CRM runtime rate engine (triangulation/derivation) |
Review
| # | Comment summary | File | Decision | Notes |
|---|---|---|---|---|
| 1 | Self-referencing pair on the pivot currency (base==quote==pivot) trivially matched parent(pivot)==pivot and silently corrupted every derived rate instead of throwing |
src/service/rate_engine.cpp | Accepted | Added an explicit base_id = quote_id= rejection before the parent-equality branches; new test asserts the throw and that the pivot's own rate stays exactly 1.0 afterwards (state not mutated by a rejected update). |
| 2 | No validation that driver_quote::rate is finite/positive; a bad tick silently propagates NaN/-inf through the whole subtree with status = fresh= |
src/service/rate_engine.cpp | Accepted | Added a std::isfinite() && > 0.0 check that throws std::invalid_argument, consistent with the existing unknown-currency/non-edge checks; new test covers zero, negative, NaN, and infinity. |
| 3 | Existing "not an edge" test used an unknown currency, so it only exercised the unknown-currency throw, not the known-but-unconnected-currencies branch | tests/rate_engine_tests.cpp | Accepted | Split into two tests: unknown currency, and a genuine known-but-unconnected pair (EUR/JPY, both hang off USD but aren't each other's parent). |
| 4 | crm_topology::edge_to_parent() added but never called anywhere – speculative API surface |
domain/crm_topology.hpp | Accepted | Removed; easy to add back with a real caller. |
| 5 | ccy_pair's doc comment claimed is_driver is used by rate_engine to pick accumulation direction, but the engine actually derives direction from tree structure, not the flag |
domain/ccy_pair.hpp | Accepted | Corrected the doc comment to say direction comes from the tree, not is_driver, and that either side of an edge may be ticked. |
Result
Shipped the runtime rate engine in ores.analytics.quant, on top of the
crm_topology from the previous task:
- New domain types:
driver_quote,rate_status,staleness_policy,derived_rate,vertex_state,rate_snapshot– matching the design agreed and diagrammed in the topology task, updated where the design needed sharpening (see below). service::rate_engine: holds the fixedcrm_topologyplus animmer::atom<rate_snapshot>; a per-vertex cumulative "log-rate from the pivot" representation makes any derived rate one subtraction (exp(log_rate[quote] - log_rate[base])).update()walks only the subtree below the changed edge (via achildren_adjacency built once at construction fromcrm_topology::parent()) and swaps in a new snapshot via structural sharing (immer::vector::transient()=/ =persistent());rate()=/=rates()each do exactly one atomicsnapshot_.load()then pure arithmetic.- Staleness: each
vertex_statecarries its own edge's tick timestamp (edge_observed_at) plus the cumulative oldest-contributing timestamp (as_of), recomputed alongsidelog_ratein the same subtree walk – so a stale major automatically taints every derived rate depending on it, with no separate propagation pass. crm_topologygained aparent()accessor (design refinement: needed by the engine to build its children adjacency and to determine, on each tick, which side of the edge is the "child" whose subtree to recompute). Anedge_to_parent()accessor was added alongside it but never used, and was removed in the review round below.- 11 new Catch2 test cases (18 total in the component, 45,000+ assertions
across repeated runs): direct rate passthrough, pivot triangulation,
unavailable-until-seeded, staleness propagation from the oldest
contributing driver, subtree-only recompute (an unrelated branch is
provably unaffected by an update elsewhere), batched
rates(), reject an unknown currency, reject two known-but-unconnected currencies, reject a self-referencing pivot pair, reject a non-finite/non-positive rate, and a concurrent-update-vs-concurrent-read stress test (single writer thread + 4 reader threads, thousands of batched reads) run repeatedly with no crashes/hangs/inconsistent reads. - Design docs updated to match: component overview, class diagram
(
vertex_stateedge fields,rate_enginemember/signature accuracy), no longer describingrate_engineas deferred.
Acceptance met in full. Story remains STARTED: risk recentering, wiring
into ores.marketdata's ingest path, and the management UI are still
open per the story's * Tasks plan.