Fast algorithm to find file system difference for deduplication

The disclosure provides techniques for deduplicating files. The techniques include, upon creating or modifying a file, placing a logical timestamp of the current logical time, within a queue associated with the directory of the file. The techniques further include placing the logical timestamp within a queue of each parent directory of the directory of the file. To determine a set of files for deduplication, the techniques disclosed herein identify files that have been modified within a logical time range. The set of files modified within a logical time is identified by traversing directories of a storage system, the directories being organized within a tree structure. If a directory's queue does not contain a timestamp that is within the logical time range, then all child directories can be skipped over for further processing, such that no files within the child directories end up being within the set of files for deduplication.

RELATED APPLICATIONS

This application is related to U.S. application Ser. No. 16/552,880, titled “SCALE OUT CHUNK STORE TO MULTIPLE NODES TO ALLOW CONCURRENT DEDUPLICATION,” U.S. application Ser. No. 16/552,908, titled “A PROBABILISTIC ALGORITHM TO CHECK WHETHER A FILE IS UNIQUE FOR DEDUPLICATION,” U.S. application Ser. No. 16/552,954, titled “EFFICIENT GARBAGE COLLECTION OF VARIABLE SIZE CHUNKING DEDUPLICATION,” U.S. application Ser. No. 16/552,998, titled “ORGANIZE CHUNK STORE TO PRESERVE LOCALITY OF HASH VALUES AND REFERENCE COUNTS FOR DEDUPLICATION,” and U.S. application Ser. No. 16/552,976, titled “SMALL IN-MEMORY CACHE TO SPEED UP CHUNK STORE OPERATION FOR DEDUPLICATION.” Each of these applications is filed on the same day as the present application. The entire contents of each of these applications are hereby incorporated by reference herein.

BACKGROUND

The amount of data worldwide grows each year at a rate that is faster than the price drop of storage devices. Thus, the total cost of storing data continues to increase. As a result, it is increasingly important to develop and improve data efficiency techniques, such as deduplication and compression for file and storage systems. Data deduplication works by calculating a hash value for each data unit and then storing units with the same hash only once. One issue that arises in data deduplication systems is efficiently identifying files that need to be deduplicated at a given point in time. Scanning all files in the system may be cost and time prohibitive.

DETAILED DESCRIPTION

The present disclosure provides techniques for identifying files for deduplication. The techniques include marking directories of files with logical timestamps so as to skip entire subtrees of the directory structure while searching for files to deduplicate. Skipping searching of subtrees of a directory structure allows identification of files for deduplication to be faster than if every directory is searched. Skipping also uses less of other computing resources, such as processing and memory. This improves the functioning of the computer itself, and also improves the functioning of a computer's storage system. The techniques herein are directed to a specific implementation of a solution to a problem in the software arts.

More specifically, techniques include, upon creating or modifying a file, placing a logical timestamp of a current logical time, within a queue associated with the directory of the file. The techniques further include placing the logical timestamp within a queue of each parent directory of the directory of the file. To determine a set of files for deduplication, the techniques disclosed herein identify files that have been modified within a logical time range. The set of files modified within a logical time range is identified by traversing directories of a storage system, the directories being organized within a tree structure. If a directory's queue does not contain a timestamp that is within the logical time range, then all child directories can be skipped over for further processing, such that no files within the child directories end up being within the set of files for deduplication.

The present disclosure also provides techniques for deduplicating files. The techniques include creating a data structure that organizes metadata about chunks of files, the organization of the metadata preserving order and locality of the chunks within files. A chunk of a file is a portion of a file, as described further below. Order and locality are further described below with reference toFIG.1CandFIG.2. The organization of the metadata within storage blocks of storage devices matches the order of chunks within files. Upon a read or write operation to a metadata, the preservation of locality of metadata results in the likely pre-fetching, from storage into a memory cache, metadata of subsequent and contiguous chunks. The preserved locality results in faster subsequent read and write operations of metadata, because the read and write operations are executed from memory rather than from storage.

The faster read and write operations result in an improvement in the functioning of the computer itself. The computer is able to execute basic read and write operations faster than otherwise. Additionally, an improvement in a deduplication process results in an improvement in the functioning of the computer itself. An improvement in deduplication improves the way a computer stores and retrieves data in memory and in storage. The deduplication techniques herein are directed to a specific implementation of a solution to a problem in the software arts.

FIG.1Adepicts a block diagram of a computer system100in which one or more embodiments of the present disclosure may be utilized. Computer system100includes a data center102connected to a network146. Network146may be, for example, a direct link, a local area network (LAN), a wide area network (WAN) such as the Internet, another type of network, or a combination of these.

Data center102includes host(s)105, a virtualization manager130, a gateway124, a management network126, a data network122, and a chunk store134. Networks122,126, in one embodiment, each provide Layer 2 or Layer 3 connectivity in accordance with the Open Systems Interconnection (OSI) model, with internal physical or software defined switches and routers not being shown. Although the management and data network are shown as separate physical networks, it is also possible in some implementations to logically isolate the management network from the data network, e.g., by using different VLAN identifiers.

Each of hosts105may be constructed on a server grade hardware platform106, such as an x86 architecture platform. For example, hosts105may be geographically co-located servers on the same rack.

Hardware platform106of each host105may include components of a computing device such as one or more central processing units (CPUs)108, system memory110, a network interface112, storage system114, a host bus adapter (HBA)115, and other I/O devices such as, for example, USB interfaces (not shown). Network interface112enables host105to communicate with other devices via a communication medium, such as data network122or management network126. Network interface112may include one or more network adapters, also referred to as Network Interface Cards (NICs). In certain embodiments, data network122and management network126may be different physical networks as shown, and the hosts105may be connected to each of the data network122and management network126via separate NICs or separate ports on the same NIC. In certain embodiments, data network122and management network126may correspond to the same physical or software defined network, but different network segments, such as different VLAN segments.

Storage system114represents persistent storage devices (e.g., one or more hard disks, flash memory modules, solid state disks, non-volatile memory express (NVMe) drive, and/or optical disks). Storage114may be internal to host105, or may be external to host105and shared by a plurality of hosts105, coupled via HBA115or NIC112, such as over a network. Storage114may be a storage area network (SAN) connected to host105by way of a distinct storage network (not shown) or via data network122, e.g., when using iSCSI or FCoE storage protocols. Storage114may also be a network-attached storage (NAS) or another network data storage system, which may be accessible via NIC112.

System memory110is hardware allowing information, such as executable instructions, configurations, and other data, to be stored and retrieved. Memory110is where programs and data are kept when CPU108is actively using them. Memory110may be volatile memory or non-volatile memory. Memory110also includes a cache132(seeFIG.1B). Although cache132is shown as located within memory110, cache132may be implemented in other components of computer system100, such as in an external storage or memory device, shared by a plurality of hosts105, and coupled to host105via HBA115or NIC112. Cache132comprises cached copies of storage blocks of storage(s)114. The cached storage blocks in cache132are fetched into memory110during deduplication method300discussed below with reference toFIG.3.

Host105is configured to provide a virtualization layer, also referred to as a hypervisor116, that abstracts processor, memory, storage, and networking resources of hardware platform106into multiple virtual machines1201to120N(collectively referred to as VMs120and individually referred to as VM120) that run concurrently on the same host. Hypervisor116may run on top of the operating system in host105. In some embodiments, hypervisor116can be installed as system level software directly on hardware platform106of host105(often referred to as “bare metal” installation) and be conceptually interposed between the physical hardware and the guest operating systems executing in the virtual machines. In some implementations, the hypervisor may comprise system level software as well as a “Domain 0” or “Root Partition” virtual machine (not shown) which is a privileged virtual machine that has access to the physical hardware resources of the host and interfaces directly with physical I/O devices using device drivers that reside in the privileged virtual machine. Although the disclosure is described with reference to VMs, the teachings herein also apply to other types of virtual computing instances (VCIs), such as containers, Docker containers, data compute nodes, isolated user space instances, namespace containers, and the like. In certain embodiments, instead of VMs120, the techniques may be performed using containers that run on host105without the use of a hypervisor and without the use of a separate guest operating system running on each container.

Virtualization manager130communicates with hosts105via a network, shown as a management network126, and carries out administrative tasks for data center102such as managing hosts105, managing VMs120running within each host105, provisioning VMs, migrating VMs from one host to another host, and load balancing between hosts105. Virtualization manager130may be a computer program that resides and executes in a central server in data center102or, alternatively, virtualization manager130may run as a virtual computing instance (e.g., a VM) in one of hosts105. Although shown as a single unit, virtualization manager130may be implemented as a distributed or clustered system. That is, virtualization manager130may include multiple servers or virtual computing instances that implement management plane functions.

Although hosts105are shown as comprising a hypervisor116and virtual machines120, in an embodiment, hosts105may comprise a standard operating system instead of a hypervisor116, and hosts105may not comprise VMs120. In this embodiment, data center102may not comprise virtualization manager130.

Gateway124provides hosts105, VMs120and other components in data center102with connectivity to one or more networks used to communicate with one or more remote data centers. Gateway124may manage external public Internet Protocol (IP) addresses for VMs120and route traffic incoming to and outgoing from data center102and provide networking services, such as firewalls, network address translation (NAT), dynamic host configuration protocol (DHCP), and load balancing. Gateway124may use data network122to transmit data network packets to hosts105. Gateway124may be a virtual appliance, a physical device, or a software module running within host105.

Chunk store134comprises storages114, tables140,142,172, deduplication module144, and a global logical clock (GLC)174. Chunk store134is a storage system that stores data of files200(seeFIG.2). The data of files200within chunk store134is deduplicated by deduplication module144.

GLC174is a counter that is incremented at specific time points, at specific points in processes described herein, or at a specific time intervals, as appropriate for system100. Each historical value of GLC174represents a temporal checkpoint. The checkpoints are used to identify files200(seeFIG.2) for deduplication, as further described below with reference toFIGS.5,6,7, and8. The logical time of GLC174may be a monotonic value that increases when it changes.

Deduplication module144may be a background process working asynchronously relative to input/output (I/O) operations directed to chunk store134, such as asynchronously relative to I/O operations by hosts105or VMs120. Deduplication module144may be software running within hypervisor116, memory110, VM120, storage114, or within another component of system100. Deduplication module144may be a separate physical device connected to chunk store134. Host105or system100may comprise one or more deduplication modules144. Deduplication module144may be associated with a virtual node running on host105, as described in U.S. application Ser. No. 16/552,880, incorporated by reference above.

One method of deduplication that may be used by deduplication module144is described in U.S. application Ser. No. 12/356,921, titled “Computer Storage Deduplication,” filed on Jan. 21, 2009, the entire content of which is hereby incorporated by reference herein. The method of deduplication that may be used by deduplication module144may be that described in application Ser. No. 12/356,921, as modified by techniques disclosed herein.

Chunk store134comprises one or more storage devices114. Although the storage devices of chunk store134are shown as storage devices114of host105, storage devices of chunk store134may be any storage devices such as other storages that may be connected to host105through HBA115. In an embodiment, chunk store134may be a distributed storage system implemented as an aggregation of storage devices114accessible by a plurality of hosts105. In such a distributed storage system, chunk store134may be a virtual storage area network (vSAN), and hypervisor116may comprise a vSAN module (not shown), as described in U.S. application Ser. No. 14/010,247, titled “Distributed Policy-Based Provisioning and Enforcement for Quality of Service,” filed on Aug. 26, 2013, now U.S. Pat. No. 9,887,924, the entire content of which is hereby incorporated by reference herein.

FIG.2depicts a block diagram of two exemplary files200, according to an embodiment. Storage devices114of chunk store134store files200. Each file200may be associated with a “modification time,” which may be the real-world time at which the file was last modified. If the file was last modified when it was created, then a file's modification time may be the same as the file's creation time. The modification time of a file200may be stored as metadata or as part of the data or content of file200, within one or more chunks202of file200.

Each file200is divided into portions or chunks202. In an embodiment, deduplication performed herein is byte-level deduplication. With byte-level deduplication, file200may be divided into chunks202by the following exemplary process. Deduplication module144chooses a small window size and computes a hash for a byte window starting at every byte offset of file200. This can be done efficiently using Rabin fingerprints. If the hash matches a fixed value (e.g., zero), deduplication module144considers that file offset to be a boundary. Such a boundary is called a content-based boundary. A chunk202may be defined to be the file data between two boundaries. A boundary may also be the start and end of file200.

Deduplication module144then computes a second hash for each chunk202, and this is the hash that is checked against and inserted into chunk store data structures140and142, as further described below. The second hash may be computed by, for example, a hash algorithm such as secure hash algorithm (SHA)-256 or SHA-512. In an embodiment, the computed hash may be truncated, and the truncated hash is the second hash that is associated with a chunk202, as further described with reference toFIG.3, below.

A benefit of such a method of dividing a file200into chunks202is that, if data in file200shifted (e.g., a new line is inserted at the beginning of file200), most chunks202in file200are not affected. Such boundary setting may result in the detection of more duplicated content and may achieve increased storage space saving via deduplication. The average size of chunk202may be, for example, approximately 80 KB. Chunks202may be of different sizes.

Returning toFIG.1A, chunk store134also comprises three data structures: time table172, chunk hash table140, and chunk ID table142. Although tables140,142, and172are described as “tables,” these data structures may be any data structure that can perform the functions of chunk hash table140, chunk ID table142, and/or time table172. Tables140,142, and172may not be the same data structure, or may be the same data structure. For example, the data structures may be an log structured merge (LSM) tree, a Bεtree, or a B+ tree. Chunk hash table140may be implemented as a file directory with each entry in chunk hash table being a file, as further described in U.S. application Ser. No. 16/552,880, incorporated by reference above.

Time table172is a key-value data structure that, when given a key, returns a value that is mapped to that key. The key-value mappings are mappings from the key to the value. Each key-value mapping is between (a) the key, which is a GLC logical time, and (b) the value, which is a real-world time. A logical time may be for example, a numerical number such as “1,” “2,” “3,” etc. A real-world time may be a time that indicates the current time in the world, such as for example “Oct. 12, 2018, 1:42:59 PM Pacific Time Zone.”

Chunk hash table140is shown in detail inFIG.1C. Chunk hash table140is a key-value data structure that, when given a key, returns a value that is mapped to that key. The key-value mappings are mappings from the key to the value. Chunk hash table140includes key-value mappings, each mapping being between (a) the key, which is the hash of the contents of chunk202(i.e., chunk hash150), and (b) the value, which is a chunk identifier (ID)152. Chunk ID152is an arbitrarily assigned alphanumeric identifier that preserves locality and sequential order of chunks202of file200. For example, chunk202Aof file2001may be assigned the arbitrary chunk ID of “650.” Chunk202Bmay then be assigned the next sequential, contiguous chunk ID, such as “651.” Chunk202cmay be assigned a chunk ID of “652,” etc. It should be noted that “contiguous” may be defined in arbitrary increments within system100. For example, contiguity may be defined in increments of 0.5 or 10. If contiguity is defined in increments of 0.5, then after chunk ID “650,” the next contiguous chunk ID is “650.5.” If contiguity is defined in increments of 10, then after chunk ID “650,” the next contiguous chunk ID is “660.” Chunk IDs152may be sourced from a reserved batch of contiguous chunk IDs152, as discussed in U.S. application Ser. No. 16/552,880, incorporated by reference above.

Chunk ID table142is shown in detail inFIG.1C. Chunk ID table142is a key-value data structure that, when given a key, returns a value that is mapped to that key. The key-value mappings are mappings from the key to the value. Chunk ID table142includes key-value mappings, each mapping being between (a) the key, which is chunk ID152(e.g., obtained from chunk hash table140), and (b) the value, which is a set of information158about chunk202corresponding to that chunk ID152. Set of information158may be considered “metadata” about chunk202corresponding to chunk ID152mapped to the set of information158. Set of information158may include: chunk hash150, a pointer154to the contents of chunk202within chunk store134, and a reference count156of chunk202. Pointer154to the contents of chunk202may include an address, such as a logical or physical address. Pointer154may be a plurality of pointers154pointing to locations of file200within storage(s)114. Pointer154may be a plurality of pointers if, for example, file200is a fragmented file, stored in more than one location within storage(s)114. In an embodiment, pointer154is a logical pointer154. Reference count156of chunk202may be the number of pointers (e.g., pointers154and pointers of files200) that point to the contents of chunk202. In an embodiment, reference counts156may be stored in a separate data structure and created, modified, and generally managed as described in U.S. application Ser. No. 16/552,954, incorporated by reference above. Tables140and142may be regarded as containing “metadata” of the content or data of chunks202.

FIG.3depicts a flow diagram of a method300of deduplicating a file200, according to an embodiment. Method300may be performed by deduplication module144. Method300may be performed in the background, asynchronously relative to I/O operations directed to chunk store134. The file200deduplicated by method300may be obtained from a list of files200identified for deduplication, and the list of files200may be identified by method800ofFIG.8, described below.

At step305, deduplication module144creates boundaries within file200so as to divide file200into chunks202. Step305may be performed by a process that includes Rabin fingerprinting, as described above with reference toFIG.2.

At step310, deduplication module144chooses a first or next chunk202for processing in subsequent steps of method300. If step310is reached from step305, then method300has just began its first iteration, and so deduplication module144chooses the first chunk202of file200. If step310is reached from step355, then method300is restarting a new iteration, and so deduplication module144chooses the next chunk202of file200.

As part of step310, deduplication module144computes a hash of the data of chosen chunk202. The hash may be computed by, for example, SHA-256 or SHA-512. In an embodiment, the computed hash may be truncated (e.g., a SHA-512 hash may be truncated to 256 bits), and the truncated hash is the hash that is “computed at step310” for subsequent steps of method300.

At step315, deduplication module144determines whether the hash of chunk202, computed at step310, is in chunk hash table140. If so, then the identical contents of chunk202have been previously processed by deduplication module144, such as for example as part of a previous execution of method300. Also if so, then a chunk identical to chunk202is already present within chunk store134. If identical contents of chunk202have been previously processed, then an entry for hash150and chunk ID152for contents of chunk202already exist within chunk hash table140, the entry having been added by a previous execution of method300. If the hash of chunk202is in chunk hash table140, then method300continues to step330. Optionally, if the hash of chunk202is in chunk hash table140, then as part of step315, deduplication module144extracts chunk ID152from chunk hash table140.

If the hash of chunk202is not in chunk hash table140, then the contents of chunk202have not been previously deduplicated through the processing of method300, and method300proceeds to step320.

At step320, deduplication module144adds an entry for chunk202to chunk hash table140. As discussed above, an entry in chunk hash table140includes a key-value mapping between (a) the key, which is the hash of the contents of chunk202(i.e., chunk hash150), and (b) the value, which is a chunk ID152. Chunk hash150was computed at step310. Chunk ID152is assigned to chunk202as described above with reference toFIG.2. If chunk202chosen at step310is the first chunk202of a file (e.g., chunk202Aof file2001), then chunk ID152may be assigned arbitrarily. If chunk202chosen at step310is a second or subsequent chunk202(e.g., chunk202Bof file2001), then chunk ID may be the next sequential identifier after chunk ID152assigned to the previous chunk202. Previous chunk202may be, for example, chunk202Aof file2001.

At step325, deduplication module144adds an entry for chunk202to chunk ID table142. As described above, an entry in chunk ID table142includes a key-value mapping between (a) the key, which is the chunk ID152assigned at step320, and (b) the value, which is a set of information158about chunk202corresponding to that chunk ID152. As part of step325, reference count156is modified to indicate that a reference to chunk202exists in chunk ID table142and in file200being deduped. In an embodiment, the reference count is set to or incremented by one. As part of step325, the storage block to which an entry for chunk202is added is copied or fetched from one of storages114into cache132. This copying of the storage block into memory110may be an automatic part of caching and swapping operations performed by hypervisor116, an operating system of host105, and/or a guest operating system of VM120. After step325, method300continues to step355.

At step330, deduplication module144uses chunk ID152extracted from chunk hash table140at step315to send a request to obtain set of information158about chunk202. The set of information158is requested from chunk ID table142. Deduplication module144uses chunk ID152as a key into chunk ID table142. The value returned (at step330or a subsequent step) is the set of information158about chunk202. Deduplication module144first checks whether the set of information158is in cache132before checking storage114of chunk store134.

At step340, the storage block on which the set of information158is stored is copied or fetched from one of storages114into cache132. As part of step340, deduplication module144obtains from block cache132the set of information158associated with chunk202. This copying of the storage block into memory110may be an automatic part of caching and swapping operations performed by hypervisor116, an operating system of host105, and/or a guest operating system of VM120.

In an embodiment, when the storage block containing the set of information corresponding to a given chunk ID is copied from storage114to cache132, the contents of the chunks202(that correspond to chunk IDs152in the storage block) are not copied into cache132.

It should be noted that the entries in chunk ID table142are arranged or organized by sequential and contiguous chunk IDs152. The entries of chunk ID table142may be stored sequentially and contiguously in storage114. This means that a storage block containing the set of information158corresponding to a given chunk ID152is likely to also store the sets of information158corresponding to a plurality of chunk IDs152that are before and/or after the given chunk ID152. The sets of information158within the storage block may be arranged contiguously with one another (in an embodiment, unseparated by other data), in an order that matches the order of associated chunk IDs152. For example, if a storage block stores the set of information corresponding to chunk ID152of chunk202Bof file2001, then that same storage block is likely to also store the set of information corresponding to the chunk IDs152of chunks202A,202C, and202D.

The advantage of preserving locality by organizing sets of information158, within chunk ID table142, by sequential and contiguous chunk IDs152, is illustrated with respect to the following example. Assume file2001has already been deduped and file2002is in the process of being deduped by method300. As used herein, the terms “deduped” and “deduplicated” are synonymous, and mean “having gone through a process of deduplication.” Assume that at step315, the hash of chunk202Eof file2002is determined to already be within chunk hash table140, meaning that a chunk identical to202Eis already in chunk store134. Assume that this previously deduped and identical chunk202is chunk202Aof file2001. It is likely that after chunk202A, the subsequent several chunks202B,202C,202D, etc. of file2001are the same as the several chunks following chunk202Eof file2002. The sets of information158corresponding to chunks202B,202C, and202Dare likely within the same storage block as the set of information158of chunk202A. When the storage block containing set of information158of chunk202Ais copied into cache132of memory110, the sets of information158corresponding to chunks202B,202C, and202Dare also likely copied into cache132. When, for example,202Fof file2002is processed by method300, the hash of the contents of chunk202Fis likely to be the same as the hash of chunk202B. The hash of chunk202Bis already in chunk hash table140and chunk ID table142as chunk hash150.

When the hash of chunk202Fis calculated, set of information158corresponding to that hash is likely to already be in cache132, precluding a need to copy a new storage block into cache132as part of an I/O operation, as illustrated by the skipping of step340if a cache hit occurs in step335of method300. This speeds up processing and deduplication of files200. Organizing the sets of information, within chunk ID table142, by sequential and contiguous chunk IDs152, preserves locality of deduped files200. The preserved locality results in faster read operations of sets of information158, because the read operations are executed from memory110rather than from storage114.

At step345, deduplication module144checks that the hash calculated at step310is the same as chunk hash150within the obtained set of information158. If not, then method300may abort and an administrator may be notified. If the hashes match, then deduplication module144performs a write to the storage block copied into cache at step340. The write increases reference count156, within the set of information158, by one. The increase by one indicates that the portion of file200corresponding to chunk202chosen at step310is now pointing to the chunk202that had already been in chunk store134(and whose set of information158was obtained at previous steps).

At step350, a deduplication module144or a garbage collection module (not shown) unreserves storage space within storage114. The unreserved storage space corresponds to the space where chunk202chosen at step310is stored. The freeing or unreserving of storage blocks may be performed as described by U.S. application Ser. No. 16/552,954, incorporated by reference above. As part of step350, the portion of file200that previously pointed to chunk202chosen at step310is remapped to point at shared chunk202that had already been in chunk store134, and whose set of information158was retrieved at steps330-340. As used herein, a “shared chunk”202is a chunk that is referenced by more than one file200.

As part of step350, memory pages corresponding to shared chunk202, whose set of information158was retrieved at steps330-340, are marked as copy-on-write (COW). Marking pages as COW may be performed by hypervisor116or an operating system of host105or VM120. Step350may be performed before, concurrently, or after step345.

FIG.4depicts a flow diagram of a method400of updating a file200that has been previously deduped, according to an embodiment. Method400may be performed by deduplication module144, hypervisor116, an operating system of host105or VM120, or a combination of these components. The file200that has been previously deduped may have been deduped by method300.

At step402, deduplication module144(or hypervisor116or an operating system of host105or VM120) marks memory pages of a shared chunk202as COW. Step402may be performed as part of method300, such as part of step350of method300.

At step404, chunk store134or hypervisor116receives an operation to update a file200that references the shared chunk202, and the update operation is directed at contents of shared chunk202.

At step406, chunk store134or hypervisor116creates a copy of shared chunk202, the copy being a new chunk202with updated data, as per the update operation of step404.

At step408, an entry for new chunk202is added to chunk hash table140, similarly to the process of step320of method300. Also as part of step408, an entry for new chunk202is added to chunk ID table142, similarly to the process of step325of method300.

At step410, the portion of updated file200that previously pointed to shared chunk202is remapped to point to new chunk202. Because file200is remapped to a new chunk, shared chunk200may no longer be a “shared chunk” at step410. As part of step410or as part of another step of method400, the memory pages of previously shared chunk202may be unmarked COW.

At step412, deduplication module144decreases the reference count of the shared chunk or previously shared chunk202by one. After step412, method400ends.

FIG.5depicts a block diagram of an exemplary file system tree500, according to an embodiment. Tree500represents organization or hierarchy of files200within chunk store134and/or storage(s)114A. Directory502may be, for example, an electronic folder as commonly known in the art. Each directory502may have any number of child files200or child directories502. A “child” file200or directory502may be regarded as contained within its parent directory502. A child file200or child directory502may be a direct or indirect child.

As used herein, a “direct child” of a parent directory502is a file200or directory502located directly underneath the parent directory502in the tree500. InFIG.5, a direct child is connected to a parent without an intermediary directory502between the child and the parent. For example, file2001is a direct child of directory502B, and directory502Bis a direct parent of file2001. For another example, directory502Fis a direct child of directory502E, and directory502Eis a direct parent of directory502F.

An “indirect child” is a file200or directory502located indirectly underneath an indirect parent directory502. InFIG.5, an indirect child is connected to an indirect parent with an intermediary directory502being present between the child and parent. An indirect parent may be referred to as an “ancestor,” and an indirect child may be referred to as a “descendant.” For example, directory502Eis an ancestor of directory502Dand directory502F. Directory502Eis a “common” ancestor of directory502Dand directory502F, because directory502Eis an ancestor of both directory502Dand directory502F.

Each directory502is associated with or comprises a timestamp queue (TQ)504. In an embodiment, TQ504is stored as a property or an attribute of its associated directory502. TQ504may be, for example, an array data structure. TQ504may be limited in the number of entries that it may contain, such as for example, five entries, ten entries, or a hundred entries. Each entry within TQ504is a logical timestamp. The logical timestamp is the GLC logical time of GLC174at the time that the timestamp is added to TQ504. Adding a timestamp to TQ504of directory502may be referred to as “marking” that directory502with the timestamp. If TQ504of directory502contains a timestamp, then that directory502may be regarded as “marked” by that timestamp. Adding timestamps to TQ504is further described below with reference toFIG.6.

FIG.6depicts a flow diagram of a method600of updating a TQ504of a directory502when a file200is created or modified, according to an embodiment. Method600may be performed by the file system of chunk store134and/or storage(s)114.

The following is a summary of method600. When a file200is updated or newly created, method600checks whether the directory502in which the file200is located has been labeled with a timestamp of current logical time of GLC174. If not, then that directory is labeled with the current logical time. The same determination and timestamping is performed for each parent and ancestor directory502of the file200, up tree500, until either (a) a directory502is reached that has been labeled with the current logical time (e.g., such as from a previous execution of method600for a different file200), or (b), the root directory502is reached and there are no more parent or ancestor directories502to evaluate.

Although it might appear expensive in terms of time and computing resources to perform method600upon each modification or creation of a file200, the stopping of method600when a parent or ancestor directory502with an updated timestamp is reached causes method600to have a reduced number of steps before method600ends.

At step604, the modification time of the file200of step602is updated. The modification time of file200may be the real-world time at the time of modifying or creating the file200.

At step606, the component of system100performing method600(e.g., file system of chunk store134and/or storage(s)114) chooses the next parent directory502up tree500for evaluation of and modification of timestamps.

If step606is reached from step604, then the component performing method600chooses directory502of the updated or modified file200for further analysis by method600. Directory502of file200may be the directory502containing file200, or directory502that is the direct parent of file200. Continuing the above example, directory502Dmay be chosen, because directory502Dis the parent directory of file2002.

If step606is reached from step612, then the direct parent directory502of the current chosen directory502is chosen.

At step608, TQ504of the chosen directory502is accessed to determine TQ504contains a timestamp that is equal to the current logical time of GLC174. If TQ504contains a timestamp equal to the current logical time of GLC174, then the current directory502and all parent and ancestor directories502have already had their associated TQs504updated to include the current logical time of GLC174, and so method600ends. If TQ504does not contain a timestamp equal to the current logical time of GLC174, then method600continues to step610.

At step610, the current logical time of GLC174is obtained from GLC174and then added to or inserted into TQ504of directory502chosen at step606. If TQ504is full at the start of step610, then the earliest (i.e., oldest) or smallest timestamp within TQ504may be evicted from TQ504.

At step612, the component performing method600determines whether the current directory502has a parent directory502, or whether the current directory502is the root directory502. InFIG.5, the root directory502is directory502A. The current directory502is the directory chosen at step606. If no parent directory502exists, then all parent and ancestor directories of the modified file200have had their associated TQs504updated to include the current logical time of GLC174, and so method600ends. If a parent directory502exists, then method600returns to step606, at which the next up parent directory502is chosen for timestamp evaluation. Following the above example, the current directory502is directory502, and method600returns to step606at which step directory502Cis chosen for timestamp evaluation.

It should be noted that in many cycles through iterations of steps606through612may be required if many directories502exist between the directory502where the file200being modified is located. This could create a deadlock of one or more processors108. The deadlock problem may be solved using the following embodiment of method600.

Tree500is traversed from (a) child directory502that contains modified/created file200to (b) parent directory502using back-link pointers from the child directory502to its parent directory502. To avoid deadlock, try-lock/release-all is used to obtain the lock of the inode (not shown) of the parent directory502. Once the last directory502that needs to be updated is reached, then the component performing method600moves down tree500toward the child directory502that contains modified/created file200to perform the actual updates (i.e., step610of method600). Because the ancestor of child directory502has been locked, no other transaction can change the sub-tree rooted at that ancestor. To avoid generating a large update transaction from the ancestor directory502to a child directory502, the transaction may be broken up into smaller chained transactions, implemented using standard techniques.

FIG.7depicts a flow diagram of a method700of identifying files200for deduplication, and deduplicating the identified files200, according to an embodiment. Method700may be performed by deduplication module144.

At step702, deduplication module144obtains the current logical time of GLC174.

At step704, deduplication module or another component of system100increments GLC174. Although incrementing GLC174is described as occurring at this point within method700, incrementing of GLC174may occur at other times within, before, after, or between the methods described herein, as appropriate. For example, GLC174may be incremented before step710between steps710and712, after step712, or at some point within method300.

At step706, deduplication module144, the file system of chunk store134and/or storage(s)114, or another component of system100adds an entry within time table172. The entry maps (a) the new logical time of GLC174, attained after incrementing of GLC174, to (b) real-world time at the time of incrementing GLC174.

At step708, deduplication module144determines a logical range for identification of files200for deduplication. For example, if at a previous execution of method700, all files that were created or modified within the logical time range of 1-3 were deduplicated, then deduplication module144may determine that a logical range of 4-5 is the appropriate logical range. In an embodiment, the logical range may be determined so as to exclude files200that were modified or created “recently.” For the purpose of step708, “recently” may mean, for example, a most recent length of threshold of time, such as the previous 24 hours. The reason for excluding files200that were recently created or modified is that resources are better utilized when only deduplicating (a) files200that are not temporary files that may be deleted soon, and (b) files200that have stabilized and are no longer undergoing frequent changes.

At step710, deduplication module144uses the logical range of step708to identify files200for deduplication. Step710is described in detail below by method800ofFIG.8.

FIG.8depicts a flow diagram of a method800of identifying files200that were modified or recreated during the logical range determined by method700, according to an embodiment. Method800may be performed by deduplication module144.

At step802, deduplication module144identifies the root directory502(e.g., directory502AofFIG.5) of file system tree500. As part of step802, deduplication module144chooses the root directory502for further processing and evaluation by method800.

At step804, deduplication module144determines whether TQ504of the current directory502contains a timestamp that is within the logical range. If step804is reached from step802, then the current directory502is the root directory502. If step804is reached from step812, then the current directory502is one of the child or descendant directories502of tree500.

If TQ504of the current directory502does not contain a logical timestamp that is within the logical range, then the current directory502and all child and descendant directories502do not contain files200that have been modified or created within the logical range. This means that the current directory502and all descendant directories502may be skipped for further processing by method800, and method800continues to step806.

If TQ504of the current directory502contains a logical timestamp that is within the logical range, then the current directory502or a child or descendant directory502of current directory502may contain at least one file200that was modified or created within the logical range. If TQ504of the current directory502contains a logical timestamp that is within the logical range, then method800continues to step808.

At step806, deduplication module144skips processing all child and descendant directories502and files200of the current directory502. In an embodiment, as part of step806, deduplication module make a record or note of which directory502did not contain a logical timestamp within the logical range, and so may be skipped (along with its child and descendant directories502).

At step808, deduplication module144adds to the list of identified files200for deduplication any files200located in the current directory502that were modified or created within the logical range. As part of step808, deduplication module144determines whether the current directory502contains any files200. If not, then step808is skipped. If files are present within the current directory502, then deduplication module converts the logical range to a real-world time range by accessing time table172. Deduplication module144then checks the modification time of each file200within the current directory to determine whether the file200has been modified with the real-world and/or logical range. Each file200that has been modified within the real-world or logical range is added to the list of identified files for deduplication.

At step810, deduplication module144determines whether more directories502remain to be processed by method800. If not, then method800ends. If so, then method800continues to step812. Otherwise, method800ends.

At step812, deduplication module144traverses to the next directory502within tree500. The traversal order may be any order appropriate for traversing a tree, such as orders known in the art. For example, tree500may be traversed in an “inorder,” “preorder,” or “postorder” manner. After step812, method800returns to directory804.

It should be understood that, for any process described herein, there may be additional or fewer steps performed in similar or alternative orders, or in parallel, within the scope of the various embodiments, consistent with the teachings herein, unless otherwise stated.