Subject: Re: NFSv4 Replication and Migration: design team conference call/Draft

From: Robert Thurlow <[email-masked]>
Date: Mon, 3 Jun 2002 09:47:13 -0600 (MDT)

> 1.-Do we want to provide for failure recovery in the migration/replication
> protocol? I know that in most cases we should be sending differential
> changes to the filesystems but I keep thinking of the case were we have a
> full (intial) migration/replication of a file system and one side involved
> in the process fails; do we want to have some type of migration
> checkpointing?

Yes; I believe that restartability in this case is a requirement.

> 2.-I think striving for a efficient bandwith utilization is a great idea so
> I wanted to make the group aware of recent work in this area that may
> relevant to the design of a a bandwith efficient migration replication
> protocol:
> 
> http://www.cs.ucsd.edu/sosp01/papers/mazieres.pdf
> 
> I think the bandwith-saving ideas presented in this paper may work great in
> migration/replication. What do you guys think?

This is an interesting paper I had not known about, but I believe
it is really only applicable with conventional filesystems traffic.
With replication/migration, you have a largely unidirectional flow
of data, and you can't benefit from caching and block recognition
as the paper describes.  The main thing would seem to be to keep
the pipe full; a streaming protocol which minimizes the risk of a
stall waiting for back-traffic from destination to source would
seem to cover us here.  Compression of data could be a benefit;
are there other ideas in the paper you believe would apply?

Rob T

---

From: "Juan Gomez" <[email-masked]>
Date: Wed, 5 Jun 2002 17:00:07 -0700

|---------+---------------------------------->
|         |           Robert Thurlow         |
|         |           <[email-masked]|
|         |           .com>                  |
|         |           Sent by:               |
|         |           owner-nfsv4-wg@sunroof.|
|         |           eng.sun.com            |
|         |                                  |
|         |                                  |
|         |           06/05/02 01:34 PM      |
|         |           Please respond to      |
|         |           Robert Thurlow         |
|         |                                  |
|---------+---------------------------------->
  >------------------------------------------------------------------------------------------------------------------------|
  |                                                                                                                        |
  |       To:       Juan Gomez/Almaden/IBM@IBMUS                                                                           |
  |       cc:       [email-masked]                                                                           |
  |       Subject:  Re: NFSv4 Replication and Migration: design team conference call/Draft                                 |
  |                                                                                                                        |
  |                                                                                                                        |
  >------------------------------------------------------------------------------------------------------------------------|

> I think I was looking at the paper more from the point of view of
> compression: recognizing similar blocks in a filesystem may help us a lot
> in compressing what we have to send during a migration, I do not have
> numbers but I think we may expect reasonable block replication on a given
> filesytem, enough to be worth exploring.

I think compression could be worthwhile to explore.  It's not clear
that we can take advantage of similar blocks except for blocks of
zeros, which we should certainly optimize.  What amount of block
replication would you expect, and under what circumstances?

I AM TRYING TO GATHER SOME REAL WORLD NUMBER ON THIS AND WILL SHARE WHEN I
HAVE THEM.

> Also in replication, I think we should have some protocol capable of
> shipping only new blocks (i.e. updates) and not the old ones already
> present in the other servers. I am not sure if we want to consider the
> complications associated with this as it requires persistent storage of
> replication-related metadata.

The protocol certainly needs to be able to send only files which have
changed, and also to send only changed regions of individual files.
Otherwise, huge files cannot be dealt with.  The draft covers this.

FAIR ENOUGH, THIS IS A GOOD DIRECTION.

Rob T

---

From: "Juan Gomez" <[email-masked]>
Date: Wed, 5 Jun 2002 17:06:35 -0700

Brent,

This is in fact in the paper, I think the issue we need to weight is how
often we use this in real life filesystems. The paper is focused on some
very spciela cases that favor the algorithm.
Perhaps we may run a replication search algorithm on filesystemns and find
that similar blocks are only 1% and then this is a hopeless alternative. It
would be nice if we could have estimates of replicated blocks in a
filesystem we need to migrate and use our block-matching algorithm on cases
where it is promissing to do so this may be another option to explore. I
think the chunking/hashing algorithms proposed on the paper may cheap
enough to predetermine block replication at a resonable CPU cost....all
this we may want to explore.

Juan

|---------+---------------------------->
|         |           Brent Callaghan  |
|         |           <[email-masked]|
|         |           m>               |
|         |           Sent by:         |
|         |           Brent.Callaghan@e|
|         |           ng.sun.com       |
|         |                            |
|         |                            |
|         |           06/05/02 02:12 PM|
|         |                            |
|---------+---------------------------->
  |                                                                                                                        |
  |       To:       Robert Thurlow <[email-masked]>                                                            |
  |       cc:       Juan Gomez/Almaden/IBM@IBMUS, [email-masked]                                             |
  |       Subject:  Re: NFSv4 Replication and Migration: design team conference call/Draft                                 |
  |                                                                                                                        |
  |                                                                                                                        |

> replication would you expect, and under what circumstances?

I'm not sure if I read it in the paper Juan referenced, but
you could in theory avoid some data transfers if you kept
track of each block of transferred data together with a
checksum.

Then when you need to transfer a block of new data in
a file, you checksum the block and see if you've transferred
it previously as part of another file.  If you get a hit,
then instead of transferring the block, you just tell the
other end where it is, and where it needs to go.

I've no idea whether this happens often enough to be
worthwhile - maybe I should go back and read Maziere's paper
again ...

             Brent

---

From: "Juan Gomez" <[email-masked]>
Date: Wed, 5 Jun 2002 17:10:46 -0700

Peter,

You may be right I just think, that as you state it would be nice exploring
or adding as an option to have the Mazieres alg dynamically switch on.
The cost of finding chunks and hashing them is important variable that
defines whether this is usable or not, I will talk to the aouthor and see
what his epxrience is.

Juan

|---------+---------------------------------->
|         |           Peter Staubach         |
|         |           <[email-masked]|
|         |           >                      |
|         |           Sent by:               |
|         |           owner-nfsv4-wg@sunroof.|
|         |           eng.sun.com            |
|         |                                  |
|         |                                  |
|         |           06/05/02 02:13 PM      |
|         |           Please respond to Peter|
|         |           Staubach               |
|         |                                  |
|---------+---------------------------------->
  |                                                                                                                        |
  |       To:       [email-masked], [email-masked]                                                          |
  |       cc:       Juan Gomez/Almaden/IBM@IBMUS, [email-masked]                                             |
  |       Subject:  Re: NFSv4 Replication and Migration: design team conference call/Draft                                 |
  |                                                                                                                        |
  |                                                                                                                        |

> worthwhile - maybe I should go back and read Maziere's paper

Between this and the sparse file detection, the cpu overheads are
possibly starting to become significant.  Looking at a block to see
whether it is all zeros is really expensive.  There needs to be a
cheaper way.

This also doesn't match real life semantics.  We will need to be able
to replicate files created with mkfile(1M) for example.  They tend
to be populated with zeros, but are fully populated for good reasons.

A block of zeros does not mean that the block is not populated.

                         ps

---

From: "Juan Gomez" <[email-masked]>
Date: Wed, 5 Jun 2002 17:20:00 -0700

David,

Even when Brent proposes the use of 32-bits checksum we should really be
thinking of hashing by a low-collision algorithm like the one use in the
paper. With that key your probability of erroneously confusing blocks are
probably less than those of your disk corrupting data and your checksum
missing the corruption. Other folks have used SHA-1 for the same purpose
and gotten no collisions ever during a long, long trial (see recent paper
on Venti coming from the folks at Bell labs working on Plan 9)

Juan

|         |           David Robinson   |
|         |           <David.Robinson@S|
|         |           un.COM>          |
|         |           06/05/02 03:02 PM|
  |                                                                                                                        |
  |       To:       Brent Callaghan <[email-masked]>                                                                    |
  |       cc:       Robert Thurlow <[email-masked]>, Juan Gomez/Almaden/IBM@IBMUS, [email-masked]|
  |       Subject:  Re: NFSv4 Replication and Migration: design team conference call/Draft                                 |
  |                                                                                                                        |
  |                                                                                                                        |

> other end where it is, and where it needs to go.

Be careful here, checksums are not generally designed to
uniquely identify a block, but to detect errors. As an
example, a 2TB storage device is all that is in theory needed
to return any 512 byte block based on a 32-bit checksum.
Clearly all the world's information is not represented
by 2TB of data. By the time you get to a high enough probability
of no error, the size of the checksum is large enough that
it is probably better to just use a lossless compression
algorithm.

             -David

---

From: "Juan Gomez" <[email-masked]>
Date: Wed, 5 Jun 2002 17:24:30 -0700

|---------+---------------------------------->
|         |           Brent Callaghan        |
|         |           <[email-masked]>    |
|         |           Sent by:               |
|         |           owner-nfsv4-wg@sunroof.|
|         |           eng.sun.com            |
|         |                                  |
|         |                                  |
|         |           06/05/02 03:13 PM      |
|         |                                  |
|---------+---------------------------------->
  |                                                                                                                        |
  |       To:       [email-masked]                                                                           |
  |       cc:                                                                                                              |
  |       Subject:  Re: NFSv4 Replication and Migration: design team conference call/Draft                                 |
  |                                                                                                                        |
  |                                                                                                                        |

> whether it is all zeros is really expensive.  There needs to be a

Yes, if moving data over a multi-gigabit network, then it's
likely cheaper just to move the zeros.  But I think a typical
application of migration will be to move the data over a
relatively low speed network, where a little CPU effort
will go a long way.

THIS IS A VERY GOOD POINT. WITH THE TERRORISTS STILL OUT THERE WE DON'T
WANT TO REPLICATE THE FILE SYSTEM IN YOUR 10th FLOOR TO A SERVER IN THE 9TH
FLOOR YOU WANT TO HAVE COPIES IN VARIOUS CITIES AT BEST, COAST TO COAST
PERHAPS. I THINK NFSv4 WAS A STEP IN THE WAN-AREA NETWORK FILE SYSTEMS WITH
LESS EMPHASYS IN LOCAL AREA.

> A block of zeros does not mean that the block is not populated.

It's not necessary to send the zeros - it's much faster just
to tell the other end to imagine some :-)

Actually, in my experience with ISDN and DSL links, the
link hardware is pretty good at simple compression.
So heroic efforts at zero compression in the protocol may
be wasted.

However, if it's something more subtle, like sending
block hashes and checksums, then that's something the
hardware cannot easily do.

             Brent

---

From: Peter Staubach <[email-masked]>
Date: Thu, 6 Jun 2002 11:41:23 -0600 (MDT)

> $ man mkfile
> No reference page found for mkfile.
> 
> but I can guess....

Sorry, I guess that it is a Solaris specific command which is used to
create swapfiles.  These files are filled with zeros to preallocate the
space.  They are fully populated files which just contain zeros to
start.

		ps