Skip to main content

objectstore_service/backend/
bigtable.rs

1//! BigTable backend for high-volume, low-latency storage of small objects.
2//!
3//! # Row Format
4//!
5//! Object row keys use the object's storage path. An object row contains either an **object** or a
6//! **tombstone** — never both. The two layouts are mutually exclusive and distinguished by
7//! column presence:
8//!
9//! | Column | Family    | Content                     | Present when       |
10//! |--------|-----------|-----------------------------|--------------------|
11//! | `p`    | `fg`/`fm` | Compressed payload bytes    | Object row only    |
12//! | `m`    | `fg`/`fm` | [`Metadata`] JSON           | Object row only    |
13//! | `r`    | `fg`/`fm` | Redirect path to LT storage | Tombstone row only |
14//!
15//! The `r` column signals a tombstone row: its **value** is the long-term `ObjectId`
16//! serialized via `as_storage_path()`. Callers can resolve the LT object directly from the
17//! `r` value without reconstructing it from the row key. Its column family and timestamp
18//! carry the tombstone's concrete expiration deadline.
19//!
20//! `p`/`m` and `r` are mutually exclusive. Every write begins with a `DeleteFromRow`
21//! mutation that clears all columns before writing the new cells, so mixed rows cannot exist.
22//!
23//! Upload markers use a separate `uploads` namespace and contain only a one-byte
24//! `u` cell in `fg`, timestamped with the upload deadline.
25//!
26//! ## Legacy Tombstone Format
27//!
28//! Tombstones written before the `r` column layout used the object-row format with an
29//! empty `p` column and `"is_redirect_tombstone": true` in the `m` JSON. Both formats are
30//! supported for reading. A `bigtable.legacy_tombstone_read` metric is emitted on each legacy
31//! read. Legacy tombstones expire naturally by TTL/GC; a successful conditional
32//! expiry extension upgrades them to the `r` format. Tombstone metadata in the historical `t`
33//! column is ignored; the corresponding `r` cell contains all information needed by readers.
34
35use std::fmt;
36use std::future::Future;
37use std::sync::Arc;
38use std::time::Duration;
39
40use bigtable_rs::bigtable::{BigTableConnection, Error as BigTableError, RowCell};
41use bigtable_rs::google::bigtable::v2::{self, mutation};
42use bytes::Bytes;
43use futures_util::TryStreamExt;
44use objectstore_types::metadata::Metadata;
45use objectstore_types::range::{ByteRange, ContentRange};
46use objectstore_types::time::Timestamp;
47use serde::{Deserialize, Serialize};
48use tonic::Code;
49use tracing::Instrument;
50
51use crate::backend::common::{
52    self, Backend, DeleteResponse, ExpiryUpdate, GetResponse, HighVolumeBackend, MetadataResponse,
53    PutResponse, SetExpiryResponse, TieredGet, TieredMetadata, TieredUpdate, TieredWrite,
54    Tombstone,
55};
56use crate::change_stream::{
57    ChangeStream, ChangeStreamFactory, CostTrackerStreamConfig, flush_change_stream,
58};
59use crate::error::{Error, ErrorKind, Result, ResultExt as _};
60use crate::gcp_auth::PrefetchingTokenProvider;
61use crate::id::ObjectId;
62use crate::stream::{ChunkedBytes, ClientStream};
63
64/// Configuration for [`BigTableBackend`].
65///
66/// Stores objects in [Google Cloud Bigtable], a NoSQL wide-column database optimized for
67/// high-throughput, low-latency workloads with small objects. Authentication uses Application
68/// Default Credentials (ADC).
69///
70/// **Note**: The table must be pre-created with the following column families:
71/// - `fg`: timestamp-based garbage collection (`maxage=1s`)
72/// - `fm`: manual garbage collection (`no GC policy`)
73///
74/// [Google Cloud Bigtable]: https://cloud.google.com/bigtable
75///
76/// # Example
77///
78/// ```yaml
79/// storage:
80///   type: bigtable
81///   project_id: my-project
82///   instance_name: objectstore
83///   table_name: objectstore
84/// ```
85#[derive(Debug, Clone, Deserialize, Serialize)]
86pub struct BigTableConfig {
87    /// Optional custom Bigtable endpoint.
88    ///
89    /// Useful for testing with emulators. If `None`, uses the default Bigtable endpoint.
90    ///
91    /// # Default
92    ///
93    /// `None` (uses default Bigtable endpoint)
94    ///
95    /// # Environment Variables
96    ///
97    /// - `OS__STORAGE__TYPE=bigtable`
98    /// - `OS__STORAGE__ENDPOINT=localhost:8086` (optional)
99    pub endpoint: Option<String>,
100
101    /// GCP project ID.
102    ///
103    /// The Google project ID (not project number) containing the Bigtable instance.
104    ///
105    /// # Environment Variables
106    ///
107    /// - `OS__STORAGE__PROJECT_ID=my-project`
108    pub project_id: String,
109
110    /// Bigtable instance name.
111    ///
112    /// # Environment Variables
113    ///
114    /// - `OS__STORAGE__INSTANCE_NAME=my-instance`
115    pub instance_name: String,
116
117    /// Bigtable table name.
118    ///
119    /// The table must exist before starting the server.
120    ///
121    /// # Environment Variables
122    ///
123    /// - `OS__STORAGE__TABLE_NAME=objectstore`
124    pub table_name: String,
125
126    /// Optional number of connections to maintain to Bigtable.
127    ///
128    /// # Default
129    ///
130    /// `None` (defaults to 1)
131    ///
132    /// # Environment Variables
133    ///
134    /// - `OS__STORAGE__CONNECTIONS=16` (optional)
135    pub connections: Option<usize>,
136
137    /// Timeout for an individual Bigtable RPC attempt.
138    ///
139    /// # Default
140    ///
141    /// `2s`
142    ///
143    /// # Environment Variables
144    ///
145    /// - `OS__STORAGE__RPC_TIMEOUT=2s`
146    /// - `OS__STORAGE__HIGH_VOLUME__RPC_TIMEOUT=2s` (tiered storage)
147    #[serde(default = "default_rpc_timeout", with = "humantime_serde")]
148    pub rpc_timeout: Duration,
149
150    /// Reports what this backend stores, for per-usecase cost attribution.
151    ///
152    /// # Default
153    ///
154    /// `None`, which disables reporting for this backend.
155    ///
156    /// # Environment Variables
157    ///
158    /// - `OS__STORAGE__COGS__SHARED_RESOURCE_ID=bigtable_objectstore`
159    /// - `OS__STORAGE__COGS__SAMPLE_RATE=1.0` (optional)
160    #[serde(default, skip_serializing_if = "Option::is_none")]
161    pub cogs: Option<CostTrackerStreamConfig>,
162}
163
164fn default_rpc_timeout() -> Duration {
165    Duration::from_secs(2)
166}
167
168/// Maximum age for connections (GRPC channels) to Bigtable, after which they will be swapped with
169/// new ones in the background.
170/// This is intended to avoid latency spikes that could occur every hour or so, when the server
171/// closes long standing connections ([source](https://web.archive.org/web/20260211140930/https://docs.cloud.google.com/bigtable/docs/performance#cold-starts:~:text=return%20an%20error.-,Cold%20start,-at%20client%20initialization)).
172/// `tonic` already handles reconnections transparently, but lazily, meaning that the first requests
173/// that attempt to use a certain channel after the server has closed it will pay the cost of the
174/// reconnection, resulting in increased latency for those requests.
175const MAX_CHANNEL_AGE: Option<Duration> = Some(Duration::from_mins(50));
176/// Permission scopes required for accessing the BigTable data API.
177const TOKEN_SCOPES: &[&str] = &["https://www.googleapis.com/auth/bigtable.data"];
178
179/// How often to retry failed requests.
180const REQUEST_RETRY_COUNT: usize = 2;
181/// How many times to retry a CAS mutation before giving up and returning an error.
182const CAS_RETRY_COUNT: usize = 3;
183
184/// Column that stores the raw payload (compressed).
185const COLUMN_PAYLOAD: &[u8] = b"p";
186/// Column that stores metadata in JSON.
187const COLUMN_METADATA: &[u8] = b"m";
188/// Column that stores the redirect path for tombstone rows.
189const COLUMN_REDIRECT: &[u8] = b"r";
190/// Regex to match all non-payload columns (`m`, `r`) for metadata-only reads.
191const FILTER_META: &[u8] = b"^[mr]$";
192
193/// Column which marks the presence of an ongoing resumable upload.
194const COLUMN_UPLOAD: &[u8] = b"u";
195
196/// Column family that uses timestamp-based garbage collection.
197///
198/// We require a GC rule on this family to automatically delete rows.
199/// See: <https://cloud.google.com/bigtable/docs/gc-cell-level>
200const FAMILY_GC: &str = "fg";
201/// Column family that uses manual garbage collection.
202const FAMILY_MANUAL: &str = "fm";
203
204/// BigTable storage backend for high-volume, low-latency object storage.
205pub struct BigTableBackend {
206    bigtable: BigTableConnection,
207
208    instance_path: String,
209    table_path: String,
210    table_name: String,
211
212    change_stream: Arc<dyn ChangeStream>,
213}
214
215impl fmt::Debug for BigTableBackend {
216    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
217        f.debug_struct("BigTableBackend")
218            .field("instance_path", &self.instance_path)
219            .field("table_path", &self.table_path)
220            .field("table_name", &self.table_name)
221            .finish_non_exhaustive()
222    }
223}
224
225/// Creates a row filter that matches a single column by exact qualifier.
226fn column_filter(column: &[u8]) -> v2::RowFilter {
227    v2::RowFilter {
228        filter: Some(v2::row_filter::Filter::ColumnQualifierRegexFilter(
229            [b"^", column, b"$"].concat(),
230        )),
231    }
232}
233
234/// Creates a row filter matching the legacy tombstone format: `m` column JSON starts with
235/// `{"is_redirect_tombstone":true`.
236///
237/// After legacy tombstones expire naturally this filter becomes dead code in both callers.
238fn legacy_tombstone_filter() -> v2::RowFilter {
239    v2::RowFilter {
240        filter: Some(v2::row_filter::Filter::Chain(v2::row_filter::Chain {
241            filters: vec![
242                column_filter(COLUMN_METADATA),
243                v2::RowFilter {
244                    filter: Some(v2::row_filter::Filter::ValueRegexFilter(
245                        b"^\\{\"is_redirect_tombstone\":true[,}].*".to_vec(),
246                    )),
247                },
248            ],
249        })),
250    }
251}
252
253/// Wraps `inner` so that it only matches live (non-expired) cells.
254///
255/// Uses the rounded access time directly. Legacy fractional cell timestamps can be excluded
256/// up to one second before their rounded metadata deadline; new writes are second-aligned.
257fn live_row_filter(inner: v2::RowFilter, now: Timestamp) -> v2::RowFilter {
258    v2::RowFilter {
259        filter: Some(v2::row_filter::Filter::Interleave(
260            v2::row_filter::Interleave {
261                filters: vec![
262                    // Manual family: never expires.
263                    v2::RowFilter {
264                        filter: Some(v2::row_filter::Filter::Chain(v2::row_filter::Chain {
265                            filters: vec![
266                                v2::RowFilter {
267                                    filter: Some(v2::row_filter::Filter::FamilyNameRegexFilter(
268                                        format!("^{FAMILY_MANUAL}$"),
269                                    )),
270                                },
271                                inner.clone(),
272                            ],
273                        })),
274                    },
275                    // GC family: only match non-expired cells.
276                    v2::RowFilter {
277                        filter: Some(v2::row_filter::Filter::Chain(v2::row_filter::Chain {
278                            filters: vec![
279                                v2::RowFilter {
280                                    filter: Some(v2::row_filter::Filter::FamilyNameRegexFilter(
281                                        format!("^{FAMILY_GC}$"),
282                                    )),
283                                },
284                                v2::RowFilter {
285                                    filter: Some(v2::row_filter::Filter::TimestampRangeFilter(
286                                        v2::TimestampRange {
287                                            start_timestamp_micros: now.as_micros() as i64,
288                                            end_timestamp_micros: 0,
289                                        },
290                                    )),
291                                },
292                                inner,
293                            ],
294                        })),
295                    },
296                ],
297            },
298        )),
299    }
300}
301
302/// Builds a raw row filter that matches any live tombstone row, new- or legacy-format.
303///
304/// New format: presence of the `r` column.
305/// Legacy format: `is_redirect_tombstone: true` in the `m` column JSON.
306///
307/// After legacy tombstones expire naturally this simplifies to just
308/// `column_filter(COLUMN_REDIRECT)`.
309fn tombstone_filter(access_time: Timestamp) -> v2::RowFilter {
310    let filter = v2::RowFilter {
311        filter: Some(v2::row_filter::Filter::Interleave(
312            v2::row_filter::Interleave {
313                filters: vec![column_filter(COLUMN_REDIRECT), legacy_tombstone_filter()],
314            },
315        )),
316    };
317    live_row_filter(filter, access_time)
318}
319
320/// Returns a [`MutatePredicate`] that matches any live tombstone row.
321///
322/// Mutations will not run on live tombstones (`predicate_matched == false`). They _will_
323/// run on expired tombstones as well as non-tombstones. Used by
324/// [`BigTableBackend::put_non_tombstone`] and [`BigTableBackend::compare_and_write`] as
325/// the `CheckAndMutateRow` predicate.
326///
327/// This predicate cannot distinguish an empty row from a row holding a regular object; a caller
328/// that needs to know whether its mutation hit anything wants [`non_tombstone_predicate`].
329fn tombstone_predicate(access_time: Timestamp) -> MutatePredicate {
330    MutatePredicate::Exclude(tombstone_filter(access_time))
331}
332
333/// Returns a [`MutatePredicate`] that is the logical negation of [`tombstone_predicate`];
334/// it matches everything _except_ live tombstones.
335///
336/// Mutations run only when the predicate matches (`predicate_matched == true`). They will
337/// run on expired tombstones as well as non-tombstones. The match result doubles as a
338/// "was a row removed?" signal. Used by [`BigTableBackend::delete_non_tombstone`] as the
339/// `CheckAndMutateRow` predicate.
340///
341/// Built as a `Condition` filter:
342/// - Predicate: [`tombstone_filter`] -> is a live tombstone present?
343/// - True branch: `BlockAllFilter` -> match nothing; live tombstones should be preserved
344/// - False branch: `PassAllFilter` -> match everything: expired tombstones and non-tombstones
345fn non_tombstone_predicate(access_time: Timestamp) -> MutatePredicate {
346    MutatePredicate::Include(v2::RowFilter {
347        filter: Some(v2::row_filter::Filter::Condition(Box::new(
348            v2::row_filter::Condition {
349                predicate_filter: Some(Box::new(tombstone_filter(access_time))),
350                true_filter: Some(Box::new(v2::RowFilter {
351                    filter: Some(v2::row_filter::Filter::BlockAllFilter(true)),
352                })),
353                false_filter: Some(Box::new(v2::RowFilter {
354                    filter: Some(v2::row_filter::Filter::PassAllFilter(true)),
355                })),
356            },
357        ))),
358    })
359}
360
361/// Builds an anchored regex pattern (`^…$`) that matches `value` literally.
362///
363/// Uses [`regex::escape`] so that metacharacters in storage paths (`.`, `/`, etc.)
364/// are treated as literal bytes.
365fn exact_value_regex(value: &str) -> Vec<u8> {
366    format!("^{}$", regex::escape(value)).into_bytes()
367}
368
369/// Matches tombstones whose redirect resolves to `target`.
370///
371/// ## Predicate Matches
372///
373/// Must be used with `true_mutations` and `predicate_matched == true`.
374///
375/// ## Details
376///
377/// Always includes an exact match on the `r` (redirect) column:
378/// - Chain: `r` column present AND value == `target` storage path
379///
380/// When `target == own_id` (the caller expects a legacy identity redirect), the
381/// exact match is wrapped in an Interleave with two additional fallbacks:
382/// - Chain: `r` column present AND value == `b""` (empty-sentinel written before the redirect
383///   column stored the path)
384/// - Chain: `m` column present AND value matches `{"is_redirect_tombstone":true...}` regex
385///   (legacy metadata format predating the dedicated `r` column)
386fn redirect_target_filter(
387    target: &ObjectId,
388    own_id: &ObjectId,
389    access_time: Timestamp,
390) -> v2::RowFilter {
391    let target_path = exact_value_regex(&target.as_storage_path().to_string());
392
393    let exact_match = v2::RowFilter {
394        filter: Some(v2::row_filter::Filter::Chain(v2::row_filter::Chain {
395            filters: vec![
396                column_filter(COLUMN_REDIRECT),
397                v2::RowFilter {
398                    filter: Some(v2::row_filter::Filter::ValueRegexFilter(target_path)),
399                },
400            ],
401        })),
402    };
403
404    if target != own_id {
405        return live_row_filter(exact_match, access_time);
406    }
407
408    let empty_redirect_match = v2::RowFilter {
409        filter: Some(v2::row_filter::Filter::Chain(v2::row_filter::Chain {
410            filters: vec![
411                column_filter(COLUMN_REDIRECT),
412                v2::RowFilter {
413                    filter: Some(v2::row_filter::Filter::ValueRegexFilter(b"^$".to_vec())),
414                },
415            ],
416        })),
417    };
418
419    // Also match legacy tombstones that resolve to the HV id:
420    // - empty `r` value (written before the redirect column stored the path)
421    // - legacy `m` column format (`is_redirect_tombstone: true`)
422    let filter = v2::RowFilter {
423        filter: Some(v2::row_filter::Filter::Interleave(
424            v2::row_filter::Interleave {
425                filters: vec![exact_match, empty_redirect_match, legacy_tombstone_filter()],
426            },
427        )),
428    };
429    live_row_filter(filter, access_time)
430}
431
432/// Returns a [`MutatePredicate`] that matches tombstones whose redirect resolves to either `old` or `new`.
433///
434/// Mutations run only when the predicate matches (`predicate_matched == true`):
435/// equivalent to `t == old || t == new`. Built as an Interleave of two
436/// [`redirect_target_filter`] calls — yields cells iff at least one branch matches.
437/// An absent row or non-tombstone row yields 0 cells, so `predicate_matched = false` (conflict).
438fn update_predicate(
439    old: &ObjectId,
440    new: &ObjectId,
441    own_id: &ObjectId,
442    access_time: Timestamp,
443) -> MutatePredicate {
444    MutatePredicate::Include(v2::RowFilter {
445        filter: Some(v2::row_filter::Filter::Interleave(
446            v2::row_filter::Interleave {
447                filters: vec![
448                    redirect_target_filter(old, own_id, access_time),
449                    redirect_target_filter(new, own_id, access_time),
450                ],
451            },
452        )),
453    })
454}
455
456/// Returns a [`MutatePredicate`] that matches rows where no conflicting tombstone exists.
457///
458/// Mutations run only when the row is conflict-free (`predicate_matched == false`):
459/// no tombstone is present, or the tombstone's redirect already points to `target`.
460///
461/// Built as an inverted `Condition` filter:
462/// - Predicate: [`redirect_target_filter`]`(target)` — tombstone already points to `target`?
463/// - True branch: `BlockAllFilter` → 0 cells (already at target, safe state).
464/// - False branch: [`tombstone_filter`] → 0 cells when no tombstone exists.
465///
466/// Both safe states yield 0 cells, so `predicate_matched = false` in both cases.
467fn optional_target_predicate(
468    target: &ObjectId,
469    own_id: &ObjectId,
470    access_time: Timestamp,
471) -> MutatePredicate {
472    MutatePredicate::Exclude(v2::RowFilter {
473        filter: Some(v2::row_filter::Filter::Condition(Box::new(
474            v2::row_filter::Condition {
475                predicate_filter: Some(Box::new(redirect_target_filter(
476                    target,
477                    own_id,
478                    access_time,
479                ))),
480                true_filter: Some(Box::new(v2::RowFilter {
481                    filter: Some(v2::row_filter::Filter::BlockAllFilter(true)),
482                })),
483                false_filter: Some(Box::new(tombstone_filter(access_time))),
484            },
485        ))),
486    })
487}
488
489fn exact_expiry_filter(start: i64) -> Result<v2::RowFilter> {
490    let end = start.checked_add(1).ok_or_else(|| {
491        Error::new(
492            ErrorKind::Internal,
493            "building Bigtable expiration predicate",
494        )
495    })?;
496    Ok(v2::RowFilter {
497        filter: Some(v2::row_filter::Filter::Chain(v2::row_filter::Chain {
498            filters: vec![
499                v2::RowFilter {
500                    filter: Some(v2::row_filter::Filter::FamilyNameRegexFilter(format!(
501                        "^{FAMILY_GC}$"
502                    ))),
503                },
504                v2::RowFilter {
505                    filter: Some(v2::row_filter::Filter::TimestampRangeFilter(
506                        v2::TimestampRange {
507                            start_timestamp_micros: start,
508                            end_timestamp_micros: end,
509                        },
510                    )),
511                },
512            ],
513        })),
514    })
515}
516
517/// Matches an inline row whose metadata cell has the observed expiry timestamp.
518fn inline_expiry_predicate(
519    observed_expiry: i64,
520    access_time: Timestamp,
521) -> Result<MutatePredicate> {
522    let inline_at_expiry = v2::RowFilter {
523        filter: Some(v2::row_filter::Filter::Chain(v2::row_filter::Chain {
524            filters: vec![
525                column_filter(COLUMN_METADATA),
526                exact_expiry_filter(observed_expiry)?,
527            ],
528        })),
529    };
530
531    Ok(MutatePredicate::Include(v2::RowFilter {
532        filter: Some(v2::row_filter::Filter::Condition(Box::new(
533            v2::row_filter::Condition {
534                predicate_filter: Some(Box::new(tombstone_filter(access_time))),
535                true_filter: Some(Box::new(v2::RowFilter {
536                    filter: Some(v2::row_filter::Filter::BlockAllFilter(true)),
537                })),
538                false_filter: Some(Box::new(inline_at_expiry)),
539            },
540        ))),
541    }))
542}
543
544fn redirect_expiry_predicate(
545    target: &ObjectId,
546    own_id: &ObjectId,
547    observed_expiry: i64,
548    access_time: Timestamp,
549) -> Result<MutatePredicate> {
550    Ok(MutatePredicate::Include(v2::RowFilter {
551        filter: Some(v2::row_filter::Filter::Chain(v2::row_filter::Chain {
552            filters: vec![
553                redirect_target_filter(target, own_id, access_time),
554                exact_expiry_filter(observed_expiry)?,
555            ],
556        })),
557    }))
558}
559
560/// The condition under which a [`BigTableBackend::check_and_mutate`] write proceeds.
561///
562/// Each variant pairs a row filter with the state that makes the write safe:
563/// `Include` writes when the row matches; `Exclude` writes when it does not.
564#[derive(Clone, Debug)]
565enum MutatePredicate {
566    /// Write proceeds when the filter matches the row.
567    ///
568    /// Mutations run in `true_mutations`; succeeds when `predicate_matched == true`.
569    Include(v2::RowFilter),
570    /// Write proceeds when the filter does not match the row.
571    ///
572    /// Mutations run in `false_mutations`; succeeds when `predicate_matched == false`.
573    Exclude(v2::RowFilter),
574}
575
576/// Creates a row filter that reads all non-payload columns (`m`, `r`).
577///
578/// Used by metadata-only reads to avoid fetching the (potentially large) payload column
579/// while still being able to detect both new- and legacy-format tombstones.
580fn metadata_filter() -> v2::RowFilter {
581    v2::RowFilter {
582        filter: Some(v2::row_filter::Filter::ColumnQualifierRegexFilter(
583            FILTER_META.to_owned(),
584        )),
585    }
586}
587
588fn mutation(mutation: mutation::Mutation) -> v2::Mutation {
589    v2::Mutation {
590        mutation: Some(mutation),
591    }
592}
593
594/// Creates a `DeleteFromRow` mutation wrapped in the outer [`v2::Mutation`] envelope.
595fn delete_row_mutation() -> v2::Mutation {
596    mutation(mutation::Mutation::DeleteFromRow(
597        mutation::DeleteFromRow {},
598    ))
599}
600
601/// Builds the three mutations that write an object row: clear existing data,
602/// then set the payload and metadata cells. Returns them with the resulting row size.
603///
604/// Used by both [`BigTableBackend::put_row`] (unconditional write) and
605/// [`BigTableBackend::put_non_tombstone`] (conditional write).
606fn object_mutations(
607    path: &[u8],
608    mut metadata: Metadata,
609    payload: Vec<u8>,
610) -> Result<([v2::Mutation; 3], u64)> {
611    let (family, timestamp_micros) = match metadata.time_expires {
612        None => (FAMILY_MANUAL, -1),
613        Some(deadline) => (FAMILY_GC, deadline.as_micros() as i64),
614    };
615
616    // Record the payload size in the metadata before persisting it.
617    metadata.size = Some(payload.len());
618
619    let metadata_bytes = serde_json::to_vec(&metadata)
620        .context(ErrorKind::Internal, "encoding Bigtable object metadata")?;
621
622    let mutations = [
623        // NB: We explicitly delete the row to clear metadata on overwrite.
624        delete_row_mutation(),
625        mutation(mutation::Mutation::SetCell(mutation::SetCell {
626            family_name: family.to_owned(),
627            column_qualifier: COLUMN_PAYLOAD.to_owned(),
628            timestamp_micros,
629            value: payload,
630        })),
631        mutation(mutation::Mutation::SetCell(mutation::SetCell {
632            family_name: family.to_owned(),
633            column_qualifier: COLUMN_METADATA.to_owned(),
634            timestamp_micros,
635            value: metadata_bytes,
636        })),
637    ];
638
639    let size = row_size(path, &mutations);
640    Ok((mutations, size))
641}
642
643/// Approximates the bytes a row occupies, as its key plus every cell value written.
644///
645/// This function does not distinguish between object rows and tombstone rows. It does not
646/// include Bigtable's own overhead.
647fn row_size(path: &[u8], mutations: &[v2::Mutation]) -> u64 {
648    let cells: usize = mutations
649        .iter()
650        .filter_map(|m| match &m.mutation {
651            Some(mutation::Mutation::SetCell(cell)) => Some(cell.value.len()),
652            _ => None,
653        })
654        .sum();
655
656    (path.len() + cells) as u64
657}
658
659/// Builds the two mutations that write a tombstone row: clear existing data,
660/// then set the redirect cell.
661///
662/// Used by both unconditional tombstone writes and the conditional expiry-extension paths.
663fn tombstone_mutations(tombstone: &Tombstone) -> [v2::Mutation; 2] {
664    let (family, timestamp_micros) = match tombstone.time_expires {
665        None => (FAMILY_MANUAL, -1),
666        Some(deadline) => (FAMILY_GC, deadline.as_micros() as i64),
667    };
668
669    [
670        delete_row_mutation(),
671        mutation(mutation::Mutation::SetCell(mutation::SetCell {
672            family_name: family.to_owned(),
673            column_qualifier: COLUMN_REDIRECT.to_owned(),
674            timestamp_micros,
675            value: tombstone.target.as_storage_path().to_string().into_bytes(),
676        })),
677    ]
678}
679
680/// Subset of [`Metadata`] that indicates a row is a tombstone instead of a real object.
681///
682/// Used to construct [`RowData`].
683#[derive(Debug, Deserialize)]
684struct LegacyTombstoneMeta {
685    /// Internal redirect tombstone marker.
686    ///
687    /// When `true`, this object is a legacy tombstone. This implies:
688    ///  - the payload is empty
689    ///  - metadata is not meaningful
690    ///  - the `r` column is not present
691    #[serde(default)]
692    is_redirect_tombstone: bool,
693}
694
695/// Parsed data from a BigTable row's cells.
696enum RowData {
697    /// A regular object row with payload and metadata.
698    Object {
699        metadata: Metadata,
700        payload: Vec<u8>,
701        /// Original GC timestamp for exact CAS matching, including legacy fractional seconds.
702        expiry_micros: i64,
703    },
704    /// A tombstone row indicating the real payload lives on the long-term backend.
705    Tombstone {
706        target: Vec<u8>,
707        time_expires: Option<Timestamp>,
708        /// Original GC timestamp for exact CAS matching, including legacy fractional seconds.
709        expiry_micros: i64,
710    },
711}
712
713impl RowData {
714    /// Parses a set of row cells into a [`RowData`].
715    ///
716    /// New-format tombstones are identified by the presence of the `r` column.
717    /// Legacy tombstones (written before the column migration) are identified by
718    /// `is_redirect_tombstone: true` in the `m` column JSON; a
719    /// `bigtable.legacy_tombstone_read` metric is emitted on each such read.
720    fn from_cells(cells: Vec<RowCell>) -> Result<Self> {
721        let mut metadata_opt: Option<Metadata> = None;
722        let mut redirect_detected = false;
723        let mut redirect_target = Vec::new();
724        let mut expire_at = None;
725        let mut expiry_micros = 0;
726        let mut payload = Vec::new();
727
728        for cell in cells {
729            // NB: All cells are written with the same timestamp; last write is safe.
730
731            // Only derive expiration from GC-family cells — manual-family cells
732            // use server-assigned timestamps that don't represent expiration.
733            if cell.family_name == FAMILY_GC {
734                expiry_micros = cell.timestamp_micros;
735                expire_at = Some(Timestamp::from_unix_micros(expiry_micros).context(
736                    ErrorKind::CorruptData,
737                    "decoding Bigtable expiration timestamp",
738                )?);
739            }
740
741            match cell.qualifier.as_slice() {
742                COLUMN_REDIRECT => {
743                    redirect_detected = true;
744                    redirect_target = cell.value;
745                }
746                COLUMN_PAYLOAD => {
747                    payload = cell.value;
748                }
749                COLUMN_METADATA => {
750                    if let Ok(legacy_meta) =
751                        serde_json::from_slice::<LegacyTombstoneMeta>(&cell.value)
752                        && legacy_meta.is_redirect_tombstone
753                    {
754                        redirect_detected = true;
755                        objectstore_metrics::count!("bigtable.legacy_tombstone_read");
756                    } else {
757                        metadata_opt = Some(serde_json::from_slice(&cell.value).context(
758                            ErrorKind::CorruptData,
759                            "decoding Bigtable object metadata",
760                        )?);
761                    }
762                }
763                _ => {}
764            }
765        }
766
767        Ok(if redirect_detected {
768            RowData::Tombstone {
769                target: redirect_target,
770                time_expires: expire_at,
771                expiry_micros,
772            }
773        } else {
774            // Metadata may have been skipped by a payload-only internal read.
775            let mut metadata = metadata_opt.unwrap_or_default();
776            metadata.time_expires = expire_at;
777            RowData::Object {
778                metadata,
779                payload,
780                expiry_micros,
781            }
782        })
783    }
784
785    /// Returns the resolved expiration timestamp for this row, regardless of variant.
786    fn time_expires(&self) -> Option<Timestamp> {
787        match self {
788            RowData::Object { metadata, .. } => metadata.time_expires,
789            RowData::Tombstone { time_expires, .. } => *time_expires,
790        }
791    }
792
793    /// Returns `true` if this row is expired as of the given `time`.
794    ///
795    /// Only applies to rows with an expiration deadline.
796    fn expires_before(&self, time: Timestamp) -> bool {
797        self.time_expires().is_some_and(|ts| ts < time)
798    }
799}
800
801/// Parses the raw `r` column bytes into a redirect target [`ObjectId`].
802///
803/// For tombstones with an empty `r` value, falls back to the ID of the tombstone
804/// itself and emits a `bigtable.empty_redirect_read` metric so deployments can
805/// track when it is safe to remove the legacy empty-value code path.
806fn parse_redirect_target(redirect_path: &[u8], tombstone_id: &ObjectId) -> Result<ObjectId> {
807    if redirect_path.is_empty() {
808        objectstore_metrics::count!("bigtable.empty_redirect_read");
809        Ok(tombstone_id.clone())
810    } else {
811        let redirect_str = std::str::from_utf8(redirect_path)
812            .context(ErrorKind::CorruptData, "decoding Bigtable redirect target")?;
813        ObjectId::from_storage_path(redirect_str)
814            .ok_or_else(|| Error::new(ErrorKind::CorruptData, "parsing Bigtable redirect target"))
815    }
816}
817
818impl BigTableBackend {
819    /// Creates a new [`BigTableBackend`] from the given `config`.
820    ///
821    /// Pass an `endpoint` in the config to connect to a local emulator; omit it to use real GCP
822    /// credentials. `connections` controls the gRPC connection pool size (defaults to 1).
823    /// A `PingAndWarm` request is sent through the pool every 10 seconds in an effort
824    /// to keep the connections active.
825    pub async fn new(
826        config: BigTableConfig,
827        streams: &ChangeStreamFactory,
828    ) -> anyhow::Result<Self> {
829        let BigTableConfig {
830            endpoint,
831            project_id,
832            instance_name,
833            table_name,
834            connections,
835            rpc_timeout,
836            cogs,
837        } = config;
838        let change_stream = streams.build(cogs.as_ref());
839
840        let bigtable = if let Some(ref endpoint) = endpoint {
841            BigTableConnection::new_with_emulator(
842                endpoint,
843                &project_id,
844                &instance_name,
845                false, // is_read_only
846                connections.unwrap_or(1),
847                Some(rpc_timeout),
848            )?
849        } else {
850            let token_provider = PrefetchingTokenProvider::gcp_auth(TOKEN_SCOPES).await?;
851            BigTableConnection::new_with_managed_transport(
852                &project_id,
853                &instance_name,
854                false, // is_read_only
855                Some(rpc_timeout),
856                Arc::new(token_provider),
857                connections.unwrap_or(1),
858                true, // prime_channels
859                None, // app_profile_id
860                MAX_CHANNEL_AGE,
861                Some(Duration::from_secs(10)), // periodic PingAndWarm
862            )
863            .await?
864        };
865
866        let client = bigtable.client();
867
868        Ok(Self {
869            bigtable,
870            instance_path: format!("projects/{project_id}/instances/{instance_name}"),
871            table_path: client.get_full_table_name(&table_name),
872            table_name,
873            change_stream,
874        })
875    }
876
877    /// Reads a single row by key, returning parsed row data.
878    ///
879    /// Returns `None` if the row is absent or has expired.
880    #[tracing::instrument(level = "debug", fields(action, result), skip_all)]
881    async fn read_row(
882        &self,
883        path: &[u8],
884        action: &'static str,
885        access_time: Timestamp,
886        filter: Option<v2::RowFilter>,
887    ) -> Result<Option<RowData>> {
888        let request = v2::ReadRowsRequest {
889            table_name: self.table_path.clone(),
890            rows: Some(v2::RowSet {
891                row_keys: vec![path.to_owned()],
892                row_ranges: vec![],
893            }),
894            filter,
895            rows_limit: 1,
896            ..Default::default()
897        };
898
899        let response = retry(action, || async {
900            self.bigtable.client().read_rows(request.clone()).await
901        })
902        .await?;
903        debug_assert!(response.len() <= 1, "Expected at most one row");
904
905        let span = tracing::Span::current();
906        let Some((_, cells)) = response.into_iter().next() else {
907            objectstore_log::debug!("Object not found");
908            span.record("result", "miss");
909            return Ok(None);
910        };
911
912        let row = RowData::from_cells(cells)?;
913        Ok(if row.expires_before(access_time) {
914            span.record("result", "expired");
915            None
916        } else {
917            span.record("result", "hit");
918            Some(row)
919        })
920    }
921
922    #[tracing::instrument(level = "debug", fields(action), skip_all)]
923    async fn mutate(
924        &self,
925        path: Vec<u8>,
926        mutations: impl Into<Vec<v2::Mutation>>,
927        action: &'static str,
928    ) -> Result<v2::MutateRowResponse> {
929        let request = v2::MutateRowRequest {
930            table_name: self.table_path.clone(),
931            row_key: path,
932            mutations: mutations.into(),
933            ..Default::default()
934        };
935
936        let response = retry(action, || async {
937            self.bigtable.client().mutate_row(request.clone()).await
938        })
939        .await?;
940
941        Ok(response.into_inner())
942    }
943
944    /// Writes an object row, returning the size of the row it wrote.
945    async fn put_row(
946        &self,
947        path: Vec<u8>,
948        metadata: Metadata,
949        payload: Vec<u8>,
950        action: &'static str,
951    ) -> Result<(v2::MutateRowResponse, u64)> {
952        let (mutations, size) = object_mutations(&path, metadata, payload)?;
953        let response = self.mutate(path, mutations, action).await?;
954        Ok((response, size))
955    }
956
957    /// Executes a `CheckAndMutateRow` request.
958    #[tracing::instrument(level = "debug", fields(action = context), skip_all)]
959    async fn check_and_mutate(
960        &self,
961        row_key: Vec<u8>,
962        predicate: MutatePredicate,
963        mutations: impl Into<Vec<v2::Mutation>>,
964        context: &'static str,
965    ) -> Result<bool> {
966        let (filter, true_mutations, false_mutations, success_on_match) = match predicate {
967            MutatePredicate::Include(f) => (f, mutations.into(), vec![], true),
968            MutatePredicate::Exclude(f) => (f, vec![], mutations.into(), false),
969        };
970
971        let request = v2::CheckAndMutateRowRequest {
972            table_name: self.table_path.clone(),
973            row_key,
974            predicate_filter: Some(filter),
975            true_mutations,
976            false_mutations,
977            ..Default::default()
978        };
979
980        let future = retry(context, || async {
981            self.bigtable
982                .client()
983                .check_and_mutate_row(request.clone())
984                .await
985        });
986
987        Ok(future.await?.predicate_matched == success_on_match)
988    }
989}
990
991#[async_trait::async_trait]
992impl Backend for BigTableBackend {
993    fn name(&self) -> &'static str {
994        "bigtable"
995    }
996
997    #[tracing::instrument(level = "debug", fields(?id), skip_all)]
998    async fn put_object(
999        &self,
1000        id: &ObjectId,
1001        metadata: &Metadata,
1002        mut stream: ClientStream,
1003        _access_time: Timestamp,
1004    ) -> Result<PutResponse> {
1005        objectstore_log::debug!("Writing to Bigtable backend");
1006        self.change_stream
1007            .begin_write(id, metadata.time_expires)
1008            .await?;
1009        let path = id.as_storage_path().to_string().into_bytes();
1010
1011        let mut payload = ChunkedBytes::new(0);
1012        while let Some(chunk) = stream.try_next().await? {
1013            payload.push(chunk);
1014        }
1015
1016        let (_, size) = self
1017            .put_row(path, metadata.clone(), payload.into_bytes().into(), "put")
1018            .await?;
1019        self.change_stream
1020            .commit_write(id, size, metadata.time_expires)
1021            .await;
1022
1023        Ok(())
1024    }
1025
1026    #[tracing::instrument(level = "debug", skip(self))]
1027    async fn get_object(
1028        &self,
1029        id: &ObjectId,
1030        access_time: Timestamp,
1031        range: Option<ByteRange>,
1032    ) -> Result<GetResponse> {
1033        match self.get_tiered_object(id, access_time, range).await? {
1034            TieredGet::Object(metadata, content_range, payload) => {
1035                Ok(Some((metadata, content_range, payload)))
1036            }
1037            TieredGet::Tombstone(_) => Err(ErrorKind::UnexpectedTombstone.into()),
1038            TieredGet::NotFound => Ok(None),
1039        }
1040    }
1041
1042    #[tracing::instrument(level = "debug", skip(self))]
1043    async fn get_metadata(
1044        &self,
1045        id: &ObjectId,
1046        access_time: Timestamp,
1047    ) -> Result<MetadataResponse> {
1048        match self.get_tiered_metadata(id, access_time).await? {
1049            TieredMetadata::Object(metadata) => Ok(Some(metadata)),
1050            TieredMetadata::Tombstone(_) => Err(ErrorKind::UnexpectedTombstone.into()),
1051            TieredMetadata::NotFound => Ok(None),
1052        }
1053    }
1054
1055    async fn set_expiry(
1056        &self,
1057        id: &ObjectId,
1058        target: ExpiryUpdate,
1059        access_time: Timestamp,
1060    ) -> Result<SetExpiryResponse> {
1061        self.compare_and_update(id, None, TieredUpdate::SetExpiry(target), access_time)
1062            .await
1063    }
1064
1065    #[tracing::instrument(level = "debug", skip(self))]
1066    async fn delete_object(
1067        &self,
1068        id: &ObjectId,
1069        _access_time: Timestamp,
1070    ) -> Result<DeleteResponse> {
1071        objectstore_log::debug!("Deleting from Bigtable backend");
1072
1073        let path = id.as_storage_path().to_string().into_bytes();
1074        self.mutate(path, [delete_row_mutation()], "delete").await?;
1075        self.change_stream.commit_delete(id).await;
1076
1077        Ok(())
1078    }
1079
1080    async fn join(&self) {
1081        flush_change_stream(&self.change_stream).await;
1082    }
1083}
1084
1085#[async_trait::async_trait]
1086impl HighVolumeBackend for BigTableBackend {
1087    async fn create_upload_marker(
1088        &self,
1089        revision: &ObjectId,
1090        time_expires: Timestamp,
1091    ) -> Result<()> {
1092        self.change_stream
1093            .begin_write(revision, Some(time_expires))
1094            .await?;
1095        let mutations = vec![mutation(mutation::Mutation::SetCell(mutation::SetCell {
1096            family_name: FAMILY_GC.to_owned(),
1097            column_qualifier: COLUMN_UPLOAD.to_vec(),
1098            timestamp_micros: time_expires.as_micros() as i64,
1099            value: vec![1],
1100        }))];
1101        let path = revision.as_upload_path().to_string().into_bytes();
1102        let size = row_size(&path, &mutations);
1103        self.mutate(path, mutations, "create_upload_marker").await?;
1104        self.change_stream
1105            .commit_write(revision, size, Some(time_expires))
1106            .await;
1107        Ok(())
1108    }
1109
1110    async fn has_upload_marker(&self, revision: &ObjectId, access_time: Timestamp) -> Result<bool> {
1111        let request = v2::ReadRowsRequest {
1112            table_name: self.table_path.clone(),
1113            rows: Some(v2::RowSet {
1114                row_keys: vec![revision.as_upload_path().to_string().into_bytes()],
1115                row_ranges: vec![],
1116            }),
1117            filter: Some(live_row_filter(column_filter(COLUMN_UPLOAD), access_time)),
1118            rows_limit: 1,
1119            ..Default::default()
1120        };
1121        let rows = retry("has_upload_marker", || async {
1122            self.bigtable.client().read_rows(request.clone()).await
1123        })
1124        .await?;
1125        Ok(!rows.is_empty())
1126    }
1127
1128    async fn delete_upload_marker(
1129        &self,
1130        revision: &ObjectId,
1131        access_time: Timestamp,
1132    ) -> Result<bool> {
1133        let deleted = self
1134            .check_and_mutate(
1135                revision.as_upload_path().to_string().into_bytes(),
1136                MutatePredicate::Include(live_row_filter(
1137                    column_filter(COLUMN_UPLOAD),
1138                    access_time,
1139                )),
1140                vec![delete_row_mutation()],
1141                "delete_upload_marker",
1142            )
1143            .await?;
1144        if deleted {
1145            self.change_stream.commit_delete(revision).await;
1146        }
1147        Ok(deleted)
1148    }
1149
1150    #[tracing::instrument(level = "debug", fields(?id), skip_all)]
1151    async fn put_non_tombstone(
1152        &self,
1153        id: &ObjectId,
1154        metadata: &Metadata,
1155        payload: Bytes,
1156        access_time: Timestamp,
1157    ) -> Result<Option<Tombstone>> {
1158        objectstore_log::debug!("Conditional put to Bigtable backend");
1159        self.change_stream
1160            .begin_write(id, metadata.time_expires)
1161            .await?;
1162
1163        let path = id.as_storage_path().to_string().into_bytes();
1164        let (mutations, size) = object_mutations(&path, metadata.clone(), payload.to_vec())?;
1165
1166        for _ in 0..CAS_RETRY_COUNT {
1167            let write_succeeded = self
1168                .check_and_mutate(
1169                    path.clone(),
1170                    tombstone_predicate(access_time),
1171                    mutations.clone(),
1172                    "put_non_tombstone",
1173                )
1174                .await?;
1175
1176            if write_succeeded {
1177                self.change_stream
1178                    .commit_write(id, size, metadata.time_expires)
1179                    .await;
1180                return Ok(None);
1181            }
1182
1183            // A tombstone was present: read its data for the caller.
1184            let row = self
1185                .read_row(
1186                    &path,
1187                    "put_non_tombstone",
1188                    access_time,
1189                    Some(metadata_filter()),
1190                )
1191                .await?;
1192
1193            match row {
1194                Some(RowData::Tombstone {
1195                    target,
1196                    time_expires,
1197                    ..
1198                }) => {
1199                    return Ok(Some(Tombstone {
1200                        target: parse_redirect_target(&target, id)?,
1201                        time_expires,
1202                    }));
1203                }
1204                // Race: Tombstone was replaced by an object, retry to overwrite
1205                Some(RowData::Object { .. }) => continue,
1206                // Race: Tombstone was deleted, retry to write.
1207                None => continue,
1208            }
1209        }
1210
1211        Err(Error::new(
1212            ErrorKind::Internal,
1213            "Bigtable put race exhausted",
1214        ))
1215    }
1216
1217    #[tracing::instrument(level = "debug", skip(self))]
1218    async fn get_tiered_object(
1219        &self,
1220        id: &ObjectId,
1221        access_time: Timestamp,
1222        range: Option<ByteRange>,
1223    ) -> Result<TieredGet> {
1224        objectstore_log::debug!("Reading from Bigtable backend");
1225        let path = id.as_storage_path().to_string().into_bytes();
1226
1227        let Some(row) = self
1228            .read_row(&path, "get_tiered_object", access_time, None)
1229            .await?
1230        else {
1231            return Ok(TieredGet::NotFound);
1232        };
1233
1234        Ok(match row {
1235            RowData::Tombstone {
1236                target,
1237                time_expires,
1238                ..
1239            } => TieredGet::Tombstone(Tombstone {
1240                target: parse_redirect_target(&target, id)?,
1241                time_expires,
1242            }),
1243            RowData::Object {
1244                metadata, payload, ..
1245            } => {
1246                let mut metadata = metadata;
1247                let payload = Bytes::from(payload);
1248                if metadata.size.is_none() {
1249                    // If object size wasn't written into the metadata, re-compute it now
1250                    metadata.size = Some(payload.len());
1251                }
1252
1253                let (content_range, payload) = apply_range(payload, range)?;
1254                TieredGet::Object(metadata, content_range, crate::stream::single(payload))
1255            }
1256        })
1257    }
1258
1259    #[tracing::instrument(level = "debug", skip(self))]
1260    async fn get_tiered_metadata(
1261        &self,
1262        id: &ObjectId,
1263        access_time: Timestamp,
1264    ) -> Result<TieredMetadata> {
1265        objectstore_log::debug!("Reading metadata from Bigtable backend");
1266        let path = id.as_storage_path().to_string().into_bytes();
1267
1268        // Read metadata and tombstone columns — skip the (potentially large) payload.
1269        // NB: `metadata.size` will only be populated if the size was added to the metadata before
1270        // writing to Bigtable.
1271        let row_opt = self
1272            .read_row(
1273                &path,
1274                "get_tiered_metadata",
1275                access_time,
1276                Some(metadata_filter()),
1277            )
1278            .await?;
1279        let Some(row) = row_opt else {
1280            return Ok(TieredMetadata::NotFound);
1281        };
1282
1283        Ok(match row {
1284            RowData::Tombstone {
1285                target,
1286                time_expires,
1287                ..
1288            } => TieredMetadata::Tombstone(Tombstone {
1289                target: parse_redirect_target(&target, id)?,
1290                time_expires,
1291            }),
1292            RowData::Object { metadata, .. } => TieredMetadata::Object(metadata),
1293        })
1294    }
1295
1296    #[tracing::instrument(level = "debug", skip(self))]
1297    async fn compare_and_update(
1298        &self,
1299        id: &ObjectId,
1300        current: Option<&ObjectId>,
1301        update: TieredUpdate,
1302        access_time: Timestamp,
1303    ) -> Result<SetExpiryResponse> {
1304        let TieredUpdate::SetExpiry(expiry_target) = update;
1305        let path = id.as_storage_path().to_string().into_bytes();
1306
1307        // Inline extension needs metadata and payload from the same read so a
1308        // successful conditional rewrite can preserve the payload verbatim.
1309        let Some(row) = self
1310            .read_row(&path, "set_expiry", access_time, None)
1311            .await?
1312        else {
1313            return Ok(SetExpiryResponse::NotFound);
1314        };
1315
1316        let (expire_at, predicate, mutations): (_, _, Vec<_>) = match row {
1317            RowData::Object {
1318                metadata,
1319                payload,
1320                expiry_micros,
1321            } => {
1322                if current.is_some() {
1323                    return Ok(SetExpiryResponse::Rejected); // wrong row kind
1324                }
1325                let Some(old_expiry) = metadata.time_expires else {
1326                    return Ok(SetExpiryResponse::Rejected);
1327                };
1328
1329                if old_expiry < access_time {
1330                    return Ok(SetExpiryResponse::NotFound); // already expired
1331                }
1332                let Some(expire_at) = expiry_target.resolve(metadata.time_created, access_time)?
1333                else {
1334                    return Ok(SetExpiryResponse::Rejected);
1335                };
1336                if old_expiry >= expire_at {
1337                    return Ok(SetExpiryResponse::Satisfied(expire_at)); // already satisfied
1338                }
1339
1340                // Observing a live cell here is not atomic with wall-clock
1341                // expiry or Bigtable GC. The conditional write may still lose
1342                // to either and then returns false.
1343                let predicate = inline_expiry_predicate(expiry_micros, access_time)?;
1344                let mut metadata = metadata;
1345                metadata.expiration_policy = common::extended_expiration_policy(
1346                    metadata.expiration_policy,
1347                    metadata.time_created,
1348                    old_expiry,
1349                    expire_at,
1350                )?;
1351                metadata.time_expires = Some(expire_at);
1352                let (mutations, _) = object_mutations(&path, metadata, payload)?;
1353                (expire_at, predicate, mutations.into())
1354            }
1355            RowData::Tombstone {
1356                target,
1357                time_expires,
1358                expiry_micros,
1359            } => {
1360                let Some(expected) = current else {
1361                    return Ok(SetExpiryResponse::Rejected); // wrong row kind
1362                };
1363                let Some(old_expiry) = time_expires else {
1364                    return Ok(SetExpiryResponse::Rejected);
1365                };
1366
1367                let redirect_target = parse_redirect_target(&target, id)?;
1368                if old_expiry < access_time {
1369                    return Ok(SetExpiryResponse::NotFound);
1370                }
1371                if redirect_target != *expected {
1372                    return Ok(SetExpiryResponse::Rejected); // wrong target
1373                }
1374                let Some(expire_at) = expiry_target.resolve(None, access_time)? else {
1375                    return Ok(SetExpiryResponse::Rejected);
1376                };
1377                if old_expiry >= expire_at {
1378                    return Ok(SetExpiryResponse::Satisfied(expire_at)); // already satisfied
1379                }
1380
1381                let predicate =
1382                    redirect_expiry_predicate(expected, id, expiry_micros, access_time)?;
1383                let tombstone = Tombstone {
1384                    target: redirect_target,
1385                    time_expires: Some(expire_at),
1386                };
1387                (expire_at, predicate, tombstone_mutations(&tombstone).into())
1388            }
1389        };
1390
1391        self.change_stream.begin_update(id, Some(expire_at)).await?;
1392        let applied = self
1393            .check_and_mutate(path, predicate, mutations, "set_expiry")
1394            .await?;
1395
1396        if applied {
1397            self.change_stream.commit_update(id, Some(expire_at)).await;
1398        }
1399
1400        Ok(if applied {
1401            SetExpiryResponse::Satisfied(expire_at)
1402        } else {
1403            SetExpiryResponse::Rejected
1404        })
1405    }
1406
1407    #[tracing::instrument(level = "debug", skip(self))]
1408    async fn delete_non_tombstone(
1409        &self,
1410        id: &ObjectId,
1411        access_time: Timestamp,
1412    ) -> Result<Option<Tombstone>> {
1413        objectstore_log::debug!("Conditional delete from Bigtable backend");
1414
1415        let path = id.as_storage_path().to_string().into_bytes();
1416
1417        for _ in 0..CAS_RETRY_COUNT {
1418            let deleted = self
1419                .check_and_mutate(
1420                    path.clone(),
1421                    non_tombstone_predicate(access_time),
1422                    [delete_row_mutation()],
1423                    "delete_non_tombstone",
1424                )
1425                .await?;
1426
1427            if deleted {
1428                self.change_stream.commit_delete(id).await;
1429                return Ok(None);
1430            }
1431
1432            // Nothing was deleted: either a tombstone is in the way, or the row is absent.
1433            // Read the row to find out which, and to hand the tombstone to the caller.
1434            let row = self
1435                .read_row(
1436                    &path,
1437                    "delete_non_tombstone",
1438                    access_time,
1439                    Some(metadata_filter()),
1440                )
1441                .await?;
1442
1443            match row {
1444                Some(RowData::Tombstone {
1445                    target,
1446                    time_expires,
1447                    ..
1448                }) => {
1449                    return Ok(Some(Tombstone {
1450                        target: parse_redirect_target(&target, id)?,
1451                        time_expires,
1452                    }));
1453                }
1454                // Race: An object appeared since the predicate ran, delete the new object now.
1455                Some(RowData::Object { .. }) => continue,
1456                // The row is absent or expired, nothing left to do.
1457                None => return Ok(None),
1458            }
1459        }
1460
1461        Err(Error::new(
1462            ErrorKind::Internal,
1463            "Bigtable delete race exhausted",
1464        ))
1465    }
1466
1467    #[tracing::instrument(level = "debug", skip(self, write))]
1468    async fn compare_and_write(
1469        &self,
1470        id: &ObjectId,
1471        current: Option<&ObjectId>,
1472        write: TieredWrite,
1473        access_time: Timestamp,
1474    ) -> Result<bool> {
1475        objectstore_log::debug!("CAS put to Bigtable backend");
1476
1477        let path = id.as_storage_path().to_string().into_bytes();
1478        let predicate = match (current, write.target()) {
1479            (Some(old), Some(new)) => update_predicate(old, new, id, access_time),
1480            (Some(target), None) => optional_target_predicate(target, id, access_time),
1481            (None, Some(target)) => optional_target_predicate(target, id, access_time),
1482            (None, None) => tombstone_predicate(access_time),
1483        };
1484
1485        // Get the correct set of mutations to apply as well as the new expiration date.
1486        // If we're deleting something, `expires_at` is `None`. If we're writing something
1487        // without an expiration date, `expires_at` is `Some(None)`.
1488        let (mutations, expires_at): (Vec<v2::Mutation>, Option<Option<Timestamp>>) = match write {
1489            TieredWrite::Tombstone(tombstone) => (
1490                tombstone_mutations(&tombstone).into(),
1491                Some(tombstone.time_expires),
1492            ),
1493            TieredWrite::Object(m, p) => {
1494                let expires_at = m.time_expires;
1495                let (mutations, _) = object_mutations(&path, m, p.to_vec())?;
1496                (mutations.into(), Some(expires_at))
1497            }
1498            TieredWrite::Delete => (vec![delete_row_mutation()], None),
1499        };
1500        if let Some(expires_at) = expires_at {
1501            self.change_stream.begin_write(id, expires_at).await?;
1502        }
1503
1504        let written = self
1505            .check_and_mutate(
1506                path.clone(),
1507                predicate,
1508                mutations.clone(),
1509                "compare_and_write",
1510            )
1511            .await?;
1512
1513        match (written, expires_at) {
1514            // Don't record anything if the write didn't succeed
1515            (false, _) => {}
1516            // We wrote something (the inner `expires_at` is `None` for manual GC)
1517            (true, Some(expires_at)) => {
1518                self.change_stream
1519                    .commit_write(id, row_size(&path, &mutations), expires_at)
1520                    .await
1521            }
1522            // We deleted something
1523            (true, None) => self.change_stream.commit_delete(id).await,
1524        }
1525
1526        Ok(written)
1527    }
1528}
1529
1530/// Retries a BigTable RPC on transient errors.
1531async fn retry<T, F>(context: &'static str, f: impl Fn() -> F) -> Result<T>
1532where
1533    F: Future<Output = Result<T, BigTableError>> + Send,
1534{
1535    let mut retry_count = 0usize;
1536
1537    loop {
1538        let attempt_span = tracing::debug_span!(
1539            "bigtable.request",
1540            action = context,
1541            grpc.status = tracing::field::Empty,
1542        );
1543        let attempt = async {
1544            let result = f().await;
1545            let span = tracing::Span::current();
1546            match &result {
1547                Ok(_) => span.record("grpc.status", "ok"),
1548                Err(BigTableError::RpcError(status)) => {
1549                    span.record("grpc.status", tracing::field::debug(status.code()))
1550                }
1551                // Non-RPC error; the error event carries the details.
1552                Err(_) => &span,
1553            };
1554            result
1555        };
1556
1557        match attempt.instrument(attempt_span).await {
1558            Ok(res) => return Ok(res),
1559            Err(e) if retry_count >= REQUEST_RETRY_COUNT || !is_retryable(&e) => {
1560                objectstore_metrics::count!("bigtable.failures", action = context);
1561                return Err(e).context(
1562                    ErrorKind::BackendFailure,
1563                    format!("running Bigtable {context}"),
1564                );
1565            }
1566            Err(e) => {
1567                retry_count += 1;
1568                objectstore_metrics::count!("bigtable.retries", action = context);
1569                objectstore_log::warn!(!!&e, retry_count, context, "Retrying request");
1570            }
1571        }
1572    }
1573}
1574
1575fn is_retryable(error: &BigTableError) -> bool {
1576    match error {
1577        // Transient errors on auth token refresh
1578        BigTableError::GCPAuthError(_) => true,
1579        // Transient GRPC network failures
1580        BigTableError::TransportError(_) => true,
1581        // These could also indicate transient network failures
1582        BigTableError::IoError(_) => true,
1583        BigTableError::TimeoutError(_) => true,
1584
1585        // See https://docs.cloud.google.com/bigtable/docs/status-codes
1586        BigTableError::RpcError(status) => match status.code() {
1587            // Generic retriable status
1588            Code::Unavailable => true,
1589            // Timeouts
1590            Code::Cancelled => true,
1591            Code::DeadlineExceeded => true,
1592            // Token might have refreshed too late
1593            Code::Unauthenticated => true,
1594            // Unspecified, attempt to retry anyways
1595            Code::Aborted => true,
1596            Code::Internal => true,
1597            Code::FailedPrecondition => true,
1598            Code::Unknown => true,
1599            _ => false,
1600        },
1601        _ => false,
1602    }
1603}
1604
1605/// Resolves an optional byte range against a payload buffer, returning the
1606/// applicable content range and the (potentially narrowed) payload.
1607///
1608/// When `range` is `None`, returns the full payload unchanged. Uses
1609/// `Bytes::slice` to avoid copying data.
1610fn apply_range(payload: Bytes, range: Option<ByteRange>) -> Result<(Option<ContentRange>, Bytes)> {
1611    let Some(byte_range) = range else {
1612        return Ok((None, payload));
1613    };
1614
1615    let total = payload.len() as u64;
1616    let content_range = byte_range
1617        .resolve(total)
1618        .ok_or(ErrorKind::RangeNotSatisfiable { total })?;
1619
1620    let sliced = payload.slice(content_range.start as usize..content_range.end as usize + 1);
1621    Ok((Some(content_range), sliced))
1622}
1623
1624#[cfg(test)]
1625mod tests {
1626    use std::collections::BTreeMap;
1627
1628    use anyhow::Result;
1629    #[cfg(feature = "storage-cogs")]
1630    use objectstore_inventory_tracker::{OpType, test_utils::DummyProducer};
1631    use objectstore_types::metadata::ExpirationPolicy;
1632    use objectstore_types::scope::{Scope, Scopes};
1633
1634    use super::*;
1635    use crate::backend::common::ExpiryTarget;
1636    use crate::id::ObjectContext;
1637    use crate::stream;
1638
1639    // NB: Most of these tests require a BigTable emulator running. This is done
1640    // automatically in CI.
1641    //
1642    // Refer to the readme for how to set up the emulator.
1643
1644    fn test_config() -> BigTableConfig {
1645        BigTableConfig {
1646            endpoint: Some("localhost:8086".into()),
1647            project_id: "testing".into(),
1648            instance_name: "objectstore".into(),
1649            table_name: "objectstore".into(),
1650            connections: None,
1651            rpc_timeout: default_rpc_timeout(),
1652            cogs: None,
1653        }
1654    }
1655
1656    async fn create_test_backend() -> Result<BigTableBackend> {
1657        BigTableBackend::new(test_config(), &ChangeStreamFactory::default()).await
1658    }
1659
1660    #[cfg(feature = "storage-cogs")]
1661    async fn create_test_backend_with_change_stream() -> Result<(BigTableBackend, DummyProducer)> {
1662        let (streams, producer) = crate::change_stream::dummy_factory();
1663        let config = BigTableConfig {
1664            cogs: Some(CostTrackerStreamConfig {
1665                shared_resource_id: "bigtable_objectstore".into(),
1666                sample_rate: 1.0,
1667            }),
1668            ..test_config()
1669        };
1670
1671        Ok((BigTableBackend::new(config, &streams).await?, producer))
1672    }
1673
1674    fn make_id() -> ObjectId {
1675        ObjectId::random(ObjectContext {
1676            usecase: "testing".parse().unwrap(),
1677            scopes: Scopes::from_iter([Scope::create("testing", "value").unwrap()]),
1678        })
1679    }
1680
1681    async fn create_object(
1682        backend: &BigTableBackend,
1683        id: &ObjectId,
1684        metadata: &Metadata,
1685        payload: &[u8],
1686        now: Timestamp,
1687    ) -> Result<()> {
1688        let path = id.as_storage_path().to_string().into_bytes();
1689        // Resolve `time_expires` from `now` (as `from_insert_headers` does) unless the test set
1690        // it explicitly, so `object_mutations` has an expiration to persist.
1691        let mut metadata = metadata.clone();
1692        if metadata.time_expires.is_none() {
1693            metadata.time_expires = metadata.expiration_policy.expires_in().map(|ttl| now + ttl);
1694        }
1695        let (mutations, _) = object_mutations(&path, metadata, payload.to_vec())?;
1696        backend.mutate(path, mutations, "test-setup").await?;
1697        Ok(())
1698    }
1699
1700    async fn create_tombstone(
1701        backend: &BigTableBackend,
1702        id: &ObjectId,
1703        tombstone: &Tombstone,
1704    ) -> Result<()> {
1705        let path = id.as_storage_path().to_string().into_bytes();
1706        let mutations = tombstone_mutations(tombstone);
1707        backend.mutate(path, mutations, "test-setup").await?;
1708        Ok(())
1709    }
1710
1711    /// Writes a legacy-format tombstone row directly into Bigtable.
1712    async fn write_legacy_tombstone(
1713        backend: &BigTableBackend,
1714        id: &ObjectId,
1715        expiration_policy: ExpirationPolicy,
1716        time_expires: Option<Timestamp>,
1717    ) -> Result<()> {
1718        let meta = if expiration_policy.is_manual() {
1719            r#"{"is_redirect_tombstone":true}"#.to_owned()
1720        } else {
1721            let policy_json = serde_json::to_string(&expiration_policy).unwrap();
1722            format!(r#"{{"is_redirect_tombstone":true,"expiration_policy":{policy_json}}}"#)
1723        };
1724
1725        let (family, timestamp_micros) = if expiration_policy.is_manual() {
1726            (FAMILY_MANUAL, -1)
1727        } else {
1728            let t =
1729                time_expires.unwrap_or(Timestamp::now() + expiration_policy.expires_in().unwrap());
1730            (FAMILY_GC, t.as_micros() as i64)
1731        };
1732
1733        let path = id.as_storage_path().to_string().into_bytes();
1734        let mutations = [mutation(mutation::Mutation::SetCell(mutation::SetCell {
1735            family_name: family.to_owned(),
1736            column_qualifier: COLUMN_METADATA.to_owned(),
1737            timestamp_micros,
1738            value: meta.into_bytes(),
1739        }))];
1740
1741        backend.mutate(path, mutations, "test-setup").await?;
1742
1743        Ok(())
1744    }
1745
1746    /// Writes a historical `r`/`t` tombstone row with an empty `r` value directly.
1747    async fn write_empty_redirect_tombstone(
1748        backend: &BigTableBackend,
1749        id: &ObjectId,
1750    ) -> Result<()> {
1751        let path = id.as_storage_path().to_string().into_bytes();
1752        let mutations = [
1753            mutation(mutation::Mutation::SetCell(mutation::SetCell {
1754                family_name: FAMILY_MANUAL.to_owned(),
1755                column_qualifier: COLUMN_REDIRECT.to_owned(),
1756                timestamp_micros: -1,
1757                value: b"".to_vec(), // empty — legacy format
1758            })),
1759            mutation(mutation::Mutation::SetCell(mutation::SetCell {
1760                family_name: FAMILY_MANUAL.to_owned(),
1761                column_qualifier: b"t".to_vec(),
1762                timestamp_micros: -1,
1763                value: b"{}".to_vec(),
1764            })),
1765        ];
1766
1767        backend.mutate(path, mutations, "test-setup").await?;
1768
1769        Ok(())
1770    }
1771
1772    // --- Section 1: Object Operations ---
1773
1774    /// Verifies the full roundtrip: put → get_object (payload + metadata) → get_metadata (metadata).
1775    #[tokio::test]
1776    async fn test_roundtrip() -> Result<()> {
1777        let backend = create_test_backend().await?;
1778
1779        let id = make_id();
1780        let metadata = Metadata {
1781            content_type: "text/plain".into(),
1782            time_created: Some(Timestamp::now()),
1783            custom: BTreeMap::from_iter([("hello".into(), "world".into())]),
1784            ..Default::default()
1785        };
1786
1787        backend
1788            .put_object(
1789                &id,
1790                &metadata,
1791                stream::single("hello, world"),
1792                Timestamp::now(),
1793            )
1794            .await?;
1795
1796        let (obj_meta, _, stream) = backend
1797            .get_object(&id, Timestamp::now(), None)
1798            .await?
1799            .unwrap();
1800        let payload = stream::read_to_vec(stream).await?;
1801        assert_eq!(payload, b"hello, world");
1802        assert_eq!(obj_meta.content_type, metadata.content_type);
1803        assert_eq!(obj_meta.custom, metadata.custom);
1804
1805        let head_meta = backend.get_metadata(&id, Timestamp::now()).await?.unwrap();
1806        assert_eq!(head_meta.content_type, metadata.content_type);
1807        assert_eq!(head_meta.custom, metadata.custom);
1808
1809        Ok(())
1810    }
1811
1812    /// Verifies that a server-resolved `time_expires` is persisted verbatim, not recomputed.
1813    #[tokio::test]
1814    async fn test_time_expires_roundtrip() -> Result<()> {
1815        let backend = create_test_backend().await?;
1816
1817        let id = make_id();
1818        let ttl = Duration::from_hours(2 * 24);
1819        let expires = Timestamp::now() + ttl;
1820        let metadata = Metadata {
1821            expiration_policy: ExpirationPolicy::TimeToLive(ttl),
1822            time_expires: Some(expires),
1823            ..Default::default()
1824        };
1825        create_object(&backend, &id, &metadata, b"data", Timestamp::now()).await?;
1826
1827        let meta = backend.get_metadata(&id, Timestamp::now()).await?.unwrap();
1828        assert_eq!(meta.time_expires, Some(expires));
1829
1830        Ok(())
1831    }
1832
1833    /// Verifies that absent rows return None or succeed silently for all read/delete operations.
1834    #[tokio::test]
1835    async fn test_nonexistent() -> Result<()> {
1836        let backend = create_test_backend().await?;
1837
1838        let id = make_id();
1839        assert!(
1840            backend
1841                .get_object(&id, Timestamp::now(), None)
1842                .await?
1843                .is_none()
1844        );
1845        assert!(backend.get_metadata(&id, Timestamp::now()).await?.is_none());
1846        backend.delete_object(&id, Timestamp::now()).await?;
1847
1848        Ok(())
1849    }
1850
1851    #[tokio::test]
1852    async fn test_overwrite() -> Result<()> {
1853        let backend = create_test_backend().await?;
1854
1855        let id = make_id();
1856        let first_metadata = Metadata {
1857            custom: BTreeMap::from_iter([("invalid".into(), "invalid".into())]),
1858            ..Default::default()
1859        };
1860        create_object(&backend, &id, &first_metadata, b"hello", Timestamp::now()).await?;
1861
1862        let second_metadata = Metadata {
1863            custom: BTreeMap::from_iter([("hello".into(), "world".into())]),
1864            ..Default::default()
1865        };
1866        backend
1867            .put_object(
1868                &id,
1869                &second_metadata,
1870                stream::single("world"),
1871                Timestamp::now(),
1872            )
1873            .await?;
1874
1875        let (meta, _, stream) = backend
1876            .get_object(&id, Timestamp::now(), None)
1877            .await?
1878            .unwrap();
1879        let payload = stream::read_to_vec(stream).await?;
1880        assert_eq!(payload, b"world");
1881        assert_eq!(meta.custom, second_metadata.custom);
1882
1883        Ok(())
1884    }
1885
1886    #[tokio::test]
1887    async fn test_read_after_delete() -> Result<()> {
1888        let backend = create_test_backend().await?;
1889
1890        let id = make_id();
1891        let metadata = Metadata::default();
1892        create_object(&backend, &id, &metadata, b"hello", Timestamp::now()).await?;
1893        backend.delete_object(&id, Timestamp::now()).await?;
1894
1895        assert!(
1896            backend
1897                .get_object(&id, Timestamp::now(), None)
1898                .await?
1899                .is_none()
1900        );
1901
1902        Ok(())
1903    }
1904
1905    /// Backend reads are side-effect-free; explicit extension preserves payload.
1906    #[tokio::test]
1907    async fn test_set_expiry() -> Result<()> {
1908        for is_ttl in [false, true] {
1909            let backend = create_test_backend().await?;
1910            let tti = Duration::from_hours(2 * 24);
1911            let mut metadata = Metadata {
1912                expiration_policy: if is_ttl {
1913                    ExpirationPolicy::TimeToLive(tti)
1914                } else {
1915                    ExpirationPolicy::TimeToIdle(tti)
1916                },
1917                ..Default::default()
1918            };
1919
1920            // Backdate `now` so the written expiry (past_now + tti) is stale but not expired.
1921            let past_now = Timestamp::now() - tti + Duration::from_mins(1);
1922
1923            let id = make_id();
1924            metadata.time_created = Some(past_now);
1925            metadata.time_expires = Some(past_now + tti);
1926            let path = id.as_storage_path().to_string().into_bytes();
1927            let (mutations, _) = object_mutations(&path, metadata, b"hello, world".to_vec())?;
1928            // Simulate a legacy fractional deadline. Renewal must match the raw GC timestamp.
1929            let mutations = mutations.map(|mut mutation| {
1930                if let Some(mutation::Mutation::SetCell(cell)) = &mut mutation.mutation {
1931                    cell.timestamp_micros -= 500_000;
1932                }
1933                mutation
1934            });
1935            backend.mutate(path, mutations, "test-setup").await?;
1936
1937            let (observed, _, _) = backend
1938                .get_object(&id, Timestamp::now(), None)
1939                .await?
1940                .unwrap();
1941            let observed_expiry = observed.time_expires.unwrap();
1942            assert_eq!(
1943                backend
1944                    .get_metadata(&id, Timestamp::now())
1945                    .await?
1946                    .unwrap()
1947                    .time_expires,
1948                Some(observed_expiry),
1949                "backend reads must not renew TTI"
1950            );
1951
1952            let requested = past_now + tti + tti;
1953            for target in [
1954                ExpiryTarget::At(requested),
1955                ExpiryTarget::FromCreation(tti + tti),
1956            ] {
1957                assert_eq!(
1958                    backend
1959                        .set_expiry(&id, target.into(), Timestamp::now())
1960                        .await?,
1961                    SetExpiryResponse::Satisfied(requested)
1962                );
1963            }
1964            assert_eq!(
1965                backend
1966                    .get_metadata(&id, Timestamp::now())
1967                    .await?
1968                    .unwrap()
1969                    .time_expires,
1970                Some(requested)
1971            );
1972            let (updated, _, stream) = backend
1973                .get_object(&id, Timestamp::now(), None)
1974                .await?
1975                .unwrap();
1976            assert_eq!(
1977                updated.expiration_policy,
1978                if is_ttl {
1979                    ExpirationPolicy::TimeToLive(tti + tti)
1980                } else {
1981                    ExpirationPolicy::TimeToIdle(tti)
1982                }
1983            );
1984            let payload = stream::read_to_vec(stream).await?;
1985            assert_eq!(payload, b"hello, world");
1986        }
1987        Ok(())
1988    }
1989
1990    #[tokio::test]
1991    async fn test_expiry_outcomes() -> Result<()> {
1992        let backend = create_test_backend().await?;
1993        let access_time = Timestamp::now();
1994        let deadline = access_time + Duration::from_hours(1);
1995        for (expiry, expected) in [
1996            (None, SetExpiryResponse::Rejected),
1997            (
1998                Some(access_time - Duration::from_secs(1)),
1999                SetExpiryResponse::NotFound,
2000            ),
2001            (Some(deadline), SetExpiryResponse::Rejected),
2002        ] {
2003            let id = make_id();
2004            let metadata = Metadata {
2005                time_expires: expiry,
2006                ..Default::default()
2007            };
2008            create_object(&backend, &id, &metadata, b"payload", access_time).await?;
2009            assert_eq!(
2010                backend
2011                    .set_expiry(
2012                        &id,
2013                        ExpiryTarget::FromCreation(Duration::from_hours(2)).into(),
2014                        access_time
2015                    )
2016                    .await?,
2017                expected
2018            );
2019        }
2020        Ok(())
2021    }
2022
2023    #[tokio::test]
2024    async fn test_expiry_conflict() -> Result<()> {
2025        let backend = create_test_backend().await?;
2026        let missing = make_id();
2027        assert_eq!(
2028            backend
2029                .set_expiry(
2030                    &missing,
2031                    ExpiryTarget::At(Timestamp::now() + Duration::from_hours(2)).into(),
2032                    Timestamp::now()
2033                )
2034                .await?,
2035            SetExpiryResponse::NotFound
2036        );
2037
2038        let id = make_id();
2039        let observed_expiry = Timestamp::now() + Duration::from_hours(1);
2040        let original = Metadata {
2041            expiration_policy: ExpirationPolicy::TimeToLive(Duration::from_hours(1)),
2042            time_expires: Some(observed_expiry),
2043            ..Default::default()
2044        };
2045        create_object(&backend, &id, &original, b"original", Timestamp::now()).await?;
2046
2047        let path = id.as_storage_path().to_string().into_bytes();
2048        let mut extended = original.clone();
2049        extended.time_expires = Some(observed_expiry + Duration::from_hours(1));
2050        let (extension, _) = object_mutations(&path, extended, b"original".to_vec())?;
2051        let predicate =
2052            inline_expiry_predicate(observed_expiry.as_micros() as i64, Timestamp::now())?;
2053
2054        let mut replacement = original.clone();
2055        replacement.time_expires = Some(observed_expiry + Duration::from_mins(1));
2056        create_object(
2057            &backend,
2058            &id,
2059            &replacement,
2060            b"replacement",
2061            Timestamp::now(),
2062        )
2063        .await?;
2064        assert!(
2065            !backend
2066                .check_and_mutate(path, predicate, extension, "test-expiry-conflict")
2067                .await?
2068        );
2069        let (_, _, payload) = backend
2070            .get_object(&id, Timestamp::now(), None)
2071            .await?
2072            .unwrap();
2073        assert_eq!(stream::read_to_vec(payload).await?, b"replacement");
2074        Ok(())
2075    }
2076
2077    #[tokio::test]
2078    async fn test_redirect_expiry() -> Result<()> {
2079        let backend = create_test_backend().await?;
2080        let id = make_id();
2081        let target = ObjectId::random(id.context().clone());
2082        let wrong_target = ObjectId::random(id.context().clone());
2083        let old_expiry = Timestamp::now() + Duration::from_hours(1);
2084        let path = id.as_storage_path().to_string().into_bytes();
2085        let mutations = tombstone_mutations(&Tombstone {
2086            target: target.clone(),
2087            time_expires: Some(old_expiry),
2088        })
2089        .map(|mut mutation| {
2090            if let Some(mutation::Mutation::SetCell(cell)) = &mut mutation.mutation {
2091                cell.timestamp_micros -= 500_000;
2092            }
2093            mutation
2094        });
2095        backend.mutate(path, mutations, "test-setup").await?;
2096
2097        let later = old_expiry + Duration::from_hours(2);
2098        assert_eq!(
2099            backend
2100                .compare_and_update(
2101                    &id,
2102                    Some(&wrong_target),
2103                    TieredUpdate::SetExpiry(ExpiryTarget::At(later).into()),
2104                    Timestamp::now(),
2105                )
2106                .await?,
2107            SetExpiryResponse::Rejected
2108        );
2109        assert_eq!(
2110            backend
2111                .compare_and_update(
2112                    &id,
2113                    Some(&target),
2114                    TieredUpdate::SetExpiry(ExpiryTarget::At(later).into()),
2115                    Timestamp::now()
2116                )
2117                .await?,
2118            SetExpiryResponse::Satisfied(later)
2119        );
2120        let requested = old_expiry + Duration::from_mins(30);
2121        assert_eq!(
2122            backend
2123                .compare_and_update(
2124                    &id,
2125                    Some(&target),
2126                    TieredUpdate::SetExpiry(ExpiryTarget::At(requested).into()),
2127                    Timestamp::now(),
2128                )
2129                .await?,
2130            SetExpiryResponse::Satisfied(requested)
2131        );
2132        let TieredMetadata::Tombstone(tombstone) =
2133            backend.get_tiered_metadata(&id, Timestamp::now()).await?
2134        else {
2135            panic!("expected tombstone");
2136        };
2137        assert_eq!(tombstone.time_expires, Some(later));
2138        Ok(())
2139    }
2140
2141    // --- Section 2: Expiration ---
2142
2143    #[tokio::test]
2144    async fn test_ttl_immediate() -> Result<()> {
2145        // NB: We create a TTL that immediately expires in this test. This might be optimized away
2146        // in a future implementation, so we will have to update this test accordingly.
2147
2148        let backend = create_test_backend().await?;
2149
2150        let id = make_id();
2151        let metadata = Metadata {
2152            expiration_policy: ExpirationPolicy::TimeToLive(Duration::from_secs(0)),
2153            time_expires: Some(Timestamp::now() - Duration::from_secs(1)),
2154            ..Default::default()
2155        };
2156        create_object(&backend, &id, &metadata, b"hello, world", Timestamp::now()).await?;
2157
2158        assert!(
2159            backend
2160                .get_object(&id, Timestamp::now(), None)
2161                .await?
2162                .is_none()
2163        );
2164
2165        Ok(())
2166    }
2167
2168    #[tokio::test]
2169    async fn test_tti_immediate() -> Result<()> {
2170        // NB: We create a TTI that immediately expires in this test. This might be optimized away
2171        // in a future implementation, so we will have to update this test accordingly.
2172
2173        let backend = create_test_backend().await?;
2174
2175        let id = make_id();
2176        let metadata = Metadata {
2177            expiration_policy: ExpirationPolicy::TimeToIdle(Duration::from_secs(0)),
2178            time_expires: Some(Timestamp::now() - Duration::from_secs(1)),
2179            ..Default::default()
2180        };
2181        create_object(&backend, &id, &metadata, b"hello, world", Timestamp::now()).await?;
2182
2183        assert!(
2184            backend
2185                .get_object(&id, Timestamp::now(), None)
2186                .await?
2187                .is_none()
2188        );
2189
2190        Ok(())
2191    }
2192
2193    // --- Section 3: Tiered Operations ---
2194
2195    /// Covers all three row states for `get_tiered_object` and `get_tiered_metadata`.
2196    ///
2197    /// - **empty**: both return NotFound.
2198    /// - **object**: put_object, both return the Object variant with correct payload/metadata.
2199    /// - **tombstone**: CAS-write with a distinct `lt_id`, both return the Tombstone variant
2200    ///   with `target == lt_id`.
2201    #[tokio::test]
2202    async fn test_tiered_get() -> Result<()> {
2203        let backend = create_test_backend().await?;
2204
2205        // empty
2206        let id = make_id();
2207        assert!(matches!(
2208            backend
2209                .get_tiered_object(&id, Timestamp::now(), None)
2210                .await?,
2211            TieredGet::NotFound
2212        ));
2213        assert!(matches!(
2214            backend.get_tiered_metadata(&id, Timestamp::now()).await?,
2215            TieredMetadata::NotFound
2216        ));
2217
2218        // object
2219        let id = make_id();
2220        let put_meta = Metadata {
2221            content_type: "text/plain".into(),
2222            custom: BTreeMap::from_iter([("k".into(), "v".into())]),
2223            ..Default::default()
2224        };
2225        create_object(&backend, &id, &put_meta, b"payload", Timestamp::now()).await?;
2226
2227        let TieredGet::Object(obj_meta, _, obj_stream) = backend
2228            .get_tiered_object(&id, Timestamp::now(), None)
2229            .await?
2230        else {
2231            panic!("expected TieredGet::Object");
2232        };
2233        let obj_payload = stream::read_to_vec(obj_stream).await?;
2234        assert_eq!(obj_payload, b"payload");
2235        assert_eq!(obj_meta.content_type, put_meta.content_type);
2236        assert_eq!(obj_meta.custom, put_meta.custom);
2237
2238        let TieredMetadata::Object(head_meta) =
2239            backend.get_tiered_metadata(&id, Timestamp::now()).await?
2240        else {
2241            panic!("expected TieredMetadata::Object");
2242        };
2243        assert_eq!(head_meta.content_type, put_meta.content_type);
2244        assert_eq!(head_meta.custom, put_meta.custom);
2245
2246        // tombstone
2247        let hv_id = make_id();
2248        let lt_id = ObjectId::random(hv_id.context().clone());
2249        let tombstone = Tombstone {
2250            target: lt_id.clone(),
2251            time_expires: None,
2252        };
2253        create_tombstone(&backend, &hv_id, &tombstone).await?;
2254
2255        match backend
2256            .get_tiered_object(&hv_id, Timestamp::now(), None)
2257            .await?
2258        {
2259            TieredGet::Tombstone(get_t) => assert_eq!(get_t.target, lt_id),
2260            other => panic!("expected TieredGet::Tombstone, got {other:?}"),
2261        }
2262        match backend
2263            .get_tiered_metadata(&hv_id, Timestamp::now())
2264            .await?
2265        {
2266            TieredMetadata::Tombstone(meta_t) => assert_eq!(meta_t.target, lt_id,),
2267            other => panic!("expected TieredMetadata::Tombstone, got {other:?}"),
2268        }
2269
2270        Ok(())
2271    }
2272
2273    /// Covers all three row states for `put_non_tombstone`.
2274    ///
2275    /// - **empty**: returns None, object is readable.
2276    /// - **object**: overwrites with new payload, returns None.
2277    /// - **tombstone**: returns Some(Tombstone) with the correct target; tombstone still intact.
2278    #[tokio::test]
2279    async fn test_put_non_tombstone() -> Result<()> {
2280        let backend = create_test_backend().await?;
2281
2282        // empty: put_non_tombstone on absent row succeeds and makes object readable.
2283        let id = make_id();
2284        let metadata = Metadata::default();
2285        let result = backend
2286            .put_non_tombstone(
2287                &id,
2288                &metadata,
2289                Bytes::from_static(b"first"),
2290                Timestamp::now(),
2291            )
2292            .await?;
2293        assert_eq!(result, None, "expected None on empty row");
2294        let (_, _, stream) = backend
2295            .get_object(&id, Timestamp::now(), None)
2296            .await?
2297            .unwrap();
2298        assert_eq!(&stream::read_to_vec(stream).await?, b"first");
2299
2300        // object: put_non_tombstone on existing object replaces payload, returns None.
2301        let id = make_id();
2302        create_object(&backend, &id, &metadata, b"old", Timestamp::now()).await?;
2303        let result = backend
2304            .put_non_tombstone(&id, &metadata, Bytes::from_static(b"new"), Timestamp::now())
2305            .await?;
2306        assert_eq!(result, None, "expected None when overwriting object");
2307        let (_, _, stream) = backend
2308            .get_object(&id, Timestamp::now(), None)
2309            .await?
2310            .unwrap();
2311        assert_eq!(&stream::read_to_vec(stream).await?, b"new");
2312
2313        // tombstone: put_non_tombstone returns Some(Tombstone) and leaves tombstone intact.
2314        let hv_id = make_id();
2315        let lt_id = ObjectId::random(hv_id.context().clone());
2316        let tombstone = Tombstone {
2317            target: lt_id.clone(),
2318            time_expires: None,
2319        };
2320        create_tombstone(&backend, &hv_id, &tombstone).await?;
2321        let result = backend
2322            .put_non_tombstone(&hv_id, &metadata, Bytes::new(), Timestamp::now())
2323            .await?;
2324        let returned = result.expect("expected Some(Tombstone) when row is a tombstone");
2325        assert_eq!(returned.target, lt_id);
2326        assert!(
2327            matches!(
2328                backend
2329                    .get_tiered_metadata(&hv_id, Timestamp::now())
2330                    .await?,
2331                TieredMetadata::Tombstone(_)
2332            ),
2333            "tombstone must still exist after put_non_tombstone"
2334        );
2335
2336        Ok(())
2337    }
2338
2339    /// Covers all three row states for `delete_non_tombstone`.
2340    ///
2341    /// - **empty**: returns None.
2342    /// - **object**: returns None, row gone.
2343    /// - **tombstone**: returns Some(Tombstone) with correct target; tombstone still intact.
2344    ///
2345    /// Verifies that the `r` column is correctly detected by both the `ReadRows` column
2346    /// filter and the `CheckAndMutate` `non_tombstone_predicate`.
2347    #[tokio::test]
2348    async fn test_delete_non_tombstone() -> Result<()> {
2349        let backend = create_test_backend().await?;
2350
2351        // empty
2352        let id = make_id();
2353        assert_eq!(
2354            backend.delete_non_tombstone(&id, Timestamp::now()).await?,
2355            None
2356        );
2357
2358        // object
2359        let id = make_id();
2360        let metadata = Metadata::default();
2361        create_object(&backend, &id, &metadata, b"hello, world", Timestamp::now()).await?;
2362        assert_eq!(
2363            backend.delete_non_tombstone(&id, Timestamp::now()).await?,
2364            None
2365        );
2366        assert!(
2367            backend
2368                .get_object(&id, Timestamp::now(), None)
2369                .await?
2370                .is_none()
2371        );
2372
2373        // tombstone
2374        let id = make_id();
2375        let tombstone = Tombstone {
2376            target: id.clone(),
2377            time_expires: None,
2378        };
2379        create_tombstone(&backend, &id, &tombstone).await?;
2380        let tombstone = backend
2381            .delete_non_tombstone(&id, Timestamp::now())
2382            .await?
2383            .expect("expected Some(tombstone)");
2384        assert_eq!(tombstone.target, id, "tombstone target must be returned");
2385        assert!(
2386            matches!(
2387                backend.get_tiered_metadata(&id, Timestamp::now()).await?,
2388                TieredMetadata::Tombstone(_)
2389            ),
2390            "tombstone must still exist after delete_non_tombstone"
2391        );
2392
2393        Ok(())
2394    }
2395
2396    // --- Section 4: Compare-and-Write ---
2397
2398    /// Creating a tombstone on an empty row succeeds; a retry of the same CAS also succeeds.
2399    ///
2400    /// After creation, both tiered and legacy APIs reflect the tombstone.
2401    #[tokio::test]
2402    async fn test_cas_create_tombstone() -> Result<()> {
2403        let backend = create_test_backend().await?;
2404
2405        let hv_id = make_id();
2406        let lt_id = ObjectId::random(hv_id.context().clone());
2407        let time_expires = Some(Timestamp::now() + Duration::from_hours(1));
2408        let tombstone = Tombstone {
2409            target: lt_id.clone(),
2410            time_expires,
2411        };
2412
2413        // First create succeeds.
2414        let committed = backend
2415            .compare_and_write(
2416                &hv_id,
2417                None,
2418                TieredWrite::Tombstone(tombstone.clone()),
2419                Timestamp::now(),
2420            )
2421            .await?;
2422        assert!(committed, "expected CAS success on empty row");
2423
2424        // Tiered reads must see the tombstone with the correct target and deadline.
2425        let TieredMetadata::Tombstone(t) = backend
2426            .get_tiered_metadata(&hv_id, Timestamp::now())
2427            .await?
2428        else {
2429            panic!("expected TieredMetadata::Tombstone");
2430        };
2431        assert_eq!(t.target, lt_id, "target must round-trip via r column");
2432        assert_eq!(t.time_expires, time_expires);
2433        match backend
2434            .get_tiered_object(&hv_id, Timestamp::now(), None)
2435            .await?
2436        {
2437            TieredGet::Tombstone(t) => assert_eq!(t.target, lt_id, "round-trip via r column"),
2438            other => panic!("expected TieredGet::Tombstone, got {other:?}"),
2439        }
2440
2441        // Legacy reads must error rather than leak tombstone data.
2442        assert!(
2443            backend
2444                .get_object(&hv_id, Timestamp::now(), None)
2445                .await
2446                .is_err_and(|error| error.kind() == ErrorKind::UnexpectedTombstone)
2447        );
2448        assert!(
2449            backend
2450                .get_metadata(&hv_id, Timestamp::now())
2451                .await
2452                .is_err_and(|error| error.kind() == ErrorKind::UnexpectedTombstone)
2453        );
2454
2455        // Idempotent retry: retry with the same target succeeds
2456        let second = backend
2457            .compare_and_write(
2458                &hv_id,
2459                None,
2460                TieredWrite::Tombstone(tombstone),
2461                Timestamp::now(),
2462            )
2463            .await?;
2464        assert!(second, "idempotent retry");
2465
2466        Ok(())
2467    }
2468
2469    /// Swapping a tombstone target: wrong expected → false, correct expected → true.
2470    #[tokio::test]
2471    async fn test_cas_swap_tombstone() -> Result<()> {
2472        let backend = create_test_backend().await?;
2473
2474        let hv_id = make_id();
2475        let old_lt_id = ObjectId::random(hv_id.context().clone());
2476        let wrong_lt_id = ObjectId::random(hv_id.context().clone());
2477        let new_lt_id = ObjectId::random(hv_id.context().clone());
2478
2479        let tombstone = Tombstone {
2480            target: old_lt_id.clone(),
2481            time_expires: None,
2482        };
2483        create_tombstone(&backend, &hv_id, &tombstone).await?;
2484
2485        // Wrong target: CAS fails, tombstone unchanged.
2486        let write = TieredWrite::Tombstone(Tombstone {
2487            target: new_lt_id.clone(),
2488            time_expires: None,
2489        });
2490        let swapped = backend
2491            .compare_and_write(&hv_id, Some(&wrong_lt_id), write.clone(), Timestamp::now())
2492            .await?;
2493        assert!(!swapped, "expected CAS failure due to wrong target");
2494        match backend
2495            .get_tiered_metadata(&hv_id, Timestamp::now())
2496            .await?
2497        {
2498            TieredMetadata::Tombstone(t) => assert_eq!(t.target, old_lt_id),
2499            other => panic!("expected tombstone, got {other:?}"),
2500        }
2501
2502        // Correct target: CAS succeeds, target updated.
2503        let swapped = backend
2504            .compare_and_write(&hv_id, Some(&old_lt_id), write.clone(), Timestamp::now())
2505            .await?;
2506        assert!(swapped, "expected CAS success with correct target");
2507        match backend
2508            .get_tiered_metadata(&hv_id, Timestamp::now())
2509            .await?
2510        {
2511            TieredMetadata::Tombstone(t) => assert_eq!(t.target, new_lt_id),
2512            other => panic!("expected tombstone, got {other:?}"),
2513        }
2514
2515        // Idempotent retry: same A→B swap returns true.
2516        let retry = backend
2517            .compare_and_write(&hv_id, Some(&old_lt_id), write, Timestamp::now())
2518            .await?;
2519        assert!(retry, "idempotent retry");
2520
2521        Ok(())
2522    }
2523
2524    /// Swapping a tombstone for inline object data: wrong expected → false, correct → true.
2525    #[tokio::test]
2526    async fn test_cas_swap_inline() -> Result<()> {
2527        let backend = create_test_backend().await?;
2528
2529        let id = make_id();
2530        let lt_id = ObjectId::random(id.context().clone());
2531        let wrong_id = ObjectId::random(id.context().clone());
2532
2533        let tombstone = Tombstone {
2534            target: lt_id.clone(),
2535            time_expires: None,
2536        };
2537        create_tombstone(&backend, &id, &tombstone).await?;
2538
2539        // Wrong target: CAS fails, tombstone intact.
2540        let write = TieredWrite::Object(Metadata::default(), Bytes::new());
2541        let swapped = backend
2542            .compare_and_write(&id, Some(&wrong_id), write, Timestamp::now())
2543            .await?;
2544        assert!(!swapped, "expected CAS failure with wrong target");
2545        assert!(matches!(
2546            backend.get_tiered_metadata(&id, Timestamp::now()).await?,
2547            TieredMetadata::Tombstone(_)
2548        ));
2549
2550        // Correct target: CAS succeeds, row becomes an inline object.
2551        let payload = Bytes::from_static(b"hello inline");
2552        let write = TieredWrite::Object(Metadata::default(), payload.clone());
2553        let swapped = backend
2554            .compare_and_write(&id, Some(&lt_id), write.clone(), Timestamp::now())
2555            .await?;
2556        assert!(swapped, "expected CAS success with correct target");
2557        let TieredGet::Object(_, _, stream) = backend
2558            .get_tiered_object(&id, Timestamp::now(), None)
2559            .await?
2560        else {
2561            panic!("expected inline object after swap");
2562        };
2563        assert_eq!(&stream::read_to_vec(stream).await?, payload.as_ref());
2564
2565        // Idempotent retry: row is already inline (no tombstone), same CAS returns true.
2566        let retry = backend
2567            .compare_and_write(&id, Some(&lt_id), write, Timestamp::now())
2568            .await?;
2569        assert!(retry, "idempotent retry");
2570
2571        Ok(())
2572    }
2573
2574    /// CAS-write an object onto an empty row (expected=None, write=Object) succeeds.
2575    #[tokio::test]
2576    async fn test_cas_create_object_on_empty_row() -> Result<()> {
2577        let backend = create_test_backend().await?;
2578
2579        let id = make_id();
2580        let payload = Bytes::from_static(b"cas object");
2581        let write = TieredWrite::Object(Metadata::default(), payload.clone());
2582        let committed = backend
2583            .compare_and_write(&id, None, write, Timestamp::now())
2584            .await?;
2585        assert!(committed, "expected CAS success on empty row");
2586
2587        let TieredGet::Object(_, _, stream) = backend
2588            .get_tiered_object(&id, Timestamp::now(), None)
2589            .await?
2590        else {
2591            panic!("expected Object after CAS-create");
2592        };
2593        assert_eq!(&stream::read_to_vec(stream).await?, payload.as_ref());
2594
2595        Ok(())
2596    }
2597
2598    /// CAS-delete: wrong expected → false; correct expected → true, row gone.
2599    #[tokio::test]
2600    async fn test_cas_delete() -> Result<()> {
2601        let backend = create_test_backend().await?;
2602
2603        let id = make_id();
2604        let lt_id = ObjectId::random(id.context().clone());
2605        let wrong_id = ObjectId::random(id.context().clone());
2606
2607        let tombstone = Tombstone {
2608            target: lt_id.clone(),
2609            time_expires: None,
2610        };
2611        create_tombstone(&backend, &id, &tombstone).await?;
2612
2613        // Wrong target: fails, row preserved.
2614        let deleted = backend
2615            .compare_and_write(&id, Some(&wrong_id), TieredWrite::Delete, Timestamp::now())
2616            .await?;
2617        assert!(!deleted, "expected CAS failure with wrong target");
2618        assert!(matches!(
2619            backend.get_tiered_metadata(&id, Timestamp::now()).await?,
2620            TieredMetadata::Tombstone(_)
2621        ));
2622
2623        // Correct target: succeeds, row gone.
2624        let deleted = backend
2625            .compare_and_write(&id, Some(&lt_id), TieredWrite::Delete, Timestamp::now())
2626            .await?;
2627        assert!(deleted, "expected CAS delete success");
2628        assert!(matches!(
2629            backend.get_tiered_metadata(&id, Timestamp::now()).await?,
2630            TieredMetadata::NotFound
2631        ));
2632
2633        // Idempotent retry: row is already absent (no tombstone), same delete returns true.
2634        let retry = backend
2635            .compare_and_write(&id, Some(&lt_id), TieredWrite::Delete, Timestamp::now())
2636            .await?;
2637        assert!(retry, "idempotent retry");
2638
2639        // Inline object replaced tombstone: Safe to delete since it is an idempotent operation.
2640        let id2 = make_id();
2641        let fake_lt_id = ObjectId::random(id2.context().clone());
2642        let metadata = Metadata::default();
2643        create_object(&backend, &id2, &metadata, b"data", Timestamp::now()).await?;
2644        let deleted = backend
2645            .compare_and_write(
2646                &id2,
2647                Some(&fake_lt_id),
2648                TieredWrite::Delete,
2649                Timestamp::now(),
2650            )
2651            .await?;
2652        assert!(deleted, "expected idempotent deletion");
2653
2654        Ok(())
2655    }
2656
2657    // --- Section 5: Legacy Tombstone Compatibility ---
2658
2659    /// Legacy Manual and TTL tombstones are correctly read via the tiered APIs.
2660    ///
2661    /// Uses `Manual` expiration so `timestamp_micros = -1` (server-assigned ≈ write time)
2662    /// does not trigger immediate expiry.
2663    #[tokio::test]
2664    async fn test_legacy_tombstone_reads() -> Result<()> {
2665        let backend = create_test_backend().await?;
2666
2667        // Manual policy: get_tiered_metadata returns a non-expiring tombstone.
2668        let id = make_id();
2669        write_legacy_tombstone(&backend, &id, ExpirationPolicy::Manual, None).await?;
2670
2671        let TieredMetadata::Tombstone(t) =
2672            backend.get_tiered_metadata(&id, Timestamp::now()).await?
2673        else {
2674            panic!("expected tombstone");
2675        };
2676        assert_eq!(t.time_expires, None);
2677        assert!(matches!(
2678            backend
2679                .get_tiered_object(&id, Timestamp::now(), None)
2680                .await?,
2681            TieredGet::Tombstone(_)
2682        ));
2683
2684        // TTL policy: get_tiered_metadata reconstructs the concrete deadline.
2685        //
2686        // A future cell timestamp (now + TTL) is required so `expires_before` does not
2687        // immediately filter the row.
2688        let id = make_id();
2689        let ttl = Duration::from_hours(2 * 24);
2690        write_legacy_tombstone(&backend, &id, ExpirationPolicy::TimeToLive(ttl), None).await?;
2691
2692        let TieredMetadata::Tombstone(t) =
2693            backend.get_tiered_metadata(&id, Timestamp::now()).await?
2694        else {
2695            panic!("expected TieredMetadata::Tombstone");
2696        };
2697        assert!(t.time_expires.is_some());
2698
2699        Ok(())
2700    }
2701
2702    /// A conditional extension upgrades a legacy TTI tombstone to `r`.
2703    #[tokio::test]
2704    async fn test_legacy_tombstone_tti_upgrade() -> Result<()> {
2705        let backend = create_test_backend().await?;
2706        let id = make_id();
2707        let path = id.as_storage_path().to_string().into_bytes();
2708
2709        let tti = Duration::from_hours(2 * 24);
2710
2711        // Place time_expires near expiry but still in the future.
2712        let old_deadline = Timestamp::now() + Duration::from_mins(1);
2713        write_legacy_tombstone(
2714            &backend,
2715            &id,
2716            ExpirationPolicy::TimeToIdle(tti),
2717            Some(old_deadline),
2718        )
2719        .await?;
2720
2721        // A read observes the legacy row but leaves it unchanged.
2722        let TieredMetadata::Tombstone(_) =
2723            backend.get_tiered_metadata(&id, Timestamp::now()).await?
2724        else {
2725            panic!("expected tombstone");
2726        };
2727        assert_eq!(
2728            backend
2729                .read_row(&path, "test-verify", Timestamp::now(), None)
2730                .await?
2731                .and_then(|row| row.time_expires()),
2732            Some(old_deadline)
2733        );
2734
2735        let requested = Timestamp::now() + tti;
2736        assert_eq!(
2737            backend
2738                .compare_and_update(
2739                    &id,
2740                    Some(&id),
2741                    TieredUpdate::SetExpiry(ExpiryTarget::At(requested).into()),
2742                    Timestamp::now()
2743                )
2744                .await?,
2745            SetExpiryResponse::Satisfied(requested)
2746        );
2747
2748        // After extension, the row uses the requested timestamp.
2749        let new_deadline = match backend
2750            .read_row(&path, "test-verify", Timestamp::now(), None)
2751            .await?
2752        {
2753            Some(RowData::Tombstone { time_expires, .. }) => time_expires.unwrap(),
2754            _ => panic!("expected tombstone row after extension"),
2755        };
2756
2757        assert!(
2758            new_deadline > old_deadline,
2759            "explicit extension should extend tombstone expiry: {old_deadline:?} -> {new_deadline:?}"
2760        );
2761
2762        Ok(())
2763    }
2764
2765    /// Legacy tombstones are handled correctly by all conditional write operations.
2766    ///
2767    /// Covers: `put_non_tombstone`, `delete_non_tombstone`, CAS-delete for both the
2768    /// legacy-metadata format and the empty-redirect format.
2769    #[tokio::test]
2770    async fn test_legacy_tombstone_conditional_ops() -> Result<()> {
2771        let backend = create_test_backend().await?;
2772
2773        // put_non_tombstone returns Some(target == id) for a legacy tombstone.
2774        let id = make_id();
2775        write_legacy_tombstone(&backend, &id, ExpirationPolicy::Manual, None).await?;
2776        let t_opt = backend
2777            .put_non_tombstone(&id, &Metadata::default(), Bytes::new(), Timestamp::now())
2778            .await?;
2779        assert_eq!(t_opt.map(|t| t.target).as_ref(), Some(&id));
2780
2781        // delete_non_tombstone returns Some(target == id) for a legacy tombstone.
2782        let id = make_id();
2783        write_legacy_tombstone(&backend, &id, ExpirationPolicy::Manual, None).await?;
2784        let t_opt = backend.delete_non_tombstone(&id, Timestamp::now()).await?;
2785        assert_eq!(t_opt.map(|t| t.target).as_ref(), Some(&id));
2786
2787        // CAS-delete succeeds on a legacy-metadata tombstone (target resolves to hv_id).
2788        let id = make_id();
2789        write_legacy_tombstone(&backend, &id, ExpirationPolicy::Manual, None).await?;
2790        let deleted = backend
2791            .compare_and_write(&id, Some(&id), TieredWrite::Delete, Timestamp::now())
2792            .await?;
2793        assert!(
2794            deleted,
2795            "CAS-delete must succeed on legacy-metadata tombstone"
2796        );
2797        assert!(matches!(
2798            backend.get_tiered_metadata(&id, Timestamp::now()).await?,
2799            TieredMetadata::NotFound
2800        ));
2801
2802        // CAS-delete succeeds on an empty-redirect tombstone (target resolves to hv_id).
2803        let id = make_id();
2804        write_empty_redirect_tombstone(&backend, &id).await?;
2805        let deleted = backend
2806            .compare_and_write(&id, Some(&id), TieredWrite::Delete, Timestamp::now())
2807            .await?;
2808        assert!(
2809            deleted,
2810            "CAS-delete must succeed on empty-redirect tombstone"
2811        );
2812        assert!(matches!(
2813            backend.get_tiered_metadata(&id, Timestamp::now()).await?,
2814            TieredMetadata::NotFound
2815        ));
2816
2817        Ok(())
2818    }
2819
2820    /// An empty `r` value falls back to the HV id when resolving the tombstone target.
2821    #[tokio::test]
2822    async fn test_empty_redirect_falls_back_to_hv_id() -> Result<()> {
2823        let backend = create_test_backend().await?;
2824        let id = make_id();
2825
2826        write_empty_redirect_tombstone(&backend, &id).await?;
2827        match backend.get_tiered_metadata(&id, Timestamp::now()).await? {
2828            TieredMetadata::Tombstone(t) => assert_eq!(t.target, id, "must fall back to hv_id"),
2829            other => panic!("expected tombstone, got {other:?}"),
2830        }
2831
2832        Ok(())
2833    }
2834
2835    // --- Section 6: Expired Tombstone Handling ---
2836
2837    /// CAS with `current=None` must succeed when the row holds an expired
2838    /// tombstone. The physical row still exists but is logically gone.
2839    #[tokio::test]
2840    async fn test_cas_create_tombstone_over_expired() -> Result<()> {
2841        let backend = create_test_backend().await?;
2842
2843        let id = make_id();
2844        let old_lt_id = ObjectId::random(id.context().clone());
2845        let old_tombstone = Tombstone {
2846            target: old_lt_id,
2847            time_expires: Some(Timestamp::now() - Duration::from_secs(1)),
2848        };
2849        create_tombstone(&backend, &id, &old_tombstone).await?;
2850
2851        let new_lt_id = ObjectId::random(id.context().clone());
2852        let new_tombstone = Tombstone {
2853            target: new_lt_id.clone(),
2854            time_expires: Some(Timestamp::now() + Duration::from_hours(1)),
2855        };
2856        let committed = backend
2857            .compare_and_write(
2858                &id,
2859                None,
2860                TieredWrite::Tombstone(new_tombstone),
2861                Timestamp::now(),
2862            )
2863            .await?;
2864        assert!(
2865            committed,
2866            "CAS with current=None must succeed over an expired tombstone"
2867        );
2868
2869        let TieredMetadata::Tombstone(t) =
2870            backend.get_tiered_metadata(&id, Timestamp::now()).await?
2871        else {
2872            panic!("expected new tombstone to be readable");
2873        };
2874        assert_eq!(t.target, new_lt_id);
2875
2876        Ok(())
2877    }
2878
2879    /// `put_non_tombstone` must succeed when the row holds only an expired
2880    /// tombstone — the expired row is logically absent.
2881    #[tokio::test]
2882    async fn test_put_non_tombstone_over_expired() -> Result<()> {
2883        let backend = create_test_backend().await?;
2884
2885        let id = make_id();
2886        let lt_id = ObjectId::random(id.context().clone());
2887        let tombstone = Tombstone {
2888            target: lt_id,
2889            time_expires: Some(Timestamp::now() - Duration::from_secs(1)),
2890        };
2891        create_tombstone(&backend, &id, &tombstone).await?;
2892
2893        let result = backend
2894            .put_non_tombstone(
2895                &id,
2896                &Metadata::default(),
2897                Bytes::from_static(b"data"),
2898                Timestamp::now(),
2899            )
2900            .await?;
2901        assert_eq!(
2902            result, None,
2903            "put_non_tombstone must succeed (return None) over an expired tombstone"
2904        );
2905
2906        let (_, _, stream) = backend
2907            .get_object(&id, Timestamp::now(), None)
2908            .await?
2909            .unwrap();
2910        assert_eq!(&stream::read_to_vec(stream).await?, b"data");
2911
2912        Ok(())
2913    }
2914
2915    // --- Range Request Tests ---
2916
2917    async fn put_range_test_object(backend: &BigTableBackend) -> Result<ObjectId> {
2918        let id = make_id();
2919        let metadata = Metadata {
2920            content_type: "text/plain".into(),
2921            ..Default::default()
2922        };
2923        let payload = b"Hello, range requests!";
2924        backend
2925            .put_object(
2926                &id,
2927                &metadata,
2928                stream::single(payload.as_slice()),
2929                Timestamp::now(),
2930            )
2931            .await?;
2932        Ok(id)
2933    }
2934
2935    #[tokio::test]
2936    async fn get_object_range_bounded() -> Result<()> {
2937        let backend = create_test_backend().await?;
2938        let id = put_range_test_object(&backend).await?;
2939
2940        let (_, content_range, stream) = backend
2941            .get_object(&id, Timestamp::now(), Some(ByteRange::Bounded(7, 11)))
2942            .await?
2943            .unwrap();
2944        let data = stream::read_to_vec(stream).await?;
2945        assert_eq!(&data, b"range");
2946
2947        let content_range = content_range.unwrap();
2948        assert_eq!(content_range.start, 7);
2949        assert_eq!(content_range.end, 11);
2950        assert_eq!(content_range.total, 22);
2951
2952        Ok(())
2953    }
2954
2955    #[tokio::test]
2956    async fn get_object_range_from() -> Result<()> {
2957        let backend = create_test_backend().await?;
2958        let id = put_range_test_object(&backend).await?;
2959
2960        let (_, content_range, stream) = backend
2961            .get_object(&id, Timestamp::now(), Some(ByteRange::From(7)))
2962            .await?
2963            .unwrap();
2964        let data = stream::read_to_vec(stream).await?;
2965        assert_eq!(&data, b"range requests!");
2966
2967        let content_range = content_range.unwrap();
2968        assert_eq!(content_range.start, 7);
2969        assert_eq!(content_range.end, 21);
2970        assert_eq!(content_range.total, 22);
2971
2972        Ok(())
2973    }
2974
2975    #[tokio::test]
2976    async fn get_object_range_last() -> Result<()> {
2977        let backend = create_test_backend().await?;
2978        let id = put_range_test_object(&backend).await?;
2979
2980        let (_, content_range, stream) = backend
2981            .get_object(&id, Timestamp::now(), Some(ByteRange::Last(9)))
2982            .await?
2983            .unwrap();
2984        let data = stream::read_to_vec(stream).await?;
2985        assert_eq!(&data, b"requests!");
2986
2987        let content_range = content_range.unwrap();
2988        assert_eq!(content_range.start, 13);
2989        assert_eq!(content_range.end, 21);
2990        assert_eq!(content_range.total, 22);
2991
2992        Ok(())
2993    }
2994
2995    #[tokio::test]
2996    async fn get_object_range_unsatisfiable() -> Result<()> {
2997        let backend = create_test_backend().await?;
2998        let id = put_range_test_object(&backend).await?;
2999
3000        match backend
3001            .get_object(&id, Timestamp::now(), Some(ByteRange::From(100)))
3002            .await
3003        {
3004            Err(error) if matches!(error.kind(), ErrorKind::RangeNotSatisfiable { total: 22 }) => {}
3005            Ok(_) => panic!("expected RangeNotSatisfiable, got Ok"),
3006            Err(e) => panic!("expected RangeNotSatisfiable, got {e:?}"),
3007        }
3008
3009        Ok(())
3010    }
3011
3012    #[tokio::test]
3013    async fn get_object_no_range_returns_full_payload() -> Result<()> {
3014        let backend = create_test_backend().await?;
3015        let id = put_range_test_object(&backend).await?;
3016
3017        let (_, content_range, stream) = backend
3018            .get_object(&id, Timestamp::now(), None)
3019            .await?
3020            .unwrap();
3021        let data = stream::read_to_vec(stream).await?;
3022        assert_eq!(&data, b"Hello, range requests!");
3023        assert!(content_range.is_none());
3024
3025        Ok(())
3026    }
3027
3028    #[test]
3029    fn row_size_counts_the_key_and_every_cell() {
3030        let path = b"attachments/org.1/objects/abc";
3031        let (mutations, size) =
3032            object_mutations(path, Metadata::default(), b"0123456789".to_vec()).unwrap();
3033
3034        // The key, the 10-byte payload, and the serialized metadata. `object_mutations`
3035        // stamps the size into the metadata before serializing it, so the expected length
3036        // has to account for that too.
3037        let stamped = Metadata {
3038            size: Some(10),
3039            ..Default::default()
3040        };
3041        let metadata_len = serde_json::to_vec(&stamped).unwrap().len();
3042        let expected = (path.len() + 10 + metadata_len) as u64;
3043
3044        assert_eq!(row_size(path, &mutations), expected);
3045        assert_eq!(size, expected, "the size handed back matches the mutations");
3046    }
3047
3048    #[test]
3049    fn row_size_is_nonzero_for_tombstones() {
3050        let path = b"attachments/org.1/objects/abc";
3051        let time_expires = Timestamp::now() + Duration::from_secs(60);
3052        let tombstone = Tombstone {
3053            target: ObjectId::from_storage_path("attachments/org.1/objects/abc/0199").unwrap(),
3054            time_expires: Some(time_expires),
3055        };
3056        let mutations = tombstone_mutations(&tombstone);
3057
3058        assert_eq!(mutations.len(), 2);
3059        let set_cell = mutations[1].mutation.as_ref().unwrap();
3060        let mutation::Mutation::SetCell(set_cell) = set_cell else {
3061            panic!("expected redirect SetCell mutation");
3062        };
3063        assert_eq!(set_cell.family_name, FAMILY_GC);
3064        assert_eq!(set_cell.column_qualifier, COLUMN_REDIRECT);
3065        assert_eq!(set_cell.timestamp_micros, time_expires.as_micros() as i64);
3066        assert!(row_size(path, &mutations) > path.len() as u64);
3067    }
3068
3069    #[cfg(feature = "storage-cogs")]
3070    #[tokio::test]
3071    async fn change_stream_reports_writes_and_deletes() -> Result<()> {
3072        let (backend, producer) = create_test_backend_with_change_stream().await?;
3073        let id = make_id();
3074        let metadata = Metadata {
3075            expiration_policy: ExpirationPolicy::TimeToLive(Duration::from_secs(3600)),
3076            time_expires: Some(Timestamp::now() + Duration::from_secs(3600)),
3077            ..Default::default()
3078        };
3079
3080        backend
3081            .put_object(
3082                &id,
3083                &metadata,
3084                stream::single::<crate::stream::ClientError>(b"hello".to_vec()),
3085                Timestamp::now(),
3086            )
3087            .await?;
3088        backend.delete_object(&id, Timestamp::now()).await?;
3089
3090        let records = producer.records();
3091        assert_eq!(records.len(), 2);
3092
3093        assert_eq!(records[0].op_type, OpType::Write);
3094        assert_eq!(records[0].app_feature, "testing");
3095        assert_eq!(records[0].shared_resource_id, "bigtable_objectstore");
3096        // Key plus payload plus metadata, so strictly more than the payload alone.
3097        assert!(records[0].size.unwrap() > b"hello".len() as u64);
3098        assert!(records[0].expiration_time.is_some());
3099
3100        assert_eq!(records[1].op_type, OpType::Delete);
3101        assert_eq!(records[1].size, None);
3102        assert_eq!(records[1].record_id, records[0].record_id);
3103
3104        Ok(())
3105    }
3106
3107    #[cfg(feature = "storage-cogs")]
3108    #[tokio::test]
3109    async fn change_stream_reports_upload_markers() -> Result<()> {
3110        let (backend, producer) = create_test_backend_with_change_stream().await?;
3111        let revision = new_test_revision(&make_id());
3112        let now = Timestamp::now();
3113        let expires_at = now + Duration::from_secs(3600);
3114
3115        backend.create_upload_marker(&revision, expires_at).await?;
3116        assert!(backend.delete_upload_marker(&revision, now).await?);
3117        assert!(!backend.delete_upload_marker(&revision, now).await?);
3118
3119        let records = producer.records();
3120        assert_eq!(records.len(), 2);
3121        assert_eq!(records[0].op_type, OpType::Write);
3122        assert_eq!(
3123            records[0].size,
3124            Some(revision.as_upload_path().to_string().len() as u64 + 1)
3125        );
3126        assert_eq!(
3127            records[0].expiration_time,
3128            Some(expires_at.as_micros() as i64)
3129        );
3130        assert_eq!(records[1].op_type, OpType::Delete);
3131        assert_eq!(records[1].record_id, records[0].record_id);
3132        Ok(())
3133    }
3134
3135    #[cfg(feature = "storage-cogs")]
3136    #[tokio::test]
3137    async fn delete_non_tombstone_reclaims_expired_rows() -> Result<()> {
3138        let (backend, producer) = create_test_backend_with_change_stream().await?;
3139
3140        // An expired tombstone is past its lifetime: reclaimed, not handed to the caller.
3141        // This test serves as documentation of that potentially surprising behavior.
3142        let id = make_id();
3143        let tombstone = Tombstone {
3144            target: ObjectId::random(id.context().clone()),
3145            time_expires: Some(Timestamp::now() - Duration::from_secs(1)),
3146        };
3147        create_tombstone(&backend, &id, &tombstone).await?;
3148        assert_eq!(
3149            backend.delete_non_tombstone(&id, Timestamp::now()).await?,
3150            None,
3151            "an expired tombstone must not be returned to the caller"
3152        );
3153        let records = producer.records();
3154        assert_eq!(records.len(), 1, "the expired tombstone must be reclaimed");
3155        assert_eq!(records[0].op_type, OpType::Delete);
3156
3157        // The same holds for an object row (expired or otherwise).
3158        let id = make_id();
3159        let metadata = Metadata {
3160            expiration_policy: ExpirationPolicy::TimeToLive(Duration::from_secs(0)),
3161            time_expires: Some(Timestamp::now() - Duration::from_secs(1)),
3162            ..Default::default()
3163        };
3164        create_object(&backend, &id, &metadata, b"gone", Timestamp::now()).await?;
3165        producer.clear();
3166        assert_eq!(
3167            backend.delete_non_tombstone(&id, Timestamp::now()).await?,
3168            None
3169        );
3170        let records = producer.records();
3171        assert_eq!(records.len(), 1, "the object row must be reclaimed");
3172        assert_eq!(records[0].op_type, OpType::Delete);
3173
3174        Ok(())
3175    }
3176
3177    #[cfg(feature = "storage-cogs")]
3178    #[tokio::test]
3179    async fn change_stream_reports_tombstone_rows() -> Result<()> {
3180        let (backend, producer) = create_test_backend_with_change_stream().await?;
3181        let id = make_id();
3182        let target = new_test_revision(&id);
3183
3184        let tombstone = Tombstone {
3185            target: target.clone(),
3186            time_expires: Some(Timestamp::now() + Duration::from_secs(3600)),
3187        };
3188        let written = backend
3189            .compare_and_write(
3190                &id,
3191                None,
3192                TieredWrite::Tombstone(tombstone),
3193                Timestamp::now(),
3194            )
3195            .await?;
3196        assert!(written);
3197
3198        let records = producer.records();
3199        assert_eq!(records.len(), 1);
3200        assert_eq!(records[0].op_type, OpType::Write);
3201        assert!(
3202            records[0].size.unwrap() > 0,
3203            "tombstone rows occupy storage and must not report zero"
3204        );
3205        assert!(records[0].expiration_time.is_some());
3206
3207        Ok(())
3208    }
3209
3210    #[cfg(feature = "storage-cogs")]
3211    #[tokio::test]
3212    async fn change_stream_reports_expiry_extension_as_an_update() -> Result<()> {
3213        let (backend, producer) = create_test_backend_with_change_stream().await?;
3214        let id = make_id();
3215        let metadata = Metadata {
3216            expiration_policy: ExpirationPolicy::TimeToIdle(Duration::from_secs(3600)),
3217            time_expires: Some(Timestamp::now() + Duration::from_secs(1)),
3218            ..Default::default()
3219        };
3220
3221        backend
3222            .put_object(
3223                &id,
3224                &metadata,
3225                stream::single::<crate::stream::ClientError>(b"hello".to_vec()),
3226                Timestamp::now(),
3227            )
3228            .await?;
3229        producer.clear();
3230
3231        backend
3232            .set_expiry(
3233                &id,
3234                ExpiryTarget::At(Timestamp::now() + Duration::from_secs(3600)).into(),
3235                Timestamp::now(),
3236            )
3237            .await?;
3238
3239        let records = producer.records();
3240        assert_eq!(records.len(), 1, "expected exactly one extension report");
3241        assert_eq!(records[0].op_type, OpType::Update);
3242        assert_eq!(
3243            records[0].size, None,
3244            "an extension does not change the size"
3245        );
3246        assert!(records[0].expiration_time.is_some());
3247
3248        Ok(())
3249    }
3250
3251    #[cfg(feature = "storage-cogs")]
3252    fn new_test_revision(id: &ObjectId) -> ObjectId {
3253        ObjectId {
3254            context: id.context.clone(),
3255            key: format!("{}/{}", id.key, uuid::Uuid::now_v7()),
3256        }
3257    }
3258}