Subject: [nfsv4] RFC5664 errata

From: Benny Halevy <[email-masked]>
Date: Sun, 04 Sep 2011 06:41:05 +0300

Here's a list of additional errata for rfc5664.
They essentially replace the errata currently listed in the rfc-editor
(#2017, 2018, 2019, http://www.rfc-editor.org/errata_search.php?rfc=5664&rec_status=15&presentation=table)

The most critical errata are listed below. in addition, editorial level
errata are listed down at the bottom.  These are also proposed for rfc5664bis.

Regards,

Benny

---

CORRECTIONS AND IMPORTANT CLARIFICATIONS:

========================================================================

Section 5.3.1. says:

 Offset 0:
   N = 0 / 16384 = 0
   C = 0-0/4096 = 0 (D0)
   O = 0*4096 + (0%4096) = 0

It should say:

 Offset 0:
   N = 0 / 16384 = 0
   C = (0-(0*16384)) = 0 (D0)
   O = 0*4096 + (0%4096) = 0

Notes:

Fix typo in numerical example:

========================================================================

Section 5.4.2. says:

   When parity is present in the file, then there is an additional
   computation to map from the file offset L to the offset that accounts
   for embedded parity, L'.  First compute L', and then use L' in the
   above equations for C and O.

   L = file offset, not accounting for parity
   P = number of parity devices in each stripe
   W = group_width, if not zero, else size of olo_components array
   N = L / (W-P * stripe_unit)
   L' = N * (W * stripe_unit) +
        (L % (W-P * stripe_unit))

It should say:

   When parity is present in the file, then the number of parity devices
   is taken into account in the above equations when calculating (D),
   the number of data devices in a stripe, as follows:

   P: number of parity devices in each stripe
      P = 1

   D: number of data devices in a stripe
      D = W - P

   I: parity device index
      I = D

Notes:

Clarify and simplify math for RAID-4 and RAID-5

========================================================================

Section 5.4.3. says:

   To compute the component object C, first compute the offset that
   accounts for parity L' and use that to compute C. Then rotate C to
   get C'.  Finally, increase C' by one if the parity information comes
   at or before C' within that stripe.  The following equations
   illustrate this by computing I, which is the index of the component
   that contains parity for a given stripe.

   L = file offset, not accounting for parity
   W = odm_group_width, if not zero, else size of olo_components array
   N = L / (W-1 * stripe_unit)
   (Compute L' as describe above)
   (Compute C based on L' as described above)
   C' = (C - (N%W)) % W
   I = W - (N%W) - 1
   if (C' <= I) {
     C'++
   }

It should say:

   Note that the math for RAID_5 is similar to RAID_4 only that the
   device indices for each stripe are rotated backwards.  So start with
   the equations above for RAID_4, then compute the rotation as
   described below.  Also note that the parity rotation cycle always starts
   on group boundaries so the first stripe in a group has its parity at
   device D.

   P: number of parity devices in each stripe
      P = 1

   PC: Parity Cycle
      PC = W

   R: The parity rotation index
      (N is as computed in above equations for RAID-4)
      R = N % PC

   I: parity device index
      I = (W + W - (R + 1) * P) % W

   Cr: The rotated device index
       (C is as computed in the above equations for RAID-4)
       Cr = (W + C - (R * P)) % W

   Note: W is added above to avoid negative numbers modulo math.

Notes:

1) Clarify and simplify math for RAID-4 and RAID-5.
2) Correct RAID-5 calculation.
3) Clarify parity rotation cycle reset on raid group boundaries.

========================================================================

Section 5.4.4. says:

   P is parity computed
   with XOR, and Q is a more complex equation that is not described
   here.  The equations given above for embedded parity can be used to
   map a file offset to the correct component object by setting the
   number of parity components to 2 instead of 1 for RAID4 or RAID5.
   Clients may simply choose to read data through the metadata server if
   two components are missing or damaged.

It should say:

   P is parity computed
   with XOR.  The Q computation is described in detail by Anvin [20].
   The same polynomial "x^8+x^4+x^3+x^2+1" and Galois field size of 2^8
   are used here.  Clients may simply choose to read data through the
   metadata server if two or more components are missing or damaged.

   The equations given above for embedded parity can be used to map a
   file offset to the correct component object by setting the number of
   parity components (P) to 2 instead of 1 for RAID-5 and computing the
   Parity Cycle length as the Lowest Common Multiple [21] of
   odm_group_width and P, devided by P, as described below.  Note: This
   algorithm can be used also for RAID-5 where P=1.

   P: number of parity devices
      P = 2

   PC: Parity cycle:
       PC = LCM(W, P) / P

   Q: The device index holding the Q component
      (I is as computed in the above equations for RAID-5)
      Qdev = (I + 1) % W

Notes:

1) Clarify and provide a reference for the Reed-Solomon algorithm to be used
for RAID-6.
	
2) Provide a reference for computing the parity cycle length for RAID-6.

========================================================================

Add the following references to Section 15.2.:

   [20]  Anvin, H., "The Mathematics of RAID-6", May 2009,
         <http://kernel.org/pub/linux/kernel/people/hpa/raid6.pdf>.

   [21]  The free encyclopedia, Wikipedia., "Least common multiple",
         April 2011,
         <http://en.wikipedia.org/wiki/Least_common_multiple>.

Notes:

1) Provide a reference for the Reed-Solomon algorithm to be used
for RAID-6.
	
2) Provide a reference for computing the parity cycle length for RAID-6.

========================================================================

EDITORIAL CHANGES:

========================================================================

Section 5.3.1. says:

5.3.1.  Simple Striping

   The mapping from the logical offset within a file (L) to the
   component object C and object-specific offset O is defined by the
   following equations:

   L = logical offset into the file
   W = total number of components
   S = W * stripe_unit
   N = L / S
   C = (L-(N*S)) / stripe_unit
   O = (N*stripe_unit)+(L%stripe_unit)

   In these equations, S is the number of bytes in a full stripe, and N
   is the stripe number.  C is an index into the array of components, so
   it selects a particular object storage device.  Both N and C count
   from zero.  O is the offset within the object that corresponds to the
   file offset.  Note that this computation does not accommodate the
   same object appearing in the olo_components array multiple times.

...

   Offset 0:
     N = 0 / 16384 = 0
     C = (0-(0*16384)) = 0 (D0)
     O = 0*4096 + (0%4096) = 0

   Offset 4096:
     N = 4096 / 16384 = 0
     C = (4096-(0*16384)) / 4096 = 1 (D1)
     O = (0*4096)+(4096%4096) = 0

   Offset 9000:
     N = 9000 / 16384 = 0
     C = (9000-(0*16384)) / 4096 = 2 (D2)
     O = (0*4096)+(9000%4096) = 808

   Offset 132000:
     N = 132000 / 16384 = 8
     C = (132000-(8*16384)) / 4096 = 0 (D0)
     O = (8*4096) + (132000%4096) = 33696

It should say:

5.3.1.  Simple Striping

   The mapping from the logical offset within a file (L) to the
   component object C and object-specific offset O is defined by the
   following equations:

   L: logical offset into the file

   W: stripe width
       W = size of olo_components array

   S: number of bytes in a stripe
       S = W * stripe_unit

   N: stripe number
       N = L / S

   C: component index corresponding to L
      C = (L % S) / stripe_unit

   O: The component offset corresponding to L
      O = (N * stripe_unit) + (L % stripe_unit)

   Note that this computation does not accommodate the same object
   appearing in the olo_components array multiple times.  Therefore the
   server may not return layouts with the same object appearing multiple
   times.  If needed the server can return multiple layout segments each
   covering a single instance of the object.

...

   Offset 0:
     N = 0 / 16384 = 0
     C = (0 % 16384) /4096 = 0 (D0)
     O = 0*4096 + (0%4096) = 0

   Offset 4096:
     N = 4096 / 16384 = 0
     C = (4096 % 16384) / 4096 = 1 (D1)
     O = (0*4096)+(4096%4096) = 0

   Offset 9000:
     N = 9000 / 16384 = 0
     C = (9000 % 16384) / 4096 = 2 (D2)
     O = (0*4096)+(9000%4096) = 808

   Offset 132000:
     N = 132000 / 16384 = 8
     C = (132000 % 16384) / 4096 = 0 (D0)
     O = (8*4096) + (132000%4096) = 33696

Notes:

Clarify and simplify math for simple striping.

========================================================================

Section 5.3.2. says:

5.3.2.  Nested Striping

   The odm_group_width and odm_group_depth parameters allow a nested
   striping pattern. odm_group_width defines the width of a data stripe
   and odm_group_depth defines how many stripes are written before
   advancing to the next group of components in the list of component
   objects for the file.  The math used to map from a file offset to a
   component object and offset within that object is shown below.  The
   computations map from the logical offset L to the component index C
   and offset relative O within that component object.

   L = logical offset into the file
   W = total number of components
   S = stripe_unit * group_depth * W
   T = stripe_unit * group_depth * group_width
   U = stripe_unit * group_width
   M = L / S
   G = (L - (M * S)) / T
   H = (L - (M * S)) % T
   N = H / U
   C = (H - (N * U)) / stripe_unit + G * group_width
   O = L % stripe_unit + N * stripe_unit + M * group_depth * stripe_unit

   In these equations, S is the number of bytes striped across all
   component objects before the pattern repeats.  T is the number of
   bytes striped within a group of component objects before advancing to
   the next group.  U is the number of bytes in a stripe within a group.
   M is the "major" (i.e., across all components) stripe number, and N
   is the "minor" (i.e., across the group) stripe number.  G counts the
   groups from the beginning of the major stripe, and H is the byte
   offset within the group.

   For example, consider an object striped over 100 devices with a
   group_width of 10, a group_depth of 50, and a stripe_unit of 1 MB.
   In this scheme, 500 MB are written to the first 10 components, and
   5000 MB are written before the pattern wraps back around to the first
   component in the array.

   Offset 0:
     W = 100
     S = 1 MB * 50 * 100 = 5000 MB
     T = 1 MB * 50 * 10 = 500 MB
     U = 1 MB * 10 = 10 MB
     M = 0 / 5000 MB = 0
     G = (0 - (0 * 5000 MB)) / 500 MB = 0
     H = (0 - (0 * 5000 MB)) % 500 MB = 0
     N = 0 / 10 MB = 0
     C = (0 - (0 * 10 MB)) / 1 MB + 0 * 10 = 0
     O = 0 % 1 MB + 0 * 1 MB + 0 * 50 * 1 MB = 0

   Offset 27 MB:
     M = 27 MB / 5000 MB = 0
     G = (27 MB - (0 * 5000 MB)) / 500 MB = 0
     H = (27 MB - (0 * 5000 MB)) % 500 MB = 27 MB
     N = 27 MB / 10 MB = 2
     C = (27 MB - (2 * 10 MB)) / 1 MB + 0 * 10 = 7
     O = 27 MB % 1 MB + 2 * 1 MB + 0 * 50 * 1 MB = 2 MB

   Offset 7232 MB:
     M = 7232 MB / 5000 MB = 1
     G = (7232 MB - (1 * 5000 MB)) / 500 MB = 4
     H = (7232 MB - (1 * 5000 MB)) % 500 MB = 232 MB
     N = 232 MB / 10 MB = 23
     C = (232 MB - (23 * 10 MB)) / 1 MB + 4 * 10 = 42
     O = 7232 MB % 1 MB + 23 * 1 MB + 1 * 50 * 1 MB = 73 MB

It should say:

5.3.2.  Nested Striping

   The odm_group_width and odm_group_depth parameters allow a nested
   striping pattern. odm_group_width defines the width of a data stripe
   and odm_group_depth defines how many stripes are written before
   advancing to the next group of components in the list of component
   objects for the file.  The math used to map from a file offset to a
   component object and offset within that object is shown below.  The
   computations map from the logical offset L to the component index C
   and offset relative O within that component object.

   L: logical offset into the file

   FW: total number of components
       FW = size of olo_components array

   W: stripe width
      W = group_width, if not zero, else FW

   group_count: number of groups
      group_count = FW / group_width, if group_width is not zero, else 1

   D: number of data devices in a stripe
      D = W

   U: number of data bytes in a stripe within a group
      U =  D * stripe_unit

   T: number of bytes striped within a group of component objects
      (before advancing to the next group)
      T = U * group_depth

   S: number of bytes striped across all component objects
      (before the pattern repeats)
      S = T * group_count

   M: The "major" (i.e., across all components) cycle number
      M = L / S

   G: group number from the beginning of the major cycle
      G = (L % S) / T

   H: byte offset within the last group
      H = (L % S) % T

   N: The "minor" (i.e., across the group) stripe number
      N = H / U

   C: component index corresponding to L
      C = (G * D) + ((H % U) / stripe_unit)

   O: The component offset corresponding to L
      O = (M * group_depth * stripe_unit) + (N * stripe_unit) +
          (L % stripe_unit)

   For example, consider an object striped over 100 devices with a
   group_width of 10, a group_depth of 50, and a stripe_unit of 1 MB.
   In this scheme, 500 MB are written to the first 10 components, and
   5000 MB are written before the pattern wraps back around to the first
   component in the array.

   Offset 0:
     W = 100
     group_count = 100 / 10 = 10
     D = 10
     U = 1 MB * 10 = 10 MB
     T = 10 MB * 50 = 500 MB
     S = 500 MB * 10 = 5000 MB
     M = 0 / 5000 MB = 0
     G = (0 % 5000 MB) / 500 MB = 0
     H = (0 % 5000 MB) % 500 MB = 0
     N = 0 / 10 MB = 0
     C = (0 * 10) + ((0 % 10 MB) / 1 MB) = 0
     O = (0 * 50 * 1 MB) + (0 * 1 MB) + (0 % 1 MB) = 0

   Offset 27 MB:
     M = 27 MB / 5000 MB = 0
     G = (27 MB % 5000 MB) / 500 MB = 0
     H = (27 MB % 5000 MB) % 500 MB = 27 MB
     N = 27 MB / 10 MB = 2
     C = (0 * 10) + ((27 MB % 10 MB) / 1 MB) = 7
     O = (0 * 50 * 1 MB) + (2 * 1 MB) + (27 MB % 1 MB) = 2 MB

   Offset 7232 MB:
     M = 7232 MB / 5000 MB = 1
     G = (7232 MB % 5000 MB) / 500 MB = 4
     H = (7232 MB % 5000 MB) % 500 MB = 232 MB
     N = 232 MB / 10 MB = 23
     C = (4 * 10) + ((232 MB % 10 MB) / 1 MB) = 42
     O = (1 * 50 * 1 MB) + (23 * 1 MB) + (7232 MB % 1 MB) = 73 MB

Notes:

Clarify and simplify math for nested striping.

========================================================================

Section 5.3.3. says:

5.3.3.  Mirroring

   The odm_mirror_cnt is used to replicate a file by replicating its
   component objects.  If there is no mirroring, then odm_mirror_cnt
   MUST be 0.  If odm_mirror_cnt is greater than zero, then the size of
   the olo_components array MUST be a multiple of (odm_mirror_cnt+1).
   Thus, for a classic mirror on two objects, odm_mirror_cnt is one.
   Note that mirroring can be defined over any RAID algorithm and
   striping pattern (either simple or nested).  If odm_group_width is
   also non-zero, then the size of the olo_components array MUST be a
   multiple of odm_group_width * (odm_mirror_cnt+1).  Replicas are
   adjacent in the olo_components array, and the value C produced by the
   above equations is not a direct index into the olo_components array.
   Instead, the following equations determine the replica component
   index RCi, where i ranges from 0 to odm_mirror_cnt.

   C = component index for striping or two-level striping
   i ranges from 0 to odm_mirror_cnt, inclusive
   RCi = C * (odm_mirror_cnt+1) + i

It should say:

5.3.3.  Mirroring

   The odm_mirror_cnt is used to replicate a file by replicating its
   component objects.  If there is no mirroring, then odm_mirror_cnt
   MUST be 0.  If odm_mirror_cnt is greater than zero, then the size of
   the olo_components array MUST be a multiple of (odm_mirror_cnt+1).
   Thus, for a classic mirror on two objects, odm_mirror_cnt is one.
   Note that mirroring can be defined over any RAID algorithm and
   striping pattern (either simple or nested).  If odm_group_width is
   also non-zero, then the size of the olo_components array MUST be a
   multiple of odm_group_width * (odm_mirror_cnt+1).  Note that
   odm_group_width does not account for mirrors.  Replicas are adjacent
   in the olo_components array, and the value C produced by the above
   equations is not a direct index into the olo_components array.
   Instead, the following equations determine the replica component
   index RCi, where i ranges from 0 to odm_mirror_cnt.

   FW = size of olo_components array / (odm_mirror_cnt+1)

   C = component index for striping or two-level striping
       as calculated using above equations

   i ranges from 0 to odm_mirror_cnt, inclusive
   RCi = C * (odm_mirror_cnt+1) + i

Notes:

Clarify math for mirroring.

========================================================================

Add the following paragraph to section 5.4.5.:

   Many alternative encoding schemes exist for P>=2 [22].  These involve
   P or Q equations different than those used in PNFS_OSD_RAID_PQ.
   Thus, if one of these schemes is to be used in the future, a distinct
   value must be added to pnfs_osd_raid_algorithm4 for it.  While Reed-
   Solomon codes are well understood, recently discovered schemes such
   as Liberation codes are more computationally efficient for small
   group_widths, and Cauchy Reed-Solomon codes are more computationally
   efficient for higher values of P.

Notes:

Clarify non-use of alternative algorithms for RAID_PQ.

========================================================================

Add the following reference to Section 15.2.:

   [22]  Plank, James S., and Luo, Jianqiang and Schuman, Catherine D.
         and Xu, Lihao and Wilcox-O'Hearn, Zooko, "A Performance
         Evaluation and Examination of Open-source Erasure Coding
         Libraries for Storage", 2007.

Notes:

Provide a reference for alternative RAID-6 encoding schemes.

========================================================================

Authors' Addresses says:

   Benny Halevy
   Panasas, Inc.
   1501 Reedsdale St. Suite 400
   Pittsburgh, PA  15233
   USA

   Phone: +1-412-323-3500
   EMail: [email-masked]
   URI:   http://www.panasas.com/

It should say:

   Benny Halevy
   Tonian, Inc.

   Email: [email-masked]
   URI:   http://www.tonian.com/

Notes:

Update Benny Halevy's organization.

========================================================================

Add Boaz Harrosh as author:

   Boaz Harrosh
   Panasas, Inc.
   1501 Reedsdale St. Suite 400
   Pittsburgh, PA  15233
   USA

   Phone: +1-412-323-3500
   Email: [email-masked]
   URI:   http://www.panasas.com/

========================================================================