ch3 存儲和文件結構

數據庫系統(tǒng)設計與實現SchoolofSoftwareEngineering

HuazhongUniversityofScience&TechnolongyChapter1:存儲和文件結構StorageandFileStructureChapter1:存儲和文件結構存儲介質概述磁盤（MagneticDisks）和快閃存儲器（Flashstorage）RAID第三級存儲（TertiaryStorage）文件組織文件中記錄的組織數據字典存儲物理存儲介質分類數據訪問的速度單位數據的成本可靠性掉電或者系統(tǒng)故障物理損壞存儲可以分為:易失性存儲（volatilestorage）:斷電之后數據丟失，高速緩存（cache）主存（mainmemory）非易失性存儲（non-volatilestorage）:斷電后數據仍然保存閃存（flashmemory）磁盤（magnetic-disk）光學存儲器（opticalstorage:compactdisk、digitalvideodisketc.）磁帶（tapestorage）物理存儲介質高速緩沖存儲器（Cache）最快也最昂貴的存儲介質;易失的;由計算機系統(tǒng)硬件來管理.一般在數據庫系統(tǒng)中不需要考慮cache的存儲管理，但在設計查詢處理的數據結構和算法時，實現者會注意高速緩沖存儲器的影響主存儲器（Mainmemory）讀取速度快(10~100s納秒;1納秒=10–9

秒)通常太小或者比較昂貴而不能用來存放整個數據庫目前廣泛采用的主存儲器可以存放幾個GB的數據；成本每年在穩(wěn)定地下降易失性

物理存儲介質(Cont.)閃存（Flashmemory）

NAND快閃NOR快閃NOR—快閃允許隨機訪問閃存中的單個字，且擁有和主存媲美的讀取速度；

NAND—快閃每次需要讀取整個數據頁（512B~4kB）,類似于磁盤中的扇區(qū)，但NAND快閃擁有更高的存儲容量和性價比。電源關閉或者故障的時候數據可以保存；也作為磁盤存儲器的替代品——固態(tài)驅動器（Solid-StateDrive）和磁盤相比，提供更快的隨機存取，一個數據頁在閃存中1~2微秒可以檢測到，而在磁盤上的隨機訪問則需要5~10毫秒。但閃存具有比磁盤低的傳輸速率20MB/s物理存儲介質(Cont.)問題：固態(tài)驅動器是如何實現的但是寫入較慢(約幾微秒)，而且閃存的頁面不能直接覆蓋，一旦寫入，必須先擦除然后再重寫，并且對閃存頁可以擦除多少次存在限制（100k~1M次之間）；閃存的寫入策略？閃存轉換層：（flashtranslationlayer）通過邏輯頁碼和物理頁碼的映射（轉換表）和損耗均衡在一定程度上解決慢訪問速度和更新次數限制的影響物理存儲介質(Cont.)磁盤（Magnetic-disk）數據存放在盤片表面，表面覆蓋著磁性物質是數據長期存儲的主要介質，通常整個數據庫都存放在磁盤上；為了能夠訪問數據，系統(tǒng)必須先將數據從磁盤上移動到主存；存儲容量到2TB左右（2012）和主存及閃存相比，有更大的存儲容量和更低的的價格磁盤容量差不多以每年50%的速度遞增掉電或者系統(tǒng)故障不會丟失數據也可能發(fā)生硬盤故障，但幾率要小很多物理存儲介質(Cont.)光學存儲器（Opticalstorage）非易失的，數據通過光學的方法存儲在光盤上CD-ROM(640MB)，DVD(4.7to17GB)藍光DVD,Blu-raydisks:27GBto54GBWORM:Write-one,read-manyMultiplewriteversions(CD-RW,DVD-RW,DVD+RW,andDVD-RAM)讀寫速度都要慢于磁盤物理存儲介質(Cont.)磁帶存儲器（Tapestorage）非易失的

—主要應用于備份和歸檔數據；順序訪問

—訪問速度要遠低于磁盤具有很高的存儲容量(40to300GB)可以從磁帶設備中移除，非常適合便宜的歸檔存儲，磁帶很便宜，但磁帶驅動器相對昂貴自動磁帶機（Tapejukeboxes）用于存儲非常巨大的數據集合。存儲設備層次結構基本存儲聯機存儲三級存儲易失性存儲非易失性存儲Fastestmediabutvolatile磁盤（magneticharddisk）（扇區(qū)）（柱面）（讀寫頭）（磁盤臂）（主軸）（磁道）（磁盤臂組件）（盤片）磁盤讀寫頭（Read-writehead）每個盤片（platter）的每一面都有一個讀寫頭緊貼著盤片表面通過讀寫磁性介質來編碼信息每張盤片的表面被劃分為圓形磁道（track）典型的，每面盤片劃分成為50K-100K磁道每條磁道被劃分成為若干扇區(qū)（sectors）

扇區(qū)是讀寫的最小單位.現在典型的磁盤的每個扇區(qū)大小一般是512bytes每條磁道典型的扇區(qū)數目：內側磁道每道約500-1000個扇區(qū)，外側磁道1000-2000個扇區(qū)Toread/writeasector磁盤臂（diskarm）把讀寫頭移動到相應磁道；盤片旋轉使得對應扇區(qū)到讀寫頭的下方柱面（Cylinder）

所有盤片的第i條磁道合在一起成為第i個柱面磁盤(Cont.)早期的磁盤比較容易發(fā)生故障讀寫頭接觸到盤片的表面，掛掉的介質散落于盤片和其它讀寫頭之間，引起整張磁盤的實效目前的磁盤使用一層金屬薄膜作為存儲記錄的介質，不易損壞磁盤控制器（Diskcontroller）–計算機系統(tǒng)和實際的磁盤驅動器硬件之間的接口（interface）.接受高層次的讀寫扇區(qū)的命令移動磁盤臂到對應的磁道用校驗和（checksum）來判斷讀取的數據是否正確如果數據出錯，很有可能讀出數據所計算的校驗和存儲的校驗和不一致執(zhí)行壞扇區(qū)的重映射（remapping）當磁盤初始格式化或者寫一個扇區(qū)時，如果磁盤控制器檢測到壞扇區(qū)，會把這個扇區(qū)在邏輯上映射到另外一個位置，多張磁盤通過一個高速互聯通道連接到計算機系統(tǒng)磁盤接口標準ATA(ATadaptor)rangeofstandards串行ATA(SATA:SerialATA，最新標準是SATAII,SATAIII等)小型計算機互聯系統(tǒng)SCSI(SmallComputerSystemInterconnect)串行附著SCSI(SAS:SerialAttachedSCSI)光纖通道接口（FC:FibrreChannel）磁盤系統(tǒng)磁盤通?？梢酝ㄟ^電纜直接與計算機系統(tǒng)的磁盤接口相連，也可以放置在遠端并通過高速網絡與磁盤控制器相連存儲局域網（StorageAreaNetworks，SAN）,大量的磁盤通過網絡和許多計算機服務器相連RAID網路附加存儲（NetworkAttachedStorage，NAS）通過使用網絡文件系統(tǒng)協議提供文件系統(tǒng)接口提供文件系統(tǒng)接口。磁盤>>磁盤性能的度量訪問時間（Accesstime）–發(fā)出讀寫請求到數據開始傳輸之間的時間.組成:尋道時間（Seektime）–磁盤臂重定位的到正確的磁道所花費的時間.平均尋道時間大約是最長尋道時間的1/2典型的磁盤的尋道時間在4-10毫秒之間。旋轉等待時間（Rotationallatencytime)–扇區(qū)旋轉到讀寫頭下所耗費的時間.平均旋轉等待時間是磁盤旋轉一周時間的1/2.平均旋轉等待時間在2-5毫秒左右（15000-5400r.p.m.)數據傳輸率–從磁盤獲得數據或者或者向磁盤存儲數據的速率目前磁盤系統(tǒng)支持25~100MB每秒的數據最大傳輸率，內側磁道的數據傳輸率明顯低于最大傳輸率一個接口的傳輸率由連接到這個接口的所有磁盤共享SATA:150MB/sec,SATA-II3Gb(300MB/sec)Ultra320SCSI:320MB/s,SAS(3to6Gb/sec)FiberChannel(FC2Gbor4Gb):256to512MB/s磁盤>>磁盤性能的度量平均故障時間（Meantimetofailure(MTTF)–指磁盤無故障連續(xù)運行的時間.大部分磁盤的工作時間3~5年生產商聲稱的平均故障時間是500k~1200k小時的含義？給定1000張新磁盤，如果MTTF是1200k小時的含義是平均在1200個小時內，將會有一張磁盤發(fā)生故障。并非磁盤預計可以連續(xù)工作1200k小時（136年）隨著時間的增加，磁盤故障率會顯著增高。磁盤>>磁盤訪問的優(yōu)化塊（Block）是一個邏輯單元，包含固定數目的連續(xù)扇區(qū)數據在主存和磁盤之間以塊為單位進行傳輸，塊的大小在512字節(jié)到幾KB之間順序訪問&隨機訪問塊大小的影響較小的塊:

較多的傳輸次數較大的塊:可能讀取的塊中只有數據有用；典型塊的大小在4到16KB之間為了提高訪問塊的速度，產生了許多技術：緩沖：從磁盤讀取的塊暫時存儲在內存緩沖區(qū)中，以滿足將來的要求緩沖區(qū)通過OS和數據庫系統(tǒng)共同運作預讀：當一個磁盤塊被訪問時，相同磁道的連續(xù)塊也被讀入到內存緩沖區(qū)，即便沒有針對這些塊的即將來臨的請求適合順序訪問，對隨機訪問不是很有效調度：如果需要把一個柱面上的幾塊從磁盤，可以按照塊經過讀寫頭的順序發(fā)出訪問請求，如果所需的塊在不同的柱面上，則按照使磁盤臂移動最短距離的順序發(fā)出訪問塊的請求是非常有利的磁盤>>磁盤訪問的優(yōu)化(Cont.)磁盤臂調度算法（Disk-arm-schedulingalgorithms）如果所訪問的數據塊在不同的柱面上，則按照使磁盤臂移動最短距離的順序發(fā)出訪問塊的請求是最為有利的。電梯算法（elevatoralgorithm）磁盤>>磁盤訪問的優(yōu)化(Cont.)R1R5R2R4R3R6InnertrackOutertrack磁盤>>磁盤訪問的優(yōu)化(Cont.)文件組織（Fileorganization）–為了減少塊訪問時間，可以按照與預期的數據訪問方式最接近的方式來組織磁盤上的塊。E.g.

如果預計一個文件將順序訪問，那么理想情況下，應該使文件的所有塊存儲在連續(xù)的相鄰柱面上。經過一段時間后，文件可能會被碎片化某些系統(tǒng)提供碎片整理工具，來提高文件的訪問速度。非易失性寫緩沖區(qū)（Nonvolatilewritebuffers）

更新操作密集的數據庫應用的性能，高度依賴于磁盤寫操作的速度。

使用非易失性隨機訪問存儲器（NonVolatileRandom-AccessMemory）Non-volatileRAM:

常用的實現方法是使用備用電池內容在發(fā)生電源故障時不會丟失，當電源恢復時，數據將會被寫回磁盤當數據庫系統(tǒng)（或者OS）請求往磁盤上寫一個塊時，磁盤控制器將這個塊先寫到NV-RAM,然后立即通知操作系統(tǒng)寫操作成功完成當磁盤沒有其它請求或者NV-RAM寫滿時，磁盤控制器將這些數據寫回到磁盤相應的目標位置。從系統(tǒng)崩潰中進行恢復時，NV-RAM中所有緩沖的未完成的操作將寫回到磁盤。磁盤>>磁盤訪問的優(yōu)化(Cont.)日志磁盤（Logdisk）

–一種專門應用于寫順序日志的磁盤和NV-RAM的使用非常相似對日志磁盤的訪問都是順序的，從根本上消除了尋道時間。不需要特定的硬件，比如(NV-RAM)支持日志磁盤的文件系統(tǒng)稱為日志文件系統(tǒng)（JournalingFileSystem)磁盤>>磁盤訪問的優(yōu)化(Cont.)RAID獨立磁盤冗余陣列RAID（RedundantArraysofIndependentDisks）磁盤的組織技術使大量磁盤組織在一起提供統(tǒng)一的磁盤視圖高容量：多張磁盤Web,數據庫，多媒體應用高讀寫速度很多獨立的讀寫操作可以并行的執(zhí)行（parallel）

提供了高可靠性在多張磁盤上存儲冗余信息，一個磁盤的故障不會導致數據的丟失

“I”的含義早期指的是``inexpensive’’，因為可以用多張小且廉價構成的系統(tǒng)替代大而昂貴的磁盤；現在使用RAID是因為更高的可靠性和更高的執(zhí)行效率（更高的帶寬）“I”代表的意思是independent通過冗余提高可靠性可靠性問題：N張磁盤組成的集合中某張磁盤發(fā)生故障的概率比特定的一張磁盤發(fā)生故障的概率要高例如：一張磁盤的MTTF的平均時間是100,000小時(大約11years),那么由100張磁盤組成的陣列發(fā)生故障的平均時間為1000小時(大約41天)。如果只存儲數據的一個拷貝，那么任何一張磁盤故障都將導致大量數據的丟失，因此引入冗余RAID（cont.）通過冗余提高可靠性冗余（Redundancy）–存儲正常情況下不需要的額外信息，這些信息可以在磁盤發(fā)生故障時重建丟失的信息.鏡像（Mirroring）復制沒一張磁盤，一張邏輯磁盤由兩張物理磁盤組成。每次寫操作都在兩張磁盤上進行讀操作可以從任意一張磁盤上進行如果一張磁盤發(fā)生故障，數據可以從另外一張磁盤上讀出。只有在第一張磁盤被修復之前，第二張磁盤也發(fā)生故障，數據才會丟失采用鏡像技術的磁盤平均故障時間依賴于單張磁盤的平均故障時間和平均修復時間例如，如果兩張磁盤發(fā)生故障是相互獨立的（并非完全合理），如果MTTF=100,000小時,平均修復時間是10小時，則鏡像磁盤系統(tǒng)的平均數據丟失時間為100,000×100,000/2*10校驗碼冗余糾錯碼（ECC）內存中每個字節(jié)都有一個奇偶校驗位與之相連，它記錄著這個字節(jié)中為1的比特位的總數是偶數（=0）還是奇數（=1），如果字節(jié)中有一位被破壞了，則字節(jié)的ECC和存儲的ECC就不相匹配，111100000101011101011111000鏡像提供了高可靠性，但是十分昂貴；拆分提供了數據的高傳輸率，但不能提供可靠性。通過結合“奇偶校驗位”和磁盤拆分思想，從而以較低的代價提供數據冗余，人們提出了不同的替代方案，這些方案在不同的成本和性能之間權衡，分成若干RAID級別

RAID級別通過并行提高性能通過磁盤鏡像，處理讀請求的速度將翻倍，因為讀請求可以發(fā)送到任意一張磁盤磁盤系統(tǒng)中并行的兩個目的1. 負載平衡（Loadbalance）多個小的訪問操作，提高訪問的吞吐量2. 并行執(zhí)行大的訪問，減少大訪問操作的響應時間.通過在多張磁盤上進行數據拆分來提高傳輸率比特級拆分（Bit-levelstriping）–將每個字節(jié)按比特分開，存儲到多個磁盤上在一個8張磁盤組成的陣列上，每個字節(jié)的第i位寫到第i張磁盤上.如果把這8張磁盤看做一張磁盤，則這張磁盤的每個扇區(qū)的大小是通常磁盤的8倍.缺點：每張磁盤都參與每次訪問，所以單位時間處理的訪問的次數和一張磁盤時一樣的，需要較多的尋道時間，比特級的拆分目前已經基本不用塊級拆分（Block-levelStriping）–將塊拆分到多張磁盤當讀一個大文件時，塊級拆分可以從n張磁盤上并行地讀取n個塊RAID級別結合奇偶校驗位（paritybits）和磁盤拆分(diskstriping)思想，以較低的代價提供數據冗余不同的RAID級別有不同的具有不同的成本，效率及可信度RAIDLevel1:使用塊級拆分的磁盤鏡像（Mirroreddisks）能提供最好的讀寫性能流行在數據庫系統(tǒng)中的日志文件的存儲RAIDLevel0:塊級拆分無冗余適用于數據不太重要的高性能應用RAID級別(Cont.)RAID2:內存風格的糾錯碼（Memory-StyleError-Correcting-Codes).RAID3:

位交叉的奇偶校驗組織結構RAIDLevel4:

塊交叉的奇偶校驗組織結構RAID5:

塊交叉的分布奇偶校驗位的組織結構RAID6:P+Q冗余方案RAID級別(Cont.)選擇RAID級別應該考慮的因素所需額外磁盤存儲所帶來的花費；在I/O操作數量方面的性能需求；磁盤故障時的性能數據重建過程中的性能RAID0—用于數據安全性不是很重要的高性能應用RAID1

—數據重建最為簡單，因為數據可以從另外一張磁盤拷貝得到，一般應用于高性能數據庫。RAID2andRAID4基本不用，因為它們分別被RAID3和RAID5所包含。RAID3和RAID5塊級拆分對于大量數據的傳輸有與RAID3級同樣好的傳輸速率，同時對于少量數據的傳輸使用了更少的磁盤比特級拆分的RAID3不如塊級拆分的RAID5，RAID6—極少被使用是因為RAID1和RAID5已經提供了足夠的安全保障來滿足大部分應用，RAID6用于數據安全十分重要的應用RAID級別的選擇RAID1提供了最好的寫操作性能廣泛應用于數據庫日志文件的存儲這類應用RAID1有較高的存儲代價磁盤容量增長迅速(每年增長50%)，因此對現存的具有中等存儲要求的數據庫而言，磁盤鏡像所需要的額外磁盤存儲開銷相對變小，而存取速度增長相對緩慢(10年3倍)I/O操作的需求飛速增長，如Web應用服務器RAID5有較低的存儲負載，但是寫操作需要更高的時間開銷，對于經常進行讀操作而很少進行寫操作的應用，RAID5是首選。

對于其它應用，較多采用RAID1.RAID級別的選擇----RAID1ORRAID5軟件RAID:不改變硬件層，在只修改軟件的基礎上實現。硬件RAID:具有專有硬件支持的RAID系統(tǒng)RAID----硬件問題Compactdisk-readonlymemory(CD-ROM)640-700MB的存儲容量尋道時間100毫秒(CD和DVD的激光頭組件更重，需要更長的尋道時間)較高的延遲(3000RPM)和較低的數據傳輸率(CD:3-6MB/s)

DigitalVideoDisk(DVD)

DVD-54.7GBDVD-98.5GBDVD-10和DVD-18是雙面存儲格式9.4GBand17GB藍光DVD:27GB(54GB雙面)和CD-ROM一樣的緣故，較長的尋道時間和較低的傳輸速率（8-20MB/s）第三級存儲----光盤特點保存時間長、可靠、存儲容量大速度慢（每秒幾到幾十MB）、只能進行順序儲存、可靠讀寫的次數是有限的種類數字音頻磁帶（幾個GB）數字線性磁帶(10-40GB)Ultrium格式（100GB）Ampex螺旋掃描磁帶(330GB)自動磁帶機（Tapejukebox）存儲范圍可以達到PB級，主要應用于備份，比如通過遙感衛(wèi)星搜集到的數據或者電視廣播的大型視頻庫第三級存儲----磁帶文件組織和存儲數據庫被影射到多個不同的文件，每個文件在邏輯上是記錄的序列.每個文件分為定長的存儲單元，塊（block，4-8k）,塊是存儲分配和數據傳輸的基本單元，創(chuàng)建數據庫實例時，允許指定塊的大小，更大的塊在一些數據庫的應用中很有用.一個塊中包含很多條記錄，假定沒有比塊更大的記錄，并且每個記錄包含在單個的塊中.情形一:假定記錄都是定長的；任意一個文件中只存儲一個固定長度的記錄不同的文件用于存放不同的關系文件組織考慮學生數據庫中的instructor記錄組成的文件定長記錄

typeinstructor=recordIDvarchar(5);namevarchar(20);dept_namevarchar(20);salarynumaric(8,2);end假設每個字符占一個字節(jié)，則每個instructor記錄占用了53個字節(jié)，比較簡單的方法是用前53個字節(jié)存儲第一條記錄，接下來的53個字節(jié)存儲第二條記錄，以此類推.存在的問題：塊的大小并非恰好是53的倍數；在這個結構中刪除一條記錄會帶來很多問題，變得比較困難問題一的解決方案在一個塊中只分配它能完整容納下的最大記錄數，每個塊中余下的部分就不用了，從而避免了讀寫一次記錄要進行兩次塊的訪問定長記錄定長記錄刪除record3方案一：定長記錄刪除record3方案二：移動記錄以占據被刪除的記錄所釋放的空間的做法并不十分理想，因為這樣需要做額外的塊訪問操作由于插入操作通常比刪除操作更為頻繁，因此讓被刪記錄占據的空間空著，直到隨后插入的記錄占據這個空間的做法是可以接受的。但問題是僅僅在被刪記錄上做一個標記，在插入時找到這個可用空間是十分困難的因此我們需要一個替代方案定長記錄-----刪除在文件的開始處，分配一定數量的字節(jié)作為頭文件，頭文件中存儲被刪除的第一條記錄的地址在第一個記錄中存儲第二個被刪記錄的地址，第二個記錄中存放第三個被刪記錄的地址，以此類推；可以直觀地把這些存儲的地址看作指針，被刪的記錄就形成了一個鏈表，這個鏈表稱為空閑鏈表（Freelist）如果沒有可用空間，就把記錄添加到文件的末尾存在的問題是------萬一頭文件損壞定長記錄--刪除----空閑列表變長記錄以以下幾種方式出現在數據庫系統(tǒng)中：多重記錄類型在同一個文件中存儲；允許一個或者多個字段是變長的記錄類型；實現變長記錄必須解決的兩個問題在塊中如何存儲變長記錄，使得塊中的記錄可以被抽??；如何描述一條記錄，使得單個屬性可以被輕松抽取。一條有變長屬性的記錄通常表示成為兩部分，初始部分是定長屬性，第二部分是變長屬性對于定長屬性，分配存儲它們的值所需的字節(jié)數；對于變長屬性，在記錄的初始部分表示成為一對值：偏移量和長度偏移量表示記錄該屬性的數據開始的位置長度表示變長屬性的字節(jié)長度文件組織----變長記錄該圖顯示一個變長記錄，前三個屬性ID,Name,Dept_name是變長字符串，第四個屬性是一個長度固定的數值假定偏移量和長度值各占2個字節(jié)，Salary占8個字節(jié)文件組織----變長記錄條目個數

空閑空間大小位置

在塊中存儲變長記錄的問題：分槽的頁結構表示法

每個塊的存儲結構如下：記錄入口數：表示塊中記錄條目的個數存儲塊中空閑空間的末尾地址一個數組：包含每個記錄的位置和大小

文件組織----變長記錄文件中記錄的組織堆文件組織(Heapfileorganization）一條記錄可以放在文件的任何位置，只要那個地方有空，記