SSD performance is inherently non-deterministic due to the internal management
activities such as the garbage collection, wear leveling, and internal buffer
flush. 168168168https://en.wikipedia.org/wiki/Wear_leveling I/O Determinism
interface is a host/SSD co-designed flash array with predictable latency,
which does not sacrifice aggregate bandwidth Li et al. 2023 [130]. Minimal
changes to the NVMe interface and flash firmware was required to achieve near
ideal latencies. 169169169https://en.wikipedia.org/wiki/NVM_Express

###  7.8 Computational Storage Drives - CSD

Active Disks projects at the turn of the century took advantage of processing
power on individual disk drives to run database, data mining, and multimedia
applications as discussed in Section 8.14 in Thomasian 2021 [245]. Active
disks dramatically reduce data traffic and take advantage of the storage
parallelism, since there are many disks Riedel et al. 1998 [190]. A scheme
supporting a Data Mining workload on an OLTP system almost for free is
possible via so-called freeblocks scheduling Lumb et al. 2000 [135] with a
small impact on the throughput and response time of the existing workload
Riedel et al. 2000 [191].

Modern CSDs can efficiently deals with high volumes of data for AI
applications. Field Programmable Gate Arrays - FPGAs are used in some cases in
preference to CPUs. Table 5 in Do et al. 2020 [43] lists five research and
four commercial products of which Newport developed at NGD.com is the only one
with a Linux OS and a file system. Newport hardware is given in Fig. 1 and
Fig. 5 shows its connection to a host running Linux. Major applications of
Newport are Nearest Neighbor -NN search and tracking objects in videos.
Results for Batch Similarity Search - BSS in Fig. 12 specify queries per
second - qps versus energy consumption in kiloJoules - kJ. Experiments with
four configurations yield: (1) host-only (1 SSD) 120 kJ, 2.00 qps. (2) host
only (8 SSDs) 110 kJ, 2.25 qps. (3) hybrid (8 SSDs) 80 kJ, 5.52 qps. (4)
hybrid (24 SSDs), 45 KJ, 9.64 qps.

You Only Look Once - YOLO is a real-time object detection software Redmon 2016
[188] versions of which were compared with others running a GPU., CPU, and CSD
are given in Table 17, whch is based in Table 2 in the paper. Intersection
over Union - IoU is the key metric for quality of object detection.
170170170https://www.superannotate.com/blog/intersection-over-union-for-
object-detection

Computing | Object | Overall | Avg-per video | Energy usage
---|---|---|---|---
resource | tracker | throughput | throughput | Joules/frame
GPU | YOLOv3 | 34.79 | 34.66 | 6.03
CPU | YOLO-lite | 2.72 | 2.76 | 14.26
CSD | YOLO-lite | 2.36 | 0.23 | 2.00
Table 17: Throughput and energy consumption of versions of YOLO object tracker
running on different platforms FPS=Frames per Second

Energy consumption (Joules/frame and accuracy of executing object trackers
(IoU) on different computing resources is given in Fig. 13. The results for
YOLO on GPU, CPU and CSD are as follows: (15.26 J/frame, 0.13), (6.03 J/frame,
0.35), (2.00 J/frame 0.13), respectively.

Storage Networking Industry Association - SNIA maintains a library on
computational storage. 171171171https://www.snia.org/education/what-is-
computational-storage

##  8 Interconnection Networks

Direct Access Storage - DAS via I/O channels was an early connectivity
paradigm in dominant IBM mainframes.
172172172\https://en.wikipedia.org/wiki/Channel_I/O A simplified analysis of
delays incurred by circuit-switched I/O channels and related studies appears
in Chapter 10 of Lazowska et al. 1984 [129]. Rotational Position Sensing - RPS
made available with IBM 3330 drives disconnects channel and controller during
disk latency phase for improved performance. An RPS miss is failure to
reconnect possibly using a different path result in extra rotation Rafii 1976
[182]

Storage Area Network - SAN typically use Fibre Channel connectivity,
173173173https://en.wikipedia.org/wiki/Fibre_Channel while Network Attached
Storage - NAS use standard Ethernet connection.
174174174https://en.wikipedia.org/wiki/Ethernet SANs store data at the block
level, while NAS at file level.
175175175https://en.wikipedia.org/wiki/Network-attached_storage

Fibre Channel connection - FICON provide high-speed data transfer between
systems and storage devices. Fibre Channel networks consist of servers,
storage controllers, and storage devices as end nodes, which are
interconnected by Fibre Channel switches, directors, and hubs. FICON is
available from IBM, Dell/EMC and Hitachi Schulz 2004 [205].
176176176https://www.computerweekly.com/feature/Mainframe-storage-Three-
players-in-a-market-thats-here-to-stay The I/O organization of latest (z16)
mainframes which are based in Telum processor are described in Chapter 4.
177177177https://www.redbooks.ibm.com/redbooks/pdfs/sg248951.pdf The PCIe Gen.
3 uses 128b/130b encoding for data transmission reducing encoding overhead to
approximately 1.54% versus the PCIe Gen. 2 overhead of 20% that uses 8b/10b
encoding. 178178178https://en.wikipedia.org/wiki/64b/66b_encoding

Disaggregated storage allows storage devices to function as a storage pool,
where devices can be allocated to any server on the network.
179179179https://en.wikipedia.org/wiki/Disaggregated_storage Fungible Inc.
founded in 2015 and acquired by Microsoft in 2023
180180180https://en.wikipedia.org/wiki/Fungible_Inc. developed Data Processing
Units - DPUs enabling composable disaggregated infrastructure.
181181181https://blogs.nvidia.com/blog/whats-a-dpu-data-processing-unit/

There is a significant increase in bandwidths used at hyperscaler data storage
centers, e.g., 100 Gb/s. 182182182https://www.nextplatform.com/2019/08/18/the-
future-of-networks-depends-on-hyperscalers-and-big-clouds/ Interconnection
network reliability and performance are discussed in Goyal and Rajkumar 2020
[70] and Rojas-Cessa 2017 [194] (Part III - Data Center Networks - DCNs),
respectively. Jupiter DCN may scale to more than 30K servers with 40 Gb/s per-
server, supporting more than 1 Pb/sec of aggregate bandwidth.
183183183https://cloud.google.com/blog/topics/systems/the-evolution-of-
googles-jupiter-data-center-network

Non-Volatile Memory Express - NVMe is an optimized high performance, software
standard for accessing NVM over Peripheral Component Interconnect Express -
PCIe. 184184184https://nvmexpress.org NVMe-SSDs which are PCIe-based are
superior to SATA and SAS SSDs in terms of bandwidth and latencies sustaining
up to one million IOPS and a 90 $\mu$second latency. The NVMe-over-Fabrics -
NVMe-oF remote storage protocol reduces the remote access overhead to less
than 10$\mu$second Guz et al. 2018 [76].

Remote Direct Memory Access - RDMA supports zero-copy networking by enabling
the network adapter to transfer data from the wire directly to application
memory or vice-versa, eliminating the need to copy data between application
memory and the data buffers in the OS. Such transfers require no work to be
done by CPUs, etc.
185185185https://en.wikipedia.org/wiki/Remote_direct_memory_access Two
versions of RDMA over Converged Ethernet - RoCE are: v1 communication between
any two hosts, v2: am internet layer protocol which allows packets to be
routed. 186186186https://en.wikipedia.org/wiki/RDMA_over_Converged_Ethernet

InfiniBand is a computer networking communications standard used in high-
performance computing with high throughput and very low latency. It is used
for data interconnect both among and within computers.
187187187https://en.wikipedia.org/wiki/InfiniBand
https://network.nvidia.com/pdf/whitepapers/IB_Intro_WP_190.pdf

##  9 Conclusions: Cloud Storage

Cloud Storage allows user to maintain their data in the cloud. There are the
following considerations: Advantages: 1\. Accessibility via the internet or
dedicated lines. 2\. Scalability. 3\. Cost-effective, pay-as you-go. 4\.
Redundancy ensuring high availability. 5\. Security. Disadvantages: 1\.
Dependence on connectivity. 2\. Privacy concerns (handled by encryption). 3\.
Limited control. 4\. Risk of data loss. 5\. Cost structure.

Teradata Vantage can run on premise and three different public clouds
simultaneously.
188188188https://assets.teradata.com/resourceCenter/downloads/Datasheets/Teradata-
Vantage-on-Google-Cloud-MD006022.pdf The user can create an Ubuntu VM with 4
CPU’s and 8GB of RAM, a 70GB balanced disk. Dedicated private connections or
Internet are two connectivity choices. Vantage relies on block storage with
fixed sized blocks rather than object and file storage.
189189189https://quickstarts.teradata.com/vantage.express.gcp.html AWS’s
Relational Data Services - RDS allows Oracle’s MySQL and PostgreSQL.
190190190https://www.theregister.com/2023/11/29/aws_launch_ibms_db2_database/
Options provided by Google’s storage are listed here.
191191191https://cloud.google.com/compute/docs/disks

Amazon Elastic Block Store - EBS supports both SSDs and HDDs provides block-
level storage volumes for users of Amazon Elastic Compute Cloud - EC2
instances. 192192192https://aws.amazon.com/pm/ec2/ EBS supports RAID1, RAID1,
RAID5 , RAID6 and RAID10. 193193193https://aws.amazon.com/blogs/aws/new-
amazon-s3-storage-class-glacier-deep-archive/ AWS Simple Storage Service - S3
Glacier storage classes deliver cost-optimized archive storage. Amazon EBS
charges users by storage capacity (GBs provisioned per month).
194194194https://aws.amazon.com/ebs/pricing/ Users also pay for IOPS and
throughput. Amazon EBS does not recommend RAID 5 or RAID 6 because of extra
IOPS (20-30%) with respect to RAID0, which may be considered a shift in RAID
paradigm..

Cloud storage is unacceptable solution for real time applications such as
those associated with Internet of Things - IoT.
195195195https://en.wikipedia.org/wiki/Internet_of_things Industrial IoT for
smart manufacturing has real time requirements.
196196196https://www.automate.org/editorials/the-relationship-between-real-
time-computing-and-the-internet-of-things-iot

Readers may follow rapid advances in the field by referring to the
comprehensive list of trade and academic publications provided in the Appendix
in Thomasian 2021 [245].

## References

  * [1] [1] J. Abate, H. Dubner, and S. B. Weinberg. 1968. Queueing analysis of the IBM 2314 disk storage facility. J. ACM 15, 4 (1968), 577-589.
  * [2] [2] M. Abd-El-Malek, W. V. Courtright II, C. Cranor, G. R. Ganger, J. Hendricks, A. J. Klosterman, M. P. Mesnier et al. 2005. Ursa Minor: Versatile cluster-based storage. In Proc. 4th USENIX File and Storage Technologies - FAST 2005: 69-72.
  * [3] [3] I. U. Akgun, A. S. Aydin, A. Burford, M. McNeill, M. Arkhangelskiy, and E. Zadok. 2023. Improving storage systems using machine learning. ACM Trans. Storage 19, 1 (2023), 9:1-9:30.
  * [4] [4] G. A. Alvarez, W. A., Burkhard, and G. Cristian. 1997. Tolerating multiple failures in RAID architectures with optimal storage and uniform declustering. In Proc. 24th Ann’l Int’l Symp. Computer Architecture - ISCA’97: 62-72.
  * [5] [5] G. A. Alvarez, W. A, Burkhard, L. J. Stockmeyer, and F. Christian. 1998 Declustered disk array architectures with optimal and near optimal parallelism. In Proc. 25th Int’l Symp. Computer Architecture, ISCA’98: 119-120.
  * [6] [6] A. Amer, D. D. E. Long, E. L. Miller, J. F. Pâris, and T. J. E. Schwarz. 2010. Design issues for a shingled write disk system. In Proc. 26th IEEE Symp. on Massive Storage Systems and Technologies, MSST 2010: 1-12
  * [7] [7] G. Amvrosiadis, A. Oprea, and B. Schroeder. 2012. Practical scrubbing: Getting to the bad sector at the right time. In Proc. 42nd IEEE/IFIP Dependable Systems and Networks, DSN 2012, 1-12.
  * [8] [8] D. Anderson, J. Dykes, and E. Riedel. 2003. More Than an Interface - SCSI vs. ATA. In Proc. 2nd USENIX Conference on File and Storage Technologies, FAST 2003: 245-257.
  * [9] [9] D. G. Andersen, J. Franklin, M. Kaminsky, A. Phanishayee, L. Tan, and V. Vasudevan. 2011 FAWN: A Fast Array of Wimpy Nodes Commun. ACM, 54, 7 (July 2011), 101-109.
  * [10] [10] J. E. Angus. 1988. On computing MTBF for a k-out-of-n: G Repairable System. IEEE Trans. Reliability 37, 3 (1988), 312-313.
  * [11] [11] M. Athanassoulis, A. Ailamaki, S. Chen, P. B. Gibbons, and R. Stoica. 2010. Flash in a DBMS: Where and how? IEEE Data Engineering Bulletin 33, 4 (2010), 28-34.
  * [12] [12] A. Amer, T. J. E. Schwarz, J. F. Paris, and D. D. E. Long. 2008. Increased reliability with SSPiRAL data layouts. In Proc. 17th IEEE/ACM Int’l Symp. on Modeling, Analysis, and Simulation On Computer and Telecomm. Systems - MASCOTS 2008, 189-198.
  * [13] [13] L. N. Bairavasundaram, G. R. Goodson, S. Pasupathy, and J. Schindler. 2007. An analysis of Latent Sector Errors in disk drives. In Proc. Int’l Conf. on Measurements and Modeling of Computer Systems, SIGMETRICS’07, 289-300.
  * [14] [14] M. Balakrishnan, A. Kadav, V. Prabhakaran, and D. Malkhi. 2010. Differential RAID: Rethinking RAID for SSD reliability, ACM Trans. Storage 6, 2 (July 2010), Article No. 4.
  * [15] [15] L. Barroso, M. Marty, D. Patterson, and P. Ranganathan. 2017. Attack of the killer microseconds. Commun. ACM 60, 4 (April 2017), 48–54.
  * [16] [16] S. H. Baek and K. H. Park. 2008. Prefetching with adaptive cache culling for striped disk arrays. In Proc. USENIX Ann’l Technical Conf., ATC 2008: 363-376.
  * [17] [17] J. Basak and R. Katz. 2015. RAID-Cube: The Modern Datacenter Case for RAID. EECS Dept. UC Berkeley. TR NO. UCB/EECS-2015-4.
https://www2.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-4.pdf

  * [18] [18] D. Bitton and J. Gray. 1988. Disk shadowing. In Proc. 14th Int’l Conf. on Very Large Data Bases - VLDB 1988: 331-338
  * [19] [19] M. Blaum and R. M. Roth. 1999. On lowest density MDS codes. IEEE Trans. Information Theory 45, 1 (Jan 1999), 46-59.
  * [20] [20] M. Blaum, J. Brady, J. Bruck, J. Menon, and A. Vardy. 2002. The EVENODD code and its generalizations. In High Performance Mass Storage and Parallel I/O: Technologies and Applications, H. Jin, T. Cortes, and R. Buyya, editors, Wiley, 2002, 187-208.
  * [21] [21] M. Blaum, J. L. Hafner, and S. Hetzler. 2013. Partial-MDS codes and their application to RAID type of architectures. IEEE Trans. Information Theory 59, 7 (2013), 4510-4519.
  * [22] [22] A. M. Blum, A. Goyal, P. Heidelberger, S. S. Lavenberg, M. K. Nakayama, and P. Shahabuddin. 1994. Modeling and analysis of system dependability using the system availability estimator. In Proc. 24th Symp. on Fault-Tolerant Computing Systems, FTCS 1994, 137-141.
  * [23] [23] J. Bonwick. 2016. Scalable high performance FLASH systems (slides). 32nd Int’l Conf. on Massive Storage Systems and Technology - MSST 2016. https://storageconference.us/2016/Slides/JeffBonwick.pdf
  * [24] [24] D. Borthakur. 2007. The Hadoop distributed file system: Architecture and design. Technical Report Apache Software Foundation 2007.
http://svn.apache.org/repos/asf/hadoop/common/tags/release-0.16.3/docs/hdfs_design.pdf

  * [25] [25] W. G. Bouricius, W. C. Carter, D. C. Jessep, P. R. Schneider, and A. B. Wadia. 1971. Reliability modeling for fault-tolerant computers. IEEE Trans. Computers 20, 11 (1971), 1306-1311.
  * [26] [26] O. J. Boxma and J. W. Cohen. 1991. The M/G/1 queue with permanent customers. IEEE J. Selected Areas in Communications - JSAC 9, 2 (1991), 179-184.
  * [27] [27] E. Brewer. 2016. Spinning disks and their cloudy future. In Proc. 14th USENIX Conf. on File and Storage Technologies - FAST 2016 (presentation).
https://www.usenix.org/sites/default/files/conference/protected-
files/fast16_slides_brewer.pdf.

  * [28] [28] E. Brewer, L. Ying, L. Greenfield, R. Cypher, and T. Ts’o. 2016. Disks for data centers. White paper for FAST 2016.
https://storage.googleapis.com/pub-tools-public-publication-data/pdf/44830.pdf

  * [29] [29] W. Bux and I. Iliadis. 2010. Performance of greedy garbage collection in flash-based solid-state drives. Performance Evaluation 67, 11, (2010), 1172-1186.
  * [30] [30] W. Bux, X.-Y. Hu, I. I. Iliadis, and R. Haas. 2012. Scheduling in flash-based solid-state drives - performance modeling and optimization. In Proc. 20th Int’l Symp. on Modeling, Analysis, and Simulation On Computer and Telecomm. Systems - MASCOTS 2012: 459-468.
  * [31] [31] P. M. Chen, E. K. Lee, G. A. Gibson, R. H. Katz, and D. A. Patterson. 1994. RAID: High-performance, reliable secondary storage. ACM Computing Survey 26, 2 (1994), 145-185.
  * [32] [32] R. Chen and L. Xu. 2020. Practical performance evaluation of space optimal erasure codes for high-speed data storage systems. SN Computer Science 1, 1 (2020), 54.
  * [33] [33] S. Chen and D. F. Towsley. 1993. The design and evaluation of RAID 5 and parity striping disk array architectures. J. Parallel Distributed Computing - JPDC 17, 1-2 (1993), 58-74.
  * [34] [34] S. Chen and D. F. Towsley. 1996. A performance evaluation of RAID architectures. IEEE Trans. Computers 45, 10, (Oct. 1996), 1116-1130.
  * [35] [35] A. Cidon, S. M. Rumble, R. Stutsman, S. Katti, J. K. Ousterhout, and M. Rosenblum. 2013. Copysets: Reducing the frequency of data loss in cloud storage. USENIX Ann’l Tech. Conf. - ATC 2013: 37-48.
  * [36] [36] D. Colarelli and D. Grunwald. 2002. Massive arrays of idle disks for storage archives. In Proc. ACM/IEEE Conf. on Supercomputing - SC’02, 2002, 56.1-56.11.
  * [37] [37] P. Corbett, B. English, A. Goel, T. Grcanac, S. Kleiman, J. Leong, and S. Sankar. 2004. Row-diagonal parity for double disk failure correction. In Proc. 3rd USENIX Conf. on File and Storage Technologies, FAST 2004:, 1-14.
  * [38] [38] W. V. Courtright II, G. Gibson, M. Holland, L. N. Reilly, and J. Zelenka. 1997. RAIDframe: A Rapid Prototyping Tool for RAID Systems. Technical Report CMU-CS-97-142. 1997. https://www.pdl.cmu.edu/PDL-FTP/RAID/CMU-CS-97-142.pdf
  * [39] [39] C. S. Crow IV, D. Goldberg, and W. Whitt. 2007. Two-moment approximations for maxima. Operations Research 55, 3 (May-June 2007), 532-548.
  * [40] [40] H. A. David and H. N. Nagaraja. 2003. Order Statistics, 3rd edition. Wiley 2003.
  * [41] [41] J. Dean and L. A. Barroso. 2013 The tail at scale. Commun. ACM 56, 2 (Feb. 2013), 74-80.
  * [42] [42] P. Desnoyers. 2014. Analytic models of SSD write performance. ACM Trans. Storage 10, 2 (2014), 8:1-8:25.
  * [43] [43] J. Do, V. C. Ferreira, H. Bobarshad, M. Torabzadehkashi et al. 2020. Cost-effective, energy-efficient, and scalable storage computing for large-scale AI applications. ACM Trans. Storage 16, 4, (Oct. 2020), Article 21:1-21:37.
  * [44] [44] P. J. Denning. 1967. Effects of scheduling on file memory operations. In Proc. AFIPS Spring Joint Computing Conf. 1967, 9-21.
  * [45] [45] A. Dholakia, E. Eleftheriou, X.-Y. Hu, I. Iliadis, J. Menon, and K. K. Rao. 2008. A new intra-disk redundancy scheme for high-reliability RAID storage systems in the presence of unrecoverable errors. ACM Trans. Storage 4, 1 (2008), 1:1-1:42.
  * [46] [46] A. G. Dimakis, K. Ramchandran, Y. Wu, and C. Suh. 2011. A survey on network codes for distributed storage. Proceedings IEEE 99, 3 (March 2011), 476-489.
  * [47] [47] B. T. Doshi. 1985. An M/G/1 queue with variable vacations. In Modeling Techniques and Tools for Performance Analysis’85, N. Abu et Ata (editor), North Holland, 67-81.
  * [48] [48] R. Durstenfeld. 1964. Algorithm 235: Random permutation. Commun. ACM, 7, 7 (1964), 420.
  * [49] [49] B. Eckart, X. Chen, X. He, and S. L. Scott. 2008. Failure prediction models for proactive fault tolerance within storage systems. In Proc. 16th IEEE/ACM Int’l Symp. on Modeling, Analysis, and Simulation On Computer and Telecomm. Systems, MASCOTS 2008: 1-8.
  * [50] [50] J. G. Elerath and J. Schindler. 2014. Beyond MTTDL: A closed-form RAID 6 reliability equation. ACM Trans. Storage 10, 2, (March 2014), Article 7.
  * [51] [51] M. Ester, H.-P. Kriegel, J. Sander, and Xiaowei Xu. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proc. Second Int’l Conf. Knowledge Discovery and Data Mining - KDD-96, 226-231.
  * [52] [52] B. Fan, W. Tantisiriroj, L. Xiao, and G. Gibson. 2009. DiskReduce: RAID for data-intensive scalable computing. In Proc. 4th Petascale Data Storage Workshop - PDSW, 2009. https://www.pdl.cmu.edu/PDL-FTP/PDSI/pdsw09-fan.pdf
  * [53] [53] T. Feldman and G. Gibson. 2013. Shingled magnetic recording: Areal density increase Requires new data management. ;login USENIX Magazine 38, 3, 2013, 22-30.
  * [54] [54] A. Fevgas, L. Akritidis, P. Bozanis, and Y. Manolopoulos. 2020. Indexing in flash storage devices: a survey on challenges, current approaches, and future trends. VLDB Journal 29, 1 (2020), 273–311.
  * [55] [55] L. Flatto and S. Hahn. 1984. Two parallel queues created by arrivals with two demands: I. SIAM J. Applied Mathematics 44 (1984), 1041-1053.
  * [56] [56] C. Fleiner, R. B. Garner, J. L. Hafner, K. K. Rao, D. R. Kenchammana-Hosekote, W. W. Wilcke, and J. S. Glider. 2006 Reliability of modular mesh-connected intelligent storage brick systems. IBM J. Research & Development 50, 2-3, (2006), 199-208.
  * [57] [57] D. A. Ford, R. J. T. Morris, and A. E. Bell. 1998. Redundant Arrays of Independent Libraries (RAIL): The StarFish tertiary storage system. Parallel Computing 24, 1 (1998), 45-64.
  * [58] [58] D. Ford, F. Labelle, F. I. Popovici, M. Stokely, V.-A. Truong, L. Barroso, C. Grimes, and S. Quinlan. 2010. Availability in globally distributed storage systems. In Proc. 9th USENIX Symp. on Operating System Design and Implementation, OSDI 2010: 61-74.
  * [59] [59] F. F. Freitas and W. W. Wilcke. 2008. Storage-class memory: The next storage system technology. IBM J. Research and Development 52, 4-5 (2008), 439-448.
  * [60] [60] G. Fu, A. Thomasian, C. Han, and S. W. Ng. 2004. Rebuild strategies for redundant disk arrays. In Proc. NASA/IEEE MSST’04: 12th NASA Goddard, 21st IEEE Conf. on Mass Storage and Technologies, MSST 2004.
  * [61] [61] G. Fu, A. Thomasian, C. Han, and S. W. Ng. 2004. Rebuild strategies for clustered RAID. In Proc. Int’l Symp. on Performance Evaluation of Computer and Telecomm. Systems, SPECTS 2004: 598-607.
  * [62] [62] E. Fujiwara. 2006. Code Design for Dependable Systems Theory and Practical Applications. Wiley-Interscience, 2006.
  * [63] [63] G. R. Ganger, B. L. Worthington, R. U. Hsu, and Y. N. Patt. 1993. Disk subsystem load balancing: Disk striping vs. conventional data placement In Proc. 26th Hawaii Int’l Conf. on System Sciences, Vol. 1, HICSS 1993: 40-49.
  * [64] [64] L. Georgiadis, C. Nikolaou, and A. Thomasian. 2004. A fair workload allocation policy for heterogeneous systems. J. Parallel Distributed Computing - JPDC 64, 4 (2004), 507-519.
  * [65] [65] G. A. Gibson. 1992. Redundant Disk Arrays: Reliable, Parallel Secondary Storage Systems. The MIT Press 1992.
  * [66] [66] G. A. Gibson and D. A. Patterson. 1993. Designing Disk Arrays for High Data Reliability. J. Parallel Distributed Computing - JPDC 17, 1-2 (1993), 4-27.
  * [67] [67] M. Goldszmidt. 2012. Finding soon-to-fail disks in a haystack. In Proc. 4th USENIX Workshop Hot Topics in Storage and File Systems, HotStorage 2012: 1-5.
  * [68] [68] I. J. Goodfellow, J. Pouget-Abadie, M. Mirza et al. 2014. Generative adversarial nets. In Proc. Advances in Neural Information Processing Systems 27: Annual Conf. on Neural Information Processing Systems 2014, 2672–-2680.
  * [69] [69] A. Goyal, P. Shahabuddin, P. Heidelberger, V. F. Nicola, and P. W. Glynn. 1992. A unified framework for simulating Markovian models of highly dependable systems. IEEE Trans. Computers 41, 1 (1992), 36-51.
  * [70] [70] N. K. Goyal and S. Rajkumar (2020): Interconnection Network Reliability Evaluation: Multistage Layouts. Wiley, 2020.
  * [71] [71] W. Grassmann. 1991. Finding transient solutions in Markovian event systems through randomization. In Stewart, W. J., ed., Numerical Solution of Markov Chains. Marcel-Dekker 1991, 357–371.
  * [72] [72] J. Gray, B. Horst, and M. Walker. 1990. Parity striping of disk arrays: Low-cost reliable storage with acceptable throughput. In Proc. 16th Int’l Conf. on Very Large Data Bases, VLDB 1990: 148-161.
  * [73] [73] J. Gray and P. J. Shenoy. 2000. Rules of thumb in data engineering. In Proc. 16th Int’l Conf. on Data Engineering, ICDE 2000: 3-10.
  * [74] [74] J. Gray. Storage bricks (presentations. In Proc. Usenix Conf. on File and Storage Technologies - FAST 2002.
https://www.usenix.org/legacy/publications/library/proceedings/fast02/gray/sld001.htm

  * [75] [75] H. S. Gunawi et al. 2018. Fail-slow at scale: evidence of hardware performance faults in large production systems. ACM Trans. Storage 14, 3 (2018), 23:1-23:26.
  * [76] [76] Z. Guz, H. Li, A. Shayesteh, and V. Balakrishnan. 2018. Performance characterization of NVMe-over-Fabrics storage disaggregation. ACM Trans. Storage 14, 4 (2018), 31:1-31:18/
  * [77] [77] J. L. Hafner, V. Deenadhayalan, T. Kanungo, and K. K. Rao, 2004. Performance metrics for erasure codes in storage systems. IBM Research Report RJ 10321, 2004. https://dominoweb.draco.res.ibm.com/c311e7efd209b90c85256ee8004fb73a.html
  * [78] [78] J. L. Hafner, V. Deenadhayalan, K. K. Rao, and J. A. Tomlin. 2005. Matrix methods for lost data reconstruction in erasure codes. In Proc. 4th USENIX Conf. on File and Storage Technologies - FAST 2005, 183-196.
  * [79] [79] J. L. Hafner, V. Deenadhayalan, W. Belluomini, and K. Rao. 2008. Undetected disk errors in RAID arrays. IBM J. Research and Development 52, 4-5 (July 2008), 413-425.
  * [80] [80] M. Hall. 1986. Combinatorial Theory, Second edition. Wiley-Interscience 1986.
  * [81] [81] R. J. Hall. 2016. Tools for predicting the reliability of large scale storage systems. ACM Trans. on Storage 12, 4 (2016), 24.1-24.30.
  * [82] [82] J. R. Hardin, A. Holder, J. C. Beck, K. Furman, A. Hanna, D. Rader, and C. Rego. 2012. Recommendations for an undergraduate curriculum at the interface of operations research and computer science. INFORMS Trans. on Education 12, 3 (2012), 117-123.
  * [83] [83] S. Hardock, I. Petrov, R. Gottstein, and A. P. Buchmann. 2013. NoFTL: Database systems on FTL-less flash storage. In Proc. VLDB Endow. 6, 12 (2013), 1278-1281.
  * [84] [84] L. Hellerstein, G. A. Gibson, R. M. Karp, R. H. Katz, and D. A. Patterson. 1994. Coding techniques for handling failures in large disk arrays. Algorithmica 12, 2/3 (1994), 182–-208.
  * [85] [85] J. L. Hennessey and D. A. Patterson. 2017. Computer Architecture: A Quantitative Approach, 6th ed. Morgan-Kaufmann Publisher 2017.
  * [86] [86] M. Holland, G. A. Gibson, and D. P. Siewiorek. 1994. Architectures and algorithms for on-line failure recovery in redundant disk arrays. Distributed Parallel Databases 2, 3 (1994), 295-335.
  * [87] [87] H.-I. Hsiao and D. J. DeWitt. 1990. Chained declustering: A new availability strategy for multiprocessor database machines. In Proc. 6th IEEE Int’l Conf. on Data Eng. - ICDE’90, 456-465.
  * [88] [88] W. W. Hsu and A. J. Smith. 2004. The performance impact of I/O optimizations and disk improvements. IBM J. Research & Development 48, 2 (2004), 255-289.
  * [89] [89] W. W. Hsu, A. J. Smith, and H. C. Young. 2005. The automatic improvement of locality in storage systems. ACM Trans. Computer Systems 23, 4 (Nov. 2005), 424-473.
  * [90] [90] Y. Hu, L. Cheng, Q. Yao, P. C. Lee, W. Wang, and W. Chen. 2021. Exploiting combined locality for wide-stripe erasure coding in distributed storage. In Proc. 19th USENIX File and Storage Technologies, FAST 2021: 233-248.
  * [91] [91] C. Huang and L. Xu, 2005. STAR: An efficient coding scheme for correcting triple storage node failures. In Proc. 4th USENIX Conf. on File and Storage Technologies, FAST 2005: 197-210.
  * [92] [92] C. Huang, M. Chen, and J. Li. 2007. Pyramid codes: Flexible schemes to trade space for access efficiency in reliable data storage systems. In Proc. 6th IEEE Int’l Symp. on Network Computing and Applications, NCA 2007: 79-86.
  * [93] [93] C. Huang, H. Simitci, Y. Xu, A. Ogus,B. Calder, P. Gopalan, J. Li, and S. Yekhanin. 2012 Erasure coding in Windows Azure Storage. In Proc. USENIX Ann’l Tech. Conf., ATC 2012: 15-26.
  * [94] [94] C. Huang. 2013. Tutorial on erasure coding for storage applications, Part 2, Tutorial. FAST-2013: 11th USENIX Conf. File and Storage Technologies - FAST 2013.
  * [95] [95] G. Hughes, J. Murray, K. Kreutz-Delagado, and C. Elkan. 2002. Improved disk drive failure warnings. IEEE Trans. on Reliability 51, 3 (2002), 350-357.
  * [96] [96] T. Ibaraki and N. Katoh. 1988. Resource Allocation Problems: Algorithmic Approach. The MIT Press, 1988.
  * [97] [97] IBM Corp. 1997 IBM RAMAC Virtual Array, IBm Redbooks SG24-4951, 1997. www.redbooks.ibm.com.
  * [98] [98] I. Iliadis, R. Haas, X.-Y. Hu, and E. Eleftheriou. 2011, Disk scrubbing versus intradisk Redundancy for RAID storage systems. ACM Trans. Storage 7, 2 (2011), 5:1-5:42.
  * [99] [99] I. Iliadis and V. Venkatesan. 2014. Expected annual fraction of data loss as a metric for data storage reliability. In Proc. 22nd IEEE/ACM Int’l Symp. on Modeling, Analysis, and Simulation On Computer and Telecomm. Systems - MASCOTS 2014: 375–384.
  * [100] [100] I. Iliadis and V. Venkatesan. 2015. Rebuttal to ”Beyond MTTDL: A closed-form RAID-6 reliability equation. ACM Trans. Storage 11, 2 (2015), 9:1-9:10.
  * [101] [101] I. Iliadis and V. Venkatesan. 2015b. Most probable paths to data loss: An efficient method for reliability evaluation of data storage systems. In Proc. 8th Int’l Conf. on Communication Theory, Reliability, Quality of Service, CTRQ 2015: 6-12.
http://personales.upv.es/thinkmind/dl/conferences/ctrq/ctrq_2015/ctrq_2015_1_20_70008.pdf

  * [102] [102] I. Iliadis, Y. Kim, S. Sarafijanovic, and V. Venkatesan. 2016. Performance evaluation of a tape library system. In Proc. 24th IEEE/ACM Int’l Symp. on Modeling, Analysis, and Simulation On Computer and Telecomm. Systems - MASCOTS 2016, 59-68.
  * [103] [103] I. Iliadis, J. Jelitto, Y. Kim, S. Sarafijanovic, and V. Venkatesan. 2017. ExaPlan: Efficient Queueing-Based Data Placement, Provisioning, and Load Balancing for Large Tiered Storage Systems. ACM Trans. on Storage 13, 2 (2017), 17:1-17:41.
  * [104] [103] I. Iliadis. 2019. Data Loss in RAID-5 and RAID-6 storage systems with latent errors Int’l Journal on Advances in Software 12, 3/4, 2019.
http://www.iariajournals.org/software/

  * [105] [105] I. Iliadis, L. Jordan, M. A. Lantz, and S. Sarafijanovic. 2021. Performance evaluation of automated tape library systems. In Proc. 28th IEEE/ACM Int’l Symp. on Modeling, Analysis, and Simulation On Computer and Telecomm. Systems, MASCOTS 2016: 1-8.
  * [106] [106] I. Iliadis. 2022. Effect of lazy rebuild on reliability of erasure coded storage systems. In Proc. CTRQ 2022: 15th Int’l Conf. on Communication Theory. https://www.iaria.org/conferences2022/filesCTRQ22/CTRQ_70005.pdf
  * [107] [107] I. Iliadis. 2023. Reliability evaluation of erasure-coded storage systems with latent errors. ACM Trans. on Storage 19, 1 (2023), 4:1-4:47.
  * [108] [108] B. L. Jacob, S. W. Ng, and D. T. Wang. 2008. Memory Systems: Cache, DRAM, Disk. Morgan Kaufmann Publishers, 2008.
  * [109] [109] D. M. Jacobson and J. Wilkes. 1991. Disk scheduling algorithms based on rotational position Tech. Report HPL–CSP–91–7rev. March 1991.
https://pages.cs.wisc.edu/~remzi/Classes/838/Fall2001/Papers/hp-sched.pdf

  * [110] [110] S. Jaffer, K. Mahdaviani, and B. Schroeder. 2022. Improving the Endurance of Next Generation SSD’s using WOM-v Codes. ACM Trans. Storage 18, 4 (2022), 29:1-29:32.
  * [111] [111] W. Jiang, C. Hu, Y. Zhou, and A. Kanevsky. 2008. Are disks the dominant contributor for storage failures? A comprehensive study of storage subsystem failure characteristics. ACM Trans. on Storage 4, 3 (2008), 7:1-7:25.
  * [112] [112] T. Jiang, P. Huang, and K. Zhou. 2019. Scrub unleveling: Achieving high data reliability at low scrubbing cost. In Proc. 2019 Design, Automation & Test in Europe Conf. & Exhibition, DATE 2019, 1403-1408.
  * [113] [113] A. M. Johnson Jr. and M. Malek. 1988. Survey of software tools for evaluating reliability, availability, and serviceability. ACM Computing Surveys 20, 4 (1988), 227-269.
  * [114] [114] N. L. Johnson, S. Kotz, and N. Balakrishnan. 1995. Continuous Univariate Distributions, Vol. 2. 2nd Ed. Wiley Series in Probability and Statistics 1995.
  * [115] [115] S. Kadekodi, F. Maturana, S. Athlur, A. Merchant, K. V. Rashmi, and G. R. Ganger. 2022. Tiger: Disk-adaptive redundancy Without placement restrictions. In Proc. 16th USENIX Symp. Operating Systems Design and Implementation- OSDI 2022, 413-429.
  * [116] [116] S. Kadekodi, S. Silas, D. Clausen, and A. Merchant. 2023. Practical design considerations for wide Locally Recoverable Codes - LRCs. In Proc. 21st USENIX Conf. on File and Storage Technologies - FAST 23, 1-16.
  * [117] [117] H.-W. Kao, J.-F. Paris, T. J. E. Schwarz, and D. D. E. Long, 2013. A flexible simulation tool for estimating data loss risks in storage arrays. In Proc. 29th Symp. on Mass Storage Systems Technology, MSST 2013: 1-5.
  * [118] [118] P. Karlsson. 2006. Solaris 10 Features In-depth: Containers and ZFS. http://uk.sun.com/sunnews/events/2006/mar/javauk06/presentations/Peter_Karlsson_Containers_ZFS.pdf
  * [119] [119] D. R. Kenchammana-Hosekote, D. He, and J. L. Hafner. 2007. REO: A generic RAID Engine and Optimizer. In Proc. 5th USENIX Conf. on File and Storage Technologies, FAST 2007: 261-276
  * [120] [120] J. Kim, M. Kim, M. D. Tehseen, J. Oh, and Y. Won, 2022. IPLFS: Log-structured file system without garbage collection. In Proc. USENIX Ann’l Tech. Conf. - ATC 2022: 739-754
  * [121] [121] T. Kim, J. Jeon, N. Arora et al. 2023. RAIZN: Redundant Array of Independent Zoned Namespaces. In Proc. 28th ACM Int’l Conf. on Architectural Support for Programming Languages and Operating Systems ASPLOS (Vol. 2) 2023: 660–673.
  * [122] [122] L. Kleinrock. 1975. Queueing Systems, Vol. I: Theory. Wiley-Interscience 1975.
  * [123] [123] L. Kleinrock. 1976. Queueing Systems, Vol. II: Applications. Wiley-Interscience 1976.
  * [124] [124] O. Kolosov, G. Yadgar, M. Liram, I. Tamo, and A. Barg. 2018. On fault tolerance, locality, and optimality in locally repairable codes. In Proc. USENIX Annual Technical Conference - ATC 2018, 2018, 865-877.
  * [125] [125] S. Kotz and S. Nadarajah. 2000. Extreme Value Distributions: Theory and Applications. Imperial College Press, London 2000.
  * [126] [126] T Lahiri, M.-A. Neimat, and S. Folkman. 2013. Oracle TimesTen: An in-memory database for enterprise applications. IEEE Data Eng. Bull. 36(2): 6-13 (2013)
  * [127] [127] S. S. Lavenberg, ed. 1983. Computer Performance Modeling Handbook. Academic Press 1983.
  * [128] [128] J. F. Lawless. 2003. Statistical Models and Methods for Lifetime Data, 2nd ed. Wiley, 2003.
  * [129] [129] E. D. Lazowska, J. Zahorjan, G. S. Graham, K. C. Sevcik: Quantitative System Performance: Computer System Analysis Using Queueing Network Models Prentice-Hall 1984.

  * [130] [130] H. Li, M. L. Putra, R. Shi et al. 2023 Extending and programming the NVMe I/O determinism interface for Flash Arrays. ACM Trans. on Storage 19, 1 (2023), 5:1-5:33.
  * [131] [131] M. Li, J. Shu, and W. Zheng. 2009. GRID codes: Strip-based erasure codes with high fault tolerance for storage systems. ACM Trans. Storage 4, 4 (2009), 15:1-15:22.
  * [132] [132] M. Li and J. Shu. 2010. Preventing silent data corruptions from propagating during data reconstruction. IEEE Trans. Computers 59, 12 (2010), 1611-1624.
  * [133] [133] S. Lin, C. Zhang, D. Wang, and J. Liu. 2009. Reliability analysis for Full-2 Code. In Proc. 10th Int’l Symp. Pervasive Systems, Algorithms, and Networks: 2009, 454-459.
  * [134] [134] R. Lu, E. Xu, Y. Zhang, F. Zhu, Z. Zhu, M. Wang, Z. Zhu, G. Xue, J. Shu, M. Li, and J. Wu. 2023. Perseus: A fail-slow detection framework for cloud storage systems. In Proc. 21st USENIX Conf. File and Storage Technologies - FAST 2023: 49-64.
  * [135] [135] C. R. Lumb, J. Schindler, G. R. Ganger, D. Nagle, E. Riedel. 2000. Towards higher disk head utilization: Extracting ”free” bandwidth from busy disk drives. In Proc. 4th Symposium on Operating System Design and Implementation - OSDI 2000): 87-102.
  * [136] [136] C. R.Lumb and R. Golding. 2004. D-SPTF: Decentralized request distribution in brick-based storage systems. In Proc. 11th Int’l Conf. on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2004: 37–47.
  * [137] [137] A. Ma, R. Traylor, F. Douglis, M. Chamness, G. Lu, D. Sawyer, S. Chandra, and W. Hsu. 2015 RAIDShield: Characterizing, monitoring, and proactively protecting against disk failures. ACM Trans. Storage 11, 4 (2015), 17.1-17.28.
  * [138] [138] F. Mahdisoltani, I. A. Stefanovici, and B. Schroeder. 2017. Proactive error prediction to improve storage system reliability. In Proc. USENIX Ann’l Technical Conf. ATC 2017, 391-402
  * [139] [139] C. Maltzahn, E. Molina-Estolano, A. Khurana, A. J. Nelson, S. A. Brandt, and S. Weil. 2010. Ceph as a scalable alternative to the Hadoop Distributed File System. ;login USENIX Magazine, 35 (4), 2010, 38-49.
  * [140] [140] S. Maneas, K. Mahdaviani, T. Emami, and B. Schroeder. 2021. Reliability of SSDs in enterprise storage Systems: A large-scale field study. ACM Trans. Storage 17, 1 (2021), 3:1-3:27.
  * [141] [141] F. P. Mathur and A. Avizienis. 1970. Reliability analysis and architecture of a hybrid-redundant digital system: Generalized triple modular redundancy with self-repair. In Proc. AFIPS Spring Joint Computing Conf. 1970, 375-383.
  * [142] [142] B. McNutt. 1994. Background data movement in a log-structured disk subsystem. IBM J. Research & Development 38, 1 (1994), 47-58.
  * [143] [143] B. McNutt. 2002. The Fractal Structure of Data Reference - Applications to the Memory Hierarchy. Advances in Database Systems 22, Kluwer 2002.
  * [144] [144] P. J. Meaney, L. A. Lastras-Montano, V. K. Papazova et al. 2012. IBM zEnterprise redundant array of independent memory subsystem. IBM J. Research and Development 56, 1 (2012), 4:1-4:12.
  * [145] [145] J. Menon and J. Cortney. 1993. The architecture of a fault-tolerant cached RAID controller. In Proc. 20th Ann’l Int’l Symp on Computer Architecture, ISCA 1993: 76-86.
  * [146] [146] J. Menon. 1994 Performance of RAID5 disk arrays with read and write caching. Distributed Parallel Databases 2, 3 (1994), 261-293.
  * [147] [147] J. Menon. 1995. A performance comparison of RAID-5 and log-structured arrays. In Proc. 4th Int’l Symp. on High Performance Distributed Computing, HPDC 1995: 167-178
  * [148] [148] J. Menon and L. J. Stockmeyer. 1998. An age threshold algorithm for garbage collection in log-structured arrays and file systems. IBM Research Report RJ 10120, Almaden Research Center, May 1998. Abridged version in High Performance Computing Systems and Applications, J. Schaefer, ed. Kluwer academic Pub., 119-132<EMAIL_ADDRESS>  * [149] [149] A. Merchant and P. S. Yu. 1996. Analytic modeling of clustered RAID with mapping based on nearly random permutation. IEEE Trans. Computers 45, 3 (1996), 367-373.
  * [150] [150] R. Micheloni, L. Crippa, and A. Marelli. 2010. Inside Flash NAND Memories. Springer 2010.
  * [151] [151] S. M. A. Mohamed and Y. Wang. 2021. A survey on novel classification of deduplication storage systems. Distributed and Parallel Databases 39, 101 (March 2021), 201–230.
  * [152] [152] R. R. Muntz and J. C. S. Lui. 1990. Performance analysis of disk arrays under failure. In Proc 16th Int’l Conf. on Very Large Data Bases - VLDB 1990, 162-173.
  * [153] [153] J. Murray, G. Hughes, and K. Kreutz-Delgado. 2005. Machine learning methods for predicting failures in hard drives: a multiple-instance application. The Journal of Machine Learning Research 6, 783–816.
  * [154] [154] R. D. Nelson and A. N. Tantawi. 1988. Approximate Analysis of Fork/Join Synchronization in Parallel Queues. IEEE Trans. Computers 37, 6, (1988), 739-743.
  * [155] [155] L. A. Newberg and D. Wolf. 1994. String layouts for a redundant array of inexpensive disks. Algorithmica 12, 2/3 (1994), 209-224.
  * [156] [156] S. W. Ng and R. L. Mattson. 1994. Uniform parity group distribution in disk arrays with multiple failures. IEEE Trans. Computers 43, 4 (1994), 501-506.
  * [157] [157] S. W. Ng. 1994. Crosshatch disk array for improved reliability and performance. In Proc. 21st Int’l Symp. on Computer Architecture - ISCA CA 1994, 255-264.
  * [158] [158] Y. W. Ng and A. Avizienis. 1980. A Unified Reliability Model for Fault-Tolerant Computers. IEEE Trans. Computers 29, 11 (1980), 1002-1011.
  * [159] [159] V. F. Nicola, M. K. Nakayama, P. Heidelberger, and A. Goyal. 1993. Fast simulation of highly dependable systems with general failure and repair processes. IEEE Trans. Computers 42, 12 (1993), 1440-1452.
  * [160] [160] V. F. Nicola, P. Shahabuddin, and M. K. Nakayama. 2001. Techniques for fast simulation of models of highly dependable systems. IEEE Trans. Reliability 50, 3 (2001), 246-264.
  * [161] [161] E. J. O’Neil, P. E. O’Neil, and G. Weikum. 1993. The LRU-K Page Replacement Algorithm For Database Disk Buffering. In Proc. ACM SIGMOD 1993 Int’l Conf. on Management of Data: 297-306
  * [162] [162] J. K. Ousterhout, A. Gopalan, A. Gupta et al. 2015. The RAMCloud storage system. ACM Trans. Computer Systems 33, 3, (2015), 7:1-7:55.
  * [163] [163] M. Ovsiannikov, S. Rus, D. Reeves, P. Sutter, S. Rao, and J. Kelly. 2013. The Quantcast file System. Proc. VLDB Endowment 6, 11 (2013), 1092-1101.
  * [164] [164] L. P. Kaelbling, M. L. Littman, and A. W. Moore. 1996. Reinforcement learning: a survey. J. Artificial Intelligence Research 4 (1996), 237–285.
  * [165] [165] B. Panda, D. Srinivasan, H. Ke, K. Gupta, V. Khot, and H. S. Gunawi. 2019. IASO: A fail-slow detection and mitigation framework for distributed storage services. In Proc. USENIX Ann’l Technical Conf. - ATC 2019: 47-6.2
  * [166] [166] L. Pang, A. Alazzawe, M. Ray, K. Kant, and J. Swift. 2023. Adaptive intelligent tiering for modern storage systems. Performance Evaluation 160 (2023), 102332.
  * [167] [167] J. F. Paris and T. J. Schwarz. 2021. Three dimensional RAID arrays with fast repairs. In Proc. Int’l Conf. on Electrical, Computer and Energy Technologies, ICECET 2021, 7 pages.
https://www2.cs.uh.edu/~paris/MYPAPERS/Icecet21.pdf

  * [168] [168] C.-I. Park. 1995. Efficient placement of parity and data to tolerate two disk failures in disk array systems. IEEE Trans. Parallel and Distributed Systems 6, 11 (Nov. 1995), 1177-1184.
  * [169] [169] D. A. Patterson, G. A. Gibson, and R. H. Katz. 1988. A case for Redundant Arrays of Inexpensive Disks (RAID). In Proc. ACM SIGMOD Int’l Conf. on Management of Data, SIGMOD 1988, 109-116.
  * [170] [170] D. A. Patterson and J. Hennessey. 2017. Computer Organization and Design. MKP 2017
  * [171] [171] J. Paulo and J. Pereira. 2014. A survey and classification of storage deduplication systems. ACM Computing Surveys 47, 1 (2014), 11.1-11:30.
  * [172] [172] H.-O. Peitgen, H. Jürgens, and D. Saupe. 2004. Chaos and Fractals: New Frontiers of Science 2nd Ed., Springer 2004.
  * [173] [173] G. Pekhimenko, V. Seshadri, Y. Kim, H. Xin, O. Mutlu, P. B. Gibbons, M. A. Kozuch, T. C. Mowry. 2013. Linearly compressed pages: a low-complexity, low-latency main memory compression framework. In Proc. 46th Annual IEEE/ACM Int’l Symp. on Microarchitecture, MICRO 2013: 172-184
  * [174] [174] W. F. Piepmeier. 1975. Optimal balancing of I/O requests to disks. Commun. ACM 18, 9 (Sept. 1975), 524-527.
  * [175] [175] E. Pinheiro, W.-D. Weber, and L. A. Barroso. 2007. Failure trends in a large disk drive population. In Proc. 5th USENIX Conf. on File and Storage Technologies - FAST 2007, 17-28.
  * [176] [176] J. S. Plank. 1997. A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems. Software Practice & Experience 27, 9, (1997), 995-1012.
  * [177] [177] J. S. Plank. 2005. Erasure codes for storage applications, Tutorial, 4th Usenix Conf. File and Storage Technologies, FAST 2005.
  * [178] [178] J. S. Plank and Y. Ding. 2005. Note: Correction to the 1997 tutorial on Reed-Solomon coding. Software Practice & Experience 35, 2 (2005), 189-194.
  * [179] [179] J. S. Plank. 2013. Tutorial on erasure coding for storage applications, Part 1, Tutorial. 11th Usenix Conf. File and Storage Technologies, FAST 2013.
  * [180] [180] J. S. Plank and M. Blaum. 2014. Sector-Disk (SD) erasure codes for mixed failure modes in RAID systems. ACM Trans. Storage 10, 1 (2014), 4:1-4:17.
  * [181] [181] V. Prabhakaran, L. N. Bairavasundaram, N. Agrawal, H. S. Gunawi, A. C. and R. H. Arpaci-Dusseau. 2005. IRON file systems. In Proc. 20th ACM Symp. on Operating Systems Principles, SOSP 2005: 206-220.
  * [182] [182] A. Rafii. 1976 Study of the performance of RPS. ACM SIGMETRICS Perform. Evaluation Rev. 5(4): 21-38 (1976)
  * [183] [183] K. K. Ramakrishnan, P. Biswas, and R. Karedla. 1992. Analysis of file I/O traces in commercial computing environments. In Proc. ACM SIGMETRICS’92/Performance’92 Joint Conf. 1992: 78-90.
  * [184] [184] R. Ramakrishnan and J. Gehrke. 2002. Database Management Systems, 3rd edition. McGraw-Hill, 2002.
  * [185] [185] K. K. Rao, J. L. Hafner, and R. A. Golding. 2011. Reliability for networked storage nodes. IEEE Trans. Dependable and Secure Computing 8, 3 (2011), 404-418.
  * [186] [186] K. V. Rashmi, N. B. Shah, D. Gu, H. Kuang, D. Borthakur, and K. Ramchandran. 2013. A solution to the network challenges of data recovery in erasure-coded distributed storage systems: A study on the Facebook warehouse cluster. In Proc. 5th USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage 2013: 1–-5.
  * [187] [187] A. L. N. Reddy, J. A. Chandy, and P. Banerjee. 1993. Design and evaluation of gracefully degradable disk arrays. J. Parallel Distributed Computing - JPDC 17, 1-2 (1993), 28-40.
  * [188] [188] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi. 2016. You only look once: Unified, real-time object detection. In Proc. IEEE Conf. on Computer Vision and Pattern Recognition, CVPR 2016: 779–788.
  * [189] [189] J. Resch and I. Volvivski. 2013. Reliability models for highly fault-tolerant storage systems. arxiv.org/abs/1310.4702
  * [190] [190] E. Riedel, G. A. Gibson, and C. Faloutsos. 1998. Active storage for large-scale data mining and multimedia. In Proc. 24rd Int’l Conf. on Very Large Data Bases, VLDB 1998: 62-73
  * [191] [191] E. Riedel, C. Faloutsos, G. R. Ganger, and D. Nagle. 2000. Data Mining on an OLTP system (nearly) for free. In Proc. Conf. on Management of Data, SIGMOD 2000: 13-21
  * [192] [192] C. Ruemmler and J. Wilkes. 1993. A trace-driven analysis of disk working set sizes Operating Systems Research Dept. HP Labs, Palo Alto, CAHPL–OSR–93–23, 1993. https://john.e-wilkes.com/papers/HPL-OSR-93-23.pdf
  * [193] [193] A. Riska and E. Riedel. 2003. It’s not fair - Evaluating efficient disk scheduling. In Proc. 11th Int’l Workshop on Modeling, Analysis and Simulation of Computer and Telecomm. Systems - MASCOTS 2003: 288-295.
  * [194] [194] R. Rojas-Cessa. 2017. Interconnections for Computer Communications and Packet Networks. CRC Press, 2017.
  * [195] [195] M. Rosenblum and J. K. Ousterhout, 1992. The design and implementation of a log-structured file system. ACM Trans. on Computing Systems, 10, 1 (1992), 26-52.
  * [196] [196] R. A. Sahner, K. S. Trivedi, and A. Puliafito. 1996. Performance and Reliability Analysis of Computer Systems: An Example-Based Approach Using the SHARPE Software Package, Kluwer 1996.
  * [197] [197] F. G. Sanchez. 2007. Modeling of Field and Thermal Magnetization Reversal in Nanostructured Magnetic Materials. PhD thesis, Autonomous Univ. of Madrid 2007.
http://www.fgarciasanchez.es/thesisfelipe.pdf

  * [198] [198] M. Sathiamoorthy, M. Asteris, D. S. Papailiopoulos, A. G. Dimakis, R. Vadali, S. Chen, and D. Borthakur. 2013. XORing elephants: Novel erasure codes for big data. In Proc. VLDB Endow. 6, 5 (2103), 325-336.
  * [199] [199] K. Sayood. 2017. Introduction to Data Compression, 5th edition. MKP Publishers, 2017.
  * [200] [200] J. Schindler, S. Shete, and K. A. Smith. 2011: Improving throughput for small disk requests with proximal I/O. IN Proc. File and Storage Technologies, FAST 2011: 133-147.
  * [201] [201] B. Schroeder and G. A. Gibson. 2007. Understanding disk failure rates: What does an MTTF of 1,000,000 hours mean to you? ACM Trans. on Storage 3, 3 (2007), 8:1-8:31.
  * [202] [202] B. Schroeder, E. Pinheiro, and W.-D. Weber. 2009 DRAM errors in the wild: a large-scale field study. Commun. ACM 54, 2 (Feb. 2011), 100-107.
  * [203] [203] B. Schroeder, S. Damouras, and P. Gill. 2010. Understanding latent sector errors and how to protect against them. ACM Trans. on Storage 6, 3 (2010), 9:1-9:23.
  * [204] [204] B. Schroeder, A. Merchant, and R. Lagisetty. 2017. Reliability of NAND-Based SSDs: What field studies tell us. Proceedings IEEE 105, 9 (Sept. 2017), 1751-1769.
  * [205] [205] G. Schulz. Resilient Storage Networks. Designing Flexible Scalable DataInfrastructures. Elsevier Digital Press 2004,
  * [206] [206] T. J. E. Schwarz and W. A. Burkhard. 1996. Almost Complete Address Translation (ACATS) disk array declustering, In Proc. 8th IEEE Symp. on Parallel and Distributed Processing - SPDP 1996: 324-331.
  * [207] [207] T. J. E. Schwarz, J. Steinberg, and W. A. Burkhard. 1999. Permutation Development Data Layout - PDDL disk array declustering. In Proc 5th IEEE Symp. on High Performance Computer Architecture - HPCA’99, pp. 214-217.
  * [208] [208] T. J. E. Schwarz, A. Amer, T. M. Kroeger, E. L. Miller, D. D. E. Long, J.-F. Pâris. 2016. RESAR: Reliable Storage at Exabyte Scale. In Proc. 24th IEEE/ACM Int’l Symp. on Modeling, Analysis, and Simulation On Computer and Telecomm. Systems, \- MASCOTS 2016: 211-220.
  * [209] [200] SEFI - European Soc. Eng. Education. 2013. A framework for mathematics curricula in engineering education: A report of the mathematics working group.2013.
http://sefibenvwh.cluster023.hosting.ovh.net/wp-
content/uploads/2017/07/Competency-based-curriculum-incl-ads.pdf

  * [210] [210] R. D. Sloan. 1992. A practical implementation of the data base machine - Teradata DB/1012. In Proc. 25th Hawaii Int’l Conf. on Systems Science, Vol. 1: 320-327.
  * [211] [211] A. J. Smith. 1981. Long term file migration: Development and evaluation of algorithms. Commun. ACM 24, 8 (Aug, 1981), 521-532.
  * [212] [212] A. J. Smith. 1985. Disk cache-miss ratio analysis and design considerations. ACM Trans. Computer Systems 3(3): 161-203 (1985).
  * [213] [213] W. J. Stewart. 2021. Introduction to the Numerical Solution of Markov Chains. Princeton University Press, 2021.
  * [214] [214] R. Sundaram. 2006. The Private Lives of Disk Drives, Tech OnTap, NetApp, Inc. 2006, http://www.netapp.com/go/techontap/matl/sample/0206tot_resiliency.htm
  * [215] [215] H. Takagi. 1986. Analysis of Polling Systems., MIT Press, 1986.
  * [216] [216] H. Takagi. 1991. Queueing Analysis: A Foundation of Performance Evaluation : Vacation and Priority Systems, North Holland 1991.
  * [217] [217] Tandem Database Group. 1987. NonStop SQL: A distributed, high-performance, high-availability implementation of SQL In High Performance Transaction Systems. D. Gawlick et al. (eds), Springer 1987. https://www.hpl.hp.com/techreports/tandem/TR-87.4.pdf
  * [218] [218] A. J. Thadhani. 1981. Interactive user productivity. IBM Systems Journal, 20, 4 (1981), 407-423.
  * [219] [219] A. Thomasian and P. F. Bay. 1986. Analytic Queueing Network Models for Parallel Processing of Task Systems. IEEE Trans. Computers 35, 12 (Dec. 1986), 1045-1054.
  * [220] [220] A. Thomasian and J. Menon. 1994. Performance analysis of RAID5 disk arrays with a vacationing server model for rebuild mode operation. In Proc. 10th Int’l Conf. on Data Engineering, ICDE 1994, 111-119.
  * [221] [221] A. Thomasian and A. N. Tantawi. 1994. Approximate solutions for M/G/1 fork/join synchronization. In Proc. 26th Conf. on Winter Simulation, WSC 1994, 361-368
  * [222] [222] A. Thomasian: Rebuild options in RAID5 disk arrays. In Proc. 7th IEEE Symp. on Parallel and Distributed Processing, SPDP 1995: 511-518.
  * [223] [223] A. Thomasian and J. Menon. 1997. RAID5 Performance with distributed sparing. IEEE Trans. Parallel Distributed Systems 8, 6 (June 1997), 640-657.
  * [224] [224] A. Thomasian and C. Liu. 2002, Some new disk scheduling policies and their performance. In Proc. ACM SIGMETRICS Conf. on Measurement and Modeling of Computer Systems 2002: 266-267
  * [225] [225] A. Thomasian. 2005. Reconstruct versus Read-Modify Writes in RAID. Information Processing Letters - IPL 93, 4 (2005), 163-168.
  * [226] [226] A. Thomasian, B. A. Branzoi, and C. Han. 2005 Performance evaluation of a heterogeneous disk array architecture. In Proc. 13th Int’l Symp. on Modeling, Analysis, and Simulation of Computer and Telecomm. Systems, MASCOTS 2005: 517-520
  * [227] [227] A. Thomasian and C. Han. 2005. Heterogeneous disk array architecture and its data allocation policies. In Proc. Int’l Symp. on Performance Evaluation of Computer and Telecommunication Systems, SPECTS 2005, 617-624.
  * [228] [228] A. Thomasian. 2005b. Clustered RAID arrays and their access costs. Comput. J. 48, 6 (2005), 702-713.
  * [229] [229] A. Thomasian and G. Fu. 2006. Anticipatory disk arm placement to reduce seek time. Computer Systems: Science &. Engineering 21, 3 (May 2006), 173-182.
  * [230] [230] A. Thomasian. 2006a. Multi-level RAID for very large disk arrays. ACM SIGMETRICS Perform. Evaluation Review, 33, 4 (2006), 17-22.
  * [231] [231] A. Thomasian. 2006. Shortcut method for reliability comparisons in RAID. J. Systems & Software 79, 11 (2006), 1599-1605.
  * [232] [232] A. Thomasian and M. Blaum. 2006. Mirrored disk organization reliability analysis. IEEE Trans. Computers 55, 12 (2006), 1640-1644.
  * [233] [233] A. Thomasian, G. Fu, and C. Han. 2007. Performance of two-disk failure-tolerant disk arrays. IEEE Trans. Computers 56, 6 (2007), 799-814.
  * [234] [234] A. Thomasian and J. Xu. 2008. Reliability and performance of mirrored disk organizations. Computer Journal 51, 6 (2008), 615-629.
  * [235] [235] A. Thomasian and M. Blaum. 2009. Higher reliability redundant disk arrays: Organization, operation, and coding. ACM Trans. Storage 5, 3 (2009), 7:1-7:59.
  * [236] [236] A. Thomasian. 2011. Survey and analysis of disk scheduling methods. ACM SIGARCH Computer Architecture News 39, 2 (2011), 8-25.
  * [237] [237] A. Thomasian and J. Xu. 2011. X-code double parity array operation with two disk failures. Information Processing Letters 111, 12 (2011), 568-574.
  * [238] [238] A. Thomasian and J. Xu. 2011b. Data Allocation in Heterogeneous Disk Arrays. In Proc. 6th Int’l Conf. on Networking, Architecture, and Storage, NAS 2011: 82-91.
  * [239] [239] A. Thomasian and Y. Tang. 2012. Performance, reliability, and performability of a hybrid RAID array and a comparison with traditional RAID1 arrays. Cluster Computing 15, 3 (2012), 239-253.
  * [240] [240] A. Thomasian, Y. Tang, and Y. Hu. 2012. Hierarchical RAID: Design, performance, reliability, and recovery. J. Parallel Distributed Computing - JPDC 72, 12 (2012), 1753-1769.
  * [241] [241] A. Thomasian. 2014. Analysis of fork/join and related queueing systems. ACM Computing Surveys 47, 2 (2014), 17:1-17:71.
  * [242] [242] A. Thomasian. 2014. Performance Evaluation of Computer Systems. Computing Handbook, 3rd ed. (Vol. 1) 2014: Chapter 56: 1-50.
  * [243] [243] A. Thomasian. 2018. Mirrored and hybrid disk arrays: Organization, scheduling, reliability, and performance. CoRR abs/1801.08873 (2018). https://arxiv.org/pdf/1801.08873.pdf
  * [244] [244] A. Thomasian. 2018. Vacationing server model for M/G/1 Queues for rebuild processing in RAID5 and threshold scheduling for readers and writers. Information Processing Letters - IPL 135 (20018), 41-46.
  * [245] [245] A. Thomasian. 2021. Storage Systems: Organization, Performance, Coding, Reliability, and Their Data Processing, Elsevier 2021.
https://www.sciencedirect.com/book/9780323907965/storage-systems

  * [246] [246] E. Thorp. 1973. Nonrandom shuffling with applications to the game of Faro. J. American Statistical Association - JASA, 68, 344 (Dec. 1973), 842-847.
  * [247] [247] K. Treiber and J. Menon. 1995. Simulation study of cached RAID5 designs. In Proc. 1st IEEE Symp. on High-Performance Computer Architecture - HPCA 1995, 186-197.
  * [248] [248] R. B. Tremaine, P. A. Franaszek, J. T. Robinson et al. 2001. IBM Memory Expansion Technology (MXT). IBM J. Research & Development 45, 2 (2001), 271-286.
  * [249] [249] K. S. Trivedi. 2001. Probabilistic and Statistics with Reliability, Queueing and Computer Science Applications, 2nd ed. Wiley 2001.
  * [250] [250] K. S. Trivedi and A. Bobbio. 2017. Reliability and Availability Engineering: Modeling, Analysis, and Applications. Cambridge Univ. Press 2017.
  * [251] [251] E. Varki, A. Merchant, J. Xu, and X. Qiu. 2004. Issues and challenges in the performance analysis of real disk arrays. IEEE Trans. Parallel Distributed Systems 15, 6 (2004), 559-574.
  * [252] [252] Y. Wang, X. Dong, L. Wang, W. Chen, and X. Zhang. 2022 Optimizing small-sample disk fault detection based on LSTM-GAN model, ACM Trans. Architecture and Code Optimization, 19, 1 (Jan. 2022), Article 13.
  * [253] [253] W. W. Wilcke, R. B. Garner, C. Fleiner et al. 2006. IBM Intelligent Bricks Project - Petabytes and Beyond. IBM J. Research and Development 50, 2-3 (2006), 181-198.
  * [254] [254] A. Wildani, T. J. E. Schwarz, E. L. Miller, and D. D. E. Long. 2009. Protecting against rare event failures in archival systems. In Proc. 17th IEEE/ACM Int’l Symp. on Modeling, Analysis, and Simulation On Computer and Telecomm. Systems - MASCOTS 2009: 1-11
  * [255] [255] J. Wilkes. 1995. The Pantheon storage-system simulator. Technical Report HPL-SSP-95-14, Storage Systems Program, Hewlett-Packard Laboratories (1996). https://john.e-wilkes.com/papers/PantheonOverview.pdf
  * [256] [256] J. Wilkes, R. A. Golding, C. Staelin, and T. Sullivan. 1996. The HP AutoRAID hierarchical storage system. ACM Trans. Computer Systems 14, 1 (1996), 108-136.
  * [257] [257] A. Wilner. 2001. Multiple drive failure tolerant RAID system. US Patent 6,327,672, Dec. 2001
  * [258] [258] B. L. Worthington, G. R. Ganger, and Y. N. Patt. 1994 Scheduling algorithms for modern disk drives. In Proc. ACM Conf. on Measurement and Modeling of Computer Systems, SIGMETRICS 1994: 241-252
  * [259] [259] M. Xia, M. Saxena, M. Blaum, and D. Pease. 2015. A tale of two erasure codes in HDFS. In Proc. 13th USENIX Conf. on File and Storage Technologies - FAST 2015, 213-226.
  * [260] [260] Q. Xin, E. L. Miller, T. J. E. Schwarz, D. D. E. Long, S. A. Brandt, and W. Litwin. 2003. Reliability mechanisms for very large storage systems. In Proc. IEEE Symp.on Mass Storage Systems, MSST 2003: 146-156
  * [261] [261] L. Xiang, Y. Xu, J. C. S. Lui, and Q. Chang. 2010. Optimal recovery of single disk failure in RDP code storage systems. In Proc. ACM SIGMETRICS Conf. on Measurement and Modeling of Computer Systems 2010, 119-130.
  * [262] [262] L. Xiang, Y. Xu, J. C. S. Lui, Q. Chang, Y. Pan, and R. Li. 2011. A hybrid approach to failed disk recovery using RAID-6 Codes: Algorithms and performance evaluation. ACM Trans. Storage 7, 3 (2011), 11:1-11:34.
  * [263] [263] L. Xu and J. Bruck. 1999. X-Code: MDS Array codes with optimal encoding: IEEE Trans. Information Theory 45, 1 (Jan. 1999), 272-276.
  * [264] [264] S. Xu, R. Li, P. P. C. Lee, Y. Zhu, L. Xiang, Y. Xu, and J. C. S. Lui. 2014. Single disk failure recovery for X-code-based parallel storage systems. IEEE Trans. Computers 63, 4 (April 2014), 995-1007.
  * [265] [265] E. Yaakobi, S. Kayser, P. H. Siegel, A. Vardy, and J. K. Wolf. 2012. Codes for Write-Once Memories IEEE Trans. Information Theory, 58, 9 (Sept. 2012), 5885-5999.
  * [266] [266] J. Yang, Z. Qiu, Y. Zhang, Y. Yue, and K. V. Rashmi. 2023. FIFO can be better than LRU: The power of lazy promotion and quick demotion. In Proc. 19th Workshop on Hot Topics in Operating Systems, HOTOS 23: 70-79.
  * [267] [267] K. Yu. 2012. Optimizing OLTP Oracle database performance using Dell Express Flash PCIe SSDs. White Paper, Dell Global Solutions Engineering, 2012.
https://downloads.dell.com/solutions/enterprise-solution-
resources/PCIe_SSD_for_oracle_database_performance.pdf

  * [268] [268] J. Zhang, Y. Wang; Y. Wang, K. Zhou, S. Sebastian, P. Huang, B. Cheng, and Y. Ji. 2022. Tier-scrubbing: An adaptive and tiered disk scrubbing scheme with improved MTTDL and reduced cost. In Proc. 57th ACM/IEEE Design Automation Conf. - DAC 2020: 1-6.
  * [269] [269] M. Zhang, S. Han, and P. P. C. Lee. 2019. SIMedc: A simulator for the reliability analysis of erasure-coded data centers. IEEE Trans. Parallel Distributed Systems 30, 12 (Dec. 2019), 2836–2848.
  * [270] [270] Y. Zhang, W. Hao, B. Niu, K. Liu, S. Wang, N. Liu, X. He, Y. Gwon, and C. Koh. 2023. Multi-view feature-based SSD failure prediction: What, when, and why. In Proc. 21st USENIX Conf. on File and Storage Technologies - FAST 2023: 409-424.
  * [271] [271] P. Zhou, V. Pandey, J. Sundaresan, A. Raghuraman, Y. Zhou, and S. Kumar. 2004. Dynamic tracking of page miss ratio curve for memory management. In Proc. 11th Int’l Conf. on Architectural Support for Programming Languages and OS - ASPLOS 2004: 177-188.

##  10 Appendix I: RAID Performance Evaluation

10.1 Application performance as affected by storage. 10.2∗ RAID performance
analysis with M/G/1 queueing model.
10.2.1∗ Components of disk service time.
10.3∗ Seek distance distribution without and with ZBR.
10.4∗. RAID5 performance analysis in normal mode.
10.6∗ Fork/Join response time analysis for degraded mode.
10.7∗ Analysis of rebuild processing with V͡acationing Server Model - VSM.
10.8∗ M/G/1 VSM analysis with multiple vacations of two types.
10.8∗ The Laplace Stieltjes Transform for rebuild seek time.
10.13∗ An alternative method to estimate rebuild time.
10.12.1 Optimizing storage allocation.
10.15 Performance analysis of a tape library system.

###  10.1 Application Performance as Affected by Storage

With the advent of faster CPUs, the performance of applications with stringent
response time requirements, such as OLTP, rely heavily on storage performance,
which is especially a problem when the data is held by disks. Transition to
Flash SSDs is expected to alleviate this performance bottleneck leading to
improved response times at a higher equipment cost.

Potential storage accesses are obviated by caching, e.g., higher levels of a
B+ tree index, see e.g., Section 9.4 in Ramakrishnan and Gehrke 2002 [184],
may reside permanently in database caches. Generally database performance can
be improved by obviating disk accesses by utilizing larger buffers and
improved buffer management policies, as discussed in Sections 8.1 and 9.4 of
the Db2 Handbook. 197197197https://docs.broadcom.com/doc/db2-for-zos-
performance-handbook

The CPU checks if a referenced database or file block is held in the main
memory buffer. 198198198https://en.wikipedia.org/wiki/Database_caching If not
an I/O request is issued which is intercepted by the DAC, which checks if it
caches the specified block and id so returns the block. DAC caches with
Battery Backed Unit - BBU are mainly used for writing.
199199199https://www.thomas-
krenn.com/en/wiki/RAID_Controller_and_Hard_Disk_Cache_Settings If the block is
not cached disk’s onboard cache is checked before accessing the disk taking
into account faulty sectors.
200200200https://en.wikipedia.org/wiki/Disk_buffer

Disk transfer rate or bandwidth is an important metric given as:

$\mbox{Sectors\\_Per\\_Track}\times\mbox{sector\\_size}\times\mbox{RPM}/60$

The data transfer rate for Constant Angular Velocity - CAV disks with ZBR from
outer tracks is higher than inner disks. Sustained disk data rates take into
account head switching times across tracks and cylinders. There is a transfer
rate from disk to the onboard buffer and then onward to the main memory.

Least Recently Used - LRU was an early replacement policy, but there are many
others. 201201201https://en.wikipedia.org/wiki/Page_replacement_algorithm
LRU-K algorithm is self-tuning, and does not rely on external hints and adapts
in real time to changing patterns of access O’Neil 1993 [161]. A recent study
advocates FIFO in preference to LRU Yang et al. 2023 [266]. Other page
replacement algorithms are discussed in Section 1.15.1 in Thomasian 2021
[245]. Large capacity of caches requires very long traces making trace-driven
simulation difficult if not impossible. Online measurement of page miss ratios
versus memory size using hardware and software is explored in Zhou et al. 2004
[271].

Part of the DAC cache is NVRAM and duplexed NVRAM is as reliable as disk
storage for logging according to Menon and Cortney 1993 [145], This allows a
fast-write capability and deferred destaging of dirty blocks. Dirty blocks are
overwritten several times before destaging thus reducing disk load. Batch
destaging allows disk scheduling to minimize disk utilization.

While prefetching is known to improve performance, excessive prefetching
results in a reduction the cache hit rate by overwriting viable data. A scheme
that maximizes the sum of hit rates due to prefetching and caching is
described in Baek and Park 2008 [16]. Five prefetching categories are: (1)
history-based, (2) application hint-based, (3) offline optimal, (4) sequential
prefetching, (5) combined with caching. Aligning sequential prefetch in strip
or stripe boundaries shows a performance improvement 3.2x for 128 clients and
2.4x for a single sequential read. on I/O performance with respect to
sequential prefetching schemes in Linux Prefetching methods are reviewed in
Section 1.31 in Thomasian 2021 [245].

Results from I/O trace analysis by Treiber and Menon 1995 [247] were
incorporated into the performance analysis in Thomasian and Menon 1997 [223],
e.g., occurrences of two blocks a short distance apart on a track, treated as
one disk access, which is an instance of disk access coalescing or proximal
I/O Schindler et al. 2011 [200].

Disk cache miss ratio analysis and design considerations are discussed in
Smith 1985 [212]. The fractal structure of cache references model by a
statistically self-similar underlying process, which is transient in nature is
discussed in McNutt 2002 [143]. Self-similarity in nature was observed by B.
Mandelbrot and is discussed in Peitgen et al. 2004 [172].
202202202https://en.wikipedia.org/wiki/Self-similarity

IBM z16 mainframe supports up to 40 TB=$10^{12}$ bytes) main memory.
203203203https://www.ibm.com/downloads/cas/6NW3RPQV Rather than just caching
the whole database may be held in main memory, e.g., IBM’s Information
Management System - IMS FastPath
204204204https://en.wikipedia.org/wiki/IBM_Information_Management_System
Oracle’s TimesTen Lahiri et al. 2013 [126], and SAP’s HANA.
205205205https://www.sap.com/products/technology-platform/hana/what-is-sap-
hana.html The sizes of largest databases in 2015 were as follows.
206206206https://www.comparebusinessproducts.com/fyi/10-largest-databases-in-
the-world Top ten largest databases using different criteria are given here.
207207207urlhttps://www.wheelhouse.com/resources/the-top-10-largest-databases-
in-the-world-past-and-present-a7843

###  10.2 Analysis of RAID5 Performance∗

An M/G/1 queueing model is adopted in this section with Poisson arrivals with
exponential interarrival times with mean $\bar{t}=1/\lambda$ (M) and generally
distributed disk service times (G) with $\overline{x^{i}}$ as the $i^{th}$
moment Kleinrock 1975 [122].

####  10.2.1 Components of Disk Service Time

Disk service time is the sum of seek (s), latency ($\ell$), and transfer time
(t). Given the mean and variance of service time components we have the
following mean, variance and second moment for disk service time:

$\bar{x}_{disk}=\bar{x}_{s}+\bar{x}_{\ell}+\bar{x}_{t},\hskip
14.22636pt\sigma^{2}_{disk}=\sigma^{2}_{s}+\sigma^{2}_{\ell}+\sigma^{2}_{t},\hskip
14.22636pt\overline{x^{2}}_{disk}=\sigma^{2}_{disk}+(\bar{x}_{disk})^{2}.$

The latter equality requires the independence of random variables, especially
latency and transfer time. This is true for accesses to small blocks. The
second moment of disk service time is:

Seagate Cheetah 15k.5 model ST3146855FC parameters extracted in 2007 at CMU’s
PDL are as follows. 208208208https://www.pdl.cmu.edu/DiskSim/diskspecs.shtml
146 GB, maximum logical block number b=286749487 (number of 512 B sectors),
c=72,170 cylinders, number of surfaces 4, RPM=15015, $h=4$ heads, The disk
rotation time is $T_{R}\approx 60,000/\mbox{RPM}=4$ ms. The mean number of
sectors per track is: $b/(c\times h)\approx 993$.

###  10.3 Seek Distance Distribution without and with ZBR∗

Most analytic studies make the false assumption that disk are fully loaded,
which is not true in practice. It was observed in a 1970s that disk arms
rarely move, which may be due to the batch workloads, e.g., a job reading
successive blocks of a disk file. Given that the probability of not moving the
disk arm is $0\leq p\leq 1$ and the remaining cylinders are accessed uniformly
then according to Lavenberg 1983 [127] the distribution of seek distance is
given in Eq. 4

$\displaystyle P_{D}[d]=\begin{cases}p,\mbox{ for }d=0,\\\
(1-p)\frac{2(C-d)}{C(C-1)},\mbox{ for }1\leq d\leq C-1.\end{cases}$ (4)

There are $2(C-d)$ ways to move $1\leq d\leq C-1$ cylinders, which are
normalized by $\sum_{d=1}^{C-1}2(C-d)=C(C-1)$. For uniform distribution across
all cylinders:

$\displaystyle P_{D}[0]=p=\frac{1}{C}\mbox{ and
}P_{D}[d]=\frac{2(C-d)}{C^{2}},1\leq d\leq C-1.$ (5)

The mean seek distance in this case is:

$\displaystyle\bar{d}=\sum_{d=1}^{C-1}dP_{D}(d)=\sum_{d=1}^{C-1}d\frac{2(C-d)}{C(C-1)}\approx\frac{C}{3}.$
(6)

In a continuous domain with $f_{x}(x)=1/L,x\in[0,L]$ the mean distance
$Y=|x_{1}-x_{2}|$ can be obtained by noting that
$f(x_{1},x_{2})=f(x_{1})f(x_{2})=1/L^{2})$. In what follows we have taken
advantage of symmetry by multiplying by two.

$\displaystyle
E[Y]=\int_{0}^{L}\int_{0}^{L}(x_{1}-x_{2})f(x_{1},x_{2})dx_{1}dx_{2}=\frac{2}{L^{2}}\int_{0}^{L}\int_{0}^{L}(x_{1}-x_{2})dx_{1}dx_{2}=\frac{2L^{3}}{6L^{2}}=\frac{L}{3}.$
(7)

The seek time versus seek distance in cylinders or tracks ($d$):
$t_{seek}(d),1\leq d\leq C-1$ is called the seek time characteristic. Curve-
fitting to experimental results yields equations of the following forms, see
e.g., Hennessey and Patterson 2017 [85]:

$t_{seek}(d)=a+b\sqrt{d-1},\mbox{ or }t_{seek}(d)=a+b\sqrt{d-1}+c(d-1)\hskip
14.22636pt1\leq d\leq C-1$

The average seek time can be expressed as $t_{seek}(\bar{d})$, where the mean
seek distance $\bar{d}$ is given by Eq. (6) but a more accurate estimate is
obtainable as follows:

$\overline{x^{i}_{s}}=\sum_{d=1}^{C-1}P_{D}(d)t^{i}_{seek}(d),\hskip
14.22636pt\sigma^{2}_{s}=\overline{x^{2}_{s}}-(\bar{x_{s}})^{2}.$

The analysis in Merchant and Yu 1996 [149] postulates a seek-time formula of
the form: $t_{seek}(f)=a+b\sqrt{f}$, where $0\leq f\leq 1$ is the fraction of
uniformly traversed tracks. This implies a mean normalized seek distance
$\bar{f}=1/2$. The same mistake is repeated in Varki et al. 2004 [251].

The analysis of seek times for disks with ZBR taking into account the
variability of track capacities is given in Thomasian et al. 2007 [233]. The
number of sectors on cylinder $c$ is $s_{c},1\leq c\leq C$. With the
assumption of fully loaded disks and uniformly accessed sectors the
probability of accessing cylinder $c$ is proportional to the number of its
sectors: $P_{c}=s_{c}/C_{d}$, where the disk capacity is
$C_{d}=\sum_{c=1}^{C}s_{c}$. Starting with the probability of seek distance
$d$ starting at cylinder $c$, requires $c+d<C$ and $c>d$. Unconditioning on
$c$:

$P_{D}(d|c)=P_{c}(c+d)+P_{c}(c-d),\hskip
14.22636ptP_{D}(d)=\sum_{c=1}^{C}P_{D}(d|c)P_{c}$

A mapping of files onto disk cylinders and their access rates can be used to
obtain more accurate estimates of seek time.

Rebuild analysis requires the LST of seek time and transfer time. Provided
that the Rebuild Unit - RU is a track, there is almost no latency due to Zero
Latency Access - ZLA which allows track reading to start at the first
encountered sector, see Section 21.1.3 Jacob et al. 2008 [108], Given that
track transfer time equals disk rotation time ($T_{R}$), the LST is: ${\cal
L}^{*}_{t}(s)=T_{R}/s$.

Latencies to access small blocks are uniformly distributed over track rotation
time: $(0,T_{R})$. The LST and $i^{th}$ moment of latency is given as:

${\cal L}^{*}_{\ell}(s)=(1-e^{-sT_{R})/(sT_{R}}),\hskip
14.22636pt\overline{x^{i}_{\ell}}\approx T^{i}_{R}/(i+1).$

Given that the transfer time of $j=8$ sectors from cylinder $c$ is
$x_{t}(j,c)=jT_{R}/s_{c}$, it follows that the $i^{th}$ moment of transfer
time is:

$\overline{x_{t}^{i}}(j)=\sum_{c=1}^{C}x_{t}^{i}(j,c)P_{c},\hskip
14.22636pt\sigma^{2}_{t}=\overline{x^{2}_{t}}-(\bar{x_{t}})^{2}.$

The transfer time of fixed size blocks in nonZBR disks is a constant
$c=x_{t}$, so that $X^{*}_{t}(s)|c_{constant}=c/s$ With ZBR the variability of
track transfer times should be taken into account by uncondioning on the
variation of transfer time, which increases almost uniformly from innermost to
outmost cylinder.

The LST of response time $R^{*}(s)=W^{*}(s)B^{*}(s)$ where the LST of service
time is $B^{*}(s)=X^{*}_{s}(s)X^{*}_{\ell}(s)X^{*}_{t}(s)$, where according to
Chapter 5 in Kleinrock 1975 [122].

$W^{*}(s)=\frac{\bar{x}(1-\rho)}{1-\lambda(1-B^{*}(s)}.$

The $i^{th}$ moment of disk response time is:

$\overline{R^{i}}=(-1)^{i}\frac{dR^{*}(s)}{ds^{i}}|_{0}$

### Shingled Magnetic Recording - SMR

SMR writes partially overlaps written tracks increasing recording density
radially while ZBR increases disk capacity linearly.
209209209https://en.wikipedia.org/wiki/Shingled_magnetic_recording The
emergence of SMR may be attributed to slowdown in disk capacity growth after
2010, while there was rapid growth in the period 2000-2010 Gray and Shenoy
2000 [73].

SMR design issues are presented in Amer et al. 2010 [6]. Theoretical
justifications for SMR are given in Sanchez 2007 [197], which in Section 1.2
introduces the trilemma: (1) thermal stability, (2) writeability, and (3)
media Signal to Noise Ratio - SNR. A technical description of SMR drives is
given in Feldman and Gibson 2013 [53].

The performance of SMR drive is unpredictable in that clean drives can be
written quickly, but if the drive has too many writes queued, or has
insufficient idle time to reorganize or discard overwritten data, then write
speeds can be significantly lower than the usual disk bandwidth, e.g., 1030
Mbits/s for 7200 RPM disks.
210210210https://en.wikipedia.org/wiki/Hard_disk_drive_performance_characteristics
Because of their access time variability SMR disks should be excluded from
RAID5 arrays. 211211211urlhttps://www.servethehome.com/surreptitiously-
swapping-smr-into-hard-drives-must-end/

###  10.4 RAID5 Performance in Normal Mode∗

RAID5 utilizes left symmetric parity layout over successive $(N+1)\times(N+1)$
segments The parities are placed at $D(N+1-i,N+1-i),0\leq i\leq N$ he parities
can be used to recover from disk failures and to cope with unreadable sectors
as long as they do not belong to the same parity group. There is extra
processing to update parities as corresponding data blocks are updated. Given
a modified disk block $d_{new}$, if not cashed its previous version $d_{old}$
has to be read from disk to compute $d_{diff}=d_{old}\oplus d_{new}$.
Similarly $p_{old}$ is accessed if not cached to compute
$p_{new}=p_{old}\oplus p_{diff}$. The fact that a single write requires four
disk accesses is called the Small Write Penalty - SWP Chen et al. 1994 [31].
RAID(4+k), $\ell\geq 1$ requires $2(k+1)$ reads and writes to update $k$ data
and $k$ check blocks.

The writing of $d_{new}$ and $p_{new}$ to disk be deferred by first writing to
NonVolatile Storage - NVS e.g., NonVolatile RAM - NVRAM. Dirty blocks in NVRAM
can be overwritten several times before being destaged or written to disk thus
obviating unnecessary writes. Destaging batches of blocks allows permuting the
order in which blocks are written to reduce positioning times. Other methods
to deal with SWP are presented in Chen et al. 1994 [31].

Let $f_{r}$ and $f_{w}=1-f_{r}$ denote the fraction of logical read and write
requests. Each read request results in a Single Read - SR access to disk if
the data is not cached and each logical write may require two SR and two
Single Write - SW disk accesses. The fraction of SRs and SWs are as follows:

$f_{SR}=(f_{r}+2f_{w})/(3f_{r}+2f_{w}),\hskip 14.22636ptf_{SW}=1-f_{SR}.$

The moments of disk service time are given as follows:

$\displaystyle\overline{x^{i}}_{disk}=f_{SR}\overline{x^{i}_{SR}}+f_{SW}\overline{x^{i}_{SW}}.$
(8)

Given that the arrival rate to the RAID5 disk array is $\Lambda$ . then RAID
striping results in uniform accesses to $N+1$ disks: $\lambda=\Lambda/(N+1)$,
so that the disk utilization factor is:

$\rho=\lambda\bar{x}_{SR}+2f_{w}(\bar{x}_{SR}+\bar{x}_{SW}).$

Given the mean and variance of disk service time with FCFS scheduling the
coefficient of variation of disk service time is:
$c^{2}_{X}=\sigma^{2}_{disk}/(\bar{x}_{disk})^{2}.$ The mean, second moment,
and variance of waiting time in M/G/1 queues is given by the Pollaczek-
Khinchine formula Kleinrock 1975 [122]:

$\displaystyle
W=\frac{\lambda\overline{x^{2}}_{disk}}{2(1-\rho)}=\frac{\rho\bar{x}(1+c^{2}_{X})}{2(1-\rho)},\hskip
14.22636pt\overline{W^{2}}=2W^{2}+\frac{\lambda\overline{x^{3}}_{disk}}{3(1-\rho)},\hskip
14.22636pt\sigma^{2}_{W}=\overline{W^{2}}-W^{2}.$ (9)

The prioritized processing of SR requests on behalf of logical reads is only
affected by disk utilization due to other logical read requests. The fraction
of such requests is ${f^{\prime}}_{SR}=f_{r}/(f_{r}+4f_{w})$ and moments of
disk service time ($x_{disk}$) should be recomputed with ${f^{\prime}}_{SR}$.
The waiting time of SR requests with nonpreemptive priorities is given in
Kleinrock 1976 [123].

$\displaystyle
W_{pr}=\frac{\lambda\overline{x^{2}}_{disk}}{2(1-\rho_{SR})}\mbox{ with
}\rho_{SR}={f^{\prime}}_{r}\lambda\bar{x}_{SR}.$ (10)

The read response without and with priorities is: $R_{SR}=\bar{x}_{SR}+W\mbox{
and }R_{SR}=\bar{x}_{SR}+W_{pr}.$

A write is considered completed when both the data and parity blocks are
written to disk, which is an instance of F/J processing discussed in Section
10.5. Write response times are of no interest since they do not affect
application response time due to the fast write capability onto NVRAM.

No-Force transaction commit does not require dirty blocks in database buffer
to be written to disk or NVS, because ”after images” of such blocks are
written to disk as part of transaction commits. Logging for database recovery
is discussed in Chapter 18 on Crash Recovery in Ramakrishnan and Gehrke 2002
[184].

Since for the FCFS policy the waiting time is independent from service time
then: $E[\tilde{W}_{SR}\tilde{x}_{SR}]=\bar{W}_{SR}\times\bar{x}_{SR}$ and the
second moment of SR requests is:

$\displaystyle\overline{R^{2}}_{SR}=\overline{W^{2}}_{SR}+\overline{x^{2}}_{SR}+2W\bar{x}_{SR}\mbox{
and }\sigma^{2}_{SR}=\overline{R^{2}}_{SR}-(R_{SR})^{2}.$ (11)

###  10.5 RAID5 Operation in Degraded Mode

A block $d_{1}$ on failed Disk1 can be reconstructed as: $d_{1}=d_{2}\oplus
d_{3}\oplus\ldots\oplus p_{1:N+1}.$

The read load on surviving disks is doubled, since given balanced read loads
due to striping each read access to the failed disk will results in an access
to $N$ surviving disks to reconstruct blocks on demand In the case of a write
to Disk1 $N-2$ disk accesses are required. $p_{1:N+1}^{new}=d_{1}^{new}\oplus
d_{2}\oplus d_{3}\oplus\ldots\oplus d_{N}.$ The load increase for a fraction
$f_{R}$ for read and $f_{W}$ for write accesses according to Ng and Mattson
1994 [156] is:

$\displaystyle\mbox{LoadIncr}(f_{R})=\frac{U_{faulty}}{U_{faultfree}}=\frac{N}{N-1}+\frac{(N-2)f_{R}+(N-8)f_{W}}{(N-1)(f_{R}+4f_{W})},\mbox{
e.g., LoadIncr}(0)=1.333.$ (12)

In the case of a RAID5 with $N+1$ disks an $N$-way (resp. $N-1$-way) F/J
request is required to process read (resp. write) requests involving failed
disks in degraded mode of operation. In addition to F/J requests disk process
their own requests termed interfering in Fig. 14.

Before rebuild processing starts F/J requests on behalf of read requests to a
failed disk constitute one-half of read requests processed by surviving disks,
but this fraction gets smaller as rebuild progresses due to “read
redirection”, i.e., reading reconstructed data from the spare disk Muntz and
Lui 1990 [152]. This term is a misnomer since redirection is also used by
writes to compute the parity block when $d_{old}$ is already reconstructed on
a spare. When $d_{old}$ or $p_{old}$ are not reconstructed yet on the spare
there is no need to compute and write $d_{new}$ or $p_{new}$, since this is
done more efficiently later as part of rebuild.

Piggybacking proposed by Muntz and Lui 1990 [152] writes blocks reconstructed
on demand on the spare disk. 212212212This piggybacking is different from that
in Section 5. Piggybacking small writes for rebuild tends to be inefficient
Holland et al. 1994 [86]. Piggypbacking at the level of tracks on which
reconstructed data blocks reside is considered in Fu et al. [60]. Instead of
half a disk rotation to read a block a full rotation will be required.

The load in clustered RAID5 and RAID6 is obtained using decision trees in
Thomasian 2005b [228]. 213213213https://en.wikipedia.org/wiki/Decision_tree
Let $\bar{x}_{\cdot}$ denotes read, write, and Read-Modify-Write - RMW mean
disk service times. RMW is a read followed by a write after a disk rotation
and can be substituted by independent single reads and writes. With arrival
rate $\Lambda$ to a RAID5 with $N$ disks disk utilizations factors due to read
and write requests with one failed disk are: 214214214Surviving disk loads
should be increased by a factor $N/(N-1)$, see e.g. Thomasian et al. 2007
[233].

$\displaystyle\rho^{RAID5/F1}_{read}=\frac{\Lambda
f_{read}}{N-1}\left[\frac{N+G-2}{N}\bar{x}_{read}\right],\hskip
14.22636pt\rho^{RAID5/F1}_{write}=\frac{\Lambda
f_{write}}{N-1}\left[\frac{G-2}{N}\bar{x}_{read}+\frac{2}{N}\bar{x}_{write}+\frac{2(N-2)}{N}\bar{w}_{RMW}\right]$

###  10.6 Methods to Obtain Response Times for Fork/Join Requests∗

The only exact result for F/J queueing systems is a 2-way F/J with two
parallel M/M/1 queues. With arrival rate $\lambda$ and mean service time
$\bar{x}=1/\mu$ server utilization $\rho=\lambda\bar{x}$. The response time
distribution in M/M/1 queues is exponentially distributed according to Eq. 1,
i.e., $R(t)=1-e^{-t/\rho}$, where $R(\rho)=\bar{x}/(1-\rho)$ is the mean
response time. The analysis in Flatto and Hahn 1984 [55] is used to derive
$R_{2}^{F/J}(\rho)$ in Nelson and Tantawi 1988 [154].

$\displaystyle
R_{2}^{F/J}(\rho)=\left[H_{2}-\frac{\rho}{8}\right]R(\rho)=\frac{12-\rho}{8}R(\rho),\mbox{
where the Harmonic sum is:
}H_{K}\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{k=1}^{K}\frac{1}{k}.$ (13)

Note that $R_{2}^{FJ}(0)=R_{2}^{max}(0)=\frac{H_{2}}{\mu}$ The following
approximate equation for $2\leq n\leq 32$-way M/M/1 F/J queueing systems is
derived in Nelson and Tantawi 1988 [154].

$\displaystyle
R_{n}^{F/J}(\rho)=\left[\frac{H_{n}}{H_{2}}+(1-\frac{H_{n}}{H_{2}})\alpha(\rho)\right]R_{2}^{F/J}(\rho),$
(14)

Curve-fitting to simulation results yielded $\alpha(\rho)\approx(4/11)\rho$.

This equation is used in Menon 1994 [146] where disk service times are assumed
to be exponentially distributed to estimate F/J response times in accessing
the failed disk. This is an underestimate because disks process interfering
requests.

Simulation results for the mean F/J response time versus server utilization by
varying the fraction of F/J requests, while the total $\rho$ is kept fixed for
different service time distributions are given in Thomasian and Tantawi 1994
[221]. As the fraction of F/J requests decreases with respect to interfering
requests, their mean response times increases and tends to the expected value
of the maximum in Eq. (15).

$\displaystyle R_{n}^{F/J}(\rho)\approx R_{n}^{max}(\rho).$ (15)

Figure 14: Fork/join processing with interfering requests processing

We next consider schemes to estimate the expected value of the maximum of $n$
i.i.d. random variables. Given the mean $\mu_{X}$ and standard deviation
$\sigma_{X}$ of the components of an F/J request according to David and
Nagaraja 2003 [40]:

$\displaystyle\overline{X}_{n}^{max}\approx\mu_{X}+\sigma_{X}G(n).$ (16)

For the exponential distribution $G(n)=H_{n}-1$ and since $\sigma_{X}=\mu_{X}$
then $\overline{X}_{n}^{max}=\mu_{X}H_{n}$, which is also given by Eq. (18),
which is exact as shown below.

The Probability Distribution Function - PDF of the maximum of $n$ random
variables with PDF $F_{Y}(y)$ is also the $n^{th}$ order statistic Trivedi
2001 [249]:

$\displaystyle F_{Y_{n}^{max}}(y)=[F_{Y}(y)]^{n}.$ (17)

$\mbox{Given }F_{y}(y)=1-e^{-\lambda y}\mbox{ for }n=2\hskip
14.22636pt\bar{Y}_{2}^{max}=\frac{2}{\lambda}-\frac{1}{2\lambda}=\frac{H_{2}}{\lambda}.$

Induction can be used to obtain $Y_{n}^{max}$ or using the method in Section
4.6.2 in Trivedi 2001 [249] or:
215215215https://mikespivey.wordpress.com/2013/05/13/expectedmaxexponential/

$\displaystyle\bar{Y}_{n}^{max}=H_{n}\bar{Y}.$ (18)

Eq. (19) in Thomasian and Tantawi 1994 [221] for the expected value of the
maximum of $n$ response times is motivated by Eq. (16):

$\displaystyle
R_{n}^{F/J}(\rho)=R(\rho)+F_{n}\sigma_{R}(\rho)\alpha_{n}(\rho),$ (19)

where $R(\rho)$ and $\sigma_{R}(\rho)$ are the mean and standard deviation of
response time at utilization factor $\rho$. Surface-fitting to simulation
results was used in this study to obtain $\alpha_{n}(\rho)$ for several
distributions.

It is shown in Nelson and Tantawi 1988 [154] that $R_{n}^{max}(rho)$ is an
upper bound to $R_{n}^{F/J}(\rho)$ for the exponential distribution. This
effect is observed via simulation in Thomasian and Tantawi 1994 [221] for
other distributions and that $R_{n}^{max}(\rho)$ is a good approximation to
$R_{n}^{F/J}(\rho)$ when F/J requests constitute a small fraction of processed
requests. This is the case for RAID5 in degraded mode as rebuild progresses
and most requests to the failed disk are satisfied by redirection and the
fraction of F/J requests drops.

A simple method to obtain the maximum of $n$ i.i.d. random variables is to use
the two-parameter Extreme Value Distribution - EVD approximation Johnson et
al. 1995 [114], Kotz and Nadarajah 2000 [125].

$\displaystyle F_{Y}(y)=P(Y<y)=exp(-e^{-\frac{y-a}{b}}),\hskip
8.53581pt\overline{Y}=a+\gamma b,\hskip
8.53581pt\sigma^{2}_{Y}=\frac{\pi^{2}b^{2}}{6},$ (20)

where $\gamma=0.577721$ is the Euler constant. Matching the first two moments:
$\bar{Y}=R(\rho)$ and $\sigma_{Y}=\sigma_{R}$ leads to:

$b=\sqrt{\frac{6}{\pi}}\sigma_{Y}\mbox{ and }a=\bar{Y}-\gamma b.$

The maximum of $n$ random variables with EVD has a simple form:

$\displaystyle\overline{Y_{n}^{m}ax}=(a+\gamma
b)+b\mbox{ln}(n)=\overline{Y}+\frac{\sqrt{6}}{\pi}\sigma_{Y}.$ (21)

It follows from simulation results in Thomasian et al. 2007 [233] that EVD
overestimates $\overline{y^{n}}_{max}$ and a better approximation is obtained
if the second summation term is divided by 1.27. Three types of EVDs are and
the above discussion is based on Gumbel distribution:
216216216https://core.ac.uk/download/pdf/15566772.pdf

The coefficient of variation of response times of M/G/1 queues for accesses to
small randomly placed disk blocks for disk characteristics in Thomasian and
Menon 1997 [223] is:

$\displaystyle
c^{2}_{R}(\rho)=\frac{\sigma^{2}_{R}(\rho)}{R^{2}(\rho)}=\frac{c^{2}_{X}+\frac{\rho
s_{X}}{3(1-\rho)}+\frac{\rho(1+c2_{X})}{4(1-\rho)^{2}}}{1+\frac{\rho(1+c^{2}_{X}}{1-\rho}+\frac{\rho(1+c2_{X})}{4(1-\rho)^{2}}},$
(22)

where $s_{X}=\overline{x^{3}}_{SR}/(\bar{X}_{SR})^{3}$. Where $c_{R}=c_{X}$
for $\rho=0$ and that as $\rho\rightarrow 1$ $c_{R}\rightarrow 1$, i.e., an
exponential distribution, hence $c_{R}<1$ for $C_{X}<1$, which was the case
the study.

Approximating the response time distribution with a distribution, which is an
exponential in form has the advantage that its expected value of its maximum
can be computed easily by integration. In the case of the Erlang distribution
whose $c^{2}<1$ the number of its stages is: $k=\lceil 1/c^{2}\rceil$ and the
mean delay per stage is $1/\mu=R(\rho)/k$ $R_{n}^{max}(\rho)$ for an $n$-way
$k$-stage Erlang distribution is then:

$\displaystyle
R^{max}_{n}(\rho)=\int_{0}^{\infty}\left[1-\prod_{i=1}^{n}\left(1-e^{-\mu_{i}t}\sum_{j=0}^{k_{i}-1}\frac{(\mu_{i}t)^{j}}{j!}\right)\right]dt.$
(23)

Provided disks have an XOR capability updating parities results in a 2-way F/J
request with unequal service times: $d_{new}$ and the block address is sent to
the disk and after $d_{old}$ is read $d_{diff}$ is computed and $d_{n}ew$
overwrites $d_{old}$ after a disk rotation. $d_{diff}$ and the address of
$P_{old}$ are then sent via the DAC to the parity disk where it is XORed with
$p_{old}$ to compute $P_{new}$, which overwrites $p_{old}$ after one disk
rotation. Write response time is the maximum of data and parity writes.

$\displaystyle
R^{max}_{2}(\rho)=\sum_{i=1}^{2}R_{i}(\rho)-\sum_{m=0}^{k_{1}-1}\sum_{n=0}^{k_{2}-1}\binom{m+n}{m}\frac{\mu_{1}^{m}\mu_{2}^{n}}{(\mu_{1}+\mu_{2})^{m+n+1}},\mbox{
where }\mu_{1}=k_{1}/R_{1}(\rho)\mbox{ and }\mu_{2}=k_{2}/R_{2}(\rho).$ (24)

The more flexible Coxian distribution used by Chen and Towsley 1993 [33]. can
be applied to any response time distribution regardless of the value of
$c_{R}$.

Two moment approximations for maxima are given in Crow et al. 2007 [39].
Formulas for special cases when the coefficient of variation $c<1$ are
provided. When $c>1$ a 3-moment approximation to the Hyperexponential-2
distribution given by Eq. (4.4) is suggested.

###  10.7 Vacationing Server Model for Analyzing Rebuild Processing∗

Rebuild is the systematic reconstruction of the contents of the failed disk on
a spare disk. Rebuild is started after an appropriate delay to allow for fail-
slow events in Section 11.10. Strip $D_{1}$ on failed Disk1 is reconstructed
in the DAC’s buffer by reading and XORing $N-1$ corresponding strips, which
are written to strip ${D^{\prime}}_{1}$ on a spare disk which replaces failed
Disk1. ${D^{\prime}}_{1}=D_{2}\oplus D_{3}\oplus\ldots P_{1:N}.$

The rebuilding of a failed disk is carried out concurrently with the
processing of external requests to maintain high availability due to the high
cost of downtime in Section 1. Rebuild time is lengthened due to the
interference of external disk requests and conversely disk response times is
increased by rebuild reads.

Distributed sparing in RAID5 provides sufficient storage on $N-1$ surviving
disks to hold the data strips of the failed disk. Spare strips are allocated
in repeating diagonals similarly to parity strips as shown in Fig. 1 in
Thomasian and Menon 1997 [223]. The advantage of distributed sparing over
dedicated sparing is that the bandwidth of the spare disk is not wasted.
Rebuild reading in distributed sparing takes longer than dedicated sparing,
since rebuild reading from surviving disks is slowed down by rebuild writes.
In fact distributed sparing is advantageous for CRAID, since a single spare
disk may become a bottleneck in this case. A disadvantage of distributed and
restriping rebuild discussed below is that an additional copyback step to copy
the contents of spare strips onto a spare disk is not required.

Restriping which overwrites check strips is preferable to distributed sparing
in that it attains higher reliability Rao et al. [185]. Starting with RAID7
there are the following transitions:
RAID7 $\rightarrow$ RAID6 $\rightarrow$ RAID5 $\rightarrow$ RAID0
$\rightarrow$ Data Loss.
In parity sparing proposed in Reddy et al. [187] two RAID5 arrays are merged
and parity blocks on one RAID5 are used as spare areas to hold missing strips.

Rebuild time in multi-TB HDDs takes hours making RAID5 vulnerable to a second
disk failure, especially if disk failures are correlated, which was an initial
reason for RAID6. Most rebuild failures are due to LSEs - Latent Sector
Errors, which stop rebuild from progressing as discussed in Section 11.4. A
queueing model to estimate rebuild time in RAID5 with HDDs is discussed in
Section 10.7

Before the introduction of ZBR fixed sized RUs were set to a single or
multiples disk tracks. Fixed size RUs can be adopted for ZBRs with RU sizes
large enough to make positioning time negligible.

RAID5 rebuild time is investigated via simulation in Holland et al. 1994 [86],
where it is concluded that Disk-Oriented Rebuild - DOR is superior to Stripe-
Oriented Rebuild - SOR, which proceeds by reading one stripe at a time, since
this introduces unnecessary synchronization delays but reduces buffer
requirements with respect to DOR. A fixed size Rebuild Unit - RU equaling one
track was postulated.

DOR which reads disks when they become idle is analyzed in Thomasian and Menon
[220, 223] using the Vacationing Server Model - VSM with multiple vacations of
two types in Doshi 1985 [47] and cited in Takagi 1991 [216].

The analysis yields the increased response time of external disk requests due
to interference caused by rebuild processing and the effect of external disk
requests expanding rebuild processing time. Rebuild reading with VSM is
restarted when the disk becomes idle. The accuracy of the analyses was
verified using a random-number driven simulation in both studies, since the
system under consideration with codename Hager in Chen et al. 1994 [31] was
under development, while NCR’s 6298 RAID5 discussed in Section 5.3 of the
tutorial was released in 1991
217217217https://techmonitor.ai/technology/ncr_offers_redundant_array_scsi_chips_controller

Rebuild reading is halted with the arrival of external requests and the
accumulated requests are served after rebuild read completes and the cycle
repeats. This is implicitly a priority queueing model with higher priority
assigned to external requests. The application of VSM to analyzing rebuild
processing is also discussed in Thomasian 2018 [244].

The initial RU or track read takes longer, since it involves a seek and
latency as shown in Fig. 15). The reading of succeeding RUs take less time,
since a seek is not required, e.g., a disk rotation if the RU size is a track.

Figure 15: Key VSM parameters associated with rebuild processing.

The delay encountered by an external request requests with VSM follows from
the fact that Poisson Arrivals See Time Averages - PASTA. The mean waiting
time for external disk requests is the sum of three delays:
(1) the mean waiting time in the queue, which is a product of mean queue
length ($\bar{N}_{q}$) and mean service time per request ($\bar{x}$).
(2) if the server is busy with probability $\rho$ there is an additional delay
given by the mean residual service time ($\bar{x}_{r}=\bar{x^{2}}/(2\bar{x})$
Kleinrock 1975 [122]).
(3) the system is idle with probability $1-\rho$, in which case the delay is
the mean residual vacation (RU reading) time:
$\bar{v}_{r}=\overline{v^{2}}^{2}/(2\bar{v})$), where the $\overline{v^{i}}$
is the $i^{th}$ moment of vacation or rebuild read time.

$W=\bar{N}_{q}\bar{x}+\rho\bar{x}_{r}+(1-\rho)\bar{v}_{r}\mbox{ due to
Little's result:}\bar{N}_{q}=\lambda W,\hskip 5.69054pt\rho=\lambda\bar{x}$

Simplifying the above equation yields:

$\displaystyle
W_{VSM}=W_{M/G/1}+\bar{v}_{r}=\frac{\lambda\bar{x^{2}}}{2(1-\rho)}+\bar{v}_{r}.$
(25)

An analysis of VSM with multiple vacations of two types is given in Section
10.8.

The M/G/1 queue alternates between busy periods with mean $\bar{g}$ during
which external disk requests are served and idle periods given with mean
interarrival time ($1/\lambda$). This is when RUs are reads although the
processing of the first external request is delayed until a rebuild read is
completed, unless preemption is allowed as discussed in Thomasian 2005b [228].
The utilization factor $\rho$ which is the fraction of time the server is busy
can be expressed as:

$\displaystyle\rho=\frac{\overline{g}}{\overline{g}+1/\lambda}\Longrightarrow\overline{g}=\frac{\bar{x}_{disk}}{1-\rho}.$
(26)

The delay cycle is different from a busy period in that it starts with a
special request whose mean is the sum of mean residual rebuild time
($\bar{v}_{r}$) and mean disk service time ($\bar{x}_{disk}$) as shown in Fig.
15. The mean duration of the delay cycle using the definition of $\rho$
according to Thomasian 2018 [244] is:

$\displaystyle\rho=\frac{\bar{T}_{dc}(\rho)-\bar{v}_{r}}{\bar{T}_{dc}(\rho)+1/\lambda}\hskip
5.69054pt\Longrightarrow\hskip
5.69054pt\bar{T}_{dc}(\rho)=\frac{\bar{x}_{disk}+\bar{v}_{r}}{1-\rho}.$ (27)

The cycle time is defined as the time between the start of successive busy
periods and is given by Eq. (28):

$\displaystyle\bar{T}_{ct}(\rho)=\bar{T}_{dc}(\rho)+\frac{1}{\lambda}.$ (28)

The moments of busy period and delay cycle can be obtained from their LSTs
Kleinrock 1975/76 [122, 123]. The variances obtained in this manner can be
used to obtain a better estimate of rebuild time as given by Eq. (16), but
this is not necessary since simulation results show that there is little
variation in the completion time of disk rebuild reading times (see e.g., Fig.
4 in Thomasian and Menon 1997 [223]).

Assuming that the RU is a track, the number of disk tracks: $N_{track}$ and
the mean number of tracks read per cycle: $\bar{n}_{track}$, the rebuild read
time is:

$\displaystyle T_{rebuild}(\rho)=\frac{N_{track}}{\bar{n}_{track}}\times
T_{cycletime}.$ (29)

Rebuild reading is overlapped with rebuild writing, $i^{th}$ RU is written as
RUs to reconstruct the $(i-1)^{st}$ RU are being being read so that rebuild
time can be approximated with RU read time.

The spare disk is not a bottleneck unless we have a Clustered RAID - CRAID in
Section 6. CRAID provides parallelism for rebuild reading, which would result
in buffer overflow with VSM rebuild to a dedicated spare. Rebuild reads can be
throttled taking into account the degree of parallelism due to CRAID. A
simpler scheme is to monitor the number of RUs to be written to the spare disk
in buffer and stopping rebuild reading when their number exceeds a certain
threshold.

###  10.8 M/G/1 VSM Analysis of Multiple Vacations with Two Types∗

This section is based on Thomasian 1994/1997 [220, 223] which utilize VSM in
Doshi 1985 [47] and summarized in Takagi 1991 [216]. Both analyses assume that
the RU size is a track.

The first RU/track read at the start of an idle period requires a seek
followed by the reading of a track, while successive rebuild reads just take a
disk rotation, as shown in Fig. 15. Due to ZLA reading of a track starts with
the first encountered sector, i.e., the rotational latency (time to access a
sector) is negligible. Track and cylinders skew in reading successive tracks
is negligible Jacob et al. 2008 [108].

#### The Laplace Stieltjes Transform for Rebuild Seek Time∗

LSTs are discussed in Appendix I in Kleinrock 1975 [122] and Appendix D in
Trivedi 2001 [249].

To obtain the LST of seek time required for type 1 vacations we approximate
the distribution in Eq. (4) by a continuous function, whose probability
density function - pdf is:

$\displaystyle f_{X}(x)=p\delta(x)+(1-p)\frac{2(C-x)}{C(C-2)}\mbox{ note that
}\int_{x=1}^{C-1}f_{X}(x)=1,$ (30)

where $\delta(x)$ is the unit impulse at $x=0$.

Motivated by Abate et al. 1968 [1] we derive the LST of seek time by using a
piecewise linear approximation to the seek time characteristic:
($T_{k},C_{k}$), where $C_{1}=1$ and $C_{K+1}=C-1$.

$t(x)=\alpha_{k}x-\beta_{k}\hskip 14.22636ptC_{k}\leq x\leq C_{k+1}.$
$\alpha_{k}=\frac{C_{k+1}-C_{k}}{T_{k+1}-T_{k}}\mbox{ and
}\beta_{k}=\alpha_{k}T_{k}-C_{k}.$

Given that $x$ denotes the number of moved tracks:

$\displaystyle
x=\sum_{k=1}^{K}(\alpha_{k}t-\beta_{k})[u(t-C_{k})-u(t-C_{k+1}],$ (31)

where $u(x)$ is the unit step function Kleinrock 1975 [122].

$u(x)=\begin{cases}1\mbox{ for }x\geq 0\\\ 0\mbox{ for }x<0.\end{cases}$

The LST of seek time using Eq. (30) and Eq. (31) is, but $p=1/C$ was used in
the study:

$\displaystyle{\cal
L}^{*}_{s}(s)=\frac{p}{s}+\frac{2(1-p)}{C(C-2)}\sum_{k=1}^{K}\alpha_{k}(C+\beta_{k})\frac{e^{-sT_{k}}-e^{-sT_{k+1}}}{s}$
(32)
$\displaystyle-\alpha_{k}^{2}\left(\frac{T_{k}e^{-sT_{k}}-T_{k+1}e^{-sT_{k+1}}}{s}-\frac{e^{-sT_{k}}-e^{-sT_{k+1}}}{s^{2}}\right)$

The LST of disk service time according to Eq. (refeq:diskservice) is the
product of the LSTs of its components:

${\cal L}^{*}_{disk}(s)={\cal L}^{*}_{s}(s)\times{\cal
L}^{*}_{\ell}(s)\times{\cal L}_{t}(s).$

The moments of disk service time can be obtained by taking the derivatives of
${\cal L}^{*}_{disk}$, such as Eq. (37).

Reading of RUs is modeled as two vacation types as noted earlier: Type 1
vacations start once the disk is idle and require a seek to access the next RU
to be read. Type 2 vacations are reads of consecutive RUs until an external
request arrives.

The PDFs of two vacation types are denoted by $V_{i}(t),i=1,2$ In the case of
Poisson arrivals the probability of no arrival (resp. an arrival) is
$e^{-\lambda t}$ (resp. $1-e^{-\lambda t}$) in time interval $(0,t)$. Let
$p_{i}$ denote the probability that a request arrives during the $i^{th}$
vacation. Unconditioning on $V_{i}(t)$:

$\displaystyle p_{i}=\left[1-\int_{0}^{\infty}e^{-\lambda
t}dV_{i}(t)\right]\prod_{j=1}^{i-1}\int_{0}^{\infty}e^{-\lambda
T}dV_{j}(t)=[1-V_{i}^{*}(t)]\prod_{j=1}^{i-1}V_{j}^{*}(\lambda).$ (33)

where $V^{*}_{j}(\cdot)$ is the LST of the $j^{th}$ vacation. The mean number
of tracks read or vacations taken per idle period is:

$\displaystyle\bar{n}_{track}=\bar{J}=\sum_{j=1}^{\infty}jp_{j}=1+\frac{V^{*}_{1}\lambda)}{1-V^{*}_{2}(\lambda)}$
(34)

The split seek-option skips track reading following a seek if there is an
arrival during the seek Thomasian and Menon 1994 [220]. Preemption during the
latency and even track transfer phases are studied via simulation in Thomasian
1995 [222].

While preemption results is an improvement in disk response times, rebuild
time is elongated since more requests are processed and this results in an
increased number of requests during rebuild processing (with increased
response times). The cumulative sum of response times is an appropriate metric
in comparing rebuild options.

The probability of an arrival during the first and $i^{th}$ vacation is:

$\displaystyle p_{1}=1-V^{*}_{1}(\lambda)\hskip
14.22636ptp_{i}=[1-V^{*}_{2}(\lambda)]V_{1}^{*}(\lambda)]V^{*}_{1}(\lambda)[V^{*}_{2}(\lambda)]^{i-2}$
(35)

The probability that the $i^{th}$ vacation occurs is $q_{i}=p_{i}/\bar{J}$,
where $\bar{J}$ was given by Eq. (34). The probability $q_{i},i=1,2$ that an
external arrival occurs during a type one or two vacation is:

$q_{1}=\frac{1}{1+V^{*}_{1}(\lambda)/(1-V^{*}_{2}\lambda)},\hskip
14.22636ptq_{2}=1-q_{1}.$

It follows that overall LST for vacations is:

$\displaystyle
V^{*}(\lambda)=\frac{(1-V^{*}_{2}(\lambda))V_{1}^{*}(s)+V^{*}_{1}(\lambda)V_{2}^{*}(s)}{1-V_{2}^{*}(\lambda)+V_{1}^{*}(\lambda)}.$
(36)

Derivatives of the LST Eq. (36 set to zero yield the $j^{th}$ moment of
vacation/rebuild read time:

$\displaystyle\overline{v^{j}}=(-1)^{j}\frac{dV^{j}(\lambda)}{d\lambda}|_{\lambda=0}=\sum_{i=1}^{\infty}q_{j}\overline{v_{i}^{j}}=\frac{(1-V^{*}_{2}(\lambda))\overline{v}_{1^{j}}+V^{*}_{1}(\lambda)\overline{v}_{2^{j}}}{1-V_{2}^{*}(\lambda)+V_{1}^{*}(\lambda)}.$
(37)

The mean residual vacation/rebuild read time as noted earlier is:
$\overline{v_{r}}=\overline{v^{2}}/(2\overline{v})$.

The variation in disk utilization due to redirection in computing
$T_{rebuild}(\rho_{i})$ is taken into account by computing rebuild processing
time over $k$ intervals with small load variation. A read only workload to
simplify the discussion results in the doubling of disk loads, but otherwise
the load decreases as rebuild progresses are given by Eq. (12). The rate of
rebuild processing accelerates as disk utilizations drop due to redirection.

$\displaystyle T_{rebuild}(\rho)=\sum_{i=1}^{k}T_{rebuild}(\rho_{i}),\hskip
5.69054pt\rho_{i}=[2-\frac{i}{k}]\rho.$ (38)

RAID5 rebuild time with readonly workload at an initial disk utilization
$\rho$ can be approximated by Eq. (refeq:beta). which results in highest load
increase in degraded mode. IBM 18ES 9 GByte, 7200 RPM HDDs were simulated in
Fu et al. 2004 [60].

$\displaystyle T_{rebuild}(\rho)=\frac{T_{rebuild}(0)}{1-\beta\rho},\mbox{
where }\beta\approx 1.75.$ (39)

###  10.9 Distributed Sparing in RAID5

Distributed sparing in RAID5 allocates sufficient spare areas on surviving
disks to accommodate a single disk failure, i.e., to hold the data blocks of a
failed disk as shown in Fig. 1 in Thomasian and Menon 1997 [223]. Empty strips
are placed in right to left diagonals in parallel with parity strips at each
disk.

The main advantage of distributed sparing with respect to dedicated sparing is
that all disks contribute to the processing of the workload in normal mode.
Rebuild reading time is slowed down because surviving disks in addition to
being read from are written onto by reconstructed RUs. An iterative solution
is used in [223] to equalize the rate at which RUs are being read and written,
This is to prevent the overflow of DAC’s buffer, which more of a problem with
CRAID where rebuild read bandwidth may exceed exceed that of the spare disk if
the external disk load is low.

The analysis for distributed sparing for RAID5 is applicable to restriping
analysis in RAID(4+K). Once a spare disk becomes available the contents of
spare areas are copied onto it in copyback mode to return the system to its
original state, which is a disadvantage of both methods.

###  10.10 Rebuild Processing Using the Permanent Customer Model

The Permanent Customer Model - PCM proposed and analyzed in Boxma and Cohen
1991 [26] postulates a circulating permanent customer in an M/G/1 queue. The
queue which serves external customers processes one permanent customer, who
once completed rejoins a FCFS queue from which all customers are served. PCM
is adopted in Merchant and Yu 1996 [149] to model rebuild processing in RAID5.
FCFS scheduling is not compatible with modern disk scheduling policies as
discussed in Section 12.1.1.

VSM for rebuild processing outperforms PCM by attaining a lower response times
for external disk requests, since it processes rebuild read requests at a
lower priority than external requests.

In PCM rebuild reads spend more time in the FCFS queue and this reduces the
probability of consecutive rebuild reads with respect to VSM and hence
increased rebuild time. The probability that rebuild requests are intercepted
by user requests arriving with rate $\lambda$ with VSM and PCM rebuild are
given in Fu et al. 2004a [60]:

$P_{VSM}=1-exp(-\lambda\bar{x}_{RU}),\hskip
5.69054ptP_{PCM}=1-exp(-\lambda(\bar{x}_{RU}+W_{RU})),$

$\bar{x}_{RU}$ is the time to read an RU and $W_{RU}$ is the mean waiting time
in the queue for rebuild reads in PCM. $P_{VSM}<P_{PCM}$ since
$\bar{x}_{RU}+W_{RU}>\bar{x}_{RU}$.

Both effects are verified via simulation in Fu et al. 2004a [60], where it is
shown that VSM provides a shorter than rebuild time with PCM fewer external
requests are processed while rebuild processing is in progress.

###  10.11 Rebuild in Heterogeneous Disk Array

Heterogeneous Disk Array - HDA postulates a DAC, which can manage multiple
RAID levels Thomasian and Xu 2011b [238] as shown in Fig. 16 The choice of
RAID1 and RAID5 for Virtual Arrays - VAs is based on their suitability for
given applications, e.g., RAID1 for OLTP and RAID5 for data mining requiring
table scans. The VA width $W$ is selected to limit the physical disk load per
Virtual Disk - VD below a certain percentage of disk bandwidth expressed in
IOPS.

Figure 16:  HDA with four disks and five VAs with different RAID levels: two
RAID1 VAs with 2 disks each, two RAID5 VAs with 3 disks each, and a single
disk referred to as RAID0, since it has no redundancy.

VAs with higher dependability requirements are allocated as RAID$(4+k),k\geq
1$. Variable redundancy levels makes it unnecessary to adopt the highest
redundancy level required by a few VAs to all VAs. In the case of cloud
storage where users are charged for IOs allowing diversity in RAID levels
reduces storage costs.

Given that disks are bandwidth rather than capacity bound the number of
allocations can be increased using the clustered RAID paradigm in Section 6.

The study is concerned with alternative data allocation methods for Virtual
Disks - VDs constituting VAs. Allocations are carried out in degraded mode, as
if one of the VDs of a VA has failed to avoid overload if a disk fails, but in
the case of RAID(4+k) allocations with up to $i\leq k$ VDs can be allowed.

Two dimensions: disk bandwidth and capacity per VD are considered in this
study, based on an improved best-fit allocation algorithm for the HDA to meet
this goal. Capacities are less relevant for HDDs, but would be so if SSDs are
included, and vice versa especially for accesses to small blocks. Note that
even in 2012 a bleak feature was predicted for Flash SSDs and hence SSDs were
not included in this early study.
218218218https://www.usenix.org/conference/fast12/bleak-future-nand-flash-
memory

As far as rebuild processing is concerned given that the disk layout is known
there is no need to read unallocated disk areas. since they can be assumed to
be set to zero and need not participate in rebuild processing, e.g., if 4th
disk fails then the blocks of RAID5 can be reconstructed on Disk 1 by XORing
corresponding blocks on 2nd and 3rd disks in Fig. 16. It is also possible to
prioritize the rebuild processing of VAs used by more critical applications,
e.g., OLTP for e-commerce generates more revenue than data mining.

When RAID(4+k) arrays share space on a broken disk rebuilding of arrays with
smaller $k$ is prioritized to prevent data loss. More specifically the rebuild
of RAID(4+k) with smallest $(k-i)$, where $i$ is the number of its failed VDs,
should be prioritized. Reliability and performance of two HDA configurations
are compared in Section 14.8.

A two level allocation scheme was considered in Thomasian et al. 2005 [226,
225]. Heterogeneous disks but not Flash SSDs were not considered in this
study. The characteristics of disks used in this study are given in Table 18.

Model | Seagate | Seagate | Maxtor
---|---|---|---
Barracuda | Atlas | 10K | 15K
Year | 1997 | 1999 | 2003
Capacity | 2 GB | 9.1 GB | 73 GB
IOPS (4KB) | 74.5 | 12.84 | 1882
IOPS/Capacity | 37,25 | 12.84 | 2.58
Table 18: HDDs used in this study and bandwidth/capacity ratio.

URSA minor cluster based storage in Abd-el-Malek et at. 2005 [2] and IBM’s
RAID Engine and Optimizer - REO project Kenchamana-Hosekote et al. 2007 [119]
have similarities to HDA.

###  10.12 Optimal Single Disk Rebuild in RAID6 Arrays

The rebuild method proposed in the context of RDP is optimal in the number of
accessed pages and balancing disk loads Xiang et al. 2010 [261]. It is
erroneously assumed that symbols are as large as strips. The method was
extended to the EVENODD layout in Xiang et al. 2011 [262], which uses small
symbol sizes like RDP as discussed in Section 2.3.

The method however is applicable to X-code arrays Xu and Bruck 1999 [263],
since it applies coding at strip level Xiang et al. 2014 [264]. A similar
method to minimize page accesses in X-code was proposed in Thomasian and Xu
2011 [237].

Given $N$ disks, which is a prime number, X-code consists of repetitive
segments of $N\times N$ strips. Rows in a segment are indexed as $0:N-1$, rows
$0:N-3$ hold data strips, row $N-2$ holds P diagonal parities with positive
slope, and row $N-1$ Q parities with negative slope, thus the redundancy level
is $2/N$ and each data block is protected by two parity groups, which are
diagonals with $\pm 1$ slopes. hence we have an MDS array since it is shown in
Xu and Bruck [263], where it is shown that recovery is possible for all two
disk failures.

Fig. 17 show the data layouts for $N=7$ columns. $B_{i,j}$ denotes a data
block (strip) at the $i^{th}$ row (stripe) and the $j^{th}$ column (disk). PG
memberships are specified by the number for the corresponding P and Q
parities. The two parities are independent and given that
${\langle{X}\rangle}_{N}\equiv X\ \mbox{mod}\ N$ then $p(i)$ and $q(i)$ for
$0\leq i\leq N-1$ are computed as follows:

$p(i)=B_{N-2,i}=\sum_{k=0}^{N-3}B_{k,{\langle{i-k-2}\rangle}_{N}},\hskip
14.22636ptq(i)=B_{N-1,i}=\sum_{k=0}^{N-3}B_{k,{\langle{i+k+2}\rangle}_{N}}.$

The parities to be updated are determined by the Parity Group - PG to which
the block belongs. The PG size is $N-1=6$ for both parities and either PG can
be accessed to reconstruct a block, so that the load increase in degraded mode
is the same as RAID6. Data recovery with two disk failures in X-code is
investigated in Thomasian and Xu 2011 [237], where it is shown that the load
increase is affected by the distance of two failed disks. A balanced load
increase can be attained by rotating successive $N\times N$ segments.

Row# | $D_{0}$ | $D_{1}$ | $D_{2}$ | $D_{3}$ | $D_{4}$ | $D_{5}$ | $D_{6}$
---|---|---|---|---|---|---|---
0 | $B_{0,0}^{2}$ | $B_{0,1}^{3}$ | $B_{0,2}^{4}$ | $B_{0,3}^{5}$ | $B_{0,4}^{6}$ | $B_{0,5}^{0}$ | $B_{0,6}^{1}$
1 | $B_{1,0}^{3}$ | $B_{1,1}^{4}$ | $B_{1,2}^{5}$ | $B_{1,3}^{6}$ | $B_{1,4}^{0}$ | $B_{1,5}^{1}$ | $B_{1,6}^{2}$
2 | $B_{2,0}^{4}$ | $B_{2,1}^{5}$ | $B_{2,2}^{6}$ | $B_{2,3}^{0}$ | $B_{2,4}^{1}$ | $B_{2,5}^{2}$ | $B_{2,6}^{3}$
3 | $B_{3,0}^{5}$ | $B_{3,1}^{6}$ | $B_{3,2}^{0}$ | $B_{3,3}^{1}$ | $B_{3,4}^{2}$ | $B_{3,5}^{3}$ | $B_{3,6}^{4}$
4 | $B_{4,0}^{6}$ | $B_{4,1}^{0}$ | $B_{4,2}^{1}$ | $B_{4,3}^{2}$ | $B_{4,4}^{3}$ | $B_{4,5}^{4}$ | $B_{4,6}^{5}$
5 | $B_{5,0}^{0}$ | $B_{5,1}^{1}$ | $B_{5,2}^{2}$ | $B_{5,3}^{3}$ | $B_{5,4}^{4}$ | $B_{5,5}^{5}$ | $B_{5.6}^{6}$
6 |  |  |  |  |  |  |

Row# | $D_{0}$ | $D_{1}$ | $D_{2}$ | $D_{3}$ | $D_{4}$ | $D_{5}$ | $D_{6}$
---|---|---|---|---|---|---|---
0 | $B_{0,0}^{5}$ | $B_{0,1}^{6}$ | $B_{0,2}^{0}$ | $B_{0,3}^{1}$ | $B_{0,4}^{2}$ | $B_{0,5}^{3}$ | $B_{0,6}^{4}$
1 | $B_{1,0}^{4}$ | $B_{1,1}^{5}$ | $B_{1,2}^{6}$ | $B_{1,3}^{0}$ | $B_{1,4}^{1}$ | $B_{1,5}^{2}$ | $B_{1,6}^{3}$
2 | $B_{2,0}^{3}$ | $B_{2,1}^{4}$ | $B_{2,2}^{5}$ | $B_{2,3}^{6}$ | $B_{2,4}^{0}$ | $B_{2,5}^{1}$ | $B_{2,6}^{2}$
3 | $B_{3,0}^{2}$ | $B_{3,1}^{3}$ | $B_{3,2}^{4}$ | $B_{3,3}^{5}$ | $B_{3,4}^{6}$ | $B_{3,5}^{0}$ | $B_{3,6}^{1}$
4 | $B_{4,0}^{1}$ | $B_{4,1}^{2}$ | $B_{4,2}^{3}$ | $B_{4,3}^{4}$ | $B_{4,4}^{5}$ | $B_{4,5}^{6}$ | $B_{4.6}^{0}$
5 |  |  |  |  |  |  |
6 | $B_{6,0}^{0}$ | $B_{6,1}^{1}$ | $B_{6,2}^{2}$ | $B_{6,3}^{3}$ | $B_{6,4}^{4}$ | $B_{6,5}^{6}$ | $B_{6,6}^{6}$

Figure 17:  X-code array with $N=7$ disks with parity group for
$p(i)=B(5,i),0\leq i\leq 6$ with slope=+1 and parity group for
$q(i)=B(6,j),0\leq i\leq 6$ at row 6 with slope=-1.

####  10.12.1 Optimizing Storage Allocation

File migration between disks and archival storage is studied in A. J. Smith
1981 [211] and it is shown that algorithms based on both file size and time
since last use work best. Miss ratios are compared with page replacement
algorithms such as P. J. Denning’s Working Set.
https://denninginstitute.com/pjd/PUBS/Starting.html Data migration policies
are reviewed here. 219219219\https://en.wikipedia.org/wiki/Data_migration

ExaPlan uses a queueing model for a given budget and workload to determine
both the data-to-tier assignment and the number of devices in each tier that
minimize the system’s mean response time Iliadis et al. 2017 [103]. IBM’s
Hierarchical Storage Management - HSM moves data both horizontally across
disks to balance loads, but also vertically from slower to faster devices and
vice-versa.
220220220https://en.wikipedia.org/wiki/Hierarchical_storage_management

Heuristic algorithms to improve overall storage performance and throughput do
not work well for all conditions and workloads. There are numerous tunable
parameters for users with continually optimizing their own storage systems and
applications. Storage systems are usually responsible for most latency in I/O
dominated applications, and the effect of small I/O latency improvement can be
significant.

Machine learning - ML techniques learn patterns and generalize from them, and
enable optimal solutions that adapt to changing workloads. KML is applied to
optimal readahead and read size values in Network File System - NFS Akgun et
al. 2023 [3] 221221221https://en.wikipedia.org/wiki/Network_File_System KML
consumes little OS resources, adds negligible latency, and yet can learn
patterns that can improve I/O throughput by as much as 2.3x or 15x in two
cases. KML is ti be extended with reinforcement learning Kaelbling et al. 1996
[164].

Adaptive Intelligent Tiering - AIT described in Pang et al. 2023 [166]
dynamically adapts to the changes of storage accesses by the running
applications using a deep learning model to generate a set of candidate
movements and employs a reinforcement learning mechanism to further refine the
candidates. Simulations of a 3-tier system show that the proposed scheme
enhances workload performance up to 85% on storage traces with a wide range of
characteristics.

###  10.13 An Alternate Method to Estimate Rebuild Time∗

Rebuild time is estimated as the ratio of utilized disk capacity ($U$) and the
mean rebuild rate ($b_{d}$). Memory bandwidth is not expected to affect RAID5
rebuild time, as shown in Section 5.2 of Dholakia et al. 2008 [45].

Zoning subdivides disk tracks into $I$ bands with the same number of sectors,
so that for small variation of track circumference the number of sectors is
not varied track to track. There are $n_{i}$ tracks with $c_{i}$ sectors per
track in the $i^{th}$ band. The data portion of the sector ($s_{sector}$) was
increased from 512B to 4096 B circa 2010. The mean disk transfer rate is:

$t_{d}\approx\sum_{i=1}^{I}n_{i}\times c_{i}\times s_{sector}/T_{R}.$

Given that the RU size is $s_{RU}$ the transfer time per RU is $s_{RU}/t_{d}$,
but access to the first RU according to VSM requires a seek ($\bar{x}_{s}$)
plus rotational latency estimated as follows. Let $f$ denote the size of RU as
a fraction of tracks size, then if the R/W head lands inside the RU then we
need a full disk rotation to transfer an RU ($f\times T_{R}$) and otherwise
the cost is $(1-f)^{2}T_{R}/2$, hence:

$\bar{x}_{\ell}=f\times T_{R}+(1-f)^{2}T_{R}/2=(1+f^{2})T_{R}/2$

Track or cylinder skew should be added if track or cylinder boundaries are
traversed. For large RU sizes track and cylinder skew Jacob et al. 2008 [108]
have a negligible effect.

The number of bytes transferred per cycle is the product of the number of RUs
transferred ($\bar{n}_{RU}$) and RU size $(s_{RU})$. The cycle time is the sum
of interarrival time ($1/\lambda$), plus the delay cycle for processing
external disk requests given by Eq. (27):

$\bar{T}_{dc}=\frac{\bar{x}_{disk}+\bar{v}_{r}}{1-\rho}$

$\displaystyle b_{d}=\frac{\bar{n}_{RU}\times
s_{RU}}{\bar{T}_{dc}+\bar{x}_{seek}+\bar{x}_{\ell}+\bar{n}_{RU}\times\bar{x}_{RU}}$
(40)

where $\bar{x}_{RU}=\bar{s}_{RU}/t_{d}$. An upper bound to rebuild time can be
obtained by setting $\bar{n}_{RU}=1$, which is also the assumption made in
Dholakia et al. 2008 [45]. The number of consecutively transferred RUs with no
intervening seeks can be derived as follows.

$p_{n}=(1-e^{-\lambda x_{RU}})(e^{-\lambda x_{RU}})^{n-1},n\geq 1\mbox{ hence
}\bar{n}_{RU}=(1-e^{-\lambda s_{RU}})^{-1}$

In the case of ZBR outer disk tracks have higher capacities and a small
fraction of disk tracks are utilized for critical data, since this allows
short strocking. With a fraction $U$ of disk capacity: $C_{d}$ utilized
rebuild time is:

$\displaystyle T_{rebuild}=UC_{d}/b_{d}.$ (41)

Dholakia et al. 2008 [45] estimates $b_{d}$ in Eq. (13) as follows:

$b_{d}=s_{req}/(1/r_{io}+s_{req}/t_{d}),$

where $r_{io}$ is the request rate and $s_{req}$ is the request size.

###  10.14 Performance Studies of Log-structured File Systems - LFS

A performance study of LFS in McNutt 1994 [142] postulates a directory for the
most recent copy of objects written more than once. A mathematical model of
garbage collection is used to show how load relates to the utilization of
storage and the amount of update locality present in the pattern of updates. A
realistic statistical model of updates, based upon trace data analysis is
applied and alternative policies are examined for determining which areas to
target.

The following relationship for LSA is quoted in Menon 1995 [147]

$\mbox{ASO}=(1-\mbox{BSO})/\mbox{ln}(1-\mbox{BSO}),\hskip
14.22636pt\mbox{e.g., if ASO=0.6 then BSO=0.324}.$

where Average Segment Occupancy - ASO and lowest or Best Segment Occupancy -
BSO. Two types of write hits are considered: (1) to dirty blocks in NVRAM
caches, (2) to clean pages. Given a request rate $K$ the fraction of request
to clean pages is $C$ and the fraction of writes to dirty ages is $D$.

The reading of segments is attributable to garbage collection and only a
fraction BSO of segment writing is attributable to garbage collection and the
rest to destage. The read miss rate is $K\times B$, the miss rate due to write
hits in clean pages is $K\times C$ and the destage rate due to write misses
$K\times D$.

Given that $X$ blocks are destaged together and $Z$ is the segment size in
tracks the rate at which dirty blocks are created in the NVS caches is
$K(C+D)/X$. It is then argued that segments are written and read at rate
$(KC+KD/(X(1-BSO)Z)$ The effect of data compression and seek affinity is
investigated in this study. It is observed that LSA outperforms RAID5 in
throughput, but offers higher response times.

A new algorithm for choosing segments for garbage collection in LFS and LSA
proposed in Menon and Stockmeyer 1998 [148] is compared against a greedy and
cost-benefit algorithms via simulation. Segments which have been recently
filled by writes are not to be considered for garbage collection until they
achieve a certain age-threshold, because as time progresses such segments are
less likely to be updated and this makes old segments eligible for garbage
collection. The algorithm chooses segments that yield the most free space.

###  10.15 Performance Analysis of a Tape Library System

An analytical model to evaluate the performance of a tape library system is
presented in Iliadis et al. 2016 [102]. Earlier studies of this topic is are
reviewed.

The analysis takes into account the number of cartridges and tape drives as
well as different mount/unmount policies to determine the mean waiting time
for tapes. The accuracy of the model is confirmed by validation against
measurements.

A tape library consists of tape drives, robot arms, a storage rack for the
tape cartridges, and a cartridge control unit. To serve a request, a robot arm
fetches the appropriate tape cartridge from the storage rack and delivers it
to a free tape drive. The tape drive control unit mounts the tape, positions
the head to the desired file and then transfers its data. To free a tape
drive, a robot arm unmounts the tape cartridge and returns it to the storage
rack. Tape read/write requests contain the cartridge id, the position of the
data block in the cartridge, and its size.

Requests submitted for cartridges are queued and served according to a
scheduling policy. A hierarchical scheduling algorithm is used to ensure
fairness and avoiding starvation as follows: Upper level: Cyclic or round-
robin scheduling among the queues (mounting cartridges). Lower level: A FCFS
policy for serving requests within a queue (reading from a mounted cartridge).

When all requests of a cartridge are served (exhaustive service), and there
are still pending requests at some other, non-mounted cartridge, an unused
cartridge is unmounted and another cartridge with pending requests is mounted.
If, however, there are no other pending requests to any other non-mounted
cartridge, the cartridge can either remain mounted in anticipation of future
requests or be unmounted so as to save time when future requests arrive for
other non-mounted cartridges. Two mount/unmount policies deployed in this
context are: 1\. Always-Unmount - AU: A tape cartridge is immediately
unmounted upon completion of all pending requests for it in anticipation of
the next request arriving for another non-mounted cartridge. 2\. Not-Unmount -
NU: A tape cartridge remains mounted upon completion of all pending requests
for it in anticipation of the next request arriving for this same currently
mounted, but idle cartridge.

The performance analysis of the resulting polling system relies on state-
dependent queues Takagi 1986 [215]. Parameters considered in this study are
based on Table II in Iliadis et al. 2021 of the IBM TS4500 tape library in
Table 19 222222222https://www.gotomojo.com/wp-content/uploads/2019/08/IBM-
TS4500-Tape-Library-Data-Sheet.pdf

Parameter | Values | Definition
---|---|---
c | 3200 | number of cartridges
d | 32 | number of tape drives
a | 1,2 | number of arms
R | 5 s (fixed) | robot transfer time
$t_{L}$ | 24 s (fixed) | load ready time
$\bar{t}_{R}$ | 59 s | mean rewind time
$\bar{t}_{U}$ | 24 s | unload ready time
$s_{max}$ | 118 s | maximum seek time
$\bar{Q}$ | 843 MB | mean request size
$\overline{Q^{2}}$ | 2.8 GB | standard deviation
$b_{w}$ | 360 MB/s | bandwidth
$n$ | 100 | # cartridges per tape drive
$M$ | 20 s (fixed) |  mount time $M=R+t_{L}$
$\bar{U}$ | 88 s |  mean unmount time ($\bar{U}=\bar{t}_{R}+t+U+R$)
$\bar{t}_{T}$ | 2.34 |  mean transfer time ($t_{T}=\bar{Q}/b_{w}$
Table 19:  Parameter values according to Table II in the paper.

Predicting the performance of a tape library system is key to efficiently
dimensioning it. The effect of two mount/unmount policies was analytically
assessed. It was observed that for light loads, the AU - Always-Unmount policy
yields a mean delay that is lower than that of the NU - Not-Unmount policy,
with the difference becoming negligible as the load increases. The effect of
the number of robot arms was assessed by means of simulation. It is shown that
given fast robot arms multiple arms do not provide a significant performance
improvement, but multiple arms may be necessary to attain higher availability.
The analysis has been extended in Iliadis et al. 2021 [105]

##  11 Appendix II: RAID Reliability Analysis

11.1 RAID5 reliability analysis. 3.4 Reliability of 2D square- and 3D cube-
RAID. 11.2. System reliability metrics.
11.3. Clustered versus declustered data placements.
11.4∗. RAID5/6 reliability analysis with unrecoverable sector errors.
11.5∗. Disk scrubbing and Intra-Disk Redundancy to deal with Latent Sector
Errors - LSEs.
11.6. Schemes to implement IDR.
11.7. IDR’s effect on disk performance.
11.8. Comparison of disk scrubbing and IDR with IPC.
11.9. Combining scrubbing with SMART and Machine Learning.
11.10 Fail-slow faults in drives and their detection.

###  11.1 RAID5 Reliability Analysis