Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-07-18
2004-11-30
Alam, Shahid (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C711S152000
Reexamination Certificate
active
06826570
ABSTRACT:
TECHNICAL FIELD
This invention relates, in general, to parallel data processing, and in particular, to providing an adaptive access strategy for a parallel file system of a computing environment.
BACKGROUND ART
A parallel, shared disk file environment includes a set of computer nodes, disk storage devices, a communication network, and a parallel file system running on each computer node. A parallel file system differs from a traditional distributed file system, like the Network File System (NFS) or the Distributed File System (DFS), in that with a parallel file system, data belonging to the same file is distributed or “striped” across disks that are attached to different nodes in the environment or directly attached to the network. A parallel file system allows data to be transferred between disks and computer nodes without requiring all the data to pass through a single server node. While this eliminates the single server bottleneck inherent in traditional distributed file systems, it requires coordinating access to the shared disks from different nodes to guarantee correct file system behavior.
In order to achieve this coordination, two different concurrency control techniques are available:
1. A distributed locking technique: With a distributed locking technique, before a node is allowed to read or write a particular data block of a file, it first acquires permission to do so from a distributed lock service (e.g., a distributed lock manager). This is done by sending a message to obtain a read-token or a write-token from a centralized token server node. Once an appropriate token (read or write) has been obtained, the node is allowed to read data from the disk and keep the data in its buffer cache, so that future requests for data in the same range can be satisfied locally without additional messages or disk I/O. If a write-token is obtained, the node is also allowed to modify the data in its buffer cache and to write the modified data back to disk. Each token represents a right to read and/or update one or more data blocks of a file, identified by a logical offset and length within the file (i.e., a byte-range token).
The token server keeps track of what tokens were granted to each node and ensures that no two nodes are holding conflicting tokens for the same data blocks. That is, only one node at a time is allowed to hold a token in write mode, whereas multiple nodes can hold a token in read mode. Before the token server grants a token to a node, conflicting tokens held by other nodes are revoked. For example, the granting of a write-token includes revoking all tokens for the same range held by other nodes, whereas the granting of a read-token only requires revoking a write-token that might be held by another node (or at least downgrading the token from write mode to read mode). Revoking a read-token from a node includes discarding the corresponding data from the buffer cache. Downgrading and/or revoking a write-token from a node includes flushing modified data to disk and/or discarding that data from the buffer cache.
One example of a distributed locking technique is employed by the General Parallel File System (GPFS), offered by International Business Machines Corporation. Further, one example of a distributed locking technique is described in U.S. Pat. No. 5,950,199, entitled “Parallel File System and Method For Granting Byte Range Tokens,” Schmuck et al., Issued Sep. 7, 1999, which is hereby incorporated herein by reference in its entirety.
2. A static file partitioning technique: With static file partitioning, all data blocks of a file are statically partitioned among a fixed set of nodes. For example, blocks might be assigned in a round-robin fashion. That is, to partition a file among a set of n nodes numbered 0, 1, . . . , n−1, block i of a file is assigned to node number (i mod n). Reading or writing a data block of a file includes sending a message to the node that the particular data block was assigned. Each node caches in its buffer pool only those data blocks that were assigned to that node.
One example of a static file partitioning technique is employed by the Parallel I/O File System (PIOFS), offered by International Business Machines Corporation. Further, one example of a static file partitioning technique is described in Corbett, Peter F.; Feitelson, Dror G., “Design and Implementation of the Vesta Parallel File System,” IBM T. J. Watson Research Center, Yorktown Heights, N.Y. 10598, IEEE Computer Society Press, pp. 63-70, published May 1994, which is hereby incorporated herein by reference in its entirety.
The distributed locking technique advantageously allows the caching of data on the node on which it is being used. For applications that exhibit coarse-grain sharing, i.e., applications where different nodes are accessing relatively large, contiguous, non-overlapping ranges of a file, the distributed locking technique may perform better than the static file partitioning technique. This is because the distributed locking technique allows the satisfying of most read and write requests from data cached in the local buffer pool, whereas static file partitioning sends a message to another node for almost all read and write requests.
On the other hand, for applications that exhibit fine-grain sharing, i.e., applications where read or write requests from different nodes frequently require access to the same data block of the file, the distributed locking technique may perform worse than the static file partitioning technique. This is because under distributed locking, reads and writes to the same data block from different nodes include revoking tokens, causing extra message traffic and disk I/O. Also, if the application accesses many different, disconnected ranges of a file (e.g., random rather than sequential access), each node will acquire many different byte range tokens; this may lead to an unmanageably large token state that the lock server would need to maintain.
Thus, while each of the concurrency control techniques offers some advantages, neither of the techniques is appropriate in all situations. Therefore, a concurrency control strategy is still needed that at least minimizes the disadvantages of the various techniques. Specifically, a need exists for a strategy that enables the dynamic switching between different types of concurrency control techniques depending on the particular need at the time.
SUMMARY OF THE INVENTION
The shortcomings of the prior art are overcome and additional advantages are provided through the provision of a method of managing access to data of a computing environment. The method includes, for instance, dynamically switching from one type of concurrency control technique to a different type of currency control technique used to access data of the computing environment; and using the different concurrency control technique to access the data.
System and computer program products corresponding to the above-summarized methods are also described and claimed herein.
The concurrency control strategy of an aspect of the present invention advantageously enables the dynamic switching within a single file system from one type of concurrency control technique (e.g., a locking-based technique) to a different type of concurrency control technique (e.g., a non-locking-based technique). This improves system performance by allowing the appropriate technique to be used with the applications most suited for that technique. For example, for applications requiring coarse-grain data sharing, a locking-based technique may be selected; while for applications requiring fine-grain data sharing, a non-locking-based technique may be selected.
Additional features and advantages are realized through the techniques of the present invention. Other embodiments and aspects of the invention are described in detail herein and are considered a part of the claimed invention.
REFERENCES:
patent: 5077658 (1991-12-01), Bendert et al.
patent: 5129088 (1992-07-01), Auslander et al.
patent: 5161227 (1992-11-01), Dias et al.
patent: 5175852 (1992-12-01), Johns
Eshel Marc M.
Hartman Carol D.
Schmuck Frank B.
Wyllie James C.
Alam Shahid
Cutter, Esq. Lawrence D.
Heslin Rothenberg Farley & & Mesiti P.C.
Schiller, Esq. Blanche E.
LandOfFree
Dynamically switching between different types of concurrency... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamically switching between different types of concurrency..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamically switching between different types of concurrency... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3348427