Skip to main content

object_log/
sequencer.rs

1//! The sequencing seam: offset assignment, the offset→location index, and
2//! retention. The engine owns storage + buffering; a `Sequencer` owns offsets.
3
4use crate::ObjectLogError;
5use serde::{Deserialize, Serialize};
6use std::collections::{HashMap, HashSet};
7use std::sync::Mutex;
8
9/// Opaque, engine-visible identifier for an independent offset stream (one dense,
10/// monotonic offset space). A Kafka broker maps `(topic, partition)` onto one of
11/// these; a WAL maps a shard. object-log treats it as an opaque key.
12#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
13pub struct PartitionKey(pub String);
14
15impl PartitionKey {
16    /// Borrow the key as a string slice.
17    pub fn as_str(&self) -> &str {
18        &self.0
19    }
20}
21
22/// Point-in-time durable bounds; grants no exclusivity or pinned history view.
23#[derive(Clone, Copy, Debug, PartialEq, Eq)]
24pub struct AuthoritativePartitionState {
25    /// Durable writer fence, or zero for genuinely unseen state.
26    pub epoch: u64,
27    /// First readable logical offset.
28    pub log_start: i64,
29    /// Next logical offset to assign.
30    pub next_offset: i64,
31}
32
33/// Where a batch's bytes live inside its object. **Authored by the engine** (it
34/// owns object layout); the sequencer stores it in the index and returns it from
35/// [`Sequencer::lookup`].
36#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
37pub struct BatchLocation {
38    /// Key of the object holding the batch.
39    pub object_id: String,
40    /// Byte offset of the batch within the object.
41    pub byte_start: u32,
42    /// Byte length of the batch.
43    pub byte_len: u32,
44}
45
46/// One batch presented to [`Sequencer::commit`]. The engine fills `partition`,
47/// `record_count`, and `location` (all engine-visible); `meta` is forwarded
48/// **uninterpreted** — only the sequencer reads it.
49pub struct CommitBatch<'a, M> {
50    /// The offset stream this batch belongs to.
51    pub partition: PartitionKey,
52    /// Number of records in the batch (offsets advance by this).
53    pub record_count: i32,
54    /// Where the batch lives in its (already-durable) object.
55    pub location: BatchLocation,
56    /// Sequencer-private metadata (e.g. idempotent-producer identity). Opaque to
57    /// the engine.
58    pub meta: &'a M,
59    /// Fence epoch the caller believes owns this partition. [`ManifestSequencer`](crate::ManifestSequencer)
60    /// rejects the batch when the stored index epoch differs. Other sequencers
61    /// ignore it.
62    pub epoch: u64,
63}
64
65/// Per-batch result of [`Sequencer::commit`].
66#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
67pub enum CommitOutcome {
68    /// A fresh, contiguous offset range was assigned starting at `base_offset`.
69    Assigned {
70        /// First offset assigned to the batch.
71        base_offset: i64,
72        /// Number of records committed.
73        record_count: i32,
74    },
75    /// A retried batch was recognized as already committed (idempotent no-op);
76    /// the original `base_offset` is returned.
77    Duplicate {
78        /// The originally assigned first offset.
79        base_offset: i64,
80    },
81    /// This batch was not indexed. Other batches in the same call may already
82    /// be durable. The caller must rewrite this batch in a new data object
83    /// rather than reuse the offsets it expected.
84    Rejected {
85        /// Why the conditional update did not land.
86        reason: String,
87    },
88}
89
90/// Opt-in conditional results; existing CommitOutcome encoding stays unchanged.
91#[derive(Clone, Debug, PartialEq, Eq)]
92pub enum ConditionalCommitOutcome {
93    /// An ordinary assigned/duplicate/rejected sequencing outcome.
94    Committed(CommitOutcome),
95    /// No entry for this batch was indexed; the original condition did not hold.
96    HeadRejected {
97        /// Original required next offset.
98        expected: i64,
99        /// Authoritative next offset that did not match.
100        current: i64,
101    },
102    /// Publication may be ambiguous. Never interpret this as a head rejection.
103    Unknown(ObjectLogError),
104}
105
106/// An index entry resolving an offset range to its bytes.
107#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
108pub struct IndexEntry {
109    /// Where the batch's bytes live.
110    pub location: BatchLocation,
111    /// First offset in the batch.
112    pub base_offset: i64,
113    /// Number of records in the batch.
114    pub record_count: i32,
115}
116
117/// The linearization point: assigns offsets to durably-stored batches and owns
118/// the offset→location index.
119///
120/// **Synchronous on purpose** — a lin-point is a critical section, not async I/O.
121/// The engine calls it from its flush worker (a dedicated thread / blocking
122/// task), so a blocking implementation (a `Mutex`, a SQL transaction) is fine.
123///
124/// Publication scope belongs to the implementation. [`InMemorySequencer`]
125/// validates and commits the whole slice under one lock. Durable manifest
126/// publication linearizes each partition independently, so an error can follow
127/// a durable earlier partition; callers must not infer global rollback.
128/// The engine presents each [`PartitionKey`] in arrival order and never splits
129/// one partition across concurrent `commit` calls.
130pub trait Sequencer: Send + Sync {
131    /// Sequencer-private per-batch metadata, forwarded uninterpreted by the
132    /// engine. object-log's default sequencers use `()`; a Kafka coordinator uses
133    /// its producer-identity fields.
134    type Meta: Send + Sync;
135
136    /// Opt in to atomic commits containing already-durable batches from several
137    /// data objects, in creation order. Default preserves one-object calls for
138    /// custom sequencers that rely on that boundary.
139    fn supports_multi_object_commit(&self) -> bool {
140        false
141    }
142
143    /// Assign offsets to durably uploaded batches and persist the index.
144    /// By default these belong to one object; an opted-in implementation may
145    /// receive several objects in one ordered call.
146    /// Returns one [`CommitOutcome`] per input batch, in order.
147    ///
148    /// An `Err` may follow indexed earlier partitions; unacknowledged publication
149    /// remains ambiguous. A [`CommitOutcome::Rejected`] batch was not indexed,
150    /// while other batches in the same call may already be durable.
151    fn commit(
152        &self,
153        batches: &[CommitBatch<'_, Self::Meta>],
154    ) -> Result<Vec<CommitOutcome>, ObjectLogError>;
155
156    /// Whether this sequencer implements native durable head conditions.
157    fn supports_conditional_commit(&self) -> bool {
158        false
159    }
160
161    /// Opt-in head compare-and-append. Conditions are next log offsets, not
162    /// record insertion counters or sparse hints. Partition publication remains
163    /// independent; this is not a cross-partition transaction. The default
164    /// rejects any condition before calling the legacy commit implementation.
165    fn commit_conditionally(
166        &self,
167        batches: &[CommitBatch<'_, Self::Meta>],
168        expected_heads: &[Option<i64>],
169    ) -> Result<Vec<ConditionalCommitOutcome>, ObjectLogError> {
170        if batches.len() != expected_heads.len()
171            || expected_heads.iter().flatten().any(|head| *head < 0)
172        {
173            return Err(ObjectLogError::InvalidBatch(
174                "invalid head conditions".into(),
175            ));
176        }
177        if expected_heads.iter().any(Option::is_some) {
178            return Err(ObjectLogError::InvalidConfig(
179                "conditional commit unsupported".into(),
180            ));
181        }
182        self.commit(batches).map(|outcomes| {
183            outcomes
184                .into_iter()
185                .map(ConditionalCommitOutcome::Committed)
186                .collect()
187        })
188    }
189
190    /// Resolve `fetch_offset` to the ordered index entries covering it onward.
191    fn lookup(
192        &self,
193        partition: &PartitionKey,
194        fetch_offset: i64,
195    ) -> Result<Vec<IndexEntry>, ObjectLogError>;
196
197    /// The next offset to be assigned (index-only; no object reads).
198    fn high_watermark(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError>;
199
200    /// The first readable offset (advances on [`truncate_before`](Sequencer::truncate_before)).
201    fn log_start_offset(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError>;
202
203    /// Retention MECHANISM (not policy): drop index entries below `offset` and
204    /// return object ids that now have **no** live references from **any**
205    /// partition (objects are multiplexed and shared), for the engine to delete.
206    fn truncate_before(
207        &self,
208        partition: &PartitionKey,
209        offset: i64,
210    ) -> Result<Vec<String>, ObjectLogError>;
211
212    /// Move the stored fence epoch for `partition` from `expected` to `new_epoch`.
213    ///
214    /// The default succeeds without storing anything. [`ManifestSequencer`](crate::ManifestSequencer)
215    /// reads that partition's durable index, fails when its epoch is neither
216    /// `expected` nor `new_epoch`, and otherwise stores `new_epoch`, creating the
217    /// index when it is missing. Once this returns, a writer that has not seen
218    /// the new epoch cannot commit to the partition.
219    fn fence_epoch(
220        &self,
221        partition: &PartitionKey,
222        expected: u64,
223        new_epoch: u64,
224    ) -> Result<(), ObjectLogError> {
225        let _ = (partition, expected, new_epoch);
226        Ok(())
227    }
228
229    /// The fence epoch this handle last read for `partition`, if it tracks one.
230    ///
231    /// The default returns `None`.
232    #[deprecated(
233        since = "0.3.6",
234        note = "the engine no longer reads fence epochs; implement `rejection_error` instead"
235    )]
236    fn partition_epoch(&self, partition: &PartitionKey) -> Option<u64> {
237        let _ = partition;
238        None
239    }
240
241    /// The error the engine reports for a batch this sequencer answered with
242    /// [`CommitOutcome::Rejected`]. `epoch` is the fence epoch the batch was
243    /// produced at.
244    ///
245    /// Classifying a rejection is the sequencer's policy; the engine only
246    /// forwards the result. The default reports
247    /// [`ObjectLogError::Sequencer`] with the rejection reason.
248    fn rejection_error(
249        &self,
250        partition: &PartitionKey,
251        epoch: u64,
252        reason: String,
253    ) -> ObjectLogError {
254        let _ = (partition, epoch);
255        ObjectLogError::Sequencer(reason)
256    }
257
258    /// Acquire a fresh durable writer epoch and the matching bounds from this
259    /// call's successful CAS. This grants no ongoing writer exclusivity.
260    /// An error may follow a durable epoch advance; never infer no effect.
261    /// Unsupported implementations fail without legacy fence fallback.
262    fn acquire_authoritative_epoch(
263        &self,
264        partition: &PartitionKey,
265    ) -> Result<AuthoritativePartitionState, ObjectLogError> {
266        let _ = partition;
267        Err(ObjectLogError::InvalidConfig(
268            "native epoch acquisition is unsupported".into(),
269        ))
270    }
271
272    /// Read validated durable state directly; unsupported implementations fail
273    /// without invoking legacy refresh or cached getters.
274    fn authoritative_partition_state(
275        &self,
276        partition: &PartitionKey,
277    ) -> Result<AuthoritativePartitionState, ObjectLogError> {
278        let _ = partition;
279        Err(ObjectLogError::InvalidConfig(
280            "native authoritative partition state is unsupported".into(),
281        ))
282    }
283
284    /// Reload `partition`'s index from durable storage, so this handle sees
285    /// commits made by other writers since it opened.
286    ///
287    /// The default does nothing: a sequencer with a single writer is already
288    /// current.
289    fn refresh_partition(&self, partition: &PartitionKey) -> Result<(), ObjectLogError> {
290        let _ = partition;
291        Ok(())
292    }
293}
294
295/// Per-partition in-memory index state.
296#[derive(Default)]
297struct PartState {
298    next_offset: i64,
299    log_start: i64,
300    entries: Vec<IndexEntry>,
301}
302
303/// A single-node, in-memory [`Sequencer`] (`Meta = ()`): assigns dense offsets and
304/// keeps the offset→location index in memory.
305///
306/// The log *bytes* live durably in the `BlobStore`, but this index does not
307/// survive a restart — use it for tests and single-process work, or persist the
308/// index yourself for a crash-durable standalone log.
309#[derive(Default)]
310pub struct InMemorySequencer {
311    state: Mutex<HashMap<PartitionKey, PartState>>,
312}
313
314impl InMemorySequencer {
315    /// Create an empty sequencer.
316    pub fn new() -> Self {
317        Self::default()
318    }
319
320    /// Object ids referenced by any live index entry (for orphan reaping).
321    pub fn live_object_ids(&self) -> HashSet<String> {
322        let state = self.state.lock().expect("poisoned");
323        let mut live = HashSet::new();
324        for ps in state.values() {
325            for e in &ps.entries {
326                live.insert(e.location.object_id.clone());
327            }
328        }
329        live
330    }
331}
332
333impl Sequencer for InMemorySequencer {
334    type Meta = ();
335
336    fn supports_multi_object_commit(&self) -> bool {
337        true
338    }
339
340    fn commit(
341        &self,
342        batches: &[CommitBatch<'_, Self::Meta>],
343    ) -> Result<Vec<CommitOutcome>, ObjectLogError> {
344        let mut state = self.state.lock().expect("poisoned");
345        // Validate the entire input before changing any partition.
346        let mut nexts: HashMap<&PartitionKey, i64> = HashMap::new();
347        for batch in batches {
348            let next = nexts.entry(&batch.partition).or_insert_with(|| {
349                state
350                    .get(&batch.partition)
351                    .map_or(0, |part| part.next_offset)
352            });
353            if batch.record_count <= 0 || batch.location.object_id.is_empty() {
354                return Err(ObjectLogError::InvalidBatch("invalid index batch".into()));
355            }
356            *next = next
357                .checked_add(i64::from(batch.record_count))
358                .ok_or_else(|| ObjectLogError::Sequencer("index offset overflow".into()))?;
359        }
360        let mut outcomes = Vec::with_capacity(batches.len());
361        for cb in batches {
362            let ps = state.entry(cb.partition.clone()).or_default();
363            let base = ps.next_offset;
364            ps.entries.push(IndexEntry {
365                location: cb.location.clone(),
366                base_offset: base,
367                record_count: cb.record_count,
368            });
369            ps.next_offset = base + cb.record_count as i64;
370            outcomes.push(CommitOutcome::Assigned {
371                base_offset: base,
372                record_count: cb.record_count,
373            });
374        }
375        Ok(outcomes)
376    }
377
378    fn lookup(
379        &self,
380        partition: &PartitionKey,
381        fetch_offset: i64,
382    ) -> Result<Vec<IndexEntry>, ObjectLogError> {
383        let state = self.state.lock().expect("poisoned");
384        let Some(ps) = state.get(partition) else {
385            return Ok(Vec::new());
386        };
387        Ok(ps
388            .entries
389            .iter()
390            .filter(|e| e.base_offset + e.record_count as i64 > fetch_offset)
391            .cloned()
392            .collect())
393    }
394
395    fn high_watermark(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError> {
396        Ok(self
397            .state
398            .lock()
399            .expect("poisoned")
400            .get(partition)
401            .map_or(0, |ps| ps.next_offset))
402    }
403
404    fn log_start_offset(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError> {
405        Ok(self
406            .state
407            .lock()
408            .expect("poisoned")
409            .get(partition)
410            .map_or(0, |ps| ps.log_start))
411    }
412
413    fn truncate_before(
414        &self,
415        partition: &PartitionKey,
416        offset: i64,
417    ) -> Result<Vec<String>, ObjectLogError> {
418        let mut state = self.state.lock().expect("poisoned");
419        let mut dropped: Vec<String> = Vec::new();
420        match state.get_mut(partition) {
421            Some(ps) => {
422                for e in ps.entries.iter() {
423                    if e.base_offset + e.record_count as i64 <= offset {
424                        dropped.push(e.location.object_id.clone());
425                    }
426                }
427                ps.entries
428                    .retain(|e| e.base_offset + e.record_count as i64 > offset);
429                if offset > ps.log_start {
430                    ps.log_start = offset.min(ps.next_offset);
431                }
432            }
433            None => return Ok(Vec::new()),
434        }
435        // An object is reclaimable only when no entry in ANY partition references it.
436        let mut live: HashSet<String> = HashSet::new();
437        for ps in state.values() {
438            for e in &ps.entries {
439                live.insert(e.location.object_id.clone());
440            }
441        }
442        let mut dead: Vec<String> = Vec::new();
443        let mut seen: HashSet<String> = HashSet::new();
444        for oid in dropped {
445            if !live.contains(&oid) && seen.insert(oid.clone()) {
446                dead.push(oid);
447            }
448        }
449        Ok(dead)
450    }
451}
452
453impl crate::BoundedSequencer for InMemorySequencer {
454    fn lookup_page(
455        &self,
456        partition: &PartitionKey,
457        offset: i64,
458        max_entries: usize,
459        max_bytes: usize,
460    ) -> Result<Vec<IndexEntry>, ObjectLogError> {
461        let state = self.state.lock().expect("poisoned");
462        if offset < state.get(partition).map_or(0, |part| part.log_start) {
463            return Err(ObjectLogError::RangeOutOfBounds(
464                "lookup precedes retained history".into(),
465            ));
466        }
467        let entries = state
468            .get(partition)
469            .map_or(&[][..], |part| part.entries.as_slice());
470        crate::bounded_lookup::page(entries, offset, max_entries, max_bytes)
471    }
472}