1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
|
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html
PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>Datastore redesign</title>
<meta name="content-type" content="text/html; charset=utf-8" />
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<meta name="author" content="Sascha Silbe" />
</head>
<body>
<h2>TODO</h2>
<ul>
<li>Is the asynchronous API design useful enough to warrant more complex implementation?
<ul>
<li>DBus operations can be run asynchronously so UI responsiveness shouldn't be an issue</li>
<li>For save() calls activity needs to wait for result (containing new <code>version_id</code>)
before it can invoke save() again for the same object which can take quite some time if
save() is sync - especially if other activities are saving at the same time.</li>
</ul>
</li>
<li>examine / define API call interactions, esp. in case we switch to fully synchronous design</li>
<li>do we want an optimized way to determine (only) the branch HEADs of a given <code>tree_id</code>?</li>
<li>example activity <-> data store interaction</li>
<li>Tomeu: What about having a separate call that returns synchronously a new <code>tree_id</code> and/or <code>version_id?</code>
<ul>
<li>need to handle missing intermediate versions in that case (parent_id set to a never-committed version)</li>
</ul>
</li>
<li>cross-<code>tree_id</code> duplicate detection/optimization</li>
</ul>
<h2>(A)synchronicity of API calls</h2>
<ul>
<li>metadata/data write requests:
<ul>
<li>synchronous submit with ACID guarantee</li>
<li>actual commit async, with callback on completion</li>
</ul>
</li>
<li>data read requests:
<ul>
<li>synchronous check for existence</li>
<li>data provided async, with callback on completion</li>
</ul>
</li>
<li>metadata read requests:
<ul>
<li>fully synchronous</li>
</ul>
</li>
<li>VCS operations won't happen in parallel (single-threaded) so we don't need locking for them
<ul>
<li>they're usually IO-bound anyway</li>
</ul>
</li>
</ul>
<h2>Notes</h2>
<ul>
<li>using the term "ACID" for simplicity even when we need only parts of it (e.g. no isolation - there's only a single datastore)</li>
<li>using symlink instead of hardlink for "incoming" queue since we want to support directory trees, not just files</li>
<li>since we need to manage the version numbers ourselves (so we can do the actual commit in the background) the VCS doesn't strictly need to support branches</li>
<li>since an index rebuild can take a lot of time we need to provide UI feedback while doing that</li>
<li>detecting identical files across objects isn't as important since duplicates are mostly expected to occur as versions
of the same object</li>
<li>For technical reasons callbacks to the activity are implemented as DBus signals. The Python API
needs to set up a DBus signal handler using string matching.</li>
</ul>
<h2>Requirements</h2>
<ul>
<li>data should be provided on the same FS as the Journal (for hardlinking)</li>
<li>activities must not modify the entry they submit to data store before it has been commited (and the activity notified about that)
<ul>
<li>Python API may copy file if activity indicates it doesn't fulfill this requirement</li>
</ul>
</li>
<li>activities must not modify the entry they received from datastore
<ul>
<li>Python API may copy file if activity indicates it doesn't fulfill this requirement</li>
</ul>
</li>
<li>activities must make the entry readable by the data store user
<ul>
<li>It might be possible to set up <a href="http://wiki.laptop.org/go/Rainbow">Rainbow</a> in a way that datastore
is running isolated as well and shared directories with appropriate permissions are created so activity
and datastore can share directories without having to change ownership in any way.</li>
</ul>
</li>
<li>activities should not submit new entries while the previously submitted one hasn't been fully committed yet</li>
<li>VCS backend must not modify files that have been provided as input (for commit) or checked out => link-breaking
<ul>
<li>if the VCS doesn't support this, the backend needs to implement it by copying</li>
</ul>
</li>
<li>VCS backend must be crash-proof, i.e. ACID
<ul>
<li>if the VCS doesn't support this, the backend needs to implement it, e.g. by copying/hardlinking and calling sync()</li>
</ul>
</li>
</ul>
<h2>ID / metadata definitions</h2>
Used by datastore:
<dl>
<dt><code>tree_id</code></dt>
<dd>Identifies the ancestry graph (i.e. all versions) of an entry. Should be treated as an opaque string by API
consumers. Potentially unique across systems (UUID).</dd>
<dt><code>version_id</code></dt>
<dd>Identifies a specific version of an object. Should be treated as an opaque string by API consumers.
Usually combined with <code>tree_id</code> but unique on its own, potentially across systems (UUID).</dd>
<dt><code>parent_id</code></dt>
<dd>The <code>version_id</code> of the parent of an object, set by datastore. Empty for the root of the
ancestry graph.</dd>
<dt><code>ctime</code></dt>
<dd>Unix timestamp of creation time of an entry, set by datastore. Not updated on changes of the version-specific
metadata.</dd>
</dl>
Not used by datastore:
<dl>
<dt><code>bundle_id</code></dt>
<dd><a href="http://wiki.laptop.org/go/Activity_bundles#.info_file_format"><code>bundle_id</code></a> of the
Activity template associated with the entry. Only set for session continuation objects. Will be used
for resuming the session.</dd>
<dt><code>entry_type</code></dt>
<dd>Valid values are <code>action</code> and <code>object</code>. Intended for use by Journal for implementing
action-oriented view.</dd>
<dt><code>creator</code></dt>
<dd><code>bundle_id</code> of the Activity template the entry has been created by (e.g.
<code>org.laptop.WebActivity</code> for downloaded files).</dd>
<dt><code>mime_type</code></dt>
<dd>MIME type of data, used for determining compatible Activity templates.</dd>
</dl>
<h2>Workflows</h2>
<h3>data+metadata creates / updates</h3>
<ul>
<li>activity saves data to a disk, ensuring it has been committed (sync) and proper access rights for data store</li>
<li>activity calls datastore DBus API to submit new/updated entry</li>
<li>data store allocates tree_id if not given</li>
<li>data store allocates (new) version number</li>
<li>data store submits metadata to database backend as "new" (with version number, ACID update)</li>
<li>data store symlinks (=atomic) data to (on-disk) queue "incoming" with version number in filename</li>
<li>data store adds metadata to queue in-memory queue "index-add"</li>
<li>data store returns on API call with allocated version number</li>
<li>VCS backend prepares commit (e.g. git checkout)</li>
<li>VCS backend hardlinks data into working copy</li>
<li>VCS backend commits data with allocated version number in commit message</li>
<li>data store records "finished" state in database backend</li>
<li>if activity requested it, data store deletes the submitted copy of the data</li>
<li>data store removes symlink in "incoming" queue</li>
<li>data store invokes callback to activity</li>
</ul>
<h3>metadata changes (to existing versions)</h3>
<ul>
<li>activity calls datastore DBus API to submit updated metadata</li>
<li>data store submits metadata to database backend (ACID update)</li>
<li>data store returns on API call</li>
</ul>
<h3>crash recovery</h3>
<ul>
<li>data store checks database for "new" entries that have no corresponding symlink in the "incoming" queue
<ul>
<li>for each such entry it asks the VCS backend for recovery and whether the commit has been finished
<ul>
<li>if commit exists, mark entry as "finished"</li>
<li>otherwise delete entry</li>
</ul>
</li>
</ul>
</li>
<li>index backend checks for corruption
<ul>
<li>in case of corruption a full index rebuild takes place</li>
</ul>
</li>
<li>data store starts accepting regular API calls</li>
<li>data store checks database for "deleted" entries. For each entry:
<ul>
<li>VCS backend deletes corresponding repository (if it still exists)</li>
<li>index backend removes corresponding entry (if it still exists)</li>
<li>database backend removes entry</li>
</ul>
</li>
<li>data store checks "incoming" queue for entries (none found => no recovery necessary)</li>
<li>VCS backend performs global integrity check / recovery (none for git)</li>
<li>for each entry in the "incoming" queue:
<ul>
<li>VCS backend performs integrity check / recovery for given entry</li>
<li>VCS backend checks whether entry has already been committed
<ul>
<li>if not: VCS backend performs commit like above</li>
</ul>
</li>
<li>index backend adds entry (if it does not yet exist)</li>
<li>data store removes symlink in "incoming" queue</li>
</ul>
</li>
</ul>
<h3>checkout</h3>
<ul>
<li>activity / shell calls datastore DBus API to request entry</li>
<li>data store checks "incoming" queue for entry
<ul>
<li>if it exists we return on API call but block waiting for the commit to finish before checkout it out</li>
</ul>
</li>
<li>database backend checks entry for validity ("deleted", existence)</li>
<li>data store returns on API call</li>
<li>VCS backend checks out entry</li>
<li>data store hardlinks entry into target directory
<ul>
<li>files read-only and directories read-write for activity (=> ensure link-breaking)</li>
</ul>
</li>
<li>data store invokes callback to activity</li>
</ul>
<h3>search</h3>
<ul>
<li>data store checks "index-add" queue for matching entries</li>
<li>data store checks index backend for matching entries (eliminating dupes)</li>
<li>database backend retrieves metadata for matching entries and checks for validity (not "deleted", does still exist)</li>
<li>data store returns all matches</li>
</ul>
<h3>delete</h3>
<ul>
<li>database backend marks entry as "deleted"</li>
<li>data store returns on API call</li>
<li>data store removes entry from "index-add" queue (if it exists)</li>
<li>index backend removes entry</li>
<li>VCS backend removes corresponding repository</li>
<li>database backend removes entry</li>
<li>data store invokes callback to activity</li>
</ul>
<h2>API</h2>
<h3>Current datastore DBus API</h3>
<h4>Functions and signals</h4>
<dl>
<dt><code>create(properties, filename, transfer_ownership)</code></dt>
<dd>
Create new journal object with metadata given in <code>properties</code>, returns <code>uid</code> / <code>object_id</code>.
If <code>transfer_ownership</code> is False the data store will make a copy of the file. Metadata storage and index update
is synchronous and while file storage and optimizer run in a separate thread, the API call actually only returns
after everything is done (including emitting a <code>Created(uid)</code> signal) and thus is fully synchronous.
Returns <code>uid</code> (<code>object_id</code>).
</dd>
<dt><code>update(uid, properties, filename, transfer_ownership)</code></dt>
<dd>Submit new version (currently replacing the old version) and/or new metadata of the object identified
by <code>uid</code> (<code>object_id</code>). Similar to <code>create()</code> Metadata storage and index update is synchronous,
file storage and optimizer run in a separate thread, but the API call only returns after everything is done, including
emitting an <code>Updated(uid)</code> signal. Doesn't return anything.
</dd>
<dt><code>delete(uid)</code></dt>
<dd>Remove given object from data store. Fully synchronous. Doesn't return anything, emits signal <code>Deleted(uid)</code>.</dd>
<dt><code>get_properties(uid)</code></dt>
<dd>Returns (full) metadata for given object. Fully synchronous.</dd>
<dt><code>get_filename(uid)</code></dt>
<dd>Hardlinks or symlinks the given object into a global directory and returns the filename. Fully synchronous.</dd>
<dt><code>find(query, properties)</code></dt>
<dd>Finds entries matching <code>query</code> in the index, returning the values of the requested <code>properties</code>.
If the index is unavailable, <em>all</em> entries are returned (but taking <code>limit</code> and <code>offset</code>
into account). <code>query</code> is a dictionary and may contain <code>propertyname=value</code> mappings
(that are directly matched against metadata - only <code>timestamp</code> (with a range), <code>uid</code>,
<code>activity</code>, <code>activity_id</code>, <code>keep</code> and <code>mime_type</code> are supported so far)
in addition to values for <code>limit</code> (max. number of results), <code>offset</code> (skip given number of results) and
<code>query</code> ("full-text" search in all properties). Returns estimated number of matching entries (not affected by
<code>limit</code> and <code>offset</code>) and requested metadata for matching entries.
<p>Journal passes <code>sort=-mtime</code> in query; datastore currently ignores it (but sorts by timestamp anyway).</p></dd>
<dt><code>get_uniquevaluesfor(propertyname, query)</code></dt>
<dd>Supposedly would returns a list of all (unique) values associated with given property (metadata) name for all
datastore entries matching query. Only supports <code>propertyname='activity'</code> and
<code>query=None</code>, so a list of all activities (<code>activity</code> / <code>bundle_id</code>) is returned.</dd>
<dt><code>mount(uri, options)</code></dt>
<dd>Compat only. Noop, returns ''.</dd>
<dt><code>unmount(mount_point_id)</code></dt>
<dd>Compat only. Noop, doesn't return anything.</dd>
<dt><code>mounts()</code></dt>
<dd>Compat only. Noop, returns [{'id': 1}].</dd>
<dt><code>Stopped()</code></dt>
<dd>Signal emitted after datastore has been shut down.</dd>
</dl>
<h3>Proposed datastore DBus API</h3>
<h4>Functions and signals</h4>
<dl>
<dt><code>save(tree_id, parent_id, metadata, path, delete_after)</code></dt>
<dd>
<p>
Submit new version (data and/or metadata) of the given object, returns <code>tree_id</code>, <code>child_id</code>.
<code>parent_id</code> and <code>child_id</code> are the <code>version_id</code> of the predecessor resp. the
to-be-saved entry.
</p>
<p>
If <code>tree_id</code> is empty <code>parent_id</code> must be empty as well and both will be newly allocated
(equivalent to create() in previous API). If only <code>parent_id</code> is empty there must not be any entry
with the same <code>tree_id</code> already in datastore.
</p>
<p>
Actual file storage and index update happen asynchronously, emitting the
signal <code>Saved(tree_id, parent_id, child_id)</code> on completion.
</p>
<p>
If <code>path</code> is non-empty it designates a file or directory containing the data and the
parent must contain of the same type (file / directory; not metadata-only), if a parent exists at all.
If <code>path</code> is empty and the parent contained data then a metadata-only update is performed,
reusing the data of the parent. If both <code>parent_id</code> and <code>path</code> are empty a
metadata-only entry is created.
</p>
<p>
If <code>delete_after</code> is True the contents of <code>path</code> are deleted
after they have been committed, but before sending the signal.
</p>
</dd>
<dt><code>change_metadata(tree_id, version_id, metadata)</code></dt>
<dd>Changes the (unversioned/version-specific) metadata of the given object to match <code>metadata</code>.
Fully synchronous, no return value.
</dd>
<dt><code>delete(tree_id)</code></dt>
<dd>Remove (all versions of) given object from data store. Fully synchronous. Doesn't return anything, emits
signal <code>Deleted(tree_id)</code>.</dd>
<dt><code>get_data(tree_id, version_id)</code></dt>
<dd>Hardlinks the given object into a global directory, making it readable (directories also
writable) to the caller. Returns the path after checking the entry for validity; actual data is written
asynchronously.
Emits signal <code>GotData(sender, tree_id, version_id, path)</code> where <code>sender</code> is the bus name of
the sender.
</dd>
<dt><code>find(query, options)</code></dt>
<dd>Finds entries matching <code>query</code> and returns output according to <code>options</code>,
including the number of matches (unaffected by <code>limit</code>) and the
<code>tree_id</code> / <code>version_id</code> of each entry.
<p>
<code>query</code> is a dictionary with metadata names as keys and
either basic types (exact/wildcard match), 2-tuples (range) or a list (multiple exact/wildcard matches)
as values. Prefixing a key name with '!'
inverts the sense of matching, OPTIONAL: prefixing it with '*' enables regular expression search (slow).
An empty dictionary matches everything. Arbitrary key names are allowed, but speed
may vary (i.e. not everything is indexed).
</p><p>
<code>options</code> is a dictionary which may contain values for the following keys:
<dl>
<dt><code>metadata</code></dt>
<dd>gives a list of metadata names that should be returned for each entry;
default is everything</dd>
<dt><code>all_versions</code></dt>
<dd>if True returns all matching versions of an object instead of only the latest one</dd>
<dt><code>sort</code></dt>
<dd>sort by given metadata name (does not need to be listed in <code>metadata</code>);
prefix '+' for ascending order, prefix '-' for descending order; default is
undefined, potentially by relevance</dd>
<dt><code>limit</code></dt>
<dd>only return the given number of results (starting at first match in sort order,
subject to <code>offset</code></dd>
<dt><code>offset</code></dt>
<dd>skip the given number of results</dd>
</dl>
</p>
</dd>
<dt><code>textsearch(querystring, query, options)</code></dt>
<dd>Preliminary API call for IR search using Xapian. Likely to be replaced for next version.
<code>querystring</code> is passed to Xapians query parser; <code>query</code> and <code>options</code>
are interpreted like for <code>find()</code>. Returns the same format as <code>find()</code>.
</dd>
<dt><code>find_unique_values(query, metadata_name)</code></dt>
<dd>Similar <code>find(...)</code>, but returns the set of unique values for the requested
metadata name.
</dd>
<dt><code>check_ready()</code></dt>
<dd>Returns True if datastore is ready for processing (regular) API calls. False during startup / recovery.
</dd>
<dt><code>Ready()</code></dt>
<dd>Signal emitted after datastore is ready for processing API calls.</dd>
<dt><code>Stopped()</code></dt>
<dd>Signal emitted after datastore has been shut down.</dd>
</dl>
<h4>Exceptions</h4>
<dl>
<dt>sugar.datastore.NoSpaceLeftError</dt>
<dd>
There's not enough space left on disk to safely store data and/or metadata.
Operation aborted, everything still at the previous state.
</dd>
<dt>sugar.datastore.InvalidArgumentError</dt>
<dd>
One or several of the passed parameters (or the combination thereof) were invalid.
See formatted string for details. This should only happen if the caller is buggy.
</dd>
<dt>sugar.datastore.CorruptionError</dt>
<dd>
The internal data structures of datastore or one of its backends are corrupted. Should
only happen in case of hardware defects or OS bugs.
</dd>
<dt>sugar.datastore.BusyError</dt>
<dd>
Datastore is busy recovering from a crash. Please wait for <code>Ready()</code> before
starting to issue any API call (except <code>check_ready()</code>).
</dd>
</dl>
</body>
</html>
|
