objectstore_service/backend/

tiered.rs

//! Two-tier storage backend with size-based routing and redirect tombstones.
//!
//! [`TieredStorage`] routes objects to a high-volume or long-term backend based
//! on size and maintains redirect tombstones so that reads never need to probe
//! both backends. See the [crate-level documentation](crate) for the high-level
//! motivation, and the [`TieredStorage`] struct docs for routing and tombstone
//! semantics.
//!
//! # Cross-Tier Consistency
//!
//! A single logical object may span both backends: a tombstone in HV pointing
//! to a payload in LT. Mutations keep the two in sync through compare-and-swap
//! on the high-volume backend (see [`HighVolumeBackend::compare_and_write`]).
//! Each operation reads the current HV revision, performs its work, then
//! atomically swaps the HV entry only if the revision is still current —
//! rolling back on conflict.
//!
//! ## Revision Keys
//!
//! Every long-term write stores its payload at a **revision key** in the
//! long-term backend: `{original_key}/{uuid}`. The UUID suffix is random (no
//! monotonicity is guaranteed), so each write targets a distinct LT path
//! regardless of whether another write to the same logical key is in progress.
//! The tombstone in HV then points to this specific revision. Because each
//! writer owns its own LT blob, the compare-and-swap on the tombstone becomes
//! an atomic pointer swap: the winner's revision is committed and the loser
//! can safely delete its own blob without affecting the winner.
//!
//! See `new_long_term_revision` for the key construction.
//!
//! ## Compare-and-Swap
//!
//! All mutating operations follow a common pattern of reading the current
//! revision, performing the upload, atomically swapping the revision (commit
//! point), and cleaning up the now-unreferenced LT blob in the background:
//!
//! ### Large-Object Write (> 1 MiB)
//!
//! 1. **Read HV** to capture the current revision (existing tombstone target,
//!    or absent).
//! 2. **Write payload to LT** at a unique revision key.
//! 3. **Compare-and-swap in HV**: write a tombstone pointing to the new
//!    revision, only if the current revision still matches step 1.
//!    - **OK** — schedule background deletion of the old LT blob, if any.
//!    - **Conflict** — another writer won the race; schedule background deletion
//!      of our new LT blob.
//!    - **Error** — reload the tombstone and delete the unreferenced blob or
//!      blobs.
//!
//! ### Small-Object Write (≤ 1 MiB)
//!
//! 1. **Write inline to HV**, skipping the write if a tombstone is present.
//!    - **OK** — done; the object is stored entirely in HV.
//!    - **Tombstone present** — a large object already occupies this key;
//!      continue:
//! 2. **Compare-and-swap in HV**: replace the tombstone with inline data, only
//!    if the tombstone's revision still matches.
//!    - **OK** — schedule background deletion of the old LT blob.
//!    - **Conflict** — another writer won the race; they will clean up the
//!      LT blob and we have no new LT blob to clean up.
//!    - **Error** — reload the tombstone and delete the unreferenced blob if
//!      the write went through.
//!
//! ### Delete
//!
//! 1. **Delete from HV** if the entry is not a tombstone.
//!    - **OK** — done; there is no LT data to clean up.
//!    - **Tombstone present** — a large object is stored here; continue:
//! 2. **Compare-and-swap in HV**: remove the tombstone, only if its revision
//!    still matches.
//!    - **OK** — schedule background deletion of the LT blob.
//!    - **Conflict** — another writer won the race; they will clean up.
//!    - **Error** — reload the tombstone and delete the unreferenced blob if
//!      the write went through.
//!
//! Tombstone removal is the commit point for deletes. If the subsequent LT
//! cleanup fails, an orphan blob remains but the object is already unreachable
//! through the normal read path.
//!
//! ## Last-Writer-Wins
//!
//! Concurrent mutations on the same key are inherently a race. Even a write
//! that returns `Ok` may be immediately overwritten by another caller — there
//! is no ordering guarantee and objectstore cannot provide a read-your-writes
//! promise.
//!
//! CAS conflicts are therefore **not errors**: the losing writer's data is
//! cleaned up and `Ok` is returned, because the result is indistinguishable
//! from having succeeded a moment earlier and then been overwritten.
//!
//! ### Idempotency
//!
//! `compare_and_write` is idempotent: if the row is already in the target state, it
//! returns `true` without re-applying the mutation. This is critical for retry
//! safety. If the server commits a write but the response is lost, a retry sees the
//! already-mutated state and still returns `true` — so callers do not mistakenly
//! treat a successful commit as a lost race and clean up data that was actually
//! persisted.
//!
//! # Resumable Uploads
//!
//! Resumable uploads are accepted only when their declared size exceeds 1 MiB and are
//! written to the long-term backend. A resumable upload remains inaccessible until
//! the long-term backend completes and a high-volume tombstone is committed.
//!
//! Each upload has a separate HV marker with a fixed five-day lifetime that serves
//! as the source of truth for whether the upload logically exists.
//! This marker is consumed upon cancellation or the first submission of a final chunk, making
//! finalization one-shot.

use std::num::NonZeroU64;
use std::sync::Arc;
use std::sync::atomic::Ordering;
use std::time::{Duration, SystemTime};

use base64::Engine as _;
use bytes::Bytes;
use futures_util::StreamExt;
use objectstore_types::metadata::Metadata;
use objectstore_types::range::ByteRange;
use objectstore_types::resumable::UploadProgress;
use objectstore_types::time::Timestamp;
use sentry::{Hub, SentryFutureExt};
use serde::{Deserialize, Serialize};

use crate::backend::changelog::{Change, ChangeGuard, ChangeLog, ChangeManager, ChangePhase};
use crate::backend::common::{
    Backend, DeleteResponse, ExpiryTarget, ExpiryUpdate, GetResponse, HighVolumeBackend,
    MetadataResponse, MultipartUploadBackend, PutResponse, SetExpiryResponse, TieredGet,
    TieredMetadata, TieredUpdate, TieredWrite, Tombstone,
};
use crate::backend::{HighVolumeStorageConfig, MultipartUploadStorageConfig};
use crate::error::{Error, ErrorKind, Result, ResultExt as _};
use crate::id::ObjectId;
use crate::multipart::{
    AbortMultipartResponse, CompleteMultipartResponse, CompletedPart, InitiateMultipartResponse,
    ListPartsResponse, PartNumber, UploadId, UploadPartResponse,
};
use crate::resumable::{BackendToken, Session};
use crate::stream::{ClientStream, SizedPeek, counting_stream};

/// The threshold up until which we will go to the "high volume" backend.
const BACKEND_SIZE_THRESHOLD: usize = 1024 * 1024; // 1 MiB

/// Fixed lifetime of an ongoing upload marker.
const RESUMABLE_UPLOAD_TTL: Duration = Duration::from_hours(5 * 24);

/// Amount of time for which a `Change` generated by a `complete_multipart` operation is kept in the `Assembling`
/// state before becoming eligible for cleanup by the `ChangeLog` recovery process.
/// This allows the client to retry the `complete_multipart` operation upon any failures for at least this long,
/// avoiding scenarios where the `ChangeLog` recovery would race to delete the assembled LT blob.
const MULTIPART_COMPLETE_CLEANUP_DELAY: Duration = Duration::from_hours(24);

/// Creates a new [`ObjectId`] with the same context but a unique revision key.
///
/// The new key has the format `{original_key}/{uuid_v7}`, producing a distinct
/// storage path for each large-object write. [`ObjectId::from_storage_path`] parses
/// the result back correctly because the key portion may contain `/`.
fn new_long_term_revision(id: &ObjectId) -> ObjectId {
    ObjectId {
        context: id.context.clone(),
        key: format!("{}/{}", id.key, uuid::Uuid::now_v7()),
    }
}

/// Configuration for [`TieredStorage`].
///
/// Composes two backends into a tiered routing setup: `high_volume` for small
/// objects and `long_term` for large objects. Nesting [`super::StorageConfig::Tiered`]
/// inside another tiered config is not supported.
///
/// # Example
///
/// ```yaml
/// storage:
///   type: tiered
///   high_volume:
///     type: bigtable
///     project_id: my-project
///     instance_name: objectstore
///     table_name: objectstore
///   long_term:
///     type: gcs
///     bucket: my-objectstore-bucket
/// ```
#[derive(Debug, Clone, Deserialize, Serialize)]
pub struct TieredStorageConfig {
    /// Backend for high-volume, small objects.
    ///
    /// Must be a backend that implements [`HighVolumeBackend`] (currently
    /// only BigTable).
    pub high_volume: HighVolumeStorageConfig,
    /// Backend for large, long-term objects.
    ///
    /// Must be a backend that implements [`MultipartUploadBackend`].
    pub long_term: MultipartUploadStorageConfig,
}

/// Two-tier storage backend that routes objects by size.
///
/// `TieredStorage` implements [`Backend`] and is intended to be used inside a
/// [`StorageService`](crate::StorageService), which wraps it with task spawning and panic
/// isolation.
///
/// # Size-Based Routing
///
/// Objects are routed at write time based on their size relative to a **1 MiB threshold**:
///
/// - Objects **≤ 1 MiB** go to the `high_volume` backend — optimized for low-latency reads
///   and writes of small objects (e.g. BigTable).
/// - Objects **> 1 MiB** go to the `long_term` backend — optimized for cost-efficient
///   storage of large objects (e.g. GCS).
/// - Resumable uploads at or below 1 MiB are declined; larger uploads go to `long_term`.
///
/// # Redirect Tombstones
///
/// Because the [`ObjectId`] is backend-independent, reads must be able to find an object
/// without knowing which backend stores it. A naive approach would check the long-term
/// backend on every read miss in the high-volume backend — but that is slow and expensive.
///
/// Instead, when an object is stored in the long-term backend, a **redirect tombstone** is
/// written in the high-volume backend. It acts as a signpost: "the real data lives in the
/// other backend at this target." On reads, a single high-volume lookup either returns the
/// object directly or follows the tombstone to long-term storage, without probing both
/// backends.
///
/// How tombstones are physically stored is determined by the [`HighVolumeBackend`]
/// implementation — refer to the backend's own documentation for storage format details.
///
/// # Consistency
///
/// Consistency across the two backends is maintained through compare-and-swap
/// operations on the high-volume backend (see
/// [`HighVolumeBackend::compare_and_write`]), not distributed locks. Each
/// mutating operation reads the current high-volume revision, performs its
/// work, and then atomically swaps the high-volume entry only if the revision
/// is still current — rolling back on conflict. Cleanup of unreferenced LT
/// blobs runs in background tasks so the caller returns as soon as the commit
/// point is reached. Call [`Backend::join`] during shutdown to wait for
/// outstanding cleanup.
///
/// See the [module-level documentation](self) for per-operation diagrams.
///
/// # Usage
///
/// `TieredStorage` handles only the routing and consistency logic. Wrap it in a
/// [`StorageService`](crate::service::StorageService) to add task spawning, panic isolation,
/// and concurrency limiting.
#[derive(Debug)]
pub struct TieredStorage {
    inner: Arc<ChangeManager>,
}

impl TieredStorage {
    /// Creates a new `TieredStorage` with the given backends and change log.
    pub fn new(
        high_volume: Box<dyn HighVolumeBackend>,
        long_term: Box<dyn MultipartUploadBackend>,
        changelog: Box<dyn ChangeLog>,
    ) -> Self {
        let inner = ChangeManager::new(high_volume, long_term, changelog);
        let hub = Hub::new_from_top(Hub::current());
        // Note on cancellation: Our `join` method will wait for all tasks tracked by the spawned
        // recovery job, so we defer shutdown until recovery is complete or times out.
        tokio::spawn(inner.clone().recover().bind_hub(hub));
        Self { inner }
    }

    /// Records the change to the log and returns a guard that cleans up on drop.
    async fn record_change(&self, change: Change) -> Result<ChangeGuard> {
        self.inner.clone().record(change).await
    }

    /// Records the change to the log in the `Assembling` phase, and returns a guard that does
    /// nothing on drop unless advanced.
    async fn record_assembling(&self, change: Change) -> Result<ChangeGuard> {
        self.inner.clone().record_assembling(change).await
    }

    /// Checks that the upload is still authorized before contacting LT.
    async fn check_upload_marker(&self, revision: &ObjectId) -> Result<()> {
        if !self
            .inner
            .high_volume
            .has_upload_marker(revision, Timestamp::now())
            .await?
        {
            return Err(ErrorKind::UploadSessionGone.into());
        }
        Ok(())
    }

    /// Consumes permission to finalize or cancel the upload.
    async fn delete_upload_marker(&self, revision: &ObjectId) -> Result<()> {
        if !self
            .inner
            .high_volume
            .delete_upload_marker(revision, Timestamp::now())
            .await?
        {
            return Err(ErrorKind::UploadSessionGone.into());
        }
        Ok(())
    }

    /// Returns the name of the backend corresponding to the given routing choice.
    fn backend_type(&self, choice: &BackendChoice) -> &'static str {
        match choice {
            BackendChoice::HighVolume => self.inner.high_volume.name(),
            BackendChoice::LongTerm => self.inner.long_term.name(),
        }
    }

    /// Puts an object into the high-volume backend.
    ///
    /// If a tombstone already exists, attempts to swap it for the new object and delete the old
    /// long-term object.
    #[tracing::instrument(level = "debug", fields(?id), skip_all)]
    async fn put_high_volume(
        &self,
        id: &ObjectId,
        metadata: &Metadata,
        payload: Bytes,
        access_time: Timestamp,
    ) -> Result<()> {
        let tombstone_opt = self
            .inner
            .high_volume
            .put_non_tombstone(id, metadata, payload.clone(), access_time)
            .await?;

        let Some(Tombstone { target, .. }) = tombstone_opt else {
            // No tombstone exists - write succeeded
            return Ok(());
        };

        // Tombstone exists — Swap it for inline data
        let mut guard = self
            .record_change(Change {
                id: id.clone(),
                new: None,
                old: Some(target.clone()),
                cleanup_after: None,
            })
            .await?;

        let write = TieredWrite::Object(metadata.clone(), payload);
        guard.advance(ChangePhase::Written);

        let written = self
            .inner
            .high_volume
            .compare_and_write(id, Some(&target), write, access_time)
            .await?;

        // Update guard and let it schedule cleanup in the background.
        guard.advance(ChangePhase::compare_and_write(written));

        Ok(())
    }

    /// Puts an object into the long-term backend with a redirect tombstone in front.
    ///
    /// Deletes the previous long-term object if overwriting an existing tombstone. If the tombstone
    /// write fails, the new long-term object is cleaned up.
    #[tracing::instrument(level = "debug", fields(?id), skip_all)]
    async fn put_long_term(
        &self,
        id: &ObjectId,
        metadata: &Metadata,
        stream: ClientStream,
        access_time: Timestamp,
    ) -> Result<()> {
        // 1. Read current HV revision to establish the write precondition
        let current = match self
            .inner
            .high_volume
            .get_tiered_metadata(id, access_time)
            .await?
        {
            TieredMetadata::Tombstone(t) => Some(t.target),
            _ => None,
        };

        // 2. Write payload to long-term at a unique revision key.
        let new = new_long_term_revision(id);
        let mut guard = self
            .record_change(Change {
                id: id.clone(),
                new: Some(new.clone()),
                old: current.clone(),
                cleanup_after: None,
            })
            .await?;

        self.inner
            .long_term
            .put_object(&new, metadata, stream, access_time)
            .await?;
        guard.advance(ChangePhase::Written);

        // 3. CAS commit: write tombstone only if HV state matches what we saw.
        let tombstone = Tombstone {
            target: new.clone(),
            time_expires: metadata.time_expires,
        };
        let written = self
            .inner
            .high_volume
            .compare_and_write(
                id,
                current.as_ref(),
                TieredWrite::Tombstone(tombstone),
                access_time,
            )
            .await?;

        // Update guard and let it schedule cleanup in the background.
        guard.advance(ChangePhase::compare_and_write(written));

        Ok(())
    }
}

type LongTermBackendToken = BackendToken;

#[derive(Debug, Serialize, Deserialize)]
struct TieredResumableToken {
    inner: LongTermBackendToken,
    revision: String,
    time_expires: Option<Timestamp>,
}

impl TieredResumableToken {
    fn decode(token: &BackendToken) -> Result<Self> {
        serde_json::from_str(token).map_err(|_| ErrorKind::UnknownUploadSession.into())
    }

    /// Builds the long-term session with the revision ID and inner token, retaining shared fields.
    fn into_inner_session(self, session: &Session) -> Session {
        Session {
            object_id: ObjectId {
                context: session.object_id.context.clone(),
                key: self.revision,
            },
            backend_token: self.inner,
            ..session.clone()
        }
    }
}

#[async_trait::async_trait]
impl Backend for TieredStorage {
    fn name(&self) -> &'static str {
        "tiered"
    }

    fn upload_granularity(&self) -> u64 {
        self.inner.long_term.upload_granularity()
    }

    fn as_multipart_upload_backend(&self) -> Result<&dyn MultipartUploadBackend> {
        Ok(self)
    }

    #[tracing::instrument(level = "debug", fields(?id, upload_length), skip_all)]
    async fn create_upload_session(
        &self,
        id: &ObjectId,
        metadata: &Metadata,
        upload_length: NonZeroU64,
    ) -> Result<Option<BackendToken>> {
        if upload_length.get() <= BACKEND_SIZE_THRESHOLD as u64 {
            return Ok(None);
        }

        let revision = new_long_term_revision(id);
        let Some(inner) = self
            .inner
            .long_term
            .create_upload_session(&revision, metadata, upload_length)
            .await?
        else {
            return Ok(None);
        };

        if let Err(error) = self
            .inner
            .high_volume
            .create_upload_marker(&revision, Timestamp::now() + RESUMABLE_UPLOAD_TTL)
            .await
        {
            // Best-effort clean-up.
            let session = Session {
                object_id: revision,
                upload_length,
                backend_token: inner,
            };
            if let Err(cleanup_error) = self.inner.long_term.cancel_upload(&session).await {
                objectstore_log::warn!(
                    !!&cleanup_error,
                    "Failed to cancel upload after marker creation failed"
                );
            }
            return Err(error);
        }
        let token = TieredResumableToken {
            revision: revision.key,
            inner,
            time_expires: metadata.time_expires,
        };
        Ok(Some(serde_json::to_string(&token).context(
            ErrorKind::Internal,
            "encoding tiered resumable session",
        )?))
    }

    #[tracing::instrument(level = "debug", fields(?session, offset, content_length), skip_all)]
    async fn put_chunk(
        &self,
        session: &Session,
        offset: u64,
        content_length: u64,
        stream: ClientStream,
    ) -> Result<UploadProgress> {
        let tiered = TieredResumableToken::decode(&session.backend_token)?;
        let time_expires = tiered.time_expires;
        let inner_session = tiered.into_inner_session(session);
        let id = &session.object_id;
        let revision = &inner_session.object_id;
        let end = offset
            .checked_add(content_length)
            .filter(|end| *end <= session.upload_length.get())
            .ok_or(ErrorKind::ChunkExceedsUploadLength {
                offset,
                content_length,
                upload_length: session.upload_length.get(),
            })?;

        let granularity = self.upload_granularity();
        if content_length > 0 && content_length < granularity && end != session.upload_length.get()
        {
            return Err(ErrorKind::ChunkTooSmall {
                chunk_length: content_length,
                upload_granularity: granularity,
            }
            .into());
        }

        // Non-final request; just forward the chunk.
        if end != session.upload_length.get() {
            let progress = self
                .inner
                .long_term
                .put_chunk(&inner_session, offset, content_length, stream)
                .await?;
            return match progress {
                UploadProgress::Incomplete { .. } => Ok(progress),
                UploadProgress::Complete => Err(ErrorKind::UploadSessionGone.into()),
            };
        }

        // Read the publication precondition while verifying the LT offset.
        let (progress, current) = tokio::join!(
            self.inner.long_term.upload_offset(&inner_session),
            self.inner
                .high_volume
                .get_tiered_metadata(id, Timestamp::now()),
        );
        match progress? {
            UploadProgress::Complete => return Err(ErrorKind::UploadSessionGone.into()),
            UploadProgress::Incomplete { offset: actual } if actual < offset => {
                return Err(ErrorKind::UploadOffsetMismatch { offset: actual }.into());
            }
            UploadProgress::Incomplete { .. } => {}
        }
        let current = match current? {
            TieredMetadata::Tombstone(t) if t.target == *revision => {
                return Ok(UploadProgress::Complete);
            }
            TieredMetadata::Tombstone(t) => Some(t.target),
            _ => None,
        };

        // Delete the marker to claim this upload.
        self.delete_upload_marker(revision).await?;

        // Follow the regular PUT flow now that this revision has a single owner.
        let mut guard = self
            .record_change(Change {
                id: id.clone(),
                new: Some(revision.clone()),
                old: current.clone(),
                cleanup_after: None,
            })
            .await?;

        let progress = self
            .inner
            .long_term
            .put_chunk(&inner_session, offset, content_length, stream)
            .await?;
        if progress != UploadProgress::Complete {
            return Err(ErrorKind::UploadSessionGone.into());
        }
        guard.advance(ChangePhase::Written);

        let written = self
            .inner
            .high_volume
            .compare_and_write(
                id,
                current.as_ref(),
                TieredWrite::Tombstone(Tombstone {
                    target: revision.clone(),
                    time_expires,
                }),
                Timestamp::now(),
            )
            .await?;
        guard.advance(ChangePhase::compare_and_write(written));
        Ok(UploadProgress::Complete)
    }

    #[tracing::instrument(level = "debug", fields(?session), skip_all)]
    async fn upload_offset(&self, session: &Session) -> Result<UploadProgress> {
        let tiered = TieredResumableToken::decode(&session.backend_token)?;
        let inner_session = tiered.into_inner_session(session);
        self.check_upload_marker(&inner_session.object_id).await?;
        match self.inner.long_term.upload_offset(&inner_session).await? {
            UploadProgress::Incomplete { offset } => Ok(UploadProgress::Incomplete { offset }),
            UploadProgress::Complete => Err(ErrorKind::UploadSessionGone.into()),
        }
    }

    #[tracing::instrument(level = "debug", fields(?session), skip_all)]
    async fn cancel_upload(&self, session: &Session) -> Result<()> {
        let tiered = TieredResumableToken::decode(&session.backend_token)?;
        let inner_session = tiered.into_inner_session(session);
        self.delete_upload_marker(&inner_session.object_id).await?;
        if let Err(error) = self.inner.long_term.cancel_upload(&inner_session).await {
            objectstore_log::warn!(!!&error, "Failed to cancel upload after deleting marker");
        }
        Ok(())
    }

    #[tracing::instrument(level = "debug", fields(?id), skip_all)]
    async fn put_object(
        &self,
        id: &ObjectId,
        metadata: &Metadata,
        stream: ClientStream,
        access_time: Timestamp,
    ) -> Result<PutResponse> {
        let timer = objectstore_metrics::timer!("put.latency", usecase = id.usecase().to_owned());
        if metadata.origin.is_none() {
            objectstore_metrics::count!("put.origin_missing", usecase = id.usecase().to_owned());
        }

        let peeked = SizedPeek::new(stream, BACKEND_SIZE_THRESHOLD).await?;
        objectstore_metrics::record!(
            "put.first_chunk.latency" = timer.elapsed(),
            usecase = id.usecase().to_owned(),
            complete = if peeked.is_exhausted() { "yes" } else { "no" },
        );

        let (backend_choice, stored_size) = if peeked.is_exhausted() {
            let payload = peeked.into_bytes().await?;
            let payload_len = payload.len() as u64;
            self.put_high_volume(id, metadata, payload, access_time)
                .await?;
            (BackendChoice::HighVolume, payload_len)
        } else {
            let (stored_size, stream) = counting_stream(peeked.into_stream());
            self.put_long_term(id, metadata, stream.boxed(), access_time)
                .await?;
            (BackendChoice::LongTerm, stored_size.load(Ordering::Acquire))
        };

        let backend_ty = self.backend_type(&backend_choice);
        timer
            .tag("backend_choice", backend_choice.as_str())
            .tag("backend_type", backend_ty)
            .record();
        objectstore_metrics::record!(
            "put.size" = stored_size,
            usecase = id.usecase().to_owned(),
            backend_choice = backend_choice.as_str(),
            backend_type = backend_ty,
            upload_type = "direct",
        );

        Ok(())
    }

    #[tracing::instrument(level = "debug", skip(self))]
    async fn get_object(
        &self,
        id: &ObjectId,
        access_time: Timestamp,
        range: Option<ByteRange>,
    ) -> Result<GetResponse> {
        let timer = objectstore_metrics::timer!(
            "get.latency.pre-response",
            usecase = id.usecase().to_owned(),
        );

        let hv_result = self
            .inner
            .high_volume
            .get_tiered_object(id, access_time, range)
            .await?;
        let (result, backend_choice) = match hv_result {
            TieredGet::NotFound => (None, BackendChoice::HighVolume),
            TieredGet::Object(metadata, content_range, stream) => (
                Some((metadata, content_range, stream)),
                BackendChoice::HighVolume,
            ),
            TieredGet::Tombstone(tombstone) => (
                self.inner
                    .long_term
                    .get_object(&tombstone.target, access_time, range)
                    .await?
                    .map(|(meta, range, stream)| (align_expiry(meta, &tombstone), range, stream)),
                BackendChoice::LongTerm,
            ),
        };

        let backend_type = self.backend_type(&backend_choice);
        timer
            .tag("backend_choice", backend_choice.as_str())
            .tag("backend_type", backend_type)
            .record();

        if let Some((ref metadata, ref content_range, _)) = result {
            let size = content_range.map(|cr| cr.len() as usize).or(metadata.size);
            if let Some(size) = size {
                objectstore_metrics::record!(
                    "get.size" = size,
                    usecase = id.usecase().to_owned(),
                    backend_choice = backend_choice.as_str(),
                    backend_type = backend_type,
                );
            }
        }

        Ok(result)
    }

    #[tracing::instrument(level = "debug", skip(self))]
    async fn get_metadata(
        &self,
        id: &ObjectId,
        access_time: Timestamp,
    ) -> Result<MetadataResponse> {
        let timer = objectstore_metrics::timer!("head.latency", usecase = id.usecase().to_owned());

        let hv_result = self
            .inner
            .high_volume
            .get_tiered_metadata(id, access_time)
            .await?;
        let (result, backend_choice) = match hv_result {
            TieredMetadata::NotFound => (None, BackendChoice::HighVolume),
            TieredMetadata::Object(metadata) => (Some(metadata), BackendChoice::HighVolume),
            TieredMetadata::Tombstone(tombstone) => (
                self.inner
                    .long_term
                    .get_metadata(&tombstone.target, access_time)
                    .await?
                    .map(|metadata| align_expiry(metadata, &tombstone)),
                BackendChoice::LongTerm,
            ),
        };

        timer
            .tag("backend_choice", backend_choice.as_str())
            .tag("backend_type", self.backend_type(&backend_choice))
            .record();

        Ok(result)
    }

    async fn set_expiry(
        &self,
        id: &ObjectId,
        target: ExpiryUpdate,
        access_time: Timestamp,
    ) -> Result<SetExpiryResponse> {
        match self
            .inner
            .high_volume
            .get_tiered_metadata(id, access_time)
            .await?
        {
            TieredMetadata::NotFound => Ok(SetExpiryResponse::NotFound),
            TieredMetadata::Object(_) => {
                self.inner
                    .high_volume
                    .compare_and_update(id, None, TieredUpdate::SetExpiry(target), access_time)
                    .await
            }
            TieredMetadata::Tombstone(tombstone) => {
                // Extend LT first. Extending the redirect first could leave it
                // alive after the blob failed to extend and was reclaimed.
                let deadline = match self
                    .inner
                    .long_term
                    .set_expiry(&tombstone.target, target, access_time)
                    .await?
                {
                    SetExpiryResponse::Satisfied(deadline) => deadline,
                    outcome @ (SetExpiryResponse::NotFound | SetExpiryResponse::Rejected) => {
                        return Ok(outcome);
                    }
                };

                // Limits have already been validated at the authoritative LT object.
                let update = TieredUpdate::SetExpiry(ExpiryTarget::At(deadline).into());

                // NOTE: If this fails, LT may remain extended while the redirect
                // becomes unreachable earlier. Rolling LT back could interfere
                // with another renewal that succeeded concurrently. Propagate
                // the resolved request, not LT's stored deadline, so an
                // already-later blob cannot over-extend the redirect.
                self.inner
                    .high_volume
                    .compare_and_update(id, Some(&tombstone.target), update, access_time)
                    .await
            }
        }
    }

    #[tracing::instrument(level = "debug", skip(self))]
    async fn delete_object(&self, id: &ObjectId, access_time: Timestamp) -> Result<DeleteResponse> {
        let timer =
            objectstore_metrics::timer!("delete.latency", usecase = id.usecase().to_owned());

        let mut backend_choice = BackendChoice::HighVolume;

        if let Some(tombstone) = self
            .inner
            .high_volume
            .delete_non_tombstone(id, access_time)
            .await?
        {
            backend_choice = BackendChoice::LongTerm;

            let mut guard = self
                .record_change(Change {
                    id: id.clone(),
                    new: None,
                    old: Some(tombstone.target.clone()),
                    cleanup_after: None,
                })
                .await?;
            guard.advance(ChangePhase::Written);

            // Remove the tombstone; the LT blob becomes unreachable at this point.
            let deleted = self
                .inner
                .high_volume
                .compare_and_write(
                    id,
                    Some(&tombstone.target),
                    TieredWrite::Delete,
                    access_time,
                )
                .await?;

            // Update guard and let it schedule cleanup in the background.
            guard.advance(ChangePhase::compare_and_write(deleted));
        }

        timer
            .tag("backend_choice", backend_choice.as_str())
            .tag("backend_type", self.backend_type(&backend_choice))
            .record();

        Ok(())
    }

    async fn join(&self) {
        self.inner.tracker.close();
        tokio::join!(
            self.inner.high_volume.join(),
            self.inner.long_term.join(),
            self.inner.tracker.wait()
        );
    }
}

#[derive(Debug)]
enum BackendChoice {
    HighVolume,
    LongTerm,
}

impl BackendChoice {
    fn as_str(&self) -> &'static str {
        match self {
            BackendChoice::HighVolume => "high-volume",
            BackendChoice::LongTerm => "long-term",
        }
    }
}

impl std::fmt::Display for BackendChoice {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_str(self.as_str())
    }
}

/// Returns the lower expiry between the redirect and blob, if any.
///
/// This is used to ensure correct expiry if they ever drift.
fn effective_expiry(
    redirect_expiry: Option<Timestamp>,
    blob_expiry: Option<Timestamp>,
) -> Option<Timestamp> {
    match (redirect_expiry, blob_expiry) {
        (Some(redirect), Some(blob)) => Some(redirect.min(blob)),
        (Some(expiry), None) | (None, Some(expiry)) => Some(expiry),
        (None, None) => None,
    }
}

/// Aligns the expiry of the metadata with the expiry of the tombstone.
///
/// Keeps the lower expiry between the metadata and the tombstone so that the client sees the most
/// conservative expiry and automatic expiry bumps still occur.
fn align_expiry(mut metadata: Metadata, tombstone: &Tombstone) -> Metadata {
    metadata.time_expires = effective_expiry(tombstone.time_expires, metadata.time_expires);
    metadata
}

/// The multipart upload state for TieredStorage.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
struct TieredUploadId {
    revision: String,
    upload_id: UploadId,
}

impl TryInto<UploadId> for TieredUploadId {
    type Error = Error;

    fn try_into(self) -> Result<UploadId, Self::Error> {
        let json =
            serde_json::to_vec(&self).context(ErrorKind::Internal, "encoding tiered upload ID")?;
        Ok(UploadId::new(
            base64::engine::general_purpose::URL_SAFE_NO_PAD.encode(json),
        )?)
    }
}

impl TryFrom<&UploadId> for TieredUploadId {
    type Error = Error;

    fn try_from(value: &UploadId) -> Result<Self, Self::Error> {
        let json = base64::engine::general_purpose::URL_SAFE_NO_PAD
            .decode(value.as_bytes())
            .kind(ErrorKind::InvalidUploadId)?;
        serde_json::from_slice(&json).kind(ErrorKind::InvalidUploadId)
    }
}

#[async_trait::async_trait]
impl MultipartUploadBackend for TieredStorage {
    #[tracing::instrument(level = "debug", fields(?id), skip_all)]
    async fn initiate_multipart(
        &self,
        id: &ObjectId,
        metadata: &Metadata,
    ) -> Result<InitiateMultipartResponse> {
        let timer = objectstore_metrics::timer!(
            "multipart.initiate.latency",
            usecase = id.usecase().to_owned(),
        );
        let physical = new_long_term_revision(id);

        let upload_id = self
            .inner
            .long_term
            .initiate_multipart(&physical, metadata)
            .await?;

        let id = TieredUploadId {
            revision: physical.key,
            upload_id,
        };
        let id = id.try_into()?;

        timer.record();
        Ok(id)
    }

    #[tracing::instrument(level = "debug", fields(?id, part_number, content_length), skip_all)]
    async fn upload_part(
        &self,
        id: &ObjectId,
        upload_id: &UploadId,
        part_number: PartNumber,
        content_length: u64,
        content_md5: Option<&str>,
        body: ClientStream,
    ) -> Result<UploadPartResponse> {
        let timer = objectstore_metrics::timer!(
            "multipart.upload_part.latency",
            usecase = id.usecase().to_owned(),
        );
        let tiered: TieredUploadId = upload_id.try_into()?;

        let physical = ObjectId {
            context: id.context.clone(),
            key: tiered.revision,
        };

        let etag = self
            .inner
            .long_term
            .upload_part(
                &physical,
                &tiered.upload_id,
                part_number,
                content_length,
                content_md5,
                body,
            )
            .await?;

        timer.record();
        objectstore_metrics::record!(
            "multipart.upload_part.size" = content_length,
            usecase = id.usecase().to_owned(),
        );

        Ok(etag)
    }

    #[tracing::instrument(level = "debug", skip(self, upload_id))]
    async fn list_parts(
        &self,
        id: &ObjectId,
        upload_id: &UploadId,
        max_parts: Option<u32>,
        part_number_marker: Option<PartNumber>,
    ) -> Result<ListPartsResponse> {
        let timer = objectstore_metrics::timer!(
            "multipart.list_parts.latency",
            usecase = id.usecase().to_owned(),
        );
        let tiered: TieredUploadId = upload_id.try_into()?;

        let physical = ObjectId {
            context: id.context.clone(),
            key: tiered.revision,
        };

        let response = self
            .inner
            .long_term
            .list_parts(&physical, &tiered.upload_id, max_parts, part_number_marker)
            .await?;

        timer.record();
        Ok(response)
    }

    #[tracing::instrument(level = "debug", fields(?id), skip_all)]
    async fn abort_multipart(
        &self,
        id: &ObjectId,
        upload_id: &UploadId,
    ) -> Result<AbortMultipartResponse> {
        let timer = objectstore_metrics::timer!(
            "multipart.abort.latency",
            usecase = id.usecase().to_owned(),
        );
        let tiered: TieredUploadId = upload_id.try_into()?;

        let physical = ObjectId {
            context: id.context.clone(),
            key: tiered.revision,
        };

        let () = self
            .inner
            .long_term
            .abort_multipart(&physical, &tiered.upload_id)
            .await?;

        timer.record();
        Ok(())
    }

    #[tracing::instrument(level = "debug", fields(?id), skip_all)]
    async fn complete_multipart(
        &self,
        id: &ObjectId,
        upload_id: &UploadId,
        parts: Vec<CompletedPart>,
        access_time: Timestamp,
    ) -> Result<CompleteMultipartResponse> {
        let timer = objectstore_metrics::timer!(
            "multipart.complete.latency",
            usecase = id.usecase().to_owned(),
        );
        let part_count = parts.len();
        let tiered: TieredUploadId = upload_id.try_into()?;

        let physical = ObjectId {
            context: id.context.clone(),
            key: tiered.revision,
        };

        // 1. Read current HV revision to establish the write precondition.
        let current = match self
            .inner
            .high_volume
            .get_tiered_metadata(id, access_time)
            .await?
        {
            // Optimization: a previous attempt already finalized this revision and tombstone -- report success.
            TieredMetadata::Tombstone(t) if t.target == physical => {
                timer.record();
                return Ok(None);
            }
            TieredMetadata::Tombstone(t) => Some(t.target),
            _ => None,
        };

        // Register a guard with cleanup deferred to now + `MULTIPART_COMPLETE_CLEANUP_DELAY`,
        // so that the user has the chance to retry finalizing the upload in this timeframe.
        let mut guard = self
            .record_assembling(Change {
                id: id.clone(),
                new: Some(physical.clone()),
                old: current.clone(),
                cleanup_after: Some(SystemTime::now() + MULTIPART_COMPLETE_CLEANUP_DELAY),
            })
            .await?;

        // 2. Complete the upload, creating the object at the given revision key.
        let maybe_complete_multipart_err = match self
            .inner
            .long_term
            .complete_multipart(&physical, &tiered.upload_id, parts, access_time)
            .await
        {
            // The request went through but we got an error in the response body.
            // Transparently proxy the error to the user.
            Ok(error) => {
                if error.is_some() {
                    return Ok(error);
                }
                None
            }
            // We got status 4xx/5xx, or a network error.
            // Either way, `complete_multipart` might have been completed successfully,
            // either now or in a previous attempt (in that case, that's a 404 and we indeed end up
            // here).
            // We cannot know if that's the case yet, so we continue to the next steps.
            Err(err) => Some(err),
        };

        // 3. Retrieve the metadata of the object, which was determined at initiation time, to
        //    get its expiration deadline and size.
        //
        //    This also serves as an existence check to understand if the LT revision was actually
        //    created successfully in this or a previous attempt, in which case we just need to
        //    finalize the tombstone.
        let metadata = self
            .inner
            .long_term
            .get_metadata(&physical, access_time)
            .await;

        let metadata = match (metadata, maybe_complete_multipart_err) {
            // The LT revision already exists, so we can continue to finalize the tombstone.
            (Ok(Some(metadata)), _) => metadata,
            // The LT revision doesn't exist, cannot proceed.
            (Ok(None), Some(err)) => return Err(err),
            // The `complete_multipart` succeeded, creating the object, but the `get_metadata`
            // immediately after failed to find the object. This should never happen.
            (Ok(None), None) => {
                objectstore_log::error!(
                    id = ?id,
                    upload_id = ?upload_id,
                    physical = ?physical,
                    "complete_multipart call succeeded on long_term backend, but subsequent get_metadata found no object"
                );
                return Err(Error::new(
                    ErrorKind::BackendFailure,
                    "tiered multipart object missing from long-term storage",
                ));
            }
            // Failed to `get_metadata`, cannot proceed.
            (Err(get_metadata_err), maybe_complete_multipart_err) => {
                // Prefer the `complete_multipart_err`, as it's likely more informative.
                // TODO(FS-358): convert this properly. Right now `ApiErrorResponse` will turn this into a 500,
                // but we would actually want to transparently surface the original status (and message?) instead.
                return Err(maybe_complete_multipart_err.unwrap_or(get_metadata_err));
            }
        };

        // 4. CAS commit: write tombstone only if HV state matches what we saw.
        let tombstone = Tombstone {
            target: physical.clone(),
            time_expires: metadata.time_expires,
        };
        let written = self
            .inner
            .high_volume
            .compare_and_write(
                id,
                current.as_ref(),
                TieredWrite::Tombstone(tombstone),
                access_time,
            )
            .await?;

        // Update guard and let it schedule cleanup in the background.
        guard.advance(ChangePhase::compare_and_write(written));

        timer.record();
        objectstore_metrics::record!(
            "multipart.complete.part_count" = part_count as u64,
            usecase = id.usecase().to_owned(),
        );
        if let Some(size) = metadata.size {
            objectstore_metrics::record!(
                "put.size" = size as u64,
                usecase = id.usecase().to_owned(),
                backend_choice = BackendChoice::LongTerm.as_str(),
                backend_type = self.backend_type(&BackendChoice::LongTerm),
                upload_type = "multipart",
            );
        }

        Ok(None)
    }
}

#[cfg(test)]
mod tests {
    use std::num::{NonZeroU32, NonZeroU64};
    use std::sync::Mutex as StdMutex;

    use futures::lock::Mutex;
    use objectstore_types::metadata::{ExpirationPolicy, Metadata};
    use objectstore_types::scope::{Scope, Scopes};

    use super::*;
    use crate::backend::bigtable::{BigTableBackend, BigTableConfig};
    use crate::backend::changelog::{InMemoryChangeLog, NoopChangeLog};
    use crate::backend::gcs::{GcsBackend, GcsConfig};
    use crate::backend::in_memory::InMemoryBackend;
    use crate::backend::testing::{Hooks, TestBackend};
    use crate::change_stream::ChangeStreamFactory;
    use crate::error::Error;
    use crate::id::ObjectContext;
    use crate::stream::{self, ClientStream};

    fn make_context() -> ObjectContext {
        ObjectContext {
            usecase: "testing".into(),
            scopes: Scopes::from_iter([Scope::create("testing", "value").unwrap()]),
        }
    }

    fn make_id(key: &str) -> ObjectId {
        ObjectId::new(make_context(), key.into())
    }

    fn make_tiered_storage() -> (
        TieredStorage,
        InMemoryBackend,
        InMemoryBackend,
        InMemoryChangeLog,
    ) {
        let hv = InMemoryBackend::new("in-memory-hv");
        let lt = InMemoryBackend::new("in-memory-lt");
        let changelog = InMemoryChangeLog::default();
        let storage = TieredStorage::new(
            Box::new(hv.clone()),
            Box::new(lt.clone()),
            Box::new(changelog.clone()),
        );
        (storage, hv, lt, changelog)
    }

    async fn resumable_token(
        storage: &TieredStorage,
        id: &ObjectId,
        metadata: &Metadata,
        length: u64,
    ) -> Session {
        let backend_token = storage
            .create_upload_session(id, metadata, NonZeroU64::new(length).unwrap())
            .await
            .unwrap()
            .unwrap();
        Session {
            object_id: id.clone(),
            upload_length: NonZeroU64::new(length).unwrap(),
            backend_token,
        }
    }

    fn upload_revision(session: &Session) -> ObjectId {
        TieredResumableToken::decode(&session.backend_token)
            .unwrap()
            .into_inner_session(session)
            .object_id
    }

    #[tokio::test]
    async fn resumable_inmemory() -> anyhow::Result<()> {
        let (storage, _, _, _) = make_tiered_storage();
        let id = make_id("tiered-resumable-inmemory");
        let payload = vec![b'a'; BACKEND_SIZE_THRESHOLD + 1];
        let token =
            resumable_token(&storage, &id, &Metadata::default(), payload.len() as u64).await;

        let revision = upload_revision(&token);
        assert!(
            storage
                .inner
                .high_volume
                .has_upload_marker(&revision, Timestamp::now())
                .await?
        );
        assert_eq!(
            storage.upload_offset(&token).await?,
            UploadProgress::Incomplete { offset: 0 }
        );
        let split = 256 * 1024;
        assert_eq!(
            storage
                .put_chunk(
                    &token,
                    0,
                    split as u64,
                    stream::single(payload[..split].to_vec())
                )
                .await?,
            UploadProgress::Incomplete {
                offset: split as u64
            }
        );
        assert!(
            storage
                .inner
                .high_volume
                .has_upload_marker(&revision, Timestamp::now())
                .await?
        );
        assert_eq!(
            storage.upload_offset(&token).await?,
            UploadProgress::Incomplete {
                offset: split as u64
            }
        );
        assert!(storage.get_metadata(&id, Timestamp::now()).await?.is_none());

        // A completed upload creates a logical object.
        assert_eq!(
            storage
                .put_chunk(
                    &token,
                    split as u64,
                    (payload.len() - split) as u64,
                    stream::single(payload[split..].to_vec())
                )
                .await?,
            UploadProgress::Complete
        );
        assert!(
            !storage
                .inner
                .high_volume
                .has_upload_marker(&revision, Timestamp::now())
                .await?
        );
        assert_eq!(
            storage.upload_offset(&token).await.unwrap_err().kind(),
            ErrorKind::UploadSessionGone
        );
        let (_, _, body) = storage
            .get_object(&id, Timestamp::now(), None)
            .await?
            .unwrap();
        assert_eq!(stream::read_to_vec(body).await?, payload);
        Ok(())
    }

    #[tokio::test]
    async fn resumable_bigtable_and_gcs() -> anyhow::Result<()> {
        let streams = ChangeStreamFactory::default();
        let lt = GcsBackend::new(
            GcsConfig {
                endpoint: Some("http://localhost:8087".into()),
                bucket: "test-bucket".into(),
                cogs: None,
            },
            &streams,
        )
        .await?;
        let hv = BigTableBackend::new(
            BigTableConfig {
                endpoint: Some("localhost:8086".into()),
                project_id: "testing".into(),
                instance_name: "objectstore".into(),
                table_name: "objectstore".into(),
                connections: None,
                rpc_timeout: Duration::from_secs(2),
                cogs: None,
            },
            &streams,
        )
        .await?;
        let storage = TieredStorage::new(Box::new(hv), Box::new(lt), Box::new(NoopChangeLog));
        let id = make_id(&format!("tiered-resumable-{}", uuid::Uuid::now_v7()));
        let payload = vec![b'a'; BACKEND_SIZE_THRESHOLD + 1];
        let token =
            resumable_token(&storage, &id, &Metadata::default(), payload.len() as u64).await;

        let error = storage
            .put_chunk(&token, 0, 1, stream::single("a"))
            .await
            .unwrap_err();
        assert_eq!(
            error.kind(),
            ErrorKind::ChunkTooSmall {
                chunk_length: 1,
                upload_granularity: 256 * 1024,
            }
        );

        let revision = upload_revision(&token);
        assert!(
            storage
                .inner
                .high_volume
                .has_upload_marker(&revision, Timestamp::now())
                .await?
        );
        assert_eq!(
            storage.upload_offset(&token).await?,
            UploadProgress::Incomplete { offset: 0 }
        );
        let split = 256 * 1024;
        assert_eq!(
            storage
                .put_chunk(
                    &token,
                    0,
                    split as u64,
                    stream::single(payload[..split].to_vec())
                )
                .await?,
            UploadProgress::Incomplete {
                offset: split as u64
            }
        );
        assert!(
            storage
                .inner
                .high_volume
                .has_upload_marker(&revision, Timestamp::now())
                .await?
        );
        assert_eq!(
            storage.upload_offset(&token).await?,
            UploadProgress::Incomplete {
                offset: split as u64
            }
        );
        assert!(storage.get_metadata(&id, Timestamp::now()).await?.is_none());

        // A completed upload creates a logical object.
        assert_eq!(
            storage
                .put_chunk(
                    &token,
                    split as u64,
                    (payload.len() - split) as u64,
                    stream::single(payload[split..].to_vec())
                )
                .await?,
            UploadProgress::Complete
        );
        assert!(
            !storage
                .inner
                .high_volume
                .has_upload_marker(&revision, Timestamp::now())
                .await?
        );
        assert_eq!(
            storage.upload_offset(&token).await.unwrap_err().kind(),
            ErrorKind::UploadSessionGone
        );
        let (_, _, body) = storage
            .get_object(&id, Timestamp::now(), None)
            .await?
            .unwrap();
        assert_eq!(stream::read_to_vec(body).await?, payload);
        Ok(())
    }

    #[tokio::test]
    async fn resumable_invalid_chunks() {
        let (storage, _, _, _) = make_tiered_storage();
        let id = make_id("resumable-invalid");
        let length = BACKEND_SIZE_THRESHOLD as u64 + 1;
        let token = resumable_token(&storage, &id, &Metadata::default(), length).await;

        // Overflow and future offsets are rejected.
        assert_eq!(
            storage
                .put_chunk(&token, u64::MAX, 1, stream::single("x"))
                .await
                .unwrap_err()
                .kind(),
            ErrorKind::ChunkExceedsUploadLength {
                offset: u64::MAX,
                content_length: 1,
                upload_length: length
            }
        );
        assert_eq!(
            storage
                .put_chunk(&token, length - 1, 1, stream::single("x"))
                .await
                .unwrap_err()
                .kind(),
            ErrorKind::UploadOffsetMismatch { offset: 0 }
        );
    }

    #[tokio::test]
    async fn resumable_cancel() {
        let (storage, hv, _, _) = make_tiered_storage();
        let id = make_id("resumable-invalid");
        let token = resumable_token(
            &storage,
            &id,
            &Metadata::default(),
            BACKEND_SIZE_THRESHOLD as u64 + 1,
        )
        .await;

        let revision = upload_revision(&token);
        assert!(
            hv.has_upload_marker(&revision, Timestamp::now())
                .await
                .unwrap()
        );
        storage.cancel_upload(&token).await.unwrap();
        assert!(
            !hv.has_upload_marker(&revision, Timestamp::now())
                .await
                .unwrap()
        );
        assert_eq!(
            storage.cancel_upload(&token).await.unwrap_err().kind(),
            ErrorKind::UploadSessionGone
        );
        assert_eq!(
            storage.upload_offset(&token).await.unwrap_err().kind(),
            ErrorKind::UploadSessionGone
        );
        assert!(!hv.contains(&id));
    }

    #[derive(Clone, Debug)]
    struct ExpiryHook {
        label: &'static str,
        events: Arc<StdMutex<Vec<&'static str>>>,
        reject: bool,
    }

    type ExpiryTestStorage = (
        TieredStorage,
        TestBackend<ExpiryHook>,
        TestBackend<ExpiryHook>,
        Arc<StdMutex<Vec<&'static str>>>,
    );

    #[async_trait::async_trait]
    impl Hooks for ExpiryHook {
        async fn set_expiry(
            &self,
            inner: &InMemoryBackend,
            id: &ObjectId,
            target: ExpiryUpdate,
            access_time: Timestamp,
        ) -> Result<SetExpiryResponse> {
            self.events.lock().unwrap().push(self.label);
            if self.reject {
                Ok(SetExpiryResponse::Rejected)
            } else {
                inner.set_expiry(id, target, access_time).await
            }
        }

        async fn compare_and_update(
            &self,
            inner: &InMemoryBackend,
            id: &ObjectId,
            current: Option<&ObjectId>,
            update: TieredUpdate,
            access_time: Timestamp,
        ) -> Result<SetExpiryResponse> {
            self.events.lock().unwrap().push(self.label);
            if self.reject {
                Ok(SetExpiryResponse::Rejected)
            } else {
                inner
                    .compare_and_update(id, current, update, access_time)
                    .await
            }
        }
    }

    fn tiered_with_expiry_hooks(hv_reject: bool, lt_reject: bool) -> ExpiryTestStorage {
        let events = Arc::new(StdMutex::new(Vec::new()));
        let hv = TestBackend::new(ExpiryHook {
            label: "hv",
            events: Arc::clone(&events),
            reject: hv_reject,
        });
        let lt = TestBackend::new(ExpiryHook {
            label: "lt",
            events: Arc::clone(&events),
            reject: lt_reject,
        });
        let storage = TieredStorage::new(
            Box::new(hv.clone()),
            Box::new(lt.clone()),
            Box::new(NoopChangeLog),
        );
        (storage, hv, lt, events)
    }

    async fn seed_redirect(
        hv: &InMemoryBackend,
        lt: &InMemoryBackend,
        id: &ObjectId,
        target: &ObjectId,
        expiry: Timestamp,
    ) {
        let metadata = Metadata {
            expiration_policy: ExpirationPolicy::TimeToLive(Duration::from_mins(10)),
            time_created: expiry.checked_sub(Duration::from_mins(10)),
            time_expires: Some(expiry),
            ..Default::default()
        };
        lt.put_object(
            target,
            &metadata,
            stream::single("payload"),
            Timestamp::now(),
        )
        .await
        .unwrap();
        hv.compare_and_write(
            id,
            None,
            TieredWrite::Tombstone(Tombstone {
                target: target.clone(),
                time_expires: metadata.time_expires,
            }),
            Timestamp::now(),
        )
        .await
        .unwrap();
    }

    #[tokio::test]
    async fn set_expiry() {
        let (storage, hv, lt, events) = tiered_with_expiry_hooks(false, false);
        let id = make_id("tiered-expiry-order");
        let target = new_long_term_revision(&id);
        let old_expiry = Timestamp::now() + Duration::from_mins(10);
        seed_redirect(&hv.inner, &lt.inner, &id, &target, old_expiry).await;

        let created = old_expiry - Duration::from_mins(10);
        let requested = created + Duration::from_hours(1);
        let blob_expiry = requested + Duration::from_hours(1);
        lt.inner
            .put_object(
                &target,
                &Metadata {
                    expiration_policy: ExpirationPolicy::TimeToIdle(Duration::from_hours(1)),
                    time_created: Some(created),
                    time_expires: Some(blob_expiry),
                    ..Default::default()
                },
                stream::single("payload"),
                Timestamp::now(),
            )
            .await
            .unwrap();
        let update = ExpiryUpdate {
            target: ExpiryTarget::FromCreation(Duration::from_hours(1)),
            max: Some(Duration::ZERO),
        };
        assert_eq!(
            storage
                .set_expiry(&id, update, created)
                .await
                .unwrap_err()
                .kind(),
            ErrorKind::InvalidMetadata,
        );
        assert_eq!(events.lock().unwrap().as_slice(), &["lt"]);
        events.lock().unwrap().clear();
        assert_eq!(
            hv.inner.get(&id).expect_tombstone().time_expires,
            Some(old_expiry)
        );
        assert_eq!(
            storage
                .set_expiry(
                    &id,
                    ExpiryUpdate {
                        max: Some(Duration::from_hours(1)),
                        ..update
                    },
                    Timestamp::now(),
                )
                .await
                .unwrap(),
            SetExpiryResponse::Satisfied(requested)
        );
        assert_eq!(events.lock().unwrap().as_slice(), &["lt", "hv"]);
        assert_eq!(
            lt.inner.get(&target).expect_object().0.time_expires,
            Some(blob_expiry)
        );
        assert_eq!(
            hv.inner.get(&id).expect_tombstone().time_expires,
            Some(requested)
        );
    }

    #[derive(Clone, Debug)]
    struct ReplaceInlineOnLookup {
        replacement: Metadata,
        replaced: Arc<StdMutex<bool>>,
    }

    #[async_trait::async_trait]
    impl Hooks for ReplaceInlineOnLookup {
        async fn get_tiered_metadata(
            &self,
            inner: &InMemoryBackend,
            id: &ObjectId,
            access_time: Timestamp,
        ) -> Result<TieredMetadata> {
            let observed = inner.get_tiered_metadata(id, access_time).await?;
            let should_replace = {
                let mut replaced = self.replaced.lock().unwrap();
                !std::mem::replace(&mut *replaced, true)
            };
            if should_replace {
                inner
                    .put_object(
                        id,
                        &self.replacement,
                        stream::single("replacement"),
                        access_time,
                    )
                    .await?;
            }
            Ok(observed)
        }
    }

    #[tokio::test]
    async fn inline_creation_target_uses_update_snapshot() {
        let access_time = Timestamp::from_unix_secs(1_700_000_000).unwrap();
        let old_created = access_time - Duration::from_hours(2);
        let new_created = access_time - Duration::from_mins(30);
        let old_expiry = access_time + Duration::from_mins(10);
        let resolved = new_created + Duration::from_hours(2);
        let replacement = Metadata {
            expiration_policy: ExpirationPolicy::TimeToLive(Duration::from_hours(1)),
            time_created: Some(new_created),
            time_expires: Some(old_expiry),
            ..Default::default()
        };
        let hv = TestBackend::new(ReplaceInlineOnLookup {
            replacement,
            replaced: Arc::new(StdMutex::new(false)),
        });
        let storage = TieredStorage::new(
            Box::new(hv.clone()),
            Box::new(InMemoryBackend::new("lt")),
            Box::new(NoopChangeLog),
        );
        let id = make_id("inline-update-snapshot");
        hv.inner
            .put_object(
                &id,
                &Metadata {
                    expiration_policy: ExpirationPolicy::TimeToLive(Duration::from_hours(1)),
                    time_created: Some(old_created),
                    time_expires: Some(old_expiry),
                    ..Default::default()
                },
                stream::single("original"),
                access_time,
            )
            .await
            .unwrap();

        assert_eq!(
            storage
                .set_expiry(
                    &id,
                    ExpiryTarget::FromCreation(Duration::from_hours(2)).into(),
                    access_time,
                )
                .await
                .unwrap(),
            SetExpiryResponse::Satisfied(resolved)
        );
        let (metadata, payload) = hv.inner.get(&id).expect_object();
        assert_eq!(
            metadata.expiration_policy,
            ExpirationPolicy::TimeToLive(Duration::from_hours(2))
        );
        assert_eq!(metadata.time_created, Some(new_created));
        assert_eq!(metadata.time_expires, Some(resolved));
        assert_eq!(payload, Bytes::from_static(b"replacement"));
    }

    #[tokio::test]
    async fn expiry_hv_conflict() {
        let (storage, hv, lt, events) = tiered_with_expiry_hooks(true, false);
        let id = make_id("tiered-hv-failure");
        let target = new_long_term_revision(&id);
        let old_expiry = Timestamp::now() + Duration::from_mins(10);
        seed_redirect(&hv.inner, &lt.inner, &id, &target, old_expiry).await;

        let requested = old_expiry + Duration::from_mins(50);
        assert_eq!(
            storage
                .set_expiry(
                    &id,
                    ExpiryTarget::FromCreation(Duration::from_hours(1)).into(),
                    Timestamp::now(),
                )
                .await
                .unwrap(),
            SetExpiryResponse::Rejected
        );
        assert_eq!(events.lock().unwrap().as_slice(), &["lt", "hv"]);
        assert_eq!(
            hv.inner.get(&id).expect_tombstone().time_expires,
            Some(old_expiry)
        );
        assert_eq!(
            lt.inner.get(&target).expect_object().0.time_expires,
            Some(requested)
        );
        assert_eq!(
            storage
                .get_metadata(&id, Timestamp::now())
                .await
                .unwrap()
                .unwrap()
                .time_expires,
            Some(old_expiry)
        );
        assert_eq!(
            lt.inner.get(&target).expect_object().0.expiration_policy,
            ExpirationPolicy::TimeToLive(Duration::from_hours(1))
        );
    }

    #[tokio::test]
    async fn expiry_lt_conflict() {
        let (storage, hv, lt, events) = tiered_with_expiry_hooks(false, true);
        let id = make_id("tiered-lt-conflict");
        let target = new_long_term_revision(&id);
        seed_redirect(
            &hv.inner,
            &lt.inner,
            &id,
            &target,
            Timestamp::now() + Duration::from_mins(10),
        )
        .await;

        assert_eq!(
            storage
                .set_expiry(
                    &id,
                    ExpiryTarget::At(Timestamp::now() + Duration::from_hours(1)).into(),
                    Timestamp::now()
                )
                .await
                .unwrap(),
            SetExpiryResponse::Rejected
        );
        assert_eq!(events.lock().unwrap().as_slice(), &["lt"]);
    }

    #[tokio::test]
    async fn expiry_not_found() {
        for missing_blob in [false, true] {
            let (storage, hv, lt, events) = tiered_with_expiry_hooks(false, false);
            let id = make_id("tiered-expiry-missing");
            let target = new_long_term_revision(&id);
            let access_time = Timestamp::now();
            let deadline = access_time + Duration::from_hours(1);
            if missing_blob {
                seed_redirect(&hv.inner, &lt.inner, &id, &target, deadline).await;
                lt.inner.delete_object(&target, access_time).await.unwrap();
            }

            assert_eq!(
                storage
                    .set_expiry(&id, ExpiryTarget::At(deadline).into(), access_time)
                    .await
                    .unwrap(),
                SetExpiryResponse::NotFound
            );
            let expected: &[&str] = if missing_blob { &["lt"] } else { &[] };
            assert_eq!(events.lock().unwrap().as_slice(), expected);
        }
    }

    // --- new_long_term_revision tests ---

    #[test]
    fn revision_id_preserves_context() {
        let id = make_id("my-key");
        let revised = new_long_term_revision(&id);
        assert_eq!(revised.context, id.context);
        assert!(
            revised.key.starts_with("my-key/"),
            "revised key should have /<uuid> suffix, got: {}",
            revised.key
        );
    }

    #[test]
    fn revision_id_roundtrips_storage_path() {
        let id = make_id("original");
        let revised = new_long_term_revision(&id);
        let path = revised.as_storage_path().to_string();
        let parsed = ObjectId::from_storage_path(&path)
            .unwrap_or_else(|| panic!("failed to parse '{path}'"));
        assert_eq!(parsed, revised);
    }

    #[test]
    fn revision_id_is_unique() {
        let id = make_id("base-key");
        let a = new_long_term_revision(&id);
        let b = new_long_term_revision(&id);
        assert_ne!(a.key, b.key, "two calls should produce different keys");
    }

    // --- Basic behavior ---

    #[tokio::test]
    async fn get_nonexistent_returns_none() {
        let (storage, _hv, _lt, _) = make_tiered_storage();
        let id = make_id("does-not-exist");

        assert!(
            storage
                .get_object(&id, Timestamp::now(), None)
                .await
                .unwrap()
                .is_none()
        );
        assert!(
            storage
                .get_metadata(&id, Timestamp::now())
                .await
                .unwrap()
                .is_none()
        );
    }

    #[tokio::test]
    async fn delete_nonexistent_succeeds() {
        let (storage, _hv, _lt, _) = make_tiered_storage();
        let id = make_id("does-not-exist");

        storage.delete_object(&id, Timestamp::now()).await.unwrap();
    }

    // --- Put routing ---

    #[tokio::test]
    async fn put_small_object_stores_inline() {
        let (storage, hv, lt, _) = make_tiered_storage();
        let id = make_id("small");
        let payload = b"small payload".to_vec();

        storage
            .put_object(
                &id,
                &Metadata::default(),
                stream::single(payload.clone()),
                Timestamp::now(),
            )
            .await
            .unwrap();

        assert!(hv.contains(&id), "expected in high-volume");
        assert!(!lt.contains(&id), "leaked to long-term");

        let (_, _, s) = storage
            .get_object(&id, Timestamp::now(), None)
            .await
            .unwrap()
            .unwrap();
        let body = stream::read_to_vec(s).await.unwrap();
        assert_eq!(body, payload);

        assert!(
            storage
                .get_metadata(&id, Timestamp::now())
                .await
                .unwrap()
                .is_some(),
            "get_metadata should return metadata for inline objects"
        );
    }

    #[tokio::test]
    async fn put_large_object_creates_tombstone() {
        let (storage, hv, lt, _) = make_tiered_storage();
        let id = make_id("large");
        let payload = vec![0xCDu8; 2 * 1024 * 1024]; // 2 MiB, over threshold
        let metadata_in = Metadata {
            content_type: "image/png".into(),
            expiration_policy: ExpirationPolicy::TimeToLive(Duration::from_hours(1)),
            time_expires: Some(Timestamp::now() + Duration::from_hours(1)),
            origin: Some("10.0.0.1".into()),
            ..Metadata::default()
        };

        storage
            .put_object(
                &id,
                &metadata_in,
                stream::single(payload.clone()),
                Timestamp::now(),
            )
            .await
            .unwrap();

        // Tombstone in HV: correct deadline, target is a revision key.
        let tombstone = hv.get(&id).expect_tombstone();
        assert_eq!(tombstone.time_expires, metadata_in.time_expires);
        let lt_id = tombstone.target;
        assert!(
            lt_id.key().starts_with(id.key()),
            "tombstone target key should be a revision of the HV key, got: {}",
            lt_id.key()
        );

        // LT object at revision key with correct metadata.
        let (lt_meta, _) = lt.get(&lt_id).expect_object();
        assert_eq!(lt_meta.content_type, "image/png");
        assert_eq!(lt_meta.expiration_policy, metadata_in.expiration_policy);
        assert_eq!(lt_meta.time_expires, tombstone.time_expires);

        // get_object follows the tombstone and returns the correct payload.
        let (_, _, s) = storage
            .get_object(&id, Timestamp::now(), None)
            .await
            .unwrap()
            .unwrap();
        let body = stream::read_to_vec(s).await.unwrap();
        assert_eq!(body, payload);

        // get_metadata follows the tombstone and returns the correct content_type.
        let metadata = storage
            .get_metadata(&id, Timestamp::now())
            .await
            .unwrap()
            .unwrap();
        assert_eq!(metadata.content_type, "image/png");
    }

    // --- Put overwrites ---

    #[tokio::test]
    async fn reinsert_small_over_large_swaps_to_inline() {
        let (storage, hv, lt, _) = make_tiered_storage();
        let id = make_id("reinsert-key");

        // First: insert a large object → creates tombstone in hv, payload in lt at lt_id
        let large_payload = vec![0xABu8; 2 * 1024 * 1024];
        storage
            .put_object(
                &id,
                &Metadata::default(),
                stream::single(large_payload),
                Timestamp::now(),
            )
            .await
            .unwrap();

        let lt_id = hv.get(&id).expect_tombstone().target;

        // Re-insert a SMALL payload with the same key.
        // The CAS-swap puts the small object inline in HV and schedules background cleanup.
        let small_payload = vec![0xCDu8; 100]; // well under 1 MiB threshold
        storage
            .put_object(
                &id,
                &Metadata::default(),
                stream::single(small_payload),
                Timestamp::now(),
            )
            .await
            .unwrap();

        // The small object is now inline in high-volume.
        hv.get(&id).expect_object();

        // Drain background cleanup tasks before asserting LT state.
        storage.join().await;

        // The old long-term blob was cleaned up.
        lt.get(&lt_id).expect_not_found();
    }

    #[tokio::test]
    async fn overwrite_large_with_large_replaces_revision() {
        let (storage, hv, lt, _) = make_tiered_storage();
        let id = make_id("overwrite-large");

        let payload1 = vec![0xAAu8; 2 * 1024 * 1024];
        storage
            .put_object(
                &id,
                &Metadata::default(),
                stream::single(payload1),
                Timestamp::now(),
            )
            .await
            .unwrap();
        let lt_id_1 = hv.get(&id).expect_tombstone().target;

        let payload2 = vec![0xBBu8; 2 * 1024 * 1024];
        storage
            .put_object(
                &id,
                &Metadata::default(),
                stream::single(payload2.clone()),
                Timestamp::now(),
            )
            .await
            .unwrap();
        let lt_id_2 = hv.get(&id).expect_tombstone().target;

        assert_ne!(
            lt_id_1, lt_id_2,
            "second write should create a new revision"
        );

        // Drain background cleanup tasks before asserting LT state.
        storage.join().await;

        lt.get(&lt_id_1).expect_not_found();
        lt.get(&lt_id_2).expect_object();

        let (_, _, s) = storage
            .get_object(&id, Timestamp::now(), None)
            .await
            .unwrap()
            .unwrap();
        let body = stream::read_to_vec(s).await.unwrap();
        assert_eq!(body, payload2);
    }

    // --- Delete ---

    #[tokio::test]
    async fn delete_small_object() {
        let (storage, hv, _lt, _) = make_tiered_storage();
        let id = make_id("delete-small");

        storage
            .put_object(
                &id,
                &Metadata::default(),
                stream::single("tiny"),
                Timestamp::now(),
            )
            .await
            .unwrap();

        storage.delete_object(&id, Timestamp::now()).await.unwrap();

        hv.get(&id).expect_not_found();
        assert!(
            storage
                .get_object(&id, Timestamp::now(), None)
                .await
                .unwrap()
                .is_none()
        );
    }

    #[tokio::test]
    async fn delete_large_object_cleans_up_both_backends() {
        let (storage, hv, lt, _) = make_tiered_storage();
        let id = make_id("delete-both");
        let payload = vec![0u8; 2 * 1024 * 1024]; // 2 MiB

        storage
            .put_object(
                &id,
                &Metadata::default(),
                stream::single(payload),
                Timestamp::now(),
            )
            .await
            .unwrap();

        // Capture lt_id before deleting (it lives at the revision key, not at id).
        let lt_id = hv.get(&id).expect_tombstone().target;

        storage.delete_object(&id, Timestamp::now()).await.unwrap();

        // Drain background cleanup tasks before asserting LT state.
        storage.join().await;

        assert!(!hv.contains(&id), "tombstone not cleaned up");
        assert!(!lt.contains(&lt_id), "long-term object not cleaned up");
    }

    #[derive(Debug)]
    struct FailDelete;

    #[async_trait::async_trait]
    impl Hooks for FailDelete {
        async fn delete_object(
            &self,
            _inner: &InMemoryBackend,
            _id: &ObjectId,
            _access_time: Timestamp,
        ) -> Result<DeleteResponse> {
            Err(Error::with_source(
                ErrorKind::BackendFailure,
                std::io::Error::new(
                    std::io::ErrorKind::ConnectionRefused,
                    "simulated long-term delete failure",
                ),
            ))
        }
    }

    /// When the long-term GCS cleanup fails after the tombstone is deleted, the
    /// delete still succeeds (GCS cleanup is best-effort). An orphan blob may
    /// remain in LT storage, which is accepted.
    #[tokio::test]
    async fn delete_succeeds_when_gcs_cleanup_fails() {
        let hv = InMemoryBackend::new("hv");
        let lt = TestBackend::new(FailDelete);
        let log = NoopChangeLog;
        let storage = TieredStorage::new(Box::new(hv.clone()), Box::new(lt), Box::new(log));

        let id = make_id("fail-delete");
        let payload = vec![0xABu8; 2 * 1024 * 1024]; // 2 MiB -> goes to long-term
        storage
            .put_object(
                &id,
                &Metadata::default(),
                stream::single(payload),
                Timestamp::now(),
            )
            .await
            .unwrap();

        // Delete succeeds even though GCS cleanup fails (it is best-effort).
        let result = storage.delete_object(&id, Timestamp::now()).await;
        assert!(
            result.is_ok(),
            "delete should succeed despite GCS cleanup failure"
        );

        // The tombstone in HV is gone (CAS-deleted first, before GCS cleanup).
        hv.get(&id).expect_not_found();

        // The orphaned GCS blob remains but the object is unreachable through the service.
        assert!(
            storage
                .get_object(&id, Timestamp::now(), None)
                .await
                .unwrap()
                .is_none(),
            "object should be unreachable after tombstone is deleted"
        );
    }

    // --- CAS conflicts ---

    #[derive(Debug, Copy, Clone)]
    struct CasConflict;

    #[async_trait::async_trait]
    impl Hooks for CasConflict {
        async fn compare_and_write(
            &self,
            _inner: &InMemoryBackend,
            _id: &ObjectId,
            _current: Option<&ObjectId>,
            _write: TieredWrite,
            _access_time: Timestamp,
        ) -> Result<bool> {
            Ok(false) // always conflict
        }
    }

    /// After a large-object write loses the CAS race, the new LT blob must be
    /// cleaned up. The put still returns `Ok(())` — from the caller's view, a
    /// concurrent write won.
    #[tokio::test]
    async fn put_large_cas_conflict_cleans_up_new_blob() {
        let hv = TestBackend::new(CasConflict);
        let lt = InMemoryBackend::new("lt");
        let log = NoopChangeLog;
        let storage = TieredStorage::new(Box::new(hv), Box::new(lt.clone()), Box::new(log));

        let id = make_id("cas-conflict-large");
        let payload = vec![0xABu8; 2 * 1024 * 1024]; // 2 MiB -> long-term path

        storage
            .put_object(
                &id,
                &Metadata::default(),
                stream::single(payload),
                Timestamp::now(),
            )
            .await
            .unwrap();

        // Drain background cleanup tasks before asserting LT state.
        storage.join().await;

        assert!(
            lt.is_empty(),
            "LT blob should be cleaned up after CAS conflict"
        );
    }

    #[tokio::test]
    async fn upload_cas_conflict_cleans_up_new_blob() {
        let hv = TestBackend::new(CasConflict);
        let lt = InMemoryBackend::new("lt");
        let storage =
            TieredStorage::new(Box::new(hv), Box::new(lt.clone()), Box::new(NoopChangeLog));
        let id = make_id("upload-cas-conflict");
        let payload = vec![0xAB; BACKEND_SIZE_THRESHOLD + 1];
        let session =
            resumable_token(&storage, &id, &Metadata::default(), payload.len() as u64).await;

        assert_eq!(
            storage
                .put_chunk(&session, 0, payload.len() as u64, stream::single(payload))
                .await
                .unwrap(),
            UploadProgress::Complete
        );
        storage.join().await;
        assert!(
            lt.is_empty(),
            "LT blob should be cleaned up after CAS conflict"
        );
    }

    /// When swapping a tombstone for inline data, a CAS conflict means another
    /// writer won. The put still returns `Ok(())` — no LT blob was written, so
    /// there is nothing to clean up.
    #[tokio::test]
    async fn put_small_over_tombstone_cas_conflict_succeeds() {
        let inner = InMemoryBackend::new("hv");
        let id = make_id("cas-conflict-small");

        // Pre-seed a tombstone directly in the inner backend so put_non_tombstone
        // returns it instead of writing inline.
        let tombstone = Tombstone {
            target: make_id("lt-object"),
            time_expires: None,
        };
        inner
            .compare_and_write(
                &id,
                None,
                TieredWrite::Tombstone(tombstone),
                Timestamp::now(),
            )
            .await
            .unwrap();

        let lt = InMemoryBackend::new("lt");
        let hv = TestBackend::with_inner(inner, CasConflict);
        let log = NoopChangeLog;
        let storage = TieredStorage::new(Box::new(hv), Box::new(lt), Box::new(log));

        // Writing a small object over a tombstone should succeed even when CAS
        // conflicts — the other writer's write is accepted.
        storage
            .put_object(
                &id,
                &Metadata::default(),
                stream::single("tiny"),
                Timestamp::now(),
            )
            .await
            .unwrap();
    }

    // --- Failure / inconsistency ---

    /// Simulates compare_and_write failure. If `true`, it fails after commit.
    #[derive(Debug)]
    struct FailCas(bool);

    #[async_trait::async_trait]
    impl Hooks for FailCas {
        async fn compare_and_write(
            &self,
            inner: &InMemoryBackend,
            id: &ObjectId,
            current: Option<&ObjectId>,
            write: TieredWrite,
            access_time: Timestamp,
        ) -> Result<bool> {
            if self.0 {
                // simulate a network error _after_ commit went through
                inner
                    .compare_and_write(id, current, write, access_time)
                    .await?;
            }
            Err(Error::with_source(
                ErrorKind::BackendFailure,
                std::io::Error::new(
                    std::io::ErrorKind::TimedOut,
                    "simulated compare_and_write failure",
                ),
            ))
        }
    }

    /// If the tombstone write to the high-volume backend fails after the long-term
    /// write succeeds, the long-term object must be cleaned up so we never leave
    /// an unreachable orphan in long-term storage.
    #[tokio::test]
    async fn no_orphan_when_tombstone_write_fails() {
        let lt = InMemoryBackend::new("lt");
        let hv = TestBackend::new(FailCas(false));
        let log = NoopChangeLog;
        let storage = TieredStorage::new(Box::new(hv), Box::new(lt.clone()), Box::new(log));

        let id = make_id("orphan-test");
        let payload = vec![0xABu8; 2 * 1024 * 1024]; // 2 MiB -> long-term path
        let result = storage
            .put_object(
                &id,
                &Metadata::default(),
                stream::single(payload),
                Timestamp::now(),
            )
            .await;

        assert!(result.is_err());

        // Drain background cleanup tasks before asserting LT state.
        storage.join().await;

        assert!(lt.is_empty(), "long-term object not cleaned up");
    }

    #[tokio::test]
    async fn upload_cas_failure_cleans_up_new_blob() {
        let hv = TestBackend::new(FailCas(false));
        let lt = InMemoryBackend::new("lt");
        let storage =
            TieredStorage::new(Box::new(hv), Box::new(lt.clone()), Box::new(NoopChangeLog));
        let id = make_id("upload-cas-failure");
        let payload = vec![0xAB; BACKEND_SIZE_THRESHOLD + 1];
        let session =
            resumable_token(&storage, &id, &Metadata::default(), payload.len() as u64).await;

        assert_eq!(
            storage
                .put_chunk(&session, 0, payload.len() as u64, stream::single(payload))
                .await
                .unwrap_err()
                .kind(),
            ErrorKind::BackendFailure
        );
        storage.join().await;
        assert!(
            lt.is_empty(),
            "LT blob should be cleaned up after CAS failure"
        );
    }

    /// If a tombstone exists in high-volume but the corresponding object is
    /// missing from long-term storage (e.g. due to a race condition or partial
    /// cleanup), reads should gracefully return None rather than error.
    #[tokio::test]
    async fn orphan_tombstone_returns_none() {
        let (storage, hv, lt, _) = make_tiered_storage();
        let id = make_id("orphan-tombstone");
        let payload = vec![0xCDu8; 2 * 1024 * 1024]; // 2 MiB

        storage
            .put_object(
                &id,
                &Metadata::default(),
                stream::single(payload),
                Timestamp::now(),
            )
            .await
            .unwrap();

        // The object is at the revision key in LT, not at id.
        let lt_id = hv.get(&id).expect_tombstone().target;

        // Remove the long-term object, leaving an orphan tombstone in hv
        lt.remove(&lt_id);

        assert!(
            storage
                .get_object(&id, Timestamp::now(), None)
                .await
                .unwrap()
                .is_none(),
            "orphan tombstone should resolve to None on get_object"
        );
        assert!(
            storage
                .get_metadata(&id, Timestamp::now())
                .await
                .unwrap()
                .is_none(),
            "orphan tombstone should resolve to None on get_metadata"
        );
    }

    // --- Redirect target ---

    /// A tombstone carrying an explicit `target` is followed correctly on reads and deletes,
    /// including when the target ObjectId differs from the HV ObjectId.
    #[tokio::test]
    async fn tombstone_target_is_used_for_reads_and_deletes() {
        let hv = InMemoryBackend::new("hv");
        let lt = InMemoryBackend::new("lt");
        let log = NoopChangeLog;
        let storage = TieredStorage::new(Box::new(hv.clone()), Box::new(lt.clone()), Box::new(log));

        let hv_id = make_id("hv-key");
        let lt_id = make_id("lt-key");
        let payload = vec![0xABu8; 100];

        // Write the object under the LT id and a tombstone pointing to it from HV.
        lt.put_object(
            &lt_id,
            &Metadata::default(),
            stream::single(payload.clone()),
            Timestamp::now(),
        )
        .await
        .unwrap();
        let tombstone = Tombstone {
            target: lt_id.clone(),
            time_expires: None,
        };
        hv.compare_and_write(
            &hv_id,
            None,
            TieredWrite::Tombstone(tombstone),
            Timestamp::now(),
        )
        .await
        .unwrap();

        // get_object must follow the tombstone and find the object via the lt_id target.
        let (_, _, s) = storage
            .get_object(&hv_id, Timestamp::now(), None)
            .await
            .unwrap()
            .unwrap();
        let body = stream::read_to_vec(s).await.unwrap();
        assert_eq!(body, payload);

        // delete_object must clean up both backends using the target.
        storage
            .delete_object(&hv_id, Timestamp::now())
            .await
            .unwrap();
        storage.join().await;
        assert!(!hv.contains(&hv_id), "tombstone should be removed");
        assert!(!lt.contains(&lt_id), "lt object should be removed");
    }

    // --- Multi-chunk ---

    #[tokio::test]
    async fn multi_chunk_large_object_chains_buffered_and_remaining() {
        let (storage, hv, lt, _) = make_tiered_storage();
        let id = make_id("multi-chunk");

        // Deliver a 2 MiB payload across multiple chunks that individually
        // fit under the threshold but collectively exceed it.
        let chunk_size = 512 * 1024; // 512 KiB per chunk
        let chunk_count = 4; // 4 × 512 KiB = 2 MiB total
        let stream: ClientStream = futures_util::stream::iter(
            (0..chunk_count).map(move |i| Ok(Bytes::from(vec![i as u8; chunk_size]))),
        )
        .boxed();

        storage
            .put_object(&id, &Metadata::default(), stream, Timestamp::now())
            .await
            .unwrap();

        // Should have been routed to long-term (over 1 MiB) at the revision key.
        let lt_id = hv.get(&id).expect_tombstone().target;
        let (_, lt_bytes) = lt.get(&lt_id).expect_object();
        assert_eq!(lt_bytes.len(), chunk_size * chunk_count);

        // Verify data integrity — each chunk's fill byte should appear in order.
        for i in 0..chunk_count {
            let offset = i * chunk_size;
            assert!(
                lt_bytes[offset..offset + chunk_size]
                    .iter()
                    .all(|&b| b == i as u8),
                "data mismatch in chunk {i}"
            );
        }
    }

    // --- Written-phase cleanup ---

    /// When a large-object overwrite commits in HV but its response is lost, the guard drops in
    /// `Written` phase. Cleanup must read HV to determine the CAS outcome, then delete whichever
    /// LT blob is no longer referenced — here the old one, since the new tombstone committed.
    #[tokio::test]
    async fn written_cleanup_after_lost_cas_response() {
        let (storage, hv, lt, log) = make_tiered_storage();
        let id = make_id("obj");

        // First put: establishes tombstone
        let payload = vec![0xAAu8; 2 * 1024 * 1024];
        storage
            .put_object(
                &id,
                &Metadata::default(),
                stream::single(payload.clone()),
                Timestamp::now(),
            )
            .await
            .unwrap();
        let tombstone1 = hv.get(&id).expect_tombstone().target;

        // Second put: Updates tombstone but fails immediately after committing
        let broken_storage = TieredStorage::new(
            Box::new(TestBackend::with_inner(hv.clone(), FailCas(true))),
            Box::new(lt.clone()),
            Box::new(log.clone()),
        );
        broken_storage
            .put_object(
                &id,
                &Metadata::default(),
                stream::single(payload.clone()),
                Timestamp::now(),
            )
            .await
            .unwrap_err(); // must fail
        let tombstone2 = hv.get(&id).expect_tombstone().target;
        assert_ne!(tombstone1, tombstone2);

        // The first tombstone's target should be cleaned up, but the second should remain.
        broken_storage.join().await;
        lt.get(&tombstone1).expect_not_found();
        lt.get(&tombstone2).expect_object();

        // Now delete the new object with the same tombstone failure
        broken_storage
            .delete_object(&id, Timestamp::now())
            .await
            .unwrap_err();
        hv.get(&id).expect_not_found();
        broken_storage.join().await;
        lt.get(&tombstone2).expect_not_found();

        // Create a fresh large object
        let id = make_id("obj2");
        storage
            .put_object(
                &id,
                &Metadata::default(),
                stream::single(payload.clone()),
                Timestamp::now(),
            )
            .await
            .unwrap();
        let tombstone3 = hv.get(&id).expect_tombstone().target;

        // Overwrite it with a small object and check again for cleanup
        broken_storage
            .put_object(
                &id,
                &Metadata::default(),
                stream::single(&b"small"[..]),
                Timestamp::now(),
            )
            .await
            .unwrap_err(); // must fail
        hv.get(&id).expect_object();
        broken_storage.join().await;
        lt.get(&tombstone3).expect_not_found();
    }

    // --- ChangeGuard drop safety tests ---

    /// Dropping a guard outside any tokio runtime must not panic.
    #[test]
    fn guard_dropped_outside_runtime_does_not_panic() {
        let manager = ChangeManager::new(
            Box::new(InMemoryBackend::new("hv")),
            Box::new(InMemoryBackend::new("lt")),
            Box::new(NoopChangeLog),
        );

        let change = Change {
            id: make_id("object-key"),
            new: Some(make_id("cleanup-target")),
            old: None,
            cleanup_after: None,
        };

        // Build the guard inside a temporary runtime, then let the runtime drop
        // so that no tokio context is active when the guard drops.
        let guard = {
            let rt = tokio::runtime::Runtime::new().unwrap();
            rt.block_on(manager.record(change)).unwrap()
        };

        drop(guard); // Must not panic.
    }

    /// `join` blocks until all in-flight guards have completed cleanup.
    ///
    /// Time is advanced manually so the test runs at virtual speed. The guard
    /// completes after 10 s; `join` must still be waiting at 9 s and done by 11 s.
    #[tokio::test(start_paused = true)]
    async fn join_waits_for_cleanup_to_complete() {
        let (storage, _hv, _lt, _) = make_tiered_storage();
        let change = Change {
            id: make_id("object-key"),
            new: None,
            old: None,
            cleanup_after: None,
        };
        let mut guard = storage.record_change(change).await.unwrap();

        tokio::spawn(async move {
            tokio::time::sleep(Duration::from_secs(10)).await;
            guard.advance(ChangePhase::Completed);
            drop(guard);
        });

        let join_future = tokio::spawn(async move { storage.join().await });

        tokio::time::sleep(Duration::from_secs(9)).await;
        assert!(!join_future.is_finished(), "finished before guard dropped");

        tokio::time::sleep(Duration::from_secs(2)).await;
        assert!(join_future.is_finished(), "finish after guard drops");
    }

    // --- Changelog integration tests ---

    /// LT backend hook that completes the write, then pauses until resumed.
    ///
    /// Lets tests cancel the owning future after the blob is committed but
    /// before the HV tombstone is set.
    #[derive(Clone, Debug)]
    struct PauseAfterPut {
        paused: Arc<tokio::sync::Notify>,
        resume: Arc<tokio::sync::Notify>,
    }

    #[async_trait::async_trait]
    impl Hooks for PauseAfterPut {
        async fn put_object(
            &self,
            inner: &InMemoryBackend,
            id: &ObjectId,
            metadata: &Metadata,
            stream: ClientStream,
            access_time: Timestamp,
        ) -> Result<PutResponse> {
            inner.put_object(id, metadata, stream, access_time).await?;
            self.paused.notify_one();
            self.resume.notified().await;
            Ok(())
        }
    }

    /// When a future is cancelled after the LT write but before the HV tombstone is set,
    /// the `ChangeGuard` cleans up the orphaned LT blob and removes the log entry.
    #[tokio::test]
    async fn dropped_future_triggers_cleanup_and_log_entry_removed() {
        let paused = Arc::new(tokio::sync::Notify::new());
        let hooks = PauseAfterPut {
            paused: Arc::clone(&paused),
            resume: Arc::new(tokio::sync::Notify::new()),
        };

        let lt_inner = InMemoryBackend::new("lt");
        let log = InMemoryChangeLog::default();
        let storage = TieredStorage::new(
            Box::new(InMemoryBackend::new("hv")),
            Box::new(TestBackend::with_inner(lt_inner.clone(), hooks)),
            Box::new(log.clone()),
        );

        let id = make_id("drop-test");
        let metadata = Metadata::default();
        let payload = vec![0xABu8; 2 * 1024 * 1024]; // 2 MiB → long-term path

        // Drive the put until the LT write commits, then cancel before the HV tombstone is set.
        tokio::select! {
            result = storage.put_object(&id, &metadata, stream::single(payload), Timestamp::now()) => {
                panic!("expected put to pause before completing, got: {result:?}");
            }
            _ = paused.notified() => {
                // LT blob stored; cancelling drops the guard in Recorded phase.
            }
        }

        // ChangeGuard dropped → background cleanup task spawned; wait for it.
        storage.join().await;

        // The orphaned LT blob must have been deleted.
        assert!(lt_inner.is_empty(), "orphaned LT blob was not cleaned up");

        // The log entry must be gone once cleanup completes.
        let entries = log.scan().await.unwrap();
        assert!(
            entries.is_empty(),
            "changelog entry not removed after cleanup"
        );
    }

    // --- Multipart upload ---

    #[test]
    fn multipart_upload_id_roundtrip() {
        let id = TieredUploadId {
            revision: "my-key/01924a6f-7e28-7b9a-9c1d-abcdef123456".into(),
            upload_id: UploadId::new("upstream-upload-id-abc".into()).unwrap(),
        };
        let encoded: UploadId = id.clone().try_into().unwrap();
        let decoded: TieredUploadId = (&encoded.clone()).try_into().unwrap();
        assert_eq!(decoded, id);
    }

    #[test]
    fn malformed_multipart_upload_ids_are_invalid_upload_ids() {
        let invalid_base64 = UploadId::new("%%%".into()).unwrap();
        let malformed_json = UploadId::new("bm90IGpzb24".into()).unwrap();

        for upload_id in [&invalid_base64, &malformed_json] {
            let error = TieredUploadId::try_from(upload_id).unwrap_err();
            assert_eq!(error.kind(), ErrorKind::InvalidUploadId);
        }
    }

    #[tokio::test]
    async fn multipart_single_part_roundtrip() {
        let (storage, hv, lt, _) = make_tiered_storage();
        let id = make_id("mp-single");
        let metadata = Metadata {
            content_type: "application/octet-stream".into(),
            expiration_policy: ExpirationPolicy::TimeToLive(Duration::from_hours(1)),
            time_expires: Some(Timestamp::now() + Duration::from_hours(1)),
            ..Metadata::default()
        };
        let payload = vec![0xABu8; 2 * 1024 * 1024]; // 2 MiB

        let upload_id = storage.initiate_multipart(&id, &metadata).await.unwrap();

        let etag = storage
            .upload_part(
                &id,
                &upload_id,
                NonZeroU32::new(1).unwrap(),
                payload.len() as u64,
                None,
                stream::single(payload.clone()),
            )
            .await
            .unwrap();

        let error = storage
            .complete_multipart(
                &id,
                &upload_id,
                vec![CompletedPart {
                    part_number: NonZeroU32::new(1).unwrap(),
                    etag,
                }],
                Timestamp::now(),
            )
            .await
            .unwrap();
        assert!(
            error.is_none(),
            "complete_multipart returned error: {error:?}"
        );

        // get_object should follow the tombstone and return the payload.
        let (got_meta, _, s) = storage
            .get_object(&id, Timestamp::now(), None)
            .await
            .unwrap()
            .unwrap();
        let body = stream::read_to_vec(s).await.unwrap();
        assert_eq!(body, payload);
        assert_eq!(got_meta.content_type, "application/octet-stream");

        // HV should have a tombstone, LT should have the object at the physical key.
        let tombstone = hv.get(&id).expect_tombstone();
        assert!(
            tombstone.target.key().starts_with(id.key()),
            "tombstone target should be a revision key"
        );
        assert_eq!(tombstone.time_expires, metadata.time_expires);
        assert_eq!(
            lt.get(&tombstone.target).expect_object().0.time_expires,
            tombstone.time_expires
        );
    }

    #[tokio::test]
    async fn multipart_upload() {
        let (storage, _hv, _lt, _) = make_tiered_storage();
        let id = make_id("multipart");

        let upload_id = storage
            .initiate_multipart(&id, &Metadata::default())
            .await
            .unwrap();

        let part1 = vec![0xAAu8; 512 * 1024];
        let part2 = vec![0xBBu8; 512 * 1024];
        let part3 = vec![0xCCu8; 512 * 1024];

        let etag3 = storage
            .upload_part(
                &id,
                &upload_id,
                NonZeroU32::new(3).unwrap(),
                part3.len() as u64,
                None,
                stream::single(part3.clone()),
            )
            .await
            .unwrap();
        let etag2 = storage
            .upload_part(
                &id,
                &upload_id,
                NonZeroU32::new(2).unwrap(),
                part2.len() as u64,
                None,
                stream::single(part2.clone()),
            )
            .await
            .unwrap();
        let etag1 = storage
            .upload_part(
                &id,
                &upload_id,
                NonZeroU32::new(1).unwrap(),
                part1.len() as u64,
                None,
                stream::single(part1.clone()),
            )
            .await
            .unwrap();

        let error = storage
            .complete_multipart(
                &id,
                &upload_id,
                vec![
                    CompletedPart {
                        part_number: NonZeroU32::new(1).unwrap(),
                        etag: etag1,
                    },
                    CompletedPart {
                        part_number: NonZeroU32::new(2).unwrap(),
                        etag: etag2,
                    },
                    CompletedPart {
                        part_number: NonZeroU32::new(3).unwrap(),
                        etag: etag3,
                    },
                ],
                Timestamp::now(),
            )
            .await
            .unwrap();
        assert!(error.is_none());

        let (_, _, s) = storage
            .get_object(&id, Timestamp::now(), None)
            .await
            .unwrap()
            .unwrap();
        let body = stream::read_to_vec(s).await.unwrap();

        let mut expected = Vec::new();
        expected.extend_from_slice(&part1);
        expected.extend_from_slice(&part2);
        expected.extend_from_slice(&part3);
        assert_eq!(body, expected);
    }

    #[tokio::test]
    async fn multipart_abort() {
        let (storage, hv, _lt, _) = make_tiered_storage();
        let id = make_id("mp-abort");

        let upload_id = storage
            .initiate_multipart(&id, &Metadata::default())
            .await
            .unwrap();

        // Upload a part then abort.
        let payload = vec![0xABu8; 100];
        storage
            .upload_part(
                &id,
                &upload_id,
                NonZeroU32::new(1).unwrap(),
                payload.len() as u64,
                None,
                stream::single(payload),
            )
            .await
            .unwrap();

        storage.abort_multipart(&id, &upload_id).await.unwrap();

        // No tombstone should have been written.
        hv.get(&id).expect_not_found();

        // The object should not be reachable.
        assert!(
            storage
                .get_object(&id, Timestamp::now(), None)
                .await
                .unwrap()
                .is_none()
        );
    }

    #[tokio::test]
    async fn multipart_list_parts() {
        let (storage, _hv, _lt, _) = make_tiered_storage();
        let id = make_id("mp-list");

        let upload_id = storage
            .initiate_multipart(&id, &Metadata::default())
            .await
            .unwrap();

        let part1 = vec![0xAAu8; 100];
        let part2 = vec![0xBBu8; 200];
        storage
            .upload_part(
                &id,
                &upload_id,
                NonZeroU32::new(1).unwrap(),
                part1.len() as u64,
                None,
                stream::single(part1),
            )
            .await
            .unwrap();
        storage
            .upload_part(
                &id,
                &upload_id,
                NonZeroU32::new(2).unwrap(),
                part2.len() as u64,
                None,
                stream::single(part2),
            )
            .await
            .unwrap();

        let resp = storage
            .list_parts(&id, &upload_id, None, None)
            .await
            .unwrap();
        assert_eq!(resp.parts.len(), 2);
        assert_eq!(resp.parts[0].part_number.get(), 1);
        assert_eq!(resp.parts[0].size, 100);
        assert_eq!(resp.parts[1].part_number.get(), 2);
        assert_eq!(resp.parts[1].size, 200);
    }

    #[tokio::test]
    async fn multipart_overwrites_existing_tombstone() {
        let (storage, hv, lt, _) = make_tiered_storage();
        let id = make_id("mp-overwrite");

        // Put a large object via the normal path.
        let payload1 = vec![0xAAu8; 2 * 1024 * 1024];
        storage
            .put_object(
                &id,
                &Metadata::default(),
                stream::single(payload1),
                Timestamp::now(),
            )
            .await
            .unwrap();
        let old_lt_id = hv.get(&id).expect_tombstone().target;

        // Overwrite via multipart.
        let upload_id = storage
            .initiate_multipart(&id, &Metadata::default())
            .await
            .unwrap();

        let payload2 = vec![0xBBu8; 2 * 1024 * 1024];
        let etag = storage
            .upload_part(
                &id,
                &upload_id,
                NonZeroU32::new(1).unwrap(),
                payload2.len() as u64,
                None,
                stream::single(payload2.clone()),
            )
            .await
            .unwrap();

        // The multipart upload is not finalized, so the tombstone still points to the old
        // revision.
        let lt_id = hv.get(&id).expect_tombstone().target;
        assert_eq!(old_lt_id, lt_id);

        let error = storage
            .complete_multipart(
                &id,
                &upload_id,
                vec![CompletedPart {
                    part_number: NonZeroU32::new(1).unwrap(),
                    etag,
                }],
                Timestamp::now(),
            )
            .await
            .unwrap();
        assert!(error.is_none());

        // Now the upload has been finalized, so the new tombstone points to the new revision.
        let new_lt_id = hv.get(&id).expect_tombstone().target;
        assert_ne!(old_lt_id, new_lt_id);

        // Wait for background cleanup.
        storage.join().await;

        // Old revision should be cleaned up.
        lt.get(&old_lt_id).expect_not_found();
        lt.get(&new_lt_id).expect_object();

        // Assert the contents of the new revision.
        let (_, _, s) = storage
            .get_object(&id, Timestamp::now(), None)
            .await
            .unwrap()
            .unwrap();
        let body = stream::read_to_vec(s).await.unwrap();
        assert_eq!(body, payload2);
    }

    // --- Multipart completion failure handling (consistency, retries, delayed cleanup) ---

    /// Assembles the blob via `complete_multipart`, but returns an error to simulate a network
    /// failure on the response path. Also fails `get_metadata` so the tiered layer cannot
    /// recover by detecting the already-assembled blob.
    #[derive(Debug)]
    struct CompleteMultipartButReturnError;

    #[async_trait::async_trait]
    impl Hooks for CompleteMultipartButReturnError {
        async fn complete_multipart(
            &self,
            inner: &InMemoryBackend,
            id: &ObjectId,
            upload_id: &UploadId,
            parts: Vec<CompletedPart>,
            access_time: Timestamp,
        ) -> Result<CompleteMultipartResponse> {
            inner
                .complete_multipart(id, upload_id, parts, access_time)
                .await
                .unwrap();
            Err(Error::with_source(
                ErrorKind::BackendFailure,
                std::io::Error::new(
                    std::io::ErrorKind::TimedOut,
                    "simulated network error on complete_multipart",
                ),
            ))
        }

        async fn get_metadata(
            &self,
            _inner: &InMemoryBackend,
            _id: &ObjectId,
            _access_time: Timestamp,
        ) -> Result<MetadataResponse> {
            Err(Error::with_source(
                ErrorKind::BackendFailure,
                std::io::Error::new(
                    std::io::ErrorKind::TimedOut,
                    "simulated network error on get_metadata",
                ),
            ))
        }
    }

    /// `complete_multipart` on the inner LT backend assembles the blob successfully, but both
    /// `complete_multipart` and `get_metadata` return errors, so the tiered layer cannot finalize.
    /// After `MULTIPART_COMPLETE_CLEANUP_DELAY`, `ChangeLog` recovery deletes the orphaned blob.
    #[tokio::test]
    async fn cleans_up_orphan_after_failed_multipart_complete() {
        let hv = InMemoryBackend::new("hv");
        let lt_inner = InMemoryBackend::new("lt");
        let log = InMemoryChangeLog::default();
        let storage = TieredStorage::new(
            Box::new(hv.clone()),
            Box::new(TestBackend::with_inner(
                lt_inner.clone(),
                CompleteMultipartButReturnError {},
            )),
            Box::new(log.clone()),
        );

        let id = make_id("mp-orphan");
        let upload_id = storage
            .initiate_multipart(&id, &Metadata::default())
            .await
            .unwrap();

        let tiered_id: TieredUploadId = (&upload_id).try_into().unwrap();
        let physical = ObjectId {
            context: id.context.clone(),
            key: tiered_id.revision,
        };

        let payload = vec![0xABu8; 2 * 1024 * 1024];
        let etag = storage
            .upload_part(
                &id,
                &upload_id,
                NonZeroU32::new(1).unwrap(),
                payload.len() as u64,
                None,
                stream::single(payload),
            )
            .await
            .unwrap();

        let result = storage
            .complete_multipart(
                &id,
                &upload_id,
                vec![CompletedPart {
                    part_number: NonZeroU32::new(1).unwrap(),
                    etag,
                }],
                Timestamp::now(),
            )
            .await;
        assert!(result.is_err());
        storage.join().await;

        // The LT blob is orphaned, and no cleanup has been performed (yet), due to the guard being
        // dropped while in the `Assembling` state.
        lt_inner.get(&physical).expect_object();
        hv.get(&id).expect_not_found();

        // Simulate the passage of time and run recovery.
        log.expire_all();
        let manager = ChangeManager::new(
            Box::new(hv.clone()),
            Box::new(lt_inner.clone()),
            Box::new(log.clone()),
        );
        manager.recover().await.unwrap();

        // The orphaned LT blob has been cleaned up.
        lt_inner.get(&physical).expect_not_found();
        // The change has been removed from the log.
        let remaining = log.scan().await.unwrap();
        assert!(remaining.is_empty());
    }

    #[derive(Debug)]
    struct FailOnFirstCompleteMultipartAttempt {
        attempt: Mutex<u32>,
    }

    impl FailOnFirstCompleteMultipartAttempt {
        fn new() -> Self {
            Self {
                attempt: Mutex::new(0),
            }
        }
    }

    #[async_trait::async_trait]
    impl Hooks for FailOnFirstCompleteMultipartAttempt {
        async fn complete_multipart(
            &self,
            inner: &InMemoryBackend,
            id: &ObjectId,
            upload_id: &UploadId,
            parts: Vec<CompletedPart>,
            access_time: Timestamp,
        ) -> Result<CompleteMultipartResponse> {
            let mut attempt = self.attempt.lock().await;
            *attempt += 1;
            if *attempt == 1 {
                Err(Error::with_source(
                    ErrorKind::BackendFailure,
                    std::io::Error::new(std::io::ErrorKind::TimedOut, "simulated network error"),
                ))
            } else {
                Ok(inner
                    .complete_multipart(id, upload_id, parts, access_time)
                    .await
                    .unwrap())
            }
        }
    }

    /// The first attempt to `complete_multipart` fails, which generates a `Change` entry.
    /// The second call succeeds.
    /// When it's time to clean up, nothing is deleted, as the `complete_multipart` eventually went
    /// through before the cleanup deadline.
    #[tokio::test]
    async fn multipart_complete_succeeds_on_retry_and_leaves_state_consistent() {
        let hv = InMemoryBackend::new("hv");
        let lt_inner = InMemoryBackend::new("lt");
        let log = InMemoryChangeLog::default();
        let storage = TieredStorage::new(
            Box::new(hv.clone()),
            Box::new(TestBackend::with_inner(
                lt_inner.clone(),
                FailOnFirstCompleteMultipartAttempt::new(),
            )),
            Box::new(log.clone()),
        );

        let id = make_id("mp-retry");
        let upload_id = storage
            .initiate_multipart(&id, &Metadata::default())
            .await
            .unwrap();

        let tiered_id: TieredUploadId = (&upload_id).try_into().unwrap();
        let physical = ObjectId {
            context: id.context.clone(),
            key: tiered_id.revision,
        };

        let payload = vec![0xABu8; 2 * 1024 * 1024];
        let etag = storage
            .upload_part(
                &id,
                &upload_id,
                NonZeroU32::new(1).unwrap(),
                payload.len() as u64,
                None,
                stream::single(payload.clone()),
            )
            .await
            .unwrap();

        // The first `complete_multipart` call fails.
        let result = storage
            .complete_multipart(
                &id,
                &upload_id,
                vec![CompletedPart {
                    part_number: NonZeroU32::new(1).unwrap(),
                    etag: etag.clone(),
                }],
                Timestamp::now(),
            )
            .await;
        assert!(result.is_err());
        storage.join().await;

        // The second `complete_multipart` call succeeds.
        let result = storage
            .complete_multipart(
                &id,
                &upload_id,
                vec![CompletedPart {
                    part_number: NonZeroU32::new(1).unwrap(),
                    etag,
                }],
                Timestamp::now(),
            )
            .await;
        assert!(result.is_ok());
        storage.join().await;

        // The object is there.
        let (_, _, s) = storage
            .get_object(&id, Timestamp::now(), None)
            .await
            .unwrap()
            .unwrap();
        let body = stream::read_to_vec(s).await.unwrap();
        assert_eq!(body, payload);

        // Simulate the passage of time and run recovery.
        log.expire_all();
        let manager = ChangeManager::new(
            Box::new(hv.clone()),
            Box::new(lt_inner.clone()),
            Box::new(log.clone()),
        );
        manager.recover().await.unwrap();

        // The LT blob has not been cleaned up, as the write eventually went through.
        lt_inner.get(&physical).expect_object();
        // The tombstone still points to the blob.
        let tombstone = hv.get(&id).expect_tombstone();
        assert_eq!(tombstone.target, physical);
        // The change has been removed from the log.
        let remaining = log.scan().await.unwrap();
        assert!(remaining.is_empty());

        // The object is still there after recovery.
        let (_, _, s) = storage
            .get_object(&id, Timestamp::now(), None)
            .await
            .unwrap()
            .unwrap();
        let body = stream::read_to_vec(s).await.unwrap();
        assert_eq!(body, payload);
    }

    #[derive(Debug)]
    struct FailOnFirstGetMetadataAttempt {
        attempt: Mutex<u32>,
    }

    impl FailOnFirstGetMetadataAttempt {
        fn new() -> Self {
            Self {
                attempt: Mutex::new(0),
            }
        }
    }

    #[async_trait::async_trait]
    impl Hooks for FailOnFirstGetMetadataAttempt {
        async fn get_metadata(
            &self,
            inner: &InMemoryBackend,
            id: &ObjectId,
            access_time: Timestamp,
        ) -> Result<MetadataResponse> {
            let mut attempt = self.attempt.lock().await;
            *attempt += 1;
            if *attempt == 1 {
                Err(Error::with_source(
                    ErrorKind::BackendFailure,
                    std::io::Error::new(std::io::ErrorKind::TimedOut, "simulated network error"),
                ))
            } else {
                inner.get_metadata(id, access_time).await
            }
        }
    }

    /// The first attempt to `complete_multipart` succeeds on the LT backend, but the subsequent
    /// `get_metadata` call fails with a network error, causing the overall `complete_multipart`
    /// to fail. The second call retries and succeeds (the LT object already exists from the first
    /// attempt).
    /// When it's time to clean up, nothing is deleted, as the `complete_multipart` eventually went
    /// through before the cleanup deadline.
    #[tokio::test]
    async fn multipart_complete_succeeds_on_retry_if_get_metadata_errs_and_leaves_state_consistent()
    {
        let hv = InMemoryBackend::new("hv");
        let lt_inner = InMemoryBackend::new("lt");
        let log = InMemoryChangeLog::default();
        let storage = TieredStorage::new(
            Box::new(hv.clone()),
            Box::new(TestBackend::with_inner(
                lt_inner.clone(),
                FailOnFirstGetMetadataAttempt::new(),
            )),
            Box::new(log.clone()),
        );

        let id = make_id("mp-retry-meta");
        let upload_id = storage
            .initiate_multipart(&id, &Metadata::default())
            .await
            .unwrap();

        let tiered_id: TieredUploadId = (&upload_id).try_into().unwrap();
        let physical = ObjectId {
            context: id.context.clone(),
            key: tiered_id.revision,
        };

        let payload = vec![0xABu8; 2 * 1024 * 1024];
        let etag = storage
            .upload_part(
                &id,
                &upload_id,
                NonZeroU32::new(1).unwrap(),
                payload.len() as u64,
                None,
                stream::single(payload.clone()),
            )
            .await
            .unwrap();

        // The first `complete_multipart` call fails (get_metadata network error), even though it
        // internally creates the LT blob.
        let result = storage
            .complete_multipart(
                &id,
                &upload_id,
                vec![CompletedPart {
                    part_number: NonZeroU32::new(1).unwrap(),
                    etag: etag.clone(),
                }],
                Timestamp::now(),
            )
            .await;
        assert!(result.is_err());
        storage.join().await;

        // The second `complete_multipart` call succeeds.
        let result = storage
            .complete_multipart(
                &id,
                &upload_id,
                vec![CompletedPart {
                    part_number: NonZeroU32::new(1).unwrap(),
                    etag,
                }],
                Timestamp::now(),
            )
            .await;
        assert!(result.is_ok());
        storage.join().await;

        // The object is there.
        let (_, _, s) = storage
            .get_object(&id, Timestamp::now(), None)
            .await
            .unwrap()
            .unwrap();
        let body = stream::read_to_vec(s).await.unwrap();
        assert_eq!(body, payload);

        // Simulate the passage of time and run recovery.
        log.expire_all();
        let manager = ChangeManager::new(
            Box::new(hv.clone()),
            Box::new(lt_inner.clone()),
            Box::new(log.clone()),
        );
        manager.recover().await.unwrap();

        // The LT blob has not been cleaned up, as the write eventually went through.
        lt_inner.get(&physical).expect_object();
        // The tombstone still points to the blob.
        let tombstone = hv.get(&id).expect_tombstone();
        assert_eq!(tombstone.target, physical);
        // The change has been removed from the log.
        let remaining = log.scan().await.unwrap();
        assert!(remaining.is_empty());

        // The object is there after recovery.
        let (_, _, s) = storage
            .get_object(&id, Timestamp::now(), None)
            .await
            .unwrap()
            .unwrap();
        let body = stream::read_to_vec(s).await.unwrap();
        assert_eq!(body, payload);
    }
}