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/// Where a batch's bytes live inside its object. **Authored by the engine** (it
23/// owns object layout); the sequencer stores it in the index and returns it from
24/// [`Sequencer::lookup`].
25#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
26pub struct BatchLocation {
27    /// Key of the object holding the batch.
28    pub object_id: String,
29    /// Byte offset of the batch within the object.
30    pub byte_start: u32,
31    /// Byte length of the batch.
32    pub byte_len: u32,
33}
34
35/// One batch presented to [`Sequencer::commit`]. The engine fills `partition`,
36/// `record_count`, and `location` (all engine-visible); `meta` is forwarded
37/// **uninterpreted** — only the sequencer reads it.
38pub struct CommitBatch<'a, M> {
39    /// The offset stream this batch belongs to.
40    pub partition: PartitionKey,
41    /// Number of records in the batch (offsets advance by this).
42    pub record_count: i32,
43    /// Where the batch lives in its (already-durable) object.
44    pub location: BatchLocation,
45    /// Sequencer-private metadata (e.g. idempotent-producer identity). Opaque to
46    /// the engine.
47    pub meta: &'a M,
48    /// Fence epoch the caller believes owns this partition. [`ManifestSequencer`](crate::ManifestSequencer)
49    /// rejects the batch when the stored index epoch differs. Other sequencers
50    /// ignore it.
51    pub epoch: u64,
52}
53
54/// Per-batch result of [`Sequencer::commit`].
55#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
56pub enum CommitOutcome {
57    /// A fresh, contiguous offset range was assigned starting at `base_offset`.
58    Assigned {
59        /// First offset assigned to the batch.
60        base_offset: i64,
61        /// Number of records committed.
62        record_count: i32,
63    },
64    /// A retried batch was recognized as already committed (idempotent no-op);
65    /// the original `base_offset` is returned.
66    Duplicate {
67        /// The originally assigned first offset.
68        base_offset: i64,
69    },
70    /// This batch was not indexed. Other batches in the same call may already
71    /// be durable. The caller must rewrite this batch in a new data object
72    /// rather than reuse the offsets it expected.
73    Rejected {
74        /// Why the conditional update did not land.
75        reason: String,
76    },
77}
78
79/// An index entry resolving an offset range to its bytes.
80#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
81pub struct IndexEntry {
82    /// Where the batch's bytes live.
83    pub location: BatchLocation,
84    /// First offset in the batch.
85    pub base_offset: i64,
86    /// Number of records in the batch.
87    pub record_count: i32,
88}
89
90/// The linearization point: assigns offsets to durably-stored batches and owns
91/// the offset→location index.
92///
93/// **Synchronous on purpose** — a lin-point is a critical section, not async I/O.
94/// The engine calls it from its flush worker (a dedicated thread / blocking
95/// task), so a blocking implementation (a `Mutex`, a SQL transaction) is fine.
96///
97/// Contract: [`commit`](Sequencer::commit) is **atomic across the whole slice**
98/// (all supplied batches commit together or not at all), and the engine
99/// presents batches for any single [`PartitionKey`] in arrival order and never
100/// splits one partition across concurrent `commit` calls.
101pub trait Sequencer: Send + Sync {
102    /// Sequencer-private per-batch metadata, forwarded uninterpreted by the
103    /// engine. object-log's default sequencers use `()`; a Kafka coordinator uses
104    /// its producer-identity fields.
105    type Meta: Send + Sync;
106
107    /// Opt in to atomic commits containing already-durable batches from several
108    /// data objects, in creation order. Default preserves one-object calls for
109    /// custom sequencers that rely on that boundary.
110    fn supports_multi_object_commit(&self) -> bool {
111        false
112    }
113
114    /// Assign offsets to durably uploaded batches and persist the index.
115    /// By default these belong to one object; an opted-in implementation may
116    /// receive several objects in one ordered call.
117    /// Returns one [`CommitOutcome`] per input batch, in order.
118    ///
119    /// On `Err`, nothing from this call was indexed. A [`CommitOutcome::Rejected`]
120    /// batch was not indexed either; earlier batches in the same call may already
121    /// be durable when the sequencer commits one partition at a time.
122    fn commit(
123        &self,
124        batches: &[CommitBatch<'_, Self::Meta>],
125    ) -> Result<Vec<CommitOutcome>, ObjectLogError>;
126
127    /// Resolve `fetch_offset` to the ordered index entries covering it onward.
128    fn lookup(
129        &self,
130        partition: &PartitionKey,
131        fetch_offset: i64,
132    ) -> Result<Vec<IndexEntry>, ObjectLogError>;
133
134    /// The next offset to be assigned (index-only; no object reads).
135    fn high_watermark(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError>;
136
137    /// The first readable offset (advances on [`truncate_before`](Sequencer::truncate_before)).
138    fn log_start_offset(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError>;
139
140    /// Retention MECHANISM (not policy): drop index entries below `offset` and
141    /// return object ids that now have **no** live references from **any**
142    /// partition (objects are multiplexed and shared), for the engine to delete.
143    fn truncate_before(
144        &self,
145        partition: &PartitionKey,
146        offset: i64,
147    ) -> Result<Vec<String>, ObjectLogError>;
148
149    /// Move the stored fence epoch for `partition` from `expected` to `new_epoch`.
150    ///
151    /// The default succeeds without storing anything. [`ManifestSequencer`](crate::ManifestSequencer)
152    /// reads that partition's durable index, fails when its epoch is neither
153    /// `expected` nor `new_epoch`, and otherwise stores `new_epoch`, creating the
154    /// index when it is missing. Once this returns, a writer that has not seen
155    /// the new epoch cannot commit to the partition.
156    fn fence_epoch(
157        &self,
158        partition: &PartitionKey,
159        expected: u64,
160        new_epoch: u64,
161    ) -> Result<(), ObjectLogError> {
162        let _ = (partition, expected, new_epoch);
163        Ok(())
164    }
165
166    /// The fence epoch this handle last read for `partition`, if it tracks one.
167    ///
168    /// After a [`CommitOutcome::Rejected`] batch the engine reports
169    /// [`ObjectLogError::Fenced`] when this epoch is past the batch's epoch. The
170    /// default returns `None`, which leaves rejections as sequencer errors.
171    fn partition_epoch(&self, partition: &PartitionKey) -> Option<u64> {
172        let _ = partition;
173        None
174    }
175
176    /// Reload `partition`'s index from durable storage, so this handle sees
177    /// commits made by other writers since it opened.
178    ///
179    /// The default does nothing: a sequencer with a single writer is already
180    /// current.
181    fn refresh_partition(&self, partition: &PartitionKey) -> Result<(), ObjectLogError> {
182        let _ = partition;
183        Ok(())
184    }
185}
186
187/// Per-partition in-memory index state.
188#[derive(Default)]
189struct PartState {
190    next_offset: i64,
191    log_start: i64,
192    entries: Vec<IndexEntry>,
193}
194
195/// A single-node, in-memory [`Sequencer`] (`Meta = ()`): assigns dense offsets and
196/// keeps the offset→location index in memory.
197///
198/// The log *bytes* live durably in the `BlobStore`, but this index does not
199/// survive a restart — use it for tests and single-process work, or persist the
200/// index yourself for a crash-durable standalone log.
201#[derive(Default)]
202pub struct InMemorySequencer {
203    state: Mutex<HashMap<PartitionKey, PartState>>,
204}
205
206impl InMemorySequencer {
207    /// Create an empty sequencer.
208    pub fn new() -> Self {
209        Self::default()
210    }
211
212    /// Object ids referenced by any live index entry (for orphan reaping).
213    pub fn live_object_ids(&self) -> HashSet<String> {
214        let state = self.state.lock().expect("poisoned");
215        let mut live = HashSet::new();
216        for ps in state.values() {
217            for e in &ps.entries {
218                live.insert(e.location.object_id.clone());
219            }
220        }
221        live
222    }
223}
224
225impl Sequencer for InMemorySequencer {
226    type Meta = ();
227
228    fn supports_multi_object_commit(&self) -> bool {
229        true
230    }
231
232    fn commit(
233        &self,
234        batches: &[CommitBatch<'_, Self::Meta>],
235    ) -> Result<Vec<CommitOutcome>, ObjectLogError> {
236        let mut state = self.state.lock().expect("poisoned");
237        let mut outcomes = Vec::with_capacity(batches.len());
238        for cb in batches {
239            let ps = state.entry(cb.partition.clone()).or_default();
240            let base = ps.next_offset;
241            ps.entries.push(IndexEntry {
242                location: cb.location.clone(),
243                base_offset: base,
244                record_count: cb.record_count,
245            });
246            ps.next_offset = base + cb.record_count as i64;
247            outcomes.push(CommitOutcome::Assigned {
248                base_offset: base,
249                record_count: cb.record_count,
250            });
251        }
252        Ok(outcomes)
253    }
254
255    fn lookup(
256        &self,
257        partition: &PartitionKey,
258        fetch_offset: i64,
259    ) -> Result<Vec<IndexEntry>, ObjectLogError> {
260        let state = self.state.lock().expect("poisoned");
261        let Some(ps) = state.get(partition) else {
262            return Ok(Vec::new());
263        };
264        Ok(ps
265            .entries
266            .iter()
267            .filter(|e| e.base_offset + e.record_count as i64 > fetch_offset)
268            .cloned()
269            .collect())
270    }
271
272    fn high_watermark(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError> {
273        Ok(self
274            .state
275            .lock()
276            .expect("poisoned")
277            .get(partition)
278            .map_or(0, |ps| ps.next_offset))
279    }
280
281    fn log_start_offset(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError> {
282        Ok(self
283            .state
284            .lock()
285            .expect("poisoned")
286            .get(partition)
287            .map_or(0, |ps| ps.log_start))
288    }
289
290    fn truncate_before(
291        &self,
292        partition: &PartitionKey,
293        offset: i64,
294    ) -> Result<Vec<String>, ObjectLogError> {
295        let mut state = self.state.lock().expect("poisoned");
296        let mut dropped: Vec<String> = Vec::new();
297        match state.get_mut(partition) {
298            Some(ps) => {
299                for e in ps.entries.iter() {
300                    if e.base_offset + e.record_count as i64 <= offset {
301                        dropped.push(e.location.object_id.clone());
302                    }
303                }
304                ps.entries
305                    .retain(|e| e.base_offset + e.record_count as i64 > offset);
306                if offset > ps.log_start {
307                    ps.log_start = offset.min(ps.next_offset);
308                }
309            }
310            None => return Ok(Vec::new()),
311        }
312        // An object is reclaimable only when no entry in ANY partition references it.
313        let mut live: HashSet<String> = HashSet::new();
314        for ps in state.values() {
315            for e in &ps.entries {
316                live.insert(e.location.object_id.clone());
317            }
318        }
319        let mut dead: Vec<String> = Vec::new();
320        let mut seen: HashSet<String> = HashSet::new();
321        for oid in dropped {
322            if !live.contains(&oid) && seen.insert(oid.clone()) {
323                dead.push(oid);
324            }
325        }
326        Ok(dead)
327    }
328}