Methods and systems for eliminating data redundancies

A method in a data processing system having data blocks with associated identifiers, the method comprising the steps of:

• receiving a request for a reference to a memory location that stores data, the request comprising the data;
• creating a new identifier that is based on the data;
• determining whether the new identifier is equivalent to one of the associated identifiers;
• when it is determined that the new identifier is equivalent to one of the associated identifiers,
• retrieving the data block associated with the one associated identifier,
• determining whether the data in the request and the retrieved data block correspond to one another by obtaining a revised new identifier having more bits than the new identifier and by obtaining a revised one associated identifier having more bits than the one associated identifier, and
• returning a reference to the data block that is associated with the one associated identifier when the data in the request and the retrieved data block correspond to one another.

A method for avoiding data redundancies in a data processing system, the method comprising the steps of:

• obtaining a first data block identifier for a first data block, the first data block identifier being calculated based on data of the first data block;
• generating a memory allocation request for the first data block;
• transmitting the memory allocation request to a redundancy handler, the memory allocation request instructing the redundancy handler to determine whether a second data block identifier matching the first data block identifier exists, wherein the second data block identifier is calculated based on data of a second data block;
• and
• receiving an allocation response indicating whether the second data block identifier of the second data block exists, the allocation response including a reference to the second data block when the second data block identifier exists,
• wherein when the redundancy handler determines that the second data block identifier matching the first data block identifier exists, the redundancy handler:
• retrieves the second data block associated with the second data block identifier, and
• determines whether the first data block and the retrieved second data block correspond to one another by obtaining a revised first data block identifier having more bits than the first data block identifier and by obtaining a revised second data block identifier having more bits than the second data block identifier.

A method for eliminating data redundancies in a data processing system, the method comprising the steps of:

• receiving a first data block;
• calculating a first data block identifier based on data of the first data block;
• determining whether a second data block identifier matching the first data block identifier exists in a list of other data block identifiers, the second data block identifier being calculated based on data of a second data block;
• when it is determined that the second data block identifier matching the first data block identifier exists,
• retrieving the second data block associated with the second data block identifier,
• determining whether the first data block and the retrieved second data block correspond to one another by obtaining a revised first data block identifier having more bits than the first data block identifier and by obtaining a revised second data block identifier having more bits than the second data block identifier, and
• replacing the first data block with a reference to the second data block when the first data block and the retrieved second data block correspond to one another;
• and
• when it is determined that the second data block identifier matching the first data block identifier does not exist, adding the first data block identifier to the list.

A computer-readable medium containing instructions that cause a data processing system to perform a method comprising the steps of:

• obtaining a first data block identifier for a first data block, the first data block identifier being calculated based on data of the first data block;
• determining whether a second data block identifier matching the first data block identifier exists, the second data block identifier being calculated based on data of a second data block;
• and
• when it is determined that the second data block identifier matching the first data block identifier exists,
• retrieving the second data block associated with the second data block identifier,
• determining whether the first data block and the retrieved second data block correspond to one another by obtaining a revised first data block identifier having more bits than the first data block identifier and by obtaining a revised second data block identifier having more bits than the second data block identifier, and
• replacing the first data block with a reference to the second data block when the first data block and the retrieved second data block correspond to one another.

A computer-readable medium containing instructions that cause a data processing system having blocks associated with identifiers to perform a method comprising the steps of:

• receiving a request for a reference to a memory location that stores data, the request comprising the data;
• creating a new identifier that is based on the data;
• determining whether the new identifier is equivalent to one of the associated identifiers;
• when it is determined that the new identifier is equivalent to one of the associated identifiers,
• retrieving the second data block associated with the second data block identifier, and
• determining whether the first data block and the retrieved second data block correspond to one another by obtaining a revised first data block identifier having more bits than the first data block identifier and by obtaining a revised second data block identifier having more bits than the second data block identifier
• returning a reference to the data block that is associated with the one associated identifier.

A computer-readable medium containing instructions that cause a data processing system to perform a method comprising the steps of:

• obtaining a first data block identifier for a first data block, the first data block identifier being calculated based on data of the first data block;
• generating a memory allocation request for the first data block;
• transmitting the memory allocation request to a redundancy handler, the memory allocation request instructing the redundancy handler to determine whether a second data block identifier matching the first data block identifier exists, wherein the second data block identifier is calculated based on data of a second data block;
• and
• receiving an allocation response indicating whether the second data block identifier of the second data block exists, the allocation response including a reference to the second data block when the second data block identifier exists,
• wherein when the redundancy handler determines that the second data block identifier matching the first data block identifier exists, the redundancy handler:
• retrieves the second data block associated with the second data block identifier, and
• determines whether the first data block and the retrieved second data block correspond to one another by obtaining a revised first data block identifier having more bits than the first data block identifier and by obtaining a revised second data block identifier having more bits than the second data block identifier.

A computer-readable medium containing instructions that cause a data processing system to perform a method comprising the steps of:

• receiving a first data block;
• calculating a first data block identifier based on data of the first data block;
• determining whether a second data block identifier matching the first data block identifier exists in a list of other data block identifiers, the second data block identifier being calculated based on data of a second data block;
• when it is determined that the second data block identifier matching the first data block identifier exists,
• retrieving the second data block associated with the second data block identifier,
• determining whether the first data block and the retrieved second data block correspond to one another by obtaining a revised first data block identifier having more bits than the first data block identifier and by obtaining a revised second data block identifier having more bits than the second data block identifier, and
• replacing the first data block with a reference to the second data block when the first data block and the retrieved second data block correspond to one another;
• and
• when it is determined that the second data block identifier matching the first data block identifier does not exist, adding the first data block identifier to the list.

A data processing system comprising:

• a secondary storage device having a stored data block with data;
• a memory comprising a computer program that obtains a first data block identifier for a first data block, the first data block identifier being calculated based on data of the first data block, determines whether a second data block identifier matching the first data block identifier exists, the second data block identifier being calculated based on data of a second data block, and when it is determined that the second data block identifier matching the first data block identifier exists,
• retrieves the second data block associated with the second data block identifier,
• determines whether the first data block and the retrieved second data block correspond to one another by obtaining a revised first data block identifier having more bits than the first data block identifier and by obtaining a revised second data block identifier having more bits than the second data block identifier, and
• replaces the first data block with a reference to the second data block;
• and
• a processing unit that runs the computer program.

A data processing system comprising:

• a secondary storage device having a stored data block with data;
• a memory comprising a computer program that receives a request for a reference to a memory location that stores data, the request comprising the data, creates a new identifier that is based on the data, determines whether the new identifier is equivalent to one of the associated identifiers, and when it is determined that the new identifier is equivalent to one of the associated identifiers,
• retrieves the data block associated with the one associated identifier,
• determines whether the data in the request and the retrieved data block correspond to one another by obtaining a revised new identifier having more bits than the new identifier and by obtaining a revised one associated identifier having more bits than the one associated identifier, and
• returns a reference to the data block that is associated with the one associated identifier;
• and
• a processing unit that runs the computer program.

A data processing system comprising:

• a secondary storage device having a stored data block with data;
• a memory comprising a computer program that obtains a first data block identifier for a first data block, the first data block identifier being calculated based on data of the first data block, generates a memory allocation request for the first data block, transmits the memory allocation request to a redundancy handler, the memory allocation request instructing the redundancy handler to determine whether a second data block identifier matching the first data block identifier exists, wherein the second data block identifier is calculated based on data of a second data block, and receives an allocation response indicating whether the second data block identifier of the second data block exists, the allocation response including a reference to the second data block when the second data block identifier exists;
• and
• a processing unit that runs the computer program,
• wherein when the redundancy handler determines that the second data block identifier matching the first data block identifier exists, the redundancy handler:
• retrieves the second data block associated with the second data block identifier, and
• determines whether the first data block and the retrieved second data block correspond to one another by obtaining a revised first data block identifier having more bits than the first data block identifier and by obtaining a revised second data block identifier having more bits than the second data block identifier.

A data processing system for eliminating data redundancies, the data processing system comprising:

• means for obtaining a first data block identifier for a first data block, the first data block identifier being calculated based on data of the first data block;
• means for determining whether a second data block identifier matching the first data block identifier exists, the second data block identifier being calculated based on data of a second data block;
• and
• means for, when it is determined that the second data block identifier matching the first data block identifier exists,
• retrieving the second data block associated with the second data block identifier,
• determining whether the first data block and the retrieved second data block correspond to one another by obtaining a revised first data block identifier having more bits than the first data block identifier and by obtaining a revised second data block identifier having more bits than the second data block identifier, and
• replacing the first data block with a reference to the second data block.

A data processing system for eliminating data redundancies, the data processing system having data blocks with associated identifiers, the data processing system comprising:

• means for receiving a request for a reference to a memory location that stores data, the request comprising the data;
• means for creating a new identifier that is based on the data;
• means for determining whether the new identifier is equivalent to one of the associated identifiers;
• means for, when it is determined that the new identifier is equivalent to one of the associated identifiers,
• retrieving the data block associated with the one associated identifier,
• determining whether the data in the request and the retrieved data block correspond to one another by obtaining a revised new identifier having more bits than the new identifier and by obtaining a revised one associated identifier having more bits than the one associated identifier, and
• returning a reference to the data block that is associated with the one associated identifier when the data in the request and the retrieved data block correspond to one another.

A data processing system for eliminating data redundancies, the data processing system comprising:

• means for obtaining a first data block identifier for a first data block, the first data block identifier being calculated based on data of the first data block;
• means for generating a memory allocation request for the first data block;
• means for transmitting the memory allocation request to a redundancy handler, the memory allocation request instructing the redundancy handler to determine whether a second data block identifier matching the first data block identifier exists, wherein the second data block identifier is calculated based on data of a second data block;
• and
• means for receiving an allocation response indicating whether the second data block identifier of the second data block exists, the allocation response including a reference to the second data block when the second data block identifier exists,
• wherein when the redundancy handler determines that the second data block identifier matching the first data block identifier exists, the redundancy handler:
• retrieves the second data block associated with the second data block identifier, and
• determines whether the first data block and the retrieved second data block correspond to one another by obtaining a revised first data block identifier having more bits than the first data block identifier and by obtaining a revised second data block identifier having more bits than the second data block identifier.

A data processing system for eliminating data redundancies, the data processing system comprising:

• means for receiving a first data block;
• means for calculating a first data block identifier based on data of the first data block;
• means for determining whether a second data block identifier matching the first data block identifier exists in a list of other data block identifiers, the second data block identifier being calculated based on data of a second data block;
• means for, when it is determined that the second data block identifier matching the first data block identifier exists,
• retrieving the second data block associated with the second data block identifier,
• determining whether the first data block and the retrieved second data block correspond to one another by obtaining a revised first data block identifier having more bits than the first data block identifier and by obtaining a revised second data block identifier having more bits than the second data block identifier, and
• replacing the first data block with a reference to the second data block when the first data block and the retrieved second data block correspond to one another;
• and
• means for, when it is determined that the second data block identifier matching the first data block identifier does not exist, adding the first data block identifier to the list.

A computer-readable memory device encoded with a data structure and a program that accesses the data structure, the program is run by a processor in a data processing system, the data structure having a plurality of entries, each entry comprising:

• a reference to a data block that contains data and an identifier that is based on the data using a calculation, wherein when the program receives a request to create a new data block containing new data, the program creates a new identifier based on the new data using the calculation, compares the new identifier to the identifiers in the entries to prevent a data block redundancy, and when the new identifier matches one of the identifiers:
• retrieves the data block associated with the one identifier,
• determines whether the new data block and the retrieved data block correspond to one another by obtaining a revised new identifier having more bits than the new identifier and by obtaining a revised one identifier having more bits than the one identifier, and
• replaces the new data block with a reference to an existing data block corresponding to the identifier when the new data block and the retrieved data block correspond to one another.