Teorija
Ideja RAID-a i kategorije
Redundant array of independent disks (RAID) je skup fizičkih diskova koje operacijski sustav vidi kao jedan logički disk. Podaci se raspodjeljuju po diskovima, a dio kapaciteta može nositi zalihosne podatke iz kojih se nakon kvara diska podaci obnavljaju. Logički disk dijeli se na strip (traka), a stripe (pruga) je skup susjednih traka koji na svaki disk polja stavlja po jednu traku. Stallings razine dijeli u četiri kategorije: striping (raspodjela u trake, RAID 0), mirroring (zrcaljenje, RAID 1), parallel access (paralelni pristup, RAID 2 i 3) i independent access (neovisni pristup, RAID 4, 5 i 6). Razine nisu hijerarhija: svaka je drukčiji kompromis između kapaciteta, otpornosti na kvarove i brzine. Simulator koristi 4-bitne trake, pa se svaki izračun može provjeriti ručno.
The idea of RAID and its categories
A redundant array of independent disks (RAID) is a set of physical disk drives viewed by the operating system as a single logical drive. Data are distributed across the disks, and part of the capacity can hold redundant information from which the data are recovered after a disk failure. The logical disk is divided into strips, and a stripe is a set of logically consecutive strips that puts one strip on each disk of the array. Stallings divides the levels into four categories: striping (RAID 0), mirroring (RAID 1), parallel access (RAID 2 and 3) and independent access (RAID 4, 5 and 6). The levels are not a hierarchy: each is a different trade-off between capacity, fault tolerance and speed. The simulator uses 4-bit strips, so every calculation can be checked by hand.
RAID 0 i RAID 1
RAID 0 samo raspodjeljuje trake redom po diskovima (traka k je na disku k mod D), pa više zahtjeva može ići na različite diskove istodobno. Zalihosti nema: kvar jednog diska gubi svaku D-tu traku, kao u scenariju „RAID 0: bez zalihosti”. RAID 1 svaku traku drži na dva diska; čitanje može ići s bilo koje kopije, pisanje ide na obje, a nakon kvara kopija preuzima čitanja i služi za obnovu. Cijena je polovica kapaciteta.
RAID 0 and RAID 1
RAID 0 only distributes the strips across the disks in order (strip k is on disk k mod D), so several requests can go to different disks at the same time. There is no redundancy: the failure of one disk loses every D-th strip, as in the scenario “RAID 0: no redundancy”. RAID 1 keeps each strip on two disks; a read can be served from either copy, a write goes to both, and after a failure the copy takes over the reads and serves the rebuild. The cost is half of the capacity.
RAID 2 i RAID 3: paralelni pristup
Kod paralelnog pristupa svaki zahtjev koristi sve diskove, a trake su vrlo male (u simulatoru jedan bit riječi po disku). RAID 2 uz podatkovne bitove sprema Hamming code (Hammingov kod): ovdje f0 = b0 XOR b1 XOR b3, f1 = b0 XOR b2 XOR b3 i f2 = b1 XOR b2 XOR b3 na tri dodatna diska, pa se izgubljeni bit vraća iz jednog kontrolnog bita i ostalih bitova koje on pokriva. RAID 3 koristi bit-interleaved parity (paritet isprepleten po bitovima): samo jedan disk pariteta. Obje razine daju veliku brzinu prijenosa za velike zahtjeve, ali istodobno obrađuju samo jedan zahtjev. Ispravljanje bitnih pogrešaka pri čitanju kod RAID 2 simulator ne prikazuje.
RAID 2 and RAID 3: parallel access
With parallel access every request uses all the disks, and the strips are very small (in the simulator, one bit of a word per disk). In addition to the data bits, RAID 2 stores a Hamming code: here f0 = b0 XOR b1 XOR b3, f1 = b0 XOR b2 XOR b3 and f2 = b1 XOR b2 XOR b3 on three extra disks, so a lost bit is recovered from one check bit and the other bits it covers. RAID 3 uses bit-interleaved parity: a single parity disk. Both levels give a high data transfer rate for large requests, but they serve only one request at a time. The simulator does not show how RAID 2 corrects bit errors on a read.
RAID 4 i RAID 5: paritet po blokovima
Kod neovisnog pristupa trake su veće, a zahtjevi za različite trake poslužuju se neovisno. Block-interleaved parity (paritet isprepleten po blokovima) P je XOR traka pruge; kad disk otkaže, polje radi u degraded mode (degradirani rad): izgubljena traka dobiva se kao XOR ostalih traka i P, a nakon zamjene diska slijedi rebuild (obnova), u simulatoru jedna pruga po taktu. Malo pisanje zahtijeva read-modify-write (čitanje–izmjena–pisanje): čitaju se stara traka i stari P, a novi paritet je P' = P XOR staro XOR novo, pa jedna traka košta 2 čitanja i 2 pisanja; to je small-write penalty (kazna malog pisanja). Pisanje cijele pruge nema tu kaznu: paritet se računa iz novih podataka. Kod RAID 4 svako pisanje ide i na isti disk pariteta, koji postaje usko grlo; RAID 5 koristi rotating parity (rotirajući paritet) i paritet svake pruge sprema na drugi disk.
RAID 4 and RAID 5: block-interleaved parity
With independent access the strips are larger, and requests for different strips are served independently. The block-interleaved parity P is the XOR of the strips of the stripe; when a disk fails, the array runs in degraded mode: a lost strip is computed as the XOR of the other strips and P, and once the disk is replaced, a rebuild follows, in the simulator one stripe per tick. A small write needs a read-modify-write: the old strip and the old P are read, and the new parity is P' = P XOR old XOR new, so one strip costs 2 reads and 2 writes; this is the small-write penalty. A full-stripe write has no such penalty: the parity is computed from the new data. In RAID 4 every write also goes to the same parity disk, which becomes a bottleneck; RAID 5 uses distributed (rotating) parity and stores the parity of each stripe on a different disk.
RAID 6: dva nezavisna koda
RAID 6 uz P sprema i drugi, nezavisni kod Q na još jednom disku, pa podnosi kvar bilo koja dva diska, uz dva diska kapaciteta za zalihost i još veću kaznu malog pisanja (3 čitanja i 3 pisanja). Stallings ne propisuje kod za Q. Simulator koristi Reed–Solomonov kod nad GF(24) s polinomom x4 + x + 1 i g = 2, kao Linux md nad GF(28): Q je XOR umnožaka gi·Di. Kad nedostaju dvije trake x i y, iz P i Q dobivaju se Pxy i Qxy, pa je Dx = (Qxy XOR gy·Pxy) · (gx XOR gy)−1 i Dy = Pxy XOR Dx. Raspored P i Q po prugama u simulatoru jedan je od mogućih. Izvan simulatora ostaju i ugniježđeni RAID (npr. RAID 1+0), vruća rezerva (hot spare) i rupa pisanja (write hole) kod nestanka struje usred pisanja pruge.
RAID 6: two independent codes
In addition to P, RAID 6 stores a second, independent code Q on one more disk, so it survives the failure of any two disks, at the cost of two disks of capacity for redundancy and an even larger small-write penalty (3 reads and 3 writes). Stallings does not prescribe the code for Q. The simulator uses a Reed–Solomon code over GF(24) with the polynomial x4 + x + 1 and g = 2, as Linux md does over GF(28): Q is the XOR of the products gi·Di. When two strips x and y are missing, P and Q give Pxy and Qxy, so Dx = (Qxy XOR gy·Pxy) · (gx XOR gy)−1 and Dy = Pxy XOR Dx. The layout of P and Q over the stripes in the simulator is one of several possible. Nested RAID (e.g. RAID 1+0), the hot spare and the write hole on a power loss in the middle of a stripe write are also left out of the simulator.
Priručna memorija diska
Disk cache (priručna memorija diska) je dio glavne memorije koji drži nedavno korištene blokove diska. Hit (pogodak) poslužuje zahtjev bez pristupa disku, a miss (promašaj) čita blok s diska i izbacuje drugi blok; učinak mjeri hit ratio (omjer pogodaka). LRU izbacuje blok koji se najdulje nije koristio, a LFU blok s najmanjim brojačem referenci. LFU griješi kad blok dobije nalet referenci pa se više ne koristi: visok brojač ga drži u memoriji. Frequency-based replacement (FBR, zamjena na temelju učestalosti) zato stog dijeli na novi i stari dio: pogodak u novom dijelu ne povećava brojač, a izbacuje se najmanji brojač samo iz starog dijela. Stallings opisuje i inačicu s tri dijela: blok koji izađe iz novog dijela ima mali brojač i mogao bi biti izbačen prije nego što ga skupi, pa mu srednji dio daje vremena. U malim primjerima simulatora prednost inačice s tri dijela ne vidi se: rezultat ovisi o veličinama dijelova (scenarij „Slijedno čitanje”). Iste politike zamjene za stranice prikazuje Zamjena stranica, redoslijed zahtjeva za disk Raspoređivanje diska, međuspremnike i DMA Tehnike U/I, a blokove datoteka Datotečni sustav.
Disk cache
A disk cache is a buffer in main memory that holds recently used disk blocks. A hit serves the request without a disk access, and a miss reads the block from the disk and evicts another block; the effect is measured by the hit ratio. LRU evicts the block that has gone unused the longest, and LFU the block with the smallest reference count. LFU goes wrong when a block gets a burst of references and is then not used again: the high count keeps it in memory. Frequency-based replacement (FBR) therefore splits the stack into a new and an old section: a hit in the new section does not increment the count, and the smallest count is evicted from the old section only. Stallings also describes a variant with three sections: a block that leaves the new section has a small count and could be evicted before it builds one up, so a middle section gives it time. In the small examples of the simulator the advantage of the three-section variant does not show: the result depends on the section sizes (scenario “Disk cache: sequential read”). The same replacement policies for pages are shown on the Page replacement page, the order of disk requests on the Disk scheduling page, buffers and DMA on the I/O techniques page, and file blocks on the File system page.
Literatura: Stallings, Operating Systems: Internals and Design Principles, 9. izd., pogl. 11 (11.6 RAID, 11.7 Disk Cache); alternativno Tanenbaum & Bos, Modern Operating Systems, pogl. 5 (5.4.1 Magnetic Disks: RAID) i pogl. 4 (4.4.4 Caching).Reading: Stallings, Operating Systems: Internals and Design Principles, 9th ed., ch. 11 (11.6 RAID, 11.7 Disk Cache); alternatively Tanenbaum & Bos, Modern Operating Systems, ch. 5 (5.4.1 Magnetic Disks: RAID) and ch. 4 (4.4.4 Caching).