Hash-based data block processing with intermittently-connected systems

• US 7,600,125 B1
• Filed: 04/29/2005
• Issued: 10/06/2009
• Est. Priority Date: 12/23/2004
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Stringham, Russell R.
• Primary Examiner(s): Zand; Kambiz
• Assistant Examiner(s): RAHIM, MONJUR
• Application Number:
  US11/119,449
• Time in Patent Office: 1,621 Days
• Field of Search: 713/190, 713/161, 713/300, 713/164, 713/176, 709/224, 380/229
• US Class Current: 713/176
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1461 Backup scheduling policy
• CPC Class Codes: G06F 11/1464 for networked environments

Abstract

Methods are provided for detecting the processing status of data blocks in systems having intermittent connections. A hash value is used at times in place of a block'"'"'s data content, thereby reducing processing of the block. Hash values may be maintained locally. Blocks collected locally may be stored locally at least until a connection to a server becomes available again. Systems and configured storage media are also provided.

Claims

1. A method for use by clients for processing blocks, the method comprising executing:

determining, at a first client that comprises a processor, a local set of processed block hash values, and a local set of indeterminate status block hash values, that a hash value is not in the local set of processed block hash values;

sending indeterminate status block hash values from the first client to the server;

receiving an indication at the first client as to whether each sent hash value has already been seen by the server;

discarding collected blocks at the first client whose hash values have been seen by the server but maintaining those hash values in the local set of processed block hash values even after their blocks are processed;

submitting, from the first client to the server, for processing blocks whose hash values have not yet been seen by the server;

sending, from a second client to the server, the hash value that was sent to the server by the first client;

receiving, at the second client, an indication that the server has already seen the hash value;

adding the hash value to a second set of processed block hash values at the second client;

refraining, at the second client, from submitting to the server for processing the block that corresponds to the hash value that has already been seen by the server.

2. The method of claim 1, further comprising the steps of:

determining that network communication with the server is unavailable;

collecting, at the first client, the hash values and corresponding blocks locally when the hash value is not in the local set of processed block hash values;

after communication with the server is available, sending the locally collected indeterminate status block hash values from the first client to the server and continuing with the steps of claim 1.

3. The method of claim 2, further comprising the step of collecting locally at the first client an additional set of indeterminate status blocks and corresponding hash values, thereby allowing delayed processing when a previous collection has not yet been checked against the server.

4. The method of claim 1, wherein the step of sending indeterminate status block hash values from the first client to the server comprises sending a superblock-hash value.

5. The method of claim 1, further comprising the steps of:

receiving, at the first client, a list of processed block hash values from the server; and

placing those hash values in the local set of processed block hash values at the first client, thereby initializing or updating that local set without necessarily collecting locally the corresponding blocks.

6. The method of claim 1, wherein the step of submitting, from the first client to the server, for processing comprises sending the block from the first client to the server to be placed in a backup repository which is not local to the first client.

7. The method of claim 1, further comprising processing locally at the first client a block which is submitted for processing, said processing comprising placing the block in a local backup repository at the first client.

8. The method of claim 1, wherein the first client does not submit the block to any other machine for processing if the hash value has already been seen by the server.

9. A computing system having a processor and a memory which are configured by software instructions and data for processing blocks, comprising a device having:

a local set of processed block hash values;

a local set of indeterminate status block hash values; and

a local collection of blocks;

wherein the software instructions operates to;

add a hash value to the local set of indeterminate status block hash values when network communication with a server is unavailable and the hash value is not in the local set of processed block hash values;

after network communication with the server is again available, send to the server indeterminate block hash values that were previously sent to the server by a second device;

receive an indication that the server has already seen the hash values;

discard collected blocks that correspond to the hash values that have already been seen by the server, yet add those hash values to the local set of processed block hash values;

refrain from submitting for processing blocks whose hash values have already been seen by the server; and

submit for processing blocks whose content or hash values have not yet been seen by the server.

10. The system of claim 9, wherein the software instructions also operate to compute superblock-hash values and to use them in determining whether to discard collected blocks.

11. The system of claim 9, further comprising an additional local set of indeterminate status blocks and corresponding hash values.

12. The system of claim 9, wherein the software instructions further operate to:

receive from the server a list of processed block hash values; and

place those hash values in the local set of processed block hash values, thereby initializing or updating that local set.

13. The system of claim 9, wherein the device has a local block repository and processes blocks locally by placing them in that repository.

14. The system of claim 9, wherein the device maintains hash values locally without sending them to the server.

15. The system of claim 9, wherein the device maintains hash values locally and also sends them to the server.

16. A computing system comprising:

a first client, a second client, and a server, each of which comprises a processor and memory and each of which is at least connectable to a computing network;

wherein the first client is configured with;

a local repository means for storing blocks locally when disconnected from the network;

a block status determining means for determining whether a block has been stored at the server by;

sending to the server, after reconnecting to the network, a hash value for the block;

receiving an indication that the server;

previously received the block from the second client; and

has stored the block at the server;

a block archiving means for;

refraining from submitting for processing the block that has already been stored at the server;

discarding the block that has already been stored at the server; and

locally storing the hash value of the block that has already been stored at the server; and

sending to the server blocks which are not yet stored at the server; and

wherein the server is configured with a central storage means for;

communicating with the first and second clients; and

coordinating storage at the server of blocks sent to the server by the first and second clients.

17. The system of claim 16, wherein the local repository means comprises a unique-hash single instance cluster store.

18. The system of claim 16, wherein the local repository means comprises a unique-hash-with-index single instance cluster store.

19. The system of claim 16, wherein the local repository means comprises software for performing a method of reducing data processing using a superblock-hash value.

20. The system of claim 16, further comprising at least three clients, wherein the central storage means comprises software for transmitting to a given client hash values of blocks received at the server from other clients.

21. The system of claim 16, wherein the block status determining means includes a local hash table of blocks have been at least partially processed, and wherein a corresponding server hash table in the central storage means is updated to include values found in the local hash table.

22. A configured computer storage medium for causing a processor of a client to perform execute a method of archiving blocks, the method comprising:

Calculating, using said processor of the client a hash value based on the content of a block;

determining that the hash value may not yet have been seen by a server;

asking the server whether the hash value was previously seen by the server;

receiving an answer from the server;

sending the corresponding block to the server if the server answers that the hash value was not previously seen;

refraining from sending the corresponding block to the server if the server answers that the hash value was previously sent by a second client; and

adding the hash value to a list of hash values seen by the server;

wherein operability of the client-server system containing the configured medium does not require that the server send the client any hash values for blocks which are not stored locally for the client.

23. A configured computer storage medium for causing a processor of a client to execute a method of processing blocks, the method comprising:

calculating, using said processor of the client a hash value based on the content of a block;

determining that the hash value may not yet have been seen by a server; and

processing the block;

wherein one of the following conditions exists;

(a) the determining step relies on a local hash table that has no corresponding server hash table, and blocks are processed locally when the client is disconnected from the server and then submitted to the server for processing when a connection to the server is reestablished;

or

(b) the determining step relies on a local hash table that has a corresponding server hash table, namely, one that is updated to contain values found in the local hash table, and the processing step;

submits blocks to the server for processing when the client is connected to the server and when the blocks have not yet been seen by the server, but refrains from submitting the blocks to the server for processing when the server indicates that the blocks were previously sent to the server by a second client; and

when the client is not connected refrains from processing the blocks locally but instead waits for a connection to be re-established.

24. The configured computer storage medium of claim 23, wherein processing a block comprises saving a copy of the block in a single instance cluster store.