You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Julian Foad <ju...@wandisco.com> on 2011/02/15 16:06:43 UTC
Pristine store - spec
Would anyone be able to review this spec please? I'm trying to get
straight what locking / access control rules need to be.
/*
* THE PRISTINE STORE
* ==================
*
* === Introduction ===
*
* The Pristine Store is the part of the Working Copy metadata that holds
* a local copy of the full text of the base version of each WC file.
*
* Texts in the Pristine Store are addressed only by their SHA-1 checksum.
* The Pristine Store does not track which text relates to which repository
* and revision and path. The Pristine Store does not hold pristine copies
* of directories, nor of properties.
*
* The Pristine Store data is held in
* * the 'PRISTINE' table in the SQLite Data Base (SDB), and
* * the files in the 'pristine' directory.
*
* This specification uses SDB transactions to ensure the consistency of
* writes and reads.
*
* ==== Invariants ====
*
* The operating procedures below maintain the following invariants.
* These invariants apply at all times except within the SDB txns defined
* below.
*
* * Each row in the PRISTINE table has an associated pristine text file
* that is not open for writing and is available for reading and whose
* content matches the columns 'size', 'checksum', 'md5_checksum'.
*
* ==== Operating Procedures ====
*
* The steps should be carried out in the order specified. (See rationale.)
*
* * To add a pristine, do the following inside an SDB txn:
* * Add the table row, and set the refcount as desired. If a row
* already exists, add the desired refcount to its refcount, and
* preferably verify the old row matches the new metadata.
* * Create the file. Creation should be fs-atomic, e.g. by moving a
* new file into place, so as never to orphan a partial file. If a
* file already exists, preferably leave it rather than replace it,
* and optionally verify it matches the new metadata (e.g. length).
*
* * To remove a pristine, do the following inside an SDB txn:
* * First, check refcount == 0, and abort if not.
* * Delete the table row.
* * Delete the file or move it away. (If not present, log a
* consistency error but, in a release build, return success.)
*
* * To query a pristine's existence or SDB metadata, the reader must:
* * Ensure no pristine-remove txn is in progress while querying it.
*
* * To read a pristine text, the reader must:
* * Ensure no pristine-remove txn is in progress while querying and
* opening it.
* * Ensure the pristine text remains in the store continuously from
* opening it for the duration of the read. (Perhaps by ensuring
* refcount remains >= 1 and/or by cooperating with the clean-up
* code.)
*
* ==== Rationale ====
*
* * Adding a pristine:
* * We can't add the file *before* the SDB txn takes out a lock,
* because that would leave a gap in which another process could
* see this file as an orphan and delete it.
* * Within the txn, the table row could be added after creating the
* file; it makes no difference as it will not become externally
* visible until commit. But then we would have to take out a lock
* explicitly before adding the file. Adding the row takes out a
* lock implicitly, so doing it first avoids an extra step.
* * Leaving an existing file in place is less likely to interfere with
* processes that are currently reading from the file. Replacing it
* might also be acceptable, but that would need further
* investigation.
*
* * Removing a pristine:
* * We can't remove the file *after* the SDB txn that updates the
* table, because that would leave a gap in which another process
* might re-add this same pristine file and then we would delete it.
* * Within the txn, the table row could be removed after creating the
* file, but see the rationale for adding a pristine.
* * In a typical use case for removing a pristine text, the caller
* would check the refcount before starting this txn, but
* nevertheless it may have changed and so must be checked again
* inside the txn.
*
* * In the add and remove txns, we need to acquire an SDB 'RESERVED'
* lock before adding or removing the file. This can be done by starting
* the txn with 'BEGIN IMMEDIATE' and/or by performing an SDB write (such
* as the table row update). ### Would a 'SHARED' lock be sufficient,
* and if so would it be noticably better?
*
* ==== Notes ====
*
* * This procedure can leave orphaned pristine files (files without a
* corresponding SDB row) if Subvsersion crashes. The Pristine Store
* will still operate correctly. It should be easy to teach "svn cleanup"
* to safely delete these. ### Do we need to define the clean-up
* procedure here?
*
* * This specification is conceptually simple, but requires completing disk
* operations within SDB transactions, which may make it too inefficient
* in practice. An alternative specification could use the Work Queue to
* enable more efficient processing of multiple transactions.
*
*
* REFERENCE COUNTING
* ==================
*
* The Pristine Store spec above defines how texts are added and removed
* from the store. This spec defines how the addition and removal of
* pristine text references within the WC DB are co-ordinated with the
* addition and removal of the pristine texts themselves.
*
* One requirement is to allow a pristine text to be stored some
* time before the reference to it is written into the NODES table. The
* 'commit' code path, for example, needs to store a file's new pristine
* text somewhere (and the pristine store is an obvious option) and then,
* when the commit succeeds, update the WC to reference it.
*
* Store-then-reference could be achieved by:
*
* (a) Store text outside Pristine Store. When commit succeeds, add it
* to the Pristine Store and reference it in the WC; if commit
* fails, remove the temporary text.
* (b) Store text in Pristine Store with initial ref count = 0. When
* commit succeeds, add the reference and update the ref count; if
* commit fails, optionally try to purge this pristine text.
* (c) Store text in Pristine Store with initial ref count = 1. When
* commit succeeds, add the reference; if commit fails, decrement
* the ref count and optionally try to purge it.
*
* Method (a) would require, in effect, implementing an ad-hoc temporary
* Pristine Store, which seems needless duplication of effort. It would
* also require changing the way the commit code path passes information
* around, which might be no bad thing in the long term, but the result
* would not appear to have any advantage over method (b).
*
* Method (b) plays well with automatically maintaining the ref counts
* equal to the number of in-SDB references, at the granularity of SDB
* txns. It requires an interlock between adding/deleting references and
* purging unreferenced pristines - e.g. guard each of these operations by
* a WC lock.
* * Add a pristine & reference it => any WC lock
* (To prevent purging it while adding.)
* * Unreference a pristine => no lock needed.
* * Unreference a pristine & purge-if-0 => Same as doing these separately.
* * Purge any/all refcount==0 pristines => an exclusive WC lock.
* (To prevent adding a ref while purging.)
* * If a WC lock remains after a crash, then purge refcount==0 pristines.
*
* Method (c):
* * ### Not sure about this one - haven't thought it through in detail...
* * Add a pristine & reference in separate steps => any WC lock (?)
* * Remove a reference requires ... (nothing more?)
* * Find & purge unreferenced pristines requires an exclusive WC lock.
* * Ref counts are sometimes too high while a WC lock is held, so
* uncertain after a crash if WC locks remain, so need to be re-counted
* during clean-up.
*
* We choose method (b).
*
*
* === Invariants in a Valid WC DB State ===
*
* * No pristine text, even if refcount == 0, will be deleted from the store
* as long as any process holds any WC lock in this WC.
*
* The following conditions are always true outside of a SQL txn:
*
* * The 'checksum' column in each NODES table row is either NULL or
* references a primary key in the 'pristine' table.
*
* * The 'refcount' column in each PRISTINE table row is equal to the
* number of NODES table rows whose 'checksum' column references this
* pristine row.
*
* The following conditions are always true
* outside of a SQL txn,
* when the Work Queue is empty:
* (### ?) when no WC locks are held by any process:
*
* * The 'refcount' column in a PRISTINE table row equals the number of
* NODES table rows whose 'checksum' column references that pristine row.
* It may be zero.
*
* ==== Operating Procedures ====
*
* The steps should be carried out in the order specified.
*
* * To add a pristine text reference to the WC, obtain the text and its
* checksum, and then do this while holding a WC lock:
* * Add the pristine text to the Pristine Store, setting the desired
* refcount >= 1.
* * Add the reference(s) in the NODES table.
*
* * To remove a pristine text reference from the WC, do this while holding
* a WC lock:
* * Remove the reference(s) in the NODES table.
* * Decrement the pristine text's 'refcount' column.
*
* * To purge an unreferenced pristine text, do this with an *exclusive*
* WC lock:
* * Check refcount == 0; skip if not.
* * Remove it from the pristine store.
*/
- Julian
Re: Pristine store - spec
Posted by Hyrum K Wright <hy...@hyrumwright.org>.
No comments on the content, but reading the ensuing email thread, it
may be useful to put the document in notes/wc-ng/pristines, and add
questions / comments / corrections there. It would allow folks down
the road to see all the critiques in one location, rather than reading
N mails.
</bike-shed>
-Hyrum
On Tue, Feb 15, 2011 at 3:06 PM, Julian Foad <ju...@wandisco.com> wrote:
> Would anyone be able to review this spec please? I'm trying to get
> straight what locking / access control rules need to be.
>
> /*
> * THE PRISTINE STORE
> * ==================
> *
> * === Introduction ===
> *
> * The Pristine Store is the part of the Working Copy metadata that holds
> * a local copy of the full text of the base version of each WC file.
> *
> * Texts in the Pristine Store are addressed only by their SHA-1 checksum.
> * The Pristine Store does not track which text relates to which repository
> * and revision and path. The Pristine Store does not hold pristine copies
> * of directories, nor of properties.
> *
> * The Pristine Store data is held in
> * * the 'PRISTINE' table in the SQLite Data Base (SDB), and
> * * the files in the 'pristine' directory.
> *
> * This specification uses SDB transactions to ensure the consistency of
> * writes and reads.
> *
> * ==== Invariants ====
> *
> * The operating procedures below maintain the following invariants.
> * These invariants apply at all times except within the SDB txns defined
> * below.
> *
> * * Each row in the PRISTINE table has an associated pristine text file
> * that is not open for writing and is available for reading and whose
> * content matches the columns 'size', 'checksum', 'md5_checksum'.
> *
> * ==== Operating Procedures ====
> *
> * The steps should be carried out in the order specified. (See rationale.)
> *
> * * To add a pristine, do the following inside an SDB txn:
> * * Add the table row, and set the refcount as desired. If a row
> * already exists, add the desired refcount to its refcount, and
> * preferably verify the old row matches the new metadata.
> * * Create the file. Creation should be fs-atomic, e.g. by moving a
> * new file into place, so as never to orphan a partial file. If a
> * file already exists, preferably leave it rather than replace it,
> * and optionally verify it matches the new metadata (e.g. length).
> *
> * * To remove a pristine, do the following inside an SDB txn:
> * * First, check refcount == 0, and abort if not.
> * * Delete the table row.
> * * Delete the file or move it away. (If not present, log a
> * consistency error but, in a release build, return success.)
> *
> * * To query a pristine's existence or SDB metadata, the reader must:
> * * Ensure no pristine-remove txn is in progress while querying it.
> *
> * * To read a pristine text, the reader must:
> * * Ensure no pristine-remove txn is in progress while querying and
> * opening it.
> * * Ensure the pristine text remains in the store continuously from
> * opening it for the duration of the read. (Perhaps by ensuring
> * refcount remains >= 1 and/or by cooperating with the clean-up
> * code.)
> *
> * ==== Rationale ====
> *
> * * Adding a pristine:
> * * We can't add the file *before* the SDB txn takes out a lock,
> * because that would leave a gap in which another process could
> * see this file as an orphan and delete it.
> * * Within the txn, the table row could be added after creating the
> * file; it makes no difference as it will not become externally
> * visible until commit. But then we would have to take out a lock
> * explicitly before adding the file. Adding the row takes out a
> * lock implicitly, so doing it first avoids an extra step.
> * * Leaving an existing file in place is less likely to interfere with
> * processes that are currently reading from the file. Replacing it
> * might also be acceptable, but that would need further
> * investigation.
> *
> * * Removing a pristine:
> * * We can't remove the file *after* the SDB txn that updates the
> * table, because that would leave a gap in which another process
> * might re-add this same pristine file and then we would delete it.
> * * Within the txn, the table row could be removed after creating the
> * file, but see the rationale for adding a pristine.
> * * In a typical use case for removing a pristine text, the caller
> * would check the refcount before starting this txn, but
> * nevertheless it may have changed and so must be checked again
> * inside the txn.
> *
> * * In the add and remove txns, we need to acquire an SDB 'RESERVED'
> * lock before adding or removing the file. This can be done by starting
> * the txn with 'BEGIN IMMEDIATE' and/or by performing an SDB write (such
> * as the table row update). ### Would a 'SHARED' lock be sufficient,
> * and if so would it be noticably better?
> *
> * ==== Notes ====
> *
> * * This procedure can leave orphaned pristine files (files without a
> * corresponding SDB row) if Subvsersion crashes. The Pristine Store
> * will still operate correctly. It should be easy to teach "svn cleanup"
> * to safely delete these. ### Do we need to define the clean-up
> * procedure here?
> *
> * * This specification is conceptually simple, but requires completing disk
> * operations within SDB transactions, which may make it too inefficient
> * in practice. An alternative specification could use the Work Queue to
> * enable more efficient processing of multiple transactions.
> *
> *
> * REFERENCE COUNTING
> * ==================
> *
> * The Pristine Store spec above defines how texts are added and removed
> * from the store. This spec defines how the addition and removal of
> * pristine text references within the WC DB are co-ordinated with the
> * addition and removal of the pristine texts themselves.
> *
> * One requirement is to allow a pristine text to be stored some
> * time before the reference to it is written into the NODES table. The
> * 'commit' code path, for example, needs to store a file's new pristine
> * text somewhere (and the pristine store is an obvious option) and then,
> * when the commit succeeds, update the WC to reference it.
> *
> * Store-then-reference could be achieved by:
> *
> * (a) Store text outside Pristine Store. When commit succeeds, add it
> * to the Pristine Store and reference it in the WC; if commit
> * fails, remove the temporary text.
> * (b) Store text in Pristine Store with initial ref count = 0. When
> * commit succeeds, add the reference and update the ref count; if
> * commit fails, optionally try to purge this pristine text.
> * (c) Store text in Pristine Store with initial ref count = 1. When
> * commit succeeds, add the reference; if commit fails, decrement
> * the ref count and optionally try to purge it.
> *
> * Method (a) would require, in effect, implementing an ad-hoc temporary
> * Pristine Store, which seems needless duplication of effort. It would
> * also require changing the way the commit code path passes information
> * around, which might be no bad thing in the long term, but the result
> * would not appear to have any advantage over method (b).
> *
> * Method (b) plays well with automatically maintaining the ref counts
> * equal to the number of in-SDB references, at the granularity of SDB
> * txns. It requires an interlock between adding/deleting references and
> * purging unreferenced pristines - e.g. guard each of these operations by
> * a WC lock.
> * * Add a pristine & reference it => any WC lock
> * (To prevent purging it while adding.)
> * * Unreference a pristine => no lock needed.
> * * Unreference a pristine & purge-if-0 => Same as doing these separately.
> * * Purge any/all refcount==0 pristines => an exclusive WC lock.
> * (To prevent adding a ref while purging.)
> * * If a WC lock remains after a crash, then purge refcount==0 pristines.
> *
> * Method (c):
> * * ### Not sure about this one - haven't thought it through in detail...
> * * Add a pristine & reference in separate steps => any WC lock (?)
> * * Remove a reference requires ... (nothing more?)
> * * Find & purge unreferenced pristines requires an exclusive WC lock.
> * * Ref counts are sometimes too high while a WC lock is held, so
> * uncertain after a crash if WC locks remain, so need to be re-counted
> * during clean-up.
> *
> * We choose method (b).
> *
> *
> * === Invariants in a Valid WC DB State ===
> *
> * * No pristine text, even if refcount == 0, will be deleted from the store
> * as long as any process holds any WC lock in this WC.
> *
> * The following conditions are always true outside of a SQL txn:
> *
> * * The 'checksum' column in each NODES table row is either NULL or
> * references a primary key in the 'pristine' table.
> *
> * * The 'refcount' column in each PRISTINE table row is equal to the
> * number of NODES table rows whose 'checksum' column references this
> * pristine row.
> *
> * The following conditions are always true
> * outside of a SQL txn,
> * when the Work Queue is empty:
> * (### ?) when no WC locks are held by any process:
> *
> * * The 'refcount' column in a PRISTINE table row equals the number of
> * NODES table rows whose 'checksum' column references that pristine row.
> * It may be zero.
> *
> * ==== Operating Procedures ====
> *
> * The steps should be carried out in the order specified.
> *
> * * To add a pristine text reference to the WC, obtain the text and its
> * checksum, and then do this while holding a WC lock:
> * * Add the pristine text to the Pristine Store, setting the desired
> * refcount >= 1.
> * * Add the reference(s) in the NODES table.
> *
> * * To remove a pristine text reference from the WC, do this while holding
> * a WC lock:
> * * Remove the reference(s) in the NODES table.
> * * Decrement the pristine text's 'refcount' column.
> *
> * * To purge an unreferenced pristine text, do this with an *exclusive*
> * WC lock:
> * * Check refcount == 0; skip if not.
> * * Remove it from the pristine store.
> */
>
>
> - Julian
>
>
>
Re: Pristine store - spec
Posted by Julian Foad <ju...@wandisco.com>.
On Fri, 2011-02-18, Daniel Shahaf wrote:
[...]
> In other words, the lower-layer API is oblivious of WC locks. I see.
>
> That said, I just noticed that your bullet points have both a "wc lock"
> and an "exclusive wc lock" --- I had overlooked that distinction
> earlier. I assume that an 'exclusive' lock is a recursive lock from
> the wc root and below?
Yes, that's right.
> Thanks,
>
> Daniel
> (I'm behind on following the commits@ list --- if there are relevant
> commits/milestones of the doc, feel free to direct my attention to them
> explicitly)
I committed updates in r1071729 and r1071795 so far.
- Julian
Re: Pristine store - spec
Posted by Daniel Shahaf <d....@daniel.shahaf.name>.
Julian Foad wrote on Wed, Feb 16, 2011 at 19:27:19 +0000:
> On Wed, 2011-02-16, Daniel Shahaf wrote:
> > Julian Foad wrote on Tue, Feb 15, 2011 at 15:06:43 +0000:
> > > *
> > > * Texts in the Pristine Store are addressed only by their SHA-1 checksum.
> > > * The Pristine Store does not track which text relates to which repository
> > > * and revision and path. The Pristine Store does not hold pristine copies
> > > * of directories, nor of properties.
> > > *
> > > * The Pristine Store data is held in
> > > * * the 'PRISTINE' table in the SQLite Data Base (SDB), and
> > > * * the files in the 'pristine' directory.
> > > *
> > > * This specification uses SDB transactions to ensure the consistency of
> > > * writes and reads.
> > > *
> >
> > Nit:
> > This doesn't say how this spec ensures the disk is consistent with the DB.
>
> Do you mean this intro should be more specific and say sthg like
>
> "This spec defines how the store operates so as to ensure
> * consistency between disk and DB;
> * atomicity of, and arbitration between, add and delete and read
> operations."
>
Obviously not the most critical change to make, but the proposed text
sounds good.
> > > * ==== Operating Procedures ====
> > > *
> > > * The steps should be carried out in the order specified. (See rationale.)
> > > *
> > > * * To add a pristine, do the following inside an SDB txn:
> > > * * Add the table row, and set the refcount as desired. If a row
> > > * already exists, add the desired refcount to its refcount, and
> > > * preferably verify the old row matches the new metadata.
> > > * * Create the file. Creation should be fs-atomic, e.g. by moving a
> > > * new file into place, so as never to orphan a partial file. If a
> > > * file already exists, preferably leave it rather than replace it,
> > > * and optionally verify it matches the new metadata (e.g. length).
> >
> > What happens if you crash (kill -9) between these two steps?
> >
> > (Reading ahead: I assume that in that case you'll leave a stray wc lock
> > or wq entry behind?)
>
> Not at this level of the spec. Here, all that happens is that the SDB
> txn prepares to commit a change to the table, but if we crash that txn
> would be abandoned and that change would never happen.
>
> On the other hand, if we crash after those two steps but before
> committing (finalizing) the SDB txn, then the file would exist on disk
> as an "orphan", which is harmless.
>
> Moving up a layer to the "Reference Counting" layer of the spec, then
> yes a WC lock is taken out before running this txn, so yes that WC lock
> would be left behind if we crash anywhere in this sequence (between the
> steps or before or after them).
>
Clear, thanks.
> > > * * In the add and remove txns, we need to acquire an SDB 'RESERVED'
> > > * lock before adding or removing the file. This can be done by starting
> > > * the txn with 'BEGIN IMMEDIATE' and/or by performing an SDB write (such
> > > * as the table row update). ### Would a 'SHARED' lock be sufficient,
> > > * and if so would it be noticably better?
> > > *
> >
> > Does that mean "We need an SDB lock that blocks both readers and writers"
> > in non-sqlite-specific terms?
>
> Yes.
>
OK. (Having it in non-sqlite-specific terms help follow the spec, IMO.)
> > > * ==== Notes ====
> > > *
> > > * * This procedure can leave orphaned pristine files (files without a
> > > * corresponding SDB row) if Subvsersion crashes. The Pristine Store
> > > * will still operate correctly. It should be easy to teach "svn cleanup"
> > > * to safely delete these. ### Do we need to define the clean-up
> > > * procedure here?
> > > *
> >
> > Yes please. (It bypasses some of the DB-keyed logic so I think it'll be
> > good to spell it out)
>
> Okay, will do.
>
Thanks.
> > > * REFERENCE COUNTING
> > > * ==================
> > > *
> > > * The Pristine Store spec above defines how texts are added and removed
> > > * from the store. This spec defines how the addition and removal of
> > > * pristine text references within the WC DB are co-ordinated with the
> > > * addition and removal of the pristine texts themselves.
> > > *
> > > * One requirement is to allow a pristine text to be stored some
> > > * time before the reference to it is written into the NODES table. The
> > > * 'commit' code path, for example, needs to store a file's new pristine
> > > * text somewhere (and the pristine store is an obvious option) and then,
> > > * when the commit succeeds, update the WC to reference it.
> > > *
> >
> > To clarify: I believe you mean "Needs" as it's currently designed,
> > rather than "Needs" due to the inherent semantics of a 'commit'
> > operation. (Extreme example: 'commit' of rN could leave the wc at
> > rN-1.)
>
> Yes.
>
> > > * Store-then-reference could be achieved by:
> > > *
> > > * (a) Store text outside Pristine Store. When commit succeeds, add it
> > > * to the Pristine Store and reference it in the WC; if commit
> > > * fails, remove the temporary text.
> > > * (b) Store text in Pristine Store with initial ref count = 0. When
> > > * commit succeeds, add the reference and update the ref count; if
> > > * commit fails, optionally try to purge this pristine text.
> > > * (c) Store text in Pristine Store with initial ref count = 1. When
> > > * commit succeeds, add the reference; if commit fails, decrement
> > > * the ref count and optionally try to purge it.
> > > *
> > > * Method (a) would require, in effect, implementing an ad-hoc temporary
> > > * Pristine Store, which seems needless duplication of effort. It would
> > > * also require changing the way the commit code path passes information
> > > * around, which might be no bad thing in the long term, but the result
> > > * would not appear to have any advantage over method (b).
> > > *
> > > * Method (b) plays well with automatically maintaining the ref counts
> > > * equal to the number of in-SDB references, at the granularity of SDB
> > > * txns. It requires an interlock between adding/deleting references and
> > > * purging unreferenced pristines - e.g. guard each of these operations by
> > > * a WC lock.
> > > * * Add a pristine & reference it => any WC lock
> > > * (To prevent purging it while adding.)
> > > * * Unreference a pristine => no lock needed.
> > > * * Unreference a pristine & purge-if-0 => Same as doing these separately.
> > > * * Purge any/all refcount==0 pristines => an exclusive WC lock.
> > > * (To prevent adding a ref while purging.)
> > > * * If a WC lock remains after a crash, then purge refcount==0 pristines.
> > > *
> >
> > I don't understand this paragraph. What does it propose to do in order
> > to avoid purging pristines that have refcount=0 while a commit is in
> > progress? Does it propose that 'commit' take a lock for the duration
> > from adding the pristine to incrementing its refcount?
>
> Yes: in the case of the way "commit" is currently implemented, where
> "add a pristine" comes first and then "reference it" comes later, the
> commit operation should hold a WC lock during that whole time.
>
Understood, thanks.
> > > * Method (c):
> > > * * ### Not sure about this one - haven't thought it through in detail...
> > > * * Add a pristine & reference in separate steps => any WC lock (?)
> > > * * Remove a reference requires ... (nothing more?)
> > > * * Find & purge unreferenced pristines requires an exclusive WC lock.
> > > * * Ref counts are sometimes too high while a WC lock is held, so
> > > * uncertain after a crash if WC locks remain, so need to be re-counted
> > > * during clean-up.
> > > *
> >
> > I think (c) has some good points. There's a variant, (c'), where
> > instead of overloading the refcount field you use a separate
> > refcounts_by_commitsinprogress flag; in that scheme, 'find & purge'
> > doesn't need a lock, it just needs to respect that flag.
>
> Food for thought, but I find that working carefully through these
> scenarios is quite time consuming. A large part of my aim here is to
> try to find a good scheme without having to first define all the
> possible schemes in detail. Your comments are helping me to do that.
>
Glad to help.
> > > * We choose method (b).
> > > *
> > > *
> > > * === Invariants in a Valid WC DB State ===
> > > *
> > > * * No pristine text, even if refcount == 0, will be deleted from the store
> > > * as long as any process holds any WC lock in this WC.
> > > *
> >
> > Surely you mean "any *other* process" :-)
>
> Yes - something like that, though that's still not quite right.
>
*nod* due to multi-threaded processes. Perhaps s/process/WC context object/,
or some other appropriate API entity.
> > > * The following conditions are always true outside of a SQL txn:
> > > *
> > > * * The 'checksum' column in each NODES table row is either NULL or
> > > * references a primary key in the 'pristine' table.
> > > *
> > > * * The 'refcount' column in each PRISTINE table row is equal to the
> > > * number of NODES table rows whose 'checksum' column references this
> > > * pristine row.
> > > *
> >
> > Will we have wc-checks.sql triggers enforce these?
>
> The first one is enforced by constraints defined in wc-metadata.sql.
>
> The second one is currently assisted by triggers defined in
> wc-metadata.sql but not strictly enforced. I would like to enforce it
> but haven't looked at doing so yet.
>
Sounds good.
> > > * The following conditions are always true
> > > * outside of a SQL txn,
> > > * when the Work Queue is empty:
> > > * (### ?) when no WC locks are held by any process:
> > > *
> > > * * The 'refcount' column in a PRISTINE table row equals the number of
> > > * NODES table rows whose 'checksum' column references that pristine row.
> > > * It may be zero.
> > > *
> >
> > IOW, the refcount may be zero if the work queue is non empty.
>
> No, I meant the number of refs does not necessarily match the refcount
> column if the work queue is non empty. When WQ is empty, refcount and
> number of refs always match each other and may (both together) be zero
> or more than zero.
>
I haven't re-read the >>>-quoted bullet poitns, but the >-quoted
paragraph (i.e., what you just said) sounds good.
(Hmm, there's another invariant --- if refcount>0 then the file exists
--- but I'm not sure offhand what section of the spec it belongs in.)
> > But a few pages above you said that this specification doesn't use the
> > work queue to manage the pristine files. Why is the work queue involved
> > here then? Does this spec use the work queue for the disk-tree files
> > but not for the .svn/pristine/ files?
>
> I think I've messed up this part. I'll take another look. I'm not sure
> whether the Work Queue needs to be involved at all.
>
OK.
> > > * ==== Operating Procedures ====
> > > *
> > > * The steps should be carried out in the order specified.
> > > *
> > > * * To add a pristine text reference to the WC, obtain the text and its
> > > * checksum, and then do this while holding a WC lock:
> > > * * Add the pristine text to the Pristine Store, setting the desired
> > > * refcount >= 1.
> > > * * Add the reference(s) in the NODES table.
> > > *
> >
> > So the first bullet will take an SDB lock, release it, and then the
> > reference will be added while the WC lock is held (and within a separate
> > SDB txn/lock)?
>
> Yes. That's to support cases like the current "commit" implementation.
> In certain other cases, these could be collapsed into a single txn.
>
OK.
> > > * * To remove a pristine text reference from the WC, do this while holding
> > > * a WC lock:
> > > * * Remove the reference(s) in the NODES table.
> > > * * Decrement the pristine text's 'refcount' column.
> > > *
> > > * * To purge an unreferenced pristine text, do this with an *exclusive*
> > > * WC lock:
> > > * * Check refcount == 0; skip if not.
> > > * * Remove it from the pristine store.
> >
> > Why is 'purge an unreferenced pristine text' part of the operating
> > procedures for incrementing/decrementing refcounts? It doesn't belong
> > here, does it?
> >
> > (i.e., there is a 'manage the pristine store' layer --- first part of
> > your email --- and a 'manage the references' layer, here)
>
> Well, it's because in the lower "manage the pristine store" layer,
> purging depends only on refcount==0 (and no simultaneous add or remove).
> At this higher "manage the references" layer, purging must be avoided
> when the WC is in the middle of a WC-lock operation. In other words,
> this upper layer's "purge" is a wrapper that adds an extra level of
> locking around the lower layer's "purge". It's not safe to call the
> lower-layer API directly.
>
In other words, the lower-layer API is oblivious of WC locks. I see.
That said, I just noticed that your bullet points have both a "wc lock"
and an "exclusive wc lock" --- I had overlooked that distinction
earlier. I assume that an 'exclusive' lock is a recursive lock from
the wc root and below?
Thanks,
Daniel
(I'm behind on following the commits@ list --- if there are relevant
commits/milestones of the doc, feel free to direct my attention to them
explicitly)
Re: Pristine store - spec
Posted by Julian Foad <ju...@wandisco.com>.
I have checked this in at notes/wc-ng/pristine-store and updated it
according to Greg's and your comments so far.
On Wed, 2011-02-16, Julian Foad wrote:
> On Wed, 2011-02-16, Daniel Shahaf wrote:
> > Julian Foad wrote on Tue, Feb 15, 2011 at 15:06:43 +0000:
> > > Would anyone be able to review this spec please? I'm trying to get
> > > straight what locking / access control rules need to be.
> >
> > Sure, review below. Having finished the review, though, I wonder if
> > I amn't missing some details of the big picture while studying all the
> > low-level details. (If I did, please point them out.)
> >
> > > /*
> > > * THE PRISTINE STORE
> > > * ==================
> > > *
> > > * === Introduction ===
[...]
> > > * * Ensure the pristine text remains in the store continuously from
> > > * opening it for the duration of the read. (Perhaps by ensuring
> > > * refcount remains >= 1 and/or by cooperating with the clean-up
> > > * code.)
> >
> > I find this vague: how does one perform the "ensure" steps?
>
> Well, I'm not quite sure yet. TODO.
That's now addressed. (In this case, hold a WC lock or rely on the OS
to preserve the file as long as a file handle is open.)
[...]
> Thanks for all this. I'll do an update (and check it in like Hyrum
> said).
I've updated the doc with most of my response, and left "###" markers in
unresolved places. (r1071795.)
- Julian
Re: Pristine store - spec
Posted by Julian Foad <ju...@wandisco.com>.
Hi Daniel. Thanks for this review.
On Wed, 2011-02-16, Daniel Shahaf wrote:
> Julian Foad wrote on Tue, Feb 15, 2011 at 15:06:43 +0000:
> > Would anyone be able to review this spec please? I'm trying to get
> > straight what locking / access control rules need to be.
> >
>
> Sure, review below. Having finished the review, though, I wonder if
> I amn't missing some details of the big picture while studying all the
> low-level details. (If I did, please point them out.)
>
> > /*
> > * THE PRISTINE STORE
> > * ==================
> > *
> > * === Introduction ===
> > *
> > * The Pristine Store is the part of the Working Copy metadata that holds
> > * a local copy of the full text of the base version of each WC file.
>
> Currently, yes. But in general it's just a cache of the text at
> non-directory (file,revision) tuples, right?
> i.e., there's no reason it has to be a subset or superset of the BASE tree.
Correct. I'll re-write the intro to say it's inherently just a blob
store and then describe roughly what libsvn_wc uses it for.
> > *
> > * Texts in the Pristine Store are addressed only by their SHA-1 checksum.
> > * The Pristine Store does not track which text relates to which repository
> > * and revision and path. The Pristine Store does not hold pristine copies
> > * of directories, nor of properties.
> > *
> > * The Pristine Store data is held in
> > * * the 'PRISTINE' table in the SQLite Data Base (SDB), and
> > * * the files in the 'pristine' directory.
> > *
> > * This specification uses SDB transactions to ensure the consistency of
> > * writes and reads.
> > *
>
> Nit:
> This doesn't say how this spec ensures the disk is consistent with the DB.
Do you mean this intro should be more specific and say sthg like
"This spec defines how the store operates so as to ensure
* consistency between disk and DB;
* atomicity of, and arbitration between, add and delete and read
operations."
> > * ==== Invariants ====
> > *
> > * The operating procedures below maintain the following invariants.
> > * These invariants apply at all times except within the SDB txns defined
> > * below.
> > *
> > * * Each row in the PRISTINE table has an associated pristine text file
> > * that is not open for writing and is available for reading and whose
> > * content matches the columns 'size', 'checksum', 'md5_checksum'.
> > *
>
> * Once written, a pristine text file never changes.
Right. That's implied by the fact that its SHA-1 checksum is assumed to
be unique, but it's clearer if I say it explicitly.
> > * ==== Operating Procedures ====
> > *
> > * The steps should be carried out in the order specified. (See rationale.)
> > *
> > * * To add a pristine, do the following inside an SDB txn:
> > * * Add the table row, and set the refcount as desired. If a row
> > * already exists, add the desired refcount to its refcount, and
> > * preferably verify the old row matches the new metadata.
> > * * Create the file. Creation should be fs-atomic, e.g. by moving a
> > * new file into place, so as never to orphan a partial file. If a
> > * file already exists, preferably leave it rather than replace it,
> > * and optionally verify it matches the new metadata (e.g. length).
>
> What happens if you crash (kill -9) between these two steps?
>
> (Reading ahead: I assume that in that case you'll leave a stray wc lock
> or wq entry behind?)
Not at this level of the spec. Here, all that happens is that the SDB
txn prepares to commit a change to the table, but if we crash that txn
would be abandoned and that change would never happen.
On the other hand, if we crash after those two steps but before
committing (finalizing) the SDB txn, then the file would exist on disk
as an "orphan", which is harmless.
Moving up a layer to the "Reference Counting" layer of the spec, then
yes a WC lock is taken out before running this txn, so yes that WC lock
would be left behind if we crash anywhere in this sequence (between the
steps or before or after them).
> (OT: how about numbering or naming the steps and invariants, so it's
> easier to refer to them?)
Good idea, now that it's (presumably) becoming more stable.
> > *
> > * * To remove a pristine, do the following inside an SDB txn:
> > * * First, check refcount == 0, and abort if not.
> > * * Delete the table row.
> > * * Delete the file or move it away. (If not present, log a
> > * consistency error but, in a release build, return success.)
> > *
> > * * To query a pristine's existence or SDB metadata, the reader must:
> > * * Ensure no pristine-remove txn is in progress while querying it.
> > *
>
> Why isn't it sufficient to "SELECT (refcount > 0) WHERE checksum = ?1
> FROM pristine", without any ensuring?
>
> Yes, an 'rm' txn could be parallel --- but won't that be indistinguishable
> from the case than an 'rm' tnx begun instantaneously after the above
> query finished?
Hmm... I think you are right.
> (Reading my "Reading ahead" comment above: okay, if there are some
> higher-level locks, then maybe a parallel 'rm' txn isn't possible)
>
> > * * To read a pristine text, the reader must:
> > * * Ensure no pristine-remove txn is in progress while querying and
> > * opening it.
>
> And what if the txn started after you opened it and returned the file
> handle (stream) to the caller?
That's addressed by the next bullet point below.
> Perhaps a wrapper stream that makes sure the correct file was read (eg,
> by comparing the length of the data read from the stream to the stored
> length, and returning an error if the stream ended prematurely)?
I think that is not necessary - see Brane's reply about "constraints"
and deleting a file that still has open file handles.
> > * * Ensure the pristine text remains in the store continuously from
> > * opening it for the duration of the read. (Perhaps by ensuring
> > * refcount remains >= 1 and/or by cooperating with the clean-up
> > * code.)
>
> I find this vague: how does one perform the "ensure" steps?
Well, I'm not quite sure yet. TODO.
> > *
> > * ==== Rationale ====
> > *
> > * * Adding a pristine:
> > * * We can't add the file *before* the SDB txn takes out a lock,
> > * because that would leave a gap in which another process could
> > * see this file as an orphan and delete it.
> > * * Within the txn, the table row could be added after creating the
> > * file; it makes no difference as it will not become externally
> > * visible until commit. But then we would have to take out a lock
> > * explicitly before adding the file. Adding the row takes out a
> > * lock implicitly, so doing it first avoids an extra step.
>
> It's not an "extra" step if it's done anyway (implicitly) :)
>
> > * * Leaving an existing file in place is less likely to interfere with
> > * processes that are currently reading from the file. Replacing it
> > * might also be acceptable, but that would need further
> > * investigation.
> > *
>
> +1
>
> > * * Removing a pristine:
> > * * We can't remove the file *after* the SDB txn that updates the
> > * table, because that would leave a gap in which another process
> > * might re-add this same pristine file and then we would delete it.
> > * * Within the txn, the table row could be removed after creating the
> > * file, but see the rationale for adding a pristine.
> > * * In a typical use case for removing a pristine text, the caller
> > * would check the refcount before starting this txn, but
> > * nevertheless it may have changed and so must be checked again
> > * inside the txn.
> > *
>
> +1
>
> > * * In the add and remove txns, we need to acquire an SDB 'RESERVED'
> > * lock before adding or removing the file. This can be done by starting
> > * the txn with 'BEGIN IMMEDIATE' and/or by performing an SDB write (such
> > * as the table row update). ### Would a 'SHARED' lock be sufficient,
> > * and if so would it be noticably better?
> > *
>
> Does that mean "We need an SDB lock that blocks both readers and writers"
> in non-sqlite-specific terms?
Yes.
> > * ==== Notes ====
> > *
> > * * This procedure can leave orphaned pristine files (files without a
> > * corresponding SDB row) if Subvsersion crashes. The Pristine Store
> > * will still operate correctly. It should be easy to teach "svn cleanup"
> > * to safely delete these. ### Do we need to define the clean-up
> > * procedure here?
> > *
>
> Yes please. (It bypasses some of the DB-keyed logic so I think it'll be
> good to spell it out)
Okay, will do.
> > * * This specification is conceptually simple, but requires completing disk
> > * operations within SDB transactions, which may make it too inefficient
> > * in practice. An alternative specification could use the Work Queue to
> > * enable more efficient processing of multiple transactions.
> > *
>
> I won't call it simple unless you dereference that "Ensure" I mentioned
> earlier :).
>
> For example, would returning a pristine stream to a caller would require
> some long-living state on the DB handle, to avoid it being prematurely
> deleted?
See above.
> > * REFERENCE COUNTING
> > * ==================
> > *
> > * The Pristine Store spec above defines how texts are added and removed
> > * from the store. This spec defines how the addition and removal of
> > * pristine text references within the WC DB are co-ordinated with the
> > * addition and removal of the pristine texts themselves.
> > *
> > * One requirement is to allow a pristine text to be stored some
> > * time before the reference to it is written into the NODES table. The
> > * 'commit' code path, for example, needs to store a file's new pristine
> > * text somewhere (and the pristine store is an obvious option) and then,
> > * when the commit succeeds, update the WC to reference it.
> > *
>
> To clarify: I believe you mean "Needs" as it's currently designed,
> rather than "Needs" due to the inherent semantics of a 'commit'
> operation. (Extreme example: 'commit' of rN could leave the wc at
> rN-1.)
Yes.
> > * Store-then-reference could be achieved by:
> > *
> > * (a) Store text outside Pristine Store. When commit succeeds, add it
> > * to the Pristine Store and reference it in the WC; if commit
> > * fails, remove the temporary text.
> > * (b) Store text in Pristine Store with initial ref count = 0. When
> > * commit succeeds, add the reference and update the ref count; if
> > * commit fails, optionally try to purge this pristine text.
> > * (c) Store text in Pristine Store with initial ref count = 1. When
> > * commit succeeds, add the reference; if commit fails, decrement
> > * the ref count and optionally try to purge it.
> > *
> > * Method (a) would require, in effect, implementing an ad-hoc temporary
> > * Pristine Store, which seems needless duplication of effort. It would
> > * also require changing the way the commit code path passes information
> > * around, which might be no bad thing in the long term, but the result
> > * would not appear to have any advantage over method (b).
> > *
> > * Method (b) plays well with automatically maintaining the ref counts
> > * equal to the number of in-SDB references, at the granularity of SDB
> > * txns. It requires an interlock between adding/deleting references and
> > * purging unreferenced pristines - e.g. guard each of these operations by
> > * a WC lock.
> > * * Add a pristine & reference it => any WC lock
> > * (To prevent purging it while adding.)
> > * * Unreference a pristine => no lock needed.
> > * * Unreference a pristine & purge-if-0 => Same as doing these separately.
> > * * Purge any/all refcount==0 pristines => an exclusive WC lock.
> > * (To prevent adding a ref while purging.)
> > * * If a WC lock remains after a crash, then purge refcount==0 pristines.
> > *
>
> I don't understand this paragraph. What does it propose to do in order
> to avoid purging pristines that have refcount=0 while a commit is in
> progress? Does it propose that 'commit' take a lock for the duration
> from adding the pristine to incrementing its refcount?
Yes: in the case of the way "commit" is currently implemented, where
"add a pristine" comes first and then "reference it" comes later, the
commit operation should hold a WC lock during that whole time.
> > * Method (c):
> > * * ### Not sure about this one - haven't thought it through in detail...
> > * * Add a pristine & reference in separate steps => any WC lock (?)
> > * * Remove a reference requires ... (nothing more?)
> > * * Find & purge unreferenced pristines requires an exclusive WC lock.
> > * * Ref counts are sometimes too high while a WC lock is held, so
> > * uncertain after a crash if WC locks remain, so need to be re-counted
> > * during clean-up.
> > *
>
> I think (c) has some good points. There's a variant, (c'), where
> instead of overloading the refcount field you use a separate
> refcounts_by_commitsinprogress flag; in that scheme, 'find & purge'
> doesn't need a lock, it just needs to respect that flag.
Food for thought, but I find that working carefully through these
scenarios is quite time consuming. A large part of my aim here is to
try to find a good scheme without having to first define all the
possible schemes in detail. Your comments are helping me to do that.
> > * We choose method (b).
> > *
> > *
> > * === Invariants in a Valid WC DB State ===
> > *
> > * * No pristine text, even if refcount == 0, will be deleted from the store
> > * as long as any process holds any WC lock in this WC.
> > *
>
> Surely you mean "any *other* process" :-)
Yes - something like that, though that's still not quite right.
> > * The following conditions are always true outside of a SQL txn:
> > *
> > * * The 'checksum' column in each NODES table row is either NULL or
> > * references a primary key in the 'pristine' table.
> > *
> > * * The 'refcount' column in each PRISTINE table row is equal to the
> > * number of NODES table rows whose 'checksum' column references this
> > * pristine row.
> > *
>
> Will we have wc-checks.sql triggers enforce these?
The first one is enforced by constraints defined in wc-metadata.sql.
The second one is currently assisted by triggers defined in
wc-metadata.sql but not strictly enforced. I would like to enforce it
but haven't looked at doing so yet.
> > * The following conditions are always true
> > * outside of a SQL txn,
> > * when the Work Queue is empty:
> > * (### ?) when no WC locks are held by any process:
> > *
> > * * The 'refcount' column in a PRISTINE table row equals the number of
> > * NODES table rows whose 'checksum' column references that pristine row.
> > * It may be zero.
> > *
>
> IOW, the refcount may be zero if the work queue is non empty.
No, I meant the number of refs does not necessarily match the refcount
column if the work queue is non empty. When WQ is empty, refcount and
number of refs always match each other and may (both together) be zero
or more than zero.
> But a few pages above you said that this specification doesn't use the
> work queue to manage the pristine files. Why is the work queue involved
> here then? Does this spec use the work queue for the disk-tree files
> but not for the .svn/pristine/ files?
I think I've messed up this part. I'll take another look. I'm not sure
whether the Work Queue needs to be involved at all.
> > * ==== Operating Procedures ====
> > *
> > * The steps should be carried out in the order specified.
> > *
> > * * To add a pristine text reference to the WC, obtain the text and its
> > * checksum, and then do this while holding a WC lock:
> > * * Add the pristine text to the Pristine Store, setting the desired
> > * refcount >= 1.
> > * * Add the reference(s) in the NODES table.
> > *
>
> So the first bullet will take an SDB lock, release it, and then the
> reference will be added while the WC lock is held (and within a separate
> SDB txn/lock)?
Yes. That's to support cases like the current "commit" implementation.
In certain other cases, these could be collapsed into a single txn.
> > * * To remove a pristine text reference from the WC, do this while holding
> > * a WC lock:
> > * * Remove the reference(s) in the NODES table.
> > * * Decrement the pristine text's 'refcount' column.
> > *
> > * * To purge an unreferenced pristine text, do this with an *exclusive*
> > * WC lock:
> > * * Check refcount == 0; skip if not.
> > * * Remove it from the pristine store.
>
> Why is 'purge an unreferenced pristine text' part of the operating
> procedures for incrementing/decrementing refcounts? It doesn't belong
> here, does it?
>
> (i.e., there is a 'manage the pristine store' layer --- first part of
> your email --- and a 'manage the references' layer, here)
Well, it's because in the lower "manage the pristine store" layer,
purging depends only on refcount==0 (and no simultaneous add or remove).
At this higher "manage the references" layer, purging must be avoided
when the WC is in the middle of a WC-lock operation. In other words,
this upper layer's "purge" is a wrapper that adds an extra level of
locking around the lower layer's "purge". It's not safe to call the
lower-layer API directly.
Thanks for all this. I'll do an update (and check it in like Hyrum
said).
- Julian
Re: Pristine store - spec
Posted by Branko Čibej <br...@e-reka.si>.
On 16.02.2011 13:06, Daniel Shahaf wrote:
> Julian Foad wrote on Tue, Feb 15, 2011 at 15:06:43 +0000:
>> * * This specification is conceptually simple, but requires completing disk
>> * operations within SDB transactions, which may make it too inefficient
>> * in practice. An alternative specification could use the Work Queue to
>> * enable more efficient processing of multiple transactions.
>> *
> I won't call it simple unless you dereference that "Ensure" I mentioned
> earlier :).
>
> For example, would returning a pristine stream to a caller would require
> some long-living state on the DB handle, to avoid it being prematurely
> deleted?
A handle to a pristine file constitutes a reference. Therefore, you can
do one of two things:
* Do proper reference counting in the WC when you open pristine
files. This is for all practical purposes impossible to implement
without hijacking the whole VFS.
* Impose constraints on what users of the file handle can expect,
for example:
o you are not allowed write access through the file (pristine
file creation is a magical step)
o you cannot assume that you will find the file that the
handle refers to in any directory listing
o you cannot assume that the file will continue to exist after
the handle is closed
That last assumes that once can delete a file that still has open file
handles. That always works on Unix, and can work on Windows when the
file is opend with the FILE_SHARE_DELETE flag set (the difference
between Ux and Win is that the file will vanish from the directory
immediately upon delete, whilst on Windows, it'll vanish when the last
handle is closed).
All in all, letting the OS maintain open-handle reference counts is much
better than trying to fake it through sqlite.
-- Brane
Re: Pristine store - spec
Posted by Daniel Shahaf <d....@daniel.shahaf.name>.
Julian Foad wrote on Tue, Feb 15, 2011 at 15:06:43 +0000:
> Would anyone be able to review this spec please? I'm trying to get
> straight what locking / access control rules need to be.
>
Sure, review below. Having finished the review, though, I wonder if
I amn't missing some details of the big picture while studying all the
low-level details. (If I did, please point them out.)
> /*
> * THE PRISTINE STORE
> * ==================
> *
> * === Introduction ===
> *
> * The Pristine Store is the part of the Working Copy metadata that holds
> * a local copy of the full text of the base version of each WC file.
Currently, yes. But in general it's just a cache of the text at
non-directory (file,revision) tuples, right?
i.e., there's no reason it has to be a subset or superset of the BASE tree.
> *
> * Texts in the Pristine Store are addressed only by their SHA-1 checksum.
> * The Pristine Store does not track which text relates to which repository
> * and revision and path. The Pristine Store does not hold pristine copies
> * of directories, nor of properties.
> *
> * The Pristine Store data is held in
> * * the 'PRISTINE' table in the SQLite Data Base (SDB), and
> * * the files in the 'pristine' directory.
> *
> * This specification uses SDB transactions to ensure the consistency of
> * writes and reads.
> *
Nit:
This doesn't say how this spec ensures the disk is consistent with the DB.
> * ==== Invariants ====
> *
> * The operating procedures below maintain the following invariants.
> * These invariants apply at all times except within the SDB txns defined
> * below.
> *
> * * Each row in the PRISTINE table has an associated pristine text file
> * that is not open for writing and is available for reading and whose
> * content matches the columns 'size', 'checksum', 'md5_checksum'.
> *
* Once written, a pristine text file never changes.
> * ==== Operating Procedures ====
> *
> * The steps should be carried out in the order specified. (See rationale.)
> *
> * * To add a pristine, do the following inside an SDB txn:
> * * Add the table row, and set the refcount as desired. If a row
> * already exists, add the desired refcount to its refcount, and
> * preferably verify the old row matches the new metadata.
> * * Create the file. Creation should be fs-atomic, e.g. by moving a
> * new file into place, so as never to orphan a partial file. If a
> * file already exists, preferably leave it rather than replace it,
> * and optionally verify it matches the new metadata (e.g. length).
What happens if you crash (kill -9) between these two steps?
(Reading ahead: I assume that in that case you'll leave a stray wc lock
or wq entry behind?)
(OT: how about numbering or naming the steps and invariants, so it's
easier to refer to them?)
> *
> * * To remove a pristine, do the following inside an SDB txn:
> * * First, check refcount == 0, and abort if not.
> * * Delete the table row.
> * * Delete the file or move it away. (If not present, log a
> * consistency error but, in a release build, return success.)
> *
> * * To query a pristine's existence or SDB metadata, the reader must:
> * * Ensure no pristine-remove txn is in progress while querying it.
> *
Why isn't it sufficient to "SELECT (refcount > 0) WHERE checksum = ?1
FROM pristine", without any ensuring?
Yes, an 'rm' txn could be parallel --- but won't that be indistinguishable
from the case than an 'rm' tnx begun instantaneously after the above
query finished?
(Reading my "Reading ahead" comment above: okay, if there are some
higher-level locks, then maybe a parallel 'rm' txn isn't possible)
> * * To read a pristine text, the reader must:
> * * Ensure no pristine-remove txn is in progress while querying and
> * opening it.
And what if the txn started after you opened it and returned the file
handle (stream) to the caller?
Perhaps a wrapper stream that makes sure the correct file was read (eg,
by comparing the length of the data read from the stream to the stored
length, and returning an error if the stream ended prematurely)?
> * * Ensure the pristine text remains in the store continuously from
> * opening it for the duration of the read. (Perhaps by ensuring
> * refcount remains >= 1 and/or by cooperating with the clean-up
> * code.)
I find this vague: how does one perform the "ensure" steps?
> *
> * ==== Rationale ====
> *
> * * Adding a pristine:
> * * We can't add the file *before* the SDB txn takes out a lock,
> * because that would leave a gap in which another process could
> * see this file as an orphan and delete it.
> * * Within the txn, the table row could be added after creating the
> * file; it makes no difference as it will not become externally
> * visible until commit. But then we would have to take out a lock
> * explicitly before adding the file. Adding the row takes out a
> * lock implicitly, so doing it first avoids an extra step.
It's not an "extra" step if it's done anyway (implicitly) :)
> * * Leaving an existing file in place is less likely to interfere with
> * processes that are currently reading from the file. Replacing it
> * might also be acceptable, but that would need further
> * investigation.
> *
+1
> * * Removing a pristine:
> * * We can't remove the file *after* the SDB txn that updates the
> * table, because that would leave a gap in which another process
> * might re-add this same pristine file and then we would delete it.
> * * Within the txn, the table row could be removed after creating the
> * file, but see the rationale for adding a pristine.
> * * In a typical use case for removing a pristine text, the caller
> * would check the refcount before starting this txn, but
> * nevertheless it may have changed and so must be checked again
> * inside the txn.
> *
+1
> * * In the add and remove txns, we need to acquire an SDB 'RESERVED'
> * lock before adding or removing the file. This can be done by starting
> * the txn with 'BEGIN IMMEDIATE' and/or by performing an SDB write (such
> * as the table row update). ### Would a 'SHARED' lock be sufficient,
> * and if so would it be noticably better?
> *
Does that mean "We need an SDB lock that blocks both readers and writers"
in non-sqlite-specific terms?
> * ==== Notes ====
> *
> * * This procedure can leave orphaned pristine files (files without a
> * corresponding SDB row) if Subvsersion crashes. The Pristine Store
> * will still operate correctly. It should be easy to teach "svn cleanup"
> * to safely delete these. ### Do we need to define the clean-up
> * procedure here?
> *
Yes please. (It bypasses some of the DB-keyed logic so I think it'll be
good to spell it out)
> * * This specification is conceptually simple, but requires completing disk
> * operations within SDB transactions, which may make it too inefficient
> * in practice. An alternative specification could use the Work Queue to
> * enable more efficient processing of multiple transactions.
> *
I won't call it simple unless you dereference that "Ensure" I mentioned
earlier :).
For example, would returning a pristine stream to a caller would require
some long-living state on the DB handle, to avoid it being prematurely
deleted?
> * REFERENCE COUNTING
> * ==================
> *
> * The Pristine Store spec above defines how texts are added and removed
> * from the store. This spec defines how the addition and removal of
> * pristine text references within the WC DB are co-ordinated with the
> * addition and removal of the pristine texts themselves.
> *
> * One requirement is to allow a pristine text to be stored some
> * time before the reference to it is written into the NODES table. The
> * 'commit' code path, for example, needs to store a file's new pristine
> * text somewhere (and the pristine store is an obvious option) and then,
> * when the commit succeeds, update the WC to reference it.
> *
To clarify: I believe you mean "Needs" as it's currently designed,
rather than "Needs" due to the inherent semantics of a 'commit'
operation. (Extreme example: 'commit' of rN could leave the wc at
rN-1.)
> * Store-then-reference could be achieved by:
> *
> * (a) Store text outside Pristine Store. When commit succeeds, add it
> * to the Pristine Store and reference it in the WC; if commit
> * fails, remove the temporary text.
> * (b) Store text in Pristine Store with initial ref count = 0. When
> * commit succeeds, add the reference and update the ref count; if
> * commit fails, optionally try to purge this pristine text.
> * (c) Store text in Pristine Store with initial ref count = 1. When
> * commit succeeds, add the reference; if commit fails, decrement
> * the ref count and optionally try to purge it.
> *
> * Method (a) would require, in effect, implementing an ad-hoc temporary
> * Pristine Store, which seems needless duplication of effort. It would
> * also require changing the way the commit code path passes information
> * around, which might be no bad thing in the long term, but the result
> * would not appear to have any advantage over method (b).
> *
> * Method (b) plays well with automatically maintaining the ref counts
> * equal to the number of in-SDB references, at the granularity of SDB
> * txns. It requires an interlock between adding/deleting references and
> * purging unreferenced pristines - e.g. guard each of these operations by
> * a WC lock.
> * * Add a pristine & reference it => any WC lock
> * (To prevent purging it while adding.)
> * * Unreference a pristine => no lock needed.
> * * Unreference a pristine & purge-if-0 => Same as doing these separately.
> * * Purge any/all refcount==0 pristines => an exclusive WC lock.
> * (To prevent adding a ref while purging.)
> * * If a WC lock remains after a crash, then purge refcount==0 pristines.
> *
I don't understand this paragraph. What does it propose to do in order
to avoid purging pristines that have refcount=0 while a commit is in
progress? Does it propose that 'commit' take a lock for the duration
from adding the pristine to incrementing its refcount?
> * Method (c):
> * * ### Not sure about this one - haven't thought it through in detail...
> * * Add a pristine & reference in separate steps => any WC lock (?)
> * * Remove a reference requires ... (nothing more?)
> * * Find & purge unreferenced pristines requires an exclusive WC lock.
> * * Ref counts are sometimes too high while a WC lock is held, so
> * uncertain after a crash if WC locks remain, so need to be re-counted
> * during clean-up.
> *
I think (c) has some good points. There's a variant, (c'), where
instead of overloading the refcount field you use a separate
refcounts_by_commitsinprogress flag; in that scheme, 'find & purge'
doesn't need a lock, it just needs to respect that flag.
> * We choose method (b).
> *
> *
> * === Invariants in a Valid WC DB State ===
> *
> * * No pristine text, even if refcount == 0, will be deleted from the store
> * as long as any process holds any WC lock in this WC.
> *
Surely you mean "any *other* process" :-)
> * The following conditions are always true outside of a SQL txn:
> *
> * * The 'checksum' column in each NODES table row is either NULL or
> * references a primary key in the 'pristine' table.
> *
> * * The 'refcount' column in each PRISTINE table row is equal to the
> * number of NODES table rows whose 'checksum' column references this
> * pristine row.
> *
Will we have wc-checks.sql triggers enforce these?
> * The following conditions are always true
> * outside of a SQL txn,
> * when the Work Queue is empty:
> * (### ?) when no WC locks are held by any process:
> *
> * * The 'refcount' column in a PRISTINE table row equals the number of
> * NODES table rows whose 'checksum' column references that pristine row.
> * It may be zero.
> *
IOW, the refcount may be zero if the work queue is non empty.
But a few pages above you said that this specification doesn't use the
work queue to manage the pristine files. Why is the work queue involved
here then? Does this spec use the work queue for the disk-tree files
but not for the .svn/pristine/ files?
> * ==== Operating Procedures ====
> *
> * The steps should be carried out in the order specified.
> *
> * * To add a pristine text reference to the WC, obtain the text and its
> * checksum, and then do this while holding a WC lock:
> * * Add the pristine text to the Pristine Store, setting the desired
> * refcount >= 1.
> * * Add the reference(s) in the NODES table.
> *
So the first bullet will take an SDB lock, release it, and then the
reference will be added while the WC lock is held (and within a separate
SDB txn/lock)?
> * * To remove a pristine text reference from the WC, do this while holding
> * a WC lock:
> * * Remove the reference(s) in the NODES table.
> * * Decrement the pristine text's 'refcount' column.
> *
> * * To purge an unreferenced pristine text, do this with an *exclusive*
> * WC lock:
> * * Check refcount == 0; skip if not.
> * * Remove it from the pristine store.
Why is 'purge an unreferenced pristine text' part of the operating
procedures for incrementing/decrementing refcounts? It doesn't belong
here, does it?
(i.e., there is a 'manage the pristine store' layer --- first part of
your email --- and a 'manage the references' layer, here)
> */
>
>
> - Julian
>
>
Re: Pristine store - spec
Posted by Julian Foad <ju...@wandisco.com>.
On Wed, 2011-02-16, I (Julian Foad) wrote:
> > > This specification is conceptually simple, but requires completing disk
> > > operations within SDB transactions, which may make it too inefficient
> > > in practice. An alternative specification could use the Work Queue to
> > > enable more efficient processing of multiple transactions.
> >
> > Note that my initial design for the pristine inserted a row which
> > effectively said "we know about this pristine, but it hasn't been
> > written yet". The file would be put into place, then the row would get
> > tweaked to say "it is now there". That avoids the disk I/O within a
> > sqlite txn.
>
> That would indeed avoid disk I/O within any txn during "add". The
> "remove" operation would go through the same states in reverse, I
> assume. But this seems to imply an extra complexity. How would the
> whole thing work - locking for "add", "remove" and read operations;
> crash recovery? Maybe it's straightforward but I'll have to write it
> out in detail if you think it's worth it.
>
> I would suggest first we need to assess whether a file move within a txn
> is in fact a problem.
I'm thinking one thing we've learned about performance is we need to
avoid doing a transaction per node. Doing so limits the speed of
multi-file WC operations severely (I've heard numbers like 50 to 100
txns per second being quoted).
So I think we need to support installing multiple pristine files per
txn.
If we do that, then whether we do the file move(s) within the txn, or
two txns with the file move(s) coming in between them, probably isn't
important in terms of speed. What about the semantic difference between
them? The two-phase installation may have the advantage that a client
can tell whether a given pristine text is already being downloaded from
the repo and thus avoid duplicating the download. That would certainly
be nice to have. However, I don't feel it is worth the extra effort at
this time: it can be a future enhancement.
- Julian
Re: Pristine store - spec
Posted by Julian Foad <ju...@wandisco.com>.
Hi Greg. Thanks for reviewing.
On Tue, 2011-02-15, Greg Stein wrote:
> On Tue, Feb 15, 2011 at 10:06, Julian Foad <ju...@wandisco.com> wrote:
> >...
> > * ==== Operating Procedures ====
> > *
> > * The steps should be carried out in the order specified. (See rationale.)
> > *
> > * * To add a pristine, do the following inside an SDB txn:
> > * * Add the table row, and set the refcount as desired. If a row
> > * already exists, add the desired refcount to its refcount, and
> > * preferably verify the old row matches the new metadata.
> > * * Create the file. Creation should be fs-atomic, e.g. by moving a
> > * new file into place, so as never to orphan a partial file. If a
> > * file already exists, preferably leave it rather than replace it,
> > * and optionally verify it matches the new metadata (e.g. length).
> > *
> > * * To remove a pristine, do the following inside an SDB txn:
> > * * First, check refcount == 0, and abort if not.
> > * * Delete the table row.
> > * * Delete the file or move it away. (If not present, log a
> > * consistency error but, in a release build, return success.)
> > *
> > * * To query a pristine's existence or SDB metadata, the reader must:
> > * * Ensure no pristine-remove txn is in progress while querying it.
>
> What does "pristine-remove txn" mean?
It means the SDB txn defined under "To remove a pristine" above. The
obvious way to ensure it's not in progress would be to do this query in
an SDB txn with a suitable lock (and I think the default lock type that
you get in a txn would be sufficient).
> > *
> > * * To read a pristine text, the reader must:
> > * * Ensure no pristine-remove txn is in progress while querying and
> > * opening it.
> > * * Ensure the pristine text remains in the store continuously from
> > * opening it for the duration of the read. (Perhaps by ensuring
> > * refcount remains >= 1 and/or by cooperating with the clean-up
> > * code.)
>
> Taking out a WC lock would prevent a pristine from being deleted, right?
Yes, that would work, because of the rule below that requires an
exclusive WC lock in order to purge an unreferenced text.
(Originally I didn't say that here because I'm trying to keep the spec
as two separate layers, first presenting this low-level spec for
maintaining consistency between the files and the PRISTINE table rows in
the store, and secondly under the heading "Reference Counting" a higher
level spec for maintaining the references to pristines, which layers on
top of this one. The latter is where WC locks are involved. However, a
cross-reference here would be helpful.)
Is a WC lock on the root of the WC an exclusive lock, in that it could
not co-exist with any other WC lock whether on the root or deeper? I'm
unsure of the semantics of WC locks.
> >...
> > * ==== Notes ====
> > *
> > * * This procedure can leave orphaned pristine files (files without a
> > * corresponding SDB row) if Subvsersion crashes. The Pristine Store
> > * will still operate correctly. It should be easy to teach "svn cleanup"
> > * to safely delete these. ### Do we need to define the clean-up
> > * procedure here?
> > *
> > * * This specification is conceptually simple, but requires completing disk
> > * operations within SDB transactions, which may make it too inefficient
> > * in practice. An alternative specification could use the Work Queue to
> > * enable more efficient processing of multiple transactions.
>
> Note that my initial design for the pristine inserted a row which
> effectively said "we know about this pristine, but it hasn't been
> written yet". The file would be put into place, then the row would get
> tweaked to say "it is now there". That avoids the disk I/O within a
> sqlite txn.
That would indeed avoid disk I/O within any txn during "add". The
"remove" operation would go through the same states in reverse, I
assume. But this seems to imply an extra complexity. How would the
whole thing work - locking for "add", "remove" and read operations;
crash recovery? Maybe it's straightforward but I'll have to write it
out in detail if you think it's worth it.
I would suggest first we need to assess whether a file move within a txn
is in fact a problem.
> >...
> > * === Invariants in a Valid WC DB State ===
> > *
> > * * No pristine text, even if refcount == 0, will be deleted from the store
> > * as long as any process holds any WC lock in this WC.
> > *
> > * The following conditions are always true outside of a SQL txn:
> > *
> > * * The 'checksum' column in each NODES table row is either NULL or
> > * references a primary key in the 'pristine' table.
> > *
> > * * The 'refcount' column in each PRISTINE table row is equal to the
> > * number of NODES table rows whose 'checksum' column references this
> > * pristine row.
>
> ACTUAL_NODE also holds references. Shouldn't these count towards the checksum?
One day, yes, but for 1.7 no. We don't use that column yet.
> > *
> > * The following conditions are always true
> > * outside of a SQL txn,
> > * when the Work Queue is empty:
> > * (### ?) when no WC locks are held by any process:
> > *
> > * * The 'refcount' column in a PRISTINE table row equals the number of
> > * NODES table rows whose 'checksum' column references that pristine row.
> > * It may be zero.
>
> hmm? duplicate text?
Could be... I was losing concentration at this end of the doc.
> > *
> > * ==== Operating Procedures ====
> > *
> > * The steps should be carried out in the order specified.
> > *
> > * * To add a pristine text reference to the WC, obtain the text and its
> > * checksum, and then do this while holding a WC lock:
> > * * Add the pristine text to the Pristine Store, setting the desired
> > * refcount >= 1.
> > * * Add the reference(s) in the NODES table.
> > *
> > * * To remove a pristine text reference from the WC, do this while holding
> > * a WC lock:
> > * * Remove the reference(s) in the NODES table.
> > * * Decrement the pristine text's 'refcount' column.
> > *
> > * * To purge an unreferenced pristine text, do this with an *exclusive*
> > * WC lock:
> > * * Check refcount == 0; skip if not.
> > * * Remove it from the pristine store.
>
> This seems a bit duplicative of the "Operating Procedures" in the first section.
This is supposed to be the higher layer of spec, defining how to add a
new pristine text to the WC ALONG WITH ADDING A REFERENCE TO IT in the
NODES table, in terms of the lower layer "add this text to the store"
operation.
- Julian
Re: Pristine store - spec
Posted by Greg Stein <gs...@gmail.com>.
On Tue, Feb 15, 2011 at 10:06, Julian Foad <ju...@wandisco.com> wrote:
>...
> * ==== Operating Procedures ====
> *
> * The steps should be carried out in the order specified. (See rationale.)
> *
> * * To add a pristine, do the following inside an SDB txn:
> * * Add the table row, and set the refcount as desired. If a row
> * already exists, add the desired refcount to its refcount, and
> * preferably verify the old row matches the new metadata.
> * * Create the file. Creation should be fs-atomic, e.g. by moving a
> * new file into place, so as never to orphan a partial file. If a
> * file already exists, preferably leave it rather than replace it,
> * and optionally verify it matches the new metadata (e.g. length).
> *
> * * To remove a pristine, do the following inside an SDB txn:
> * * First, check refcount == 0, and abort if not.
> * * Delete the table row.
> * * Delete the file or move it away. (If not present, log a
> * consistency error but, in a release build, return success.)
> *
> * * To query a pristine's existence or SDB metadata, the reader must:
> * * Ensure no pristine-remove txn is in progress while querying it.
What does "pristine-remove txn" mean?
> *
> * * To read a pristine text, the reader must:
> * * Ensure no pristine-remove txn is in progress while querying and
> * opening it.
> * * Ensure the pristine text remains in the store continuously from
> * opening it for the duration of the read. (Perhaps by ensuring
> * refcount remains >= 1 and/or by cooperating with the clean-up
> * code.)
Taking out a WC lock would prevent a pristine from being deleted, right?
>...
> * ==== Notes ====
> *
> * * This procedure can leave orphaned pristine files (files without a
> * corresponding SDB row) if Subvsersion crashes. The Pristine Store
> * will still operate correctly. It should be easy to teach "svn cleanup"
> * to safely delete these. ### Do we need to define the clean-up
> * procedure here?
> *
> * * This specification is conceptually simple, but requires completing disk
> * operations within SDB transactions, which may make it too inefficient
> * in practice. An alternative specification could use the Work Queue to
> * enable more efficient processing of multiple transactions.
Note that my initial design for the pristine inserted a row which
effectively said "we know about this pristine, but it hasn't been
written yet". The file would be put into place, then the row would get
tweaked to say "it is now there". That avoids the disk I/O within a
sqlite txn.
>...
> * === Invariants in a Valid WC DB State ===
> *
> * * No pristine text, even if refcount == 0, will be deleted from the store
> * as long as any process holds any WC lock in this WC.
> *
> * The following conditions are always true outside of a SQL txn:
> *
> * * The 'checksum' column in each NODES table row is either NULL or
> * references a primary key in the 'pristine' table.
> *
> * * The 'refcount' column in each PRISTINE table row is equal to the
> * number of NODES table rows whose 'checksum' column references this
> * pristine row.
ACTUAL_NODE also holds references. Shouldn't these count towards the checksum?
> *
> * The following conditions are always true
> * outside of a SQL txn,
> * when the Work Queue is empty:
> * (### ?) when no WC locks are held by any process:
> *
> * * The 'refcount' column in a PRISTINE table row equals the number of
> * NODES table rows whose 'checksum' column references that pristine row.
> * It may be zero.
hmm? duplicate text?
> *
> * ==== Operating Procedures ====
> *
> * The steps should be carried out in the order specified.
> *
> * * To add a pristine text reference to the WC, obtain the text and its
> * checksum, and then do this while holding a WC lock:
> * * Add the pristine text to the Pristine Store, setting the desired
> * refcount >= 1.
> * * Add the reference(s) in the NODES table.
> *
> * * To remove a pristine text reference from the WC, do this while holding
> * a WC lock:
> * * Remove the reference(s) in the NODES table.
> * * Decrement the pristine text's 'refcount' column.
> *
> * * To purge an unreferenced pristine text, do this with an *exclusive*
> * WC lock:
> * * Check refcount == 0; skip if not.
> * * Remove it from the pristine store.
This seems a bit duplicative of the "Operating Procedures" in the first section.
Cheers,
-g