Patent ID: 12223197

DETAILED DESCRIPTION

Embodiments of the improved technique will now be described. One should appreciate that such embodiments are provided by way of example to illustrate certain features and principles but are not intended to be limiting.

An improved technique for copying data from a source range to a destination range includes identifying a chunk of the source range. The chunk includes multiple logical blocks that map, through a series of source-mapping pages, to a set of virtual pages that point to physical data of the chunk. The technique further includes copying the series of source-mapping pages to form a corresponding series of destination-mapping pages pointed to by the destination range, so that a corresponding chunk of the destination range maps, via the series of destination-mapping pages, to the same set of virtual pages mapped to by the series of source mapping pages.

FIG.1shows an example environment100in which embodiments of the improved technique can be practiced. Here, multiple hosts110are configured to access a data storage system116over a network114. The data storage system116includes one or more nodes120(e.g., node120aand node120b), and storage190, such as magnetic disk drives, electronic flash drives, and/or the like. Nodes120may be provided as circuit board assemblies or blades, which plug into a chassis (not shown) that encloses and cools the nodes. The chassis has a backplane or midplane for interconnecting the nodes120, and additional connections may be made among nodes120using cables. In some examples, the nodes120are part of a storage cluster, such as one which contains any number of storage appliances, where each appliance includes a pair of nodes120connected to shared storage. In some arrangements, a host application runs directly on the nodes120, such that separate host machines110need not be present. No particular hardware configuration is required, however, as any number of nodes120may be provided, including a single node, in any arrangement, and the node or nodes120can be any type or types of computing device capable of running software and processing host I/O's.

The network114may be any type of network or combination of networks, such as a storage area network (SAN), a local area network (LAN), a wide area network (WAN), the Internet, and/or some other type of network or combination of networks, for example. In cases where hosts110are provided, such hosts110may connect to the node120using various technologies, such as Fibre Channel, iSCSI (Internet small computer system interface), NVMeOF (Nonvolatile Memory Express (NVMe) over Fabrics), NFS (network file system), and CIFS (common Internet file system), for example. As is known, Fibre Channel, iSCSI, and NVMeOF are block-based protocols, whereas NFS and CIFS are file-based protocols. The node120is configured to receive I/O requests112according to block-based and/or file-based protocols and to respond to such I/O requests112by reading or writing the storage190.

The depiction of node120ais intended to be representative of all nodes120. As shown, node120aincludes one or more communication interfaces122, a set of processors124, and memory130. The communication interfaces122include, for example, SCSI target adapters and/or network interface adapters for converting electronic and/or optical signals received over the network114to electronic form for use by the node120a. The set of processors124includes one or more processing chips and/or assemblies, such as numerous multi-core CPUs (central processing units). The memory130includes both volatile memory, e.g., RAM (Random Access Memory), and non-volatile memory, such as one or more ROMs (Read-Only Memories), disk drives, solid state drives, and the like. The set of processors124and the memory130together form control circuitry, which is constructed and arranged to carry out various methods and functions as described herein. Also, the memory130includes a variety of software constructs realized in the form of executable instructions. When the executable instructions are run by the set of processors124, the set of processors124is made to carry out the operations of the software constructs. Although certain software constructs are specifically shown and described, it is understood that the memory130typically includes many other software components, which are not shown, such as an operating system, various applications, processes, and daemons.

As further shown inFIG.1, the memory130“includes,” i.e., realizes by execution of software instructions, a metadata-based XCOPY facility (MBXF)132, a metadata transaction log134, a data path140, and any number of data objects180, such as volumes, LUNs (Logical UNits), file systems, virtual machine disks, and the like. The data objects180may be composed of blocks182, where a “block” is a unit of allocatable storage space. Blocks182typically have uniform size, such as 4 kB (kilobytes), 8 kB, or any other suitable size. The data storage system116is configured to access the data objects180by specifying blocks of the data objects to be created, read, updated, or deleted. Although data objects180may be represented by programming objects in memory130, one should appreciate that the data of such data objects180are typically persisted in storage190.

The metadata-based XCOPY facility (MBXF)132is configured to respond to XCOPY requests, which may arrive, for example, from hosts110, from administrators, and/or from other components of the data storage system116. As will be described, the MDXF132is configured to respond to XCOPY requests by performing metadata-only transactions involving the data path140. Such transactions for an XCOPY request have the effect of logically copying data from a specified source range150in the storage system116to a specified destination range160.

The metadata transaction log134is configured to store metadata changes in the form of transactions. In an example, an individual transaction may include multiple metadata operations, such as allocating metadata pages, updating metadata pages, deleting metadata pages, and the like. The metadata transaction log134is managed such that the various metadata operations for any given transaction are performed atomically, meaning that all operations are performed to completion or none of them are performed at all. In an example, the metadata transaction log134maintains transactions in a time-ordered sequence.

The data path140is configured to provide metadata for accessing and organizing data objects180. As described in more detail below, data path140may include various logical blocks, mapping structures, and block virtualization structures.

In example operation, hosts110issue I/O requests112to the data storage system116. Node120areceives the I/O requests112at the communication interfaces122and initiates further processing. Such processing may include reading and/or writing data of one or more of the data objects180.

At some point during operation, a host110, a separate administrator, or some other entity, may issue an XCOPY request118. The XCOPY request118directs the storage system116to copy data from a specified source range (S)150to a specified destination range (D)160. The source range150specifies a location from which data are to be copied, and the destination range160specifies a location to which the data specified by the source range are to be copied. In an example, the XCOPY request118may specify the source range150and the destination range160by logical address ranges, such as by LUN and offset, by file names or directory names, by file handles, or in any other suitable way, which may be specific to the type of data object180involved. Upon receipt of the XCOPY request118by node120a, the MDXF132orchestrates various activities for conducting an XCOPY operation170in response to the request118. Details of the XCOPY operation170will now be described in connection withFIGS.2aand2b.

FIG.2ashows an example of the data path140in which aspects of the XCOPY operation170may be performed. As shown, the data path140includes a namespace210, a mapping structure (“mapper”)220, and a physical block layer230. The namespace210is configured to organize logical data, such as data of volumes, file systems, virtual machine disks, snapshots, clones, and/or the like in a single logical address space, which can be very large (e.g., 8 exabytes). In an example, the namespace210is denominated in logical blocks214having associated logical addresses, which may be identified by LBA (logical block address)212. In an example, the namespace210is configured to map logical addresses specific to particular data objects (e.g., LUN and offset, file name and range, etc.) to corresponding ranges of LBA212, such that all logical data managed by the storage system116can be represented by LBA ranges in the namespace210.

The mapper220is configured to map logical blocks214in the namespace210to corresponding physical blocks232in the physical block layer230. The physical blocks232are normally compressed and may thus have non-uniform size. The mapper220may include multiple levels of mapping structures arranged in a tree. The levels include tops222, mids224, and leaves226, which together are capable of mapping large amounts of data. The mapper220may also include a layer of virtuals228, i.e., block virtualization structures for providing indirection between the leaves226and physical blocks232, thus enabling physical blocks232to be moved without disturbing leaves226.

The tops222, mids224, leaves226, and virtuals228may be arranged in mapping pages, where each mapping page includes a respective array of pointers. For example, a top page222smay include hundreds of pointers (e.g., 512 pointers, 1024 pointers, etc.), for pointing to respective mid pages224. Likewise, a mid page224smay include hundreds of pointers for pointing to respective leaf pages226. Also, a leaf page226smay include hundreds of pointers250for pointing to respective virtuals260. The virtuals260pointed to by the pointers250in the leaf page226smay all reside within a single virtual page228s, or they may reside within multiple virtual pages in the virtual page layer228. Physical blocks232may be arranged in physical large blocks (PLBs). See, for example, PLB230s.

FIG.2afurther shows an example leaf pointer250and an example virtual260in greater detail. An example leaf pointer250is seen to include the following fields:Pointer250ato Virtual. A pointer (e.g., an address) of the virtual260associated with the leaf pointer250. Each leaf pointer250may be associated with a single respective virtual260.P/C Flag250b. A flag or other indicator that specifies whether the leaf pointer250is a parent or a child. Parent/child relationships may be formed, for example, by snapshots, clones, and the like. A leaf pointer for a base object may be considered to be a parent, whereas a leaf pointer in a snapshot may be considered to be a child. This distinction can become relevant when moving or copying pointers, e.g., for avoiding deadlocks.Generation Count250c. A generation number used, for example, for detecting whether a virtual260has been redirected to a new location, e.g., as a result of defragmentation or deduplication.

An example virtual260may include the following fields:Reference Count260a. A number of pointers in the mapper220that point directly to the virtual260, e.g., a number of leaf pointers250that point to the virtual.Pointer260bto Data. A pointer (e.g., an address) of a physical block232that stores data associated with the virtual260.Redirect Pointer260c. A pointer to a new virtual that is intended to replace the virtual260for locating a physical block232. Relevant to defragmentation and certain forms of deduplication.Generation Count260d. A generation number, which is used, for example, for detecting whether the virtual260is being redirected to a new location. For example, when accessing a physical block232from a leaf pointer250, the data path140compares the generation count250cin the leaf pointer with the generation count260din the virtual260. If the two generation counts match, then there is no redirection and the virtual260properly maps to the physical block232. But if the two generation counts do not match, then the virtual260is no longer current and data path140locates the current virtual for the physical block232by following the redirect pointer260c.
One should appreciate that the depicted fields of the leaf pointer250and the virtual260are merely examples, which help to illustrate certain activities that may be relevant to this disclosure. Other embodiments may contain different fields, additional fields, or fewer fields.

In an example, each leaf pointer250corresponds to a respective logical block214in the namespace210. Thus, for example, there may be a one-to-one relationship between logical blocks214and leaf pointers250. Also, consecutive leaf pointers250in a leaf page correspond to consecutive logical blocks214, i.e., logical blocks with consecutive LBAs212. Thus, a leaf page226sthat includes 512 leaf pointers250can map up to 512 consecutive logical blocks214, which equates to 2 MB of logical space (assuming a 4-kB logical block size). The number of logical blocks being mapped increases for higher levels of the mapper220. For example, mid page224scan map up to 512 leaf pages, for a total of 1 GB of logical space. Likewise, top page222scan map up to 512 mid pages, for a total of 512 GB. In an example, the mapper220associates top pages222with respective logical address ranges of the namespace210. Thus, top page222smay be associated with a particular 512-GB range of contiguous logical data in the namespace210. To access a particular physical block232for a particular logical block214, the mapper220identifies the top page222that maps the range of LBAs that include the logical block, locates the pointer in that top page222that maps an associated subrange, locates the associated mid page224and mid pointer, follows that mid pointer to the associated leaf page226, and identifies the associated leaf pointer250. The identified leaf pointer250then points to the physical block232. Here, the pointing from the leaf pointer250to the physical block232is indirect, as the leaf pointer250points first to a virtual260, which points in turn to the physical block232.

As further shown inFIG.2a, the XCOPY operation170is arranged as a logical copy from source range150to destination range160. Both the source range150and the destination range160correspond to respective LBA ranges in the namespace210. In accordance with improvements hereof, the XCOPY operation170identifies one or more chunks152in the source range150. For example, the XCOPY170identifies chunks152aand152b. In an example, each chunk152includes a range of contiguous logical blocks214that map to a single leaf page226. For instance, a chunk152may be aligned to a particular address212athat is known to mark the beginning or middle of a particular leaf page226. To ensure that chunks are mapped by respective leaf pages226, the size of each chunk152ais preferably no larger than the amount of data that can be mapped by a single leaf page226. For a leaf page capable of mapping 2 MB of data, for example, a chunk size of 1 MB may be selected. Other options may include 2 MB, or sizes smaller than 1 MB. Preferably, chunk size is an integer submultiple of leaf page capacity. One should appreciate that selecting a chunk size that enable chunks to be mapped by individual leaf pages222is an optimization rather than a requirement.

In the example shown, the data of chunk152ais mapped entirely by the leaf page226s, which is accessed by a pointer in top page222sand a pointer in mid page224s. Also, a single virtual page228smay contain all virtuals250for mapping all the data of chunk152a. In other examples, virtuals250may be distributed across multiple virtual pages228, however.

As already mentioned, the XCOPY170specifies not only a source range150but also a destination range160. For copying data from source to destination, the XCOPY170proceeds by logically copying chunks152to corresponding chunks162in the destination range (e.g., chunks162aand162b). The chunks162are the same size as the respective chunks152. As with the source chunks152, the destination chunks162are also aligned so that they map to particular leaf pages226. For example, chunk162ais aligned so that all of its data can be mapped to a single leaf page226d, via a top page222dand a mid page224d. At the time of the XCOPY170, the destination mapping pages222d,224d, and226dmay not exist, so that it may be necessary to allocate the pages222d,224d, and226dto complete the XCOPY. Alternatively, some of or all of the pages222d,224d, and226dmay exist already and may be used for mapping existing data, which will be overwritten once the XCOPY operation170is complete. A virtual page228d, or multiple such pages, may be used for mapping any existing data.

One may recognize that the source range150includes not only chunks152but also regions154aand154b, which are not contained within any chunks152. In an example, logical blocks214within regions154aand154bmay be logically copied to corresponding locations in the destination range160by conventional techniques, e.g., by using block-based deduplication.

FIG.2bshows a high-level overview of additional activities that accompany the XCOPY operation170. Here, a series of source-mapping pages270is copied to a corresponding series of destination-mapping pages280. The source-mapping pages270include the above-described pages222s,224s, and226s(top, mid, and leaf), which are used for mapping the data of the chunk152a. The destination-mapping pages280include a top page222d, a mid page224d, and a leaf page226d, which are provided for mapping the data of the destination chunk162a. Pages222d,224d, and226dmay be newly-allocated pages and/or they may be previously-allocated pages that map existing data, i.e., data already found in the chunk162a. In the case where existing data was present, virtual page228dmay point to associated physical blocks (not shown).

To implement the copy of source chunk152ato destination chunk162a, the data path140copies the block pointers in top page222sto top page222d. It also copies the block pointers in mid page224sto mid page224d. It further copies the block pointers in leaf page226sto leaf page226d. Preferably, the copying of pointers of top page222sand mid page224sadjusts for different offsets of destination pages280so that relative pointing between destination pages280is analogous to relative pointing between source pages270. Upon copying the pointers, the leaf pointers250in the destination leaf page226dpoint to the same virtuals260as do the leaf pointers250in the source leaf page226s. Thus, the reference count260aof each virtual260pointed to by leaf page226is incremented by one. For example, each reference count260ais increased from one to two. Also, any reference counts260aof virtuals260previously used at the destination are decremented. For example, a virtual260previously used for data that is now overwritten will be reduced by one.

In the event of any redirects, e.g., where there is a mismatch between the generation count250cof a destination leaf pointer250and the generation count260dof a pointed-to virtual260, the destination leaf pointer250may be adjusted to point to a virtual at the location specified by the redirect pointer260c. In such cases, the reference count260ato be incremented is the reference count of the virtual at the redirected location.

In an example, the processing associated withFIG.2bmay be performed in batches, e.g., by processing all leaf pointers250for chunk162atogether at once, and by processing reference-count updates to all affected virtuals260together at once. In this manner, chunk-based processing may be accomplished with high efficiency.

Once the source-mapping pages270have been copied to the destination-mapping pages280and associated updates and adjustments are made, the XCOPY170is complete with regard to chunk152a. Similar activities may then be conducted for chunk152b, and for any other chunks152. In some examples, multiple chunks152may be processed in parallel. Any data of the source range150not found in a chunk (regions154aand154b) may be logically copied in the conventional way, e.g., by reading the data from the source150and writing it back at the destination, preferably using deduplication.

The depicted XCOPY operation170results in significant performance gains. In preliminary testing, for example, the XCOPY operation170results in greater than a factor of ten improvement in copying speed.

In some cases, complications can arise when logically copying chunks152from a source range to a destination range. For example, deadlocks can occur unless system protocols are carefully followed. One such protocol specifies that, where there is a parent-child relationship between two pages, a child should generally be locked before the parent. This protocol can lead to inefficiencies in the context of XCOPY, as parent-child relationship between mapping pages are generally unknown. For example, a mapping page for an XCOPY destination160might be the parent of a corresponding mapping page for an XCOPY source150, but it might also be a child. In practice this means that it may be necessary to read source-mapping pages270(which involves taking locks), reading destination-mapping pages280(which involves taking additional locks), and checking whether any parent-child relationship exists between the pages. If the locks are taken in the wrong order, the locks may have to be released and new locks may have to be taken in the proper order. All of this locking and unlocking consumes valuable time and can undermine the high efficiency of the XCOPY operation170.

FIG.3shows an example method300of efficiently accessing source-mapping pages270and destination-mapping pages280while avoiding deadlocks. The method300may be performed, for example, by one or more threads running on the node120a.

At310, node120aaccesses the destination-mapping pages under a write-lock. For example, node120amay open a new transaction (Tx) in the metadata transaction log134(FIG.1). The new transaction specifies new destination-mapping pages280to be allocated. Notably, the new destination-mapping pages280are to be allocated regardless of whether destination-mapping pointers already exist for the specified destination range160, i.e., regardless of whether the XCOPY results in an original write or an overwrite. By definition, the newly-allocated destination-mapping pages280cannot be parents of the source-mapping pages270. Rather, they are either new pages or they are copies of existing pages.

At320, the node120aaccesses the source-mapping pages270for reading using a try-lock. A “try-lock” is a special type of lock which is designed to return a failure immediately if the requested lock cannot be taken. The try-lock does not wait for requested pages to become free. For example, taking a try-lock on page226swill immediately return a failure if any other thread is accessing any of the same pages. If the try-lock succeeds, however, the try-lock may immediately return a pass result and may assert the requested lock, which in this case may be done by locking the source-mapping pages270for reading.

At330, node120adetermines whether the try-lock succeeded or failed. If the try-lock failed, then operation proceeds to340, whereupon the node120acommits any pending transactions in the metadata transaction log134. As the try-lock will typically fail if there are uncommitted transactions on any of the source-mapping pages270, committing these transactions completes the specified changes on the source pages and removes any existing locks. At the same time, node120aalso commits the new transaction (from step310) for allocating the new destination-mapping pages280, thereafter releasing the write lock on those pages.

At350, the node120areads the (now free) source-mapping pages270under a read-lock. It also re-reads the (now committed and free) destination mapping pages280under a new write lock.

With locks acquired on both source-mapping pages270and destination-mapping pages280, operation proceeds to step360, whereupon the node120acopies the mapping pointers from the source-mapping pages270to the destination-mapping pages280, e.g., as described in connection withFIG.2babove. Note that step360is also reached directly from step330if the try-lock succeeds. Copying the pointers may itself be performed as part of an additional transaction (not shown), which itself may be committed to complete the update of the destination-mapping pointers280. Any additional processing of the pointers being copied may be done under the same additional transaction. Any further changes, such as reference count updates in virtuals260, may also be done under the same additional transaction, or in some cases under a separate transaction.

One should appreciate that the method300successfully avoids deadlocks that could otherwise result from accessing a parent page before accessing a child page of that parent. In particular, step310ensures that the destination pages cannot be parents of the source pages270by allocating new destination pages280. As new destination pages are allocated for both existent and non-existent destination mapping pages, the method300may consume more metadata than is strictly required. But the consumption of additional metadata is justified by the improvement in performance.

FIG.4shows an example method400that may be carried out in connection with the environment100and provides an overview of some of the features described above. The method400is typically performed, for example, by the software constructs described in connection withFIG.1, which reside in the memory130of the node120aand are run by the set of processors124. The various acts of method400may be ordered in any suitable way. Accordingly, embodiments may be constructed in which acts are performed in orders different from that illustrated, which may include performing some acts simultaneously.

At410, a request118is received to copy a set of data from a source range150to a destination range160. The request118may be provided as an XCOPY command, which directs the data storage system116to perform the requested copy.

At420, a chunk152of the source range150is identified. The chunk152includes multiple logical blocks214which are mapped, through a series of source-mapping pages270, to a set of virtual pages228that point to physical data232of the chunk152.

At430, the series of source-mapping pages270is copied to a corresponding series of destination-mapping pages280pointed to by the destination range160. The corresponding series of destination-mapping pages280maps a corresponding chunk162of the destination range160to the set of virtual pages228. The destination range160thereby points to the physical data232of the chunk152of the source range150and provides a copy thereof.

An improved technique has been described for copying data from a source range150to a destination range160. The technique includes identifying a chunk152of the source range150. The chunk152includes multiple logical blocks214that map, through a series of source-mapping pages270, to a set of virtual pages228that point to physical data232of the chunk152. The technique further includes copying the series of source-mapping pages270to form a corresponding series of destination-mapping pages280pointed to by the destination range160, so that a corresponding chunk162of the destination range160maps, via the series of destination-mapping pages280, to the same set of virtual pages228mapped to by the series of source mapping pages270. The destination range160thereby points to the same data as the source range150and provides a copy thereof.

Having described certain embodiments, numerous alternative embodiments or variations can be made. For example, although embodiments have been described in connection with a particular mapping arrangement that involves tops, mids, leaves, and virtuals, this is merely an example. Alternatively, embodiments may be constructed that include different numbers and/or types of mapping pages from those shown.

Also, although embodiments have been described in connection with a single logical address space (namespace210), this is also merely an example. Alternatively, embodiments may be constructed that arrange logical data differently from the manner shown, including providing different logical address spaces for different data objects.

Also, although embodiments have been described that involve one or more data storage systems, other embodiments may involve computers, including those not normally regarded as data storage systems. Such computers may include servers, such as those used in data centers and enterprises, as well as general purpose computers, personal computers, and numerous devices, such as smart phones, tablet computers, personal data assistants, and the like.

Further, although features have been shown and described with reference to particular embodiments hereof, such features may be included and hereby are included in any of the disclosed embodiments and their variants. Thus, it is understood that features disclosed in connection with any embodiment are included in any other embodiment.

Further still, the improvement or portions thereof may be embodied as a computer program product including one or more non-transient, computer-readable storage media, such as a magnetic disk, magnetic tape, compact disk, DVD, optical disk, flash drive, solid state drive, SD (Secure Digital) chip or device, Application Specific Integrated Circuit (ASIC), Field Programmable Gate Array (FPGA), and/or the like (shown by way of example as medium450inFIG.4). Any number of computer-readable media may be used. The media may be encoded with instructions which, when executed on one or more computers or other processors, perform the process or processes described herein. Such media may be considered articles of manufacture or machines, and may be transportable from one machine to another.

As used throughout this document, the words “comprising,” “including,” “containing,” and “having” are intended to set forth certain items, steps, elements, or aspects of something in an open-ended fashion. Also, as used herein and unless a specific statement is made to the contrary, the word “set” means one or more of something. This is the case regardless of whether the phrase “set of” is followed by a singular or plural object and regardless of whether it is conjugated with a singular or plural verb. Also, a “set of” elements can describe fewer than all elements present. Thus, there may be additional elements of the same kind that are not part of the set. Further, ordinal expressions, such as “first,” “second,” “third,” and so on, may be used as adjectives herein for identification purposes. Unless specifically indicated, these ordinal expressions are not intended to imply any ordering or sequence. Thus, for example, a “second” event may take place before or after a “first event,” or even if no first event ever occurs. In addition, an identification herein of a particular element, feature, or act as being a “first” such element, feature, or act should not be construed as requiring that there must also be a “second” or other such element, feature or act. Rather, the “first” item may be the only one. Also, and unless specifically stated to the contrary, “based on” is intended to be nonexclusive. Thus, “based on” should be interpreted as meaning “based at least in part on” unless specifically indicated otherwise. Although certain embodiments are disclosed herein, it is understood that these are provided by way of example only and should not be construed as limiting.

Those skilled in the art will therefore understand that various changes in form and detail may be made to the embodiments disclosed herein without departing from the scope of the following claims.