KR101553028B1 - Variable processing file system and file variable processing method based on fixed block - Google Patents

Abstract

The present invention relates to a variable processing file system and a file variable processing method based on a fixed block, and a variable processing file system based on a fixed block according to the present invention includes a nonvolatile memory unit for storing file data, When the file data is stored in the nonvolatile memory unit in the first place, the file data is stored in the plurality of fixed blocks. When the file data stored in at least one of the plurality of fixed blocks stored in the nonvolatile memory unit is changed, To a variable block, and stores the processed data in a variable block. Thus, it is possible to quickly perform file storage according to a change of file data.

Description

[0001] The present invention relates to a variable processing file system based on a fixed block and a variable file processing method and a file variable processing method,

The present invention relates to a variable processing file system and a variable file processing method based on a fixed block, and more particularly, to a variable processing file system and a file variable processing method, which are based on a fixed block that enables storage of variable- And a method of processing the same.

The file system is responsible for storing the operating system, various executables, and user data in the computer system. In the user area, a file is regarded as a byte stream and is used to read or write file data through a file handle.

The read / write request for the file in the user area is transferred to the file system of the kernel area, and finally converted to a read / write request for the block of data stored in the block device. Therefore, the byte stream processed in the user area is converted into a block unit at the device level, which causes various problems in the operation of the file.

For example, a case in which a portion of a file is read into a memory buffer of a user area, and then a byte of data is added or deleted in the middle of the buffer will be described. In this case, it is possible to easily change the data while moving the file offset to the area to be changed in the user area and inserting or deleting the new byte. However, if such a change is stored in the file system, . The byte stream present on the memory buffer must ultimately be stored in a block on the disk, and the data change of one byte will require the modification of all subsequent data blocks in succession.

This problem occurs in the same way when insertion or deletion of data occurs in units of blocks as well as insertion or deletion in units of bytes. For example, an application such as Winzip or WinRAR, which is widely used on a desktop computer, has a structure in which a plurality of sub-files constitute one file, and each sub-file is block-aligned. Structure. Therefore, the process of deleting or inserting a subfile corresponds to a process of inserting or deleting consecutive blocks. Most file systems, however, do not consider the operations of inserting or deleting data in block units, and process file modification operations like ordinary files.

In order to solve the above-described problems, it is an object of the present invention to provide a variable processing file system and a variable file processing method based on a fixed block which enables storage of variable-size file data on a fixed-size block.

According to an aspect of the present invention, there is provided a variable processing file system based on a fixed block according to an embodiment of the present invention includes a nonvolatile memory unit for storing file data, In a case where file data stored in at least one block among a plurality of fixed blocks stored in the nonvolatile memory unit is changed, the changed block is processed as a variable block and stored And a file management unit.

Wherein the nonvolatile memory unit includes a file management area and a data storage area, and when the file is first stored in the nonvolatile memory unit, the nonvolatile memory unit stores the fixed block information in the file management area, Wherein when the file data stored in at least one block among the plurality of fixed blocks stored in the nonvolatile memory unit is changed, the block variable information for the changed block in the file management area is stored in the file management area, It is possible to store the corresponding file data only for the blocks which are further stored and changed.

The fixed block information includes position information of the data storage area for each block, and the block variable information may include the number of changed blocks and the number of bytes of file data stored in the changed block.

In the variable-processing file system based on the fixed block, when the file is first stored in the non-volatile memory unit by the file management unit, one file data to be stored is divided into a predetermined unit size smaller than the block size, And a file similarity processor for extracting the hash values and measuring the file similarity using the extracted hash values and the hash values associated with the file data stored in the nonvolatile memory.

The file management unit may generate indexes for the redundant blocks using the file similarity measured by the file similarity processing unit and process some file data existing at the beginning of the redundant blocks as a block variable so that no byte- have.

According to another aspect of the present invention, there is provided a method of variable file processing based on a fixed block, comprising the steps of: storing file data in a plurality of fixed blocks when a file is first stored in the non-volatile memory; When the file data stored in at least one block among the plurality of fixed blocks stored in the storage unit is changed, the modified block is processed as a variable block and stored, thereby achieving the above object.

According to the above-described structure, it is possible to store file data of a variable size in a fixed size block, thereby enabling file storage according to a change of file data to be performed quickly.

In addition, the present invention can extend the lifetime of a flash memory or the like, which is a semiconductor type nonvolatile memory, by minimizing the recording of data in the data area of the storage medium.

FIG. 1 is a block diagram showing an overall configuration of a fixed block file-based variable processing file system according to an embodiment of the present invention.
Figs. 2A to 2C are diagrams for explaining variable processing based on a fixed block according to the present invention. Fig.
3 is a diagram showing an embodiment of metadata according to the present invention.
4A and 4B are diagrams for explaining redundant data processing in a variable processing file system based on a fixed block according to the present invention.
FIG. 5 is a diagram showing the file similarity processing unit shown in FIG. 1 in more detail.
FIG. 6 is a flowchart showing a file variable processing method based on a fixed block according to another embodiment of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, preferred embodiments of a fixed block file-based variable processing file system and a file variable processing method according to the present invention will be described with reference to the accompanying drawings. In the following description of the present invention, it is to be understood that the terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the technical scope of the present invention. Will be.

FIG. 1 is a block diagram showing an overall configuration of a fixed block file-based variable processing file system according to an embodiment of the present invention.

1, the fixed processing file system based on the fixed block includes a non-volatile memory unit 110, a file management unit 120, and a file similarity processing unit 130. [

The non-volatile memory unit 110 is divided into a file management area 112 and a data storage area 114 for storing file data. The non-volatile memory unit 110 is not limited to a flash memory, which is a semiconductor memory, and includes a hard disk and the like.

In the file management area 112, fixed block information related to fixed-length block information and block variable information for storing variable-length information are stored in a fixed-length block. In the data storage area 114, a file management area 112 And the file information is stored according to the block variable information. On the other hand, the fixed block information includes position information of the data storage area 114 for each block. The block variable information may include the number of changed blocks and the number of bytes of file data stored in the changed block.

The file management unit 120 includes a file generation module 122, a file change detection module 124, a block variable processing module 126, and an index modification module (hereinafter, referred to as " file modification module ") 122 for managing file data stored in the nonvolatile memory unit 110 128).

The file generation module 122 stores the file data in a plurality of fixed blocks when the file is initially stored in the non-volatile memory unit. When the file is initially stored in the nonvolatile memory unit, the file generation module 122 stores the fixed block information in the file management area 112 and stores the file data in the data storage area 114 allocated to the fixed block information .

The file change detection module 124 detects whether there is a change in the file data after the file data stored in the non-volatile memory unit 110 is read. For example, the file change detection module 124 detects whether the user has performed deletion of a byte corresponding to a predetermined block of the file data after reading the file data.

When the file change detection module 124 detects a change in file data stored in at least one block among a plurality of fixed blocks stored in the nonvolatile memory unit 110, the block variable processing module 126 sets the changed block And the variable block is stored. In addition, the block variable processing module 126 may further store the block variable information for the changed block in the file management area 112 upon storage, and may store corresponding file data only for the changed block. In addition, when the index modification module 126 intends to change the index information with respect to the redundant blocks, the block variable processing module 126 may process some file data existing at the beginning of the redundant blocks as a block variable.

The index modification module may use the file similarity measured by the file similarity processor 130 to store duplicate blocks in the file management area 112 without storing the redundant blocks in the data storage area 114, And the index is corrected and stored with the position information of the data storage area 114 of the block.

The file similarity processing unit 130 determines the degree of similarity between the file data to be initially stored in the nonvolatile memory unit 110 and the file data already stored in the nonvolatile memory unit 110, 132 and a similarity comparison module 132.

The hash value extraction module 132 divides one file data to be stored into a predetermined unit size smaller than the block size when the file management unit 120 stores the file in the nonvolatile memory unit 110 for the first time, Extract the hash value for each size.

The similarity comparing module 132 compares the hash values extracted from the hash value extracting module 132 with the hash values associated with the file data stored in the nonvolatile memory 110 to check whether or not there is the same hash value .

Hereinafter, embodiments of the present invention will be described in more detail.

Figs. 2A to 2C are diagrams for explaining variable processing based on a fixed block according to the present invention. Fig.

FIG. 2A is a conceptual diagram of a conventional file system. When the file is stored in the nonvolatile memory unit 110 as a byte stream, the file is stored through the chunking step. At this time, the INODE has information to record the position of each block together with the information of the file. Here, the fixed size of each block may be, for example, 512 bytes.

2B is a conceptual diagram of a conventional file system for modifying stored file data. As shown in FIG. 2B, when the "K" is deleted, since the block is changed from the third block to the internal file data in the chunking step, the third block is changed and stored in the nonvolatile memory unit 110. [ In this case, the existing block may be invalidated according to the file system, the new block may be allocated and the file data may be stored, or the existing block may be overwritten.

FIG. 2C is a conceptual diagram for modifying file data using a variable based on a fixed block according to the present invention. As shown in FIG. 2C, when the "K" is deleted, the file data size smaller than 512 bytes is stored in the third block in the chunking step. And INODE modifies the block index on the changed contents. In the case of storing file data according to the present invention, only the third block in the data block is changed, and no change occurs in the remaining blocks.

3 is a diagram showing an embodiment of metadata according to the present invention.

INODE stores basic information for file I / O. In the present invention, an existing INODE is extended to be based on a fixed block to support variable processing of the block. As shown in FIG. 3, in the metadata information according to the present invention, two pieces of information are added in addition to the information (B0, B1, B2, and B3) about the existing fixed block as well as the variable processing of the fixed block. A variable block (VB) records how many block variables it has. If VB is 1, it indicates that the block in which the change has been made by the variable process of the block in the file data is one block. A variable block index (VBI) indicates an index of a block in which variable processing for a block has occurred. In FIG. 3, V1, V2, V3 and V4 are shown.

As shown in FIG. 3, it is assumed that 16 bytes have been deleted due to the change of the file data in the third block. In this case, only 496 bytes are stored in the block located at 53, and the remaining 16 bytes are meaningless data. In order to refer to this in the file system, the corresponding information must be described in the INODE. 1 is stored in VB because one variable process is generated for the fixed block. In V1, it is informed that block 53 is a block having a variable process for a fixed block, and information about that 496 bytes is recorded in block 53 is stored.

In FIG. 3, variable processing for the fixed block is limited to a maximum of four, but the maximum number can be increased as needed. However, when variable processing is required for a fixed number of blocks or more, a process of forcibly performing garbage collection and removing all the variable processing for a fixed block may be performed.

4A and 4B are diagrams for explaining redundant data processing in a variable processing file system based on a fixed block according to the present invention.

FIG. 4A shows a redundant data processing method in a conventional file system. As shown in FIG. 4A, when a new file is created, duplication can not be removed even though there are four blocks in the conventional file system. Because there is redundant data, it is impossible to share block by block due to byte-shift phenomenon.

FIG. 4B shows a method of processing redundant data using variable processing based on a fixed block according to the present invention. As shown in FIG. 4B, when the variable processing file system based on the fixed block implemented by the present invention is used, chunking can be performed on the basis of redundant blocks to find redundancy for four blocks. It is possible to replace the redundant four blocks by storing them in the nonvolatile memory by modifying the index into blocks of the existing file without storing them in the nonvolatile memory.

The file similarity is a numerical value indicating the degree of similarity between files, and redundant data can be efficiently removed using similarity information. Deduplication is a technique in which when a new file is stored, the same portion is searched for in another file, and the same portion is not stored but only the different portion is stored. Therefore, similarity information of the file requires high accuracy.

FIG. 5 is a diagram showing the file similarity processing unit shown in FIG. 1 in more detail.

5, the file similarity processing unit 130 includes a hash value extracting module and a similarity comparing module 132. The file similarity processing unit 130 includes a HDD 510 as a nonvolatile memory unit 110, A file creation memory 520 associated with the volatile memory where new file data is created and stored, and a hash value storage memory 530 associated with the volatile memory in which the hash value for the file is stored. Here, the file creation memory 520 and the hash value storage memory 530 may be separate memories, but may be one memory.

When the file creation module 122 of the file management unit 120 stores the file stored in the file creation memory 520 in the HDD 510, the hash value extraction module 132 stores the file in the file creation memory 520 And extracts the hash value. In this case, the hash value extraction module 132 may divide the file data into a predetermined unit size smaller than the block size, and extract the hash value for each predetermined unit size. The hash values extracted from the hash value extraction module 132 may be stored in the hash value storage memory 530.

The similarity comparison module 132 compares the hash values extracted by the hash value extraction module 132 with the hash values associated with the respective file data stored in the hash value storage memory 530 to check whether the same hash value exists . The hash values associated with each file data stored in the hash value storage memory 530 can be read to the HDD 510. [

The similarity digest hashing (SDHASH) scheme or the SSDEEP scheme can be used to process the file similarity.

Instead of choosing arbitrary chunk sizes using a rabin fingerprint, SDHASH uses stochastic features using the newness entropy, so that the feature point selection does not shift to a specific part of the data, Reliability is improved. The selected feature points measure the statistical based file similarity using Bloom filter. The 64-byte minutiae are used to generate the minutiae by selecting the minutiae that contain the popularity score above a given threshold value. In addition, among the selected minutiae, minutiae which have a value of more than 100 and less than 990 are excluded, thereby lowering the positive error rate of the Bloom filter.

In SDHASH, the Bloom filter is generated with a fixed size of 256 bytes. 128 feature point values are assigned to each generated bloom filter. If the number of minutiae exceeds 128, a new Bloom filter is added and minutiae values are assigned. Each feature point is computed as a 160-bit hash value using the SHA-1 hash function. The SDHASH comparison process compares all generated Bloom filters one by one and measures the file similarity by averaging all Bloom filter comparison values.

SSDEEP performs file similarity measurement using two hash methods. The rolling hash function moves the contents of the file one byte at a time and generates a hash value. Calculate the trigger position, which is the boundary point inside the file, using the generated rolling hash value. If a trigger location is found, it is treated as a single chunk from the beginning of the file to the trigger location, and the junk generates a junk hash using the MD5 hash function. The generated chunk hash value is converted into a bit string using Base64 encoding, extracts the last 6 bits of the converted bit string, and concatenates the bit values of each bit string to generate a file digest.

The file similarity degree processing unit 130 can maintain the similarity value of each file processed by the above technique in a string form in the INODE. Therefore, when a new file is imported or generated, the file similarity processing unit 130 can find the most similar file through comparison of hash strings. The file management unit 120 stores duplicate blocks between the original file and the incoming file You can proceed to find and share.

On the other hand, if the file similarity processing unit 130 processes the file similarity based on the fixed block based on the fixed partitioning technique, the file similarity processing unit 130 may apply the variable partitioning technique to the data existing in the front of the redundant block. As a result, it is possible to effectively store the file data for the similar file and significantly reduce the input / output overhead.

FIG. 6 is a flowchart showing a file variable processing method based on a fixed block according to another embodiment of the present invention.

If the file management unit 120 wants to store the file in the nonvolatile memory, the file generation module 122 checks whether the file is first stored in the nonvolatile memory (S602). If the file management unit 120 firstly stores the file in the nonvolatile memory, the hash value extraction module 132 divides one file data to be stored into a predetermined unit size smaller than the block size and extracts a plurality of hash values (S604).

The similarity comparison module 132 compares the hash values extracted from the hash value extraction module 132 with the hash values associated with the file data stored in the non-volatile memory unit 110, and measures file similarity (S606) . The index modification module 128 creates an index for the redundant blocks using the file similarity measured by the similarity comparison module 132 (S608). In step S610, the block variable processing module 126 performs block variable processing on some file data existing in the front part of the redundant blocks so that byte-shifting does not occur.

The file change detection block detects whether there is a change in the file to be stored in the nonvolatile memory (S612). If there is a change in the file, the block variable processing module 126 stores the block variable information for the changed block in the file management area 112 (S614), and stores the corresponding file data only for the changed block (S616).

The scope of protection of the present invention should be interpreted according to the claims. It will be apparent to those skilled in the art that various modifications and variations can be made in the present invention without departing from the spirit and scope of the invention as defined by the appended claims. It should be interpreted that it is included in the scope of right.

110: nonvolatile memory unit 112: file management area
114: Data storage area 120: File management part
122: file generation module 124: file change detection module
126: block variable processing module 128: index modification module
130: file similarity processing unit 132: hash value extraction module
134: Similarity comparison module 510: HDD
530: file generation memory 530: hash value storage memory

Claims (8)

A non-volatile memory unit for storing file data, and
When the file is initially stored in the nonvolatile memory unit, the file data is stored in the plurality of fixed blocks. When the file data stored in at least one of the plurality of fixed blocks stored in the nonvolatile memory unit is changed And a file manager for processing and storing the changed block as a variable block,
Wherein the nonvolatile memory unit includes a file management area and a data storage area,
Wherein the file management unit stores the fixed block information in the file management area and the file data in the data storage area allocated to the fixed block information when the file is initially stored in the nonvolatile memory unit, When the file data stored in at least one block among the plurality of fixed blocks stored in the file management area is changed, the block variable information for the changed block is further stored in the file management area, and the file data corresponding to the changed block is stored Based variable block file system. delete The method according to claim 1,
Wherein the fixed block information includes position information of the data storage area for each block,
Wherein the block variable information includes a number of changed blocks and a number of bytes of file data stored in the changed block. The method according to claim 1 or 3,
When the file is first stored in the nonvolatile memory unit by the file management unit, one file data to be stored is divided into a predetermined unit size smaller than the block size to extract a plurality of hash values, and a plurality of extracted hash values And a file similarity processor for measuring file similarity using hash values associated with the file data stored in the nonvolatile memory unit. 5. The method of claim 4,
The file management unit generates an index for the redundant blocks using the file similarity measured by the file similarity processing unit and processes some file data existing in the front part of the redundant blocks as a block variable so that no byte-shift occurs A variable processing file system based on a fixed block that features. Storing the file data in a plurality of fixed blocks when the file is initially stored in the non-volatile memory section; and
If the file data stored in at least one of the plurality of fixed blocks stored in the nonvolatile memory unit is changed, processing the modified block as a variable block and storing the modified block,
Wherein the nonvolatile memory unit includes a file management area and a data storage area,
Wherein the step of storing the file data in the plurality of fixed blocks comprises the steps of storing the fixed block information in the file management area when the file is first stored in the nonvolatile memory part, Storing the data,
Wherein when the file data stored in at least one of the plurality of fixed blocks stored in the nonvolatile memory unit is changed, the step of processing and storing the changed block as a variable block includes: And storing the file data corresponding only to the changed block. The method of claim 1, delete The method according to claim 6,
Dividing one file data to be stored into a predetermined unit size smaller than a block size to extract a plurality of hash values when the file is first stored in the nonvolatile memory unit,
Measuring file similarity using a plurality of hash values extracted in the extracting of the plurality of hash values and hash values related to file data stored in the non-volatile memory unit; and
An index is generated for the redundant blocks by using the file similarity measured in the step of measuring the file similarity and a process for processing some file data existing in the front part of the redundant blocks in a block variable manner so as to prevent the byte- Wherein the fixed-block-based variable-processing method further comprises:

Images