DACO is a proposal to provide disk head separation so that a Read-Modify-Write to update check blocks in RAID arrays with erasure encoding can be processed with a minimal rotational delay. Aside from the difficulty associated with implementation of such R/W heads, there are various reasons why such a disk architecture which runs contrary to the write verify SCSI (read after write) command is not highly desirable. DACO is not utilized by the Disk Array Controller in XORing data from multiple disks and processing updates to prevent write holes. We discuss alternate methods to cope with the small write penalty and quantify the effect of DACO on performance via a simple queueing analysis.

We consider a two level Hierarchical RAID: HRAIDk/ℓ with MDS erasure coding, so that it tolerates k node and ℓ disk failures per node with the minimum redundancy level. With no controller failures WRAIDk/ℓ tolerates all (k + 1)(ℓ + 1) - 1 disk failures, while the maximum number of disk failures tolerated in an array with N nodes and M disks per node is N × ℓ + (M - ℓ)k. We vary RAID controller failure rates with respect to the disk failure rate in a simulation study to determine the Mean Time to Data Loss (MTTDL) and HRAID performability defined as number of I/Os processed till the system fails, while disks are processing requests at their maximum bandwidth. Rebuild via restriping is used to handle both disk and node failures until check strips are exhausted. WRAIDk/ℓ provides the higher MTTDL and performability for kthpercentile of this number may be used to determine the minimum controller failure rate with respect to disk failure rates in a design study to equalize the probability of data loss due to disk and controller failures. We investigate the cost of fault-tolerance by comparing HRAIDk/ℓ performance using maximum I/O rates (IOPS) and mean response times as metrics. System performance is at its worst after controller and disk failures, when the system is operating in degraded mode, but surprisingly the max IOPS increases after restriping, which is due to the reduction in small write penalty as check strips are overwritten. Finally, we undertake a design study to determine the number of disk failures leading to one or more node failures, which is used to determine the maximum controller failure rates. We investigate system performance (maximum IOPS and read response times) in degraded mode and with varying levels of redundancy. There is a strong correlation between MTTDL and performability and k <; ℓ yields the lower performability for highly reliable failure rate.

We consider the allocation of Virtual Arrays (VAs)with different RAID levels in a Heterogeneous Disk Array (HDA). This is expected to provide significant cost savings by consolidating multiple disk arrays into one. Disk load balancing across disk arrays is a by-product of HDA. We provide an example of potential performance benefits expected from HDA. The number of Virtual Disks (VDs) required to materialize a VA is determined by upper bounds on VD bandwidth and space per physical disk drive. Only RAID1 and RAID5 are considered in this paper, but we develop the analysis for other RAID levels. A VA allocation is successful if disks sharing VAs with a failed disk are not overloaded in degraded mode. Single-pass data allocation methods for HDA are evaluated with a synthetic stream of allocation requests. Experimental results show that allocation methods minimizing the maximum disk bandwidth and capacity utilization or their variance across all disks yield the maximum number of allocated VAs. When the disk bandwidth is the bottleneck resource we utilize clustered RAID5 arrays to increase the number of allocated VAs.

Parity is a popular form of data protection in redundant arrays of inexpensive/independent disks (RAID) . RAID5 dedicates one out of N disks to parity to mask single disk failures, that is, the contents of a block on a failed disk can be reconstructed by exclusive-ORing the corresponding blocks on surviving disks. RAID5 can mask a single disk failure, and it is vulnerable to data loss if a second disk failure occurs. The RAID5 rebuild process systematically reconstructs the contents of a failed disk on a spare disk, returning the system to its original state, but the rebuild process may be unsuccessful due to unreadable sectors. This has led to two disk failure tolerant arrays (2DFTs) , such as RAID6 based on Reed-Solomon (RS) codes. EVENODD, RDP (Row-Diagonal-Parity), the X-code, and RM2 (Row-Matrix) are 2DFTs with parity coding. RM2 incurs a higher level of redundancy than two disks, while the X-code is limited to a prime number of disks. RDP is optimal with respect to the number of XOR operations at the encoding, but not for short write operations. For small symbol sizes EVENODD and RDP have the same disk access pattern as RAID6, while RM2 and the X-code incur a high recovery cost with two failed disks. We describe variations to RAID5 and RAID6 organizations, including clustered RAID, different methods to update parities, rebuild processing, disk scrubbing to eliminate sector errors, and the intra-disk redundancy (IDR) method to deal with sector errors. We summarize the results of recent studies of failures in hard disk drives. We describe Markov chain reliability models to estimate RAID mean time to data loss (MTTDL) taking into account sector errors and the effect of disk scrubbing. Numerical results show that RAID5 plus IDR attains the same MTTDL level as RAID6, while incurring a lower performance penalty. We conclude with a survey of analytic and simulation studies of RAID performance and tools and benchmarks for RAID performance evaluation.

Journal Article Reliability and Performance of Mirrored Disk Organizations Get access Alexander Thomasian, Alexander Thomasian * 1Computer Science Department, New Jersey Institute of Technology – NJIT, Newark, NJ 07102, USA2Thomasian and Associates, 17 Meadowbrook Road, Pleasantville, NY 10570, USA *Corresponding author: [email protected], [email protected] Search for other works by this author on: Oxford Academic Google Scholar Jun Xu Jun Xu 1Computer Science Department, New Jersey Institute of Technology – NJIT, Newark, NJ 07102, USA Search for other works by this author on: Oxford Academic Google Scholar The Computer Journal, Volume 51, Issue 6, November 2008, Pages 615–629, https://doi.org/10.1093/comjnl/bxm079 Published: 19 January 2008 Article history Received: 07 March 2006 Revision received: 25 July 2007 Published: 19 January 2008

RAID5 tolerates single disk failures by exclusive-ORing (XORing) the blocks corresponding to a requested block on the failed disk to reconstruct it. This results in increased loads on surviving disks and degraded disk response times with respect to normal mode operation. Provided a spare disk is available, a rebuild process systematically reads successive disk tracks, XORs them to recreate lost tracks and writes them onto a spare disk, thus returning the system to its original state. Rebuild time is important since RAID5 disk arrays with a single disk failure are susceptible to data loss if a second disk fails. According to the vacationing server model (VSM), rebuild read requests on surviving disks are given a lower priority than external user requests, so as to have less impact on their response time. Given that disk loads are balanced due to striping, rebuild time can be approximated by the time to read the contents of any one of the surviving disks. The analysis of the M/G/1 queueing model of VSM, given in this article, is more accurate and yet simpler than a previous analysis, but it also takes into account the effect of disk zoning explicitly. We also present a heuristic method to estimate rebuild time, which can be combined with the new analysis. The ability to quickly and accurately estimate rebuild time is useful in computing the reliability of RAID5 systems, especially during design tradeoff studies. The accuracy of the various analyses to estimate rebuild time are checked against detailed simulation results.

RAID5 disk arrays use the rebuild process to reconstruct the contents of a failed disk on a spare disk, but this process is unsuccessful if latent sector failures are encountered or a second disk failure occurs. The high cost of data loss has led to two-disk failure-tolerant (2DFT) arrays: RAID6, EVENODD, row-diagonal parity (RDP), and RM2. RAID6 uses Reed-Solomon (RS) codes, whereas the latter three use parity encoding. This paper is concerned with the performance from the viewpoint of disk accesses, which, with an appropriate choice of symbol sizes, is the same for RAID6, EVENODD, and RDP, rather than the computational cost (number of XOR operations). We compare the performance of 2DFTs with each other, as well as RAIDO and RAID5 in normal and degraded operating modes. We derive cost functions for processing discrete disk accesses. The mean response time can be obtained analytically with Poisson arrivals and first-come, first-served (FCFS) scheduling. A simulation is used for validation, calibrating the approximate fork-join response analysis, and shortest-access-time-first (SATF) scheduling. The response time for read requests in RAID6 and RM2 is higher than RAID5 and RAIDO and increases with the fraction of write requests. When there is a single disk failure, RM2 outperforms RAID6 since it has a smaller parity group size than RAID6, but RAID6 outperforms RM2 with two disk failures because of its costlier recovery process. Disk loads in RM2 and RAID6 in degraded mode are unbalanced, and a solution based on pseudorandom permutations is proposed for this purpose

Similarity search is a powerful paradigm for image and multimedia databases, time series databases, and DNA and protein sequence databases. Objects are represented by high-dimensional feature vectors based on color, texture, and shape, in the case of images, for example object similarity is usually implemented via k-nearest neighbor (k-NN) queries, determined by the distance of the endpoints of the feature vectors. The cost of processing k-NN queries via a sequential scan increases with the number of objects and the number of dimensions. Multi-dimensional indexing structures can be used to improve the efficiency of k-NN query processing, but lose their effectiveness as the dimensionality increases. The curse of dimensionality manifests itself in the form of increased overlap among the nodes of the index, so that a high fraction of index pages are touched in processing k-NN queries. The increased dimensionality results in a reduced fanout and an increased index height. We propose a stepwise dimensionality increasing (SDI)-tree index, which aims at reducing the number of disk accesses and CPU processing cost. The index is built using feature vectors transformed via principal component analysis. Dimensions are retained in non-increasing order of their variance according to a parameter p, which specifies the incremental fraction of variance at each level of the index. The optimal value for p is determined experimentally. Experiments on three datasets have shown that SDI-trees access fewer disk pages and incur less CPU time than SR-trees, VAMSR-trees, vector approximation (VA)-Files and the recently proposed iDistance method. In CPU time SDI outperforms the sequential scan and OMNI methods.

Similarity search is a popular paradigm in advanced database applications. In content based image retrieval (CBIR) for example, images are transformed into feature vectors, which are then used for similarity search via k-nearest-neighbor (k-NN) queries in the feature vector space. Clustering by building a disk resident index is one method to speed up the processing of k-NN queries. In the case of high-dimensional feature vectors the dimensionality curse results in a high degree of overlap among the minimum bounding rectangles of the index, which results in most pages of the index being accessed. This is especially detrimental to performance, since disk positioning time for random disk accesses is slow and improving only at a rate of 8% annually. We propose an alternative solution to indexing high-dimensional data, which takes advantage of increasing main memory sizes and the 40% annual improvement in disk transfer rates, More specifically we make the Ordered-Partition—OP-tree, which is a main memory resident index, persistent by writing it onto disk. We investigate the optimization of OP-tree parameters and compare its performance with the sequential scan method with and without Karhunen–Loève transformation. We use serialization to compact the dynamically allocated nodes of the OP-tree in main memory, which form a linked list, into a contiguous area. The index can then be saved on disk as a single file and loaded into main memory by a single transfer. The original OP-tree is static, so we propose several methods to support the insertion of new points dynamically. We compare these methods from the viewpoints of time and space efficiency. We also study the effect of incrementally building the index with and without applying the Karhunen-Loève transformation. We compare the processing time of k-NN queries on persistent OP-trees and SR-trees to demonstrate the viability of the proposed method. We use one synthetic and three real world datasets in our experiments.

Disk mirroring or RAID level 1 (RAID1) is a popular paradigm to achieve fault tolerance and a higher disk access bandwidth for read requests. We consider four RAID1 organizations: basic mirroring, group rotate declustering, interleaved declustering, and chained declustering, where the last three organizations attain a more balanced load than basic mirroring when disk failures occur. We first obtain the number of configurations, A(n, i), which do not result in data loss when i out of n disks have failed. The probability of no data loss in this case is A(n, i)/matrix of(n, i). The reliability of each RAID1 organization is the summation over 1 les i les n/2 of A(n, i)rn-i(1 - r)i, where r denotes the reliability of each disk. A closed-form expression for A(n, i) is obtained easily for the first three organizations. We present a relatively simple derivation of the expression for A(n, i) for the chained declustering method, which includes a correctness proof. We also discuss the routing of read requests to balance disk loads, especially when there are disk failures, to maximize the attainable throughput

We provide an improved performance analysis of zoned disk drives, especially the seek distance distribution, than in a paper by Thomasian and Menon.

A heterogeneous disk array (HDA) architecture is proposed that allows device heterogeneity, as well as RAID level heterogeneity. Various disks of different types may be incorporated into a single HDA, and multiple RAID levels may coexist in the same array while sharing disk space. The goal of this architecture is to utilize the resources of all its disks to the maximum possible extent by using appropriate RAID levels to meet the varying availability and performance requirements for different applications. An improved best-fit allocation algorithm is proposed for the HDA to meet this goal.

RAID5 (resp. RAID6) are two popular RAID designs, which can tolerate one (resp. two) disk failures, but the load of surviving disks doubles (resp. triples) when failures occur. Clustered RAID5 (resp. RAID6) disk arrays utilize a parity group size G, which is smaller than the number of disks N, so that the redundancy level is 1/G (resp. 2/G). This enables the array to sustain a peak throughput closer to normal mode operation; e.g. the load increase for RAID5 in processing read requests is given by α = (G − 1)/(N − 1). Three methods to realize clustered RAID are balanced incomplete blocks designs and nearly random permutations, which are applicable to RAID5 and RAID6, and RM2 where each data block is protected by two parity disks. We derive cost functions for the processing requirements of clustered RAID in normal and degraded modes of operation. For given disk characteristics, the cost functions can be translated into disk service times, which can be used for the performance analysis of disk arrays. Numerical results are used to quantify the level of load increase in order to determine the value of G which maintains an acceptable level of performance in degraded mode operation.

Magnetic disk capacity is increasing rapidly, while disk positioning time is decreasing very slowly. Disks are a system bottleneck for applications generating accesses to random disk blocks, which do not benefit from caching and prefetching. Disk mirroring is a solution to this problem, since it provides twice the access bandwidth of a single disk in processing read requests and in addition tolerates single disk failures. Performance can be further improved by affinity-based routing (ABR), i.e. sending a request to a disk which will yield a reduced positioning time. We analytically evaluate a specific instance of ABR in zoned disks, which improves performance (reduces the seek time) by routing read requests intended for outer disk cylinders to one disk and those for inner disk cylinders to another. We evaluate several criteria for specifying the pivot point, which delineates inner and outer disk cylinders. This is accomplished by analyzing the performance of a single zoned disk with FCFS scheduling. Analytic and numerical results show that balancing disk utilizations achieves the same performance as methods that improve the response time. A transposed disk organization, which stores data in reversed directions on two disks, is also proposed and shown to achieve the best performance for fully loaded disks. We also discuss an adaptive approach to implement ABR, so that the pivot point is determined by the router based on the history of routed requests. The simple criterion of balancing disk loads can then be adopted easily in this context.

We address an analysis of the SCAN disk scheduling, which approximates the mean seek distance as the ratio of maximum distance and disk/spl I.bar/queue+1. We also comment on using the mean seek distance to estimate the mean disk response time.

Nearest-neighbor search of high-dimensionality spaces is critical for many applications, such as content-based retrieval from multimedia databases, similarity search of patterns in data mining, and nearest-neighbor classification. Unfortunately, even with the aid of the commonly used indexing schemes, the performance of nearest-neighbor (NN) queries deteriorates rapidly with the number of dimensions. We propose a method, called Clustering with Singular Value Decomposition (CSVD), which supports efficient approximate processing of NN queries, while maintaining good precision-recall characteristics. CSVD groups homogeneous points into clusters and separately reduces the dimensionality of each cluster using SVD. Cluster selection for NN queries relies on a branch-and-bound algorithm and within-cluster searches can be performed with traditional or in-memory indexing methods. Experiments with texture vectors extracted from satellite images show that CSVD achieves significantly higher dimensionality reduction than plain SVD for the same normalized mean squared error (NMSE), which translates into a higher efficiency in processing approximate NN queries.

Advances in magnetic recording technology have resulted in a rapid increase in disk capacities, but improvements in the mechanical characteristics of disks have been quite modest. For example, the access time to random disk blocks has decreased by a mere factor of two, while disk capacities have increased by several orders of magnitude. OLTP applications subject disks to a very demanding workload consisting of accesses to randomly distributed disk blocks and gain limited benefit from caching and prefetching (at the onboard disk cache). We propose some new disk scheduling methods to address the limited disk access bandwidth problem.Some well-known disk scheduling methods are: (i) FCFS. (ii) Shortest Seek Time First (SSTF). (iii) SCAN and Cyclical SCAN (CSCAN). The latter moves the disk arm to its beginning point after each SCAN so that requests at all disk cylinders are treated symmetrically. (iv) CSCAN with a lookahead of next i requests (CSCAN-LAi) takes into account latency to reorder their processing to minimize the sum of their service times. (v) Shortest Access Time First (SATF), which provides the best performance [2]. (vi) SATF with lookahead for i requests (SATF-LAi).In the case of SATF-LAi with i = 2 after the completion of request X the scheduler chooses requests A and B such that the sum of their service times processed consecutively, i.e., tX,A + atA,B, is minimized. In SATF with flexible lookahead only request A is definitely processed and request B is processed provided that it is selected in the next round. We refer to a as the discount factor (0 ≤ a ≤ 1), because less weight is attached to the service time of request B, since it may not be processed after request A. The case a = 0 corresponds to pure SATF. When a = 1 we consider a variant called SATF with fixed lookahead where B is processed unconditionally after A before any other other (perhaps more favorable recent) requests. Thus requests are processed two at a time, unless only one request is available. More generally requests in the temporal neighborhood of request A are given higher priority.

High-dimensionality indexing of feature spaces is critical for many data-intensive applications such as content-based retrieval of images or video from multimedia databases and similarity retrieval of patterns in data mining.Unfortunately, the performance of nearest neighbor (NN) queries, which are required for similarity search, deteriorates rapidly with the increase in the number of dimensions.We propose the Clustering with Singular Value Decomposition (CSVD) method, which combines clustering and singular value decomposition (SVD) to reduce the numb e r o f i n d e x d i m e nsions, while maintaining a reasonably high precision for a given value of recall.In the proposed CSVD method, homogeneous points are grouped into clusters such that the points in each cluster are more amenable to dimensionality reduction than the original dataset.Experiments with texture vectors extracted from satellite images show that CSVD achieves signi cantly higher dimensionality reduction than SVD for the same fraction of total variance preserved.Conversely, for the same compression ratio CSVD results in an increase in preserved total variance with respect to SVD (e.g., a 70% increase for a 20:1 compression ratio).This translates to a higher eciency in processing approximate NN queries, as quanti ed through experimental results.

There is an ever-increasing demand for more complex transactions and higher throughputs in transaction processing systems leading to higher degrees of transaction concurrency and, hence, higher data contention. The conventional two-phase locking (2PL) Concurrency Control (CC) method may, therefore, restrict system throughput to levels inconsistent with the available processing capacity. This is especially a concern in shared-nothing or data-partitioned systems due to the extra latencies for internode communication and a reliable commit protocol. The optimistic CC (OCC) is a possible solution, but currently proposed methods have the disadvantage of repeated transaction restarts. We present a distributed OCC method followed by locking, such that locking is an integral part of distributed validation and two-phase commit. This method ensures at most one re-execution, if the validation for the optimistic phase fails. Deadlocks, which are possible with 2PL, are prevented by preclaiming locks for the second execution phase. This is done in the same order at all nodes. We outline implementation details and compare the performance of the new OCC method with distributed 2PL through a detailed simulation that incorporates queueing effects at the devices of the computer systems, buffer management, concurrency control, and commit processing. It is shown that for higher data contention levels, the hybrid OCC method allows a much higher maximum transaction throughput than distributed 2PL in systems with high processing capacities. In addition to the comparison of CC methods, the simulation study is used to study the effect of varying the number of computer systems with a fixed total processing capacity and the effect of locality of access in each case. We also describe several interesting variants of the proposed OCC method, including methods for handling access variance, i.e., when rerunning a transaction results in accesses to a different set of objects.

A number of recent studies have proposed lock conflict resolution methods to improve the performance of standard locking, i.e., strict two-phase locking with the general waiting method. This paper is primarily concerned with the performance of wait depth limited methods with respect to each other and some other methods. The methods considered include the general waiting, wound-wait, and no-waiting methods, symmetric and asymmetric versions of cautious waiting and running priority methods, the wait depth limited (WDL) method, and a modified version of it. In spite of the availability of analytic solutions for most of wait depth limited methods, for reasons given in-the paper, the performance comparison is based on simulation results. The contributions of this study are as follows: 1) modeling assumptions, i.e., a careful definition of transaction restart options; 2) new results concerning the relative performance of wait depth limited methods, which show that a) the running priority method outperforms cautious waiting and may even outperform the WDL method in a system with limited hardware resource, b) WDL outperforms other methods in high lock contention, high capacity systems, and c) modified WDL has a performance comparable to WDL, but incurs less overhead in selecting the abort victim; and 3) contrary to common belief, Tay's Effective Database Size Paradigm for dealing with shared and exclusive locks and/or skewed database accesses in standard locking is applicable to some wait depth limited methods and provides acceptably accurate approximations in others-as long as locking modes for restarted transactions are not resampled.

Distributed sparing is a method to improve the performance of RAID5 disk arrays with respect to a dedicated sparing system with N+2 disks (including the spare disk), since it utilizes the bandwidth of all N+2 disks. We analyze the performance of RAID5 with distributed sparing in normal mode, degraded mode, and rebuild mode in an OLTP environment, which implies small reads and writes. The analysis in normal mode uses an M/G/1 queuing model, which takes into account the components of disk service time. In degraded mode, a low-cost approximate method is developed to estimate the mean response time of fork-join requests resulting from accesses to recreate lost data on the failed disk. Rebuild mode performance is analyzed by considering an M/G/1 vacationing server model with multiple vacations of different types to take into account differences in processing requirements for reading the first and subsequent tracks. An iterative solution method is used to estimate the mean response time of disk requests, as well as the time to read each disk, which is shown to be quite accurate through validation against simulation results. We next compare RAID5 performance in a system (1) without a cache; (2) with a cache; and (3) with a nonvolatile storage (NVS) cache. The last configuration, in addition to improved read response time due to cache hits, provides a fast-write capability, such that dirty blocks can be destaged asynchronously and at a lower priority than read requests, resulting in an improvement in read response time. The small write penalty is also reduced due to the possibility of repeated writes to dirty blocks in the cache and by taking advantage of disk geometry to efficiently destage multiple blocks at a time.

Restart-oriented concurrency control (CC) methods, such as optimistic CC, outperform blocking-oriented methods, such as standard two-phase locking in a high data contention environment, but this is at the cost of wasted processing due to restarts. Volatile savepoints are considered in this study as a method to reduce this wasted processing and to improve response time. There is the usual tradeoff between the checkpointing overhead and the wasted processing when a transaction is restarted. Our study shows that in a system where objects are accessed and updated uniformly during the lifetime of transactions, significant improvement in performance at high data conflict levels are attainable only when the checkpointing cost is low. This implies few optimally placed checkpoints per transaction. It is observed that checkpointing may result in a significant improvement in performance when access to database hot-spots are deferred to the final steps of transaction execution. The parametric studies reported in this paper are facilitated by closed-form analytic solutions expressing system performance, as well as an iterative solution which takes into account hardware resource contention in addition to data contention.>

Most performance modeling studies of lock contention in transaction processing systems are deficient in that they postulate a homogeneous database access model. The non-homogeneous database access model described in this paper allows multiple transaction classes with different access patterns to the database regions. The performance of the system from the viewpoint of lock contention is analyzed in the context of the standard two-phase locking concurrency control method with the general waiting policy. The approximate analysis is based on mean values of parameters and derives expressions for the probability of lock conflict (usually leading to transaction blocking) and the mean blocking time. The latter requires estimating the distribution of the effective wait-depth encountered by blocked transactions and the mean waiting time associated with different blocking levels. The accuracy of the analysis is validated against simulation results and also shown to be more accurate than analytic solutions considering only two levels of transaction blocking. Previously proposed metrics for load control have limited applicability for the model under consideration.>

We analyze the performance of RAIDS disk arrays in normal, degraded, and rebuild modes. The analysis, which is shown to be highly accurate through validation against simulation results, achieves its accuracy by (1) modeling detailed disk characteristics; (2) developing a simple approximation to compute the mean response time for fork-join requests arising in degraded mode operation; and (3) using a vacationing server model with multiple vacation types for rebuild mode analysis. According to this model vacations (rebuild reads) are started when the server (disk) becomes idle and are repeated until the arrival of an external disk request. Type one (two) vacations correspond to the reading of the first track which requires a seek (successive tracks requiring no seeks). The analytic solution is used to quantify the effect of different rebuild options, such as read redirection and the split-seek option.>

An analysis of a threshold policy for scheduling readers and writers in a multiserver system and a comparison of its performance with the first-come, first-served (FCFS) policy are presented. The threshold fastest emptying (FTE) policy is analyzed in a system with writer arrivals and an infinite backlog of readers using a Markovian model as well as a vacationing server model to yield closed-form expressions for the mean writer response time and the reader throughput. The maximum throughput achieved by the TFE policy is shown to be an increasing function of K, the threshold on the number of writers in the system, which even at K=1 exceeds the maximum throughput achieved by FCFS. In a system with reader and writer arrivals (nonsaturated system), simulation is used to study and compare the mean response time for the FCFS and the TFE policies.>

article Free Access Share on Two-phase locking performance and its thrashing behavior Author: Alexander Thomasian IBM T. J. Watson Research Center IBM T. J. Watson Research CenterView Profile Authors Info & Claims ACM Transactions on Database SystemsVolume 18Issue 4Dec. 1993 pp 579–625https://doi.org/10.1145/169725.169720Published:01 December 1993Publication History 58citation1,233DownloadsMetricsTotal Citations58Total Downloads1,233Last 12 Months123Last 6 weeks62 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The performance of high-volume transaction processing systems for business applications is determined by the degree of contention for hardware resources as well as for data. Hardware resource requirements may be met cost-effectively with a data-partitioned or shared-nothing architecture. However, the two-phase locking (2PL) concurrency control method may restrict the performance of a shared-nothing system more severely than that of a centralized system due to increased lock holding times. Deadlock detection and resolution are an added complicating factor in shared-nothing systems. The authors describe distributed Wait-Depth Limited (WDL) concurrency control (CC), a locking-based distributed CC method that limits the wait-depth of blocked transactions to one, thus preventing the occurrence of deadlocks. Several implementations of distributed WDL which vary in the number of messages and the amount of information available for decision making are discussed. The performance of a generic implementation of distributed WDL is compared with distributed 2PL (with general-waiting policy) and the Wound-Wait CC method through a detailed simulation. It is shown that distributed WDL behaves similarly to 2PL for low lock contention levels, but for substantial lock contention levels (caused by higher degrees of transaction concurrency), distributed WDL outperforms the other methods to a significant degree.>

The number of remote accesses and the number of distinct remote sites accessed by global transactions in a distributed database environment are characterized. Both measures are important in determining the overhead of distributed transaction processing and are affected by the distribution of transaction size (number of distinct objects accessed by a transaction) and the distribution of remote accesses made by a transaction. Keeping the mean transaction size fixed, it is shown that in the case of some commonly used distributions for the number of remote accesses variable size transactions access fewer distinct remote sites on the average than fixed size transactions. Also, for these and some other distributions the mean number of remote accesses is independent of the distribution of transaction size, but this is not generally true.>

Distributed wait-depth-limited (DWDL) concurrency control, a locking-based method that limits the wait-depth of blocked transactions to one, which assures that deadlocks are resolved as part of regular transaction processing is described. The performance of DWDL is compared with that of distributed two-phase locking (2PL) and the wound-wait concurrency control method through a detailed simulated. Results show that DWDL behaves similarly to 2PL for low data contention levels, but at high lock contention levels, DWDL outperforms the other methods to a significant degree.>

Allocation and reallocation techniques for resources in a distributed database (DDB) system are discussed. An abstract model of the DDB, which partitions data among a set of nodes in a network, is presented. Initial resource allocation and demand driven borrowing policies are investigated using the model. It is shown that a single token borrowing policy which attempts to correct the greatest waste of resources in the system, achieves a cost within several percent of the unachievable lower bound, and multiple token borrowing polices, which anticipate future need and keep the system balanced with respect to the remaining number of tokens, perform much better than those that only borrow the needed amount.>

The fraction of blocked transactions ( beta ) and the conflict rate, the ratio of locks held by all and active transactions, have been proposed as parameters to be monitored for load control. This study investigates the robustness of these parameters in the case of transactions requesting a variable number of locks and different processing times for transaction steps. Simulation results show that beta and the fraction of lock conflicts with blocked transactions rho both vary in a rather narrow range as transaction parameters are varied. The fact that rho is a key parameter and is suitable for implementing load control is demonstrated by developing an analytic solution method which utilizes it in an equation. Validation results show that this method is quite accurate and outperforms an earlier solution method based on two levels of transaction blocking.>

The performance of a transaction processing system with the standard two-phase locking (2PL) concurrency control (CC) method (with the general waiting policy upon a lock conflict) may be degraded significantly due to transaction blocking in a high lock contention environment. In the limit this effect leads to the thrashing phenomenon, i.e., the majority of the transactions in the system become blocked. Limiting the wait depth of blocked transactions is an effective method to increase the number of active transactions in the system and to prevent thrashing, but this is at the cost of additional processing due to transaction restarts. The no-waiting (or immediate restart) policy limits the wait-depth to zero, while cautious waiting and the running priority policies use different methods to limit the wait depth to one. A variant of the wait depth limited (WDL) policy [8] also limits the wait depth to one, while attempting to minimize the wasted processing incurred by transaction aborts. A unified methodology to analyze the performance of the 2PL CC method with limited wait depth policies in a system with multiple transaction classes is described in this paper. The analysis is based on Markov chains representing the execution steps of each transaction in isolation, but as affected by hardware resource and data contention with other transactions in the system. Since the transition rates of the Markov chain are not known a priori, an iterative solution method is developed, which is then applied to the running priority and WDL policies. Simulation is used for validating the accuracy of the approximate analytic solutions. Of interest are the conservation laws governing the rate at which locks are transferred among transactions, which can be used to verify the correctness of the analysis.

Future transaction processing systems may have substantially higher levels of concurrency due to reasons which include: (1) increasing disparity between processor speeds and data access latencies, (2) large numbers of processors, and (3) distributed databases. Another influence is the trend towards longer or more complex transactions. A possible consequence is substantially more data contention, which could limit total achievable throughput. In particular, it is known that the usual locking method of concurrency control is not well suited to environments where data contention is a significant factor. Here we consider a number of concurrency control concepts and transaction scheduling techniques that are applicable to high contention environments, and that do not rely on database semantics to reduce contention. These include access invariance and its application to prefetching of data, approximations to essential blocking such as wait depth limited scheduling, and phase dependent control. The performance of various concurrency control methods based on these concepts are studied using detailed simulation models. The results indicate that the new techniques can offer substantial benefits for systems with high levels of data contention.

A new class of wait depth limited (WDL) concurrency control (CC) methods is described. The WDL policy is shown by simulations to be effective both in systems with proportionately large I/O latencies as well as in systems with large numbers of processors. WDL is also attractive in terms of implementation. In many applications little or no system modification may be required other than the CC code. Since it is a lock-based method, unlike optimistic methods, there is no need for private copies of modified data for each transaction, nor is there any need for snapshot, timestamp, or versioning mechanisms to guarantee that transactions are always provided with a fully consistent database image.>

A novel mean-value analysis method for two-phase locking (2PL) is presented which extends previous work to the important case of variable size transactions. The system performance expressed as the fraction of blocked transactions ( beta ) is determined by solving a cubic equation in beta whose coefficients are functions of a single parameter ( alpha ), which determines the degree of lock contention in the system. In fact, alpha is proportional to the mean number of lock requests per transaction ( eta /sub c/) and additionally the mean waiting time (W/sub 1/) for a lock held by an active transaction. For alpha>

A straightforward analytic solution method is developed which takes into account the variability of transaction size (the number of lock requests). The authors first obtain analytic expressions for the probability of lock conflict, probability of deadlock, and the waiting time per lock conflict. They then develop a family of noniterative analytic solutions to evaluate the overall system performance by considering the expansion in transaction response time due to transaction blocking. The accuracy of these solutions is verified by validation against simulation results. Also introduced is a new measure for the degree of lock contention, which is a product of the mean number of lock conflicts per transaction and the mean waiting time per lock conflict (when blocked by an active transaction). It is shown that the variability in transaction size results in an increase in both measures as compared to fixed-size transactions of comparable size. The authors also provide a solution method for the case when the processing times of transaction steps are different.>

A distributed optimistic concurrency control (OCC) method followed by locking, such that locking is an integral part of distributed validation and two-phase commit is presented. This OCC method ensures that a transaction failing its validation will not be reexecuted more than once, in general. Furthermore, deadlocks, which are difficult to handle in a distributed environment, are avoided by serializing lock requests. Implementation details are outlined, and the performance of the schemes is compared with distributed two-phase locking (2PL) through a detailed simulation, which incorporates queueing effects at the devices of the computer systems, buffer management, concurrency control, and commit processing. It is shown that in the case of higher data contention levels, the hybrid OCC method allows a much higher maximum transaction throughput than distributed 2PL. The performance of the method with respect to variable-size transactions is reported. It is shown that by restricting the number of restarts to one, the performance achieved for variable-size transactions is comparable to fixed-size transactions with the same mean size.>

Various factors suggest that data contention may be of increasing significance in transaction processing systems. One approach to this problem is to run transactions twice, the first time without making any changes to the database. Benefits may result either from data prefetching during the first execution or from determining the locks required for purposes of scheduling. Consideration is given to various concurrency control methods based on this notion, and properties required for these methods to be useful are formalized. Performance results based on detailed simulation models suggest that such policies offer potential benefits for some system configurations.>

A detailed model of a transaction processing system with dynamic locking is developed and analyzed. Transaction classes are distinguished on the basis of the number of data items accessed and the access mode (read-only/update). The performance of the system is affected by transaction blocking and restarts, due to lock conflicts that do not or do cause deadlocks, respectively. The probability of these events is determined by the characteristics of transactions and the database access pattern. Hardware resource contention due to concurrent transaction processing is taken into account by specifying the throughput characteristic of the computer system for processing transactions when there is no data contention. A solution method based on decomposition is developed to analyze the system, and also used as the basis of an iterative scheme with reduced computational cost. The analysis to estimate the probability of lock conflicts and deadlocks is based on the mean number of locks held by transactions. These probabilities are used to derive the state transition probabilities for the Markov chain specifying the transitions among the system states. The decomposition solution method and the associated iterative scheme are shown to be more accurate than previously defined methods for dynamic locking through validation against simulation results. Several important conclusions regarding the behavior of dynamic locking systems are derived from parametric studies.

A transaction processing system with two-phase dynamic locking with the no waiting policy (DLNW) for concurrency control is considered. In this method, transactions making conflicting lock requests are aborted and restarted rather than blocked, thereby eliminating blocking delays (and deadlocks), but making it susceptible to cyclic restarts. Cyclic restarts are dealt with by delaying the restart of a transaction encountering a lock conflict or replacing it with a new transaction. Analytic solution methods for evaluating the performance of the variants of the DLNW method are described. The analytic methods, validated against simulation and shown to be acceptably accurate, are used to study the effect of the following parameters on system performance: transaction size and its distribution, degree of concurrency, the throughput characteristic of the computer system, and the mixture of read-only query and update transactions. A comparison of the DLNW and dynamic locking with waiting (DLW) methods shows that DLW provides higher throughput than DLNW, except when there is no hardware resource contention and conflicted transactions can be replaced by new transactions. The DLNW method outperforms the time-stamp ordering method, as observed from simulation results as well as case by case analyses of possible scenarios.>

This paper is concerned with the performance evaluation of a realistic model of parallel computations. We present an efficient algorithm to determine the mean completion time and related performance measures for a task system: a set of tasks with precedence relationships in their execution sequence, such that the resulting graph is acyclic. A queueing network (QN) is used to model tasks executing on a single or multicomputer system. In the case of multicomputer systems, we take into account the delay due to interprocess communication. A straight- forward application of a QN solver to the problem is not possible due to variations in the state of the system (composition of tasks in execution). An accurate algorithm based on hierarchical decomposition is presented for solving task systems. At the higher level, the system behavior is specified by a Markov chain whose states correspond to the combination of tasks in execution. The state transition rate matrix for the Markov chain is triangular (since the task system graph was assumed to be acyclic), therefore it can be solved efficiently to compute the state probabilities and the task initiation/completion times. At the lower level, the transition rates among the states of the Markov chain are computed using a QN solver, which determines the throughput of the computer system for each system state. The model and the solution method can be used in performance evaluation of applications exhibiting concurrency in centralized/distributed systems where there are conflicting goals of load balancing and minimizing interprocess communication overhead.

The performance of transaction processing systems is determined by the contention for hardware as well as software resources (database locks), due to the concurrency control mechanism of the database being accessed by transactions. We consider a transaction processing system with a set of dominant transcation classes. Each class needs to acquire a certain subset of the locks in the database before it can be processed, i.e., predeclared lock requests with static locking. Straightforward application of the decomposition method requires the numerical solution of a two-dimensional Markov chain. Equivalently, a hierarchical simulation method, where the computer system is represented by a composite queue with exponential service rates, can be used to analyze the system. We propose an inexpensive analytic solution method, also based on hierarchical decomposition, such that the throughput of the computer system ic characterized by the number of active transactions (regardless of class). Numerical results are provided to show that the new method is adequately accurate compared to the other two rather costly methods. It can be used to determine the effect of granularity of locking on system performance. The solution method is also applicable to multiresource queueing systems with multiple contention points.

This paper deals with the analysis of large-scale closed queueing network (QN) models which are used for the performance analysis of computer communication networks (CCN's). The computer systems are interconnected by a wide-area network. Users accessing local/remote computers are affected by the contention (queueing delays) at the computer systems and the communication subnet. The computational cost of analyzing such models increases exponentially with the number of user classes (chains), even when the QN is tractable (product-form). In fact, the submodels of the integrated model are generally not product-form, e.g., due to blocking at computer systems (multiprogramming level constraints) and in the communication subnet (window flow control constraints). Two approximate solution methods are proposed in this paper to analyze the integrated QN model. Both methods use decomposition and iterative techniques to exploit the structure of the QN model such that computational cost is proportional to the number of chains. The accuracy of the solution methods is validated against each other and simulation. The model is used to study the effect that channel capacity assignments, window sizes for congestion control, and routing have on system performance.

Queueing Network Models - QNM's with population size constraints and delayed blocked customers occur due to MultiProgramming Level - MPL constraints in computer systems and window flow-control mechanisms in Computer Communication Networks - CCN's. The computational cost of existing algorithms is unacceptable for large numbers of chains and high population sizes. A fast approximate solution technique based on load concealment is presented to solve such QNM's. The solution procedure is non-iterative in the case of fixed rate Poisson arrivals, while iteration is required in the case of quasi-random arrivals. Each iteration requires the solution of a single chain network of queues comprised of stations visited by each chain. We then present an algorithm to detect saturated chains and determine their maximum throughput. A fast solution algorithm due to Reiser for closed chains is also extended to the case of quasi-random arrivals. The accuracy of the proposed solution techniques is compared to previous techniques by applying it to a test case, reported in the literature, and a set of randomly generated examples.

The effect of concurrency control methods on the performance of computer systems is analyzed in the context of a centralized database with a static lock request policy, i.e., database transactions should acquire all locks before their activation. In the lock conflict model the L locks required by each transaction are uniformly distributed over the N locks in the database. The computer system is modelled as a queueing network. Two scheduling policies for transaction activation are considered: FCFS with and without skip. In each case the scheduling overhead for scanning the blocked transactions is taken into account. The number of transactions to be scanned is limited by a window size parameter. The system is analyzed using a hierarchical decomposition method, where the highest level model yields the mean user response time. The results of the approximate solution are validated using a detailed simulation, which shows that the analysis based on no resampling of locks is quite accurate and outperforms the simplified analysis with resampling of locks in accuracy. The effect of varying the values of parameters such as transaction size, granularity of locking, scheduling discipline for transaction activation, scheduling overhead, and window size on system performance is investigated.

In queueing network models the complexity of the model can be reduced by aggregating stations. This amounts to obtaining the throughput of the flow-equivalent station for the subnetwork of stations to be aggregated. When the subnetwork has a separable solution, aggregation can be carried out using the Chandy-Herzog-Woo theorem. The throughput of the subnetwork can be expressed explicitly in terms of its parameters when the stations are balanced (have equal utilizations). This expression for throughput can be used as an approximation when the stations are relatively unbalanced. The basic expression can be modified to increase the accuracy of the approximation. A generating function approach was used to obtain upper bounds on the relative error due to the basic approximation and its modifications. Provided that the relative error bound is tolerable, a set of unbalanced stations can be replaced by a single aggregate station or a set of balanced stations. Finally, we propose a methodology to simplify the queueing network model of a large-scale multiprogrammed computer, which makes use of the previous aggregation results.

The motivations for the design study of a modular, shared resource computing system are given by discussing fault-tolerance and resource utilization issues in parallel processing architectures. A design is presented which employs an array of pipelined arithmetic processors to perform array operations. The design provides for fault-tolerance (“graceful degradation”) capability and is efficient in using main memory bandwidth. Various architectural tradeoffs of the design are discussed. Some results of simulations used for the verification of design decisions are also reported.