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}
49
50/// Per-batch result of [`Sequencer::commit`].
51#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
52pub enum CommitOutcome {
53    /// A fresh, contiguous offset range was assigned starting at `base_offset`.
54    Assigned {
55        /// First offset assigned to the batch.
56        base_offset: i64,
57        /// Number of records committed.
58        record_count: i32,
59    },
60    /// A retried batch was recognized as already committed (idempotent no-op);
61    /// the original `base_offset` is returned.
62    Duplicate {
63        /// The originally assigned first offset.
64        base_offset: i64,
65    },
66}
67
68/// An index entry resolving an offset range to its bytes.
69#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
70pub struct IndexEntry {
71    /// Where the batch's bytes live.
72    pub location: BatchLocation,
73    /// First offset in the batch.
74    pub base_offset: i64,
75    /// Number of records in the batch.
76    pub record_count: i32,
77}
78
79/// The linearization point: assigns offsets to durably-stored batches and owns
80/// the offset→location index.
81///
82/// **Synchronous on purpose** — a lin-point is a critical section, not async I/O.
83/// The engine calls it from its flush worker (a dedicated thread / blocking
84/// task), so a blocking implementation (a `Mutex`, a SQL transaction) is fine.
85///
86/// Contract: [`commit`](Sequencer::commit) is **atomic across the whole slice**
87/// (all supplied batches commit together or not at all), and the engine
88/// presents batches for any single [`PartitionKey`] in arrival order and never
89/// splits one partition across concurrent `commit` calls.
90pub trait Sequencer: Send + Sync {
91    /// Sequencer-private per-batch metadata, forwarded uninterpreted by the
92    /// engine. object-log's default sequencers use `()`; a Kafka coordinator uses
93    /// its producer-identity fields.
94    type Meta: Send + Sync;
95
96    /// Opt in to atomic commits containing already-durable batches from several
97    /// data objects, in creation order. Default preserves one-object calls for
98    /// custom sequencers that rely on that boundary.
99    fn supports_multi_object_commit(&self) -> bool {
100        false
101    }
102
103    /// Assign offsets to durably uploaded batches and persist the index.
104    /// By default these belong to one object; an opted-in implementation may
105    /// receive several objects in one ordered call.
106    /// Returns one [`CommitOutcome`] per input batch, in order. Atomic: on `Err`,
107    /// nothing is committed.
108    fn commit(
109        &self,
110        batches: &[CommitBatch<'_, Self::Meta>],
111    ) -> Result<Vec<CommitOutcome>, ObjectLogError>;
112
113    /// Resolve `fetch_offset` to the ordered index entries covering it onward.
114    fn lookup(
115        &self,
116        partition: &PartitionKey,
117        fetch_offset: i64,
118    ) -> Result<Vec<IndexEntry>, ObjectLogError>;
119
120    /// The next offset to be assigned (index-only; no object reads).
121    fn high_watermark(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError>;
122
123    /// The first readable offset (advances on [`truncate_before`](Sequencer::truncate_before)).
124    fn log_start_offset(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError>;
125
126    /// Retention MECHANISM (not policy): drop index entries below `offset` and
127    /// return object ids that now have **no** live references from **any**
128    /// partition (objects are multiplexed and shared), for the engine to delete.
129    fn truncate_before(
130        &self,
131        partition: &PartitionKey,
132        offset: i64,
133    ) -> Result<Vec<String>, ObjectLogError>;
134}
135
136/// Per-partition in-memory index state.
137#[derive(Default)]
138struct PartState {
139    next_offset: i64,
140    log_start: i64,
141    entries: Vec<IndexEntry>,
142}
143
144/// A single-node, in-memory [`Sequencer`] (`Meta = ()`): assigns dense offsets and
145/// keeps the offset→location index in memory.
146///
147/// The log *bytes* live durably in the `BlobStore`, but this index does not
148/// survive a restart — use it for tests and single-process work, or persist the
149/// index yourself for a crash-durable standalone log.
150#[derive(Default)]
151pub struct InMemorySequencer {
152    state: Mutex<HashMap<PartitionKey, PartState>>,
153}
154
155impl InMemorySequencer {
156    /// Create an empty sequencer.
157    pub fn new() -> Self {
158        Self::default()
159    }
160
161    /// Object ids referenced by any live index entry (for orphan reaping).
162    pub fn live_object_ids(&self) -> HashSet<String> {
163        let state = self.state.lock().expect("poisoned");
164        let mut live = HashSet::new();
165        for ps in state.values() {
166            for e in &ps.entries {
167                live.insert(e.location.object_id.clone());
168            }
169        }
170        live
171    }
172}
173
174impl Sequencer for InMemorySequencer {
175    type Meta = ();
176
177    fn supports_multi_object_commit(&self) -> bool {
178        true
179    }
180
181    fn commit(
182        &self,
183        batches: &[CommitBatch<'_, Self::Meta>],
184    ) -> Result<Vec<CommitOutcome>, ObjectLogError> {
185        let mut state = self.state.lock().expect("poisoned");
186        let mut outcomes = Vec::with_capacity(batches.len());
187        for cb in batches {
188            let ps = state.entry(cb.partition.clone()).or_default();
189            let base = ps.next_offset;
190            ps.entries.push(IndexEntry {
191                location: cb.location.clone(),
192                base_offset: base,
193                record_count: cb.record_count,
194            });
195            ps.next_offset = base + cb.record_count as i64;
196            outcomes.push(CommitOutcome::Assigned {
197                base_offset: base,
198                record_count: cb.record_count,
199            });
200        }
201        Ok(outcomes)
202    }
203
204    fn lookup(
205        &self,
206        partition: &PartitionKey,
207        fetch_offset: i64,
208    ) -> Result<Vec<IndexEntry>, ObjectLogError> {
209        let state = self.state.lock().expect("poisoned");
210        let Some(ps) = state.get(partition) else {
211            return Ok(Vec::new());
212        };
213        Ok(ps
214            .entries
215            .iter()
216            .filter(|e| e.base_offset + e.record_count as i64 > fetch_offset)
217            .cloned()
218            .collect())
219    }
220
221    fn high_watermark(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError> {
222        Ok(self
223            .state
224            .lock()
225            .expect("poisoned")
226            .get(partition)
227            .map_or(0, |ps| ps.next_offset))
228    }
229
230    fn log_start_offset(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError> {
231        Ok(self
232            .state
233            .lock()
234            .expect("poisoned")
235            .get(partition)
236            .map_or(0, |ps| ps.log_start))
237    }
238
239    fn truncate_before(
240        &self,
241        partition: &PartitionKey,
242        offset: i64,
243    ) -> Result<Vec<String>, ObjectLogError> {
244        let mut state = self.state.lock().expect("poisoned");
245        let mut dropped: Vec<String> = Vec::new();
246        match state.get_mut(partition) {
247            Some(ps) => {
248                for e in ps.entries.iter() {
249                    if e.base_offset + e.record_count as i64 <= offset {
250                        dropped.push(e.location.object_id.clone());
251                    }
252                }
253                ps.entries
254                    .retain(|e| e.base_offset + e.record_count as i64 > offset);
255                if offset > ps.log_start {
256                    ps.log_start = offset.min(ps.next_offset);
257                }
258            }
259            None => return Ok(Vec::new()),
260        }
261        // An object is reclaimable only when no entry in ANY partition references it.
262        let mut live: HashSet<String> = HashSet::new();
263        for ps in state.values() {
264            for e in &ps.entries {
265                live.insert(e.location.object_id.clone());
266            }
267        }
268        let mut dead: Vec<String> = Vec::new();
269        let mut seen: HashSet<String> = HashSet::new();
270        for oid in dropped {
271            if !live.contains(&oid) && seen.insert(oid.clone()) {
272                dead.push(oid);
273            }
274        }
275        Ok(dead)
276    }
277}