This document is the implementation plan and design for LevelDB Scopes. It serves to both document the current state and the future plans for implementing LevelDB Scopes.
See LevelDB Scopes general design doc here.
Things not covered in this README:
Scope
A scope encompasses a group of changes that can be reverted. It is basically synonymous with a transaction, and would be used for readwrite and versionchange transactions in LevelDB. The scope has a defined list of key ranges where the changes can occur. It operates by keeping an undo task log, which is either discarded on commit, or replayed on revert. It also keeps a cleanup task log for specialty operations to happen during log cleanup.
Task
A task is something that is executed after a scope has been committed. There are two types of tasks (undo/revert tasks and cleanup tasks), and they are stored in the separate logs.
Undo Task
Undo tasks are used to revert a scope (that is, undo the changes that were written by the scope). An undo task is a single operation that is used to undo one or more of these changes. See the LevelDBScopesUndoTask in scopes_metadata.proto
. Undo tasks are only executed when a scope is reverted.
Cleanup Tasks
Cleanup tasks are optionally executed when a scopes is cleaned up. They consist of deferred deletions (range deletions that the user doesn't need to happen right away).
Log
There are two task logs in a scope, the undo task log
and the cleanup task log
. They each have a unique key prefix so they can be iterated easily.
Scope Number (scope#)
Each scope has an identifier unique to the backing store that is auto-incrementing. During recovery, it is set to the minimum unused scope (see more in the recovery section).
Sequence Number (seq#)
Every undo log entry has a unique sequence number within the scope. These should start at {max int} (using Fixed64) and decrement.
Commit Point
This signifies that a scope has been committed. The commit point for a scope is the absence of locks
in the scope's metadata.
Key Range
Represents a range of LevelDB keys. Every operation has a key or a key range associated with it. Sometimes key ranges are expected to be re-used or modified again by subsequent operations, and sometimes key ranges are known to be never used again.
Lock
To prevent reading uncommitted data, IndexedDB ‘locks’ objects stores when there are (readwrite) transactions operating on them.
Purpose | Key | Format | Value (protobufs) |
---|---|---|---|
Metadata | metadata | prefix0 | LevelDBScopesMetadata |
Scope Metadata | scope-{scope#} | prefix1{scope#} | LevelDBScopesScopeMetadata |
Undo log operations | log-undo-{scope#}-{seq#} | prefix20{scope#}{seq#} | LevelDBScopesUndoTask |
Cleanup log operations | log-cleanup-{scope#}-{seq#} | prefix21{scope#}{seq#} | LevelDBScopesCleanupTask |
prefix
).See leveldb_scopes_coding.h
for the key encoding implementation.
All values are protobufs, see scopes_metadata.proto
.
IndexedDB Sequence
IndexedDB Sequence
IndexedDB Sequence
LevelDBScopesScopeMetadata
(at scope-{scope#}
) to remove the lock
key ranges. This change is flushed to disk.Revert Sequence
log-undo-{scope#}-0
LevelDBScopesScopeMetadata
entry (at scope-{scope#}
) by cleaning the locks
and setting ignore_cleanup_tasks = true
, and flush this change to disk.IndexedDB Sequence
LevelDBScopesScopeMetadata
at scope-{scope#}
) has locks
, then those are considered lockedLevelDBScopesScopeMetadata
that has no locks
LevelDBScopesScopeMetadata
that has locks
Cleanup & Revert Sequence
scope-{scope#}
metadatalocks
are not empty), then error.log-cleanup-{scope#}-
cleanup tasks and execute them (range deletes).scope-{scope#}
metadataThe scopes feature needs a fairly generic lock manager. This lock manager needs two levels, because versionchange transactions need to lock a whole database, where other transactions will lock smaller ranges within the level one range.
Accepts a list of lock request and a callback which is given a moveable-only lock object, which releases its lock on destruction. Each lock request consists of a lock type (shared or exclusive), a level number, and a key range. The levels are totally independent from the perspective of the lock manager.
To keep the implementation simple, all required locks for a given scope or operation need to be acquired all at once.
The lock manager basically holds ranges, and needs to know if a new range intersects any old ranges. A good data structure for this is an Interval Tree.
Undo operations are generated when the undo tasks are required. Note that for under a certain scope ‘size’ (where the buffer write batch is small enough), no undo operations are generated.
Put(key, value)
Delete(key)
DeleteRange(key_range)
See LevelDBScopesUndoTask
in the scopes_metadata.proto
Note - all cases where “old_value” is used requires reading the current value from the database.
Put(key, value)
Delete(key)
if an old value doesn't exist,Put(key, old_value)
if an old value does exist, orAdd(key, value)
Delete(key)
Put(key, old_value)
if the old_value exists, orDeleteRange(key_range)
Put(key, old_value)
for every entry in that key range. This requires iterating the database using the key_range to find all entries.If the values being created are in a key range that is initially empty (we trust the API caller here - there is no verification), and if the key range will never be reused if it is reverted, then the undo log can consist of a single:
DeleteRange(key_range)
Examples of this are creating new databases or indexes in a versionchange transaction. The scopes system can check to make sure it's range is empty before doing operations in debug builds.
This is done by creating a cleanup task (see LevelDBScopesCleanupTask
in scopes_metadata.proto
). When the scope is cleaned up, these operations are executed. This allows a user to defer the deletion to a later time and a different thread.