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 /// The default returns `None`.
169 #[deprecated(
170 since = "0.3.6",
171 note = "the engine no longer reads fence epochs; implement `rejection_error` instead"
172 )]
173 fn partition_epoch(&self, partition: &PartitionKey) -> Option<u64> {
174 let _ = partition;
175 None
176 }
177
178 /// The error the engine reports for a batch this sequencer answered with
179 /// [`CommitOutcome::Rejected`]. `epoch` is the fence epoch the batch was
180 /// produced at.
181 ///
182 /// Classifying a rejection is the sequencer's policy; the engine only
183 /// forwards the result. The default reports
184 /// [`ObjectLogError::Sequencer`] with the rejection reason.
185 fn rejection_error(
186 &self,
187 partition: &PartitionKey,
188 epoch: u64,
189 reason: String,
190 ) -> ObjectLogError {
191 let _ = (partition, epoch);
192 ObjectLogError::Sequencer(reason)
193 }
194
195 /// Reload `partition`'s index from durable storage, so this handle sees
196 /// commits made by other writers since it opened.
197 ///
198 /// The default does nothing: a sequencer with a single writer is already
199 /// current.
200 fn refresh_partition(&self, partition: &PartitionKey) -> Result<(), ObjectLogError> {
201 let _ = partition;
202 Ok(())
203 }
204}
205
206/// Per-partition in-memory index state.
207#[derive(Default)]
208struct PartState {
209 next_offset: i64,
210 log_start: i64,
211 entries: Vec<IndexEntry>,
212}
213
214/// A single-node, in-memory [`Sequencer`] (`Meta = ()`): assigns dense offsets and
215/// keeps the offset→location index in memory.
216///
217/// The log *bytes* live durably in the `BlobStore`, but this index does not
218/// survive a restart — use it for tests and single-process work, or persist the
219/// index yourself for a crash-durable standalone log.
220#[derive(Default)]
221pub struct InMemorySequencer {
222 state: Mutex<HashMap<PartitionKey, PartState>>,
223}
224
225impl InMemorySequencer {
226 /// Create an empty sequencer.
227 pub fn new() -> Self {
228 Self::default()
229 }
230
231 /// Object ids referenced by any live index entry (for orphan reaping).
232 pub fn live_object_ids(&self) -> HashSet<String> {
233 let state = self.state.lock().expect("poisoned");
234 let mut live = HashSet::new();
235 for ps in state.values() {
236 for e in &ps.entries {
237 live.insert(e.location.object_id.clone());
238 }
239 }
240 live
241 }
242}
243
244impl Sequencer for InMemorySequencer {
245 type Meta = ();
246
247 fn supports_multi_object_commit(&self) -> bool {
248 true
249 }
250
251 fn commit(
252 &self,
253 batches: &[CommitBatch<'_, Self::Meta>],
254 ) -> Result<Vec<CommitOutcome>, ObjectLogError> {
255 let mut state = self.state.lock().expect("poisoned");
256 let mut outcomes = Vec::with_capacity(batches.len());
257 for cb in batches {
258 let ps = state.entry(cb.partition.clone()).or_default();
259 let base = ps.next_offset;
260 ps.entries.push(IndexEntry {
261 location: cb.location.clone(),
262 base_offset: base,
263 record_count: cb.record_count,
264 });
265 ps.next_offset = base + cb.record_count as i64;
266 outcomes.push(CommitOutcome::Assigned {
267 base_offset: base,
268 record_count: cb.record_count,
269 });
270 }
271 Ok(outcomes)
272 }
273
274 fn lookup(
275 &self,
276 partition: &PartitionKey,
277 fetch_offset: i64,
278 ) -> Result<Vec<IndexEntry>, ObjectLogError> {
279 let state = self.state.lock().expect("poisoned");
280 let Some(ps) = state.get(partition) else {
281 return Ok(Vec::new());
282 };
283 Ok(ps
284 .entries
285 .iter()
286 .filter(|e| e.base_offset + e.record_count as i64 > fetch_offset)
287 .cloned()
288 .collect())
289 }
290
291 fn high_watermark(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError> {
292 Ok(self
293 .state
294 .lock()
295 .expect("poisoned")
296 .get(partition)
297 .map_or(0, |ps| ps.next_offset))
298 }
299
300 fn log_start_offset(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError> {
301 Ok(self
302 .state
303 .lock()
304 .expect("poisoned")
305 .get(partition)
306 .map_or(0, |ps| ps.log_start))
307 }
308
309 fn truncate_before(
310 &self,
311 partition: &PartitionKey,
312 offset: i64,
313 ) -> Result<Vec<String>, ObjectLogError> {
314 let mut state = self.state.lock().expect("poisoned");
315 let mut dropped: Vec<String> = Vec::new();
316 match state.get_mut(partition) {
317 Some(ps) => {
318 for e in ps.entries.iter() {
319 if e.base_offset + e.record_count as i64 <= offset {
320 dropped.push(e.location.object_id.clone());
321 }
322 }
323 ps.entries
324 .retain(|e| e.base_offset + e.record_count as i64 > offset);
325 if offset > ps.log_start {
326 ps.log_start = offset.min(ps.next_offset);
327 }
328 }
329 None => return Ok(Vec::new()),
330 }
331 // An object is reclaimable only when no entry in ANY partition references it.
332 let mut live: HashSet<String> = HashSet::new();
333 for ps in state.values() {
334 for e in &ps.entries {
335 live.insert(e.location.object_id.clone());
336 }
337 }
338 let mut dead: Vec<String> = Vec::new();
339 let mut seen: HashSet<String> = HashSet::new();
340 for oid in dropped {
341 if !live.contains(&oid) && seen.insert(oid.clone()) {
342 dead.push(oid);
343 }
344 }
345 Ok(dead)
346 }
347}