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 batches in one object 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 /// Assign offsets to a just-PUT object's batches and persist the index.
97 /// Returns one [`CommitOutcome`] per input batch, in order. Atomic: on `Err`,
98 /// nothing is committed.
99 fn commit(
100 &self,
101 batches: &[CommitBatch<'_, Self::Meta>],
102 ) -> Result<Vec<CommitOutcome>, ObjectLogError>;
103
104 /// Resolve `fetch_offset` to the ordered index entries covering it onward.
105 fn lookup(
106 &self,
107 partition: &PartitionKey,
108 fetch_offset: i64,
109 ) -> Result<Vec<IndexEntry>, ObjectLogError>;
110
111 /// The next offset to be assigned (index-only; no object reads).
112 fn high_watermark(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError>;
113
114 /// The first readable offset (advances on [`truncate_before`](Sequencer::truncate_before)).
115 fn log_start_offset(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError>;
116
117 /// Retention MECHANISM (not policy): drop index entries below `offset` and
118 /// return object ids that now have **no** live references from **any**
119 /// partition (objects are multiplexed and shared), for the engine to delete.
120 fn truncate_before(
121 &self,
122 partition: &PartitionKey,
123 offset: i64,
124 ) -> Result<Vec<String>, ObjectLogError>;
125}
126
127/// Per-partition in-memory index state.
128#[derive(Default)]
129struct PartState {
130 next_offset: i64,
131 log_start: i64,
132 entries: Vec<IndexEntry>,
133}
134
135/// A single-node, in-memory [`Sequencer`] (`Meta = ()`): assigns dense offsets and
136/// keeps the offset→location index in memory.
137///
138/// The log *bytes* live durably in the `BlobStore`, but this index does not
139/// survive a restart — use it for tests and single-process work, or persist the
140/// index yourself for a crash-durable standalone log.
141#[derive(Default)]
142pub struct InMemorySequencer {
143 state: Mutex<HashMap<PartitionKey, PartState>>,
144}
145
146impl InMemorySequencer {
147 /// Create an empty sequencer.
148 pub fn new() -> Self {
149 Self::default()
150 }
151
152 /// Object ids referenced by any live index entry (for orphan reaping).
153 pub fn live_object_ids(&self) -> HashSet<String> {
154 let state = self.state.lock().expect("poisoned");
155 let mut live = HashSet::new();
156 for ps in state.values() {
157 for e in &ps.entries {
158 live.insert(e.location.object_id.clone());
159 }
160 }
161 live
162 }
163}
164
165impl Sequencer for InMemorySequencer {
166 type Meta = ();
167
168 fn commit(
169 &self,
170 batches: &[CommitBatch<'_, Self::Meta>],
171 ) -> Result<Vec<CommitOutcome>, ObjectLogError> {
172 let mut state = self.state.lock().expect("poisoned");
173 let mut outcomes = Vec::with_capacity(batches.len());
174 for cb in batches {
175 let ps = state.entry(cb.partition.clone()).or_default();
176 let base = ps.next_offset;
177 ps.entries.push(IndexEntry {
178 location: cb.location.clone(),
179 base_offset: base,
180 record_count: cb.record_count,
181 });
182 ps.next_offset = base + cb.record_count as i64;
183 outcomes.push(CommitOutcome::Assigned {
184 base_offset: base,
185 record_count: cb.record_count,
186 });
187 }
188 Ok(outcomes)
189 }
190
191 fn lookup(
192 &self,
193 partition: &PartitionKey,
194 fetch_offset: i64,
195 ) -> Result<Vec<IndexEntry>, ObjectLogError> {
196 let state = self.state.lock().expect("poisoned");
197 let Some(ps) = state.get(partition) else {
198 return Ok(Vec::new());
199 };
200 Ok(ps
201 .entries
202 .iter()
203 .filter(|e| e.base_offset + e.record_count as i64 > fetch_offset)
204 .cloned()
205 .collect())
206 }
207
208 fn high_watermark(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError> {
209 Ok(self
210 .state
211 .lock()
212 .expect("poisoned")
213 .get(partition)
214 .map_or(0, |ps| ps.next_offset))
215 }
216
217 fn log_start_offset(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError> {
218 Ok(self
219 .state
220 .lock()
221 .expect("poisoned")
222 .get(partition)
223 .map_or(0, |ps| ps.log_start))
224 }
225
226 fn truncate_before(
227 &self,
228 partition: &PartitionKey,
229 offset: i64,
230 ) -> Result<Vec<String>, ObjectLogError> {
231 let mut state = self.state.lock().expect("poisoned");
232 let mut dropped: Vec<String> = Vec::new();
233 match state.get_mut(partition) {
234 Some(ps) => {
235 for e in ps.entries.iter() {
236 if e.base_offset + e.record_count as i64 <= offset {
237 dropped.push(e.location.object_id.clone());
238 }
239 }
240 ps.entries
241 .retain(|e| e.base_offset + e.record_count as i64 > offset);
242 if offset > ps.log_start {
243 ps.log_start = offset.min(ps.next_offset);
244 }
245 }
246 None => return Ok(Vec::new()),
247 }
248 // An object is reclaimable only when no entry in ANY partition references it.
249 let mut live: HashSet<String> = HashSet::new();
250 for ps in state.values() {
251 for e in &ps.entries {
252 live.insert(e.location.object_id.clone());
253 }
254 }
255 let mut dead: Vec<String> = Vec::new();
256 let mut seen: HashSet<String> = HashSet::new();
257 for oid in dropped {
258 if !live.contains(&oid) && seen.insert(oid.clone()) {
259 dead.push(oid);
260 }
261 }
262 Ok(dead)
263 }
264}