JP4546387B2 - Backup system, method and program - Google Patents

Description

The present invention relates to a backup system, method, and program for distributing and backing up data to a plurality of local storages in preparation for disasters and accidents, and in particular, data to be distributed to local storages is redundantly coded to increase tolerance against failures The present invention relates to a backup system, method, and program.

  Conventionally, there is RAID (Redundant Array of Independent Disks) as a commonly used technique for protecting data on a storage such as a magnetic disk device from a failure or an unexpected accident. RAID levels range from RAID 0 to RAID 6 depending on the application, but typical ones that are used as techniques for improving data security are RAID 1, RAID 5, and RAID 6.

  RAID1 is generally realized by using two disks. This is the simplest method for improving the fault tolerance of a disk by writing the same data to two disks, and is called mirroring.

  FIG. 14 shows a distributed storage system to which RAID 1 is applied. In FIG. 14, local storages 104-1 to 104-3 functioning as distributed storage are connected to the main storage 100 via a network 102. In RAID1, all the local storages 104-1 to 104-3 have the same data 106 as the main storage 100, and all the local storage 104-1 to 104-3 have the same replicated data 106-1 to 106-3 as the data 106 of the main storage apparatus 100. When lost, the lost data 106 can be restored by transferring data from any of the local storages 104-1 to 104-3.

  RAID5 is a method of recording data in a distributed manner on a plurality of disks. A redundant code called parity, which is obtained by adding data at the time of writing, is generated and written simultaneously. Thus, even if any one disk fails, the original complete data can be restored from the data and parity information of the other disks.

  FIG. 15 shows a distributed storage to which RAID 5 is applied. The data in the main storage 100 is divided into data 108 and 110 and a parity 112 is generated and distributedly stored in the local storages 104-1 to 104-3. In this case, for example, even if the data 110 is lost due to a failure of the local storage 104-2, the lost data 110 can be restored from the data 108 and the parity 112 of the local storage devices 104-1 and 104-3.

  RAID6 is an extended version of RAID5, and generates two parities that were one in RAID5. In this way, the original data can be restored even if two disks fail simultaneously. There are several methods for obtaining the second parity, but a Reed-Solomon code is generally used.

  FIG. 16 shows a distributed storage to which RAID 6 is applied. Data in the main storage 100 is divided into data 108 and 110, and parity 112 and 114 are generated and distributedly stored in the local storages 104-1 to 104-4. In this case, for example, even if two pieces of data in the local storages 104-1 to 104-4 are lost due to a failure or the like, the normal two pieces of data and / or lost data from the parity can be restored.

  In addition, as a management method for a conventional distributed storage system, data can be recovered even when a storage failure occurs by providing dual redundancy when storing data in multiple storages. (Patent Document 1).

In addition, as a data storage method using a wide-area distributed storage system, data is distributed and stored in a plurality of storages to improve data security, while taking into account the physical distance between the storages, By selecting a set, the line efficiency and the safety of data at the time of disaster are improved (Patent Document 2).

Japanese translation of PCT publication No. 2004-539446 (Japanese Patent Application No. 2004-539446) JP 2004-126716 A

  However, when backup is performed using the RAID 1 mirroring method to a plurality of conventional local storages that are geographically distributed, a copy of the original data is created locally. There is a problem that the use efficiency of is very bad.

  In RAID 5, the storage utilization efficiency is higher than in RAID 1, but recovery is possible only when one local storage fails, and recovery is impossible when two or more devices fail at the same time.

  Further, since RAID 6 generates two parities, the use efficiency of the disk is lower than that of RAID 5, and because the Reed-Solomon code is used to obtain the second parity, the calculation amount is large. There is a problem.

  On the other hand, in Patent Document 1, when data is stored in a plurality of storages, the data can be recovered even when a failure occurs in the storage by performing double redundancy, and reading is also possible. Although this is a method of speeding up, data recovery is impossible when two or more storage devices fail simultaneously.

  Although the thing of patent document 2 is the method of improving the security of data by distributing and storing data in several storage, since the data amount which each storage stores is the same, the utilization efficiency of storage is bad. There is a problem.

It is an object of the present invention to provide a backup system, method, and program having high resilience against a failure when backup is performed by distributing data to a plurality of local storages.

(system)
The present invention provides a backup system. The backup system of the present invention
A main storage device for storing original data;
A plurality of local storage devices that distribute and store the storage device data; and
An encoding unit that generates a plurality of encoded data equal to or greater than the number of divisions using a variable redundancy code after dividing the original data;
A redundancy control unit for changing the redundancy in the encoding unit;
A distribution processing unit for distributing and storing a plurality of encoded data to a plurality of local storage devices;
A recovery unit that recovers at least the encoded data corresponding to the number of divisions of the original data from the local storage device and restores the original data;
It is provided with.

Here, the encoding unit is
A block division unit for dividing original data into n block data;
A code composed of a header in which a bit map specifying one or more blocks for exclusive OR in n block data is arranged, and exclusive OR data of one or more block data specified by the header Code data generation unit for generating a number m according to redundancy Q,
With
The restoration unit collects encoded data of the number of blocks n or more from a plurality of local storage devices, and restores the n block data by unitizing the header part by a Gaussian elimination method.

The redundancy control unit changes the redundancy in the encoding unit according to the importance of the original data. The redundancy control unit automatically sets the importance of the original data based on the manual setting or the keyword included in the original data, the update date / time, or the update frequency. For example, the redundancy control unit sets the corresponding importance from the keywords included in the original data as automatic importance setting, and then modifies the importance according to the update date and / or update frequency. The number of encoded data distributions is set according to the reliability or usable capacity of a plurality of local storage devices. The distribution control unit automatically sets the importance of the local storage device based on manual setting or operation rate or response time (RTT). For example, the distribution control unit sets the importance of the local storage device according to the operating rate, and then corrects it according to the response time (RTT) of the local storage.

  When a new local storage device is added or deleted, the encoded data is regenerated by the encoding unit based on the changed local storage device and then redistributed by the distribution processing unit.

  The main storage device stores original data in synchronization with the data in the client storage device, and a plurality of local storage devices are connected to the main storage device via a network.

(Method)
The present invention provides a backup method. That is, the present invention relates to a system backup method including a main storage device that stores original data and a plurality of local storage devices that store data in the main storage device in a distributed manner.
An encoding step for generating a plurality of encoded data equal to or greater than the number of divisions using a variable redundancy code after dividing the original data;
A redundancy control step for changing the redundancy in the encoding step;
A distribution processing step for distributing and storing a plurality of encoded data to a plurality of local storage devices;
A recovery step of recovering at least the encoded data corresponding to the number of divisions of the original data from the local storage device and restoring the original data;
It is provided with.

(program)
The present invention provides a backup program. The backup program of the present invention is stored in a computer of a main storage device that stores original data in a distributed manner in a plurality of local storage devices.
An encoding step for generating a plurality of encoded data equal to or greater than the number of divisions using a variable redundancy code after dividing the original data;
A redundancy control step for changing the redundancy in the encoding step;
A distribution processing step for distributing and storing a plurality of encoded data to a plurality of local storage devices;
And restore steps that restore the recovered and original data coded data of the number of divisions of at least the original data from the local storage device,
Is executed.

The details of the backup method and program according to the present invention are basically the same as those of the backup system according to the present invention.

  In the present invention, redundant data is added to the data by an encoding method capable of changing the redundancy (coding rate) so that the data can be recovered even when one or more local storages simultaneously fail. Encoded data is generated and distributed and stored in multiple local storages. Even if a failure or disaster occurs in multiple local storages, the required number of encoded data can be collected from the remaining local storages. If possible, the original data can be recovered, and the reliability of backup by the distributed storage can be improved.

  Further, according to the present invention, when data is encoded, the redundancy rate is increased for important data and the redundancy rate is decreased for less important data. Without increasing the number of data, the encoded data can be efficiently distributed in the local storage and the original data can be backed up.

  In the present invention, the number of encoded data to be distributed to a plurality of local storages is determined according to the reliability of each local storage. The higher the reliability, the more encoded data is distributed and the reliability is low. By reducing the number of encoded data to be distributed, it is possible to minimize the loss of encoded data due to a local storage failure and to collect the required number of encoded data stably for restoring the original data. It is possible to suppress the data redundancy rate while ensuring high reliability.

  In addition, when distributing encoded data to multiple local storages, the number of encoded data to be distributed is dynamically determined according to the difficulty of failure of each local storage (operating rate), usable capacity, etc. Thus, the reliability at the time of failure can be further increased.

Furthermore, with the number of encoded data to be distributed to the local storage (data amount) is variable, high-performance local storage and low-performance local storage, or backup available capacity of many local storage and less local storage It is possible to use the storage system to increase the utilization efficiency of the local storage, facilitate the construction of the backup system, and reduce the cost.

  FIG. 1 is a block diagram of a system functional configuration showing an embodiment of a backup system according to the present invention. In FIG. 1, the backup system according to the present embodiment is constructed to back up the data of the client 14, the main storage server 10 is connected to the client 14, and the client 14 is connected to the main storage 12 of the main storage server 10. Data stored in the storage 16 created by the user, for example, files are stored in the main storage 12 synchronously.

  Local storage servers 20-1 to 20-5 are connected to the main storage server 10 via the network 18, and the local storage servers 20-1 to 20-5 include local storages 22-1 to 22-5, respectively. The local storages 22-1 to 22-5 function as a distributed storage for the main storage 10.

  When the file created and updated by the client 14 is stored in the main storage 12 of the main storage server 10, the user's file stored in the main storage 12 is converted into encoded data using a variable variable code with the original data as the original data. Later, it is distributed and stored in the local storages 22-1 to 22-5. When the main storage server 10 needs to restore the file, it accesses the local storage servers 20-1 to 20-5 via the network 18, collects the encoded data distributed, and restores the original file. To restore.

  The main storage server 10 includes an input / output unit 24, an encoding unit 26, a redundancy control unit 28, an importance management table 30, a distribution processing unit 32, a distribution management table 34, and a restoration unit 36.

  Among these, the basic functions of the main storage server 10 are configured by an encoding unit 26, a distribution processing unit 32, and a restoration unit 36. The encoding unit 26 divides a file serving as the user's original data stored in the main storage 12 into block data having a predetermined number of blocks n, and then codes each block data with a variable redundancy, for example, the present invention. In this case, the data is converted into a random parity stream code (RPS code) composed of a header and XOR data, which will be clarified later, and a plurality of pieces of encoded data having the number of divided blocks or more are generated.

  The distribution processing unit 32 distributes and stores the plurality of pieces of encoded data generated by the encoding unit 26 to the local storages 22-1 to 22-5. The restoration unit 36 collects at least the encoded data corresponding to the number of divided blocks of the file serving as the original data from the local storages 22-1 to 22-5, and restores the original file.

Here, the redundancy control unit 28 changes the redundancy of the encoding process in the encoding unit 26. The redundancy is Q = m / n, where n is the number of block divisions of the original data and m is the number of encoded data generated by the random parity stream code.
It can be expressed as This redundancy Q is the reciprocal of the coding rate R. That is, the coding rate R is the coding rate R = n / m = 1 / Q.
Can be expressed as Here, the redundancy Q is a value of 1 or more, while the coding rate R is a value between 1 and 0.

  Therefore, in the encoding unit 26, based on the redundancy Q set by the redundancy control unit 28, m encodings according to the redundancy Q from the n block data of the file divided as the original data. Data will be generated. Further, the redundancy control unit 28 changes the redundancy Q in the encoding unit 26 according to the importance of the file serving as the original data. That is, the redundancy Q is increased as the importance of the file is higher, and the redundancy is decreased as the importance of the file is lower.

  For example, keywords included in the file can be used to determine the importance of the file. In addition to the keyword, the update date / time and update frequency of the file can be used as the importance.

  In the distribution processing unit 32, the number of encoded data distributions to the local storages 22-1 to 22-5 can be determined according to the reliability of the local storages 22-1 to 22-5. That is, if the reliability of the local storage is high, the distribution number of the encoded data is increased, and if the reliability is low, the distribution is performed so that the distribution number of the encoded data is reduced.

  The reliability of the local storages 22-1 to 22-5 can be set manually or automatically based on the operating rate and response time (RTT). For example, regarding the automatic setting of the reliability of the local storage, first, after determining the reliability from the operating rate, processing is performed to correct the value according to the response time (RTT).

  Furthermore, the distribution number of the encoded data may be determined according to the reliability of the local storage and the usable capacity.

  When the random parity stream code is used as the variable variable redundancy code, the restoration unit 36 collects at least the divided block number n or more from the local storages 22-1 to 22-5 and performs Gaussian elimination. By making the header into a unit matrix, n block data can be restored.

  FIG. 2 is a block diagram of a hardware environment of a computer to which the main storage server 10, the local storage servers 20-1 to 20-5, and the client 14 of FIG. 1 are applied.

  In FIG. 2, a RAM 42, a ROM 44, a hard disk drive 46, a keyboard 50, a mouse 52, a device interface 48 connected to a display 54, and a network adapter 56 are provided for the bus 40 of the CPU 38. In the main storage server 10 of FIG. 1, a processing program for constructing the backup system of this embodiment is stored in the hard disk drive 46, and this processing program is read into the RAM 42 when the computer is started up, and the CPU 38 Will be executed.

  FIG. 3 is an explanatory diagram of the encoding process, the distribution process, and the recovery process for restoration according to the present invention, and FIG. 4 shows the restoration process subsequent to the recovery process of FIG. In the present invention, the encoding unit 26 in FIG. 1 uses a random parity stream code (RPS code) with a variable redundancy Q.

  Random parity stream codes require less computation than Reed-Solomon codes used in RAID 6, and the redundancy Q can be dynamically changed, so that a backup system that distributes data in multiple local storages can be flexibly configured. It is possible to build.

  As shown in FIG. 3, the encoding of the random parity stream code used in the present invention divides a file as the original data 58 into a predetermined number n of blocks to generate block data 60-1 to 60-n. .

  In an actual apparatus, for example, the number of divided blocks n = 1028 and the block size = 1280 bytes are fixedly set. The file capacity determined by the number of divided blocks n and the block size is set as the maximum capacity, and the user file as the original data 58 is stored. To divide. If the user file is smaller than the maximum size of the original data, dummy data is inserted in the empty portion to generate block data with a fixed number of divided blocks n.

  Block data 60-1 to 60-n obtained by dividing the original data 58 into the number of divided blocks n is composed of a header 64 and XOR data 66, and m pieces of encoded data 62-1 to 62-m determined by the redundancy Q. Is converted to

  Taking the encoded data 62-1 as an example, the header 64 is n-bit bitmap data indicating the positions of the divided block data 60-1 to 60-n in the original data 58 used for calculating the XOR data 66. It is. For example, the header 64 of the encoded data 62-1 is “10000... 000”, only the leftmost 1 bit is “1”, and the rest are all “0”.

The XOR data 66 selects one or more corresponding block data from the original data 58 according to the bitmap of the header 64 to calculate an exclusive OR (XOR), and calculates and stores data P1 as the XOR data 66. Yes.

  In this embodiment, as encoded data 62-1 to 62-n corresponding to n block data 60-1 to 60-n, each header 64 is a bit indicating the position of the corresponding block data. Is set to “1” and all others are set to “0”. As a result, only one block data is used in the XOR calculation by the header 64.

  Therefore, P1, P2, P3, P4,... Pn in the XOR data 66 are the same data as the block data BD1, BD2, BD3, BD4,.

  On the other hand, for the remaining encoded data 62- (n + 1) to 62-m exceeding the number of divided blocks n, a bit “1” is set in the header 64 to designate two or more blocks for exclusive OR calculation. For example, the bitmap in the header 64 is randomly generated.

Further, as the bitmap of the header 64 in the encoded data 62- (n + 1) to 62-m, it is desirable to use a numerical value that can be easily converted into a unit matrix at the time of restoration processing, which will be clarified later. As this numerical value, for example, 1111... 111
0101 ... 101
1010 ... 010
0000 ... 111
1111 ... 000
and so on.

  The m pieces of encoded data 62-1 to 62-m generated by the encoding process are stored in the local storages 22-1 to 22-N in a uniform or distributed manner according to the reliability.

  The restoration based on the encoded data distributed in the local storages 22-1 to 22-N performs the recovery 68 of the encoded data to obtain the encoded data 62-1 to 62-k as the recovered data 70. As shown in FIG. 4, the original block data 60-1 to 60 -m can be restored as restored data 74 from the pieces of encoded data.

  The restoration process in FIG. 4 is performed by performing a unit matrixization 72 process by a Gaussian elimination method on the header 64 in the k pieces of encoded data 62-1 to 62-k obtained as the recovered data 70. The block data 60-1 to 60-n can be restored as the original block data BD1 to BDn from the values P1 to Pn corresponding to the XOR data 66 added to the.

  In this restoration process, even if loss of encoded data occurs due to a failure in the local storage 22-3 among the local storages 22-1 to 22-N as shown in FIG. 3, as shown in FIG. If the inverse matrix of the header is obtained by the unit matrixization 72 on the restoration side, the original block data 60-1 to 60-n can be restored.

  That is, in the distributed arrangement of data using the random parity stream code of the present invention and the restoration process by the start of the disappearance of a part of the data, the block data 60-1 to 60- of the original data 58 with the redundancy Q. By generating m encoded data that is several percent more than the division n of n and distributing them, the number of encoded data necessary for restoring the original data is reduced to k. If there are two or more local storages, the original data can be restored if a total of k pieces of encoded data can be collected from the remaining normal local storages.

  Therefore, in the present invention, dynamic redundancy (encoding rate) determination processing is performed according to the importance of data distributed and stored in the local storage.

  Since the number k of encoded data that can restore the original data using the random parity stream code changes according to the number m of encoded data to be generated, the safety of the data when a failure occurs also changes. As the number m of encoded data is increased, the redundancy Q increases and the total capacity of the local storage necessary for the distributed arrangement increases. However, the original data can be restored more reliably. That is, it is possible to adjust the tolerance against a failure by the number m of encoded data.

  Also, since the encoding redundancy Q in the random parity stream code can be changed for each file to be backed up, control is performed so that the redundancy Q is changed according to the importance of the file serving as the original data. That is, it is possible to increase the redundancy Q for important files and increase the tolerance to failures, and reduce the redundancy Q to reduce the tolerance for failures for less important files, thereby reducing the required local storage capacity. .

  Specifically, V1 to Vn are determined in advance as the level of importance for each file as the original data, and the number m of encoded data to be generated is determined according to the following expression according to the predetermined importance Vi. .

  The method of determining the importance Vi for obtaining the number m of encoded data by this equation (1) may be set manually by the user or automatically. As the automatic setting of importance, for example, a keyword is registered corresponding to a file in order to determine the importance of the file, and when the file is encoded, the keyword held by the file and the keyword registered in advance If the corresponding keyword is included in the file, a preset importance is set according to the keyword.

  In this case, if the automatically determined importance level is significantly different from the automatically set importance level by the user, the importance level automatically set by the user is displayed and the user selects one. It may be.

  Furthermore, as the parameter for determining the importance of the file, the last update date of the file, the access frequency, and the like can be used. The update date / time and access frequency of these files may be prepared by setting the importance level independently by using table information, for example, or the importance level determined based on keywords, for example, based on the last update date, access frequency, etc. May be corrected.

  The number m of encoded data set according to the importance of the original data means that the redundancy Q (= m / n) is changed, and the range of the redundancy Q that is changed according to the importance is the redundancy If the value is too large, the amount of data distributed to the local storage increases and the utilization efficiency decreases, so the practical range is, for example, about 1.1 to 1.5.

  FIG. 5 is an explanatory diagram of the importance management table 30 in FIG. 1 for managing the importance of files used for calculating the number n of encoded data. The importance level management table 30-1 in FIG. 5A includes keywords 76 and importance levels 78, and stores any one of keywords W1 to W5 indicating the importance levels in a file. Therefore, when encoding a file, one of the keywords corresponding to the file is extracted, and the corresponding importance is set by referring to the importance official table 30-1.

  The importance level management table 30-2 in FIG. 5B includes a file last update date 80 and an importance level 78. As the last update date 80, for example, less than 3 days, less than 1 week, less than 1 month, Less than 3 months or the like is set, and importance levels V1 to V5 are set correspondingly. The last update date 80 has a higher importance 78 as the last update date is closer.

  The importance level management table 30-3 in FIG. 5C includes an update frequency 82 and an importance level 78. As the update frequency 82, a predetermined update frequency range is set in five stages. The higher the frequency, the higher the importance 78 is set.

  The importance management tables 30-1, 30-2, and 30-3 shown in FIGS. 5A, 5B, and 5C may be used independently to set the importance. After determining the importance level 78 from the keyword 76 of the file using the importance level management table 30-1 in FIG. 5A, if the last update date is near, the value of the importance level 78 set by the keyword 76 is increased. If the update frequency is high, the priority is increased. If the update frequency is low, the importance is decreased. The method of correcting may be used.

  Next, the distribution process of the encoded data based on the reliability of the local storage in the distributed processing unit 32 in FIG. 1 will be described. In conventional RAID and mirroring, a local storage having the same capacity is required to configure a distributed storage. Furthermore, it is desirable that all local storages have the same performance in order to securely store data.

  On the other hand, in this embodiment, in order to restore the original data, it is only necessary to collect k or more encoded data from the local storage, and each local storage stores how many encoded data. It doesn't matter if you have it.

  Therefore, in the distribution processing of the encoded data according to the present embodiment, when the encoded data is distributed to the local storage, a large amount of encoded data is distributed and stored in the highly reliable local storage. A small amount of encoded data is distributed and stored in a low local storage. As a result, it is not necessary to prepare local storage with the same performance, and a backup system using local storage as distributed storage can be constructed at a lower cost.

  FIG. 6 is an explanatory diagram of the distribution result of the encoded data 62 by the main storage server 10 when the reliability of the local storages 22-1 to 22-5 is the same. In this case, for example, encoding is performed by the main storage server 10 The 20 encoded data 62 are equally divided into five local storages 22-1 to 22-5, and five distributed encoded data 94-1 to 94-5 are stored respectively.

  FIG. 7 shows a case in which the reliability of the local storages 22-1 to 22-5 is different. For example, the reliability R1 and R2 of the local storages 22-1, 22-2 are the same and the highest, and then the local storage 22- This is a case where the reliability R3 and R4 of 3,22-4 are the same and next highest, and the reliability R5 of the local storage 22-5 is the lowest.

  In such a case, for the 20 encoded data 62 encoded by the main storage server 10, five distributed encoded data 96 are stored in the local storages 22-1 and 22-2 having the highest reliability R1 and R2. -1 and 96-2 are stored, and the four distributed encoded data 96-3 and 96-4 are stored in the local storages 22-3 and 22-4 of the reliability R3 and R4 having the next highest reliability, For the local storage 22-5 having the lowest reliability R5, two distributed encoded data 96-5 are stored.

  As the reliability for determining the distribution number of the encoded data stored in the local storage in this way, an operation rate value generally used as an index of storage reliability is used. The operating rate Ai is obtained from the average failure time MTBF (Mean Time Between Failure) and the average repair time MTTR (Mean Time To Prepare) by the following equation.

  Here, the average failure time MTBF is an index indicating how many times the failure occurs on average, and is obtained by the following equation.

  The average repair time MTTR represents the time required for repair when a failure occurs, and can be obtained by the following equation.

  Therefore, the reliability Ri of the local storage is a value obtained by the following equation using the operation rate Ai of the equation (2).

  Further, if the number of encoded data generated by encoding is m and the reliability of n local storages is Ri, the number Di of encoded data distributed to the local storage is given by Can be determined.

Here, since the number m of the encoded data generated in the equation (6) can be expressed using the importance Vi of the file serving as the original data according to the equation (1), each local storage is finally obtained. The number D i of encoded data distributed in the above can be expressed by the following equation using the importance Vi of the file and the reliability Ri of the local storage.

  In the above description, the local storage utilization rate Ai is used to determine the reliability Ri of the local storage, but the physical storage between the main storage 12 and the local storages 22-1 to 22-5 is used. The number m of encoded data to be distributed can be determined by RTT (Round Trip Time) which is a distance, capacity Ci usable for backup of local storage, and the like.

  For example, when the physical distance RTT of the local storage with respect to the main storage 12 is used, the local storage reliability Ri calculated by the equation (5) is corrected by the following equation.

  When the usable capacity Ci of the local storage is used, the equation (6) may be replaced with the following equation.

  Furthermore, in the present invention, when the number N of local storages connected to the main storage server 10 via the network 18 is changed, the encoding for the changed local storage is performed according to the above equation (6). The data distribution number Di is recalculated, and the encoded data corresponding to the difference is redistributed.

  FIG. 8 is an explanatory diagram of the distribution management table 34 used for distributing the encoded data to the local storage by the distribution processing unit 32 of FIG. The distribution management table 34 in FIG. 8 is formed with a local storage number 84, an operation rate 90, a reliability 86, and a distribution data number 88. From the operation rate 90 calculated by the equation (2) to the reliability by the equation (5). 86 is obtained, and the distribution data number 88 finally calculated by the equation (6) is stored.

  Further, if necessary, the number of distributed data obtained by the correction of the reliability using the physical distance RRT to the local storage or the calculation by the equation (9) using the usable capacity Ci of the local storage is stored in the table. On the basis of this, the encoded data may be distributed to the local storage.

  FIG. 9 shows the relationship of the number of possible failures with the redundancy rate of the random parity stream code used in this embodiment in comparison with the conventional RAID. In FIG. 9, the horizontal axis represents the data redundancy rate, and the vertical axis represents the number of local storage failures that can be recovered. In this case, the total number N of local storages is 10.

  At this time, in the conventional RAID 5, as indicated by the characteristic point 100, the number of local storages capable of failure is one, and the data redundancy rate is fixed at 1.111. Also for RAID 6, as indicated by the characteristic point 102, the number of local storages that can fail is two, and the data redundancy rate is fixed at 1.25.

  On the other hand, when the random parity stream code in the present embodiment is used, by changing the redundancy rate, the number of possible failures can be changed from 1 to 4 as shown in the characteristic curve 98, It is possible to flexibly deal with local storage failures.

  FIG. 10 is a flowchart of the backup processing of the present invention by the main storage server 10 of FIG. In FIG. 10, the presence or absence of a file save request from the client 14 is checked in step S1, and when the file save request is received, the transfer file from the client 14 is saved in the main storage 12 in step S2. Subsequently, after the storage file encoding process is executed in step S3, a distribution process for distributing the encoded data to the local storages 22-1 to 22-5 is performed in step S4.

  Subsequently, in step S5, it is checked whether there is a configuration change in the local storage, that is, a change in the number of units. If so, the process returns to step S4 to recalculate the number of distributions of the encoded data and encode the difference. Redistribute data.

  If there is no change in the configuration of the local storage, the presence / absence of a file restoration request is checked in step S6. If there is a file restoration request, it is distributed and saved from the local storages 22-1 to 22-5 in step S7. The encoded data is collected, and in step S8, the restoration unit 36 restores the original data file by converting the header into a unit matrix by the Gaussian elimination method. Such processes of steps S1 to S8 are repeated until a stop instruction is issued in step S9.

  Note that the file restoration request in step S6 requires that, for example, a file backed up in the main storage 12 of the main storage server 10 is lost due to a failure or the like, and it is necessary to restore the original data backed up to the main storage 12 by failure recovery. This is the case.

  FIG. 11 is a flowchart of the encoding process in step S3 of FIG. In FIG. 11, in the encoding process, after determining the importance of the file as the original data in step S1, the number m of encoded data is determined in accordance with the formula (1) from the determined importance in step S2. To do.

  Subsequently, in step S3, the file, which is the original data to be processed, is divided into n blocks, for example, n = 1028 blocks, and then headers for the number m of encoded data are generated in step S4. XOR data is generated by extracting a block corresponding to 1 and calculating an exclusive logical ring. In step S6, the header and the XOR data are combined to generate encoded data.

Then check whether generates m pieces of encoded data in step S 7, unless generated returns to step S5, in the same way for the next header to generate encoded data, when generates m Then, the encoding process is terminated and the process returns to the main routine of FIG.

  FIG. 12 is a flowchart of importance determination processing used in the encoding processing in step S1 of FIG. In FIG. 12, in the importance level determination process, the importance level Vuser set by the user by the client 14 is fetched in step S1, and the automatic setting importance level V is initialized to V = 0 in step S2.

  Subsequently, in step S3, it is checked whether or not there is a keyword in the file to be processed. If there is a keyword, an importance management table 30-1 as shown in FIG. Refer to and acquire the importance V corresponding to the keyword.

  Subsequently, in step S5, it is checked whether or not the file last update date is new. If it is new, the process proceeds to step S6, and the importance V acquired in step S4 is increased by a predetermined amount or a predetermined ratio. On the other hand, if the file update date is old, the process proceeds to step S7, and the importance level V is decreased by a predetermined amount or a predetermined ratio.

  In step S8, it is checked whether the data update frequency is high. If the update frequency is high, the importance level V is corrected to increase in step S9. If the update frequency is low, correction is made to reduce the importance in step S10.

  Subsequently, in step S11, the importance level Vuser set by the user is compared with the importance level V automatically determined by the processing in steps S3 to S10. If it is determined in step S12 that both are significantly different, in step S13. The importance automatically determined is displayed on the screen of the client 14, the user is confirmed, and the importance is confirmed in step S14. If the difference between the two is not large, the importance is determined as it is in step S14.

  FIG. 13 is a flowchart of the encoded data distribution process in step S4 of FIG. In FIG. 13, in the distribution process of encoded data, the operation rate Ai of the local storage is obtained by the calculation of the equation (2) in step S1, and the reliability Ri of the local storage is calculated from the equation (5) in step S3. To do.

  Subsequently, in step S3, it is checked whether or not there is a correction due to the physical distance RTT from the main storage 12 to each local storage. If there is a correction, the process proceeds to step S4, and a response time RTTi to the local storage is obtained. Then, the reliability Ri is calculated by the above equation (8).

  Subsequently, in step S6, it is checked whether or not there is a correction due to the usable capacity of the local storage. The number of encoded data Di to be transmitted to the local storage is calculated from the degree Ri and the usable capacity Ci.

  On the other hand, if there is no correction due to the local storage usable capacity in step S6, the process proceeds to step S9, and the distribution number Di of the encoded data is calculated from the reliability Ri by the previous term (6). Note that the number of encoded data distributions in steps S8 and S9 is calculated based on the importance Vi of the file serving as the original data as shown in equation (7), instead of the encoded data number m in equation (6). You may make it calculate from a type | formula.

  The present invention also provides a backup program executed by the computer of the main storage server 10 of FIG. 1, which has the contents shown in the flowcharts of FIGS. 10, 11, 12 and 13.

  The present invention also provides a computer-readable recording medium storing a backup program, which includes a portable storage medium such as a CD-ROM, floppy disk (R), DVD disk, optical disk, and IC card. In addition to a recording device such as a hard disk provided inside and outside the computer system, it includes a database for holding a program via a line, or another computer system and its database, and further a transmission medium on the line.

In the present embodiment, the number of block divisions n is fixed and the number m of encoded data is determined according to the importance Vi of the original data, as shown in equation (1). Although Q (= m / n) is changed, the number of block divisions n is changed according to the importance of the original data, n = G (Vi)
You may decide as. This relationship increases the number of block divisions as the importance of the original data increases.

  In this case, by setting the redundancy Q as a fixed value in the range of 1.1 to 1.5, for example, if the block division number n is determined according to the importance Vi, the encoded data number m is fixedly set. The redundancy Q is determined uniquely.

  Further, the present invention includes appropriate modifications that do not impair the object and advantages thereof, and is not limited by the numerical values shown in the above embodiments.

Here, the features of the present invention are enumerated as follows.
(Appendix)

(Appendix 1)
A main storage device for storing original data;
A plurality of local storage devices for distributing and storing data of the main storage device;
After dividing the original data, an encoding unit that generates a plurality of encoded data equal to or greater than the number of divisions using a variable variable redundancy;
A redundancy control unit for changing redundancy in the encoding unit;
A distribution processing unit for distributing and storing the plurality of encoded data to the plurality of local storage devices;
A restoration unit that recovers at least the encoded data corresponding to the number of divisions of the original data from the local storage device and restores the original data;
A backup system characterized by comprising: (1)

(Appendix 2)
In the backup system described in Appendix 1,
The encoding unit is
A block division unit for dividing original data into n block data;
Consists of a header in which a bitmap designating one or more blocks to be exclusive ORed in the n block data is arranged, and exclusive OR data of one or more block data designated in the header part Code data generation unit for generating the encoded data to be generated by a number m corresponding to the redundancy Q;
With
The restoration unit collects encoded data of the number of blocks n or more from the plurality of local storage devices, and restores the n block data by unitizing the header part by Gaussian elimination. A backup system characterized by (2)

(Appendix 3)
In the backup system of Appendices 1, wherein said redundancy control unit, the backup system and changing the encoding unit definitive redundancy in accordance with the importance of the original data.

(Appendix 4)
In the backup system according to attachment 3, the redundancy control unit manually sets the importance of the original data, or automatically sets the importance according to a keyword, update date / time, or update frequency included in the original data. A featured backup system.

(Appendix 5)
In the backup system according to appendix 4, the redundancy degree control unit sets the corresponding importance degree from the keyword included in the original data as the importance degree automatic setting, and then sets the importance degree according to the update date and / or the update frequency. A backup system characterized by correcting the importance.

(Appendix 6)
In the backup system according to appendix 1, the distribution processing unit determines the distribution number of the plurality of encoded data according to reliability and / or usable capacity of the plurality of local storage devices. Backup system.

(Appendix 7)
In the backup system according to Note 6, wherein the content distribution processing unit, the backup system, which comprises automatically set based on the reliability of the local storage device, a manual setting or operation rate or response time (RTT) .

(Appendix 8)
In the backup system according to appendix 6, the distribution control unit sets the importance of the local storage device according to the operating rate and then corrects it according to the response time (RTT) of the local storage. And backup system.

(Appendix 9)
In the backup system of Appendices 1, wherein when the local storage device is newly added or deleted, based on the local storage device of the changed the distribution processing after regenerating the encoded data by the encoding unit A backup system characterized by redistribution by department .

(Appendix 10)
In the backup system according to appendix 1, the main storage device stores the original data in synchronization with data of a client storage device, and the plurality of local storage devices are connected to the main storage device via a network. A backup system characterized by

(Appendix 11)
In a system backup method comprising: a main storage device that stores original data; and a plurality of local storage devices that distribute and store data of the storage device.
An encoding step of generating a plurality of encoded data equal to or greater than the number of divisions using a variable redundancy code after dividing the original data;
A redundancy control step for changing the redundancy in the encoding step;
A distribution processing step of distributing and storing the plurality of encoded data to the plurality of local storage devices;
A recovery step of recovering at least the encoded data corresponding to the number of divisions of the original data from the local storage device and restoring the original data;
A backup method characterized by comprising: (3)

(Appendix 12)
In the backup method described in appendix 11,
The encoding step includes
A block dividing step for dividing the original data into n block data;
Composed the n and header arranged a bitmap that specifies one or more blocks taking the exclusive OR in the block data, the exclusive OR data of one or a plurality of block data designated by the header A code data generation step for generating the encoded data by a number m corresponding to the redundancy Q;
With
The restoring step recovers the n block data by collecting encoded data of the number of blocks n or more from the plurality of local storage devices and unitizing the header step by a Gaussian elimination method. A backup method characterized by this. (4)

(Appendix 13)
The backup method according to claim 11, wherein the redundancy control step changes the redundancy in the encoding step according to the importance of the original data.

(Appendix 14)
In the backup method according to attachment 13, in the redundancy control step, the importance of the original data is manually set, or automatically set based on a keyword, update date / time, or update frequency included in the original data. A featured backup method.

(Appendix 15)
The backup method according to appendix 11, wherein the distribution processing step determines the distribution number of the plurality of encoded data according to reliability and / or usable capacity of the plurality of local storage devices. How to back up.

(Appendix 16)
In the backup method according to attachment 11, when the local storage device is newly added or deleted, the distribution processing step is performed after regenerating the encoded data in the encoding step based on the changed local storage device. A backup method characterized by redistribution in

(Appendix 17)
In the computer of the main storage device that stores the original data distributed to multiple local storage devices,
An encoding step of generating a plurality of encoded data equal to or greater than the number of divisions using a variable redundancy code after dividing the original data;
A redundancy control step for changing the redundancy in the encoding step;
A distribution processing step of distributing and storing the plurality of encoded data to the plurality of local storage devices;
A recovery step of recovering at least the encoded data corresponding to the number of divisions of the original data from the local storage device and restoring the original data;
A backup program characterized by causing (5)

(Appendix 18)
In the backup program described in Appendix 17,
The encoding step includes
A block dividing step for dividing the original data into n block data;
Consists of a header in which a bitmap designating one or more blocks to be exclusive ORed in the n block data is arranged, and exclusive OR data of one or more block data specified in the header step A code data generation step for generating the encoded data by a number m corresponding to the redundancy Q;
With
The restoring step recovers the n block data by collecting encoded data of the number of blocks n or more from the plurality of local storage devices and unitizing the header step by a Gaussian elimination method. A backup program characterized by

(Appendix 19)
In the backup program according to appendix 17, the redundancy control step includes manually setting the importance of the original data or automatically setting based on a keyword, update date / time, or update frequency included in the original data. A featured backup program.

(Appendix 20)
The backup program according to appendix 17, wherein the distribution processing step determines the distribution number of the plurality of encoded data according to reliability and / or usable capacity of the plurality of local storage devices. Backup program.

1 is a block diagram of a system functional configuration showing an embodiment of the present invention. 1 is a block diagram of a hardware environment of a computer to which the server of FIG. 1 is applied. Explanatory drawing of the encoding process by this invention, a distribution process, and the collection process for a restoration | restoration Explanatory drawing of the restoration process following the collection process of FIG. Explanatory drawing of the importance management table of FIG. Explanatory diagram of distribution processing evenly distributed to local storage Explanatory drawing of distribution processing distributed to local storage according to reliability Explanatory drawing of the distribution management table of FIG. Characteristic diagram of redundancy rate and possible number of failures in encoded data and RAID according to the present invention Flow chart of backup processing according to the present invention Flowchart of encoding process in step S3 of FIG. Flowchart of importance determination processing in step S1 of FIG. Flowchart of distribution processing in step S4 of FIG. Explanatory drawing of conventional distributed storage using RAID1 Explanatory drawing of conventional distributed storage using RAID5 Explanatory drawing of conventional distributed storage using RAID6

Explanation of symbols

10: main storage server 12: main storage 14: client 16: storage 18: network 20-1 to 20-5: local storage server 22-1 to 22-5: local storage 24: input / output unit 26: encoding unit 28 : Redundancy control unit 30, 30-1 to 30-3: Importance management table 32: Distribution processing unit 34: Distribution management table 36: Restoring unit 38: CPU
42: RAM
44: ROM
46: hard disk drive 48: device interface 50: keyboard 52: mouse 54: display 56: network adapter 58: original data 60-1 to 60-n: block data 62, 62-1 to 62-m: encoded data 64: Header 66: XOR data 68: Collection 70: Collection data 72: Unit matrix 74: Restore data 76: Keyword 78: Importance 80: Last update date 82: Update frequency 84: Local storage number 86: Reliability 88: Distribution data Numbers 94-1 to 94-5, 96-1 to 96-5: Distribution coding data

Claims (3)

A main storage device for storing original data;
A plurality of local storage devices for distributing and storing data of the main storage device;
Said original data after dividing the, sign-unit for generating a plurality of sign-data of more than division number using a variable code redundancy,
A redundancy control section for changing the redundancy in the sign-section corresponding to the importance of the original data,
A distribution processing unit of the plurality of the sign-data, to be stored by distributing to the plurality of local storage devices,
A restoration unit for restoring the original data at least said recovered number of divisions of the sign-data of the original data by unit matrix header portion by Gaussian elimination from the local storage device,
Bei to give a,
The encoding unit includes:
A block division unit for dividing original data into n block data;
A header in which a bitmap specifying one or a plurality of blocks to be exclusive ORed in the n block data is arranged, and one or a plurality of blocks specified in the header part by a number m corresponding to the redundancy Q A code data generation unit that generates encoded data composed of exclusive OR data of data;
With
The backup system is characterized in that the restoration unit restores the n block data by collecting encoded data of the block number n or more from the plurality of local storage devices .
In a system backup method comprising a main storage device for storing original data and a plurality of local storage devices for distributing and storing data of the main storage device,
After dividing the original data, and sign-of generating a plurality of sign-data of more than division number using a variable code redundancy,
A redundancy control step of changing corresponding redundancy to the importance of the original data in the sign-step,
A distribution processing step of said plurality of sign-data, to be stored by distributing to the plurality of local storage devices,
A restoration step of restoring the original data and the recovered at least sign-coded data of the original data the number of divisions by unit matrix header portion by Gaussian elimination from the local storage device,
With
The encoding step includes:
A block dividing step for dividing the original data into n block data;
A header in which a bitmap specifying one or a plurality of blocks to be exclusive ORed in the n block data is arranged, and one or a plurality of blocks specified in the header part by a number m corresponding to the redundancy Q A code data generation step for generating encoded data composed of exclusive OR data of the data;
With
In the backup method , the restoring step restores the n block data by collecting the encoded data of the block number n or more from the plurality of local storage devices .
In the computer of the main storage device that stores the original data distributed to multiple local storage devices,
After dividing the original data, and sign-of generating a plurality of sign-data of more than division number using a variable code redundancy,
A redundancy control step of changing corresponding redundancy to the importance of the original data in the sign-step,
A distribution processing step of said plurality of sign-data, to be stored by distributing to the plurality of local storage devices,
A restoration step of restoring the original data and the recovered at least sign-coded data of the original data the number of divisions by unit matrix header portion by Gaussian elimination from the local storage device,
And execute
The encoding step includes:
A block dividing step for dividing the original data into n block data;
A header in which a bitmap specifying one or a plurality of blocks to be exclusive ORed in the n block data is arranged, and one or a plurality of blocks specified in the header part by a number m corresponding to the redundancy Q A code data generation step for generating encoded data composed of exclusive OR data of the data;
With
The restoration step, the backup program characterized by restoring the n pieces of block data by collecting sign-data of more than the number of blocks n from the plurality of local storage devices.

Images