Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #4000

Re: Using free space for more fault tolerant file systems.

Cross-posted to 5 groups.

Show all headers | View raw

On Tue, 27 Sep 2011 18:05:19 -0400, Paul wrote:

> Think "QuickPar". (This article doesn't do it justice, but you have to
> start somewhere.)
> 
> http://en.wikipedia.org/wiki/Quickpar

> One of the problems with PAR, was the implementation was less than
> perfect. There is a "maths" problem with the tools in popular
> circulation, such that you can't always recover the data. There were
> some proposals on how to fix that (some kind of sparse matrix of some
> sort), but I stopped following the conversation on the subject. I did
> some testing, i.e. remove a block of data, grab a parity block, and see
> the tool recover the data, so it did work in very limited testing. But
> there are reports, from people who have enough parity blocks but can't
> get the data back.

The "maths problem" was in the first version of PAR (and in the academic
paper on which it was based), which has been deprecated for years. The
problem was fixed in PAR2, which QuickPAR uses.

Specifically: the algorithm relies upon generating an (n+m) x n matrix
(where n is the number of data blocks and m is the number of recovery
blocks) with the properties that the first n rows are an identity matrix,
and that any combination of n rows result in an invertible matrix. The
original algorithm didn't always satisfy the second constraint.

The fix is to start with a Vandermonde matrix (which inherently satisfies
the second constraint) and manipulate it using equivalence-maintaining
operations (swapping columns, multiplying a column by a scalar, adding a
multiple of another column) until the first constraint is satisfied.

Apart from the maths problem (which, in practice, meant that you might
occasionally need one or two blocks more should have been needed), there
were more significant limitations, the main ones being a limit of 255
blocks and the block size being equal to or larger than the largest file
in the set (i.e. each file was a single block).

> The PAR method is typically used on USENET, in binary groups, for
> pirating movies.

While the PAR/PAR2 implementation is mostly a usenet thing, the underlying
technology (Reed-Solomon error correction) is used far more widely:
CDs (audio and data), DSL, QR-codes, and RAID-6 all use it.

Back to comp.arch | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Using free space for more fault tolerant file systems. "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2011-09-27 19:03 +0200
  Re: Using free space for more fault tolerant file systems. "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2011-09-27 19:06 +0200
  Re: Using free space for more fault tolerant file systems. Patrick Scheible <kkt@zipcon.net> - 2011-09-27 13:49 -0700
    Re: Using free space for more fault tolerant file systems. John Gordon <gordon@panix.com> - 2011-09-27 21:21 +0000
      Re: Using free space for more fault tolerant file systems. Paul <nospam@needed.com> - 2011-09-27 18:05 -0400
        Re: Using free space for more fault tolerant file systems. Nobody <nobody@nowhere.com> - 2011-09-28 02:13 +0100
    Re: Using free space for more fault tolerant file systems. "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2011-09-28 11:47 +0200
  Re: Using free space for more fault tolerant file systems. China Blue Corn Chips <chine.bleu@yahoo.com> - 2011-09-28 06:26 -0700
    Re: Using free space for more fault tolerant file systems. "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2011-09-28 16:39 +0200
      Re: Using free space for more fault tolerant file systems. "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2011-09-28 16:43 +0200

csiph-web