: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
//! Typed keyspaces: the sole constructors of the state column families' keys.
//!
//! A [`Keyspace`] binds a key type to exactly one [`Cf`] and to whether that CF is partition-prefixed,
//! so a key cannot be encoded for the wrong column family and every new CF is forced to declare
//! whether a partition wipe reclaims it (the [`Cf::partitioned`] exhaustive match). The state CFs are
//! person-clustered: [`PersonPrefix`] is the 26-byte `(partition, team, person)` prefix under which a
//! person's rows sort contiguously, and [`BehavioralKey`] appends a 16-byte leaf-state key so one
//! person's leaf rows form one contiguous, prefix-scannable slice.
use uuid::Uuid;
use super::column_families::Cf;
use super::rocks::StoreError;
use crate::stage1::key::LeafStateKey;
/// `[partition_id u16][team_id u64][person_id 16]`. The person-clustered prefix.
pub const PERSON_PREFIX_LEN: usize = 2 + 8 + 16;
/// `[partition_id u16][team_id u64][person_id 16][leaf_state_key 16]`.
pub const BEHAVIORAL_KEY_LEN: usize = PERSON_PREFIX_LEN + 16;
/// The 26-byte person prefix: every state key for one person sorts under it, so a person's rows are
/// one contiguous slice reachable by a prefix scan or reclaimed by a single range delete.
#[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub struct PersonPrefix {
pub partition_id: u16,
pub team_id: u64,
pub person_id: Uuid,
}
impl PersonPrefix {
pub fn new(partition_id: u16, team_id: u64, person_id: Uuid) -> Self {
Self {
partition_id,
team_id,
person_id,
}
}
pub fn encode(&self) -> [u8; PERSON_PREFIX_LEN] {
let mut out = [0u8; PERSON_PREFIX_LEN];
out[0..2].copy_from_slice(&self.partition_id.to_be_bytes());
out[2..10].copy_from_slice(&self.team_id.to_be_bytes());
out[10..26].copy_from_slice(self.person_id.as_bytes());
out
}
pub fn decode(bytes: &[u8]) -> Result<Self, StoreError> {
check_len(bytes, PERSON_PREFIX_LEN, "person_prefix")?;
Ok(Self {
partition_id: u16::from_be_bytes(array2(&bytes[0..2])),
team_id: u64::from_be_bytes(array8(&bytes[2..10])),
person_id: Uuid::from_bytes(array16(&bytes[10..26])),
})
}
/// The behavioral state key for one of this person's leaves.
pub fn behavioral_key(&self, lsk: LeafStateKey) -> BehavioralKey {
BehavioralKey { prefix: *self, lsk }
}
/// This person's `cf_person_records` key — the 26-byte prefix itself, since there is exactly one
/// record per person.
pub fn record_key(&self) -> PersonRecordKey {
PersonRecordKey(*self)
}
/// The half-open byte range `[prefix, prefix-successor)` covering exactly this person's slice of a
/// person-clustered CF — the unit of prefix iteration and of a single `delete_range_cf`. For an
/// all-`0xFF` prefix (which has no shorter successor) the end is an all-`0xFF` sentinel one byte
/// longer than the longest key under the prefix, which exceeds every such key.
pub fn scan_range(&self) -> (Vec<u8>, Vec<u8>) {
let start = self.encode().to_vec();
let end = prefix_successor(&start).unwrap_or_else(|| vec![0xFFu8; BEHAVIORAL_KEY_LEN + 1]);
(start, end)
}
}
/// `cf_behavioral` key: one person's per-leaf state, keyed person-first so all of a person's leaves
/// sort contiguously under their [`PersonPrefix`].
#[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub struct BehavioralKey {
pub prefix: PersonPrefix,
pub lsk: LeafStateKey,
}
impl BehavioralKey {
pub fn new(partition_id: u16, team_id: u64, person_id: Uuid, lsk: LeafStateKey) -> Self {
Self {
prefix: PersonPrefix::new(partition_id, team_id, person_id),
lsk,
}
}
pub fn partition_id(&self) -> u16 {
self.prefix.partition_id
}
pub fn team_id(&self) -> u64 {
self.prefix.team_id
}
pub fn person_id(&self) -> Uuid {
self.prefix.person_id
}
pub fn lsk(&self) -> LeafStateKey {
self.lsk
}
pub fn encode(&self) -> [u8; BEHAVIORAL_KEY_LEN] {
let mut out = [0u8; BEHAVIORAL_KEY_LEN];
out[0..PERSON_PREFIX_LEN].copy_from_slice(&self.prefix.encode());
out[PERSON_PREFIX_LEN..].copy_from_slice(&self.lsk.0);
out
}
pub fn decode(bytes: &[u8]) -> Result<Self, StoreError> {
check_len(bytes, BEHAVIORAL_KEY_LEN, "behavioral")?;
Ok(Self {
prefix: PersonPrefix::decode(&bytes[0..PERSON_PREFIX_LEN])?,
lsk: LeafStateKey(array16(&bytes[PERSON_PREFIX_LEN..])),
})
}
}
/// `cf_person_records` key: exactly one record per person, so the key IS the 26-byte
/// [`PersonPrefix`] — no leaf suffix. Byte-identical to the prefix encoding, so it nests inside the
/// same partition range as the behavioral keys and a partition wipe reclaims it.
#[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub struct PersonRecordKey(pub PersonPrefix);
impl PersonRecordKey {
pub fn new(partition_id: u16, team_id: u64, person_id: Uuid) -> Self {
Self(PersonPrefix::new(partition_id, team_id, person_id))
}
pub fn encode(&self) -> [u8; PERSON_PREFIX_LEN] {
self.0.encode()
}
pub fn decode(bytes: &[u8]) -> Result<Self, StoreError> {
Ok(Self(PersonPrefix::decode(bytes)?))
}
}
/// `[partition_id u16][0xFE]` in `cf_person_records`: every image's `delete_partition` removes it
/// with its slice, and person-record reads are 26-byte point gets that never reach it.
#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
pub struct SliceCoverageKey(pub u16);
const SLICE_COVERAGE_KEY_LEN: usize = 3;
const SLICE_COVERAGE_KEY_SUFFIX: u8 = 0xFE;
impl SliceCoverageKey {
pub fn encode(&self) -> [u8; SLICE_COVERAGE_KEY_LEN] {
let [high, low] = self.0.to_be_bytes();
[high, low, SLICE_COVERAGE_KEY_SUFFIX]
}
pub fn decode(bytes: &[u8]) -> Result<Self, StoreError> {
check_len(bytes, SLICE_COVERAGE_KEY_LEN, "slice_coverage")?;
if bytes[2] != SLICE_COVERAGE_KEY_SUFFIX {
return Err(StoreError::UnknownKey {
kind: "slice_coverage",
});
}
Ok(Self(u16::from_be_bytes(array2(&bytes[0..2]))))
}
}
/// `cf_meta` key: a small set of ASCII-literal keys carrying store-wide guards (schema version). Not
/// partition-prefixed, so it is exempt from partition wipes.
#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
pub struct MetaKey(pub &'static [u8]);
/// `cf_meta[b"schema_version"]` → the store schema version as a big-endian `u32`.
pub const META_SCHEMA_VERSION: MetaKey = MetaKey(b"schema_version");
/// Present once the store records slice coverage. The value is empty.
pub const META_SLICE_COVERAGE: MetaKey = MetaKey(b"slice_coverage");
/// `cf_meta[b"pod_partitions"]` → the [`PartitionOwnership`](crate::partitions::PartitionOwnership)
/// the store was written under.
pub const META_POD_PARTITIONS: MetaKey = MetaKey(b"pod_partitions");
// `Meta::decode` assumes one key length.
const _: () = assert!(META_SLICE_COVERAGE.0.len() == META_SCHEMA_VERSION.0.len());
const _: () = assert!(META_POD_PARTITIONS.0.len() == META_SCHEMA_VERSION.0.len());
mod sealed {
/// Sealed so only this module's keyspaces implement [`super::Keyspace`]; downstream code cannot
/// bind a new key type to a CF without declaring its partitioning here.
pub trait Sealed {}
}
/// A typed keyspace: one key type bound to one column family and to whether that CF is partitioned.
///
/// The binding is what stops a key from being written to the wrong CF (the generic
/// `BatchBuilder::put::<K>` / `StagedBatch::put::<K>` route by `K::CF`) and what forces every CF to
/// declare, via [`Cf::partitioned`]'s exhaustive match, whether a partition wipe reclaims it.
pub trait Keyspace: sealed::Sealed {
/// The column family this keyspace's keys live in.
const CF: Cf;
/// Whether keys carry the partition prefix, so a partition wipe's range delete reclaims them.
const PARTITIONED: bool;
/// The typed key. `Copy + Send + 'static` so it can be encoded into an owned staged op.
type Key: Copy + Send + 'static;
fn encode(key: &Self::Key) -> Vec<u8>;
fn decode(bytes: &[u8]) -> Result<Self::Key, StoreError>;
}
/// The person-clustered behavioral-state keyspace.
pub struct Behavioral;
impl sealed::Sealed for Behavioral {}
impl Keyspace for Behavioral {
const CF: Cf = Cf::Behavioral;
const PARTITIONED: bool = true;
type Key = BehavioralKey;
fn encode(key: &BehavioralKey) -> Vec<u8> {
key.encode().to_vec()
}
fn decode(bytes: &[u8]) -> Result<BehavioralKey, StoreError> {
BehavioralKey::decode(bytes)
}
}
/// One coverage record per partition, in `cf_person_records`.
pub struct SliceCoverages;
impl sealed::Sealed for SliceCoverages {}
impl Keyspace for SliceCoverages {
const CF: Cf = Cf::PersonRecords;
const PARTITIONED: bool = true;
type Key = SliceCoverageKey;
fn encode(key: &SliceCoverageKey) -> Vec<u8> {
key.encode().to_vec()
}
fn decode(bytes: &[u8]) -> Result<SliceCoverageKey, StoreError> {
SliceCoverageKey::decode(bytes)
}
}
/// The per-person-record keyspace: one row per person under the 26-byte prefix. Partitioned, so a
/// partition wipe reclaims it via the shared partition range.
pub struct PersonRecords;
impl sealed::Sealed for PersonRecords {}
impl Keyspace for PersonRecords {
const CF: Cf = Cf::PersonRecords;
const PARTITIONED: bool = true;
type Key = PersonRecordKey;
fn encode(key: &PersonRecordKey) -> Vec<u8> {
key.encode().to_vec()
}
fn decode(bytes: &[u8]) -> Result<PersonRecordKey, StoreError> {
PersonRecordKey::decode(bytes)
}
}
/// The store-metadata keyspace. Not partitioned: its ASCII-literal keys are shorter than a partition
/// range's upper bound and would collide with an arbitrary partition's slice, so a partition wipe must
/// never range over it (e.g. `b"sc"` = `0x7363` sits inside partition `29539`'s range).
pub struct Meta;
impl sealed::Sealed for Meta {}
impl Keyspace for Meta {
const CF: Cf = Cf::Meta;
const PARTITIONED: bool = false;
type Key = MetaKey;
fn encode(key: &MetaKey) -> Vec<u8> {
key.0.to_vec()
}
fn decode(bytes: &[u8]) -> Result<MetaKey, StoreError> {
// `cf_meta` keys are a closed set of literals; match them rather than fabricate a `&'static`
// from runtime bytes. A wrong length is a length error; a right-length key that matches no
// literal is an unknown key — conflating the two would report "expected N bytes, got N".
if let Some(key) = [
META_SCHEMA_VERSION,
META_SLICE_COVERAGE,
META_POD_PARTITIONS,
]
.into_iter()
.find(|key| key.0 == bytes)
{
Ok(key)
} else if bytes.len() != META_SCHEMA_VERSION.0.len() {
Err(StoreError::KeyDecode {
kind: "meta",
expected: META_SCHEMA_VERSION.0.len(),
actual: bytes.len(),
})
} else {
Err(StoreError::UnknownKey { kind: "meta" })
}
}
}
/// The smallest byte string strictly greater than every extension of `prefix`: increment the last
/// byte below `0xFF`, dropping the trailing `0xFF` run. Returns `None` for an all-`0xFF` prefix, which
/// has no such bound — the caller supplies a length-based sentinel that exceeds every key.
fn prefix_successor(prefix: &[u8]) -> Option<Vec<u8>> {
let mut end = prefix.to_vec();
while let Some(last) = end.last_mut() {
if *last == 0xFF {
end.pop();
} else {
*last += 1;
return Some(end);
}
}
None
}
fn check_len(bytes: &[u8], expected: usize, kind: &'static str) -> Result<(), StoreError> {
if bytes.len() == expected {
Ok(())
} else {
Err(StoreError::KeyDecode {
kind,
expected,
actual: bytes.len(),
})
}
}
fn array2(s: &[u8]) -> [u8; 2] {
let mut a = [0u8; 2];
a.copy_from_slice(s);
a
}
fn array8(s: &[u8]) -> [u8; 8] {
let mut a = [0u8; 8];
a.copy_from_slice(s);
a
}
fn array16(s: &[u8]) -> [u8; 16] {
let mut a = [0u8; 16];
a.copy_from_slice(s);
a
}
#[cfg(test)]
mod tests {
use super::*;
use crate::store::keys::partition_range;
fn lsk(b: u8) -> LeafStateKey {
LeafStateKey([b; 16])
}
fn person(n: u128) -> Uuid {
Uuid::from_u128(n)
}
fn behavioral(partition_id: u16, team_id: u64, p: u128, l: u8) -> BehavioralKey {
BehavioralKey::new(partition_id, team_id, person(p), lsk(l))
}
#[test]
fn encoded_lengths_are_exact() {
assert_eq!(PERSON_PREFIX_LEN, 26);
assert_eq!(BEHAVIORAL_KEY_LEN, 42);
assert_eq!(
PersonPrefix::new(1, 2, person(3)).encode().len(),
PERSON_PREFIX_LEN,
);
assert_eq!(behavioral(1, 2, 3, 4).encode().len(), BEHAVIORAL_KEY_LEN);
}
#[test]
fn person_prefix_round_trips() {
let key = PersonPrefix::new(0xBEEF, 0x0123_4567_89AB_CDEF, person(0xDEAD_BEEF));
assert_eq!(PersonPrefix::decode(&key.encode()).unwrap(), key);
}
#[test]
fn behavioral_key_round_trips() {
let key = behavioral(0xBEEF, 0x0123_4567_89AB_CDEF, 0xDEAD_BEEF, 0x5A);
assert_eq!(BehavioralKey::decode(&key.encode()).unwrap(), key);
}
#[test]
fn behavioral_key_accessors_match_the_prefix() {
let key = behavioral(7, 42, 99, 0xAB);
assert_eq!(key.partition_id(), 7);
assert_eq!(key.team_id(), 42);
assert_eq!(key.person_id(), person(99));
assert_eq!(key.lsk(), lsk(0xAB));
}
#[test]
fn decode_rejects_wrong_length() {
let err = BehavioralKey::decode(&[0u8; 41]).unwrap_err();
assert!(
matches!(
err,
StoreError::KeyDecode {
kind: "behavioral",
expected: 42,
actual: 41,
}
),
"unexpected error: {err:?}",
);
}
#[test]
fn behavioral_keys_sort_person_first_then_leaf() {
// Person clustering: a person's leaves are contiguous; a different person sorts as a block.
assert!(behavioral(5, 7, 1, 0xFF).encode() < behavioral(5, 7, 2, 0x00).encode());
// Within one person, leaves sort by lsk.
assert!(behavioral(5, 7, 1, 0x01).encode() < behavioral(5, 7, 1, 0x02).encode());
// Partition then team still dominate.
assert!(
behavioral(1, u64::MAX, u128::MAX, 0xFF).encode() < behavioral(2, 0, 0, 0x00).encode()
);
assert!(behavioral(5, 1, 0, 0x00).encode() < behavioral(5, 2, 0, 0x00).encode());
}
#[test]
fn scan_range_brackets_exactly_one_persons_leaves() {
let prefix = PersonPrefix::new(5, 7, person(42));
let (start, end) = prefix.scan_range();
let min_leaf = prefix.behavioral_key(lsk(0x00)).encode();
let max_leaf = prefix.behavioral_key(lsk(0xFF)).encode();
assert!(start.as_slice() <= min_leaf.as_slice());
assert!(max_leaf.as_slice() < end.as_slice());
// A neighbouring person's minimum leaf is at or past the end (never inside this person's range).
let next_person = PersonPrefix::new(5, 7, person(43))
.behavioral_key(lsk(0x00))
.encode();
assert!(end.as_slice() <= next_person.as_slice());
// The previous person's maximum leaf is strictly below the start.
let prev_person = PersonPrefix::new(5, 7, person(41))
.behavioral_key(lsk(0xFF))
.encode();
assert!(prev_person.as_slice() < start.as_slice());
}
#[test]
fn scan_range_handles_a_trailing_0xff_in_the_person_id() {
// The middle `prefix_successor` case, hit by neither existing test: a trailing `0xFF` run is
// popped and then a non-`0xFF` byte is incremented, yielding a *shortened* successor.
// person(0xFF)'s 26-byte prefix ends `..0x00 0xFF` while the partition/team are not maxed, so
// it takes neither the no-pop path (person(42)) nor the all-ones sentinel path. A bug in the
// popping loop would mis-bracket exactly the persons whose UUID ends in `0xFF`.
let prefix = PersonPrefix::new(5, 7, person(0xFF));
let (start, end) = prefix.scan_range();
let min_leaf = prefix.behavioral_key(lsk(0x00)).encode();
let max_leaf = prefix.behavioral_key(lsk(0xFF)).encode();
assert!(start.as_slice() <= min_leaf.as_slice());
assert!(max_leaf.as_slice() < end.as_slice());
// The next person (UUID rolls `..0x00 0xFF` -> `..0x01 0x00`) starts at or past the end.
let next_person = PersonPrefix::new(5, 7, person(0x100))
.behavioral_key(lsk(0x00))
.encode();
assert!(end.as_slice() <= next_person.as_slice());
// The previous person's maximum leaf is strictly below the start.
let prev_person = PersonPrefix::new(5, 7, person(0xFE))
.behavioral_key(lsk(0xFF))
.encode();
assert!(prev_person.as_slice() < start.as_slice());
}
#[test]
fn scan_range_handles_the_all_ones_prefix() {
let prefix = PersonPrefix::new(u16::MAX, u64::MAX, person(u128::MAX));
let (start, end) = prefix.scan_range();
let max_leaf = prefix.behavioral_key(lsk(0xFF)).encode();
assert!(start.as_slice() <= max_leaf.as_slice());
assert!(
max_leaf.as_slice() < end.as_slice(),
"sentinel exceeds the all-ones key"
);
}
#[test]
fn behavioral_keys_share_the_partition_prefix_so_delete_range_reclaims_them() {
// The person-prefix range nests inside the partition range, so a partition wipe still reclaims
// every behavioral key in the partition.
for p in [0u16, 5, 256, u16::MAX] {
let (start, end) = partition_range(p);
let max = behavioral(p, u64::MAX, u128::MAX, 0xFF).encode();
let min = behavioral(p, 0, 0, 0x00).encode();
assert!(start.as_slice() <= min.as_slice(), "start>min at p={p}");
assert!(max.as_slice() < end.as_slice(), "max>=end at p={p}");
}
}
#[test]
fn keyspace_consts_bind_key_types_to_the_right_cf() {
assert_eq!(Behavioral::CF, Cf::Behavioral);
assert_eq!(PersonRecords::CF, Cf::PersonRecords);
assert_eq!(Meta::CF, Cf::Meta);
// Each keyspace's PARTITIONED const must agree with its CF's `partitioned()` — the exhaustive
// match `delete_partition` relies on. A drift here would range-delete (or spare) the wrong CF.
assert_eq!(Behavioral::PARTITIONED, Cf::Behavioral.partitioned());
assert_eq!(PersonRecords::PARTITIONED, Cf::PersonRecords.partitioned());
assert_eq!(
SliceCoverages::PARTITIONED,
SliceCoverages::CF.partitioned()
);
assert_eq!(Meta::PARTITIONED, Cf::Meta.partitioned());
}
#[test]
fn person_record_key_is_byte_identical_to_the_person_prefix() {
let prefix = PersonPrefix::new(0xBEEF, 0x0123_4567_89AB_CDEF, person(0xDEAD_BEEF));
let key = prefix.record_key();
assert_eq!(key.0, prefix);
assert_eq!(
key.encode(),
prefix.encode(),
"record key encodes as the bare prefix"
);
assert_eq!(PersonRecordKey::decode(&key.encode()).unwrap(), key);
assert_eq!(
PersonRecordKey::new(0xBEEF, 0x0123_4567_89AB_CDEF, person(0xDEAD_BEEF)),
key,
);
}
#[test]
fn person_record_keyspace_encode_matches_the_key_encoder() {
let key = PersonRecordKey::new(3, 7, person(9));
assert_eq!(PersonRecords::encode(&key), key.encode().to_vec());
assert_eq!(
PersonRecords::decode(&PersonRecords::encode(&key)).unwrap(),
key
);
}
#[test]
fn person_record_keys_share_the_partition_prefix_so_delete_range_reclaims_them() {
// Same nesting property as the behavioral keys: a person-record key sits inside the partition
// range, so a partition wipe reclaims it too.
for p in [0u16, 5, 256, u16::MAX] {
let (start, end) = partition_range(p);
let max = PersonRecordKey::new(p, u64::MAX, person(u128::MAX)).encode();
let min = PersonRecordKey::new(p, 0, person(0)).encode();
assert!(start.as_slice() <= min.as_slice(), "start>min at p={p}");
assert!(max.as_slice() < end.as_slice(), "max>=end at p={p}");
}
}
#[test]
fn behavioral_keyspace_encode_matches_the_key_encoder() {
let key = behavioral(3, 7, 9, 0xAB);
assert_eq!(Behavioral::encode(&key), key.encode().to_vec());
assert_eq!(Behavioral::decode(&Behavioral::encode(&key)).unwrap(), key);
}
#[test]
fn meta_keyspace_round_trips_the_known_literal_and_rejects_others() {
assert_eq!(
Meta::encode(&META_SCHEMA_VERSION),
b"schema_version".to_vec()
);
assert_eq!(
Meta::decode(b"schema_version").unwrap(),
META_SCHEMA_VERSION,
);
assert_eq!(
Meta::decode(b"slice_coverage").unwrap(),
META_SLICE_COVERAGE,
);
// Wrong length reports the length; a right-length unknown key reports the content — a
// conflation would claim "expected 14 bytes, got 14" for the latter.
assert!(matches!(
Meta::decode(b"unknown").unwrap_err(),
StoreError::KeyDecode {
kind: "meta",
expected: 14,
actual: 7,
},
));
assert!(matches!(
Meta::decode(b"schema_versioX").unwrap_err(),
StoreError::UnknownKey { kind: "meta" },
));
}
}