JP2013190891A - Data transfer system - Google Patents

Abstract

An object of the present invention is to eliminate the need for transfer even when the data owned by the receiving side is similar.
[Solution]
The transmission side transmits the feature amount of the first data and the restored byte string for error correction.
The receiving side identifies second data having a feature amount in a range similar to the received feature amount among the already owned data, performs error correction processing on the received restored byte sequence, and converts it to the first feature amount. Store as data.
Even if the data is several kilobytes, the feature amount and the restored byte string are both tens of bytes at most, and the network load is small.
[Selection] Figure 2

Description

  The present invention relates to a data transfer system for exchanging data between computers.

  Non-Patent Document 1 proposes a method in which data is divided into units of several kilobytes called chunks on the client side, and only new chunks not owned by the server are transferred. Whether the server owns the chunk is determined by whether the hash values of the chunks match. Since the hash value has a smaller data amount than a chunk (several tens of bytes), it can be transmitted without load even in a low-bandwidth network. The client only needs to transfer chunks that are not owned by the server, and all data can be exchanged at a higher speed than the normal data transfer method.

  When the method of Non-Patent Document 1 is applied, if the contents of the chunk that the client intends to transfer are slightly different from the contents of the chunk that the server owns, the hash values do not match, so the client It is necessary to transfer all the contents. In order to solve this waste, Non-Patent Document 2 and Patent Document 1 propose a method in which chunks are further divided on the client side, and portions that do not match are narrowed down and transferred.

  Note that chunking is described in Non-Patent Documents 3 to 5, and feature amounts described below are described in Non-Patent Document 6 and Patent Document 2.

A. Muthitacharoen, B. Chen and D. Mazieres: "A low-bandwidth network file system," Proceedings of the 18th SOSP, Banff, Canada, 10-2001. S. Ihm, K. Park and V. S. Pai: "Wide-area Network Acceleration for the Developing World," USENIXATC'10 Proceedings of the 2010 USENIX conference on USENIX annual technical conference, 2010. J. Kornblum: "Identifying almost identical files using context triggered piecewise hashing," Digital investigation 3S pp.91-97, 2006. R. M. Karp and M. O. Rabin: "Pattern-matching algorithms," IBM Journal of Research and Development, 31 (2) pp. 249-260, 1987. N. Bjorner, A. Blass, Y. Gurevich: "Content-dependent chunking for differential compression, the local maximum approach," Journal of Computer and System Sciences, 76 (3-4), pp. 154-203, 2010. D. Teodosiu, N. Bjorner, Y. Gurevich, M. Manasse, J. Porkka and A. Wable: "Optimizing File Replication over Limited-Bandwidth Networks using Remote Differential Compression," Technical report, Microsoft Corporation, 2006.

US Patent 7,116,249 International Publication No.2012-005016

  When the method of Non-Patent Document 1 is applied, if the content of the chunk that the transmission side is trying to transfer is slightly different from the content of the chunk that is owned by the reception side, the hash values do not match. All the contents of the chunk need to be transferred. Even in the methods of Non-Patent Document 2 and Patent Document 1, it is necessary to transfer the mismatched portion of the contents of the chunk.

  Therefore, an object of the present invention is to eliminate the need for transfer even when the data owned by the receiving side is similar.

(Combined with claims)
In the present invention, a data transmission device that transmits the feature amount of the first data and the restored byte sequence for error correction of the first data to the communication line;
The second data having a feature amount in a range similar to the feature amount received via the communication line among the data already owned is specified, and the second data received via the communication line There is provided a data transfer system including a data receiving device that performs error correction processing by adding a restored byte sequence and stores second data after the error correction processing as the first data.

  Even if the data is several kilobytes, the feature amount and the restored byte string are both tens of bytes at most, and the network load is small.

It is a figure which illustrates the outline of a differential transfer system. It is a figure which shows the outline | summary of main processes. It is a block diagram which illustrates schematic structure of a data transmission client. It is a block diagram which illustrates schematic structure of a database server. It is a sequence diagram which illustrates the data transfer process of a data transmission client and a database server. It is a sequence diagram which illustrates the data transfer process of a data transmission client and a database server. It is a sequence diagram which illustrates the data transfer process of a data transmission client and a database server. It is a sequence diagram which illustrates the data transfer process of a data transmission client and a database server. It is a sequence diagram which illustrates the data transfer process of a data transmission client and a database server. It is a figure which illustrates the data structure of the management table which a database server produces. It is a figure which illustrates the procedure which divides | segments a file into chunks. It is a figure which illustrates the outline | summary of the process which calculates a fuzzy hash from a chunk, and the process which calculates a similarity from a fuzzy hash. It is a figure which illustrates the outline | summary of the process which calculates a Bloom filter from a chunk, and the process which calculates similarity from a Bloom filter. It is a figure which illustrates the outline | summary of the process which calculates a trait from a chunk. It is a figure which illustrates the outline | summary of the process which calculates | requires a decompression | restoration byte sequence from a chunk. It is a figure which illustrates the outline | summary of the process which decompress | restores a chunk using a decompression | restoration byte sequence. It is a figure which illustrates the data structure of the basic chunk management table which a database server produces.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

FIG. 1 is a diagram illustrating an outline of a differential transfer system. As shown in the figure, the differential transfer system includes n data transmission clients 20-1 to 20-n and a database server 30, which are designed to be able to transmit and receive information to and from each other via the network 10. The data transmission clients 20-1 to 20-n all have the same configuration. Hereinafter, an arbitrary one is referred to as a data transmission client 20.
In the present embodiment, words such as a client and a server are used in accordance with the words of known documents such as Non-Patent Document 1. In general, the data transmission client 20 is called a data transmission device that transmits data, and the database server 30 is called a data reception device that receives data.

In the present embodiment, the data transmission client 20 first divides a file to be transferred into chunks, and transfers only the chunk 100 that is not owned by the database server 30, thereby speeding up data transfer.
Hereinafter, in order to clarify the explanation, data obtained by dividing a file in accordance with a known document such as Non-Patent Document 1 is referred to as a chunk. Since the substance of the chunk is only data composed of byte strings, the embodiment described below operates correctly even if the chunk is read as data.

  An outline of main processing in the present embodiment will be described with reference to FIG. Assume that the data transmission client 20 transfers the file 200 to the database server 30.

  First, the data transmission client 20 divides the file 200 into units called chunks (chunking). A specific procedure for chunking will be described later with reference to FIG. In FIG. 2, as a result of chunking, the file 200 is divided into four chunks 202 of chunks 202-1 to 202-4.

  Next, the data transmission client 20 calculates a feature amount for each of the chunks 202-1 to 202-4. The feature amount is a byte string of several bytes to several tens of bytes for approximately obtaining the similarity between chunks. Details will be described later with reference to FIGS. In FIG. 2, the feature amount 204 of the chunk 202-3 is obtained as an example. The feature amount 204 is transmitted to the database server 30.

  The database server 30 collates the received feature quantity 204 with the feature quantity of each owned chunk to calculate the similarity (feature quantity collation processing 210), and identifies a chunk similar to the chunk 202-3. In FIG. 2, chunk 212 was found.

  If a similar chunk exists, the data transmission client 20 is notified of that fact. In response to this, the data transmission client 20 calculates the restored byte string 206 from the chunk 202-3. The restored byte string corresponds to a check byte string of a block code such as a Reed-Solomon code. Chunk restoration is performed by adding a restoration byte string to a similar chunk and performing error correction processing. Details will be described later with reference to FIGS. The database server 30 receives the restored byte string 206 from the data transmission client 20, adds it to the chunk 212, and tries to restore the chunk (chunk restoration processing 220).

  In FIG. 2, the restoration was successful and a chunk 222 was obtained. The database server 30 notifies the data transmission client 20 that the restoration is successful. In response to this, the data transmission client 20 calculates the hash value 208 of the chunk 202-3 and transmits it to the database server 30. The database server 30 collates the received hash value with the hash value of the chunk 222, and if they match, the chunk 202-3 owned by the data transmission client 20 is restored and the transmission of the chunk 202-3 is performed. Is notified to the data transmission client 20 (hash collation processing 230). If the chunk cannot be restored or the hash values do not match, the data transmission client 20 is requested to transfer the chunk 202-3.

  With the above method, the amount of data exchanged on the network is reduced, and the transfer time of the file 200 can be expected to be shortened.

  FIG. 3 is a block diagram illustrating a schematic configuration of the data transmission client. As shown in the figure, the data transmission client 20 includes a CPU 302, a memory 304, a storage device 306, a user interface 308, a communication interface 310, a data transmission unit 32, and a setting unit 330, which mutually communicate information via the internal bus 300. It is designed to send and receive. The data transmitting unit 32 includes a file information collating unit 320, a chunking unit 322, a feature amount calculating unit 324, a restored byte string calculating unit 326, and a hash value calculating unit 328. These devices can transmit / receive information to / from the CPU 302 or the like alone via the internal hub 300.

  First, general-purpose components will be described. The CPU 302 is a central processing unit that performs various numerical calculations, information processing, device control, and the like. The memory 304 is a semiconductor storage device such as a RAM or ROM that can be directly read and written by the CPU 302. The storage device 306 is a device such as a hard disk, a magnetic tape, or a flash memory that stores data and programs in the computer. The apparatus stores a file to be transmitted to the database server 30 and the like.

  The user interface 308 is a device such as a display, a mouse, and a keyboard for outputting a processing result to the user, receiving a user instruction, and reflecting it on each component of the data transmission client 20.

  The communication interface 310 is a device for controlling transmission / reception of data via the network 10 of each component of the data transmission client 20. Control is performed such as establishing a communication path by authenticating with the other party, or disconnecting the communication path after completion of processing, or when the other party does not respond after a certain period of time.

  Constituent elements unique to the present embodiment are a data transmission unit 32, a file information collation unit 320, a chunking unit 322, a feature amount calculation unit 324, a restored byte string calculation unit 326, and a hash value calculation unit 328 that constitute the data transmission unit 32. Among these, the most characteristic components that are not found in the conventional data transfer device are a feature amount calculation unit 324 and a restored byte string calculation unit 326.

  The data transmission unit 32 receives an instruction to transfer a file stored in the storage device 306 to the database server 30 from the user via the user interface 308, and receives a file information collation unit 320, a chunking unit 322, and a feature amount calculation unit 324. , Control the restoration byte string calculation unit 326, the hash value calculation unit 328, etc., and transmit / receive data such as chunks and feature quantities stored in the memory 304 or the storage device 306 to / from the database server 30 via the communication interface 310. It is a device for doing. A series of operation flows of the data transfer process will be described later with reference to FIGS.

  The file information matching unit 320 is a device for confirming whether or not the database server 30 owns the same file before transferring the file to the database server 30. Details will be described with reference to FIGS.

  The chunking unit 322 is a device for reading a file stored in the storage device 306, dividing it into chunks, and temporarily storing it in the memory 304 or the storage device 306. Details of the chunking process will be described later with reference to FIG.

  The feature amount calculation unit 324 is a device that reads a chunk temporarily stored in the memory 304 or the storage device 306, calculates a feature amount, and outputs the feature amount to the memory 304 or the storage device 306. A specific method for calculating the feature amount will be described later with reference to FIGS.

  The restored byte string calculating unit 326 is a device that reads a chunk temporarily stored in the memory 304 or the storage device 306, calculates a restored byte string, and outputs the restored byte string to the memory 304 or the storage device 306. A specific method for calculating the restored byte sequence will be described later with reference to FIG.

  The hash value calculation unit 328 is a device that reads a file or chunk stored in the memory 304 or the storage device 306, calculates a hash value, and outputs the hash value to the memory 304 or the storage device 306. For example, MD5 and SHA-1 are known as hash functions for deriving a hash value.

  The setting unit 330 is an apparatus for setting an upper limit of a waiting time for waiting for a response from the database server 30 and parameters necessary for processing such as chunking and feature amount calculation. These parameters are set by the user via the user interface 308 and reflected in the chunking unit 322, the feature amount calculation unit 324, the restored byte string calculation unit 326, the hash value calculation unit 328, and the like.

  The data transmitting unit 32, the file information collating unit 320, the chunking unit 322, the feature amount calculating unit 324, the restored byte string calculating unit 326, the hash value calculating unit 328, and the setting unit 332 that constitute the data transmitting unit 32, Each apparatus may execute processing alone, or each apparatus may include only a program, and the CPU 302 may read the program into the memory 304 and execute the program.

  FIG. 4 is a block diagram illustrating a schematic configuration of the database server 30. As illustrated, the database server 30 includes a CPU 402, a memory 404, a storage device 406, a user interface 408, a communication interface 410, a data receiving unit 42, a table management unit 430, and a setting unit 432, which are connected via an internal bus 400. Are designed to send and receive information to each other. The data receiving unit 42 includes a file information matching unit 420, a feature amount matching unit 422, a chunk restoration unit 424, a hash value matching unit 426, and a data registration unit 428. These devices can transmit / receive information to / from the CPU 402 or the like alone via the internal hub 400.

  General-purpose components such as the CPU 402, the memory 404, the storage device 406, the user interface 408, and the communication interface 410 have the same functions as those in FIG. Constituent elements unique to the present embodiment are the data receiving unit 42, the file information collating unit 420, the feature amount collating unit 422, the chunk restoring unit 424, the hash value collating unit 426, the data registering unit 428, and the table managing unit. 430. Among these, the most characteristic components that are not included in the conventional data transfer device are a feature amount calculation unit 422 and a chunk restoration unit 424.

  The data receiving unit 42 receives data such as feature quantities and chunks from the data transmission client 20 via the communication interface 410 and temporarily stores them in the memory 404 or the storage device 406. The file information matching unit 420 and the feature quantity matching This is a device for controlling the unit 422, the chunk restoring unit 424, the hash value matching unit 428, etc. to receive or restore the file transferred by the data transmission client 20 and store it in the storage device 406. A series of operation flows of the data transfer process will be described later with reference to FIGS.

  The file information matching unit 420 refers to a list of files (file management table) stored in the storage device 406 in response to a request from the data transmission client 20, and is the same as the file that the data transmission client 20 is to transfer. This is a device for confirming whether a file exists in the storage device 406. A specific example of the file management table will be described later with reference to FIG. If the same file exists, the data receiving unit 42 notifies the data transmission client 20 via the communication interface 310 to that effect. Details will be described later with reference to FIGS.

  The feature amount matching unit 422 receives the feature amount from the data transmission client 20, temporarily stores it in the memory 404 or the storage device 406, and lists a chunk feature amount stored in the storage device 406 (chunk management table). Is a device for collating the received feature value with the feature value of each chunk and identifying similar chunks. A specific example of the chunk management table will be described later with reference to FIG. Details of the feature amount matching processing will be described later with reference to FIGS. The actual data or pointer of the identified similar chunk is temporarily stored in the memory 404 or the storage device 406.

  The chunk restoration unit 424 receives the restored byte sequence from the data transmission client 20 and temporarily stores it in the memory 404 or the storage device 406, and the feature amount matching unit 422 temporarily stores it in the memory 404 or the storage device 406. This is an apparatus that performs chunk restoration processing by adding an error correction to a chunk. Details of the restoration process will be described later with reference to FIG. The chunk that has been successfully restored is temporarily stored in the memory 404 or the storage device 406.

  The hash value matching unit 426 receives the hash value from the data transmission client 20 and temporarily stores it in the memory 404 or the storage device 406, and the chunk restoration unit 424 stores the chunk temporarily stored in the memory 404 or the storage device 406. It is a device that calculates hash values and checks whether they match.

  The data registration unit 428 is a device for storing the chunk received from the data transmission client 20 and the restored chunk in the storage device 406 and updating the file management table, the chunk management table, and the like via the table management unit 430.

The table management unit 430 is a device for monitoring a file operation on the storage device 406 or receiving a call from the data reception unit 42 to update a file management table, a chunk management table, or the like. Specific examples of these management tables will be described later with reference to FIG. These management tables themselves are stored in the memory 404 or the storage device 406.
The setting unit 432 is a device for setting an upper limit of a waiting time for waiting for a response from the data transmission client 20 and parameters necessary for processing such as feature amount matching and hash value calculation. These parameters are set by the user via the user interface 408, and are reflected in the file information matching unit 420, the feature amount matching unit 422, the chunk restoration unit 424, the hash value matching unit 426, the data registration unit 428, and the like.

  The data receiving unit 42, the file information collating unit 420, the feature amount collating unit 422, the chunk restoring unit 424, the hash value collating unit 426, the data registering unit 428, the table managing unit 430, and the setting unit 43 constituting the data receiving unit 42 Each device may execute processing alone, or each device may include only a program, and the CPU 402 may read the program into the memory 404 and execute it.

  A typical data transfer process between the data transmission client 20 and the database server 30 will be illustrated with reference to FIG. The data transmission unit 32 in FIG. 3 and the data reception unit 42 in FIG. 4 perform data transfer via the network 10 in the following procedure.

  (S500) First, a communication path is established between the data transmission client 20 and the database server 30. Specifically, the communication interface 310 of the data transmission client 20 notifies the connection request to the communication interface 410 of the database server 30, and the communication interface 410 allows it to establish a communication path between them. Alternatively, a more secure communication path may be established by exchanging and sharing information such as an encryption method and an encryption key by a standard procedure such as IKE (Internet Key Exchange).

  (S502) The file information collation unit 320 of the data transmission client 20 transmits the file F information 502 that the user has instructed to transfer via the user interface 308 to the database server 30 via the communication interface 310. Here, the file information 502 includes the name, size, creation date and time, hash value, and the like of the file F. The hash value calculation unit 328 calculates the hash value of the file F.

  (S504) The data receiving unit 42 of the database server 30 receives the file information 502 via the communication interface 410 and passes it to the file information collating unit 420. The file information collating unit 420 refers to a list of files (file management table) stored in the storage device 406 and determines whether the same file as the file F exists in the storage device 406 based on the file information 502. Check. A specific example of the file management table will be described later with reference to FIG. Hereinafter, it is assumed that the same file as file F is not owned. The case of possession will be described with reference to FIG.

(S506) The data receiving unit 42 of the database server 30 notifies the data transmission client 20 via the communication interface 410 that the same file is not owned 506.
(S508) The data transmission unit 32 of the data transmission client 20 receives the notification 506 that the same file is not owned via the communication interface 310, and activates the chunking unit 322. The chunking unit 322 reads the file F from the storage device 306 and divides it into chunks. Details of the chunking process will be described later with reference to FIG. Hereinafter, it is assumed that the transfer target file is divided into k chunks Ai (i = 1,..., K).

  (S52) The following processing of S520 to S542 is performed for each chunk Ai (i = 1,..., K). When the processing of S520 to S542 is completed for all chunks Ai, the process jumps to S560.

  (S520) The feature amount calculation unit 324 of the data transmission client 20 calculates the feature amount 522 of the chunk Ai. A specific method for calculating the feature amount will be described later with reference to FIGS.

  (S522) The data transmission unit 32 of the data transmission client 20 transmits the feature quantity 522 obtained in S520 to the database server 30 via the communication interface 310.

  (S524) The data receiving unit 42 of the database server 30 receives the feature quantity 522 via the communication interface 410 and passes it to the feature quantity matching unit 422. The feature amount matching unit 422 refers to the list of chunk feature amounts (chunk management table), compares the feature amount 522 with the feature amount of each chunk, and identifies a chunk similar to the chunk Ai. A specific example of the chunk management table will be described later with reference to FIG. Details of the feature amount matching processing will be described later with reference to FIGS. Hereinafter, it is assumed that a similar chunk Ai ′ is found. The case where it is not found will be described with reference to FIG.

(S526) The data receiving unit 42 of the database server 30 notifies the data transmission client 20 via the communication interface 410 that the similar chunk Ai ′ is owned 526.
(S528) When the data transmission unit 32 of the data transmission client 20 receives the notification 526 indicating that the similar chunk Ai ′ is owned via the communication interface 310, the data transmission unit 32 activates the restored byte string calculation unit 326. The restoration byte string calculation unit 326 calculates the restoration byte string 530 of the chunk Ai. A specific method for calculating the restored byte sequence will be described later with reference to FIG.

  (S530) The data transmission unit 32 of the data transmission client 20 transmits the restored byte sequence 530 obtained in S528 to the database server 30 via the communication interface 310.

  (S532) The data receiving unit 42 of the database server 30 receives the restored byte sequence 530 via the communication interface 410 and passes it to the chunk restoring unit 424. The chunk restoration unit 424 adds the restoration byte sequence 530 to the similar chunk Ai ′ and performs chunk restoration processing. Details of the restoration process will be described later with reference to FIG. In the following, it is assumed that restoration was successful and chunk Bi was obtained. A case where the restoration fails will be described with reference to FIG.

  (S534) The data receiving unit 42 of the database server 30 notifies the data transmission client 20 via the communication interface 410 that the restoration is successful 534.

  (S536) The data transmission unit 32 of the data transmission client 20 receives the notification 534 that the restoration is successful via the communication interface 310, and activates the hash value calculation unit 328. The hash value calculation unit 328 calculates the hash value 528 of the chunk Ai.

  (S538) The data transmission unit 32 of the data transmission client 20 transmits the hash value 528 obtained in S536 to the database server 30 via the communication interface 310.

  (S540) The data receiving unit 42 of the database server 30 receives the hash value 530 via the communication interface 410 and passes it to the hash value matching unit 426. The hash value matching unit 426 calculates the hash value of the chunk Bi and confirms whether or not it matches the hash value 530. Hereinafter, it is assumed that they match. The case where they do not match will be described with reference to FIG.

  (S542) The data registration unit 428 of the database server 30 stores the chunk Bi restored on the database server 30 side (that is, the chunk Ai owned by the data transmission client 20) in the storage device 406, and the chunk stored in the table management unit 430. Bi information is notified to the table management unit 430. The table management unit 430 adds the chunk information to the chunk management table. A specific example of the chunk management table will be described later with reference to FIG.

  (S560) When the processing of S520 to S542 is completed for all chunks Ai, the communication path established in S500 is disconnected.

  (S562) The data receiving unit 42 of the database server 30 notifies the table management unit 430 that file transfer has been completed. In response to this, the table management unit 430 updates the file management table and the like. This completes the data transfer process.

  According to this embodiment, when the database server 30 owns a chunk similar to the chunk that the data transmission client 20 intends to transfer, it can be reproduced on the database server 30 side, and transfer is not necessary. Compared with conventional systems such as Nos. 1 and 2 and Patent Document 1, the total data transfer time can be further shortened.

  In this embodiment, the identity of the file or chunk is confirmed using the hash value, but there is a slight possibility that a “collision” in which the hash value is the same despite the fact that the file or chunk is different. Exists. When a collision occurs, the database server 30 cannot correctly receive or restore the chunk. As a method for suppressing the collision, a method using a plurality of different hash functions can be considered. The probability that multiple hash values collide simultaneously is given by the product of the respective collision probabilities, so it is very small. Since the hash value is at most several tens of bytes, the load on the network is small even if multiple hash values are transmitted. Therefore, this method can reduce the collision probability without imposing a load on the network.

  Further, instead of specifying only one chunk similar to the chunk Ai in S425, a plurality of chunks that give a similarity equal to or higher than a predetermined threshold value may be specified. In this case, the data receiving unit 42 performs the restoration process of S532 on the plurality of chunks. Since it should be only one chunk (which matches the chunk that the data sending client 30 is trying to transfer) that succeeds in the restoration, if the restoration is successful, the processing of S532 is aborted, and the processing after S534 is performed on the restored chunk. . When restoration fails for all the plurality of chunks, the processing described in FIG. 8 is performed.

The processing flow when the database server 30 owns the file F to be transferred by the data transmission client 20 in S504 of FIG. 5 will be described with reference to FIG.
(S500) to (S502) This is the same as the description of FIG.
(S600) The data receiving unit 42 of the database server 30 receives the file information 502 via the communication interface 410 and passes it to the file information collating unit 420. The file information collating unit 420 refers to the file management table and confirms whether the same file as the file F exists in the storage device 406 based on the file information 602. Hereinafter, it is assumed that the same file as file F is owned.

  (S602) The data receiving unit 42 notifies the data transmission client 20 through the communication interface 410 that the same file is owned 602. In response, the data transmission client 20 disconnects the communication path (S560), and the process is completed.

The processing flow when the feature amount matching unit 422 of the database server 30 cannot find a chunk similar to the chunk that the data transmission client 20 is trying to transfer in S524 of FIG. 5 will be described with reference to FIG.
(S500) to (S522) This is the same as the description of FIG.
(S700) Similar to S524, the feature quantity matching unit 422 of the database server 30 refers to the list of chunk feature quantities (chunk management table), collates the feature quantity 522 with the feature quantity of each chunk, and transmits the data transmission client. Identify a chunk that is similar to the chunk that 20 is trying to transfer. In the following, it is assumed that no similar chunk is found.

  (S702) The data reception unit 42 of the database server 30 notifies the data transmission client 20 via the communication interface 410 that the similar chunk 702 is not owned.

  (S704) The data transmission unit 32 of the data transmission client 20 transfers the chunk 704 to be transferred by the data transmission client 20 to the database server 30 via the communication interface 310.

  (S706) The data receiving unit 42 of the database server 30 receives the chunk 704 via the communication interface 410 and passes it to the data registration unit 428. The data registration unit 428 stores the chunk 704 in the storage device 406 and notifies the table management unit 430 of information on the stored chunk. The table management unit 430 adds the chunk information to the chunk management table.

  (S560) to (S562) The same as the description of FIG.

A processing flow when the chunk restoring unit 424 of the database server 30 cannot restore the chunk that the data transmission client 20 is to transfer in S532 of FIG. 5 will be described with reference to FIG.
(S500) to (S530) This is the same as the description of FIG.
(S800) The data receiving unit 42 of the database server 30 receives the restored byte sequence 530 via the communication interface 410 and passes it to the chunk restoring unit 424. The chunk restoration unit 424 performs chunk restoration processing using the restoration byte sequence 530. Hereinafter, it is assumed that restoration has failed.

(S802) The data receiving unit 42 of the database server 30 notifies the data transmission client 20 via the communication interface 410 that the restoration has failed 802.
(S704) to (S706) This is the same as the description of FIG.
(S560) to (S564) This is the same as the description of FIG.

In the case where the hash value of the restored chunk generated by the hash value matching unit 426 of the database server 30 does not match the hash value received from the data transmission client 20 in S540 of FIG. explain.
(S500) to (S538) This is the same as the description of FIG.
(S900) The data receiving unit 42 of the database server 30 receives the hash value 530 via the communication interface 410 and passes it to the hash value matching unit 426. The hash value collating unit 426 calculates the hash value of the chunk restored by the chunk restoring unit 424, and confirms whether or not it matches the hash value 530. Hereinafter, it is assumed that they do not match.

(S902) The data reception unit 42 of the database server 30 notifies the data transmission client 20 via the communication interface 410 that the hash values do not match 902.
(S704) to (S706) This is the same as the description of FIG.
(S560) to (S564) This is the same as the description of FIG.

  5 to 9, when the communication path is disconnected during the data transfer process, or when a predetermined time elapses, no response is made and the communication interfaces 310 and 410 disconnect the communication path. In this case, the data receiving unit 42 stops receiving the file and does not update the file management table 1000 or the file configuration chunk management table 1040. As a result, chunks that do not become constituent elements of any file are accumulated in the storage device 406. In this embodiment, the more the database server 30 owns more chunks, the more effective the data transfer is. Therefore, the storage device 406 takes the position that there is no problem in accumulating chunks that do not constitute any file. The chunk management table that manages only the chunks stored in is decided.

  Of course, when the capacity of the storage device 406 is imminent, it is possible to delete a chunk that is not associated with any file. In this case, the chunk management table needs to be updated via the table management unit 430.

  The data configuration of the file management table 1000, chunk management table 1020, and file configuration chunk table 1040 managed by the table management unit 430 will be described with reference to FIG.

  The file management table 1000 is a list of files stored in the storage device 406 of the database server 30 described with reference to FIGS. The file management table 1000 includes a file ID column 1002 for storing a unique ID of a file, a file name column 1004 for storing a file name, a folder name column 1006 for storing a folder name in which the file is stored, and a byte length of the file. It includes a file size column 1008 for storing, a file creation date / time column 1010 for storing the file creation date / time, a hash value column 1012 for storing the hash value of the file, and the like. These pieces of information are used to determine whether the database server 30 owns the same file as the file transferred by the data transmission client 20. The hash value column 1012 stores a plurality of hash values when determining the identity of a file using a plurality of hash values as described in the explanation of FIG.

  In the example of FIG. 10, the file “manual.doc” with the file ID “1” is stored in the folder “C: \”, the file size is 133,423 bytes, and the file creation date is October 21, 2007. It can be seen that the hash value is given as “0abf016edf” in hexadecimal notation.

  The file management table 1000 is updated by the table management unit 430 when a file is added or deleted on the storage device 406 or when file transfer is completed in S562 in FIG.

  The chunk management table 1020 is a list of chunks stored in the storage device 406 of the database server 30 described with reference to FIGS. The chunk management table 1020 stores a chunk ID column 1022 that stores a unique ID of a chunk, a feature column 1024 that stores a chunk feature, a hash value column 1026 that stores a hash value of the chunk, and a byte length of the chunk. It consists of a chunk size column 1028 and the like. The hash value column 1026 stores a plurality of hash values when the identity is determined using a plurality of hash values as described in the explanation of FIG. Details of chunk similarity determination using feature quantities will be described later with reference to FIGS.

  In the example of FIG. 10, it can be seen that the feature value of the chunk with the chunk ID “0x000001” is given as “AEHgyXIWET / BAQC7PRcRP8EBAFi” in Base64 notation, the hash value is given as “9bac9347ff” in hexadecimal notation, and the chunk size is 1,423 bytes. In order to distinguish it from the file ID, the chunk ID is described as a character string starting with “0x”.

  The chunk management table 1100 is displayed when a chunk is added or deleted on the storage device 406, or when the data registration unit 428 stores the chunk in the storage device 406 in S542 of FIG. 5 or S706 of FIGS. Updated by the table manager 430.

  The file configuration chunk management table 1040 is a list in which information on chunks constituting a file is collected. The file configuration chunk management table 1040 includes a file ID column 1042 for storing a file ID, a file name column 1044 for storing a file name, a folder name column 1046 for storing a folder name in which the file is stored, and a chunk name constituting the file It includes a chunk ID column 1048 for storing a chunk ID, an offset column 1050 for storing information about the offset, the chunk size column 1052 for storing the chunk size, and the like.

  In the example of FIG. 10, the file “manual.doc” with the file ID “1” is stored in the folder “C: \”, and the chunk ID “0x000001” is from the first 1,422 bytes of the file “manual.doc”. It can be seen that the chunks from 1,423 bytes to 2,314 bytes are composed of chunks with chunk ID “0x000002”.

  The file configuration chunk management table 1040 is updated by the table management unit 430 when a file is added or deleted on the storage device 406 or when file transfer is completed in S562 in FIG.

  A specific procedure of file chunking performed by the chunking unit 322 in FIG. 3 will be described with reference to FIG.

  As a simple chunking method, a method of dividing a file by a predetermined fixed length can be considered. However, with this method, if even one byte is inserted at the beginning of the file, the file division point will shift and the chunks will not match. In a known technique such as Non-Patent Document 1, a chunk to be transferred is determined based on the identity of the hash value of the chunk, which is not preferable. Therefore, Non-Patent Document 1 and the like use a method of dividing a file by changing the chunk length. In the present embodiment, either the fixed length method of the chunk length, the variable length method employed in Non-Patent Document 1 or the like, either chunking method may be employed.

In the variable length method, the file 1100 is chunked by performing the following processing as shown in FIG.
(1) The chunking unit 322 scans one byte at a time from the t-th byte of the file 1100, and extracts a partial byte string 1102 of t bytes before the scanning point 1104. t is a small value, for example, 7 in Non-Patent Document 3. In this embodiment, the same value may be taken. When the scan point 1104 is at the pth byte from the beginning, the partial byte sequence 1102 is composed of t byte values from the byte value 1106-1 of the p-t + 1 byte to the byte value 1106-t of the p byte. Is done. Note that the byte value 1106-t of the p-th byte matches the scanning point 1104.
(2) In order to determine whether the scanning point 1104 is a division point for dividing the file 1100 into chunks, a rabin fingerprint 1120 is calculated from the t byte values 1106-1 to 1106-t. The rabin fingerprint 1120 is an inner product of random byte values r1 to rt and a partial byte string 1102. See Non-Patent Document 4 for details of Rabin fingerprint. Hereinafter, the value of the Rabin fingerprint for the partial byte sequence 1102 is written as R.
(3) When the remainder obtained by dividing R by a predetermined value (hereinafter referred to as D) becomes 0, the scanning point 1104 is set as a division point for dividing the file 1100 into chunks (chunking condition 1140).
(4) The chunking unit 322 divides the file 1100 into a plurality of chunks by repeatedly performing the processes (1) to (3) by scanning byte by byte from the t-th byte of the file 1100.

  If the file 1100 is composed of random byte values, the probability that the chunking condition 1140 is satisfied is equal to 1 / D, and the chunk has an average length D. However, since the distribution of byte values in the file 1100 is actually biased, it cannot always be broken down into chunks of length D. Rabin fingerprints are often used in chunking because they are less prone to chunk length deviation and can be calculated at high speed. Non-patent document 5 details mathematical analysis such as the chunk length deviation.

  The first feature of the present embodiment is that the database server 30 finds a similar chunk using the chunk feature value. The chunk feature value calculation method and the chunk similarity determination method using the feature value will be specifically described below with reference to FIGS. Specific examples of feature amounts include a fuzzy hash with a high degree of similarity approximation (FIG. 12), a Bloom filter with a small amount of data (FIG. 13), and a trait (FIG. 14) as an improvement.

FIG. 12 is a diagram illustrating an overview of a process for calculating a fuzzy hash from a chunk and a process for calculating a similarity from a fuzzy hash. It is assumed that the file 1200 has been chunked through the chunking process described with reference to FIG. The fuzzy hash of the chunk 1202 in the file 1200 after chunking is obtained by the following procedure.
(1) The feature amount calculation unit 324 of the data transmission client 20 calls the chunking unit 322 to chunk the chunk 1202 more finely. As described in FIG. 11, chunk 1202 can be further chunked by reducing the value of D in chunking condition 1140. Hereinafter, the chunk 1202 further chunked is called a sub chunk. Let d be the number of sub-chunks. In FIG. 12, chunks 1202 are chunked to d = 5, and sub chunks 1204 (S1,..., S5) are obtained.
(2) A hash value is calculated for each of the sub chunks (S1, S2,..., Sd). Let Hash (Si) be the hash value of sub-chunk Si (i = 1, ..., d).
(3) The array of calculated hash values {Hash (Si) | i = 1,..., D} (Hash (S1),..., Hash (Sd)) is a fuzzy hash. In the example of FIG. 12, the fuzzy hash 1206 of the chunk 1202 is given by an array (Hash (S1),..., Hash (S5)) having d = 5 elements.

  Using a fuzzy hash, it is easy to identify which sub-chunk matches. Therefore, if the similarity of chunks is approximated by the ratio of the number of common sub-chunks and the number of elements in the entire sub-chunk, an approximate value of similarity can be calculated at high speed. Specifically, when fuzzy hashes H = (h1, h2, ...) and F = (f1, f2, ...) are given, the similarity is calculated as the number of elements in the intersection of H and F and H Can be approximated by the ratio of the number of elements in the union of F and F.

  In the example of FIG. 12, the chunk 1202 is chunked into the sub chunk 1204 to obtain the fuzzy hash 1206, and the chunk 1212 is chunked into the sub chunk 1214 to obtain the fuzzy hash 1216. Sub-chunk 1214 differs from sub-chunk 1204 in S2 and S2 ′, and there is no sub-chunk corresponding to S5. Since the hash value is different for different chunks, the product set of fuzzy hashes 1206 and 1216 is (Hash (S1), Hash (S3), Hash (S4)), and the union is (Hash (S1), Hash (S2), Hash (S2 '), Hash (S3), Hash (S4), Hash (S5)). Therefore, the similarity between chunks 1202 and 1212 is approximately given by 3/6 = 1/2.

  The fuzzy hash is used for searching similar files. See Non-Patent Document 3 and Patent Document 2 for details.

Since the fuzzy hash needs to hold all the hash values of the sub chunks, the amount of data is large. A Bloom filter is known as a feature amount that greatly reduces the amount of data. The outline of the process for calculating the Bloom filter and the process for calculating the similarity from the fuzzy hash will be described with reference to FIG. As in FIG. 11, it is assumed that the file 1300 is chunked through the chunking process described with reference to FIG. The Bloom filter of the chunk 1302 in the file 1300 after chunking is obtained by the following procedure.
(1) The feature amount calculation unit 324 of the data transmission client 20 calls the chunking unit 322 to chunk the chunk 1302 more finely. Let d be the number of sub-chunks. In the example of FIG. 13, chunks 1302 are chunked to d = 5, and sub-chunks 1304 (S1,..., S5) are obtained.
(2) A hash value is calculated for each sub chunk 1304. Let Hash (Si) be the hash value of sub-chunk Si (i = 1, ..., d).
(3) The logical sum 1306 of all hash values Hash (Si) (i = 1,..., D) is taken. The kth bit of the logical sum of the hash values Hash (S1) and Hash (S2) is 1 if either the kth bit of Hash (S1) or the kth bit of Hash (S2) is 1, both 0 only if it is 0.
(4) If the output of the hash function Hash is L bits, a bit string of length L is obtained in (3). In the example of FIG. 13, a 32-bit bit string is obtained. This is the Bloom filter.

  If there is a common sub-chunk, the bit at the same position is 1. Therefore, if the number of matching bits is counted, the similarity of chunks can be obtained approximately. More specifically, when Bloom filters B = (b1, ..., bL) and D = (d1, ..., dL) are given, the similarity is bi = di (i = 1,. .., L) can be approximated by the number of i divided by L. This is equivalent to taking the logical product of B and D and dividing the number of 0s by L.

  In the above-described fuzzy hash, it is necessary to save all hash values as feature quantities. However, since this Bloom filter takes the logical sum of hash values, there is an advantage that the capacity can be greatly reduced. In addition, since the logical product calculation is fast, there is an advantage that the similarity can be calculated faster than the fuzzy hash. However, generally, even if bits at the same position match, the corresponding sub-chunks do not always match. Therefore, the accuracy of similarity is inferior to that of fuzzy hash.

  In the example of FIG. 12, chunk 1302 is chunked into sub chunk 1304 to obtain Bloom filter 1208, and Bloom filter 1318 is obtained from chunk 1312. The bit length of the Bloom filter is 32 bits, and there are 12 non-matching bits (unmatched bits are underlined), so the similarity is approximately calculated as 12/32 = 3/8.

The Bloom filter is a feature amount that greatly reduces the amount of data, but as described above, the approximation accuracy of the similarity is poor. The trait has improved its accuracy. An outline of processing for calculating a trait from a chunk will be described with reference to FIG. As in FIG. 11, it is assumed that the file 1400 has been chunked through the chunking process described with reference to FIG. The trait of the chunk 1402 in the file 1400 after chunking is obtained by the following procedure.
(1) The feature amount calculation unit 324 of the data transmission client 20 calls the chunking unit 322 to chunk the chunk 1402 more finely. Let d be the number of sub-chunks. In the example of FIG. 14, chunks 1402 are chunked into five, and subchunks 1404 (S1,..., S5) are obtained.
(2) The hash value calculation unit 328 prepares t types of hash functions Hash_k (k = 1,..., T). In the example of FIG. 14, t = 4 types of hash functions Hash_1,..., Hash_4 are prepared. The feature amount calculation unit 324 calls the hash calculation unit 328 and calculates the hash value by applying t types of hash functions for each sub chunk Si (i = 1,..., D). In the example of FIG. 14, 4 × 5 = 20 hash values Hash_1 (S1),..., Hash_4 (S5) are obtained.
(3) For each k, find the minimum value of d hash values Hash_k (Si) (i = 1,..., D) (k = 1,..., T). In FIG. 14, Hash_1 (S2) has a minimum value 1406-1 for k = 1, and Hash_4 (S4) has a minimum value 1406-4 for k = 4. The minimum value obtained below is called the minimum hash value.
(4) Take the first b bytes from the k minimum hash values. A bit string having a length k × b obtained by concatenating these is a trait. In the example of FIG. 14, the first 7 bits 1408-1 of the minimum hash value 1406-1 and the first 7 bits 1408-4 of the minimum hash value 1406-4 are concatenated.

  The calculation of the similarity is the same as that of the Bloom filter. That is, it is given by the number of matching bits divided by the trait bit length.

  It is known that the trait gives similarities more accurately than the Bloom filter by extracting and concatenating the leading b bits instead of taking the logical sum of the hash values. See Non-Patent Document 6 for details.

  The second feature of the present embodiment is that the chunk that the data transmission client 20 intends to transfer is restored on the database server 30 side using the restored byte sequence. Hereinafter, a process for obtaining a restored byte string from a chunk and a process for restoring a chunk using the restored byte string will be described with reference to FIGS.

  First, the outline of the error correction technology that is the basis of the above processing will be described. Various methods such as block codes and convolutional codes are known for error correction. In this embodiment, block codes are used. The block code calculates a check byte string from information to be transmitted and adds this to add redundancy, thereby enabling decoding on the receiving side with as little error as possible. In general, the error correction technique is composed of a pair of error correction coding processing for obtaining a check byte string and error correction processing for correcting an error occurring in transmitted information.

  A feature of the block code is that the information to be transmitted and the inspection byte string have a fixed length. That is, if the information to be transmitted is k bytes and the inspection byte string is h bytes, the combination of k and h is fixed depending on the type of block code used. This is different from an error correction method such as a convolutional code. In general, the number of bytes that can be corrected increases as the byte length h of the inspection byte sequence is increased. However, the total data (k + h bytes) that must be transmitted increases accordingly, and a network load is applied.

  A Reed-Solomon code is known as one of the block codes having the highest error correction capability. It is known that when the Reed-Solomon code is used and the inspection byte string is h bytes, roughly h / 2 bytes of the total data (k + h bytes) to be transmitted can be corrected. That is, even if the value of h / 2 bytes in the total data changes on the network or the like, the original byte string can be restored by correcting the error. On the other hand, if it changes by more than h / 2 bytes, error correction fails and nothing can be restored, and the result that error correction failed is returned.

  Originally, error correction is a technique that has been conceived to correct errors that occur in a network or the like, but in this embodiment, the chunk A to be transferred by the client and the similar chunk A ′ owned by the server side Considering the difference as an error, an error correction technique is used to restore A from A ′.

FIG. 15 is a diagram illustrating an outline of processing for obtaining a restored byte string from a chunk. The restoration byte string calculation unit 326 of the data transmission client 20 obtains the restoration byte string 1512 from the chunk 1500 by the following procedure.
(1) Parameters and the like of the error correction coding process 1510 are determined in advance via the setting unit 330. The parameters and the like can be freely changed, but need to be combined with error correction processing executed by the chunk restoration unit 424 of the database server 30. This is because the error correction coding process and the error correction process are a pair, and the error correction process cannot be executed correctly with different parameter settings. Hereinafter, the input length of the error correction coding process 1510 is assumed to be k.
(2) Divide the chunk 1500 every k bytes. If the byte length of chunk 1500 is not a multiple of k, padding 1504 is added at the end to make the length a multiple of k. The contents of the padding 1504 may be anything, but it is necessary to share the same generation method with the chunk restoration unit 424 so that the same padding can be obtained. By this division processing, a post-division chunk 1502 is obtained. For example, in FIG. 15, the chunk 1500 is divided into six k-byte sequences with padding 1504 added.
(3) An error correction encoding process 1510 is performed on each k byte string in the divided chunk 1502 to obtain a check byte string. Let h be the length of the inspection byte string. The restored byte sequence 1512 is obtained by concatenating the obtained check byte sequences. In the example of FIG. 15, the length of the restored byte string 1512 is 6h.

  As described above, chunks with different contents can be correctly restored by the number of bytes that is approximately half the length of the restored byte sequence. Therefore, in (1), h should be set as much as possible so as not to be a burden of transmission / reception on the low-bandwidth network. It is preferable to keep large.

FIG. 16 is a diagram illustrating an overview of processing for restoring a chunk using a restored byte sequence. It is assumed that a similar chunk 1600 is found by searching the chunk management table based on the feature amount transmitted from the data transmission client 20. The chunk restoration unit 424 of the database server 30 tries to restore a chunk from the similar chunk 1600 according to the following procedure.
(1) The same parameters as those of the error correction encoding process 1510 are determined in advance via the setting unit 432. Hereinafter, it is assumed that the input length of the error correction encoding process 1510 is k, and the length of the check byte string is h.
(2) Divide chunk 1600 into k bytes. If the byte length of the chunk 1600 is not a multiple of k, padding 1604 is added at the end to make the length a multiple of k. Note that the generation method of the padding 1604 needs to be the same as the padding generation method in the restored byte string calculation unit 326 of the data transmission client 20. By this division processing, a similar chunk 1602 after division is obtained. For example, in FIG. 16, the chunk 1600 is divided into six k-byte sequences with padding 1604 added.
(3) For each k byte string in the divided similar chunk 1602, the restored byte string received from the data transmission client 20 is cut out for each h byte and added as a check byte string. If the check byte sequence cannot be added to all k byte sequences in the similar chunk 1602 after the division, the error correction process cannot be executed, and the process ends as a restoration failure. If the check byte string remains, it is clear that the chunk that the data transmission client 20 is trying to transfer cannot be restored, and thus the process ends as a restoration failure. For example, in FIG. 16, an inspection byte sequence 1608 is added to the byte sequence 1606.
(4) The error correction process 1610 is performed on each byte string of length k + h to which the check byte string is added. If error correction fails for any byte string, the process ends as a restoration failure. For example, in FIG. 16, the byte sequence 1606 is corrected to 1616 and the check byte sequence 1608 is corrected to 1618 by the error correction processing 1610.
(5) Cut and concatenate the first k bytes of each byte sequence subjected to error correction.
(6) The padding 1604 is removed from the end, and a restored chunk 1620 is obtained. This is a candidate for the chunk that the data transmission client 20 intends to transfer.

  A supplementary explanation of the management method for restoration chunks. In the present embodiment, as described with reference to FIG. 4, the chunk restoration unit 424 of the database server 30 stores the restored chunk in the storage device 406. Since the restored byte sequence is shorter than the chunk itself, instead of storing the restored chunk in the storage device 406, by storing only the pair of the chunk ID and the restored byte sequence before restoration, the storage device 406 The amount of data stored in can be reduced.

  Hereinafter, a table for managing a pair of a chunk before restoration and a restored byte string is referred to as a basic chunk management table. FIG. 17 is a diagram illustrating a data configuration of the basic chunk management table 1700. The basic chunk management table 1700 includes a chunk ID column 1702 for storing the ID of the restored chunk, a basic chunk ID column 1704 for storing the ID of the chunk before the restoration, and a restoration byte string for storing the restoration byte string necessary for restoration. It consists of a column 1706 and the like.

  The data registration unit 428 updates the basic chunk management table 1700 via the table management unit 430 at the timing of storing the restored chunk in the storage device 406. A chunk ID is issued to the restored chunk to update the chunk management table 1020 and the file configuration chunk management table 1040, but the actual data is not stored in the storage device 406.

  When an attempt is made to access a chunk configuring a file via the file configuration chunk management table 1040, first, the basic chunk management table 1700 is scanned to check whether the chunk ID of the chunk exists. If there is, restore the chunk using the restored byte sequence. If not, the chunk is acquired from the storage device 406.

  For example, in FIG. 17, it can be seen that the chunk with the chunk ID “0x000001” can be restored from the chunk with the chunk ID “0x003523” using the restoration byte string “f016ed”. According to the file configuration chunk management table 1040 of FIG. 10, the file “manual.doc” is composed of chunks with a chunk ID “0x000001”, and so on. When accessing the file “manual.doc”, the chunk ID “0x000001” In order to generate the chunk “”, it is necessary to restore from the chunk with the chunk ID “0x003523” using the restoration byte string “f016ed”. Since the next chunk “0x000002” does not exist in the basic chunk management table 1700, it is acquired from the storage device 406.

  Whether the actual chunk data is stored in the storage device 406 may be managed by providing a new column in the file configuration chunk management table 1040. In this case, access to the basic chunk management table 1700 is minimized, and the time required for file access can be reduced.

  The system configuration and data transfer method of the present invention have been described above with reference to FIGS. According to this embodiment, when the data transmission client 20 owns a chunk similar to the chunk to be transferred in the database server 30, it can be reproduced on the database server 30 side and transfer is not required. In comparison, the total data transfer time can be shortened.

10: Network
20, 20-1 to 20-n: Data transmission client
30: Database server
100: Chunk
200: File
202, 202-1 to 202-4, 212, 222: Chunk
204: Feature amount
206: Restored byte sequence
208: Hash value
210: Feature verification processing
220: Chunk restoration processing
230: Hash collation processing
300: Internal bus
302: CPU
304: Memory
306: Storage device
308: User interface
310: Communication interface
32: Data transmitter
320: File information verification unit
322: Chunking club
324: Feature amount calculator
326: Restored byte string calculator
328: Hash value calculator
330: Setting section
400: Internal bus
402: CPU
404: Memory
406: Storage device
408: User interface
410: Communication interface
42: Data receiver
420: File information verification unit
422: Feature amount calculation unit
424: Chunk restoration part
426: Hash value verification unit
428: Data registration department
430: File table manager
432: Setting section
502: File information
506: Notification that the same file is not owned
522: Feature value
526: Notification of similar chunk ownership
530: Restored byte sequence
534: Notification of successful restoration
538: Hash value
602: Notification of ownership of the same file
702: Notification of similar chunk not owned
704: Chunk
802: Notification of restoration failure
902: Hash value mismatch notification
1000: File management table
1002: ID column
1004: File name column
1006: Folder name column
1008: File size column
1010: File creation date / time column
1012: Hash value column
1020: Chunk management table
1022: Chunk ID column
1024: Feature column
1026: Hash value column
1028: Chunk size column
1040: File structure chunk management table
1042: File ID column
1044: File name column
1046: Folder name column
1048: Chunk ID column
1050: Offset column
1052: Chunk size column
1100: File
1102: Partial byte sequence
1104: Scanning point
1106-1 to 1106-T: Byte value
1120: Rabin Fingerprint
1140: Chunking conditions
1200, 1300, 1400: File after chunking
1202, 1212, 1302, 1312, 1402: Chunk
1204, 1214, 1304, 1404: Sub-chunk
1206, 1216: Fuzzy hash
1306: OR
1308, 1318: Bloom filter
1406-1, 1406-4: Minimum hash value
1408: Trait
1408-1, 1408-4: First b bits of minimum hash value
1500: Chunk
1502: Chunk after split
1504: Padding
1510: Error correction coding process
1512: Restored byte sequence
1600: Similar chunk
1602: Similar chunk after split
1604: Padding
1606: Byte string
1608: Inspection byte sequence
1610: Error correction processing
1616: Byte sequence after error correction
1618: Inspection byte sequence after error correction
1620: Restore chunk
1700: Basic chunk management table
1702: Chunk ID column
1704: Basic chunk ID column
1706: Restored byte string column

Claims (4)

A data transmission device that transmits a feature amount of the first data, a restored byte sequence for error correction of the first data, and a hash value of the first data to the communication line;
The second data having a feature amount in a range similar to the feature amount received via the communication line among the data already owned is specified, and the second data received via the communication line Perform error correction processing by adding a restored byte sequence, calculate the hash value of the second data after the error correction processing, compare it with the hash value of the first data, and correct the error when they match A data transfer system comprising: a data receiving device that stores second processed data as the first data. In claim 1,
The data transmission device
A feature amount calculation unit for calculating a feature amount of the first data;
A restored byte string calculating unit for calculating a restored byte string capable of error correction of the first data;
A hash value calculation unit for calculating a hash value of the first data,
The data receiving device is
A feature amount matching unit that checks whether the feature amount of data already possessed and the feature amount received via the communication line are in a numerical range predetermined as a similar range;
A restoration unit that performs error correction processing of the second data using the restored byte sequence;
A data transfer system comprising: a hash value collating unit that calculates a hash value of the second data after the error correction process and compares the hash value of the first data. In claim 2,
The data receiving device has no data having a feature amount in a range similar to the feature amount received via the communication line among already owned data, or the same value as the hash value of the first data. If not, send a message to that effect or the first data transmission request to the data transmission device,
The data transmitting apparatus transmits the first data to the data receiving apparatus when receiving the request or the request. A data transmission device that transmits the feature amount of the first data and the restored byte sequence for error correction of the first data to the communication line;
The second data having a feature amount in a range similar to the feature amount received via the communication line among the data already owned is specified, and the second data received via the communication line A data transfer system comprising: a data receiving device that performs error correction processing by adding a restored byte sequence and stores second data after the error correction processing as the first data.

Images