diff --git a/go.mod b/go.mod
index 80fbe5e..5de6a20 100644
--- a/go.mod
+++ b/go.mod
@@ -5,6 +5,7 @@
 require (
 	github.com/cockroachdb/pebble v1.1.1
 	github.com/google/generative-ai-go v0.16.0
+	github.com/google/go-replayers/grpcreplay v1.3.0
 	golang.org/x/tools v0.23.0
 	google.golang.org/api v0.186.0
 	rsc.io/markdown v0.0.0-20240617154923-1f2ef1438fed
@@ -19,6 +20,7 @@
 	cloud.google.com/go/auth v0.6.0 // indirect
 	cloud.google.com/go/auth/oauth2adapt v0.2.2 // indirect
 	cloud.google.com/go/compute/metadata v0.3.0 // indirect
+	cloud.google.com/go/firestore v1.15.0 // indirect
 	cloud.google.com/go/longrunning v0.5.7 // indirect
 	github.com/DataDog/zstd v1.4.5 // indirect
 	github.com/beorn7/perks v1.0.1 // indirect
@@ -36,7 +38,6 @@
 	github.com/golang/groupcache v0.0.0-20210331224755-41bb18bfe9da // indirect
 	github.com/golang/protobuf v1.5.4 // indirect
 	github.com/golang/snappy v0.0.4 // indirect
-	github.com/google/go-replayers/grpcreplay v1.2.0 // indirect
 	github.com/google/s2a-go v0.1.7 // indirect
 	github.com/google/uuid v1.6.0 // indirect
 	github.com/googleapis/enterprise-certificate-proxy v0.3.2 // indirect
@@ -65,6 +66,7 @@
 	golang.org/x/sys v0.22.0 // indirect
 	golang.org/x/text v0.16.0 // indirect
 	golang.org/x/time v0.5.0 // indirect
+	google.golang.org/genproto v0.0.0-20240617180043-68d350f18fd4 // indirect
 	google.golang.org/genproto/googleapis/api v0.0.0-20240617180043-68d350f18fd4 // indirect
 	google.golang.org/genproto/googleapis/rpc v0.0.0-20240617180043-68d350f18fd4 // indirect
 	google.golang.org/grpc v1.64.1 // indirect
diff --git a/go.sum b/go.sum
index 01b7262..cf23ab1 100644
--- a/go.sum
+++ b/go.sum
@@ -31,6 +31,8 @@
 cloud.google.com/go/compute/metadata v0.3.0/go.mod h1:zFmK7XCadkQkj6TtorcaGlCW1hT1fIilQDwofLpJ20k=
 cloud.google.com/go/datastore v1.0.0/go.mod h1:LXYbyblFSglQ5pkeyhO+Qmw7ukd3C+pD7TKLgZqpHYE=
 cloud.google.com/go/datastore v1.1.0/go.mod h1:umbIZjpQpHh4hmRpGhH4tLFup+FVzqBi1b3c64qFpCk=
+cloud.google.com/go/firestore v1.15.0 h1:/k8ppuWOtNuDHt2tsRV42yI21uaGnKDEQnRFeBpbFF8=
+cloud.google.com/go/firestore v1.15.0/go.mod h1:GWOxFXcv8GZUtYpWHw/w6IuYNux/BtmeVTMmjrm4yhk=
 cloud.google.com/go/longrunning v0.5.7 h1:WLbHekDbjK1fVFD3ibpFFVoyizlLRl73I7YKuAKilhU=
 cloud.google.com/go/longrunning v0.5.7/go.mod h1:8GClkudohy1Fxm3owmBGid8W0pSgodEMwEAztp38Xng=
 cloud.google.com/go/pubsub v1.0.1/go.mod h1:R0Gpsv3s54REJCy4fxDixWD93lHJMoZTyQ2kNxGRt3I=
@@ -163,6 +165,8 @@
 github.com/google/go-cmp v0.6.0/go.mod h1:17dUlkBOakJ0+DkrSSNjCkIjxS6bF9zb3elmeNGIjoY=
 github.com/google/go-replayers/grpcreplay v1.2.0 h1:JlxRH0a1d8lLTXq6Xl+CD5aqMwHNhMyMxvFjqa3EAvg=
 github.com/google/go-replayers/grpcreplay v1.2.0/go.mod h1:v6NgKtkijC0d3e3RW8il6Sy5sqRVUwoQa4mHOGEy8DI=
+github.com/google/go-replayers/grpcreplay v1.3.0 h1:1Keyy0m1sIpqstQmgz307zhiJ1pV4uIlFds5weTmxbo=
+github.com/google/go-replayers/grpcreplay v1.3.0/go.mod h1:v6NgKtkijC0d3e3RW8il6Sy5sqRVUwoQa4mHOGEy8DI=
 github.com/google/gofuzz v1.0.0/go.mod h1:dBl0BpW6vV/+mYPU4Po3pmUjxk6FQPldtuIdl/M65Eg=
 github.com/google/martian v2.1.0+incompatible/go.mod h1:9I4somxYTbIHy5NJKHRl3wXiIaQGbYVAs8BPL6v8lEs=
 github.com/google/martian/v3 v3.0.0/go.mod h1:y5Zk1BBys9G+gd6Jrk0W3cC1+ELVxBWuIGO+w/tUAp0=
@@ -541,6 +545,8 @@
 google.golang.org/genproto v0.0.0-20200729003335-053ba62fc06f/go.mod h1:FWY/as6DDZQgahTzZj3fqbO1CbirC29ZNUFHwi0/+no=
 google.golang.org/genproto v0.0.0-20200804131852-c06518451d9c/go.mod h1:FWY/as6DDZQgahTzZj3fqbO1CbirC29ZNUFHwi0/+no=
 google.golang.org/genproto v0.0.0-20200825200019-8632dd797987/go.mod h1:FWY/as6DDZQgahTzZj3fqbO1CbirC29ZNUFHwi0/+no=
+google.golang.org/genproto v0.0.0-20240617180043-68d350f18fd4 h1:CUiCqkPw1nNrNQzCCG4WA65m0nAmQiwXHpub3dNyruU=
+google.golang.org/genproto v0.0.0-20240617180043-68d350f18fd4/go.mod h1:EvuUDCulqGgV80RvP1BHuom+smhX4qtlhnNatHuroGQ=
 google.golang.org/genproto/googleapis/api v0.0.0-20240617180043-68d350f18fd4 h1:MuYw1wJzT+ZkybKfaOXKp5hJiZDn2iHaXRw0mRYdHSc=
 google.golang.org/genproto/googleapis/api v0.0.0-20240617180043-68d350f18fd4/go.mod h1:px9SlOOZBg1wM1zdnr8jEL4CNGUBZ+ZKYtNPApNQc4c=
 google.golang.org/genproto/googleapis/rpc v0.0.0-20240617180043-68d350f18fd4 h1:Di6ANFilr+S60a4S61ZM00vLdw0IrQOSMS2/6mrnOU0=
diff --git a/internal/firestore/db.go b/internal/firestore/db.go
new file mode 100644
index 0000000..447cada
--- /dev/null
+++ b/internal/firestore/db.go
@@ -0,0 +1,240 @@
+// Copyright 2024 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package firestore
+
+import (
+	"context"
+	"encoding/hex"
+	"fmt"
+	"iter"
+	"math/rand/v2"
+	"net/url"
+	"slices"
+	"time"
+
+	"cloud.google.com/go/firestore"
+	"golang.org/x/oscar/internal/storage"
+	"google.golang.org/api/option"
+)
+
+// DB implements [storage.DB].
+type DB struct {
+	*fstore
+	uid int64 // unique ID, to identify lock owners
+}
+
+// NewDB constructs a [DB].
+func NewDB(ctx context.Context, dbopts *DBOptions, copts ...option.ClientOption) (*DB, error) {
+	fs, err := newFstore(ctx, dbopts, copts)
+	if err != nil {
+		return nil, err
+	}
+	return &DB{fs, rand.Int64()}, nil
+}
+
+const (
+	lockCollection  = "locks"
+	valueCollection = "values"
+)
+
+// vars for testing
+var (
+	// how long to wait before stealing a lock
+	lockTimeout = 2 * time.Minute
+
+	timeSince = time.Since
+)
+
+// Lock implements [storage.DB.Lock].
+func (db *DB) Lock(name string) {
+	// Wait for the lock in a separate function to avoid defers inside a loop, consuming
+	// memory on each iteration.
+	for !db.waitForLock(name) {
+	}
+}
+
+// waitForLock waits for the lock to become available.
+// It returns true if it acquires the lock.
+// It returns false if the snapshot iterator timed out without the lock
+// being acquired.
+func (db *DB) waitForLock(name string) bool {
+	ctx, cancel := context.WithTimeout(context.Background(), lockTimeout)
+	defer cancel()
+	// A snapshot iterator iterates over changing states of the document.
+	// It yields its first value immediately, and subsequent values only when
+	// the document changes state.
+	dr := db.client.Collection(lockCollection).Doc(url.PathEscape(name))
+	iter := dr.Snapshots(ctx)
+	defer iter.Stop()
+	for {
+		ds, err := iter.Next()
+		if err == nil {
+			if !ds.Exists() && db.tryLock(name) {
+				// The lock doesn't exist and we managed to get it.
+				return true
+			}
+			// Wait for a change in the lock document.
+			continue
+		}
+		if isTimeout(err) {
+			return db.tryLock(name)
+		}
+		// unreachable except for bad DB
+		db.Panic("firestore waiting for lock", "name", name, "err", err)
+	}
+}
+
+// tryLock tries to acquire the named lock in a transaction.
+func (db *DB) tryLock(name string) (res bool) {
+	db.runTransaction(func(ctx context.Context, tx *firestore.Transaction) {
+		uid, createTime := db.getLock(tx, name)
+		if createTime.IsZero() || timeSince(createTime) > lockTimeout {
+			// Lock does not exist or timed out.
+			if !createTime.IsZero() {
+				db.slog.Warn("taking lock", "name", name, "old", uid, "new", db.uid)
+			}
+			db.setLock(tx, name)
+			res = true
+		} else {
+			res = false
+		}
+	})
+	return res
+}
+
+// Unlock releases the lock. It panics if the lock isn't locked by this DB.
+func (db *DB) Unlock(name string) {
+	db.runTransaction(func(ctx context.Context, tx *firestore.Transaction) {
+		uid, createTime := db.getLock(tx, name)
+		if createTime.IsZero() {
+			db.Panic("unlock of never locked key", "key", name)
+		}
+		if uid != db.uid {
+			db.Panic("unlocker is not owner", "key", name)
+		}
+		db.deleteLock(tx, name)
+	})
+}
+
+// A lock describes a lock in firestore.
+// The value consists of the UID of the DB that acquired the lock.
+type lock struct {
+	UID int64
+}
+
+// setLock sets the value of the named lock in the DB, along with its creation time.
+func (db *DB) setLock(tx *firestore.Transaction, name string) {
+	db.set(tx, lockCollection, url.PathEscape(name), lock{db.uid})
+}
+
+// getLock returns the value of the named lock in the DB.
+func (db *DB) getLock(tx *firestore.Transaction, name string) (int64, time.Time) {
+	ds := db.get(tx, lockCollection, url.PathEscape(name))
+	if ds == nil {
+		return 0, time.Time{}
+	}
+	uid := dataTo[lock](db.fstore, ds).UID
+	return uid, ds.CreateTime
+}
+
+// deleteLock deletes the named lock in the DB.
+func (db *DB) deleteLock(tx *firestore.Transaction, name string) {
+	db.delete(tx, lockCollection, url.PathEscape(name))
+}
+
+// Set implements [storage.DB.Set].
+func (db *DB) Set(key, val []byte) {
+	db.set(nil, valueCollection, encodeKey(key), encodeValue(val))
+}
+
+// Get implements [storage.DB.Get].
+func (db *DB) Get(key []byte) ([]byte, bool) {
+	ekey := encodeKey(key)
+	ds := db.get(nil, valueCollection, ekey)
+	if ds == nil {
+		return nil, false
+	}
+	return decodeValue(ds.Data()), true
+}
+
+// Delete implements [storage.DB.Delete].
+func (db *DB) Delete(key []byte) {
+	db.delete(nil, valueCollection, encodeKey(key))
+}
+
+// DeleteRange implements [storage.DB.DeleteRange].
+func (db *DB) DeleteRange(start, end []byte) {
+	db.deleteRange(valueCollection, encodeKey(start), encodeKey(end))
+}
+
+// Scan implements [storage.DB.Scan].
+func (db *DB) Scan(start, end []byte) iter.Seq2[[]byte, func() []byte] {
+	return func(yield func(key []byte, valf func() []byte) bool) {
+		for ds := range db.scan(nil, valueCollection, encodeKey(start), encodeKey(end)) {
+			if !yield(decodeKey(ds.Ref.ID), func() []byte { return decodeValue(ds.Data()) }) {
+				return
+			}
+		}
+	}
+}
+
+// Batch implements [storage.DB.Batch].
+func (db *DB) Batch() storage.Batch {
+	return &dbBatch{db.newBatch(valueCollection)}
+}
+
+type dbBatch struct {
+	b *batch
+}
+
+// Delete implements [storage.Batch.Delete].
+func (b *dbBatch) Delete(key []byte) {
+	b.b.delete(encodeKey(key))
+}
+
+// DeleteRange implements [storage.Batch.DeleteRange].
+func (b *dbBatch) DeleteRange(start, end []byte) {
+	b.b.deleteRange(encodeKey(start), encodeKey(end))
+}
+
+// Set implements [storage.Batch.Set].
+func (b *dbBatch) Set(key, val []byte) {
+	// TODO(jba): account for size of encoded map.
+	b.b.set(encodeKey(key), encodeValue(slices.Clone(val)), len(val))
+}
+
+// MaybeApply implements [storage.Batch.MaybeApply].
+func (b *dbBatch) MaybeApply() bool {
+	return b.b.maybeApply()
+}
+
+// Apply implements [storage.Batch.Apply].
+func (b *dbBatch) Apply() {
+	b.b.apply()
+}
+
+// encodeKey converts k to a string, preserving ordering.
+func encodeKey(k []byte) string {
+	return hex.EncodeToString(k)
+}
+
+func decodeKey(s string) []byte {
+	b, err := hex.DecodeString(s)
+	if err != nil {
+		// unreachable except for bad DB
+		panic(fmt.Sprintf("decodeKey(%q) failed: %v", s, err))
+	}
+	return b
+}
+
+// encodeValue encodes v in a format acceptable to Firestore.
+// (Firestore values must be maps or structs.)
+func encodeValue(v []byte) any {
+	return map[string][]byte{"v": v}
+}
+
+func decodeValue(m map[string]any) []byte {
+	return m["v"].([]byte)
+}
diff --git a/internal/firestore/db_test.go b/internal/firestore/db_test.go
new file mode 100644
index 0000000..dc11d6e
--- /dev/null
+++ b/internal/firestore/db_test.go
@@ -0,0 +1,156 @@
+// Copyright 2024 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package firestore
+
+import (
+	"context"
+	"flag"
+	"fmt"
+	"math/rand/v2"
+	"strings"
+	"testing"
+	"time"
+
+	"golang.org/x/oscar/internal/grpcrr"
+	"golang.org/x/oscar/internal/storage"
+)
+
+var (
+	project  = flag.String("project", "", "project ID for testing")
+	database = flag.String("database", "", "Firestore database for testing")
+)
+
+func TestDB(t *testing.T) {
+	ctx := context.Background()
+	rr, err := grpcrr.Open("testdata/db.grpcrr")
+	if err != nil {
+		t.Fatalf("grpcrr.Open: %v", err)
+	}
+	defer func() {
+		if err := rr.Close(); err != nil {
+			t.Fatal(err)
+		}
+	}()
+
+	var fsProject, fsDatabase string
+	if rr.Recording() {
+		if *project == "" {
+			t.Fatal("recording requires -project")
+		}
+		// The -database flag can be omitted. We'll use the default one.
+		rr.SetInitial([]byte(*project + "," + *database))
+		fsProject = *project
+		fsDatabase = *database
+	} else {
+		// Allow -project and -database on replay because other tests might need them.
+		var found bool
+		fsProject, fsDatabase, found = strings.Cut(string(rr.Initial()), ",")
+		if !found {
+			t.Fatal("bad initial state")
+		}
+	}
+
+	db, err := NewDB(ctx, &DBOptions{ProjectID: fsProject, Database: fsDatabase}, rr.ClientOptions()...)
+	if err != nil {
+		t.Fatal(err)
+	}
+	// Use a fixed UID for deterministic record/replay.
+	db.uid = 1
+	defer db.Close()
+
+	// Make the timeout short, in case the locks exist from a previous run.
+	defer func(lt time.Duration) {
+		lockTimeout = lt
+	}(lockTimeout)
+	lockTimeout = 2 * time.Second
+
+	storage.TestDB(t, db)
+
+	// Test Batch.DeleteRange with MaybeApply.
+	b := db.Batch()
+	b.DeleteRange([]byte("a"), []byte("b"))
+	applied := b.MaybeApply()
+	if !applied {
+		t.Error("MaybeApply with DeleteRange did not apply")
+	}
+}
+
+func TestLock(t *testing.T) {
+	// The lock tests cannot be run with record/replay because they depend too much on time and state.
+	if *project == "" {
+		t.Skip("missing -project")
+	}
+	ctx := context.Background()
+	db, err := NewDB(ctx, &DBOptions{ProjectID: *project, Database: *database})
+	if err != nil {
+		t.Fatal(err)
+	}
+	defer db.Close()
+
+	defer func(lt time.Duration) {
+		lockTimeout = lt
+	}(lockTimeout)
+	lockTimeout = 2 * time.Second
+
+	t.Run("basic", func(t *testing.T) {
+		storage.TestDBLock(t, db)
+	})
+
+	t.Run("timeout", func(t *testing.T) {
+		c := make(chan struct{})
+
+		go func() {
+			db.Lock("L")
+			// The second Lock should wait until the first Lock times
+			// out, then it should succeed.
+			db.Lock("L")
+			db.Unlock("L")
+			close(c)
+		}()
+		select {
+		case <-c:
+			// Success.
+		case <-time.After(2 * lockTimeout):
+			t.Fatal("lock timeout didn't happen in time")
+		}
+	})
+	t.Run("owner", func(t *testing.T) {
+		// When run frequently, this test causes contention on the lock name.
+		// So pick a random name.
+		name := fmt.Sprintf("M%d", rand.IntN(10))
+		db.deleteLock(nil, name) // Ensure the lock is not present.
+		db2, err := NewDB(ctx, &DBOptions{ProjectID: *project, Database: *database})
+		if err != nil {
+			t.Fatal(err)
+		}
+		defer db2.Close()
+
+		func() {
+			defer func() { recover() }()
+			db.Lock(name)
+			db2.Unlock(name)
+			t.Error("unlock wrong owner did not panic")
+		}()
+	})
+}
+
+func TestErrors(t *testing.T) {
+	if !panics(func() {
+		var b batch
+		b.set("x", nil, 1)
+	}) {
+		t.Error("batch.set does not panic on nil value")
+	}
+}
+
+func panics(f func()) (b bool) {
+	defer func() {
+		if recover() != nil {
+			b = true
+		}
+	}()
+	f()
+	return false
+}
diff --git a/internal/firestore/firestore.go b/internal/firestore/firestore.go
new file mode 100644
index 0000000..25d215b
--- /dev/null
+++ b/internal/firestore/firestore.go
@@ -0,0 +1,312 @@
+// Copyright 2024 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package firestore implements [storage.DB] and [storage.VectorDB]
+// using Google Cloud's [Firestore] service.
+//
+// A brief introduction to Firestore: it is a document DB with hierarchical keys.
+// A key is a string of the form "coll1/id1/coll2/id2/.../collN/idN",
+// where the colls are called "collections". The values are called "documents".
+// Each document is a set of key-value pairs. In Go, a document is represented
+// by a map[string]any. The Go Firestore client provides convenience functions for
+// converting documents to and from structs.
+//
+// [Firestore]: https://cloud.google.com/firestore
+package firestore
+
+import (
+	"context"
+	"iter"
+	"log/slog"
+	"reflect"
+
+	"cloud.google.com/go/firestore"
+	"golang.org/x/oscar/internal/storage"
+	"google.golang.org/api/iterator"
+	"google.golang.org/api/option"
+	"google.golang.org/grpc/codes"
+	"google.golang.org/grpc/status"
+)
+
+// DBOptions is the configuration for a [DB] or [VectorDB].
+type DBOptions struct {
+	ProjectID string
+	Database  string
+	Logger    *slog.Logger
+}
+
+// fstore implements operations common to both [storage.DB] and [storage.VectorDB].
+type fstore struct {
+	client *firestore.Client
+	slog   *slog.Logger
+}
+
+func newFstore(ctx context.Context, dbopts *DBOptions, copts []option.ClientOption) (*fstore, error) {
+	if dbopts == nil {
+		dbopts = &DBOptions{}
+	}
+	if dbopts.ProjectID == "" {
+		dbopts.ProjectID = firestore.DetectProjectID
+	}
+	if dbopts.Database == "" {
+		dbopts.Database = firestore.DefaultDatabaseID
+	}
+	if dbopts.Logger == nil {
+		dbopts.Logger = slog.Default()
+	}
+	client, err := firestore.NewClientWithDatabase(ctx, dbopts.ProjectID, dbopts.Database, copts...)
+	if err != nil {
+		return nil, err
+	}
+	return &fstore{client: client, slog: dbopts.Logger}, nil
+}
+
+func (f *fstore) Flush() {
+	// Firestore operations do not require flushing.
+}
+
+func (f *fstore) Close() {
+	if err := f.client.Close(); err != nil {
+		// unreachable except for bad DB
+		f.Panic("firestore close", "err", err)
+	}
+}
+
+func (f *fstore) Panic(msg string, args ...any) {
+	f.slog.Error(msg, args...)
+	storage.Panic(msg, args...)
+}
+
+// get retrieves the document with the given collection and ID.
+// If tx is non-nil, the get happens inside the transaction.
+func (f *fstore) get(tx *firestore.Transaction, coll, id string) *firestore.DocumentSnapshot {
+	dr := f.client.Collection(coll).Doc(id)
+	var ds *firestore.DocumentSnapshot
+	var err error
+	if tx == nil {
+		ds, err = dr.Get(context.TODO())
+	} else {
+		ds, err = tx.Get(dr)
+	}
+	if err != nil {
+		if isNotFound(err) {
+			return nil
+		}
+		// unreachable except for bad DB
+		f.Panic("firestore get", "collection", coll, "key", id, "err", err)
+	}
+	return ds
+}
+
+// set sets the document with the given collection and ID to value.
+// If tx is non-nil, the set happens inside the transaction.
+func (f *fstore) set(tx *firestore.Transaction, coll, key string, value any) {
+	dr := f.client.Collection(coll).Doc(key)
+	var err error
+	if tx == nil {
+		_, err = dr.Set(context.TODO(), value)
+	} else {
+		err = tx.Set(dr, value)
+	}
+	if err != nil {
+		// unreachable except for bad DB
+		f.Panic("firestore set", "collection", coll, "key", key, "err", err)
+	}
+}
+
+// delete deletes the document with the given collection and ID.
+// If tx is non-nil, the delete happens inside the transaction.
+// It is not an error to call delete on a document that doesn't exist.
+func (f *fstore) delete(tx *firestore.Transaction, coll, key string) {
+	dr := f.client.Collection(coll).Doc(key)
+	var err error
+	if tx == nil {
+		_, err = dr.Delete(context.TODO())
+	} else {
+		err = tx.Delete(dr)
+	}
+	if err != nil {
+		// unreachable except for bad DB
+		f.Panic("firestore delete", "collection", coll, "key", key, "err", err)
+	}
+}
+
+// deleteRange deletes all the documents in the collection coll whose IDs are between
+// start and end, inclusive.
+func (f *fstore) deleteRange(coll, start, end string) {
+	bw := f.client.BulkWriter(context.TODO())
+	for ds := range f.scan(nil, coll, start, end) {
+		if _, err := bw.Delete(ds.Ref); err != nil {
+			// unreachable except for bad DB
+			f.Panic("firestore delete range", "collection", coll, "err", err)
+		}
+	}
+	bw.End()
+}
+
+// runTransaction executes fn inside a transaction.
+func (f *fstore) runTransaction(fn func(ctx context.Context, tx *firestore.Transaction)) {
+	err := f.client.RunTransaction(context.TODO(), func(ctx context.Context, tx *firestore.Transaction) error {
+		fn(ctx, tx)
+		return nil
+	})
+	if err != nil {
+		// unreachable except for bad DB
+		f.Panic("firestore transaction", "err", err)
+	}
+}
+
+// scan returns an iterator over the documents in the collection coll whose IDs are
+// between start and end, inclusive.
+func (f *fstore) scan(tx *firestore.Transaction, coll, start, end string) iter.Seq[*firestore.DocumentSnapshot] {
+	query := f.client.Collection(coll).
+		OrderBy(firestore.DocumentID, firestore.Asc).
+		StartAt(start).
+		EndAt(end)
+	var iter *firestore.DocumentIterator
+	if tx == nil {
+		iter = query.Documents(context.TODO())
+	} else {
+		iter = tx.Documents(query)
+	}
+	return func(yield func(*firestore.DocumentSnapshot) bool) {
+		defer iter.Stop()
+		for {
+			ds, err := iter.Next()
+			if err == iterator.Done {
+				return
+			}
+			if err != nil {
+				// unreachable except for bad DB
+				f.Panic("firestore scan", "collection", coll, "err", err)
+			}
+			if !yield(ds) {
+				return
+			}
+		}
+	}
+}
+
+// dataTo converts the data in the given DocumentSnapshot to a value of type T.
+func dataTo[T any](f *fstore, ds *firestore.DocumentSnapshot) T {
+	var data T
+	if err := ds.DataTo(&data); err != nil {
+		// unreachable except for bad DB
+		f.Panic("dataTo", "type", reflect.TypeFor[T](), "err", err)
+	}
+	return data
+}
+
+// batch implements [storage.Batch].
+// All of a batch's operations must occur within the same collection.
+type batch struct {
+	f              *fstore
+	coll           string
+	ops            []*op
+	size           int  // approximate size of ops
+	hasDeleteRange bool // at least one op is a deleteRange
+}
+
+func (f *fstore) newBatch(coll string) *batch {
+	return &batch{f: f, coll: coll, size: fixedSize}
+}
+
+// An op is a single batch operation.
+type op struct {
+	id    string // or start, for deleteRange
+	value any    // nil for delete, deleteRange
+	// for deleteRange:
+	end       string
+	deleteIDs []string // the list of IDs to delete, determined inside the transaction
+}
+
+// Approximate proto sizes, determined empirically.
+const (
+	fixedSize    = 300
+	perWriteSize = 5
+	// Firestore supposedly has a limit of 10 MiB per request
+	// (see https://cloud.google.com/firestore/quotas#writes_and_transactions).
+	// However, I found that exceeding 4 MiB often failed
+	// with a "too big" error.
+	maxSize = 4 << 20
+)
+
+// set adds a set operation to the batch. It is the caller's responsibility to
+// estimate the size of val.
+func (b *batch) set(id string, val any, valSize int) {
+	if val == nil {
+		panic("firestore batch set: nil value")
+	}
+	b.ops = append(b.ops, &op{id: id, value: val})
+	b.size += perWriteSize + len(id) + valSize
+}
+
+// delete adds a delete operation to the batch.
+func (b *batch) delete(id string) {
+	b.ops = append(b.ops, &op{id: id, value: nil})
+	b.size += perWriteSize + len(id)
+}
+
+// delete adds a deleteRange operation to the batch.
+func (b *batch) deleteRange(start, end string) {
+	b.ops = append(b.ops, &op{id: start, end: end})
+	b.size += perWriteSize + len(start) + len(end)
+	b.hasDeleteRange = true
+}
+
+// maybeApply applies the batch if it is big enough.
+func (b *batch) maybeApply() bool {
+	// Apply if the batch is large, or if there is even one deleteRange.
+	// We don't know how many documents are in the range, and each one
+	// is a separate operation in the transaction, so be conservative.
+	if b.size > maxSize || b.hasDeleteRange {
+		b.apply()
+		return true
+	}
+	return false
+}
+
+// apply applies the batch by executing all its operations in a transaction.
+func (b *batch) apply() {
+	b.f.runTransaction(func(ctx context.Context, tx *firestore.Transaction) {
+		// Reads must happen before writes in a transaction, and we can only delete
+		// a range by querying the documents.
+		// So read all the ranges first, and store the IDs in their respective ops
+		// to preserve deletion order.
+		for _, op := range b.ops {
+			if op.end != "" {
+				for ds := range b.f.scan(tx, b.coll, op.id, op.end) {
+					op.deleteIDs = append(op.deleteIDs, ds.Ref.ID)
+				}
+			}
+		}
+
+		// Execute each op inside the transaction.
+		for _, op := range b.ops {
+			switch {
+			case op.value != nil: // set
+				b.f.set(tx, b.coll, op.id, op.value)
+			case op.end == "": // delete
+				b.f.delete(tx, b.coll, op.id)
+			default: // deleteRange
+				for _, id := range op.deleteIDs {
+					b.f.delete(tx, b.coll, id)
+				}
+			}
+		}
+	})
+	b.ops = nil
+	b.size = fixedSize
+}
+
+// isNotFound reports whether an error returned by the Firestore client is a NotFound
+// error.
+func isNotFound(err error) bool {
+	return status.Code(err) == codes.NotFound
+}
+
+// isTimeout reports whether an error returned by the Firestore client indicates a timeout.
+func isTimeout(err error) bool {
+	return status.Code(err) == codes.DeadlineExceeded
+}
diff --git a/internal/firestore/testdata/db.grpcrr b/internal/firestore/testdata/db.grpcrr
new file mode 100644
index 0000000..0750b1a
--- /dev/null
+++ b/internal/firestore/testdata/db.grpcrr
@@ -0,0 +1,1424 @@
+RPCReTxt1
+"go-discovery-exp,"
+443
+kind: REQUEST
+method: "/google.firestore.v1.Firestore/Commit"
+message: {
+  [type.googleapis.com/google.firestore.v1.CommitRequest]: {
+    database: "projects/go-discovery-exp/databases/(default)"
+    writes: {
+      update: {
+        name: "projects/go-discovery-exp/databases/(default)/documents/values/6b6579"
+        fields: {
+          key: "v"
+          value: {
+            bytes_value: "value"
+          }
+        }
+      }
+    }
+  }
+}
+290
+kind: RESPONSE
+message: {
+  [type.googleapis.com/google.firestore.v1.CommitResponse]: {
+    write_results: {
+      update_time: {
+        seconds: 1721655326
+        nanos: 448583000
+      }
+    }
+    commit_time: {
+      seconds: 1721655326
+      nanos: 448583000
+    }
+  }
+}
+ref_index: 1
+79
+kind: CREATE_STREAM
+method: "/google.firestore.v1.Firestore/BatchGetDocuments"
+262
+kind: SEND
+message: {
+  [type.googleapis.com/google.firestore.v1.BatchGetDocumentsRequest]: {
+    database: "projects/go-discovery-exp/databases/(default)"
+    documents: "projects/go-discovery-exp/databases/(default)/documents/values/6b6579"
+  }
+}
+ref_index: 3
+552
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.BatchGetDocumentsResponse]: {
+    found: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/6b6579"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "value"
+        }
+      }
+      create_time: {
+        seconds: 1721655326
+        nanos: 448583000
+      }
+      update_time: {
+        seconds: 1721655326
+        nanos: 448583000
+      }
+    }
+    read_time: {
+      seconds: 1721655326
+      nanos: 448583000
+    }
+  }
+}
+ref_index: 3
+39
+kind: RECV
+is_error: true
+ref_index: 3
+79
+kind: CREATE_STREAM
+method: "/google.firestore.v1.Firestore/BatchGetDocuments"
+270
+kind: SEND
+message: {
+  [type.googleapis.com/google.firestore.v1.BatchGetDocumentsRequest]: {
+    database: "projects/go-discovery-exp/databases/(default)"
+    documents: "projects/go-discovery-exp/databases/(default)/documents/values/6d697373696e67"
+  }
+}
+ref_index: 7
+279
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.BatchGetDocumentsResponse]: {
+    missing: "projects/go-discovery-exp/databases/(default)/documents/values/6d697373696e67"
+    read_time: {
+      seconds: 1721655326
+      nanos: 756828000
+    }
+  }
+}
+ref_index: 7
+39
+kind: RECV
+is_error: true
+ref_index: 7
+308
+kind: REQUEST
+method: "/google.firestore.v1.Firestore/Commit"
+message: {
+  [type.googleapis.com/google.firestore.v1.CommitRequest]: {
+    database: "projects/go-discovery-exp/databases/(default)"
+    writes: {
+      delete: "projects/go-discovery-exp/databases/(default)/documents/values/6b6579"
+    }
+  }
+}
+204
+kind: RESPONSE
+message: {
+  [type.googleapis.com/google.firestore.v1.CommitResponse]: {
+    write_results: {}
+    commit_time: {
+      seconds: 1721655326
+      nanos: 859376000
+    }
+  }
+}
+ref_index: 11
+79
+kind: CREATE_STREAM
+method: "/google.firestore.v1.Firestore/BatchGetDocuments"
+263
+kind: SEND
+message: {
+  [type.googleapis.com/google.firestore.v1.BatchGetDocumentsRequest]: {
+    database: "projects/go-discovery-exp/databases/(default)"
+    documents: "projects/go-discovery-exp/databases/(default)/documents/values/6b6579"
+  }
+}
+ref_index: 13
+272
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.BatchGetDocumentsResponse]: {
+    missing: "projects/go-discovery-exp/databases/(default)/documents/values/6b6579"
+    read_time: {
+      seconds: 1721655326
+      nanos: 944912000
+    }
+  }
+}
+ref_index: 13
+40
+kind: RECV
+is_error: true
+ref_index: 13
+222
+kind: REQUEST
+method: "/google.firestore.v1.Firestore/BeginTransaction"
+message: {
+  [type.googleapis.com/google.firestore.v1.BeginTransactionRequest]: {
+    database: "projects/go-discovery-exp/databases/(default)"
+  }
+}
+414
+kind: RESPONSE
+message: {
+  [type.googleapis.com/google.firestore.v1.BeginTransactionResponse]: {
+    transaction: "\x11\xc7b\xd1~RZ5\xd4\"Y\x00\xd4u\xc8\xcdJ\xaf7\xa7\x8b\x0f`\xc7\x12!sG\xae\xacC\xab\x9dh\x92\x94\x87]\xc7\xfe\x15\x07jb\x00l\x8d\x19'2\xfd\x88S\x85\xf9\x13\x84{\x12\xc6\xd5\x18\x80\xc4\"\xa7d\xf8z\xae\xf1\xfe$'V\x15m\xc6ia\x07V\x07 \x8e<\xf3\xba*\xb0*\xeb\x83Yr\x85\xa5Ab\xc9"
+  }
+}
+ref_index: 17
+2848
+kind: REQUEST
+method: "/google.firestore.v1.Firestore/Commit"
+message: {
+  [type.googleapis.com/google.firestore.v1.CommitRequest]: {
+    database: "projects/go-discovery-exp/databases/(default)"
+    writes: {
+      update: {
+        name: "projects/go-discovery-exp/databases/(default)/documents/values/3000"
+        fields: {
+          key: "v"
+          value: {
+            bytes_value: "0"
+          }
+        }
+      }
+    }
+    writes: {
+      update: {
+        name: "projects/go-discovery-exp/databases/(default)/documents/values/3001"
+        fields: {
+          key: "v"
+          value: {
+            bytes_value: "1"
+          }
+        }
+      }
+    }
+    writes: {
+      update: {
+        name: "projects/go-discovery-exp/databases/(default)/documents/values/3002"
+        fields: {
+          key: "v"
+          value: {
+            bytes_value: "2"
+          }
+        }
+      }
+    }
+    writes: {
+      update: {
+        name: "projects/go-discovery-exp/databases/(default)/documents/values/3003"
+        fields: {
+          key: "v"
+          value: {
+            bytes_value: "3"
+          }
+        }
+      }
+    }
+    writes: {
+      update: {
+        name: "projects/go-discovery-exp/databases/(default)/documents/values/3004"
+        fields: {
+          key: "v"
+          value: {
+            bytes_value: "4"
+          }
+        }
+      }
+    }
+    writes: {
+      update: {
+        name: "projects/go-discovery-exp/databases/(default)/documents/values/3005"
+        fields: {
+          key: "v"
+          value: {
+            bytes_value: "5"
+          }
+        }
+      }
+    }
+    writes: {
+      update: {
+        name: "projects/go-discovery-exp/databases/(default)/documents/values/3006"
+        fields: {
+          key: "v"
+          value: {
+            bytes_value: "6"
+          }
+        }
+      }
+    }
+    writes: {
+      update: {
+        name: "projects/go-discovery-exp/databases/(default)/documents/values/3007"
+        fields: {
+          key: "v"
+          value: {
+            bytes_value: "7"
+          }
+        }
+      }
+    }
+    writes: {
+      update: {
+        name: "projects/go-discovery-exp/databases/(default)/documents/values/3008"
+        fields: {
+          key: "v"
+          value: {
+            bytes_value: "8"
+          }
+        }
+      }
+    }
+    writes: {
+      update: {
+        name: "projects/go-discovery-exp/databases/(default)/documents/values/3009"
+        fields: {
+          key: "v"
+          value: {
+            bytes_value: "9"
+          }
+        }
+      }
+    }
+    transaction: "\x11\xc7b\xd1~RZ5\xd4\"Y\x00\xd4u\xc8\xcdJ\xaf7\xa7\x8b\x0f`\xc7\x12!sG\xae\xacC\xab\x9dh\x92\x94\x87]\xc7\xfe\x15\x07jb\x00l\x8d\x19'2\xfd\x88S\x85\xf9\x13\x84{\x12\xc6\xd5\x18\x80\xc4\"\xa7d\xf8z\xae\xf1\xfe$'V\x15m\xc6ia\x07V\x07 \x8e<\xf3\xba*\xb0*\xeb\x83Yr\x85\xa5Ab\xc9"
+  }
+}
+1271
+kind: RESPONSE
+message: {
+  [type.googleapis.com/google.firestore.v1.CommitResponse]: {
+    write_results: {
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    write_results: {
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    write_results: {
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    write_results: {
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    write_results: {
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    write_results: {
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    write_results: {
+      update_time: {
+        seconds: 1721655264
+        nanos: 64308000
+      }
+    }
+    write_results: {
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    write_results: {
+      update_time: {
+        seconds: 1721171630
+        nanos: 112889000
+      }
+    }
+    write_results: {
+      update_time: {
+        seconds: 1721171630
+        nanos: 112889000
+      }
+    }
+    commit_time: {
+      seconds: 1721655327
+      nanos: 222942000
+    }
+  }
+}
+ref_index: 19
+70
+kind: CREATE_STREAM
+method: "/google.firestore.v1.Firestore/RunQuery"
+695
+kind: SEND
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryRequest]: {
+    parent: "projects/go-discovery-exp/databases/(default)/documents"
+    structured_query: {
+      from: {
+        collection_id: "values"
+      }
+      order_by: {
+        field: {
+          field_path: "__name__"
+        }
+        direction: ASCENDING
+      }
+      start_at: {
+        values: {
+          reference_value: "projects/go-discovery-exp/databases/(default)/documents/values/3003"
+        }
+        before: true
+      }
+      end_at: {
+        values: {
+          reference_value: "projects/go-discovery-exp/databases/(default)/documents/values/3006"
+        }
+      }
+    }
+  }
+}
+ref_index: 21
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3003"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "3"
+        }
+      }
+      create_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 322624000
+    }
+  }
+}
+ref_index: 21
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3004"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "4"
+        }
+      }
+      create_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 322624000
+    }
+  }
+}
+ref_index: 21
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3005"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "5"
+        }
+      }
+      create_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 322624000
+    }
+  }
+}
+ref_index: 21
+539
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3006"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "6"
+        }
+      }
+      create_time: {
+        seconds: 1721655264
+        nanos: 64308000
+      }
+      update_time: {
+        seconds: 1721655264
+        nanos: 64308000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 322624000
+    }
+  }
+}
+ref_index: 21
+40
+kind: RECV
+is_error: true
+ref_index: 21
+70
+kind: CREATE_STREAM
+method: "/google.firestore.v1.Firestore/RunQuery"
+695
+kind: SEND
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryRequest]: {
+    parent: "projects/go-discovery-exp/databases/(default)/documents"
+    structured_query: {
+      from: {
+        collection_id: "values"
+      }
+      order_by: {
+        field: {
+          field_path: "__name__"
+        }
+        direction: ASCENDING
+      }
+      start_at: {
+        values: {
+          reference_value: "projects/go-discovery-exp/databases/(default)/documents/values/3003"
+        }
+        before: true
+      }
+      end_at: {
+        values: {
+          reference_value: "projects/go-discovery-exp/databases/(default)/documents/values/3006"
+        }
+      }
+    }
+  }
+}
+ref_index: 28
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3003"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "3"
+        }
+      }
+      create_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 565710000
+    }
+  }
+}
+ref_index: 28
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3004"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "4"
+        }
+      }
+      create_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 565710000
+    }
+  }
+}
+ref_index: 28
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3005"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "5"
+        }
+      }
+      create_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 565710000
+    }
+  }
+}
+ref_index: 28
+70
+kind: CREATE_STREAM
+method: "/google.firestore.v1.Firestore/RunQuery"
+695
+kind: SEND
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryRequest]: {
+    parent: "projects/go-discovery-exp/databases/(default)/documents"
+    structured_query: {
+      from: {
+        collection_id: "values"
+      }
+      order_by: {
+        field: {
+          field_path: "__name__"
+        }
+        direction: ASCENDING
+      }
+      start_at: {
+        values: {
+          reference_value: "projects/go-discovery-exp/databases/(default)/documents/values/3004"
+        }
+        before: true
+      }
+      end_at: {
+        values: {
+          reference_value: "projects/go-discovery-exp/databases/(default)/documents/values/3007"
+        }
+      }
+    }
+  }
+}
+ref_index: 33
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3004"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "4"
+        }
+      }
+      create_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 657343000
+    }
+  }
+}
+ref_index: 33
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3005"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "5"
+        }
+      }
+      create_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 657343000
+    }
+  }
+}
+ref_index: 33
+539
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3006"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "6"
+        }
+      }
+      create_time: {
+        seconds: 1721655264
+        nanos: 64308000
+      }
+      update_time: {
+        seconds: 1721655264
+        nanos: 64308000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 657343000
+    }
+  }
+}
+ref_index: 33
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3007"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "7"
+        }
+      }
+      create_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 657343000
+    }
+  }
+}
+ref_index: 33
+40
+kind: RECV
+is_error: true
+ref_index: 33
+626
+kind: REQUEST
+method: "/google.firestore.v1.Firestore/BatchWrite"
+message: {
+  [type.googleapis.com/google.firestore.v1.BatchWriteRequest]: {
+    database: "projects/go-discovery-exp/databases/(default)"
+    writes: {
+      delete: "projects/go-discovery-exp/databases/(default)/documents/values/3004"
+    }
+    writes: {
+      delete: "projects/go-discovery-exp/databases/(default)/documents/values/3005"
+    }
+    writes: {
+      delete: "projects/go-discovery-exp/databases/(default)/documents/values/3006"
+    }
+    writes: {
+      delete: "projects/go-discovery-exp/databases/(default)/documents/values/3007"
+    }
+  }
+}
+260
+kind: RESPONSE
+message: {
+  [type.googleapis.com/google.firestore.v1.BatchWriteResponse]: {
+    write_results: {}
+    write_results: {}
+    write_results: {}
+    write_results: {}
+    status: {}
+    status: {}
+    status: {}
+    status: {}
+  }
+}
+ref_index: 40
+70
+kind: CREATE_STREAM
+method: "/google.firestore.v1.Firestore/RunQuery"
+695
+kind: SEND
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryRequest]: {
+    parent: "projects/go-discovery-exp/databases/(default)/documents"
+    structured_query: {
+      from: {
+        collection_id: "values"
+      }
+      order_by: {
+        field: {
+          field_path: "__name__"
+        }
+        direction: ASCENDING
+      }
+      start_at: {
+        values: {
+          reference_value: "projects/go-discovery-exp/databases/(default)/documents/values/2fff"
+        }
+        before: true
+      }
+      end_at: {
+        values: {
+          reference_value: "projects/go-discovery-exp/databases/(default)/documents/values/300b"
+        }
+      }
+    }
+  }
+}
+ref_index: 42
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3000"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "0"
+        }
+      }
+      create_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 903250000
+    }
+  }
+}
+ref_index: 42
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3001"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "1"
+        }
+      }
+      create_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 903250000
+    }
+  }
+}
+ref_index: 42
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3002"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "2"
+        }
+      }
+      create_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 903250000
+    }
+  }
+}
+ref_index: 42
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3003"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "3"
+        }
+      }
+      create_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 903250000
+    }
+  }
+}
+ref_index: 42
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3008"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "8"
+        }
+      }
+      create_time: {
+        seconds: 1721171630
+        nanos: 112889000
+      }
+      update_time: {
+        seconds: 1721171630
+        nanos: 112889000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 903250000
+    }
+  }
+}
+ref_index: 42
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3009"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "9"
+        }
+      }
+      create_time: {
+        seconds: 1721171630
+        nanos: 112889000
+      }
+      update_time: {
+        seconds: 1721171630
+        nanos: 112889000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 903250000
+    }
+  }
+}
+ref_index: 42
+40
+kind: RECV
+is_error: true
+ref_index: 42
+222
+kind: REQUEST
+method: "/google.firestore.v1.Firestore/BeginTransaction"
+message: {
+  [type.googleapis.com/google.firestore.v1.BeginTransactionRequest]: {
+    database: "projects/go-discovery-exp/databases/(default)"
+  }
+}
+410
+kind: RESPONSE
+message: {
+  [type.googleapis.com/google.firestore.v1.BeginTransactionResponse]: {
+    transaction: "\x11s\xa5\xdd0k\xd2\x04\x0f\"Y\x00\xd4u\xc8\xcd\x1d\xe5\xd31\xeb\xc1i\x01l+~M\xe6\xeb\xc3\xe1\xf22\xa5\xcc\x01G1\xe3i\xc4u\xf0\xa4Lt!\x07\x97\xeb\xaeൃX \xac\x1f\x7f\xf2\x8b\xa9\x7f;\x1e\xd6\xf7\x8f\x11RSi\xfaME\x82\xa1c\x85\xf8^\xf0'\xcfX\xbfN{e\xef\xeb\xa6XRς\x19\x055"
+  }
+}
+ref_index: 51
+70
+kind: CREATE_STREAM
+method: "/google.firestore.v1.Firestore/RunQuery"
+987
+kind: SEND
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryRequest]: {
+    parent: "projects/go-discovery-exp/databases/(default)/documents"
+    structured_query: {
+      from: {
+        collection_id: "values"
+      }
+      order_by: {
+        field: {
+          field_path: "__name__"
+        }
+        direction: ASCENDING
+      }
+      start_at: {
+        values: {
+          reference_value: "projects/go-discovery-exp/databases/(default)/documents/values/3000"
+        }
+        before: true
+      }
+      end_at: {
+        values: {
+          reference_value: "projects/go-discovery-exp/databases/(default)/documents/values/3000"
+        }
+      }
+    }
+    transaction: "\x11s\xa5\xdd0k\xd2\x04\x0f\"Y\x00\xd4u\xc8\xcd\x1d\xe5\xd31\xeb\xc1i\x01l+~M\xe6\xeb\xc3\xe1\xf22\xa5\xcc\x01G1\xe3i\xc4u\xf0\xa4Lt!\x07\x97\xeb\xaeൃX \xac\x1f\x7f\xf2\x8b\xa9\x7f;\x1e\xd6\xf7\x8f\x11RSi\xfaME\x82\xa1c\x85\xf8^\xf0'\xcfX\xbfN{e\xef\xeb\xa6XRς\x19\x055"
+  }
+}
+ref_index: 53
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3000"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "0"
+        }
+      }
+      create_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+      update_time: {
+        seconds: 1721655327
+        nanos: 222942000
+      }
+    }
+    read_time: {
+      seconds: 1721655327
+      nanos: 907076000
+    }
+  }
+}
+ref_index: 53
+40
+kind: RECV
+is_error: true
+ref_index: 53
+2293
+kind: REQUEST
+method: "/google.firestore.v1.Firestore/Commit"
+message: {
+  [type.googleapis.com/google.firestore.v1.CommitRequest]: {
+    database: "projects/go-discovery-exp/databases/(default)"
+    writes: {
+      delete: "projects/go-discovery-exp/databases/(default)/documents/values/3000"
+    }
+    writes: {
+      update: {
+        name: "projects/go-discovery-exp/databases/(default)/documents/values/3000"
+        fields: {
+          key: "v"
+          value: {
+            bytes_value: "0"
+          }
+        }
+      }
+    }
+    writes: {
+      delete: "projects/go-discovery-exp/databases/(default)/documents/values/3001"
+    }
+    writes: {
+      update: {
+        name: "projects/go-discovery-exp/databases/(default)/documents/values/3002"
+        fields: {
+          key: "v"
+          value: {
+            bytes_value: "2"
+          }
+        }
+      }
+    }
+    writes: {
+      delete: "projects/go-discovery-exp/databases/(default)/documents/values/3002"
+    }
+    writes: {
+      update: {
+        name: "projects/go-discovery-exp/databases/(default)/documents/values/3004"
+        fields: {
+          key: "v"
+          value: {
+            bytes_value: "4"
+          }
+        }
+      }
+    }
+    writes: {
+      delete: "projects/go-discovery-exp/databases/(default)/documents/values/3003"
+    }
+    writes: {
+      update: {
+        name: "projects/go-discovery-exp/databases/(default)/documents/values/3006"
+        fields: {
+          key: "v"
+          value: {
+            bytes_value: "6"
+          }
+        }
+      }
+    }
+    writes: {
+      delete: "projects/go-discovery-exp/databases/(default)/documents/values/3004"
+    }
+    writes: {
+      update: {
+        name: "projects/go-discovery-exp/databases/(default)/documents/values/3008"
+        fields: {
+          key: "v"
+          value: {
+            bytes_value: "8"
+          }
+        }
+      }
+    }
+    writes: {
+      delete: "projects/go-discovery-exp/databases/(default)/documents/values/3000"
+    }
+    transaction: "\x11s\xa5\xdd0k\xd2\x04\x0f\"Y\x00\xd4u\xc8\xcd\x1d\xe5\xd31\xeb\xc1i\x01l+~M\xe6\xeb\xc3\xe1\xf22\xa5\xcc\x01G1\xe3i\xc4u\xf0\xa4Lt!\x07\x97\xeb\xaeൃX \xac\x1f\x7f\xf2\x8b\xa9\x7f;\x1e\xd6\xf7\x8f\x11RSi\xfaME\x82\xa1c\x85\xf8^\xf0'\xcfX\xbfN{e\xef\xeb\xa6XRς\x19\x055"
+  }
+}
+598
+kind: RESPONSE
+message: {
+  [type.googleapis.com/google.firestore.v1.CommitResponse]: {
+    write_results: {}
+    write_results: {}
+    write_results: {}
+    write_results: {}
+    write_results: {}
+    write_results: {}
+    write_results: {}
+    write_results: {
+      update_time: {
+        seconds: 1721655328
+        nanos: 296191000
+      }
+    }
+    write_results: {}
+    write_results: {
+      update_time: {
+        seconds: 1721171630
+        nanos: 112889000
+      }
+    }
+    write_results: {}
+    commit_time: {
+      seconds: 1721655328
+      nanos: 296191000
+    }
+  }
+}
+ref_index: 57
+70
+kind: CREATE_STREAM
+method: "/google.firestore.v1.Firestore/RunQuery"
+695
+kind: SEND
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryRequest]: {
+    parent: "projects/go-discovery-exp/databases/(default)/documents"
+    structured_query: {
+      from: {
+        collection_id: "values"
+      }
+      order_by: {
+        field: {
+          field_path: "__name__"
+        }
+        direction: ASCENDING
+      }
+      start_at: {
+        values: {
+          reference_value: "projects/go-discovery-exp/databases/(default)/documents/values/2fff"
+        }
+        before: true
+      }
+      end_at: {
+        values: {
+          reference_value: "projects/go-discovery-exp/databases/(default)/documents/values/300b"
+        }
+      }
+    }
+  }
+}
+ref_index: 59
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3006"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "6"
+        }
+      }
+      create_time: {
+        seconds: 1721655328
+        nanos: 296191000
+      }
+      update_time: {
+        seconds: 1721655328
+        nanos: 296191000
+      }
+    }
+    read_time: {
+      seconds: 1721655328
+      nanos: 389515000
+    }
+  }
+}
+ref_index: 59
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3008"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "8"
+        }
+      }
+      create_time: {
+        seconds: 1721171630
+        nanos: 112889000
+      }
+      update_time: {
+        seconds: 1721171630
+        nanos: 112889000
+      }
+    }
+    read_time: {
+      seconds: 1721655328
+      nanos: 389515000
+    }
+  }
+}
+ref_index: 59
+541
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    document: {
+      name: "projects/go-discovery-exp/databases/(default)/documents/values/3009"
+      fields: {
+        key: "v"
+        value: {
+          bytes_value: "9"
+        }
+      }
+      create_time: {
+        seconds: 1721171630
+        nanos: 112889000
+      }
+      update_time: {
+        seconds: 1721171630
+        nanos: 112889000
+      }
+    }
+    read_time: {
+      seconds: 1721655328
+      nanos: 389515000
+    }
+  }
+}
+ref_index: 59
+40
+kind: RECV
+is_error: true
+ref_index: 59
+222
+kind: REQUEST
+method: "/google.firestore.v1.Firestore/BeginTransaction"
+message: {
+  [type.googleapis.com/google.firestore.v1.BeginTransactionRequest]: {
+    database: "projects/go-discovery-exp/databases/(default)"
+  }
+}
+408
+kind: RESPONSE
+message: {
+  [type.googleapis.com/google.firestore.v1.BeginTransactionResponse]: {
+    transaction: "\x11\x11 \x8b\x8cX\xe5\x84\xdc\"Y\x00\xd4u\xc8͎\xeb=\xcc\x18ב\x02\x1fu\xed\xaaj\xc0\xf4zZ+\xb8\xb3E\xb9N\xc6\x14\xe2\xbdk\xac\xa8\x1bj\xd7\x0e\x97R<\x7fR\xd3\x0f\x84\xc3\x1d\x14\xb0\xf0\r<G\xf2I\xdf\xee*\xc2x1h.$\xa2X\x12dyY\x10\x95I\xb3w\x99\xdf\xcd\xcefy\xa1V\xe5n4?"
+  }
+}
+ref_index: 65
+70
+kind: CREATE_STREAM
+method: "/google.firestore.v1.Firestore/RunQuery"
+981
+kind: SEND
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryRequest]: {
+    parent: "projects/go-discovery-exp/databases/(default)/documents"
+    structured_query: {
+      from: {
+        collection_id: "values"
+      }
+      order_by: {
+        field: {
+          field_path: "__name__"
+        }
+        direction: ASCENDING
+      }
+      start_at: {
+        values: {
+          reference_value: "projects/go-discovery-exp/databases/(default)/documents/values/61"
+        }
+        before: true
+      }
+      end_at: {
+        values: {
+          reference_value: "projects/go-discovery-exp/databases/(default)/documents/values/62"
+        }
+      }
+    }
+    transaction: "\x11\x11 \x8b\x8cX\xe5\x84\xdc\"Y\x00\xd4u\xc8͎\xeb=\xcc\x18ב\x02\x1fu\xed\xaaj\xc0\xf4zZ+\xb8\xb3E\xb9N\xc6\x14\xe2\xbdk\xac\xa8\x1bj\xd7\x0e\x97R<\x7fR\xd3\x0f\x84\xc3\x1d\x14\xb0\xf0\r<G\xf2I\xdf\xee*\xc2x1h.$\xa2X\x12dyY\x10\x95I\xb3w\x99\xdf\xcd\xcefy\xa1V\xe5n4?"
+  }
+}
+ref_index: 67
+178
+kind: RECV
+message: {
+  [type.googleapis.com/google.firestore.v1.RunQueryResponse]: {
+    read_time: {
+      seconds: 1721655328
+      nanos: 585255000
+    }
+  }
+}
+ref_index: 67
+40
+kind: RECV
+is_error: true
+ref_index: 67
+492
+kind: REQUEST
+method: "/google.firestore.v1.Firestore/Commit"
+message: {
+  [type.googleapis.com/google.firestore.v1.CommitRequest]: {
+    database: "projects/go-discovery-exp/databases/(default)"
+    transaction: "\x11\x11 \x8b\x8cX\xe5\x84\xdc\"Y\x00\xd4u\xc8͎\xeb=\xcc\x18ב\x02\x1fu\xed\xaaj\xc0\xf4zZ+\xb8\xb3E\xb9N\xc6\x14\xe2\xbdk\xac\xa8\x1bj\xd7\x0e\x97R<\x7fR\xd3\x0f\x84\xc3\x1d\x14\xb0\xf0\r<G\xf2I\xdf\xee*\xc2x1h.$\xa2X\x12dyY\x10\x95I\xb3w\x99\xdf\xcd\xcefy\xa1V\xe5n4?"
+  }
+}
+182
+kind: RESPONSE
+message: {
+  [type.googleapis.com/google.firestore.v1.CommitResponse]: {
+    commit_time: {
+      seconds: 1721655328
+      nanos: 585255000
+    }
+  }
+}
+ref_index: 71
diff --git a/internal/grpcrr/rr.go b/internal/grpcrr/rr.go
index c9ac391..7165274 100644
--- a/internal/grpcrr/rr.go
+++ b/internal/grpcrr/rr.go
@@ -76,6 +76,24 @@
 	return &RecordReplay{replayer: rep}, nil
 }
 
+// SetInitial provides data to be stored at the beginning of the file in record mode.
+// It panics in replay mode.
+func (r *RecordReplay) SetInitial(initial []byte) {
+	if r.recorder == nil {
+		panic("SetInitial called in replay mode")
+	}
+	r.recorder.SetInitial(initial)
+}
+
+// Initial returns the data stored with SetInitial.
+// It panics in record mode.
+func (r *RecordReplay) Initial() []byte {
+	if r.replayer == nil {
+		panic("Initial called in record mode")
+	}
+	return r.replayer.Initial()
+}
+
 // ClientOptions returns options to pass to a gRPC client
 // that accepts them.
 func (r *RecordReplay) ClientOptions() []option.ClientOption {