JP7804186B2 - Storage control program, storage control method, and storage control device - Google Patents

Description

The present invention relates to a storage control program, a storage control method, and a storage control device.

Storage services that provide storage space over a network, such as online storage services and cloud storage services, are becoming more common. There are also storage gateways that function as gateways between such storage services and customer computers.

For example, a storage gateway has been proposed that relays write data between a customer's computer and external storage such as cloud storage. This storage gateway accepts data write requests on a file-by-file basis from the customer's computer, deduplicates the data requested to be written, and transfers the deduplicated data to external storage on an object-by-object basis.

Furthermore, with regard to data deduplication technology, for example, a storage device has been proposed that, when merging multiple chunks containing identical data, transfers the reference count corresponding to one chunk to the other chunk. Furthermore, with regard to data storage technology for storage, for example, an information processing system has been proposed that classifies file sets that have relatively similar word frequencies and write times in the same cluster and stores them on a common tape medium.

Japanese Patent Application Laid-Open No. 2019-95925 JP 2017-45177 A JP 2018-190393 A

By the way, one type of storage service is one that provides archive storage suitable for long-term data storage. The storage gateway described above may also use archive storage as the external storage for storing data. In this case, for example, a dataset for archive storage containing one or more objects is generated, and this dataset is stored in the archive storage as a unit.

Furthermore, defragmentation of datasets stored in archive storage is performed, for example, using the following procedure: A first dataset with many chunks with a reference count of "0" is identified from among the datasets, and the first dataset is retrieved and deleted from the archive storage. Valid chunks with a reference count other than "0" are extracted from the retrieved dataset, and a new second dataset is generated (reconstructed) using the extracted chunks and stored in the archive storage.

However, when defragmentation processing using this procedure is repeated, cases may arise in which a newly generated dataset is stored in archive storage by defragmentation, and then deleted from archive storage shortly thereafter. In this case, the number of chunks with a reference count of "0" increases early in a dataset that has been reconstructed and stored in archive storage, and the dataset is retrieved for reconstruction and deleted from archive storage.

In archive storage, a minimum storage period for datasets is set for the purpose of long-term storage, and additional fees may be incurred if a dataset is deleted before the minimum storage period has elapsed. As mentioned above, if a dataset generated by defragmentation and stored in archive storage is deleted in a short period of time, additional fees may be incurred for the deletion, which is a problem.

In one aspect, the present invention aims to provide a storage control program, a storage control method, and a storage control device that can prevent data from being deleted from external storage in a short period of time.

In one proposal, a computer obtains multiple chunks by eliminating duplicates from multiple split datasets obtained by splitting each of multiple files for which writing is requested, and generates multiple storage datasets by combining two or more chunks selected from the multiple chunks.When a storage request for a first file of the multiple files is received, the computer identifies one or more first storage datasets including chunks referenced by the first file of the multiple chunks, stores the one or more first storage datasets in external storage, and increases the reference count associated with the chunk referenced by the first file of the multiple chunks by the number referenced by the split dataset included in the first file of the multiple split datasets.When a deletion request for a second file of the multiple files is received, the computer decreases the reference count associated with the chunk referenced by the second file of the multiple chunks by the number referenced by the split dataset included in the second file of the multiple split datasets. a storage control program for executing a process to identify one or more first chunks referenced by files among a plurality of files for which storage in external storage has been requested within a recent fixed period from among a plurality of storage datasets stored in external storage, acquire them from the external storage, generate one or more second chunks each having the same data as the one or more first chunks, assign one or more second chunks to the reference numbers corresponding to each of the one or more first chunks, respectively, and update the reference numbers corresponding to each of the one or more first chunks to zero, combine the one or more second chunks to generate a new storage dataset and store it in the external storage, and, if a second storage dataset in which the reference numbers corresponding to all chunks in the corresponding storage dataset are zero is detected from among the storage datasets stored in external storage and the new storage dataset among the plurality of storage datasets, delete the second storage dataset from the external storage.

In addition, one proposal provides a storage control method in which a computer executes processing similar to the processing based on the above-mentioned storage control program.
Furthermore, in one proposal, a storage control device is provided that executes processing similar to the processing based on the above-mentioned storage control program.

On the one hand, it can prevent data from being deleted from external storage in a short period of time.

1 illustrates a configuration example and a processing example of a storage system according to a first embodiment; FIG. 10 illustrates an example of a configuration of an information processing system according to a second embodiment. FIG. 2 illustrates an example of the hardware configuration of a cloud storage gateway. FIG. 2 is a diagram illustrating an example of the configuration of processing functions provided in a cloud storage gateway. FIG. 10 is a diagram illustrating an example of the data configuration of a chunk map table. FIG. 10 is a diagram illustrating an example of the data configuration of a chunk management table. FIG. 10 is a diagram illustrating an example of object generation. FIG. 10 is a diagram illustrating an example of the data configuration of a chunk group management table. FIG. 10 is a diagram illustrating an example of the data configuration of a defragmentation determination table. FIG. 1 is a first diagram illustrating an example of data storage processing for object storage and archive storage. FIG. 2 is a second diagram illustrating an example of data storage processing for object storage and archive storage. FIG. 3 is a third diagram illustrating an example of data storage processing for object storage and archive storage. FIG. 10 is a first diagram showing a comparative example of defragmentation processing. FIG. 11 is a second diagram showing a comparative example of defragmentation processing. FIG. 11 is a first diagram illustrating an example of defragmentation processing according to the second embodiment. FIG. 11 is a second diagram illustrating an example of defragmentation processing according to the second embodiment. FIG. 10 is a third diagram illustrating an example of defragmentation processing according to the second embodiment. 10 is a first example of a flowchart illustrating a procedure for a file writing process. 10 is a second example of a flowchart illustrating a procedure for a file writing process. 10 is an example of a flowchart illustrating a procedure for a data storage process in archive storage. 10 is an example of a flowchart illustrating a procedure for deleting data from archive storage. 10 is a first example of a flowchart illustrating a procedure for defragmentation processing. 10 is a second example of a flowchart illustrating a procedure for defragmentation processing.

Hereinafter, an embodiment of the present invention will be described with reference to the drawings.
First Embodiment
1 is a diagram showing an example of the configuration and processing of a storage system according to a first embodiment. The storage system shown in FIG.

The storage control device 1 performs control processes such as storing data in the external storage 2, retrieving data from the external storage 2, and deleting data stored in the external storage 2 in response to requests from, for example, a client device (not shown). The storage control device 1 is, for example, a computer having a processor (not shown). In this case, the above control processes are realized, for example, by the processor executing a program.

External storage 2 is a storage area connected externally to storage control device 1. External storage 2 is suitable for long-term data storage, but not for short-term data storage. For example, a minimum data storage period is set for external storage 2, and if data is deleted from external storage 2 before the minimum storage period has elapsed since the data was stored, additional charges will be incurred.

The processing of the storage control device 1 will be described below.
The storage control device 1 acquires multiple chunks by eliminating duplicates from multiple split data sets obtained by dividing each of multiple files requested to be written. The storage control device 1 also generates multiple storage data sets by combining two or more chunks selected from the acquired multiple chunks. In the example of FIG. 1 , chunks CK1 to CK9, ..., CK21, and CK22 are acquired from m files FL1 to FLm. Furthermore, n storage data sets AC1 to ACn are generated from chunks CK1 to CK9, ..., CK21, and CK22.

In Figure 1, each split dataset contained in files FL1 to FLm is labeled with the symbol of the corresponding chunk. For example, file FL1 is split into four split datasets, which correspond to chunks CK1, CK2, CK3, and CK4, respectively. File FL2 is split into four split datasets, which correspond to chunks CK1, CK5, CK3, and CK6, respectively. It can be seen that split datasets with the same content corresponding to chunks CK1 and CK3 overlap between files FL1 and FL2.

In addition, each chunk from which duplicates have been removed is associated with a reference number. The reference number indicates how many of the split data sets of the file stored in external storage 2 reference the corresponding chunk. The initial value of the reference number is "0".

When the storage control device 1 receives a storage request for a first file of multiple files, it identifies one or more stored datasets that include chunks referenced by this first file. The storage control device 1 stores the identified one or more first stored datasets in the external storage 2. At the same time, the storage control device 1 increases the reference count corresponding to the chunks referenced by the first file by the number referenced by the split datasets included in this first file.

For example, when a request is made to store file FL1, the storage control device 1 identifies storage dataset AC1, which includes chunks CK1 to CK4 referenced by file FL1, and stores storage dataset AC1 in external storage 2. At the same time, the storage control device 1 increases the reference counts corresponding to chunks CK1 to CK4 by the number of references from split datasets included in file FL1. For example, because chunk CK1 is referenced by one split dataset within file FL1, the reference count corresponding to chunk CK1 is increased by "1". As a result, the reference count corresponding to chunk CK1 becomes "1".

Let's assume that a request to store files FL1 to FLm in external storage 2 is made using this procedure, and all of the saved data sets AC1 to ACn containing chunks corresponding to files FL1 to FLm are stored in external storage 2. At this point, let's assume that the reference counts corresponding to chunks CK1 to CK9 are "8", "1", "3", "1", "6", "2", "4", "1", and "1", respectively. Also, let's assume that the reference counts corresponding to chunks CK21 and CK22 are "1" and "1", respectively.

Furthermore, when the storage control device 1 receives a request to delete a second file, it decrements the reference counts corresponding to chunks referenced by this second file by the number of references from the split data sets included in the second file. For example, suppose a request is made to delete files FL1 and FL2. In this case, as shown in Figure 1, the storage control device 1 updates the reference counts corresponding to chunks CK1 to CK6 referenced by files FL1 and FL2 from "8", "1", "3", "1", "6", and "2" to "6", "0", "1", "0", "5", and "1", respectively.

The storage control device 1 also identifies one or more chunks from among the storage datasets AC1 to ACn stored in the external storage 2 that are referenced by files that have been requested to be stored in the external storage 2 within a certain recent period. When the storage control device 1 identifies chunks that satisfy these conditions, it acquires the identified chunks from the external storage 2.

In Figure 1, as an example, it is assumed that chunks CK1, CK5, and CK7 have been identified as chunks that satisfy the above conditions. The storage control device 1 obtains chunks CK1, CK5, and CK7 by, for example, retrieving stored dataset AC1, which includes chunks CK1 and CK5, and stored dataset AC2, which includes chunk CK7, from external storage 2.

The storage control device 1 generates new chunks CK1', CK5', and CK7' that contain the same data as the acquired chunks CK1, CK5, and CK7, respectively. At this time, the storage control device 1 replaces the reference counts corresponding to the original chunks CK1, CK5, and CK7 with the new chunks CK1', CK5', and CK7', respectively. In the example of Figure 1, the reference count "6" for chunk CK1 is replaced with chunk CK1', the reference count "5" for chunk CK5 is replaced with chunk CK5', and the reference count "4" for chunk CK7 is replaced with chunk CK7'. The storage control device 1 also updates the reference counts corresponding to the original chunks CK1, CK5, and CK7 to "0."

Although not shown, the storage control device 1 updates the information indicating the correspondence between the file and the original chunks CK1, CK5, and CK7 to indicate the correspondence between the file and the new chunks CK1', CK5', and CK7'. For example, if the original chunk CK1 is associated with a certain split data set of a certain file, the chunk corresponding to this split data set is updated to the new chunk CK1'.

The storage control device 1 then combines the new chunks CK1', CK5', and CK7' to generate a new storage dataset ACx, and stores this storage dataset ACx in the external storage 2. On the other hand, the storage datasets AC1 and AC2 that contain chunks CK1, CK5, and CK7 that satisfy the above conditions simply have their reference numbers changed as described above, and continue to be stored in the external storage 2.

Furthermore, when the storage control device 1 detects a storage dataset in which the reference count for all chunks in the corresponding storage dataset is "0" from among the storage datasets AC1 to ACn stored in the external storage 2 and the new storage dataset ACx, it deletes this storage dataset from the external storage 2. However, when the storage dataset ACx is stored in the external storage 2 as described above, a storage dataset in which the reference count for all chunks is "0" is not detected.

After this, although not shown, suppose a request is made to delete files FL3 and FL4. In this case, the storage control device 1 reduces the reference counts corresponding to the chunks referenced by files FL3 and FL4 by the number referenced by the split data sets contained in files FL3 and FL4. As a result of this process, the reference counts corresponding to chunks CK3, CK6, CK8, and CK9 each become "0."

As a result, the reference counts of all chunks contained in storage datasets AC1 and AC2 become "0," and the storage control device 1 deletes storage datasets AC1 and AC2 from external storage 2. Meanwhile, storage dataset ACx, which has just been stored in external storage 2, remains stored without being deleted.

Here, a comparative example of defragmentation processing when a request to delete files FL1 and FL2 is received will be described.
In this comparative example, when a file deletion request results in a storage dataset with many chunks whose reference count is "0," the storage dataset is extracted. Then, of the chunks in the extracted storage dataset, a new storage dataset is generated from only those chunks whose reference count is not "0," and the new storage dataset is stored in the external storage 2. Meanwhile, the extracted storage dataset is deleted from the external storage 2.

For example, after the reference counts are updated in response to a request to delete files FL1 and FL2, storage dataset AC1 is identified as the storage dataset with the largest number of chunks with a reference count of "0." Then, storage dataset AC1 is extracted, and a new storage dataset is generated from chunks CK1, CK3, CK5, and CK6, whose reference counts are not "0," and stored in external storage 2. Meanwhile, storage dataset AC1 is deleted from external storage 2.

Next, when a request is made to delete files FL3 and FL4, the reference counts of chunks CK3 and CK6 become "0." In this case, the newly stored stored dataset is identified as the stored dataset with the largest number of chunks with a reference count of "0," and is extracted and deleted from external storage 2. In this way, in the comparative example, stored datasets are likely to be deleted shortly after being stored in external storage 2.

In contrast, the storage control device 1 of this embodiment does not delete from the external storage 2 the stored dataset AC1, which now has many chunks with a reference count of "0" after the reference count is updated in response to a deletion request for files FL1 and FL2. Instead, the storage control device 1 identifies chunks CK1, CK5, and CK7 that are referenced by files that have been requested to be stored in the external storage 2 within the most recent fixed period.

The storage control device 1 generates new chunks CK1', CK5', and CK7' that contain the same data as the identified chunks CK1, CK5, and CK7, respectively. At this time, the reference numbers corresponding to the original chunks CK1, CK5, and CK7 are replaced with the reference numbers corresponding to the new chunks CK1', CK5', and CK7', respectively, and the reference numbers corresponding to the original chunks CK1, CK5, and CK7 are updated to "0." The storage control device 1 then combines the new chunks CK1', CK5', and CK7' to generate a new storage dataset ACx, and stores this storage dataset ACx in the external storage 2.

The stored storage dataset ACx contains only chunks referenced by files requested to be stored in external storage 2 within a recent fixed period, so the reference count for each chunk is unlikely to reach "0" in a short period of time. For this reason, storage dataset ACx is unlikely to be deleted early after being stored in external storage 2. On the other hand, storage dataset AC1, which contains the original chunks CK1, CK5, and CK7, will continue to be stored in external storage 2 until the reference counts for all chunks reach "0." For this reason, storage dataset AC1 is also unlikely to be deleted early after being stored in external storage 2.

In this way, the storage control device 1 of this embodiment can prevent data from being deleted from the external storage 2 in a short period of time.
Second Embodiment
Next, an example will be described in which an archive storage is used as the external storage 2 in FIG. 1 and a cloud storage gateway is used as the storage control device 1 in FIG.

Figure 2 is a diagram showing an example configuration of an information processing system according to the second embodiment. The information processing system shown in Figure 2 includes a cloud storage gateway 100, a NAS (Network Attached Storage) client 210, and a cloud storage system 220. The cloud storage gateway 100 is connected to the NAS client 210 via a network 231, and is also connected to the cloud storage system 220 via a network 232. The network 231 is, for example, a LAN (Local Area Network), and the network 232 is, for example, a WAN (Wide Area Network).

Cloud storage system 220 provides cloud storage services via network 232. Cloud storage system 220 provides object storage 221 and archive storage 222 as cloud storage areas. In object storage 221, data is managed on an object-by-object basis. For example, object storage 221 is implemented as a distributed storage system. On the other hand, archive storage 222 is a storage area suitable for long-term data storage.

The cloud storage system 220 accepts a request to store an object in the object storage 221 from a service client (here, the cloud storage gateway 100), and stores the object in the object storage 221. The cloud storage system 220 also accepts a designation of an object to be stored in the archive storage 222 from among the objects stored in the object storage 221, and stores the designated object in the archive storage 222. Data storage in the archive storage 222 is performed in units of archives containing one or more objects. For example, when multiple objects are designated to be stored in the archive storage 222, an archive containing these multiple objects is created, and the archive is stored in the archive storage 222. Note that objects stored in the archive storage 222 may be deleted from the object storage 221.

For both object storage 221 and archive storage 222, fees are incurred when storing and retrieving data. As mentioned above, archive storage 222 is suitable for long-term data storage. For this reason, for example, archive storage 222 has a minimum archive storage period, and an additional fee is incurred if an archive is deleted before the minimum storage period has elapsed.

Although not shown, the cloud storage system 220 includes a server device that receives access requests to the object storage 221 and archive storage 222 and performs processes such as access control to each storage. These processes may be distributed and performed by multiple server devices.

The NAS client 210 recognizes the cloud storage gateway 100 as a NAS server that provides a storage area managed by a file system. This storage area is provided by the cloud storage system 220. The NAS client 210 then requests the cloud storage gateway 100 to read and write data on a file-by-file basis, for example, according to the NFS (Network File System) protocol or the CIFS (Common Internet File System) protocol. In other words, the NAS server function of the cloud storage gateway 100 allows the NAS client 210 to use the storage area of the cloud storage system 220 as a large-capacity virtual network file system.

The NAS client 210, for example, executes backup software for data backup. In this case, the NAS client 210 backs up files stored in the NAS client 210 or files stored on a server (e.g., a business server) connected to the NAS client 210 to a storage area provided by the NAS server.

The cloud storage gateway 100 is an example of the storage control device 1 shown in Figure 1. The cloud storage gateway 100 relays data transferred between the NAS client 210 and the cloud storage system 220.

For example, the cloud storage gateway 100 receives a file write request from the NAS client 210 using its NAS server function, and caches the file requested to be written internally. The cloud storage gateway 100 divides the file requested to be written into chunks, and stores the actual data in the chunks (chunk data) in the object storage 221. At this time, a predetermined number of chunk data are grouped to generate an object, and the generated object is transferred to the object storage 221.

In addition, when the cloud storage gateway 100 caches a file from the NAS client 210, it divides the file into chunks and performs "deduplication" to prevent duplicate chunk data of the same content from being stored. Furthermore, chunk data may be stored in a compressed state. For example, cloud storage services may charge based on the amount of data stored. By performing deduplication and data compression, it is possible to reduce the amount of data stored in the storage area within the cloud storage system 220 and suppress service usage costs.

Furthermore, the cloud storage gateway 100 accepts a request from the NAS client 210 to store data in the archive storage 222. This storage request is accepted, for example, using a GUI (Graphical User Interface) or API (Application Programming Interface) provided by the cloud storage gateway 100. This storage request is accepted on a file-by-file basis. When the cloud storage gateway 100 accepts the specification of a file to be stored in the archive storage 222, it identifies objects that include chunk data contained in the file that is not stored in the archive storage 222. The cloud storage gateway 100 requests the cloud storage system 220 to store the identified object in the archive storage 222. In response to this request, the identified object is read from the object storage 221 and stored in the archive storage 222.

Figure 3 shows an example hardware configuration of a cloud storage gateway. The cloud storage gateway 100 is realized, for example, as a computer such as that shown in Figure 3.

The cloud storage gateway 100 includes a processor 101, a RAM (Random Access Memory) 102, a HDD (Hard Disk Drive) 103, a GPU (Graphics Processing Unit) 104, an input interface (I/F) 105, a reading device 106, and a communication interface (I/F) 107.

The processor 101 provides overall control over the entire cloud storage gateway 100. The processor 101 is, for example, a CPU (Central Processing Unit), an MPU (Micro Processing Unit), a DSP (Digital Signal Processor), an ASIC (Application Specific Integrated Circuit), or a PLD (Programmable Logic Device). The processor 101 may also be a combination of two or more elements of a CPU, MPU, DSP, ASIC, or PLD.

RAM 102 is used as the main storage device of cloud storage gateway 100. RAM 102 temporarily stores at least a portion of the OS (Operating System) program and application programs executed by processor 101. RAM 102 also stores various data necessary for processing by processor 101.

HDD 103 is used as a secondary storage device for cloud storage gateway 100. The HDD 103 stores the OS program, application programs, and various data. Note that other types of non-volatile storage devices, such as SSDs (Solid State Drives), can also be used as secondary storage devices.

A display device 104a is connected to the GPU 104. The GPU 104 displays images on the display device 104a in accordance with instructions from the processor 101. Examples of the display device 104a include a liquid crystal display and an organic EL (electroluminescence) display.

An input device 105a is connected to the input interface 105. The input interface 105 transmits signals output from the input device 105a to the processor 101. Examples of the input device 105a include a keyboard and a pointing device. Examples of pointing devices include a mouse, touch panel, tablet, touchpad, and trackball.

A portable recording medium 106a is detachably attached to the reading device 106. The reading device 106 reads data recorded on the portable recording medium 106a and transmits it to the processor 101. Examples of the portable recording medium 106a include an optical disc and semiconductor memory.

The communication interface 107 transmits and receives data to and from other devices via a network 107a.
The above hardware configuration can realize the processing functions of the cloud storage gateway 100. The NAS client 210 can also be realized as a computer having the same hardware configuration as that shown in FIG.

Figure 4 shows an example configuration of the processing functions of a cloud storage gateway. The cloud storage gateway 100 includes a storage unit 110, a file input/output unit 120, a deduplication processing unit 130, and a cloud communication unit 140.

The memory unit 110 is a storage area allocated in a storage device provided in the cloud storage gateway 100, such as the RAM 102 or HDD 103. The processing of the file input/output unit 120, deduplication processing unit 130, and cloud communication unit 140 is realized, for example, by the processor 101 executing a predetermined program.

The memory unit 110 stores a directory table 111, a chunk map table 112, a chunk management table 113, a chunk group management table 114, and a defragmentation judgment table 115. In addition, part of the memory area of the memory unit 110 is used as a data cache 116.

Directory table 111 is management information for representing the directory structure in a file system. Directory table 111 registers records corresponding to directories (folders) in the directory structure or files within a directory. Each record registers an inode number to identify the directory or file. Furthermore, for example, the relationship between directories and between directories and files is expressed by registering the inode number of the parent directory in each record.

The chunk map table 112 is management information for managing the correspondence between files and deduplicated chunks. The chunk management table 113 is management information for managing the correspondence between chunks and objects and chunk groups, the number of references to chunks, hash keys corresponding to chunks, etc. A chunk group is a group of chunks included in one or more objects (in this embodiment, for example, a predetermined number of objects greater than or equal to two).

The chunk group management table 114 is management information for managing, for each chunk group stored in the archive storage 222, the number of valid chunks indicating valid chunks among the chunks included in the chunk group, and the number of invalid chunks indicating invalid chunks. The defragmentation determination table 115 is management information for managing, for each archive group, the number of valid chunks indicating valid chunks among the chunks included in that group, and the number of invalid chunks indicating invalid chunks. The chunk group management table 114 and defragmentation determination table 115 are used to determine whether defragmentation is required for objects stored in the archive storage 222.

The data cache 116 is a storage area for caching deduplicated chunks. Chunk data corresponding to a file requested to be written by the NAS client 210 is deduplicated and temporarily stored in the data cache 116, and then incorporated into an object and stored in the object storage 221. When the capacity of the data cache 116 decreases due to the storage of chunks, chunks that have already been stored in the object storage 221 and are infrequently accessed by the NAS client 210 are deleted from the data cache 116.

The file input/output unit 120 performs interface processing as a NAS server. For example, the file input/output unit 120 accepts file read/write requests and file storage requests to the archive storage 222 from the NAS client 210, requests the deduplication processor 130 to perform processing according to the request, and responds to the NAS client 210.

The cloud communication unit 140 performs communication processing with the cloud storage system 220 in response to a request from the deduplication processing unit 130. For example, the deduplication processing unit 130 uploads objects to the object storage 221 and downloads objects from the object storage 221. The cloud communication unit 140 also sends requests to the cloud storage system 220 to store objects in the archive storage 222 and to retrieve archives from the archive storage 222.

The deduplication processor 130 performs processing to store the actual data of a file with duplicates eliminated. The deduplication processor 130 includes a duplication determination unit 131, a chunk management unit 132, and a defragmentation processor 133.

The duplication determination unit 131 divides the actual data of the file for which writing is requested into chunks, and stores the divided actual data in the data cache 116 while eliminating duplicates.
The chunk management unit 132 generates an object by aggregating a plurality of chunks stored in the data cache 116 by the duplication determination unit 131 to an appropriate size. The chunk management unit 132 stores the generated object in the object storage 221 via the cloud communication unit 140. In this embodiment, as an example, an object is generated from a predetermined number of chunks.

The defragmentation processing unit 133 monitors chunks (invalid chunks) that are no longer referenced due to a file deletion request stored in the archive storage 222, and defragments objects stored in the archive storage 222 based on the monitoring results. In this embodiment, defragmentation is a process for deleting invalid chunks that have occurred from the archive storage 222, thereby reducing the amount of space used by the archive storage 222.

Next, the management information used in the deduplication process will be described with reference to FIGS.
Fig. 5 is a diagram showing an example of the data configuration of a chunk map table. The chunk map table 112 is management information for managing the correspondence between files and deduplicated chunks. As shown in Fig. 5, the chunk map table 112 registers records each having the following fields: file number, offset, size, and chunk number. Each record is associated with one chunk generated by dividing the actual data of the file.

The file number indicates the file's identification number. The offset indicates the offset from the beginning of the file to the beginning of the chunk. The size indicates the size of the chunk. The offset and size values identify the chunk's area in the file.

The chunk number indicates the identification number of a deduplicated chunk corresponding to a chunk in a file. If the data content is the same between a first chunk in a file and a second chunk in the same file or another file, the same chunk number is registered in the record corresponding to the first chunk and the record corresponding to the second chunk. For example, in Figure 5, the same chunk number "ck1" is registered in the record of the chunk identified by file number "f1" and offset "o1", and the record of the chunk identified by file number "f2" and offset "o14". This indicates that the data content is the same between the former chunk and the latter chunk, and that this data is stored in the data cache 116 or cloud storage system 220 as the chunk with chunk number "ck1".

Figure 6 shows an example of the data structure of a chunk management table. The chunk management table 113 is management information for managing the correspondence between deduplicated chunks and objects and chunk groups, the number of references to chunks, and the hash keys corresponding to chunks. As shown in Figure 6, the chunk management table 113 stores records having the following fields: chunk number, object number, offset, size, chunk group number, number of references (1), hash key, number of references (2), archive number, and archive storage date and time. Each record is associated with one deduplicated chunk.

The object number indicates the identification number of the object to which the chunk belongs. The offset indicates the offset from the beginning of the object to the beginning of the chunk. The size indicates the size of the chunk. The offset and size values identify the chunk's area within the object.

The chunk group number indicates the identification number of the chunk group to which the chunk belongs. A chunk group contains chunks contained in a predetermined number of objects. In this embodiment, the chunk group is the unit of data transfer between the cloud storage system 220.

The reference count (1) indicates how many of the chunks generated by dividing the file reference the chunk indicated by the chunk number. In other words, the reference count (1) indicates how many chunks in the file overlap the chunk indicated by the chunk number. For example, if the reference count (1) corresponding to a certain chunk number is "2," then there will be two records in the chunk map table 112 that have the same chunk number value registered.

In the example of Figure 5, the file with file number "f1" is divided into two chunks, and the file with file number "f2" is divided into four chunks. Also, in the example of Figure 6, the data of the two chunks contained in the former file and the data of the first two chunks of the chunks contained in the latter file are stored in the cloud storage system 220 as chunks belonging to the object with object number "ob1".

A hash key is a hash value calculated based on the chunk's data. The hash key is used to search for chunks with the same data as the chunk in the file being requested to be written.

7 is a diagram showing an example of object generation, and the object generation method will be described with reference to this FIG.
Table 113a shown in Fig. 7 is obtained by extracting from the chunk management table 113 the chunk number and object number items of records corresponding to chunks belonging to the object with object number "ob11". Similarly, table 113b shown in Fig. 7 is obtained by extracting from the chunk management table 113 the chunk number and object number items of records corresponding to chunks belonging to the object with object number "ob12". Furthermore, table 113c shown in Fig. 7 is obtained by extracting from the chunk management table 113 the chunk number and object number items of records corresponding to chunks belonging to the object with object number "ob13".

When a NAS client 210 requests the writing of a new file or the updating of an existing file, the duplication determination unit 131 divides the actual data of the file into chunks. In the example of Figure 7, the actual data of file f11 is divided into eight chunks, and the actual data of file f12 is divided into five chunks.

To simplify the explanation, we will assume that the data in these chunks is all different (non-overlapping). For this reason, the chunk data obtained by dividing file f11 is assigned individual chunk numbers "ck11" to "ck18," and the chunk data obtained by dividing file f12 is assigned individual chunk numbers "ck19" to "ck23." The chunk data corresponding to chunk numbers "ck11" to "ck23" (chunks ck11 to ck23) is stored individually in data cache 116.

Each chunk is assigned an object number for the object, and that object number is registered in the chunk management table 113. In addition, in this embodiment, when the number of chunks assigned to the same object number reaches a predetermined number, the object number is counted up, and the next chunk is assigned the incremented object number. In this way, a predetermined number of chunks are assigned to the same object.

Note that the state of an object whose number of chunks has not yet reached a predetermined number will be called "active" and ready to accept the next chunk. An active object is an incomplete object that is not ready to be stored in object storage 221. Also, the state of an object whose number of chunks has reached a predetermined number will be called "inactive" and unable to accept the next chunk. Inactive objects are objects that are ready to be stored in object storage 221, and are transferred to object storage 221 at a predetermined time. In practice, when a predetermined number of inactive objects have been created, these objects are transferred together as a chunk group to object storage 221.

In the example in Figure 7, chunks ck11 to ck15 are first assigned to the object with object number "ob11" (object ob11). At this stage, the number of chunks contained in object ob11 reaches a predetermined number (five in the example in Figure 7), and object ob11 becomes inactive. Then, the next chunk, ck16, is assigned a new object number, "ob12."

After this, chunks ck16 to ck20 are assigned to the object with object number "ob12" (object ob12), and at this stage object ob12 becomes inactive. The next chunk, ck21, is then assigned a new object number, "ob13." In the example in Figure 7, chunks ck21 to ck23 are assigned to the object with object number "ob13" (object ob13), but at this stage object ob13 is active. In this case, the next chunk created (not shown) will be assigned object number "ob13."

By following the above procedure, when an object is created when a file is written, a new object is created each time a certain number of chunks are newly created through deduplication. Objects are assigned object numbers in the order in which they are created. Chunks with consecutive chunk numbers are also assigned to a single object.

The above Figure 7 describes a case where there is no data duplication. For example, if a chunk in a file for which writing is subsequently requested contains data with the same content as any of chunks ck11 to ck23, the data for that chunk will not be newly stored in the data cache 116, nor will it be transferred to the cloud storage system 220. In other words, no actual data will be written to this chunk, and only metadata for associating the file with the stored chunks will be written to the chunk map table 112. In this way, a "deduplication process" is performed to prevent duplicate data from being stored.

In this embodiment, an object is deactivated when a predetermined number of chunks are assigned to it. However, as an alternative, for example, an object may be deactivated when the total size of the chunks assigned to the object exceeds a predetermined size.

The description will be continued below with reference to FIG.
The reference count (2) indicates how many chunks, among the chunks generated by dividing a file stored in archive storage 222, reference the chunk indicated by the chunk number. In other words, the reference count (2) indicates the number of references from files stored in archive storage 222, out of the reference count (1).

The archive number indicates the identification number of the archive containing the chunk. The archive number is registered when the object containing the chunk is stored in archive storage 222.

The archive storage date and time indicates the date and time when the file referencing the chunk was stored in archive storage 222. A chunk can be referenced by multiple files, but the archive storage date and time is the date and time when the file referencing the chunk was most recently stored in archive storage 222. Therefore, when the reference count (2) is incremented, the archive storage date and time is also updated.

Next, the management information used to determine whether defragmentation is necessary will be described with reference to FIGS. 8 and 9. FIG.
8 is a diagram showing an example of the data configuration of the chunk group management table. In the chunk group management table 114, a record corresponding to that chunk group is created each time the chunk group is stored in the archive storage 222. In each record, the chunk group number, the number of valid chunks, and the number of invalid chunks are registered.

The chunk group number indicates the identification number of the chunk group. The number of valid chunks indicates the number of chunks contained in the chunk group whose reference count (2) is 1 or greater. The number of invalid chunks indicates the number of chunks contained in the chunk group whose reference count (2) is 0.

Figure 9 shows an example of the data structure of a defragmentation judgment table. In the defragmentation judgment table 115, a record is created for each archive group that contains a predetermined number of archives. An archive group contains a predetermined number of archives in the order in which they were created. In the example of Figure 9, the archive group contains 10 archives.

Each record in the defragmentation judgment table 115 registers an archive number, the number of valid chunks, and the number of invalid chunks. The archive number indicates the identification number of the archive included in the archive group. The number of valid chunks indicates the number of chunks included in each archive in the archive group that have a reference count (2) of 1 or more. The number of invalid chunks indicates the number of chunks included in each archive in the archive group that have a reference count (2) of 0.

Next, an example of data storage processing in the object storage 221 and archive storage 222 will be described with reference to FIGS.
10 is a first diagram showing an example of data storage processing in object storage and archive storage. In the example of Fig. 10, it is assumed that the NAS client 210 requests the cloud storage gateway 100 to write files F1 and F2 in that order.

Let's say that file F1 is split into chunks A to D using variable-length chunking, and that file F1 is split into chunks A, E, C, and F. Here, we assume that the data in chunks assigned the same alphabetical character has the same content. For example, chunk A split from files F1 and F2 both contains the same data. In other words, the data in chunk A is duplicated between files F1 and F2.

When a request is made to write such files F1 and F2, chunks A to F are stored one by one in the data cache 116 through deduplication processing. Furthermore, the reference counts (here, reference count (1)) corresponding to chunks A to F are "2", "1", "2", "1", "1", and "1", respectively.

Also, in Figure 10, as an example, three chunks are assigned to an object. In this case, object O1 is generated from chunks A to C, and object O2 is generated from chunks D to F. Objects O1 and O2 are then transferred from the cloud storage gateway 100 to the object storage 221 using a PUT command.

Furthermore, suppose that the NAS client 210 subsequently requests the cloud storage gateway 100 to store files F1 and F2 in archive storage 222. In this case, objects O1 and O2 containing chunks referenced by files F1 and F2 are identified. An archive A1 containing these objects O1 and O2 is then generated, and archive A1 is stored in archive storage 222. Furthermore, the reference count (2) of chunks A to F contained in archive A1 is set to the same value as the reference count (1).

Figure 11 is a second diagram showing an example of data storage processing for object storage and archive storage. In the example of Figure 11, after the processing of Figure 10, the NAS client 210 requests the cloud storage gateway 100 to write files F3 and F4 in sequence.

Let's assume that file F3 has been split into chunks A, C, E, G, and F using variable-length chunking, and file F4 has been split into chunks A, E, G, H, and I. Of these, chunks A, C, and E are already stored in data cache 116, so only the reference counts (1) for chunks A, C, and E are incremented. That is, the reference counts (1) for chunks A, C, and E are updated to "4," "3," and "3," respectively. Meanwhile, chunks G to I are newly stored in data cache 116, and the reference counts (1) corresponding to chunks G to I become "2," "1," and "1," respectively. Furthermore, object O3 is generated from chunks G to I, and object O3 is transferred to object storage 221.

Then, suppose that the NAS client 210 requests the cloud storage gateway 100 to store files F3 and F4 in archive storage 222. In this case, object O3 is identified, which includes chunks G, H, and I that are not stored in archive storage 222 among the chunks referenced by files F3 and F4. An archive A2 is then generated that includes this object O3, and archive A2 is stored in archive storage 222. Furthermore, the reference count (2) of chunks G to I included in archive A2 is set to the same value as the reference count (1).

FIG. 12 is a third diagram illustrating an example of data storage processing in the object storage and archive storage.
10 and 11, it is assumed that a write request up to the m-th file Fm is made from the NAS client 210 to the cloud storage gateway 100. In addition, it is assumed that chunks A to M are generated accordingly, and multiple objects including chunks A to M are transferred to the object storage 221.

Furthermore, suppose that the NAS client 210 requests the cloud storage gateway 100 to store all files up to file Fm in the archive storage 222. As a result, archives from the first archive A1 to the nth archive An are stored in the archive storage 222. At this time, the reference counts (1) of chunks A to M are "8", "1", "3", "1", "6", "2", "4", "1", "1", "1", and "1", respectively. Also, suppose that the reference counts (2) of chunks A to M are all the same as the reference count (1).

Note that, because the data cache 116 has a capacity limit, chunks (objects) that have already been transferred to the cloud storage system 220 are deleted from the data cache 116. Here, it is assumed that chunks A to M have been deleted from the data cache 116. However, management information for chunks A to M, such as reference counts (1) and (2), remains in the memory unit 110 of the cloud storage gateway 100. Furthermore, of the objects that have been transferred to the object storage 221, objects that have been stored in the archive storage 222 may also be deleted from the object storage 221. Here, it is assumed that all objects generated based on files F1 to Fm have been deleted from the object storage 221.

Next, we will explain the case where defragmentation processing is performed on data stored in archive storage 222 from the state shown in Figure 12. First, we will explain a comparative example of defragmentation processing using Figures 13 and 14, and then we will explain defragmentation processing in the second embodiment using Figures 15 to 17.

Fig. 13 is a first diagram showing a comparative example of defragmentation processing, and Fig. 14 is a second diagram showing a comparative example of defragmentation processing.
Services that provide object storage 221 and archive storage 222 generally do not provide a command for deleting only part of the data area within an object. Therefore, in the comparative example of defragmentation processing shown in Figures 13 and 14, the following procedure is executed: an object including invalid chunks is acquired, the invalid chunks are removed, the object is reconstructed, and the reconstructed object is then stored as an archive in archive storage 222. Note that in Figures 13 and 14, only reference count (1) is used as the reference count, and reference count (2) is not used.

In Figure 13, it is assumed that the NAS client 210 requests the cloud storage gateway 100 to delete files F1 and F2 from archive storage 222. For example, when the period during which files F1 and F2 need to be stored on the user side (NAS client 210 side) has ended, a request is made to delete files F1 and F2 from archive storage 222.

In this case, the reference count (1) of each chunk contained in files F1 and F2 is decremented, and objects containing a certain number of chunks whose reference count (1) has become "0" after the decrement are identified as targets for reconstruction. In the example of Figure 13, the reference count (1) of chunks B and D becomes "0", making them targets for reconstruction. Therefore, archive A1 containing objects O1 and O2, which contain chunks B and D, is extracted from archive storage 222, and objects O1 and O2 are transferred to cloud storage gateway 100, for example, via object storage 221. In addition, the extracted archive A1 is deleted from archive storage 222.

The cloud storage gateway 100 removes chunks B and D with a reference count (1) of "0" from the acquired objects O1 and O2, and reconstructs the objects using the remaining chunks A, C, E, and F. In the example shown in Figure 13, object Ox is generated using chunks A and E with a large reference count (1), and object Oy is generated using chunks C and F with a small reference count (1). An archive Ax containing object Ox and an archive Ay containing object Oy are then stored in archive storage 222. By separately generating an object made up of chunks with a large reference count (1) and an object made up of chunks with a small reference count (1) in this way, the reference count (1) of the chunks in the latter object quickly becomes "0," increasing the likelihood that the objects can be deleted all at once.

Next, as shown in FIG. 14, assume that the NAS client 210 requests the cloud storage gateway 100 to delete files F3 and F4 from archive storage 222. In this case, the reference count (1) of each chunk contained in files F3 and F4 is decremented, and objects containing a certain number of chunks whose reference count (1) has become "0" after the decrement are identified as targets for reconstruction. In the example of FIG. 14, the reference count (1) of chunks C, F, H, and I becomes "0," making them targets for reconstruction. Therefore, archives A2 and Ay containing objects O3 and Oy, which contain chunks C, F, H, and I, are extracted from archive storage 222, and objects O3 and Oy are transferred to the cloud storage gateway 100, for example, via object storage 221. Furthermore, the extracted archives A2 and Ay are deleted from archive storage 222.

The cloud storage gateway 100 removes chunks C, F, H, and I whose reference count (1) is "0" from the retrieved objects O3 and Oy, and reconstructs object Oz using the remaining chunk G. Then, archive Az containing object Oz is stored in archive storage 222.

By performing the above process, invalid chunks whose reference count (1) has reached "0" can be deleted from archive storage 222, and an archive containing only the remaining valid chunks can be left in archive storage 222. This reduces the amount of space used by archive storage 222.

However, when a request to delete files F3 and F4 is made in Figure 14, archive Ay, which was just stored in archive storage 222, has already been deleted. As mentioned above, archive storage 222 has a minimum storage period for archives, and deleting an archive before the minimum storage period has elapsed incurs an additional fee. In the process of Figure 14, archive Ay is stored and then deleted before the minimum storage period has elapsed, resulting in an additional fee.

As such, the above comparative example of defragmentation processing poses the problem that archives may be deleted before the minimum storage period set for archive storage 222 has elapsed, which could result in increased fees. Therefore, in this embodiment, the object and archive reconstruction procedures are modified during defragmentation processing so that archives with short storage periods are less likely to be deleted.

An example of defragmentation processing in this embodiment will be explained below using Figures 15 to 17. Note that in Figures 15 to 17, for simplicity's sake, defragmentation targets are selected on an object-by-object basis, but in reality, defragmentation targets are selected on a chunk group basis, each chunk group containing multiple objects.

Fig. 15 is a first diagram showing an example of defragmentation processing in the second embodiment, and Fig. 16 is a second diagram showing an example of defragmentation processing in the second embodiment.
15, it is assumed that the NAS client 210 requests the cloud storage gateway 100 to delete the files F1 and F2 from the archive storage 222 in the state shown in FIG.

In this case, cloud storage gateway 100 decrements the reference counts (1) and (2) of each chunk contained in files F1 and F2. After this decrement, cloud storage gateway 100 selects, as targets for defragmentation, objects (actually chunk groups) that contain chunks that satisfy at least one of the following conditions (1) and (2):

Condition (1): The file is referenced from a file that has been requested to be stored in the archive storage 222 within a recent fixed period.
Condition (2): The number of references (2) exceeds a predetermined threshold.

The cloud storage gateway 100 extracts chunks that satisfy at least one of the above conditions (1) and (2) from the object selected for defragmentation, and generates new chunks containing the same data content as each of the extracted chunks. At this time, the cloud storage gateway 100 replaces the reference counts (1) and (2) of the original chunks with the generated chunks. The reference counts (1) and (2) of the original chunks become "0". The cloud storage gateway 100 generates a new object using the generated new chunks, and requests the cloud storage system 220 to store a new archive containing the generated object in the archive storage 222.

In Figure 15, as an example, let us assume that objects O1 to O3 have been identified as objects containing chunks that satisfy at least one of the above conditions (1) and (2). For example, chunk G contained in object O3 is referenced by file Fm, which was requested to be stored in archive storage 222 most recently, and therefore satisfies condition (1). Furthermore, chunk A contained in object O1 and chunk E contained in object O2 have a large reference count (2), and therefore satisfy condition (2).

In this case, the cloud storage gateway 100 retrieves archive A1, which contains objects O1 and O2, and archive A2, which contains object O3, from archive storage 222. However, the cloud storage gateway 100 does not delete these archives A1 and A2 at this point. The cloud storage gateway 100 obtains objects O1 to O3 contained in archives A1 and A2, for example, via object storage 221. As a result, objects O1 to O3 are selected as targets for defragmentation.

Next, as shown in FIG. 16, the cloud storage gateway 100 selects chunks from the acquired objects O1 to O3 that satisfy at least one of conditions (1) and (2). In the example of FIG. 16, chunks A, E, and G are selected. The cloud storage gateway 100 generates new chunks A', E', and G' that contain the same data content as the selected chunks A, E, and G, respectively. The cloud storage gateway 100 replaces the reference counts of the original chunks A, E, and G, "6," "5," and "4," respectively, with the generated chunks A', E', and G', and updates the reference counts of the original chunks A, E, and G to "0." This replacement of reference counts is performed for both reference counts (1) and (2).

In addition, the management information indicating the files corresponding to the original chunks A, E, and G is reassigned to the new chunks A', E', and G', respectively. That is, in the chunk map table 112, the chunk number of the original chunk associated with the file number is updated to the chunk number of the new chunk.

The cloud storage gateway 100 generates a new object Ow using the generated chunks A', E', and G', and requests the cloud storage system 220 to store the generated object Ow in the archive storage 222. As a result, an archive Aw containing the object Ow is generated and stored in the archive storage 222.

Figure 17 is a third diagram showing an example of defragmentation processing in the second embodiment. In Figure 17, it is assumed that, from the state shown in Figure 16, the NAS client 210 requests the cloud storage gateway 100 to delete files F3 and F4 from the archive storage 222.

In this case, the cloud storage gateway 100 decrements the reference counts (1) and (2) of each chunk contained in files F3 and F4. In the example of Figure 17, this decrement causes the reference counts (2) of chunks C, F, H, and I to become "0." As a result, the reference counts (2) of all chunks contained in archives A1 and A2 become "0." Therefore, the cloud storage gateway 100 requests the cloud storage system 220 to delete archives A1 and A2. Because a sufficient amount of time has passed since archives A1 and A2 were stored in archive storage 222, archives A1 and A2 can be deleted from archive storage 222 without consuming additional space.

In the comparative example shown in Figure 13, the object selected for reconstruction was simply one with many chunks whose reference count (1) was "0," regardless of when the file referencing the chunk was stored in archive storage 222 or the "number" of references. As a result, after a new archive containing the reconstructed object (archive Ay containing object Oy in Figure 13) was stored in archive storage 222, the archive was deleted in a short time, as shown in Figure 14.

In contrast, the cloud storage gateway 100 of this embodiment does not select as defragmentation targets objects with many chunks whose reference count (1) is "0." Instead, the cloud storage gateway 100 selects as defragmentation targets objects containing chunks that satisfy at least one of the above conditions (1) and (2). The cloud storage gateway 100 generates new chunks containing data with the same content as chunks that satisfy at least one of conditions (1) and (2), assigns the reference counts (1) and (2) of the original chunks to the new chunks, and sets the reference counts (1) and (2) of the original chunks to "0." The cloud storage gateway 100 generates new objects using the new chunks, archives the generated objects, and stores them in archive storage 222.

An archive stored in this way contains only chunks that satisfy at least one of conditions (1) and (2). Chunks that satisfy condition (1) are referenced by files that are likely to be requested for deletion some time in the future, so the reference count (2) of these chunks is unlikely to immediately reach "0." Chunks that satisfy condition (2) also currently have a large reference count (2), so the reference count (2) is unlikely to immediately reach "0." For this reason, it is likely that a long time will pass before the reference counts (2) of all chunks contained in a newly stored archive reach "0," and they are unlikely to become targets for deletion from archive storage 222 in a short period of time. Therefore, additional costs are unlikely to be incurred due to deletion before the minimum storage period has elapsed.

On the other hand, the original chunks corresponding to the newly generated chunks have their reference count updated to "0" and are left in archive storage 222. In archives containing such original chunks, they continue to be stored in archive storage 222 until the reference counts (2) of all chunks in the archive become "0".

In this way, an archive is only deleted when the reference count (2) of all chunks in the archive reaches "0." In other words, unlike the comparative example above, the process of deleting some chunks in an object contained in the archive and reconstructing the object is not performed. This makes it less likely that an archive will be deleted before the minimum storage period has elapsed.

Here, in the processing of this embodiment, the data storage capacity in archive storage 222 and the number of archive inputs and outputs to and from archive storage 222 may be greater than in the case of the comparative example described above. However, the overall cost reduction effect is greater in reducing the number of additional costs incurred by deleting archives before the minimum storage period has elapsed than in increasing costs due to increased storage capacity and number of inputs and outputs.

Furthermore, with the processing of this embodiment, the number of archives in archive storage 222 that are difficult to delete increases as defragmentation progresses. As a result, the number of archive input/output operations between archive storage 222 decreases over time. Therefore, over a relatively long period of time, the number of archive input/output operations between archive storage 222 will be less than in the comparative example above, and it is possible to achieve cost reduction effects by reducing the number of input/output operations.

As explained in the flowchart below, in actual processing, chunks to be defragmented are selected from chunk groups that contain many chunks with a reference count (2) of "0." This increases the number of chunks with a reference count (2) of "0" in the chunk group selected for defragmentation, enabling the reference count (2) of all chunks in that chunk group to quickly reach "0."

Next, the processing of the cloud storage gateway 100 will be described using a flowchart.
18 and 19 are examples of flowcharts showing the procedure of file writing processing.

[Step S11] The file input/output unit 120 receives a file write request and file data from the NAS client 210. The duplication determination unit 131 of the deduplication processing unit 130 obtains the file data requested to be written and adds a record indicating the directory information for that file to the directory table 111. At this time, a file number is assigned to the file. The duplication determination unit 131 also divides the file data into variable-length chunks.

[Step S12] The duplication determination unit 131 selects one chunk to process, starting from the beginning of the file. The duplication determination unit 131 also calculates a hash key based on the data of the selected chunk.

[Step S13] The duplication determination unit 131 adds a record to the chunk map table 112 and registers the following information in this record: The file number field registers the file number of the file requested to be written, and the offset and size fields register information about the chunk to be processed.

[Step S14] The duplication determination unit 131 references the chunk management table 113 and determines whether a record exists in which the hash key calculated in step S13 is registered. This determines whether a chunk with the same content as the chunk selected in step S12 has already been stored (whether there is a duplicate). If a matching record is found, processing proceeds to step S15; if a matching record does not exist, processing proceeds to step S21 in Figure 19.

[Step S15] The duplication determination unit 131 obtains the chunk number from the record searched for in the chunk management table 113 in step S14, and registers the obtained chunk number in the record added to the chunk map table 112 in step S13.

[Step S16] The duplication determination unit 131 references the record in the chunk management table 113 that contains the chunk number obtained in step S15, and counts up the reference count (1) registered in this record.

[Step S17] The duplication determination unit 131 determines whether all chunks divided in step S11 have been processed. If there are unprocessed chunks, processing proceeds to step S12, where one unprocessed chunk is selected from the beginning and processing continues. On the other hand, if all chunks have been processed, the duplication determination unit 131 notifies the file input/output unit 120 that file writing has been completed. Upon receiving the notification, the file input/output unit 120 sends response information to the NAS client 210 indicating that file writing has been completed.

The description will be continued below with reference to FIG.
[Step S21] The duplication determination unit 131 calculates a new chunk number for the chunk selected in step S12. This chunk number is the maximum chunk number registered in the chunk management table 113 plus "1". The duplication determination unit 131 adds a new record to the chunk management table 113. The duplication determination unit 131 registers the calculated new chunk number, the chunk size, and the hash key calculated in step S12 in the added record, and registers "1" as the reference count (1).

[Step S22] The duplication determination unit 131 stores the data of the chunk selected in step S12 in the data cache 117.
[Step S23] The duplication determination unit 131 registers the new chunk number calculated in step S21 in the record added to the chunk map table 112 in step S13.

[Step S24] An object number is assigned to the chunk selected in step S12. This object number indicates the object to which the chunk belongs. This object number is the object number of the object currently being created. The chunk management unit 132 registers the assigned object number in the record added to the chunk management table 113 in step S21.

The chunk management unit 132 also registers, for the same record, a chunk group number that indicates the chunk group to which the object currently being created belongs. A chunk group contains a predetermined number of objects in the order in which they were created. Therefore, the chunk group number is incremented each time a predetermined number of objects are created.

When a new chunk group number is registered, the chunk management unit 132 adds a new record containing that chunk group number to the chunk group management table 114. The initial value "0" is registered in this record as the number of valid chunks and the number of invalid chunks.

[Step S25] The chunk management unit 132 determines whether the number of chunks included in the object currently being created has reached a predetermined threshold (defined as M). If the number of chunks has reached threshold M, processing proceeds to step S26. On the other hand, if the number of chunks has not reached threshold M, the object currently being created is in an active state and is not uploaded to the object storage 221. In this case, steps S26 and S27 are skipped.

[Step S26] The object currently being created becomes inactive and contains M chunks, and the chunk management unit 132 requests the cloud communication unit 140 to upload this object to the object storage 221. The cloud communication unit 140 uses a PUT command to upload the object to the object storage 221.

[Step S27] The chunk management unit 132 increments the object number indicating the object currently being created. As a result, the next time step S24 is executed, the object number of a new object will be assigned to the chunk.

Thereafter, the process proceeds to step S17 in FIG.
Fig. 20 is an example of a flowchart showing the procedure for data storage processing in archive storage. The processing in Fig. 20 starts when the file input/output unit 120 receives a request from the NAS client 210 to store a file in the archive storage 222. This storage request specifies one or more files to be stored.

[Step S31] The chunk management unit 132 identifies objects that are not stored in archive storage 222 from among the objects (objects containing chunk data) corresponding to chunks included in the file specified as the storage target. In this process, if an archive number is not registered in the chunk management table 113 for the chunk number associated with the specified file, it is determined that the object containing the chunk indicated by that chunk number is not stored in archive storage 222.

[Step S32] The chunk management unit 132 requests the cloud communication unit 140 to store an archive containing the object identified in step S31 in the archive storage 222. The cloud communication unit 140 specifies the object number of the identified object and requests the cloud storage system 220 to store it in the archive storage 222. As a result, the archive containing the identified object is stored from the object storage 221 to the archive storage 222.

[Step S33] The chunk management unit 132 identifies records corresponding to each chunk included in the object identified in step S31 from the chunk management table 113. For each identified record, the chunk management unit 132 registers an archive number indicating the archive stored in the archive storage 222.

[Step S34] The chunk management unit 132 performs the following process for each object identified in step S31. The chunk management unit 132 identifies a record corresponding to the chunk group that includes the object in question from the chunk group management table 114. The chunk management unit 132 adds the number of chunks included in the object in question (M above) to the number of valid chunks registered in the identified record.

[Step S35] The chunk management unit 132 identifies a record from the defragmentation determination table 115 that corresponds to the archive group to which the archive stored in the archive storage 222 in step S32 belongs. The chunk management unit 132 adds the number of chunks included in the archive (the total number of chunks added in step S34) to the number of valid chunks registered in the identified record.

[Step S36] The chunk management unit 132 identifies records from the chunk management table 113 that contain chunk numbers associated with each file requested to be stored in the archive storage 222. The chunk management unit 132 registers the current date and time as the archive storage time for each identified record. If a date and time has already been registered, that date and time is updated with the current date and time.

[Step S37] The chunk management unit 132 performs the following process for each chunk number associated with each file requested to be stored in the archive storage 222. The chunk management unit 132 identifies a record containing the corresponding chunk number from the chunk management table 113, and increments the reference count (2) registered in the identified record.

Figure 21 is an example of a flowchart showing the steps in the process of deleting data from archive storage. The process in Figure 21 begins when the file input/output unit 120 receives a request from the NAS client 210 to delete a file from the archive storage 222. This deletion request specifies one or more files to be deleted.

[Step S41] The chunk management unit 132 references the chunk management table 113 and decrements the reference counts (1) and (2) corresponding to each chunk included in the file specified to be deleted. Specifically, the chunk management unit 132 performs the following process for each chunk number associated with each specified file: The chunk management unit 132 identifies a record containing the relevant chunk number from the chunk management table 113 and decrements (subtracts 1) the reference counts (1) and (2) registered in the identified record.

[Step S42] The chunk management unit 132 determines whether a chunk with a reference count (2) of "0" has been generated as a result of the processing in step S41. If such a chunk has been generated, processing proceeds to step S43; if such a chunk has not been generated, the data deletion processing ends.

[Step S43] The chunk management unit 132 updates the number of valid chunks and the number of invalid chunks registered in the corresponding records in the chunk management table 113 and the defragmentation judgment table 115. Specifically, the chunk management unit 132 performs the following process for each chunk whose reference count (2) has become "0".

The chunk management unit 132 identifies a record from the chunk management table 113 that corresponds to the chunk group to which the chunk belongs. The chunk management unit 132 decrements the number of valid chunks registered in the identified record and increments the number of invalid chunks. The chunk management unit 132 also identifies a record from the defragmentation determination table 115 that corresponds to the archive group to which the chunk belongs. The chunk management unit 132 decrements the number of valid chunks registered in the identified record and increments the number of invalid chunks.

[Step S44] The chunk management unit 132 determines whether there is an archive with a valid chunk count of "0" (an archive with a reference count (2) of all chunks to which it belongs equals "0"). If there is a matching archive, processing proceeds to step S45; if there is no matching archive, processing proceeds to step S46.

[Step S45] The chunk management unit 132 requests the cloud communication unit 140 to delete archives with a valid chunk count of "0" from the archive storage 222. The cloud communication unit 140 specifies the archive number of the relevant archive and requests the cloud storage system 220 to delete it from the archive storage 222. As a result, the relevant archive is deleted from the archive storage 222.

Note that steps S44 and S45 may be performed on an archive group basis, rather than on an archive basis. In this case, step S44 determines whether there is an archive group in the defragmentation determination table 115 for which the number of valid chunks is "0." If such an archive group is found, then in step S45, each archive included in that archive group is deleted from the archive storage 222.

[Step S46] The chunk management unit 132 references the defragmentation determination table 115 and determines whether there is an archive group whose percentage of invalid chunks exceeds a predetermined threshold. The percentage of invalid chunks is calculated as the ratio of the number of invalid chunks to the total number of valid chunks and invalid chunks. If a matching archive group is found, processing proceeds to step S47; if no matching archive group is found, the data deletion process ends.

[Step S47] The chunk management unit 132 instructs the defragmentation processing unit 133 to start defragmentation processing. This starts the defragmentation processing shown in Figures 22 and 23.

22 and 23 are examples of flowcharts showing the procedure of the defragmentation process.
[Step S51] The defragmentation processing unit 133 waits for a certain period of time to elapse after the instruction to start defragmentation is received in step S47 of Fig. 21. Then, after the certain period of time has elapsed, the defragmentation processing unit 133 executes the processing of step S52. By starting defragmentation a certain period of time after the instruction to start, more invalid chunks with a reference count (2) of "0" are generated, and it is expected that more archives that can be deleted in bulk will be generated.

[Step S52] The defragmentation processing unit 133 references the defragmentation determination table 115 and identifies archive groups whose percentage of invalid chunks exceeds a predetermined threshold. As in step S46 of FIG. 21, the percentage of invalid chunks is calculated as the ratio of the number of invalid chunks to the total number of valid chunks and invalid chunks.

[Step S53] The defragmentation processing unit 133 selects one chunk group to be processed from among the chunk groups included in the archive group identified in step S52.
[Step S54] The defragmentation processing unit 133 determines whether the selected chunk group includes a chunk that satisfies at least one of the aforementioned conditions (1) and (2). Whether a chunk satisfies condition (1) is determined by whether the archive storage time registered in the corresponding record in the chunk management table 113 is within the most recent fixed period. Whether a chunk satisfies condition (2) is determined by whether the reference count (2) corresponding to the chunk exceeds a predetermined threshold. The threshold for condition (2) is set, for example, to the median (the N/2th value in ascending order) based on the reference count (2) of all chunks (assuming N chunks) whose reference count (2) is 2 or greater.

If the selected chunk group contains one or more matching chunks, processing proceeds to step S55; if it does not contain any matching chunks, processing proceeds to step S56.

[Step S55] The defragmentation processor 133 designates the selected chunk group as a target for defragmentation.
[Step S56] The defragmentation processing unit 133 determines whether all of the chunk groups included in the archive group identified in step S52 have been selected as processing targets. If there are any unselected chunk groups, the process proceeds to step S53, where one unselected chunk group is selected. On the other hand, if all chunk groups have been selected, the process proceeds to step S57.

[Step S57] The defragmentation processing unit 133 requests the cloud communication unit 140 to download the archive containing the chunk group designated as the defragmentation target from the archive storage 222. The cloud communication unit 140 specifies the archive number of the relevant archive and requests the cloud storage system 220 to retrieve it from the archive storage 222. As a result, the relevant archive is downloaded to the cloud storage gateway 100.

[Step S58] The defragmentation processing unit 133 extracts chunks that satisfy at least one of conditions (1) and (2) from the chunks contained in the downloaded archive. The defragmentation processing unit 133 sorts the extracted chunks using the archive storage date and time in the chunk management table 113 as the first key and the reference count (2) in the chunk management table 113 as the second key. In other words, the extracted chunks are sorted in descending order of the most recent archive storage date and time, and chunks with the same archive storage date and time are sorted in descending order of the reference count (2).

The description will be continued below with reference to FIG.
[Step S61] The defragmentation processing unit 133 selects one chunk from the beginning of the chunks sorted in step S58 as a processing target.

[Step S62] The defragmentation processing unit 133 determines whether either of the following conditions is met: there are no existing chunk groups being created during defragmentation processing, or there are existing chunk groups being created but the size of those chunk groups exceeds a specified size. If either condition is met, processing proceeds to step S63; if neither condition is met, processing proceeds to step S64.

[Step S63] The defragmentation processing unit 133 creates a new chunk group. A new chunk group number is assigned to the created chunk group. In addition, a record corresponding to the new chunk group is added to the chunk group management table 114, and the chunk group number is registered.

[Step S64] The defragmentation processing unit 133 adds a new chunk containing data with the same content as the selected chunk to the chunk group. If step S63 is executed, the new chunk is added to the chunk group newly created in step S63. On the other hand, if the determination in step S62 is No, the new chunk is added to the existing chunk group being created.

In this process, the defragmentation processing unit 133 assigns a new chunk number to the new chunk, adds a record to the chunk management table 113, and registers the chunk number in that record. The defragmentation processing unit 133 also registers the chunk group number of the chunk group to which the chunk is to be added in the added record, and registers a new object number that corresponds one-to-one with the chunk group number as the object number. Note that values indicating the starting position of the chunk in the chunk group are registered as the offset and size.

[Step S65] The defragmentation processing unit 133 changes the reference counts (1) and (2) from the original chunk (the chunk selected in step S61) to the new chunk. Specifically, the defragmentation processing unit 133 copies the reference counts (1) and (2) corresponding to the original chunk to the reference counts (1) and (2) corresponding to the new chunk in the chunk management table 113, respectively, and updates the reference counts (1) and (2) corresponding to the original chunk to "0".

The defragmentation processing unit 133 also copies the hash key value corresponding to the original chunk to the hash key item corresponding to the new chunk in the chunk management table 113. Furthermore, the defragmentation processing unit 133 updates all of the chunk numbers of the original chunks registered in the chunk map table 112 to the chunk numbers of the new chunks. This updates the management information indicating the correspondence between chunks and files, and the original chunks are no longer referenced by the files.

[Step S66] The defragmentation processing unit 133 determines whether all of the chunks sorted in step S58 have been selected for processing. If there are unselected chunks, processing proceeds to step S61, where the first chunk among the unselected chunks is selected. On the other hand, if all applicable chunks have been selected, processing proceeds to step S67.

[Step S67] The defragmentation processing unit 133 requests the cloud communication unit 140 to store an archive containing the chunk groups created in steps S61 to S66 in the archive storage 222. The cloud communication unit 140 uploads each created chunk group to the object storage 221 as an individual object. The cloud communication unit 140 then requests that an archive containing each uploaded object be stored in the archive storage 222. As a result, the relevant objects are stored in the archive storage 222.

[Step S68] The defragmentation processing unit 133 registers the archive numbers of all chunk records in the chunk management table 113 that are included in the archive stored in the archive storage 222. The defragmentation processing unit 133 also registers the current date and time in the archive storage date and time fields of those records.

Furthermore, the defragmentation processing unit 133 adds the number of chunks included in the chunk group to the number of valid chunks in the records in the chunk group management table 114 that correspond to each chunk group included in the archive. It also adds the number of chunks included in the archive to the number of valid chunks associated with the archive number of the archive in the defragmentation determination table 115.

The defragmentation processing unit 133 also performs the following processing for each of the original chunks whose reference counts (1) and (2) were updated to "0" in step S65. The defragmentation processing unit 133 decrements the number of valid chunks and increments the number of invalid chunks in the records of the chunk group management table 114 that correspond to the chunk group to which the chunk belongs. Furthermore, the defragmentation processing unit 133 decrements the number of valid chunks and increments the number of invalid chunks in the records of the defragmentation determination table 115 that correspond to the archive to which the chunk belongs.

[Step S69] The chunk management unit 132 determines whether there is an archive with a valid chunk count of "0" (an archive with a reference count (2) of all chunks to which it belongs equals "0"). If there is a matching archive, processing proceeds to step S70; if there is no matching archive, defragmentation processing ends.

[Step S70] The chunk management unit 132 requests the cloud communication unit 140 to delete archives with a valid chunk count of "0" from the archive storage 222. The cloud communication unit 140 specifies the archive number of the relevant archive and requests the cloud storage system 220 to delete it from the archive storage 222. As a result, the relevant archive is deleted from the archive storage 222.

As with steps S44 and S45, the processing of steps S69 and S70 may be executed in units of archive groups, rather than in units of archives.
According to the above process, during the defragmentation process, the cloud storage gateway 100 stores archives that are unlikely to be deleted early in the archive storage 222. This reduces the probability of an archive being deleted from the archive storage 222 before the specified minimum storage period has elapsed. As a result, it is possible to increase the possibility of reducing the usage costs of the archive storage 222.

In steps S53 to S56 of Figure 22, defragmentation targets may be specified on an object-by-object basis rather than on a chunk group basis. However, since a large number of objects are created in actual processing, if defragmentation targets are specified on an object-by-object basis, defragmentation processing using small defragmentation target data may be performed frequently, resulting in low processing efficiency. In contrast, processing efficiency can be improved by specifying defragmentation targets on a chunk group basis containing multiple objects.

Similarly, in step S46 of FIG. 21 and step S52 of FIG. 22, the percentage of invalid chunks may be calculated on an archive basis rather than on an archive group basis. However, calculating the percentage of invalid chunks on an archive group basis can improve processing efficiency.

The processing functions of the devices described in the above embodiments (e.g., storage control device 1, cloud storage gateway 100) can be implemented by a computer. In this case, a program describing the processing details of the functions that each device should have is provided, and the processing functions are implemented on the computer by executing the program. The program describing the processing details can be recorded on a computer-readable recording medium. Examples of computer-readable recording media include magnetic storage devices, optical discs, and semiconductor memories. Magnetic storage devices include hard disk drives (HDDs) and magnetic tapes. Optical discs include CDs (Compact Discs), DVDs (Digital Versatile Discs), and Blu-ray Discs (BD, registered trademark).

When distributing a program, for example, the program is recorded on a portable recording medium such as a DVD or CD and sold. The program can also be stored in the storage device of a server computer, and then transferred from the server computer to other computers via a network.

A computer that executes a program stores, for example, a program recorded on a portable recording medium or a program transferred from a server computer in its own storage device. The computer then reads the program from its own storage device and executes processing in accordance with the program. Note that the computer can also read the program directly from a portable recording medium and execute processing in accordance with that program. The computer can also execute processing in accordance with the received program each time a program is transferred from a server computer connected via a network.

1 Storage control device 2 External storage AC1, AC2, ACn, ACx Storage data set CK1 to CK9, CK21, CK22, CK1', CK5', CK7' Chunk FL1 to FL4, FLm File

Claims (5)

On the computer,
Obtaining a plurality of chunks from a plurality of divided data sets obtained by dividing each of the plurality of files for which writing is requested, while eliminating duplicates, and generating a plurality of storage data sets by combining two or more chunks selected from the plurality of chunks,
when a storage request for a first file of the plurality of files is received, one or more first storage datasets including chunks of the plurality of chunks referenced by the first file are identified, and the one or more first storage datasets are stored in an external storage, and a reference count associated with the chunks of the plurality of chunks referenced by the first file is increased by the number of references from split datasets included in the first file among the plurality of split datasets;
When a request to delete a second file among the plurality of files is received, the reference count corresponding to a chunk among the plurality of chunks referenced by the second file is decreased by the number of chunks referenced by a split data set included in the second file among the plurality of split data sets;
Among the plurality of stored data sets stored in the external storage, one or more first chunks that are referenced by files among the plurality of files for which storage in the external storage has been requested within a recent fixed period are identified and acquired from the external storage;
generating one or more second chunks each having the same data as the one or more first chunks, respectively reassigning the reference numbers corresponding to the one or more first chunks to the one or more second chunks, respectively, and updating the reference numbers corresponding to the one or more first chunks to 0, and aggregating the one or more second chunks to generate a new storage dataset and storing the new dataset in the external storage;
When a second storage dataset in which the reference count corresponding to all chunks in a corresponding storage dataset is 0 is detected from among the storage datasets stored in the external storage among the plurality of storage datasets, the second storage dataset is deleted from the external storage.
Storage control program. As the one or more first chunks, chunks whose reference count is greater than a predetermined threshold are further identified from among the plurality of stored datasets stored in the external storage.
The storage control program according to claim 1. In identifying the one or more first chunks,
Identifying one or more third storage datasets from among the plurality of storage datasets stored in the external storage, in which the proportion of chunks with the reference count of 0 exceeds a predetermined proportion;
identifying the one or more first chunks from within the one or more third archived data sets;
3. The storage control program according to claim 1. The computer
Obtaining a plurality of chunks from a plurality of divided data sets obtained by dividing each of the plurality of files for which writing is requested, while eliminating duplicates, and generating a plurality of storage data sets by combining two or more chunks selected from the plurality of chunks,
when a storage request for a first file of the plurality of files is received, one or more first storage datasets including chunks of the plurality of chunks referenced by the first file are identified, and the one or more first storage datasets are stored in an external storage, and a reference count associated with the chunks of the plurality of chunks referenced by the first file is increased by the number of references from split datasets included in the first file among the plurality of split datasets;
When a request to delete a second file among the plurality of files is received, the reference count corresponding to a chunk among the plurality of chunks referenced by the second file is decreased by the number of chunks referenced by a split data set included in the second file among the plurality of split data sets;
Among the plurality of stored data sets stored in the external storage, one or more first chunks that are referenced by files among the plurality of files for which storage in the external storage has been requested within a recent fixed period are identified and acquired from the external storage;
generating one or more second chunks each having the same data as the one or more first chunks, respectively reassigning the reference numbers corresponding to the one or more first chunks to the one or more second chunks, respectively, and updating the reference numbers corresponding to the one or more first chunks to 0, and aggregating the one or more second chunks to generate a new storage dataset and storing the new dataset in the external storage;
When a second storage dataset in which the reference count corresponding to all chunks in a corresponding storage dataset is 0 is detected from among the storage datasets stored in the external storage among the plurality of storage datasets, the second storage dataset is deleted from the external storage.
Storage control methods. Obtaining a plurality of chunks from a plurality of divided data sets obtained by dividing each of the plurality of files for which writing is requested, while eliminating duplicates, and generating a plurality of storage data sets by combining two or more chunks selected from the plurality of chunks,
when a storage request for a first file of the plurality of files is received, one or more first storage datasets including chunks of the plurality of chunks referenced by the first file are identified, and the one or more first storage datasets are stored in an external storage, and a reference count associated with the chunks of the plurality of chunks referenced by the first file is increased by the number of references from split datasets included in the first file among the plurality of split datasets;
When a request to delete a second file among the plurality of files is received, the reference count corresponding to a chunk among the plurality of chunks referenced by the second file is decreased by the number of chunks referenced by a split data set included in the second file among the plurality of split data sets;
Among the plurality of stored data sets stored in the external storage, one or more first chunks that are referenced by files among the plurality of files for which storage in the external storage has been requested within a recent fixed period are identified and acquired from the external storage;
generating one or more second chunks each having the same data as the one or more first chunks, respectively reassigning the reference numbers corresponding to the one or more first chunks to the one or more second chunks, respectively, and updating the reference numbers corresponding to the one or more first chunks to 0, and aggregating the one or more second chunks to generate a new storage dataset and storing the new dataset in the external storage;
a processing unit that, when a second storage dataset in which the reference count corresponding to all chunks in a corresponding storage dataset is 0 is detected from among the storage datasets stored in the external storage among the plurality of storage datasets, deletes the second storage dataset from the external storage;
A storage control device having: