README.md
1# LevelDB Scopes Implementation Design
2
3This 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.
4
5See LevelDB Scopes general design doc [here](https://docs.google.com/document/d/16_igCI15Gfzb6UYqeuJTmJPrzEtawz6Y1tVOKNtYgiU/edit).
6
7# Status / Current State
8
9* Lock manager - Done
10* Scopes - Done
11* Blob / large value support - Future
12
13Things not covered in this README:
14
15* How iterators & scopes interact to ensure the iterator is operating on fresh data
16
17# Vocabulary
18
19**Scope**
20
21A 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.
22
23**Task**
24
25A 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 **log**s.
26
27**Undo Task**
28
29Undo 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`](scopes_metadata.proto). Undo tasks are only executed when a scope is reverted.
30
31**Cleanup Tasks**
32
33Cleanup 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).
34
35**Log**
36
37There 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.
38
39**Scope Number (scope#)**
40
41Each 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).
42
43**Sequence Number (seq#)**
44
45Every undo log entry has a unique sequence number within the scope. These should start at {max int} (using Fixed64) and decrement.
46
47**Commit Point**
48
49This signifies that a scope has been committed. The commit point for a scope is the absence of `locks` in the scope's metadata.
50
51**Key Range**
52
53Represents 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.
54
55**Lock**
56
57To prevent reading uncommitted data, IndexedDB 'locks' objects stores when there are (readwrite) transactions operating on them.
58
59## New LevelDB Table Data
60
61|Purpose|Key |Format|Value (protobufs)|
62|---|---|---|---|
63|Metadata|metadata|`prefix0`|`LevelDBScopesMetadata`|
64|Scope Metadata|scope-{scope#}|`prefix1{scope#}`|`LevelDBScopesScopeMetadata`|
65|Undo log operations|log-undo-{scope#}-{seq#}|`prefix20{scope#}{seq#}`|`LevelDBScopesUndoTask`|
66|Cleanup log operations|log-cleanup-{scope#}-{seq#}|`prefix21{scope#}{seq#}`|`LevelDBScopesCleanupTask`|
67
68
69### Key Format
70
71* Allow the 'user' of the scopes system to choose the key prefix (`prefix`).
72* Scope # is a varint
73* Sequence # is a big-endian Fixed64 (to support bytewise sorting)
74
75See [`leveldb_scopes_coding.h`](leveldb_scopes_coding.h) for the key encoding implementation.
76
77### Value Format
78
79All values are protobufs, see [`scopes_metadata.proto`](scopes_metadata.proto).
80
81# Operation Flows
82
83## Acquiring Locks
84**IndexedDB Sequence**
85
86* Input - lock ranges & types. The lock ranges should correspond to the key ranges that will be read from or written to. The type signifies if the lock range should be requested as exclusive or shared.
87* If any of the key ranges are currently locked, then wait until they are all free. This is the IDB transaction sequencing logic.
88* Output - a list of locks, one per requested lock range.
89
90## Creating & Using a Scope
91**IndexedDB Sequence**
92
93* Input - a list of locks for the scope. See [Acquiring Locks](#acquiring-locks) above
94* Create the scope
95 * Use the next available scope # (and increment the next scope #)
96* Enable operations on the scope
97* While the total size of changes is less than X Mb, buffer them in a write batch.
98 * If the scope is committed before reaching X Mb, then just commit the scope without generating an undo log.
99* If the size of the buffer write batch is > X Mb, or the user needs to 'read' in the range that was just written to, then the changes must be written to disk.
100 * For every operation, the scope must read the database and append the undo operation to the undo task log.
101 * See the [Undo Operation Generation](#undo-operations) section below
102* Deferred operations are written do the cleanup task log.
103* Output - a Scope
104
105## Committing a Scope
106**IndexedDB Sequence**
107
108* Input - a Scope
109* The scope is marked as 'committed' by writing the `LevelDBScopesScopeMetadata` (at `scope-{scope#}`) to remove the `lock` key ranges. This change is flushed to disk.
110* The Cleanup Sequence is signalled for cleaning up the committed scope #.
111* Output - Scope is committed, and lock is released.
112
113## Reverting a Scope
114**Revert Sequence**
115
116* Input - revert a given scope number.
117* Opens a cursor to `log-undo-{scope#}-0`
118 * Cursor should be at the first undo entry
119 * If the scope's commit point exists (in the scope's metadata, if the locks are empty) then error - reverting a committed scope is an invalid state in this design
120* Iterate through undo tasks, committing operations.
121* Update the Scope's `LevelDBScopesScopeMetadata` entry (at `scope-{scope#}`) by cleaning the `locks` and setting `ignore_cleanup_tasks = true`, and flush this change to disk.
122* The Cleanup Sequence is signalled for cleaning up the reverted scope #.
123* Output - Scope was successfully reverted, and lock released.
124
125## Startup & Recovery
126**IndexedDB Sequence**
127
128* Input - the database
129* Reads metadata (fail for unknown version)
130* Opens a cursor to scopes- & iterates to read in all scopes
131 * If the scope metadata (`LevelDBScopesScopeMetadata` at `scope-{scope#}`) has `locks`, then those are considered locked
132 * The maximum scope # is found and used to determine the next scope number (used in scope creation)
133* Requests locks from the lock system
134* Signals IndexedDB that it can start accepting operations (IndexedDB can now start running)
135* For every `LevelDBScopesScopeMetadata` that has no `locks`
136 * Kick off an [Undo Log Cleanup](#undo-log-cleanup) task to eventually clean this up.
137* For every `LevelDBScopesScopeMetadata` that has `locks`
138 * Kick off a [Reverting a Scope](#reverting-a-scope) task. This state indicates a shutdown while a revert was in progress.
139* Output - nothing, done
140
141## Undo Log Cleanup
142**Cleanup & Revert Sequence**
143
144* Input - scope #
145* Open the `scope-{scope#}` metadata
146 * If the commit point is not there (if the `locks` are not empty), then error.
147* If the 'ignore_cleanup_tasks' value is false, then
148 * Iterate through the `log-cleanup-{scope#}-` cleanup tasks and execute them (range deletes).
149* Delete both the undo tasks log and the cleanup task log
150* Delete the `scope-{scope#}` metadata
151* Output - nothing
152
153# Lock Manager
154
155The 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.
156
157### API Methods
158
159#### AcquireLocks
160
161Accepts 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.
162
163To keep the implementation simple, all required locks for a given scope or operation need to be acquired all at once.
164
165### Internal Data Structure
166
167The 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.
168
169# Undo Operations
170
171Undo 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.
172
173## Types
174
175* `Put(key, value)`
176* `Delete(key)`
177* `DeleteRange(key_range)`
178
179See `LevelDBScopesUndoTask` in the [`scopes_metadata.proto`](scopes_metadata.proto)
180
181## Generation
182
183### Normal Cases
184
185Note - all cases where "old_value" is used requires reading the current value from the database.
186
187**`Put(key, value)`**
188
189* `Delete(key)` if an old value doesn't exist,
190* `Put(key, old_value)` if an old value does exist, or
191* Nothing if the old value and new value matche
192
193**`Add(key, value)`**
194
195* Delete(key), trusting the client that there wasn't a value here before.
196
197**`Delete(key)`**
198
199* `Put(key, old_value)` if the old_value exists, or
200* Nothing if no old_value exists.
201
202**`DeleteRange(key_range)`**
203
204* `Put(key, old_value)` for every entry in that key range. This requires iterating the database using the key_range to find all entries.
205
206### Special Case - Empty Unique Key Range
207
208#### Creation - key range is empty initially
209
210If 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:
211
212`DeleteRange(key_range)`
213
214Examples 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.
215
216#### Deletion - key range will never be used again.
217
218This is done by creating a cleanup task (see `LevelDBScopesCleanupTask` in [`scopes_metadata.proto`](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.