Subject: [sidr] repository directory lock?

From: Stephen Kent <[email-masked]>
Date: Tue, 7 Sep 2010 18:25:16 -0400

Folks,

At the IETF meeting in Maastricht I mentioned that we might need to 
augment the repository structure doc (that I briefed on Geoff's 
behalf) with some sort of lock capability.  My concern is that if RP 
softwre visits a publication point (file system directory) while the 
directory is being modified, the RP software has no easy way to know 
that rsync has returned an inconsistent set of records.

Yes, the manifest will indicate a mismatch in this case, but the 
manifest was designed to enable an RP to detect malicious 
modification of a directory. If we try to use a manifest to detect 
inconsistency due to benign directory maintenance, I fear this will 
lead to a lot of complexity.  Also, if one downloads signed objects 
and later processes them against the manifest (itself a signed 
object) detecting an inconsistency may be late in the process, long 
after the directory was visited, making it harder (and slower) to 
respond.

I think it would be clearer if we had a separate object dedicated to 
this function.  The mechanism should be easy to check quickly, 
enabling RP software to detect that a directory is being modified, so 
that the RP can discard the (changed) files that it is retrieving, 
and schedule a revisit to the directory in a little while, when the 
directory update is complete.

I have no specific proposal for the lock object, or the details of 
how RP software interpret it.  I'l looking for suggestions, or an 
alternative way to address the problem.

Steve

---

From: Terry Manderson <[email-masked]>
Date: Tue, 7 Sep 2010 22:56:14 -0700

Hi Steve

> that rsync has returned an inconsistent set of records.

I agree, there does appear to be an issue here where changes during fetch
could cause delays via validation/refresh/validation stages.

> directory update is complete.

Although I think I would be reluctant to add another object, for the same
complexity reasons that exist in the manifest instance and I'm not sure that
it will avoid the issues about concurrent modifications as the RP's fetch
may run longer than the creation/destruction/validity of the object as well
as any update to the repository. This also makes me think about the depth 0,
1, or infinity issues of directory and subdirectories.

> alternative way to address the problem.

It sounds like system hackery, but I feel more comfortable in looking
towards recommendations about how the directory structure is laid down,
given that rsync is file based and not block based, and after a repository
is constructed then new file-lists and transfers (for a client) can be
directed at the latest repository version. Existing rsync processes would
need to stay within the state of the repository as it was when they were
started.

Making this a server issue then removes all RP decisions except for
freshness.

Cheers
Terry

---

From: Tim Bruijnzeels <[email-masked]>
Date: Wed, 08 Sep 2010 10:09:22 +0200

> On 8/09/10 8:25 AM, "Stephen Kent" <[email-masked]> wrote:
....
> Making this a server issue then removes all RP decisions except for

I don't know how to make this work. We do not want to re-implement or
modify rsync(d) so I don't see a way to make client 'sessions' sticky to
a previous state of the repository.

I would be more comfortable with a client side strategy to detect
problems. How about we advise clients that detect problems to re-fetch
the manifest and look at the not-before time in the EE certificate? If
this is too close to now for comfort (i.e. just re-issued), try again...

Cheers
Tim

> Cheers
> Terry
> 
> _______________________________________________
> sidr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sidr

---

From: Andy Newton <[email-masked]>
Date: Wed, 8 Sep 2010 08:48:30 -0400

> a previous state of the repository.

I agree. Requiring modifications or re-implementation of rsyncd is a non-starter in my opinion.

However, I read Terry's message as using directory structure to avoid inconsistent states.

-andy

---

From: Rob Austein <[email-masked]>
Date: Wed, 08 Sep 2010 10:04:18 -0400

I don't see any locking strategy (either modifying rsync or creating a
new RPKI object to represent a lock) as likely to work.  I can go into
details if necessary, but in short there are just too many different
ways that a relying party could end up with a potentially inconsistent
collection of objects, and this problem goes beyond a single directory
("publication point"), or the rsync protocol.

I see no alternative but to place the burden of assembling a
consistent view on the relying party.  This may mean that the relying
party's view lags the latest published data in some cases, and that a
relying party that's just starting up (has no cache of valid results
from previous retrieval runs) may end up with an incomplete picture
portions of the universe.  So be it.

Welcome to the world of loosely consistent databases.

---

From: Christopher Morrow <[email-masked]>
Date: Wed, 8 Sep 2010 10:12:02 -0400

> Welcome to the world of loosely consistent databases.

as an aside, rsync issues can mostly be avoided with:
morrowc@donkey:~$ rsync --help | grep delay
     --delete-delay          find deletions during, delete after
     --delay-updates         put all updated files into place at transfer's end

or that sort of thing (--delay-updates) is a common thing to use in
syncing large sets of data where other parties are reliant on a
consistent view (and changing that view under them is considered
rude).

For this discussion though it strikes me that there could be lots of
reasons that an RP sees a slightly different view of the publication
point over time, different from what another RP sees, or the publisher
intends inside a short period of time at least. Checking what you
download with what is supposed to have been there (manifest checks)
are still required, or prudent at least.

-chris

---

From: Roque Gagliano <[email-masked]>
Date: Wed, 8 Sep 2010 16:16:31 +0200

Hi Rob,

> Welcome to the world of loosely consistent databases.

I agree with you. However, can we think on some operational practices that may help the RP?

Here is one example I was thinking about: what if we recommend the server to always start updating a publication point by the manifest?. In this sense the RP can always re-fetch the manifest at the end of the sync process to compare it with the original one at the start of the sync process.

Roque.

---

From: Stephen Kent <[email-masked]>
Date: Wed, 8 Sep 2010 10:38:23 -0400

At 10:56 PM -0700 9/7/10, Terry Manderson wrote:
>...

I don't understand you reference here. A lock on a directory need not 
affect access to sub-directories. The rekey design that Geoff 
developed (and that I now co-author) restricts changes to a directory 
for rekey, to that directory. And the 1-day (minimum) staging period 
allows a reasonable interval to fetch the new CA cert (and the 
subordinate CRL and manifest) before objects at the next level are 
replaced.

>...

I don't think we should make too many assumptions about the directory 
structure, other than what is mandated by the overall system design. 
For example, while a lot of these files will be in repository 
instances operated by RIRs, I've heard folks suggest that big ISPs 
may operate their own repositories, containing their objects and 
objects for their customers.  Also, if one tries to parallelize 
repository access, to avoid potential DoS concerns, then one may have 
a list of URIs to visit, and they may not be visited in a purely 
top-down fashion. So I think we should focus on per-directory 
consistency.

Steve

---

From: Stephen Kent <[email-masked]>
Date: Wed, 8 Sep 2010 10:33:48 -0400

>Welcome to the world of loosely consistent databases.

I didn't mean to suggest that we use a lock object to prevent an RP 
from fetching a set of file that may be inconsistent.  I merely want 
the RP to have
an easy way to detect that this has happened, preferably in a way that is
deterministic (or close to it).

Steve

---

From: Tim Bruijnzeels <[email-masked]>
Date: Wed, 08 Sep 2010 16:46:12 +0200

> Here is one example I was thinking about: what if we recommend the server to always start updating a publication point by the manifest?. In this sense the RP can always re-fetch the manifest at the…

FYI: we publish everything to a new, empty directory. When this is done
we change the symlink that points to the 'current' directory, to this
new dir. Rsync follows the symlink. I believe this is similar to other
implementations.

This does not prevent mid-transfer issues as such, but.. the change
itself is fairly atomic. In other words if the RP suspects a
mid-transfer update may have occurred, and then restarts the transfer:
they should get a consistent view.

Since the manifest is always updated when changes occur, and a new EE
certificate issued with not-before time set to the moment of
publication, the RP can re-fetch the manifest and check whether it was
updated.

So, when processing the SIA for a cert:
1) get manifest (follow manifest pointer)
2) get all other objects (follow dir pointer)
3) get manifest again and compare to 1
  --> if 3 and 1 don't match, wait a moment and repeat.

I am not sure though whether this enough.. other ideas?

Cheers
Tim

---

From: Stephen Kent <[email-masked]>
Date: Wed, 8 Sep 2010 14:20:03 -0400

Tim,

>I am not sure though whether this enough.. other ideas?

I like your overall approach, although not the details of the algorithm :-).

I prefer a description that does not assume that the RP software is 
always extracting SIA URLs to drive the rsync operation in realtime. 
For example, our RP software builds a list of URLs from validated 
certs (as well as from trust anchors) and we visit directories based 
on that list. We update the list anachronously, based on later stage 
processing of certs. So, if you believe the following procedure is 
equivalent, wrt detecting and responding to fetching files from a 
directory that is being updated, I'd be comfortable:

1- retrieve changed files from a directory (what rsync does by default)
2- wait a moment (how long?) and ask rsync to do this again, for the 
same directory
3- if no changes are detected, hence no files returned, then assume that
    the files that were retrieved in step 1 are a consistent; reset the counter
    for this directory to 0.

    OTHERWISE increment the counter for this directory; if the counter 
is greater
    than a threshold value, give up on this directory for now, and 
note this error,

    OTHERWISE wait a moment and return to step 1.

This description does not require any "deep" processing of the 
retrieved objects,
it gives the directory time to stabilize, and allows for a max number 
of retries, without getting stuck. It  does not rely on the manifest 
being updated in a particular order. It does have the downside of 
making rsync to visit every directory at least twice. I'm not enough 
of an rsync guy to know if Chris's command line parameters are a 
simple way to implement the semantics of my step 2 above. Chris?

Steve

---

From: "Charles W. Gardiner" <[email-masked]>
Date: Fri, 10 Sep 2010 10:12:15 -0400

At 10:46 AM 9/8/2010, Tim Bruijnzeels wrote:
<snip>
>I am not sure though whether this enough.. other ideas?

     I think this sounds good.  I tried a little experiment on a Linux 
machine using simply renaming of a directory while another process was in 
that directory.  The second process was not disturbed.  I think, therefore, 
one could do the following at the rsync target machine where the rsync 
target directory is named, say, xxxxx:

     1. Create a new directory named, say, newxxxxx as a sibling to xxxxx.
     2. Fill newxxxxx with the new material for rsync.
     3. Rename xxxxx to oldxxxxx.
     4. Rename newxxxxx to xxxxx.

     Anyone connected to xxxxx before step 3 will remain connected to 
oldxxxxx and get old data.  Anyone starting rsync between steps 3 and 4 
will get nothing -- or some signal that xxxxx is unavailable.  Anyone 
starting after step 4 will get the new data. (I'm not sure that newxxxxx 
has to be a sibling of xxxxx, but I haven't tried anything different.)

Charlie Gardiner

---

From: Robert Kisteleki <[email-masked]>
Date: Fri, 10 Sep 2010 16:30:36 +0200

> I think this sounds good. I tried a little experiment on a Linux machine
> using simply renaming of a directory while another process was in that
> directory. The second process was not disturbed. I think, therefore, one

Welcome to the wonderful world of inodes.

> could do the following at the rsync target machine where the rsync target
> directory is named, say, xxxxx:
>
> Anyone connected to xxxxx before step 3 will remain connected to oldxxxxx
> and get old data. Anyone starting rsync between steps 3 and 4 will get
> nothing -- or some signal that xxxxx is unavailable. Anyone starting after
> step 4 will get the new data. (I'm not sure that newxxxxx has to be a
> sibling of xxxxx, but I haven't tried anything different.)

And anyone entering between 1 and 3 will have a problem. You can create 
newxxx outside of this space and then swap in quickly, but even that's not 
atomic, and not always possible.

The thing is, it's very difficult to implement anything on the server side 
that is guaranteed to be atomic from the RP's point of view. There's simply 
too much interaction between various abstraction levels (fs caches, 
filesystems, inodes, directory scans, symlinks, rsync, ...)

It's far easier to check consistency on the receiving side.

Robert

---

From: Tim Bruijnzeels <[email-masked]>
Date: Fri, 10 Sep 2010 17:13:41 +0200

>> 4. Rename newxxxxx to xxxxx.

Oops.. I double checked our code and it seems I lied to the list.. I
said that we were using a symlink, but we are in fact doing the renames
as described here..

Using a symlink would be a bit better, so we may update our
implementation. So something like this:

1) create new dir 'new-YYMMDD-millisecond..something'
2) fill it with the new content
3) ln -sf ./new-YYMMDD-millisecond..something ./current-repos

but... below

> newxxx outside of this space and then swap in quickly, but even that's
> not atomic, and not always possible.
> 
> The thing is, it's very difficult to implement anything on the server
> side that is guaranteed to be atomic from the RP's point of view.
> There's simply too much interaction between various abstraction levels
> (fs caches, filesystems, inodes, directory scans, symlinks, rsync, ...)
> 

Even with the symlinking this problem still stands. It just makes it a
whole less likely to get to the repo between the renames and see
nothing. Content may still change during your transfer (not sure that
rsync has a session, it may just fetch the new content when it gets to
it) and relying parties may actually come to you multiple times.

As mentioned by Steve my proposed approach for relying parties only
works in a specific case (where one walks down the SIAs). So his
proposal may be more generic.

I think choosing the right strategy depends a lot on the implementation
details of the RP software. So I am not 100% sure if the WG can provide
an algorithm for RPs that is guaranteed to work. Listing some
recommendations may still be helpful though.

Tim

---

From: Rob Austein <[email-masked]>
Date: Fri, 10 Sep 2010 14:44:51 -0400

Right, the renaming-a-symlink-to-a-directory hack is old unix lore,
but it doesn't solve all problems in this space.

The specific problem that hack solves is that, on unix filesystems
where the rename() system call can be implemented as an disk block
write, one can be reasonably certain that the filename always points
to *something*; that is, this eliminates the race condition in which
the directory vanishes completely for a while, which network clients
(among other programs) find disconcerting.

But this does not solve all the problems of which readers get what
view of the universe, whether any particular reader follows the new
symlink to the new target directory, gets a mix of old directory and
new directory, etc.  That kind of thing is heavily dependent on
implementation details (eg, does the process chdir() to the directory
of interest or not?) that are way out of scope for an IETF document.

As RobK says, there are just too many paths through the implementation
maze for it to be safe to believe that anything based this closely on
a filesystem is going to support atomic operations.  This problem goes
beyond rsync, HTTP or FTP have essentially the same problem, for the
same reasons.

Relying parties already have to cope with inconsistencies due to parts
of the global database becoming unreachable (perhaps globally, perhaps
just for some relying parties).  Transient inconsistencies introduced
during the publication process are just another form of inconsistency
that relying parties have to cope with.

---

From: Stephen Kent <[email-masked]>
Date: Sun, 12 Sep 2010 17:10:50 -0400

A
>that relying parties have to cope with.

Rob,

I think we moved beyond the notion getting an inconsistent set of 
records a while ago. So, I'm confused. Are you saying that there is 
no deterministic solution that allows an RP to detect that it has 
fetched an inconsistent set of records. That's what i would like to 
see. If the suggestion is to check the manifest, I would be 
disappointed, as I think that makes it hard to distinguish between 
attacks and sync problems.  Also, as I noted in my reply to Tim, that 
approach requires fairly invasive processing, i.e., looking into a 
(verified?) manifest. My suggestion avoids that concern, although 
perhaps at the cost of an additional rsync activity. (I'm still 
interested in learning what Chris's parameterized rsync call does.)

I don't think we can go progress the repository doc without a better 
description of the problem and recommended solution approaches.

Steve

---

From: Rob Austein <[email-masked]>
Date: Sun, 12 Sep 2010 17:48:36 -0400

At Sun, 12 Sep 2010 17:10:50 -0400, Steve Kent wrote:
> 
> Are you saying that there is no deterministic solution that allows
> an RP to detect that it has fetched an inconsistent set of
> records.

Pretty much.  A RP gets what it gets, then puts together the best
picture of the world it can from what it was able to fetch.  Some of
what it was able to fetch may not validate.  Figuring out whether
validation failures were caused by a race condition, some RPKI
analogue of what would be called a "lame server" in the DNS world,
failing disk hardware on some server, a network partition, sunspots,
or enemy action may be more trouble than it's worth.  We got what we
got, we validated what we could, and we'll try again later in any
case.

Here's the key question: what do you intend the RP to do differently
based on this determination, why, and how much are you willing to pay
(in protocol complexity, convergence time, etc) to achieve this?

> That's what i would like to see. If the suggestion is to
> check the manifest, I would be disappointed, as I think that makes
> it hard to distinguish between attacks and sync problems.

Indeed.  I just doubt we're likely to do better.

> Also, as I noted in my reply to Tim, that approach requires fairly
> invasive processing, i.e., looking into a (verified?) manifest.

As I think you know, my implementation of the validation process looks
at the manifest every time anyway, so this doesn't bother me as much
as it appears to bother you.

> My suggestion avoids that concern, although perhaps at the cost of
> an additional rsync activity. (I'm still interested in learning what
> Chris's parameterized rsync call does.)

If I understand correctly, Chris's suggestion solves a slightly
different problem than the one I think we're having.  He's talking
about a way of avoiding local race conditions (eg, validator running
in parallel with rsync, validator gets confused because it sees
partially fetched data before rsync is done fetching); we're talking
about remote race conditions.  Avoiding local race conditions is
relatively easy, Chris's suggestion is one way of doing it.  Avoiding
remote conditions ranges from hard to impossible for the kinds of
protocols we've been talking about.

I respect your quest for a synchronization tool to eliminate remote
race conditions, I just don't think you're going to find one that will
work in any sane fashion with off the shelf implementations of
file-oriented protocols like rsync, http, and ftp, and I don't think
anybody wants to push deployment back by several years while we go off
to design a custom network protocol with the semantics you want.

> description of the problem and recommended solution approaches.

Agreed, so long as "this is the RP's problem, deal with it" is on the
table as one of the solutions we might recommend.