Write anywhere file-system layout method and apparatus

Description: TECHNICAL FIELD [Detailed description of the invention]

Lite Anywhere File System Layout Background of the invention 1. Field of invention The present invention maintains a consistent file system and provides this. Regarding how to make a read-only copy of a file system and the field of its equipment To do. 2. Background technology All file systems maintain integrity in the event of a system failure There is a need. To date, several different integrity maintenance techniques have been used for this purpose. , Has been used in the prior art. The most difficult and time-consuming problem in managing any file server One is to make a backup of the file data. Traditional solution The method was to copy the data to tape or other offline media. For some file systems, make sure the backup is perfectly consistent Therefore, the file server needs to be taken offline during the backup process. .. Recent advances in backup have made it possible to quickly clone filesystems. Make (clone) (ie, a read-only copy of the filesystem on disk Proven method of making), not from an active file system You can also back up from this clone. This type of file The system can keep the file server online during the backup. File system integrity The file system by the conventional technology is the episode fa by Chutani etc. A paper entitled The Episode File System (USENIX, 19) It is disclosed in the 1992 Winter issue, pp. 43-59). This treatise is metadata (Ie, inode tables, directories, bitmaps, indirect blocks) etc. Describes the episode file system, which is the file system used. .. It can be a standalone file system or a distributed file Can be used as a system. The episode file system has multiple separate fabs Supports file system hierarchy and for multiple file systems Collectively referred to as an "aggregate". Especially, the episode system gradually A clone of each file system is provided to change the data. episode In the system, each logical file system has an "anode table" "including. Anode table is Berkeley Fast File System (Be Inode table used in file systems such as rkeley Fast File System) Corresponds to The anode table has a structure of 252 bytes. Anoh De is not just the metadata of the episode file system, but all user data It is used to memorize data. Anode contains auxiliary files and directories Describe the root directory of the file system. This of each episode Such a file system is called a "file set". All data in the file set The data decides to iterate through the anode table and process each file in turn. You can find out more. The episode system reads the file system Make a dedicated copy (called a clone here) and copy-on-write (here) Active file system and data using Copy-On-Write (COW) technology Share data. Episode system recovers file system after system crash Logging technology is used to make it work. Logging technology is a file system Check if the metadata is consistent. Bitmap table is fa Contains information about whether each block in the Ilsystem is assigned .. Also, in the bitmap table, whether or not each block is logged (recorded) Is also shown. All up-to-date metadata records aggregate transaction logs It is stored in the memorized log "container". The log is a disk Treated as a circular buffer for locks. Episode system processing logging Originally developed for databases to check file system integrity Was done Use logging techniques. This technique is a carefully ordered write And recovery program (supplemented by database techniques within it) Is used. Including IBM's JFS and Veritas Corporation's VxFS Prior art systems use each form of processing logging to speed up recovery processing. However, it still needs recovery processing. Another prior art method is the "ordered write" technique. Called, it causes a system failure during a series of related writes Carefully decide on all directory blocks to minimize damage when Write in the order given. In this prior art, the inconsistencies that occur are harmless. Try to make sure that. For example, a few unused blocks or The inode is marked as assigned. The main disadvantage of this technique is Difficult to achieve high performance due to the limitations it imposes on the order of the disc Is to become. Other prior art systems are "ordered write wi with recovery." This is an improvement method of the above-mentioned second conventional technique called the "th recovery)" technique. this In the method, inconsistencies can be potentially harmful. However, the order of writing is The recovery program is restricted to discovering and handling inconsistencies. Example of this method As the original UNIX file system and Berkeley Fast Filesystem There is a system (FFS). In this technique, the sex of disc ordering The disc ordering is reduced so as to sufficiently eliminate the deduction of Noh. Another disadvantage The point is that the recovery process is time consuming. It is typically Phi It is proportional to the size of the system. So, for example, a 5GB FFS file It takes more than an hour to recover the system. File system clone Figure 1 shows copy-on-write (C) for cloning a set of files. It is a diagram of the prior art of an episode file system showing the use of the OW) technology. A Is node 110 the first pointer 110A with the set COW bit? It consists of. Pointer 110A directly references data block 114. Anode 1 10 consists of a second pointer 110B with a cleared COW bit. Anode pointer 110B refers to indirect block 112 . Indirect block 112 consists of a pointer 112A that directly references data block 124. Po The COW bit of the inter 112A is set. The indirect block 112 It consists of a second pointer 112B that references data block 126. Pointer 1 The 12B COW bit is cleared. The clone anode 120 is a first pointer to reference to data block 114. It consists of 120A. The COW bit of pointer 120A is cleared. Claw The second pointer 120B of the anode 120 refers to the indirect block 122. The COW bit of pointer 120B is cleared. Next, the indirect block 122 , Consists of pointer 122A referencing data block 124. Pointer 122 The COW bit of A is cleared. As shown in Figure 1, each direct pointer 110A of the episode file system, 112A ~ 112B, 120A and 122A, and indirect pointer 110B And 120B include COW bits. Blocks that have not changed are active Included in both the file system and the clone, set the COW bit (1) .. The COW bit is cleared when the block referenced by the pointer changes (0), so it is part of the active file system, but cloned is not it. As shown in Figure 1, when the copy-on-write block is changed, a new one is added. Blocks are assigned and updated. Then in the pointer to this new block COW flag is set. CO of pointer 110A of original anode 110 The W bit is cleared. In this way, when the clone anode 120 is created, the clone anode 120 Pointer 120A also references data block 114. Original anode 110 too The clone anode 120 also refers to data block 114. Also, day Tabloc 124 also clears pointer 112A in the original indirect block 112 It is modified as indicated by the COW bit. In this way, Clone Anno When the card is created, the indirect block 122 is created. Indirect block 122 Inter 122A refers to data block 124 and COW on pointer 122A. The bit is cleared. Indirect block 122 of the original anode 110 and clone The indirect block 122 of the anode 120 both refers to the data block 124. To. Figure 1 shows the anode co-node for making a clone anode 120 for a single file. Shows a pee operation. However, the clone anode was changed in the file system Must be created for each file that has a data block. Clone place In that case, all inodes must be copied. In the file system By creating a clone anode for all modified files, quite a bit Will consume a large amount of disk space. In addition, the episode system , Since each pointer has only one COW bit, it has a large number of clones. Cannot port. A single COW cannot distinguish one or more clones .. There is no second COW that can be set for one or more clones. A "clone" of a file set is read by the active file set and also A writable, read-only copy of the active set of files. The clone is Implemented using COW technology, block by block, active file set and data Share Tabrock. The episode system is stored in a set of files Copy each anode and perform cloning. When you first clone The writable anode of the active file set is also the same as the cloned anode Refers to the same data block. But the direct block in the original anode and The disk address of the indirect block is tagged as COW. Et cetera Therefore, updating the writable file set does not affect the clone. COW When a block changes, a new block is assigned in the file system , Will be updated with the change. COW of pointers to this new block The flag is cleared. The traditional episode system is the entire inode file in the file system And clone all indirect blocks. The episode system is For blocks used by both the active file system and the clone Allows copy-on-write (COW) bits to be set on all pointers Duplicate all inodes and indirect blocks. In the episode system, Acte The new data written to the live file system is part of the clone, These boots should not be overwritten with "old" data that should not be modified for It is important to check the lock. Use up to 32MB on an IGB disk to clone with this prior art To use. This prior art also maintains eight clones of the file system. However, an IGB disk with a 256MB disk (for a 4KB block) Use space. Thus, prior art has many to prevent data loss. Cannot use a clone of. Instead, like a tape backup device, Auxiliary storage means other than disk drive backs up the file system It is used to facilitate. The clone is arranged at the moment when the clone is created. Used to back up the file system in a compatible state. Phi By cloning the system, the clone becomes the active file system. Shuts down the stem and prevents users from using the file system It is possible to back up to the auxiliary storage means. In this way, Kuro Use while the file system is backed up for integrity Allows a person to continue to access the active file system. Then , Once the backup is completed once, the clone will be deleted. Episode system Many clones because each pointer has only one COW bit Cannot be supported. A single COW bit cannot distinguish one or more clones I. There is no second COW bit that can be set for more than one clone. Cloning the file system One of the disadvantages of this prior art system is , It requires duplication of all inodes and all indirect blocks in the file system It is important. On systems with many small files, it's an inode Even so, it uses a significant percentage of the total disk space in the file system. Tato e For example, a 1GB file system filled with 4KB files is a 32MB i Has a node. Is it possible to create an episode clone like this? A large amount (ie, many megabytes) of disk troughs that use a lot of disk space Produces traffic. As a result of this condition, the file system black It takes a considerable amount of time to complete the game. Another disadvantage of this prior art system is the large number of files in the same file system. The point is that it is difficult to make a loan. As a result, the clone will be a file One at 1 o'clock for short-term operations such as backing up the system on tape It tends to be used and then erased. Outline of the invention The present invention maintains a file system in a consistent state and provides a file system. Provides a way to make a read-only copy of the stem. Align file system Changes to the file system are tightly controlled to keep it sexual It is controlled. This file system is self-aligned from one self-aligned state to another Proceed to the state. Self-regulating on disk rooted by the root inode The set of compatibility blocks is called the alignment point (CP). To implement the consistency point WAFL always puts new data on unallocated blocks on the disk But never overwrite existing data. File system information The (fsinfo) block contains a new root inode for the inode file. When updated by writing to, a new consistency point arises. In this way, Lou The state of the file system existing on the disk unless the inode is updated Does not change. Further, the present invention is a snap system which is a virtual read-only copy of a file system. Also create a snapshot. When created for the first time, the snapshot is , Does not use disk space. It has many for the same file system Designed to allow you to create different snapshots. Traditional file system By duplicating the entire inode file and all indirect blocks Clone, but unlike this, the present invention describes an inode file. - Duplicate only. Thus, the actual disk space required for the snapshot It is only 128 bytes used to store duplicate inodes. snap shot The 128 bytes of the invention required for the prior art clones are several megabytes. Much less than In the present invention, new data written to the active file system can be stored. Prevents overwriting "old" data that is part of a napshot (1 or more) To. Old data will not be overwritten as long as it is part of a snapshot It is necessary. This uses a multi-bit free block map Achieved by. Most prior art file systems have blocks assigned Freebro with a single bit per block to indicate if it is Use a cook map. The present invention provides a block map with 32-bit entries. Use. The first bit is used by the block by the active file system Indicates whether or not it is done, and the remaining 20 bits are used up to 20 snapshots. However, some of the 31 bits may be used for other purposes. A brief description of the drawing FIG. 1 is a block diagram showing a prior art "clone" of a file system. .. FIG. 2 is a diagram showing a list of inodes with dirt buffers. Figure 3 shows a WAFL on-disk inode. Figures 4A-4D show WAFLs with different levels of indirection. It is a figure which shows the on-disk inode of. FIG. 5 is a flow chart showing a method of generating matching points. FIG. 6 is a flow chart showing step 530 of FIG. 5 for generating a matching point. Figure 7 shows the flow showing step 530 in Figure 5 for creating a snapshot. It is a figure. FIG. 8 is a diagram showing an incore inode of WAFL according to the present invention. .. 9A-9D show the WAFLs with different levels of indirectness according to the present invention. It is a figure which shows the in node in memory. FIG. 10 is a diagram showing an in-memory inode 1020 for a file. 11A to 11D are diagrams showing a block map file according to the present invention. .. FIG. 12 is a diagram showing an inode file according to the present invention. 13A to 13B are diagrams showing an inode map file according to the present invention. .. FIG. 14 is a diagram showing a directory according to the present invention. FIG. 15 is a diagram showing a file system information structure. FIG. 16 is a diagram showing a WAFL file system. 17A to 17L are diagrams showing the generation of matching points. 18A to 18C are diagrams showing the generation of snapshots. FIG. 19 is a diagram showing changes to the inode file. Figure 20 shows the files used to keep the file system consistent. It is a figure which shows the system information block. 21A to 21F are detailed views showing the generation of snapshots. Figure 22 has three snapshots, each referencing a common file. It is a figure which shows the active WAFL file system. FIGS. 23A to 23B are diagrams showing the update of the a time. Detailed description of the invention A read-only copy creation system in a file system will be described. Book Discs to explain in more detail throughout the description of the invention. ) Numbers and properties, disk block size, etc. will be described in detail below. However, obviously, even without such a detailed explanation, experts in the art If so, it is possible to carry out the present invention. For example, the present invention is obscured The known features are not described in detail in order to avoid this. Lite Anywhere File System Layout The present invention is a write anywhere. Use the file system layout (WAFL). This disc format The stem is block-based (that is, a 4KB block with no fragments) And simply specially formatted, using inodes to represent the file Contains a directory of files. WAFL is a file system layer Use multiple files to store the metadata that describes the out. WAF L metadata files are inode files, blockmap files Includes file and inode map (inomap) files. Inode file is a file Contains an inode table for the file system. Which de block map file is Indicates whether a disk block is assigned. Inode map is which i no Indicates whether or not is assigned. On-disk and in-core WA The FL inode will be described later. On-disk WAFLi node WAFL inodes are different from traditional inodes. On disk (on disk) ) WAFLi nodes each have the same level of indirection Refers to 16 blocks. The block number is 4 bits long. In one inode File recursives by using block numbers with the same level of indirectness in Making the process easier. Figure 3 shows a browser representing an on-disk inode 310. It is a figure. On-disk inode 310 is the same as standard inode information 310A It consists of 16 block number entries 310B with a level of indirectness. i No File information 310A is the file owner, permission, file size, access tie It consists of information on the above, but these are known to those skilled in the art. on Disk inode 310 has multiple block numbers with different levels of indirectness. It is different from the conventional inode consisting of issues. All contained in one inode 310 By keeping the indirectness of block number entry 310B of The illumination system can be simplified. For small files of 64 bytes or less, instead of 16 block numbers , The data is stored directly in the inode itself. Figure 4A shows the inode shown in Figure 3. Represents a level 0 inode 410, similar to 310. But inode 410 From 64 bytes of data 410B instead of 16 block numbers 310B Become. Therefore, for very small files, split the disk block You don't have to hit it. For files smaller than 64KB, each of the 16 block numbers It directly references a 4KB data block. Figure 4B shows 16 block numbers 31 Represents a level 1 inode 310 consisting of 0B. Block number entry 0 ~ 15 Refers to the corresponding 4KB data blocks 420A to 420C. 16 blocks for files larger than 64KB and smaller than 64MB Each of the numbers refers to a single indirect block. In this case, 4KB single indirect The lock consists of 1024 block numbers that reference a 4KB data block. To. Figure 4C shows 16 single indirect blocks 430A to 430C. Represents a level 2 inode 310 consisting of block number 310B. Shown in Figure 4C As such, block number entry 0 points to the single indirect block 430A. Alone Indirect block 430A refers to 4KB data blocks 440A ~ 440C It consists of 1024 block numbers. Similarly, each single indirect block 430B ~ The 430C can address up to 1024 data blocks. 16 blocks in an inode for files larger than 64MB The number refers to the double indirect block. Double indirect blocks of 4KB each It consists of 1024 block numbers that point to the corresponding single indirect blocks. in this case , Each single indirect block has 1024 block numbers pointing to 4KB data blocks Consists of. In this way, addresses up to 64GB are possible. Figure 4D shows Block number entries 0, 1 and 15 are double indirect blocks 470A,470 A check consisting of 16 block numbers 310B that refer to B and 470C respectively. Represents the inode 310 of Bell 3. Double indirect block 470A is a single indirect block 1024 block number entries 0 to 1023 pointing to 480A to 480B It consists of. In this case, each single indirect block 480A to 480B has 1024 units. Refer to the data block. As shown in Figure 4D, the single indirect block 480A is 1 Refers to 024 data blocks 490A to 490C and is a single indirect block 48 0B refers to 1024 data blocks 490C to 490F. WAFLi node in memory Figure 8 is a block diagram representing the in-core WAFLi node 820. is there. The in-memory inode 820 is the on-disk inode 31 (shown in Figure 3). 0 information, WAFL buffer data structure 820A and 16 buffer points It consists of Ta 820B. WAFLi node in memory has a size of 300 bytes To do. The WAFL buffer corresponds to a 4KB block stored on disk 4KB in memory. In-memory inode 820 has different levels of indirectness It is different from the conventional inode that refers to the buffer with. WAF in each memory Linode 820 refers to 16 buffers with the same indirectness level. Ba The puffer pointer is 4 bytes long. All bags included in one inode 820 File system by keeping the fapointer 820B at the same indirectness level You can easily do it. In-memory inode 820 is also a poi for linked lists From the in-consistency (IN_CP) and dirty flags Contains in-memory information 820C. The dirt flag has changed the inode itself Or the buffer referenced by the dirt flag has been modified. Is shown. The IN_CP flag is set by the inode at the consistency point (described later). Used to mark something. About the pointer for the linked list, Described below. Figure 10 shows the files referenced by WAFLi node 1010. This phi Indirect WAFL buffers 1020 to 1024 and direct WAFL buffers 10 It consists of 30 to 1034. In-node 1010 in WAFL memory is a standard i-node Data information 1010A (including the count value of the dirt buffer), WAFL buffer data Structure 1010B, 16 buffer pointers 1010C and standard on-disk It consists of inode 1010D. WAFLi node 1010 in memory is approximately It has a size of 300 bytes. On-disk inode is 128 bytes in size Is. WAFL buffer data structure 1010B has 16 buffer pointers The first pointer to 1010C and the on-disk block number 1010D It consists of a second pointer to refer to. Each inode 1010 has a reference dirt buffer count. i no De 1010 has a list of dirty inodes and / or a dirty buffer. You will be placed in the list of cards. All of the dirt buffers referenced by one inode If writing to the disk is planned or actually written , The count value of the dirt buffer for inode 1010 is set to 0. And , Inode 1010 follows that flag (that is, there is no dirt buffer) And will be queued again. This inode 1010 is processed by the next inode It will be cleared before it is cleared. In addition, the inode indicates that the inode is in the alignment point. Flag is cleared. Inode 1010 itself writes to disk at consistency point Be squeezed. The WAFL buffer structure is represented by the indirect WAFL buffer 1020. WAFL buffer 1020 has WAFL buffer data structure 1020A and 10 4KB buffer 1020B consisting of 24 WAFL buffer pointers and 10 Consists of 4KB buffer 1020C consisting of 24 on-disk block numbers .. The WAFL buffer data structure has a size of 56 bytes and has two Consists of pointers. One of the pointers to the WAFL buffer data structure 1020A , Refer to 4KB buffer 1020B, another pointer is buffer 1020 See C. In Figure 10, the 16 buffers of WAFLi node 1010 Po Inter 1010C has 16 independent indirect WAFL buffers 1020 ~ 1024 Point to. The WAFL buffer 1020, on the other hand, has 1024 direct WAFL buffers. See structures 1030-1034. WAFL buffer 1030 directly WAF It represents the L buffer. Direct WAFL buffer 1030 with WAFL buffer data structure 1030A , Includes cached version of corresponding on-disk 4KB data block 4 It consists of KB direct buffer 1030B. Direct WAFL buffer 1030, It does not have a 4KB buffer like the contact WAFL buffer 1020. WAFL bag The second buffer pointer of the data structure 1030A is set to 0 and the second 4KB. Do not point to the buffer. This prevents inefficient use of memory and frees memory Avoid allocating to unused buffers. WAFL memory in the WAFL file system, as shown in Figure 10. Inode structure 1010 in, WAFL buffer structure 1020 ~ 1024 and Refer to the tree from 1030 to 1034. This is an indirect block and / or Referenced by a standard inode consisting of block numbers that point directly to the block, Similar to a block tree on a disk. Thus, WAFLi node 10 10 is an on-disk inode 101 consisting of 16 volume block numbers 0D and WAFL buffer structures 1020 ~ 1024 and 1030 ~ 1034 Consists of 16 buffer pointers 1010C pointing to. WAFL buffer 103 0 to 1034 are the caps of the blocks referenced by the volume block number. Contains shu ingredients. WAFL in-code i-node 1010 has 16 buffer points Includes data 1010C. Next, the 16 buffer pointers 1010C are WAFL. The root of the tree in buffers 1020 ~ 1024 and 1030 ~ 1034 Referenced by WAFL buffer structure 1010B. In this way, each WAFL The inode 1010 is the 16 buffer pointers 1010 in the inode 1010. Contains WAFL buffer structure 1010B pointing to C. This causes it to be executed recursively It simplifies the algorithm for processing the tree of buffers. Temporarily inode 10 16 buffer pointers 1010C out of 10 are WAFL buffer structure 1010 Buffers 1020 ~ 1024 and 1030 ~ 1 if not represented by B It becomes difficult to implement a recursive algorithm for manipulating the entire tree of 034. Figures 9A-9D represent inodes with different levels of indirectness. Figure 9A ~ Figure 9D shows a simplified indirect and direct WAFL buffer to show the degree of indirectness. Is represented. However, the WAFL buffer of FIG. 9 is the corresponding indirect and direct of FIG. It should be understood to represent a tangent buffer. Small files of 64 bytes or less As for, the data goes directly into the inode instead of the 16 buffer pointers. It is saved in. Figure 9A shows a buffer port with 16 inodes 820 shown in Figure 8. Except that it consists of 64 bytes of data 920B instead of the inter 820B Therefore, the level 0 inode 820 is the same as this inode 820. Therefore, additional buffers will be allocated for very small files. There is no point. For files smaller than 64KB, each of the 16 buffer pointers , Directly refer to the 4KB direct WAFL buffer. Figure 9B shows 16 buffer ports Represents a level 1 inode 820 consisting of the inter 820B. Buffer pointer P TR0 ~ PTR15 are the corresponding 4KB direct WAFL buffers 922A ~ 92 Refers to 2C. For files larger than 64KB and smaller than 64MB, 16 bags Each fapointer references a single indirect WAFL buffer. In this case, 4 each KB single indirect WAFL buffer references 4KB direct WAFL buffer 1 It consists of 024 buffer pointers. Figure 9C shows 16 single indirect WAFL bars. From 16 buffer pointers 820B that reference the iffers 930A to 930C Represents a level 2 inode 820. Buffer pointer P, as shown in Figure 9C TR0 refers to the single indirect WAFL buffer 930A. Single indirect WAFL buff A 930A refers to 4KB direct WAFL buffers 940A ~ 940C 10 It consists of 24 pointers. Similarly, a single indirect WAFL buffer 930B ~ 93 Each 0C can address up to 1024 direct WAFL buffers. 16 buffer poi for inodes for large files larger than 64MB The data refers to the double indirect WAFL buffer. 4KB each 4KB double indirect WAFL buff A consists of 1024 pointers to the corresponding single indirect WAFL buffer .. In this case, each single indirect WAFL buffer points to a 4KB direct WAFL buffer. It consists of 1024 pointers. In this way, you can address up to 64GB. In Figure 9D, the pointers PTR0, PTR1 and PTR15 are double indirect WAFLs. 16 points referencing buffers 970A, 970B and 970C respectively Represents a level 3 inode 820 with a data 820B. Double indirect WAFL buff 970A points to 1024 single indirect WAFL buffers 980A-980B It consists of 1024 pointers. Then each independent indirect WAFL buffer 980A ~ 980B refers to 1024 direct WAFL buffers. Shown in Figure 9D As such, the single indirect WAFL buffer 980A has 1024 direct WAFL buffs. Refer to 990A to 990C. And a single indirect WAFL buffer 980B Refers to 1024 direct WAFL buffers 990D ~ 990F. directory The directory in the WAFL system is divided into two sections, 4KB Bro. It is saved in the box. FIG. 14 shows the directory block 1410 in the present invention. explain. Each directory block 1410 is a fixed-length directory entry structure. The first division 1410A consisting of structures 1412 to 1414 and the actual directory name 1 It consists of the second division 1410B including 416 to 1418. Each directory ent The file contains the file ID (id) and generation. This information is in our business It is not shown in Figure 14 as it is well known in the world. First division of the directory block Each entry 1412-1414 in 1410A is included in the second division 1410B. It has a pointer to its name. In addition, each entry 1412-1 414 contains a hash value that depends on its name contained in the second segment. , The name is checked only when the hash hits (hash match). Example For example, entry 1412 of the first division 1410A has a hash value of 1412A and a port. Consists of Inter 1412B. The hash value 1412A can be the second division 1410B. Weird Directory name "DIRECTORY_A" stored in long entry 1416 It is a value that depends on "BC". The pointer 1412B of entry 1410 is the second ward. Refers to variable length entry 1416 for minutes 1410B. Fixed length in the first division 1410A Name lookup by using directory entries 1412-1414 The process of uploading becomes faster. See the next entry in directory block 1410 No operation is required to attach it. In addition, entry 1 in Category 1 1410A Line fill data cache by keeping 412-1414 small The hit speed of file systems with is improved. Metadata WAFL is a file system in a file, known as metadata Holds information that describes. Metadata is inode file, inodema It consists of a file and a blockmap file. WAFL is metadata In a file that can be written anywhere on the disk Exists. All WAFL metadata is kept in the file, so it's positive Can be written anywhere, just like any other file in the file system To. The first metadata file is all other files in the file system It is an "inode file" that contains the inode that describes. Figure 12 shows the inodef It is the figure which showed the pile 1210. Inode file 1210 is a fixed disk Unlike the conventional system that writes the "inode table" in the specified location, You can write anywhere on the disk. Inode file 1210 is i For each file in the file system, except for the file 1210 itself Includes inodes 1210A-1210F. The inode file 1210 is Pointed to by an inode referred to as "to inode". The root inode is Referenced as a file system information (fsinfo) block described below It is held in a designated place on the desk. The inode file 1210 itself is It is stored in a 4KB block (or a 4KB buffer in memory) on the screen. In Figure 12, inodes 1210A-1210C are stored in the 4KB buffer 1220. It shows that it is done. On-disk i-no with a size of 128 bytes - 4KB buffer (or block) is more than 32 inodes To. In-memory inode file 1210 from WAFL buffer 1220 To. When an inode in one memory (ie 1210A) is loaded, The on-disk inode part of inode 1210A in the moly is the inode file 1 Copied for 210 buffers 1220. The buffer data itself is Loaded from the desk. Data is written to disk in reverse order. Onde The in-memory inode 1210A, which is a copy of the inode, is the inode fa It is copied to the corresponding buffer 1220 of Il 1210. And inode phi Le 1210 is assigned to write and the inode file 1210 is loaded. Data is stored in the iffa 1220. Other metadata files are "blockmap" files is there. FIG. 11A represents one blockmap file 1110. Blockma File 1110 is 32 for each 4KB block in the disk system. Includes bit entries 1110A-1110C. This is also a free block Used as a map file. The block map file 1110 is one Indicates whether a disk block has been allocated. Figure 11B shows the block map It is a diagram of one block entry 1110A in file 1110 (shown in Figure 11A). To. As shown in Figure 11B, entry 1110A is 32 bits (bits 0 to bi). It consists of 31). Bit 0 of entry 1110A is the active file The system bit (FS bit). The FS bit of entry 1110A is paired Indicates whether the corresponding block is part of the active file system. D Bits 1 to 20 of the entry 1110A are snapshot 1 corresponding to the block. A bit indicating whether or not it is a part of ~ 20. Next high-order 10 bits (bit 2) 1 to bit 30) are reserved. Bit 31 matches entry 1110A It is a point bit (CP bit). All bits in 32-bit entry 1110A for block (bits 0 ~ bi) When t31) is clear (set to a value of 0), the file In the system, one block is valid as a free block. Figure 11 C Indicates that the disk block is free entry 1110A in Figure 11A Represents. Thus, when all bits 0 to 31 have a value of zero, the block The block referenced by entry 1110A in map file 1110 is Lee. Figure 11D shows the allocation in the active file system. Represents entry 1110A in Figure 11A, which shows all of the blocks. As FS bit When bit 0 referenced by is set to a value of 1, the blockmap file Entry 1110A in 1110 is part of the active file system Shows a block. Bits 1 to 20 are blocks, if any Used to show a corresponding snapshot that references. About snapshots Will be described in detail later. Even if bit 0 is set to a value of 0, it is not always blown. It does not indicate that the hook is assignable. To allocate blocks Must have all snapshot bits zero. But one of the consistency points Entry 1110 when loaded into memory bit 31 to record as part Bit 31 of A always has the same state as bit 0 on the disk. Other metadata files are used as free inode maps "i" It is a "node map" (inomap). Figure 13A shows one inode map. Represents file 1310. The inode map file 1310 is shown in Figure 12. 8-bit entries 1310A ~ 1 for each block in the inode file 1210 Including 310C. Each entry 1310A ~ 1310C is an inode file 12 The count value of the assigned inodes in the 10 corresponding blocks. Figure 13A shows Shows the values 32, 5 and 0 in entries 1310A-1310C, respectively. Inode file 1210 is still free which inode in the block I have to find out. However, a large number of random blocks can be printed from the disk. No need to load into Mori. Each 4KB block of inode file 1210 1 The 220 holds 32 inodes. Therefore, the inode file 121 8-bit inode map entries for each block of 0 1310A-1310C Can have a value in the range 0-32. Inode file 1210 If block 1220 does not have an in-node in use, that inode map Isle Entries 1310A to 1310C in 1310 are zero. Block 1220 When all inodes in the inode file 1210 are in use, i no Entries 1310A to 1310C in the domap file 1310 have a value of 32. To. Figure 13B shows the 4KB blocks 1340A-134 of the inode file 1340. Represents an inode map file 1350 that references 0C. For example, inodefa Il 1340 has 37 in 3 4KB blocks 1340A ~ 1340C Save the inode. Blocks 1340A ~ 134 of inode file 1340 0C contains 32, 5 and 0 used inodes, respectively. Block mat Entries 1350A to 1350C in file 1350 are inodes, respectively. See blocks 1340A to 1340C in file 1340. in this way, In-node map file entries 1350A-1350C are in-node files For blocks 1340A to 1340C of Le 1340, 32 and 5 respectively And has a value of 0. Meanwhile, inode map file entry 1350A ~ 1350C are each block 1340A ~ of inode file 1340 It shows 0, 27 and 32 free inodes of 1340C. As shown in FIG. 13, instead of the count value, the inode map file 1310 d. It is disadvantageous to use bitmaps for inputs 1310A to 1310C. Because for block 1220 of inode file 1210 (shown in Figure 12) Entry 1310A ~ 1310C requires 4 bytes instead of 1 byte Because there is. Free inno in block 1220 of inode file 1210 The mode does not need to be shown in the inode map file 1310. Because i This is because the node itself contains such information. FIG. 15 represents the file system information (fsinfo) structure 1510. File system Stem root inode 1510B is held in place on disk The location is known during the boot of the file system. File system The stem information block is not metadata but is part of the WAFL system .. Root inode 1510B is an inode that references inode 1210. So This is the block number in the file system, the file system creation time, etc. Information Containing 1510A Part of the file system information structure that contains. This various Information 1510A further consists of a checksum 1510C (discussed below). In another embodiment, this information 151, except for the root inode 1510B itself. 0A can be kept in the metadata file. File system information Two identical copies of structure 1510 are kept in place on disk .. Figure 16 shows the WAFL file system 1670 in a consistent state on disk. Representing this file system is two file system information blocks 1610 And 1612, inode file 1620, blockmap file 1630 , Inode map file 1640, root directory 1650 and typical File (or directory) consists of 1660. inode file 162 0 refers to other files 1630 ~ 1660 in file system 1670 It consists of multiple inodes 1620A to 1620D. Inode file 1620 Inode 1620A references blockmap file 1630. i no De 1620B refers to the inode map file 1640. inode 162 0C refers to the root directory 1650. Inode 1620D is typical File (or directory) 1660. Thus, i no Files are file except for file system information blocks 1610 and 1612. Refers to all files 1630 to 1660 in the file system 1670. Phi The system information blocks 1610 and 1612 are inode files, respectively. Contains copies 1610B and 1612B of the 1620 inode. File system Root inodes 1610B and 1 of stem information blocks 1610 and 1612 The 612B is a file system 1670 containing all metadata 1630 to 1640. Inode file 1620 that describes the remaining files 1630 ~ 1660 inside It is described. Therefore, root inodes 1610B and 1612B are Considered the root of the lock tree. WAFL system 1670 is this -To update the structure for its update method (consistency) and to take a snapshot Used for. These will be described later. List of inodes with dirty blocks In-node in memory of the WAFL file system (ie, W shown in Figure 10) AFLi node 1010) keeps different linked list according to each state It is possessed. For the inode, refer to the dirt block, as shown in Figure 2. The card is kept in the dirty inode list. Clean ballid data The containing inode is kept in a separate list. And have non-valid data The inode is kept separate. These are known in the art. The present invention Write to do using a list of inodes with dirty data blocks Make it easy to find all inodes that need to be assigned. FIG. 2 shows a list 210 of dirty inodes according to the present invention. Dirty inode The strike 210 consists of inodes 220 to 1750 in WAFL memory. Figure 1 As shown in 7, each inode 220-250 in WAFL memory is , Consists of pointers 220A to 250A pointing to other inodes in the linked list. For example, WAFLi nodes 220 to 250 are located at position 20 in memory, respectively. Stored at 48, 2152, 2878, 3448 and 3712. in this way Then, the pointer 220A of the inode 220 contains the address 2152. Therefore The WAFLi node 222 is pointed to. Next, WAFLi node 222 Refers to the WAFLi node with dress 2878. WAFLi node 230 Refers to WAFLi node 240. WAFL i-node 240 is i-node 1750 Point to. Pointer 250A on WAFLi node 250 contains a null value and therefore And do not point to other inodes. Thus, it is a list of dirty inodes 21 The last inode in 0. Each inode in Listing 210 is depicted in Figure 10. As you can see, it represents a file consisting of a buffer tree. Each inode 220 ~ At least one of the blocks referenced by 250 is a dirt buffer. The dirt buffer is written to the new disk location in the WAFL system. Contains modified data that must be included. WAFL always keeps the dirt buffer Write to a new location on the disc. Consistency point The WAFL disk structure described so far is static. In the present invention Changes to file system 1670 put file system 1670 in a consistent state Strongly controlled to keep. File system 1670 has one self-alignment Proceed from one state to another self-aligned state. Routed by root inode 1510B A set (or tree) of self-aligned blocks on an disk is called an alignment point (CP). U. To provide a consistency point, WAFL always allocates new data on disk. Write in unassigned blocks. WAFL overwrites existing data There is nothing to do. Thus, unless root inode 1510B is updated The date of file system 1670 represented by disk does not change. But For the file system 1670 to be useful, the file system is always new You have to refer to the well-written data, so a new consistency point is written. Must be. With reference to Figure 16, the new consistency point is first of all file system blocks. (Inode file 1620, block map file 1630, inodema (Including blocks in metadata files such as upload file 1640) Written by flushing to a new location on the disk. Fu New route inode 1610B, 1612B for file system 1670 Is then written to disk. This person who updates the file system atomically Using the law, the on-disk file system is by no means consistent. This o Disk file system 1670, root inodes 1610B, 1612 Reflect the old consistency point until B is written. Root inode 1610B, 16 Immediately after 12B was written, file system 1670 broke the new consistency point. To project. The data structure of file system 1670 can be updated in any order. File system 167 before inode 1610B, 1612B is updated Except for one condition that all blocks in 0 must be written to disk , There is no order condition for writing data to disk. Root inodes 1610B, 1612B are credited to convert to a new alignment point. It must be updated atomically again so that it can be relied upon. Root inode 1610B , 1612B file system information structure 1610, 1612 two identical WAFL does this by keeping a copy of. Root inode No. 16 of file system information structure 1610 while updating 1610B, 1612B A copy of 1 is written to disk, then file system information structure 1612 A second copy of is written. File system information structure 1610, 1612 Checksums 1610C and 1612C can be written to the disc respectively. File system information structure 1610, each containing a copy of the inode To detect the occurrence of a system crash destroying one of the 1612 copies used. Usually these two file system information structures 1610, 1612 Are the same. Algorithm to create a matching point FIG. 5 illustrates how to create a matching point. In step 510, system All "dirty" inodes in the software (new blocks containing modified data) Inode), whose contents are written to the disk, and only the contents are written to the disk. Marked as at the point. Others only when these writes are complete Writes from the inode are allowed to reach the disk. In addition, dirty writing While the is occurring, new changes can be made to the inode at the consistency point. I can't. In addition to flagging all dirty inodes that are part of the consistency point The global consistency point flag is raised in a strongly controlled manner for the changes required by the user. It can be set up like this. When the global consistency point flag is set, the user requests Changes that make are not allowed to affect the inode at the point of alignment. In addition, alignment Only inodes flagged as points have disk space for that dirty block Can be assigned. As a result, the state of the file system is when the consistency point begins. It is flushed to disk exactly as it was in. At step 520, a regular file is flushed to disk. Will be Flashing this legitimate file is a dirty blow in the legitimate file Tsu Steps to allocate disk space for the key and the corresponding WAFL buffer It consists of steps to write to disc. The inode itself is then the inode file It is flushed (copied) to. All inodes that need to be written , A list of inodes with a dirty buffer, or a dirty inode but dirty It exists in one of the list of inodes that does not have a buffer. Step 520 When finished, the normal inode no longer exists at the consistency point, everything coming in I / O request is a buffer that is still locked for disk I / O operations. If not used, these requirements will work. At step 530, a special file is flushed to disk. This Flush special files with two special files, an inode file and Allocate disk space for dirty blocks in blockmap files Steps, update consistency points to each entry in the blockmap file Steps to harmonize the active file system bits (FS bits) , And the steps of writing the block to disk. With inode files Writes that allocate blockmap files are overwrites that allocate them It's complicated because it changes those files themselves. Then step 5 At 30, an important block in disk I / O operation before the change is over Writes, while modifying these files to prevent them from being locked Be disabled. Also, in step 530, except for the file system information block, The only file system that is completely self-aligned and will try to be written to disk Since it is a point in time, the snapshot is created and removed (described later). To. One screen so that the same snapshot inode can be used in one path Knapshots are removed from the file system before new ones are created Is done. FIG. 6 is a flow chart showing the steps included in step 530. Step 5 30 allocates disk space to blockmap files and inode files , The active FS bit for each entry in the blockmap file To the CP bit. In step 610, the blockmap file of The inode for this is pre-flushed to the inode file. this thing Blocks in the inode file that contains the inode in the blockmap file Dirty and keep step 620 allocating disk space for that block I testify. In step 620, the disk space is inode and blockmap file. Assigned to all dirt blocks in the building. This dirt block , Block map file stains Bro in inode files including inodes Includes In step 630, the inode for the blockmap file is covered But this time, the actual inode is the inode file Written in the previously flushed block in. Step 6 10 is a block of the inode file that contains the inode of the blockmap file Is already dirty. Thus, as in step 620, another Write assignments do not need to be scheduled. In step 640, for each block in the blockmap file Entry is updated. Each entry is dirty in the blockmap file Convert the active FS bit to the CP bit for all entries in the block Updated by beeping (ie copying bit 0 to bit 31) Is done. At step 650, everything in the blockmap and inode file The dirty block is written to the disc. Only entries in dirty blocks in the block map file are in step 6 At 40, the active file system bit (FS bit) is matched. It is necessary to copy to the (CP bit). Immediately after the alignment point, all the points Same for both FS and CP bits with active lockmap entry Has the same value. File system blockmap file over time Some active FS bits of the entry are cleared or set .. Blocks in the blockmap file that contain the changed FS bits follow hand, Marked as dirty. Blocks that are clean during the next match point are again It doesn't have to be peeped. A clean block is clean at the previous alignment point and also Nothing has changed in those blocks since then, so they are not copied .. Thus, Acty with the same value in all blockmap entries As long as the file system is first generated with the FS and CP bits Therefore, only entries with dirty blocks need to be updated at each consistency point. To. File system information (fsinfo) in step 540, with reference to Figure 5. The block is updated and then flushed to disk. File system information Information block decides to write a new root inode for the inode file Will be updated more. The file system information block is written twice. Introduction Written in one position and then in a second position. These two writes Self-aligned file system when a system crash occurs during a write Is done so that is on the disk. Therefore, if the second file If the system crashes while writing the stem information block, new A match point exists, or if the first file system information block fails If so, there is a previous match (on disk before the recent match started). Fa Correct checker when the file system is restarted after a file failure Best creation for consistency points in file system information blocks with value (generation) The count value is used. This will be explained in detail later. At step 550, the alignment point is completed. This means that the dirty inode The match point that was delayed because it was not part of the match point is queued again. And request. Inodes whose state has changed during the match point have a match point weight (C). P_WAIT) Queued. The CP_WAIT queue has finished step 540 The inode that changed before and after step 510 where the alignment point started Hold. At the end of the match, the inode in the CP_WAIT queue becomes dirty A regular list of inodes with buffers and a dirty inno with no dirty buffer In the list of cards, it is queued again. Single ordering condition of integrity As shown in FIGS. 20A-20C, the present invention has a single ordering condition. To do. This single ordering condition is that all other blocks are written to disk. When the file system information block 1810 is written to disk only after That is to say. Writing in file system information block 1810 is atomic Yes, otherwise the entire file system 1830 will be lost. Thus, the WAFL file system has a file system information block 181. Requires 0s to be written at once, not in a consistent state. Shown in Figure 15 As such, each file system information block 1810 (1510) is a checker Includes 1510C and created count 1510D. Figure 20A shows the created counts for file system information blocks 1810 and 1870. The update of 1810D and 1870D is explained. Consistency point (or snapshot) Is performed, the creation count value of the file system information block is updated. Figure 20A shows a creation meter with the same value N, which indicates the consistency point of the file system. Two file system information blocks with the numbers 1810D and 1870D 18 Indicates 10, 1870. The two file system information blocks were previously aligned See point (old file system on disk) 1830. File system A new version of the game exists on disk and comes in as a new alignment point 1831. Be illuminated. The created count value is incremented at each matching point. In Figure 20B, the creation count of the first file system information block 1810 The value 1810D is updated and given a value of N + 1. This is then written to disc Be included. Figure 20B shows the creation count value 1 of the file system information block 1810. Shows the value N + 1 of 810D, but in the second file system information block 1870 The created count value 1870D has a value N. File system information block 181 0 refers to the new consistency point 1831, whereas the file system information Block 1870 refers to the old consistency point 1830. Next, it is shown in Fig. 20C. File system information block 1870 created count value 1870D updated Is written to the disc. In Figure 20C, the file system information block The created count value 1870D of 1870 has the value N + 1. Therefore, these two File system information blocks 1810 and 1870 have the same creation count value N + 1 Have. System crash occurs between file system information block updates At this time, each copy of file system information blocks 1810 and 1870 is self-contained. Has self-matching checksums (not shown), but created counts 1810D and 187 One of 0D has a larger value. System crash is a file system Occurs when is in the state shown in Figure 20B. For example, a book as shown in Figure 20B Creating a file system information block 1810 in a preferred embodiment of the invention. Count value 1810D updated before second file system information block 1870 Will be done. Therefore, the created count value 1810D (value 1) is the file system information. Create block 1870 Greater than the count value 1870D. First file system It is a system classy because the creation count value of information block 1810 is higher Selected to recover the file system after the operation. This is the first phi The system information block 1810 is indicated by its creation count value 1810D. This is because it contains newer data. First file system information block If it gets corrupted due to a system crash during the update, the file system Another copy of the information block 1870 makes the file system 1830 consistent Used to recover to. Two file space information blocks 1810 and 1870 at the same time in the present invention It cannot be updated. Therefore, file space information blocks 1810 and 1 At least one copy of the 870 exists in the file system. this child Allows the system to always be restored to a consistent state. WAFL does not require a special playback process. This is logging, ordered Writes (ordered writing), and often order dry with recovery It is different from the conventional technology that uses This is RAID-protected data corruption Or only software can destroy the WAFL file system. Shi To avoid losing data in the event of a stem failure, WAFL is up to date Can keep a log of non-destructive transactions for all operations performed after the consistency point To. This log is completely independent of the WAFL disc format and is easy to operate. Only needed to prevent loss during a stem crash. But fa Not required to maintain the integrity of the ill system. Creating a consistency point As explained earlier, the change to the WAFL file system is the file system. It is strongly controlled to keep it consistent. Figures 17A to 17H are WAFs. Shows the creation of a consistency point for the L file system. To create a matching point, see Figure 5 and Figure Explained with reference to 6. In Figures 17A to 17H, buffers that have not changed are marked with an aster on that side. Has no risk. Therefore, the buffer corresponds to the on-disk block. Contains the same data as. Thus, the block can be loaded into memory, but its No change with respect to the on-disk version. One asterisk (*) A buffer with is on the side refers to a dirty buffer in memory (its data has changed) Will be). A buffer with a double asterisk (**) on the side is allocated to disk space. Refers to the dirt buffer that is being applied. Finally, a triple asterisk (***) The buffer on the side is a dirty buffer that is written to a new block on the disk. is there. This method of representing the state of the buffer is also used in FIGS. 21A-21E. Is done. Figure 17A shows an i with a dirt buffer consisting of inodes 2306A and 2306B. Here is a list of nodes 2390. Inodes 2306A and 2306B are buffers Refer to the tree (s) of. Where at least one buffer in each tree has been edited. First, the alignment flag 23 for inodes 2306A and 2306B 91 and 2392 are cleared (0). Have a dirt buffer about this system A list of inodes 2390 is shown, which is obvious to those skilled in the art, inodes. Other lists may also exist in memory. For example, a dirty inode However, a list of inodes that do not have a dirty buffer is kept in memory. Also, These inodes must be marked as being at a consistent point. these are, Dirty inode does not refer to dirty blocks, but dirty inode file Must be flushed to the disc in order to write the content to the disc .. This is done in step 520 of FIG. Figure 17B shows file system information block 2302, inode file 23. 46, from blockmap files 2344 and files 2340, 2342 Represents the WAFL file system of the matching point before becoming. File 2340 is it Consists of blocks 2310 ~ 2314 containing data "A", "B", "C" respectively .. File 2342 is a block containing data "D", "E", and "F", respectively. It consists of 2316 ~ 2320. Block map file 2344 is block 23 Consists of 24. Inode file 2346 with two 4KB blocks 2304 It consists of 2306. The second block 2306 is file 2340, file 2 Inodefa that references 342 and blockmap file 2344 respectively It consists of Il 2306A ~ 2306C. This is the file number on the inode Is shown in block 2306 by listing. File system Information block 2302 consists of a root inode. This root inode is i See blocks 2304 and 2306 in node file 2346. thus, Figure 17B shows the file system information block 2302 containing the root inode. Shows the tree of buffers in the routed file system. Figure 17C shows two changes for blocks 2314 and 2322 in memory. Explain the buffer that was created. The active file system has data "C" The containing block 2314 is modified to be removed from file 2340. Also, the data "F" stored in block 2320 has been changed to "F prime". It is stored in the buffer for disk block 2322. Disc block The data to be changed contained in the buffer for 2314 and 2322 is at this time. It exists only in memory at a point. Active file system in Figure 17C All other blocks in the tem are unchanged and therefore ass beside them Has no tarisk. But some or all of these blocks You may have the corresponding clean buffer in memory. Figure 17D shows entry 23 of blockmap file 2344 in memory. 24A ~ 2324M will be described. Entry 2324A ~ 2324M is a block Included in buffer for 4KB block 2324 of map file 2344 .. As explained earlier, bit 0 and bit 31 are the FS bit and CP, respectively. It's a bit. The matching point bit (CP bit) starts and ends at one matching point. Consistency to ensure that the corresponding block does not change when not Set between points. Bit 1 is the first snapshot bit (discussed later) ). Blockmap entries 2324A and 2324B are shown in Figure 17B. As you can see, the 4KB blocks 2304 and 2306 of the inode file 2346 are It is in the active file system (FS bit = 1) and at the consistency point (CP bit = 1) T = 1) is shown. Similarly, the other blocks 2310 ~ 2312 and 2316 ~ 23 20 and 2324 are in the active file system and are at the same point Shown. However, blocks 2308, 2322 and 2326 ~ 2328 are Also on the active file system (as shown on note 0 and bit 31, respectively) Not even at the consistency point. The entry for the removed block 2314 is the FS bit Has a value of 0, indicating that it has been removed from the active file system. In step 510 of Figure 5, all "dirt" blocks in the system Is marked as being at a matching point. Dirty inodes are dirty inodes and dirty inodes Contains both inodes that reference the buffer. Figure 171 shows i with a dirt buffer Shows a list of nodes. Here, the matching point hula of inodes 2306A and 2306B 2391 and 2392 are set (1). Inode 2306A is Acty Contains data "C" for file 2340 that should be removed from a bad file system See block 2314. Block 2306 for inode file 2342 Inode 2306A references file 2342. A bu containing the data "F" Lock 2320 has changed and is split by a new block containing data "F" Must be hit. In step 510, dirty inodes 2306A and 2 306B is copied to the buffer for block 2308. Block 23 The buffer for 06 is subsequently written to disk (step 530). This This is shown in Figure 17E. The modified data exists only in memory and Buffer 2308 is marked dirty. Arrangement of inodes 2306A and 2306B The point flags 2391 and 2392 are cleared (0), as shown in Figure 17A. .. This frees these inodes for use by other processes. At step 520, the legitimate file is flushed to disk. This Thus, block 2322 is allocated in disk space. File 2340 Block 2314 has been deleted and therefore this block until the end of the alignment point Nothing happens to Ku. Block 2322 at step 520 Written to disc. These are shown in Figure 17F, where the blocks Buffers for 2322 and 2314 are written to disk (*** by Mar Will be asked). No intermediate disk space allocation (**) is shown. inodefa In-nodes 2308A and 2308B of block 2308 of Il 2346 are i-no It is flushed to a file. Inode 2308A in block 2308 is See blocks 2310 and 2312 of file 2346. inode 2308B Refers to blocks 2316, 2318, 2322 for file 2342 To. As shown in Figure 17F, the disk space is block 23 of inode 2346. Assigned for 08 and direct file 2322 for file 2342 To. However, the file system itself is not updated. Thus, the file The system remains consistent. In step 530, the blockmap file 2344 is stored on disk. Be rushed. This is shown in Figure 17G, where blockmap file 2 344 is shown as dirty by an asterisk. In step 610 of Figure 6, the inode for the blockmap file is , Flashed in advance of the inode file, as shown in Figure 17H .. Inode 2308C is located in block 2306B of inode file 2346. It is rushed. However, inode 2308C still sees block 2324 Illuminate. In step 620, the disk space is the blockmap file 2 Assigned for 344 and inode file 2346. Block 2308 Is allocated for inode file 2346 and block 2326 is Lot Allotted for the cmap file 2344. As explained above, i no Block 2308 in file 2346 is a block map file 2644 Includes pre-flushed block 2308C for. Step 63 At 0, the inode for blockmap file 2344 is inode 2 Write to block 2308C previously flushed above in 346 Is done. Thus, the in-memory inode 2308C is updated in step 620. See block 2324 in, block to be written in block 2308 Copyed to a buffer in memory containing 2306. This is shown in Figure 17H Here, inode 2308C refers to block 2326. In step 640, each block in blockmap file 2344 Entry 2326A ~ 2326L for ku 2304 ~ 2326 is shown in Figure 17J. Will be updated. The blocks that have not changed since the start of the consistency point in Figure 17B , Have the same value in those entries. The entry is bit 0 (FS bit) It is updated by copying (g) to the matching point bit (bit 31). Bro Cook 2306 is not part of the active file system. Therefore, Bit 0 is equal to 0 (bit 0 is that of the inode file in step 620) When block 2308 is assigned to hold new data in the part To be fooled). This is shown for entry 2326B in Figure 17J. .. Similarly, entry 2326F for block 2314 in file 2340 It has bit 0 and bit 31 equal to 0. Block 232 of file 2342 Block 2324 with 0 and block map file 2344 is an entry as well. Treated as shown in 2361 and 2326K. In step 650, i Dirty block 2308 and block map file 23 for node file 2346 44 dirty blocks 2326 are written to disc. This is shown in Figure 17K And indicated by a triple asterisk on the side of blocks 2308 and 2326. With reference to FIG. 5, in step 540, file system information block 2 302 is flushed to disk, which is done twice. Thus, Figure 17L In, the file space (fs) information block 2302 is tainted and then (3 Written to disk (as indicated by a heavy asterisk). In Figure 17L A single file space information block 2302 is shown. As shown in the figure The file space information block 2302 is now in the inode file 2346. See locks 2304 and 2308. In Figure 17L, block 2306 In part of the inode file 2346, which is no longer in the active file space There is no. Similarly, referenced by inode 2308A in inode file 2346. File 2340 consists of blocks 2310 and 2312. Block 23 14 is no longer part of file 2340 at this consistency point. File 2342 blocks 2316, 2318 and 23 at this new alignment point It consists of 22, but block 2320 is not part of file 2342. further , Block 2308 in inode file 2346 consists of block 2326 See new blockmap file 2344. Active file system at one consistency point, as shown in Figure 17L File space information block 23 It will be updated by copying to 02. But block 23 of the previous consistency point 14, 2320, 2324 and 2306 remain on the disc. these The block has both the old alignment point 1830 and the new alignment point 1831 in Figure 20. Update the file system to ensure that it exists during step 540 It will never be overwritten when new. snap shot The WAFL system supports snapshots. Snapshot Is for the entire file system at the moment the snapshot is generated. This is a read-only copy. The newly created snapshot is active Refers to the same disk block that the file system refers to. Therefore, it Is created in a short amount of time and does not consume additional disk space. Active A data block in the file system has changed to a new location on disk Only when written, the snapshot begins to use additional space. WAFLs are up to 20 different snapshots numbered from 1 to 20 Support Therefore, WAFL is a multiplex of the same file system. Allows the creation of "clone". Each snapshot is an active phi Snapshot i, just as the system is represented by the root inode Represented by a node. The snapshot is the root day of the file system It is created by duplicating the data structure. In a preferred embodiment, root day The data structure is the root inode. But how to represent the whole file system Data structures can also be used. Snapshot inode is an inode It exists in a fixed position in the file. The 20 limit of snapshots is block It is determined by the size of the cmap entry. WAFL is a new snap Creating Shot N requires two steps. That is, the root inode Copy to inode for snapshot N and blockbit 0 Copy to bit N of each blockmap entry in the file. Bit 0 is roux Indicates the block pointed to by the tree below the inode. The result is a snapshot showing exactly the same disk block as the root inode. A new file system tree established by inode N. Suna If you set the bit corresponding to the block map of each block in the shot , Even if the active file no longer uses the snapshot block The release of the nap shot block is prevented. WAFL uses no new data Always writes to the disk location of, so the active file system changes Also The napshot tree remains the same. Newly created snapshot tree Refers to the exact same block as the root inode, so the new disk space is Not used. Over time, the snapshot will be released separately. See Kubrock. Therefore, over time, snapshots and Blocks shared by active filesystems are gradually reduced and snapped The space used by the shot increases. Snapshot is unacceptable It can be deleted when a number of disk blocks are used. A list of active snapshots, along with the snapshot name It is stored in a metadata file called the snapshot directory. De The status of the disk is updated as described above. Some adjustments, along with all other changes The update is performed by automatically advancing from the point to another match point. Changed The lock was written to an unused location on the disk and then the updated file A new root inode describing the system is written. Overview of snapshots Figure 18A shows the file system 1830 before the snapshot was taken. Indirect level to show and make the WAFL file system look easier. Le is excluded. File system 1830 is the file system 1 in Figure 16. Shows 690. File system 1830 blocks 1812-1820 Consists of. The inode of the inode file is the file system information block 18 Included in 10. Only one copy of file system information block 1810 is shown Not shown in 18A, but also a second copy of the file system information block Should be interpreted as being on disk. File system information block 18 Inode 1810A contained in 10 has 16 blocks of the same indirect level It has 16 pointers to point to. Blocks 1812-1820 in Figure 18A All blocks in the file system 1830, including direct blocks, indirect blocks, etc. Shows the hook. Only 5 blocks 1812-1820 are shown, Each block may point to another block. Figure 18B shows the creation of a snapshot. The snapshot is all phi Stored in file system information block 1810 for system 1830 A snapshot of the inode 1810A in the inode file that is in the inode 182 Created by simply copying to 2. Inode 181 in the inode file By copying 0A, the same file system as the active file system A new inode file showing the stem is created. inode file itself The body inode 1810A is copied, so the other blocks 1812-1820 Does not have to be duplicated. Copied inode or snapshot inno The 1822 is then copied to the inode file and the inode file is displayed. Dirty locks. In an inode file consisting of one or more indirect levels On the other hand, each indirect block is polluted in turn. This process of polluting blocks is all Proceed through the indirect level. 4 kilobytes each of inode files on disk The lock contains 32 inodes, each of which is 128 bytes long. The new snapshot inode 1822 in Figure 18B is snapshot 1. When the 822 is retrieved, it is referenced by the inode 1810A in the inode file. Refers to the highest level of indirect block 1812-1820. Inode Phi Because it itself contains a snapshot of the file system 1830 , Recursive structure. Copy each snapshot 1822 into an inode file This is a copy of the inode 1810A of the inode file to be created. Figure 18C shows the active fa The active file system 18 when changes occur in the file system 1830 30 and snapshot 1822 are shown. As shown in this figure, the data "D Block 1818 with "" after snapshot 1822 was taken As it changes (Figure 18B), a new block 182 containing the data "Dprime" 4 is assigned for the active file system 1830. But So the active file system 1830 is blocks 1812-1816 Has 1820-1824, but contains block 1818 containing data "D" Absent. However, the WAFL system does not overwrite the blocks on the disk, so Block 1818 containing data "D" is not overwritten. Block 1818 Bu Snapshot set on blockmap entry for lock 1818 It is protected from being overwritten by bits. Therefore, snap shot To 1822 is still the same as blocks 1812-1816 and 1820. Pointing to lock 1818. The present invention is as shown in FIGS. 18A-18C. , Create a "clone" of the file system and the clone is an inode file on disk It is different from the traditional system, which is a copy of all the blocks of the file. Therefore , Since the entire contents of the conventional inode file are duplicated, disk I / O operation Not only does it take a considerable amount of time to work, but also a significant amount (MB) of empty disk It takes time. When the active file system 1830 changes in Figure 18C, Filesystems with blocks 1812-1820 will not be overwritten, so The active file system uses more disk space. Figure 18C In, block 1818 is shown as a direct block. But in fact In the file system of, block 1818 is also blocked by an indirect block. You may point. Therefore, block 1818 has been modified to block 1824. When stored in a new disk location, the corresponding direct and indirect blocks Also copied and assigned to the active file system 1830 To. FIG. 19 shows the changes that occur in block 1824 of FIG. 18C. Figure 18C Lock 1824 is shown inside the dashed line 1824 in FIG. Figure 19 Shows some indirect levels for block 1824 in Figure 18C. .. The new block 1910 written to the disk in Figure 18C is in Figure 19. Is labeled with 1910. Block 1824 referenced by double indirectness Since it has a data block 1910 containing the modified data to be made, two other Blocks 1918 and 1926 will also change. Point of single indirect block 1918 Since data 1924 indicates a new block 1910, block 1918 is also a disk. Need to write to the new location of. Similarly, a pointer to indirect block 1926 The 1928 points to block 1918 and is therefore modified. Therefore, as shown in FIG. Some indirect by modifying data block 1910 so that Bu Locks 1918 and 1926 can also make changes. This is also Di Requires writing of blocks 1918 and 1926 to the new location of the desk. Direct and indirect blocks 1910, 1 of data block 1824 in Figure 18C 918 and 1926 are changed and written to new positions, so inode file The inode is written to a new block. Inode file modified The block is not overwritten with data, so a new block on the disk is split. You can guess. As shown in FIG. 19, block 1910 is an indirect block 1926, 191. Pointed to by 8 respectively. Therefore, block 1910 has changed When stored in a new disk location, the corresponding direct and indirect blocks also Copied and assigned to the active file system. Therefore, many Many data structures need to be updated. Direct block 1910 and indirect blow If you change the lock 1918 or 1926, the block map file will be changed. The key data structure for the snapshot is a block map entry, and each en Birds have multiple bits for a snapshot. This is multiple Allows you to create nap shots. The snapshot is a file system ( It is a picture of a tree of blocks which is 1830) of FIG. New data By snapshot unless written on a block of snapshot The file system represented does not change. Snapshots are similar to matching points doing. The file system of the present invention has file system information blocks 1810, 18 Fully consistent when 70 is written. Therefore, powering the system File system 1830 reaches a consistent state on restart, even if To. The traditional "clone" of an IGB file system is 8 ~ 32MB Since disk space is used, the clone can be a matching point or as in the present invention. Does not lead to a snapshot. See Figure 22 with two snapshots 2110A already on disk 2110B exists. The moment the third snapshot is created, Acte I The root inode that points to a bad file system is the inode file 2110. Copied to inode entry 2110C for 3 snapshots. same Occasionally flags that snapshot 3 was created at a passing alignment point Indicates. For all file systems, please refer to each entry in the blockmap file. Check whether bit 0 is set (1) or cleared (0). It is processed by clicking. For all bits 0 of each blockmap entry The value is copied to the plane for snapshot 3. When finished, Phi Each active block 2110 ~ 2116 and 1207 of the system is taken by it It exists in the snapshot at the moment it is released. A third snapshot of blocks that have been on the disk for a specified amount of time in a row Present in the corresponding snapshots 2110A ~ 2110B before 2110C .. If a block has been in the file system for long enough, it should be Present in all snapshots. Block 1207 is such a block To. As shown in Figure 22, block 1207 is the active inode fa Illustrated by Inode 2210G and snapshots 1, 2, Indirectly indicated by 3. The order of snapshots does not necessarily indicate the chronological order of file system copies Do not mean. Delete individual snapshots of the file system at any time This allows the entry to be used further .. Bit 0 of the blockmap entry that references the active file system Is cleared (indicating that the block has been removed from the active file system) Blocks can be reused if any snapshot reference bit is set Absent. This is because the block is part of the snapshot still in use Is. The block has all bits of the block map entry set to 0 Can only be reused at times. Algorithm for taking snapshots Taking a snapshot is almost like creating a regular consistency point as shown in Figure 5. It's completely similar. At step 510, all dirty inodes are consistent points Marked as being in. In step 520, all legitimate The file is flushed to the disc. In step 530, special Files (ie inode files and blockmap files) are diss It is flushed against the screen. In step 540, file system information The lock is flushed to disk. Not at the matching point in step 550 All inodes are processed. FIG. 5 has been described in detail earlier. In fact, The snapshot creation is done as part of the alignment point creation. Snap show The basic difference between creating a block and creating a consistency point is in the blockmap file. Active FS with all entries copied to snapshot bits To have a bit. The snapshot bit is a snapshot Corresponding snaps to protect the blocks from being overwritten Shows Yot. Creating and deleting snapshots in step 530 This is done, but this is because the file system is completely self-aligned and on disk It's just the only point to move. Consistency between different steps when a new snapshot is created Is done in step 530 shown in FIG. Step is positive It is very similar to the step of the consistency point of the regulation. Figure 7 creates a snapshot It is a flow chart which shows the step which a step 530 has to do. As mentioned above In step 530, the disk space is blocked with a blockmap file and an inode file. A snapshot that assigns for the file and shows the corresponding snapshot Copy the active FS bit to the tobit and the snapshot block is up Protect it from being written. Created with the blockmap file inode in step 710 Snapshots are pre-flashed to disk. Block map Flashing a file's inode to a block of inode files (against a consistency point) In addition to (as in step 610 in Figure 6), the snapshot being created Inode is also flushed to a block of inode files. resulting in , Blocks of inode files containing snapshot inodes get dirty To Become. At step 720, each blockmap in the blockmap file is dirty ing. In step 760 (described later) of the blockmap file All entries are updated in place of the dirty block entries. Therefore And mark that all blocks in the block map file are dirty here Must be attached, and step 730 allocates disk space to it for writing. To. In step 730, the disk space is inode and blockmap file. Assigned to all dirt blocks in Le. For dirt blocks, dirt blocks Blocks of inode files containing inodes in map files and new snaps Includes blocks containing inodes for shots. In step 740, the content of the root inode for the file system is i. It is copied to the inode of the snapshot of the file. At this time, a new adjustment Each block that is part of the point and is written to disk is assigned to it. There is disk space. Therefore, take a snapshot of the root inode i no Duplexing effectively copies all active file systems. The actual block present in the snapshot is the active file system Is the same block of. In step 750, blockmap file and snapshot inno The card is copied to the inode file. At step 760, the blockmap file entry is updated. In addition to copying to the CP bit for the entry of the active FS bit, The active FS bit also supports new snapshots. Copied to a bit. In step 770, everything in the blockmap and the inode file Dirty blocks are written to disk. Finally, at some point, the snapshot itself, at step 760. Removed from the file system. The snapshot is the active file Its snapshot inodeent in the system inode file Clear and take a snapshot of each entry in the blockmap file Deleted from the file system by clearing each bit corresponding to the number Is done. Also, snares in all block map entries that are cleared from the settings. Each bit of the snapshot is counted, which deletes the snapshot The count value of the block released by doing (the amount of disk space released by (Equivalent to) is obtained. This system is based on the oldest snapshot Decide which snapshot to delete. The user also has a specific snap You can manually choose to delete the yot. The present invention limits the total number of snapshots and, like episodes. Track snapshots instead of using pointers with COW bits Maintain a blockmap file with entries with multiple bits for To. Unused blocks have bits in their blockmap file entry All are 0. Over time, the active file system bit 0 ( Bit 0) is generally 1 at some point. By setting bit 0, pair Corresponding block assigned in the active file system To identify as. As mentioned above, all snapshot bits are initially 0 Is set to. Active before any snapshot bit is set When the bits of a file are cleared, which snaps stored on the disk There are no blocks in Yot either. Therefore, the block will soon be reassigned Can be used for and cannot be subsequently recovered from the snapshot. Take a snapshot As mentioned earlier, snapshots are very similar to alignment points. Therefore, Creating a snapshot, and creating the matching points shown in Figures 17A to 17L It will be explained with reference to the difference between Naru and Naru. Figures 21A to 21F are snapshots Shows the difference in creation. Figures 17A to 17D show the WAFL file system at the start of the snapshot. Indicates the state of. All dirty inodes have a matching point in step 510 Marked as being in, the legitimate file smells at step 520 Is flushed to disk. Therefore, the first processing of the snapshot is , Same as that of the matching point. The process for the snapshot is step 53 At 0, it differs from that of the matching point. Processing snapshots according to Figure 7 This will be described below. The following description is for a second snapshot of the WAFL file system Is. The first snapshot is recorded in the blockmap entry in Figure 17C. Has been done. Block as shown in entries 2324A ~ 2324M 2304 ~ 2306, 2310 ~ 2320, 2324 are the first snapshots Included in. All other snapshot bits (bits 1 to 20) Has a value of 0 indicating that the corresponding snapshot is not on disk Shall be. Figure 21A shows the screen after steps 510 and 520 are completed. Shows the file system. In step 710, snapshot 2 inodes 2308C and 230 8D and blockmap file 2344 pre-flash to disk Will be done. As a result, the inodes that are containing the inodes in snapshot 2 Guarantee that the pile blocks are dirty. In Figure 21B, inode 2308 C and 2308D are for snapshot 2 and blockmap files Flashed in advance for 2344. At step 720, all blockmap files 2344 are polluted .. As a result, in step 730, the entire blockmap file 2344 Is allocated to disk space. In step 730, the disk space is Dirt blocks 2308 and 2326 and inodef as shown in Figure 21C. Assigned to file 2346 and blockmap file 2344. this That is indicated by a triple asterisk (***) next to blocks 2308 and 2326. ing. This is the blockmap file 234 in step 620 of Figure 6. Disk space is allocated only to blocks with entries changed in 4. It is different from creating a point. The blockmap file 2344 in Figure 21C is a single block Tsu It has 2324. But blockmap file 2344 is more than 1 If you have a block, the disk space will be allocated to all blocks in step 730. Can be guessed. In step 740, the root inode of the new file system is snare. Copied to inode 2308D in shotshot 2. At step 750 , Blockmap file 2344 and snapshot 2 inode 2308C And 2308D are flushed to disk as shown in Figure 21D. The figure is , Snapshot 2 inode 2308D is not block 2306, but bro It is shown to refer to CK2304 and 2308. In step 760, block 232 of block map file 2344 Entries 2326A-2326L in 6 have been updated as shown in Figure 21E. Is done. In Figure 21E, the bits in snapshot 2 (bit 2) are in each entry 2. Indicates that the FS and CP bits of 326A to 2326L are updated in the same way. ing. Therefore, blocks 2304, 2308-2312, 2316-23 18, 2322, 2326 are included in snapshot 2, whereas blocks 2306, 2314, 2320, 2324 are not included. Step 770 smell The dirty blocks 2308 and 2326 are written to disk. The next step in snapshot 2 is the same as creating the alignment point shown in Figure 5. Is. In step 540, the two file system information blocks are di It is flushed to the desk. Therefore, Figure 21F shows the consistency after this step. Shows the WAFL file system in the state. After step 540 is finished Consistent file system files 2340, 2342, 2344, 2346 is shown inside the dashed line in Figure 21F. Consistency at step 550 The point ends by processing the inode that was not at this matching point. Access time overwrite The UNIX file system has an "access time" (a data) for each inode. Im (a time)) needs to be maintained. a time is the maximum when the file is read It shows the later time. It is updated every time the file is accessed. As a result, when the file is read, the inode contains the inode in the inode file. The block is rewritten and the inode is updated. This results in a file Since reading of may run out of disk space, a snapshot It is disadvantageous for the creation of. In addition, read all files in the file system Causes duplication of all inode files. The present invention solves this problem. To. When you change the inode by a time, a new block for the inode file Is written to disk, so reading can consume disk space .. In addition, it is abnormal for a file system that fills up the file system. If something goes wrong, the read operation may fail. In general, the data on the disc should protect the data stored on the disc. In addition, the WAFL file system will not be overwritten. The only example of this rule Outside, a-time override for inode, as shown in Figures 23A-23B Is. When "a time overwrite" occurs, it changes in the block of the inode file. The only data that is generated is the data of one or more inodes contained in it. Im, the block is rewritten at the same position. This is a WAFL system The only exception to this is that in other cases new data will always be on the new disk location. Written in. Figure 23A shows the inode 24 of the old WAFLinode file block 2420. Snapshot inode showing 22 a times 2423 and block 2420 It shows a time 2433 of 2432. Inode 2422 of block 2420 is straight See tangent block 2410. The a time 2423 of innode 2422 is "4 / 30 9:15 PM "while the snapshot inode 2432 a time 2433 is "5/1 10:00 AM". Figure 23A shows the direct back Shows the file system before the fa 2410 was accessed. Figure 23B shows the direct block 241 after the direct block 2410 has been accessed. Indicates 0 inode 2422. Access to inode 2422, as shown in the figure Stime 2423 is the access time 2 of snapshot 2432 showing it. Overwritten with 433. Therefore, inode 2 of direct block 2410 The access time 2423 of 422 is "5/1 11:23 AM". Overwriting an inode file block with a new a-time snaps There is a slight inconsistency in Snapshot file a time Should actually be after the time the snapshot was taken. User WAFL has all the fascia of the snapshot so that it does not discover this inconsistency. Snap a time of the file instead of the time the file was last accessed Adjust to the time when it was actually created. This snapshot time is Suna It is stored in the inode that describes the shot as a whole. Therefore, Access time 2 for inode 2422 when accessed via napshot 423 is always reported as "5/1 10:00 AM". This is "4 / Before the update, which is expected to be "30 9:15 PM", and "5/1 11:23 AM" Occurs both after the update, which is expected to be. Active file system When accessed via, the time is "4/30" before and after the update, respectively. Reported as "9:15 PM" and "5/1 11:23 AM". In this way, the file system is kept in a consistent state and the file system is read. A method for making a dedicated copy was disclosed.