:hedgehog: PostHog is the leading platform for building self-driving products. Our developer tools – AI observability, analytics, session replay, flags, experiments, error tracking, logs, and more – capture all the context agents need to diagnose problems, uncover opportunities, and ship fixes. Steer it all from Slack, web, desktop, or the MCP.
Python ab-testingai-analyticsanalyticscdpdata-warehouseexperimentsfeature-flagsjavascriptproduct-analyticspythonreactsession-replaysurveystypescriptweb-analytics
//! Reading and evaluating one reconcile settlement page in bounded blocking sections.
//!
//! Reconcile scans a whole cohort, so every row of a page composes the same tree: one
//! [`CompositionReadPlan`] serves the page, and each row only binds it to a person. That lets a
//! section carry many rows through one handoff instead of one row per handoff, which is the whole
//! point of this module.
//!
//! What a section must not become is unbounded. A started blocking task cannot be cancelled and
//! shutdown joins it, so each section stops at [`MAX_ROWS`] rows, [`MAX_KEYS`] keys, or
//! [`MAX_BYTES`] of returned values, releases the maintenance permit, and resumes from the row it
//! stopped in. Rows and keys are hard stops. Bytes are not: the budget is consulted between reads,
//! so the peak a section can hold is [`MAX_BYTES`] plus whatever one more read of up to
//! [`MAX_KEYS`] values returns. Sizing memory from [`MAX_BYTES`] alone understates it.
//!
//! The page stays the settlement boundary: [`read_page`] returns one diff per row or an error, so no
//! caller can produce half a page. Only decoded inputs cross a section boundary, never a raw value.
use std::sync::Arc;
use metrics::{counter, histogram};
use crate::filters::reverse_index::TeamFilters;
use crate::filters::tree::CohortTree;
use crate::filters::CohortId;
use crate::observability::metrics::{
RECONCILE_KEYS_FETCHED_TOTAL, RECONCILE_READ_BYTES, RECONCILE_ROWS_ATTEMPTED_TOTAL,
};
use crate::stage2::evaluator::evaluate_tree;
use crate::store::{BehavioralKey, CohortStore, Stage2Key, StoreError, StoreHandle};
use crate::workers::composition_inputs::{
raw_bytes, CompositionReadPlan, PersonScope, ResolvedPersonInputs,
};
use crate::workers::stage2_path::RecomputeDiff;
/// Rows one section may settle before handing the page back. Caps how much of a page one
/// uncancellable blocking task owns, and with it the store permit it holds. Visible to
/// [`reconcile`](super::reconcile) so its retry test can size a page that spans sections.
pub(super) const MAX_ROWS: usize = 32;
/// Keys one section may fetch, counting every state source. A fresh section always has its whole
/// allowance, so every section issues at least one read and the page cannot stall.
const MAX_KEYS: usize = 1_024;
/// Returned value bytes after which a section stops issuing **further** reads. Not a ceiling: the
/// read that crosses it has already returned, and the next read is handed the whole remaining key
/// allowance, so a section's peak is this plus one read of up to [`MAX_KEYS`] values. Behavioral
/// values grow with their window, which is why no key count bounds bytes, and why a single value
/// larger than the whole budget still has to make progress rather than deadlock its row.
/// [`RECONCILE_READ_BYTES`] measures what a read actually cost.
const MAX_BYTES: usize = 4 * 1024 * 1024;
const SECTION_OP: &str = "reconcile_page";
/// Compose and diff every row of `page` against the bit the store holds, in sections that release
/// the maintenance permit between them.
///
/// Reconcile's reads belong on [`ReadLane::Maintenance`](crate::store::ReadLane), which is the
/// permit [`StoreHandle::run_section`] draws, so a cohort scan cannot contend with live event reads.
///
/// Diffs come back in scan order, one per row including the rows that did not change: the caller
/// emits a full snapshot, not only flips.
///
/// # Panics
/// `filters` must be the same frozen snapshot the drain guard passed, in which `cohort_id` has a
/// tree. Reconcile's guard proves that before it scans; a caller that passes another snapshot
/// panics in [`PageReader::evaluate`].
pub(super) async fn read_page(
handle: &StoreHandle,
filters: &Arc<TeamFilters>,
cohort_id: CohortId,
page: &[Stage2Key],
) -> Result<Vec<RecomputeDiff>, StoreError> {
// Dirty verification reaches here with every row of its page deleted. Those pages still have
// markers to clear, so the caller runs on; there is just nothing to take a store permit for.
if page.is_empty() {
return Ok(Vec::new());
}
let plan = Arc::new(CompositionReadPlan::for_cohorts([cohort_id], filters));
let mut reader = PageReader::new(Arc::clone(filters), plan, cohort_id, page.to_vec());
loop {
match handle
.run_section(SECTION_OP, move |store| reader.run_section(store))
.await??
{
PageRead::Complete(diffs) => return Ok(diffs),
PageRead::Reading(resumed) => reader = resumed,
}
}
}
/// One section's outcome. `Complete` is the only way to reach the diffs, so a page whose reads are
/// unfinished cannot be settled.
enum PageRead {
/// Keys are still outstanding. The reader carries every diff settled so far, and at most one
/// row's decoded inputs.
Reading(PageReader),
/// One diff per requested row, in scan order.
Complete(Vec<RecomputeDiff>),
}
struct PageReader {
filters: Arc<TeamFilters>,
plan: Arc<CompositionReadPlan>,
cohort_id: CohortId,
/// The rows to settle, in scan order.
page: Vec<Stage2Key>,
/// One diff per row already evaluated, so `page[diffs.len()]` is the row being read.
diffs: Vec<RecomputeDiff>,
/// Set only while that row's keys span a section boundary.
pending: Option<RowRead>,
}
impl PageReader {
fn new(
filters: Arc<TeamFilters>,
plan: Arc<CompositionReadPlan>,
cohort_id: CohortId,
page: Vec<Stage2Key>,
) -> Self {
// The prior bit is read under `cohort_id` while the key written back comes from the row, so
// a row from another cohort's prefix would read one key and write another.
debug_assert!(
page.iter().all(|row| row.cohort_id == cohort_id.0 as u64),
"a reconcile page is one cohort's prefix scan",
);
Self {
filters,
plan,
cohort_id,
diffs: Vec::with_capacity(page.len()),
page,
pending: None,
}
}
/// Read, decode and evaluate rows until a budget stops the section or the page is finished.
/// Raw values are dropped inside this call, so only the diffs and one row's decoded inputs
/// survive it.
fn run_section(mut self, store: &CohortStore) -> Result<PageRead, StoreError> {
let plan = Arc::clone(&self.plan);
let filters = Arc::clone(&self.filters);
// Hoisted out of the row loop, so the section states the catalog precondition once.
let tree = filters
.cohorts
.get(&self.cohort_id)
.expect("the drain guard proved this cohort has a tree in the frozen catalog");
let mut budget = SectionBudget::default();
while self.diffs.len() < self.page.len() {
if !budget.accepts_row() {
return Ok(PageRead::Reading(self));
}
let row = self.page[self.diffs.len()];
let mut read = self.pending.take().unwrap_or_else(|| {
// Counted on the blocking thread with the keys, so a section whose caller future
// was dropped still records the rows it read.
counter!(RECONCILE_ROWS_ATTEMPTED_TOTAL).increment(1);
RowRead::new(&plan)
});
let scope = PersonScope::new(row.partition_id, row.team_id, row.person_id);
while let Some(next) = read.next {
let Some(key_limit) = budget.key_allowance() else {
self.pending = Some(read);
return Ok(PageRead::Reading(self));
};
read.next = RowSection {
store,
plan: &plan,
scope,
inputs: &mut read.inputs,
budget: &mut budget,
}
.read(next, key_limit)?;
}
let diff = self.evaluate(tree, row, &read.inputs);
self.diffs.push(diff);
budget.row_settled();
}
Ok(PageRead::Complete(self.diffs))
}
/// Compose the row and diff it against the bit the store holds. Runs in the section that
/// finished the row's reads, so the decoded inputs are spent here rather than retained for the
/// page.
fn evaluate(
&self,
tree: &CohortTree,
row: Stage2Key,
inputs: &ResolvedPersonInputs,
) -> RecomputeDiff {
let references = self.plan.reference_membership(inputs);
let new_bit = evaluate_tree(&tree.root, inputs.membership(), &references);
RecomputeDiff::new(new_bit, inputs.prior_stage2(self.cohort_id), row)
}
}
/// What one section has spent.
#[derive(Debug, Default)]
struct SectionBudget {
rows: usize,
keys: usize,
bytes: usize,
}
impl SectionBudget {
fn accepts_row(&self) -> bool {
self.rows < MAX_ROWS
}
/// How many keys the next read may fetch, or `None` once the section is out of work.
fn key_allowance(&self) -> Option<usize> {
(self.keys < MAX_KEYS && self.bytes < MAX_BYTES).then(|| MAX_KEYS - self.keys)
}
fn spend(&mut self, keys: usize, bytes: usize) {
self.keys += keys;
self.bytes += bytes;
}
fn row_settled(&mut self) {
self.rows += 1;
}
}
/// One row's read in progress.
struct RowRead {
inputs: ResolvedPersonInputs,
/// `None` once every key the plan names is decoded.
next: Option<NextRead>,
}
impl RowRead {
fn new(plan: &CompositionReadPlan) -> Self {
Self {
inputs: ResolvedPersonInputs::with_capacity_for(plan),
next: Some(NextRead::RecordAndBehavioral),
}
}
}
/// The next keys one row needs, in source order.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum NextRead {
/// Nothing read yet: the person record rides along the first batch of behavioral keys, in the
/// one mixed-CF lookup the event fold already issues.
RecordAndBehavioral,
/// Behavioral keys from this offset on; the record is decoded.
Behavioral(usize),
/// Stage 2 rows from this offset on.
Stage2(usize),
}
impl NextRead {
/// Where a row stands with `offset` behavioral keys decoded: the rest of them, else the next
/// source. [`RowRead::new`] names the first source; these two name every step after it.
fn behavioral_at(offset: usize, plan: &CompositionReadPlan) -> Option<Self> {
if offset < plan.behavioral().len() {
Some(Self::Behavioral(offset))
} else {
Self::stage2_at(0, plan)
}
}
fn stage2_at(offset: usize, plan: &CompositionReadPlan) -> Option<Self> {
(offset < plan.stage2_cohorts().len()).then_some(Self::Stage2(offset))
}
}
/// One section's reads for one row: holds what the whole section shares, so each read takes only
/// what varies.
struct RowSection<'a> {
store: &'a CohortStore,
plan: &'a CompositionReadPlan,
scope: PersonScope,
inputs: &'a mut ResolvedPersonInputs,
budget: &'a mut SectionBudget,
}
// The sanctioned sync context: these reads already run on the blocking pool, inside the section
// `StoreHandle::run_section` offloaded.
#[allow(clippy::disallowed_methods)]
impl RowSection<'_> {
/// Fetch at most `key_limit` of the row's outstanding keys, decode them, and drop the raw
/// values. `None` once every key the plan names is decoded.
fn read(&mut self, next: NextRead, key_limit: usize) -> Result<Option<NextRead>, StoreError> {
match next {
NextRead::RecordAndBehavioral => self.record_and_behavioral(key_limit),
NextRead::Behavioral(from) => self.behavioral(from, key_limit),
NextRead::Stage2(from) => self.stage2(from, key_limit),
}
}
/// The person record rides along the first behavioral batch in one mixed-CF `multi_get`, so a
/// row costs one RocksDB lookup fewer. A row whose cohort reads no person condition asks for no
/// record.
fn record_and_behavioral(&mut self, key_limit: usize) -> Result<Option<NextRead>, StoreError> {
let record_key =
(!self.plan.person_leaves().is_empty()).then(|| self.scope.person_record_key());
let batch = batch_from(
self.plan.behavioral(),
0,
key_limit.saturating_sub(usize::from(record_key.is_some())),
);
let keys: Vec<BehavioralKey> = batch
.iter()
.map(|&(lsk, _)| self.scope.behavioral_key(lsk))
.collect();
let snapshot = self.store.read_event_snapshot(&keys, record_key.as_ref())?;
if let Some(record) = snapshot.record {
self.spend(
ReadSource::PersonRecord,
1,
record.as_ref().map_or(0, Vec::len),
);
self.inputs
.absorb_person_record(self.plan.person_leaves(), record);
}
if !batch.is_empty() {
self.spend(
ReadSource::Behavioral,
batch.len(),
raw_bytes(&snapshot.behavioral),
);
self.inputs.absorb_behavioral(batch, snapshot.behavioral);
}
Ok(NextRead::behavioral_at(batch.len(), self.plan))
}
fn behavioral(
&mut self,
from: usize,
key_limit: usize,
) -> Result<Option<NextRead>, StoreError> {
let batch = batch_from(self.plan.behavioral(), from, key_limit);
let keys: Vec<BehavioralKey> = batch
.iter()
.map(|&(lsk, _)| self.scope.behavioral_key(lsk))
.collect();
let raw = self.store.multi_get_behavioral(&keys)?;
self.spend(ReadSource::Behavioral, batch.len(), raw_bytes(&raw));
self.inputs.absorb_behavioral(batch, raw);
Ok(NextRead::behavioral_at(from + batch.len(), self.plan))
}
/// The row's own prior bit and every composed referent's bit come from one key set, so a
/// referent is read as stored rather than substituted with a bit this page is about to write.
fn stage2(&mut self, from: usize, key_limit: usize) -> Result<Option<NextRead>, StoreError> {
let batch = batch_from(self.plan.stage2_cohorts(), from, key_limit);
let keys: Vec<Stage2Key> = batch
.iter()
.map(|&cohort_id| self.scope.stage2_key(cohort_id))
.collect();
let raw = self.store.multi_get_stage2(&keys)?;
self.spend(ReadSource::Stage2, batch.len(), raw_bytes(&raw));
self.inputs.absorb_stage2(batch, raw);
Ok(NextRead::stage2_at(from + batch.len(), self.plan))
}
fn spend(&mut self, source: ReadSource, keys: usize, bytes: usize) {
source.record(keys, bytes);
self.budget.spend(keys, bytes);
}
}
/// At most `limit` entries of `source` from `from`.
fn batch_from<T>(source: &[T], from: usize, limit: usize) -> &[T] {
&source[from..source.len().min(from + limit)]
}
/// The closed set of `source` label values on the page counters.
#[derive(Debug, Clone, Copy)]
enum ReadSource {
Behavioral,
PersonRecord,
Stage2,
}
impl ReadSource {
fn label(self) -> &'static str {
match self {
Self::Behavioral => "behavioral",
Self::PersonRecord => "person_record",
Self::Stage2 => "stage2",
}
}
fn record(self, keys: usize, bytes: usize) {
counter!(RECONCILE_KEYS_FETCHED_TOTAL, "source" => self.label()).increment(keys as u64);
histogram!(RECONCILE_READ_BYTES, "source" => self.label()).record(bytes as f64);
}
}
#[cfg(test)]
// Tests seed the store directly through `CohortStore`, the sanctioned direct-store surface for tests.
#[allow(clippy::disallowed_methods)]
mod tests {
use super::*;
use chrono_tz::UTC;
use serde_json::{json, Value};
use tempfile::TempDir;
use uuid::Uuid;
use crate::filters::{TeamFiltersBuilder, TeamId};
use crate::stage1::key::LeafStateKey;
use crate::stage1::person_record::{MatchedSet, PersonRecord};
use crate::stage1::state::{AppliedOffsets, Stage1State, StatefulRecord};
use crate::stage2::state::Stage2State;
use crate::store::{
Behavioral, OffloadConfig, OffloadMode, PersonRecordKey, PersonRecords, ReadLane,
StoreConfig,
};
use crate::workers::stage2_path::recompute_and_diff;
const TEAM: u64 = 7;
const PARTITION: u16 = 0;
const COHORT: CohortId = CohortId(1);
/// Composable, so cohort 1 reads it as a stored row.
const COMPOSED_REF: CohortId = CohortId(2);
/// One leaf, so cohort 1 reads it through that leaf's comparator.
const SINGLE_LEAF_REF: CohortId = CohortId(3);
const PERSON_HASH: [u8; 16] = *b"fedcba9876543210";
const EVENT_MS: i64 = 1_700_000_000_000;
fn temp_store() -> (TempDir, CohortStore) {
let dir = TempDir::new().unwrap();
let store = CohortStore::open(&StoreConfig {
path: dir.path().join("db"),
..StoreConfig::default()
})
.unwrap();
(dir, store)
}
/// Wraps the store so `read_page` exercises the same blocking-pool transport as production.
fn handle(store: &CohortStore) -> StoreHandle {
StoreHandle::new(
store.clone(),
OffloadConfig {
mode: OffloadMode::All,
event_read_permits: 16,
maintenance_permits: 6,
},
)
}
fn behavioral_leaf(condition_hash: &str) -> Value {
json!({
"type": "behavioral", "value": "performed_event", "key": "$pageview",
"time_value": 7, "time_interval": "day",
"conditionHash": condition_hash,
"bytecode": ["_H", 1, 32, "$pageview", 32, "event", 1, 1, 11],
})
}
fn person_leaf() -> Value {
json!({
"type": "person", "key": "email", "value": "[email protected]", "operator": "exact",
"conditionHash": "fedcba9876543210",
"bytecode": ["_H", 1, 32, "[email protected]", 32, "email", 32, "properties", 32, "person", 1, 3, 11],
})
}
fn cohort_ref(target: CohortId, negation: bool) -> Value {
json!({ "type": "cohort", "value": target.0, "negation": negation })
}
fn hash(text: &str) -> [u8; 16] {
text.as_bytes().try_into().expect("a 16-byte hash")
}
fn freeze(cohorts: Vec<(CohortId, Vec<Value>)>) -> Arc<TeamFilters> {
let mut builder = TeamFiltersBuilder::default();
for (id, values) in cohorts {
let cohort = json!({ "properties": { "type": "AND", "values": values } });
builder
.add_cohort(id, TeamId(TEAM as i32), &cohort)
.unwrap();
}
Arc::new(builder.freeze_with(UTC, true))
}
/// Cohort 1 over every reference kind and both leaf stores, so one page exercises each state
/// source a reconcile read has.
fn mixed_cohort() -> Arc<TeamFilters> {
freeze(vec![
(
COHORT,
vec![
behavioral_leaf("own0000000000001"),
person_leaf(),
cohort_ref(COMPOSED_REF, false),
cohort_ref(SINGLE_LEAF_REF, false),
// Absent from the catalog, so it reads as a non-member and the negation lets
// the AND through.
cohort_ref(CohortId(404), true),
],
),
(
COMPOSED_REF,
vec![behavioral_leaf("ref0000000000002"), person_leaf()],
),
(SINGLE_LEAF_REF, vec![behavioral_leaf("ref0000000000003")]),
])
}
fn person(n: u128) -> Uuid {
Uuid::from_u128(n)
}
fn stage2_key(cohort: CohortId, who: Uuid) -> Stage2Key {
Stage2Key {
partition_id: PARTITION,
team_id: TEAM,
cohort_id: cohort.0 as u64,
person_id: who,
}
}
fn behavioral_match() -> Stage1State {
Stage1State::BehavioralSingle {
has_match: true,
last_event_at_ms: EVENT_MS,
earliest_eviction_at_ms: i64::MAX,
}
}
fn behavioral_miss() -> Stage1State {
Stage1State::BehavioralSingle {
has_match: false,
last_event_at_ms: EVENT_MS,
earliest_eviction_at_ms: i64::MAX,
}
}
fn write_behavioral(store: &CohortStore, lsk: LeafStateKey, who: Uuid, state: Stage1State) {
let record = StatefulRecord::new(state, AppliedOffsets::default());
write_behavioral_bytes(store, lsk, who, &record.encode());
}
fn write_behavioral_bytes(store: &CohortStore, lsk: LeafStateKey, who: Uuid, bytes: &[u8]) {
let key = BehavioralKey::new(PARTITION, TEAM, who, lsk);
store
.write_batch(|b| b.put::<Behavioral>(&key, bytes))
.unwrap();
}
fn write_person_record(store: &CohortStore, who: Uuid, matched: &[[u8; 16]]) {
let key = PersonRecordKey::new(PARTITION, TEAM, who);
let mut record = PersonRecord::absent();
record.matched = MatchedSet::from_iter(matched.iter().copied());
store
.write_batch(|b| b.put::<PersonRecords>(&key, &record.encode()))
.unwrap();
}
fn write_corrupt_person_record(store: &CohortStore, who: Uuid) {
let key = PersonRecordKey::new(PARTITION, TEAM, who);
store
.write_batch(|b| b.put::<PersonRecords>(&key, b"not a person record"))
.unwrap();
}
fn write_stage2(store: &CohortStore, cohort: CohortId, who: Uuid, in_cohort: bool) {
let state = Stage2State {
in_cohort,
last_evaluated_at_ms: EVENT_MS,
};
write_stage2_bytes(store, cohort, who, &state.encode());
}
/// A bit a merge transfer carried over, which a receiver-side evaluation must claim even when
/// the logical membership is unchanged.
fn write_transferred_fallback(store: &CohortStore, cohort: CohortId, who: Uuid, bit: bool) {
let state = Stage2State {
in_cohort: bit,
last_evaluated_at_ms: EVENT_MS,
};
write_stage2_bytes(store, cohort, who, &state.encode_transferred_fallback());
}
fn write_stage2_bytes(store: &CohortStore, cohort: CohortId, who: Uuid, bytes: &[u8]) {
let key = stage2_key(cohort, who);
store.write_batch(|b| b.put_stage2(&key, bytes)).unwrap();
}
/// Everything the settlement path reads off one diff.
fn settled(diff: &RecomputeDiff) -> (Stage2Key, bool, bool, bool, bool) {
(
diff.stage2_key,
diff.new_bit,
diff.prior_bit,
diff.flipped(),
diff.requires_write(),
)
}
/// Drive the reader the way [`read_page`] does, but synchronously, so a test can see exactly
/// where the section boundaries fell: one entry per section, holding the rows it settled and
/// where the next section resumes. `None` means it stopped between rows, not inside one.
fn read_in_sections(
store: &CohortStore,
filters: &Arc<TeamFilters>,
page: &[Stage2Key],
) -> (Vec<RecomputeDiff>, Vec<(usize, Option<NextRead>)>) {
let plan = Arc::new(CompositionReadPlan::for_cohorts([COHORT], filters));
let mut reader = PageReader::new(Arc::clone(filters), plan, COHORT, page.to_vec());
let mut sections = Vec::new();
let mut settled = 0;
loop {
match reader.run_section(store).unwrap() {
PageRead::Complete(diffs) => {
sections.push((diffs.len() - settled, None));
return (diffs, sections);
}
PageRead::Reading(resumed) => {
let resume = resumed.pending.as_ref().and_then(|read| read.next);
sections.push((resumed.diffs.len() - settled, resume));
settled = resumed.diffs.len();
reader = resumed;
}
}
}
}
async fn per_row(
store: &CohortStore,
filters: &Arc<TeamFilters>,
page: &[Stage2Key],
) -> Vec<RecomputeDiff> {
let handle = handle(store);
let tree = filters.cohorts.get(&COHORT).expect("the cohort is frozen");
let mut diffs = Vec::with_capacity(page.len());
for key in page {
diffs.push(
recompute_and_diff(
PARTITION,
key.person_id,
tree,
filters,
&handle,
ReadLane::Maintenance,
)
.await
.unwrap(),
);
}
diffs
}
/// One person per state shape a reconcile scan meets. Returns the page in scan order.
fn seed_every_state_shape(store: &CohortStore, filters: &TeamFilters) -> Vec<Stage2Key> {
let own = filters.by_condition_to_lsk[&hash("own0000000000001")][0];
let referent = filters.by_condition_to_lsk[&hash("ref0000000000003")][0];
// Everything matches over a non-member row: enters.
let entering = person(1);
write_behavioral(store, own, entering, behavioral_match());
write_person_record(store, entering, &[PERSON_HASH]);
write_behavioral(store, referent, entering, behavioral_match());
write_stage2(store, COMPOSED_REF, entering, true);
write_stage2(store, COHORT, entering, false);
// No state at all, and no row of its own: stays a non-member and writes nothing.
let absent = person(2);
write_stage2(store, COHORT, absent, false);
// Everything matches over a member row: unchanged.
let unchanged = person(3);
write_behavioral(store, own, unchanged, behavioral_match());
write_person_record(store, unchanged, &[PERSON_HASH]);
write_behavioral(store, referent, unchanged, behavioral_match());
write_stage2(store, COMPOSED_REF, unchanged, true);
write_stage2(store, COHORT, unchanged, true);
// A corrupt behavioral value reads as a non-member, so a stale member bit is fixed.
let corrupt_leaf = person(4);
write_behavioral_bytes(store, own, corrupt_leaf, b"not a stage 1 record");
write_person_record(store, corrupt_leaf, &[PERSON_HASH]);
write_behavioral(store, referent, corrupt_leaf, behavioral_match());
write_stage2(store, COMPOSED_REF, corrupt_leaf, true);
write_stage2(store, COHORT, corrupt_leaf, true);
// A corrupt person record reads every person leaf as a non-member, over a transferred
// fallback the evaluation must claim even though the bit does not move.
let corrupt_record = person(5);
write_behavioral(store, own, corrupt_record, behavioral_match());
write_corrupt_person_record(store, corrupt_record);
write_behavioral(store, referent, corrupt_record, behavioral_match());
write_stage2(store, COMPOSED_REF, corrupt_record, true);
write_transferred_fallback(store, COHORT, corrupt_record, false);
// A corrupt own row reads as a non-member prior, so a real member enters again.
let corrupt_prior = person(6);
write_behavioral(store, own, corrupt_prior, behavioral_match());
write_person_record(store, corrupt_prior, &[PERSON_HASH]);
write_behavioral(store, referent, corrupt_prior, behavioral_match());
write_stage2(store, COMPOSED_REF, corrupt_prior, true);
write_stage2_bytes(store, COHORT, corrupt_prior, b"not a stage 2 row");
// The composed referent is a non-member, so the AND fails on the reference alone.
let referent_missing = person(7);
write_behavioral(store, own, referent_missing, behavioral_match());
write_person_record(store, referent_missing, &[PERSON_HASH]);
write_behavioral(store, referent, referent_missing, behavioral_match());
write_stage2(store, COHORT, referent_missing, true);
// The single-leaf referent misses, which only its own comparator can tell.
let leaf_referent_miss = person(8);
write_behavioral(store, own, leaf_referent_miss, behavioral_match());
write_person_record(store, leaf_referent_miss, &[PERSON_HASH]);
write_behavioral(store, referent, leaf_referent_miss, behavioral_miss());
write_stage2(store, COMPOSED_REF, leaf_referent_miss, true);
write_stage2(store, COHORT, leaf_referent_miss, true);
(1..=8).map(|n| stage2_key(COHORT, person(n))).collect()
}
/// The page reader is the only reconcile read path, so what keeps it honest is agreement with
/// `recompute_and_diff` — the per-row path it replaced, still live on the cascade.
#[tokio::test]
async fn a_page_agrees_with_the_per_row_path_on_every_state_shape() {
let (_dir, store) = temp_store();
let filters = mixed_cohort();
let page = seed_every_state_shape(&store, &filters);
let by_page = read_page(&handle(&store), &filters, COHORT, &page)
.await
.unwrap();
let by_row = per_row(&store, &filters, &page).await;
assert_eq!(
by_page.iter().map(settled).collect::<Vec<_>>(),
by_row.iter().map(settled).collect::<Vec<_>>(),
);
assert_eq!(
by_page.iter().map(|diff| diff.new_bit).collect::<Vec<_>>(),
[true, false, true, false, false, true, false, false],
"the fixture has to exercise both bits, or agreement proves nothing",
);
assert_eq!(
by_page
.iter()
.map(|diff| diff.requires_write())
.collect::<Vec<_>>(),
[true, false, false, true, true, true, true, true],
"an unchanged transferred fallback still settles its ownership",
);
}
/// Page widths derived from the row budget, so the test sits on the boundary wherever it moves:
/// exactly the budget is one section, one more splits it.
const ROW_BOUNDARY_PAGES: [usize; 2] = [MAX_ROWS, MAX_ROWS + 1];
#[tokio::test]
async fn a_page_wider_than_the_row_budget_settles_every_row_across_sections() {
for (rows, expected) in ROW_BOUNDARY_PAGES
.into_iter()
.zip([vec![(MAX_ROWS, None)], vec![(MAX_ROWS, None), (1, None)]])
{
let (_dir, store) = temp_store();
let filters = freeze(vec![(COHORT, vec![behavioral_leaf("own0000000000001")])]);
let own = filters.by_condition_to_lsk[&hash("own0000000000001")][0];
let page: Vec<Stage2Key> = (0..rows)
.map(|index| {
let who = person(index as u128 + 1);
write_behavioral(&store, own, who, behavioral_match());
write_stage2(&store, COHORT, who, false);
stage2_key(COHORT, who)
})
.collect();
let (diffs, sections) = read_in_sections(&store, &filters, &page);
assert_eq!(
sections, expected,
"{rows} rows: the row budget stops a section between rows, never inside one",
);
assert_eq!(
diffs.iter().map(settled).collect::<Vec<_>>(),
per_row(&store, &filters, &page)
.await
.iter()
.map(settled)
.collect::<Vec<_>>(),
"{rows} rows",
);
}
}
/// Leaf counts derived from the key budget. A row reads its person record, its behavioral
/// leaves and its one Stage 2 row, so `MAX_KEYS - 2` leaves is exactly one section's allowance
/// and one more splits the row.
const KEY_BOUNDARY_WIDTHS: [usize; 2] = [MAX_KEYS - 2, MAX_KEYS - 1];
fn wide_leaf(index: usize) -> Value {
behavioral_leaf(&format!("beh{index:013}"))
}
/// A leaf the read skipped would leave the AND short, so the entry proves every key landed.
#[tokio::test]
async fn a_row_wider_than_the_key_budget_reads_every_key_across_sections() {
let expectations = [
vec![(1, None)],
// One key short: the row's own Stage 2 read is what spills into a second section.
vec![(0, Some(NextRead::Stage2(0))), (1, None)],
];
for (leaves, expected) in KEY_BOUNDARY_WIDTHS.into_iter().zip(expectations) {
let (_dir, store) = temp_store();
let mut values: Vec<Value> = (0..leaves).map(wide_leaf).collect();
values.push(person_leaf());
let filters = freeze(vec![(COHORT, values)]);
let lsks: Vec<LeafStateKey> = (0..leaves)
.map(|index| filters.by_condition_to_lsk[&hash(&format!("beh{index:013}"))][0])
.collect();
let alice = person(1);
for &lsk in &lsks {
write_behavioral(&store, lsk, alice, behavioral_match());
}
write_person_record(&store, alice, &[PERSON_HASH]);
let page = vec![stage2_key(COHORT, alice)];
let (entered, sections) = read_in_sections(&store, &filters, &page);
assert_eq!(sections, expected, "{leaves} leaves");
assert!(entered[0].new_bit, "{leaves} leaves");
// The entry above proves every batch landed. This half pins that the last leaf's value
// is read, not just its key.
write_behavioral(&store, lsks[leaves - 1], alice, behavioral_miss());
let (left, _) = read_in_sections(&store, &filters, &page);
assert!(!left[0].new_bit, "{leaves} leaves");
}
}
/// A value bigger than the whole byte budget: the read that crosses it is already issued, so
/// the section has to stop after it rather than refuse to make progress.
#[tokio::test]
async fn a_value_larger_than_the_byte_budget_stops_the_section_after_it() {
let (_dir, store) = temp_store();
let filters = freeze(vec![(COHORT, vec![behavioral_leaf("own0000000000001")])]);
let own = filters.by_condition_to_lsk[&hash("own0000000000001")][0];
let oversized = vec![b'x'; MAX_BYTES + 1];
let page: Vec<Stage2Key> = (1..=2)
.map(|index| {
let who = person(index);
write_behavioral_bytes(&store, own, who, &oversized);
write_stage2(&store, COHORT, who, true);
stage2_key(COHORT, who)
})
.collect();
let (diffs, sections) = read_in_sections(&store, &filters, &page);
// Per row: the oversized behavioral read crosses the budget and ends the section with the
// row unsettled, then the next section reads its Stage 2 row.
assert_eq!(
sections,
[
(0, Some(NextRead::Stage2(0))),
(1, Some(NextRead::Stage2(0))),
(1, None),
],
);
assert_eq!(
diffs.iter().map(settled).collect::<Vec<_>>(),
per_row(&store, &filters, &page)
.await
.iter()
.map(settled)
.collect::<Vec<_>>(),
"an undecodable oversized value still reads as a non-member",
);
}
/// A cohort whose tree names only references reads no behavioral key and no person record, so
/// its first source is empty. Skipping an empty source has to advance the read; a reader that
/// re-entered it would spin on a section that spends nothing.
#[tokio::test]
async fn a_cohort_with_no_leaves_reads_only_its_stage_2_rows() {
let (_dir, store) = temp_store();
let filters = freeze(vec![
(
COHORT,
vec![
cohort_ref(COMPOSED_REF, false),
cohort_ref(CohortId(404), true),
],
),
(
COMPOSED_REF,
vec![behavioral_leaf("ref0000000000002"), person_leaf()],
),
]);
let alice = person(1);
write_stage2(&store, COMPOSED_REF, alice, true);
write_stage2(&store, COHORT, alice, false);
let page = vec![stage2_key(COHORT, alice)];
let (diffs, sections) = read_in_sections(&store, &filters, &page);
assert_eq!(sections, [(1, None)]);
assert!(
diffs[0].new_bit,
"the referent's stored bit is the only input this cohort has",
);
assert_eq!(
diffs.iter().map(settled).collect::<Vec<_>>(),
per_row(&store, &filters, &page)
.await
.iter()
.map(settled)
.collect::<Vec<_>>(),
);
}
/// The row that starts with one key left in the section reads its person record alone. Charging
/// the record to the row's own allowance is what keeps that read non-empty — a section that
/// handed out a zero allowance would spin instead of yielding.
#[tokio::test]
async fn a_row_that_starts_with_one_key_left_reads_its_record_alone() {
// A row costs its record, its behavioral leaves and its one Stage 2 row. Size the cohort so
// that every row but the last spends the key allowance down to exactly one.
let full_rows = MAX_ROWS - 1;
let keys_per_row = (MAX_KEYS - 1) / full_rows;
assert_eq!(
full_rows * keys_per_row,
MAX_KEYS - 1,
"the budgets no longer divide into the corner this test exists for",
);
let leaves = keys_per_row - 2;
let (_dir, store) = temp_store();
let mut values: Vec<Value> = (0..leaves).map(wide_leaf).collect();
values.push(person_leaf());
let filters = freeze(vec![(COHORT, values)]);
let lsks: Vec<LeafStateKey> = (0..leaves)
.map(|index| filters.by_condition_to_lsk[&hash(&format!("beh{index:013}"))][0])
.collect();
let page: Vec<Stage2Key> = (0..MAX_ROWS)
.map(|index| {
let who = person(index as u128 + 1);
for &lsk in &lsks {
write_behavioral(&store, lsk, who, behavioral_match());
}
write_person_record(&store, who, &[PERSON_HASH]);
write_stage2(&store, COHORT, who, false);
stage2_key(COHORT, who)
})
.collect();
let (diffs, sections) = read_in_sections(&store, &filters, &page);
assert_eq!(
sections,
[(full_rows, Some(NextRead::Behavioral(0))), (1, None)],
"the one key left buys the record alone, so the behavioral read resumes at 0",
);
assert!(
diffs.iter().all(|diff| diff.new_bit),
"a row split across sections still reads every leaf",
);
}
/// Bytes accumulate across rows, not only within one read. A page of many moderate values is
/// what the byte budget exists for; the oversized-value case above crosses it inside one read.
#[tokio::test]
async fn bytes_accumulate_across_rows_until_the_budget_stops_the_section() {
// Sized so a whole number of rows fits under the budget, with rows to spare after it.
let value_bytes = MAX_BYTES / 8 + 1;
let rows_within_budget = MAX_BYTES / value_bytes;
let rows = rows_within_budget + 3;
let (_dir, store) = temp_store();
let filters = freeze(vec![(COHORT, vec![behavioral_leaf("own0000000000001")])]);
let own = filters.by_condition_to_lsk[&hash("own0000000000001")][0];
let value = vec![b'x'; value_bytes];
let page: Vec<Stage2Key> = (0..rows)
.map(|index| {
let who = person(index as u128 + 1);
write_behavioral_bytes(&store, own, who, &value);
write_stage2(&store, COHORT, who, true);
stage2_key(COHORT, who)
})
.collect();
let (diffs, sections) = read_in_sections(&store, &filters, &page);
// The budget is consulted between reads, so the row that crosses it has already issued one
// read and finishes in the next section — it is not held back whole.
assert_eq!(
sections,
[
(rows_within_budget, Some(NextRead::Stage2(0))),
(rows - rows_within_budget, None),
],
"the crossing row settles in the next section, not the one that read it",
);
assert_eq!(
diffs.iter().map(settled).collect::<Vec<_>>(),
per_row(&store, &filters, &page)
.await
.iter()
.map(settled)
.collect::<Vec<_>>(),
);
}
/// Benchmark, not a test. Run it in release:
///
/// ```text
/// cargo test -p cohort-stream-processor --release --lib \
/// reconcile_page_benchmark -- --ignored --nocapture
/// ```
///
/// It asserts agreement only, because a wall-time threshold would flake on a slower box. It
/// times the read and evaluation alone: acknowledgments are the settlement half, measured in
/// production off `cohort_reconcile_page_duration_seconds`. Handoffs per row come from
/// `store_offload_exec_duration_seconds{op="reconcile_page"}_count` over
/// `cohort_reconcile_rows_attempted_total`.
#[tokio::test]
#[ignore = "benchmark; run in release with --ignored --nocapture"]
async fn reconcile_page_benchmark() {
use std::time::Instant;
println!(
"{:>5} {:>12} {:>12} {:>7}",
"page", "per-row", "by-page", "ratio"
);
for rows in [256, 512] {
let (_dir, store) = temp_store();
let filters = mixed_cohort();
let own = filters.by_condition_to_lsk[&hash("own0000000000001")][0];
let referent = filters.by_condition_to_lsk[&hash("ref0000000000003")][0];
let page: Vec<Stage2Key> = (0..rows)
.map(|index| {
let who = person(index as u128 + 1);
write_behavioral(&store, own, who, year_long_history());
write_behavioral(&store, referent, who, year_long_history());
write_person_record(&store, who, &[PERSON_HASH]);
write_stage2(&store, COMPOSED_REF, who, true);
// Half the rows disagree with the truth, so half the page really flips.
write_stage2(&store, COHORT, who, index % 2 == 0);
stage2_key(COHORT, who)
})
.collect();
let handle = handle(&store);
// Warm the block cache, so the timed passes measure the read shape and not the first
// touch of every SST.
let warm_by_page = read_page(&handle, &filters, COHORT, &page).await.unwrap();
let warm_per_row = per_row(&store, &filters, &page).await;
assert_eq!(
warm_by_page.iter().map(settled).collect::<Vec<_>>(),
warm_per_row.iter().map(settled).collect::<Vec<_>>(),
);
let started = Instant::now();
per_row(&store, &filters, &page).await;
let per_row_elapsed = started.elapsed();
let started = Instant::now();
read_page(&handle, &filters, COHORT, &page).await.unwrap();
let by_page_elapsed = started.elapsed();
println!(
"{:>5} {:>10.1?} {:>10.1?} {:>6.2}x",
rows,
per_row_elapsed,
by_page_elapsed,
per_row_elapsed.as_secs_f64() / by_page_elapsed.as_secs_f64(),
);
}
}
/// One entry per day of a year-long window, so each value is kilobytes rather than bytes.
fn year_long_history() -> Stage1State {
Stage1State::BehavioralCompressedHistory {
entries: (0..365).map(|day| (20_600 + day, 1)).collect(),
window_start_day: 20_600,
last_event_at_ms: EVENT_MS,
earliest_eviction_at_ms: i64::MAX,
}
}
}