gcp

GCP Design

This document describes how the storage implementation for running Tessera on Google Cloud is intended to work.

Overview

This design takes advantage of GCS for long term storage and low cost & complexity serving of read traffic, but leverages something more transactional for coordinating the cluster.

New entries flow in from the binary built with Tessera into transactional storage, where they're held temporarily to batch them up, and then assigned sequence numbers as each batch is flushed. This allows the Add API call to quickly return with durably assigned sequence numbers.

From there, an async process derives the entry bundles and Merkle tree structure from the sequenced batches, writes these to GCS for serving, before finally removing integrated bundles from the transactional storage.

Since entries are all sequenced by the time they're stored, and sequencing is done in "chunks", it's worth noting that all tree derivations are therefore idempotent.

Transactional storage

The transactional storage is implemented with Cloud Spanner, and uses a schema with the following tables:

Tessera

This table is used to identify the current schema version.

SeqCoord

A table with a single row which is used to keep track of the next assignable sequence number.

Seq

This holds batches of entries keyed by the sequence number assigned to the first entry in the batch.

IntCoord

This table is used to coordinate integration of sequenced batches in the Seq table.

PubCoord

This table is used to coordinate publication of new checkpoints, ensuring that checkpoints are not published more frequently than configured.

Life of a leaf

1. Leaves are submitted by the binary built using Tessera via a call the storage's Add func.
2. The storage library batches these entries up, and, after a configurable period of time has elapsed or the batch reaches a configurable size threshold, the batch is written to the Seq table which effectively assigns a sequence numbers to the entries using the following algorithm: In a transaction:
   1. selects next from SeqCoord with for update ← this blocks other FE from writing their pools, but only for a short duration.
   2. Inserts batch of entries into Seq with key SeqCoord.next
   3. Update SeqCoord with next+=len(batch)
3. Newly sequenced entries are periodically appended to the tree: In a transaction:
   1. select seq from IntCoord with for update ← this blocks other integrators from proceeding.
   2. Select one or more consecutive batches from Seq for update, starting at IntCoord.seq
   3. Write leaf bundles to GCS using batched entries
   4. Integrate in Merkle tree and write tiles to GCS
   5. Delete consumed batches from Seq
   6. Update IntCoord with seq+=num_entries_integrated and the latest rootHash
4. Checkpoints representing the latest state of the tree are published at the configured interval.

Dedup

An experimental implementation has been tested which uses Spanner to store the <identity_hash> --> sequence mapping. This works well using "slack" Spanner CPU available in the smallest possible footprint, and consequently is comparably cheap requiring only extra Spanner storage costs.

Alternatives considered

Other transactional storage systems are available on GCP, e.g. CloudSQL or AlloyDB. Experiments were run using CloudSQL (MySQL), AlloyDB, and Spanner.

Spanner worked out to be the cheapest while also removing much of the administrative overhead which would come from even a managed MySQL instance, and so was selected.

The experimental implementation was tested to around 1B entries of 1KB each at a write rate of 1500/s. This was done using the smallest possible Spanner alloc of 100 Processing Units.