磁盘系统lec5-6(chap2).ppt

高级数据库技术 ch2,杨圣洪 ,第二章,Memeory Hierarchy Disks Access Times Optimizations Other Topics: Storage costs Using secondary storage Disk failures,Storage Hierarchy,2.1 存储介质,当前的电子数字计算机系统常采用电、磁、光等存储介质存储数据。这些存储介质包括（按存取速度由高到低次序）： 1）CPU寄存器，CPU缓存存储器，高速缓存存储器。它们一般用来存放将要执行的机器指令和有关操作数据，由操作系统使用和管理。数据库管理系统不考虑它们。拷贝、直写；容量为128KB-512KB; 访问速度为纳秒(nanosecond)级：10-9-10-8秒。 2）主存储器，常为MOS器件，可以随机访问，一般数据库系统只用它存储从外存调入主存需要处理的那部分数据。掉电后，主存中的数据丢失（易失）。容量为几百MB-几GB; 访问速度为10-8-10-7秒。 是主存数据库（实际用的是虚存）的主要存储介质。,2.1 存储介质,3）快闪存储器(EEPROM) 断电后数据仍能保存在，速度在内存与磁盘之间，读数=100ns=100*10-9，写数=410微秒=410*10-6，容量在32MB1024MB。 擦写次数有限！优盘到一定的次数后不能用！ 4)虚存:硬盘上的一小块的地盘，32位地址空间，232=22*210*210*210=4GB，是主存数据库的主要存储介质。,2.1 存储介质,5）硬盘（第二级存储），是连机存储数据、程序的主要存储设备。掉电后，数据不丢失（非易失），是一种直接存取存储设备。硬盘被逻辑分块（block), 块大小为4KB-56KB。 容量为几十GB-几百GB。 磁盘I/O, 访问速度在毫秒级10-2。 磁盘阵列，是近年来用于提高数据库性能和可靠性的一种技术。 6）磁带（第三级存储），是顺序存取设备，常脱机作为数据归档的存储设备。访问速度约为几秒-几分，容量为GB-TB。 5）光盘，目前常用的是只读光盘（ROM/RW），一次存入，多次访问，常用于文献库，资料库。,Storage Cost,10-9,10-6,10-3,10-0,103,access time (sec),1015,1013,1011,109,107,105,103,cache,electronic main,electronic secondary,magnetic optical disks,online tape,nearline tape & optical disks,offline tape,typical capacity (bytes),from Gray & Reuter,Storage Cost,10-9,10-6,10-3,10-0,103,access time (sec),104,102,100,10-2,10-4,cache,electronic main,electronic secondary,magnetic optical disks,online tape,nearline tape & optical disks,offline tape,dollars/MB,from Gray & Reuter,第二章,Memeory Hierarchy Disks Access Times Optimizations Other Topics: Storage costs Using secondary storage Disk failures,Magnetic Disks Mechanism,磁盘控制器：(1)将磁头移到适当的磁道上，同一时刻各个磁头处在不同盘片的同一磁道上，从而形成一个柱面。 (2)选择盘面(某个磁头)与相应的扇区。 (3)将数据传送到内存。,Terms: Platter(碟), Head(浮在盘片上), Track ,Cylinder, Sector (physical), Block (logical)=1n个Sector, Gap(缝隙10%),DISK,“Typical” Numbers Diameter: 1 inch 15 inches Cylinders: 100 2000 Surfaces: 1 (CDs) 2 (floppies) 30 Tracks/Surface:39 10,000 Sector/Tracks:9 256 Sector Size: 512B 50K Capacity: 360 KB (old floppy) 300 GB =盘面数道数扇区数扇区尺寸 =8面*8192道/面*256区/道*512字节/区 =23*213*28*29=23*210*210*210=8GB,“Typical” Numbers Capacity=盘面数道数扇区数扇区尺寸 =8面*8192道/面*256区/道*512字节/区 =23*213*28*29=23*210*210*210=8GB 单个磁道的容量=扇区数/道扇区尺寸 =256区*512字节/区=28*29字节=128KB/道Block块=4KB=4096Byte，一个块有8个扇区 因4096Byte/512Byte=8扇区， Rotation Speed:5400RPM=5400RP/60s =90RP/S , 1S/90RP=11ms/RP,第二章,Memeory Hierarchy Disks Access Times Optimizations Other Topics: Storage costs Using secondary storage Disk failures,Disk Access Time,block x in memory,?,I want block X,Time=Seek Time(移动磁头到道固定) + Rotational Delay(旋到磁头下方固定) + Transfer Time (边旋边读送内存不定) + Other( CPU+磁控，0.?ms不计),Seek Time寻道时间 若磁头就在待读磁道上方寻道时间为0， 否则= 固定的启动-停止时间(几ms)+ 与移动距离相关的巡航时间(1040ms),Average Random Seek Time(磁盘速度）,N,N,“Typical” S: 10 ms 40 ms,Seek Time,3x20x,x,1,N,Cylinders Traveled,Time,X为移动一道的时间,Average Random Seek Time(磁盘速度）,N,N,此公式可看成,Average Random Seek Time(磁盘速度）,当磁头起始位置在0道时，移动的道数是：0道、1道、2道、n-1道，则其平均值=(0+1+2+3+n-1)/n 磁头起始位置在中间位置，移动的道数是：0道、1道、2道、n/2道，则其平均值=(0+1+2+3+n/2)/(n/2). 依次考虑不同的起始位置，可以得相应的平均值，将这些平均值加起来，再除以N便得到总的平均值。 对于747型机,N=8192,其总平均寻道数为2730.,Average Random Seek Time(磁盘速度）,依次考虑不同的起始位置，可以得相应的平均值，将这些平均值加起来，再除以N便得到总的平均值。 对于747型机,N=8192,其总平均寻道数为2730,故平均寻道时间为： 1秒的启动-停止时间(见前面介绍)+ 平均寻道的巡航时间 =1ms+2730道/(500道/1ms)=1+5.46=6.46ms,Rotation Delay旋转延迟： 3600rp/m=60rp/s, 1s/60rp=16.7ms/rp 5400rp/m=90rp/s, 1s/90rp=11.11ms/rp 7200rp/m=120rp/s, 1s/120rp=8.33ms/rp 如果恰好在待读扇区的上方则不转； 若刚好转过去则要等一转！，故 平均转速=旋转一周的/2,Average Rotational Delay,R = 1/2 revolution “typical” R = 8.33 ms (3600 RPM) 60*1000ms/3600/2=1000/(2*60) =100/12=25/3=8.33ms,Complication 转一圈才能读到,May have to wait for start of track before we an read desired block,Head Here,Block We Want,Track Start,Transfer time传输时间： 待读数据所在的扇区sectors与间隙gap，依次旋过磁头下方的时间。 需要转过的角度w= 待读数据所占用的扇区数*每区的度数+ 待读数据所占用的间隙数*每间的度数,wo/(360o/转*x转/s) =w/(360*90/s) 3600RPM,Transfer Rate: t,“typical” t: 1 3 MB/second transfer time: block size t 传输速率=转数/s*扇区数/转*字节数/扇区 =120转/s*256扇/转*512字节/扇区= =120*256*512字节/s=120*28*29B/s =(2627)*217B/s=816MB/s,Other Delays,CPU time to issue I/O Contention for controller Contention for bus, memory,“Typical” Value: 0,Seek Time=1ms的启动-停止+巡航时间 =1ms+磁道数/(500道/ms) 最好不要动，道就在头下方=0 最坏情况=要跨越所有磁道=1ms+8191rp/500rp/ms=1+16.382=17.4ms Rotation latency:最长等1圈,最快为0。 转速为3840rp/m=3840rp/60s=64rp/s 1s/64rp=15.625ms/rp，最长等15.625ms Transfer Time:4096byte,An Example,Megatron 747 Disk (old),每道扇区数=256，占90%=360o*90%=324o, 每扇度数= 324o/256扇 每道间隙数=256，占10%=36o /256间, 每间度数=36o/256间 待传数据所占扇区数=4096B/512B=8扇 共占用度数=8个扇区+7间隙= 8扇* 324o /256扇+7间* 36o /256间=11.109o 转速=3840rp/m=3840rp*360o/rp/(60*1000ms) =3840*360o/(60*1000ms)=23.04o/ms 传输时间=11.109o/(23.04o/ms)=0.482ms,An Example,Megatron 747 Disk (old),最长总时间=最长寻道时间17.4ms+ 最长旋转等待时间15.625ms + 输传时间0.482ms =33.5ms 最短总时间=最短寻道时间0ms+ 最短旋转等待时间0ms + 输传时间0.482ms(只与数据长相关) =0.5ms 平均时间=平均寻道时间6.5ms(见前面)+ 平均旋转等待时间15.625ms/2 + 输传时间0.482ms =14.8ms 传一个块,An Example,Megatron 747 Disk (old),Cost for Writing similar to Reading,. unless we want to verify! need to add (full) rotation + Block size t,To Modify a Block?,Block Address:,Physical Device Cylinder # Surface # Sector,Complication: Bad Blocks,Messy (杂乱) to handle May map via software to integer sequence 1 2 . Map Actual Block Addresses . m,第二章,Memeory Hierarchy Disks Using Secondary Storage Effectively Optimizations Other Topics: Storage costs Using secondary storage Disk failures,2.3Using Secondary Storage,In most studies, one assumes that the data is in main memory and access any item of data takes as much time as any other. When implementing a DBMS, the data does not fit into main memory. One must take into account the use of secondary, tertiary storage.,P,M,C,Typical Computer,2.3.1 I/O Model Computer: One Process, One Disk Controller, One Disk DBMS: query ,database modification, the data does not fit in RAM Key parts be buffered in RAM. Time read + write Time manipulating in RAM.,I/O开销占主要部分的模型,I/O开销的主导地位 读一个大小位4KB的块需15毫秒，同样时间CPU可处理百万条指令。（最快的微型计算机可达5969MIPS，即每秒59亿次。） 大数据量的排序问,题两阶段归并算法。 r: 1,000,000个元组，每个长100字节，共1GB. B: 4096字节，放40个元组。需250,000块。 Buffer: 50MB,放12,800块。 Conclusion: I/O costs dominate(主要是IO开销) Design algorithms to reduce I/O,Example: Sorting in Disk,10,000,000tuples,several fields, Key field Fixed length,100bytes/record,1,000,000,000. disk blocks 4096bytes, 可将40100bytes压缩到一个block中. Entire relation occupies 250,000block Main memory is 50*1024*1024. 装进内存的block数: 50*1024*1024/(4*1024)= 12800 Only key fields and their pointers 在排序 Merge sort合并排序法,Example: Merge-sort,将数据分成等长的几部分。 对每部分排序。 将每个子表的首元素进行比较，小者进入输出列表。 当某个子表元素用完了则不与其比较。 各个击破！ 将数据读入主存-排序-写回另处-合并。,Example: Merge-sort,将250,000块中的12800块读入主存，读 -排-写共20次，最后一次有6800块，建立了20个已排好序的列表。 耗时主要250000块读、写时间，它的排序时间远少于其读/写时间，可忽略。写=读 250000块*15ms/块*2=7500000ms=7500s=125分. Classical Merge-Sort: 先读入一对到内存，合并后写回到磁盘另一个位置，则20表10表5表(4表变2+1)3表2表1表。由于每块读入内存的次数不止一次，其耗时会超过250000块一次读/写的125分。,Example: Merge-sort,Classical Merge-Sort: 先读入一对到内存，合并后写回到磁盘另一个位置，则20表10表5表(4表变2+1)3表2表1表。 其耗时会超过250000块一次读/写的125分。 改进：合并时先将每个列表第首块读入主存缓存。 (1)找出全体所有列表的首元素中的最小值。Log2n (2)将最小元素移到输出块。 (3)如果输出块已满(如4096Byte)，将其写回磁盘。 (4)若移走最小元素的块已耗尽，则从磁盘上读入相应列表的下一个块，若对应列中没有块了，则将此缓存区删除。每个块只读一次共250000块，写回的块也一样多，耗时也是125分钟， 总共250分钟。,第二章,Memory Hierarchy Disks Using Secondary Storage Effectively Optimizations Other Topics: Storage costs Using secondary storage Disk failures,Optimizations (in controller or O.S.),Organizing Data by Cylinders Disk Scheduling Algorithms e.g., elevator algorithm Track (or larger) Buffer Pre-fetch Arrays Mirrored Disks,2.4 改善访问时间,2.4.1 Organizing Data by Cylinders,因为最长 latency 17.4+15.6+0.5=33.5, 而 平均latency 为6.5+7.8+0.5=14.8, 故 seek time 接近1/2。 另一方面，很多应用程序经常要连续访问数据，如一个关系中的数据，这些数据宜放一个柱面上，至少要放相邻的柱面。 事实上，连续读单个磁道或单个柱面上的数据，仅在读第一个扇区时，才发生seek time与rotation latency，读紧跟其后的扇区时，只需要计算transfer time，因此读/写数据速度将接近磁盘的理论transfer rate。,2.4.1 Organizing Data by Cylinders,平均seek time：6.5ms/柱面 平均rotation latency：7.8ms/道 平均transfer time：0.5ms/块 长约2500,000块，内存为50MB,每次可读入12,800块。 Two-Phase排序法：125分钟排序+125分钟合并。 每柱面：256扇/道*512字节/扇*8道/面= 28*29*23= 210*210B=1MB 每列表：12800块*8扇/块*512字节/扇 (210*210字节/柱面)=50柱面 ，共占1000柱！ 1次寻道6.5ms+49次邻道切换1ms+0次旋转(始在首扇，读完后还在首扇)+12800*0.5ms=6455.5ms。读+写 20块的总耗时=6455.5ms*20*2=129110ms*2= 129.11*2s=2.15*2分=4.2分与125分钟！,2.4.1 Organizing Data by Cylinders,Two-Phase排序法：125分排序+125分合并。 每柱面：256扇/道*512字节/扇*8道/面= 28*29*23= 210*210B=1MB 每列表：12800块*8扇/块*512字节/扇 (210*210字节/柱面)=50柱面 1次寻道6.5ms+49次邻道切换1ms+0次旋转(始在首扇，读完后还在首扇)+12800*0.5ms=6455.5ms。 读+写 20块=6455.5ms*20*2=129110ms*2= 129.11*2s=2.15*2分=4.2分与125分钟！ 因合并时是不定期的各读入每个列表一块，不是在连续时间内读，满一个输出块时才写入到磁盘，也不是在连续时间内写，故连续存放对阶段2无效,2.4.2 Using Multiple Disks,将具有多个同步移动磁头的单个硬盘,换成多个具有独立移动磁头的硬盘,只要Disk Controller, bus, and main memory的数据传输速度足够快，其执行效率相当于几个硬盘并行作业。 如：747有4碟8面8GB，737有1碟2面2GB，其他性能指标相同，将二阶段排序移植到4个737机上。 将数据库在每磁盘放一个备份，连续放在1000柱中，在阶段1中： 读数时在连续时间内将连续存放数据读入内存， 写数时在连续时间内将数据写入连续的柱面中。 因4个磁盘并行作业，故时间降为4.2分/4=1.05分,2.4.2 Using Multiple Disks,如：747有4碟8面8GB，737有1碟2面2GB，其他性能指标相同，将二阶段排序移植到4个737机上。 将数据库在每磁盘放一个备份，连续放在1000柱中，在阶段1中： 读数时在连续时间内将连续存放数据读入内存， 写数时在连续时间内将数据写入连续的柱面中。 因4个磁盘并行作业，故时间降为4.2分/4=1.05分 因合并时是不定期的各读入每个列表一块，不是在连续时间内读，满一个输出块时才写入到磁盘，也不是在连续时间内写，故连续存放对阶段2无效,2.4.2 Using Multiple Disks,因合并时是不定期的各读入每个列表一块，不是在连续时间内读，满一个输出块时才写入到磁盘，也不是在连续时间内写，故连续存放对阶段2无效 如果能做到：一旦某队列的待读块的第一个元素进入内存，就开始排序，并且假设每个队列的数据分布在不同的磁盘上，则每个队列的数据可并行进入内存，从而可将阶段2的读取降为1/4！ 如果队列的数据交叉存放在不同磁盘上则无效。 写时可建立4个写缓存，分别对应于不同磁盘，缓存满后开始写磁盘，其他处理结果写另一缓存。不可降到1/4，只能是2/3左右。,2.4.3 Mirroring Disks,当多个磁盘保存的数据相同时称为互为Mirrors，用于数据拯救，也能加快数据的访问。 当待读的4个块来自于不同的磁盘时，可以节省读盘地间。 一般说来，如果一个盘有n个备份，可以并行读n个块，如果读的块数小于n则能立即完成，并且能选择一个离待读柱面最近的磁头来读，使其最快。 镜像不会提升写速，但不会降低写速。 因为每写一块，必须同时向每个备份写！,2.4.4Disk Scheduling and the Elevator Algorithm next,对于不能连续存贮或镜像时，让Disk Controller将多个读写请求综合处理，使其整体读写速度最快。 当进行大量数据读写(如二段排序法)该方法无效。 当很多小进程，分别访问不同的小数据块，给予不同读写请求以不同优先级可增加吞吐量。 Elevator Algorithm是简单且有效的调度算法。 当磁头每前进一轮，沿途读写一遍数据，相当于电梯上升或下降一次，将同方向的客户带走。 磁头在前进时，若到了待读/写数据所在柱面上则停下读/写，沿同一方向前进，直到同方向没有待读数据，然后反向运行，这样可避免来回移动磁头。,2.4.4Disk Scheduling and the Elevator Algorithm,从不同的柱面上读取一个块，读柱面1000上的数字时也需要寻道，现假设就在1000柱上，然后根据柱面次序排序，最终读完为80.8ms。,2.4.4Disk Scheduling and the Elevator Algorithm,从不同的柱面上读取一个块，读柱面1000上的数字时也需要寻道，现假设就在1000柱上，若根据先来先服务的原则最终需要94.880.8.,2.4.4Disk Scheduling and the Elevator Algorithm,当请求池长度=柱面数，一次运动恰好满足所有请求，寻道时间可达到最小，当请求池长柱面区，则将同一柱面的请求调在一块尽可能减少旋转延迟。,2.4.4Disk Scheduling and the Elevator Algorithm,如747型机，它有8192柱面，现在每隔8个柱面有一个请求，共有1000个，磁头在最内层，按电梯算法去读写数据，则每个请求的时间=1ms的启止+7.8ms的旋转+0.5ms的传输=9.3ms，最后请求为93000ms=9.3s， 若请求减半则所有请求完成的时间为4.63s，这已非常好了。 若清求池16384=2*8192,假设每柱面上有2个请求，每个请求的寻道为1ms(仅启止时间无巡航)，传输0.5ms，因为二块处在一个柱面上，故旋转时间(1/2)*(2/3)*15.6 =5.2ms, 共1+0.5+5.2=6.7ms，比前面的9.3ms更短！ 总共8192*6.7ms=54886.4ms=55s,2.4.5 Prefetching and Large-scale Buffering,对于某些应用程序可以预测即将用到的数据是谁，就像体系结构中 “指令的前瞻执行”一样，将所需的数据“预读到主存prefetching”，至少可让电梯算法先调度, 也称为doubl buffering。 在二阶段排序算法中，若主存足够多，我们将每个已排序的列表的块，读二个到内存中，当某个子表的一个缓存用完后，立即切换到另一个缓存，同时再将当前列表的下一个块读入内存，使读写时间降到最小。 在这里下一个待读的数据块是确定的，所以预读prefetching是完全没问题的，对效率的提升是明显的。,Double Buffering,Problem: Have a File Sequence of Blocks B1, B2 Have a Program Process B1 Process B2 Process B3,Single Buffer Solution (1) Read B1 Buffer (2) Process Data in Buffer (3) Read B2 Buffer (4) Process Data in Buffer .,Say P = time to process/block R = time to read in 1 block n = # blocks Single buffer time = n(P+R),Single Buffer Solution (1) Read B1 Buffer (2) Process Data in Buffer (3) Read B2 Buffer (4) Process Data in Buffer .,Double Buffering,Memory: Disk:,Say P R,What is processing time?,P = Processing time/block R = IO time/block n = # blocks,Double buffering time = R + nP Single buffering time = n(R+P),2.4.5 Prefetching and Large-scale Buffering,在二阶段排序算法中，若主存足够多，我们将每个已排序的列表的块，读二个到内存中，当某个子表的一个缓存用完后，立即切换到另一个缓存，同时再将当前列表的下一个块读入内存，使读写时间降到最小。 在这里下一个待读的数据块是确定的，所以预读prefetching是完全没问题的，对效率的提升是明显的。 可将双缓存与基于柱面的方法综合起来： (1)将整个已排好序的子表保存在连续的柱面中(减少寻道时间)，每个磁盘道中块也连续存放(减少旋转时间)。 (2)一旦需要某列表中的数据时，将整个磁道或整个柱面读入内存。,2.4.5 Prefetching and Large-scale Buffering,(1)将整个已排好序的子表保存在连续的柱面中(减少寻道时间)，每个磁盘道中块也连续存放(减少旋转时间)。 (2)一旦需要某列表中的数据时，将整个磁道或整个柱面读入内存。 为体会整道读与整柱读的优点，为二阶段排序算法中的20个列表中的每一个建立2个与磁道等长的缓存。 因128KB/道，共需要20*2*128KB=5*1024KB=5MB， 读入整道的时间=平均寻道6.5+旋转一圈15.6=22.1ms，因为20 列表占用1000个柱面=8000磁道=8000*128=1G，故将其读入内存需要=22.1*8000=176800ms=176.8s=2.95分，没有采用任何策略125分。,2.4.5 Prefetching and Large-scale Buffering,(1)将整个已排好序的子表保存在连续的柱面中(减少寻道时间)，每个磁盘道中块也连续存放(减少旋转时间)。 (2)一旦需要某列表中的数据时，将整个磁道或整个柱面读入内存。 读入整道的时间=平均寻道6.5+旋转一圈15.6=22.1ms， 20 表占用1000柱面=8000磁道，故延时=22.1*8000 =176.8s=2.95分没有采用任何策略125分。 主存要=20*2*128KB=5120KB=5*1024KB 读入整柱的时间=6.5+旋转一圈15.6*8=131.3ms， 20 表占用1000柱面故延时=131.3*1000 =131.3s=2.19分 主存要=20*2*128KB*8=5120KB*8=40MB 只要某个缓存不再使用了，就可将其写出到磁盘。,Block Size Selection?,Big Block Amortize分期清偿I/O Cost,Trend,As memory prices drop, blocks get bigger .,Trend,2.4.5 改善访问速度-总结,(1)Organizing data by cylinders-访问可预测. (2)Using several disks in place of one-并行读/写. (3)Mirrors disks (4)Scheduling request by the elevator algorithm (5)Prefetching data in track- or cylinder-sized chunks. 这些策略只能用在如下情况： (1)非常规范情形：单CPU-单硬盘-连续读/写(可预测)。 (2)处理过程很短-并行执行-共享磁盘空间(不可预测)。,第二章,Memory Hierarchy Disks Using Secondary Storage Effectively Optimizations Other Topics: Storage costs Using secondary storage Disk failures,2.5 Disk Failures,Intermittent (间歇性，某次读/写不成功，重复读写是成功的) Permanent (media decay，介质坏了，无论读多少次都不成功) Write failure(无论写多少次都不成功，可能在写的过程中有power outage错) Partial Total(disk crash坠落，整个磁盘都报废了),2.5.1 Intermittent Failures,扇区中有冗余位，根据它可判断数据是否正确读/写了。 如读数函数返回所读数据w与校验位的值s，首次读某该区时s为“坏”，但多次读后表示该扇区是“好”，此类故障称为间歇性故障。 我们有可能被愚弄，某扇区本来是“坏”的，只是读的次数多了，系统才返回了”好“。 如果采用更多的冗余信息可能会更好一点。 判断写成功的方法：写了一个数，马上将其读出来，若相同或者能正常读出来，或读出该标志位，手工判断常见方式。,2.5.2 Checksums,每个扇区有一个校验和checksum，它与存贮在该单元中的数据相关。 当读出某个扇区中的数据及校验位时，若该校验位与该数据不匹配，则表示该扇区为“坏”，否则为“好”。 有可能数据读错了，错误的校验位恰与错误的数据匹配，我们误以为是正确的数字。 为了避免这种现象，加大校验位。 最简单的方式奇偶位：奇数个1则为1，偶数个1则为0。如“01101000”，有奇数个1即3个1，故其奇偶位为1，由写入到扇区为011010001。 11101110有偶数个0，则写入扇区为111011100,2.5.2 Checksums,奇偶位：奇数个1则为1，偶数个1则为0。如“01101000”，有奇数个1即3个1，故其奇偶位为1，由写入到扇区为011010001。 11101110有偶数个0，则写入扇区为111011100 若恰好错了2位，如11101110读成11001100，则仍有偶数个1，仍与校验位的0匹配，从而无法发现这种错误。 利用haming等手段可避免，甚至可以纠正其中的错误，如通信编码等问题中。,2.5.3 Stable(稳定) Storage,校验和可找出介质错(media failue)，读多次也不成功的情形，但无法改正错误。 很恐怖的是能多次写，但是读不出新写的内容，如我们可以写入新的余额，但读不出新的余额，这时可完蛋了，旧的余额没了，新的余额可写入，但读不出来，旧的、新的全没了。 stable storage:一对扇区表示同一个内容，称其中一个为“左”备份XL，另个为“右”备份XR，并且其校验位很长，可以识别出一个“看起来”是好的，但实际上是坏的扇区。 如果read函数从XL与XR均返回(w,good)，则w肯定是真值X 。,2.5.3 Stable(稳定) Storage,stable-storage writing policy: (1)将X的值写入XL，若校验位为“坏”则反复写。若多次写后仍不成功，则启动修复程序将X写入其他扇区。 (2)将X的值写入XR并检查其校验位是否“好”，若不是反复写。若多次写后仍不成功，则启动修复程序，将X写入其他扇区。 stable-storage reading policy: (1)读XL。若校验位是“坏”则反复读指定次数。若最后校验位为“好”则将其作为X的真值。 (2)若不能读XL,则读XR，方法同(1)。,2.5.3 Stable(稳定) Storage,stable-storage 错误处理能力: (1)介质错误。 将X的值保存在扇区XL和XR后，其中一个扇区经历了介质错而变成了永久不可用了，我们仍可从另一个好的扇区中读出X。 若XR坏了但XL没坏，根据其读写策略会正确读出X的值，XR的好坏要到下次写时才能发现。 若XL坏了但XR没坏，则只能从XR中读出X，并且能及时发现XL坏了。 若XL与XR都坏了，则不能读出X，非常罕见。,2.5.3 Stable(稳定) Storage,stable-storage writing policy: (1)将X的值写入XL，若校验位为“坏”则反复写。若多次写后仍不成功，则启动修复程序将X写入其他扇区。 (2)将X的值写入XR并检查其校验位是否“好”，若不是反复写。若多次写后仍不成功，则启动修复程序，将X写入其他扇区。 stable-storage reading policy: (1)读XL。若校验位是“坏”则反复读指定次数。若最后校验位为“好”则将其作为X的真值。 (2)若不能读XL,则读XR，方法同(1)。,2.5.3 Stable(稳定) Storage,stable-storage 错误处理能力: (1)介质错误Media failure 将X的值保存在扇区XL和XR后，其中一个扇区经历了介质错而变成了永久不可用了，我们仍可从另一个好的扇区中读出X。 若XR坏了但XL没坏，根据其读写策略会正确读出X的值，XR的好坏要到下次写时才能发现。 若XL坏了但XR没坏，则只能从XR中读出X，并且能及时发现XL坏了。 若XL与XR都坏了，则不能读出X，非常罕见。,2.5.3 Stable(稳定) Storage,stable-storage 错误处理能力: (2)写错误Write failure 假设写X时发生了系统故障，如power outage (电源存储损耗) ，此时X在主存中的值被覆盖或丢失了，需要同时写入的X的备份也被混淆了。,2.6 Recovery from Disk Crashes,当出现像“Disk Crash”之类的永久性故障后，如果事先没有对数据进行备份，那么将无法恢复数据。 为了减少这种危险，通常方法有： 采有冗余设备redundancy、扩展奇偶校验位、扇区双份，最常见的方式是“冗余独立磁盘阵列Redundancy Array of Independent Disk RAID”，RAID可处理总是读不出数据的介质错误Media failure、由于暂时性系统错而使单个扇区出错的corruption of data。,2.6.1The Failure Model for Disks,Mean time to failure是指在过了这个时间后，50%的硬盘将会出现灾难性故障，常有10年，它与数据丢失Mean time to data loss不相同。 可采用线性故障率，如10年内50%的硬盘会坏掉，则第一年坏掉的比例为5%，第二年又坏掉5%累计10%，第十年坏掉5%累计50%。 像多数电子设备一样，制造过程中的细微过失面产生的故障会在早期出现，且出厂之前的检测中会查出来。使用过程中的“wear-and-tear(磨损)”及细微灰尘颗粒长年累计，会带来故障。,2.6.2Mirroring as a Redundancy Technique,Mirror each disk互为镜象，其中一个为data 盘，其他为redundant盘，已在2.4.3中介绍过，本节的 Mirror称为RAID 1。各冗余方法仅在备份盘也坏了时才丢失数据，可能性很小。 如某型盘的mean time to failure为10年，并假设每年坏掉5%。若在复制备份盘上的数据到坏盘时出错，其可能性的计算如下： 假设正常修复时长为3小时=1/8天=1/2920年，每年故障率5%，因此备份盘在3小时内坏掉可能性为5%1/2920=1/58400。一个盘10年才坏，在1年内的坏可能性为1/10，二个盘中坏一个可能性为1/10+1/10=1/5，因此3小时一对盘坏一个的可能性为(1/58400)*(1/5)=1/292000。,2.6.2Mirroring as a Redundancy Technique,Mirror each disk互为镜象，在写入数据时并行写到两个磁盘上,读数只要读一个,若一个有故障则从另一个恢复，仅两个都坏时才无法恢复。 读数如果从两个磁盘上并行读数，则是从单盘读数的两倍。 与此类似，将每个byte拆分成8个位bit,由8个磁盘构成阵列，每个字节的第i个比特位写到第i个磁盘上，即将8个磁盘看成单一的磁盘。 原来依次写/读每个位，现在并行的写/读每个位，是原来单个磁盘的8倍。 此类技术称为“比特级拆分”。,2.6.2Mirroring as a Redundancy Technique,比特级拆分可推广到磁盘总数为8的倍数或能被8整除的情况，如4个磁盘，则每个字节的第i个比特位及4+i比特位写第i个磁盘（哪个位写到哪个磁盘有一个分配表）。 块级拆分：文件的第i块保存 i mod n+1个磁盘上，还可按扇区拆分等。 总之，磁盘系统中的并行操作有目的如下： (1)负载平衡多个小的存取操作，提高吞吐率。 (2)并行执行大的存取操作，以减少反应时间。,RAID级别,RAID0级是指块级拆分，但没有任何冗余的磁盘阵列，将文件的第i块保存到 i mod 4+1号磁盘 需要知道每块保存到了哪个磁盘即文件分配表。,RAID级别,RAID1级是指块级拆分的磁盘镜像，将文件的第i块保存到 i mod 4+1号磁盘，同时每一块都并行保存二份。 需要知道每块保存到了哪个磁盘即文件分配表。,RAID级别,RAID2级也称内存风格的纠错码ECC结构，每个字节有1位奇偶校验位。当字节中的数与其奇偶位不匹配时，表示数据错或奇偶位错。 多位纠错码如haming码纠正多位错误。 可将字节第1、5位保存在1号盘，2、6位保存在2号盘，3、7保存在3号盘，4、8位保存在4号盘，纠错码保存在5、6、7号盘中。,RAID级别,RAID3级也称为位交叉的奇偶校验位结构。假设Disk Controller能检测出每个扇区是否正确读出。 当某个扇区坏了，计算其他磁盘上对应扇区的对应位的奇偶值来恢复，其原理详见RAID4。,2.6.3Parity Blocks,在RAID 4中，无论有多少个数据盘，都只采用一个冗余盘(这些盘体结构应相同) 。 冗余盘的第i块是由所有磁盘(数据盘与冗余盘)的奇偶校验位组成，其计算方法是： 若多个数据盘的第i块的第j位上已有奇数个1，则将冗余盘的第i块的第j位置成1； 若多个数据盘的第i块的第j位上已有偶数个1，则将冗余盘的第i块的第j位置成0； 即为数据盘中1之个数的模2和modulo-2 sum,2.6.3 Parity Blocks,冗余盘的第i块是由所有磁盘(数据盘与冗余盘)的奇偶校验位组成，data盘中1之个数的模2和。 如1Block=1Byte=8bits,3个data盘与1个冗余盘，每个盘的首块内容为： d1:11110000 d2:10101010 d3:00111000 dr:01100010 此时这4个块的每位上1的个数之和均为偶数！,2.6.3Parity Blocks-Reading,采用奇偶位块的冗余时,直接从指定data盘上读数,不读冗余盘,但读冗余盘可得到并行读数效果 d1:11110000 d2:10101010 d3:00111000 dr:01100010 若正在盘1的第3块时，读盘1第1块的新请求来了，按理要先读完第3块，再去读第1块。 若盘2、盘3、冗余盘均空，则可同时读出这些盘第1块的内容,通过计算得到盘1第1块的内容： d2:10101010， d3:00111000， dr:01100010，计算各位上1的模2和11110000，也能得到盘1上的第1块内容，达到并行读效果,2.6.3Parity Blocks-Writing,写入新块到指定盘时，同时要修改冗余盘。 修改冗余盘的naive方法： (1)将新块写入到盘k的第i块， (2)读出(n-1)个数据盘上第i块， (3)重新计算冗余盘的第i块 (4)写回冗余盘的第i块 共有