US 6,185,663 B2 · Computer method and apparatus for file system block allocation with multiple redo

Abstract

A shared persistent memory (e.g., disk) file system provides persistent memory block allocation with multiple redo logging of memory blocks. The file system employs a three part block state indicator (V,A,U). V is a volume indication. A is allocation sequence indication. U is update sequence number indication. The file system (a) generates indication of the allocation sequence in the allocation map in a manner free of initially reading the block from storage memory, (b) records the indication of volume, allocation sequence and update sequence in an entry of the transaction log of the requesting computer node, and (c) sets indications of volume, allocation sequence and update sequence on the subject block in storage memory. Subsequent transactions on the subject block, by the requesting node are recorded in respective entries in the transaction log. Each respective entry reflects state of the subject block by indicating in the block state indicator the volume, allocation sequence and order of update sequence. The file system includes redo recovery means for updating blocks in the storage memory upon a failure in the computer system. For each block being updated, the recovery means utilizes one transaction log and the block state indicators recorded therein corresponding to indications of volume and update sequence in the block in storage memory.

Claims27

Dependent claims

In a computer system having a plurality of computer nodes sharing a storage memory formed of a plurality of blocks, a file system comprising:

an allocation map for indicating use of blocks in the storage memory;
a plurality of transaction logs, a different transaction log for each computer node, for recording a sequence of data transactions by the computer node on a block from the storage memory, each transaction log formed of a plurality of entries, a different entry for each data transaction of the respective computer node;
a block state indicator for each transaction log entry, the block state indicator being with respect to a subject block from the storage memory and providing an indication of allocation sequence of the block, the indication of allocation sequence being determinable from the allocation map such that upon the file system allocating usage of the subject block in response to a requesting computer node, the file system (a) sets indication of the allocation sequence in a manner free of initially reading the block from the storage memory, and (b) records the indication of allocation sequence in an entry of the transaction log of the requesting computer node, subsequent transactions on the subject block by the requesting node being recorded in respective entries in the transaction log, each respective entry reflecting state of the subject block by indicating in the block state indicator the allocation sequence;
and
recovery means for updating blocks in the storage memory upon a failure in the computer system, for each block being updated, the recovery means using one transaction log and the block state indicators recorded therein corresponding to the block in the storage memory.

2 more elements

In a computer system having a plurality of computer nodes sharing a storage memory formed of a plurality of blocks, a file system comprising:

an allocation map for indicating use of blocks in the storage memory;
a plurality of transaction logs, a different transaction log for each computer node, for recording a sequence of data transactions by the computer node on a block from the storage memory, each transaction log formed of a plurality of entries, a different entry for each data transaction of the respective computer node;
a block state indicator for each transaction log entry, the block state indicator being with respect to a subject block from the storage memory and providing an indication of allocation sequence of the block, the indication of allocation sequence being determinable from the allocation map such that upon the file system allocating usage of the subject block in response to a requesting computer node, the file system (a) sets indication of the allocation sequence in a manner free of initially reading the block from the storage memory, and (b) records the indication of allocation sequence in an entry of the transaction log of the requesting computer node, subsequent transactions on the subject block by the requesting node being recorded in respective entries in the transaction log, each respective entry reflecting state of the subject block by indicating in the block state indicator the allocation sequence;
a first counter coupled to the transaction logs for determining an update sequence, the first counter increasing each time a computer node transaction on a subject block occurs, and increasing in order from one corresponding transaction log entry to a succeeding one;
a second counter coupled to the allocation map for determining the allocation sequence, the second counter incrementing each time a computer node of the computer system causes a block to be allocated, such that for the subject block, the transaction log entries recording requesting computer node transactions on the subject block indicate a same allocation sequence throughout the block state indicators of those transaction log entries while the corresponding update sequence indication is sequentially increased from a first one of said transaction log entries to succeeding ones;
recovery means for updating blocks in the storage memory upon a failure in the computer system, for each block being updated, the recovery means using one transaction log and the block state indicators recorded therein corresponding to the block in the storage memory;
wherein the allocation map includes a file allocation map and a block allocation map, the file allocation map indicating use of metadata blocks, and
wherein:
the block state indicator provides an indication of (i) volume, (ii) the allocation sequence, and (iii) the update sequence of the block;
the file system sets indications of volume, allocation sequence and update sequence on the subject block in the storage memory;
and
the recovery means updates a block in the storage memory according to a transaction log entry if [V′=V and A′>A] or [V′=V and A′=A and U′=(U+1) mod W] where
U′ is the update sequence indication in the transaction log entry;
V′ is the volume indication in the transaction log entry;
A′ is the allocation sequence indication in the transaction log entry;
V is the volume indication of the block in the storage memory;
A is the allocation sequence indication in the block in the storage memory;
U is the update sequence indication of the block in the storage memory;
and
W is word size in the computer system.

17 more elements

In a computer system having a plurality of computer nodes sharing a storage memory formed of a plurality of blocks, a file system comprising:

an allocation map for indicating use of blocks in the storage memory;
a plurality of transaction logs, a different transaction log for each computer node, for recording a sequence of data transactions by the computer node on a block from the storage memory, each transaction log formed of a plurality of entries, a different entry for each data transaction of the respective computer node;
a block state indicator for each transaction log entry, the block state indicator being with respect to a subject block from the storage memory and providing an indication of allocation sequence of the block, the indication of allocation sequence being determinable from the allocation map such that upon the file system allocating usage of the subject block in response to a requesting computer node, the file system (a) sets indication of the allocation sequence in a manner free of initially reading the block from the storage memory, and (b) records the indication of allocation sequence in an entry of the transaction log of the requesting computer node, subsequent transactions on the subject block by the requesting node being recorded in respective entries in the transaction log, each respective entry reflecting state of the subject block by indicating in the block state indicator the allocation sequence;
a first counter coupled to the transaction logs for determining an update sequence, the first counter increasing each time a computer node transaction on a subject block occurs, and increasing in order from one corresponding transaction log entry to a succeeding one;
a second counter coupled to the allocation map for determining the allocation sequence, the second counter incrementing each time a computer node of the computer system causes a block to be allocated, such that for the subject block, the transaction log entries recording requesting computer node transactions on the subject block indicate a same allocation sequence throughout the block state indicators of those transaction log entries while the corresponding update sequence indication is sequentially increased from a first one of said transaction log entries to succeeding ones;
recovery means for updating blocks in the storage memory upon a failure in the computer system, for each block being updated, the recovery means using one transaction log and the block state indicators recorded therein corresponding to the block in the storage memory;
and
wherein:
the block state indicator provides an indication of (i) volume, (ii) the allocation sequence, and (iii) the update sequence of the block;
the file system sets indications of volume, allocation sequence and update sequence on the subject block in the storage memory;
and
the recovery means updates a block in the storage memory according to a transaction log entry if [V′=V and A′>A] or [V′=V and A′=A and U′=(U+1) mod W] where
U′ is the update sequence indication in the transaction log entry;
V′ is the volume indication in the transaction log entry;
A′ is the allocation sequence indication in the transaction log entry;
V is the volume indication of the block in the storage memory;
A is the allocation sequence indication of the block in the storage memory;
U is the update sequence indication of the block in the storage memory;
and
W is word size in the computer system.

17 more elements

In a computer system having a plurality of computer nodes sharing a storage memory, a method for allocating and updating blocks in the storage memory, the method comprising the steps of:

using an allocation map, indicating use of blocks in the storage memory;
providing a plurality of transaction logs, a different transaction log for each computer node, each transaction log formed of a plurality of entries;
recording in the transaction log of a computer node a sequence of data transactions, by the computer node on a block from the storage memory, for each different transaction, the transaction being recorded in a different entry of the transaction log;
indicating block state in each transaction log entry, the block state being with respect to a subject block from the storage memory, said indicating providing an indication of allocation sequence of the block;
upon allocation of the subject block in response to a requesting computer node, (a) determining from the allocation map the allocation sequence of the block, in a manner free of initially reading the block from the storage memory, and (b) recording the indication of allocation sequence in an entry of the transaction log of the requesting computer node and in the subject block in the storage memory;
in each of subsequent transactions on the subject block by the requesting node, recording the transaction in a respective entry in the transaction log including in each respective entry reflecting state of the subject block by indicating the allocation sequence of the block as recorded in the block in the storage memory;
and
updating blocks in the storage memory upon a failure in the computer system, for each block being updated, using one transaction log and the block state indications recorded therein corresponding to the block in the storage memory.

5 more elements

In a computer system having a plurality of computer nodes sharing a storage memory, a method for allocating and updating blocks in the storage memory, the method comprising the steps of:

using an allocation map, indicating use of blocks in the storage memory;
providing a plurality of transaction logs, a different transaction log for each computer node, each transaction log formed of a plurality of entries;
recording in the transaction log of a computer node a sequence of data transactions, by the computer node on a block from the storage memory, for each different transaction, the transaction being recorded in a different entry of the transaction log;
indicating block state in each transaction log entry, the block state being with respect to a subject block from the storage memory, said indicating providing an indication of allocation sequence of the block;
upon allocation of the subject block in response to a requesting computer node, (a) determining from the allocation map the allocation sequence of the block, in a manner free of initially reading the block from the storage memory, and (b) recording the indication of allocation sequence in an entry of the transaction log of the requesting computer node and in the subject block in the storage memory;
in each of subsequent transactions on the subject block by the requesting node, recording the transaction in a respective entry in the transaction log including in each respective entry reflecting state of the subject block by indicating the allocation sequence of the block as recorded in the block in the storage memory;
and
updating blocks in the storage memory upon a failure in the computer system, for each block being updated, using one transaction log and the block state indications recorded therein corresponding to the block in the storage memory;
wherein the step of indicating use of blocks includes using a file allocation map and a block allocation map, the file allocation map indicating use of metadata blocks, and wherein the step of indicating block state includes (i) counting each time a computer node transaction occurs on a subject block, said counting providing an update sequence, and (ii) increasing the update sequence in order from one corresponding transaction log entry to a succeeding one;
wherein the step of providing an indication of the allocation sequence includes counting each time a computer node of the computer system causes a block to be allocated, such that for the subject block, the transaction log entries recording requesting computer node transactions on the subject block indicate a same allocation sequence throughout the block state indications of those transaction log entries, while the corresponding update sequence indication is sequentially increased from a first one of said transaction log entries to succeeding ones;
and
wherein:
the step of indicating block state includes providing an indication of (i) volume, (ii) the allocation sequence and (iii) the update sequence of the block;
further setting indication of volume and update sequence on the subject block in the storage memory upon allocation of the subject block;
and
the step of updating blocks using one transaction log per block being updated includes:
comparing volume indication in the transaction log entry to volume indication of a subject block in the storage memory;
comparing allocation sequence indication in the transaction entry to allocation sequence stored in the subject block in the storage memory;
and
comparing update sequence indication in the transaction log entry to update sequence indication of the block in the storage memory.

17 more elements

In a computer system having a plurality of computer nodes sharing a storage memory, a method for allocating and updating blocks in the storage memory, the method comprising the steps of:

using an allocation map, indicating use of blocks in the storage memory;
providing a plurality of transaction logs, a different transaction log for each computer node, each transaction log formed of a plurality of entries;
recording in the transaction log of a computer node a sequence of data transactions, by the computer node on a block from the storage memory, for each different transaction, the transaction being recorded in a different entry of the transaction log;
indicating block state in each transaction log entry, the block state being with respect to a subject block from the storage memory, said indicating providing an indication of allocation sequence of the block;
upon allocation of the subject block in response to a requesting computer node, (a) determining from the allocation map the allocation sequence of the block, in a manner free of initially reading the block from the storage memory, and (b) recording the indication of allocation sequence in an entry of the transaction log of the requesting computer node and in the subject block in the storage memory;
in each of subsequent transactions on the subject block by the requesting node, recording the transaction in a respective entry in the transaction log including in each respective entry reflecting state of the subject block by indicating the allocation sequence of the block as recorded in the block in the storage memory;
updating blocks in the storage memory upon a failure in the computer system, for each block being updated, using one transaction log and the block state indications recorded therein corresponding to the block in the storage memory;
wherein the step of indicating block state includes (i) counting each time a computer node transaction occurs on a subject block, said counting providing an update sequence, and (ii) increasing the update sequence in order from one corresponding transaction log entry to a succeeding one;
the step of providing an indication of the allocation sequence includes counting each time a computer node of the computer system causes a block to be allocated, such that for the subject block, the transaction log entries recording requesting computer node transactions on the subject block indicate a same allocation sequence throughout the block state indications of those transaction log entries while the corresponding update sequence indication is sequentially increased from a first one of said transaction log entries to succeeding ones;
and
wherein:
the step of indicating block state includes providing an indication of (i) volume, (ii) the allocation sequence and (iii) the update sequence of the block;
further setting indication of volume and update sequence on the subject block in the storage memory upon allocation of the subject block;
and
the step of updating blocks using one transaction log per block being updated includes:
comparing volume indication in the transaction log entry to volume indication of a subject block in the storage memory;
comparing allocation sequence indication in the transaction entry to allocation sequence stored in the subject block in the storage memory;
and
comparing update sequence indication in the transaction log entry to update sequence indication of the block in the storage memory.

16 more elements

A computer readable medium encoding a digital processor routine for implementing a shared memory file system with memory block allocation and multiple redo update of memory blocks, the processor routine comprising:

allocation map means for indicating use of blocks on the shared memory;
a plurality of transaction logs, a different transaction log for each computer node, for recording a sequence of data transactions by the computer node on a block from a storage memory, each transaction log formed of a plurality of entries, a different entry for each data transaction of the respective computer node;
a block state indicator for each transaction log entry, the block state indicator being with respect to a subject block from the storage memory and providing an indication of at least allocation sequence of the block, the indication of allocation sequence being provided by the allocation map such that upon the file system allocating usage of the subject block in response to a requesting computer node, the file system (a) sets indication of the allocation sequence in the allocation map in a manner free of initially reading the block from the storage memory, and (b) records the indication of allocation sequence in an entry of the transaction log of the requesting computer node, subsequent transactions on the subject block by the requesting node being recorded in respective entries in the transaction log, each respective entry reflecting state of the subject block by indicating in the block state indicator at least the allocation sequence;
recovery means for updating blocks in the storage memory upon a failure in the computer system, for each block being updated, the recovery means using one transaction log and the block state indicators recorded therein corresponding to the block in the storage memory;
and
wherein:
the block state indicator provides an indication of (i) volume, (ii) allocation sequence and (iii) update sequence of the block;
the file system sets indications of volume, allocation sequence and update sequence on the subject block in the storage memory;
and
the recovery means updates a block in the storage memory according to a transaction log entry if [V′=V and A′>A] or [V′=V and A′=A and U′=(U+1) mod W] where
U′ is the update sequence indication in the transaction log entry;
V′ is the volume indication in the transaction log entry;
A′ is the allocation sequence indication in the transaction log entry;
V is the volume indication of the block in the storage memory;
A is the allocation sequence indication in the block in the storage memory;
U is the update sequence indication of the block in the storage memory;
and
W is word size in the computer system.

15 more elements

Dependencies are inferred from the claim text.

Computer method and apparatus for file system block allocation with multiple redo

Life of this patent

Computer method and apparatus for file system block allocation with multiple redo

Life of this patent

Abstract

Claims27