Snapshot

A snapshot captures a point-in-time view of the DB at the time it's created. Snapshots do not persist across DB restarts.

We can associate rocksdb snapshots with user-specified timestamps, e.g. HLC. Since a snapshot is a volatile object representing a sequence number, timestamped snapshots establish an explicit bi-directional mapping between sequence numbers and timestamps. This is helpful because it allows applications to perform consistent reads on multiple rocksdb snapshots each of which is taken from a different RocksDB instance as long as the snapshots have the same timestamp. This is not possible in the past, because original snapshots/sequence numbers from different RocksDB instances are not comparable/related. Currently, this functionality is exposed to the layer of rocksdb transactions.

Applications can take a timestamped snapshot with T when all writes that correspond to timestamps <= T have been acknowledged by RocksDB. Applications also need to ensure that any two timestamped snapshots should satisfy the following:

snapshot1.seq <= snapshot2.seq iff. snapshot1.ts <= snapshot2.ts

API Usage

Snapshot allows applications to perform point-in-time read. Applications can read from a snapshot by setting ReadOptions::snapshot.

// General APIs
//
// Create a snapshot. Caller is responsible for releasing the returned snapshot.
const Snapshot* DB::GetSnapshot();

// When finished, release resources associated with the snapshot.
void DB::ReleaseSnapshot(const Snapshot* snapshot);

// Timestamped snapshot APIs
// Commit a transaction and create a snapshot with timestamp ts. The
// created snapshot includes the updates made by the transaction.
Status Transaction::CommitAndTryCreateSnapshot(
    std::shared_ptr<TransactionNotifier> notifier,
    TxnTimestamp ts,
    std::shared_ptr<const Snapshot>* ret);

std::pair<Status, std::shared_ptr<const Snapshot>>
TransactionDB::CreateTimestampedSnapshot(TxnTimestamp ts);

// Return the timestamped snapshot correponding to given timestamp. If ts is
// kMaxTxnTimestamp, then we return the latest timestamped snapshot if present.
// Othersise, we return the snapshot whose timestamp is equal to `ts`. If no
// such snapshot exists, then we return null.
std::shared_ptr<const Snapshot> TransactionDB::GetTimestampedSnapshot(TxnTimestamp ts) const;

// Return the latest timestamped snapshot if present.
std::shared_ptr<const Snapshot> 
TransactionDB::GetLatestTimestampedSnapshot() const;

Status TransactionDB::GetAllTimestampedSnapshots(
    std::vector<std::shared_ptr<const Snapshot>>& snapshots) const;

// Return timestamped snapshots whose timestamps fall in [ts_lb, ts_ub) and store them in `snapshots`.
Status TransactionDB::GetTimestampedSnapshots(
    TxnTimestamp ts_lb,
    TxnTimestamp ts_ub,
    std::vector<std::shared_ptr<const Snapshot>>& snapshots) const;

// Release timestamped snapshots whose timestamps < ts
void TransactionDB::ReleaseTimestampedSnapshotsOlderThan(TxnTimestamp ts);

Implementation

Flush/compaction

Representation

A snapshot is represented by a small object of SnapshotImpl class. It holds only a few primitive fields, like the seqnum at which the snapshot was taken.

Snapshots are stored in a linked list owned by DBImpl. One benefit is we can allocate the list node before acquiring the DB mutex. Then while holding the mutex, we only need to update list pointers. Additionally, ReleaseSnapshot() can be called on the snapshots in an arbitrary order. With linked list, we can remove a node from the middle without shifting.

Scalability

The main downside of linked list is it cannot be binary searched despite its ordering. During flush/compaction, we have to scan the snapshot list when we need to find out the earliest snapshot to which a key is visible. When there are many snapshots, this scan can significantly slow down flush/compaction to the point of causing write stalls. We've noticed problems when snapshot count is in the hundreds of thousands. To address this limitation, we allocate a binary-searchable data structure, e.g. a vector and copy the sequence numbers of all alive snapshots for each flush/compaction job.