Skip to main content

object_log/
manifest_sequencer.rs

1//! A `BlobStore`-persisted [`Sequencer`]: the offset→location index survives a
2//! restart, so a standalone object-log is crash-durable end to end.
3//!
4//! Each `commit` durably writes one manifest object (≤1 PUT per group-commit,
5//! co-amortized with the data object) recording the batches it assigned. On
6//! [`open`](ManifestSequencer::open) the index is rebuilt by replaying the
7//! manifest objects in order.
8
9use crate::{
10    BlobStore, CasOutcome, CommitBatch, CommitOutcome, IndexEntry, ObjectLogError, PartitionKey,
11    Sequencer,
12};
13use bytes::Bytes;
14use serde::{Deserialize, Serialize};
15use std::collections::{HashMap, HashSet};
16use std::sync::{Arc, Mutex};
17use tokio::runtime::{Builder, Runtime};
18
19#[derive(Serialize, Deserialize)]
20struct ManifestRecord {
21    entries: Vec<(PartitionKey, IndexEntry)>,
22}
23
24#[derive(Clone, Serialize, Deserialize)]
25struct PartitionIndexDoc {
26    epoch: u64,
27    next_offset: i64,
28    log_start: i64,
29    entries: Vec<IndexEntry>,
30}
31
32#[derive(Clone, Serialize, Deserialize, Default)]
33struct IndexCatalog {
34    partitions: Vec<String>,
35}
36
37#[derive(Default)]
38struct Part {
39    next_offset: i64,
40    log_start: i64,
41    epoch: u64,
42    entries: Vec<IndexEntry>,
43    /// Exact bytes last read or written for this partition's index object.
44    observed: Option<Bytes>,
45}
46
47struct Inner {
48    parts: HashMap<PartitionKey, Part>,
49    counter: u64,
50    catalog: Option<Bytes>,
51}
52
53/// A [`Sequencer`] (`Meta = ()`) that persists its index to a [`BlobStore`].
54pub struct ManifestSequencer {
55    blob: Arc<dyn BlobStore>,
56    prefix: String,
57    // `Option` so `Drop` can `shutdown_background()` — dropping a `Runtime` inside
58    // an async context (e.g. an `Arc` last-ref drop in a `#[tokio::test]`) panics.
59    rt: Option<Runtime>,
60    // Serialize mutations across publication without blocking committed reads.
61    commit_order: Mutex<()>,
62    inner: Mutex<Inner>,
63}
64
65impl Drop for ManifestSequencer {
66    fn drop(&mut self) {
67        if let Some(rt) = self.rt.take() {
68            rt.shutdown_background();
69        }
70    }
71}
72
73impl ManifestSequencer {
74    /// Open (or recover) a persisted sequencer. Manifest objects live under
75    /// `manifest_prefix` (keep it disjoint from the engine's data-object prefix).
76    /// Existing manifests are replayed to rebuild the index.
77    pub async fn open(
78        blob: Arc<dyn BlobStore>,
79        manifest_prefix: impl Into<String>,
80    ) -> Result<Self, ObjectLogError> {
81        let prefix = manifest_prefix.into();
82        let catalog_key = format!("{prefix}catalog");
83        let (parts, catalog, counter) = if let Some(catalog_bytes) = blob.get(&catalog_key).await? {
84            let catalog: IndexCatalog = serde_json::from_slice(&catalog_bytes)
85                .map_err(|e| ObjectLogError::Sequencer(format!("index catalog: {e}")))?;
86            let mut parts = HashMap::new();
87            for name in &catalog.partitions {
88                let key = index_object_key(&prefix, name);
89                let Some(doc_bytes) = blob.get(&key).await? else {
90                    parts.insert(PartitionKey(name.clone()), Part::default());
91                    continue;
92                };
93                let doc: PartitionIndexDoc = serde_json::from_slice(&doc_bytes).map_err(|e| {
94                    ObjectLogError::Sequencer(format!("partition index {name}: {e}"))
95                })?;
96                parts.insert(PartitionKey(name.clone()), Part::from_doc(doc, doc_bytes));
97            }
98            let counter = parts.len() as u64;
99            (parts, Some(catalog_bytes), counter)
100        } else {
101            let mut keys = blob.list(&prefix).await?;
102            keys.sort();
103            let mut parts: HashMap<PartitionKey, Part> = HashMap::new();
104            for key in &keys {
105                if key == &catalog_key || key.starts_with(&format!("{prefix}index/")) {
106                    continue;
107                }
108                let Some(bytes) = blob.get(key).await? else {
109                    continue;
110                };
111                let Ok(rec) = serde_json::from_slice::<ManifestRecord>(&bytes) else {
112                    continue;
113                };
114                for (pkey, entry) in rec.entries {
115                    let p = parts.entry(pkey).or_default();
116                    let end = entry.base_offset + entry.record_count as i64;
117                    if end > p.next_offset {
118                        p.next_offset = end;
119                    }
120                    p.entries.push(entry);
121                }
122            }
123            (parts, None, keys.len() as u64)
124        };
125        let rt = Builder::new_current_thread()
126            .enable_all()
127            .build()
128            .map_err(|e| ObjectLogError::StorageUnavailable(e.to_string()))?;
129        Ok(Self {
130            blob,
131            prefix,
132            rt: Some(rt),
133            commit_order: Mutex::new(()),
134            inner: Mutex::new(Inner {
135                parts,
136                counter,
137                catalog,
138            }),
139        })
140    }
141
142    fn index_key(&self, partition: &PartitionKey) -> String {
143        index_object_key(&self.prefix, partition.as_str())
144    }
145
146    fn catalog_key(&self) -> String {
147        format!("{}catalog", self.prefix)
148    }
149
150    fn block_on<T>(&self, future: impl std::future::Future<Output = T>) -> T {
151        self.rt
152            .as_ref()
153            .expect("runtime present until drop")
154            .block_on(future)
155    }
156
157    fn read_object(&self, key: &str) -> Result<Option<Bytes>, ObjectLogError> {
158        self.block_on(self.blob.get(key))
159    }
160
161    fn cas(
162        &self,
163        key: &str,
164        expected: Option<Bytes>,
165        new_value: Bytes,
166    ) -> Result<CasOutcome, ObjectLogError> {
167        self.block_on(self.blob.compare_and_swap(key, expected, new_value))
168    }
169
170    fn ensure_catalog(&self, partitions: &[PartitionKey]) -> Result<(), ObjectLogError> {
171        let key = self.catalog_key();
172        for _ in 0..8 {
173            let current = self.read_object(&key)?;
174            let mut names = if let Some(bytes) = &current {
175                serde_json::from_slice::<IndexCatalog>(bytes)
176                    .map_err(|error| ObjectLogError::Sequencer(format!("index catalog: {error}")))?
177                    .partitions
178            } else {
179                Vec::new()
180            };
181            let mut changed = false;
182            for partition in partitions {
183                if !names.iter().any(|name| name == partition.as_str()) {
184                    names.push(partition.0.clone());
185                    changed = true;
186                }
187            }
188            if !changed {
189                self.inner.lock().expect("poisoned").catalog = current;
190                return Ok(());
191            }
192            names.sort();
193            names.dedup();
194            let new_bytes = Bytes::from(
195                serde_json::to_vec(&IndexCatalog { partitions: names })
196                    .map_err(|error| ObjectLogError::Sequencer(error.to_string()))?,
197            );
198            match self.cas(&key, current, new_bytes.clone())? {
199                CasOutcome::Stored => {
200                    self.inner.lock().expect("poisoned").catalog = Some(new_bytes);
201                    return Ok(());
202                }
203                CasOutcome::Conflict { .. } => continue,
204            }
205        }
206        Err(ObjectLogError::Sequencer(
207            "catalog compare-and-swap did not land".into(),
208        ))
209    }
210
211    fn publish_partition(
212        &self,
213        partition: &PartitionKey,
214        batches: &[CommitBatch<'_, ()>],
215        indexes: &[usize],
216    ) -> Result<Vec<CommitOutcome>, ObjectLogError> {
217        let epoch = batches[indexes[0]].epoch;
218        if indexes.iter().any(|index| batches[*index].epoch != epoch) {
219            return Ok(reject_all(
220                indexes.len(),
221                "one partition commit mixed fence epochs",
222            ));
223        }
224        let (observed, mut doc) = {
225            let inner = self.inner.lock().expect("poisoned");
226            match inner
227                .parts
228                .get(partition)
229                .and_then(|part| part.observed.clone())
230            {
231                Some(bytes) => {
232                    let doc = serde_json::from_slice::<PartitionIndexDoc>(&bytes)
233                        .map_err(|error| ObjectLogError::Sequencer(error.to_string()))?;
234                    (Some(bytes), doc)
235                }
236                None => {
237                    let part = inner.parts.get(partition);
238                    (
239                        None,
240                        PartitionIndexDoc {
241                            epoch,
242                            next_offset: part.map_or(0, |part| part.next_offset),
243                            log_start: part.map_or(0, |part| part.log_start),
244                            entries: part.map(|part| part.entries.clone()).unwrap_or_default(),
245                        },
246                    )
247                }
248            }
249        };
250        if observed.is_some() && doc.epoch != epoch {
251            return Ok(reject_all(
252                indexes.len(),
253                format!(
254                    "partition {} epoch is {}, not {epoch}",
255                    partition.as_str(),
256                    doc.epoch
257                ),
258            ));
259        }
260        let mut outcomes = Vec::with_capacity(indexes.len());
261        let mut planned = Vec::with_capacity(indexes.len());
262        for index in indexes {
263            let batch = &batches[*index];
264            let entry = IndexEntry {
265                location: batch.location.clone(),
266                base_offset: doc.next_offset,
267                record_count: batch.record_count,
268            };
269            outcomes.push(CommitOutcome::Assigned {
270                base_offset: entry.base_offset,
271                record_count: entry.record_count,
272            });
273            doc.next_offset += i64::from(batch.record_count);
274            planned.push(entry.clone());
275            doc.entries.push(entry);
276        }
277        let new_bytes = Bytes::from(
278            serde_json::to_vec(&doc)
279                .map_err(|error| ObjectLogError::Sequencer(error.to_string()))?,
280        );
281        match self.cas(&self.index_key(partition), observed, new_bytes.clone())? {
282            CasOutcome::Stored => {
283                self.install_doc(partition, &doc, new_bytes);
284                Ok(outcomes)
285            }
286            CasOutcome::Conflict { current } => {
287                if let Some(bytes) = current
288                    && let Ok(found) = serde_json::from_slice::<PartitionIndexDoc>(&bytes)
289                {
290                    let already = planned
291                        .iter()
292                        .all(|entry| found.entries.iter().any(|have| have == entry));
293                    self.install_doc(partition, &found, bytes);
294                    if already {
295                        return Ok(outcomes);
296                    }
297                }
298                Ok(reject_all(
299                    indexes.len(),
300                    format!("partition {} tail moved", partition.as_str()),
301                ))
302            }
303        }
304    }
305
306    /// Install `partition`'s durable index, if any, and return it.
307    fn reload_partition(
308        &self,
309        partition: &PartitionKey,
310    ) -> Result<Option<(PartitionIndexDoc, Bytes)>, ObjectLogError> {
311        let Some(bytes) = self.read_object(&self.index_key(partition))? else {
312            return Ok(None);
313        };
314        let doc: PartitionIndexDoc = serde_json::from_slice(&bytes)
315            .map_err(|error| ObjectLogError::Sequencer(error.to_string()))?;
316        self.install_doc(partition, &doc, bytes.clone());
317        Ok(Some((doc, bytes)))
318    }
319
320    fn install_doc(&self, partition: &PartitionKey, doc: &PartitionIndexDoc, observed: Bytes) {
321        let mut inner = self.inner.lock().expect("poisoned");
322        inner.parts.insert(
323            partition.clone(),
324            Part {
325                next_offset: doc.next_offset,
326                log_start: doc.log_start,
327                epoch: doc.epoch,
328                entries: doc.entries.clone(),
329                observed: Some(observed),
330            },
331        );
332    }
333
334    /// Object ids referenced by any live index entry (for orphan reaping).
335    /// Does not include manifest object keys themselves.
336    pub fn live_object_ids(&self) -> HashSet<String> {
337        let st = self.inner.lock().expect("poisoned");
338        let mut live = HashSet::new();
339        for p in st.parts.values() {
340            for e in &p.entries {
341                live.insert(e.location.object_id.clone());
342            }
343        }
344        live
345    }
346
347    /// Point-in-time view of the rebuilt index (diagnostics / CLI).
348    pub fn snapshot(&self) -> IndexSnapshot {
349        let st = self.inner.lock().expect("poisoned");
350        let mut partitions: Vec<PartitionSnapshot> = st
351            .parts
352            .iter()
353            .map(|(k, p)| PartitionSnapshot {
354                partition: k.0.clone(),
355                log_start: p.log_start,
356                high_watermark: p.next_offset,
357                entry_count: p.entries.len(),
358                entries: p.entries.clone(),
359            })
360            .collect();
361        partitions.sort_by(|a, b| a.partition.cmp(&b.partition));
362        IndexSnapshot {
363            manifest_prefix: self.prefix.clone(),
364            manifest_count: st.counter,
365            partitions,
366        }
367    }
368}
369
370/// Full index view from [`ManifestSequencer::snapshot`].
371#[derive(Clone, Debug, Serialize, Deserialize)]
372pub struct IndexSnapshot {
373    /// Prefix used for manifest objects.
374    pub manifest_prefix: String,
375    /// Number of manifest objects replayed (commit counter).
376    pub manifest_count: u64,
377    /// Per-partition index state.
378    pub partitions: Vec<PartitionSnapshot>,
379}
380
381/// One partition's index bounds and entries.
382#[derive(Clone, Debug, Serialize, Deserialize)]
383pub struct PartitionSnapshot {
384    /// Partition key string.
385    pub partition: String,
386    /// First readable offset.
387    pub log_start: i64,
388    /// Next offset to assign (high watermark).
389    pub high_watermark: i64,
390    /// Number of index entries.
391    pub entry_count: usize,
392    /// Ordered index entries (may be large; CLI can omit via flag).
393    pub entries: Vec<IndexEntry>,
394}
395
396impl Sequencer for ManifestSequencer {
397    type Meta = ();
398
399    fn supports_multi_object_commit(&self) -> bool {
400        true
401    }
402
403    fn commit(
404        &self,
405        batches: &[CommitBatch<'_, ()>],
406    ) -> Result<Vec<CommitOutcome>, ObjectLogError> {
407        let _commit = self.commit_order.lock().expect("poisoned");
408        if batches.is_empty() {
409            return Ok(Vec::new());
410        }
411        let mut order: Vec<PartitionKey> = Vec::new();
412        let mut groups: HashMap<PartitionKey, Vec<usize>> = HashMap::new();
413        for (index, batch) in batches.iter().enumerate() {
414            if !groups.contains_key(&batch.partition) {
415                order.push(batch.partition.clone());
416            }
417            groups
418                .entry(batch.partition.clone())
419                .or_default()
420                .push(index);
421        }
422        self.ensure_catalog(&order)?;
423        let mut outcomes = vec![None; batches.len()];
424        let mut published = false;
425        for partition in order {
426            let indexes = &groups[&partition];
427            match self.publish_partition(&partition, batches, indexes) {
428                Ok(partition_outcomes) => {
429                    for (index, outcome) in indexes.iter().zip(partition_outcomes) {
430                        if matches!(
431                            outcome,
432                            CommitOutcome::Assigned { .. } | CommitOutcome::Duplicate { .. }
433                        ) {
434                            published = true;
435                        }
436                        outcomes[*index] = Some(outcome);
437                    }
438                }
439                Err(error) => {
440                    for index in indexes {
441                        outcomes[*index] = Some(CommitOutcome::Rejected {
442                            reason: error.to_string(),
443                        });
444                    }
445                }
446            }
447        }
448        if published {
449            let mut inner = self.inner.lock().expect("poisoned");
450            inner.counter = inner.counter.saturating_add(1);
451        }
452        Ok(outcomes
453            .into_iter()
454            .map(|outcome| outcome.expect("every batch has an outcome"))
455            .collect())
456    }
457
458    fn fence_epoch(
459        &self,
460        partition: &PartitionKey,
461        expected: u64,
462        new_epoch: u64,
463    ) -> Result<(), ObjectLogError> {
464        let _commit = self.commit_order.lock().expect("poisoned");
465        if expected == new_epoch {
466            return Ok(());
467        }
468        // Fence the durable index, not this handle's view of it: another writer
469        // may have created or advanced the index since this handle opened, and a
470        // fence that only compared cached bytes would silently store nothing.
471        self.ensure_catalog(std::slice::from_ref(partition))?;
472        for _ in 0..8 {
473            let (mut doc, observed) = match self.reload_partition(partition)? {
474                Some((current, bytes)) => {
475                    if current.epoch == new_epoch {
476                        return Ok(());
477                    }
478                    if current.epoch != expected {
479                        return Err(ObjectLogError::Sequencer(format!(
480                            "partition {} epoch is {}, not {expected}",
481                            partition.as_str(),
482                            current.epoch
483                        )));
484                    }
485                    (current, Some(bytes))
486                }
487                None => {
488                    // No index yet: create it at the new epoch, so a writer that
489                    // never saw one cannot publish under an older epoch.
490                    let inner = self.inner.lock().expect("poisoned");
491                    let part = inner.parts.get(partition);
492                    let doc = PartitionIndexDoc {
493                        epoch: new_epoch,
494                        next_offset: part.map_or(0, |part| part.next_offset),
495                        log_start: part.map_or(0, |part| part.log_start),
496                        entries: part.map(|part| part.entries.clone()).unwrap_or_default(),
497                    };
498                    (doc, None)
499                }
500            };
501            doc.epoch = new_epoch;
502            let new_bytes = Bytes::from(
503                serde_json::to_vec(&doc)
504                    .map_err(|error| ObjectLogError::Sequencer(error.to_string()))?,
505            );
506            match self.cas(&self.index_key(partition), observed, new_bytes.clone())? {
507                CasOutcome::Stored => {
508                    self.install_doc(partition, &doc, new_bytes);
509                    return Ok(());
510                }
511                // A concurrent commit or fence moved the index; re-read and retry.
512                CasOutcome::Conflict { .. } => continue,
513            }
514        }
515        Err(ObjectLogError::Sequencer(format!(
516            "partition {} epoch fence did not land",
517            partition.as_str()
518        )))
519    }
520
521    fn partition_epoch(&self, partition: &PartitionKey) -> Option<u64> {
522        let inner = self.inner.lock().expect("poisoned");
523        inner
524            .parts
525            .get(partition)
526            .filter(|part| part.observed.is_some())
527            .map(|part| part.epoch)
528    }
529
530    /// A batch rejected because this partition's index was fenced past its epoch
531    /// can never commit: report [`ObjectLogError::Fenced`]. Other rejections stay
532    /// [`ObjectLogError::Sequencer`]. The index read during the rejected commit
533    /// is the one consulted.
534    fn rejection_error(
535        &self,
536        partition: &PartitionKey,
537        epoch: u64,
538        reason: String,
539    ) -> ObjectLogError {
540        #[allow(deprecated)]
541        match self.partition_epoch(partition) {
542            Some(current) if current > epoch => ObjectLogError::Fenced {
543                partition: partition.as_str().to_owned(),
544                epoch,
545                current,
546            },
547            _ => ObjectLogError::Sequencer(reason),
548        }
549    }
550
551    fn refresh_partition(&self, partition: &PartitionKey) -> Result<(), ObjectLogError> {
552        let _commit = self.commit_order.lock().expect("poisoned");
553        self.reload_partition(partition)?;
554        Ok(())
555    }
556
557    fn lookup(
558        &self,
559        partition: &PartitionKey,
560        fetch_offset: i64,
561    ) -> Result<Vec<IndexEntry>, ObjectLogError> {
562        let st = self.inner.lock().expect("poisoned");
563        let Some(p) = st.parts.get(partition) else {
564            return Ok(Vec::new());
565        };
566        Ok(p.entries
567            .iter()
568            .filter(|e| e.base_offset + e.record_count as i64 > fetch_offset)
569            .cloned()
570            .collect())
571    }
572
573    fn high_watermark(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError> {
574        Ok(self
575            .inner
576            .lock()
577            .expect("poisoned")
578            .parts
579            .get(partition)
580            .map_or(0, |p| p.next_offset))
581    }
582
583    fn log_start_offset(&self, partition: &PartitionKey) -> Result<i64, ObjectLogError> {
584        Ok(self
585            .inner
586            .lock()
587            .expect("poisoned")
588            .parts
589            .get(partition)
590            .map_or(0, |p| p.log_start))
591    }
592
593    fn truncate_before(
594        &self,
595        partition: &PartitionKey,
596        offset: i64,
597    ) -> Result<Vec<String>, ObjectLogError> {
598        let _commit = self.commit_order.lock().expect("poisoned");
599        let snapshot = {
600            let st = self.inner.lock().expect("poisoned");
601            let Some(part) = st.parts.get(partition) else {
602                return Ok(Vec::new());
603            };
604            (
605                part.observed.clone(),
606                part.entries.clone(),
607                part.next_offset,
608                part.epoch,
609                part.log_start,
610            )
611        };
612        let (observed, entries, next_offset, epoch, mut log_start) = snapshot;
613        let mut dropped = Vec::new();
614        let mut kept = Vec::new();
615        for entry in entries {
616            if entry.base_offset + i64::from(entry.record_count) <= offset {
617                dropped.push(entry.location.object_id.clone());
618            } else {
619                kept.push(entry);
620            }
621        }
622        if offset > log_start {
623            log_start = offset.min(next_offset);
624        }
625        let doc = PartitionIndexDoc {
626            epoch,
627            next_offset,
628            log_start,
629            entries: kept,
630        };
631        if observed.is_some() {
632            let new_bytes = Bytes::from(
633                serde_json::to_vec(&doc)
634                    .map_err(|error| ObjectLogError::Sequencer(error.to_string()))?,
635            );
636            match self.cas(&self.index_key(partition), observed, new_bytes.clone())? {
637                CasOutcome::Stored => self.install_doc(partition, &doc, new_bytes),
638                CasOutcome::Conflict { .. } => {
639                    return Err(ObjectLogError::Sequencer(format!(
640                        "partition {} truncate lost the compare-and-swap",
641                        partition.as_str()
642                    )));
643                }
644            }
645        } else {
646            let mut st = self.inner.lock().expect("poisoned");
647            if let Some(part) = st.parts.get_mut(partition) {
648                part.entries = doc.entries.clone();
649                part.log_start = doc.log_start;
650            }
651        }
652        let live = {
653            let st = self.inner.lock().expect("poisoned");
654            let mut live = HashSet::new();
655            for part in st.parts.values() {
656                for entry in &part.entries {
657                    live.insert(entry.location.object_id.clone());
658                }
659            }
660            live
661        };
662        let mut dead = Vec::new();
663        let mut seen = HashSet::new();
664        for object_id in dropped {
665            if !live.contains(&object_id) && seen.insert(object_id.clone()) {
666                dead.push(object_id);
667            }
668        }
669        Ok(dead)
670    }
671}
672
673impl Part {
674    fn from_doc(doc: PartitionIndexDoc, observed: Bytes) -> Self {
675        Self {
676            next_offset: doc.next_offset,
677            log_start: doc.log_start,
678            epoch: doc.epoch,
679            entries: doc.entries,
680            observed: Some(observed),
681        }
682    }
683}
684
685fn index_object_key(prefix: &str, partition: &str) -> String {
686    let mut encoded = String::with_capacity(partition.len() * 2);
687    for byte in partition.as_bytes() {
688        encoded.push_str(&format!("{byte:02x}"));
689    }
690    format!("{prefix}index/{encoded}")
691}
692
693fn reject_all(count: usize, reason: impl Into<String>) -> Vec<CommitOutcome> {
694    let reason = reason.into();
695    vec![CommitOutcome::Rejected { reason }; count]
696}
697
698#[cfg(test)]
699mod index_tests {
700    use super::*;
701    use crate::{
702        BatchLocation, BlobStore, CommitBatch, CommitOutcome, Durability, FlushConfig,
703        InMemorySequencer, LogEngine, MemoryBlobStore, ObjectLogError, PartitionKey,
704    };
705    use async_trait::async_trait;
706    use bytes::Bytes;
707    use std::sync::Arc;
708    use std::sync::atomic::{AtomicUsize, Ordering};
709
710    fn location(object: &str) -> BatchLocation {
711        BatchLocation {
712            object_id: object.to_string(),
713            byte_start: 0,
714            byte_len: 1,
715        }
716    }
717
718    fn run_commit(
719        seq: Arc<ManifestSequencer>,
720        partitions: Vec<(&str, &str, u64)>,
721    ) -> Result<Vec<CommitOutcome>, ObjectLogError> {
722        let owned: Vec<(String, String, u64)> = partitions
723            .into_iter()
724            .map(|(partition, object, epoch)| (partition.to_string(), object.to_string(), epoch))
725            .collect();
726        std::thread::spawn(move || {
727            let meta = ();
728            let batches: Vec<CommitBatch<'_, ()>> = owned
729                .iter()
730                .map(|(partition, object, epoch)| CommitBatch {
731                    partition: PartitionKey(partition.clone()),
732                    record_count: 1,
733                    location: location(object),
734                    meta: &meta,
735                    epoch: *epoch,
736                })
737                .collect();
738            seq.commit(&batches)
739        })
740        .join()
741        .expect("commit thread")
742    }
743
744    /// Run a blocking sequencer call off the async test thread.
745    fn on_thread<T: Send + 'static>(
746        seq: &Arc<ManifestSequencer>,
747        call: impl FnOnce(&ManifestSequencer) -> T + Send + 'static,
748    ) -> T {
749        let seq = Arc::clone(seq);
750        std::thread::spawn(move || call(&seq))
751            .join()
752            .expect("sequencer thread")
753    }
754
755    struct ListProbe {
756        inner: MemoryBlobStore,
757        lists: Arc<AtomicUsize>,
758    }
759
760    #[async_trait]
761    impl BlobStore for ListProbe {
762        async fn put(&self, key: &str, value: Bytes) -> Result<(), ObjectLogError> {
763            self.inner.put(key, value).await
764        }
765        async fn get(&self, key: &str) -> Result<Option<Bytes>, ObjectLogError> {
766            self.inner.get(key).await
767        }
768        async fn get_range(
769            &self,
770            key: &str,
771            range: std::ops::Range<u64>,
772        ) -> Result<Option<Bytes>, ObjectLogError> {
773            self.inner.get_range(key, range).await
774        }
775        async fn list(&self, prefix: &str) -> Result<Vec<String>, ObjectLogError> {
776            self.lists.fetch_add(1, Ordering::SeqCst);
777            self.inner.list(prefix).await
778        }
779        async fn delete(&self, key: &str) -> Result<(), ObjectLogError> {
780            self.inner.delete(key).await
781        }
782        async fn compare_and_swap(
783            &self,
784            key: &str,
785            expected: Option<Bytes>,
786            new_value: Bytes,
787        ) -> Result<crate::CasOutcome, ObjectLogError> {
788            self.inner.compare_and_swap(key, expected, new_value).await
789        }
790    }
791
792    #[tokio::test]
793    async fn two_writers_cannot_commit_the_same_partition_tail() {
794        let blob: Arc<dyn BlobStore> = Arc::new(MemoryBlobStore::new());
795        let first = Arc::new(
796            ManifestSequencer::open(Arc::clone(&blob), "manifest/")
797                .await
798                .unwrap(),
799        );
800        let second = Arc::new(
801            ManifestSequencer::open(Arc::clone(&blob), "manifest/")
802                .await
803                .unwrap(),
804        );
805        let won = run_commit(first, vec![("p", "obj-a", 1)]).unwrap();
806        assert!(matches!(
807            won[0],
808            CommitOutcome::Assigned {
809                base_offset: 0,
810                record_count: 1
811            }
812        ));
813        let lost = run_commit(second, vec![("p", "obj-b", 1)]).unwrap();
814        assert!(
815            matches!(lost[0], CommitOutcome::Rejected { .. }),
816            "stale tail must fail closed, got {lost:?}"
817        );
818        let reopened = ManifestSequencer::open(blob, "manifest/").await.unwrap();
819        let partition = PartitionKey("p".into());
820        assert_eq!(reopened.high_watermark(&partition).unwrap(), 1);
821        let entries = reopened.lookup(&partition, 0).unwrap();
822        assert_eq!(entries.len(), 1);
823        assert_eq!(entries[0].location.object_id, "obj-a");
824    }
825
826    #[tokio::test]
827    async fn mixed_seal_keeps_the_partition_that_won_and_rejects_the_moved_tail() {
828        let blob: Arc<dyn BlobStore> = Arc::new(MemoryBlobStore::new());
829        let first = Arc::new(
830            ManifestSequencer::open(Arc::clone(&blob), "manifest/")
831                .await
832                .unwrap(),
833        );
834        let second = Arc::new(
835            ManifestSequencer::open(Arc::clone(&blob), "manifest/")
836                .await
837                .unwrap(),
838        );
839        run_commit(first, vec![("p", "obj-a", 1)]).unwrap();
840        let mixed = run_commit(second, vec![("p", "obj-b", 1), ("q", "obj-b", 1)]).unwrap();
841        assert!(matches!(mixed[0], CommitOutcome::Rejected { .. }));
842        assert!(matches!(
843            mixed[1],
844            CommitOutcome::Assigned { base_offset: 0, .. }
845        ));
846        let reopened = ManifestSequencer::open(blob, "manifest/").await.unwrap();
847        assert_eq!(
848            reopened.lookup(&PartitionKey("p".into()), 0).unwrap().len(),
849            1
850        );
851        assert_eq!(
852            reopened.high_watermark(&PartitionKey("p".into())).unwrap(),
853            1,
854            "the rejected partition must not skip an offset"
855        );
856        assert_eq!(
857            reopened.lookup(&PartitionKey("q".into()), 0).unwrap()[0]
858                .location
859                .object_id,
860            "obj-b"
861        );
862    }
863
864    #[tokio::test]
865    async fn open_does_not_list_the_manifest_prefix_when_an_index_exists() {
866        let memory = MemoryBlobStore::new();
867        let blob: Arc<dyn BlobStore> = Arc::new(memory.clone());
868        let seq = Arc::new(
869            ManifestSequencer::open(Arc::clone(&blob), "manifest/")
870                .await
871                .unwrap(),
872        );
873        run_commit(seq, vec![("p", "obj-a", 4)]).unwrap();
874        let lists = Arc::new(AtomicUsize::new(0));
875        let probe = Arc::new(ListProbe {
876            inner: memory,
877            lists: Arc::clone(&lists),
878        });
879        let reopened = ManifestSequencer::open(probe, "manifest/").await.unwrap();
880        assert_eq!(
881            lists.load(Ordering::SeqCst),
882            0,
883            "a current index catalog must be read by key, not by listing manifests"
884        );
885        assert_eq!(
886            reopened.high_watermark(&PartitionKey("p".into())).unwrap(),
887            1
888        );
889    }
890
891    #[tokio::test]
892    async fn distinct_writers_do_not_share_a_data_object_key() {
893        let blob = Arc::new(MemoryBlobStore::new());
894        let config = FlushConfig {
895            linger: std::time::Duration::ZERO,
896            ..FlushConfig::default()
897        };
898        let left = LogEngine::new_with_writer(
899            Arc::clone(&blob) as Arc<dyn BlobStore>,
900            Arc::new(InMemorySequencer::new()),
901            config,
902            "data/",
903            "writer-a",
904        );
905        let right = LogEngine::new_with_writer(
906            Arc::clone(&blob) as Arc<dyn BlobStore>,
907            Arc::new(InMemorySequencer::new()),
908            config,
909            "data/",
910            "writer-b",
911        );
912        left.produce_at_epoch(
913            PartitionKey("p".into()),
914            Bytes::from_static(b"left"),
915            1,
916            (),
917            Durability::Sequenced,
918            3,
919        )
920        .await
921        .unwrap();
922        right
923            .produce_at_epoch(
924                PartitionKey("p".into()),
925                Bytes::from_static(b"right"),
926                1,
927                (),
928                Durability::Sequenced,
929                3,
930            )
931            .await
932            .unwrap();
933        let keys = blob.list("data/").await.unwrap();
934        assert_eq!(
935            keys.len(),
936            2,
937            "writers must not overwrite one object: {keys:?}"
938        );
939        assert!(keys.iter().any(|key| key.contains("writer-a")));
940        assert!(keys.iter().any(|key| key.contains("writer-b")));
941        assert!(
942            keys.iter()
943                .all(|key| key.contains("/00000000000000000003/"))
944        );
945    }
946
947    #[tokio::test]
948    async fn fence_from_a_handle_that_never_saw_the_index_rejects_the_stale_writer() {
949        let blob: Arc<dyn BlobStore> = Arc::new(MemoryBlobStore::new());
950        let owner = Arc::new(
951            ManifestSequencer::open(Arc::clone(&blob), "manifest/")
952                .await
953                .unwrap(),
954        );
955        // The standby opens before the owner's first commit, so it holds no index.
956        let standby = Arc::new(
957            ManifestSequencer::open(Arc::clone(&blob), "manifest/")
958                .await
959                .unwrap(),
960        );
961        run_commit(Arc::clone(&owner), vec![("p", "obj-a", 1)]).unwrap();
962        let partition = PartitionKey("p".into());
963        let fence_partition = partition.clone();
964        on_thread(&standby, move |seq| seq.fence_epoch(&fence_partition, 1, 2)).unwrap();
965
966        let stale = run_commit(Arc::clone(&owner), vec![("p", "obj-stale", 1)]).unwrap();
967        assert!(
968            matches!(stale[0], CommitOutcome::Rejected { .. }),
969            "a commit at the fenced epoch must fail closed, got {stale:?}"
970        );
971        let fresh = run_commit(standby, vec![("p", "obj-b", 2)]).unwrap();
972        assert!(matches!(
973            fresh[0],
974            CommitOutcome::Assigned { base_offset: 1, .. }
975        ));
976        let reopened = ManifestSequencer::open(blob, "manifest/").await.unwrap();
977        let objects: Vec<_> = reopened
978            .lookup(&partition, 0)
979            .unwrap()
980            .into_iter()
981            .map(|entry| entry.location.object_id)
982            .collect();
983        assert_eq!(objects, ["obj-a", "obj-b"]);
984    }
985
986    #[tokio::test]
987    async fn fence_before_any_commit_creates_the_index_at_the_new_epoch() {
988        let blob: Arc<dyn BlobStore> = Arc::new(MemoryBlobStore::new());
989        let stale = Arc::new(
990            ManifestSequencer::open(Arc::clone(&blob), "manifest/")
991                .await
992                .unwrap(),
993        );
994        let fencer = Arc::new(
995            ManifestSequencer::open(Arc::clone(&blob), "manifest/")
996                .await
997                .unwrap(),
998        );
999        on_thread(&fencer, |seq| {
1000            seq.fence_epoch(&PartitionKey("p".into()), 0, 2)
1001        })
1002        .unwrap();
1003        let lost = run_commit(stale, vec![("p", "obj-stale", 1)]).unwrap();
1004        assert!(
1005            matches!(lost[0], CommitOutcome::Rejected { .. }),
1006            "a writer that never saw the fenced index must not commit, got {lost:?}"
1007        );
1008        let won = run_commit(fencer, vec![("p", "obj-b", 2)]).unwrap();
1009        assert!(matches!(
1010            won[0],
1011            CommitOutcome::Assigned { base_offset: 0, .. }
1012        ));
1013        let reopened = ManifestSequencer::open(blob, "manifest/").await.unwrap();
1014        assert_eq!(
1015            reopened.snapshot().partitions[0].entries[0]
1016                .location
1017                .object_id,
1018            "obj-b"
1019        );
1020    }
1021
1022    #[tokio::test]
1023    async fn refresh_partition_reveals_another_writers_commits() {
1024        let blob: Arc<dyn BlobStore> = Arc::new(MemoryBlobStore::new());
1025        let writer = Arc::new(
1026            ManifestSequencer::open(Arc::clone(&blob), "manifest/")
1027                .await
1028                .unwrap(),
1029        );
1030        let reader = Arc::new(
1031            ManifestSequencer::open(Arc::clone(&blob), "manifest/")
1032                .await
1033                .unwrap(),
1034        );
1035        run_commit(writer, vec![("p", "obj-a", 1), ("p", "obj-b", 1)]).unwrap();
1036        let partition = PartitionKey("p".into());
1037        assert_eq!(reader.high_watermark(&partition).unwrap(), 0);
1038        let refreshed = partition.clone();
1039        on_thread(&reader, move |seq| seq.refresh_partition(&refreshed)).unwrap();
1040        assert_eq!(reader.high_watermark(&partition).unwrap(), 2);
1041        assert_eq!(reader.lookup(&partition, 0).unwrap().len(), 2);
1042    }
1043
1044    #[tokio::test]
1045    async fn a_fenced_writer_gets_a_typed_fenced_error() {
1046        let blob: Arc<dyn BlobStore> = Arc::new(MemoryBlobStore::new());
1047        let config = FlushConfig {
1048            linger: std::time::Duration::ZERO,
1049            ..FlushConfig::default()
1050        };
1051        let owner_sequencer = Arc::new(
1052            ManifestSequencer::open(Arc::clone(&blob), "manifest/")
1053                .await
1054                .unwrap(),
1055        );
1056        let standby = Arc::new(
1057            ManifestSequencer::open(Arc::clone(&blob), "manifest/")
1058                .await
1059                .unwrap(),
1060        );
1061        let owner = LogEngine::new_with_writer(
1062            Arc::clone(&blob),
1063            owner_sequencer,
1064            config,
1065            "data/",
1066            "writer-a",
1067        );
1068        let partition = PartitionKey("p".into());
1069        owner
1070            .produce_at_epoch(
1071                partition.clone(),
1072                Bytes::from_static(b"before"),
1073                1,
1074                (),
1075                Durability::Sequenced,
1076                1,
1077            )
1078            .await
1079            .unwrap();
1080        let fenced = partition.clone();
1081        on_thread(&standby, move |seq| seq.fence_epoch(&fenced, 1, 2)).unwrap();
1082
1083        let stale = owner
1084            .produce_at_epoch(
1085                partition.clone(),
1086                Bytes::from_static(b"stale"),
1087                1,
1088                (),
1089                Durability::Sequenced,
1090                1,
1091            )
1092            .await;
1093        match stale {
1094            Err(ObjectLogError::Fenced {
1095                partition: name,
1096                epoch: 1,
1097                current: 2,
1098            }) => assert_eq!(name, "p"),
1099            other => panic!("a write behind the fence must be Fenced, got {other:?}"),
1100        }
1101    }
1102
1103    #[tokio::test]
1104    async fn default_rejection_error_is_a_sequencer_error() {
1105        let seq = crate::InMemorySequencer::new();
1106        let error = seq.rejection_error(&PartitionKey("p".into()), 1, "tail moved".into());
1107        assert!(matches!(error, ObjectLogError::Sequencer(reason) if reason == "tail moved"));
1108    }
1109}