sectionSpanner [14084886]

www.cs.princeton.edu/courses/archive/fall16/cos418/docs/P6-Spanner.pdf
Worldwide LTP, SQL semantics, horizontal scalability, availablity, transactional consistency
Parts
- Client
- Load balancer
- Zone - between 100 and a few thousand servers
  - Zone manager
  - Placement driver, responsible for automated data transfer between zones
- Location proxy
  - Uses the per zone location proxies to find spanservers for data
- Universe manager
  - For interactive debugging
- Spanserver - consists of tablets
- Colossus - distributed file system that stores tablet's state similar to B-tree format

1. Design

Spanner is deployed as "universes", and only a few are active at one time
Each one relies on TrueTime to provide strong external consistency and global serialization
Also performs automatic resharding based on data size and load
Universe manager and placement driver are both singletons, although there are shadow replicas that will take over
Each zone works like a cluster of bigtable servers, each spanserver has several tablets ranging from 100-1000
- (key:string, timestamp:int64) -> strings
paxos and TrueTime are used to cover time, and Colossus is used to store data
Each tablet stores metadata and logs for the state machines, and the paxos implementation supports time-based leaders with long-lived leaders (aka fastpaxos)
- Single leader fast paxos effectively function as raft
Concurrency is handled via a lock table
- Each server enforces concurrency control based on the long-lived paxos leader
- Paxos leaders have around 10s for their leases
Paxos group that has a participant leader that acts as the transaction manager, and the other replicas are participant followers.
For transactions that span multiple groups, a coordinator is elected
Note that we only lock for writes
bully algorithm is used for leader election

When a write is done, the lease vote is automatically extended, and leaders need to ask for a lease extension.
Notably, it waits out the uncertainty before proceeding with a commit
To serve reads, each replica in Spanner keeps track of the maximum timestap that it was up to date. When a read transaction comes in, it decides whether it's able to serve it
Commit protocol guaranteees that all nodes know the lower bound of a prepared transaction timestamp.
We have to assign a timestamp for a snapshot reads, and snapshot reads are only done on replicas that are up to date

Spanner has an additional layer of abstraction over the bag of key-value mappings in the form of a directory or bucket
- All adjacent keys that begin with the same prefix
- All the data in the same bucket shares the same replication settings
- Move frequently accessed buckets into the same paxos group or place a bucket geographically closer to its accessors
Spanner buckets differ from Bigtable ones because they don't need to be lexicographically contiguous
We can movedir buckets across Paxos groups, which then moves the data in the background. The metadata setting is then flipped in the background RCU style
We use a bucket to specify the geographical replication attributes and placements
- Two settings:
  - Total number and type of replicas
    - You can tune the amount of voting replicas and place them physically closer
    - Read only - can't vote, only allow for scaling reads
    - Witness - Vote for the leader and commit write transactions, but don't keep a copy of the data. Can't serve as read leaders
    - Read-write replicas - Does both, can be a leader
  - Geographic placement of replicas

With truetime, any two transactions T1 and T2,m if T2 begins to commit after T1 completes committing, then T2's timestamp is > T1's timestamp
Consistent timestamp allows easy snapshot isolation, since we can just read at a point in tiem
Liskov, Barbara. “Practical Usesof Synchronized Clocks Undistributed Systems,” n.d.

does not guarentee uptime, but real databases need maint anyways, so it is "essentially CA"
Since paxos is used, it opts for consistency over availability, as paxos is possible to livelock

For read transactions, we buffer them on the client side until commits.
Transactions writes are not visible to subsequent reads inside the same transaction
Uses wound-wait to prevent deadlocks
- Read request
- The lead replica acquires a lock
- Read to update to date data from the replicas
For read-only transactions
- within a single paxos groups: just send the read transaction to the group's leader
- if it's multiple paxos groups: then determine the $s_{read}$ value on the last timestamp by doing consensus with leaders
  - Or avoid the consensus round

Guarentees isolation and strong consistency
If participants in a 2PC are physically nearby, then it selects paxos groups closer
Leader who aren't coordinators gets access to write locks, and then also does prepare timestamps
Coordinator roles
- The coordinator bypasses the prepare step and gets locks for writes, and recieves inputs from all the group's leaders
- Commit transactions
  - Greater than or equal all prepare timestamps to satisfy the invariants of read-write transactions
  - Greater than TT.now().latest
  - Greater than the timestamps of all the transactions that the leader coordinator has assigned previously

Changing the schema in Spanner
1. A future timestamp is determined in the prepare phase
2. Consider that the t is the timestamp of a registered schema change transaction

Important thing to understand about spanner is TrueTime, by putting bounds on clock drift, you acn get transactions

Spanner was ultimately based off of F1, which had implemented quite a bit of this before
- Shute, Jeff, Radek Vingralek, Bart Samwel, Ben Handy, Chad Whipkey, Eric Rollins, Mircea Oancea, et al. “F1: A Distributed SQL Database That Scales.” Proceedings of the VLDB Endowment 6, no. 11 (August 27, 2013): 1068–79. doi.org/10.14778/2536222.2536232.
- interesting secret sauce was about how they retry requests
- F1 previous had to fetch the entire protobuf value to do a partial decode
- Spanner wasn't originally SQL, but they decided to do quite a bit of pushdown as a result
Becoming a SQL system (Bacon, David F., Nathan Bales, Nico Bruno, Brian F. Cooper, Adam Dickinson, Andrew Fikes, Campbell Fraser, et al. “Spanner: Becoming a SQL System.” In Proceedings of the 2017 ACM International Conference on Management of Data, 331–43. Chicago Illinois USA: ACM, 2017. doi.org/10.1145/3035918.3056103.)
- range extraction and pushdown
  - static decomposition of SQL down into scan, filter, and apply primitives
- ressi
- shard pruning
  - location hints about the location of a particular shard
- restart token
  - not much mentioned but this seems to be the secret sauce here