HK1173514B - Garbage collection and hotspots relief for a data deduplication chunk store - Google Patents

Description

Garbage collection and hot spot release for data deduplication block storage

Technical Field

The invention relates to garbage collection and hot spot release for data deduplication chunk storage.

Background

Data deduplication, also known as data optimization, is an action that reduces the amount of physical bytes of data that need to be stored on disk or transferred over a network, without compromising the fidelity or integrity of the original data. Data deduplication reduces the storage capacity needed to store data and may therefore result in savings in storage hardware costs and data management costs. Data deduplication provides a solution to handle the rapidly growing number of digitally stored data.

Data deduplication may be performed according to one or more techniques for eliminating redundancy within and between persistent stored files. For example, according to one technique, unique data regions that occur multiple times in one or more files may be identified, and a single copy of these identified unique data regions may be physically stored. References to these identified unique data regions (also referred to as data "blocks") may be stored, the references indicating the files containing these unique data regions and the locations within these files. This technique is generally referred to as single instantiation. In addition to single instantiation, compression of data may also be performed. Other data reduction techniques may also be implemented as part of the data deduplication solution.

Managing data stored according to data deduplication technologies presents various difficulties. For example, due to the fragmentation of data storage imposed by data deduplication, there may be latency in accessing files stored according to the deduplication. This latency limits adoption of data deduplication solutions, particularly for primary storage data where users desire seamless, fast access to files. Moreover, the data deduplication algorithm may run on a dedicated device, or on the device that stores and provides the data (e.g., a file server). In the file server example, data deduplication may not be the primary function of the device, and thus data deduplication techniques may need to be efficient so as not to unduly consume device resources (e.g., memory, input/output (I/O) mechanisms, Central Processing Unit (CPU) capacity, etc.). Moreover, because the amount of digital data grows at very high speeds, the size of the storage device (e.g., disk) and the overall storage capacity associated with the computing device must increase, leading to difficulties with data deduplication technologies that do not scale well with increasing storage.

Furthermore, there are challenges in handling deletion of optimized files from storage. Deleting such files may result in unused data corresponding to the deleted files remaining in storage. This remaining unused data occupies memory space that could otherwise be used. Challenges also exist in enabling data to be reliably stored, particularly when such data is shared by multiple files. When data is shared by a large number of files, the loss of stored data sectors can negatively impact multiple files or even thousands of files.

Disclosure of Invention

This summary is provided to introduce a selection of concepts in a simplified form that are further described below in the detailed description. This summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

Methods, systems, and computer program products are provided for garbage collecting unused data blocks in storage and for storing redundant copies of frequently used data blocks.

For example, various implementations are provided for garbage collecting unused data blocks in storage. According to one implementation, unused data chunks stored in a chunk container are identified based on one or more stream map chunks indicated as deleted. The identified data block is indicated as deleted. The storage space in the chunk container filled with the data chunks indicated as deleted may be reclaimed.

In one implementation, unused data blocks may be identified as follows: the plurality of stream map chunks are scanned to determine any stream map chunks not indicated as deleted. The data chunk identifiers referenced by each stream map chunk indicated as undeleted are included in a data structure (e.g., Bloom filter). The plurality of stream map chunks are scanned to determine any stream map chunks indicated as deleted. Data chunk identifiers referenced by stream map chunks not included in the data structure that are indicated as deleted are determined and indicated as deleted.

In one implementation, the storage space filled by data blocks indicated as deleted may be reclaimed as follows: each data chunk in the chunk container that is not indicated as deleted is copied to the new container file. The redirection table of the new container file is populated to map the unique identifier of the copied data chunk to the starting offset of the data chunk in the new container file. The chunk container is then deleted and the new container file may be renamed to the file name of the chunk container to replace the chunk container as a compressed version of the chunk container.

Various implementations are provided for data backup in block storage. According to one implementation, a data chunk is received for storage in a chunk container. It is determined whether the received data chunk is a "hot spot" and has not been copied for backup. A "hot spot" data chunk may be defined as being included in a predetermined percentage of the most referenced data chunks in the data store, having a number of references greater than a predetermined reference threshold, or both. If the received data chunk is a hotspot and has not been copied for backup, a backup copy of the received data chunk is stored in a backup container.

In one implementation, the storing of the backup copy of the received data blocks may be performed as follows: it is determined whether the received data block is a duplicate of a data block stored in the block store. If it is determined that the received data chunk is a duplicate, it is determined whether the received data chunk has an entry in the reference count table. If it is determined that the received data chunk is a duplicate and has an entry in the reference count table, the reference count value in the entry for the received data chunk in the reference count table is incremented. If it is determined that the received data chunk is a duplicate and there is no entry in the reference count table, adding an entry to the reference count table for the received data chunk, the entry comprising: a data block identifier of the received data block; a reference count value for the received data block, the reference count value being a sum of an initial reference count value and an expected count value; an indication that the reference count value of the received data block is not an exact value; and an indication that the received data chunk is not replicated in the backup container. If it is determined that the received data chunk is not a duplicate, an entry for the received data chunk is added to the reference count table. The added entries include: a data block identifier of the received data block; an initial reference count value for the received data block; an indication that the reference count value of the received data block is an exact value; and an indication that the received data chunk is not replicated in the backup container.

If it is determined that the received data chunk is a duplicate, it is determined whether the received data chunk is replicated in the backup container. If it is determined that the received data chunk is not replicated in the backup container, the received data chunk may be designated for replication in the backup container based on an analysis of the reference count table. The received data block may be designated for replication if it is determined that the received data block has a reference count value greater than a minimum reference count value for replicated data blocks and/or the reference count value for the received data block is greater than a predetermined threshold.

If it is determined that the received data chunk is not replicated in the backup container and is designated for replication in the backup container based on the analysis of the reference count table, a backup copy of the received data chunk is stored in the backup container and an entry of the received data chunk in the reference count table is modified to include an indication that the received data chunk is replicated in the backup container.

It may be determined that the reference count table has reached a predetermined size. As a result, the reference count table may be reintegrated to reduce memory consumption while maintaining entries for data chunks that have met the hotspot condition. If the memory is sufficient, additional entries may be retained for data blocks that have a high reference count but have not met the hotspot condition. After the refmerge, a backup copy of the data chunks may be stored in a backup container for data chunks that have entries in the refcount table after the refmerge, that have met the hotspot condition, and that have not yet appeared in the backup container.

Computer program products for garbage collecting unused data chunks in storage, for storing backup copies of hot spot chunks, and for further embodiments described herein are also described herein.

Further features and advantages of the invention, as well as the structure and operation of various embodiments of the invention, are described in detail below with reference to the accompanying drawings. It should be noted that the present invention is not limited to the particular embodiments described herein. These examples are presented herein for illustrative purposes only. Other embodiments will be apparent to persons skilled in the relevant art based on the description contained herein.

Drawings

The accompanying drawings, which are incorporated herein and form a part of the specification, illustrate the present invention and, together with the description, further serve to explain the principles of the invention and to enable a person skilled in the pertinent art to make and use the invention.

FIG. 1 shows a block diagram of a data deduplication system, according to an example embodiment.

FIG. 2 illustrates a block diagram of a chunk store, according to an example embodiment.

FIG. 3 illustrates a block diagram of a chunk store, according to an example embodiment.

FIG. 4 shows a block diagram of metadata included in a stream map, according to an example embodiment.

FIG. 5 illustrates the chunk store of FIG. 3, further indicating some data chunks referenced by the stream map, according to an example embodiment.

FIG. 6 shows a block diagram of a data stream storage system, according to an example embodiment.

FIG. 7 shows a flow diagram for storing a data stream, according to an example embodiment.

FIG. 8 shows a block diagram of a metadata generator, according to an example embodiment.

FIG. 9 shows a flowchart for assigning locality indicators, according to an example embodiment.

FIG. 10 shows a block diagram illustrating an example of storing a data stream in a data store, according to an embodiment.

FIG. 11 illustrates a block diagram of a block storage interface including a rehydration module, according to an example embodiment.

FIG. 12 shows a block diagram of a chunk container, according to an example embodiment.

FIG. 13 shows a block diagram of a data chunk identifier, according to an example embodiment.

FIG. 14 shows the example of FIG. 10 where a data stream is stored in a data store, and also illustrates the effect of removing a data block from the data store, according to an embodiment.

FIG. 15 shows a block diagram of a redirection table, according to an example embodiment.

FIG. 16 shows a flow diagram for storing a data stream, according to an example embodiment.

FIG. 17 shows a block diagram of a data chunk redirection system, according to an example embodiment.

FIG. 18 shows a flowchart for locating data chunks in a chunk container, according to an example embodiment.

FIG. 19 illustrates a block diagram of a rehydration module to access a chunk store to rehydrate a data stream, according to an example embodiment.

FIG. 20 shows a flowchart for performing garbage collection of a chunk container, according to an example embodiment.

FIG. 21 shows a flowchart providing a process for identifying and indicating data chunks for deletion according to an example embodiment.

FIG. 22 shows a flowchart providing a process for reclaiming storage space filled with data chunks indicated for deletion, according to an example embodiment.

FIG. 23 illustrates a block diagram of a garbage collection module that communicates with a stream container and a chunk container to reclaim storage space filled by deleted data chunks, according to an example embodiment.

FIG. 24 illustrates an example of a block diagram of data chunks being copied from an old chunk container to a new chunk container, according to an embodiment.

FIG. 25 shows a flowchart for storing backup copies of data chunks stored in a chunk container, according to an example embodiment.

26A and 26B illustrate an example of the process of FIG. 25, according to an embodiment.

FIG. 27 illustrates a block diagram of a backup storage module that communicates with a stream container, a chunk container, and a backup container to backup frequently referenced data chunks, according to an example embodiment.

FIG. 28 shows a flowchart providing a process for reconsolidating a reference count table, according to an example embodiment.

FIG. 29 shows a flowchart providing an example of the reconsolidation process of FIG. 28, according to an example embodiment.

FIG. 30 illustrates a block diagram of an example computer that can be used to implement embodiments of the invention.

The features and advantages of the present invention will become more apparent from the detailed description set forth below when taken in conjunction with the drawings, in which like reference characters identify corresponding elements. In the drawings, like reference numbers generally indicate identical, functionally similar, and/or structurally similar elements. The drawing in which an element first appears is indicated by the leftmost digit(s) in the corresponding reference number.

Detailed Description

I. Introduction to

This specification discloses one or more embodiments that include the features of the present invention. The disclosed embodiments are merely illustrative of the invention. The scope of the invention is not limited to the disclosed embodiments. The invention is defined by the appended claims.

References in the specification to "one embodiment," "an example embodiment," etc., indicate that the embodiment described may include a particular feature, structure, or characteristic, but every embodiment may not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same embodiment. Further, when a particular feature, structure, or characteristic is described in connection with an embodiment, it is submitted that it is within the knowledge of one skilled in the art to effect such feature, structure, or characteristic in connection with other embodiments whether or not explicitly described.

In this specification, optimized data refers to data that has been optimized or data that has been deduplicated by one or more of data deduplication techniques (such as single instantiation and compression of blocks, etc.). Optimized streams refer to streams that are deduplicated, or in other words, their data has been optimized using data deduplication techniques.

Example embodiments

Embodiments provide techniques for data deduplication. These embodiments allow for a reduction in the amount of data (e.g., number of bytes) to be stored or to be transferred without compromising the fidelity or integrity of the data. For example, embodiments allow for a reduction in the amount of latency in accessing optimized data. Moreover, embodiments enable resources, such as computing machines/devices, to be more efficiently used, thereby reducing resource consumption. Further, embodiments provide for storage of backup copies of data for data deduplication, garbage collection, and scalability as the amount of digital data stored grows.

For example, in one embodiment, a scalable chunk store is provided for data deduplication. This chunk store allows various techniques for minimizing latency in access to deduplicated data, reducing machine resource consumption (e.g., memory and disk I/O), and enhancing reliability during data deduplication, rehydration, garbage collection, and data backup. Example embodiments are described in further detail in the following subsections.

A. Exemplary data deduplication embodiments

In various embodiments, the data to be stored may be optimized to reduce the amount of storage required for the data. For example, the data stream may be stored in the form of unique data blocks. The data chunks may be referenced by a map that defines the data stream. In this manner, the data stream is stored more efficiently because multiple mappings may reference the same stored data block, rather than the same data block being stored multiple times. Also, optimized data may be requested from storage (e.g., by an application) as needed. In this case, the data stream may be reassembled from the stored data chunks according to the corresponding mapping.

For example, FIG. 1 shows a block diagram of a data deduplication system 100, according to an example embodiment. As shown in FIG. 1, system 100 includes storage system 102, data deduplication module 104, maintenance module 106, and storage 108. Further, the storage system 102 includes a data flow API (application programming interface) 110, a block maintenance API 112, and a data access API 114. The system 100 is described below to illustrate the storage of optimized data and the retrieval of optimized data from storage, and is not intended to be limiting.

System 100 is configured to allow data to be stored in storage 108 in an efficient manner, and to allow data to be retrieved from storage 108. For example, in an embodiment, data deduplication module 104 may be present. The data deduplication module 104 is configured to optimize the received data for storage. For example, the data deduplication module 104 may segment and compress received data received as the data stream 132. Data stream 132 may include a portion of a data file, a single data file, multiple data files, and/or a combination of files and/or portions of files. As shown in fig. 1, the data deduplication module 104 generates data chunks 124, the data chunks 124 may be compressed and segmented versions of the data stream 132.

The data flow API110 provides an interface for the storage system 102 to receive the data chunks 124. The data chunks 124 may include a plurality of data chunks forming a data stream 132 from which the data chunks 124 are generated 132. The data flow API110 may be configured in any suitable manner known to those skilled in the relevant art. The data stream API110 may output data chunks 124 received by the chunk store interface 116.

As shown in FIG. 1, storage 108 is coupled to storage system 102. Block store interface 116 is an interface between APIs 110, 112, and 114 and store 108. For example, chunk store interface 116 may receive data chunks 124 and may store data chunks of data chunks 124 in storage 108. For example, as shown in FIG. 1, storage 108 includes chunk store 118. Chunk store interface 116 may store received ones of data chunks 124, such as data chunks 128, in chunk store 118.

The data access API 114 provides an interface for applications to request data of the storage system 102. For example, as shown in FIG. 1, the data access API 114 may receive a data stream request 120. The data access API 114 may be configured in any suitable manner known to those skilled in the relevant art. The data access API 114 may output a data stream request 120 to be received by the chunk store interface 116. Chunk store interface 116 may request data chunks from store 108 (e.g., from chunk store 118) that correspond to the data streams requested in data stream request 120. Chunk store interface 116 may receive the requested data chunk from store 108 as data chunk 130, and may provide a data stream including data chunk 130 to data access API 114. The data access API 114 may provide a data stream (e.g., one or reassembled files) as a data stream response 122 to the requesting application.

Also, maintenance module 106 may be present to perform one or more types of maintenance jobs related to data chunks stored in chunk store 118. For example, maintenance module 106 may include a defragmentation module that performs defragmentation of data chunks stored in storage 108. For example, the defragmentation module may be configured to: eliminate empty space in storage 108, move related data blocks into a sequence, and/or perform other related tasks. In another example, maintenance module 106 may include a garbage collection module that performs garbage collection on data blocks stored in storage 108. For example, the garbage collection module may be configured to delete unused data blocks in the storage 108 (e.g., perform compaction). In other embodiments, maintenance module 106 may perform additional or alternative maintenance tasks on storage 108.

As shown in FIG. 1, the block maintenance API 112 provides an interface for the maintenance module 106 to interact with the storage system 102. Maintenance module 106 may generate maintenance tasks 126 (e.g., defragmentation instructions, compression instructions, data block deletion instructions, etc.) that are received by block maintenance API 112. The block maintenance API 112 may be configured in any suitable manner known to those skilled in the relevant art. The block maintenance API 112 may provide the maintenance tasks 126 to the block storage interface 116. The block store interface 116 may allow maintenance tasks 126 to be performed on data blocks stored in the store 108.

Storage system 102 may be implemented in any suitable form, including one or more computer/computing devices or the like. Storage 108 may include one or more of any type of storage mechanism, including a magnetic disk (e.g., in a hard disk drive), an optical disk (e.g., in an optical disk drive), a magnetic tape (e.g., in a tape drive), one or more memory devices (e.g., flash memory, Solid State Drive (SSD), etc.), and/or any other suitable type of storage medium.

Note that data deduplication system 100 is an example of an environment in which embodiments of the present invention may be implemented. The data deduplication system 100 is provided for purposes of illustration and is not intended to be limiting. Embodiments may be incorporated in other types and configurations of data deduplication systems.

B. Example Block storage embodiments that allow data Block positioning

Chunk store 118 in fig. 1 may store data streams in the form of data chunks in any manner. For example, chunk store 118 may store a map indicating data chunks included in a data stream, and may store referenced data chunks. In one embodiment, chunk store 118 does not store duplicate copies of data chunks, according to data deduplication techniques.

For example, FIG. 2 shows a block diagram of chunk store 118, according to an example embodiment. As shown in FIG. 2, chunk store 118 includes a stream container 202 and a chunk container 204. Stream container 202 includes one or more stream maps 206 and chunk container 204 includes a plurality of data chunks 208. Although shown in FIG. 2 as including a single stream container 202 and chunk container 204 for ease of depiction, chunk store 118 may include any number of stream containers 202 and chunk containers 204. Data chunk 208 is a piece of data that is referenced by one or more data streams (e.g., data stream 132 in fig. 1). Stream map 206 is a data structure that describes a mapping between the original data stream structure and the optimized data block structure. Stream map 206 contains data block location information and data block ordering, either directly or through an indirection layer, so that referenced data blocks can be located and assembled into a filestream view. Data chunks 208 and stream map 206 are stored in stream container 202 and chunk container 204, respectively, which may be files in a file system. In an embodiment, chunk store 118 stores all data in chunks, such that stream map 206 is stored as data chunks containing internal metadata (data stream metadata) that describes the mapping of file streams to data chunks 208, data block addresses, and hashes.

In various embodiments, stream container 202 and chunk container 204 may be configured in various ways. For example, FIG. 3 shows a block diagram of a chunk store 300, according to an example embodiment. Chunk store 300 is one example of chunk store 118 in FIG. 2. As shown in FIG. 3, chunk store 300 includes a stream container 302 and a chunk container 304. Stream container 302 is one example of stream container 202 in FIG. 2, and chunk container 304 is one example of chunk container 204 in FIG. 2. In the embodiment of FIG. 3, stream container 302 includes a file header 306, a redirection table 308, and a plurality of stream maps 310. First and second stream maps 310a and 310b are shown in fig. 3 for purposes of illustration, but in embodiments, any number of stream maps 310 may be included in stream container 302, including hundreds, thousands, and even greater numbers of stream maps 310. Chunk container 304 includes a file header 318, a redirection table 320, and a plurality of data chunks 322. First data chunk 322a and second data chunk 322b are shown in FIG. 3 for purposes of illustration, but in embodiments, any number of data chunks 322 may be included in chunk container 304, including hundreds, thousands, and even greater numbers of data chunks 322. These features of fig. 3 are described below.

In embodiments where the stream container 302 is stored as a file, the file header 306 is the file header of the stream container 302. The file header 306 may include information associated with the stream container 302 including a stream container identifier (e.g., a stream container identification number), and the like.

Redirection table 308 is optionally present in stream container 302. When present, redirection table 308 may store information about the change in location of any of stream maps 310 in stream container 302. For example, the first stream map 310a may be deleted from the stream container 302, and the second stream map 310b may be moved to the location of the first stream map 310a (e.g., due to a defragmentation or compaction routine). After the move, the stream container 302 may be accessed by the application to retrieve the second stream map 310 b. However, the application may still be using the previous location of the second stream map 310 b. Redirection table 308 may include a mapping of second stream map 310b that indicates a current location of second stream map 310 b. Accordingly, the application may access redirection table 308 (e.g., indirectly, as through API 116 of fig. 1) to determine the current location of second stream map 310b, and thus may be allowed to retrieve second stream map 310b from the new location.

Stream map 310 is an example of stream map 206 in fig. 2. Each of stream maps 310 is used to define a sequence of data chunks 322 that make up a particular data stream. As shown in fig. 3, each of stream maps 310 includes a stream header 312, metadata 314, and hash values 316. For example, a first stream map 310a is shown to include a stream header 312a, metadata 314a, and hash values 316a, while a second stream map 310b is shown to include a stream header 312b, metadata 314b, and hash values 316 b. Each stream header 312 includes information associated with a corresponding stream map 310, such as a stream map identifier (e.g., a stream map identification number), and the like. Each metadata 314 includes information describing data chunks 322 that make up the data stream defined by the corresponding stream map 310. Hash value 316 is optionally present. Hash values 316 are hash values of data chunks 322 that make up the data stream defined by the corresponding stream map 310. Hash values 316 may be stored in stream maps 310 in order to provide efficient access to hash vectors of data blocks that make up a respective data stream. This may be useful, for example, for wired data transfer scenarios where fast access to the entire list of data stream hashes (hashes of all optimized file chunks) is desired.

Various types of information may be included in the metadata 314. For example, FIG. 4 shows a block diagram of metadata 400, according to an example embodiment. Metadata 400 is an example of metadata 314 in fig. 3. Metadata 400 is an example of metadata that may be included in stream map 310 (e.g., per-chunk metadata) for each referenced data chunk 322. As shown in fig. 4, metadata 400 includes a data stream offset 402, a data chunk identifier 404, and a locality indicator 406. Data stream offset 402 indicates the location of the associated data chunk 322 in the data stream defined by the particular stream map 310. For example, data stream offset 402 may indicate the number of bytes from the beginning of the data stream, or the number of bytes from other reference points in the data stream where associated data chunk 322 begins. Data chunk identifier 404 (also referred to as a chunk id or "reliable chunk locator") is a reference or pointer to the corresponding data chunk 322 in chunk container 304. For example, data chunk identifier 404 for a particular data chunk allows for reliable location of the data chunk in chunk container 304. The data chunk identifier 404 may have various forms, including example forms described in more detail below (e.g., with reference to fig. 13). Locality indicator 406 is information that indicates the order of chunk insertion in chunk container 304, allowing a determination of which data chunks 322 may be referenced by common stream map 310. For example, locality indicator 406 allows data chunks 322 associated with the same stream map 310 to be contiguously stored in chunk container 304, or allows data chunks 322 to be stored closely together when contiguous storage is not straightforward (e.g., because multiple stream maps 310 refer to the same data chunk 322). The locality indicator 406 may also be used by other data deduplication components, such as a chunk hash index, to improve hash lookup and insertion performance, or by a defragmenter to rearrange data chunks to reduce latency for a particular data stream.

Referring to chunk container 304 in FIG. 3, in embodiments where chunk container 304 is stored as a file, file header 318 is a file header of chunk container 304. File header 318 may include information associated with chunk container 304, including a chunk container identifier (e.g., chunk container identification number), a chunk container generation indicator indicating a revision number for chunk container 304, and so forth.

Redirection table 320 may optionally be present in chunk container 304. When present, redirection table 320 may store information about the change in location in chunk container 304 of any one of data chunks 322 in a manner similar to that in which redirection table 308 of stream container 302 handles changes in location of stream map 310.

Data chunk 322 is an example of data chunk 208 in fig. 2. As shown in FIG. 3, each of data chunks 322 includes a chunk header 324 and chunk data 326. For example, first data chunk 322a includes chunk header 324a and chunk data 326a, and second data chunk 322b includes chunk header 324b and chunk data 326 b. Each chunk header 312 includes information associated with a corresponding data chunk 322, such as a data chunk identifier, and the like. Each chunk data 326 includes corresponding data, which may be in compressed or uncompressed form.

Stream map 310 and data chunks 322 are stored in stream container 302 and chunk container 304, respectively, to allow data deduplication. For example, chunk store interface 116 in FIG. 1 may receive data chunks 124 associated with data stream 132 and may store the data chunks in chunk store 300 in FIG. 3. For example, for a particular data stream 132, chunk store interface 116 may generate a stream map that is stored as stream map 310 in stream container 302 by chunk store interface 116, stream map 310 referencing one or more data chunks 322 stored in one or more chunk containers 304.

For example, FIG. 5 illustrates chunk store 300 of FIG. 3 and indicates some data chunks 322 that are referenced by stream maps 310, according to an example embodiment. As shown in FIG. 5, first stream map 310a includes metadata 314a, where metadata 314a includes references to first data chunk 322a and second data chunk 322b in chunk container 304. Thus, first data chunk 322a and second data chunk 322b are included in the source data stream associated with first stream map 310 a. For example, metadata 314a may include a data stream offset 402 value for first data chunk 322a indicating the location of first data chunk 322a in the source data stream defined by first stream map 310a, a data chunk identifier 404 for first data chunk 322a in chunk container 304 (e.g., the data chunk identifier for first data chunk 322a stored in chunk header 324 a), and a locality indicator 406 for first data chunk 322 a. Moreover, metadata 314a may include a data stream offset 402 value for second data chunk 322b that indicates a location of second data chunk 322b in the source data stream, a data chunk identifier 404 for second data chunk 322b in chunk container 304 (e.g., the data chunk identifier for second data chunk 322b stored in chunk header 324 b), and a locality indicator 406 for second data chunk 322 b. In an embodiment, first data chunk 322a and second data chunk 322b may have locality indicators of the same value that is generated to correspond to the source data stream defined by first stream map 310a, and that indicates that first data chunk 322a and second data chunk 322b are contiguously (adjacently) stored in chunk container 304.

In addition, second stream map 310b includes metadata 314b, where metadata 314b includes a reference to second data chunk 322b in chunk container 304. For example, metadata 314b may include a data stream offset 402 value for second data chunk 322b that indicates a location of second data chunk 322b in the source data stream defined by second stream map 310b, a data chunk identifier 404 for second data chunk 322b in chunk container 304 (e.g., the data chunk identifier for second data chunk 322b stored in chunk header 324 b), and a locality indicator 406 for second data chunk 322 b. Locality indicator 406 of second data chunk 322b in metadata 314b has the same value as the locality indicators generated for first data chunk 322a and second data chunk 322b, because second data chunk 322b was originally stored in chunk container 304 for first stream map 310 a. Any other data chunks 322 (not shown in FIG. 5) that are newly stored in chunk container 304 are assigned a new value for locality indicator 406 when the source data stream defined by second stream map 310b is stored in chunk store 300.

Block store interface 116 in FIG. 1 may be configured in various ways to store data streams in block store 300 of FIG. 3. For example, FIG. 6 shows a block diagram of a data stream storage system 600, according to an example embodiment. As shown in FIG. 6, data stream storage system 600 includes data stream parser 602, chunk store interface 116, stream container 302, and chunk container 304. In an embodiment, data stream parser 602 may be included in data deduplication module 104 of FIG. 1. In the FIG. 6 embodiment, chunk store interface 116 includes a data chunk store manager 604, a metadata generator 606, and a stream map generator 608. These features in fig. 6 are described below with reference to fig. 7. FIG. 7 shows a flow diagram 700 for storing a data stream, according to an example embodiment. In an embodiment, system 600 in FIG. 6 may operate according to flowchart 700. Further structural and operational embodiments will be apparent to those skilled in the relevant arts based on the discussion of flowchart 700. Flowchart 700 and system 600 are described as follows.

Flowchart 700 begins with step 702. In step 702, the data stream is parsed into data chunks. For example, as shown in FIG. 6, data stream parser 602 may receive data stream 610. Similar to data stream 132 in FIG. 1, data stream 610 may include one or more files and/or file portions. Data stream parser 602 is configured to parse data stream 610 into a sequence of data chunks indicated as data chunk sequence 612. For example, in an embodiment, data chunk sequence 612 may include a sequence of data chunks in the order in which the data chunks are positioned in data stream 610. The data chunks in the sequence of data chunks 612 may have the same size or may have different sizes.

In step 704, a determination is made as to whether any of the data chunks are duplicates of data chunks stored in the chunk container. For example, as shown in FIG. 6, data chunk store manager 604 receives data chunk sequence 612. Data chunk storage manager 604 is configured to determine whether any of the data chunks in data chunk sequence 612 have been stored in chunk container 304 and are therefore duplicate. For example, in an embodiment, as shown in FIG. 6, data chunk storage manager 604 may receive data chunk information 626 from chunk container 304, which data chunk information 626 may include a hash value for each data chunk 322 stored in chunk container 304. In another embodiment, data chunk storage manager 604 may receive hash value 316 (FIG. 3) from stream container 302, hash value 316 being a hash value of data chunks 322 stored in chunk container 304. Data chunk storage manager 604 may generate a hash value for each data chunk in data chunk sequence 612 and may compare the generated hash value to hash values received in data chunk information 626 (or from stream container 302) to determine which data chunks in data chunk sequence 612 have been stored in chunk container 304. In other embodiments, data chunk store manager 604 may determine which data chunks of data chunk sequence 612 have been stored in chunk container 304 in other manners known to those skilled in the relevant art.

As shown in FIG. 6, data chunk storage manager 604 generates stored chunk indication 616, which stored chunk indication 616 indicates which data chunks of data chunk sequence 612 have been stored in chunk container 304.

Referring again to FIG. 7, in step 706, data chunks determined not to be duplicates are stored in one or more chunk containers in a contiguous arrangement and in the same order as in the data stream. For example, in an embodiment, data chunk storage manager 604 may be configured to store data chunks of data chunk sequence 612 that are not determined to be stored in chunk container 304. For example, in an embodiment, data chunk storage manager 604 may generate a chunk header 324 (e.g., a data chunk identifier) for each new data chunk, and store each new data chunk as a data chunk 322 having chunk header 324 and chunk data 326. Furthermore, in an embodiment, data chunk storage manager 604 is configured to store new data chunks in chunk container 304 in a contiguous arrangement and in the same order as in the source data stream (e.g., in the order received in data chunk sequence 612). Note that in another embodiment, data chunks determined to not be duplicates may be stored in multiple chunk containers in a manner that facilitates parallel reading of the data chunks.

In step 708, metadata is generated for each of the data chunks in the chunk sequence, the metadata for the data chunk including a data stream offset, a pointer to a location in the chunk container, and a locality indicator. For example, as shown in FIG. 6, metadata generator 606 may receive data chunk sequence 612 and stored chunk indication 616. In an embodiment, metadata generator 606 may be configured to generate metadata (e.g., metadata 314 in fig. 3). Metadata generator 606 may generate metadata for each data chunk in data chunk sequence 612, including data stream offset 402, data chunk identifier 404, and locality indicator 406. For data chunks determined to have been stored in chunk container 304 (in step 704), data chunk identifier 404 is configured to point to the stored data chunk. For each data chunk newly stored in chunk container 304 in step 708, data chunk identifier 404 is configured to point to the newly stored data chunk.

In various embodiments, metadata generator 606 may be configured in various ways to generate metadata. For example, FIG. 8 shows a block diagram of metadata generator 606, according to an example embodiment. As shown in FIG. 8, metadata generator 606 includes a metadata collector 802 and a locality indicator generator 804. As shown in FIG. 8, locality indicator generator 804 receives a sequence of data chunks 612 and a stored chunk indication 616. Locality indicator generator 804 is configured to generate locality indicator 406 for each data chunk of data chunk sequence 612 that is not indicated by stored chunk indication 616 as having been stored in chunk container 304. As shown in FIG. 8, locality indicator generator 804 generates one or more locality indicator values 622 that indicate locality indicator 406 for each data chunk in sequence of data chunks 612.

Metadata collector 802 receives locality indicator value 622, data chunk sequence 612, and stored chunk indication 616. Metadata collector 802 collects metadata for each data chunk in data chunk sequence 612. For example, metadata collector 802 may determine data stream offset 402 for each data chunk received in data chunk sequence 612. For example, metadata collector 802 may determine data stream offset 402 for each data chunk based on the order in which the data chunks are received in data chunk sequence 612 and/or the length of the received data chunks (e.g., for a data chunk, data stream offset 402 may be set to the sum of the lengths of the data chunks received in data chunk sequence 612 prior to the data chunk, or otherwise set). Metadata collector 802 may generate data chunk identifier 404 for each data chunk to identify each data chunk in chunk container 304. Metadata collector 802 assigns each data block a respective locality indicator value received in locality indicator values 622. Metadata collector 802 outputs metadata associated with each data chunk received in data chunk sequence 612 as data chunk metadata 620.

In an embodiment, metadata generator 606 may assign locality indicator values 622 according to FIG. 9. FIG. 9 shows a flowchart 900 for assigning locality indicators, according to an example embodiment. Flowchart 900 begins with step 902. In step 902, a new locality indicator value associated with the data stream is selected. For example, when data chunk sequence 612 is received for a data stream, locality indicator generator 804 may select a new locality indicator value to associate with the data stream. This new locality indicator value is unique and is different from the locality indicator value being used for previously received data streams that already have data chunks stored in chunk container 304. For example, the new locality indicator value may be a unique number generated in association with the data stream. Locality indicator generator 804 outputs the selected locality indicator value as selected locality indicator value 622.

In step 904, the new locality indicator value is assigned to the locality indicator of each of the data blocks determined in step 704 to not be duplicates. For example, as shown in FIG. 8, selected locality indicator value 622 is received by metadata collector 802. Metadata collector 802 is configured to assign a selected locality indicator value 622 as locality indicator 406 to each data chunk of the first set of data chunks (i.e., new data chunks) in data chunk sequence 612 that are indicated by stored chunk indication 616 as not already stored in chunk container 304.

In step 906, for each data chunk determined to be a duplicate in step 704, a locality indicator value associated with the matching data chunk already stored in the chunk container is assigned to the locality indicator. For example, each data chunk 322 (duplicate data chunk) already stored in chunk container 304 has an assigned locality indicator 406 because the locality indicator value is assigned to the data chunk 322 at the time the data chunk 322 was originally stored in chunk container 304. In an embodiment, for data chunks indicated by stored chunk indication 616 as having been stored in a chunk container, metadata collector 802 assigns a locality indicator value associated with a data chunk already stored in chunk container 304 to a matching/duplicate data chunk received in data chunk sequence 612. Thus, one or more groups of data chunks in data chunk sequence 612 may each be assigned a respective locality indicator value associated with a respective data chunk stored in chunk container 304.

Referring again to FIG. 7, in step 710, a stream map is generated for the data stream that includes the generated metadata. For example, as shown in FIG. 6, stream map generator 608 receives data chunk metadata 620 for each data chunk received in data chunk sequence 612 for a particular data stream. Stream map generator 608 generates a stream map 624 associated with the data stream that includes data chunk metadata 620 for each received data chunk. Further, stream map generator 608 may generate stream header 312 for stream map 624 and may include hash value 316 for each received data chunk in stream map 624.

In step 712, the stream map is stored in a stream container. For example, as shown in fig. 6, stream map generator 608 may store (or "persist") stream map 624 in stream container 302 (e.g., as stream map 310).

FIG. 10 shows a block diagram illustrating an example of storing a data stream in a data store, according to an embodiment. FIG. 10 is provided for purposes of illustration and is not intended to be limiting. In the example of fig. 10, the first data stream 1002a is stored in a data store, followed by the second data stream 1002 b. For the first data stream 1002a, a stream link 1008a (also referred to as a "stream pointer" or "stream stub (stub)") is shown, and for the second data stream 1002b, a stream link 1008b is shown. As shown in FIG. 10, first data stream 1002a includes four data chunks 1014a-1014 d. As described above, stream map 1004a may be generated for first data stream 1002a and four data chunks 1014a-1014d may be stored in chunk container 1006. Stream map 1004a includes pointers (represented by arrows in FIG. 10) to each of data chunks 1014a-1014 d. Data chunks 1014a-1014d may be sorted into a single group of all data chunks that is new and unique to chunk container 1006. As such, data chunks 1014a-1014d may be stored in chunk container 1006 in a contiguous arrangement and in the same order as in data stream 1002 a. For example, data chunks 1014a-1014d may be the first four data chunks stored in chunk container 1006, or if one or more data chunks are already stored in chunk container 1006, data chunks 1014a-1014d may be stored in chunk container 1006 immediately following these already stored data chunks. Each of data chunks 1014a-1014d is assigned the same locality indicator value in stream map 1004a that was selected for first data stream 1002 a.

Second data stream 1002b includes four data chunks 1014b, 1014c, 1014e, and 1014 f. Stream map 1004b may be generated for second data stream 1002 b. Data chunks 1014b, 1014c, 1014e, and 1014f may be categorized in two groups of data chunks according to step 704 of flowchart 700: a first group comprising chunks 1014b and 1014c, chunks 1014b and 1014c already having copies residing in chunk container 1006 (due to the sequence of chunks of first data stream 1002 a); and a second group comprising chunks 1014e and 1014f, chunks 1014e and 1014f being new, unique data chunks (which do not have copies already stored in chunk container 1006). Since data chunks 1014b and 1014c are already stored in chunk container 1006, stream map 1004b includes pointers (values of data chunk identifier 404) to data chunks 1014b and 1014c already stored in chunk container 1006. Thus, data chunks 1014b and 1014c may be stored as pointers to existing data chunks in chunk container 1006 without storing chunk data for data chunks 1014b and 1014 c. As described above, data chunks 1014e and 1014f may be stored in chunk container 1006 because data chunks 1014e and 1014f are not already stored in chunk container 1006. For example, because data chunks 1014e and 1014f are new, unique data chunks to chunk container 1006, chunks 1014e and 1014f may be stored in chunk container 1006 in a contiguous arrangement, in the same order as in data stream 1002b, after the last stored data chunk currently stored in chunk container 1006 (e.g., data chunk 1014 d). Stream map 1004b includes first through fourth data chunk identifiers 1012a-1012d, which point to data chunks 1014b, 1014c, 1014e, and 1014f, respectively, stored in chunk container 1006. In stream map 1004b, data chunks 1014b and 1014c are assigned the locality indicator value associated with first data stream 1002a (according to step 906 in FIG. 9), and data chunks 1014e and 1014f are assigned the locality indicator value selected for second data stream 1002b (e.g., according to steps 902 and 904 in FIG. 9).

Note that any number of additional data streams 1002 may be stored in a similar manner as data streams 1002a and 1002 b. Further, note that in the example of fig. 10, the data chunks in the second stream map 1004b are each assigned one of two locality indicator values — either the new locality indicator value selected for the second stream map 1004b, or the locality indicator value associated with the data chunk of the first stream map 1004 a. In embodiments, a data chunk of a certain stream map may be assigned one of any number of locality indicator values, depending on the number of different locality indicators associated with data chunks already in the chunk container in that stream map. For example, as described above, a new data chunk may be assigned to a chunk container a new locality indicator value selected for a particular data stream associated with a stream map. In addition, any number of data chunks referenced by the stream map that already exist in a chunk container are given the corresponding locality indicator values of the data chunks already present in the chunk container. This may mean that any number of one or more sets of data blocks in a data stream may be assigned respective locality indicator values, such that each data block in the data stream may be given a locality indicator selected from two, three or even more different locality indicator values.

Thus, the position indicator in the stream map metadata allows the position of each data chunk in the data stream to be determined. This is because repeated data blocks tend to occur in groups. When a new data stream contains known data chunks (already stored in the chunk container), there is a reasonable likelihood of: the next data chunk in the new data stream is also a duplicate data chunk (already stored in the chunk container). Since each new, original data chunk is stored in the chunk container adjacent to each other according to the locality indicator, each already existing data chunk referenced by the new data stream is more likely to also be stored contiguously in the chunk container. This helps to improve the performance of reading and/or processing optimized data streams from the block store. For example, a rehydration module configured to reassemble a data stream based on the corresponding stream map and data chunks may perform a read-ahead on each data chunk stored in the chunk container in the hope of finding the next data chunk needed in the read-ahead buffer. In addition, chunk store maintenance tasks such as defragmentation and compaction may perform their tasks while attempting to maintain the original location by holding existing adjacent chunks together as they move around in the chunk container.

For example, after data streams are optimized and stored in chunk store 300 in the form of stream maps 310 and data chunks 322, these data streams may be read from chunk store 300. FIG. 11 illustrates a block diagram of a block storage interface 116 that includes a rehydration module 1102, according to an example embodiment. Rehydration module 1102 is configured to reassemble the requested data stream (e.g., the requested data stream according to data stream request 120 shown in fig. 1). For example, for a data stream to be read from chunk store 300 in response to data stream request 120 (FIG. 1), rehydration module 1102 determines and receives stream map 310 referenced (e.g., at a reparse location) by the optimized file of data stream request 120 from chunk store 300. For example, rehydration module 1102 may provide the stream map identifier for request 120 to chunk store 300 in FIG. 3. Chunk store 300 retrieves a corresponding stream map 310 based on the stream map identifiers (e.g., container identifier and chunk offset value if container generation values match, container identifier, local identifier, and redirection table if container generation values do not match), and rehydration module 1102 may regenerate or "rehydrate" the data stream according to the retrieved stream map 310. Note that the stream map may be identified in other ways, such as by using a separate index that translates the stream map identifier of the stream map to the exact location of the stream map on disk. Retrieved stream map 310 includes a pointer (data chunk identifier 404 in FIG. 4) to each of the data chunks included in the data stream in chunk container 304. The rehydration module 1102 uses the pointers to retrieve each of the data chunks 322. Rehydration module 1102 may arrange the retrieved data chunks 322 in a suitable order using data stream offsets 402 included in the retrieved stream map 310 (e.g., plus data chunk length information that may be included in the retrieved stream map 310) to regenerate the data stream output by rehydration module 1102 as data stream 1104.

Through the use of location indicator 406, a sequential read of data chunks 322 from chunk container 304 may be performed. For example, when a file stream is being accessed in chunk store 300 by rehydration module 1102 using sequential I/O (input/output) requests or any I/O request that includes more than one data chunk boundary, fast access to the data chunks is allowed due to the sequential storage of the data chunks according to their original data stream order. This is because when chunk store 300 creates stream map 310, new data chunks are stored in chunk container 304 in an optimized manner so that the data chunks may be quickly read at a later time. For example, data chunks may be stored sequentially in associated containers that may be processed in parallel (for data chunk insertion and/or for data chunk reading). Thus, during sequential data accesses by rehydration module 1102, data chunks belonging to the same data stream may be stored contiguously, which may be accessed and read with a single data access "seek" (e.g., moving forward or backward through the chunk container to find the next stored data chunk to read), and fragmentation is reduced to non-unique data chunks (data chunks referenced by the stream map that already exist in the chunk container prior to storing the corresponding data stream). Data access lookups during sequential data accesses are limited to situations where a data block or series of blocks of a certain data stream are found to already exist in the block store. Stream map 310 provides an efficient metadata representation for optimized file metadata (e.g., metadata 314) that may be needed by other modules in the data deduplication system (e.g., a list of hash values used by the file replication module). Stream map 310 is concise and can be cached in memory for fast access. Chunk store 300 or a higher level data access layer may cache frequently accessed stream maps 310 (of optimized data streams frequently requested and rehydrated by rehydration module 1102) based on an LRU (least recently used) algorithm or other type of caching algorithm.

C. Example chunk store embodiments that allow reliable positioning of data chunks and stream maps

As described above, data chunks may be moved in chunk containers for various reasons, such as due to compression techniques that perform garbage collection, or potentially for other reasons. Various embodiments for tracking movement of data chunks in chunk containers are described in this section.

FIG. 12 shows a block diagram of chunk container 304, according to an example embodiment. As shown in FIG. 12, chunk container 304 is substantially similar to chunk container 304 in FIG. 3, but also includes, in file header 318, chunk container identifier 1202 and chunk container generation indication 1204. Chunk container identifier 1202 is a unique identifier (e.g., an identification number) assigned to chunk container 304 to distinguish chunk container 304 from other chunk containers that may be present in chunk store 300. Chunk container generation indication 1204 indicates a revision or generation of chunk container 304. For example, generation indication 1204 may be modified (e.g., may be increased from a starting generation level, such as 0 or other starting value, to a next generation level) each time one or more data chunks 322 are moved in chunk container 304.

In an embodiment, chunk container 304 may be identified by a combination of chunk container identifier 1202 and chunk container generation indication 1204 (e.g., may form a file name of chunk container 304). In another embodiment, chunk container 304 may be identified by a unique identifier assigned to chunk container 304, which may be mapped (e.g., using an indexing structure such as a hash table) to a particular physical data stream (e.g., a file, etc.) and a location (e.g., an offset) with respect to the data stream. In an embodiment, both chunk container identifier 1202 and chunk container generation indication 1204 may be integers. Chunk container 304 may have a fixed size (i.e., a fixed number of entries), or may have a variable size. For example, in one example embodiment, the size of each chunk container file defining chunk container 304 may be set to store approximately 16000 chunks, and the average data chunk size is 64KB, with the size of the chunk container file set to 1 GB. In other embodiments, the chunk container file may have an alternate size.

Data chunks 322 stored in chunk container 304 may be referenced in various ways based on data chunk identifier 404 of metadata 400 (FIG. 4). For example, a data chunk may have a unique identifier that may be mapped (e.g., by container identifier or offset within a container) to a specific location within a particular container using an indexing structure (e.g., a hash table or similar structure). In another example, fig. 13 shows a block diagram of a data chunk identifier 1300, according to an example embodiment. In various embodiments, stream map 310 may store data chunk identifier 1300 as data chunk identifier 404 in metadata 314. As shown in FIG. 13, data chunk identifier 1300 includes a data chunk container identifier 1302, a local identifier 1304, a chunk container generation value 1306, and a chunk offset value 1308. Chunk container identifier 1302 has the value of chunk container identifier 1202 for chunk container 304 in which data chunk 322 is stored. Local identifier 1304 is an identifier (e.g., a numerical value) assigned to data chunk 322 that is unique to the assigned data chunk 322 in chunk container 304 in which data chunk 322 is stored (e.g., is a unique, per-container identifier for the data chunk). Chunk container generation value 1306 has the value of chunk container generation indication 1204 for the chunk container 304 in which data chunk 322 is stored at the time data chunk 322 is stored in chunk container 304. Note that the value of local identifier 1304 assigned to data chunk 322 is unique to data chunk 322 throughout the history of chunk container 304 (e.g., across all generations), and is immutable. Chunk offset value 1308 is the offset of data chunk 322 in chunk container 304 at the time data chunk 322 is added to chunk container 304.

Thus, according to the embodiment in FIG. 13, data chunks 322 may be referenced by stream map 310 by data chunk identifier 1300, data chunk identifier 1300 including chunk offset value 1308 indicating the offset of data chunks 322 in chunk container 304 as they are stored. However, if data chunk 322 is subsequently moved in chunk container 304 (i.e., the offset of data chunk 322 in chunk container 304 changes), then existing data chunk identifier 1300 for data chunk 322 used in stream map 310 may have an incorrect value for chunk offset value 1308.

This concept is illustrated in fig. 14. FIG. 14 shows the example of FIG. 10 where a data stream is stored in a data store, and also illustrates the effect of removing a data block from the data store, according to an embodiment. As shown in FIG. 14, similar to FIG. 10, second data stream 1002b has a corresponding stream map 1004b (e.g., stored in stream container 302, not shown in FIG. 14) and has data chunks 1014b, 1014c, 1014e, and 1014f stored in chunk container 1006. In contrast to FIG. 10, however, first data stream 1002a has been removed from the chunk store. Thus, the first stream map 1004a no longer exists. In addition, data chunks 1014a and 1014b, which in this example were referenced only by stream map 1004a, are removed from chunk container 1006 (e.g., by a garbage collection technique). Moreover, since data chunks 1014a and 1014d are no longer present in chunk container 1006, leaving unused space/storage gaps, the compression algorithm has moved 1014b, 1014c, 1014e, and 1014f in chunk container 1006 to reclaim the unused space. As shown in FIG. 14, in chunk container 304, data chunk 1014b has been transferred to a first offset location in chunk container 1006 (the location that data chunk 1014a was in before), data chunk 1014c has been transferred to another offset location that is adjacent to after data chunk 1014b, data chunk 1014e has been transferred to another offset location that is adjacent to after data chunk 1014c, and data chunk 1014f has been transferred to another offset location that is adjacent to after data chunk 1014 e. In this manner, the storage space in chunk container 304 previously filled by data chunks 1014a and 1014d may be reclaimed.

However, because data chunks 1014b, 1014c, 1014e, and 1014f have moved within chunk container 1006, data chunk identifiers 1012a-1012d in stream map 1004b no longer point to data chunks 1014b, 1014c, 1014e, and 1014f (e.g., the arrows representing pointers 1012a-1012d are shown as pointing to previous locations of data chunks 1014b, 1014c, 1014e, and 1014 f). If stream map 1004b is used in an attempt to rehydrate data stream 1002b, the attempt will fail because data chunks 1014b, 1014c, 1014e, and 1014f are not retrievable in their previous locations. Accordingly, it is desirable to have techniques for locating data chunks 1014b, 1014c, 1014e, and 1014f at their new offsets.

In an embodiment, the chunk store may implement a reliable chunk locator that may be used to track the moved data chunks. In contrast to conventional techniques, the reliable chunk locator does not use a global index for mapping data chunk identifiers to physical chunk locations. Conventional techniques use a global index that maps chunk identifiers to chunk data physical locations. The size of the storage system (e.g., 100 times terabytes or more) and the average chunk size (e.g., 64KB) make this global index very large. If this global index is loaded in its entirety into memory, it will consume a large amount of available memory and processor resources. If the index is not loaded into memory, data access will become slow because portions of the index need to be paged continuously into memory. Embodiments described herein do not use such a global index, and thus system resources are reserved.

In an embodiment, a reliable chunk locator is implemented in the form of a redirection table, such as redirection table 320 of chunk container 304 in FIG. 3. The redirection table may be stored in chunk container 304 or separately. The redirection table described below refers to a single container, but in another embodiment, the redirection table may serve multiple containers. Redirection table may store one or more entries for data chunks 322 that have been moved in chunk container 304. Each entry identifies a moved data chunk 322 and has a data chunk offset value that indicates the location of the data chunk 322 at its new location in chunk container 304. The redirection table may be referenced during rehydration of the data stream to locate any data chunks in the data stream that have moved.

For example, FIG. 15 shows a block diagram of a redirection table 1500, according to an example embodiment. If data chunks 322 are moved in chunk container 304, redirection table 1500 is used to locate data chunks 322 (including the stream maps stored as data chunks). For example, redirection table 1500 allows data chunks to be moved in chunk container 304 for space reclamation as part of the garbage collection and compaction process, and yet reliably located based on the original chunk identifier of data chunk 322. As shown in fig. 15, redirection table 1500 includes a plurality of entries 1502, such as a first entry 1502a and a second entry 1502 b. Any number of entries 1502 may be included in redirection table 1500, including hundreds, thousands, and even greater numbers of entries 1502. Each entry 1502 includes a local identifier 1504 and a changed chunk offset value 1506. For example, first entry 1502a includes a first local identifier 1504a and a first changed chunk offset value 1506a, and second entry 1502b includes a second local identifier 1504b and a second changed chunk offset value 1506 b.

Local identifier 1504 is a unique local identifier (local identifier 1304 in FIG. 13) assigned to data chunk 322 when data chunk 322 is initially stored in chunk container 304. Changed chunk offset value 1506 is a new chunk offset value for the data chunk 322 that was moved with the corresponding local identifier 1504. Thus, redirection table 1500 may be accessed using the local identifier of the data chunk to determine a changed chunk offset value for the data chunk.

For example, local identifier 1504a in FIG. 15 may be the local identifier assigned to data chunk 1014b in FIG. 14. Entry 1502a in redirection table 1500 may be accessed using the local identifier assigned to data chunk 1014b to determine a changed chunk offset value 1506a, which changed chunk offset value 1506a indicates the new location of data chunk 1014b in chunk container 304.

Note that redirection table 1500 may have any size. For example, in one embodiment, the size of redirection table 1500 is bounded by (a predetermined maximum number of data blocks-a predetermined minimum number of data blocks deleted due to compression) × (the size of the redirection table entry). In some cases, relocation of data blocks may occur infrequently. In an embodiment, after determining the changed chunk offset value for a data chunk, any pointers in the stream map that point to the data chunk from the stream map may be modified to the changed chunk offset value, and entry 1502 may be removed from redirection table 1500. In some cases, redirection table 1500 may not have entry 1502 over time in this manner.

Entries may be added to the redirection table in various ways. For example, FIG. 16 shows a flow chart 1600 for storing a data stream, according to an example embodiment. Flowchart 1600 is described as follows with reference to fig. 17. FIG. 17 shows a block diagram of a data chunk redirection system 1700, according to an example embodiment. As shown in FIG. 17, data chunk redirection system 1700 includes a redirection table modifier 1702 and a generation incrementer 1704. For example, in an embodiment, data chunk redirection system 1700 may be implemented in chunk store interface 116 in FIG. 1. Further structural and operational embodiments will be apparent to those skilled in the relevant arts based on the discussion of flowchart 1600. Flowchart 1600 is described as follows.

Flowchart 1600 begins with step 1602. At step 1602, the contents of the chunk container are modified. For example, in one embodiment, one or more data chunks 322 in chunk container 304 of FIG. 12 may be moved. These data chunks 322 may be moved by a maintenance task (e.g., maintenance module 106 in FIG. 1), such as a defragmentation process following garbage collection, a compaction process, or other process.

In step 1604, one or more entries are added to the redirection table, the one or more entries indicating chunk offset values for one or more data chunks in the chunk container that changed as a result of step 1602. For example, as shown in FIG. 17, redirection table modifier 1702 receives a moved data chunk indication 1706 that indicates one or more data chunks 322 that were moved in chunk container 304 of FIG. 12 in accordance with the maintenance task of step 1602. Moved data block indication 1706 may be received from performing the maintenance task of step 1602, and moved data block indication 1706 may indicate: a chunk container identifier for chunk container 304, each moved data chunk (e.g., via local identifier 1304), and an offset of the moved data chunk in chunk container 304. Redirection table modifier 1702 is configured to add one or more entries 1502 to redirection table 1500 that correspond to one or more moved data chunks 322 indicated in moved data chunk indication 1706. For example, for each moved data chunk 322, redirection table modifier 1702 generates an entry 1502, which entry 1502 indicates the local identifier value for that moved data chunk 322 as local identifier 1504 and the new offset value for that moved data chunk 322 as changed chunk offset value 1506.

At step 1606, the generation indication in the chunk container header is incremented due to step 1602. For example, as shown in FIG. 17, generation incrementer 1704 receives a moved data chunk indication 1706 that indicates that the data chunk has been moved in chunk container 304 of FIG. 12, as identified by the chunk container identifier received in moved data chunk indication 1706. Therefore, generation incrementer 1704 modifies chunk container generation indication 1204 of chunk container 304. For example, in an embodiment, chunk container generation indication 1204 may have an initial value of 0, and each time data chunk 322 is moved in chunk container 304, chunk container generation indication 1204 may be incremented to indicate a higher generation value. In other embodiments, chunk container generation indication 1204 may be modified in other ways.

Thus, when data chunk identifier (data chunk identifier 1300 in FIG. 13) stored in reference stream map 310 is used to find data chunk 322 in chunk container 304 of FIG. 12, chunk container generation indication 1204 of chunk container 304 may be checked to see if the current generation of chunk container 304 is the same as chunk container generation value 1306 in data chunk identifier 1300. If they are the same, data chunk 322 may be positioned at the offset indicated by chunk offset value 1308 in data chunk identifier 1300. If not, redirection table 1500 is read to determine the changed offset value for data chunk 322 in chunk container 304.

For example, FIG. 18 shows a flow diagram 1800 for locating data chunks in chunk containers, according to an example embodiment. For example, flowchart 1800 may be performed by rehydration module 1102 in FIG. 11 when rehydrating a data stream from a stream map. Flowchart 1800 is described as follows with reference to fig. 19. FIG. 19 illustrates a block diagram of a rehydration module 1930 communicating with a stream container 302 and a chunk container 304 to rehydrate a data stream in accordance with a data stream request 1910, according to an example embodiment. As shown in FIG. 19, rehydration module 1930 includes data stream assembler 1902, generation checker 1906, and data chunk retriever 1908. Further structural and operational embodiments will be apparent to those skilled in the relevant arts based on the discussion of flowchart 1800. Flowchart 1800 and fig. 19 are described as follows.

In FIG. 19, data stream assembler 1902 receives data stream request 1910, which data stream request 1910 indicates a stream map corresponding to a data stream to be rehydrated, such as stream map 1904 stored in stream container 302. Data stream assembler 1902 processes stream map 1904 to generate data chunk request 1912 for each data chunk referenced by stream map 1904.

Flowchart 1800 begins with step 1802. In step 1802, a request for a data chunk is received, the request including an identifier for the data chunk, the data chunk identifier including a chunk container identifier, a local identifier, a chunk container generation value, and a first chunk offset value. For example, in an embodiment, data chunk request 1912 generated by data stream assembler 1902 may include data chunk identifier 1300 of FIG. 13 to identify requested data chunk 322. As shown in FIG. 13, data chunk identifier 1300 may include chunk container identifier 1302, local identifier 1304, chunk container generation value 1306, and chunk offset value 1308 for the requested data chunk 322. A chunk container having chunk container identifier 1202 matching chunk container identifier 1302 in data chunk identifier 1300 is located. For example, the located chunk container may be chunk container 304 in FIG. 3. The located chunk container is accessed as follows to retrieve the requested data chunk. Operation proceeds to step 1804.

At step 1804, a determination is made whether the generation indication of the chunk container that matches the chunk container identifier matches the chunk container generation value. For example, as shown in FIG. 19, generation checker 1906 receives data chunk request 1912 for the requested data chunk. Generation checker 1906 accesses chunk container 304 (identified above as having chunk container identifier 1202 that matches chunk container identifier 1302 of requested data chunk 322). Generation checker 1906 is configured to compare chunk container generation indication 1204 of chunk container 304 with chunk container generation value 1306 of requested data chunk 322, and to output generation match indication 1914. If their values do not match (e.g., the value of chunk container generation indication 1204 is greater than the value of chunk container generation value 1306 for requested data chunk 322), generation match indication 1914 indicates that a match was not found, and the operation proceeds to step 1806. If their values do match, the generation match indication 1914 indicates that a match was found, and operation proceeds to step 1810, where the standard I/O path (or other path) for retrieving the requested data block may be followed in step 1810.

At step 1806, a redirection table associated with the chunk container is searched for an entry that includes a match to the local identifier, the entry including a second chunk offset value that is different from the first chunk offset value. For example, as shown in FIG. 19, data chunk retriever 1908 receives generation match indication 1914 and data chunk request 1912. If a generation match indication 1914 indicates that no match was found in step 1804, data chunk retriever 1908 accesses redirection table 1500 for changed chunk offset value 1506 in entry 1502 having local identifier 1504 matching local identifier 1304 of the requested data chunk 322 (FIG. 15). As shown in fig. 19, data chunk retriever 1908 receives a second chunk offset value 1916 that is different from the first chunk offset value of chunk offset value 1308. Operation proceeds to step 1808.

In step 1808, the data chunk at the second chunk offset value is retrieved from the chunk container. For example, as shown in FIG. 19, data chunk retriever 1908 accesses chunk container 304 to obtain data chunk 322z located at second chunk offset value 1916. Data chunk 322z is the requested data chunk 322 that has been moved in chunk container 304 from chunk offset value 1308 to second chunk offset value 1916.

As shown in FIG. 19, data chunk retriever 1908 outputs data chunk 1918, which in the present example is data chunk 322 z. Data chunk 1918 is received by data stream assembler 1902. In this manner, data stream assembler 1902 receives all data chunks 322 referenced by stream map 1904 from data chunk retriever 1908, either retrieved directly from chunk container 304 according to corresponding chunk offset value 1308, or retrieved from chunk container 304 as redirected by redirection table 1500. As shown in FIG. 19, data stream assembler 1902 generates data stream 1920, which data stream 1920 is a rehydrated version of the requested data stream indicated in data stream request 1910. As described elsewhere herein, data stream assembler 1902 assembles all received data chunks 322 together to form data stream 1920.

Note that the stream map reference identifier residing in the reparse point of the data stream (e.g., stream link 1008a or 1008b in FIG. 10) may have the same structure as data chunk identifier 1300 in FIG. 13. As described above, stream map 310 may have the form of data chunks 322 that contain stream map metadata and not end user file data. Thus, the process of addressing stream map 310 may be the same as addressing data chunks 322 — both techniques may use a data chunk identifier 1300 structure. The optimized data stream references stream map 310 by placing data chunk identifier 1300 of stream map 310 at the file reparse point (attached to the actual data stream/file object). The flow map identifier contains [ container identifier, local identifier, generation value, offset value ] information that may be used to locate (directly or through a redirection table) the flow map 310 data chunk inside the flow container 302. Thus, in an embodiment, the format and layout of stream container 302 may be substantially the same as the format and layout of chunk container 304.

D. Example garbage Collection embodiment

When the optimized data stream is deleted and its corresponding data chunks are no longer referenced, the storage space in the chunk store filled by the unused data chunks may be reclaimed. In this section, embodiments are described for performing "garbage collection" and compaction, where the storage space filled by deleted data chunks is reclaimed. Embodiments may execute relatively quickly and may scale proportionally to the amount of optimized data present. Furthermore, these embodiments are very efficient in terms of machine resource consumption (memory, disk I/O).

Many currently used data optimization schemes use reference counts (or reference lists or reference tables) to detect obsolete data blocks that fill storage space that can be reclaimed. According to these aspects, a reference count is maintained for each data block that counts the number of stored data streams that reference the corresponding data block. If the reference count reaches 0, the data block is no longer used and the storage space may be reclaimed. However, maintaining a reference count (or reference list or reference table) for a data block is inefficient in terms of machine resources. This is because: the reference count is updated each time a non-unique data block is received as part of a new data stream to be stored, and each time a data block is deleted (e.g., each time a data stream involving the data block is deleted). In embodiments, no reference count (or reference list or reference table) is maintained for the data block, thereby reserving machine resources relative to currently used schemes. According to embodiments, when an optimized data stream (e.g., a file stored in a deduplicated manner) is deleted, a chunk store may mark/indicate metadata chunks corresponding to the stream map of the data stream as deleted without immediately interacting with the data chunks. The data block may then be garbage collected and the space filled by the data block may be compacted, as described in various embodiments below.

In an embodiment, garbage collection may be performed by identifying and marking obsolete data blocks and then compacting, where the container is compacted to delete the identified obsolete data blocks and reclaim the storage space. For example, FIG. 20 shows a flowchart 2000 for performing garbage collection of one or more chunk containers, according to an example embodiment. In one embodiment, flowchart 2000 may be performed by block store interface 116 of FIG. 1. Further structural and operational embodiments will be apparent to those skilled in the relevant arts based on the discussion of flowchart 2000. Flowchart 2000 is described as follows.

In step 2002 of flowchart 2000, unused data chunks stored in one or more chunk containers are identified based on stream map chunk references that are only indicated as deleted. For example, referring to FIG. 1, chunk store interface 116 may receive a request to delete a data stream stored in chunk store 118. Each time such a request is received, chunk store interface 116 may indicate the data stream as deleted by providing a deleted indication in the stream map stored in data store 118 corresponding to the deleted data stream. For example, referring to fig. 3, first stream map 310a and second stream map 310b may be stored in stream container 302 in the form of stream map data chunks ("stream map chunks"). If a data stream corresponding to the second stream map 310b is requested to be deleted from chunk store 300 (e.g., as indicated by the stream map identifier/locator of the second stream map 310b in the delete request), chunk store interface 116 may include a delete indication in metadata 314b for the stream map chunks of the second stream map 310 b. Thus, each stream map chunk in stream container 302 that includes a deletion indication corresponds to a data stream that has been requested to be deleted.

In accordance with stored metadata 400 (FIG. 4), metadata 314 for each stream map chunk/stream map 310 in stream container 302 references one or more data chunks 322 in chunk container 304. The referenced data chunk 322 is a data chunk included in the corresponding data stream. As such, chunk store interface 116 may identify data chunks referenced by stream map chunks indicated as deleted by analyzing metadata 400. For data chunks referenced only by stream map chunk/stream map 310 that are indicated as deleted, chunk store interface 116 may identify the data chunk as unused.

In step 2004, an indication is provided to the data chunks identified as deleted. For example, data chunks 322 in chunk container 304 identified as unused in step 2002 may be indicated by chunk store interface 116. Chunk store interface 116 may provide a delete indication in chunk header 324 or elsewhere in data chunk 322 identified for deletion. Alternatively, chunk store interface 116 may generate a deletion log or other data structure that lists the data chunks 322 identified for deletion (e.g., by data chunk identifiers and/or other information).

In step 2006, the storage space in the chunk container filled with the data chunks indicated as deleted is reclaimed. For example, chunk store interface 116 may reclaim the storage space in chunk container 304 previously filled by data chunk 322 indicated in step 2004. Chunk store interface 116 may reclaim the storage space in various ways, including generating a new chunk container and copying data chunks 322 that are not indicated as deleted from chunk container 304 into the new chunk container. The storage space may be reclaimed in the new chunk container by sequentially appending non-deleted data chunks 322 in the new chunk container. The new chunk container may then be used in place of chunk container 304.

Fig. 21 and 22 show a flowchart for performing flowchart 2000, according to an example embodiment. For example, FIG. 21 shows a flowchart 2100 for identifying and indicating data chunks for deletion (e.g., steps 2002 and 2004 of flowchart 2000), according to an example embodiment. Further, FIG. 22 shows a flowchart for reclaiming storage space filled with data chunks indicated for deletion, according to an example embodiment. For example, flowcharts 2100 and 2200 may be performed by block storage interface 116. Flowcharts 2100 and 2200 are described below with reference to FIG. 23. FIG. 23 illustrates a block diagram of a garbage collection module 2302 that communicates with the stream container 302 and chunk container 304 to reclaim storage space filled by deleted data chunks, according to an example embodiment. As shown in FIG. 23, garbage collection module 2302 includes a stream map chunk scanner 2304, a deleted data chunk indicator 2306, and a storage space reclaimer 2308. Further structural and operational embodiments will be apparent to persons skilled in the relevant arts based on a discussion of flowcharts 2100 and 2200. Flowchart 2100 is described as follows, followed by a description of flowchart 2200.

Flowchart 2100 begins with step 2102. In step 2102, a plurality of stream map chunks are scanned to determine any stream map chunks not indicated as deleted. For example, as shown in fig. 23, the stream map chunk scanner 2304 may receive a garbage collection start signal 2328, the start signal 2328 indicating that garbage collection is to be performed by the garbage collection module 2302. Signal 2328 may be generated periodically, when storage space of chunk container 304 is filled to a predetermined amount or percentage, by user instruction, and/or otherwise. Upon being initiated by signal 2328, stream map chunk scanner 2304 scans stream map chunks 2324 (e.g., stream maps 310a-310n shown in FIG. 3) to determine any of stream map chunks 2324 that are not indicated as deleted. For example, stream map chunk scanner 2304 may perform a sequential scan of stream map chunks 2324 in each stream container 302. As described above, metadata 314 of stream map chunks 2324 may store a deletion indication when their respective data streams have been requested to be deleted. In another embodiment, stream map chunk scanner 2304 may scan one or more previously generated delete logs (e.g., as described below) that indicate deleted stream map chunks of stream container 302 to determine stream map chunks 2324 that are not indicated as deleted. Thus, according to these embodiments, stream map chunk scanner 2304 may determine any of stream map chunks 2324 that do not include a deletion indication. The determined stream map chunk may be identified by a stream map identifier (data chunk identifier of the stream map chunk).

In step 2104, the data chunk identifiers referenced by each stream map chunk indicated as undeleted are included in a Bloom filter. As described above in step 2104, stream map chunk scanner 2304 identifies one or more of stream map chunks 2324 that are not indicated as deleted. Stream map chunk scanner 2304 may analyze each of stream map chunks 2324 identified in step 2104 to determine a corresponding referenced data chunk (e.g., by a data chunk identifier). In an embodiment, stream map chunk scanner 2304 may use a data structure, such as a bloom filter, to track the data chunks referenced by identified stream map chunks 2324. As shown in FIG. 23, stream map tile scanner 2304 may include a bloom filter generator 2314. Bloom filter generator 2314 is configured to generate bloom filter 2310, bloom filter 2310 including data chunk identifiers referenced by stream map chunks indicated as not deleted. Although the use of a bloom filter is described herein, in alternative embodiments, other data structures (e.g., hash tables or similar structures/techniques) may be used in place of a bloom filter to determine deleted flow mappings.

Bloom filters are data structures well known to those skilled in the relevant art. A bloom filter is a compact set that can be used by program code to reliably determine whether an entry is not a member of a set. The bloom filter has a false negative rate of 0 and has a certain (small) percentage of false positive rate. In an embodiment, bloom filter 2310 may be a bit array initially set to all 0's. To add an element to bloom filter 2310 (e.g., a data chunk identifier for a particular data chunk), the element is fed to a set of k hash functions to generate k array positions. Each of the k array positions is set to 1 in bloom filter 2310 to include the element in bloom filter 2310. In alternative embodiments, data structures other than bloom filters (e.g., tables, maps, arrays, etc.) may be used to track data chunks referenced by stream map chunks 2324 identified as undeleted.

In another embodiment, other associative data structures, such as hash tables, may be used instead of using bloom filter generator 2314 and bloom filter 2310. Advantages of the bloom filter are: bloom filters are more compact and more memory efficient than most alternatives. The disadvantage of bloom filters over other data structures such as hash tables is that: a bloom filter may have false positives without reclaiming all unused space.

In step 2106, the plurality of stream map chunks is scanned to determine any stream map chunks indicated as deleted. For example, stream map chunk scanner 2304 may scan stream map chunks 2324 to determine any of stream map chunks 2324 indicated as deleted. As described above, metadata 314 of stream map chunks 2324 may include a deletion indication when their respective data stream is requested to be deleted. Accordingly, stream map chunk scanner 2304 may determine any stream map chunks in stream map chunks 2324 that include a deletion indication. The determined stream map chunk may be identified by a stream map identifier (data chunk identifier of the stream map chunk). In another embodiment, stream map chunk scanner 2304 may scan one or more previously generated deletion logs (e.g., as described below) that indicate deleted stream map chunks of stream container 302 to determine stream map chunks 2324 that are indicated as deleted.

In step 2108, data chunk identifiers that are referenced by stream map chunks determined to be indicated as deleted and that are not included in the bloom filter are determined. For example, stream map chunk scanner 2304 may analyze each of stream map chunks 2324 identified in step 2106 with a deletion indication to determine the referenced data chunks. As shown in FIG. 23, stream map chunk scanner 2304 outputs an identified data chunk indication 2332 that identifies the referenced data chunk (e.g., by a data chunk identifier). As shown in FIG. 23, deleted data chunk indicator 2306 receives bloom filter 2310 and indication 2332. Deleted data chunk indicator 2306 applies the data chunk identifier received in indication 2332 to bloom filter 2310 to determine data chunk identifiers not included in bloom filter 2310. As described above, the bloom filter has no false negatives. Thus, if bloom filter 2310 returns that a particular data chunk identifier was not found therein, then this result is guaranteed to be correct. Thus, if a data chunk identifier is not found in the bloom filter that tracks all non-deleted data chunks, the data chunk identifier must be referenced only by deleted chunks and thus corresponds to an unused data chunk. In this manner, deleted data chunk indicator 2306 determines the data chunk identifiers that are referenced by stream map chunks 2324 determined to be indicated as deleted and that are not included in bloom filter 2310 to determine one or more unused data chunks (identified by data chunk identifiers).

By arranging the stream map chunks in one or more dedicated stream containers, embodiments may efficiently scan all stream map chunks, as the total size of all stream map chunks is much smaller compared to the total size of the original (non-optimized) data. The ratio is approximately the ratio of the size of the stream map entry to the average size of the data block. In an embodiment where the stream map entry size is 64 bytes and the average data block size is 64KB, the ratio of the total size of all stream map blocks to the total size of the original data is 1 to 1000. Also, most sequential I/O may be used to scan through all stream map blocks. Note that the presently described techniques for identifying unused data chunks do not assume how the data chunks are stored in the chunk store. The data chunks may be stored in data containers as described herein, or may be stored in any other data structure. Furthermore, a count/list/table of references to the data streams maintained for each data block in the block store is not necessary. Further, the data chunk identifier and stream map chunk identifier may have any value that uniquely identifies the data chunk and stream map chunk, such as the structure of the data chunk identifier 1300 shown in fig. 13, a number of auto-increments, a randomly generated globally unique id (guid), and so forth. Moreover, the presently described techniques specify that each stream map entry 400 contains a data chunk identifier. Other fields (e.g., data stream offset, locality indicator) are optional.

In step 2110, the data chunk corresponding to the data chunk identifier determined in step 2108 is indicated as deleted. As shown in fig. 23, deleted data chunk indicator 2306 outputs deleted data chunk indication 2334, deleted data chunk indication 2334 indicating data chunks determined to be unused (by data chunk indicator). In one embodiment, as shown in FIG. 23, deleted data chunk indicator 2306 may store deleted data chunk indication 2334 in a delete log 2312 of chunk container 304. Delete log 2312 stores data chunk indicators received in indication 2334 that are data chunk indicators of unused data chunks (that may have been deleted from storage). In another embodiment (not shown in FIG. 23), deleted data chunk indicator 2306 may store a deletion indication in the metadata of each data chunk identified in deleted data chunk indication 2334. Updating data chunk record metadata in place in this manner may add a reliability risk to the chunk store (e.g., if the system crashes in the middle of an update). Tracking deleted data chunks with deletion log 2312 may provide improved performance when scanning deleted data chunks during the compression stage (e.g., as described below with reference to flowchart 2200). However, any technique may be used.

Further, as shown in fig. 23, a hash index 2326 may be present. Hash index 2326 stores a plurality of entries, each mapping a data chunk identifier to a hash of its corresponding data chunk. Hash index 2326 may be referenced as needed to compare data chunks to determine if they are duplicates of each other. For example, if a newly received data chunk has a hash value that matches the hash value of a stored data chunk in chunk container 304, then the new and stored data chunks are duplicates. In an embodiment, for each data chunk indicated as deleted in deleted data chunk indication 2334, an entry may be deleted from hash index 2326 (e.g., by deleted data chunk indicator 2306). Hash index 2326 is maintained in synchronization with chunk container 304 by deleting these entries (assuming that the data chunks indicated as deleted in deleted data chunk indication 2334 were eventually deleted).

Thus, according to flowchart 2100, unused data chunks are determined and indicated as deleted. Subsequently, the storage space filled by the undeleted data chunk may be reclaimed and chunk container 304 may be compressed. For example, flowchart 2200 may be performed to reclaim the memory space. Note that reclamation according to flowchart 2200 may be performed immediately after execution of flowchart 2100 or at a later time. For example, if the number of data chunks indicated as deleted (e.g., in deletion log 2312, in data chunk metadata, etc.) is greater than a predetermined threshold (e.g., 20% or other percentage of the total chunk container size), then flowchart 2200 may be performed. If the number of data chunks indicated as deleted is below the threshold, then storage reclamation/compression of chunk container 304 may be deferred or not performed. Using such a predetermined threshold may prevent a reclamation procedure that uses system resources with a relatively small memory reclamation gain from being performed.

Note that other techniques may be used to determine unused data blocks. For example, flowchart 2100 may be modified in one or more ways. For example, in step 2102 of flowchart 2100, one or more delete logs may be scanned to determine any stream map chunks not indicated as deleted. In step 2104, the data chunk identifiers referenced by each stream map chunk indicated as undeleted may be included in a Bloom filter. Next, a deletion bitmap may be generated that indicates a number of stream map chunks for one or more stream containers 302 being processed, stream map chunks indicated as not deleted (as determined in step 2102), and any other stream map chunks in stream container 302 as deleted. The delete log may then be deleted. As an alternative to step 2106, the deletion bitmap may be scanned to determine any stream map blocks indicated as deleted. In step 2110, any data chunk identifiers referenced by stream map chunks determined to be indicated as deleted (as determined in step 2106) that are not included in the bloom filter may be indicated as deleted. One example advantage of this alternative embodiment is that: the delete bitmap is a very compact structure that can be used to describe the deleted and non-deleted states of a container, and can do so more efficiently than a delete log. Furthermore, the delete log becomes unnecessary and can be deleted earlier than in the prior art.

As shown in FIG. 22, flowchart 2200 begins with step 2202. In step 2202, each data chunk in the chunk container that is not indicated as deleted is copied to the new container file. For example, as shown in FIG. 23, storage space reclaimer 2308 includes a data chunk copier 2316 and a redirection table populator 2120. In an embodiment, data chunk copier 2316 copies each data chunk 322 in chunk container 304 that is not indicated as deleted into a new container file (for a new chunk container). For example, as shown in FIG. 23, data chunk copier 2316 may receive a deletion log 2312, where deletion log 2312 includes data chunk identifiers for data chunks indicated for deletion. Data chunk copier 2316 may copy each data chunk 322 that does not have a data chunk identifier in deletion log 2312 to a new chunk container. In another embodiment, in which data chunks 322 in chunk container 304 may store deletion indications in their metadata, data chunk copier 2316 may analyze the metadata of each data chunk 322 in chunk container 304 and may copy each data chunk 322 in its metadata that does not have a deletion indication into a new chunk container.

FIG. 24 shows a block diagram of an example of data chunks copied from chunk container 304 (e.g., the first or original chunk container) to new chunk container 2400 (e.g., as the second chunk container), according to an example embodiment. In the example of FIG. 24, data chunks 322a, 322c, 322f, and 322h are indicated for deletion (e.g., in deletion log 2312 and/or in their own metadata), and data chunks 322b, 322d, 322e, and 322g are not indicated for deletion. Although data chunks 322a, 322c, 322f, and 322h are indicated for deletion, they still exist in chunk container 304. Thus, data chunk copier 2316 is configured to generate a new container file for new chunk container 2400 and to copy data chunks 322b, 322d, 322e, and 322g that are not indicated for deletion into the new container file of new chunk container 2400. For example, data chunk copier 2316 may copy data chunks 322b, 322d, 322e, and 322g to new chunk container 2400 in that order to keep their order the same as in chunk container 304. Moreover, data chunk copier 2316 may copy data chunks 322b, 322d, 322e, and 322g to new chunk container 2400 to be positioned adjacent to each other such that there is no unused storage space between data chunks 322b, 322d, 322e, and 322g, thereby creating a compressed new chunk container 2400.

In step 2204, a redirection table of the new container file is populated to map the local identifier to a new offset in the container file for each copied data chunk. For example, in an embodiment, redirection table populator 2120 may be configured to populate a redirection table of a new chunk container similar to redirection table 1500 of FIG. 15. The redirection table of the new chunk container allows data access to the data chunks stored in the new chunk container in a manner similar to that described above with respect to redirection table 1500. Similar to FIG. 15, redirection table populator 2120 may be configured to populate a redirection table for the new chunk container to include an entry for each copied data chunk. Each entry for a data chunk may include a local identifier 1304 for the data chunk and a chunk offset value 1308 for the data chunk in the new chunk container. Further, the entry for the data chunk may include a chunk container generation value and a chunk offset value 1308 for the data chunk in chunk container 304 to map the chunk container generation value and the first offset value in chunk container 304 directly to the second offset value in the new chunk container.

For example, with respect to the example in FIG. 24, the redirection table is populated by redirection table populator 2120 with four new entries corresponding to data chunks 322b, 322d, 322e, and 322g copied to new chunk container 2400 (and possibly more entries corresponding to additional data chunks copied from chunk container 304 to new chunk container 2400). Each entry maps a local identifier for data chunk 322 to a corresponding chunk offset value in new chunk container 2400.

In this regard, optionally, new container files (e.g., new chunk container 2400), which may each reside in a cache memory, may be flushed from the cache memory and stored in storage. Examples of such memories and storages are described elsewhere herein.

Although not shown in FIG. 22, flowchart 2200 may optionally include another step in which at least one entry of the hash index is modified by replacing the data chunk identifier in the hash entry with a new data chunk identifier obtained from the merge log of the corresponding data chunk. In an embodiment, storage space reclaimer 2308 may include a hash index updater module configured to update hash index 2326 to point to the copied data chunks in the new chunk container. For example, for each copied data chunk, storage space reclaimer 2308 may scan a redirection table to obtain a new chunk identifier and chunk header for the hash value of the copied data chunk. Storage space reclaimer 2308 may look up the hash value (a data chunk hash value is typically a key in a hash index) in hash index 2326 to locate an entry or record for the copied data chunk in hash index 236. Storage space reclaimer 2308 may modify the record to point to a new data chunk location in a new chunk container by replacing an existing data chunk indicator in the record with a new data chunk indicator for the copied data chunk.

Referring back to flowchart 2300, storage space reclaimer 2308 may rename the file name of the new chunk container to the file name of chunk container 304 to replace chunk container 304 with the new chunk container. For example, in step 2206, the original file name of the chunk container is renamed to a third file name. Referring to FIG. 24, the file name of chunk container 304 may be renamed to a third (e.g., dummy or temporary) file name. In step 2208, the file name of the new container file is renamed to the original file name of the chunk container. Referring to FIG. 24, the file name of new chunk container 2400 may be renamed to the file name of chunk container 304 (the file name before renaming it in step 2206). In step 2210, the chunk container is deleted. Referring to FIG. 24, chunk container 304 renamed to the third file name may be deleted such that new chunk container 2400 replaces chunk container 304.

At this point, new chunk container 2400 that replaces chunk container 304 is compressed and any unused storage space is reclaimed. Flowcharts 2100 and 2200 may be performed as often as necessary to reclaim unused memory.

In an embodiment, it may be desirable to reduce the size of the redirection table for the new chunk container. For example, in an embodiment, redirection tables for one or more chunk containers may be loaded, and a temporary index keyed by the local identifier and the new data chunk identifier may be generated from the redirection tables. The stream maps of stream container 302 may be enumerated, and the data blocks referenced by each stream map may be enumerated. The local identifier 1304 portion of the data chunk identifier may be looked up in the temporary index. If a match is found, the data chunk references in the stream map may be updated with the new data chunk identifier.

Note that in one embodiment, the data chunk identifier may be appended (e.g., replaced) in-place to the stream map chunk in stream container 302. In another embodiment (e.g., for improved reliability), a new stream container may be generated in a manner similar to that described above for chunk containers, and a portion of flowchart 2200 may be followed (e.g., steps 2202, 2204, 2206, 2208, and 2210) to populate the new stream container with the updated stream map. In such embodiments, the stream map chunk is copied to the new stream container at the same offset as in the old stream container. Also, the generation number of the stream map block identifier does not need to be updated. The stream container file may be compressed by executing flowchart 2200.

E. Example embodiments for providing hotspot relief

In the namespace of optimized data, certain data blocks are repeated (e.g., thousands of times). In other words, certain data chunks stored in a chunk store may be referenced by thousands of data streams (e.g., files) or even larger numbers of data streams. If one of these highly referenced data chunks (also referred to herein as "hot spots") is lost (e.g., corrupted in storage), thousands of data streams may be lost, which is a reliability concern for the data storage system. Embodiments for providing data chunk redundancy for hotspot release are described in this section, where backup copies are automatically made and stored for frequently referenced data chunks ("hotspots"). As a result, if a frequently referenced data block is corrupted in the block store, the corruption may be detected and a backup copy of the data block may be used. In addition, if a backup copy is corrupted, the original copy of the data may be used to restore the backup copy. In addition, other techniques may be employed to achieve reliable storage of metadata, such as N-way replication (replicating a block of data in more than two replicas), erasure coding techniques, and so forth.

Many currently used techniques for improving storage reliability limit the number of references that can be made to a unique data block. For example, according to one technique, a count of the total number of references to each data chunk in the chunk store is maintained. When the total number of references to a data chunk exceeds a threshold, a backup copy of the data chunk is made. However, maintaining a reference count (or reference list, or reference table) for a data block is inefficient in terms of machine resources. This is because: the reference count is updated each time a non-unique data block is received as part of a new data stream to be stored, and each time a data block is deleted (e.g., each time a data stream involving the data block is deleted).

Thus, in embodiments, the most used data block (the block with the highest reference count) is identified and mirrored (creating a second copy) so that when a corruption occurs (bad memory sector, etc.), the second copy may be used when accessing the data block. In this way, exposure to corrupted data streams in the presence of corrupted data blocks may be reduced. Embodiments scale with ever increasing amounts of stored data, consume little in machine resources, and do not require maintenance of reference counts for each data block, which facilitates block storage in terms of scaling and resource utilization.

In an embodiment, providing redundant data blocks to improve storage reliability may be performed by identifying data blocks in a certain first percentage (e.g., 1%, etc.) of the most referenced data blocks and/or data blocks having a number of references greater than a threshold. The backup copies may be stored in a backup chunk container or other storage location. For example, FIG. 25 shows a flowchart 2500 for backing up data chunks in a chunk container, according to an example embodiment. In an embodiment, flowchart 2500 may be performed by block store interface 116 of FIG. 1. Other structural and operational embodiments will be apparent to those skilled in the relevant arts based on the discussion regarding flowchart 2500. Flowchart 2500 is described as follows.

In step 2502 of flowchart 2500, a data chunk is received for storage in a chunk container. For example, referring to FIG. 1, chunk store interface 116 may receive data chunks for storage in chunk containers in chunk store 118.

In step 2504, it is determined whether the received data chunk is a "hot spot" (a highly referenced data chunk) and has not been copied for backup. A hotspot data chunk may be defined as a data chunk that is included in the top predetermined percentage of the most referenced data chunks in all existing chunk containers, or has a number of references greater than a predetermined reference threshold, or both. In an embodiment, chunk store interface 116 may be configured to determine whether a received data chunk is a highly referenced data chunk that may be desired to be stored in a backup container and that is not already stored in the backup container. In an embodiment, criteria for a highly referenced data chunk that may be desired to be stored in a backup container include that the data chunk is in a top predetermined percentage of the most referenced data chunks of all existing chunk containers, and/or has a number of references greater than a predetermined reference threshold. For example, a data chunk may be determined to be highly referenced if the data chunk is classified in the top 1%, 5%, 10%, or other top percentage of the data chunks stored in all existing chunk containers in terms of being most referenced. Additionally or alternatively, a data chunk may be determined to be highly referenced if the data chunk has a number of references (by stream mapping) greater than a predetermined threshold, such as 10 references, 50 references, 100 references, or other threshold number of references.

In step 2506, if it is determined that the received data chunk is a hotspot and has not been copied for backup, a backup copy of the received data chunk is stored in a backup container. If it is determined that the received data chunk is highly referenced, the data chunk may be replicated and a copy of the data chunk may be stored in a backup storage, such as a backup chunk container. If the first, primary copy of a data block becomes lost or otherwise corrupted, a copy of the data block in backup storage may be used.

Fig. 26A and 26B illustrate a process for performing flowchart 2500, according to an example embodiment. For example, FIGS. 26A and 26B illustrate a flowchart 2600 for backing up highly referenced data chunks, according to an example embodiment. In an embodiment, flowchart 2600 may be performed by block storage interface 116. Flowchart 2600 is described as follows with reference to fig. 27. FIG. 27 illustrates a block diagram of a backup storage module 2702 that communicates with the stream container 302, chunk container 304, and backup container 2704 to backup frequently referenced data chunks, according to an example embodiment. As shown in FIG. 27, backup storage module 2702 includes a reference handling module 2706, a chunk memory module 2708, and a reconsolidation module 2710. For ease of illustration, a single chunk container 304 is shown in FIG. 27. However, in embodiments, any number of chunk containers may exist in the chunk store containing chunk container 304 of FIG. 27, and all of the existing chunk containers may be processed with chunk container 304. Also, in embodiments, any number of backup containers 2704 may be present. Also, in embodiments, any number of flow containers 302 may be present. Other structural and operational embodiments will be apparent to those skilled in the relevant arts based on the discussion regarding flowchart 2600. Flowchart 2600 is described as follows.

As shown in FIG. 26A, flowchart 2600 begins with step 2602. In step 2602, a determination is made as to whether the received data chunk is a duplicate of a data chunk stored in any chunk container. For example, as shown in FIG. 27, reference processing module 2706 receives received data chunk 2714. Data chunk 2714 is a data chunk received for storage in chunk container 304. For example, data chunk 2714 may be one data chunk of a plurality of data chunks of a data stream to be stored. Because chunk container 304 is included in a chunk store that stores data chunks in a deduplicated manner, reference processing module 2706 determines whether received data chunk 2714 is a duplicate of a data chunk 322 that is already stored in chunk container 304. For example, data chunk 2714 may be received in a storage request that indicates whether data chunk 2714 is already stored in a chunk container, and reference processing module 2706 may determine whether data chunk 2714 has duplicates stored in chunk container 304 based on the storage request. Alternatively, reference processing module 2706 may determine whether data chunk 2714 has duplicates stored in chunk container 304 by generating a hash of data chunk 2714 and comparing the generated hash to hashes stored in hash index 2326 (when hash index 2326 is present). Hash index 2326 stores the hashes of each of data chunks 322 stored in chunk container 304, and thus if the hash of data chunk 2714 matches the hash in hash index 2326, data chunk 2714 is a duplicate of the data chunk stored in chunk container 304. If data chunk 2714 is a duplicate, the operations of flow 2600 proceed to step 2604. If data chunk 2714 is not a duplicate of a data chunk stored in chunk container 304, then the operations of flow 2600 proceed to step 2610. Note that step 2602 is optional. In embodiments, step 2602 may be skipped and the operation may instead proceed to step 2604.

In step 2604, a determination is made as to whether the received data chunk has an entry in the reference count table. For example, as shown in FIG. 27, there is a reference count table 2712. Reference count table 2712 may be maintained in memory. Reference count table 2712 is configured to store entries for a portion of data chunks 322 stored in any chunk container 304 for that chunk store. The number of entries in the reference count table is at least the same as the number of hot spots in all chunk containers. The number of hot spots depends on various criteria and the raw data size. For example, if a hotspot data chunk is defined as a data chunk that is referenced 100 times or more, the maximum number of hotspots is the original data size divided by 100 and then divided by the average data chunk size. If a hotspot chunk is defined as the first 1% of the most referenced chunks, then the maximum number of hotspots is the number of unique data chunks in all chunk containers divided by 100. To reduce the number of rejoins (e.g., as described below), in one embodiment, the reference count table may be sized to be several times the estimated number of hot spots in all chunk containers. For example, if a hot chunk is defined as the first 1% of the most referenced chunks, reference count table 2712 may maintain entries for approximately 2% of the data chunks 322 of all chunk containers 304 stored for that chunk. A portion of reference count table 2712 maintains entries for a currently tracked/known top predetermined percentage (e.g., 1%) of data chunks for highly referenced data chunks 322, where each entry includes a reference count. The remainder of reference count table 2712 is used to track the exact reference count of received data chunks or the estimated reference count of some received data chunks. Thus, reference count table 2712 tracks reference counts for a portion of the total number of data chunks 322 for chunk container 304, unlike some currently used techniques that track reference counts for all stored data chunks.

In an embodiment, each entry or record of reference count table 2712 may include the following fields (in any order) for the corresponding tracked data chunk 322:

a first field: a data block identifier (e.g., data block identifier 1300 of figure 13),

a second field: a reference count (e.g., an exact count or an expected count),

a third field: an indication of whether the reference count is an exact value (e.g., true/false), an

A fourth field: an indication of whether the data block is copied (e.g., true/false).

Only the first, second and fourth fields must be present, while the third field is optional. Without the third field, all reference counts are considered to be non-exact. Note that the data chunk identifier may be any value that uniquely identifies a data chunk or stream map chunk, such as the structure of data chunk identifier 1300 shown in fig. 13, a number of auto-increments, a randomly generated globally unique id (guid), and so forth. Reference processing module 2706 may determine whether received data chunk 2714 has an entry in reference count table 2712 by comparing data chunk identifiers of data chunk 2714 (e.g., received with data chunk 2714, obtained from hash index 2326, etc.) to data chunk identifiers of entries in reference count table 2712, and if a match occurs, an entry for data chunk 2714 is present.

If received data chunk 2714 has an entry in reference count table 2712, operation proceeds from step 2604 to step 2606. If received data chunk 2714 does not have an entry in reference count table 2712, operation proceeds from step 2604 to step 2608.

In step 2606, a reference count value is incremented in an entry of the received data chunk in the reference count table. In the case of step 2606, where data chunk 2714 is a duplicate of data chunk 322 in chunk container 304 and an entry exists in reference count table 2712 for data chunk 2714, the reference count of data chunk 2714 in the entry in reference count table 2712 is incremented, or in embodiments modified in other ways than being incremented, by reference processing module 2706. For example, the reference count may be incremented by 1 to indicate that additional references to data chunk 2714 (stored in chunk container 304) were received (e.g., by a stored new data stream that includes received data chunk 2714). Operation proceeds from step 2606 in fig. 26A to step 2612 in fig. 26B.

In step 2608, an entry for the received data chunk is added to the reference count table. In the case of step 2608, where data chunk 2714 is a duplicate of data chunk 322 in chunk container 304 if step 2602 is not skipped (or may not be a duplicate of data chunk 322 in chunk container if step 2602 is skipped), and no entry exists in reference count table 2712 for data chunk 2714, a new entry is added to reference count table 2712 by reference processing module 2706 for data chunk 2714. In this case, although data chunk 2714 is a duplicate, data chunk 2714 does not have enough references to be considered a highly referenced data chunk, as evidenced by data chunk 2714 having no entry in reference count table 2712. The new entry added to data chunk 2714 of reference count table 2712 includes a data chunk identifier of data chunk 2714, a reference count value for data chunk 2714 that is the sum of the initial reference count value (e.g., reference count value 1) and the expected count value (e.g., "Ce"), an indication that the reference count value for data chunk 2714 is not an exact value, and an indication that data chunk 2714 is not replicated in backup container 2704.

If step 2602 is not skipped, expected count value Ce is an expected reference count value for a new entry of reference count table 2712 with duplicate data chunks stored in chunk container 304. Because the data chunks have duplicates already stored in chunk container 304, their exact reference count values are not known, and thus expected count value Ce is used to provide an estimated reference count value. The value of the expected count value Ce may be selected on an application-by-application basis. The upper bound for expected count value Ce may be the maximum reference count (e.g., "Cd") in the data chunks discarded from reference count table 2712. In an embodiment, the expected count value Ce may be set to 1 to avoid unnecessarily copying the data block. If step 2602 is skipped, the lower bound of Ce is 0 instead of 1. Operation proceeds from step 2608 in fig. 26A to step 2612 in fig. 26B.

In step 2610, an entry for the received data chunk is added to the reference count table. In the case of step 2610, where data chunk 2714 is not a duplicate of data chunk 322 in chunk container 304, and is therefore a new data chunk in chunk container 304, then an entry for the data chunk will not exist in reference count table 2712. Thus, an entry for data chunk 2714 may be added to reference count table 2712 by reference processing module 2706. An entry for data chunk 2714 includes a data chunk identifier for data chunk 2714, an initial reference count value (e.g., reference count value 1) for the received data chunk, an indication that the reference count value for data chunk 2714 is an exact value, and an indication that data chunk 2714 is not copied in backup container 2704. After adding a new entry for data chunk 2714, in accordance with step 2610, processing of data chunk 2714 is complete.

For example, referring to chunk container 304 and backup container 2704 shown in FIG. 27, reference count table 2712 may include example information (provided for purposes of illustration) shown in Table 1 below.

With respect to the first entry in Table 1, data chunk 2714 may have been received as a duplicate of data chunk 322b, while an entry with respect to data chunk 2714/322b may already exist in Table 1. In this case, step 2606 of flowchart 2600 may have been performed, increasing the reference count value of data block 2714/322b from 14 to 15. As shown in the entry for data block 2714/322b, the reference count value is indicated to be exact, and data block 2714/322b is indicated to have been copied in backup container 2704.

With respect to the second entry in Table 1, data chunk 2714 may have been received into chunk container 304 as a new data chunk and stored in chunk container 304 as data chunk 322 h. In this case, step 2610 of flowchart 2600 may have been performed to add an entry to table 1 for data block 2714/322 h. As shown in Table 1, the new entry for data chunk 2714/322h includes the data chunk identifier for data chunk 322h, an initial reference count value of 1, an indication that the reference count value is exact, and an indication that data chunk 2714/322h was not copied in backup container 2704.

With respect to the third entry in Table 1, data chunk 2714 may have been received as a duplicate of data chunk 322c, while an entry for data chunk 2714/322b may not already exist in Table 1. In this case, step 2608 of flowchart 2600 may have been performed, thereby adding an entry to table 1 for data block 2714/322 c. As shown in Table 1, the new entry for data chunk 2714/322c includes the data chunk identifier for data chunk 322c, the initial reference count value of 1 plus the example expected count value of 1 (and is 2), an indication that the reference count value is not exact, and an indication that data chunk 2714/322c was not copied in backup container 2704.

In step 2612, a determination is made as to whether the received data chunk is replicated in the backup container. For example, referring to FIG. 27, reference handling module 2706 may determine whether data chunk 2714 is copied in backup container 2704. Reference processing module 2706 can make the determination in a variety of ways. For example, if it is determined in step 2602 that data chunk 2714 is not a duplicate of data chunk 322 of chunk container 304, or it is determined in step 2604 that there is no entry in reference count table 2712, reference processing module 2706 may determine that data chunk 2714 is not copied in backup container 2704. If an entry for data chunk 2714 is present in reference count table 2712, reference processing module 2706 may access a field of reference count table 2712 (e.g., the fourth field) indicating whether the data chunk is copied to make this determination. If it is determined that data chunk 2714 is not copied in backup container 2704, operation proceeds from step 2612 to step 2614. If data chunk 2714 is determined to be copied in backup container 2704, then processing of data chunk 2714 is complete.

In step 2614, a determination is made whether the received data block has a reference count value that is greater than a minimum reference count value for already copied data blocks and/or whether the reference count value for the received data block is greater than a predetermined threshold. In an embodiment, if the data chunk has a reference count that is greater than the minimum reference count Cz of the data chunk currently being copied in the backup container 2704, the data chunk is considered to have a number of references that is at the top 1% or other top percentage of the respective data chunk. Thus, reference processing module 2706 may be configured to compare the reference count value (from the corresponding entry in reference count table 2712) of data chunk 2714 to the minimum reference count Cz.

In one embodiment, a predetermined threshold Y may be maintained that is a minimum threshold reference count value that a data block must exceed in order to be copied by a backup. The predetermined threshold Y may have any suitable value, such as 10 references, 20 references, or other values. Thus, in an embodiment, reference processing module 2706 may be configured to also compare the reference count value of data chunk 2714 to a predetermined threshold Y.

In an embodiment, if the reference count value of data chunk 2714 is greater than minimum reference count Cz and/or greater than a predetermined threshold Y, then operation proceeds from step 2614 to step 2616. If the reference count value of data chunk 2714 is less than minimum reference count Cz and/or less than predetermined threshold Y, then processing of data chunk 2714 is complete.

In step 2616, a backup copy of the received data chunk is stored in the backup container. For example, as shown in FIG. 27, reference processing module 2706 can generate storage instructions 2716, which storage instructions 2716 indicate that a backup copy of data chunk 2714 should be stored. As shown in FIG. 27, block memory module 2708 receives store instructions 2716. Block memory module 2708 provides an interface to storage (e.g., block container 304 and backup container 2704) for reference handling module 2706. As shown in FIG. 27, block memory module 2708 receives data block 2714. Chunk memory module 2708 stores data chunks 2714 in backup container 2704 as a result of backup copy requests included in storage instructions 2716. Operation proceeds from step 2616 to step 2618.

Note that if, in step 2602, it is determined that data chunk 2714 is a new data chunk (a duplicate of data chunk 2714 is not already stored in chunk container 304), reference processing module 2706 may generate store instructions 2716 to instruct chunk memory module 2708 to store data chunk 2714 in chunk container 304.

In step 2618, the entry of the received data chunk in the reference count table is modified to include an indication that the received data chunk is replicated in the backup container. Reference processing module 2706 may modify an entry (e.g., a fourth field) of data chunk 2714 in reference count table 2712 to indicate that data chunk 2714 is copied (copied in step 2616) in backup container 2704. Processing of data block 2714 is complete.

Flowchart 2600 may be repeated for any number of received data blocks. For example, in an embodiment, flowchart 2600 may be repeated until reference count table 2712 is filled (e.g., reaches a predetermined size). At this point and/or at other checkpoints, reference count table 2712 may be reconsolidated to reduce its size and ensure that the most highly referenced data chunks (e.g., the first 1%) have entries maintained in reference count table 2712.

For example, in one embodiment, the process illustrated in FIG. 28 may be performed. FIG. 28 shows a flow diagram 2800 providing a process for reconsolidating a reference count table, according to an example embodiment. For example, the reconsolidation module 2710 shown in fig. 27 may operate in accordance with the flowchart 2800. Flowchart 2800 is described as follows with reference to fig. 27. Other structural and operational embodiments will be apparent to those skilled in the relevant arts based on the discussion regarding flowchart 2800. Flowchart 2800 is described as follows.

As shown in fig. 28, flowchart 2800 begins with step 2802. In step 2802, it is determined whether the reference count table has reached a predetermined size. As described above, the size of the reference count table must be large enough to store an entry for each hotspot in all chunk containers. The number of hot spots depends on the standard and the original data size. To reduce the number of re-merges (as described below), embodiments may size the reference count table several times the estimated number of hot spots in all chunk containers. For example, in one embodiment, if a hotspot chunk is defined as the first 1% of the most referenced chunks, then the maximum number of hotspots is the number of data chunks in all chunk containers divided by 100 (i.e., 1% of all data chunks). Also, if reconsolidation module 2710 expects chunk stores to store 1 million data chunks in a chunk container, it may determine the size of reference count table 2712 and may compare the determined size to a predetermined threshold size (e.g., 2% of the total number of data chunks). The predetermined threshold size may be calculated as: 1 million data blocks × 0.02 equals 20000 entries. Thus, in such an example, reconsolidation module 2710 may compare the determined size (in entries) of reference count table 2712 to a predetermined threshold of 20000 entries. In another embodiment, the predetermined size may be determined in other ways.

If it is determined that reference count table 2712 has reached the predetermined size, operation proceeds from step 2802 to step 2804. If it is determined that reference count table 2712 has not reached the predetermined size, operation exits from flowchart 2800.

In step 2804, the reference count table is reintegrated to determine an exact reference count value for all entries for which the reference count is not exact. In an embodiment, reference count table 2712 may be recombined by reconsolidation module 2710 to reduce its size by removing some or all entries of data chunks that are not highly referenced. Operation proceeds from step 2804 to step 2806.

In step 2806, for data chunks that do not exist in the backup container and that have an entry in the refmerged reference count table, a backup copy of the data chunks is stored in the backup container. In an embodiment, reconsolidation module 2710 may analyze reconsolidated reference count table 2712 generated in step 2804. Merge module 2710 may store backup copies in backup container 2704 for any data chunks 322 that have an entry in refmerged reference count table 2712 that do not have a backup copy already stored in backup container 2704.

Also, although not shown in FIG. 28, reconsolidation module 2710 may mark data chunks that no longer satisfy the replication criteria for deletion (e.g., store a deletion indication in data chunk metadata, in a deletion log such as deletion log 2312 of FIG. 23, etc.) to delete the marked data chunks from backup container 2704. Also, a new value for the minimum reference count Cz of data chunks that have currently been copied in the backup container 2704 may be determined by the reconsolidation module 2710 at this point.

Note that the reconsolidation process of step 2804 of flowchart 2800 may be performed in various ways. According to this reconsolidation process, highly referenced data chunks/hotspots are intended to be included in reference count table 2712. However, the exact reference count values for some of these data chunks are unknown because reference count table 2712 does not track the reference count values for all data chunks 322. Thus, during the re-merge process, the exact reference count value is determined. Also, note that data chunks may become hot prior to re-merging, but current techniques may not detect hot data chunks until re-merging. In some embodiments, it may be desirable to copy a data chunk once it becomes a hotspot. This can be handled in various ways. In one embodiment, Ce is set to the maximum reference count of the entry removed from the reference count table in step 2804. Alternatively, if a hotspot chunk is defined as a data chunk with a number of references (by stream mapping) greater than a predetermined threshold, Ce may be set to 1, a backup copy may be created, and if the reference count reaches the predetermined threshold divided by 2, the database may be maintained in reference count table 2712 for chunks.

For example, fig. 29 shows a flow diagram 2900 providing a re-merge process, according to an example embodiment. For example, reconsolidation module 2710 shown in fig. 27 may operate in accordance with flowchart 2900 to reconsolidate reference count table 2712. Flowchart 2900 is described below with reference to fig. 27. Other structural and operational embodiments will be apparent to those skilled in the relevant arts based on the discussion regarding flowchart 2900. Flowchart 2900 is described as follows.

As shown in fig. 29, flowchart 2900 begins at step 2902. In step 2902, a second reference count table is generated that includes a subset of the entries for the data chunks in the first reference count table. For example, a second reference count table (e.g., reference count table 2712b) may be generated by reconsolidation module 2710. The second reference count table includes the same fields as reference count table 2712 and includes a subset of the entries of reference count table 2712. The subset of entries includes entries in reference count table 2712 that indicate data chunks whose reference count value is not an exact value (e.g., in a third field thereof, as described above). In embodiments, if step 2602 is skipped and the third field is omitted, the second reference count table may include all entries for the first reference count table for data chunks.

In step 2904, the reference count values for all entries in the second reference count table may be set to 0. For example, reconsolidation module 2710 may set all reference count values (e.g., the second field) of the second reference count table to 0.

In step 2906, the reference count value for each data chunk in the second reference count table is incremented each time that data chunk is referenced by a non-deleted stream map. Reconsolidation module 2710 may scan stream map chunks 2324 of all stream containers 302 of the chunk store to determine which stream maps are not deleted (e.g., stream map chunks that do not include a deletion indication, are not logged for deletion, etc.). For data chunks referenced by stream map chunks determined to be undeleted, reconsolidation module 2710 may increment their reference count value (e.g., the second field) in a second reference count table. The reference count value is incremented each time a data chunk is referenced by a stream map chunk, so that the total number of references to the data chunk by the stream map is counted. By arranging the stream map chunks in one or more dedicated stream containers, in embodiments, all stream map chunks may be efficiently scanned, as the total size of all stream map chunks is much smaller compared to the total size of the original (non-optimized) data. This ratio is approximately the ratio of the size of the stream map entry to the average size of the data blocks. In an embodiment where the stream map entry size is 64 bytes and the average data block size is 64KB, the ratio of the total size of all stream map blocks to the total size of the original data is 1 to 1000. Also, most sequential I/O may be used to scan through all stream map blocks. Note that the present example does not assume how the data blocks are stored in the block store. The data chunks may be stored in data containers as described above, or may be stored in any other data structure. A count/list/table of references to the data streams maintained for each data block in the block store need not be maintained. Further, the data chunk identifier and stream map chunk identifier may have any value that uniquely identifies the data chunk and stream map chunk, such as the data chunk identifier 1300 shown in fig. 13, a number of auto-increments, a randomly generated globally unique id (guid), and so forth. Moreover, the present technique utilizes only the data block identifier of each stream map entry 400. Other fields (e.g., data stream offset, locality indicator) are optional.

In step 2908, for each entry in the first reference count table, the reference count value in the first reference count table is replaced with the corresponding reference count value in the second reference count table. Reconsolidation module 2710 may copy the reference count value (e.g., the second field) from the second reference count table to a corresponding entry in reference count table 2712 that has replaced its reference count value.

In step 2910, in each entry in the first reference count table, the corresponding reference count value is indicated as an exact value. Reconsolidation module 2710 may provide an indication in each entry of reference count table 2712 that the reference count is an exact value (e.g., "true" may be entered in a third field of each entry).

In step 2912, an entry in the first reference count table that is not a hotspot is determined. In an embodiment, reconsolidation module 2710 may compare the reference count values (e.g., the second field) of all entries in reference count table 2712 to determine which entries have reference count values in a previous predetermined percentage (e.g., 1%) and/or have a number of references greater than a predetermined reference threshold (e.g., 100). The determined entry corresponds to a hotspot having a backup copy in the backup container 2704. For example, if any of these highly referenced data chunks do not have a backup copy in backup container 2704, then a backup copy is made in accordance with step 2806 (FIG. 28) as described above.

In step 2914, some or all of the entries in the first reference count table determined to not be hotspots may be discarded. For each data chunk that is determined not to be highly referenced, reconsolidation module 2710 may delete the entry from reference count table 2712.

As such, a backup copy of data chunk 322 that is deemed to be highly referenced is stored in backup container 2704. These backup copies may be accessed in the event that the primary copy of data chunks 322 in chunk container 304 is corrupted or otherwise lost (e.g., a particular data chunk is corrupted, data container 304 is lost or partially or fully corrupted, etc.). For example, in an embodiment, chunk store may maintain a checksum for all data chunks in the data chunk metadata stored in the corresponding stream map chunk 2324. When a request for a data block is received and the data block is accessed in block store 118 through block store interface 116 of FIG. 1, block store interface 116 may calculate a checksum for the requested data block based on the version of the data block accessed in block container 304. If the calculated checksum does not match the stored checksum for the requested data chunk (e.g., stored in data chunk metadata), then a corruption of the data chunk in chunk container 304 is detected. If the corrupted data block has a backup copy in backup container 2704, block storage interface 116 may access the backup copy in backup container 2704 and return the backup copy in response to the request. In addition, chunk store interface 116 may replace the corrupted data chunks in chunk container 304 with a backup copy of the requested data chunks stored in backup container 2704.

Example computing device embodiments

Data deduplication module 104, maintenance module 106, data stream API110, chunk maintenance API 112, data access API 114, chunk store interface 116, data stream parser 602, data chunk store manager 604, metadata generator 606, stream map generator 608, metadata collector 802, locality indicator generator 804, rehydration module 1102, redirection table modifier 1702, generation incrementer 1704, data stream assembler 1902, generation checker 1906, data chunk retriever 1908, garbage collector module 2302, stream map chunk scanner 2304, deleted data chunk indicator 2306, storage space reclaimer 2308, bloom filter generator 2314, data chunk copier 2316, merge log generator 2318, redirection table populator 2320, backup storage module 2702, reference handling module 2706, chunk memory module 2708, and reconsolidation module 2710 may be implemented in hardware, software, firmware, or firmware, Firmware, or any combination thereof. For example, data deduplication module 104, maintenance module 106, data stream API110, chunk maintenance API 112, data access API 114, chunk store interface 116, data stream parser 602, data chunk store manager 604, metadata generator 606, stream map generator 608, metadata collector 802, locality indicator generator 804, rehydration module 1102, redirection table modifier 1702, generation incrementer 1704, data stream assembler 1902, generation checker 1906, data chunk retriever 1908, garbage collector module 2302, stream map chunk scanner 2304, deleted data chunk indicator 2306, storage space reclaimer 2308, bloom filter generator 2314, data chunk copier 2316, merge log generator 2318, redirection table populator 2320, backup storage module 2702, reference processing module 2706, chunk memory module 2708, and/or reconsolidation module 2710 may be implemented as computer program code configured to be executed in one or more processors. Alternatively, data deduplication module 104, maintenance module 106, data stream API110, chunk maintenance API 112, data access API 114, chunk store interface 116, data stream parser 602, data chunk store manager 604, metadata generator 606, stream map generator 608, metadata collector 802, locality indicator generator 804, rehydration module 1102, redirection table modifier 1702, generation incrementer 1704, data stream assembler 1902, generation checker 1906, data chunk retriever 1908, garbage collector module 2302, stream map chunk scanner 2304, deleted data chunk indicator 2306, storage space reclaimer 2308, bloom filter generator 2314, data chunk copier 2316, merge log generator 2318, redirection table populator 2320, backup storage module 2702, reference processing module 2706, chunk memory module 2708, and/or reconsolidation module 2710 may be implemented as hardware logic/circuitry.

FIG. 30 depicts an exemplary implementation of a computer 3000 in which embodiments of the present invention may be implemented. For example, storage system 102 and/or any portion thereof may be implemented in one or more computer systems similar to computer 3000, including one or more features of computer 3000 and/or various additional features. Computer 3000 may be a general-purpose computing device in the form of a conventional personal computer, a mobile computer, or a workstation, for example, or computer 3000 may be a special purpose computing device. The description of computer 3000 provided herein is provided for purposes of illustration, and is not intended to be limiting. As will be appreciated by one skilled in the relevant art, embodiments of the invention may be implemented in other types of computer systems.

As shown in fig. 30, computer 3000 includes a processing unit 3002, a system memory 3004, and a bus 3006 that couples various system components including system memory 3004 to processing unit 3002. The system bus 3006 represents one or more of any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. The system memory 3004 includes Read Only Memory (ROM)3008 and Random Access Memory (RAM) 3010. A basic input/output system 3012(BIOS) is stored in ROM 3008.

Computer 3000 also has one or more of the following drives: a hard disk drive 3014 for reading from and writing to a hard disk, a magnetic disk drive 3016 for reading from or writing to a removable magnetic disk 3018, and an optical disk drive 3020 for reading from or writing to a removable optical disk 3022 such as a CD ROM, DVD ROM, or other optical media. The hard disk drive 3014, magnetic disk drive 3016, and optical disk drive 3020 are connected to the bus 3006 by a hard disk drive interface 3024, a magnetic disk drive interface 3026, and an optical drive interface 3028, respectively. The drives and their associated computer-readable media provide nonvolatile storage of computer-readable instructions, data structures, program modules and other data for the computer. Although a hard disk, a removable magnetic disk and a removable optical disk are described, other types of computer-readable storage media can be used to store data, such as flash memory cards, digital video disks, Random Access Memories (RAMs), Read Only Memories (ROMs), and the like.

Several program modules may be stored on the hard disk, magnetic disk, optical disk, ROM, or RAM. These programs include an operating system 3030, one or more application programs 3032, other program modules 3034, and program data 3036. Application programs 3032 or program modules 3034 may include, for example, computer program logic for: data deduplication module 104, maintenance module 106, data stream API110, chunk maintenance API 112, data access API 114, chunk store interface 116, data stream parser 602, data chunk store manager 604, metadata generator 606, stream map generator 608, metadata collector 802, locality indicator generator 804, rehydration module 1102, redirection table modifier 1702, generation incrementer 1704, data stream assembler 1902, generation checker 1906, data chunk retriever 1908, garbage collector module 2302, stream map chunk scanner 2304, deleted data chunk indicator 2306, storage space reclaimer 2308, bloom filter generator 2314, data chunk copier 2316, merge log generator 2318, redirection table populator 2320, backup storage module 2702, reference handling module 2706, chunk memory module 2708, re-merge module 2710, flowchart 700, flowchart 900, block store interface module 116, and data stream manager module, Flowchart 1600, flowchart 1800, flowchart 2000, flowchart 2100, flowchart 2200, flowchart 2500, flowchart 2600, flowchart 2800, flowchart 2900 (including any steps of flowcharts 700, 900, 1600, 1800, 2000, 2100, 2200, 2500, 2600, 2800, and 2900), and/or other embodiments described herein.

A user may enter commands and information into the computer 3000 through input devices such as a keyboard 3038 and pointing device 3040. Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to the processing unit 3002 through a serial port interface 3042 that is coupled to bus 3006, but may be connected by other interfaces, such as a parallel port, game port, or a Universal Serial Bus (USB).

A display device 3044 is also connected to the bus 3006 via an interface, such as a video adapter 3046. In addition to the monitor, computer 3000 may also include other peripheral output devices (not shown), such as speakers and printers.

Computer 3000 is connected to a network 3048 (e.g., the Internet) through an adapter or network interface 3050, a modem 3052, or other means for establishing communications over the network. Modem 3052 (which may be internal or external) is connected to bus 3006 via serial port interface 3042.

As used herein, the terms "computer program medium," "computer-readable medium," and "computer-readable storage medium" are used to generally refer to media such as the hard disk associated with hard disk drive 3014, removable magnetic disk 3018, removable optical disk 3022, as well as other media such as flash memory cards, digital video disks, Random Access Memories (RAMs), Read Only Memories (ROM), and the like. These computer-readable storage media are distinct from and non-overlapping with communication media. Communication media typically embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave. The term "modulated data signal" means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wireless media such as acoustic, RF, infrared and other wireless media. Embodiments are also directed to these communication media.

As indicated above, computer programs and modules (including application programs 3032 and other program modules 3034) may be stored on the hard disk, magnetic disk, optical disk, ROM, or RAM. Such computer programs may also be received via network interface 3050 or serial port interface 3042. Such computer programs, when executed or loaded by an application, enable computer 3000 to implement features of the present invention as discussed herein. Accordingly, such computer programs represent controllers of the computer 3000.

The invention also relates to a computer program product comprising software stored on any computer usable medium. Such software, when executed in one or more data processing devices, causes the data processing devices to operate as described herein. Embodiments of the present invention employ any computer-usable or computer-readable medium, known now or in the future. Examples of a computer-readable medium include, but are not limited to, storage devices such as RAM, hard drives, floppy disks, CD ROMs, DVD ROMs, zip disks, tapes, magnetic storage devices, optical storage devices, MEMs (memories), nanotechnology-based storage devices, and the like.

Conclusion VI

While various embodiments of the present invention have been described above, it should be understood that they have been presented by way of example only, and not limitation. It will be understood by those of ordinary skill in the relevant art that various changes in form and details may be made therein without departing from the spirit and scope of the present invention as defined by the following claims. Thus, the scope of the present invention should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.

Claims (23)

1. A method (2000) for garbage collecting a chunk store, the chunk store comprising data stored as a plurality of data chunks, the plurality of data chunks comprising stream map chunks, each stream map chunk corresponding to a stream map of a respective data stream and referencing data chunks included in the respective data stream stored in one or more chunk containers of the chunk store, the method comprising:

identifying (2002) unused data chunks stored in the one or more chunk containers based on being referenced only by stream map chunks indicated as deleted, wherein each stream map chunk indicated as deleted corresponds to a deleted data stream;

indicating (2004) the identified data chunk as deleted; and

storage space in one or more chunk containers containing data chunks indicated as deleted is reclaimed (2006).

2. The method of claim 1, wherein each stream map chunk references data chunks stored in the one or more chunk containers by a respective data chunk identifier, the identifying comprising:

scanning the plurality of stream map chunks to determine any stream map chunks not indicated as deleted;

including in a data structure a data chunk identifier referenced by each stream map chunk indicated as undeleted;

scanning the plurality of stream map chunks to determine any stream map chunks indicated as deleted; and

determining any data chunk identifiers not included in the data structure that are referenced by the stream map chunk determined to be indicated as deleted.

3. The method of claim 2, wherein the indicating comprises:

indicating as deleted the data chunk corresponding to the data chunk identifier determined to be referenced by the stream map chunk indicated as deleted and not included in the data structure.

4. The method of claim 1, wherein each stream map chunk references data chunks stored in the one or more chunk containers by a respective data chunk identifier, the identifying comprising:

scanning at least one deletion log to determine any stream map chunks not indicated as deleted;

including in a data structure a data chunk identifier referenced by each stream map chunk indicated as undeleted;

generating a deletion bitmap indicating as deleted a plurality of stream map chunks of one or more stream containers, stream map chunks indicated as not deleted, and other stream map chunks;

deleting the scanned at least one deletion log;

scanning the deletion bitmap to determine any stream map blocks indicated as deleted; and

determining any data chunk identifiers not included in the data structure that are referenced by the stream map chunk determined to be indicated as deleted.

5. The method of claim 1, wherein the recovering comprises:

copying each data chunk of the chunk container that is not indicated as deleted to a new container; and

populating a redirection table of the new container to map, for each data chunk copied, a first chunk identifier in the chunk container to a second chunk identifier in the new container.

6. The method of claim 5, wherein the chunk store comprises a hash index that stores a plurality of hash index entries, wherein each hash index entry of the hash index maps a data chunk identifier to a hash of a corresponding data chunk, wherein the reclaiming further comprises:

modifying at least one entry of the hash index by replacing a data chunk identifier in a hash entry with a new data chunk identifier obtained from a chunk header of the data chunk and the redirection table.

7. The method of claim 5, further comprising:

for each stream map block of the block store,

locating one or more referenced data chunks in one or more redirection tables of one or more chunk containers of the chunk store by respective data chunk identifiers stored in the stream map chunk for the one or more referenced data chunks; and

for each of the one or more referenced data chunks located in the one or more redirection tables of the one or more chunk containers, appending the data chunk identifier in the stream map chunk with the corresponding new data chunk identifier in the one or more redirection tables of the one or more chunk containers.

8. The method of claim 7, wherein the appending comprises:

appending a data chunk identifier in-situ in the stream map chunk in the chunk container.

9. The method of claim 7, wherein the appending comprises:

generating a second chunk container comprising the stream map chunk; and

appending a data chunk identifier in the stream map chunk in the second chunk container, the second chunk container being a stream map container.

10. A system for garbage collecting a chunk store, the chunk store comprising data stored as a plurality of data chunks, the plurality of data chunks comprising stream map chunks, each stream map chunk corresponding to a stream map of a respective data stream and referencing data chunks included in the respective data stream stored in one or more chunk containers of the chunk store, comprising:

means for identifying unused data chunks stored in the one or more chunk containers based on being referenced only by stream map chunks indicated as deleted, wherein each stream map chunk indicated as deleted corresponds to a deleted data stream;

means for indicating the identified data block as deleted; and

means for reclaiming storage space in one or more chunk containers containing data chunks indicated as deleted.

11. The system of claim 10, wherein each stream map chunk references data chunks stored in the one or more chunk containers by a respective data chunk identifier, the means for identifying comprising:

means for scanning the plurality of stream map chunks to determine any stream map chunks not indicated as deleted;

means for including in a data structure a data chunk identifier referenced by each stream map chunk indicated as undeleted;

means for scanning the plurality of stream map chunks to determine any stream map chunks indicated as deleted; and

means for determining any data chunk identifiers not included in the data structure that are referenced by the stream map chunk determined to be indicated as deleted.

12. The system of claim 11, wherein the means for indicating comprises:

means for indicating as deleted data chunks corresponding to data chunk identifiers determined to be referenced by stream map chunks indicated as deleted and not included in the data structure.

13. The system of claim 10, wherein each stream map chunk references data chunks stored in the one or more chunk containers by a respective data chunk identifier, the means for identifying comprising:

means for scanning at least one deletion log to determine any stream map blocks not indicated as deleted;

means for including in a data structure a data chunk identifier referenced by each stream map chunk indicated as undeleted;

means for generating a deletion bitmap indicating as deleted a plurality of stream map chunks, stream map chunks indicated as not deleted, and other stream map chunks of one or more stream containers;

means for deleting the scanned at least one deletion log;

means for scanning the deletion bitmap to determine any stream map blocks indicated as deleted; and

means for determining any data chunk identifiers not included in the data structure that are referenced by the stream map chunk determined to be indicated as deleted.

14. The system of claim 10, wherein the means for recycling comprises:

means for copying each data chunk of the chunk container that is not indicated as deleted to a new container; and

means for populating a redirection table of the new container to map, for each data chunk copied, a first chunk identifier in the chunk container to a second chunk identifier in the new container.

15. The system of claim 14, wherein the chunk store comprises a hash index that stores a plurality of hash index entries, wherein each hash index entry of the hash index maps a data chunk identifier to a hash of a corresponding data chunk, wherein the means for reclaiming further comprises:

means for modifying at least one entry of the hash index by replacing a data chunk identifier in a hash entry with a new data chunk identifier obtained from a chunk header of the data chunk and the redirection table.

16. The system of claim 14, further comprising:

for each stream map block of the block store,

means for locating one or more referenced data chunks in one or more redirection tables of one or more chunk containers of the chunk store by respective data chunk identifiers stored in the stream map chunk for the one or more referenced data chunks; and

means for appending, for each of the one or more referenced data chunks located in the one or more redirection tables of the one or more chunk containers, the data chunk identifier in the stream map chunk with the corresponding new data chunk identifier in the one or more redirection tables of the one or more chunk containers.

17. The system of claim 16, wherein the means for appending comprises:

means for appending a data chunk identifier in-situ in the stream map chunk in the chunk container.

18. The system of claim 16, wherein the means for appending comprises:

means for generating a second chunk container comprising the stream map chunk; and

means for appending a data chunk identifier in the stream map chunk in the second chunk container, the second chunk container being a stream map container.

19. A garbage collection module (2302) for garbage collecting a chunk store, the chunk store comprising data stored as a plurality of data chunks (322), the plurality of data chunks comprising stream map chunks (2324), each stream map chunk corresponding to a stream map of a respective data stream and referencing data chunks included in the respective data stream stored in one or more chunk containers (304) of the chunk store, the garbage collection module (2302) comprising:

a stream map chunk scanner (2304) configured to identify unused data chunks stored in the one or more chunk containers (304) based on reference only by stream map chunks (2324) indicated as deleted, wherein each stream map chunk indicated as deleted corresponds to a deleted data stream;

a deleted data chunk indicator (2306) configured to indicate the identified data chunk as deleted (2334); and

a storage space reclaimer (2308) configured to reclaim storage space in one or more chunk containers (304) containing data chunks indicated as deleted (2334).

20. The garbage collection module of claim 19 wherein each stream map chunk references a data chunk stored in the one or more chunk containers by a corresponding data chunk identifier, wherein the stream map chunk scanner comprises:

a bloom filter generator configured to generate a bloom filter;

wherein the stream map block scanner scans a plurality of stream map blocks to determine any stream maps not indicated as deleted, includes database block identifiers referenced by each stream map block indicated as not deleted in the bloom filter, scans the plurality of stream map blocks to determine any stream map blocks indicated as deleted, and determines any data block identifiers referenced by stream map blocks determined as deleted that are not included in the bloom filter.

21. The garbage collection module of claim 19, wherein the storage space reclaimer comprises:

a data chunk copier to copy each data chunk in the chunk container that is not indicated as deleted to a new container; and

a redirection table populator populating a redirection table of the new container to map, for each data chunk copied, a first chunk identifier in the chunk container to a second chunk identifier in the new container.

22. The garbage collection module of claim 21, wherein the chunk store comprises a hash index that stores a plurality of hash index entries, wherein each hash index entry of the hash index maps a data chunk identifier to a hash of a corresponding data chunk, wherein the storage space reclaimer modifies at least one entry in the hash index by replacing a data chunk identifier in a hash entry with a new data chunk identifier obtained from the redirect table and a header of a data chunk.

23. The garbage collection module of claim 22, wherein for each stream map chunk in the chunk store, the one or more referenced data chunks are located in one or more redirection tables of one or more chunk containers of the chunk store by respective data chunk identifiers stored in the stream map chunk for the one or more referenced data chunks, and for each of the one or more referenced data chunks located in the one or more redirection tables of the one or more chunk containers, the data chunk identifiers are appended in the stream map chunk with respective new data chunk identifiers in the one or more redirection tables of the one or more chunk containers.