# Overview of Mass Storage Structure
* 現代電腦的大部分次級存儲是硬碟驅動器 (HDD) 和非揮發性記憶體 (NVM) 裝置。
* 硬碟驅動器(HHDS)透過移動的讀寫磁頭在旋轉的磁性塗層材料的碟片上進行讀寫操作
* 驅動器以每秒60到250次的速度旋轉
* 傳輸率(Transfer rate)是數據在驅動器和電腦之間流動的速度
* 定位時間(Positioning time)（隨機存取時間(random-access time)）是將磁碟臂移動到所需磁柱（尋道時間(seek time)）以及所需扇區旋轉到磁頭下方（旋轉延遲(rotational latency)）的時間
* 磁頭碰撞(Head crash)是指磁頭與磁碟表面接觸的情況 -- 這很糟糕
* 磁碟可以是可移除的

## Moving-head Disk Mechanism

## Hard Disk Drives
* 碟片的尺寸範圍從0.85英寸到14英寸（歷史上）
* 常見的尺寸為3.5英寸、2.5英寸和1.8英寸
* 每個驅動器的容量範圍從30GB到3TB
* 性能
* 傳輸率（理論值）為6 Gb/sec
* 有效傳輸率（實際）為1 Gb/sec
* 尋道時間從3毫秒到12毫秒——桌面驅動器常見為9毫秒
* 平均尋道時間基於1/3磁軌測量或計算得出
* 延遲基於主軸速度
* 1 / (轉速 / 60) = 60 / 轉速
* 平均延遲 = ½延遲（轉速範圍為5,400到15,000 RPM）

## Hard Disk Performance
* 存取延遲 = 平均存取時間 = 平均尋道時間 + 平均延遲
* 對於最快的磁碟：3毫秒 + 2毫秒 = 5毫秒
* 對於較慢的磁碟：9毫秒 + 5.56毫秒 = 14.56毫秒
* 平均I/O時間 = 平均存取時間 + （傳輸量 / 傳輸速率）+ 控制器開銷
* 例如，傳輸一個4KB區塊在7200轉速的磁碟上，平均尋道時間為5毫秒，1Gb/sec的傳輸速率，控制器開銷為0.1毫秒：
* 5毫秒 + 4.17毫秒 + 0.1毫秒 + 傳輸時間
* 傳輸時間 = 4KB / 1Gb/s * 8Gb / GB * 1GB / 1024^2KB = 32 / 1024^2 = 0.031毫秒
* 4KB區塊的平均I/O時間 = 9.27毫秒 + 0.031毫秒 = 9.301毫秒

## The First Commercial Disk Drive
* 1956年，IBM RAMDAC電腦包括了IBM Model 350磁碟存儲系統
* 5百萬（7位元）字元
* 50片24英寸的碟片
* 存取時間 < 1秒

## Nonvolatile Memory Devices
* 如果像磁碟驅動器一樣，則稱為固態硬碟（SSDs）
* 其他形式包括USB隨身碟（拇指碟、閃存碟）、DRAM磁碟替代品、主板上的表面貼裝裝置，以及智能手機等設備中的主存儲
* 可能比硬碟驅動器（HDDs）更可靠 -> no moving parts
* 每MB價格更昂貴
* 壽命可能較短，需要謹慎管理
* 容量較小
* 但速度更快
* 資料總線可能過慢 -> 例如，直接連接到PCI
* 沒有移動部件，因此沒有尋道時間或旋轉延遲

* 具有一些挑戰性的特徵：
* 以“頁”增量讀取和寫入（類似扇區），但不能就地覆蓋
* 必須先擦除，而且擦除是以更大的“塊”增量進行
* 擦除次數有限，大約只能擦除100,000次，之後會磨損
* 壽命以每日驅動器寫入次數(drive writes per day)（DWPD）衡量
* 一個1TB的NAND硬碟，額定5 DWPD，預計在保修期內每天可寫入5TB而不會失效

## NAND Flash Controller Algorithms
* 由於不能覆蓋寫入，頁面最終會混合有效和無效數據
* 為了追蹤哪些邏輯塊是有效的，控制器維護一個閃存轉換層（FTL）表
* 還實現了垃圾回收（GC）來釋放無效頁面的空間
* 分配過度配置的空間來為垃圾回收提供工作空間
* 每個存儲單元都有壽命，因此需要進行磨損均衡（Wear Leveling），以確保所有單元被均等寫入
=>具有有效頁和無效頁的 NAND 區塊
## Volatile Memory
* DRAM經常用作大容量存儲設備
* 雖然技術上不是次級存儲，因為是易失性的，但可以有文件系統，可以像非常快速的次級存儲一樣使用
* RAM驅動器（有許多名稱，包括RAM磁碟）作為原始塊設備存在，通常格式化為文件系統
* 電腦通過RAM進行緩衝和緩存，那麼為什麼還需要RAM驅動器呢？
* 緩存和緩衝區由程式設計師或操作系統分配
* 而RAM驅動器允許用戶使用標準文件操作將數據放入內存中進行臨時保管
* 存在於所有主要操作系統中
* Linux的/dev/ram，macOS的diskutil創建它們，Linux的/tmp文件系統類型為tmpfs
* RAM驅動器用作高速臨時存儲
* 程式可以通過讀寫RAM驅動器快速共享大量數據

## Magnetic Tape

## Disk Attachment
* 主機連接存儲通過I/O端口訪問I/O總線
* 有多種總線可用，包括高級技術附件（ATA）、串行ATA（SATA）、外部SATA（eSATA）、串行附加SCSI（SAS）、通用串行總線（USB）和光纖通道（FC）。
* 最常見的是SATA
* 由於NVM比HDD快得多，為NVM設計了一種新的快速接口，稱為NVM Express（NVMe），直接連接到PCI總線
* 數據傳輸由稱為控制器（或主機總線適配器，HBA）的特殊電子處理器完成
* 主控制器位於總線的計算機端，設備控制器位於設備端
* 計算機使用內存映射I/O端口將命令放置在主控制器上
* 主控制器將消息發送到設備控制器
* 數據通過DMA（直接存儲器存取）

## Address Mapping
* 磁碟驅動器被視為大型的一維邏輯塊數組，其中邏輯塊是傳輸的最小單位
* 低級格式化在物理媒體上創建邏輯塊
* 邏輯塊的一維數組被映射到磁碟的扇區中
* 扇區0是最外層柱面上第一個軌道的第一個扇區
* 映射按順序進行，首先是該軌道上的扇區，然後是該柱面中的其他軌道，然後是從最外層柱面到最內層柱面的其他柱面
* 邏輯到物理地址應該很容易
* 除了壞扇區
* 通過恆定角速度實現的軌道上的扇區數不是固定的，這會影響映射

## HDD Scheduling
* 作業系統負責有效地使用硬體，對於磁碟驅動器來說，這意味著具有快速的存取時間和磁碟帶寬
* 最小化尋道時間
* 尋道時間約等於尋道距離
* 磁碟帶寬是傳輸的總字節數除以從服務的第一個請求到最後一次傳輸完成的總時間

## Disk Scheduling
* 磁碟I/O請求的來源有很多
* 操作系統
* 系統進程
* 用戶進程
* I/O請求包括輸入或輸出模式、磁碟地址、記憶體地址、要傳輸的扇區數量
* 操作系統會針對每個磁碟或裝置維護一個請求佇列
* 空閒的磁碟可以立即處理I/O請求，繁忙的磁碟則需要將工作排隊
* 當佇列存在時，優化算法才有意義
* 過去，操作系統負責佇列管理和磁碟驅動器磁頭調度
* 現在，這些功能已內建於存儲裝置和控制器中
* 只需提供邏輯區塊地址（LBA），並處理請求排序
* 以下描述他們使用的一些算法
* 注意，磁碟控制器有小型緩衝區，並且可以管理不同“深度”的I/O請求佇列
* 有幾種算法可以用來安排磁碟I/O請求的處理
* 對一個或多個磁碟片進行分析是適用的
* 我們用一個請求佇列（0-199）來說明調度算法：98, 183, 37, 122, 14, 124, 65, 67
* 磁頭指針在53位置

## FCFS
示例顯示磁頭總共移動了640個磁柱

## SSTF
從當前磁頭位置選擇具有最小尋道時間的請求。
SSTF排程是SJF排程的一種形式；可能會導致某些請求饑餓。
例示顯示總共移動了236個磁柱

## SCAN
* 磁碟臂從磁碟的一端開始，向另一端移動，處理請求，直到它到達磁碟的另一端，然後磁頭移動方向會反轉，並繼續處理請求。
* SCAN演算法有時被稱為電梯算法
* 例示顯示總共移動了208個磁柱
* 但請注意，如果請求均勻分佈，則相對較少的請求會立即出現在磁頭前面，因為這些磁柱最近已被服務。最大密度在磁碟的另一端。這些請求已經等待了很長時間

## C-SCAN
* 提供比SCAN更加均勻的等待時間
* 當磁頭移動從磁碟的一端到另一端時，它會在途中處理請求
* 當它到達另一端時，立即返回到磁碟的開始，但在返回行程上不處理任何請求
* 將磁柱視為循環列表，從最後一個磁柱環繞到第一個磁柱
* 總磁柱數是多少？

## C-LOOK
* C-SCAN 版本
* 磁臂只會移動到每個方向的最後一個請求位置，然後立即反轉方向，而不是先一路移動到磁碟的末端

## Selecting a Disk-Scheduling Algorithm
* SSTF是常見的，並且具有自然吸引力。
* SCAN和C-SCAN在系統對磁碟的負載較重時表現更好。
* 較少的饑餓，但仍然可能發生。
* 為了避免饑餓，Linux實現了截止時間調度器。
* 保持獨立的讀取和寫入佇列，優先處理讀取。
* 因為進程更有可能在讀取時阻塞而不是寫入時。
* 實現了四個佇列：2個讀取和2個寫入。
* 按LBA順序排序的1個讀取和1個寫入佇列，實質上實現了C-SCAN。
* 按FCFS順序排序的1個讀取和1個寫入佇列。
* 所有I/O請求按批次發送，按照該佇列的順序排序。
* 每個批次後，檢查是否有任何請求的FCFS年齡大於配置的年齡（默認為500毫秒）- 如果是，則選擇包含該請求的LBA佇列進行下一批次的I/O。
* 在RHEL7(Red Hat Enterprises Linux)中，還提供了NOOP(NO Operation Performed)和完全公平佇列調度器（CFQ），默認值因存儲設備而異。

## NVM Scheduling
* 沒有磁碟磁頭或旋轉延遲，但仍有優化的空間。
* 在RHEL 7中使用NOOP（無排程），但相鄰的LBA請求會合併。
* NVM在隨機I/O方面表現最佳，HDD在順序I/O方面表現最佳。
* 當順序訪問的數據接近讀/寫頭時，吞吐量可以類似。
* 每秒輸入/輸出操作（IOPS）與NVM相比要高得多（數十萬比數百）。
* 寫入NVM比讀取慢，降低了這一優勢。
* NVM設備的寫入性能取決於設備的填充程度和“磨損”程度。
* 但寫入放大（一次寫入，導致垃圾收集和多次讀/寫）可能會降低性能優勢。

## Error Detection and Correction
* 許多計算機的基本方面（記憶體、網絡、存儲）
* 錯誤檢測用於確定是否發生了問題（例如位翻轉）
* 如果檢測到，可以停止操作
* 檢測通常通過奇偶校驗位進行
* 記錄設定為 1 的位元組中的位數是偶數（奇偶校驗 = 0）還是奇數（奇偶校驗 = 1）。
* 奇偶校驗是一種校驗和的形式-使用模算術計算、存儲和比較固定長度詞的值
* 網絡中常見的另一種錯誤檢測方法是循環冗余校驗（CRC），它使用哈希函數檢測多位錯誤
* 錯誤更正碼（ECC）不僅可以檢測，還可以糾正一些錯誤
* 可糾正的軟錯誤，檢測到但無法糾正的硬錯誤

## Storage Device Management
* 低階格式化，或稱為物理格式化-將磁盤劃分為磁區，磁盤控制器可以讀寫
* 每個磁區可以包含標頭信息、數據和錯誤校正碼（ECC）
* 通常每個磁區可容納512字節的數據，但可以進行選擇
* 為了將磁盤用於存儲文件，操作系統仍然需要在磁盤上記錄自己的數據結構
* 將磁盤分割為一個或多個柱面組，每個柱面組視為一個邏輯磁盤
* 邏輯格式化或“建立文件系統”
* 為了提高效率，大多數文件系統將數據區塊分組成簇
* 磁盤I/O以區塊為單位進行
* 文件I/O以簇為單位進行

* 根分區包含操作系統，其他分區可以容納其他操作系統、其他文件系統，或者是原始分區
* 在啟動時掛載
* 掛載檔案系統是指使檔案系統可供系統和使用者使用
* 其他分區可以自動或手動掛載
* 在掛載時，檢查文件系統的一致性
* 所有元數據是否正確？
* 如果不正確，則修復它，然後重試
* 如果是，則將其添加到掛載表中，並允許訪問
* 引導區塊可以指向引導卷或包含足夠代碼的引導程序集區塊，以知道如何從文件系統加載內核
* 或者是用於多操作系統引導的引導管理程序

* 對於希望自行進行區塊管理、避免操作系統介入的應用程序（例如數據庫），提供了原始磁盤訪問。
* 引導區塊初始化系統
* 引導加載程序存儲在ROM、固件中
* 完整的引導程序存儲在設備上的引導區塊中的固定位置。
* 引導程序能夠從設備中加載整個操作系統並啟動操作系統運行。
* 使用像扇區保留這樣的方法來處理壞塊

## Swap-Space Management
* 用於在DRAM不足以容納所有進程時，將整個進程（交換）或頁面（分頁）從DRAM移動到二級存儲
* 操作系統提供交換空間管理
* 次級存儲比DRAM慢，因此優化性能非常重要
* 通常可能有多個交換空間-減少對任何給定設備的I/O負載
* 最好有專用設備
* 可以是原始分區中的原始分區，也可以是文件系統中的文件（以方便添加）
* 在Linux系統上進行交換的數據結構:

## Storage Attachment
* 計算機通過三種方式訪問存儲
* 主機連接
* 網絡連接
* 雲端
* 通過本地I/O端口進行主機連接，使用多種技術之一
* 若要連接多個設備，可使用USB、FireWire、Thunderbolt等存儲匯流排
* 高端系統使用光纖通道（FC）
* 使用光纖或銅電纜的高速串行架構
* 多個主機和存儲設備可以連接到FC網絡

## Network-Attached Storage
* 網絡連接存儲（NAS）是通過網絡而不是本地連接（例如匯流排）提供的存儲
* 遠程連接到文件系統
* NFS和CIFS（通用互聯網文件系統）是常見的協議
* 通常通過主機和存儲之間的遠程過程調用（RPC）在IP網絡上使用TCP或UDP實現
* iSCSI協議使用IP網絡來傳輸SCSI協議
* 遠程連接到設備（塊）
* 主機可以將它們的存儲處理為直接附加的存儲

## Cloud Storage
* 與NAS類似，提供了通過網絡訪問存儲的功能
* 與NAS不同，它通過互聯網或廣域網絡（WAN）連接到遠程數據中心
* NAS被呈現為另一個文件系統，而雲存儲基於API，程序使用API提供訪問
* 例如Dropbox、Amazon S3、Microsoft OneDrive、Apple iCloud
* 使用API是因為延遲和故障情況（NAS協議不適用）（NAS被設計用於局域網，其延遲比廣域網絡低，且更不容易失去連接）

## Storage Array
* 可以直接連接磁盤或磁盤陣列
* 避免了使用網絡帶寬的NAS缺點
* 存儲陣列有控制器，為附加的主機提供功能
* 連接主機到陣列的端口
* 內存，控制軟件（有時是NVRAM等）
* 數個到數千個磁盤
* RAID，熱備用，熱插拔(hot swap)（稍後討論）
* 共享存儲 -> 更高效
* 一些文件系統中的功能
* 快照、克隆、薄虛擬化、複製、重復消除等

## Storage Area Network
* 常見於大型儲存環境中
* 多台主機連接到多個儲存陣列 – 靈活
* SAN是一個或多個儲存陣列
* 連接到一個或多個光纖通道交換器或InfiniBand(IB)網絡

## RAID Structure
* RAID - 廉價磁碟冗餘陣列
* 通過多個磁盤驅動器提供冗餘性以增強可靠性
* 冗餘資訊儲存在多個磁碟機上
* 增加故障間隔平均時間
* 一個磁碟需要 100,000 小時，100 個磁碟將需要 1,000 小時......高！
* 平均修復時間 - 替換故障驅動器並恢復其上的數據所需的時間（平均）
* 基於上述因素的平均數據丟失時間
* 如果鏡像磁盤獨立失敗，考慮具有1300,000故障平均時間和10小時平均修復時間的磁盤
* 數據丟失的平均時間是100, 0002 /（2 10）= 500 10的6小時，或者是57,000年！
* 經常與NVRAM結合以提高寫入性能
* 多個磁盤合作工作的幾種磁盤使用技術改進

## Improvement in Performance via Parallelism
* 通過鏡像，讀取請求的處理速率加倍。
* 通過多個驅動器，數據條帶化可以改進傳輸速率。
* 位級條帶化：數據條帶化包括將每個字節的位拆分到多個驅動器上。例如：八個驅動器的陣列將每個字節的第i位寫入驅動器i。
* 每次訪問可以同時讀取八倍的數據，與單個驅動器相比。
* 條帶化不一定需要在位級進行。在塊級條帶化中，文件的塊被分散到多個驅動器上。
* 兩個主要目標：
* 通過負載平衡來增加多個小訪問的吞吐量。
* 減少大型訪問的響應時間。

## RAID
* 磁盤條帶化使用一組磁盤作為一個存儲單元
* RAID被分為六種不同的級別
* RAID方案通過存儲冗餘數據來提高性能和存儲系統的可靠性
* 鏡像或影子（RAID 1）保存每個磁盤的副本
* 條帶鏡像（RAID 1+0）或鏡像條帶（RAID 0+1）提供高性能和高可靠性
* 塊間奇偶校驗（RAID 4、5、6）使用的冗餘性較少
* 如果存儲陣列內的RAID失敗，則存儲陣列內的RAID仍然可能失敗，因此數據之間的自動複製在陣列之間是常見的
* 經常情況下，會留下少量的熱備用磁盤未分配，自動替換失敗的磁盤，並將數據重建到它們上面

## RAID Levels

## RAID (0 + 1) and (1 + 0)

## Other Features
* 無論RAID實施在何處，都可以添加其他有用的功能
* 快照是在一組變化發生之前（即在某一時間點）的文件系統的視圖
* 詳情請參見第12章
* 複製是在不同站點之間自動複製寫入的操作
* 用於冗餘和災難恢復
* 可以是同步或異步的
* 熱備用磁盤是未使用的磁盤，如果一個磁盤失敗，RAID生產將自動使用它來替換失敗的磁盤，並在可能的情況下重建RAID集合
* 減少平均修復時間

## Extensions
* RAID可以防範物理媒體錯誤，但無法防範其他硬體和軟體錯誤。
* 例如：指向檔案或檔案結構內的指標可能是錯誤的。在完整寫入或其他進程中意外寫入檔案系統的結構
* Solaris ZFS對所有數據和元數據添加校驗和
* 校驗和與對象的指針一起保存，以檢測對象是否正確且是否發生變化
* 可以檢測和糾正數據和元數據的損壞
* ZFS還可以移除卷和分區
* 磁盤分配在池中
* 具有池的文件系統共享該池，使用和釋放空間就像malloc（）和free（）記憶體分配/釋放調用一樣

## Traditional and Pooled Storage