Verifying a file in a system with duplicate segment elimination using segmention-independent checksums

[0001] Some data storage systems avoid storing duplicate data segments to use the available storage space more efficiently. This is particularly applicable for backup systems. A data set of data files is transmitted from a source system to a storage system. At some point, data files in the data set are broken into segments. To make storage more efficient, a reduced number of copies of a segment that appears multiple times in a data set are stored in the storage system along with location information indicating how to reconstruct the original data files in the data set. There are points in the segmenting, transmission, and other processing steps of the files in the data set where corruption can occur. However, traditional means of verifying a data file would require reconstructing the file from the data segments. It would be valuable if it could be determined efficiently that no corruption has occurred so that the data files in the data set could be recovered without any errors.

[0006] The invention can be implemented in numerous ways, including as a process, an apparatus, a system, a composition of matter, a computer readable medium such as a computer readable storage medium or a computer network wherein program instructions are sent over optical or electronic communication links. In this specification, these implementations, or any other form that the invention may take, may be referred to as techniques. A component such as a processor or a memory described as being configured to perform a task includes both a general component that is temporarily configured to perform the task at a given time or a specific component that is manufactured to perform the task. In general, the order of the steps of disclosed processes may be altered within the scope of the invention.

[0007] A detailed description of one or more embodiments of the invention is provided below along with accompanying figures that illustrate the principles of the invention. The invention is described in connection with such embodiments, but the invention is not limited to any embodiment. The scope of the invention is limited only by the claims and the invention encompasses numerous alternatives, modifications and equivalents. Numerous specific details are set forth in the following description in order to provide a thorough understanding of the invention. These details are provided for the purpose of example and the invention may be practiced according to the claims without some or all of these specific details. For the purpose of clarity, technical material that is known in the technical fields related to the invention has not been described in detail so that the invention is not unnecessarily obscured.

[0008] Verifying a file in a system with duplicate segment elimination using segment-independent checksums is disclosed. A checksum is computed for a data file. In some embodiments, the data file and the data file checksum are transmitted from a source system and received at a storage system. The data file is segmented into a plurality of distinct data segments and checksums are computed for each of the distinct data segments. The segment checksums are used to construct a data file checksum. The original data file checksum and the constructed data file checksum from the checksums of each of the segments are compared. If the data file checksum and the constructed data file checksum are the same, then the data file and the plurality of distinct data segments is determined to be equivalent. The data file can therefore be reconstructed from the plurality of distinct data segments without fear of corruption.

[0009] FIG. 1 illustrates a system verifying a file in a system with duplicate segment elimination using segment-independent checksums in one embodiment. In the example shown, source system 100 includes storage device 102 and processor 104. Storage system 106 includes processor 108 and storage device 110. Source system 100 is the source of information that is to be stored on storage system 106. Source information from storage device 102 is processed by processor 104 and transmitted to storage system 106. The processed source information is received by storage system 106 and processed by processor 108 before being stored on storage device 110. In various embodiments, storage device 102 and storage device 110 include a plurality of storage devices. Storage device 102 and storage device 110 can be a magnetic hard drive, a redundant array of magnetic hard drives, a tape drive, an optical drive, a flash drive or any other storage device for storing digital information. In various embodiments, source system 100 and/or storage system 106 comprise one or more separate computer systems with one or more separate processors. In various embodiments, source information from source system 100 is transmitted to storage system 106 using a direct connection, a local network connection, a wide area network connection, a wireless network connection, the internet, or any other connection able to appropriately transmit the information.

[0010] FIG. 2 illustrates location information on the storage device in one embodiment. In the example shown, a tree is used to locate segments in a data file. The data file includes data segments ‘a,’ ‘b,’ ‘a,’ ‘b,’ ‘c,’ ‘d,’ ‘e,’ ‘f,’ and ‘a.’ Top tree segment 200 includes three segment references SR1, SR2, and SR3. Each segment reference includes information such as the content derived identifier, the checksum for the segment, and the logical size of the segment. In some embodiments, the content derived identifier is a cryptographic hash function, and the checksum is a composable hash function. Each segment reference of top tree segment 200 (for example, SR1, SR2, and SR3) refers to another segment (for example tree segment 202, 204, and 206, respectively). Tree segment 202 includes two segment references SR4 and SR5. Segment reference SR4 refers to data segment ‘a’ and segment reference SR5 refers to data segment ‘b.’ Tree segment 204 includes four segment references SR6, SR7, SR8, and SR9. Segment references SR6, SR7, SR8, and SR9 refer to data segments ‘a,’ ‘b,’ ‘c,’ and ‘d,’ respectively. Tree segment 206 includes four segment references SRA, SRB, and SRC. Segment references SRA, SRB, and SRC refer to data segments ‘e,’ ‘f,’ and ‘a,’ respectively. In some embodiments, the B-tree is used to locate data files in a data set and/or segments in a data file efficiently at arbitrary offsets. In some embodiments, the checksums for data segments and groups of data segments associated with tree segments are computed as the tree is built using the checksums for each data segment.

[0011] A hash function takes a long string (or message) of any length as input and produces a fixed length string as output. A cryptographic hash function is a hash function suitable for use as an identifier for data segments in a deduplication system because of their collision resistant properties. A cryptographic hash function typically has properties including 1) given h, it should be hard to find m such that h=hash(m); 2) given m1, it should be hard to find m2 (not equal to m1) such that hash(m1)=hash(m2); and 3) it should be hard to find two different m1 and m2 such that hash(m1)=hash(m2). Cryptographic hash functions include SHA-1 (Secure Hash Algorithm 1), MD5 (Message-Digest algorithm 5), and RIPEMD-160 (RACE Integrity Primitives Evaluation Message Digest 160-bit version). In some embodiments, the identifier is a similar to identifiers as described in U.S. patent application Ser. No. 10/611,309 by Patterson entitled: “DATA STORAGE USING IDENTIFIERS” which is incorporated by reference for all purposes.

[0012] Hash functions include 1-byte XOR, redundancy checks (for example, Fletcher's checksum, Adler-32, and cyclic redundancy checks), byte-wise sums, a Rabin fingerprint, and Fowler-Noll-Vo (FNV) hash function. A composable hash function has the additional property that, given data file DATA which can be segmented into two segments data1 and data2 or two other segments data3 and data4, (i.e. DATA=data1.data2=data3.data4)

[0013]

c_hash(DATA)	= c_hash_compose(	c_hash(data1), length(data1),
		c_hash(data2), length(data2) )
	= c_hash_compose(	c_hash(data3), length(data3))
		c_hash(data4), length(data4) )

where c_hash is the composable hash function, c_hash_compose is the compose function for the composable hash function such that the composable hash of DATA can be computed from the composable hash of segments data1 and data2, and length is a function giving the length of the data segment. The composable function depends on the composable hash function. In various embodiments, the length of one or both of the data segments is not required for the composable function. Composable hash functions include 1-byte XOR, 4-byte XOR, byte-wise sum, and a Rabin fingerprint. For example, the hash function of a 4-byte XOR is a composable hash function. So, the relation between the 4-byteXOR function and the 4-byteXOR_compose function is given by

[0014]

4_byteXOR(DATA)	= 4_byteXOR_compose(	4_byteXOR(data1), length(data1),
		4_byteXOR(data2) )
	= 4_byteXOR_compose(	4_byteXOR(data3), length(data3),
		4_byteXOR(data4) )
where the compose function is
4_byteXOR_compose( X1, L1, X2, L2 ) = X1 {circumflex over ( )} rotate( X2, (L1 mod 4) * 8)
and where the rotate function is
rotate( X, Y ) = ( X << Y ) | ( X >> 32 − Y ).

For example, the hash function of a 1-byte XOR is a composable hash function. So, the relation between the 1_byteXOR function and the 1_byteXOR_compose function is given by

[0015]

1_byteXOR(DATA)	= 1_byteXOR_compose ( 1_byteXOR(data1),
	1_byteXOR(data2) )
	= 1_byteXOR_compose ( 1_byteXOR(data3),
	1_byteXOR(data4) )

where the compose function is

[0016] 1_byteXOR_compose(X1, L1, X2, L2)=X1^X2,

where the composable hash function is

[0017] 1_byteXOR(Y)=Y_byte1^Y_byte2^ . . . ^Y_byteN,

where Y_bytei is the i^th byte in Y, and where there are N bytes in Y.

[0018] FIG. 3 illustrates an embodiment of a process for verifying a file in a system with duplicate segment elimination using segment-independent checksums. In the example illustrated, a data file is received in 300. In 302, the data file is segmented into a plurality of distinct data segments. In 304, a checksum is computed for each of the plurality of distinct data segments. In 306, a constructed data file checksum is constructed using the checksums for each of the plurality of distinct data segments. Using the checksums for each distinct data segment to construct a data file checksum is more efficient than reconstructing the data file from the distinct data segments and then calculating the data file checksum. This is because the same distinct data segment may appear multiple times in the data set of data files. In some embodiments, the checksums for each distinct data segment are calculated only once and used to determine checksums for groups of data segments associated with tree segments or the entire data file.

[0019] In 308, it is determined if the constructed data file checksum is the same as the data file checksum. In various embodiments, the data file checksum is calculated before the data file is transmitted from the source system to the storage system, while the data file is streamed out of the source system, while the data file is being received at the storage system, or at any other appropriate point in time or in any other appropriate system. If the constructed data file checksum is the same as the data file checksum, then control is passed to 310. In 310, it is indicated that the data file and the plurality of distinct data segments are verified as being equivalent, and the process ends. If the constructed data file checksum is not the same as the data file checksum, then control is passed to 312. In 312, it is indicated that the data file and the plurality of distinct data segments are not equivalent, and the process ends.

[0020] Although the foregoing embodiments have been described in some detail for purposes of clarity of understanding, the invention is not limited to the details provided. There are many alternative ways of implementing the invention. The disclosed embodiments are illustrative and not restrictive.