Skip to content

: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.

63.1 KB
Raw Blame
use std::collections::{BTreeMap, VecDeque};
use std::fmt;
use std::mem::size_of;

use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
use serde::Serialize;
use serde_json::Value;
use uuid::Uuid;

use super::ops::{
    CanonicalReadPayload, DistinctIdAssignmentPayload, DistinctIdMove, FullMergePayload,
    MergeShape, NanosSincePhaseStart, OpDescriptor, OpPayload, OperationId, PersonUpsertPayload,
    ReadExpectation,
};

const ZIPF_EXPONENT: f64 = 1.5;
const RECENT_SELECTION_ATTEMPTS: usize = 8;
const FANOUT_ROLLS: u32 = 100_000;
const WHALE_MIN_FANOUT: u32 = 101;
const PROPERTY_SEED_MIX: u64 = 0xa076_1d64_78bd_642f;
const NONE_INDEX: u32 = u32::MAX;
const PENDING_INDEX: u32 = u32::MAX - 1;
const ARENA_CHUNK_CAPACITY: usize = 65_536;

// RFC sample: 95% single-DID, almost all remaining at 2, with rare large tails.
const FANOUT_BUCKETS: [FanoutBucket; 4] = [
    FanoutBucket::new(95_000, 1, 1),
    FanoutBucket::new(99_990, 2, 2),
    FanoutBucket::new(99_999, 3, 100),
    FanoutBucket::new(FANOUT_ROLLS, 101, 1_000),
];

#[derive(Debug, Clone, Copy)]
struct FanoutBucket {
    upper_roll_exclusive: u32,
    min: u32,
    max: u32,
}

impl FanoutBucket {
    const fn new(upper_roll_exclusive: u32, min: u32, max: u32) -> Self {
        Self {
            upper_roll_exclusive,
            min,
            max,
        }
    }
}

#[derive(Debug, Clone)]
pub struct WorldConfig {
    pub seed: u64,
    pub team_count: i32,
    pub initial_person_count: usize,
    pub recent_capacity_per_team: usize,
    pub recent_target_percent: u8,
    pub property_bytes: usize,
}

impl Default for WorldConfig {
    fn default() -> Self {
        Self {
            seed: 42,
            team_count: 100,
            initial_person_count: 100_000,
            recent_capacity_per_team: 4_096,
            recent_target_percent: 50,
            property_bytes: 700,
        }
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ReplayMode {
    Fresh,
    Stale,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum AssignmentMode {
    New,
    FreshExisting,
    StaleReplay,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ReadMode {
    Hit,
    Miss,
}

#[derive(Debug, Clone, PartialEq)]
pub struct CreationDescriptors {
    pub person_upsert: OpDescriptor,
    pub distinct_id_assignment: OpDescriptor,
    pub activation: PendingCreationToken,
}

#[derive(Debug, Clone, PartialEq)]
pub struct AssignmentDescriptor {
    pub operation: OpDescriptor,
    pub activation: Option<PendingDistinctIdToken>,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct PendingCreationToken {
    person: PersonKey,
    distinct_id: DistinctIdKey,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct PendingDistinctIdToken {
    distinct_id: DistinctIdKey,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
#[repr(transparent)]
struct PersonKey(u32);

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[repr(transparent)]
struct DistinctIdKey(u32);

#[derive(Debug)]
struct ChunkedArena<T> {
    chunks: Vec<Vec<T>>,
    len: u32,
}

impl<T> ChunkedArena<T> {
    fn new() -> Self {
        Self {
            chunks: Vec::new(),
            len: 0,
        }
    }

    fn push(&mut self, value: T) -> Option<u32> {
        if self.len >= PENDING_INDEX {
            return None;
        }
        if self
            .chunks
            .last()
            .is_none_or(|chunk| chunk.len() == ARENA_CHUNK_CAPACITY)
        {
            self.chunks.push(Vec::with_capacity(ARENA_CHUNK_CAPACITY));
        }
        let index = self.len;
        self.chunks.last_mut()?.push(value);
        self.len += 1;
        Some(index)
    }

    fn can_push(&self, count: u32) -> bool {
        self.len
            .checked_add(count)
            .is_some_and(|len| len <= PENDING_INDEX)
    }

    fn len(&self) -> usize {
        self.len as usize
    }

    fn get(&self, index: u32) -> &T {
        let index = index as usize;
        &self.chunks[index / ARENA_CHUNK_CAPACITY][index % ARENA_CHUNK_CAPACITY]
    }

    fn get_mut(&mut self, index: u32) -> &mut T {
        let index = index as usize;
        &mut self.chunks[index / ARENA_CHUNK_CAPACITY][index % ARENA_CHUNK_CAPACITY]
    }

    fn iter(&self) -> impl Iterator<Item = &T> {
        self.chunks.iter().flat_map(|chunk| chunk.iter())
    }

    #[cfg(test)]
    fn chunk_count(&self) -> usize {
        self.chunks.len()
    }
}

#[derive(Debug)]
#[repr(C)]
struct PersonState {
    version: i64,
    first_distinct_id: u32,
    last_distinct_id: u32,
    distinct_id_count: u32,
    team_index: u32,
    live_index: u32,
    whale_index: u32,
}

impl PersonState {
    fn new(team_index: u32, live_index: u32) -> Self {
        Self {
            version: 1,
            first_distinct_id: NONE_INDEX,
            last_distinct_id: NONE_INDEX,
            distinct_id_count: 0,
            team_index,
            live_index,
            whale_index: NONE_INDEX,
        }
    }

    fn first_distinct_id(&self) -> Option<DistinctIdKey> {
        (self.first_distinct_id != NONE_INDEX).then_some(DistinctIdKey(self.first_distinct_id))
    }

    fn last_distinct_id(&self) -> Option<DistinctIdKey> {
        (self.last_distinct_id != NONE_INDEX).then_some(DistinctIdKey(self.last_distinct_id))
    }

    fn live_index(&self) -> Option<usize> {
        (self.live_index != NONE_INDEX).then_some(self.live_index as usize)
    }

    fn whale_index(&self) -> Option<usize> {
        (self.whale_index != NONE_INDEX).then_some(self.whale_index as usize)
    }

    fn clear_distinct_ids(&mut self) {
        self.first_distinct_id = NONE_INDEX;
        self.last_distinct_id = NONE_INDEX;
        self.distinct_id_count = 0;
    }
}

#[derive(Debug)]
#[repr(C)]
struct DistinctIdState {
    version: i64,
    owner: PersonKey,
    next: u32,
}

impl DistinctIdState {
    fn next(&self) -> Option<DistinctIdKey> {
        (self.next < PENDING_INDEX).then_some(DistinctIdKey(self.next))
    }

    fn is_pending(&self) -> bool {
        self.next == PENDING_INDEX
    }
}

#[derive(Debug)]
struct TeamState {
    team_id: i32,
    live_persons: Vec<PersonKey>,
    whales: Vec<PersonKey>,
    recent: VecDeque<PersonKey>,
    pending_persons: u32,
}

impl TeamState {
    fn new(team_id: i32, initial_person_count: usize) -> Self {
        Self {
            team_id,
            live_persons: Vec::with_capacity(initial_person_count),
            whales: Vec::new(),
            recent: VecDeque::new(),
            pending_persons: 0,
        }
    }
}

#[derive(Debug)]
pub struct WorldState {
    topology_rng: StdRng,
    property_rng: StdRng,
    seed: u64,
    property_bytes: usize,
    recent_capacity_per_team: usize,
    recent_target_percent: u8,
    team_cdf: Vec<f64>,
    teams: Vec<TeamState>,
    persons: ChunkedArena<PersonState>,
    distinct_ids: ChunkedArena<DistinctIdState>,
    pending_distinct_ids_by_person: BTreeMap<PersonKey, u32>,
    growth_reservation_enabled: bool,
    next_miss_counter: u64,
    next_operation_id: u64,
}

impl WorldState {
    pub fn new(config: WorldConfig) -> Result<Self, WorldError> {
        if config.team_count <= 0 {
            return Err(WorldError::InvalidTeamCount(config.team_count));
        }
        if config.recent_target_percent > 100 {
            return Err(WorldError::InvalidRecentTargetPercent(
                config.recent_target_percent,
            ));
        }
        if u64::try_from(config.initial_person_count).unwrap_or(u64::MAX) >= u64::from(u32::MAX) {
            return Err(WorldError::PopulationTooLarge(config.initial_person_count));
        }

        let weights: Vec<f64> = (1..=config.team_count)
            .map(|rank| 1.0 / f64::from(rank).powf(ZIPF_EXPONENT))
            .collect();
        let team_counts = allocate_zipf_counts(&weights, config.initial_person_count);
        let total_weight: f64 = weights.iter().sum();
        let mut cumulative = 0.0;
        let team_cdf = weights
            .iter()
            .map(|weight| {
                cumulative += weight / total_weight;
                cumulative
            })
            .collect::<Vec<_>>();

        let teams = team_counts
            .iter()
            .enumerate()
            .map(|(team_index, count)| TeamState::new(team_index as i32 + 1, *count))
            .collect();
        let mut world = Self {
            topology_rng: StdRng::seed_from_u64(config.seed),
            property_rng: StdRng::seed_from_u64(config.seed ^ PROPERTY_SEED_MIX),
            seed: config.seed,
            property_bytes: config.property_bytes,
            recent_capacity_per_team: config.recent_capacity_per_team,
            recent_target_percent: config.recent_target_percent,
            team_cdf,
            teams,
            persons: ChunkedArena::new(),
            distinct_ids: ChunkedArena::new(),
            pending_distinct_ids_by_person: BTreeMap::new(),
            growth_reservation_enabled: false,
            next_miss_counter: 1,
            next_operation_id: 1,
        };

        for (team_index, count) in team_counts.into_iter().enumerate() {
            for _ in 0..count {
                let fanout = world.sample_fanout();
                world.create_person(team_index, fanout)?;
            }
        }
        Ok(world)
    }

    pub fn population(&self) -> PopulationView<'_> {
        PopulationView { world: self }
    }

    pub fn live_person_count(&self) -> usize {
        self.teams.iter().map(|team| team.live_persons.len()).sum()
    }

    pub fn distinct_id_count(&self) -> usize {
        self.distinct_ids.len()
    }

    pub fn reserve_person_growth(
        &mut self,
        person_creations: PersonCreationCount,
    ) -> Result<(), WorldError> {
        let total = usize::try_from(person_creations.get())
            .map_err(|_| WorldError::MemoryEstimateOverflow)?;
        let mut previous = 0.0;
        let weights = self
            .team_cdf
            .iter()
            .map(|cumulative| {
                let weight = cumulative - previous;
                previous = *cumulative;
                weight
            })
            .collect::<Vec<_>>();
        for (team, additional) in self
            .teams
            .iter_mut()
            .zip(allocate_zipf_counts(&weights, total))
        {
            team.live_persons
                .try_reserve_exact(additional)
                .map_err(|_| WorldError::AllocationFailed("team live person"))?;
        }
        self.growth_reservation_enabled = true;
        Ok(())
    }

    pub fn estimate_initial_memory(
        config: &WorldConfig,
    ) -> Result<WorldMemoryEstimate, WorldError> {
        Self::estimate_memory(config, WorldGrowth::default())
    }

    pub fn estimate_memory(
        config: &WorldConfig,
        growth: WorldGrowth,
    ) -> Result<WorldMemoryEstimate, WorldError> {
        if config.team_count <= 0 {
            return Err(WorldError::InvalidTeamCount(config.team_count));
        }
        let initial_person_count = u64::try_from(config.initial_person_count)
            .map_err(|_| WorldError::MemoryEstimateOverflow)?;
        let person_count = initial_person_count
            .checked_add(growth.person_creations.get())
            .ok_or(WorldError::MemoryEstimateOverflow)?;
        let distinct_id_count = expected_distinct_id_count(initial_person_count)?
            .checked_add(growth.person_creations.get())
            .and_then(|count| count.checked_add(growth.distinct_id_assignments.get()))
            .ok_or(WorldError::MemoryEstimateOverflow)?;
        let person_chunks = chunk_count(person_count)?;
        let distinct_id_chunks = chunk_count(distinct_id_count)?;
        let person_arena_bytes = chunk_allocation_bytes(person_chunks, size_of::<PersonState>())?;
        let distinct_id_arena_bytes =
            chunk_allocation_bytes(distinct_id_chunks, size_of::<DistinctIdState>())?;
        let live_person_index_bytes = checked_product(person_count, size_of::<PersonKey>() as u64)?;
        let recent_capacity = checked_product(
            config.team_count as u64,
            config.recent_capacity_per_team as u64,
        )?;
        let recent_index_bytes = checked_product(recent_capacity, size_of::<PersonKey>() as u64)?;
        let initial_whale_count = div_ceil(
            checked_product(initial_person_count, whale_bucket_rolls())?,
            u64::from(FANOUT_ROLLS),
        )?;
        let whale_count = initial_whale_count
            .checked_add(growth.distinct_id_assignments.get().min(person_count))
            .ok_or(WorldError::MemoryEstimateOverflow)?
            .min(person_count);
        let whale_index_bytes = checked_product(whale_count, size_of::<PersonKey>() as u64)?;
        let team_state_bytes =
            checked_product(config.team_count as u64, size_of::<TeamState>() as u64)?;
        let chunk_metadata_bytes = checked_product(
            person_chunks
                .checked_add(distinct_id_chunks)
                .ok_or(WorldError::MemoryEstimateOverflow)?,
            size_of::<Vec<PersonState>>() as u64,
        )?;
        let total_bytes = [
            person_arena_bytes,
            distinct_id_arena_bytes,
            live_person_index_bytes,
            recent_index_bytes,
            whale_index_bytes,
            team_state_bytes,
            chunk_metadata_bytes,
        ]
        .into_iter()
        .try_fold(0u64, |total, bytes| {
            total
                .checked_add(bytes)
                .ok_or(WorldError::MemoryEstimateOverflow)
        })?;

        Ok(WorldMemoryEstimate {
            growth,
            person_count,
            expected_distinct_id_count: distinct_id_count,
            person_slot_bytes: size_of::<PersonState>(),
            distinct_id_slot_bytes: size_of::<DistinctIdState>(),
            person_arena_bytes,
            distinct_id_arena_bytes,
            live_person_index_bytes,
            recent_index_bytes,
            whale_index_bytes,
            chunk_metadata_bytes,
            total_bytes,
        })
    }

    pub fn resolve_person_upsert(
        &mut self,
        scheduled_at: NanosSincePhaseStart,
        replay: ReplayMode,
    ) -> Result<OpDescriptor, WorldError> {
        let team_index = self.select_team(|team| !team.live_persons.is_empty())?;
        let person_key = self.select_person(team_index, None, false, false)?;
        let current_version = self.person(person_key).version;
        let version = match replay {
            ReplayMode::Fresh => {
                let version = increment_version(current_version)?;
                self.person_mut(person_key).version = version;
                version
            }
            ReplayMode::Stale => stale_version(current_version),
        };
        let payload = PersonUpsertPayload {
            team_id: self.teams[team_index].team_id,
            person_uuid: self.person_uuid(person_key),
            properties: generate_properties(&mut self.property_rng, self.property_bytes),
            version,
        };
        self.touch_person(person_key);
        self.describe(scheduled_at, OpPayload::PersonUpsert(payload))
    }

    pub fn resolve_distinct_id_assignment(
        &mut self,
        scheduled_at: NanosSincePhaseStart,
        mode: AssignmentMode,
    ) -> Result<AssignmentDescriptor, WorldError> {
        let team_index = self.select_team(|team| !team.live_persons.is_empty())?;
        let person_key = self.select_person(team_index, None, false, false)?;
        let distinct_id_key = match mode {
            AssignmentMode::New => self.reserve_distinct_id(person_key)?,
            AssignmentMode::FreshExisting | AssignmentMode::StaleReplay => {
                self.select_distinct_id(person_key)?
            }
        };
        let version = match mode {
            AssignmentMode::New => self.distinct_id(distinct_id_key).version,
            AssignmentMode::FreshExisting => {
                let version = increment_version(self.distinct_id(distinct_id_key).version)?;
                self.distinct_id_mut(distinct_id_key).version = version;
                version
            }
            AssignmentMode::StaleReplay => stale_version(self.distinct_id(distinct_id_key).version),
        };
        let payload = DistinctIdAssignmentPayload {
            team_id: self.teams[team_index].team_id,
            person_uuid: self.person_uuid(person_key),
            distinct_id: self.distinct_id_value(distinct_id_key),
            version,
        };
        self.touch_person(person_key);
        let operation = self.describe(scheduled_at, OpPayload::DistinctIdAssignment(payload))?;
        Ok(AssignmentDescriptor {
            operation,
            activation: (mode == AssignmentMode::New).then_some(PendingDistinctIdToken {
                distinct_id: distinct_id_key,
            }),
        })
    }

    pub fn resolve_creation(
        &mut self,
        scheduled_at: NanosSincePhaseStart,
    ) -> Result<CreationDescriptors, WorldError> {
        let enforce_reservation = self.growth_reservation_enabled;
        let team_index = self.select_team(|team| {
            !enforce_reservation
                || team
                    .live_persons
                    .len()
                    .saturating_add(team.pending_persons as usize)
                    < team.live_persons.capacity()
        })?;
        let person_key = self.reserve_person(team_index)?;
        let distinct_id_key = self.reserve_distinct_id(person_key)?;
        let team_id = self.teams[team_index].team_id;
        let person_uuid = self.person_uuid(person_key);
        let person_version = self.person(person_key).version;
        let distinct_id_value = self.distinct_id_value(distinct_id_key);
        let distinct_id_version = self.distinct_id(distinct_id_key).version;
        let properties = generate_properties(&mut self.property_rng, self.property_bytes);

        let person_upsert = self.describe(
            scheduled_at,
            OpPayload::PersonUpsert(PersonUpsertPayload {
                team_id,
                person_uuid,
                properties,
                version: person_version,
            }),
        )?;
        let distinct_id_assignment = self.describe(
            scheduled_at,
            OpPayload::DistinctIdAssignment(DistinctIdAssignmentPayload {
                team_id,
                person_uuid,
                distinct_id: distinct_id_value,
                version: distinct_id_version,
            }),
        )?;
        Ok(CreationDescriptors {
            person_upsert,
            distinct_id_assignment,
            activation: PendingCreationToken {
                person: person_key,
                distinct_id: distinct_id_key,
            },
        })
    }

    pub fn activate_creation(&mut self, token: PendingCreationToken) -> Result<(), WorldError> {
        if self.person(token.person).live_index().is_some()
            || !self.distinct_id(token.distinct_id).is_pending()
            || self.distinct_id(token.distinct_id).owner != token.person
        {
            return Err(WorldError::InvalidPendingActivation);
        }
        self.activate_person(token.person)?;
        self.activate_distinct_id_key(token.distinct_id)?;
        self.touch_person(token.person);
        Ok(())
    }

    pub fn activate_distinct_id(
        &mut self,
        token: PendingDistinctIdToken,
    ) -> Result<(), WorldError> {
        self.activate_distinct_id_key(token.distinct_id)
    }

    pub fn abandon_distinct_id(&mut self, token: PendingDistinctIdToken) -> Result<(), WorldError> {
        if !self.distinct_id(token.distinct_id).is_pending() {
            return Err(WorldError::InvalidPendingActivation);
        }
        let person_key = self.distinct_id(token.distinct_id).owner;
        self.remove_pending_distinct_id(person_key)
    }

    pub fn resolve_full_merge(
        &mut self,
        scheduled_at: NanosSincePhaseStart,
    ) -> Result<OpDescriptor, WorldError> {
        self.resolve_merge(scheduled_at, MergeShape::Standard)
    }

    pub fn resolve_whale_merge(
        &mut self,
        scheduled_at: NanosSincePhaseStart,
    ) -> Result<OpDescriptor, WorldError> {
        self.resolve_merge(scheduled_at, MergeShape::Whale)
    }

    pub fn resolve_read(
        &mut self,
        scheduled_at: NanosSincePhaseStart,
        mode: ReadMode,
    ) -> Result<OpDescriptor, WorldError> {
        let team_index = self.select_team(|team| !team.live_persons.is_empty())?;
        let team_id = self.teams[team_index].team_id;
        let payload = match mode {
            ReadMode::Hit => {
                let person_key = self.select_person(team_index, None, false, false)?;
                let distinct_id_key = self.select_distinct_id(person_key)?;
                let payload = CanonicalReadPayload {
                    team_id,
                    distinct_id: self.distinct_id_value(distinct_id_key),
                    expectation: ReadExpectation::Hit,
                };
                self.touch_person(person_key);
                payload
            }
            ReadMode::Miss => CanonicalReadPayload {
                team_id,
                distinct_id: self.next_miss_distinct_id()?,
                expectation: ReadExpectation::Miss,
            },
        };
        self.describe(scheduled_at, OpPayload::CanonicalRead(payload))
    }

    fn resolve_merge(
        &mut self,
        scheduled_at: NanosSincePhaseStart,
        shape: MergeShape,
    ) -> Result<OpDescriptor, WorldError> {
        let eligible_teams = self
            .teams
            .iter()
            .map(|team| {
                let sources = if shape == MergeShape::Whale {
                    &team.whales
                } else {
                    &team.live_persons
                };
                team.live_persons.len() >= 2
                    && sources
                        .iter()
                        .any(|source| !self.pending_distinct_ids_by_person.contains_key(source))
            })
            .collect::<Vec<_>>();
        let team_index = self.select_eligible_team(&eligible_teams)?;
        let source = self.select_person(team_index, None, shape == MergeShape::Whale, true)?;
        let target = self.select_person(team_index, Some(source), false, false)?;

        let source_version = self.person(source).version;
        let target_version = self.person(target).version;
        let merged_target_version = source_version
            .max(target_version)
            .checked_add(1)
            .ok_or(WorldError::VersionExhausted)?;
        let source_tombstone_version = source_version
            .checked_add(100)
            .ok_or(WorldError::VersionExhausted)?;
        let source_first = self.person(source).first_distinct_id();
        let source_last = self.person(source).last_distinct_id();
        let source_count = self.person(source).distinct_id_count;
        let target_first = self.person(target).first_distinct_id();
        let target_last = self.person(target).last_distinct_id();
        let merged_count = self
            .person(target)
            .distinct_id_count
            .checked_add(source_count)
            .ok_or(WorldError::FanoutExhausted)?;

        let mut planned_moves = Vec::with_capacity(source_count as usize);
        let mut current = source_first;
        while let Some(distinct_id_key) = current {
            let distinct_id = self.distinct_id(distinct_id_key);
            let version = increment_version(distinct_id.version)?;
            planned_moves.push((
                distinct_id_key,
                version,
                self.distinct_id_value(distinct_id_key),
            ));
            current = distinct_id.next();
        }

        if let (Some(target_last), Some(source_first)) = (target_last, source_first) {
            self.distinct_id_mut(target_last).next = source_first.0;
        }
        let mut moves = Vec::with_capacity(planned_moves.len());
        for (distinct_id_key, version, distinct_id) in planned_moves {
            let state = self.distinct_id_mut(distinct_id_key);
            state.owner = target;
            state.version = version;
            moves.push(DistinctIdMove {
                distinct_id,
                version,
            });
        }

        {
            let target_state = self.person_mut(target);
            target_state.first_distinct_id = target_first
                .or(source_first)
                .map_or(NONE_INDEX, |key| key.0);
            target_state.last_distinct_id =
                source_last.or(target_last).map_or(NONE_INDEX, |key| key.0);
            target_state.distinct_id_count = merged_count;
            target_state.version = merged_target_version;
        }
        {
            let source_state = self.person_mut(source);
            source_state.clear_distinct_ids();
            source_state.version = source_tombstone_version;
        }

        let source_uuid = self.person_uuid(source);
        let target_uuid = self.person_uuid(target);
        self.ensure_whale(target);
        self.remove_live_person(source);
        self.touch_person(target);

        let payload = FullMergePayload {
            team_id: self.teams[team_index].team_id,
            source_person_uuid: source_uuid,
            target_person_uuid: target_uuid,
            distinct_id_moves: moves.into_boxed_slice(),
            target_properties: generate_properties(&mut self.property_rng, self.property_bytes),
            target_version: merged_target_version,
            source_tombstone_version,
            shape,
        };
        self.describe(scheduled_at, OpPayload::FullMerge(payload))
    }

    fn describe(
        &mut self,
        scheduled_at: NanosSincePhaseStart,
        payload: OpPayload,
    ) -> Result<OpDescriptor, WorldError> {
        let operation_id = OperationId(self.next_operation_id);
        self.next_operation_id = self
            .next_operation_id
            .checked_add(1)
            .ok_or(WorldError::IdentifierExhausted("operation"))?;
        Ok(OpDescriptor::new(operation_id, scheduled_at, payload))
    }

    fn create_person(&mut self, team_index: usize, fanout: u32) -> Result<PersonKey, WorldError> {
        if !self.distinct_ids.can_push(fanout) {
            return Err(WorldError::ArenaExhausted("distinct ID"));
        }
        let person_key = self.reserve_person(team_index)?;
        self.activate_person(person_key)?;
        for _ in 0..fanout {
            self.create_distinct_id(person_key)?;
        }
        self.ensure_whale(person_key);
        self.touch_person(person_key);
        Ok(person_key)
    }

    fn reserve_person(&mut self, team_index: usize) -> Result<PersonKey, WorldError> {
        let pending_persons = self.teams[team_index]
            .pending_persons
            .checked_add(1)
            .ok_or(WorldError::IndexExhausted("pending person"))?;
        let team_index =
            u32::try_from(team_index).map_err(|_| WorldError::IndexExhausted("team"))?;
        let person_index = self
            .persons
            .push(PersonState::new(team_index, NONE_INDEX))
            .ok_or(WorldError::ArenaExhausted("person"))?;
        self.teams[team_index as usize].pending_persons = pending_persons;
        Ok(PersonKey(person_index))
    }

    fn activate_person(&mut self, person_key: PersonKey) -> Result<(), WorldError> {
        if self.person(person_key).live_index().is_some() {
            return Err(WorldError::InvalidPendingActivation);
        }
        let team_index = self.person(person_key).team_index as usize;
        let live_index = u32::try_from(self.teams[team_index].live_persons.len())
            .map_err(|_| WorldError::IndexExhausted("team live person"))?;
        self.teams[team_index].pending_persons = self.teams[team_index]
            .pending_persons
            .checked_sub(1)
            .ok_or(WorldError::InvalidPendingActivation)?;
        self.teams[team_index].live_persons.push(person_key);
        self.person_mut(person_key).live_index = live_index;
        Ok(())
    }

    fn create_distinct_id(&mut self, person_key: PersonKey) -> Result<DistinctIdKey, WorldError> {
        let distinct_id_key = self.reserve_distinct_id(person_key)?;
        self.activate_distinct_id_key(distinct_id_key)?;
        Ok(distinct_id_key)
    }

    fn reserve_distinct_id(&mut self, person_key: PersonKey) -> Result<DistinctIdKey, WorldError> {
        let distinct_id_index = self
            .distinct_ids
            .push(DistinctIdState {
                version: 1,
                owner: person_key,
                next: PENDING_INDEX,
            })
            .ok_or(WorldError::ArenaExhausted("distinct ID"))?;
        let pending = self
            .pending_distinct_ids_by_person
            .entry(person_key)
            .or_default();
        *pending = pending.checked_add(1).ok_or(WorldError::FanoutExhausted)?;
        Ok(DistinctIdKey(distinct_id_index))
    }

    fn activate_distinct_id_key(
        &mut self,
        distinct_id_key: DistinctIdKey,
    ) -> Result<(), WorldError> {
        if !self.distinct_id(distinct_id_key).is_pending() {
            return Err(WorldError::InvalidPendingActivation);
        }
        let person_key = self.distinct_id(distinct_id_key).owner;
        if self.person(person_key).live_index().is_none() {
            return Err(WorldError::InvalidPendingActivation);
        }
        let count = self
            .person(person_key)
            .distinct_id_count
            .checked_add(1)
            .ok_or(WorldError::FanoutExhausted)?;
        self.remove_pending_distinct_id(person_key)?;
        let previous_last = self.person(person_key).last_distinct_id();
        self.distinct_id_mut(distinct_id_key).next = NONE_INDEX;
        if let Some(previous_last) = previous_last {
            self.distinct_id_mut(previous_last).next = distinct_id_key.0;
        }
        let person = self.person_mut(person_key);
        if person.first_distinct_id == NONE_INDEX {
            person.first_distinct_id = distinct_id_key.0;
        }
        person.last_distinct_id = distinct_id_key.0;
        person.distinct_id_count = count;
        self.ensure_whale(person_key);
        Ok(())
    }

    fn remove_pending_distinct_id(&mut self, person_key: PersonKey) -> Result<(), WorldError> {
        let remove_entry = {
            let pending = self
                .pending_distinct_ids_by_person
                .get_mut(&person_key)
                .ok_or(WorldError::InvalidPendingActivation)?;
            *pending = pending
                .checked_sub(1)
                .ok_or(WorldError::InvalidPendingActivation)?;
            *pending == 0
        };
        if remove_entry {
            self.pending_distinct_ids_by_person.remove(&person_key);
        }
        Ok(())
    }

    fn person(&self, key: PersonKey) -> &PersonState {
        self.persons.get(key.0)
    }

    fn person_mut(&mut self, key: PersonKey) -> &mut PersonState {
        self.persons.get_mut(key.0)
    }

    fn distinct_id(&self, key: DistinctIdKey) -> &DistinctIdState {
        self.distinct_ids.get(key.0)
    }

    fn distinct_id_mut(&mut self, key: DistinctIdKey) -> &mut DistinctIdState {
        self.distinct_ids.get_mut(key.0)
    }

    fn person_uuid(&self, person_key: PersonKey) -> Uuid {
        Uuid::from_u128((u128::from(self.seed) << 64) | u128::from(person_key.0).saturating_add(1))
    }

    fn distinct_id_value(&self, distinct_id_key: DistinctIdKey) -> Box<str> {
        format!(
            "bench-{:016x}-{:016x}",
            self.seed,
            u64::from(distinct_id_key.0) + 1
        )
        .into_boxed_str()
    }

    fn next_miss_distinct_id(&mut self) -> Result<Box<str>, WorldError> {
        let counter = self.next_miss_counter;
        self.next_miss_counter = counter
            .checked_add(1)
            .ok_or(WorldError::IdentifierExhausted("read miss"))?;
        Ok(format!("bench-miss-{:016x}-{counter:016x}", self.seed).into_boxed_str())
    }

    fn sample_fanout(&mut self) -> u32 {
        let bucket_roll = self.topology_rng.gen_range(0..FANOUT_ROLLS);
        let within_bucket_roll = self.topology_rng.gen::<u64>();
        fanout_for_roll(bucket_roll, within_bucket_roll)
    }

    fn select_team<F>(&mut self, eligible: F) -> Result<usize, WorldError>
    where
        F: Fn(&TeamState) -> bool,
    {
        let eligible = self.teams.iter().map(eligible).collect::<Vec<_>>();
        self.select_eligible_team(&eligible)
    }

    fn select_eligible_team(&mut self, eligible: &[bool]) -> Result<usize, WorldError> {
        for _ in 0..self.teams.len().saturating_mul(2).max(1) {
            let roll = self.topology_rng.gen::<f64>();
            let team_index = self
                .team_cdf
                .partition_point(|cumulative| *cumulative < roll)
                .min(self.teams.len() - 1);
            if eligible[team_index] {
                return Ok(team_index);
            }
        }
        eligible
            .iter()
            .position(|eligible| *eligible)
            .ok_or(WorldError::NoEligiblePerson)
    }

    fn select_person(
        &mut self,
        team_index: usize,
        exclude: Option<PersonKey>,
        whale_only: bool,
        exclude_pending: bool,
    ) -> Result<PersonKey, WorldError> {
        if !whale_only
            && self
                .topology_rng
                .gen_ratio(u32::from(self.recent_target_percent), 100)
            && !self.teams[team_index].recent.is_empty()
        {
            for _ in 0..RECENT_SELECTION_ATTEMPTS {
                let index = self
                    .topology_rng
                    .gen_range(0..self.teams[team_index].recent.len());
                let candidate = self.teams[team_index].recent[index];
                if self.person(candidate).live_index().is_some()
                    && Some(candidate) != exclude
                    && (!exclude_pending
                        || !self.pending_distinct_ids_by_person.contains_key(&candidate))
                {
                    return Ok(candidate);
                }
            }
        }

        let candidates = if whale_only {
            &self.teams[team_index].whales
        } else {
            &self.teams[team_index].live_persons
        };
        if candidates.is_empty() {
            return Err(WorldError::NoEligiblePerson);
        }
        let start = self.topology_rng.gen_range(0..candidates.len());
        for offset in 0..candidates.len() {
            let candidate = candidates[(start + offset) % candidates.len()];
            if Some(candidate) != exclude
                && (!exclude_pending
                    || !self.pending_distinct_ids_by_person.contains_key(&candidate))
            {
                return Ok(candidate);
            }
        }
        Err(WorldError::NoEligiblePerson)
    }

    fn select_distinct_id(&mut self, person_key: PersonKey) -> Result<DistinctIdKey, WorldError> {
        let (head, tail, count) = {
            let person = self.person(person_key);
            (
                person
                    .first_distinct_id()
                    .ok_or(WorldError::NoEligibleDistinctId)?,
                person.last_distinct_id(),
                person.distinct_id_count,
            )
        };
        if count > 1 {
            let tail = tail.ok_or(WorldError::NoEligibleDistinctId)?;
            let next = self
                .distinct_id(head)
                .next()
                .ok_or(WorldError::NoEligibleDistinctId)?;
            self.distinct_id_mut(tail).next = head.0;
            self.distinct_id_mut(head).next = NONE_INDEX;
            let person = self.person_mut(person_key);
            person.first_distinct_id = next.0;
            person.last_distinct_id = head.0;
        }
        Ok(head)
    }

    fn touch_person(&mut self, person_key: PersonKey) {
        if self.recent_capacity_per_team == 0 || self.person(person_key).live_index().is_none() {
            return;
        }
        let team_index = self.person(person_key).team_index as usize;
        let recent = &mut self.teams[team_index].recent;
        recent.push_back(person_key);
        if recent.len() > self.recent_capacity_per_team {
            recent.pop_front();
        }
    }

    fn ensure_whale(&mut self, person_key: PersonKey) {
        let person = self.person(person_key);
        if person.distinct_id_count < WHALE_MIN_FANOUT
            || person.whale_index().is_some()
            || person.live_index().is_none()
        {
            return;
        }
        let team_index = person.team_index as usize;
        let Ok(whale_index) = u32::try_from(self.teams[team_index].whales.len()) else {
            return;
        };
        self.teams[team_index].whales.push(person_key);
        self.person_mut(person_key).whale_index = whale_index;
    }

    fn remove_live_person(&mut self, person_key: PersonKey) {
        let team_index = self.person(person_key).team_index as usize;
        let live_index = self
            .person(person_key)
            .live_index()
            .expect("only live persons can be merged");
        let moved_live = {
            let live_persons = &mut self.teams[team_index].live_persons;
            live_persons.swap_remove(live_index);
            live_persons.get(live_index).copied()
        };
        if let Some(moved) = moved_live {
            self.person_mut(moved).live_index = live_index as u32;
        }

        if let Some(whale_index) = self.person(person_key).whale_index() {
            let moved_whale = {
                let whales = &mut self.teams[team_index].whales;
                whales.swap_remove(whale_index);
                whales.get(whale_index).copied()
            };
            if let Some(moved) = moved_whale {
                self.person_mut(moved).whale_index = whale_index as u32;
            }
        }
        let person = self.person_mut(person_key);
        person.live_index = NONE_INDEX;
        person.whale_index = NONE_INDEX;
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct PopulationPerson {
    pub team_id: i32,
    pub person_uuid: Uuid,
    pub version: i64,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PopulationDistinctId {
    pub team_id: i32,
    pub person_uuid: Uuid,
    pub distinct_id: Box<str>,
    pub version: i64,
}

#[derive(Debug, Clone, Copy)]
pub struct PopulationView<'a> {
    world: &'a WorldState,
}

impl PopulationView<'_> {
    pub const fn property_bytes(&self) -> usize {
        self.world.property_bytes
    }

    pub const fn property_seed(&self) -> u64 {
        self.world.seed ^ PROPERTY_SEED_MIX
    }

    pub fn persons(&self) -> impl Iterator<Item = PopulationPerson> + '_ {
        self.world
            .persons
            .iter()
            .enumerate()
            .filter_map(|(index, person)| {
                person.live_index().map(|_| {
                    let person_key = PersonKey(index as u32);
                    PopulationPerson {
                        team_id: self.world.teams[person.team_index as usize].team_id,
                        person_uuid: self.world.person_uuid(person_key),
                        version: person.version,
                    }
                })
            })
    }

    pub fn distinct_ids(&self) -> impl Iterator<Item = PopulationDistinctId> + '_ {
        self.world
            .distinct_ids
            .iter()
            .enumerate()
            .filter(|(_, distinct_id)| !distinct_id.is_pending())
            .map(|(index, distinct_id)| {
                let owner = self.world.person(distinct_id.owner);
                PopulationDistinctId {
                    team_id: self.world.teams[owner.team_index as usize].team_id,
                    person_uuid: self.world.person_uuid(distinct_id.owner),
                    distinct_id: self.world.distinct_id_value(DistinctIdKey(index as u32)),
                    version: distinct_id.version,
                }
            })
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
#[repr(transparent)]
pub struct PersonCreationCount(u64);

impl PersonCreationCount {
    pub const fn new(count: u64) -> Self {
        Self(count)
    }

    pub const fn get(self) -> u64 {
        self.0
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
#[repr(transparent)]
pub struct DistinctIdAssignmentCount(u64);

impl DistinctIdAssignmentCount {
    pub const fn new(count: u64) -> Self {
        Self(count)
    }

    pub const fn get(self) -> u64 {
        self.0
    }
}

#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Serialize)]
pub struct WorldGrowth {
    pub person_creations: PersonCreationCount,
    pub distinct_id_assignments: DistinctIdAssignmentCount,
}

impl WorldGrowth {
    pub const fn new(
        person_creations: PersonCreationCount,
        distinct_id_assignments: DistinctIdAssignmentCount,
    ) -> Self {
        Self {
            person_creations,
            distinct_id_assignments,
        }
    }
}

impl Default for PersonCreationCount {
    fn default() -> Self {
        Self::new(0)
    }
}

impl Default for DistinctIdAssignmentCount {
    fn default() -> Self {
        Self::new(0)
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
pub struct WorldMemoryEstimate {
    pub growth: WorldGrowth,
    pub person_count: u64,
    pub expected_distinct_id_count: u64,
    pub person_slot_bytes: usize,
    pub distinct_id_slot_bytes: usize,
    pub person_arena_bytes: u64,
    pub distinct_id_arena_bytes: u64,
    pub live_person_index_bytes: u64,
    pub recent_index_bytes: u64,
    pub whale_index_bytes: u64,
    pub chunk_metadata_bytes: u64,
    pub total_bytes: u64,
}

impl WorldMemoryEstimate {
    pub const fn headroom_bytes(self, limit_bytes: u64) -> Option<u64> {
        limit_bytes.checked_sub(self.total_bytes)
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum WorldError {
    InvalidTeamCount(i32),
    InvalidRecentTargetPercent(u8),
    PopulationTooLarge(usize),
    NoEligiblePerson,
    NoEligibleDistinctId,
    VersionExhausted,
    FanoutExhausted,
    ArenaExhausted(&'static str),
    IndexExhausted(&'static str),
    IdentifierExhausted(&'static str),
    AllocationFailed(&'static str),
    MemoryEstimateOverflow,
    InvalidPendingActivation,
}

impl fmt::Display for WorldError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::InvalidTeamCount(team_count) => {
                write!(formatter, "team count must be positive, got {team_count}")
            }
            Self::InvalidRecentTargetPercent(percent) => {
                write!(
                    formatter,
                    "recent target percent must be at most 100, got {percent}"
                )
            }
            Self::PopulationTooLarge(count) => {
                write!(formatter, "population of {count} exceeds the u32 arena")
            }
            Self::NoEligiblePerson => formatter.write_str("no eligible live person"),
            Self::NoEligibleDistinctId => formatter.write_str("no eligible distinct ID"),
            Self::VersionExhausted => formatter.write_str("entity version exhausted"),
            Self::FanoutExhausted => formatter.write_str("person fanout exhausted"),
            Self::ArenaExhausted(kind) => write!(formatter, "{kind} arena exhausted"),
            Self::IndexExhausted(kind) => write!(formatter, "{kind} index exhausted"),
            Self::IdentifierExhausted(kind) => write!(formatter, "{kind} identifier exhausted"),
            Self::AllocationFailed(kind) => write!(formatter, "allocate {kind} index capacity"),
            Self::MemoryEstimateOverflow => formatter.write_str("memory estimate overflowed"),
            Self::InvalidPendingActivation => {
                formatter.write_str("pending world activation is invalid or already applied")
            }
        }
    }
}

impl std::error::Error for WorldError {}

fn increment_version(version: i64) -> Result<i64, WorldError> {
    version.checked_add(1).ok_or(WorldError::VersionExhausted)
}

fn stale_version(version: i64) -> i64 {
    version.saturating_sub(1)
}

fn allocate_zipf_counts(weights: &[f64], total: usize) -> Vec<usize> {
    let total_weight: f64 = weights.iter().sum();
    let exact = weights
        .iter()
        .map(|weight| weight / total_weight * total as f64)
        .collect::<Vec<_>>();
    let mut counts = exact
        .iter()
        .map(|value| value.floor() as usize)
        .collect::<Vec<_>>();
    let assigned: usize = counts.iter().sum();
    let mut remainders = exact
        .iter()
        .enumerate()
        .map(|(index, value)| (index, value.fract()))
        .collect::<Vec<_>>();
    remainders.sort_by(|left, right| {
        right
            .1
            .total_cmp(&left.1)
            .then_with(|| left.0.cmp(&right.0))
    });
    for (index, _) in remainders.into_iter().take(total.saturating_sub(assigned)) {
        counts[index] += 1;
    }
    counts
}

fn fanout_for_roll(bucket_roll: u32, within_bucket_roll: u64) -> u32 {
    let bucket = FANOUT_BUCKETS
        .iter()
        .find(|bucket| bucket_roll < bucket.upper_roll_exclusive)
        .unwrap_or(&FANOUT_BUCKETS[FANOUT_BUCKETS.len() - 1]);
    let width = u64::from(bucket.max - bucket.min + 1);
    bucket.min + (within_bucket_roll % width) as u32
}

fn whale_bucket_rolls() -> u64 {
    let previous_upper = FANOUT_BUCKETS[FANOUT_BUCKETS.len() - 2].upper_roll_exclusive;
    u64::from(FANOUT_ROLLS - previous_upper)
}

fn expected_distinct_id_count(person_count: u64) -> Result<u64, WorldError> {
    let weighted_doubled_fanout =
        FANOUT_BUCKETS
            .iter()
            .enumerate()
            .try_fold(0u64, |total, (index, bucket)| {
                let lower = if index == 0 {
                    0
                } else {
                    FANOUT_BUCKETS[index - 1].upper_roll_exclusive
                };
                let rolls = u64::from(bucket.upper_roll_exclusive - lower);
                let doubled_mean = u64::from(bucket.min + bucket.max);
                total
                    .checked_add(
                        rolls
                            .checked_mul(doubled_mean)
                            .ok_or(WorldError::MemoryEstimateOverflow)?,
                    )
                    .ok_or(WorldError::MemoryEstimateOverflow)
            })?;
    let numerator = person_count
        .checked_mul(weighted_doubled_fanout)
        .ok_or(WorldError::MemoryEstimateOverflow)?;
    div_ceil(numerator, u64::from(FANOUT_ROLLS) * 2)
}

fn chunk_count(items: u64) -> Result<u64, WorldError> {
    div_ceil(items, ARENA_CHUNK_CAPACITY as u64)
}

fn chunk_allocation_bytes(chunks: u64, item_bytes: usize) -> Result<u64, WorldError> {
    checked_product(
        checked_product(chunks, ARENA_CHUNK_CAPACITY as u64)?,
        item_bytes as u64,
    )
}

fn checked_product(left: u64, right: u64) -> Result<u64, WorldError> {
    left.checked_mul(right)
        .ok_or(WorldError::MemoryEstimateOverflow)
}

fn div_ceil(numerator: u64, denominator: u64) -> Result<u64, WorldError> {
    let adjusted = numerator
        .checked_add(denominator - 1)
        .ok_or(WorldError::MemoryEstimateOverflow)?;
    Ok(adjusted / denominator)
}

/// Generate a JSONB properties object padded to approximately `target_bytes`.
pub fn generate_properties(rng: &mut impl Rng, target_bytes: usize) -> Value {
    const KEYS: &[&str] = &[
        "$browser",
        "$os",
        "$initial_referrer",
        "$initial_referring_domain",
        "$geoip_city_name",
        "$geoip_country_code",
        "$geoip_time_zone",
        "email",
        "name",
        "plan",
        "company",
        "role",
        "signup_date",
        "last_login",
    ];

    let mut object = serde_json::Map::with_capacity(KEYS.len() + 1);
    for key in KEYS {
        let value_len = rng.gen_range(4..30);
        let value = (0..value_len)
            .map(|_| rng.gen_range(b'a'..=b'z') as char)
            .collect::<String>();
        object.insert((*key).to_owned(), Value::String(value));
    }
    let current_bytes = Value::Object(object.clone()).to_string().len();
    if current_bytes < target_bytes {
        let value_len = (target_bytes - current_bytes).saturating_sub(12);
        let padding = (0..value_len)
            .map(|_| rng.gen_range(b'a'..=b'z') as char)
            .collect::<String>();
        object.insert("_pad".to_owned(), Value::String(padding));
    }
    Value::Object(object)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::benchmark::ops::PhaseId;

    const TEST_PHASE: PhaseId = PhaseId::new(1);

    fn at(nanos: u64) -> NanosSincePhaseStart {
        at_in_phase(TEST_PHASE, nanos)
    }

    fn at_in_phase(phase_id: PhaseId, nanos: u64) -> NanosSincePhaseStart {
        NanosSincePhaseStart::from_nanos(phase_id, nanos)
    }

    fn empty_world() -> WorldState {
        WorldState::new(WorldConfig {
            seed: 7,
            team_count: 1,
            initial_person_count: 0,
            recent_capacity_per_team: 8,
            recent_target_percent: 50,
            property_bytes: 32,
        })
        .expect("valid world")
    }

    #[test]
    fn versions_survive_phases_and_full_merge_matches_producer_versions() {
        let mut world = empty_world();
        world.create_person(0, 3).expect("first person");

        let update_one = world
            .resolve_person_upsert(at(10), ReplayMode::Fresh)
            .expect("first update");
        let update_two = world
            .resolve_person_upsert(at_in_phase(PhaseId::new(2), 0), ReplayMode::Fresh)
            .expect("next phase update");
        let version = |descriptor: &OpDescriptor| match &descriptor.payload {
            OpPayload::PersonUpsert(payload) => payload.version,
            _ => panic!("expected person upsert"),
        };
        assert!(version(&update_two) > version(&update_one));

        world.create_person(0, 2).expect("second person");
        let before = world
            .persons
            .iter()
            .enumerate()
            .filter(|(_, person)| person.live_index().is_some())
            .map(|(index, person)| {
                (
                    world.person_uuid(PersonKey(index as u32)),
                    person.version,
                    person.distinct_id_count,
                )
            })
            .collect::<Vec<_>>();
        let merge = world.resolve_full_merge(at(20)).expect("full merge");
        let payload = match merge.payload {
            OpPayload::FullMerge(payload) => payload,
            _ => panic!("expected full merge"),
        };

        let (_, source_version, source_fanout) = before
            .iter()
            .find(|(uuid, _, _)| *uuid == payload.source_person_uuid)
            .expect("source existed");
        let (_, target_version, _) = before
            .iter()
            .find(|(uuid, _, _)| *uuid == payload.target_person_uuid)
            .expect("target existed");
        assert_eq!(payload.distinct_id_moves.len(), *source_fanout as usize);
        assert_eq!(
            payload.target_version,
            (*source_version).max(*target_version) + 1
        );
        assert_eq!(payload.source_tombstone_version, source_version + 100);
        assert_eq!(world.live_person_count(), 1);

        let source_key = before
            .iter()
            .position(|(uuid, _, _)| *uuid == payload.source_person_uuid)
            .map(|index| PersonKey(index as u32))
            .expect("source key");
        let target_key = before
            .iter()
            .position(|(uuid, _, _)| *uuid == payload.target_person_uuid)
            .map(|index| PersonKey(index as u32))
            .expect("target key");
        assert_eq!(
            world.person(source_key).version,
            payload.source_tombstone_version
        );
        assert_eq!(world.person(target_key).version, payload.target_version);
        assert!(world.person(source_key).live_index().is_none());
        assert_eq!(world.person(source_key).distinct_id_count, 0);

        let population = world.population();
        for moved in &payload.distinct_id_moves {
            let mapping = population
                .distinct_ids()
                .find(|mapping| mapping.distinct_id == moved.distinct_id)
                .expect("moved mapping");
            assert_eq!(mapping.person_uuid, payload.target_person_uuid);
        }
    }

    #[test]
    fn read_misses_and_fanout_edges_are_explicit() {
        assert_eq!(fanout_for_roll(0, 0), 1);
        assert_eq!(fanout_for_roll(94_999, u64::MAX), 1);
        assert_eq!(fanout_for_roll(95_000, 0), 2);
        assert_eq!(fanout_for_roll(99_989, u64::MAX), 2);
        assert_eq!(fanout_for_roll(99_990, 0), 3);
        assert_eq!(fanout_for_roll(99_998, 97), 100);
        assert_eq!(fanout_for_roll(99_999, 0), 101);
        assert_eq!(fanout_for_roll(99_999, 899), 1_000);

        let mut world = empty_world();
        world.create_person(0, 101).expect("whale person");
        world.create_person(0, 1).expect("merge target");
        let miss = world
            .resolve_read(at(0), ReadMode::Miss)
            .expect("read miss");
        let miss_payload = match miss.payload {
            OpPayload::CanonicalRead(payload) => payload,
            _ => panic!("expected read"),
        };
        assert_eq!(miss_payload.expectation, ReadExpectation::Miss);
        assert!(world
            .population()
            .distinct_ids()
            .all(|mapping| mapping.distinct_id != miss_payload.distinct_id));

        let whale_merge = world.resolve_whale_merge(at(1)).expect("whale merge");
        let merge_payload = match whale_merge.payload {
            OpPayload::FullMerge(payload) => payload,
            _ => panic!("expected merge"),
        };
        assert_eq!(merge_payload.shape, MergeShape::Whale);
        assert_eq!(merge_payload.distinct_id_moves.len(), 101);
    }

    #[test]
    fn forty_five_million_person_estimate_stays_below_five_gibibytes() {
        let config = WorldConfig {
            initial_person_count: 45_000_000,
            ..WorldConfig::default()
        };
        let estimate = WorldState::estimate_initial_memory(&config).expect("memory estimate");

        assert_eq!(estimate.person_slot_bytes, 32);
        assert_eq!(estimate.distinct_id_slot_bytes, 16);
        assert_eq!(size_of::<PersonKey>(), 4);
        assert_eq!(estimate.expected_distinct_id_count, 47_697_300);
        assert!(estimate.total_bytes < 5 * 1024 * 1024 * 1024);
    }

    #[test]
    fn memory_estimate_accounts_for_growth_and_creation_primary_ids() {
        let config = WorldConfig::default();
        let initial = WorldState::estimate_initial_memory(&config).expect("initial estimate");
        assert_eq!(
            initial,
            WorldState::estimate_memory(&config, WorldGrowth::default())
                .expect("zero-growth estimate")
        );

        let growth = WorldGrowth::new(
            PersonCreationCount::new(1_000),
            DistinctIdAssignmentCount::new(2_000),
        );
        let grown = WorldState::estimate_memory(&config, growth).expect("growth estimate");

        assert_eq!(grown.person_count, initial.person_count + 1_000);
        assert_eq!(
            initial.recent_index_bytes,
            config.team_count as u64
                * config.recent_capacity_per_team as u64
                * size_of::<PersonKey>() as u64
        );
        assert_eq!(
            grown.expected_distinct_id_count,
            initial.expected_distinct_id_count + 3_000
        );
        assert!(grown.total_bytes >= initial.total_bytes);
        assert!(
            initial.headroom_bytes(grown.total_bytes).expect("headroom")
                >= grown.headroom_bytes(grown.total_bytes).expect("exact fit")
        );
        assert!(grown.headroom_bytes(grown.total_bytes - 1).is_none());
    }

    #[test]
    fn person_growth_is_reserved_before_the_workload() {
        let mut world = WorldState::new(WorldConfig {
            team_count: 4,
            initial_person_count: 100,
            ..WorldConfig::default()
        })
        .expect("world");
        world
            .reserve_person_growth(PersonCreationCount::new(50))
            .expect("growth reservation");

        let reserved_slots = world
            .teams
            .iter()
            .map(|team| team.live_persons.capacity() - team.live_persons.len())
            .sum::<usize>();
        assert!(reserved_slots >= 50);
        assert!(world.growth_reservation_enabled);
    }

    #[test]
    fn distinct_id_selection_rotates_the_intrusive_list() {
        let mut world = empty_world();
        let person = world.create_person(0, 3).expect("person");
        let first = world
            .person(person)
            .first_distinct_id()
            .expect("first distinct ID");
        let second = world.distinct_id(first).next().expect("second distinct ID");
        let third = world.distinct_id(second).next().expect("third distinct ID");

        let selected = (0..4)
            .map(|_| {
                world
                    .select_distinct_id(person)
                    .expect("selected distinct ID")
            })
            .collect::<Vec<_>>();

        assert_eq!(selected, vec![first, second, third, first]);
        assert_eq!(world.person(person).first_distinct_id(), Some(second));
        assert_eq!(world.person(person).last_distinct_id(), Some(first));
    }

    #[test]
    fn person_creation_preflights_distinct_id_capacity() {
        let mut world = empty_world();
        let person_count = world.persons.len();
        let live_count = world.teams[0].live_persons.len();
        let recent_count = world.teams[0].recent.len();
        world.distinct_ids.len = u32::MAX;

        assert_eq!(
            world.create_person(0, 1),
            Err(WorldError::ArenaExhausted("distinct ID"))
        );
        assert_eq!(world.persons.len(), person_count);
        assert_eq!(world.teams[0].live_persons.len(), live_count);
        assert_eq!(world.teams[0].recent.len(), recent_count);
    }

    #[test]
    fn pending_creation_is_invisible_until_both_writes_activate_it() {
        let mut world = empty_world();
        let creation = world.resolve_creation(at(0)).expect("pending creation");
        let distinct_id = match &creation.distinct_id_assignment.payload {
            OpPayload::DistinctIdAssignment(payload) => payload.distinct_id.clone(),
            _ => panic!("expected distinct ID assignment"),
        };

        assert_eq!(world.live_person_count(), 0);
        assert_eq!(world.population().persons().count(), 0);
        assert_eq!(world.population().distinct_ids().count(), 0);
        assert_eq!(
            world.resolve_read(at(1), ReadMode::Hit),
            Err(WorldError::NoEligiblePerson)
        );

        world
            .activate_creation(creation.activation)
            .expect("both writes completed");
        let read = world.resolve_read(at(2), ReadMode::Hit).expect("live read");
        let read_distinct_id = match read.payload {
            OpPayload::CanonicalRead(payload) => payload.distinct_id,
            _ => panic!("expected canonical read"),
        };
        assert_eq!(read_distinct_id, distinct_id);
        assert_eq!(world.live_person_count(), 1);
        assert_eq!(
            world.activate_creation(creation.activation),
            Err(WorldError::InvalidPendingActivation)
        );
    }

    #[test]
    fn new_distinct_id_is_invisible_until_its_write_activates_it() {
        let mut world = empty_world();
        world.create_person(0, 1).expect("live person");
        let assignment = world
            .resolve_distinct_id_assignment(at(0), AssignmentMode::New)
            .expect("pending assignment");
        let pending_distinct_id = match &assignment.operation.payload {
            OpPayload::DistinctIdAssignment(payload) => payload.distinct_id.clone(),
            _ => panic!("expected distinct ID assignment"),
        };

        assert_eq!(world.population().distinct_ids().count(), 1);
        let before = world
            .resolve_read(at(1), ReadMode::Hit)
            .expect("existing read");
        assert_ne!(
            match before.payload {
                OpPayload::CanonicalRead(payload) => payload.distinct_id,
                _ => panic!("expected canonical read"),
            },
            pending_distinct_id
        );

        world
            .activate_distinct_id(assignment.activation.expect("new assignment token"))
            .expect("assignment completed");
        assert_eq!(world.population().distinct_ids().count(), 2);
        let reads = (0..2)
            .map(|offset| {
                let read = world
                    .resolve_read(at(2 + offset), ReadMode::Hit)
                    .expect("live read");
                match read.payload {
                    OpPayload::CanonicalRead(payload) => payload.distinct_id,
                    _ => panic!("expected canonical read"),
                }
            })
            .collect::<Vec<_>>();
        assert!(reads.contains(&pending_distinct_id));
    }

    #[test]
    fn fresh_existing_assignment_reuses_a_slot_and_advances_its_version() {
        let mut world = empty_world();
        world.create_person(0, 1).expect("live person");
        let before = world
            .population()
            .distinct_ids()
            .next()
            .expect("existing distinct ID");

        let assignment = world
            .resolve_distinct_id_assignment(at(0), AssignmentMode::FreshExisting)
            .expect("fresh existing assignment");
        let payload = match assignment.operation.payload {
            OpPayload::DistinctIdAssignment(payload) => payload,
            _ => panic!("expected distinct ID assignment"),
        };

        assert!(assignment.activation.is_none());
        assert_eq!(world.distinct_id_count(), 1);
        assert_eq!(payload.distinct_id, before.distinct_id);
        assert_eq!(payload.version, before.version + 1);
    }

    #[test]
    fn merge_does_not_remove_the_owner_of_a_pending_distinct_id() {
        let mut world = empty_world();
        world.create_person(0, 1).expect("first live person");
        world.create_person(0, 1).expect("second live person");
        let assignment = world
            .resolve_distinct_id_assignment(at(0), AssignmentMode::New)
            .expect("pending assignment");
        let (pending_owner, pending_distinct_id) = match &assignment.operation.payload {
            OpPayload::DistinctIdAssignment(payload) => {
                (payload.person_uuid, payload.distinct_id.clone())
            }
            _ => panic!("expected distinct ID assignment"),
        };

        let merge = world.resolve_full_merge(at(1)).expect("merge");
        let merge = match merge.payload {
            OpPayload::FullMerge(payload) => payload,
            _ => panic!("expected merge"),
        };
        assert_ne!(merge.source_person_uuid, pending_owner);
        assert_eq!(merge.target_person_uuid, pending_owner);

        world
            .activate_distinct_id(assignment.activation.expect("pending assignment token"))
            .expect("assignment completed");
        let mapping = world
            .population()
            .distinct_ids()
            .find(|mapping| mapping.distinct_id == pending_distinct_id)
            .expect("activated mapping");
        assert_eq!(mapping.person_uuid, pending_owner);
    }

    #[test]
    fn chunk_growth_keeps_existing_allocations_stable() {
        let mut arena = ChunkedArena::new();
        arena.push(0u32).expect("first item");
        let first_address: *const u32 = arena.get(0);
        for value in 1..=ARENA_CHUNK_CAPACITY as u32 {
            arena.push(value).expect("arena item");
        }

        assert_eq!(arena.chunk_count(), 2);
        let current_first_address: *const u32 = arena.get(0);
        assert_eq!(first_address, current_first_address);
        assert_eq!(
            *arena.get(ARENA_CHUNK_CAPACITY as u32),
            ARENA_CHUNK_CAPACITY as u32
        );
    }
}