[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00 01

NFSv4                                                          M. Eisler
Internet-Draft                                                    NetApp
Intended status: Standards Track                        October 27, 2008
Expires: April 30, 2009


                Storage De-Duplication Awareness in NFS
                 draft-eisler-nfsv4-pnfs-dedupe-00.txt

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on April 30, 2009.

Abstract

   This Internet-Draft describes a means to add awareness of de-
   duplication storage to NFS.

Requirements Language

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [1].







Eisler                   Expires April 30, 2009                 [Page 1]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


Table of Contents

   1.  Introduction and Motivation  . . . . . . . . . . . . . . . . .  3
   2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  4
   3.  Scope of De-Duplication  . . . . . . . . . . . . . . . . . . .  5
   4.  Overview of De-Duplication via pNFS  . . . . . . . . . . . . .  5
   5.  The Definition of De-Duplication Layouts . . . . . . . . . . .  5
     5.1.  Name of De-Duplication Striping Layout Type  . . . . . . .  5
     5.2.  Value of De-Duplication Striping Layout Type . . . . . . .  6
     5.3.  Definition of the da_addr_body Field of the
           device_addr4 Data Type . . . . . . . . . . . . . . . . . .  6
     5.4.  Definition of the loh_body Field of the layouthint4
           Data Type  . . . . . . . . . . . . . . . . . . . . . . . .  7
     5.5.  Definition of the loc_body Field of the
           layout_content4 Data Type  . . . . . . . . . . . . . . . .  8
     5.6.  Definition of the lou_body Field of the layoutupdate4
           Data Type  . . . . . . . . . . . . . . . . . . . . . . . . 20
     5.7.  Storage Access Protocols . . . . . . . . . . . . . . . . . 20
     5.8.  Revocation of Layouts  . . . . . . . . . . . . . . . . . . 20
     5.9.  Recovery . . . . . . . . . . . . . . . . . . . . . . . . . 21
       5.9.1.  Failure and Restart of Client  . . . . . . . . . . . . 21
       5.9.2.  Failure and Restart of Server  . . . . . . . . . . . . 21
       5.9.3.  Failure and Restart of Storage Device  . . . . . . . . 21
   6.  Negotiation  . . . . . . . . . . . . . . . . . . . . . . . . . 21
   7.  Operational Recommendation for Deployment  . . . . . . . . . . 21
   8.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 21
   9.  Security Considerations  . . . . . . . . . . . . . . . . . . . 21
   10. IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 22
   11. Normative References . . . . . . . . . . . . . . . . . . . . . 22
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 22
   Intellectual Property and Copyright Statements . . . . . . . . . . 24




















Eisler                   Expires April 30, 2009                 [Page 2]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


1.  Introduction and Motivation

   De-duplication is an emerging trend in the data storage.  De-
   duplication means that two files that have common content derive that
   content from a common location on the same storage device.  As a
   result, the total storage used is less than the total length of each
   file.  A holes in a file represents a primitive form of de-
   duplication.  De-duplication is also called folding.

   De-duplication is accomplished in several ways including,

   o  Hierarchical de-duplication, where one file is derived from
      another, usually by one file starting of as copy of another, but
      zero, or nearly zero bytes of data are actually copied or moved.
      Instead, the two files share common blocks of data storage.  An
      example is a snapshot, where a snapshot is made of a file system,
      such that the snapshot and active file system are equal at the
      time snapshot is taken, and share the same data storage, and thus
      are effectively copies that involve zero or near zero movement of
      data.  As the source file system changes, the number of shared
      blocks of data storage reduces.  A variation of this is a writable
      snapshot (aka clone) which is taken of a file system.  In this
      variation as the source and cloned file systems each change, there
      are fewer shared blocks.

   o  In-line de-duplication, where a storage access protocol initiator
      (e.g. an NFS client) creates content via write operations, and the
      target of the storage access protocol checks if the content being
      written is duplicated some where else on the target's storage.  If
      so, the data is not written, but instead the logical content
      refers to the duplicate.

   o  Background de-duplication, where a background task on the storage
      access protocol target scans for duplicate blocks, and frees all
      but one of the duplicates, mapping the pointers to the now free
      blocks to the remaining duplicate.

   The use of de-duplicated storage does not require changes to the NFS
   protocol.  However if the NFS client is caching content from an NFS
   server that provides access to de-duplicated files, without changes
   to the protocol, inefficient use of the resources like memory and
   network bandwidth will result.  E.g., two files of length 1024 bytes
   are exactly the same and are de-duplicated.  The client reads, and
   caches the first file.  A process on the client requests to read the
   second file.  If the client were aware the second file was a
   duplicate of the first, it would not have read the second file, nor
   would it have to cache the second file.  A classic use case is
   hypervisors, which switch between multiple guest operating systems on



Eisler                   Expires April 30, 2009                 [Page 3]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


   a single physical computer.  If each of these guest operating systems
   were cloned from a single source, or if each guest was installed from
   the same operating system installation image, then much of the data
   of each guest might be highly de-duplicated.  De-duplication
   awareness is consistent with the typical reasons for deploying a
   hypervisor: reducing costs by reducing utilization of memory,
   computer cycles, and network.

   This document describes a method by which NFSv4.1 clients can be
   aware of de-duplicated storage.  This document does not require a new
   minor version of NFSv4.  Instead, it requires several new layout
   types, and thus uses the pNFS protocol [2].

   The XDR description is provided in this document in a way that makes
   it simple for the reader to extract into a ready to compile form.
   The reader can feed this document into the following shell script to
   produce the machine readable XDR description of the de-duplication
   layout:

   #!/bin/sh
   grep "^  *///" | sed 's?^  *///  ??' | sed 's?^.*///??'


   I.e. if the above script is stored in a file called "extract.sh", and
   this document is in a file called "spec.txt", then the reader can do:

    sh extract.sh < spec.txt > dd.x

   The effect of the script is to remove leading white space from each
   line of the specification, plus a sentinel sequence of "///".


2.  Terminology

   o  Source file, the file that contains the de-duplicated data.

   o  Target file, the file the client has opened.

   o  Block, the smallest unit of de-duplication that the server is
      willing to support.

   o  Slab, a byte range that refers to lists of other byte ranges that
      contain de-duplicated data (either in whole, or part).  A slab can
      refer to a lists of smaller slabs, or lists of blocks.

   o  Regular file: An object of file type NF4REG or NF4NAMEDATTR.





Eisler                   Expires April 30, 2009                 [Page 4]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


3.  Scope of De-Duplication

   This document only de-duplicates the data contents of regular files.
   Everything else is considered metadata, and de-duplication of
   metadata is not considered in this document.  [[Comment.1: Some
   metadata, including the contents of directories and symbolic links,
   as well as attributes (e.g.  ACLs) are practical to de-duplicate.  A
   future revision of this document might address de-duplication of
   metadata.]]


4.  Overview of De-Duplication via pNFS

   Providing awareness of de-duplication to clients needs to be
   practical.  If the data structures the server provides the client are
   not compact, or require expensive processing, then de-duplication
   awareness is not practical.  The approach presented in this document
   uses leaf bitmaps to indicate whether a byte range of a file has been
   de-duplicated, and if so from what offset of what file.  Since the
   granularity of de-duplication will vary by implementation, and by
   file, the NFS server has the option of providing indirect bitmaps
   that refer to bitmaps of finer grained byte ranges.  An indirect
   bitmap can refer to another indirect bitmap or a leaf bitmap.

   As noted in Section 1, de-duplication can be the result of
   hierarchical, inline, or background processes.  The approach to
   providing awareness of de-duplication allows servers to optimize for
   any approach.

   NFSv4.1 introduces pNFS, which allows clients to access data from
   multiple storage devices.  This means that the NFS server is
   distributed across a set of nodes on a network.  Such a server might
   be capable of de-duplication among the server's nodes.  The de-
   duplication awareness feature will allow servers to present awareness
   of cross-node de-duplication to NFS clients.


5.  The Definition of De-Duplication Layouts

5.1.  Name of De-Duplication Striping Layout Type

   There are multiple de-duplication layout types, in order to support
   multiple levels of indirection plus a leaf level.  Since the maximum
   sized file in pNFS is 2^64 - 1 bytes, a total of 63 levels of
   indirection are provided.  If for some reason a server needs more
   levels of indirection, the server will use a layout type from the
   private use range, 0x80000000 to 0xFFFFFFFF.




Eisler                   Expires April 30, 2009                 [Page 5]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


   The name of the top-level de-duplication layout type is
   LAYOUT4_DEDUP_TOP.  The names of the remaining de-duplication layout
   types are LAYOUT4_DEDUP_LEVEL_<xx>, where <xx> is a two digit decimal
   number that ranges between 02 and 64.  The server MUST NOT return
   LAYOUT4_DEDUP_LEVEL_<xx> in the response to a GETATTR request for the
   fs_layout_type attribute.

5.2.  Value of De-Duplication Striping Layout Type

   The value LAYOUT4_DEDUP_TOP is TBD1.  The values of
   LAYOUT4_DEDUP_LEVEL_<xx> are TBD02 through TBD64.

5.3.  Definition of the da_addr_body Field of the device_addr4 Data Type

   ///  %#include "nfs4_prot.h"
   ///
   ///  %/* Encoded in the da_addr_body field. */
   ///
   ///  union dd_layout_addr switch (bool ddla_simple) {
   ///    case TRUE:
   ///      multipath_list4 ddla_simple_addr;
   ///    case FALSE:
   ///      layouttype4     ddla_complex_addr;
   ///  };


                                 Figure 1

   The device address is only used in leaf layouts, and even then, only
   when cross server-node de-duplication is in effect.  There are two
   types of device addresses, a simple network address, with zero or
   more alternate addresses for multipathing, or a complex address which
   is the value of another layout type.  The value of
   ddla_complex_addr.ddldp_ltype MUST NOT be LAYOUT4_DEDUP_TOP or any of
   LAYOUT4_DEDUP_LEVEL_<xx>.
















Eisler                   Expires April 30, 2009                 [Page 6]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


5.4.  Definition of the loh_body Field of the layouthint4 Data Type

   ///  enum dd_layout_hint_care4 {
   ///
   ///         DD4_CARE_STRIPE_UNIT_SIZE    = 0x040,
   ///         DD4_CARE_STRIPE_UNIT_ALIGN   = 0x100
   ///  };
   ///  %
   ///  %/* Encoded in the loh_body field of type layouthint4: */
   ///  %
   ///  struct dd_layouthint4 {
   ///         uint32_t       ddlh_care;
   ///         length4        ddlh_stripe_unit_size;
   ///         length4        ddlh_stripe_unit_align;
   ///  };

                                 Figure 2

   The layout-type specific content for the LAYOUT4_DEDUP_TOP layout
   type is composed of three fields.  The first field, ddlh_care, is a
   set of flags indicating which values of the hint the client cares
   about.  If DD4_CARE_STRIPE_UNIT_SIZE is set, then the client
   indicates in the second field, preferred unit of granularity for de-
   duplication in bytes.  If DD4_CARE_STRIPE_UNIT_ALIGN is set, then the
   client indicates in the third field, the preferred minimum alignment
   de-duplicated units.  For example, if the client specifies
   ddlh_stripe_unit_size as 1024, and ddlh_stripe_unit_align as 128,
   then if two files have in common content a string of bytes that is
   1024 bytes long, and the string is at offset zero in the first file,
   and offset 1024 + 128 = 1152 in the second file, then the client
   would like the server to de-duplicate the common 1024 byte string.
   Note that the leaf layouts returned by the server are unable to
   indicate byte ranges that are not whole multiple of the unit size the
   server uses, so if the server accepts a layout hint with
   ddlh_stripe_unit_align less than ddlh_stripe_unit_size, it will
   report units that are equal to ddlh_stripe_unit_align.  If the client
   specifies a value in ddlh_stripe_unit_align that is greater than the
   value of ddlh_stripe_unit_size, the server will ignore the
   ddlh_stripe_unit_align hint.












Eisler                   Expires April 30, 2009                 [Page 7]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


5.5.  Definition of the loc_body Field of the layout_content4 Data Type

   ///  %/*
   ///  %/* How the bits of each element
   ///  % * of ddll_blockmap are split up
   ///  % */
   ///  const DDLL4_BLKMAP_MASK_ACTIVE      = 0x8000000000000000;
   ///
   ///  %/* The remain bits follow DDLL4_BITS_* */
   ///  const DDLL4_BLKMAP_MASK_PARTITIONED = 0x7FFFFFFFFFFFFFFF;
   ///
   ///  %/* These constants index into ddll_bmap_partition */
   ///  const DDLL4_BITS_FOR_DEVID_IDX   = 0;
   ///  const DDLL4_BITS_FOR_FH_IDX      = 1;
   ///  const DDLL4_BITS_FOR_BLK_NUM_IDX = 2;
   ///
   ///  struct dd_layout_leaf4 {
   ///    length4   ddll_block_size;
   ///
   ///  % /* ddll_blockmap_partition[0-2] MUST add up to 63 */
   ///
   ///    opaque    ddll_blockmap_partition[4];
   ///    verifier4 ddll_fhsuffix;
   ///    nfs_fh4   ddll_fhlist<>;
   ///    uint64_t  ddll_change_attr<>;
   ///    deviceid4 ddll_devlist<>;
   ///    uint64_t  ddll_blockmap<>;
   ///  };
   ///
   ///  struct dd_layout_indirect4 {
   ///    length4     ddli_slab_size;
   ///    layouttype4 ddli_next_level;
   ///    bitmap4     ddli_bitmap;
   ///  };
   ///
   ///  union dd_layout4_u switch (bool ddl_is_leaf) {
   ///    case TRUE:
   ///      dd_layout_leaf4     ddl_leaf;
   ///    case FALSE:
   ///      dd_layout_indirect4 ddl_indirect;
   ///  };
   ///  struct dd_layout4 {
   ///    offset4      ddl_firstoff;
   ///    offset4      ddl_lastoff;
   ///    dd_layout4_u ddl_u;
   ///  };





Eisler                   Expires April 30, 2009                 [Page 8]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


                                 Figure 3

   The first fields further bound the layout.

   o  ddl_firstoff, the first offset in the file that the layout has de-
      duplication information for.  The relationship between the
      lo_offset field of the layout4 data type that envelops the de-
      duplication layout and ddl_firstoff is that ddl_firstoff MUST be
      greater than or equal to lo_offset.  If ddl_firstoff is not equal
      to lo_offset, then this means that the byte range from lo_offset
      through ddl_firstoff - 1 inclusive either has not been de-
      duplicated or the server has decided to not provide the
      information.  The value of the field ddl_firstoff MUST be a whole
      multiple of ddli_slab_size or ddll_block_size.

   o  ddl_lastoff, the last offset in the file that the layout has de-
      duplication information for.  Field ddl_lastoff MUST be greater
      than or equal to ddl_firstoff.  Field ddl_lastoff MUST be less
      than or equal to lo_offset + lo_length - 1.  If the difference
      between ddl_lastoff and lo_offset + lo_length - 1 exceeds zero,
      then this means that byte range from offset ddl_lastoff + 1
      through lo_offset + lo_length - 1 inclusive either has not be been
      de-duplicated or the server has decided to not provide the
      information.  The value of the ddl_lastoff + 1 MUST be a whole
      multiple of ddli_slab_size or ddll_block_size, even if this means
      ddl_lastoff goes beyond the end of file.

   The remainder of the de-duplication layout is either a leaf layout or
   an indirect layout.

   An indirect layout consists of,

   o  ddli_slab_size is the length, in bytes of each slab represented by
      the ddli_bitmap bitmap array.

   o  ddli_next_level is the layout type the NFS client MUST use when
      using LAYOUTGET to get finer grained de-duplication information
      about the de-duplication of one or more slabs.  This field SHOULD
      be one of LAYOUT4_DEDUP_LEVEL_<xx>.  The use of ddli_next_level
      provides a hint to the server for what slab or block size to use
      on the next level of de-duplication.

   o  ddli_bitmap, is a bitmap.  If bit N is set in ddli_bitmap, then
      this means that slab N has de-duplicated content.  Each bit
      respects a byte range (a slab) of size ddli_slab_size, such that
      ddl_firstoff is that start of the first slab (slab zero, relative
      to ddl_firstoff), and ddl_lastoff is the start of the last slab.
      Slab N represents the byte range ddl_firstoff + N * ddli_slab_size



Eisler                   Expires April 30, 2009                 [Page 9]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


      to ddl_firstoff + (N + 1) * ddli_slab_size - 1, inclusive.  The
      field ddli_bitmap is an array of elements each consisting of a 32
      bit unsigned integer.  The number of elements in ddli_bitmap MUST
      be greater than or equal to ((((ddl_lastoff - ddl_firstoff) + 1) /
      ddli_slab_size) / 32) rounded up to the next whole number.

   A leaf layout consists of,

   o  ddll_block_size is the length, in bytes of each slab represented
      by the ddll_blockmap array.

   o  ddll_blockmap_partition is an array of bytes, the first three of
      which are inspected by the client.  This array indicates how each
      element of ddll_blockmap is partitioned.

   o  ddll_fhlist is an array of zero or more filehandles.  Each element
      of ddll_blockmap can correspond to a filehandle in ddll_fhlist.
      Each filehandle represents a source file that has a de-duplicated
      block that it shares with the target file.  If the array is of
      zero length, then the source file for all de-duplicated blocks is
      the target file.

   o  ddll_fhsuffix MUST be appended to each filehandle in ddll_fhlist
      that the client uses for READ or LAYOUTGET operations.  This
      allows the server to detect if the client is using an invalid
      layout.

   o  ddll_change_attr is an array of zero or more change attributes.
      If the array is not zero in length, then each element corresponds
      an element in ddll_fhlist with the same position in the array.
      I.e. ddll_change_attr[i] is the change attribute for the source
      file identified by ddll_fhlist[i].  If the array is of zero
      length, then the server is promising to recall the byte ranges of
      the layout that refer to each file identified in the ddll_fhlist
      array.  If the ddll_fhlist array is of zero length, and the
      ddll_change_attr array has one element, then ddll_change_attr[0]
      is the change attribute for the source file, which also happens to
      be the target file.

   o  ddll_devlist is an array of zero or more device IDs, for the
      purpose of enabling cross-node de-duplication.  Each element of
      ddll_blockmap can correspond to a device ID in ddll_devlist.  Each
      device ID represents a device that has a source file with a de-
      duplicated block.  The device ID is always for a LAYOUT4_DEDUP_TOP
      device, and can either map to a network address of an MDS, or a
      non-de-duplication layout type.  The device ID will map to an MDS
      network address if the source file has not been striped.
      Otherwise, the device ID will be the layout type used for striping



Eisler                   Expires April 30, 2009                [Page 10]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


      the file.  By providing the layout type, the client does not have
      to send a GETATTR request on the source file for fs_layout_type
      attribute.

   o  ddll_blockmap is an array of elements, each a 64 bit unsigned
      integer.  Each element corresponds to a block of size
      ddll_block_size.  E.g., the first element, ddll_blockmap[0]
      corresponds to the byte range, ddl_firstoff through ddl_firstoff +
      ddll_block_size - 1 inclusive.

      *  If ddll_blockmap[i] & DDLL4_BLKMAP_MASK_ACTIVE is non-zero,
         then this element corresponds to a block that is de-duplicated.
         Otherwise, the element does not correspond to a de-duplicated
         block, and the rest of the element is undefined.

      *  The mask ddll_blockmap[i] & DDLL4_BLKMAP_MASK_PARTITIONED
         represents a bit field that is partitioned according to the
         content of ddll_blockmap_partition.

         The element ddll_blockmap_partition[DDLL4_BITS_FOR_DEVID_IDX]
         indicates how many bits at the start of the bit field are for
         indexing into the ddll_devlist array.  The number of elements
         in ddll_devlist MUST be less than or equal to
         2^ddll_blockmap_partition[DDLL4_BITS_FOR_DEVID_IDX].  If
         ddll_blockmap_partition[DDLL4_BITS_FOR_DEVID_IDX] is zero, then
         this means that the blocks of the source file come from the
         same MDS as the target file.

         The element ddll_blockmap_partition[DDLL4_BITS_FOR_FH_IDX]
         indicates how many bits in the middle of the bit field are for
         indexing into the ddll_fhlist array.  The number of elements in
         ddll_fhlist MUST ne less than or equal to
         2^ddll_blockmap_partition[DDLL4_BITS_FOR_FH_IDX].  If
         ddll_blockmap_partition[DDLL4_BITS_FOR_FH_IDX] is zero, this
         means that the source file is the same as the target file in
         every element of ddll_blockmap_partition.

         The element ddll_blockmap_partition[DDLL4_BITS_FOR_BLK_NUM_IDX]
         indicates how many bits at the end of the bit field correspond
         to an absolute block number into the source file.  The absolute
         offset is calculated by computing the product of
         ddll_block_size and the absolute block number.  If
         ddll_blockmap_partition[DDLL4_BITS_FOR_BLK_NUM_IDX] is zero,
         then this means the absolute block number of the source is the
         same as the absolute block number of the target.

         The dynamic partitioning of the ddll_blockmap element allows
         for several optimizations.  If the de-duplication in the range



Eisler                   Expires April 30, 2009                [Page 11]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


         identified by the layout is due to hierarchical de-duplication,
         then there is no need for a block number, so
         ddll_blockmap_partition[DDLL4_BITS_FOR_BLK_NUM_IDX] will be
         zero.  If there is no cross node de-duplication in the range
         then ddll_blockmap_partition[DDLL4_BITS_FOR_DEVID_IDX] will be
         zero.  If all the de-duplication in the range is confined to
         the target file, i.e. the duplicate blocks were only in the
         target file and no other file, then
         ddll_blockmap_partition[DDLL4_BITS_FOR_FH_IDX] will be zero.

   An outline for an algorithm for processing a read() system call when
   the potential for de-duplicated data exists follows.  This algorithm
   illustrates how the layout is interpreted.  In this algorithm, we
   assume that the client always starts with a layout that spans the
   entire file.


   /*
    * Returns a vector call "result" of elements
    * containing key / value pairs of ((offset,
    * length), (status, source_mds, source_fh,
    * source_offset)).
    */

   dedupe_read(read_offset, read_length, target_fh,
       layout4 logr_layout[]) {

     if (number of elements in logr_layout == zero)
     {
       result[(read_offset, read_length)] =
           NO_DEDUP_AVAILABLE;

       return result;
     }

     for i from the end of logr_layout to start {
       if (logr_layout[i].lo_offset > read_offset) {
         continue;
       }

       /* check for range split across segments */
       if (logr_layout[i].lo_length <
           read_length) {

         read_offset_A = read_offset;
         read_length_A = logr_layout[i].lo_length;
         read_offset_B = logr_layout[i+1].lo_offset;
         read_length_B = read_length -



Eisler                   Expires April 30, 2009                [Page 12]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


           read_length_A;

         result[(read_offset_A, read_length_A)] =
           dedupe_read(read_offset_A, read_length_A,
           target_fh, logr_layout);

         result[(read_offset_B, read_length_B)] =
           dedupe_read(read_offset_B, read_length_B,
           target_fh, logr_layout);

         return result;
       }

       last_offset = read_offset + read_length - 1;

       if (read_offset > ddl_lastoff) {
         result[(read_offset, read_length)] =
           NO_DEDUP_AVAILABLE;
       }

       if (last_offset > ddl_lastoff) {
         /* we cannot de-dupe the entire range */

         result[(ddl_lastoff + 1, last_offset -
           ddl_lastoff)] = NO_DEDUP_AVAILABLE;
         last_offset = ddl_lastoff;
       }
       if (read_offset < ddl_firstoff) {
         /* we cannot de-dupe the entire range */

         result[(read_offset, ddl_firstoff -
           read_offset)] = NO_DEDUP_AVAILABLE;
         read_offset = ddl_firstoff;
       }

       if (ddl_is_leaf == FALSE) {
         /* indirect layout */

         let trunc_read_off = read_offset truncated
           to next lowest multiple of
           ddli_slab_size;

         let round_last_off = (last_offset rounded
           to next highest multiple of
           ddli_slab_size) - 1;

         first_bit = trunc_read_off /
           ddli_slab_size; last_bit =



Eisler                   Expires April 30, 2009                [Page 13]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


           (round_last_off + 1) / ddli_slab_size;

         for (j = first_bit; j++; j <= last_bit)
         {
           k = j / 32;
           l = j mod 32;
           bit = l << 1;

           if (j == first_bit) {
             read_offset_A = read_offset;
             read_length_A = trunc_read_off +
               ddli_slab_size - read_offset;

           } else {
             read_offset_A = ddl_firstoff + (j *
               ddli_slab_size);
             read_length_A = ddli_slab_size;
           }

           if ((ddli_bitmap[k] & bit) == 1) {
             next_layout_off = j * ddli_slab_size +
               trunc_read_off;

             next_layout_length = ddli_slab_size;
             next_layout_type = ddli_next_level;

             if (client does not have layout for
                 (next_layout_off,
                 next_layout_length, and
                 ddli_next_level) {

                send a LAYOUTGET request;
             }
             let logr_layout_A = logr_layout array
                 of layout for (next_layout_off,
                 next_layout_length,
                 next_layout_type);

             result[(read_offset_A, read_length_A)]
               = dedupe_read(read_offset_A,
               read_length_A, target_fh,
               logr_layout_A);

           } else {
             result[(read_offset_A, read_length_A)]
               = NO_DEDUP_AVAILABLE;

           }



Eisler                   Expires April 30, 2009                [Page 14]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


         }
       } else {
         /* process a leaf layout */

         let trunc_read_off = read_offset truncated
           to next lowest multiple of
           ddll_block_size;

         let round_last_off = (last_offset rounded
           to next highest multiple of
           ddll_block_size) - 1;

         bits_for_blknum = ddll_blockmap_partition
           [DDLL4_BITS_FOR_BLK_NUM_IDX];

         mask_for_blknum = 0;
         for (j = 0; j < bits_for_blknum; j++) {
           mask_for_blknum = (mask_for_blknum
             << 1) | 1;
         }

         bits_for_fh = ddll_blockmap_partition
           [DDLL4_BITS_FOR_FH_IDX];

         mask_for_fh = 0;
         for (j = 0; j < bits_for_fh; j++) {
           mask_for_fh = (mask_for_blknum <<
             1) | 1;
         }

         mask_for_fh = mask_for_fh <<
           bits_for_blknum;

         bits_for_dev = ddll_blockmap_partition
           [DDLL4_BITS_FOR_DEVID_IDX];

         mask_for_dev = 0;
         for (j = 0; j < bits_for_dev; j++) {
           mask_for_dev = (mask_for_dev << 1)
             | 1;
         }
         mask_for_dev = mask_for_dev <<
           (bits_for_blknum + mask_for_fh);

         if ((bits_for_blknum + bits_for_fh +
             bits_for_dev) != 63) {

           result[(read_offset, read_length)] =



Eisler                   Expires April 30, 2009                [Page 15]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


             CORRUPT_LAYOUT;

           return result;
         }

         first_block = trunc_read_off /
           ddll_block_size;
         last_block = (round_last_off + 1) /
           ddll_block_size;
         slopoff = read_offset - trunc_read_off;
         sloplen = round_last_off - last_offset;

         read_offset_A = trunc_read_off;

         for (j = first_block; j++, read_offset_A +=
             ddll_block_size; j <= last_block) {

           if (ddll_blockmap[j] &
               DDLL4_BLKMAP_MASK_ACTIVE) {

             blockmap = ddll_blockmap[j] &
               DDLL4_BLKMAP_MASK_PARTITIONED;

             source_length = ddll_block_size;
             source_change = 0;
             source_dev = 0;

             if (mask_for_blknum == 0) {
               source_offset = ddl_firstoff + j *
                 ddll_block_size;
             } else {
               source_offset = (blockmap &
                 mask_for_blknum) * ddll_block_size;
             }

             if (j == first_block) {
               source_offset += slopoff;
               read_offset_B = read_offset;
             } else {
               read_offset_B = read_offset_A;
             }

             if (j == last_block) {
               source_length -= sloplen;
             }

             if (mask_for_fh == 0) {
               source_fh = target_fh;



Eisler                   Expires April 30, 2009                [Page 16]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


               if (number of elements in
                   ddll_change_attr > 0) {
                 source_change = ddl_change_attr[0];
               }
             } else {
               fhidx = (blockmap & mask_for_fh) >>
                 bits_for_blknum;
               source_fh = ddll_fhlist[fhidx];
               if (number of elements in
                   ddll_change_attr > 0) {
                 source_change =
                   ddl_change_attr[fhidx];
               }
             }
             read_source_fh = source_fh concatenated
               with ddll_fhsuffix;
             source_ltype = 0;
             source_mds = MDS of target_fh;
             if (mask_for_dev != 0) {
               devidx = (blockmap & mask_for_dev) >>
                 bits_for_blknum;
               source_dev = ddll_devlist[devidx];

               if (client does not have device
                   address for source_dev) {
                 send a GETDEVICEINFO
                   (LAYOUT4_DEDUP_TOP, source_dev);
               }

               if (ddla_simple from GETDEVICEINFO is
                   TRUE) {
                 let source_mds be an element of
                   ddla_simple_addr;
               } else {
                 source_ltype = ddldp_ltype;

                 if (client does not have layout for
                     (source_mds, source_fh,
                     source_ltype, source_offset,
                     source_length)) {

                   send a LAYOUTGET request for
                     (read_source_fh, source_ltype,
                     source_dev, source_offset,
                     source_length) to target_fh's
                     MDS;

                   cache LAYOUTGET result;



Eisler                   Expires April 30, 2009                [Page 17]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


                 }

                 if (client still does not have
                     layout for (source_mds, source_fh,
                     source_ltype, source_offset,
                     source_length)) {
                   source_ltype = 0;
                 } else {
                   let source_layout = the layout
                     from cache;
                 }
               }
             }

             if (source_change == 0 || client has
                 delegation on source_fh) {

               if ({source_fh, source_mds,
                   source_offset, source_length} in
                   cache) {

                 result[(read_offset_B,
                   source_length)] =
                   (SATISFY_READ_FROM_CACHE,
                   source_mds, source_fh,
                   source_offset;)

               } else {
                 if (source_ltype == 0) {
                   if (read_source_fh not yet open)
                   {
                     send an OPEN request for
                       read_source_fh;
                   }
                   send a { PUTFH read_source_fh,
                     READ source_offset,
                     source_length } request to
                     source_mds;

                   enter results in cache;

                 } else {
                   read from read_source_fh,
                     source_offset, source_length
                     according to source_layout;

                   enter results in cache;
                 }



Eisler                   Expires April 30, 2009                [Page 18]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


                 result[(read_offset_B,
                   source_length)] =
                   (SATISFY_READ_FROM_CACHE,
                   source_mds, source_fh,
                   source_offset);

               }
             } else {
               if ({source_mds, source_fh,
                   source_offset, source_length} in
                   cache) {

                 send a { PUTFH source_fh, GETATTR
                   change } request to source_mds;

                 if (change attribute ==
                     source_change) {

                   result[(read_offset_B,
                     source_length)] =
                     (SATISFY_READ_FROM_CACHE,
                     source_mds, source_fh,
                     source_offset);

                 } else {
                   result[(read_offset_B,
                     source_length)] =
                     (STALE_DEDUP_LAYOUT,
                     source_mds, source_fh,
                     source_offset);

                 }
               }
             }
           }
         }
       }
       return result;
     }

     /* should never get here */
     result[(read_offset, read_length)] =
       CORRUPT_LAYOUT;

     return result;
   }





Eisler                   Expires April 30, 2009                [Page 19]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


                                 Figure 4

   There is a trade off between resources (space and time) used for
   providing de-duplication layouts (especially leaf layouts) and
   resources for redundant caching of de-duplicated storage.  E.g., if a
   client has to descend through 52 levels of caching to avoid caching a
   single 4096 byte block twice, then it is not cost effective for the
   server to return a layout.  On the other hand, if 99% of a file is
   using de-duplicated storage, then having a complete block map for a
   one gigabyte file, or at least the parts of the file the client wants
   to cache, is more effective than redundantly caching nearly one
   gigabyte of storage.

5.6.  Definition of the lou_body Field of the layoutupdate4 Data Type

   ///  %/*
   ///  % * LAYOUT4_DEDUP_TOP or any of LAYOUT4_DEDUP_LEVEL_<xx>.
   ///  % * Encoded in the lou_body field of type layoutupdate4:
   ///  % *      Nothing. lou_body is a zero length array of octets.
   ///  % */
   ///  %

                                 Figure 5

   The LAYOUT4_DEDUP_TOP and LAYOUT4_DEDUP_LEVEL_<xx> layout types have
   no content for lou_body filed of the layoutupdate4 data type.

5.7.  Storage Access Protocols

   The LAYOUT4_DEDUP_TOP and LAYOUT4_DEDUP_LEVEL_<xx> layout types use
   NFSv4.1 operations (and potentially, operations of higher minor
   versions of NFSv4, subject to the definition of a minor version of
   NFSv4) to access de-duplicated data.  The de-duplication layout types
   do not affect access to storage devices.  Thus a client might be able
   to obtain both a de-duplication layout type and a non-de-duplication
   layout type (e.g., LAYOUT4_NFSV4_1_FILES, LAYOUT4_OSD2_OBJECTS, or
   LAYOUT4_BLOCK_VOLUME) on the same regular file.

5.8.  Revocation of Layouts

   Servers MAY revoke de-duplication layouts.  A client using a de-
   duplication layout SHOULD check if the change attribute of the source
   file has changed.  The use of the ddll_fhsuffix will prevent clients
   using revoked de-duplication layouts from using potentially stale
   information.  Attempts to use filehandles with the value of
   ddll_fhsuffix appended, will result in NFS4ERR_STALE.





Eisler                   Expires April 30, 2009                [Page 20]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


5.9.  Recovery

   [[Comment.2: it is likely this section will follow that of the files
   layout type specified in the NFSv4.1 specification.]]

5.9.1.  Failure and Restart of Client

   TBD

5.9.2.  Failure and Restart of Server

   TBD

5.9.3.  Failure and Restart of Storage Device

   TBD


6.  Negotiation

   A pNFS client sends a GETATTR request for the fs_layout_type
   attribute to see if the LAYOUT4_DEDUP_TOP layout type is supported.


7.  Operational Recommendation for Deployment

   Deploy the de-duplication layouts when it a significant fraction of
   data storage is de-duplicated.


8.  Acknowledgements

   Thanks to Pranoop Erasani, Arthur Lent, and Dave Noveck for
   validating the strategy described in this document.


9.  Security Considerations

   If an ACCESS operation by the principal on the source file would
   fail, then the server has take care when processing requests for de-
   duplication layouts of the target file.  If the server is unable to
   perform access control at the granularity of the a byte-range, then
   the server MUST NOT allow the principal to read the source file.  A
   related concern is that if the server can provide per-byte-range
   access, then the server will need to allow an OPEN operation of the
   source file by the principal.  The server will need to reject READ
   operations for the non-de-duplicated data.  The reader should adjust
   the algorithm in Figure 4 accordingly.



Eisler                   Expires April 30, 2009                [Page 21]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


10.  IANA Considerations

   This specification requires 64 additions to the Layout Types registry
   described in Section 22.4 of [2].  Each added entry has five fields.
   This entry is:

   1.  Name of layout type: LAYOUT4_DEDUP_TOP.

   2.  Value of layout type: TBD1.

   3.  Standards Track RFC that describes this layout: RFCTBD65, which
       is the RFC of this document.

   4.  How the RFC Introduces the specification: L.

   5.  Minor versions of NFSv4 that can use the layout type: 1.

   The second through 64th additions to the Layout Types registry each
   have the following form, where <xx> is a decimal number between 02
   and 64, inclusive:

   1.  Name of layout type: LAYOUT4_DEDUP_LEVEL_<xx>.

   2.  Value of layout type: TBD_<xx>.

   3.  Standards Track RFC that describes this layout: RFCTBD65, which
       is the RFC of this document.

   4.  How the RFC Introduces the specification: L.

   5.  Minor versions of NFSv4 that can use the layout type: 1.


11.  Normative References

   [1]  Bradner, S., "Key words for use in RFCs to Indicate Requirement
        Levels", RFC 2119, March 1997.

   [2]  Shepler, S., Eisler, M., and D. Noveck, "NFS Version 4 Minor
        Version 1", draft-ietf-nfsv4-minorversion1-26 (work in
        progress), Sep 2008.










Eisler                   Expires April 30, 2009                [Page 22]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


Author's Address

   Mike Eisler
   NetApp
   5765 Chase Point Circle
   Colorado Springs, CO  80919
   US

   Phone: +1-719-599-9026
   Email: mike@eisler.com









































Eisler                   Expires April 30, 2009                [Page 23]


Internet-Draft   Storage De-Duplication Awareness in NFS    October 2008


Full Copyright Statement

   Copyright (C) The IETF Trust (2008).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.


Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.











Eisler                   Expires April 30, 2009                [Page 24]


Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/