海量数据存储之Key-Value存储简介 - forchenyun【十年磨剑】 - ITeye博客
博客分类：
Key-value存储简介
具备高可靠性及可扩展性的海量数据存储对互联网公司来说是一个巨大的挑战，传统的数据库往往很难满足该需求，并且很多时候对于特定的系统绝大部分的检索都是基于主键的的查询，在这种情况下使用关系型数据库将使得效率低下，并且扩展也将成为未来很大的难题。在这样的情况下，使用Key-value存储将会是一个很好的选择。
它被广泛应用于缓存，搜索引擎等等领域。
根据以上的描述，一个好的key-value存储需要满足哪些条件呢？
Availability可用性
Scalability可扩展性
Failover故障恢复
Performance高性能
简单来说，就是数据不能丢失，服务不能中断，能对故障进行感知并能自动恢复，读写性能极高。
这一部分比较大，以后会另开主题写
单文件还是多文件
不少nosql的产品采用的是单文件存储的，数据量大以后肯定会遇到性能瓶颈，这一点无需多说，我想强调的是，采用多文件存储数据优点还是非常多的，不过也需要注意，操作系统对于能够打开的文件数目是由限制的，貌似Linux好像是1024（待确认），
Only Append
为了支持更快的写操作，数据文件的写操作只支持append，这个就不多说了，相信大部分的海量存储设计都是这样的。因此，更新操作等价于写操作，不过在写的时候第一步判断写到树的哪个位置时肯定会定位到树已有的节点上，这样可以使得这次写失效或者直接覆盖。
这样存在一个问题，就是对于失效的数据（比如更新过的数据）如何处理，比较好的办法是启动独立线程定时或手动进行清理，请注意，这是一个非常巨大的过程，它将耗光你的CPU和I/O，因为要进行频繁计算和数据迁移。
B Tree家族这一数据结构被广泛的运用于数据库索引，如Mssql的B+tree，oracle的B-tree，熟悉索引的朋友一定很清楚，这种数据结构非常适合作为我们的Key-value存储的数据结构.关于B+tree，可以参见下图：它是一个多路搜索树, 数据存储在叶子节点上，非叶子节点作为叶子节点的索引，加速数据的查找，而叶子节点是一个有序的链表，每次搜索都会到达叶子节点才会结束，插入新数据可能会引起节点的分裂。
在本篇文章中，你需要知道，上层的节点成为IN（Internal Node）,它持有其他节点的引用，叶子节点的上层是（Bottom Internal Node），而叶子节点则是存储数据的节点。
图片来自：http://blog.csdn.net/manesking/archive//1505979.aspx
这部分是纯粹的数据结构，就不多说了，如果想深入了解的话可以看看这篇论文《The Ubiquitous B-Tree》
因为系统要具备高扩展性，因此，增加删除机器是频繁的操作，如何将数据均匀分散到集群中呢？比较常用的办法是hash取模的办法，但是这样一来，增加机器的瞬间，按照之前的hash取模方式，数据无法读取，这意味着需要对数据进行迁移，等待机器预热，这是很不好的办法。
目前比较公认的解决办法就是一致性哈希(consistent hashing)
首先按照机器的hash进行顺时针分布，如图，目前有5台机器，如果有一个读写请求，那么hash该key值得的一个hash值，定位到环上，如果没有定位到具体的机器，那么按照顺时针查找，找到的第一个机器就是目标节点。
如果需要新增机器，增加过程为，首先hash新机器得到其位置，加入新机器F，这时访问策略不变，那么按照之前的策略，如果hash到C-F之间的数据就无法找到了，但是这样一来影响就局限于C-F之间，不象之前需要整体迁移了。
最后，为了降低增加机器所带来的影响，我们可以为其增加虚拟节点（virtual nodes）。这样的话服务器在环上的分布就比较均匀，这样多个虚拟节点将对应一个我们的物理节点，增加机器所受到的影响也会变得最小。
Replication
为了达到高可用性和数据不丢失，我们需要通过复制将数据备份到多台机器，replication的实现机制一般是通过Master与replica之间的TCP/IP连接，然后根据相应的一致性策略将数据分发到replica上，这里的一致性策略主要包括两项：
replica能够延迟master的时间，这个的意思就是说，在这个时间内更新的数据，replica可能是看不到的。例如你设置的一致性时间是3s，那么在某个特定的时刻，replica上的数据实际上可能是master3s以前的snapshot。
master事务提交返回之前是否需要得到replica的确认。为了尽量保证数据不丢失，master需要得到一定数量的replica确认数据更新成功之后才能提交事务。
关于数据可靠性和性能之间，是需要进行折衷的，很显然，越是高的数据保障，那么性能肯定会受到影响。在这样的情况下，需要对上层的应用进行分析，看是否允许丢失一部分数据。
另外，还有一个问题就是，数据的同步是采用master分发还是replica定时请求的问题，两者各有优缺点，前者会在replica较多的情况下遇到瓶颈，而后者可能会有一些延迟。多级同步的方式能在一定程度上解决这个问题，即master向某些机器同步，而这些机器向其他机器同步。
当然，master管理写请求而replica管理读请求，至于如何决定读写请求的分发，我们可以使用monitor节点，由它来作为读写的入口，
如下图，然后Monitor管理集群的状态和生命周期，例如Master fail后，monitor将收到事件，它将发起一次选举选出新的Master，一般的选举算法就是在集群中寻找最后一次更新的节点，因为往往它的数据是最新。还有就是在有新的机器加入集群的情况下，Monitor会告诉新机器集群内的master是谁，replica机器才能与master取得连接同步数据。
&!--[if gte mso 9]&&xml&
&o:OLEObject Type="Embed" ProgID="Visio.Drawing.11" ShapeID="_x"
DrawAspect="Content" ObjectID="_"&
&/o:OLEObject&
&/xml&&![endif]--&
使用Monitor的Master-replica集群
当然，自从有了ZooKeeper，这种监控和协同的脏活累活就可以都交给它了，利用ZooKeeper管理集群内节点的健康状况具备很大的便利，毕竟，上面这个办法的架构存在单点问题，最后肯定Monitor会拖集群的后腿。所以用ZooKeeper管理集群并且针对不同的事件作出响应。下面是一个示意图：
&!--[if gte mso 9]&&xml&
&o:OLEObject Type="Embed" ProgID="Visio.Drawing.11" ShapeID="_x"
DrawAspect="Content" ObjectID="_"&
&/o:OLEObject&
&/xml&&![endif]--&
用ZooKeeper管理集群
最后，关于事务提交时的处理策略也值得注意，你需要为master和replica都指定.一般情况下，我们需要在减少频繁的I/O操作和数据保障性方面进行折衷，以下提交策略可选：
在事务提交时将数据由内存刷到硬盘，这样数据具有最高的保障，但是你需要等待昂贵的I/O操作。
在事务提交时将数据刷到操作系统buffer中，然后由操作系统自己决定何时刷到硬盘。这样可以在虚拟机挂了的情况下保证数据不丢失，但是不能hardware failture
在事务提交时数据仍然维持在内存中，而在存储系统比较闲的时候进行持久到硬盘的操作，或在内存不够用的情况下进行写磁盘操作。
Get和Put操作
这两个动作是key-value存储系统最核心的两个操作，因此在设计上需要做更多的考虑。
下面是一种写操作的过程：
执行tree搜索以定位插入数据所在的位置
锁定该位置的父节点
创建新的叶子节点
将叶子节点写入。这个写操作发生在内存中，并且返回一个number它决定了叶子节点写到硬盘的位置
修改父节点指向该叶子节点的引用。该父节点既持有指向内存的叶子节点的引用又持有磁盘的位置的number。
标记该父节点为dirty(意味着内存中的版本没有出现在磁盘中)
解锁该父节点
请注意，很明显，这个写操作完全发生在内存中，那么何时将数据同步到磁盘呢？这就是后面要讲的checkpoint。通过它定时的将内存中的脏数据写到硬盘。
读操作就简单很多了，搜索tree，定位到叶子节点，取出数据就行了，当然还有一些包括为缓存服务的操作就不细讲了（比如，为每个节点计数，每次对该节点的访问都使得其+1，这样在缓存evict的时候就很有用了）
上面所说的写操作在内存中并不会影响到读操作，因为，为了加快读操作，我们会在启动时预加载硬盘数据文件的内容到内存，由于只有叶子节点存储数据，因此我们需要根据加载的叶子节点还原整棵B+tree，毫无疑问这是一个耗时的操作，但是却是值得的。
这块比较大，这里只重点讲一下以什么数据结构存取的问题。
首先需要解决的是，存储对象的问题，很显然，我们都有存取对象的需求，那么如何将对象转换为我们的底层存储格式呢？一般的办法有序列化，Json，XML之类，下面依次讲一下优缺点：
序列化。可能是比较简单易实现的办法，但是空间占用过大
Json和XML都差不多，存储格式比较可读一点，解析和转换比较方便，不过对于数据量大的情况还是不推荐。
字符串或者字节数组。我们按照一定的约定将对象拼成字符串，或者一次将对象的属性写入到字节数组，读取时按照相同的顺序解析即可，比较好的办法是定义一个接口，然后由客户端去实现对象字符串之间转换顺序的方法。这个比较推荐。
还有一些序列化的工具值得推荐，比如hadoop下的avro。
Checkpoint
和普通的关系型数据库一样，key-value也可以有自己的checkpoint，一般情况，checkpoint是为了减少数据恢复所需要的时间.在检查点到来时，按照之前的设计，它会将所有的dirty Internal Node写入log，这样会存在一个问题，大多数情况下，checkpoint会把整棵树写到log,解决问题的办法是我们采用增量的办法进行log，例如，如果有a和b加入到某个父节点。那么此时如果进行checkpoint时我们需要首先写一个完整的IN引用，并且记录对其进行的操作，add a，add b，这些操作记录在一个list中，当list变得过大以后我们又重新写一个完整的IN节点。
过期数据清理
这一部分只针对按照顺序写并且仅append的情况，为了减少I/O操作，无效数据仅仅被标记为delete且删除内存中对应的树的叶节点而不进行物理的删除，那么长期下去，失效数据会很多，这时候需要进行清理，一般的策略就是，当失效数据在文件中所占比例达到一定程度以后，执行清除操作。
首先根据预先存储的记录信息判断哪些文件需要进行清理操作。
扫描文件，找到仍然active的数据，拷贝到新的文件，扫描完成后删除此文件。
请注意，在写操作密集的情况下，这会造成竞争，因此尽量在访问量少的情况下执行此操作。
另外，可以使用多线程来进行清理操作。当然还有很多策略可以在清理的时候使用，比如，缓存一个叶子节点的父节点，在锁住该父节点执行迁移操作的时候可以顺便扫描该父节点下的其他叶子节点。
Need More？
人的欲望是无止境的…….除了基于主键的检索你可能还需要基于某个属性的检索，最好还能在多个属性上查询完了以后来个取交集，这个时候怎么办呢？
首先，我们有一个基于主键的key-value数据库，key存储的主键，而value存储的对象（物理存储为byte数组），那么假如我们想对对象的某个属性如name进行查询的话，那么我们可以再建一个数据库，key是待查询的字段，value是主键数据库的id。
Primary Database
Value(Object)
Foreign Key(Name)
这样一来按照name查询只需要查询一次secondary database取出主键id，再查一查primary database即可，这有点像正排索引和倒排索引的概率，如果对于多个字段的组合查询，只需要对其进行一次join即可，在join的时候可以先对待join的结果按照结果集大小进行排序，这样可以省下不少时间消耗。
虽然key-value存储按照上面的描述也可以支持多条件查询，但是不建议这样做，一是建立索引（二级数据库）需要额外的空间，二是这样需要多次查询影响性能，不管怎么样适度的折衷吧。
最后不得不提一下，由于B+tree的数据结构，它很好地支持范围查询（查询可以不下到叶子节点）可以极大的弥补搜索引擎中倒排索引进行范围查询需要全部扫描的缺陷。这也是其应用场景之一。
Key-value在海量数据存储中占据很重要的地位，对于它的深入研究能带给我们很多启发，而它在某些局部问题上所表现的优秀的能力也值得我们关注。本文大致总结了一下目前所了解的一些问题，没有提到的东西还有很多（文件系统设计，事务，缓存等等），接下来如果有空会对文件系统设计进行详细讲解。
首先，本文只是代表本人的一些浅见，不代表任何官方意见。其次，由于作者水平的原因，肯定会出现错误，欢迎指正（最好站内，给我留一点脸面-_-）
参考文献：
Dynamo: Amazon’s Highly Available Key-value
http://blog.csdn.net/manesking/archive//1505979.aspx
(BTree,B-Tree,B+Tree,B*Tree都是什么)
浏览 39977
forchenyun 写道54yj 写道forchenyun 写道54yj 写道对b树结构的删除修改导致的老化，oracle也有一些策略，包括空间的重用策略、删除合并的时间选择等。这一点能详细分享吗这篇文章是否有点价值：tks，关于数据库级别的优化请多多分享楼主的综合能力远在我之上，真的非常钦佩，目标也很远大，加油呀，给你鼓掌。关于数据库内部的数据结构和一些算法，ali有好多高手，比如biti_rainy。俗话说三人行必有我师呀，不知道有没有搞类似“同行评审”的活动。有空可以组织一下，呵呵
54yj 写道forchenyun 写道54yj 写道对b树结构的删除修改导致的老化，oracle也有一些策略，包括空间的重用策略、删除合并的时间选择等。
这一点能详细分享吗
这篇文章是否有点价值：
tks，关于数据库级别的优化请多多分享
楼主的综合能力远在我之上，真的非常钦佩，目标也很远大，加油呀，给你鼓掌。
关于数据库内部的数据结构和一些算法，ali有好多高手，比如biti_rainy。
俗话说三人行必有我师呀，不知道有没有搞类似“同行评审”的活动。
forchenyun 写道54yj 写道对b树结构的删除修改导致的老化，oracle也有一些策略，包括空间的重用策略、删除合并的时间选择等。这一点能详细分享吗这篇文章是否有点价值：tks，关于数据库级别的优化请多多分享
54yj 写道对b树结构的删除修改导致的老化，oracle也有一些策略，包括空间的重用策略、删除合并的时间选择等。
这一点能详细分享吗
这篇文章是否有点价值：
对b树结构的删除修改导致的老化，oracle也有一些策略，包括空间的重用策略、删除合并的时间选择等。这一点能详细分享吗
那个文件句柄，我记得默认是1024，但你好像可以通过修改内核参数重新编译来增大这个数值。tks
& 上一页 1
forchenyun
浏览: 250749 次
来自: 杭州
你好 你知道b+树在初始化的时候加载策略么？不会全部加载，一般 ...
专门注册了个账号来顶楼主
上面写错了,提示是:There are no categori ...
楼主你好,我按照你的方法来做,却提示there is no s ...Development of E-Commerce
数据恢复服务
您现在的位置：
数据存储及恢复的基本原理
现实中很多人不知道删除、格式化等硬盘操作丢失的数据可以恢复，以为删除、格式化以后数据就不存在了。事实上，上述简单操作后数据仍然存在于硬盘中，懂得数据恢复原理知识的人只需几下便可将消失的数据找回来。
感知科技是如何能把丢失的数据帮您找回的
分区：硬盘存放数据的基本单位为扇区，我们可以理解为一本书的一页。当我们装机或买来一个移动硬盘，第一步便是为了方便管理--分区。无论用何种分区工具，都会在硬盘的第一个扇区标注上硬盘的分区数量、每个分区的大小，起始位置等信息，术语称为主引导记录（MBR），也有人称为分区信息表。当主引导记录因为各种原因（硬盘坏道、病毒、误操作等）被破坏后，一些或全部分区自然就会丢失不见了，根据数据信息特征，我们可以重新推算计算分区大小及位置，手工标注到分区信息表，"丢失"的分区回来了。
文件分配表：为了管理文件存储，硬盘分区完毕后，接下来的工作是格式化分区。格式化程序根据分区大小，合理的将分区划分为目录文件分配区和数据区，就像我们看得小说，前几页为章节目录，后面才是真正的内容。文件分配表内记录着每一个文件的属性、大小、在数据区的位置。我们对所有文件的操作，都是根据文件分配表来进行的。文件分配表遭到破坏以后，系统无法定位到文件，虽然每个文件的真实内容还存放在数据区，系统仍然会认为文件已经不存在。我们的数据丢失了，就像一本小说的目录被撕掉一样。要想直接去想要的章节，已经不可能了，要想得到想要的内容（恢复数据），只能凭记忆知道具体内容的大约页数，或每页（扇区）寻找你要的内容。我们的数据还可以恢复回来。
格式化：我们向硬盘里存放文件时，系统首先会在文件分配表内写上文件名称、大小，并根据数据区的空闲空间在文件分配表上继续写上文件内容在数据区的起始位置。然后开始向数据区写上文件的真实内容，一个文件存放操作才算完毕。
　　删除操作却简单的很，当我们需要删除一个文件时，系统只是在文件分配表内在该文件前面写一个删除标志，表示该文件已被删除，他所占用的空间已被"释放"，其他文件可以使用他占用的空间。所以，当我们删除文件又想找回他（数据恢复）时，只需用工具将删除标志去掉，数据被恢复回来了。当然，前提是没有新的文件写入，该文件所占用的空间没有被新内容覆盖。
删除：格式化操作和删除相似，都只操作文件分配表，不过格式化是将所有文件都加上删除标志，或干脆将文件分配表清空，系统将认为硬盘分区上不存在任何内容。格式化操作并没有对数据区做任何操作，目录空了，内容还在，借助数据恢复知识和相应工具，数据仍然能够被恢复回来。注意：格式化并不是100%能恢复，有的情况磁盘打不开，需要格式化才能打开。如果数据重要，千万别尝试格式化后再恢复，因为格式化本身就是对磁盘写入的过程，只会破坏残留的信息。
数据恢复工程师常说："只要数据没有被覆盖，数据就有可能恢复回来"。因为磁盘的存储特性，当我们不需要硬盘上的数据时，数据并没有被拿走。删除时系统只是在文件上写一个删除标志，格式化和低级格式化也是在磁盘上重新覆盖写一遍以数字0为内容的数据，这就是覆盖。一个文件被标记上删除标志后，他所占用的空间在有新文件写入时，将有可能被新文件占用覆盖写上新内容。这时删除的文件名虽然还在，但他指向数据区的空间内容已经被覆盖改变，恢复出来的将是错误异常内容。同样文件分配表内有删除标记的文件信息所占用的空间也有可能被新文件名文件信息占用覆盖，文件名也将不存在了。当将一个分区格式化后,有拷贝上新内容,新数据只是覆盖掉分区前部分空间,去掉新内容占用的空间,该分区剩余空间数据区上无序内容仍然有可能被重新组织,将数据恢复出来。同理，克隆、一键恢复、系统还原等造成的数据丢失，只要新数据占用空间小于破坏前空间容量，数据恢复工程师就有可能恢复你要的分区和数据。65673人阅读
计算机原理（3）
网络知识（8）
& & & & &&硬盘的种类主要是SCSI 、IDE 、以及现在流行的SATA等；任何一种硬盘的生产都要一定的标准；随着相应的标准的升级，硬盘生产技术也在升级；比如 SCSI标准已经经历了SCSI-1 、SCSI-2、SCSI-3；其中目前咱们经常在服务器网站看到的
Ultral-160就是基于SCSI-3标准的；IDE 遵循的是ATA标准，而目前流行的SATA，是ATA标准的升级版本；IDE是并口设备，而SATA是串口，SATA的发展目的是替换IDE；
& & &我们知道信息存储在硬盘里，把它拆开也看不见里面有任何东西，只有些盘片。假设，你用显微镜把盘片放大，会看见盘片表面凹凸不平，凸起的地方被磁化，凹的地方是没有被磁化；凸起的地方代表数字1（磁化为1），凹的地方代表数字0。因此硬盘可以以二进制来存储表示文字、图片等信息。
& & & & 硬盘大家一定不会陌生，我们可以把它比喻成是我们电脑储存数据和信息的大仓库。一般说来，无论哪种硬盘，都是由盘片、磁头、盘片主轴、控制电机、磁头控制器、数据转换器、接口、缓存等几个部份组成。
& & & & & & & & & & & & & & & &
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 平面图：
&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 立体图
& & & & 所有的盘片都固定在一个旋转轴上，这个轴即盘片主轴。而所有盘片之间是绝对平行的，在每个盘片的存储面上都有一个磁头，磁头与盘片之间的距离比头发 丝的直径还小。所有的磁头连在一个磁头控制器上，由磁头控制器负责各个磁头的运动。磁头可沿盘片的半径方向动作，（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。而盘片以每分钟数千转到上万转的速度在高速旋转，这样磁头就能对盘片上的指定位置进行数据的读写操作。
& & & & & & & & & & & & & &&
由于硬盘是高精密设备，尘埃是其大敌，所以必须完全密封。
& & & & & & & & & & & &&
3、盘面、磁道、柱面和扇区
&&&&& 盘面号：扇区所在的磁头（或盘面）
&&&&& 柱面号：磁道，确定磁头的径向方向。
&&&& 扇区号：在磁道上的位置。也叫块号。确定了数据在盘片圆圈上的位置。
头标中还包括一个字段，其中有显示扇区是否能可靠存储数据，或者是否已发现某个故障因而不宜使用的标记。有些硬盘控制器在扇区头标中还记录有指示字，可在原扇区出错时指引磁盘转到替换扇区或磁道。最后，扇区头标以循环冗余校验（CRC）值作为结束，以供控制器检验扇区头标的读出情况，确保准确无误。
扇区的第二个主要部分是存储数据的数据段，可分为数据和保护数据的纠错码（ECC）。在初始准备期间，计算机用512个虚拟信息字节（实际数据的存放地）和与这些虚拟信息字节相应的ECC数字填入这个部分。
&5. 访盘请求完成过程 ：
确定磁盘地址（柱面号，磁头号，扇区号），内存地址（源/目）：
& & & &当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。
为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点：
& & & & &1）首先必须找到柱面，即磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，
& & & & &2）然后目标扇区旋转到磁头下，即磁盘旋转将目标扇区旋转到磁头下。这个过程耗费的时间叫做旋转时间。
即一次访盘请求（读/写）完成过程由三个动作组成：
& & & &1）寻道（时间）：磁头移动定位到指定磁道&
& & & &2）旋转延迟（时间）：等待指定扇区从磁头下旋转经过&
& & & &3）数据传输（时间）：数据在磁盘与内存之间的实际传输
因此在磁盘上读取扇区数据（一块数据）所需时间：
&&&&&&Ti/o=tseek&+tla&+
tseek 为寻道时间
tla为旋转时间
twm 为传输时间
系统将文件存储到磁盘上时，按柱面、磁头、扇区的方式进行，即最先是第1磁道的第一磁头下（也就是第1盘面的第一磁道）的所有扇区，然后，是同一柱面的下一磁头，……，一个柱面存储满后就推进到下一个柱面，直到把文件内容全部写入磁盘。
（文件的记录在同一盘组上存放是，应先集中放在一个柱面上，然后再顺序存放在相邻的柱面上，对应同一柱面，则应该按盘面的次序顺序存放。）
（从上到下，然后从外到内。数据的读/写按柱面进行，而不按盘面进行，先）
系统也以相同的顺序读出数据。读出数据时通过告诉磁盘控制器要读出扇区所在的柱面号、磁头号和扇区号（物理地址的三个组成部分）进行。磁盘控制器则 直接使磁头部件步进到相应的柱面，选通相应的磁头，等待要求的扇区移动到磁头下。在扇区到来时，磁盘控制器读出每个扇区的头标，把这些头标中的地址信息与期待检出的磁头和柱面号做比较（即寻道），然后，寻找要求的扇区号。待磁盘控制器找到该扇区头标时，根据其任务是写扇区还是读扇区，来决定是转换写电路， 还是读出数据和尾部记录。找到扇区后，磁盘控制器必须在继续寻找下一个扇区之前对该扇区的信息进行后处理。如果是读数据，控制器计算此数据的ECC码，然
后，把ECC码与已记录的ECC码相比较。如果是写数据，控制器计算出此数据的ECC码，与数据一起存储。在控制器对此扇区中的数据进行必要处理期间，磁 盘继续旋转。
　　由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：
　　当一个数据被用到时，其附近的数据也通常会马上被使用。
　　程序运行期间所需要的数据通常比较集中。
　　由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。
　　预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
俗话说一图胜千言，先用一张ACSII码图来解释为什么会产生磁盘碎片。
& & & & & & & &
上面的ASCII图表示磁盘文件系统，由于目前上面没有任何数据文件，所以我把他表示成0。
在图的最上侧和左侧各有a-z 26个字母，这是用来定位每个数据字节的具体位置，如第1行1列是aa,26行26列是zz。
我们创建一个新文件，理所当然的，我们的文件系统就产生了变化，现在是
& & & & & & & & & & &
如图所示：”内容表”(TOC)占据了前四行,在TOC里存贮着每件文件在系统里所在的位置。
在上图，TOC包括了一个名字叫hello.txt的文件，其具体内容是”Hello, world”，在系统里的位置是ae到le。
接下来再新建一个文件
& & & & & & & & & & &
如图，我们新建的文件bye.txt紧贴着第一个文件hello.txt。
其实这是最理想的系统结构，如果你将你的文件都按照上图所表示的那样一个挨着一个，紧紧的贴放在一起的话，那么读取他们将会非常的容易和迅速，这是因为在硬盘里动得最慢的(相对来说)就是传动手臂，少位移一些，读取文件数据的时间就会快一些。
然而恰恰这就是问题的所在。现在我想在”Hello, World”后加上些感叹号来表达我强烈的感情，现在的问题是：在这样的系统上，文件所在的行就没有地方让我放这些感叹号了，因为bye.txt占据了剩下的位置。
现在有俩个方法可以选择，但是没有一个是完美的
1.我们从原位置删除文件，重新建个文件重新写上”Hello, World!!”. –这就无意中延长了文件系统的读和写的时间。
2.打碎文件，就是在别的空的地方写上感叹号，也就是”身首异处”–这个点子不错，速度很快，而且方便，但是，这就同时意味着大大的减慢了读取下一个新文件的时间。
如果你对上面的文字没概念,上图
& & & & & & & & & &
这里所说的方法二就像是我们的windows系统的存储方式，每个文件都是紧挨着的，但如果其中某个文件要更改的话，那么就意味着接下来的数据将会被放在磁盘其他的空余的地方。
如果这个文件被删除了，那么就会在系统中留下空格，久而久之，我们的文件系统就会变得支离破碎，碎片就是这么产生的。
试着简单点，讲给mm听的硬盘读写原理简化版
& & & & & & & & &
硬盘的结构就不多说了,我们平常电脑的数据都是存在磁道上的,大致上和光盘差不多.读取都是靠磁头来进行.
& & & & & &
我们都知道,我们的数据资料都是以信息的方式存储在盘面的扇区的磁道上,硬盘读取是由摇臂控制磁头从盘面的外侧向内侧进行读写的.所以外侧的数据读取速度会比内侧的数据快很多.
& & & & & & & & &
其实我们的文件大多数的时候都是破碎的，在文件没有破碎的时候,摇臂只需要寻找1次磁道并由磁头进行读取,只需要1次就可以成功读取;但是如果文件破碎成 11处,那么摇臂要来回寻找11次磁道磁头进行11次读取才能完整的读取这个文件,读取时间相对没有破碎的时候就变得冗长.
因此，磁盘碎片往往也是拖慢系统的重要因素之一，Vista之家团队也计划在后续版本内加入磁盘碎片整理功能，敬请期待。
在linux系统，要计算硬盘容量及分区大小，我们先通过fdsik -l查看硬盘信息：
　　Disk /dev/hda: 80.0 GB,
heads, 63 sectors/track, 9729
　　Units = cylinders of 16065 * 512 = 8225280 bytes
　　 Device Boot Start End Blocks Id System
　　/dev/hda1 * 1 765
　　/dev/hda2 766 0 c W95 FAT32 (LBA)
　　/dev/hda3
　　/dev/hda5 9 linux
　　/dev/hda6
　　/dev/hda7
linux swap / Solaris
　　/dev/hda8
　　/dev/hda9 8 linux
　　/dev/hda10 ; 83 linux
& & heads 是磁盘面；
& & sectors 是扇区；
& & cylinders 是柱面；
& & 每个扇区大小是 512byte，也就是0.5K；
　　通过上面的例子，我们发现此硬盘有 255个磁盘面，有63个扇区，有9729个柱面；所以整个硬盘体积换算公式应该是：
　　磁面个数 * 扇区个数
* 每个扇区的大小512
* 柱面个数 = 硬盘体积 （单位bytes)
　　所以在本例中磁盘的大小应该计算如下：
　　255 x 63 x 512 x 9729 =
　　提示：由于硬盘生产商和操作系统换算不太一样，硬盘厂家以10进位的办法来换算，而操作系统是以2进位制来换算，所以在换算成M或者G 时，不同的算法结果却不一样；所以我们的硬盘有时标出的是80G，在操作系统下看却少几M；
　　上面例子中，硬盘厂家算法 和 操作系统算数比较：
　　硬盘厂家：
M （向大单位换算，每次除以1000）
　　操作系统：
K = 281 M （向大单位换算，每次除以1024）
　　我们在查看分区大小的时候，可以用生产厂家提供的算法来简单推算分区的大小；把小数点向前移动六位就是以G表示的大小；比如 hda1 的大小约为 6.144831G ；
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：6750685次
积分：31541
积分：31541
排名：第159名
原创：219篇
评论：1581条
扫码打赏,你说多少就多少
(1)(1)(2)(3)(2)(4)(2)(1)(2)(1)(1)(2)(1)(1)(1)(1)(1)(2)(2)(1)(2)(3)(3)(2)(2)(2)(4)(3)(2)(15)(6)(8)(14)(29)(26)(27)(18)(7)(8)(6)(2)