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_, where is a two digit decimal number that ranges between 02 and 64. The server MUST NOT return LAYOUT4_DEDUP_LEVEL_ 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_ 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_. 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_. 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_. /// % * 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_ 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_ 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 is a decimal number between 02 and 64, inclusive: 1. Name of layout type: LAYOUT4_DEDUP_LEVEL_. 2. Value of layout type: TBD_. 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]