Computer disk management system using doublet A-B logging

Details Computer disk management system using doublet A-B logging Computer disk management system using doublet A-B logging

1999-01-12

2001-10-02

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Control technique

C711S161000, C711S202000, C707S793000

Reexamination Certificate

active

06298425

ABSTRACT:

BACKGROUND OF THE INVENTION
In general, a computer disk holds blocks of data. The disk blocks are numbered, starting at 0 and sequentially proceeding up to the total number of blocks on the disk (less one). The disk blocks are addressed using Logical Block Numbers, or LBN's for short.
An application stores its data persistently on disk within named files. Each file consists of blocks of data, where each block is a sequence of consecutive bytes. Typically, the sequence of consecutive bytes is in the range of 512 bytes up to several kilobytes (fixed by the design of each disk). Blocks within a file are numbered from 1 up to the current maximum in the file. These blocks are addressed using Virtual Block Numbers, or so-called VBN's. Note that the term VBN only has meaning within a specified file. For example, two files can both contain a VBN3, but the content of VBN3 for the two files is totally unrelated. Moreover, these two VBN's are stored on the disk at completely different LBN's.
FIG. 1
is illustrative of the foregoing. Referring to
FIG. 1
, two small files labeled “spec.txt” and “myprog.exe” are shown. “spec.txt” contains VBN's 1 through 3, while “myprog.exe” contains VBN's 1 through 5. VBNl of “spec.txt” is held in LBN8 of subject disk 100; spec.txt VBN2 is held in LBN2 and so on. The layout on disk 100 of these two files is summarized in the table below:
spec.txt
myprog.exe
VBN
LBN
VBN
LBN
1
 8
1
 4
2
 2
2
 9
3
12
3
 6
4
14
5
10
The component of software that remembers the mapping from file VBN's to the disk LBN is called the file system. The file system takes care of allocating, freeing and remembering which logical blocks are used by which virtual blocks within each file at any instant. The file system also remembers the names given by applications to each file and how these files are held together in a directory tree. The file system stores this metadata (e.g., the VBN to LBN mapping) on blocks of the disk that it keeps for its own use, but which applications do not normally access.
So an application conducts its operations in terms of reading and writing blocks of data to a file called by some convenient name, for example “[accounts.monthly]January. details”. An application can choose to extend the file, or to truncate the file, either action can change the number of virtual blocks in the file. The file system accepts those requests from the application, expressed as operations upon VBN's within named files, and ultimately turns them into reads and writes upon LBN's for data stored on the disk. The mechanical details of the reads and writes to LBN's on the disk for the file system are handled by another software component that is specific to the disk and called the device driver.
The file system metadata blocks must be stored persistently in reserved memory, i.e., permanently across computer reboots within reserved areas of the disk.
One approach for maintaining persistent metadata is known as “A-B Logging”. See “Transaction Processing: Concepts and Techniques” by Jim Gray and Andreas Reuter in
Morgan Kaufmann Series in Data Management Systems.
In A-B logging, the subject metadata is written to blocks in area A of the disk. A copy of those blocks is made in area B of the disk, where A and B are separate and distinct areas of the disk. The metadata stored in area B are used until a block failure or other failure occurs. In that event, area A serves as a backup copy of the metadata. This meets the requirements of 3. above. However, maintenance of such dual areas imposes a high overhead (against requirement 4. above).
Similarly, redo logging, undo logging or a mixture of both types of logging may be used to provide atomic updates to a number of disparate pieces of metadata. See C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh and P. Schwarz, “ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging,”
ACM Transactions on Database Systems
17, No. 1 (March 1992). This solution involves writing the updates to a sequential log before updating the disk locations of the metadata. Once the operations have been written to the log, the operations are said to be committed, in other words, the metadata changes are stable and persistent. A background task is required to roll the changes written in the log to the disk location. While this can be done at leisure, additional I/O's are required, thus lowering the theoretical maximum throughput, particularly where most operations are a single block update.
In another approach called ABC Update, if metadata requires 100 blocks of space, then the disk management system allocates three times this amount at the start of the target disk. The three allocated areas are called the “A”, “B” and “C” area, and when the disk management system is transactionally consistent, the three areas contain identical copies of the 100 blocks of metadata. To provide persistence, the ABC update approach provides an AddRecord operation that write-locks some metadata block, F, which is known to hold some free slots, and modifies the in-memory copy of that block to reflect the fact that it selects one of these free slots for use. The ABC update approach then write-locks the metadata block, M, that will map the new user record, R, (in effect it is a mapping from the key field in record R to the slot where that records is actually stored within the disk). The in-memory copy of that block is then updated to hold this new mapping. The disk management system then writes out record R to the selected slot. Once that is complete, the disk management system writes out metadata blocks M and F to their locations in the “A” area. Once complete, the disk management system does the same to the “B” area. In turn, the disk management system does the same to the “C” area.
Note that each transaction always writes to A, B and C areas in that order. In total, using the ABC update approach, the disk management system performs one user write, followed by six metadata writes; however, those metadata writes are done as three pairs, where each pair is issued to the underlying device driver in parallel.
After all these writes have completed, the transaction releases its exclusive write lock on metadata blocks M and F and acknowledges successful addition of the user record back to the caller. Each block in each metadata area includes a headlet that describes a transaction of which it forms a part. The headlet is formed of a “TxNum” part and a “TxSize” part. The “TxNum” part is a 64-bit integer which uniquely identifies the transaction. And the “TxSize” part holds a value which indicates the total number of metadata blocks involved in the transaction. Note that writes to any one metadata area are issued in parallel—the disk is allowed to reorder parallel I/O's, and therefore metadata blocks M and F may be updated in either order.
Consider first the case where there are no disk errors—all blocks can be read by recovery. In this simplified case, all one needs is an “A” area and a “B” area; the “C” area is not required. Suppose the system just has ten blocks of metadata. Before a subject transaction, the on-disk state is, happily, transactionally consistent and shown below.
Block
1
2
3
4
5
6
7
8
9
10
A
27.2
39.1
37.2
27.2
35.1
37.2
41.3
41.3
38.1
41.3
B
27.2
39.1
37.2
27.2
35.1
37.2
41.3
41.3
38.1
41.3
C
27.2
39.1
37.2
27.2
35.1
37.2
41.3
41.3
38.1
41.3
This table shows the transaction headlet in each of the ten metadata blocks, for areas A, B and C. The contents of the three areas are identical. The two numbers in each box represent the transaction identifier “TxNum”, followed, after the dot, by “TxSize” the number of metadata transaction blocks involved in the transaction. One can see six transactions, identified by TxNums 27, 35, 37, 38, 39 and 41. They are all complete. For example, transaction 27 affected two blocks, namely block numbers 1 and 4. The same holds true for the other (five) transactions.
Consider a new AddRecord transac

Affiliated with

Also associated with

Rating

Computer disk management system using doublet A-B logging does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Computer disk management system using doublet A-B logging, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer disk management system using doublet A-B logging will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2609078