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)
Received on 2011-02-18 18:33:42 CET