Back to results
US 8,806,143 B1Granted
Queuing received write blocks for reducing file fragmentation
AssigneeNetApp, Inc.
InventorShiow-wen Wendy Cheng
Life of this patent
Estimating the term…
Abstract
A method and apparatus for queuing FBNs of received write blocks for a file to a queuing data structure for assigning LBNs to the FBNs is described herein. A queuing data structure may comprise a modified binary search tree, such as a modified red-black search tree. Each node of a queuing data structure may comprise a base field for storing a base FBN and a range field for storing a range value comprising X bits. The range field of a single node may represent a range of two or more FBNs (“FBN range”), the FBN range being based on the base FBN. Each FBN in the FBN range may have a corresponding bit in the range field, the base FBN corresponding to a “base bit” in the range field. The value of the corresponding bit in the range field may indicate whether the FBN has been received.
Claims23
A storage system for queuing received write blocks prior to storing the write blocks to a storage device, the storage system comprising:
- at least one storage device for storing write blocks;
- and
- an operating system configured for:
- receiving a plurality of file block numbers (FBNs) of write blocks for a file;
- and
- providing a queuing data structure for representing the received FBNs of the write blocks for the file and queuing the received FBNs prior to storing write blocks corresponding to the received FBNs to the at least one storage device, the queuing data structure comprising at least one node, each node comprising a range field representing an FBN range of at least two FBNs, the range field indicating whether one or more FBNs in the FBN range is in the plurality of received FBNs;
- and
- using the queuing data structure, processing the received FBNs of the write blocks for assigning a logical block number (LBN) for each received FBN, the LBN indicating a storage location on a storage device, wherein:
- the range field comprises X bits, X comprising an integer greater than 1;
- the number of FBNs represented by the range field is equal to X;
- each bit in the range field corresponds to an FBN in the FBN range for indicating whether the corresponding FBN is in the plurality of received FBNs;
- each node in the queuing data structure further comprises a base field for storing a base FBN, the base FBN being within the FBN range;
- and
- the values of the FBN range represented by the node are based on the base FBN.
11 more elements
A non-transitory computer readable medium having instructions stored thereon when executed by a processor, queue received write blocks prior to storing the write blocks to a storage device, the computer readable medium comprising sets of instructions for:
- receiving a plurality of file block numbers (FBNs) of write blocks for a file;
- and
- providing a queuing data structure for representing the received FBNs of the write blocks for the file and queuing the received FBNs prior to storing write blocks corresponding to the received FBNs to the at least one storage device, the queuing data structure comprising at least one node, each node comprising a range field representing an FBN range of at least two FBNs, the range field indicating whether one or more FBNs in the FBN range is in the plurality of received FBNs;
- and
- using the queuing data structure, processing the received FBNs of the write blocks for assigning a logical block number (LBN) for each received FBN, the LBN indicating a storage location on the storage device, wherein:
- the range field comprises X bits, X comprising an integer greater than 1;
- the number of FBNs represented by the range field is equal to X;
- each bit in the range field corresponds to an FBN in the FBN range for indicating whether the corresponding FBN is in the plurality of received FBNs;
- each node in the queuing data structure further comprises a base field for storing a base FBN, the base FBN being within the FBN range;
- and
- the values of the FBN range represented by the node are based on the base FBN.
8 more elements
A storage system for queuing received write blocks prior to storing the write blocks to a storage device, the storage system comprising:
- at least one storage device for storing write blocks;
- and
- an operating system configured for:
- receiving a plurality of file block numbers (FBNs) of write blocks for a file;
- and
- providing a queuing data structure for representing the received FBNs of the write blocks for the file and queuing the received FBNs prior to storing write blocks corresponding to the received FBNs to the at least one storage device, the queuing data structure comprising at least one node comprising a range field comprising X bits, X comprising an integer greater than 1, each bit in the range field corresponding to an FBN for indicating whether the corresponding FBN is in the plurality of received FBNs;
- and
- using the queuing data structure, processing the received FBNs of the write blocks for assigning a logical block number (LBN) for each received FBN, the LBN indicating a storage location on a storage device, wherein:
- each node in the queuing data structure further comprises a base field for storing a base FBN, the base FBN being within the FBN range;
- and
- the values of the FBN range represented by the node are based on the base FBN.
8 more elements
A non-transitory computer readable medium having instructions stored thereon when executed by a processor, queue received write blocks prior to storing the write blocks to a storage device, the computer readable medium comprising sets of instructions for:
- receiving a plurality of file block numbers (FBNs) of write blocks for a file;
- and
- providing a queuing data structure for representing the received FBNs of the write blocks for the file and queuing the received FBNs prior to storing write blocks corresponding to the received FBNs to the at least one storage device, the queuing data structure comprising at least one node comprising a range field comprising X bits, X comprising an integer greater than 1, each bit in the range field corresponding to an FBN for indicating whether the corresponding FBN is in the plurality of received FBNs;
- and
- using the queuing data structure, processing the received FBNs of the write blocks for assigning a logical block number (LBN) for each received FBN, the LBN indicating a storage location on a storage device, wherein:
- each node in the queuing data structure further comprises a base field for storing a base FBN, the base FBN being within the FBN range;
- and
- the values of the FBN range represented by the node are based on the base FBN.
5 more elements
A storage system for queuing received write blocks prior to storing the write blocks to a storage device, the storage system comprising:
- at least one storage device for storing write blocks;
- and
- an operating system configured for:
- receiving a plurality of file block numbers (FBNs) of write blocks for a file;
- and
- representing each received FBN in a queuing data structure for the file and queuing the received FBNs prior to storing write blocks corresponding to the received FBNs to the at least one storage device, the queuing data structure comprising at least one node, each node comprising a range field representing an FBN range of at least two FBNs, the range field indicating whether one or more FBNs in the FBN range is in the plurality of received FBNs;
- ordering the received FBNs using the queuing data structure to produce a value ordered list of FBNs;
- and
- assigning a logical block number (LBN) for each received FBN based on the value ordered list of FBNs, the LBN indicating a storage location on a storage device, wherein:
- the range field comprises X bits, X comprising an integer greater than 1;
- the number of FBNs represented by the range field is equal to X;
- each bit in the range field corresponds to an FBN in the FBN range for indicating whether the corresponding FBN is in the plurality of received FBNs;
- each node in the queuing data structure further comprises a base field for storing a base FBN, the base FBN being within the FBN range;
- and
- the values of the FBN range represented by the node are based on the base FBN.
12 more elements
A storage system for queuing received write blocks prior to storing the write blocks to a storage device, the storage system comprising:
- at least one storage device for storing write blocks;
- and
- an operating system configured for:
- receiving a plurality of file block numbers (FBNs) of write blocks for a file;
- and
- providing a queuing data structure for representing the received FBNs of the write blocks for the file and queuing the received FBNs prior to storing write blocks corresponding to the received FBNs to the at least one storage device, the queuing data structure comprising at least one node, each node comprising a range field representing an FBN range of at least two FBNs, the range field indicating whether one or more FBNs in the FBN range is in the plurality of received FBNs;
- and
- using the queuing data structure, processing the received FBNs of the write blocks for assigning a logical block number (LBN) for each received FBN, the LBN indicating a storage location on a storage device, wherein:
- each bit in the range field corresponds to an FBN in the FBN range for indicating whether the corresponding FBN is in the plurality of received FBNs;
- a bit in the range field corresponding to an FBN is equal to 1 if the FBN is in the plurality of received FBNs and is equal to 0 if the FBN is not in the plurality of received FBNs, or a bit in the range field corresponding to an FBN is equal to 0 if the FBN is in the plurality of received FBNs and is equal to 1 if the FBN is not in the plurality of received FBNs;
- each node in the queuing data structure further comprises a base field for storing a base FBN, the base FBN being within the FBN range;
- and
- the values of the FBN range represented by the node are based on the base FBN.
10 more elements
A storage system for queuing received write blocks prior to storing the write blocks to a storage device, the storage system comprising:
- at least one storage device for storing write blocks;
- and
- an operating system configured for:
- receiving a plurality of file block numbers (FBNs) of write blocks for a file;
- and
- providing a queuing data structure for representing the received FBNs of the write blocks for the file and queuing the received FBNs prior to storing write blocks corresponding to the received FBNs to the at least one storage device, the queuing data structure comprising at least one node, each node comprising a range field representing an FBN range of at least two FBNs, the range field indicating whether one or more FBNs in the FBN range is in the plurality of received FBNs;
- and
- using the queuing data structure, processing the received FBNs of the write blocks for assigning a logical block number (LBN) for each received FBN, the LBN indicating a storage location on a storage device, wherein:
- the queuing data structure comprises a binary search tree, wherein each node has one parent node, one left child node having a lower base FBN, and one right child node having a higher base FBN;
- each node further comprises fields for a base FBN, a pointer to the parent node, a pointer to the left child node, and a pointer to the right child node;
- each node in the queuing data structure further comprises a base field for storing a base FBN, the base FBN being within the FBN range;
- and
- the values of the FBN range represented by the node are based on the base FBN.
10 more elements
A non-transitory computer readable medium having instructions stored thereon when executed by a processor, queue received write blocks prior to storing the write blocks to a storage device, the computer readable medium comprising sets of instructions for:
- receiving a plurality of file block numbers (FBNs) of write blocks for a file;
- and
- providing a queuing data structure for representing the received FBNs of the write blocks for the file and queuing the received FBNs prior to storing write blocks corresponding to the received FBNs to the at least one storage device, the queuing data structure comprising at least one node, each node comprising a range field representing an FBN range of at least two FBNs, the range field indicating whether one or more FBNs in the FBN range is in the plurality of received FBNs;
- and
- using the queuing data structure, processing the received FBNs of the write blocks for assigning a logical block number (LBN) for each received FBN, the LBN indicating a storage location on the storage device, wherein:
- each bit in the range field corresponds to an FBN in the FBN range for indicating whether the corresponding FBN is in the plurality of received FBNs;
- a bit in the range field corresponding to an FBN is equal to 1 if the FBN is in the plurality of received FBNs and is equal to 0 if the FBN is not in the plurality of received FBNs, or a bit in the range field corresponding to an FBN is equal to 0 if the FBN is in the plurality of received FBNs and is equal to 1 if the FBN is not in the plurality of received FBNs;
- each node in the queuing data structure further comprises a base field for storing a base FBN, the base FBN being within the FBN range;
- and
- the values of the FBN range represented by the node are based on the base FBN.
7 more elements
A non-transitory computer readable medium having instructions stored thereon when executed by a processor, queue received write blocks prior to storing the write blocks to a storage device, the computer readable medium comprising sets of instructions for:
- receiving a plurality of file block numbers (FBNs) of write blocks for a file;
- and
- providing a queuing data structure for representing the received FBNs of the write blocks for the file and queuing the received FBNs prior to storing write blocks corresponding to the received FBNs to the at least one storage device, the queuing data structure comprising at least one node, each node comprising a range field representing an FBN range of at least two FBNs, the range field indicating whether one or more FBNs in the FBN range is in the plurality of received FBNs;
- and
- using the queuing data structure, processing the received FBNs of the write blocks for assigning a logical block number (LBN) for each received FBN, the LBN indicating a storage location on the storage device, wherein:
- the queuing data structure comprises a binary search tree, wherein each node has one parent node, one left child node having a lower base FBN, and one right child node having a higher base FBN;
- each node further comprises fields for a base FBN, a pointer to the parent node, a pointer to the left child node, and a pointer to the right child node;
- each node in the queuing data structure further comprises a base field for storing a base FBN, the base FBN being within the FBN range;
- and
- the values of the FBN range represented by the node are based on the base FBN.
7 more elements
Dependencies are inferred from the claim text.