[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: pristine store design

From: Julian Foad <julian.foad_at_wandisco.com>
Date: Mon, 15 Feb 2010 15:51:33 +0000

Neels J Hofmeyr wrote:
> taking stock of the current state of the pristine store API and finding
> design docs missing, I have created a "design paper" to clarify.

Excellent. This is very useful.

BTW, I am joining the WC-NG effort so I'm glad to jump in here, as it
looks like one of the easier places to start.

Are you intending to use the descriptions in this paper to write doc
strings for this pristine store API functions? We should.

I'm interspersing comments on the API with comments on your doc, but I
try to say which are which.

> If you could be so kind to glance over it and straighten out my picture, if
> necessary. Upon approval, I'll check it into notes/ so we can edit.
>
> Note, if my view is correct, this design text implies small changes to the
> current state of the API:
> - no need for _pristine_write()

Can I suggest that, instead, _install() and _get_temp_dir() should not
be exposed. _write() should accept NULL for the checksum parameter and,
in that case, calculate the checksum itself. The implementation could
(at least in that case) use _get_temp_dir() and _install() like your
pseudo-code for the use case "store". Even when the checksum is provided
it could do the same and then verify the provided checksum.

Then your use cases "store" and "new" and "fetch" would all use _write()
in simple ways.

However I think you are meaning to document the existing API first, so
we should perhaps keep these suggested changes separate.

> - need to add _pristine_forget()
> - change the _pristine_checkmode_t enum.
>
> Still missing completely: how to handle a "high-water mark", i.e. how to
> determine which pristines get forgotten first.
>
> Thanks!
> ~Neels
> plain text document attachment (pristine-store-design.txt)
> THE PRISTINE STORE
> ==================
>
> The pristine store is a local cache of complete content of files that are
> known to be in the repository. It is hashed by a checksum of that content
> (SHA1).
>
>
> SOME IMPLEMENTATION INSIGHTS
> ============================
>
> There is a PRISTINE table in the SQLite database with columns
> (checksum, md5_checksum, size, refcount)
>
> The pristine contents are stored in the local filesystem in a pristine file,
> which may or may not be compressed (opaquely hidden behind the pristines API).
> The goal is to be able to have a pristine store per working copy, per user as
> well as system-wide, and to configure each working copy as to which pristine
> store(s) it should use for reading/writing.
>
> There is a canonical way of getting a given CHECKSUM's pristine file name for
> a given working copy without contacting the WC database (static function
> get_pristine_fname()).

> When interacting with the pristine store, we want to, as appropriate, check
> for (combos of):
> db-presence - presence in the PRISTINE table with noted file size > 0
> file-presence - pristine file presence
> stat-match - PRISTINE table's size and mtime match file system
> checksum-match - validity of data in the file against the checksum
>
> file-presence is gotten for free from a successful stat-match (fstat),
> checksum-match (fopen) and unchecked read of the file (fopen).
>
> How fast we consider things:
> db-presence - very fast to moderately fast (in case of "empty db cache")
> file-presence - slow (fstat or fopen)
> stat-match - slow (fstat plus SQLite query)
> checksum-match - super slow (reading, checksumming)
>
>
> On the method of writing pristine files:
> In short: *ALWAYS* copy to pristine temp and checksum along with that, then
> 'mv' into place.
>
> To avoid incomplete pristines, we never want to have a write stream to a
> pristine file location. Instead, we write to a tempfile on the same file-
> system device as the pristine store, after which a filesystem 'mv' puts it
> into place and a row is stored in the database. Like that, a pristine file
> is either intact or doesn't exist (unless corrupted by alien ray guns).
>
> When fetching a new pristine from the repository, get a temporary-file
> location from the pristine API, receive&checksum to that file, install.
> Typically, we have already checked if the pristine is stored yet.
>
> When there is some new content (added/modified file in the working copy), a
> pristine with the same content may already exist "coincidentally" -- that
> may be common in certain use scenarios, but is generally less common.
> Discussing optimal ways in different situations:
> - New file is *not* a temporary file ('svn add'/'commit', we are not allowed
> to 'mv' the file away), and a pristine with the same checksum and content
> as this file does *not* exist yet: The file needs to be checksummed and
> copied to the pristine store.
> --> write to pristine-tempfile, checksum along the way, install.
> - New file is *not* a temporary file ('svn add'/'commit'), but a pristine
> with the same content already exists. To catch this case, we would need to
> checksum the file *before* copying to the tempfile and then don't bother to
> copy if a match is found. BUT the file could be changed in-between us
> checksumming in-place, not finding a match and then copying! We should
> copy to a tempfile first anyway.
> - New file *is* a tempfile (we may 'mv' it away) and happens to be on the
> same filesystem device as the pristine store. We could checksum in-place
> and call pristine_install() on the tempfile directly. *But* code, in this
> case, should already have chosen the pristine-store tempfile location to
> begin with.
> So, it does not make sense to optimize here.
> (Depending on hardware, copying across devices can be faster or slower
> than copying within the same device. Can't optimise on that.)
>
>
> On overwriting orphaned pristine files that have no database entry:
> "Maybe the user saved his favourite aunt's final poetic words in a file that
> has a name that is this checksum and which ended up in the pristine store
> accidentally ..."
> This is super highly unlikely, given that the file name would have to match
> the checksum. We don't really need to play safe.
> But, if we find a pristine file where the db didn't expect one, it may
> sometimes be faster to checksum that file and find it intact than to
> overwrite with data possibly received from a repository.
> But again, that implies that something must have gone wrong (interrupted at
> just the right time/bug/db corruption) and we don't need to optimise for
> that.
> So, when storing a pristine, we can simply `mv` over an existing checksum
> file in the pristine store, not bothering to even check if it exists.
>
>
>
> USE CASES
> =========
>
> Pseudocode implies args for reference to working copy, pool etc. as needed.
> pristine_* = svn_wc__db_pristine_*
> _usable = svn_wc__db_checkmode_usable, etc.
>
>
> Use case "new": "I have locally-created content which should be stored
> -------------- as a pristine."
> Another pristine with identical content may exist coincidentally, in which
> case we technically don't need to write the pristine at all. But, as discussed
> in "On the method to write pristine files" above, we should anyway copy the
> new content to a tempfile to make sure nothing changes it in-between us
> checksumming and copying. So, this is exactly the same as use case "store"!

I think the important distinction between your use cases "new" and
"store" is whether you have the checksum available a-priori. (Whether
the source is a file or a stream is not so important.)

> Use case "fetch": "I'm in one of the get_pristine_from_repos() places (9).
> ---------------- I want to get a pristine from the repository and store it."
> This will contact the repos to read a revision content. Even though the repos
> provides a checksum for the content, we need to anyway validate that checksum
> on our end.
> Getting the data from the repos, employ use case "store" below.
> (We don't need to bother to checksum our end before storing the pristine,
> checksumming is included in use case "store".)
>
>
>
> Use case "store": "I am going to receive data that should be stored
> ---------------- as a new pristine!"
> We are going to receive data which we will checksum (to validate, or even to
> determine the checksum in the first place), after which we want to place it in
> the pristine file. We want to write to a temporary file, which should be on
> the same file system as the pristine store, to ensure a fast mv into place
> once we are sure the file is complete and checksummed.
> We want to write the PRISTINE table row after the pristine file is in place.
> (The API should provide a temporary dir, callers can use e.g.
> svn_stream_open_unique() to get a temporary file inside it).
>
> pseudocode:
> pristine_get_tempdir(&tempdir) (1)
>
> svn_stream_open_unique(&tempstream, &tempfile_path, tempdir)
> tempstream = svn_stream_checksummed2(tempstream, &write_checksum)
> write to and close tempstream
>
> if a_priori_checksum && a_priori_checksum != write_checksum:
> bail: data corruption during copy
>
> if paranoid_beyond_recognition:
> pristine_check(&present, write_checksum, _usable)
> if present:
> pristine_read(&stream, write_checksum)
> read(&my_content, tempfile_path)
> compare(&same, my_content, stream)
> if !same:
> bail: hash collision o_O
>
> pristine_install(tempfile_path, checksum) (2)
>
> (1) Get a temporary folder on the same file system device as the pristine
> store used by the given working copy.
>
> (2) Take a temporary file (in the temp folder from (1)) and filesystem-'mv' it
> into the proper pristine file location, then create a database row in the
> PRISTINE table.
>
>
>
> Use case "need": "I want to use this pristine's content, definitely."
> ---------------
> pseudocode:
> pristine_check(&present, checksum, _usable) (3)
> if !present:
> get_pristine_from_repos(checksum, ra) (9)
> pristine_read(&stream, checksum) (6)
>
> (3) check for _usable:
> - db-presence
> - if the checksum is not present in the table, return that it is not
> present (don't check for file existence as well).
> - stat-match (includes file-presence)
> - if the checksum is present in the table but file is bad/not there,
> bail, asking user to 'svn cleanup --pristines' (or sth.)
>
> (9) See use case "fetch". After this, either the pristine file is ready for
> reading, or "fetch" has bailed already.
>
> (6) fopen()
>
>
>
> Use case "would use": "I'd use this pristine if it's here already,
> -------------------- if not I still have other options."
> pseudocode:
> pristine_check(&present, checksum, _usable) (3)
> if !present:
> pursue other options
> else:
> pristine_read(&stream, checksum) (6)
>
>
>
> Use case "could use": "I have more complex options, and I want to get a
> -------------------- *fast* count on how many of certain pristines I can
> expect to exist. Does this one show?"

That's not really a use case, now, is it? *Why* do I care whether the
store *might* have the pristine text I'm asking about?

What are the semantics of the answer?

  * "Yes" means it might be present
  * "No" means it definitely is not present

?

Note the comment in svn_wc__db_checkmode_t:

/* ### bah. this is bogus. we open the sqlite database "all the time",
   ### and don't worry about optimizing that. so: given the db is always
   ### open, then the following modes are overengineered, premature
   ### optimizations. ... will clean up in a future rev. */

API comment: I hope we could reduce the checking modes to just two: a
"normal" check which tells whether the store has a pristine copy (and if
it says it does, we assume it is usable!), and a "verify" which verifies
all the metadata including the checksum. These could (should, I think)
be two separate functions rather than modes of a single function.

> pseudocode:
> pristine_check(&present, checksum, _known) (4)
>
> (4) ### Depending on which turns out to be faster:
> Only check db-presence
> ### OR
> Only check file-presence
>
>
>
> Use case "routine check": "I want to do some effort to validate this pristine"
> ------------------------
> pseudocode:
> pristine_check(NULL, checksum, _valid) (5)
>
> (5) check for _valid:
> - stat-match (includes db-presence and file-presence)
> - checksum-match
> Bail if this checksum is in the db but the content is invalid/file is
> missing.
> If it is not known in the db in the first place, return *PRESENT as FALSE,
> but in this case we're not even interested (completely missing is also
> valid).
>
>
>
> Use case "repair": "I've seen this pristine is børken. Restore or remove!"
> -----------------
> pseudocode:
> pristine_repair(&present, checksum) (7)

Commenting on the API: The idea of having a separate "repair" API
function and use case sounds flawed - it just creates unnecessary work.
We should do something simpler such as having the _check(_valid) call
automatically delete any entry that is found to be invalid.

Commenting on this document giving examples to document the existing
API: OK.

> [if !present:
> get_pristine_from_repos(checksum, ra) (9)
> pristine_read(&stream, checksum) (6)
> ]
>
> (7) Iff the pristine file exists in the file system and the content matches
> the checksum, (re)write the PRISTINE table row with the checksum, mtime
> and size and return *PRESENT as TRUE.
> In all other cases, remove all of table row and file. We will fetch the
> pristine from the repos the next time it is needed. *PRESENT = FALSE.
>
>
>
> Use case "remove": "I have lowered or hit the watermark or failed to repair.
> ----------------- This pristine has to go."
> (or am moving pristines to another pristine store...)
> pseudocode:
> pristine_forget(checksum) (8)
>
> (8) Without bailing on non-existence, remove anything that exists about
> this checksum: PRISTINE table row, pristine file.
>
>
>
> API
> ===
> Above use cases result in these API calls:
>
> _usable, _known, _valid: enum values. (3),(4),(5)
>
> pristine_get_tempdir(&tempdir) (1)
> pristine_install(tempfile, checksum) (2)
> pristine_check(&present, checksum, _usable) (3)
> pristine_check(&present, checksum, _known) (4)
> pristine_check(NULL, checksum, _valid) (5)
> pristine_read(&stream, checksum) (6)
> pristine_repair(hash) (7)
> pristine_forget(hash) (8)
>
>
> CENTRAL PRISTINE STORES
> =======================
> ### TODO: How to configure (per WC and user), how to get write access for
> multiple users while safeguarding against malicious corruption, whether to
> have read-only pristine stores with a per-user writable store, whether to have
> a chain of pristine stores that get asked for presence of a pristine, how to
> record which working copies use which pristine store to get a valid refcount.

- Julian
Received on 2010-02-15 16:52:12 CET

This is an archived mail posted to the Subversion Dev mailing list.