You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Neels J Hofmeyr <ne...@elego.de> on 2010/02/15 13:45:46 UTC

pristine store design

Hi all,

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

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()
- 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

Re: pristine store design

Posted by Julian Foad <ju...@btopenworld.com>.
Stefan Sperling wrote:
> On Mon, Mar 01, 2010 at 06:14:33PM +0000, Julian Foad wrote:
> > On Thu, 2010-02-18, Neels J Hofmeyr wrote:
> > > The one thing left now is:
> > > > Can someone explain a motivation for even creating a database row before
> > > > the pristine file is moved into place in the pristine store? I currently
> > > > don't see why it can't be way simpler.
> > [...]
> 
> > "Simultaneous or multi-threaded clients" would be my first reaction to
> > that particular question.
> 
> If two threads write to the same pristine, the content written
> will be the same (except in case of a SHA1 checksum collision
> which we choose to ignore). So, thread 1 writes to a tempfile, and
> when it's done, it moves the tempfile into place. The new filename
> of the tempfile being based on the SHA1 sum of the written content.
> If thread 2 does the same concurrently, the end result will be the
> same -- the file will only exist once at its SHA1 sum name.

Yup, the file will be OK.

I didn't have any specific failure mode in mind, and I can't think of
one now.  If there is some reason, then we can tackle it when we find
the reason.

+1 on KISS.

> Of course, writing the same pristine more than once is redundant.
> So we could try to optmize this redundancy away. But I don't think
> it is worth it. [...]

Agreed.

- Julian



RE: pristine store design

Posted by Julian Foad <ju...@wandisco.com>.
On Wed, 2010-03-03, Bert Huijben wrote:
> 
> > -----Original Message-----
> > From: Stefan Sperling [mailto:stsp@elego.de]
> > Sent: maandag 1 maart 2010 19:32
> > To: Julian Foad
> > Cc: Neels J Hofmeyr; Greg Stein; dev@subversion.apache.org; Bert Huijben
> > Subject: Re: pristine store design
> > 
> > On Mon, Mar 01, 2010 at 06:14:33PM +0000, Julian Foad wrote:
> > > On Thu, 2010-02-18, Neels J Hofmeyr wrote:
> > > > The one thing left now is:
> > > > > Can someone explain a motivation for even creating a database row
> > before
> > > > > the pristine file is moved into place in the pristine store? I
> currently
> > > > > don't see why it can't be way simpler.
> > > [...]
> > 
> > > "Simultaneous or multi-threaded clients" would be my first reaction to
> > > that particular question.
> > 
> > If two threads write to the same pristine, the content written
> > will be the same (except in case of a SHA1 checksum collision
> > which we choose to ignore). So, thread 1 writes to a tempfile, and
> > when it's done, it moves the tempfile into place. The new filename
> > of the tempfile being based on the SHA1 sum of the written content.
> > If thread 2 does the same concurrently, the end result will be the
> > same -- the file will only exist once at its SHA1 sum name.
> 
> On posix, when using svn_io_rename_file() this would be true and this would
> be pretty safe.
> 
> On Windows you get an access denied (bad) and a 15 second delay retrying the
> move (worse).

That's what svn_io_rename_file() does, but for cases like this we should
(write and) use a different rename function that expects no file to
exist at the target path, and that returns immediately if there is a
problem.

- Julian


> So we should try to avoid overwriting existing files here. (I would guess
> that tools like rsync and incremental backusp also like that we don't change
> the date of these files)
> 
> > Of course, writing the same pristine more than once is redundant.
> > So we could try to optmize this redundancy away. But I don't think
> > it is worth it. If you're only talking about threads within a single
> 
> See ^^^.
> 
> 	Bert
> 



Re: pristine store design

Posted by Ivan Zhakov <iv...@visualsvn.com>.
On Wed, Mar 3, 2010 at 5:34 PM, Bert Huijben <be...@qqmail.nl> wrote:
>> > On Windows you get an access denied (bad) and a 15 second delay retrying
>> the
>> > move (worse).
>> >
>> > So we should try to avoid overwriting existing files here. (I would guess
>> > that tools like rsync and incremental backusp also like that we don't change
>> > the date of these files)
>> >
>> That's not correct. Windows API function MoveFileEx has option to
>> overwrite destination file [1]. apr_file_rename() uses MoveFileEx with
>> MOVEFILE_REPLACE_EXISTING flag, so it should replace existing file.
>
> The text above talks about the case that another application has the file open.
>
Ok, didn't get it.


-- 
Ivan Zhakov
VisualSVN Team

RE: pristine store design

Posted by Bert Huijben <be...@qqmail.nl>.

> -----Original Message-----
> From: Ivan Zhakov [mailto:ivan@visualsvn.com]
> Sent: woensdag 3 maart 2010 15:22
> To: Bert Huijben
> Cc: Stefan Sperling; Julian Foad; Neels J Hofmeyr; Greg Stein;
> dev@subversion.apache.org
> Subject: Re: pristine store design
> 
> On Wed, Mar 3, 2010 at 3:54 PM, Bert Huijben <be...@qqmail.nl> wrote:
> > On posix, when using svn_io_rename_file() this would be true and this
> would
> > be pretty safe.
> >
> > On Windows you get an access denied (bad) and a 15 second delay retrying
> the
> > move (worse).
> >
> > So we should try to avoid overwriting existing files here. (I would guess
> > that tools like rsync and incremental backusp also like that we don't change
> > the date of these files)
> >
> That's not correct. Windows API function MoveFileEx has option to
> overwrite destination file [1]. apr_file_rename() uses MoveFileEx with
> MOVEFILE_REPLACE_EXISTING flag, so it should replace existing file.

The text above talks about the case that another application has the file open.

	Bert

Re: pristine store design

Posted by Ivan Zhakov <iv...@visualsvn.com>.
On Wed, Mar 3, 2010 at 3:54 PM, Bert Huijben <be...@qqmail.nl> wrote:
> On posix, when using svn_io_rename_file() this would be true and this would
> be pretty safe.
>
> On Windows you get an access denied (bad) and a 15 second delay retrying the
> move (worse).
>
> So we should try to avoid overwriting existing files here. (I would guess
> that tools like rsync and incremental backusp also like that we don't change
> the date of these files)
>
That's not correct. Windows API function MoveFileEx has option to
overwrite destination file [1]. apr_file_rename() uses MoveFileEx with
MOVEFILE_REPLACE_EXISTING flag, so it should replace existing file.

http://msdn.microsoft.com/en-us/library/aa365240%28VS.85%29.aspx

-- 
Ivan Zhakov
VisualSVN Team

RE: pristine store design

Posted by Julian Foad <ju...@wandisco.com>.
On Wed, 2010-03-03, Bert Huijben wrote:
> 
> > -----Original Message-----
> > From: Stefan Sperling [mailto:stsp@elego.de]
> > Sent: maandag 1 maart 2010 19:32
> > To: Julian Foad
> > Cc: Neels J Hofmeyr; Greg Stein; dev@subversion.apache.org; Bert Huijben
> > Subject: Re: pristine store design
> > 
> > On Mon, Mar 01, 2010 at 06:14:33PM +0000, Julian Foad wrote:
> > > On Thu, 2010-02-18, Neels J Hofmeyr wrote:
> > > > The one thing left now is:
> > > > > Can someone explain a motivation for even creating a database row
> > before
> > > > > the pristine file is moved into place in the pristine store? I
> currently
> > > > > don't see why it can't be way simpler.
> > > [...]
> > 
> > > "Simultaneous or multi-threaded clients" would be my first reaction to
> > > that particular question.
> > 
> > If two threads write to the same pristine, the content written
> > will be the same (except in case of a SHA1 checksum collision
> > which we choose to ignore). So, thread 1 writes to a tempfile, and
> > when it's done, it moves the tempfile into place. The new filename
> > of the tempfile being based on the SHA1 sum of the written content.
> > If thread 2 does the same concurrently, the end result will be the
> > same -- the file will only exist once at its SHA1 sum name.
> 
> On posix, when using svn_io_rename_file() this would be true and this would
> be pretty safe.
> 
> On Windows you get an access denied (bad) and a 15 second delay retrying the
> move (worse).

That's what svn_io_rename_file() does, but for cases like this we should
(write and) use a different rename function that expects no file to
exist at the target path, and that returns immediately if there is a
problem.

- Julian


> So we should try to avoid overwriting existing files here. (I would guess
> that tools like rsync and incremental backusp also like that we don't change
> the date of these files)
> 
> > Of course, writing the same pristine more than once is redundant.
> > So we could try to optmize this redundancy away. But I don't think
> > it is worth it. If you're only talking about threads within a single
> 
> See ^^^.
> 
> 	Bert
> 


Re: pristine store design

Posted by 'Stefan Sperling' <st...@elego.de>.
On Wed, Mar 03, 2010 at 01:54:28PM +0100, Bert Huijben wrote:
> 
> > If two threads write to the same pristine, the content written
> > will be the same (except in case of a SHA1 checksum collision
> > which we choose to ignore). So, thread 1 writes to a tempfile, and
> > when it's done, it moves the tempfile into place. The new filename
> > of the tempfile being based on the SHA1 sum of the written content.
> > If thread 2 does the same concurrently, the end result will be the
> > same -- the file will only exist once at its SHA1 sum name.
> 
> On posix, when using svn_io_rename_file() this would be true and this would
> be pretty safe.
> 
> On Windows you get an access denied (bad) and a 15 second delay retrying the
> move (worse).

If renaming the tempfile to the SHA1 name fails because the SHA1-named
file exists, we can rest assured that the content of the file which already
exists matches exactly what we want the file to contain (assuming SHA1
collisions are negligible).

So if we get access denied on windows because the file exists on disk
already, we can return, knowing some other process did our job for us.
We don't need to retry. We just need to stat and see if the file exists.
Only if it does not exist we need to raise an error (because this means
there's a permissions problem or something like that).

> So we should try to avoid overwriting existing files here. (I would guess
> that tools like rsync and incremental backusp also like that we don't change
> the date of these files)

There is no need to even consider how this would affect other tools.

We're talking about a race condition, where 2 processes try to write the
same pristine at the same time because they both found it to be missing.
This won't happen often, and if it happens, the existing file being renamed
upon will only have existed for a very short time.

Stefan

RE: pristine store design

Posted by Bert Huijben <be...@qqmail.nl>.

> -----Original Message-----
> From: Stefan Sperling [mailto:stsp@elego.de]
> Sent: maandag 1 maart 2010 19:32
> To: Julian Foad
> Cc: Neels J Hofmeyr; Greg Stein; dev@subversion.apache.org; Bert Huijben
> Subject: Re: pristine store design
> 
> On Mon, Mar 01, 2010 at 06:14:33PM +0000, Julian Foad wrote:
> > On Thu, 2010-02-18, Neels J Hofmeyr wrote:
> > > The one thing left now is:
> > > > Can someone explain a motivation for even creating a database row
> before
> > > > the pristine file is moved into place in the pristine store? I
currently
> > > > don't see why it can't be way simpler.
> > [...]
> 
> > "Simultaneous or multi-threaded clients" would be my first reaction to
> > that particular question.
> 
> If two threads write to the same pristine, the content written
> will be the same (except in case of a SHA1 checksum collision
> which we choose to ignore). So, thread 1 writes to a tempfile, and
> when it's done, it moves the tempfile into place. The new filename
> of the tempfile being based on the SHA1 sum of the written content.
> If thread 2 does the same concurrently, the end result will be the
> same -- the file will only exist once at its SHA1 sum name.

On posix, when using svn_io_rename_file() this would be true and this would
be pretty safe.

On Windows you get an access denied (bad) and a 15 second delay retrying the
move (worse).

So we should try to avoid overwriting existing files here. (I would guess
that tools like rsync and incremental backusp also like that we don't change
the date of these files)

> Of course, writing the same pristine more than once is redundant.
> So we could try to optmize this redundancy away. But I don't think
> it is worth it. If you're only talking about threads within a single

See ^^^.

	Bert

Re: pristine store design

Posted by Stefan Sperling <st...@elego.de>.
On Mon, Mar 01, 2010 at 06:14:33PM +0000, Julian Foad wrote:
> On Thu, 2010-02-18, Neels J Hofmeyr wrote:
> > The one thing left now is:
> > > Can someone explain a motivation for even creating a database row before
> > > the pristine file is moved into place in the pristine store? I currently
> > > don't see why it can't be way simpler.
> [...]

> "Simultaneous or multi-threaded clients" would be my first reaction to
> that particular question.

If two threads write to the same pristine, the content written
will be the same (except in case of a SHA1 checksum collision
which we choose to ignore). So, thread 1 writes to a tempfile, and
when it's done, it moves the tempfile into place. The new filename
of the tempfile being based on the SHA1 sum of the written content.
If thread 2 does the same concurrently, the end result will be the
same -- the file will only exist once at its SHA1 sum name.

Of course, writing the same pristine more than once is redundant.
So we could try to optmize this redundancy away. But I don't think
it is worth it. If you're only talking about threads within a single
process, it's fairly easy. But if you're talking about multiple
processes using the same pristine store concurrently with mutual
exclusion, you need inter-process communication to deal with stale locks.
What is a process supposed to do with a locked pristine store, if
it has no way of telling what happened to the process which locked
the pristine store? What if the other process has chrashed?

Stefan

RE: pristine store design

Posted by Bert Huijben <be...@qqmail.nl>.

> -----Original Message-----
> From: Neels J Hofmeyr [mailto:neels@elego.de]
> Sent: woensdag 3 maart 2010 20:26
> To: Greg Stein
> Cc: Stefan Sperling; dev@subversion.apache.org
> Subject: Re: pristine store design
> 
> Two separate things are getting mixed up here.
> 
> 1) The fact that storing (only) md5 in the DB introduces the need for
> locking where it would otherwise be lockless.

If we move the file in place from temp to final location, not overwriting
existing files (fixes Windows case), then retrieve file size and date, then

INSERT OR IGNORE INTO PRISTINE (..., ...) VALUES (..., ...)

You have enough synchronization for adding new files. 

A reader won't notice that anything happens and a simultaneous writer will
do exactly the same thing, as the MD5, size and timestamp of the file in the
pristine store will be identical for both clients.

(This will fail for the case where one writes a compressed version and one
doesn't. But if you make the compressed files use another extension you can
detect this case by checking the affected_rows value of the INSERT and
delete the file afterwards)


The real problem is: how do you handle removing files from the pristine
store with this scheme?

Possible (too) Easy fix for 1.7: Make sure you have a depth infinity lock on
the entire working copy/working copy database.

	Bert

Re: pristine store design

Posted by Neels J Hofmeyr <ne...@elego.de>.
Two separate things are getting mixed up here.

1) The fact that storing (only) md5 in the DB introduces the need for
locking where it would otherwise be lockless.

2) Some misty idea of us to split pristines into multiple chunks of a max
size each in order to be able to verify checksums of subsections. *This one
should not be of concern now.*

So let's concentrate on 1).


Surely it would be silly to introduce a skel when we are going to have lots
of volatile data associated with pristines, anyway. Also, storing in the DB
is not a speed concern. The point is to KISS WRT concurrency.

Greg, you said it's not a concern, could you quantify that? I'm not aware
how the locking works concerning db and file system. Can we, like, open the
DB transaction, then mv the temp pristine file into place, then store the DB
row and close the transaction, and thereby guarantee that the set (mv,
write-db-row) is atomic, and does this also hold on windows? Or are we
talking workqueue or something?

Going back to the start, why do we need to store the md5 sum, exactly? I
assume for sending it back to the server without having to calculate it
again. Right? And do we really need that in the first place? If we anyway
read the whole pristine, and if we send the md5 sum in the *end* anyway,
let's get compat by rather having an md5-tee in the sending stream. This is
simply to save ourselves the md5 storing code path.

(Discussed size, compression columns elsewhere, as well as the yet
non-existing mtime, and assuming that the refcount column will go away for
the benefit of a nice and proper query.)

In 1.7, we will really just need the md5. If my assumption is right about
re-calculating md5 being cheap, we can do without an md5-passing-on code
path and we can, independently from that, but in effect, have no metadata
with pristines at all and roll out 1.7 without DB table nor skel. We can add
a DB table when *real* metadata shows up. Is this sane?

~Neels

Greg Stein wrote:
> I didn't miss any part.
> 
> You're optimizing writes, when you should worry about reads.
> 
> The DB is always open, so reading and writing to it is "cheap".
> 
> I don't care about a scheme to seek to the end of a 16Gb chunk. You're
> making stuff up again.
> 
> On Mar 3, 2010 9:45 AM, "Stefan Sperling" <st...@elego.de> wrote:
> 
> On Wed, Mar 03, 2010 at 12:24:29PM -0500, Greg Stein wrote:
>> You're talking about schemes to verify...
> I didn't say that. I'd very much like svn to verify data it
> reads from the pristine store, on the fly, and point out corrupted
> pristines to the user.
> 
> 
>> You're talking about splitting files for certain filesystems to help with
>> size limitations, yet...
> Those are side-issues.
> 
> What Neels and I are trying to get rid of is the need for
> locking when writing to the pristine store.
> 
> You missed the part of not storing data in an sqlite DB which will
> never change once written.
> We need to store the MD5 of every pristine somewhere, for instance.
> If we do store this data in a DB, writing to the pristine store requires
> synchronising access to the DB to keep the DB in a consistent state,
> on top writing the pristine itself.
> 
> Writing the pristine itself is already lockless, and also writing
> the MD5 while at it means we wouldn't need any locking.
> 
> 
>> Putting data in the file means you have to *open* it to read the data.
> We're opening and reading pristines anyway.
> Reading pristines is disk i/o we cannot avoid.
> 
> The proposed scheme even minimises I/O in case we need only a chunk
> near the end of a file: Seek across a few SHA1 checksums, read a SHA1
> checksum, then open the pristine with that checksum, instead of seeking
> an entire 16GB pristine until the right block has been found.
> 
> Granted, reading an entire huge pristine involves opening a number of
> other prisitines. Not sure which is better.
> 
> 
>> Again: we are centralizing in order to aggregate data and reduce I/O. Your
>> idea defeats that go...
> Is writing another few bytes to the file slower than writing to the file
> and then opening the DB and modifying the DB, possibly waiting for another
> process to unlock the DB, so we can store the MD5?
> 
> Stefan
> 


Re: pristine store design

Posted by Greg Stein <gs...@gmail.com>.
I didn't miss any part.

You're optimizing writes, when you should worry about reads.

The DB is always open, so reading and writing to it is "cheap".

I don't care about a scheme to seek to the end of a 16Gb chunk. You're
making stuff up again.

On Mar 3, 2010 9:45 AM, "Stefan Sperling" <st...@elego.de> wrote:

On Wed, Mar 03, 2010 at 12:24:29PM -0500, Greg Stein wrote:
> You're talking about schemes to verify...
I didn't say that. I'd very much like svn to verify data it
reads from the pristine store, on the fly, and point out corrupted
pristines to the user.


> You're talking about splitting files for certain filesystems to help with
> size limitations, yet...
Those are side-issues.

What Neels and I are trying to get rid of is the need for
locking when writing to the pristine store.

You missed the part of not storing data in an sqlite DB which will
never change once written.
We need to store the MD5 of every pristine somewhere, for instance.
If we do store this data in a DB, writing to the pristine store requires
synchronising access to the DB to keep the DB in a consistent state,
on top writing the pristine itself.

Writing the pristine itself is already lockless, and also writing
the MD5 while at it means we wouldn't need any locking.


> Putting data in the file means you have to *open* it to read the data.
We're opening and reading pristines anyway.
Reading pristines is disk i/o we cannot avoid.

The proposed scheme even minimises I/O in case we need only a chunk
near the end of a file: Seek across a few SHA1 checksums, read a SHA1
checksum, then open the pristine with that checksum, instead of seeking
an entire 16GB pristine until the right block has been found.

Granted, reading an entire huge pristine involves opening a number of
other prisitines. Not sure which is better.


> Again: we are centralizing in order to aggregate data and reduce I/O. Your
> idea defeats that go...
Is writing another few bytes to the file slower than writing to the file
and then opening the DB and modifying the DB, possibly waiting for another
process to unlock the DB, so we can store the MD5?

Stefan

Re: pristine store design

Posted by Julian Foad <ju...@wandisco.com>.
Neels J Hofmeyr wrote:
> Julian Foad wrote:
[...]
> > I want us to be able to move on to bigger things like considering
> > whether to build a "pristine whole nodes" store on top of the "pristine
> > texts" store, because I think we should be able to reference a whole
> > node (especially a tree-conflict old/theirs/mine node) with a single
> > handle, whether that handle be a checksum or a "repos:rev:path" triple.
> 
> You mean "whole subtrees"?? I don't understand.

A local cache [1] of nodes from the repository. Each file would have not
only its text but also its props and perhaps other metadata such as
copyfrom info. Each dir would props, other metadata, and a list of its
children. Each child might or might not be in the cache.

([1] "cache" in the sense of "optional, exact copy"; higher layers can
go fetch the equivalent node from the repository if it's not in the
cache, but this "cache" could also have a property whereby it guarantees
to keep all nodes (or particular nodes as specified by the caller) until
the caller explicitly deletes them.)

The "properties" and "pristine checksum" and some other columns in wc.db
could then be replaced by a single "node handle", which I think could
simplify some of the problems with referring to a "revert-base of a
replaced child of a copied parent" and such like.

But I'm getting too far ahead.


> > I continue to argue below why I think a stream-based interface is better
> > than path-based, but the choice of "write" method is not a critical
> > decision, as long as it stays within libsvn_wc. I'm not keen to spend
> > more time on that, now that I've looked and as far as I can tell it
> > doesn't need to be exposed outside libsvn_wc.
> 
> Note that the entire pristine API we are discussing is private to svn_wc,
> like svn_wc__db_read_info() et al..

OK. Although I saw the "__" in their names, I hadn't really appreciated
until now that the dir/filename transferred between them is necessarily
staying private. I'm glad. That makes this a whole lot less important.

[...]
> > Yes, and that looks neater, but still has all the problems caused by
> > exposing the path.
> 
> For the records, we'd never expose the final pristine-file path, not even
> within libsvn_wc. This whole thing about having a write location is all
> about the temp file that will finally be moved into place.

Yup, I know.

> So at no point will any function that does not have _pristine_ in its name
> be able to find the final pristine file location. Only the tempdir is known,
> and only inside libsvn_wc.
> 
> The final _install() call would then have the option to just 'mv' the file
> into its final location or do whatever with it. We don't lose feasibility of
> any features by doing this.

[...]
> >>  So IMHO it boils down to: Do you think it is better to opaquify
> >> such baton for the sacrifice of not being able to get a write destination on
> >> the target device in advance?
> > 
> > Yes, I think that is the better API for general use. (Note that the
> > stream would always write to a file that is on the destination device.
> > The only thing you can't get with this API is a path to that file (or
> > directory).)
> 
> Hm, this argument actually revolves around: will we have cases where a
> tempfile already exists, and where we have no control on redirecting streams
> into the pristine store? When committing new or modified files, we need to
> copy&checksum, can't checksum in-place; When receiving from the repos, we
> can direct the stream straight into the pristine store, and validate proper
> reception via that.
> 
> I can't come up with a use case of interest. If there aren't (going to be)
> any, I actually agree with a stream-only write API. Reversing my own
> argument, we can still split such stream-only function into _get_temp_dir()
> and _install() later on, making the original stream-only function a
> convenience function. So I am actually convinced before even looking at the
> disadvantages. Thanks :)
> 
> > 
> > 
> > Now let's look at some disadvantages of "return a directory path".
[...]
> > If the path is exposed just within libsvn_wc, these issues stay under
> > our control, so that's OK. If the path is exposed in a public API, to
> > libsvn_client and beyond, that's when I worry.
> 
> (No paths would ever leak out of libsvn_wc. The pristine-tempdir path would
> be known inside libsvn_wc. I'd say we can trust libsvn_wc to use a proper
> function for creating a unique file. But see my being convinced above.)

OK, I feel much better knowing it's staying within libsvn_wc. And it has
the advantage of already being implemented :-)


> >>> VERIFYING CHECKSUMS
> > [...]

+1 on (from your previous email) removing svn_wc__db_checkmode_t and
having a single explicit check() function.

> > [DBs and concurrency ...]
> > [...]
> > 
> > I'm not replying to those parts in this email.
> 
> heh, me and stsp are also coming up with new directions by the hour.
> 
> We were discussing that having a separate pristine database basically sucks.
> We need to ensure atomicity of mv-into-place with write-db-row.
> 
> This would be more straightforward if we had no DB, but instead an
> information header in each pristine file itself.
[...]
> Given that we checksum all read operations, we only want to store the MD5
> sum! The initial header could simply be always fixed 32 bytes of MD5
> checksum. And even this is just a speed optimization. Given that we checksum
> all reads, all reads can *calculate* the MD5 sum on-the-fly. Pushing for
> simplicity here.
> 
> If we want more values in the future, like compression, we introduce a skel.
> 
> Any minus-ones?

Sounds OK. I can't see any need for the "pristine" table in wc.db at the
moment. I note that the svn_wc__db_pristine_*() functions don't use the
DB except to determine the PDH and local_relpath.

On the other hand I don't think ensuring consistency of the db and the
file system should be a big hassle, but I haven't thought exactly how to
do it.

The important thing is that the APIs have the DB parameter so we can add
in some DB <-> file consistency later if we want it.

- Julian


Re: pristine store design

Posted by Julian Foad <ju...@wandisco.com>.
On Wed, 2010-03-03 at 11:10 -0500, Greg Stein wrote:
> On Wed, Mar 3, 2010 at 08:48, Neels J Hofmeyr <ne...@elego.de> wrote:
> >...
> >> If the caller creates the file, the caller chooses the file's name. We
> >> have to trust the caller to use the right kind of creation functions to
> >> give a safely unique name.
> 
> libsvn_wc. no big deal.

I have just noticed that we already sort-of leak the temporary file name
in a public API, svn_wc_transmit_text_deltas3():

  /** Send the local modifications for versioned file @a local_abspath (with
   * matching @a file_baton) through @a editor, then close @a file_baton
   * afterwards.  Use @a scratch_pool for any temporary allocation.
   *
   * This process creates a copy of @a local_abspath with keywords and eol
   * untranslated.  If @a tempfile is non-NULL, set @a *tempfile to the
   * absolute path to this copy, allocated in @a result_pool.  Do not clean
   * up the copy; caller can do that.  If @a digest is non-NULL, put the MD5
   * checksum of the temporary file into @a digest, which must point to @c
   * APR_MD5_DIGESTSIZE bytes of storage.  (The purpose of handing back the
   * tmp copy is that it is usually about to become the new text base anyway,
   * but the installation of the new text base is outside the scope of this
   * function.)
   ... */
  svn_wc_transmit_text_deltas3(const char **tempfile, ...)

It's used by svn_client__do_commit() which passes the tempfiles and
checksums up to its callers which are ...

  svn_client_commit4() which just removes those files if it encounters
an error (it doesn't try to use them or pass them anywhere else);

  libsvn_client:wc_to_repos_copy() which doesn't look at them.


That is the only usage in Subversion. Of course it may possibly be used
by other clients.

We can still implement this API compatibly, of course, even if we were
to want an implementation that ; it just means we have to produce a
temporary file even if we would not otherwise have done so. We could say
that it's none of the caller's business to look in that file and it
should be doing nothing other than deleting it, in which case we could
cheat and return something other than a true copy (an empty file? no
file?).

I don't think this is a critical problem, but it's worth being aware of.
I haven't checked whether there are any other leaks.


> >> If the caller creates the file, the pristine store can't keep track of
> >> what's in its temporary directory. Does it matter? Maybe not, yet.
> 
> No.

Hmm.

> >> If the caller creates the file, the caller chooses the file's
> >> permissions. The pristine store loses the ability to control privacy.
> >> Does it matter? Maybe not, yet.
> 
> bunk.
> 
> install:
>   move file
>   chmod file
> 
> we do this *today* ... there isn't anything new tech here.

OK, sure.

But as I said to Neels, this "write" API isn't on the critical path so
I'm now looking at *using* the one we have (even though it's not my
personal favourite).

- Julian


Re: pristine store design

Posted by Greg Stein <gs...@gmail.com>.
On Wed, Mar 3, 2010 at 08:48, Neels J Hofmeyr <ne...@elego.de> wrote:
>...
>> If the caller creates the file, the caller chooses the file's name. We
>> have to trust the caller to use the right kind of creation functions to
>> give a safely unique name.

libsvn_wc. no big deal.

>> If the caller creates the file, the pristine store can't keep track of
>> what's in its temporary directory. Does it matter? Maybe not, yet.

No.

>> If the caller creates the file, the caller chooses the file's
>> permissions. The pristine store loses the ability to control privacy.
>> Does it matter? Maybe not, yet.

bunk.

install:
  move file
  chmod file

we do this *today* ... there isn't anything new tech here.

>...

-g

Re: pristine store design

Posted by Philipp Marek <ph...@emerion.com>.
Hello Stefan,

On Mittwoch, 3. März 2010, Stefan Sperling wrote:
> A block is "just another pristine".
> So a block can happen to also serve as a pristine for a different 10MB
> file which happens to have the same content as the block.
> We set the block size to something fixed, like 10MB.
> The last block is allowed to be smaller and runs till EOF.
You could go a little step further and determine the block borders by a 
synchronizing checksum, ie. a manber-hash.

FSVS does this; the advantages are
a) you can quit comparing the files (or hashs) as soon as a different block
   is found
b) sending nearly-optimal deltas is trivial, because you know that the file
   originally had the blocks A,B,C,D and E, and now the blocks hash to
   A,X,C,Y and E - so you can just tell the server "the first length(A) bytes 
   are identical, then you need X, then length(C) are unchanged, ..."
   Of course, that's not byte-optimized, but AFAIK the server will re-compute
   the delta anyway (for BDB and FSFS).
c) identical blocks from different files get shared; so keeping 3 revisions of
   a 100MB file might need only 100 + epsilon space, and that's without having
   the blocks compressed.
d) small point: the manber-CRC provide a few bits more security that there's
   no hash-collision.

So on commit the content verification goes once through the file, and records
offsets and length of the blocks (and whether they did exist in the older 
version); for transferring the delta only some seeks and writes are needed.

The manber-hash block size can be chosen arbitrarily; in FSVS I'm using 
~128kB, which means that small files just have a single hash to store, but for 
larger ones the IO savings get realized.



Regards,

Phil

Re: pristine store design

Posted by Stefan Sperling <st...@elego.de>.
On Wed, Mar 03, 2010 at 12:24:29PM -0500, Greg Stein wrote:
> You're talking about schemes to verify partial reads, yet stated you
> couldn't think of any cases.

I didn't say that. I'd very much like svn to verify data it
reads from the pristine store, on the fly, and point out corrupted
pristines to the user.

> You're talking about splitting files for certain filesystems to help with
> size limitations, yet the working file still has to be whole, and we have
> no/few? reports of size problems.
> 
> IOW, you're just making up requirements and work.

Those are side-issues.

What Neels and I are trying to get rid of is the need for
locking when writing to the pristine store.

You missed the part of not storing data in an sqlite DB which will
never change once written.
We need to store the MD5 of every pristine somewhere, for instance.
If we do store this data in a DB, writing to the pristine store requires
synchronising access to the DB to keep the DB in a consistent state,
on top writing the pristine itself.

Writing the pristine itself is already lockless, and also writing
the MD5 while at it means we wouldn't need any locking.

> Putting data in the file means you have to *open* it to read the data.

We're opening and reading pristines anyway.
Reading pristines is disk i/o we cannot avoid.

The proposed scheme even minimises I/O in case we need only a chunk
near the end of a file: Seek across a few SHA1 checksums, read a SHA1
checksum, then open the pristine with that checksum, instead of seeking
an entire 16GB pristine until the right block has been found.

Granted, reading an entire huge pristine involves opening a number of
other prisitines. Not sure which is better.

> Again: we are centralizing in order to aggregate data and reduce I/O. Your
> idea defeats that goal.

Is writing another few bytes to the file slower than writing to the file
and then opening the DB and modifying the DB, possibly waiting for another
process to unlock the DB, so we can store the MD5?

Stefan

Re: pristine store design

Posted by Greg Stein <gs...@gmail.com>.
You're talking about schemes to verify partial reads, yet stated you
couldn't think of any cases.

You're talking about splitting files for certain filesystems to help with
size limitations, yet the working file still has to be whole, and we have
no/few? reports of size problems.

IOW, you're just making up requirements and work.

Putting data in the file means you have to *open* it to read the data.
Again: we are centralizing in order to aggregate data and reduce I/O. Your
idea defeats that goal.

On Mar 3, 2010 8:51 AM, "Stefan Sperling" <st...@elego.de> wrote:

On Wed, Mar 03, 2010 at 11:03:59AM -0500, Greg Stein wrote:
> We have one area for metadata, and tha...
That's true. But it may be worth making an exception for this.
Keep in mind that once the pristine is created, its data never changes.

We could use a skel for the header if we decide to make an exception
and store meta data about pristines inside of pristines.
So we won't have to write a new custom parser.

We'd still use the wc.db for any volatile data concerning the pristine.
But so far it looks like the only volatile data is the mtime, which
according to Neels was invented as a way to "cheaply verify" partial
reads (WTF?). The scheme proposed below makes storing the mtime unnecessary.


> You should not have any problems moving a pristine into place and
> storing a record into the db....
DB access needs to be synchronised while creating the pristine is
lock-free. Why not just go lock-free all the way?


> Funky headers in the file means that I cannot do:
>
> $ sha1sum myfile.c
> abcdef...
> $ sha1sum...
Why would you want to do that?

If the pristine has the same name as the SHA1 of myfile.c, you know
they are related. You just could not validate a pristine without
using some svn command that knows how to skip the pristine's header
and verifying just the content. But why would you want to use Subversion's
pristine store without also using svn? Which tool, if not svn itself,
would want to verify pristines?


> The files you're talking about storing do not actually *have* the
> desired checksum. That's just...
I think that splitting up pristines for large files is a nice way
of dealing with the problem of verifying partial reads.
Require callers to read at least a whole chunk of which the checksum
is known and you can verify even partial reads relatively cheaply.

It also helps dealing with file system limitations in the future,
e.g. if the pristine store resides on a file system that does not
support files as large as the filesystem the working copy is
sitting in -- pristine store on FAT32, working copy on ZFS :)

For example:

-----
pristine-for-16GB-file (named "sha1 of 16GB file"):
[header saying amount of fixed-size blocks, size of last block in bytes,
 and sha1 of what follows][sha1 name of block 1][sha1 name of block2][...]

pristine for block 1 (named "sha 1 of block 1's content"):
[header][block 1 data]

pristine for block 2 (named "sha 1 of block 2's content"):
[header][block 2 data]

etc...
-----

A block is "just another pristine".
So a block can happen to also serve as a pristine for a different 10MB
file which happens to have the same content as the block.
We set the block size to something fixed, like 10MB.
The last block is allowed to be smaller and runs till EOF.

We can stat the size of small pristines, and parse a small header
to find the size of large pristines:
 #fixed-sized blocks * blocksize + size of last block

Of course, reading large files would involve a bit of seeking.

Also, this extension is optional -- for 1.7, we can write 16GB large
pristines and verify them upon read (even partial reads). Later, we can
add the proposed scheme on top and get cheaply verifiable partial reads.
Or if we get there in time, we can already have it in 1.7.

Starting with 1.7, the header would at least store the MD5 of the content
of the pristine. The header indicates its own size, so we're backwards
compatible forever since it's easy to skip unknown header data and read
and verify the content.

Stefan

Re: pristine store design

Posted by Stefan Sperling <st...@elego.de>.
On Wed, Mar 03, 2010 at 11:03:59AM -0500, Greg Stein wrote:
> We have one area for metadata, and that is the sqlite file named wc.db.
> 
> Spreading metadata around is not very attractive. New custom file
> formats is also unattractive.

That's true. But it may be worth making an exception for this.
Keep in mind that once the pristine is created, its data never changes.

We could use a skel for the header if we decide to make an exception
and store meta data about pristines inside of pristines.
So we won't have to write a new custom parser.

We'd still use the wc.db for any volatile data concerning the pristine.
But so far it looks like the only volatile data is the mtime, which
according to Neels was invented as a way to "cheaply verify" partial
reads (WTF?). The scheme proposed below makes storing the mtime unnecessary.

> You should not have any problems moving a pristine into place and
> storing a record into the db. Sync is not the problem.

DB access needs to be synchronised while creating the pristine is
lock-free. Why not just go lock-free all the way?

> Funky headers in the file means that I cannot do:
> 
> $ sha1sum myfile.c
> abcdef...
> $ sha1sum .svn/pristine/ab/abcdef...
> abcdef...

Why would you want to do that?

If the pristine has the same name as the SHA1 of myfile.c, you know
they are related. You just could not validate a pristine without
using some svn command that knows how to skip the pristine's header
and verifying just the content. But why would you want to use Subversion's
pristine store without also using svn? Which tool, if not svn itself,
would want to verify pristines?

> The files you're talking about storing do not actually *have* the
> desired checksum. That's just nasty.

I think that splitting up pristines for large files is a nice way
of dealing with the problem of verifying partial reads.
Require callers to read at least a whole chunk of which the checksum
is known and you can verify even partial reads relatively cheaply.

It also helps dealing with file system limitations in the future,
e.g. if the pristine store resides on a file system that does not
support files as large as the filesystem the working copy is
sitting in -- pristine store on FAT32, working copy on ZFS :)

For example:

-----
pristine-for-16GB-file (named "sha1 of 16GB file"):
[header saying amount of fixed-size blocks, size of last block in bytes,
 and sha1 of what follows][sha1 name of block 1][sha1 name of block2][...]

pristine for block 1 (named "sha 1 of block 1's content"):
[header][block 1 data]

pristine for block 2 (named "sha 1 of block 2's content"):
[header][block 2 data]

etc...
-----

A block is "just another pristine".
So a block can happen to also serve as a pristine for a different 10MB
file which happens to have the same content as the block.
We set the block size to something fixed, like 10MB.
The last block is allowed to be smaller and runs till EOF.

We can stat the size of small pristines, and parse a small header
to find the size of large pristines:
  #fixed-sized blocks * blocksize + size of last block

Of course, reading large files would involve a bit of seeking.

Also, this extension is optional -- for 1.7, we can write 16GB large
pristines and verify them upon read (even partial reads). Later, we can
add the proposed scheme on top and get cheaply verifiable partial reads.
Or if we get there in time, we can already have it in 1.7.

Starting with 1.7, the header would at least store the MD5 of the content
of the pristine. The header indicates its own size, so we're backwards
compatible forever since it's easy to skip unknown header data and read
and verify the content.

Stefan

Re: pristine store design

Posted by Greg Stein <gs...@gmail.com>.
We have one area for metadata, and that is the sqlite file named wc.db.

Spreading metadata around is not very attractive. New custom file
formats is also unattractive.

You should not have any problems moving a pristine into place and
storing a record into the db. Sync is not the problem.

Funky headers in the file means that I cannot do:

$ sha1sum myfile.c
abcdef...
$ sha1sum .svn/pristine/ab/abcdef...
abcdef...

The files you're talking about storing do not actually *have* the
desired checksum. That's just nasty.

-g

On Wed, Mar 3, 2010 at 08:48, Neels J Hofmeyr <ne...@elego.de> wrote:
> Julian Foad wrote:
>> On Wed, 2010-03-03, Neels J Hofmeyr wrote:
>>> Julian Foad wrote:
>>>> On Thu, 2010-02-18, Neels J Hofmeyr wrote:
>>>>> Great, moving forward fast on pristine design questions!
>>>> Hi Neels.
>>>>
>>>> Did you start working the new knowledge into a document?  Lots of stuff
>>>> was said in this thread and it would be useful to see where we are at.
>>> thanks for poking :)
>>
>> No problem. I'm glad you're working on this.
>>
>> Please go ahead with this pristine store. Delete the "_write" interface.
>
> looking forward to that one, nice and simple :)
>
>> Implement the path-based ones; at least they're already declared. It's
>> really important to get it moving.
>
> Just aside, I once started looking for places where the pristine is used
> properly, but there's more to do before we can roll out the pristine:
> foremost getting rid of write-metadata-via-entry_t.
>
>>
>> I want us to be able to move on to bigger things like considering
>> whether to build a "pristine whole nodes" store on top of the "pristine
>> texts" store, because I think we should be able to reference a whole
>> node (especially a tree-conflict old/theirs/mine node) with a single
>> handle, whether that handle be a checksum or a "repos:rev:path" triple.
>
> You mean "whole subtrees"?? I don't understand.
>
>>
>> I continue to argue below why I think a stream-based interface is better
>> than path-based, but the choice of "write" method is not a critical
>> decision, as long as it stays within libsvn_wc. I'm not keen to spend
>> more time on that, now that I've looked and as far as I can tell it
>> doesn't need to be exposed outside libsvn_wc.
>
> Note that the entire pristine API we are discussing is private to svn_wc,
> like svn_wc__db_read_info() et al..
>
> [...]
>>> pseudocode:
>>> [[[
>>>  pristine_get_tempdir(&tempdir)
>>>
>>>  /* Make tempfile */
>>>  svn_stream_open_unique(&tempstream, &tempfile_path, tempdir)
>>>
>>>  /* Write and checksum */
>>>  tempstream = svn_stream_checksummed2(tempstream, &write_checksum)
>>>  write to and close tempstream
>>>
>>>  pristine_install(tempfile_path, write_checksum)
>>> ]]]
>>>
>>> When there is only a write-stream available, some options get lost, while
>>> _get_tempdir() and _install() offer the whole palette of possibilities. For
>>> convenience, we can offer a wrapper for the first three instructions above.
>>> But additionally, we can offer the possibility to determine a file location
>>> *on the same file system device* as the pristine store. This is useful when
>>> we can provide some external tool or specialized function X with a
>>> destination path in advance. We create a tempfile in pristine_temp_dir() and
>>> pass that location to X.  X writes or OS-copies or <whatever>s to the final
>>> device, possibly saving one copy-across-fs-devices operation per pristine.
>>
>> Sure.  That's my "case (4)" of the cases I enumerated.  But I think it's
> For the records, I did see that :)
>
>> a less important case.  See my investigation of "actual uses" below,
>> near the end of this email.
>>
>>> Also, X may already have a checksum tee in its implementation, obsoleting
>>> the need to calculate again. In that case it's nice that pristine_install()
>>> doesn't care where the checksum came from.
>>
>> Sure, but, for the cases where X writes to a stream, a stream-based API
>> (slightly different from how I suggested) could do that too.
>
> Yes, an optional parameter would do.
>
>>
>>>  (Also, if we are going to
>>> validate the checksum on "every" read, there is no need to be paranoid about
>>> correctness of the checksum when writing -- we anyway have to "expect"
>>> corruptions to occur after any successful write.)
>>>
>>> Note that your proposed usage is a subset of the usage provided by
>>> _get_temp_dir() and _install(). Your way does KISS some API complexity
>>> goodbye when thinking in human terms, but the OS will find the
>>> _get_temp_dir() and _install() simpler in some cases :P
>>
>> Yes, but also the stream way allows the pristine store to grow new
>> features transparently - see "disadvantages" below.
>
> (also see below)
>
>>
>>> The simpler usage of above pseudocode would be:
>>>
>>> pseudocode:
>>> [[[
>>>  /* convenience function provided by API or whomever. */
>>>  svn_error_t *
>>>  pristine_get_write_stream(stream_t **write_stream,
>>>                            svn_checksum_t *write_checksum,
>>>                            const char **temp_path)
>>>  {
>>>    pristine_get_tempdir(&tempdir)
>>>
>>>    /* Make tempfile */
>>>    svn_stream_open_unique(&tempstream, &tempfile_path, tempdir)
>>>
>>>    /* Write checksum to the checksum location provided by caller */
>>>    *write_stream = svn_stream_checksummed2(tempstream, write_checksum)
>>>  }
>>>
>>>  ...
>>>
>>>  /* calling code */
>>>  {
>>>    pristine_get_write_stream(&stream, &write_checksum, &stream_temp_path)
>>>    write to and close stream
>>>    if (had priori checksum and does not match write_checksum):
>>>      bail
>>>    pristine_install(stream_temp_path, write_checksum)
>>>  }
>>> ]]]
>>>
>>> This is similar to what you propose,
>>
>> Yes, and that looks neater, but still has all the problems caused by
>> exposing the path.
>
> For the records, we'd never expose the final pristine-file path, not even
> within libsvn_wc. This whole thing about having a write location is all
> about the temp file that will finally be moved into place.
>
> So at no point will any function that does not have _pristine_ in its name
> be able to find the final pristine file location. Only the tempdir is known,
> and only inside libsvn_wc.
>
> The final _install() call would then have the option to just 'mv' the file
> into its final location or do whatever with it. We don't lose feasibility of
> any features by doing this.
>
>>
>>>  when considering that your
>>> implementation would also need a baton to pass the stream temp path along
>>> (right?).
>>
>> The API wouldn't need an extra baton parameter. It would return a stream
>> whose internal "baton" (user data) stores any metadata it needs.
>
> That's cool, wasn't aware of it.
>
>>
>>>  So IMHO it boils down to: Do you think it is better to opaquify
>>> such baton for the sacrifice of not being able to get a write destination on
>>> the target device in advance?
>>
>> Yes, I think that is the better API for general use. (Note that the
>> stream would always write to a file that is on the destination device.
>> The only thing you can't get with this API is a path to that file (or
>> directory).)
>
> Hm, this argument actually revolves around: will we have cases where a
> tempfile already exists, and where we have no control on redirecting streams
> into the pristine store? When committing new or modified files, we need to
> copy&checksum, can't checksum in-place; When receiving from the repos, we
> can direct the stream straight into the pristine store, and validate proper
> reception via that.
>
> I can't come up with a use case of interest. If there aren't (going to be)
> any, I actually agree with a stream-only write API. Reversing my own
> argument, we can still split such stream-only function into _get_temp_dir()
> and _install() later on, making the original stream-only function a
> convenience function. So I am actually convinced before even looking at the
> disadvantages. Thanks :)
>
>>
>>
>> Now let's look at some disadvantages of "return a directory path".
>>
>> If the caller creates the file, the caller chooses the file's name. We
>> have to trust the caller to use the right kind of creation functions to
>> give a safely unique name.
>>
>> If the caller creates the file, the pristine store can't keep track of
>> what's in its temporary directory. Does it matter? Maybe not, yet.
>>
>> If the caller creates the file, the caller chooses the file's
>> permissions. The pristine store loses the ability to control privacy.
>> Does it matter? Maybe not, yet.
>
> I never thought of that!
>
>>
>> If the caller writes to the file, the pristine store doesn't have a
>> streamy way to compress the data if it wants to - it would have to read
>> it again. Does it matter? Maybe we never will, or maybe we'll want to
>> change the API anyway when we support compressed texts so it wouldn't
>> matter.
>>
>> If the path is exposed just within libsvn_wc, these issues stay under
>> our control, so that's OK. If the path is exposed in a public API, to
>> libsvn_client and beyond, that's when I worry.
>
> (No paths would ever leak out of libsvn_wc. The pristine-tempdir path would
> be known inside libsvn_wc. I'd say we can trust libsvn_wc to use a proper
> function for creating a unique file. But see my being convinced above.)
>
>>
>>
>> The other thing we can do is look at the actual uses and see what would
>> be best for them.
>>
>>   * svn_wc_add_repos_file4() is a public API that takes (as an input
>> parameter) the new pristine contents as a stream and writes it to the
>> pristine store, among other things.
>>
>>   * update_editor.c:apply_textdelta() gets a readable stream of the
>> existing text base file, and a writable stream to a new (temporary) text
>> base file, and passes the two streams to svn_txdelta_apply(). Presumably
>> some other function then moves the temp base file to the real base path.
>>
>> It looks like it would be slightly easier and more "natural" for both of
>> those functions to get a writable pristine stream than to create an
>> intermediate file itself and then wrap it in a stream. Not a big deal,
>> perhaps.
>
> Agreed. Not a big deal, but why have high granularity when no-one uses it.
>
> [...]
>>>> VERIFYING CHECKSUMS
>> [...]
>>
>> [DBs and concurrency ...]
>> [...]
>>
>> I'm not replying to those parts in this email.
>
> heh, me and stsp are also coming up with new directions by the hour.
>
> We were discussing that having a separate pristine database basically sucks.
> We need to ensure atomicity of mv-into-place with write-db-row.
>
> This would be more straightforward if we had no DB, but instead an
> information header in each pristine file itself. Either that header would
> have fixed size, or (rather) we'd write the file offset of where the actual
> content starts in the first few bytes.
>
> The only thing that would remain a problem is wanting to record a pristine's
> mtime. We can't write the mtime into the file itself, and hope that we are
> still within the same mtime grain, not altering the real mtime of the file
> *again* (think usec mtime resolution). But we agree that even storing the
> mtime of a pristine is bogus. We should checksum every read anyway.
>
> We currently have the pressing need to store *only* the md5-checksum
> associated with a SHA1. I can't see why we need size or mtime when we
> checksum anyway (I'm hereby taking back my own suggestion to add mtime).
>
> That brought us into the realm of partial reads. We can't think of a case
> where partial reads are even used. But if they are, we can easily introduce
> a super-pristine header thing that references other pristines as chunks of
> which it is made up, so that no pristine ever grows larger than, say, 10 Mb.
> We've got it figured out already, and that would be easy to leave aside for
> now and add later when the need arises. (Smaller pristines are still stored
> the same way, but as soon as a checksum is not found, we can also look up
> the set of super-headers. Writing would split up the large pristine into say
> 10 Mb chunks, write each one in itself, which may even coincide with
> existing pristine chunks, and as a final step write the super-header into a
> separate location. Easy as pie.)
>
> In a nutshell, I'd like to push a filesystem-only pristine store! No DB
> required. This removes all concurrency problems of syncing the DB and the
> file system, because there is no DB anymore.
> (except that on windows, concurrent moves to the same location may cause one
> of the callers to fail. We'd need to cover this even with a DB in place.)
> _pristine_read() would open the pristine file, seek to just after the
> header, and then deliver the stream to the caller.
>
> As said, we can store any and all metadata in a header in the pristine file
> itself, except the mtime. I think we should go for it, mtime being a sad
> excuse of a sanity check anyway, IMHO. (We *can* store the size, given that
> we use a header of pre-determinable size, but same as mtime, I wouldn't even
> want to store the size anyway.)
>
> Given that we checksum all read operations, we only want to store the MD5
> sum! The initial header could simply be always fixed 32 bytes of MD5
> checksum. And even this is just a speed optimization. Given that we checksum
> all reads, all reads can *calculate* the MD5 sum on-the-fly. Pushing for
> simplicity here.
>
> If we want more values in the future, like compression, we introduce a skel.
>
> Any minus-ones?
>
> ~Neels
>
>

Re: pristine store design

Posted by Neels J Hofmeyr <ne...@elego.de>.
Julian Foad wrote:
> On Wed, 2010-03-03, Neels J Hofmeyr wrote:
>> Julian Foad wrote:
>>> On Thu, 2010-02-18, Neels J Hofmeyr wrote:
>>>> Great, moving forward fast on pristine design questions!
>>> Hi Neels.
>>>
>>> Did you start working the new knowledge into a document?  Lots of stuff
>>> was said in this thread and it would be useful to see where we are at.
>> thanks for poking :)
> 
> No problem. I'm glad you're working on this.
> 
> Please go ahead with this pristine store. Delete the "_write" interface.

looking forward to that one, nice and simple :)

> Implement the path-based ones; at least they're already declared. It's
> really important to get it moving.

Just aside, I once started looking for places where the pristine is used
properly, but there's more to do before we can roll out the pristine:
foremost getting rid of write-metadata-via-entry_t.

> 
> I want us to be able to move on to bigger things like considering
> whether to build a "pristine whole nodes" store on top of the "pristine
> texts" store, because I think we should be able to reference a whole
> node (especially a tree-conflict old/theirs/mine node) with a single
> handle, whether that handle be a checksum or a "repos:rev:path" triple.

You mean "whole subtrees"?? I don't understand.

> 
> I continue to argue below why I think a stream-based interface is better
> than path-based, but the choice of "write" method is not a critical
> decision, as long as it stays within libsvn_wc. I'm not keen to spend
> more time on that, now that I've looked and as far as I can tell it
> doesn't need to be exposed outside libsvn_wc.

Note that the entire pristine API we are discussing is private to svn_wc,
like svn_wc__db_read_info() et al..

[...]
>> pseudocode:
>> [[[
>>  pristine_get_tempdir(&tempdir)
>>
>>  /* Make tempfile */
>>  svn_stream_open_unique(&tempstream, &tempfile_path, tempdir)
>>
>>  /* Write and checksum */
>>  tempstream = svn_stream_checksummed2(tempstream, &write_checksum)
>>  write to and close tempstream
>>
>>  pristine_install(tempfile_path, write_checksum)
>> ]]]
>>
>> When there is only a write-stream available, some options get lost, while
>> _get_tempdir() and _install() offer the whole palette of possibilities. For
>> convenience, we can offer a wrapper for the first three instructions above.
>> But additionally, we can offer the possibility to determine a file location
>> *on the same file system device* as the pristine store. This is useful when
>> we can provide some external tool or specialized function X with a
>> destination path in advance. We create a tempfile in pristine_temp_dir() and
>> pass that location to X.  X writes or OS-copies or <whatever>s to the final
>> device, possibly saving one copy-across-fs-devices operation per pristine.
> 
> Sure.  That's my "case (4)" of the cases I enumerated.  But I think it's
For the records, I did see that :)

> a less important case.  See my investigation of "actual uses" below,
> near the end of this email.
> 
>> Also, X may already have a checksum tee in its implementation, obsoleting
>> the need to calculate again. In that case it's nice that pristine_install()
>> doesn't care where the checksum came from.
> 
> Sure, but, for the cases where X writes to a stream, a stream-based API
> (slightly different from how I suggested) could do that too.

Yes, an optional parameter would do.

>   
>>  (Also, if we are going to
>> validate the checksum on "every" read, there is no need to be paranoid about
>> correctness of the checksum when writing -- we anyway have to "expect"
>> corruptions to occur after any successful write.)
>>
>> Note that your proposed usage is a subset of the usage provided by
>> _get_temp_dir() and _install(). Your way does KISS some API complexity
>> goodbye when thinking in human terms, but the OS will find the
>> _get_temp_dir() and _install() simpler in some cases :P
> 
> Yes, but also the stream way allows the pristine store to grow new
> features transparently - see "disadvantages" below.

(also see below)

> 
>> The simpler usage of above pseudocode would be:
>>
>> pseudocode:
>> [[[
>>  /* convenience function provided by API or whomever. */
>>  svn_error_t *
>>  pristine_get_write_stream(stream_t **write_stream,
>>                            svn_checksum_t *write_checksum,
>>                            const char **temp_path)
>>  {
>>    pristine_get_tempdir(&tempdir)
>>
>>    /* Make tempfile */
>>    svn_stream_open_unique(&tempstream, &tempfile_path, tempdir)
>>
>>    /* Write checksum to the checksum location provided by caller */
>>    *write_stream = svn_stream_checksummed2(tempstream, write_checksum)
>>  }
>>
>>  ...
>>
>>  /* calling code */
>>  {
>>    pristine_get_write_stream(&stream, &write_checksum, &stream_temp_path)
>>    write to and close stream
>>    if (had priori checksum and does not match write_checksum):
>>      bail
>>    pristine_install(stream_temp_path, write_checksum)
>>  }
>> ]]]
>>
>> This is similar to what you propose,
> 
> Yes, and that looks neater, but still has all the problems caused by
> exposing the path.

For the records, we'd never expose the final pristine-file path, not even
within libsvn_wc. This whole thing about having a write location is all
about the temp file that will finally be moved into place.

So at no point will any function that does not have _pristine_ in its name
be able to find the final pristine file location. Only the tempdir is known,
and only inside libsvn_wc.

The final _install() call would then have the option to just 'mv' the file
into its final location or do whatever with it. We don't lose feasibility of
any features by doing this.

> 
>>  when considering that your
>> implementation would also need a baton to pass the stream temp path along
>> (right?).
> 
> The API wouldn't need an extra baton parameter. It would return a stream
> whose internal "baton" (user data) stores any metadata it needs.

That's cool, wasn't aware of it.

> 
>>  So IMHO it boils down to: Do you think it is better to opaquify
>> such baton for the sacrifice of not being able to get a write destination on
>> the target device in advance?
> 
> Yes, I think that is the better API for general use. (Note that the
> stream would always write to a file that is on the destination device.
> The only thing you can't get with this API is a path to that file (or
> directory).)

Hm, this argument actually revolves around: will we have cases where a
tempfile already exists, and where we have no control on redirecting streams
into the pristine store? When committing new or modified files, we need to
copy&checksum, can't checksum in-place; When receiving from the repos, we
can direct the stream straight into the pristine store, and validate proper
reception via that.

I can't come up with a use case of interest. If there aren't (going to be)
any, I actually agree with a stream-only write API. Reversing my own
argument, we can still split such stream-only function into _get_temp_dir()
and _install() later on, making the original stream-only function a
convenience function. So I am actually convinced before even looking at the
disadvantages. Thanks :)

> 
> 
> Now let's look at some disadvantages of "return a directory path".
> 
> If the caller creates the file, the caller chooses the file's name. We
> have to trust the caller to use the right kind of creation functions to
> give a safely unique name.
> 
> If the caller creates the file, the pristine store can't keep track of
> what's in its temporary directory. Does it matter? Maybe not, yet.
> 
> If the caller creates the file, the caller chooses the file's
> permissions. The pristine store loses the ability to control privacy.
> Does it matter? Maybe not, yet.

I never thought of that!

> 
> If the caller writes to the file, the pristine store doesn't have a
> streamy way to compress the data if it wants to - it would have to read
> it again. Does it matter? Maybe we never will, or maybe we'll want to
> change the API anyway when we support compressed texts so it wouldn't
> matter.
> 
> If the path is exposed just within libsvn_wc, these issues stay under
> our control, so that's OK. If the path is exposed in a public API, to
> libsvn_client and beyond, that's when I worry.

(No paths would ever leak out of libsvn_wc. The pristine-tempdir path would
be known inside libsvn_wc. I'd say we can trust libsvn_wc to use a proper
function for creating a unique file. But see my being convinced above.)

> 
> 
> The other thing we can do is look at the actual uses and see what would
> be best for them.
> 
>   * svn_wc_add_repos_file4() is a public API that takes (as an input
> parameter) the new pristine contents as a stream and writes it to the
> pristine store, among other things.
> 
>   * update_editor.c:apply_textdelta() gets a readable stream of the
> existing text base file, and a writable stream to a new (temporary) text
> base file, and passes the two streams to svn_txdelta_apply(). Presumably
> some other function then moves the temp base file to the real base path.
> 
> It looks like it would be slightly easier and more "natural" for both of
> those functions to get a writable pristine stream than to create an
> intermediate file itself and then wrap it in a stream. Not a big deal,
> perhaps.

Agreed. Not a big deal, but why have high granularity when no-one uses it.

[...]
>>> VERIFYING CHECKSUMS
> [...]
> 
> [DBs and concurrency ...]
> [...]
> 
> I'm not replying to those parts in this email.

heh, me and stsp are also coming up with new directions by the hour.

We were discussing that having a separate pristine database basically sucks.
We need to ensure atomicity of mv-into-place with write-db-row.

This would be more straightforward if we had no DB, but instead an
information header in each pristine file itself. Either that header would
have fixed size, or (rather) we'd write the file offset of where the actual
content starts in the first few bytes.

The only thing that would remain a problem is wanting to record a pristine's
mtime. We can't write the mtime into the file itself, and hope that we are
still within the same mtime grain, not altering the real mtime of the file
*again* (think usec mtime resolution). But we agree that even storing the
mtime of a pristine is bogus. We should checksum every read anyway.

We currently have the pressing need to store *only* the md5-checksum
associated with a SHA1. I can't see why we need size or mtime when we
checksum anyway (I'm hereby taking back my own suggestion to add mtime).

That brought us into the realm of partial reads. We can't think of a case
where partial reads are even used. But if they are, we can easily introduce
a super-pristine header thing that references other pristines as chunks of
which it is made up, so that no pristine ever grows larger than, say, 10 Mb.
We've got it figured out already, and that would be easy to leave aside for
now and add later when the need arises. (Smaller pristines are still stored
the same way, but as soon as a checksum is not found, we can also look up
the set of super-headers. Writing would split up the large pristine into say
10 Mb chunks, write each one in itself, which may even coincide with
existing pristine chunks, and as a final step write the super-header into a
separate location. Easy as pie.)

In a nutshell, I'd like to push a filesystem-only pristine store! No DB
required. This removes all concurrency problems of syncing the DB and the
file system, because there is no DB anymore.
(except that on windows, concurrent moves to the same location may cause one
of the callers to fail. We'd need to cover this even with a DB in place.)
_pristine_read() would open the pristine file, seek to just after the
header, and then deliver the stream to the caller.

As said, we can store any and all metadata in a header in the pristine file
itself, except the mtime. I think we should go for it, mtime being a sad
excuse of a sanity check anyway, IMHO. (We *can* store the size, given that
we use a header of pre-determinable size, but same as mtime, I wouldn't even
want to store the size anyway.)

Given that we checksum all read operations, we only want to store the MD5
sum! The initial header could simply be always fixed 32 bytes of MD5
checksum. And even this is just a speed optimization. Given that we checksum
all reads, all reads can *calculate* the MD5 sum on-the-fly. Pushing for
simplicity here.

If we want more values in the future, like compression, we introduce a skel.

Any minus-ones?

~Neels


Re: pristine store design

Posted by Julian Foad <ju...@wandisco.com>.
On Wed, 2010-03-03, Neels J Hofmeyr wrote:
> Julian Foad wrote:
> > On Thu, 2010-02-18, Neels J Hofmeyr wrote:
> >> Great, moving forward fast on pristine design questions!
> > 
> > Hi Neels.
> > 
> > Did you start working the new knowledge into a document?  Lots of stuff
> > was said in this thread and it would be useful to see where we are at.
> 
> thanks for poking :)

No problem. I'm glad you're working on this.

Please go ahead with this pristine store. Delete the "_write" interface.
Implement the path-based ones; at least they're already declared. It's
really important to get it moving.

I want us to be able to move on to bigger things like considering
whether to build a "pristine whole nodes" store on top of the "pristine
texts" store, because I think we should be able to reference a whole
node (especially a tree-conflict old/theirs/mine node) with a single
handle, whether that handle be a checksum or a "repos:rev:path" triple.

I continue to argue below why I think a stream-based interface is better
than path-based, but the choice of "write" method is not a critical
decision, as long as it stays within libsvn_wc. I'm not keen to spend
more time on that, now that I've looked and as far as I can tell it
doesn't need to be exposed outside libsvn_wc.


> > I have a couple of comments.
> > 
> > 
> > THE PRISTINE-WRITE API
> > 
> > I was thinking about the "write" API and how an API designed around a
> > stream is surely better than one designed around "tell me the path where
> > I can put a file".
> > 
> > The objection to "give me a writable stream and I'll write to it" was
> > that the stream close handler wouldn't know whether the stream was
> > closed after a successful write or because of an error.  We can rectify
> > this by adding a second step: require the caller to call a special
> > "commit" API to close the stream on success, and any other way of
> > closing the stream would abandon the new content.
> > 
> >   // Caller passes the checksum if it knows it, or passes NULL and
> >   // the store in that case will calculate the checksum.
> >   stream = pristine_start_new_file(expected_checksum);
> > 
> >   [caller writes to stream]
> > 
> >   // Now the store commits the new text, verifies the checksum
> >   // (if it was given an expected one) and returns it.
> >   new_checksum = pristine_close_new_file(stream);
> 
> Let's also look at the advantages of the current design of
> svn_wc__db_pristine_get_tempdir() and _install():
>  
> pseudocode:
> [[[
>  pristine_get_tempdir(&tempdir)
> 
>  /* Make tempfile */
>  svn_stream_open_unique(&tempstream, &tempfile_path, tempdir)
> 
>  /* Write and checksum */
>  tempstream = svn_stream_checksummed2(tempstream, &write_checksum)
>  write to and close tempstream
> 
>  pristine_install(tempfile_path, write_checksum)
> ]]]
> 
> When there is only a write-stream available, some options get lost, while
> _get_tempdir() and _install() offer the whole palette of possibilities. For
> convenience, we can offer a wrapper for the first three instructions above.
> But additionally, we can offer the possibility to determine a file location
> *on the same file system device* as the pristine store. This is useful when
> we can provide some external tool or specialized function X with a
> destination path in advance. We create a tempfile in pristine_temp_dir() and
> pass that location to X.  X writes or OS-copies or <whatever>s to the final
> device, possibly saving one copy-across-fs-devices operation per pristine.

Sure.  That's my "case (4)" of the cases I enumerated.  But I think it's
a less important case.  See my investigation of "actual uses" below,
near the end of this email.

> Also, X may already have a checksum tee in its implementation, obsoleting
> the need to calculate again. In that case it's nice that pristine_install()
> doesn't care where the checksum came from.

Sure, but, for the cases where X writes to a stream, a stream-based API
(slightly different from how I suggested) could do that too.
  
>  (Also, if we are going to
> validate the checksum on "every" read, there is no need to be paranoid about
> correctness of the checksum when writing -- we anyway have to "expect"
> corruptions to occur after any successful write.)
> 
> Note that your proposed usage is a subset of the usage provided by
> _get_temp_dir() and _install(). Your way does KISS some API complexity
> goodbye when thinking in human terms, but the OS will find the
> _get_temp_dir() and _install() simpler in some cases :P

Yes, but also the stream way allows the pristine store to grow new
features transparently - see "disadvantages" below.

> The simpler usage of above pseudocode would be:
> 
> pseudocode:
> [[[
>  /* convenience function provided by API or whomever. */
>  svn_error_t *
>  pristine_get_write_stream(stream_t **write_stream,
>                            svn_checksum_t *write_checksum,
>                            const char **temp_path)
>  {
>    pristine_get_tempdir(&tempdir)
> 
>    /* Make tempfile */
>    svn_stream_open_unique(&tempstream, &tempfile_path, tempdir)
> 
>    /* Write checksum to the checksum location provided by caller */
>    *write_stream = svn_stream_checksummed2(tempstream, write_checksum)
>  }
> 
>  ...
> 
>  /* calling code */
>  {
>    pristine_get_write_stream(&stream, &write_checksum, &stream_temp_path)
>    write to and close stream
>    if (had priori checksum and does not match write_checksum):
>      bail
>    pristine_install(stream_temp_path, write_checksum)
>  }
> ]]]
> 
> This is similar to what you propose,

Yes, and that looks neater, but still has all the problems caused by
exposing the path.

>  when considering that your
> implementation would also need a baton to pass the stream temp path along
> (right?).

The API wouldn't need an extra baton parameter. It would return a stream
whose internal "baton" (user data) stores any metadata it needs.

>  So IMHO it boils down to: Do you think it is better to opaquify
> such baton for the sacrifice of not being able to get a write destination on
> the target device in advance?

Yes, I think that is the better API for general use. (Note that the
stream would always write to a file that is on the destination device.
The only thing you can't get with this API is a path to that file (or
directory).)


Now let's look at some disadvantages of "return a directory path".

If the caller creates the file, the caller chooses the file's name. We
have to trust the caller to use the right kind of creation functions to
give a safely unique name.

If the caller creates the file, the pristine store can't keep track of
what's in its temporary directory. Does it matter? Maybe not, yet.

If the caller creates the file, the caller chooses the file's
permissions. The pristine store loses the ability to control privacy.
Does it matter? Maybe not, yet.

If the caller writes to the file, the pristine store doesn't have a
streamy way to compress the data if it wants to - it would have to read
it again. Does it matter? Maybe we never will, or maybe we'll want to
change the API anyway when we support compressed texts so it wouldn't
matter.

If the path is exposed just within libsvn_wc, these issues stay under
our control, so that's OK. If the path is exposed in a public API, to
libsvn_client and beyond, that's when I worry.


The other thing we can do is look at the actual uses and see what would
be best for them.

  * svn_wc_add_repos_file4() is a public API that takes (as an input
parameter) the new pristine contents as a stream and writes it to the
pristine store, among other things.

  * update_editor.c:apply_textdelta() gets a readable stream of the
existing text base file, and a writable stream to a new (temporary) text
base file, and passes the two streams to svn_txdelta_apply(). Presumably
some other function then moves the temp base file to the real base path.

It looks like it would be slightly easier and more "natural" for both of
those functions to get a writable pristine stream than to create an
intermediate file itself and then wrap it in a stream. Not a big deal,
perhaps.


> I vote for removing _pristine_write() and for keeping _get_temp_dir() and
> _install(), plus adding a convenience function in the spirit of above
> pseudocode to make the stream-only case sit comfortably.
> 
> Yay?
> 
> > 
> > Now let's examine the ways in which a caller might want to give new
> > content to the store:
> > 
> >   1. Caller asks for a writable stream and pushes content to that, then
> > calls a "commit" function.
> > 
> >   2. Caller has a readable stream and wants the store to pull from that.
> > 
> >   3. Caller has a (non-temporary) file and wants the store to read from
> > that file.
> > 
> >   4. Caller has to create a temporary file for reasons beyond its
> > control (output of an external tool perhaps) and wants the store to take
> > the entire file by an atomic move if possible. This is the case where it
> > would be more efficient if it know where to put the file in the first
> > place.
> > 
> > The caller can easily implement 2 and 3 in terms of an API that provides
> > 1, so that just leaves 1 and 4 that are worthwhile as an API.
> > 
> > I feel that (1) is by far the more important one to have, and (4) is a
> > specialist optimisation.
> 
> ...which may nevertheless come up and is not that different in its
> implementation, IMHO. As above. Internal API.


> > VERIFYING CHECKSUMS
[...]

[DBs and concurrency ...]
[...]

I'm not replying to those parts in this email.

- Julian


Re: pristine store design

Posted by Neels J Hofmeyr <ne...@elego.de>.
Julian Foad wrote:
> On Thu, 2010-02-18, Neels J Hofmeyr wrote:
>> Great, moving forward fast on pristine design questions!
> 
> Hi Neels.
> 
> Did you start working the new knowledge into a document?  Lots of stuff
> was said in this thread and it would be useful to see where we are at.

thanks for poking :)

> I have a couple of comments.
> 
> 
> THE PRISTINE-WRITE API
> 
> I was thinking about the "write" API and how an API designed around a
> stream is surely better than one designed around "tell me the path where
> I can put a file".
> 
> The objection to "give me a writable stream and I'll write to it" was
> that the stream close handler wouldn't know whether the stream was
> closed after a successful write or because of an error.  We can rectify
> this by adding a second step: require the caller to call a special
> "commit" API to close the stream on success, and any other way of
> closing the stream would abandon the new content.
> 
>   // Caller passes the checksum if it knows it, or passes NULL and
>   // the store in that case will calculate the checksum.
>   stream = pristine_start_new_file(expected_checksum);
> 
>   [caller writes to stream]
> 
>   // Now the store commits the new text, verifies the checksum
>   // (if it was given an expected one) and returns it.
>   new_checksum = pristine_close_new_file(stream);

Let's also look at the advantages of the current design of
svn_wc__db_pristine_get_tempdir() and _install():

pseudocode:
[[[
 pristine_get_tempdir(&tempdir)

 /* Make tempfile */
 svn_stream_open_unique(&tempstream, &tempfile_path, tempdir)

 /* Write and checksum */
 tempstream = svn_stream_checksummed2(tempstream, &write_checksum)
 write to and close tempstream

 pristine_install(tempfile_path, write_checksum)
]]]

When there is only a write-stream available, some options get lost, while
_get_tempdir() and _install() offer the whole palette of possibilities. For
convenience, we can offer a wrapper for the first three instructions above.
But additionally, we can offer the possibility to determine a file location
*on the same file system device* as the pristine store. This is useful when
we can provide some external tool or specialized function X with a
destination path in advance. We create a tempfile in pristine_temp_dir() and
pass that location to X.  X writes or OS-copies or <whatever>s to the final
device, possibly saving one copy-across-fs-devices operation per pristine.

Also, X may already have a checksum tee in its implementation, obsoleting
the need to calculate again. In that case it's nice that pristine_install()
doesn't care where the checksum came from. (Also, if we are going to
validate the checksum on "every" read, there is no need to be paranoid about
correctness of the checksum when writing -- we anyway have to "expect"
corruptions to occur after any successful write.)

Note that your proposed usage is a subset of the usage provided by
_get_temp_dir() and _install(). Your way does KISS some API complexity
goodbye when thinking in human terms, but the OS will find the
_get_temp_dir() and _install() simpler in some cases :P

The simpler usage of above pseudocode would be:

pseudocode:
[[[
 /* convenience function provided by API or whomever. */
 svn_error_t *
 pristine_get_write_stream(stream_t **write_stream,
                           svn_checksum_t *write_checksum,
                           const char **temp_path)
 {
   pristine_get_tempdir(&tempdir)

   /* Make tempfile */
   svn_stream_open_unique(&tempstream, &tempfile_path, tempdir)

   /* Write checksum to the checksum location provided by caller */
   *write_stream = svn_stream_checksummed2(tempstream, write_checksum)
 }

 ...

 /* calling code */
 {
   pristine_get_write_stream(&stream, &write_checksum, &stream_temp_path)
   write to and close stream
   if (had priori checksum and does not match write_checksum):
     bail
   pristine_install(stream_temp_path, write_checksum)
 }
]]]

This is similar to what you propose, when considering that your
implementation would also need a baton to pass the stream temp path along
(right?). So IMHO it boils down to: Do you think it is better to opaquify
such baton for the sacrifice of not being able to get a write destination on
the target device in advance?

I vote for removing _pristine_write() and for keeping _get_temp_dir() and
_install(), plus adding a convenience function in the spirit of above
pseudocode to make the stream-only case sit comfortably.

Yay?

> 
> Now let's examine the ways in which a caller might want to give new
> content to the store:
> 
>   1. Caller asks for a writable stream and pushes content to that, then
> calls a "commit" function.
> 
>   2. Caller has a readable stream and wants the store to pull from that.
> 
>   3. Caller has a (non-temporary) file and wants the store to read from
> that file.
> 
>   4. Caller has to create a temporary file for reasons beyond its
> control (output of an external tool perhaps) and wants the store to take
> the entire file by an atomic move if possible. This is the case where it
> would be more efficient if it know where to put the file in the first
> place.
> 
> The caller can easily implement 2 and 3 in terms of an API that provides
> 1, so that just leaves 1 and 4 that are worthwhile as an API.
> 
> I feel that (1) is by far the more important one to have, and (4) is a
> specialist optimisation.

...which may nevertheless come up and is not that different in its
implementation, IMHO. As above. Internal API.

> 
> 
> VERIFYING CHECKSUMS
> 
> I didn't read everything you were discussing but I got worried by
> hearing about providing options for the caller to request checksums to
> be verified or not per call.  That sounds like too much complexity.  I'm
> sure we should start with a global compile-time verification enable
> switch, and if we really find we need more fine-grained control then we
> should consider how to provide it then.  It might not need an API flag:
> for example we might decide it should automatically verify on the first
> read and once in every hundred reads, or all sorts of internal
> possibilities like that.

Yes, during pristine_read(), we will want to switch on checksum validation
by default, until we find the need to do otherwise. We argued so far that
the API could checksum along internally, perform the checksum validation on
stream close, and just ignore the calculated checksum for partial reads,
which does not happen a lot.

The check mode, which I presume you are worried about, comes in when we want
to determine whether we have a valid pristine or not in various situations.
Previously, I ended up having these checkmodes:

_usable: "The pristine exists in both DB and file system and
          size and mtime match up"

_known:  "Take any one indication that a pristine exists at
          face value, do that in any way, but fast please."

_valid:  "In addition to checking DB and filesystem, read
          the whole pristine file and checksum it."

Thinking about it now, we can lose _valid. That can be done by checking
_usable and pumping the stream provided by pristine_read(). Or *only* a
pristine_read() and stream pump, even.

We were also ambiguous about _known. Some argue that it's too special, while
it makes sense to me (in case of many checks done for heuristics) and Greg
says he remembers to have known such a use case to exist, heh.

But I now think we should drop the enum svn_wc__db_checkmode_t entirely.
Let's provide the _usable check as a single function in 1.7. If we find the
need, we can add a faster check in a later release, or we can even make this
single check function faster by never checking mtime and len (except when
_read()ing).

Having gone that far, one could argue that we need no _check function at
all, we can just have pristine_read(). If it returns a stream, it indicates
existence and usability, just close it and be merry. Since _usable will
anyway cause disk I/O when we decide to check mtime and size via fstat, the
argument that we want a check function that causes no disk I/O is half-hearted.
On the other hand, if we were only having a _read() API function, we would
want to have a convenience function that closes the stream for those callers
that just want _usable. In this case, the convenience function would provide
practically the same API as providing a separate _check() function in the
first place, just slightly less optimal (causing file preread instead of
just fstat traffic). It would also blur the option of easily making all the
check() use cases faster by a central handle. Some more pseudocode to
illustrate:

No check() function:

  pristine_read(stream_t **stream):
    if (static_check_mtime_and_len() == match):
      *stream = <open checksumming stream>

  convenience_pristine_check(svn_boolean_t *exists):
    pristine_read(&stream)
    *exists = (stream != NULL)
    if (stream):
      <close stream>            <-- no need to have opened it


With check() function in the API:

  pristine_read(stream_t **stream):
    /* same as above */

  pristine_check(svn_boolean_t *exists):
    *exists = (static_check_mtime_and_len() == match)


I still favor the explicit check() function included in the API and keep
with my above suggestion for 1.7. We can provide a second, faster check
function later or even make the single check function faster.

> 
> 
>> The one thing left now is:
>>> Can someone explain a motivation for even creating a database row before
>>> the pristine file is moved into place in the pristine store? I currently
>>> don't see why it can't be way simpler.
> [...]
> 
> I would just write it down the way you think it should be in the main
> flow of your document, and mention outstanding questions like this in
> notes.
> 
> "Simultaneous or multi-threaded clients" would be my first reaction to
> that particular question.

You guys already agreed on what I think in the other two posts, i.e. that we
just let people write concurrently. With pristine_install(), there isn't
anything that can go wrong concerning concurrency -- assuming a 'mv' is
atomic that's obvious, but even if not, the concurrent processes should
anyway write the same values to the same file offsets. (not given when we
have compressed pristines! see below)

Q: Is there any deadlock / error with concurrent OS 'mv's to the same
location? I am assuming not, but am not 100% sure. If there turns out to be
one, we can still create a lock-file write lock thang (which could also
serve to prevent two separate processes from downloading the same pristine
twice, if we choose to cover that).


However, I am now also thinking about database consistency. If one
concurrent process wins the database race, while another wins the file
system race, there may be a mismatching mtime in the database (questionable
if the mtime resolution is no less than a whole eternal second, but it still
remains possible; also, mtime currently does not exist in the schema but
possibly should). Would this problem go away if we mv the pristine file into
place while the DB transaction is open? Would SQLite mutex the two processes
apart for free? (talking just about the final 'mv' during _install())

The same problem as with mtime is more aggravating with compression. If one
process decides to compress the pristine while the other decides to write it
out plainly, we have a concurrency problem in *both* DB and on disk. We
could avoid this by having absolute per-pristine-store rules in place about
when a pristine is compressed, e.g. compress all those being larger than a
certain size. Alternatively, we could append a .gz/.bz2/.zip suffix to the
checksum filename for compressed files, doing away with concurrency problems
in the file system. It would then not matter which process wins the DB race,
but the pristine would exist twice (once compressed, once uncompressed).

We have not put any thought in implementing compression yet. I think we
should drop compression from 1.7, and plan to provide an opaque compression
mechanism behind pristine_install() based on absolute rules.

Or maybe not, because disk space is too cheap to bother and no-one has
called for a compressed pristine store because we already put some kind of
high-water mark in place. Who knows.

(I don't like pristine compression. If we're optimizing for disk space, why
store it in the first place. It makes a lot of things way more complex.)

Either way, it would be nice to not have a "locked" state in the pristine
database. E.g. if we allow the database row to be able to say "I'm busy
writing this file", then we need to decide what the other process should do
in that case. Wait indefinitely? I'd prefer not to have that, but rather
have the option for lock-file based optimization to prevent the same content
from being downloaded twice at the same time, emphasis on *option*. Lock
files are cleaned up when a process dies. Not so the DB row.



<Reminding myself that the need for MD5 sums forces us to have some storage
over and above the pristine itself. Still dreaming of a DB-less pristine
store like
  echo "content" > SHA1SUMSHA1SUMSHA1SUM
  touch MD5SUMMD5SUM
  ln -s MD5SUMMD5SUM SHA1SUMSHA1SUMSHA1SUM.md5
but that's probably nonsense. Having a DB is also better for implementing
future features.>


Comments welcome!

As you can see, reading this thread again now, a little while later, has
brought some more things to the surface. I shall cast a newer version of the
pristine API design doc I started, but my time for today is *so* over :)

*neels feels the early morning breath of a two-year-old down his sleepy neck

~Neels



Re: pristine store design

Posted by Julian Foad <ju...@btopenworld.com>.
On Thu, 2010-02-18, Neels J Hofmeyr wrote:
> Great, moving forward fast on pristine design questions!

Hi Neels.

Did you start working the new knowledge into a document?  Lots of stuff
was said in this thread and it would be useful to see where we are at.
I have a couple of comments.


THE PRISTINE-WRITE API

I was thinking about the "write" API and how an API designed around a
stream is surely better than one designed around "tell me the path where
I can put a file".

The objection to "give me a writable stream and I'll write to it" was
that the stream close handler wouldn't know whether the stream was
closed after a successful write or because of an error.  We can rectify
this by adding a second step: require the caller to call a special
"commit" API to close the stream on success, and any other way of
closing the stream would abandon the new content.

  // Caller passes the checksum if it knows it, or passes NULL and
  // the store in that case will calculate the checksum.
  stream = pristine_start_new_file(expected_checksum);

  [caller writes to stream]

  // Now the store commits the new text, verifies the checksum
  // (if it was given an expected one) and returns it.
  new_checksum = pristine_close_new_file(stream);

Now let's examine the ways in which a caller might want to give new
content to the store:

  1. Caller asks for a writable stream and pushes content to that, then
calls a "commit" function.

  2. Caller has a readable stream and wants the store to pull from that.

  3. Caller has a (non-temporary) file and wants the store to read from
that file.

  4. Caller has to create a temporary file for reasons beyond its
control (output of an external tool perhaps) and wants the store to take
the entire file by an atomic move if possible. This is the case where it
would be more efficient if it know where to put the file in the first
place.

The caller can easily implement 2 and 3 in terms of an API that provides
1, so that just leaves 1 and 4 that are worthwhile as an API.

I feel that (1) is by far the more important one to have, and (4) is a
specialist optimisation.


VERIFYING CHECKSUMS

I didn't read everything you were discussing but I got worried by
hearing about providing options for the caller to request checksums to
be verified or not per call.  That sounds like too much complexity.  I'm
sure we should start with a global compile-time verification enable
switch, and if we really find we need more fine-grained control then we
should consider how to provide it then.  It might not need an API flag:
for example we might decide it should automatically verify on the first
read and once in every hundred reads, or all sorts of internal
possibilities like that.


> The one thing left now is:
> > Can someone explain a motivation for even creating a database row before
> > the pristine file is moved into place in the pristine store? I currently
> > don't see why it can't be way simpler.
[...]

I would just write it down the way you think it should be in the main
flow of your document, and mention outstanding questions like this in
notes.

"Simultaneous or multi-threaded clients" would be my first reaction to
that particular question.

- Julian


Re: pristine store design

Posted by Neels J Hofmeyr <ne...@elego.de>.
Great, moving forward fast on pristine design questions!

The one thing left now is:
> Can someone explain a motivation for even creating a database row before
> the pristine file is moved into place in the pristine store? I currently
> don't see why it can't be way simpler.
>
> (And, if it is necessary, how does a client deal with encountering a
> pristine table row that has a SIZE==null? Idle a bit and try to wait for
> the hypothetical other client process to finish? Discard and start
> fetching the pristine, possibly again?)

We will only write/store to the pristine tempdir and then move into place.
There will be no state "busy writing". Is there a different motivation left
for the special case SIZE==null?

The rest of the relevant stuff reposted below.

~Neels

Neels J Hofmeyr wrote:
> Greg Stein wrote:
>> The schema is designed to *allow* for faulty files. The faulty file
>> will NOT be used because SIZE==null in the database.
>>
>> If the file is successfully written, *then* we store a value into
>> SIZE, indicating the file is present and correct.
>>
>> Of course, if you're overwriting a pristine file, then you better
>> store SIZE==null before you begin writing.
> 
> stsp and I have been discussing this a bit. I can't really see why
> indicating a null size in the PRISTINE table is necessary. Our discussion
> ended here:
> 
> If we always write (copy) a pristine to a tempfile in the pristine tempdir
> first and then move it into the final pristine file location, there either
> *is* a complete pristine file, or there *isn't* one at all. (assuming atomic
> 'mv' within the same filesystem device. *can that be assumed??*)
> 
> It's not difficult to prevent one client from wanting to install the same
> pristine twice within the same code path.
> 
> To prevent two concurrently running clients from installing the same
> pristine twice, a file lock seems more appropriate (with one wc.db per WC,
> benefit of even that is debatable, but with one wc.db per user that might be
> good).
> 
> Either way, a pristine can only have one specific content -- it does not
> really matter that much if one client overwrites it just after the other
> created it.


Re: pristine store design

Posted by Greg Stein <gs...@gmail.com>.
On Wed, Feb 17, 2010 at 18:32, Neels J Hofmeyr <ne...@elego.de> wrote:
>...
> +1 -- I was hoping it'd make sense to go that way.
> - "always" internally checksum streams returned by pristine_read()
>  (until proven that performance is affected significantly)
> - Allow a boolean flag to switch off this checksumming

yup...

> - _read() knows the size of the pristine from the pristine file. It
>  will skip checksum comparison on premature close.

Unless it does a stat(), it doesn't know. But that isn't need. The
checksumming stream just reads to EOF. If it never hits EOF, then it
never attempts to validate. Very simple.

>...
>>>> [ ] If the checksum is already known and the data exists in the local
>>>>     file system, there is no need to verify the checksum.
>>
>> I'm assuming you mean copying from a source in the local file system,
>> and writing that into the pristine store.
>>
>> Yes, if we have a checksum for that file, then we can just use it
>> since we (invariably) *just* computed it.
>
> Are you talking specifically about a tempfile? Because below, we all seem to
> agree that it is dangerous to compute a checksum from an Actual working copy
> file and to only copy it later. ?

Yes.

>>> That depends. If we are going to read it anyway...
>>> In most cases I agree. The filesystem also has verifications on bit errors.
>>> But you also have sed -i <.....>
>>
>> Not all filesystems do. That is why we record checksums for repository
>> contents. That "one bit error every five years" needs to be
>> detectable.
>
> ^ Further support for rather doing checksums with every read, where certain
> situations in the code get "special permission" to switch off checksumming.

I doubt working copies will suffer degradation like a server
repository, but ... yeah. Sure.

>...
>> I think a flag to pristine_read() may be the way to go.
>
> And I'd prefer to term it from the other end, as I stated above, i.e. to say
> "do checksums unless we know in advance that it makes no sense, and unless
> we know that it hits performance really hard".

Sure.

I would also have no problem with a separate function like
svn_wc__db_pristine_read_unsafely() :-)

>...
> To prevent two concurrently running clients from installing the same
> pristine twice, a file lock seems more appropriate (with one wc.db per WC,
> benefit of even that is debatable, but with one wc.db per user that might be
> good).

Eep. I hadn't considered this.

Okay. Forgot all that I've written about allowing faulty files, and
writing directly to the target location. Tempfile-then-move is best.

Thanks.

>...
>>>> [ ] It is ok to open a write stream to the final location of the
>>>>     pristine file for a given checksum, no need to store in a
>>>>     pristine-tempfile first.
>>> I think we should say no here, to guarantee a stable behavior. If the file
>>> is in the pristine store it should be OK. We can't trust the initial write
>>> to always provide the full file and a valid hash of this file.
>>> We should calculate ourselves if it is possible that we receive an
>>> incomplete file.
>>
>> The schema allows for this, so it can/should be just fine.
>
> This kinda contradicts the impression I get from you saying "_write() has to
>  go" and "we always copy to temp before/while calculating the checksum".
> (s.b. ...)

_write() just can't function properly because of the
stream-close-means-WHAT? issue. That's independent of allowing faulty
files into the store.

>>> And calculating ourselves defines that we don't know the final location.
>>
>> Usually, we assemble a file in the temp area that is detranslated. At
>> that time, we can compute the checksum. And then we install the file
>> as a pristine.
>>
>> We might have a file incoming from the repository with a known
>> checksum. We can spool that directly into the pristine store.
>
> (...) But when we receive a pristine over the network, we should surely
> verify its checksum before writing it to the final pristine file location?
>
> I tend to favor doing all partial work in the pristine tempdir and OS-moving
> into place once the file is complete.

Agreed (now), for the multi-process issue.

>...
>>> ...
>>>> SHA1/MD5 compat.
>>>> [ ] When talking to an old server, we use only MD5 checksums to reference
>>>>     the pristine in the pristine store, nevermind hash collisions.
>>
>> If we don't have a SHA1 handy, then I don't mind this. But I think we
>> should store stuff using *only* MD5 or *only* SHA1. Mixing them could
>> end up with duplicates. Not sure if that is a problem, but it feels
>> like it could be.
>
> I was hoping to get a -1 on this. To me it feels preferable to make the
> pristine store *always* use SHA1 for the hash index. I'd be totally against
> having a mixed hash index. Given that streaming to create a checksum when
> receiving from the repos should be cheap, let's only use SHA1 indexes?

That's fine. Just saying I don't mind either way, as long as we stick
to *one* form of checksums.

>>> ...
>>>> [ ] When talking to an old server, we use SHA1 to index the pristine
>>>>     store and also store the MD5 checksum for server comm. We create the
>>>>     SHA1 checksum locally after having verified the MD5 checksum.
>>> +1. This is the original WC-NG plan
>>
>> I wouldn't go *that* far. There was definitely some hand-waving going
>> on. The MD5 in the editor API is a severely complicating item. I had
>> hoped to fix that particular problem with Ev2.
>
> ...so you disagree.

nono... was just disagreeing with Bert's assertion that it was "the
original WC-NG plan".

> What about md5 collisions? Are they unlikely enough?
> Also, with only SHA1 in use, we don't need to maintain code that figures out
> which kind of checksum is used in a pristine store.
>
> What say you?

My assumption is that we'll figure out how to get a SHA-1 for any file
we wish to install, despite the Editor API problems, and (thus) we'll
use SHA-1 for the index. And that further means that we'll store MD5's
into the metadata store.

But if you *can't* always get a SHA1 easily, and determine it would be
easier *today* to use MD5 for the indexes? Fine.

If we can get Ev2 into 1.7 and solve some of these problems? Awesomeness.

>>>> [ ] When talking to a 1.7 server, we will receive and use only SHA1
>>>>     checksums and don't store any MD5 checksums.
>>> There is currently no delta editor upgrade for 1.7, so we still have to send
>>> MD5 to our 1.7 server as it is now. And to wrap old editors with new editors
>>> (and reversed) we probably have to send both hashes whenever possible.
>>> (The repository filesystem already stores SHA1 hashes since 1.6 or ?)
>>
>> I think we need to keep MD5 checksums around, in addition to the SHA1
>> for compat with the Editor v1 APIs. Sigh.
>
> Group sigh.

Bah. You're just thinking too small. Work on Editor v2!!

... hehehe

Actually, I suspect that we *may* want to use Ev2 in one or two places
to make our lives manageable. Not a full conversion of all editors.
Just a targeted, surgical replacement of (say) the update editor.

Cheers,
-g

Re: pristine store design

Posted by Neels J Hofmeyr <ne...@elego.de>.
Greg Stein wrote:
> On Wed, Feb 17, 2010 at 08:09, Bert Huijben <be...@qqmail.nl> wrote:
>> ...
>>> [ ] It is cheap to tee to a checksumming stream when reading a
>>>     stored pristine. The I/O is much slower anyway.
>> When we are reading the complete stream: Yes.
>> I would skip verification if we only do a partial read (if possible).
> 
> That's my belief, but testing can/should confirm. I imagine an SSD
> "disk" and a good OS buffer cache might actually be pretty damned
> fast, which would then lead to a checksum being a "noticable"
> percentage of reading the stream.
> 
> Of course, we're usually doing *something* with that stream as we read
> it, and that invariably is to write it somewhere else (temp file,
> network, etc).
> 
>>> [ ] It is expensive to *always* want to tee to a checksumming stream,
>>>     because that defies speed gain when wanting to read just a subsection
>>>     of a pristine, and defies using OS copy without de-/translation to put
>>>     a pristine's copy into the WC.
>> See previous answer
> 
> I doubt we read portions all that often. My naive approach would have
> pristine_read() return a checksumming stream. *IF* the stream is read
> to completion, then it verifies the result. If the stream is closed
> early (due to partial-read), then we just don't validate.
> 
> That said... if "always checksumming" proves to be a bit expensive
> overall, then we may want to be strategic about *when* to do a
> checksum. That would imply a flag to pristine_read() asking it to do a
> checksum as we read. (and for known partial-reads, we just set the
> flag to FALSE).

+1 -- I was hoping it'd make sense to go that way.
- "always" internally checksum streams returned by pristine_read()
  (until proven that performance is affected significantly)
- Allow a boolean flag to switch off this checksumming
- _read() knows the size of the pristine from the pristine file. It
  will skip checksum comparison on premature close.

> 
>>> [ ] We don't care about optimizing for reading subsections of a pristine.
>>>     We "always" read the whole pristine anyway.
>> Not sure.
>> We certainly don't read the entire file if we are only trying to check if a
>> file has changed or not. (1st byte in a 2GB file has changed?)
> 
> Right. I think this kind of goes to "we may want to be strategic about
> when to do a checksum verification"
> 
>>> [ ] If the checksum is already known and the data exists in the local
>>>     file system, there is no need to verify the checksum.
> 
> I'm assuming you mean copying from a source in the local file system,
> and writing that into the pristine store.
> 
> Yes, if we have a checksum for that file, then we can just use it
> since we (invariably) *just* computed it.

Are you talking specifically about a tempfile? Because below, we all seem to
agree that it is dangerous to compute a checksum from an Actual working copy
file and to only copy it later. ?

> 
>> That depends. If we are going to read it anyway...
>> In most cases I agree. The filesystem also has verifications on bit errors.
>> But you also have sed -i <.....>
> 
> Not all filesystems do. That is why we record checksums for repository
> contents. That "one bit error every five years" needs to be
> detectable.

^ Further support for rather doing checksums with every read, where certain
situations in the code get "special permission" to switch off checksumming.

> 
>>> [ ] If the checksum is already known and the data exists in the local
>>>     file system, we still have to verify the checksum again via a tempfile
>>>     unless that local file already *is* a tempfile (and is thus reasonably
>>>     protected from accidental modification before we finish our copy).
>> Agree. Any process can change files in the WC at any time. Even if we
>> checksummed and then moved we have a chance of failure.
> 
> Yup. Note that we pretty much *always* copy a source file into a temp
> area. During that copy, we can checksum and (de)translate the thing.
> These kinds of file copies occur all over the WC.
> 
>> ...
>>> [ ] We are totally fine with just checking size (and maybe mtime) of
>>>     pristines locally, no need to *always* do checksumming when reading.
>> +1.
>> Just check where it doesn't impact performance. (E.g. incoming updates that
>> read the whole file anyway)
> 
> I think a flag to pristine_read() may be the way to go.

And I'd prefer to term it from the other end, as I stated above, i.e. to say
"do checksums unless we know in advance that it makes no sense, and unless
we know that it hits performance really hard".

> 
>>> Pristine check.
>>> Do we need a "fast" check? Note that it doesn't need to say how it's
>>> implemented; just say whether you think we need a presence check that
>>> tries
>>> to be as fast as possible by assuming the pristine store is consistent.
>>> Greg said there is a use case for that lurking, so I suggest keeping it in
>>> the design doc but marking it for post-1.7. Yes?
> 
> Sure. I think the question that comes us is, "am I missing this
> pristine?"  Would have to dig more to remember where/why that comes
> up.
> 
>>> Write.
>>> Julian said: there possibly should be only _write(), a simple API that
>> takes
>>> care of the rest internally.
>>> Greg said: _write() has to go away, it has no way of telling whether the
>>> write stream was interrupted by error or ended successfully.
>>> Greg also said: It is fine to write directly to a pristine file location.
>>> Which are/should be true?
> 
> Write does have to go away. No getting around that, and I won't
> support further changes to the stream API to "fix" that issue. We've

+1

> already made the streams more complicated than I think they should be
> (the recent: reset, mark, seek, and line functions). They used to just
> be read/write/close. Grr.
> 
>>> [ ] We will validate pristines when reading anyway, so we can neglect
>>>     being paranoid about writing to pristine files without losing safety.
>> We should not write faulty files. If somebody opens the stream he assumes
>> the file is ok and on some OSs he keeps a lock on the file while he as
>> reading so nobody can repair it. (And on other OSs the file should never
>> change while it is open)
> 
> The schema is designed to *allow* for faulty files. The faulty file
> will NOT be used because SIZE==null in the database.
> 
> If the file is successfully written, *then* we store a value into
> SIZE, indicating the file is present and correct.
> 
> Of course, if you're overwriting a pristine file, then you better
> store SIZE==null before you begin writing.

stsp and I have been discussing this a bit. I can't really see why
indicating a null size in the PRISTINE table is necessary. Our discussion
ended here:

If we always write (copy) a pristine to a tempfile in the pristine tempdir
first and then move it into the final pristine file location, there either
*is* a complete pristine file, or there *isn't* one at all. (assuming atomic
'mv' within the same filesystem device. *can that be assumed??*)

It's not difficult to prevent one client from wanting to install the same
pristine twice within the same code path.

To prevent two concurrently running clients from installing the same
pristine twice, a file lock seems more appropriate (with one wc.db per WC,
benefit of even that is debatable, but with one wc.db per user that might be
good).

Either way, a pristine can only have one specific content -- it does not
really matter that much if one client overwrites it just after the other
created it.

Can someone explain any motivation for even creating a database row before
the pristine file is moved into place in the pristine store? I currently
don't see why it can't be way simpler.

(And, if it is necessary, how does a client deal with encountering a
pristine table row that has a SIZE==null? Idle a bit and try to wait for the
hypothetical other client process to finish? Discard and start fetching the
pristine, possibly again? A file lock has the benefit of disappearing if its
client process dies unexpectedly.)

> 
>>> [ ] It is ok to open a write stream to the final location of the
>>>     pristine file for a given checksum, no need to store in a
>>>     pristine-tempfile first.
>> I think we should say no here, to guarantee a stable behavior. If the file
>> is in the pristine store it should be OK. We can't trust the initial write
>> to always provide the full file and a valid hash of this file.
>> We should calculate ourselves if it is possible that we receive an
>> incomplete file.
> 
> The schema allows for this, so it can/should be just fine.

This kinda contradicts the impression I get from you saying "_write() has to
 go" and "we always copy to temp before/while calculating the checksum".
(s.b. ...)

> 
>> And calculating ourselves defines that we don't know the final location.
> 
> Usually, we assemble a file in the temp area that is detranslated. At
> that time, we can compute the checksum. And then we install the file
> as a pristine.
> 
> We might have a file incoming from the repository with a known
> checksum. We can spool that directly into the pristine store.

(...) But when we receive a pristine over the network, we should surely
verify its checksum before writing it to the final pristine file location?

I tend to favor doing all partial work in the pristine tempdir and OS-moving
into place once the file is complete.

> 
>> ...
>>> [ ] However, we do not provide an API function for that. The only way
>>>     to create a pristine (for now) will be via _tempdir() and _install().
>> +1
> 
> I see no reason to limit it this way.

(Does this confuse me in the same way I said above, with _write()-must-go
vs. allow-direct-writing? Or is this another confusion? I'd love to limit it
this way, noting that a file can be cp/mv'd to the _tempdir().)

> 
>>> [ ] But we will likely see a need at some point, upon which such API
>>>     will be added. We will change _write() so that it can tell the
>>>     difference between successful and unsuccessful stream closure.
> 
> -1

Nice, was hoping that. Thanks.

> 
>> ...
>>> [ ] Callers can also pass any other file locations to _install(), to
>>>     facilitate OS-copying/moving into the pristine store without de-/
>>>     translation (when the checksum is known beforehand).
>> At which API level do we trust the callers?
> 
> This would be a wc_db API, and (thus) trustable within WC.
> 
> The APIs for pristine management provided as the WC public API... none
> beyond "read", I think.

I see agreement.

> 
>>> [ ] ^ ... copying ...
>>> [ ] ^ ... moving ...
>> There are not that many operations where this is actually used. Maybe after
>> a commit? The pristine store is mostly read-only and no apis should deliver
>> the file locations; just streams.
> 
> Absolutely never a path. That killed us in wc-1.

...overwhelming agreement.

When I said 'copying' / 'moving' I was trying to poke you to say something
like "_install() always does a move, never a copy, and it always assumes to
get a (disposable) tempfile in the pristine tempdir". Does that sound right?

> 
>>> Separate pristine store?
>> ...
>> So: design needed
> 
> Yah. Post-1.7, I say. For now, the pristine store and wc.db are tied
> on a 1:1 basis, at the root of each working copy.

Agreed.

> 
>> ...
>>> SHA1/MD5 compat.
>>> [ ] When talking to an old server, we use only MD5 checksums to reference
>>>     the pristine in the pristine store, nevermind hash collisions.
> 
> If we don't have a SHA1 handy, then I don't mind this. But I think we
> should store stuff using *only* MD5 or *only* SHA1. Mixing them could
> end up with duplicates. Not sure if that is a problem, but it feels
> like it could be.

I was hoping to get a -1 on this. To me it feels preferable to make the
pristine store *always* use SHA1 for the hash index. I'd be totally against
having a mixed hash index. Given that streaming to create a checksum when
receiving from the repos should be cheap, let's only use SHA1 indexes?

> 
>> ...
>>> [ ] When talking to an old server, we use SHA1 to index the pristine
>>>     store and also store the MD5 checksum for server comm. We create the
>>>     SHA1 checksum locally after having verified the MD5 checksum.
>> +1. This is the original WC-NG plan
> 
> I wouldn't go *that* far. There was definitely some hand-waving going
> on. The MD5 in the editor API is a severely complicating item. I had
> hoped to fix that particular problem with Ev2.

...so you disagree. What about md5 collisions? Are they unlikely enough?
Also, with only SHA1 in use, we don't need to maintain code that figures out
which kind of checksum is used in a pristine store.

What say you?

> 
>>> [ ] When talking to a 1.7 server, we will receive and use only SHA1
>>>     checksums and don't store any MD5 checksums.
>> There is currently no delta editor upgrade for 1.7, so we still have to send
>> MD5 to our 1.7 server as it is now. And to wrap old editors with new editors
>> (and reversed) we probably have to send both hashes whenever possible.
>> (The repository filesystem already stores SHA1 hashes since 1.6 or ?)
> 
> I think we need to keep MD5 checksums around, in addition to the SHA1
> for compat with the Editor v1 APIs. Sigh.

Group sigh.

~Neels


Re: pristine store design

Posted by Greg Stein <gs...@gmail.com>.
On Wed, Feb 17, 2010 at 08:09, Bert Huijben <be...@qqmail.nl> wrote:
>...
>> [ ] It is cheap to tee to a checksumming stream when reading a
>>     stored pristine. The I/O is much slower anyway.
> When we are reading the complete stream: Yes.
> I would skip verification if we only do a partial read (if possible).

That's my belief, but testing can/should confirm. I imagine an SSD
"disk" and a good OS buffer cache might actually be pretty damned
fast, which would then lead to a checksum being a "noticable"
percentage of reading the stream.

Of course, we're usually doing *something* with that stream as we read
it, and that invariably is to write it somewhere else (temp file,
network, etc).

>> [ ] It is expensive to *always* want to tee to a checksumming stream,
>>     because that defies speed gain when wanting to read just a subsection
>>     of a pristine, and defies using OS copy without de-/translation to put
>>     a pristine's copy into the WC.
> See previous answer

I doubt we read portions all that often. My naive approach would have
pristine_read() return a checksumming stream. *IF* the stream is read
to completion, then it verifies the result. If the stream is closed
early (due to partial-read), then we just don't validate.

That said... if "always checksumming" proves to be a bit expensive
overall, then we may want to be strategic about *when* to do a
checksum. That would imply a flag to pristine_read() asking it to do a
checksum as we read. (and for known partial-reads, we just set the
flag to FALSE).

>> [ ] We don't care about optimizing for reading subsections of a pristine.
>>     We "always" read the whole pristine anyway.
> Not sure.
> We certainly don't read the entire file if we are only trying to check if a
> file has changed or not. (1st byte in a 2GB file has changed?)

Right. I think this kind of goes to "we may want to be strategic about
when to do a checksum verification"

>> [ ] If the checksum is already known and the data exists in the local
>>     file system, there is no need to verify the checksum.

I'm assuming you mean copying from a source in the local file system,
and writing that into the pristine store.

Yes, if we have a checksum for that file, then we can just use it
since we (invariably) *just* computed it.

> That depends. If we are going to read it anyway...
> In most cases I agree. The filesystem also has verifications on bit errors.
> But you also have sed -i <.....>

Not all filesystems do. That is why we record checksums for repository
contents. That "one bit error every five years" needs to be
detectable.

>> [ ] If the checksum is already known and the data exists in the local
>>     file system, we still have to verify the checksum again via a tempfile
>>     unless that local file already *is* a tempfile (and is thus reasonably
>>     protected from accidental modification before we finish our copy).
> Agree. Any process can change files in the WC at any time. Even if we
> checksummed and then moved we have a chance of failure.

Yup. Note that we pretty much *always* copy a source file into a temp
area. During that copy, we can checksum and (de)translate the thing.
These kinds of file copies occur all over the WC.

>...
>> [ ] We are totally fine with just checking size (and maybe mtime) of
>>     pristines locally, no need to *always* do checksumming when reading.
> +1.
> Just check where it doesn't impact performance. (E.g. incoming updates that
> read the whole file anyway)

I think a flag to pristine_read() may be the way to go.

>> Pristine check.
>> Do we need a "fast" check? Note that it doesn't need to say how it's
>> implemented; just say whether you think we need a presence check that
>> tries
>> to be as fast as possible by assuming the pristine store is consistent.
>> Greg said there is a use case for that lurking, so I suggest keeping it in
>> the design doc but marking it for post-1.7. Yes?

Sure. I think the question that comes us is, "am I missing this
pristine?"  Would have to dig more to remember where/why that comes
up.

>> Write.
>> Julian said: there possibly should be only _write(), a simple API that
> takes
>> care of the rest internally.
>> Greg said: _write() has to go away, it has no way of telling whether the
>> write stream was interrupted by error or ended successfully.
>> Greg also said: It is fine to write directly to a pristine file location.
>> Which are/should be true?

Write does have to go away. No getting around that, and I won't
support further changes to the stream API to "fix" that issue. We've
already made the streams more complicated than I think they should be
(the recent: reset, mark, seek, and line functions). They used to just
be read/write/close. Grr.

>> [ ] We will validate pristines when reading anyway, so we can neglect
>>     being paranoid about writing to pristine files without losing safety.
> We should not write faulty files. If somebody opens the stream he assumes
> the file is ok and on some OSs he keeps a lock on the file while he as
> reading so nobody can repair it. (And on other OSs the file should never
> change while it is open)

The schema is designed to *allow* for faulty files. The faulty file
will NOT be used because SIZE==null in the database.

If the file is successfully written, *then* we store a value into
SIZE, indicating the file is present and correct.

Of course, if you're overwriting a pristine file, then you better
store SIZE==null before you begin writing.

>> [ ] It is ok to open a write stream to the final location of the
>>     pristine file for a given checksum, no need to store in a
>>     pristine-tempfile first.
> I think we should say no here, to guarantee a stable behavior. If the file
> is in the pristine store it should be OK. We can't trust the initial write
> to always provide the full file and a valid hash of this file.
> We should calculate ourselves if it is possible that we receive an
> incomplete file.

The schema allows for this, so it can/should be just fine.

> And calculating ourselves defines that we don't know the final location.

Usually, we assemble a file in the temp area that is detranslated. At
that time, we can compute the checksum. And then we install the file
as a pristine.

We might have a file incoming from the repository with a known
checksum. We can spool that directly into the pristine store.

>...
>> [ ] However, we do not provide an API function for that. The only way
>>     to create a pristine (for now) will be via _tempdir() and _install().
> +1

I see no reason to limit it this way.

>> [ ] But we will likely see a need at some point, upon which such API
>>     will be added. We will change _write() so that it can tell the
>>     difference between successful and unsuccessful stream closure.

-1

>...
>> [ ] Callers can also pass any other file locations to _install(), to
>>     facilitate OS-copying/moving into the pristine store without de-/
>>     translation (when the checksum is known beforehand).
> At which API level do we trust the callers?

This would be a wc_db API, and (thus) trustable within WC.

The APIs for pristine management provided as the WC public API... none
beyond "read", I think.

>
>> [ ] ^ ... copying ...
>> [ ] ^ ... moving ...
> There are not that many operations where this is actually used. Maybe after
> a commit? The pristine store is mostly read-only and no apis should deliver
> the file locations; just streams.

Absolutely never a path. That killed us in wc-1.

>> Separate pristine store?
>...
> So: design needed

Yah. Post-1.7, I say. For now, the pristine store and wc.db are tied
on a 1:1 basis, at the root of each working copy.

>...
>> SHA1/MD5 compat.
>> [ ] When talking to an old server, we use only MD5 checksums to reference
>>     the pristine in the pristine store, nevermind hash collisions.

If we don't have a SHA1 handy, then I don't mind this. But I think we
should store stuff using *only* MD5 or *only* SHA1. Mixing them could
end up with duplicates. Not sure if that is a problem, but it feels
like it could be.

>...
>> [ ] When talking to an old server, we use SHA1 to index the pristine
>>     store and also store the MD5 checksum for server comm. We create the
>>     SHA1 checksum locally after having verified the MD5 checksum.
> +1. This is the original WC-NG plan

I wouldn't go *that* far. There was definitely some hand-waving going
on. The MD5 in the editor API is a severely complicating item. I had
hoped to fix that particular problem with Ev2.

>> [ ] When talking to a 1.7 server, we will receive and use only SHA1
>>     checksums and don't store any MD5 checksums.
>
> There is currently no delta editor upgrade for 1.7, so we still have to send
> MD5 to our 1.7 server as it is now. And to wrap old editors with new editors
> (and reversed) we probably have to send both hashes whenever possible.
> (The repository filesystem already stores SHA1 hashes since 1.6 or ?)

I think we need to keep MD5 checksums around, in addition to the SHA1
for compat with the Editor v1 APIs. Sigh.

>...

Cheers,
-g

RE: pristine store design

Posted by Bert Huijben <be...@qqmail.nl>.
> -----Original Message-----
> From: Neels J Hofmeyr [mailto:neels@elego.de]
> Sent: woensdag 17 februari 2010 13:29
> To: dev@subversion.apache.org
> Subject: Re: pristine store design
> 
> Thanks for the numerous replies! I'd like the design document to soak them
> all up, and to that end have a few questions (misunderstandings?) to
clarify.
> 
> 
> Verification upon using a pristine.
> Which of these are/should be true?
> [ ] We want to make sure that there is no way that a corrupted pristine
>     can cause faulty content to be successfully committed to a repository.

I don't think we can get at 100% safety, but where it is cheap to verify I
think we should perform verification.

> [ ] We want to make sure that there is no way that a corrupted pristine
>     can affect the 'actual' working copy files.
If possible without great performance impact: Yes

> [ ] It is cheap to tee to a checksumming stream when reading a
>     stored pristine. The I/O is much slower anyway.
When we are reading the complete stream: Yes.
I would skip verification if we only do a partial read (if possible).

> [ ] It is expensive to *always* want to tee to a checksumming stream,
>     because that defies speed gain when wanting to read just a subsection
>     of a pristine, and defies using OS copy without de-/translation to put
>     a pristine's copy into the WC.
See previous answer

> [ ] We don't care about optimizing for reading subsections of a pristine.
>     We "always" read the whole pristine anyway.
Not sure.
We certainly don't read the entire file if we are only trying to check if a
file has changed or not. (1st byte in a 2GB file has changed?)

> [ ] If the checksum is already known and the data exists in the local
>     file system, there is no need to verify the checksum.
That depends. If we are going to read it anyway...
In most cases I agree. The filesystem also has verifications on bit errors.
But you also have sed -i <.....> 

> [ ] If the checksum is already known and the data exists in the local
>     file system, we still have to verify the checksum again via a tempfile
>     unless that local file already *is* a tempfile (and is thus reasonably
>     protected from accidental modification before we finish our copy).
Agree. Any process can change files in the WC at any time. Even if we
checksummed and then moved we have a chance of failure.

> [ ] Checking size and mtime is a basic check, but it allows for crafted,
>     coincidentally-matching-fstat or hw failure corruptions. We don't want
>     that to be possible, so we will make sure that any corruption will
>     be caught at *some* point in the code path.
It also finds that occasional search and replace touching the pristine
store.

> [ ] We are totally fine with just checking size (and maybe mtime) of
>     pristines locally, no need to *always* do checksumming when reading.
+1. 
Just check where it doesn't impact performance. (E.g. incoming updates that
read the whole file anyway)

> Pristine check.
> Do we need a "fast" check? Note that it doesn't need to say how it's
> implemented; just say whether you think we need a presence check that
> tries
> to be as fast as possible by assuming the pristine store is consistent.
> Greg said there is a use case for that lurking, so I suggest keeping it in
> the design doc but marking it for post-1.7. Yes?
> 
> 
> Write.
> Julian said: there possibly should be only _write(), a simple API that
takes
> care of the rest internally.
> Greg said: _write() has to go away, it has no way of telling whether the
> write stream was interrupted by error or ended successfully.
> Greg also said: It is fine to write directly to a pristine file location.
> Which are/should be true?
> [ ] We will validate pristines when reading anyway, so we can neglect
>     being paranoid about writing to pristine files without losing safety.
We should not write faulty files. If somebody opens the stream he assumes
the file is ok and on some OSs he keeps a lock on the file while he as
reading so nobody can repair it. (And on other OSs the file should never
change while it is open)

> [ ] It is ok to open a write stream to the final location of the
>     pristine file for a given checksum, no need to store in a
>     pristine-tempfile first.
I think we should say no here, to guarantee a stable behavior. If the file
is in the pristine store it should be OK. We can't trust the initial write
to always provide the full file and a valid hash of this file. 
We should calculate ourselves if it is possible that we receive an
incomplete file.

And calculating ourselves defines that we don't know the final location.

(So +1 on greg's _write() should go)

> [ ] However, we do not provide an API function for that. The only way
>     to create a pristine (for now) will be via _tempdir() and _install().
+1

> [ ] But we will likely see a need at some point, upon which such API
>     will be added. We will change _write() so that it can tell the
>     difference between successful and unsuccessful stream closure.

How would you do that?
Pool cleanup closes streams, etc. But is a stream close successful?

> [ ] Callers can also pass any other file locations to _install(), to
>     facilitate OS-copying/moving into the pristine store without de-/
>     translation (when the checksum is known beforehand).
At which API level do we trust the callers?

> [ ] ^ ... copying ...
> [ ] ^ ... moving ...
There are not that many operations where this is actually used. Maybe after
a commit? The pristine store is mostly read-only and no apis should deliver
the file locations; just streams.

> Separate pristine store?
> The current design envisions multiple working copies per wc.db. This
> suggests that a pristine store be closely tied to a wc.db.
> Which is/should be true?
> [ ] It is likely that we need to separate a pristine store from a wc.db
>     once we want to move to a system wide pristine store.
Don't know. A wc.db without a workingcopy is possible

> [ ] A system wide pristine store is a whole other ballgame. There will
>     always be a pristine store tied to a wc.db.
Not sure. Designing a system wide pristine store has huge security impact.
Not sure if we really want to do this for 1.8 or later. 
I think this needs a dedicated server design...

So: design needed

> [ ] They are currently tied. We are not prepared/able/willing to say
>     anything else right now. We'll just go with the flow.

+1 on that.

> SHA1/MD5 compat.
> [ ] When talking to an old server, we use only MD5 checksums to reference
>     the pristine in the pristine store, nevermind hash collisions.
-1

That would be MD5 only in 1.7 as the editor hasn't changed. And we will see
collisions until at least a few years after we release the first major
revision with a new RA api.

> [ ] When talking to an old server, we use SHA1 to index the pristine
>     store and also store the MD5 checksum for server comm. We create the
>     SHA1 checksum locally after having verified the MD5 checksum.
+1. This is the original WC-NG plan

> [ ] When talking to a 1.7 server, we will receive and use only SHA1
>     checksums and don't store any MD5 checksums.

There is currently no delta editor upgrade for 1.7, so we still have to send
MD5 to our 1.7 server as it is now. And to wrap old editors with new editors
(and reversed) we probably have to send both hashes whenever possible.
(The repository filesystem already stores SHA1 hashes since 1.6 or ?)

> 
> 
> Thanks for your insights/opinions/check marks.
> 
> 
> (I have noted that these things should soak into the doc:
> - clarify which parts are 1.7 and which are beyond.
> - clarify use cases WRT which API layer is doing what (client vs. wc).
> - different use case distinction than "store"/"new"/"fetch".
> - when to use which method of pristine verification.
> - need db for backwards compat (md5).
> - how the PRISTINE table's size column works.
> - how closely the pristine store is/will be tied to wc.db.
> - incorporate 'repair' in 'check(_usable)'.
> - something like a "high-water mark" is not designed yet.
> - maybe think through the transition of pristine store use.)
> 
> BTW, I've seen my use case descriptions more like a list of general
> situations, not as something specific to the internal pristine API.
> ...needs to be clarified. :)
> 
> Thanks,
> ~Neels
> 
> 
> Neels J Hofmeyr wrote:
> > Hi all,
> >
> > taking stock of the current state of the pristine store API and finding
> > design docs missing, I have created a "design paper" to clarify.
> >
> > 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()
> > - 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
> >


Re: pristine store design

Posted by Neels J Hofmeyr <ne...@elego.de>.
Thanks for the numerous replies! I'd like the design document to soak them
all up, and to that end have a few questions (misunderstandings?) to clarify.


Verification upon using a pristine.
Which of these are/should be true?
[ ] We want to make sure that there is no way that a corrupted pristine
    can cause faulty content to be successfully committed to a repository.
[ ] We want to make sure that there is no way that a corrupted pristine
    can affect the 'actual' working copy files.
[ ] It is cheap to tee to a checksumming stream when reading a
    stored pristine. The I/O is much slower anyway.
[ ] It is expensive to *always* want to tee to a checksumming stream,
    because that defies speed gain when wanting to read just a subsection
    of a pristine, and defies using OS copy without de-/translation to put
    a pristine's copy into the WC.
[ ] We don't care about optimizing for reading subsections of a pristine.
    We "always" read the whole pristine anyway.
[ ] If the checksum is already known and the data exists in the local
    file system, there is no need to verify the checksum.
[ ] If the checksum is already known and the data exists in the local
    file system, we still have to verify the checksum again via a tempfile
    unless that local file already *is* a tempfile (and is thus reasonably
    protected from accidental modification before we finish our copy).
[ ] Checking size and mtime is a basic check, but it allows for crafted,
    coincidentally-matching-fstat or hw failure corruptions. We don't want
    that to be possible, so we will make sure that any corruption will
    be caught at *some* point in the code path.
[ ] We are totally fine with just checking size (and maybe mtime) of
    pristines locally, no need to *always* do checksumming when reading.


Pristine check.
Do we need a "fast" check? Note that it doesn't need to say how it's
implemented; just say whether you think we need a presence check that tries
to be as fast as possible by assuming the pristine store is consistent.
Greg said there is a use case for that lurking, so I suggest keeping it in
the design doc but marking it for post-1.7. Yes?


Write.
Julian said: there possibly should be only _write(), a simple API that takes
care of the rest internally.
Greg said: _write() has to go away, it has no way of telling whether the
write stream was interrupted by error or ended successfully.
Greg also said: It is fine to write directly to a pristine file location.
Which are/should be true?
[ ] We will validate pristines when reading anyway, so we can neglect
    being paranoid about writing to pristine files without losing safety.
[ ] It is ok to open a write stream to the final location of the
    pristine file for a given checksum, no need to store in a
    pristine-tempfile first.
[ ] However, we do not provide an API function for that. The only way
    to create a pristine (for now) will be via _tempdir() and _install().
[ ] But we will likely see a need at some point, upon which such API
    will be added. We will change _write() so that it can tell the
    difference between successful and unsuccessful stream closure.
[ ] Callers can also pass any other file locations to _install(), to
    facilitate OS-copying/moving into the pristine store without de-/
    translation (when the checksum is known beforehand).
[ ] ^ ... copying ...
[ ] ^ ... moving ...


Separate pristine store?
The current design envisions multiple working copies per wc.db. This
suggests that a pristine store be closely tied to a wc.db.
Which is/should be true?
[ ] It is likely that we need to separate a pristine store from a wc.db
    once we want to move to a system wide pristine store.
[ ] A system wide pristine store is a whole other ballgame. There will
    always be a pristine store tied to a wc.db.
[ ] They are currently tied. We are not prepared/able/willing to say
    anything else right now. We'll just go with the flow.


SHA1/MD5 compat.
[ ] When talking to an old server, we use only MD5 checksums to reference
    the pristine in the pristine store, nevermind hash collisions.
[ ] When talking to an old server, we use SHA1 to index the pristine
    store and also store the MD5 checksum for server comm. We create the
    SHA1 checksum locally after having verified the MD5 checksum.
[ ] When talking to a 1.7 server, we will receive and use only SHA1
    checksums and don't store any MD5 checksums.



Thanks for your insights/opinions/check marks.


(I have noted that these things should soak into the doc:
- clarify which parts are 1.7 and which are beyond.
- clarify use cases WRT which API layer is doing what (client vs. wc).
- different use case distinction than "store"/"new"/"fetch".
- when to use which method of pristine verification.
- need db for backwards compat (md5).
- how the PRISTINE table's size column works.
- how closely the pristine store is/will be tied to wc.db.
- incorporate 'repair' in 'check(_usable)'.
- something like a "high-water mark" is not designed yet.
- maybe think through the transition of pristine store use.)

BTW, I've seen my use case descriptions more like a list of general
situations, not as something specific to the internal pristine API.
...needs to be clarified. :)

Thanks,
~Neels


Neels J Hofmeyr wrote:
> Hi all,
> 
> taking stock of the current state of the pristine store API and finding
> design docs missing, I have created a "design paper" to clarify.
> 
> 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()
> - 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
> 


Re: pristine store database -- was: pristine store design

Posted by Neels J Hofmeyr <ne...@elego.de>.
Commenting on myself...

Neels J Hofmeyr wrote:
> Philip Martin wrote:
>> Neels J Hofmeyr <ne...@elego.de> writes:
>>
>>> 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).
>> I'm not sure whether you are planning one table per pristine store or
>> one table per working copy, but I think it's one per pristine store.
>> Obviously it doesn't makes no difference until pristine stores can be
>> shared (and it might be one per directory in the short term depending
>> on when stop being one database per directory).
> 
> Thanks for that. This is the tip of an iceberg called 'a pristine store does
> not equal a working copy [root]'.
> 
> The question is how to store the PRISTINE table (also see below) once it
> serves various working copies. Will we have a separate SQLite db store, and
> create a new file system entity called 'pristine store' that the user can
> place anywhere, like a working copy?
> 
> We could also keep pristine store and working copy welded together, so that
> one working copy can use the pristine store of another working copy, and
> that a 'pristine store' that isn't used as a working copy is just a
> --depth=empty checkout of any folder URL of that repository. It practically
> has the same effect as completely separating pristine stores from working
> copies (there is another SQLite store somewhere else), but we can just
> re-use the WC API, no need to have a separate pristine *store* API (create
> new store, contact local store database, indicate a store location, checking
> presence given a location, etc.).

If we have a single wc.db per user, we can also easily have a single
pristine store per user. Until then, we'll probably better use a separate
pristine store per WC...?

How to tackle a system-wide pristine store also has to cope with write
permissions, so that may be a different thing entirely (like a local service
daemon instead of a publicly writable file system location...)

> 
>>> 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)
>> I'm prepared to believe a database query can be faster that stat when
>> the inode cache is cold, but what about when the inode cache is hot?
> 
> Also thanks for this!
> 
> I don't know that much about database/file system benchmarks, let alone on
> different platforms. My initial classifications are mostly guessing, mixed
> with provocative prodding to wake up more experienced devs ;)
> 
> I'm also not really aware how expensive it is to calculate a checksum while
> reading a stream for other purposes. How much cpu time does it add if the
> file I/O would happen anyway? Is it neglectable?
> 
> I guess we'll ultimately have to just try out what performs best.
> 
>> If the database query requires even one system call then it could well
>> be slower.  Multiple processes accessing a working copy, or writing to
>> the pristine store, might bias this further towards stat being faster,
>> If we decide to share the pristine store between several working
>> copies then a shared database could become a bottleneck.
>>
>> [...]
>>
>>> 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()
>>
>> I think this is the most important case from a performance point of
>> view.  This is what 'svn status' et al. use, and it's important for
>> GUIs as a lot of the "feel" depends on how fast a process can query
>> the metadata.
> 
> Agreed.
> 
>> If we were to do away with the PRISTINE table, then we would not have
>> to worry about it becoming a bottleneck.  We don't need the existance
>> check if we are just about to open the file, since opening the file
>> proves that it exists.
> 
> <rant>Yes, I meant that, semantically, there has to be an existence check.
> You're right that it is gotten for free from opening the file. It's still
> important to note where the antenna sits that detects non-existence.</rant>
> 
>> We obviously have the checksum already, from
>> the BASE/WORKING table, so we only need the PRISTINE table for the
>> size/mtime.  Perhaps we could store those in the BASE/WORKING table
>> and eliminate the PRISTINE table, or is this too much of a layering
>> violation?  The pristine store is then just a sharded directory, into
>> which we move files and from which we read files.
> 
> -1
> 
> While we could store size&mtime in the BASE/WORKING tables, this causes size
> and mtime to be stored multiple times (whereever a pristine is referenced)
> and involves editing multiple entries when a pristine is removed/added due
> to high-water-mark or repair. That would be nothing less than horrible.
> Taking one step away from that, each working copy should have a dedicated
> table that stores size and mtime only once. Then we still face the situation
> that size and mtime are stored multiple times (once per working copy), and
> where, if a central pristine store is restructured, every working copy has
> to be updated. Bad idea.
> 
> Instead, we could not store size and mtime at all! :)

A big BUT is that we also need to store and send the MD5 checksum for
backwards compatibility with older servers/clients. So we'll definitely need
a database until 2.0, because of the MD5 compat alone.

We also currently have a 'compressed' flag stored, which allows optionally
compressing pristines. I think it's debatable if that is really useful. The
pristine store should be *fast* and, ideally, random-access-able. Opening a
decompression stream is kind of versus that; it's optimising for disk space,
and that's inherently not what the pristine store is for. I'd lose it.

~Neels

> 
> They are merely half-checks for validity. During normal operation, size and
> mtime should never change, because we don't open write streams to pristines.
> If anyone messes with the pristine store accidentally, we would pick it up
> with the size, or if that stayed the same, with the mtime. But we can pick
> up all cases of bitswaps/disk failure *only* by verifying *full checksum
> validity*!
> 
> So, while checking size and mtime gives a sense of basic sanity, it is
> really just a puny excuse for not checking full checksum validity. If we
> really care about correctness of pristines, *every* read of a pristine
> should verify the checksum along the way. (That would include to always read
> the complete pristine, even if just a few lines along the middle are needed)
> 
> * neels dreams of disks that hardware-checksum on-the-fly
> 
> If I further follow my dream of us emulating such hardware, we would store
> checksums for sub-chunks of each pristine, so that we can read small
> sections of pristines, being sure that the given section is correct without
> having to read the whole pristine.
> 
> Whoa, look where you got me now! ;)
> 
> I think it's a very valid question. Chuck the mtime and size, thus get rid
> of the PRISTINE table, thus do away with checking for any inconsistency
> between table and file system, also do away with possible database
> bottlenecks, and reduce the location of the pristine store to a mere local
> abspath. We have the checksum, we have the filename. Checking mtime and
> length protects against accidental editing of the pristine files. But any
> malicious or hw-failure corruption can in fact be *protected* by keeping
> mtime and length intact! ("hey, we checked it, it must be correct.")
> 
> Let's play through a corrupted pristine (with unchanged mtime/length). This
> is just theoretical...
> 
> Commit modification:
> 
> - User makes a checkout / revert / update that uses a locally
>   corrupted pristine. The corrupted pristine thus sits in the WC.
> 
> - User makes a text mod
> 
> - User commits
> 
> - Client/network layer communicate the *delta* between the local pristine
>   and the local mod to the repository, and the checksum of the modified
>   text.
> 
> - Repos applies the delta to the intact pristine it has in *its* store.
> 
> - Repos finds the resulting checksum to be *different* from the client's
>   checksum, because the underlying pristine was corrupt.
> 
> --> Yay! No need to do *ANY* local verification at all!!
> 
> Of course, in case the client/network layer decide to send the full text
> instead of a delta, the corruption is no longer detected. :(
> 
> 
> Merge and commit:
> 
> - User makes a merge that uses a locally corrupted pristine.
> 
> - The merge *delta* applied to the working copy is incorrect.
> 
> - User does not note the corruption (e.g. via --accept=mine-full)
> 
> - User commits
> 
> - Repos accepts the changes based on the corrupted pristine that was
>   used to get the merge delta, because it can't tell the difference
>   from a normal modification.
> 
> --> My goodness, merge needs to check pristine validity on each read,
>     as if it wasn't slow enough. But as discussed above, even if merge
>     checked mtime and length, it would not necessarily detect disk failure
>     and crafted malicious corruption.
> 
> 
> Thanks, Philip.
> 
> I'm now challenging the need to store mtime and length, and a need to do
> more checksumming instead. The checksumming overhead could be smaller than
> the database bottleneck slew.
> 
> For future optimisation, I'm also suggesting pristines should have
> additionally stored checksums for small chunks of each pristine, while still
> being indexed by the full checksum.
> (Which may imply a db again :/ , but that db would only be hit if we're
> trying to save time by reading just a small bit of the pristine)
> 
> Everyone, please prove me wrong!
> 
> Thanks,
> ~Neels
> 


Re: pristine store database -- was: pristine store design

Posted by "Hyrum K. Wright" <hy...@mail.utexas.edu>.
On Feb 16, 2010, at 10:52 PM, Neels J Hofmeyr wrote:

> Greg Stein wrote:
>> On Tue, Feb 16, 2010 at 16:22, Johan Corveleyn <jc...@gmail.com> wrote:
>>> OTOH, I guess a 0 bytes pristine has to be handled specially anyway
>>> (what's the checksum of 0 bytes), no?
> 
> SHA1: da39a3ee5e6b4b0d3255bfef95601890afd80709
> MD5: d41d8cd98f00b204e9800998ecf8427e
> 
> ;)

And we even special case these values in libsvn_subr:

static const unsigned char svn_sha1__empty_string_digest_array[] = {
  0xda, 0x39, 0xa3, 0xee, 0x5e, 0x6b, 0x4b, 0x0d, 0x32, 0x55,
  0xbf, 0xef, 0x95, 0x60, 0x18, 0x90, 0xaf, 0xd8, 0x07, 0x09
};

static const unsigned char svn_md5__empty_string_digest_array[] = {
  212, 29, 140, 217, 143, 0, 178, 4, 233, 128, 9, 152, 236, 248, 66, 126
};

-Hyrum

Re: pristine store database -- was: pristine store design

Posted by Neels J Hofmeyr <ne...@elego.de>.
Greg Stein wrote:
> On Tue, Feb 16, 2010 at 16:22, Johan Corveleyn <jc...@gmail.com> wrote:
>> OTOH, I guess a 0 bytes pristine has to be handled specially anyway
>> (what's the checksum of 0 bytes), no?

SHA1: da39a3ee5e6b4b0d3255bfef95601890afd80709
MD5: d41d8cd98f00b204e9800998ecf8427e

;)

> 
> Oops. You're right. I meant a null column value, as I documented in
> the schema file.

It *is* kind of useless to store an empty pristine :)
But given that empty files don't happen often in version control it could be
just as silly to special-case it at all.

~Neels


Re: pristine store database -- was: pristine store design

Posted by Greg Stein <gs...@gmail.com>.
On Tue, Feb 16, 2010 at 16:22, Johan Corveleyn <jc...@gmail.com> wrote:
> On Tue, Feb 16, 2010 at 8:15 PM, Greg Stein <gs...@gmail.com> wrote:
>>>> Instead, we could not store size and mtime at all! :)
>>>
>>> Or we could store both to perform simple consistency checks...
>>
>> Dunno about that, but the storage of SIZE is part of the (intended)
>> algorithm for pristine storage. It is allowed to have a row in
>> PRISTINE with SIZE==0 in order to say "I know about this pristine, and
>> this row is present to satisfy integrity constraints with other
>> tables, but the pristine has NOT been written into the store." Once
>> the file *is* written, then the resulting size is stored into the
>> table.
>
> Shouldn't the marker value to indicate "pristine has NOT been written
> into the store" be something like -1 instead of 0? Just taking into
> account that there might be files that really have a size of 0 bytes.
> These should be supported, shouldn't they?
>
> OTOH, I guess a 0 bytes pristine has to be handled specially anyway
> (what's the checksum of 0 bytes), no?

Oops. You're right. I meant a null column value, as I documented in
the schema file.

Cheers,
-g

Re: pristine store database -- was: pristine store design

Posted by Johan Corveleyn <jc...@gmail.com>.
On Tue, Feb 16, 2010 at 8:15 PM, Greg Stein <gs...@gmail.com> wrote:
>>> Instead, we could not store size and mtime at all! :)
>>
>> Or we could store both to perform simple consistency checks...
>
> Dunno about that, but the storage of SIZE is part of the (intended)
> algorithm for pristine storage. It is allowed to have a row in
> PRISTINE with SIZE==0 in order to say "I know about this pristine, and
> this row is present to satisfy integrity constraints with other
> tables, but the pristine has NOT been written into the store." Once
> the file *is* written, then the resulting size is stored into the
> table.

Shouldn't the marker value to indicate "pristine has NOT been written
into the store" be something like -1 instead of 0? Just taking into
account that there might be files that really have a size of 0 bytes.
These should be supported, shouldn't they?

OTOH, I guess a 0 bytes pristine has to be handled specially anyway
(what's the checksum of 0 bytes), no?

Johan

Re: pristine store database -- was: pristine store design

Posted by Greg Stein <gs...@gmail.com>.
Meta-comment: all of these issues that you're bringing up are
*exactly* why I wanted to punt the issue of external-to-WC stores out
of 1.7. Keeping a 1:1 correspondence of pristine stores to working
copies keeps the problem tractable, especially given all the other
work that is needed.

On Tue, Feb 16, 2010 at 09:58, Bert Huijben <be...@qqmail.nl> wrote:
>...
> The idea was not to move just the pristine store, but also wc.db to a
> central location.

Yup. There were also some comments of separable locations of the
wc.db: one where you keep your metadata (e.g. home dir), and one for
the pristines (e.g. /var/svn). I never liked that idea, but reference
it for completeness sake.

As Bert noted in his response, the schema is designed to manage
multiple working copies.

>...
>> Instead, we could not store size and mtime at all! :)
>
> Or we could store both to perform simple consistency checks...

Dunno about that, but the storage of SIZE is part of the (intended)
algorithm for pristine storage. It is allowed to have a row in
PRISTINE with SIZE==0 in order to say "I know about this pristine, and
this row is present to satisfy integrity constraints with other
tables, but the pristine has NOT been written into the store." Once
the file *is* written, then the resulting size is stored into the
table.

> A query over checksum from BASE_NODE and WORKING_NODE + older_checksum,
> left_checksum  and right_checksum from ACTUAL_NODE would give a list from
> all PRISTINE records that are in-use.
> The rest can safely be deleted if diskspace is required.

Yes. That was the design goal.

it gets more complicated when you have a centralized wc.db and one or
more of the working copies are offline (e.g. removable storage,
network unavailable, etc). Again, these questions are why a
centralized concept has been punted for this generation.

>...
>> So, while checking size and mtime gives a sense of basic sanity, it is
>> really just a puny excuse for not checking full checksum validity. If we
>> really care about correctness of pristines, *every* read of a pristine
>> should verify the checksum along the way. (That would include to always

Since the pristine design returns a *stream* on the pristine, then we
can always insert a checksumming stream in order to verify the
contents. I believe the bottleneck will be I/O, so performing a
checksum should be Just Fine. If the stream is read to completion,
then we can validate the checksum (and don't worry about partial
reads; that isn't all that common, I believe).

Note that we'd only have to insert a single checksum stream, not SHA1 *and* MD5.

Also, since I/O is the (hypothetical) bottleneck, this is also why
compression is handy.

>...
> This is cheap to detect. If we have to read the file anyway, we can just
> recalculate the hash via the stream hash apis. The disk IO for reading the
> file is the real pain with current CPUs. (At least for SHA1/MD5. Sha256 is
> still painful in my tests)
>...
> You would probably see our binary diff fail before you get here and if the
> RA layer provides a hash for the result or input file you can use that for
> verification on the streams. (See the update editor for some examples where
> we do that in one pass since 1.6)

Right, and right.

>...

Cheers,
-g

RE: pristine store database -- was: pristine store design

Posted by Bert Huijben <be...@qqmail.nl>.
> -----Original Message-----
> From: Neels J Hofmeyr [mailto:neels@elego.de]
> Sent: dinsdag 16 februari 2010 14:55
> To: dev@subversion.apache.org
> Cc: Philip Martin; Greg Stein; Hyrum Wright
> Subject: pristine store database -- was: pristine store design
> 
> Philip Martin wrote:
> > Neels J Hofmeyr <ne...@elego.de> writes:
> >
> >> 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).
> >
> > I'm not sure whether you are planning one table per pristine store or
> > one table per working copy, but I think it's one per pristine store.
> > Obviously it doesn't makes no difference until pristine stores can be
> > shared (and it might be one per directory in the short term depending
> > on when stop being one database per directory).
> 
> Thanks for that. This is the tip of an iceberg called 'a pristine store
does
> not equal a working copy [root]'.
> 
> The question is how to store the PRISTINE table (also see below) once it
> serves various working copies. Will we have a separate SQLite db store,
and
> create a new file system entity called 'pristine store' that the user can
> place anywhere, like a working copy?

The idea was not to move just the pristine store, but also wc.db to a
central location.

In this case the .svn directory will just have a 'look there' marker,
indicating where the wc database is. (Another option would be to just write
the location in the subversion configuration, but this would make it very
hard to detect if a directory is really a working copy or just a normal
directory)

The wc.db database schema (as designed by Greg) was designed to handle
multiple working copies. (All wc related tables have a wc_id column,
indicating which working copy the record applies to).


This week some other mail talked about the performance characteristics of a
central database, but I don't think this is really relevant here

The normal situation is that there is only one (single-threaded) operation
performing changes on a working copy at a time (and possibly multiple
readers). In this situation the performance of one open database with the
Sqlite + filesystem caching support of an exclusively opened file should be
much better, than deleting and recreating our own database files everywhere
through the filesystem. The old working copy used an exclusive per directory
write lock to the same effect.

<snip>

> While we could store size&mtime in the BASE/WORKING tables, this causes
> size
> and mtime to be stored multiple times (whereever a pristine is referenced)
> and involves editing multiple entries when a pristine is removed/added due
> to high-water-mark or repair. That would be nothing less than horrible.
> Taking one step away from that, each working copy should have a dedicated
> table that stores size and mtime only once. Then we still face the
situation
> that size and mtime are stored multiple times (once per working copy), and
> where, if a central pristine store is restructured, every working copy has
> to be updated. Bad idea.

The size&mtime in BASE_NODE and WORKING_NODE don't relate to pristine data,
but to the in-WC files. If a files date and size haven't changed 'svn
status' sees the file as unmodified.

Note that the PRISTINE table currently doesn't have a mtime column. It does
have a SIZE, MD5 and COMPRESSION column to allow storing the MD5 hash for
communicating over editor-v1.0 (Needed for Subversion 1.0-1.7
compatibility).

> Instead, we could not store size and mtime at all! :)

Or we could store both to perform simple consistency checks...

A query over checksum from BASE_NODE and WORKING_NODE + older_checksum,
left_checksum  and right_checksum from ACTUAL_NODE would give a list from
all PRISTINE records that are in-use.
The rest can safely be deleted if diskspace is required.

> They are merely half-checks for validity. During normal operation, size
and
> mtime should never change, because we don't open write streams to
> pristines.
> If anyone messes with the pristine store accidentally, we would pick it up
> with the size, or if that stayed the same, with the mtime. But we can pick
> up all cases of bitswaps/disk failure *only* by verifying *full checksum
> validity*!

Good luck verifying 20 files with a total of 32 GB of data over a LAN :)

Well working over a LAN is not a design requirement for WC-NG, but a lot of
our users use NFS or CIFS... And checking via fstat is a lot cheaper than
reading all data.

> So, while checking size and mtime gives a sense of basic sanity, it is
> really just a puny excuse for not checking full checksum validity. If we
> really care about correctness of pristines, *every* read of a pristine
> should verify the checksum along the way. (That would include to always
> read
> the complete pristine, even if just a few lines along the middle are
needed)
> 
> * neels dreams of disks that hardware-checksum on-the-fly
> 
> If I further follow my dream of us emulating such hardware, we would store
> checksums for sub-chunks of each pristine, so that we can read small
> sections of pristines, being sure that the given section is correct
without
> having to read the whole pristine.
> 
> Whoa, look where you got me now! ;)
> 
> I think it's a very valid question. Chuck the mtime and size, thus get rid
> of the PRISTINE table, thus do away with checking for any inconsistency
> between table and file system, also do away with possible database
> bottlenecks, and reduce the location of the pristine store to a mere local
> abspath. We have the checksum, we have the filename. Checking mtime and
> length protects against accidental editing of the pristine files. But any
> malicious or hw-failure corruption can in fact be *protected* by keeping
> mtime and length intact! ("hey, we checked it, it must be correct.")

That would still leave MD5. Having a checksum before processing the file is
a common use-case in editor-1.0. And calculating a checksum over a really
large file and then reading it again for the operation is not cheap.

Another reason to keep this record around is supporting compression. In that
case we don't have the size by a cheap fstat anymore.

> Let's play through a corrupted pristine (with unchanged mtime/length).
This
> is just theoretical...
> 
> Commit modification:
> 
> - User makes a checkout / revert / update that uses a locally
>   corrupted pristine. The corrupted pristine thus sits in the WC.
> 
> - User makes a text mod
> 
> - User commits
> 
> - Client/network layer communicate the *delta* between the local pristine
>   and the local mod to the repository, and the checksum of the modified
>   text.
> 
> - Repos applies the delta to the intact pristine it has in *its* store.
> 
> - Repos finds the resulting checksum to be *different* from the client's
>   checksum, because the underlying pristine was corrupt.
> 
> --> Yay! No need to do *ANY* local verification at all!!
> 
> Of course, in case the client/network layer decide to send the full text
> instead of a delta, the corruption is no longer detected. :(
> 
> 
> Merge and commit:
> 
> - User makes a merge that uses a locally corrupted pristine.

This is cheap to detect. If we have to read the file anyway, we can just
recalculate the hash via the stream hash apis. The disk IO for reading the
file is the real pain with current CPUs. (At least for SHA1/MD5. Sha256 is
still painful in my tests)

> - The merge *delta* applied to the working copy is incorrect.
> 
> - User does not note the corruption (e.g. via --accept=mine-full)

You would probably see our binary diff fail before you get here and if the
RA layer provides a hash for the result or input file you can use that for
verification on the streams. (See the update editor for some examples where
we do that in one pass since 1.6)

> - User commits
> 
> - Repos accepts the changes based on the corrupted pristine that was
>   used to get the merge delta, because it can't tell the difference
>   from a normal modification.
> 
> --> My goodness, merge needs to check pristine validity on each read,
>     as if it wasn't slow enough. But as discussed above, even if merge
>     checked mtime and length, it would not necessarily detect disk failure
>     and crafted malicious corruption.

I don't know if we check .svn-base files for merges now. I know we do that
for 'svn update'. Before 1.6 introduced the stream checksum apis, this was
an additional scan, but that is not necessary anymore.

> Thanks, Philip.
> 
> I'm now challenging the need to store mtime and length, and a need to do
> more checksumming instead. The checksumming overhead could be smaller
> than
> the database bottleneck slew.

I assume a normal wc.db is read by the filesystem and harddisks read ahead
buffer for most small working copies. (If a hard drive spins around it
usually reads the next few sectors after the read operation in its internal
buffer if it has nothing better to do)

As we usually look at wc-file statuses at the same time this file should be
pretty hot in the cache. 
(and the strict locking of the db file by sqlite even allows caching
portions of this file over network connections).

	Bert

> For future optimisation, I'm also suggesting pristines should have
> additionally stored checksums for small chunks of each pristine, while
still
> being indexed by the full checksum.
> (Which may imply a db again :/ , but that db would only be hit if we're
> trying to save time by reading just a small bit of the pristine)
> 
> Everyone, please prove me wrong!
> 
> Thanks,
> ~Neels


Re: pristine store database -- was: pristine store design

Posted by Mark Mielke <ma...@mark.mielke.cc>.
On 02/16/2010 03:24 PM, Mark Mielke wrote:
> On 02/16/2010 08:54 AM, Neels J Hofmeyr wrote:
>> They are merely half-checks for validity. During normal operation, 
>> size and
>> mtime should never change, because we don't open write streams to 
>> pristines.
>> If anyone messes with the pristine store accidentally, we would pick 
>> it up
>> with the size, or if that stayed the same, with the mtime. But we can 
>> pick
>> up all cases of bitswaps/disk failure *only* by verifying *full checksum
>> validity*!
>>
>> So, while checking size and mtime gives a sense of basic sanity, it is
>> really just a puny excuse for not checking full checksum validity. If we
>> really care about correctness of pristines, *every* read of a pristine
>> should verify the checksum along the way. (That would include to 
>> always read
>> the complete pristine, even if just a few lines along the middle are 
>> needed)
>
> Checking size and mtime gives huge benefits over checking contents. 
> Size and mtime can be picked up with a single stat(), whereas a 
> checksum requires open()/read()/.../close(). The data for stat() is 
> usually stored in the inode which is read in either situation, and 
> often small enough to be easily cached. For large work spaces, 
> especially those with multi-Kbyte files, doing checksum tests on most 
> operations would result in unacceptable performance.
>
> I think it's fine to compare checksum on any files that are noticed to 
> have changed (size/mtime), but if the file looks unchanged, assuming 
> that it *is* unchanged, is a fine compromise for the performance gains.
>
> If you want a "--compare-checksum" option which does the full check 
> optionally - it might be use to some people. I suspect most people 
> would avoid using it once they see how much more expensive it is...
>

I just realized perhaps you are talking about size/mtime of the pristine 
and not of the working copy. If so, ignore the above. I see no reason to 
check the sanity of the pristine during normal operation, presuming 
there is some sort of transactional model that guarantees that 
Subversion itself will not corrupt the pristine during normal operation 
in the case of an expected failure (control-C by user, network failure, 
...). :-)

Cheers,
mark

Re: pristine store database -- was: pristine store design

Posted by Mark Mielke <ma...@mark.mielke.cc>.
On 02/16/2010 08:54 AM, Neels J Hofmeyr wrote:
> They are merely half-checks for validity. During normal operation, size and
> mtime should never change, because we don't open write streams to pristines.
> If anyone messes with the pristine store accidentally, we would pick it up
> with the size, or if that stayed the same, with the mtime. But we can pick
> up all cases of bitswaps/disk failure *only* by verifying *full checksum
> validity*!
>
> So, while checking size and mtime gives a sense of basic sanity, it is
> really just a puny excuse for not checking full checksum validity. If we
> really care about correctness of pristines, *every* read of a pristine
> should verify the checksum along the way. (That would include to always read
> the complete pristine, even if just a few lines along the middle are needed)
>    

Checking size and mtime gives huge benefits over checking contents. Size 
and mtime can be picked up with a single stat(), whereas a checksum 
requires open()/read()/.../close(). The data for stat() is usually 
stored in the inode which is read in either situation, and often small 
enough to be easily cached. For large work spaces, especially those with 
multi-Kbyte files, doing checksum tests on most operations would result 
in unacceptable performance.

I think it's fine to compare checksum on any files that are noticed to 
have changed (size/mtime), but if the file looks unchanged, assuming 
that it *is* unchanged, is a fine compromise for the performance gains.

If you want a "--compare-checksum" option which does the full check 
optionally - it might be use to some people. I suspect most people would 
avoid using it once they see how much more expensive it is...

Cheers,
mark

pristine store database -- was: pristine store design

Posted by Neels J Hofmeyr <ne...@elego.de>.
Philip Martin wrote:
> Neels J Hofmeyr <ne...@elego.de> writes:
> 
>> 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).
> 
> I'm not sure whether you are planning one table per pristine store or
> one table per working copy, but I think it's one per pristine store.
> Obviously it doesn't makes no difference until pristine stores can be
> shared (and it might be one per directory in the short term depending
> on when stop being one database per directory).

Thanks for that. This is the tip of an iceberg called 'a pristine store does
not equal a working copy [root]'.

The question is how to store the PRISTINE table (also see below) once it
serves various working copies. Will we have a separate SQLite db store, and
create a new file system entity called 'pristine store' that the user can
place anywhere, like a working copy?

We could also keep pristine store and working copy welded together, so that
one working copy can use the pristine store of another working copy, and
that a 'pristine store' that isn't used as a working copy is just a
--depth=empty checkout of any folder URL of that repository. It practically
has the same effect as completely separating pristine stores from working
copies (there is another SQLite store somewhere else), but we can just
re-use the WC API, no need to have a separate pristine *store* API (create
new store, contact local store database, indicate a store location, checking
presence given a location, etc.).

> 
>> 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)
> 
> I'm prepared to believe a database query can be faster that stat when
> the inode cache is cold, but what about when the inode cache is hot?

Also thanks for this!

I don't know that much about database/file system benchmarks, let alone on
different platforms. My initial classifications are mostly guessing, mixed
with provocative prodding to wake up more experienced devs ;)

I'm also not really aware how expensive it is to calculate a checksum while
reading a stream for other purposes. How much cpu time does it add if the
file I/O would happen anyway? Is it neglectable?

I guess we'll ultimately have to just try out what performs best.

> If the database query requires even one system call then it could well
> be slower.  Multiple processes accessing a working copy, or writing to
> the pristine store, might bias this further towards stat being faster,
> If we decide to share the pristine store between several working
> copies then a shared database could become a bottleneck.
> 
> [...]
> 
>> 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()
> 
> 
> I think this is the most important case from a performance point of
> view.  This is what 'svn status' et al. use, and it's important for
> GUIs as a lot of the "feel" depends on how fast a process can query
> the metadata.

Agreed.

> If we were to do away with the PRISTINE table, then we would not have
> to worry about it becoming a bottleneck.  We don't need the existance
> check if we are just about to open the file, since opening the file
> proves that it exists.

<rant>Yes, I meant that, semantically, there has to be an existence check.
You're right that it is gotten for free from opening the file. It's still
important to note where the antenna sits that detects non-existence.</rant>

> We obviously have the checksum already, from
> the BASE/WORKING table, so we only need the PRISTINE table for the
> size/mtime.  Perhaps we could store those in the BASE/WORKING table
> and eliminate the PRISTINE table, or is this too much of a layering
> violation?  The pristine store is then just a sharded directory, into
> which we move files and from which we read files.

-1

While we could store size&mtime in the BASE/WORKING tables, this causes size
and mtime to be stored multiple times (whereever a pristine is referenced)
and involves editing multiple entries when a pristine is removed/added due
to high-water-mark or repair. That would be nothing less than horrible.
Taking one step away from that, each working copy should have a dedicated
table that stores size and mtime only once. Then we still face the situation
that size and mtime are stored multiple times (once per working copy), and
where, if a central pristine store is restructured, every working copy has
to be updated. Bad idea.

Instead, we could not store size and mtime at all! :)

They are merely half-checks for validity. During normal operation, size and
mtime should never change, because we don't open write streams to pristines.
If anyone messes with the pristine store accidentally, we would pick it up
with the size, or if that stayed the same, with the mtime. But we can pick
up all cases of bitswaps/disk failure *only* by verifying *full checksum
validity*!

So, while checking size and mtime gives a sense of basic sanity, it is
really just a puny excuse for not checking full checksum validity. If we
really care about correctness of pristines, *every* read of a pristine
should verify the checksum along the way. (That would include to always read
the complete pristine, even if just a few lines along the middle are needed)

* neels dreams of disks that hardware-checksum on-the-fly

If I further follow my dream of us emulating such hardware, we would store
checksums for sub-chunks of each pristine, so that we can read small
sections of pristines, being sure that the given section is correct without
having to read the whole pristine.

Whoa, look where you got me now! ;)

I think it's a very valid question. Chuck the mtime and size, thus get rid
of the PRISTINE table, thus do away with checking for any inconsistency
between table and file system, also do away with possible database
bottlenecks, and reduce the location of the pristine store to a mere local
abspath. We have the checksum, we have the filename. Checking mtime and
length protects against accidental editing of the pristine files. But any
malicious or hw-failure corruption can in fact be *protected* by keeping
mtime and length intact! ("hey, we checked it, it must be correct.")

Let's play through a corrupted pristine (with unchanged mtime/length). This
is just theoretical...

Commit modification:

- User makes a checkout / revert / update that uses a locally
  corrupted pristine. The corrupted pristine thus sits in the WC.

- User makes a text mod

- User commits

- Client/network layer communicate the *delta* between the local pristine
  and the local mod to the repository, and the checksum of the modified
  text.

- Repos applies the delta to the intact pristine it has in *its* store.

- Repos finds the resulting checksum to be *different* from the client's
  checksum, because the underlying pristine was corrupt.

--> Yay! No need to do *ANY* local verification at all!!

Of course, in case the client/network layer decide to send the full text
instead of a delta, the corruption is no longer detected. :(


Merge and commit:

- User makes a merge that uses a locally corrupted pristine.

- The merge *delta* applied to the working copy is incorrect.

- User does not note the corruption (e.g. via --accept=mine-full)

- User commits

- Repos accepts the changes based on the corrupted pristine that was
  used to get the merge delta, because it can't tell the difference
  from a normal modification.

--> My goodness, merge needs to check pristine validity on each read,
    as if it wasn't slow enough. But as discussed above, even if merge
    checked mtime and length, it would not necessarily detect disk failure
    and crafted malicious corruption.


Thanks, Philip.

I'm now challenging the need to store mtime and length, and a need to do
more checksumming instead. The checksumming overhead could be smaller than
the database bottleneck slew.

For future optimisation, I'm also suggesting pristines should have
additionally stored checksums for small chunks of each pristine, while still
being indexed by the full checksum.
(Which may imply a db again :/ , but that db would only be hit if we're
trying to save time by reading just a small bit of the pristine)

Everyone, please prove me wrong!

Thanks,
~Neels


Re: pristine store design

Posted by Philip Martin <ph...@wandisco.com>.
Neels J Hofmeyr <ne...@elego.de> writes:

> 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).

I'm not sure whether you are planning one table per pristine store or
one table per working copy, but I think it's one per pristine store.
Obviously it doesn't makes no difference until pristine stores can be
shared (and it might be one per directory in the short term depending
on when stop being one database per directory).

> 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)

I'm prepared to believe a database query can be faster that stat when
the inode cache is cold, but what about when the inode cache is hot?
If the database query requires even one system call then it could well
be slower.  Multiple processes accessing a working copy, or writing to
the pristine store, might bias this further towards stat being faster,
If we decide to share the pristine store between several working
copies then a shared database could become a bottleneck.

[...]

> 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()


I think this is the most important case from a performance point of
view.  This is what 'svn status' et al. use, and it's important for
GUIs as a lot of the "feel" depends on how fast a process can query
the metadata.

If we were to do away with the PRISTINE table, then we would not have
to worry about it becoming a bottleneck.  We don't need the existance
check if we are just about to open the file, since opening the file
proves that it exists.  We obviously have the checksum already, from
the BASE/WORKING table, so we only need the PRISTINE table for the
size/mtime.  Perhaps we could store those in the BASE/WORKING table
and eliminate the PRISTINE table, or is this too much of a layering
violation?  The pristine store is then just a sharded directory, into
which we move files and from which we read files.

-- 
Philip

Re: pristine store design

Posted by Greg Stein <gs...@gmail.com>.
On Mon, Feb 15, 2010 at 08:45, Neels J Hofmeyr <ne...@elego.de> wrote:
> Hi all,
>
> taking stock of the current state of the pristine store API and finding
> design docs missing, I have created a "design paper" to clarify.
>
> 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()
> - 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.

As noted elsewhere, you can definitively figure out which pristine
files are required by scanning the "checksum" columns in the tables to
figure out which are referenced. The notion of a "high-water mark" is
not part of the current design because svn *expects* the pristines to
be present. We do not have a capability for demand-load pristines from
a foreign repository. Thus, you need "all" of the pristines, not just
"32 gig" of pristines.

>...
> 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,

For 1.7.

> 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.

For future versions.

> 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

There is a fifth mode, potentially not useful, which is SIZE==0. That
means "I know about the pristine, but do not have its contents (yet)."
(altho, it may be that the file *is* there, but a failure occurred
between its write-completion, and the update of the row in PRISTINE).

> 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.

The current design allows for writing directly into the store. If the
checksum is known beforehand, then you don't need to compute it. The
design is also intended to ignore any (partial) file when the row has
SIZE==0. Only when the file has been completely written, will SIZE be
updated, thus signifying a useful pristine.

>  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).

Not necessary.

>  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 a file comes from the repository, we "should" already know its checksum.

Maybe the current code does not, but as we rebuild this stuff... it
WILL. When fetching stuff from the repository, we *always* want to get
the checksum first. Then we can determine whether to fetch it (not in
the pristine store), or to skip the network fetch (found it in the
store).

Thus, we will always have a checksum when we begin to write a new
pristine into the store. And we already have protection against
partial writes.

>  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.

Agreed. The common case is "not present", so the design can optimize
around that.

Note that (branch) checkouts in a shared-pristine environment may want
to optimize for "present". Not something to worry about today, though.

>  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.)

Note that, in many cases, we already have checksums for most of these
files. Or it would be very easy to get the values. Many of these files
are constructed through stream copies, potentially with
(de)translation, and we can perform a checksum, too.

> 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.

Generally true, I'd think.

In "repair mode", if you find a pristine file without a database
record, then you'd probably delete the file. Recall that the record
"should" be present if it is referenced from one of the other tables
(and, thus, needed).

(of course, we generally don't have referential integrity turned on,
so it *may* be possible to delete a row from PRISTINE even when you
need it; thus, keeping the file may actually be necessary)

> 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"!

In most cases, when we do an "add" (or somesuch), we make a copy of
the file into a temporary area, potentially (de)translating that file.
At that time, we can also checksum it. No need to do further I/O (a
move) if you already have the file.

If we do a raw filesystem copy w/o detranslation, then we may not have
a checksum.

I think it would be easier to break up your use cases with what we
know about the source file, and what needs to be done to it.
Detranslation? Copy into a holding area from original source? Copied
from a version-controlled file, so we already have info about it? etc.

Each of these different types of sources will determine a data flow
into the pristine storage.

> 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".)

Does this use case imply that the pristine is NOT present already?
(because, of course, we we already have it, then we don't need to
fetch it from the repository under any situation).

> 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

Again, you may or may not need to checksum. Depends on the original
location/status of the intended pristine.

>...
> 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)

Woah. Fetching from the repository can only be done in libsvn_client.
The WC library cannot do that. Your APIs and use cases need to
consider this, depending on the scope (are you trying to define wc_db
/ pristine APIs? or public WC APIs that assist libsvn_client?).

I also don't see a need for "check" in this case. Just try to fetch
it, and have a unique error code for "I don't have it."

> 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)

Just read, and catch an error.

> 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?"
> 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

Right. This was the intent around the check() API that I designed.
Then later figured out that we'd always have a wc.db open anyways, so
the fine-tuned granularity of check options was premature.

Something like this *is* handy, though. I forget the real-world use
case for the check, but it is there.

> Use case "routine check": "I want to do some effort to validate this pristine"
> ------------------------
> pseudocode:
>  pristine_check(NULL, checksum, _valid)              (5)

I'm not sure when this would be used explicitly, rather than as a
side-effect to other operations.

I think that any explicit check would also be an explicit repair.

>...
> Use case "repair": "I've seen this pristine is børken. Restore or remove!"
> -----------------
> pseudocode:
>  pristine_repair(&present, checksum)                 (7)
>  [if !present:
>    get_pristine_from_repos(checksum, ra)            (9)
>  pristine_read(&stream, checksum)                   (6)
>  ]

I think we'd want to do this as a normal part of "svn cleanup" (and
maybe "svn upgrade").

>...
> 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.

Removal during repair is *part* of repair, and not part of the API.
Other removal should be automatic, and part of the wc_db APIs. For
example, when a BASE_NODE is deleted, we should consider removing its
pristine, too.

>...
> 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.

IMO, punt to post-1.7.

Cheers,
-g

Re: pristine store design

Posted by Greg Stein <gs...@gmail.com>.
On Mon, Feb 15, 2010 at 10:51, Julian Foad <ju...@wandisco.com> wrote:
>...
>> 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.

pristine_write() is broken and should go away. The implementation
cannot determine if the stream was closed due to *successful*
completion, or if it is being closed due to an error.

>...
>> 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.)

Yes, it *is* important. If only a stream is present, then we can
checksum as we go (if we don't have it). If a file is present, then we
could do a filesystem copy, rather than streaming operations (ie. no
detranslation or checksumming needed).

This is why I suggested the use cases focus around the source constraints.

>...
>> 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?

IIRC, the use case is more "are you *missing* <this> pristine?"
Higher-level code may need to contact a repository if certain
pristines are missing.

If the pristine is there, but unusable... that's not a likely question.

>...
> 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.

I believe so, yes, which is why I added that comment.

>...
>> 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.

Repair may also involve fetching broken entries. Of course, that isn't
possible from a pure-WC standpoint, but the repair operation (as part
of 'svn cleanup'?) will need to do that.

>...

Cheers,
-g

Re: pristine store design

Posted by Julian Foad <ju...@wandisco.com>.
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