数据存储系统的基本原理（存储系统原理介绍）

一、硬件层介绍

简介

在工程架构领域里，存储是一个非常重要的方向，这个方向从底至上，我分成了如下几个层次来介绍：

1. 硬件层：讲解磁盘，SSD，SAS, NAS, RAID等硬件层的基本原理，以及其为操作系统提供的存储界面；
2. 操作系统层：即文件系统，操作系统如何将各个硬件管理并对上提供更高层次接口；
3. 单机引擎层：常见存储系统对应单机引擎原理大概介绍，利用文件系统接口提供更高级别的存储系统接口；
4. 分布式层：如何将多个单机引擎组合成一个分布式存储系统；
5. 查询层：用户典型的查询语义表达以及解析；

主板结构

在进入对硬件层的分析前，让我们来看看电脑主板上各个原件之间的关系。

上图展示了主板上主要元件的结构图，以及他们之间的总线连接情况。核心连接点是北桥和南桥两块芯片。

其中北桥比较吊，连接的都是些高速设备。一般来说只连接CPU，内存和显卡几种设备。不过近些年也出现了PCIE2.0的高速接口接入北桥，使得一些符合标准的设备就可以接入北桥。

而南桥就相对搓了，他负责接入所有低速设备。什么USB，鼠标，磁盘，声卡等等都是接在南桥上的。而不同的设备用途和协议都有很大不同，所以设计了不同的交互协议。由于历史原因，不同设备传输介质可能都不一样，导致总线上布线十分复杂。所以到目前为止，主流设备都已经统一成为了PCI总线，大家一起用这条总线。

读写过程

我们来模拟一下CPU要从磁盘读入一份数据的过程：

1. CPU发出一条指令说哥要准备读数据了
2. 这条指令依次通过系统总线，桥间总线，PCI总线传递到了磁盘控制器。控制器收到指令了之后知道这是一次读请求，且读完了是否要发中断的信息。做好一些准备工作，等待读取数据。
3. CPU再发出一条指令说要读取的逻辑地址
4. 这条指令还是通过系列总线发给磁盘控制器之后。磁盘控制器就忙活了，查找逻辑快对应的物理块地址，查找，寻道等工作，就开始读取数据了。
5. CPU再发出一条指令说读入内存的地址
6. 当收到这条指令之后，CPU就不管了，他告诉一个叫DMA的总管，说接下来就靠你了。DMA设备会接管总线，负责将磁盘数据通过PCI总线，桥间总线，内存总线同步到内存指定位置。

写操作的过程是类似的，就不累述了。

上面我们只是讲解了在主板上数据流转的过程，但是还有一个黑盒，就是磁盘控制器。这哥们到底是怎么管理的各个磁盘呢？在下一节我们将为你描述。

存储介质原理

上面讲了计算机读取数据的过程。这一章我们来大概说一下常见的存储介质的存储原理。

磁带

磁带就跟小时候听歌的时候的磁带类似。一条黑色带子上面有很多小的磁性粒子，根据粒子的南北级来判定0/1。

软盘

软盘比磁带要先进一点，记录数据的原理是一样的，只是可以随机读取，而磁带只能顺序读取。

硬盘

硬件原理

如果说前两个都是古老的东西，技术含量一般的话。硬盘就是一个很有技术含量的存储设备了，主要包含三大设备：

1. 电机
2. 电机的目的是控制磁臂精准定位到磁道，一个磁道可能很小，要精准定位到哪个地方是高科技。
3. 盘面
4. 盘面主要有两点。一点是基板要足够光滑平整，不能有任何瑕疵；一点是要将磁粉均匀的镀到基板上。这里有两个高科技，一个是磁粉的制造，一个是如何均匀的镀到基板上。
5. 磁头
6. 磁头的主要难点是要控制好跟盘面的距离，跟软盘类似，硬盘也是通过修改磁粉的南北极来记录数据的。如果隔得太远，就感知不到磁性数据了，隔得太近呢，又可能把盘面刮到。当然0/1的表示并不是只有一个磁粉，而是一片区域的磁粉。
7. 现在磁盘都是利用空气动力学，将磁头漂浮在盘面上面一点距离来控制磁头和盘面的距离。但是当硬盘停止工作不转的时候，磁头就肯定掉在盘面上了，所以一般盘面靠近圆心的地方一般都有一块没有磁粉的地方，用于安全停靠磁头。当硬盘要开始工作的时候，磁头在同心圆里面起飞，飞起来了之后再移动到其他地区。
8. 不过我一直在想，是否可以有这样的技术，能在磁臂上装多个磁头，每个磁道对应一个，停止工作的时候就把磁臂固定在某个高度让他不挨着盘面，这样是不是能大大提高硬盘的读写效率，因为这样减少了寻道的时间。

基本概念

硬盘组成原理图如下：

如上图, 硬盘主要有如下几个概念（概念比较简单，就不解释了）：

1. 扇区
2. 磁道
3. 柱面

读写过程

读写过程得分成两头来说，一头说将数据从各个盘面中读取出来；一头说如何将数据送给计算机。

1. 从盘面中读取数据
2. 我们知道再磁盘中，顺序读取会比随机读取快很多，那么有这么多盘面，磁道，这个顺序到底是什么顺序呢？
3. 假设我们现在是再顺序遍历磁盘上的数据，那么读取顺序是这样的。首先读完最上面一块盘面的最外面一个磁道，等盘面旋转完一圈之后，即这个磁道被读取完毕，然后立即切换到第二块盘面，读第二块盘面的最外面一个磁道，以此类推，直到读完最底下一块盘面。然后磁臂在向内移动一个磁道，重复刚才的过程，直到读到最里面一个磁道。
4. 其实再读取过程中还会更复杂一点，因为盘面是一直匀速高速旋转的，可能在一个扇区过度到下一个扇区的时候，就那么一点时间，可能存在误差，导致下一个扇区的数据没读到。为了解决这个问题，一般数据是在磁道上是间隔存储的。假设一个数据有10个扇区，分别为，d1,d2,...,d10；为了说明这个思想，我们假设一个磁道正好也有10个扇区，分别为，s1,s2,...s10。如果是紧挨着存放的话，那么扇区和数据的对应关系为：[(s1,d1), (s2, d2), ... , (s10, d10)]。这样就存在刚才说的有误差。那么间隔存储的话，映射关系为：[(s1,d1), (s3,d2), (s5,d3), ..., (s2, d10)]。
5. 而且在切换盘面的时候，虽然是电子切换，但是速度还是会有一定延迟，下一个盘面和上一个盘面的起始点位置不能一一对应，也是会有一定错开的。
6. 在古老的磁盘里面，这些值可能还需要用户来设置，不过现在都是厂商给咱们设置好，用户不需要关心了。
7. 由于磁臂的移动要比盘面的切换要慢很多（一个是机械切换，一个是电子切换），所以为了减少磁臂的移动，所以如上的顺序读取会是先读一个柱面，再读取下一个磁道，而不是先读完一个盘面，在读下一个盘面。
8. 那么既然磁臂的移动如此的慢，刚才讲了顺序读取的时候的磁臂移动逻辑。那么在真实情况下，有大量随机访问的情况下，磁臂是如何移动的呢？这里就需要考虑常见的磁臂调度算法了：
9. RSS：随机调度。这个就是扯蛋，只是拿来给别人做绿叶对比性能用的。
10. FIFO：先进先出。这个对于随机读取来说，性能很不友好。
11. PRI：交给用户来管理。这个跟FIFO类似，只不过优先级是由用户来指定的，不仅增加了用户使用磁盘的成本，效率也不见得高。
12. SSTF：最短时间调度。这个是指磁头总是处理离自己这次请求最近的一次请求处理。这样最大的问题就是会存在饿死的情况。
13. SCAN：电梯算法。在磁盘上往复。这个是比较常见的算法，跟电梯类似，磁臂就一个磁道一个磁道的动，移动最外面或者最里面的磁道就转向。这个算法不会饿死。
14. C-SCAN：类似电梯算法，只是单向读取数据。磁臂总是再内圈到外圈的时候读取数据，当到达外圈过后迅速返回内圈，返回过程中不读取数据，在重复之前的过程。
15. LOOK：类似SCAN，只是会快速返回，如果前面没有读写请求就立即返回。
16. C-LOOK：类似C-SCAN和SCAN之间的关系。
17. 一般来说，再IO比较少的情况下，SSTF性能会比较好，在IO压力比较大的情况下，SCAN/LOOK算法会更优秀。
18. 大家可以到这里来看看硬盘读取数据的视频：http://v.ku6.com/show/2gl1CHY7iNa_CVLum3NQHg.html
19. 将数据送给计算机
20. 刚才我们从磁盘中读到了数据，接下来我们讲解磁盘通过什么样的接口跟计算机做交互。这个接口也叫磁盘管理协议。
21. 磁盘管理协议的定义又分成两部分：软件和硬件。其中软件是指指令级，目前指令级就两个：ATA和SCSI；硬件代表数据传输方式，一般都是主板上的导线传输原理，但并不限制，数据甚至可以通过TCP/IP传输。定义一个协议需要同时定义了指令级以及硬件传输方式。
22. ATA
23. 全称是Advanced Technology Attachment，现在看起来不咋地，不过从名字看来，当时这个东西还是很高级的。
24. 这个指令是上个世纪80年代提出的。按照硬件接口的不同，又分成了两类，一类是并行ATA(PATA，一类是串行ATA(SATA)。一开始流行起来的是PATA，也叫IDE。不过由于并行线抗干扰能力太差，排线占空间，不利电脑散热。而更高级的SATA协议自从2000年被提出之后，很快PATA/IDE接口的磁盘就被历史淘汰，目前的ATA接口的磁盘只有SATA磁盘了。
25. SCSI
26. 全称是Small Computer System Interface。也是上个世纪80年代提出来的，当时设计他的目的就是为了小型服务器设计的磁盘交互接口。用该接口可以达到更大的转速，更快的传输效率。但是价格也相对较高。
27. 所以目前基本上在服务器领域SCSI磁盘会比较多，在PC机领域SATA硬盘会比较多。不过随着SATA盘的进化以及其得天独厚的价格优势，在服务器领域SATA也在逐步侵蚀SCSI的市场。
28. 不过SCSI也不会坐以待毙，他按照PATA进化成SATA的思路，自己也搞串行化，进化出来了SAS(Serial Attach SCSI)接口。这个接口目前很对市场胃口，不仅价格低廉，而且性能也还不错。所以估计SATA淘汰PATA的一幕在不久的将来也会在SCSI领域里上演。
29. SCSI指令还可以通过Internet传输(iSCSI)，通过FC网络传输(FC-SCSI)，这些我们会再后文提及。

ssd

硬件原理

ssd是近些年才火起来的存储介质。ssd一般有两种，一种利用flash闪存为芯片，另一种直接用内存(DRAM)作为存储介质，只是在里面加了个电池，在断电以后还能继续用电池来维持数据。

我们本文中讲的ssd全部是都指代前者，即用flash闪存做存储介质。先来看一下ssd的存储原理。

在磁盘中0/1的表示是用的磁粉的南北极的信息，在闪存中则用的是电子信号。他利用的是一种叫浮动门场效应晶体管作为基本存储介质。在该晶体管里面，主要是由两个门电路构成：控制门和浮动门。在两个门之间有一堆电子。当控制门加上一个电势的时候，电子就往浮动门那边跑，然后控制门断开电势，电子会储存在浮动门那边(靠中间的二氧化硅绝缘层)，则代表二进制中的0；控制门加一个反向电势的时候，电子跑回到控制门这边，浮动门那边没电子，代表二进制中的1。这样就通过检测浮动门那边的电势就能得到0或者1。而且现在有的ssd制造商，根据不同的电势，将一个晶体管表示的值从0/1拓展到0/1/2/3。这样就使得存储容量翻倍。这种类型的晶体管叫MLC(Multi Level Cell)，相对，只表示0/1的叫SLC(Single Level Cell)。不过一般而言，MLC的出错率也高很多，所以目前市面上主流产品还是SLC的。

了解了ssd的基本原理之后，我们来看看ssd是怎么组织这些晶体管的。看如下几个概念：

1. Page。一般一个Page为4K。则该Page包含4K*8个晶体管，Page是ssd读写的最小单元；
2. Block。一般128个Page组成一个Block，Block的概念非常重要，读写数据的控制都是针对Block的，待会我们再重点讲一下Block的概念；
3. Plane。一般2048个Block组成一个Plane;
4. 一块芯片再包含多个Plane，多个Plane之间可以并行操作。

Block的组织，见下图：

如图，可以看到block中的晶体管是按照井字型组织的。一横排就代表一个Page，所以一个Block一般就有128行，4K*8列。当然，由于还需要针对每个Page加一些纠错数据，所以一般还会多一些列。

横排是控制线，负责给电压，来做充电放电的作用；竖排是读取线，负责读浮动门里的电势之用。

读写过程

读取的过程是这样的：

假设要读取第三行数据，那么会给第三行控制线的电势置位0，其他127行控制线都会给一个电势，这样就能保证再竖排的读取线上只读到第三行的数据，而读不到其他数据。可以看到ssd再读取数据的时候不再需要寻道这些复杂的事情，速度会比传统的磁盘块很多。

而ssd写入就比较麻烦了，因为ssd无法再一个block内对部分cell充电，对部分cell放电，这样信号会相互干扰从而造成不可预期的情况发生。那ssd怎么处理这个问题呢，那就暴力了，把一个block的数据全部读到ssd自带的内存当中，并做好修改，接下来把整个block全部放电，即擦除所有数据，最后再将内存中整个block写回。可以看到，即使是只修改一个bit的数据，也需要大动干戈，倒腾4K*128这么多数据，所以ssd写数据的代价是很大的。但是瘦死的骆驼比马大，比起机械硬盘，还是要快好几个数量级的。

而且，ssd还有一个很头疼的问题，就是随着充放电次数的增加，中间的二氧化硅绝缘层绝缘效果会逐步降低，当降低到一定程度之后浮动门保存不住电子了的话，这个晶体管就算废了。所以单个晶体管还有擦写次数寿命，目前主流的晶体管这个上限大概是10万的数量级。而MLC的更差，只有1万次左右。

那么针对如上两个问题，ssd目前一般都有哪些解决方案来应对呢？

1. 为了优化写的时候的性能，一般ssd并不在写的时候做擦除。而是在写数据的时候，选择另外一块干净的block写数据。对于老的block数据，会做一个标记，回头定期做擦除工作；
2. 对于坏掉的晶体管，可以通过额外的纠错位来实现。根据不同的纠错算法，可以容忍同一个Page中坏掉的位的个数也是不一样的。如果超过上限，只能报告说不可恢复的错误。

常见存储介质性能数字

最后我们来对比一下目前主流的硬盘和ssd的参数，这是笔者在工作中测试得到的数据，测试数据为各种存储介质在4K大小下的随机/顺序 读/写数据，数字做了模糊化处理，保留了数量级信息，大家看个大概，心里有数即可：

| 测试项\磁盘类型 | SATA | SAS | SSD |

| 顺序读(MB/s) | 400 | 350 | 500 |

| 顺序写(MB/s) | 200 | 300 | 400 |

| 随机读(IOPS) | 700 | 1300 | 7w |

| 随机写(IOPS) | 400 | 800 | 3w |

硬盘组合

上面一节中，我们了解了单个磁盘的存储原理和读写过程。在实际生产环境中，单个磁盘能提供的容量和性能还是有限，我们就需要利用一些组合技术将多个磁盘组合起来提供更好的服务。

这一节，我们主要介绍各种磁盘组合技术。首先，我们会看一下最基本的组合技术RAID系列技术；然后，我们在看一下更大规模的集成技术SAN和NAS。

RAID

RAID技术是上个世纪80年代提出来的。

1. RAID0：条带化。读写效率都很高。但是容错很差。
2. RAID1：镜像存储。读效率可达2倍，写的时候差不多。容错牛B。
3. RAID2 & RAID3：多加一块校验盘。在RAID0的基础之上多了容错性。RAID2和RAID3的区别是使用了不同的校验算法。而且这两个的校验是针对bit的，所以读写效率很高。
4. RAID4 & RAID5 & RAID6：这几个都是针对block的，所以效率比RAID2&RAID3要更差一些。RAID4是没有交错，有一块盘就是校验盘；RAID5是有交错，每块盘都有数据和校验信息；RAID6是双保险，存了两个校验值。

目前用得比较多的就是Raid5和Raid1。

Raid的实现方式一般有两种：软Raid和硬Raid。软Raid是指操作系统通过软件的方式，对下封装SCSI/SATA接口的硬盘操作，对上提供虚拟硬盘的接口，中间实现Raid对应逻辑；硬Raid就是一个再普通的SCSI/SATA卡上加了一块芯片，里面执行可以执行Raid对应的逻辑。

现在一般的Raid实现方案都是硬Raid，因为软Raid有如下两个确定：

1. 占用额外的内存和CPU资源；
2. Raid依赖操作系统，所以操作系统本身无法使用Raid，如果操作系统对应的那块硬盘坏了，那么整个Raid就无法用了；

现在Raid卡一般都比较高级，可以针对插在上面的多块磁盘做多重Raid。比如这三块磁盘做Raid5，另外两块做Raid1。然后对操作系统提供两块『逻辑盘』。这里的逻辑盘对操作系统而言就是一块磁盘，但实际底层可能是多块磁盘。

逻辑盘不一定要占据整块独立的磁盘，同样RAID的几块盘也可以做成多块逻辑盘。假设有三块磁盘做成了Raid5，假设一共有200G空间，也可以从中在划分成两块，每块100G，相当于用户就看到了两块100G的磁盘。不过一般逻辑盘不会跨Raid实现。倒不是不能做，而是没需求，而且对上层造成不一致的印象：这磁盘怎么忽快忽慢的呀。

这个逻辑盘还有一个英语名字：LUN(Logic Unit Number)，现在存储系统一般把硬件虚拟出来的盘叫『LUN』，软件虚拟出来的盘叫『卷』。LUN这个名词原本是SCSI协议专属的，SCSI协议规定一条总线最多只能接16个设备(主机或者磁盘)，在大型存储系统中，可能有成千上万个设备，肯定是不够的，所以发明了一个新的地址标注方法，叫LUN，通过SCSI_ID LUN_ID来寻址磁盘。后来这个概念逐步发展成为所有硬件虚拟磁盘了。

操作系统看到逻辑盘之后，一般还要再做一次封装。逻辑盘始终都还是硬件层在做的事情，硬件层实现的特点就是效率高，但是不灵活，比如逻辑盘定好了100G就是100G，空间用光了想要调整为150G就只有干瞪眼了，实现成本很高。为了达到灵活性的目的，所以操作系统还要再做一层封装『卷管理』。这层卷管理就是把逻辑盘在软件层再拆分合并一下，组成新的操作系统真正看到的"磁盘"。

最后操作系统再在这些卷上面去做一些分区，并在分区上安装操作系统等工作。

磁盘独立闹革命

上面都是讲的单台机器内部的磁盘组织方式，而单台机器所提供的存储空间是有限的，毕竟机器大小空间是有限的，只能放得下那么几块盘。在一般的2U的机器里面能放得下20块盘就算是很不错的了。在实际工业需求中，对于一些大型应用来说，肯定是远远不够的。而工业界采用的方案就是：堆磁盘，单台机器装不下这么多磁盘就单独拿一个大箱子来装磁盘，再通过专线接到电脑接口上。

当然，在近些年又发展起来了一块新的技术领域大数据存储的市场——分布式存储。分布式存储价格便宜，但是性能较低，占据了不少不需要太高性能和查询语义不复杂的市场。分布式存储我们后面再谈，现在先看看堆磁盘这条路。

当磁盘多了之后，人们发现，磁盘容量是上去了，但是传输速度还是上不去。默认SCSI的导线传输机制有如下几个限制：

1. 规定最多只能接16个设备，也就是说一个存储设备最多只能有15台机器来访问；
2. SCSI导线最长不能超过25米，这对机房布线来说造成了很大的挑战；

于是SCSI在一些企业级应用市场开始遭到嫌弃，于是人们就寻求别的硬件解决方案，人们找到了：FC网络。

FC网络是上个世纪80年代研究网络的一帮人搞出来的网络交互方式，跟以太网是同类产品，有自己完整的一套OSI协议体系(从物理链路层到传输层以及应用层)。他就是以太网的高富帅版本，价格更贵，性能更高。而当时FC网络也主要是为了高速骨干网设计的，人家都没想到这东西还在存储系统领域里面大放异彩。

这里提一下，FC中的F是Fibre，而不是Fiber。前者是网络的意思，而不是光线。虽然一般FC网络都采用光纤作为传输介质，但是其主要定义并不只是光纤，而是一整套网络协议。

但是不管怎么样，FC网络的引入，完美解决了SCSI导线的问题：

1. FC网络就跟以太网类似，有自己的交换机，网络连接方式和路由算法，可以随便连接多少个设备；
2. 光纤传输最大甚至可以有上百公里，也就是说主机在北京，存储可以在青岛；
3. 传输带宽更大；

并且只是替换了硬件层的东西，指令集仍然是SCSI，所以对于上层来说迁移成本很低，所以在企业级应用里得到了广泛使用。

就目前主流的存储协议：短距离(机内为主)使用SAS，长距离使用FC。

经过如上的系列技术发展，大规模存储系统的技术方案也就逐渐成熟了，于是市面上就逐步出现了商业化的产品，其实就是一个带得有一堆磁盘的盒子，这个盒子我们把它叫做SAN(Storage Area Network)。

说到SAN，就必须要提另外一个概念：NAS（Network Attach Storage）。因为字母都一样只是换了个顺序，所以比较容易混淆。NAS其实就是SAN 文件系统。SAN提供的还是磁盘管理协议级的接口(ATA/SCSI)；NAS直接提供一个文件系统接口（ext/NTFS）。但是一般来说，SAN都是以FC网络(光纤高速网状网络)提供给主机的，所以性能高；而NAS一般都是通过以太网接入存储系统的，所以性能低。

另外，经常跟SAN和NAS一起的还有另外一个概念，DAS（Direct Attached Storage）。这个跟SAN类似，只是DAS只能被一台机器使用，而SAN提供了多个接口可以供多个用户使用。

二、文件系统介绍

文件系统磁盘分配

在存储知识栈上提到文件系统, 大家首先就关心他是如何管理好硬件层提供的磁盘空间的。

本文开篇就先描述典型的几种文件系统管理磁盘的技术方案: 连续分配, 链式分配, 索引分配。

连续分配

顾名思义, 就是创建文件的时候, 给分配一组连续的块。在单独拿出一块地方存储各个文件的meta信息, meta信息也很简单, 包含文件名, 起始位置和长度即可, 这个存放meta信息的地方也叫做FAT(文档分配表)。

如下图:

该方案的优点:

1. 简便, 适用于一次性写入操作;
2. 所需磁盘寻道次数和寻道时间最少;

缺点也很明显:

1. 文件不能动态增长, 因为后面的块可能已经分配给别人了;
2. 不利于文件的插入和删除, 插入文件之前需要声明文件大小;
3. 外部碎片问题;

为了克服连续分配的问题, 又进化出来了链式分配方案。

链式分配

链式分配即将文件块像链表一样管理起来, 每个块中放一个指针, 指针指向下一个文件块所在的位置。这样在FAT中存储也很简单, 只需要存储文件名, 起始块号和结束块号(都可以不存)。

如下图:

该方案的优点:

1. 提高磁盘利用率, 没有碎片问题
2. 有利于文件的插入, 删除

缺点:

1. 存取速度慢, 需要移动的磁道次数多, 寻道时间长;
2. 读写任何一个地方都需要沿着指针前进直到找到对应块为止;
3. 链接占据了一定的磁盘空间, 数据不是严格按照块大小分配;

索引分配

这是一个折衷方案, 也是现在大部分文件系统采用的方案, 他综合了连续分配和链式分配的好处。

该方案会在FAT中保存所有文件块的位置, 各文件系统都有一套自己对应的细节分配策略, 会保证一个文件尽量连续的同时, 又避免出现大量的磁盘碎片。

如下图:

该方案的优点是:

1. 能够保持好大部分文件的局部性
2. 满足文件插入, 删除的高效
3. 随机读写不需要沿着指针前进

缺点:

1. 会有较多的磁盘寻道次数
2. 索引表本身管理复杂, 也会带来额外的系统开销

ext文件系统

基本概念

1. 块. 即Block, 数据存储的最小单元, 每个块都有一个唯一的地址, 从0开始, 起源于第一个可以用来存储数据的扇区;
2. 超级块. 超级块保存了各种文件系统的meta信息, 比如块大小信息。他位于文件系统的2号和3号扇区(物理地址), 占用两个扇区大小;
3. 块组. 所有的块会划分成多个块组, 每个块组包含同样多个块, 但是可能整个文件系统整个块数不是块组的整数倍, 所以最后一个块组包含的个数可能会小于其他块;

总体结构

一个ext文件系统分成多个块组, 每个块组的结构基本相同, 如下:

解释如下:

1. 0~1号扇区: 引导扇区. 如果没有引导代码, 则这两个扇区为空, 全部用0填充;
2. 2~3号扇区: 超级块, 超级块包含各种meta信息:
3. 块大小, 每个块组包含块数, 总块数, 第一个块前保留块数, inode节点数, 每个块组的inode节点数
4. 卷名, 最后挂载时间, 挂载路径, 文件系统是否干净, 是否要调用一致性检查标识
5. 空间inode节点和空闲块的记录信息, 在分配inode节点和新块的时候使用
6. 组描述符表:
7. 位于超级块后面的一个块, 注意在超级块之前只占用了4个扇区, 如果一个块大小超过4个扇区的话, 这里就会有空的扇区。
8. 组描述符表中包含了所有块组的描述信息, 每个块组占据32个字节(差不多是8个整数的大小)。如果格式化使用默认参数, 那么组描述符表不会超过一块块组。
9. 组描述符和超级块在每个块组中都有一个备份, 但是激活了稀疏超级块特征的情况除外。
10. 稀疏超级块即不是在所有块组中都存储超级块和组描述符的备份, 默认该策略被激活, 其策略类似当块组号是3,5,7的幂的块组才存副本。
11. 块位图表
12. 每个块对应一个bit, 只包含了本块组的信息。而文件系统创建的时候, 默认每个块组包含的块数跟每个块包含的bit数是一样的, 这种情况下每个块位图表正好等于一个块的大小。
13. 而该位图表的块的起始位置会在组描述符表中指定, 大小则为块组中包含块数个bit。
14. inode位图块
15. 跟块位图表类似, 通常情况他也只占用一个块。通常一个块组中的inode节点数会小于block数量, 所以其不会超过一个块大小。
16. inode节点表
17. 每个inode都占用128位的一个描述信息, 起始位置在组描述符中表示, 大小为inode节点数*128。
18. 数据区
19. 这就是真正存储数据的区域。

块大小为4096的时候, 各部分和扇区对应关系如下图:

块大小为2048的时候, 各部分和扇区对应关系如下图:

超级块详细信息

超级块总是位于文件系统的第1024~2048字节处。

超级块中包含的信息如下:

偏移(16进制)字节数含义&解释00~034文件系统中总inode节点数04~074文件系统中总块数08~0B4为文件系统预保留的块数0C~0F4空闲块数10~134空间inode节点数14~1740号块组起始块号18~1B4块大小(1024左移位数)1C~1F4片段大小, 跟块大小一模一样20~234每个块组中包含的块数量24~274每个块组中包含的片段数量, 跟包含的快数量一致28~2B4每个块组中包含的inode节点数量2C~2F4文件系统最后挂载时间30~334文件系统最后写入时间34~352当前挂载数36~372最大挂载数38~392文件系统签名标识 53EF3A~3B2文件系统状态, 正常, 错误, 恢复了孤立的inode节点3C~3D2错误处理方式, 继续, 以只读方式挂载3E~3F2辅版本号40~434最后进行一致性检查的时间44~474一致性检查的间隔时间48~4B4创建本文件系统的操作系统4C~4F4主版本号, 只有该值为1的时候, 偏移54之后的扩展超级块的一些动态属性值才是有意义的50~512默认为UID的保留块52~532默认为GID的保留块54~572第一个非保留的inode节点号, 即用户可以使用的第一个inode节点号58~592每个inode节点的大小字节数5A~5B2本超级块所在的块组号5C~5F4兼容标识特征60~634非兼容标识特征64~674只读兼容特征标识68~7716文件系统ID号78~8716卷名88~C764最后的挂载路径C8~CB4位图使用的运算法则CC~CC1文件再分配的块数CD~CD1目录再分配的块数CE~CF2未使用D0~DF16日志IDE0~E34日志inode节点E4~E74日志设备E8~EB4孤立的inode节点表EC~3FF788未使用

块组描述符详细信息

每个块组描述符占用32个字节, 其数据结构如下:

偏移(16进制)字节数含义&解释00~034块位图起始地址(块号)04~074inode节点位图起始地址(块号)08~0B4inode节点表起始地址(块号)0C~0D2块组中空闲块数0E~0F2块组中空闲inode节点数10~112块组中的目录数12~1F-未使用

inode信息

每个inode会被分配给一个目录或者一个文件, 每个inode包含了128个字节, 里面包含了这个文件的各种meta信息。

在所有inode中, 1~10号会用作保留给内核使用, 在这些保留节点中, 2号节点用于存储根目录信息, 1号表示坏块, 8号表示日志文件信息。

第一个用户可见的都是从11号inode开始, 11号节点一般用作lost found目录, 当检查程序发现一个inode节点已经被分配, 但是没有文件名指向他的时候, 就会把他添加到lost found目录中并赋予一个新的文件名。

inode通过三级指针的方式来找到文件数据最终存储的数据块, 见下图:

这种方式能保证小文件的读取效率的同时, 也支持大文件的读取。

目录项

在ext文件系统中, 每个目录也对应一个inode节点, 该inode节点对应的数据块里面会存储该目录下所有文件/目录的信息。

每个文件/目录对应的信息就叫目录项, 目录项包含的内容也很简单, 主要就是文件名和指向该文件名的inode指针, 详细信息如下:

偏移(16进制)字节数含义&解释00~034inode节点号04~052本目录项的长度字节数06~061名字长度字节数07~071文件类型08~不定长度名字的ascii码

当文件删除的时候, 不会真正删除文件, 会将该文件所属目录对应的目录项给删除, 同时将对应数据块在快位图表中标记为0。

链接

1. 硬链接是指在另外一个目录对应的目录项中增加一个目录项。硬链接建立之后, 用户无法通过文件名来判断到底哪个是原文件名, 哪个是链接名;
2. 软连接是一种文件类型, 该文件里面就存储源文件的完整路径, 如果源文件完整路径长度小于60个字节, 那么就将该值直接存储在inode节点表中, 避免浪费数据块;

分配策略

1. 首先判断应该在哪个块组中分配
2. 如果是为文件创建节点
3. 默认会在其父目录所在的组中为其创建节点, 这样可以确保一个目录中所有文件都位于一个大致的区域中
4. 如果父目录所在组没有空闲的节点或者空闲的块了, 就到别的块组中为该文件分配节点, 找寻别的块组的算法如下
5. 每次讲当前组号加上2^N次方再求hash
6. 如果上面的算法没找到, 就线性查找
7. 如果是为目录创建节点
8. 会将其分配到可用空间较多的块组中, 分配算法如下:
9. 首先利用超级块中的剩余inode和剩余块数字算出每个块组的平均剩余数字, 然后依次找到一个大于平均值的块组
10. 如果没找到, 就利用块组描述符表中的信息, 找到一个最空闲的块组
11. 当一个数据块分配给某文件之后
12. 该块原来的内容会被请出, inode节点对应的各种元信息会跟着做修改
13. 如果是文件, 节点对应链接数会设置为1, 如果是目录, 链接数会被设置为2

实际创建/删除文件过程

我们创建一个/xuanku/file.txt, 该文件大小为10000字节, 文件块大小为4096, 那么下面来看一下过程:

1. 读取文件系统的1024字节~2048字节, 即超级块信息。通过超级块得到快大小为4096, 每个块组含有8192个块以及2008个inode节点
2. 读取文件系统中第1个块(即组描述符表), 得到所有块组布局信息
3. 访问2号inode节点(即根节点), 通过读取根节点数据块信息, 假设读到其位于5号块
4. 在第5号块所有目录项中从前往后遍历, 直到找到文件名为xuanku的目录项, 读到该inode节点为4724
5. 每个块组有2008个inode, 用4724针对2008取模, 得到的结果是2号块组
6. 通过组描述符表中得到第2个块组的inode节点表起始于16378号块
7. 从16378号块读取inode节点表中查找4724号对应的inode节点(708号表项), 查询到该xuanku的目录内容位于17216号块
8. 从17216块读取xuanku目录项内容, 将file.txt相关信息更新到该块的目录项当中
9. 然后开始为文件分配inode节点, 默认会放到父目录所在块组, 即2号块组, 再次2号块组的inode节点表16378, 开始从4724往后找到第一个可用的inode节点分配给该文件, 假设找到的是4850号inode。
10. 然后就给4850号的inode位图表设置为1, 组描述符的空闲inode节点数和超级块的总空闲inode节点数都减1, 将inode节点的地址写入file.txt对应的目录项当中, 然后写各种时间, 记录日志
11. file.txt需要3个块的存储空间, 通过2号块组描述符找到块位图对应的块, 并从前往后找到可用的块。然后将对应的位设置为1, 并更新到inode节点当中
12. 然后将文件的内容写入到对应的块中

下面再演示一下将该文件删除的过程:

读取文件系统的1024字节~2048字节, 即超级块信息。通过超级块得到快大小为4096, 每个块组含有8192个块以及2008个inode节点

读取文件系统中第1个块(即组描述符表), 得到所有块组布局信息

访问2号inode节点(即根节点), 通过读取根节点数据块信息, 假设读到其位于5号块

在第5号块所有目录项中从前往后遍历, 直到找到文件名为xuanku的目录项, 读到该inode节点为4724

每个块组有2008个inode, 用4724针对2008取模, 得到的结果是2号块组

通过组描述符表中得到第2个块组的inode节点表起始于16378号块

从16378号块读取inode节点表中查找4724号对应的inode节点(708号表项), 查询到该xuanku的目录内容位于17216号块

从17216块读取xuanku目录项内容, 读到file.txt的inode节点为4850

然后取消file.txt的目录项分配, 修改系列xuanku目录对应的目录项信息

取消inode节点信息, 修改2号块组对应的inode节点表信息, 将inode节点位设置为0, 更新块组描述符和超级块的空闲inode节点数加1

还要回收文件内容对应的6个块空间, 将块位图表中的bit设置为0, 清除inode节点的块指针, 更新块组描述符和超级块的空闲块数加1。

三、分布式存储系统

分布式系统主要分成存储模型和计算模型两类。本文主要描述的是存储模型的介绍。其中计算模型的分布式系统原理跟存储模型类似，只是会根据自身计算特点加一些特殊调度逻辑进去。

任何一个分布式系统都需要考虑如下5个问题：

1.数据如何分布

就像把鸡蛋放进篮子里面。一般来说篮子大小是一样的，当然也有的系统支持不一样大小的篮子。鸡蛋大小也不一样，有很多系统就把鸡蛋给"切割"成一样大小然后再放。并且有的鸡蛋表示对篮子有要求，比如对机房/机架位的要求。

衡量一个数据分布算法好不好就看他是否分得足够均匀，使得所有机器的负载方差足够小。

2.如何容灾

分布式系统一个很重要的定位就是要让程序自动来管机器，尽量减少人工参与，否则一个分布式系统的运维成本将不可接受。

容灾问题非常复杂，有很多很成熟的系统也不敢保证自己做得特别好，那么来看看一个典型的系统都有可能出哪些问题吧：

1.机器宕机

这是最常见的故障了。系统中最容易出问题的硬盘的年故障率可能能达到10%。这样算下来，一个有1000台机器的集群，每一个星期就会有2台机器宕机。所以在机器数量大了之后，这是一个很正常的事情。

一般一台机器出故障之后修复周期是24小时，这个过程是人工接入换设备或者重启机器。在机器恢复之后内存信息完全丢失，硬盘信息可能可以保存。

一个分布式系统必须保证一台机器的宕机对服务不受影响，并且在修复好了之后再重新放到集群当中之后也能正常工作。

2.网络故障

这是最常见且要命的故障。就是该问题会大大增加分布式系统设计的难度。故障一般发生在网络拥塞，路由变动，设备异常等情况。出现的问题可能是丢包，可能是延时，也可能是完全失去连接。

有鉴于此，我们一般在设计分布式系统的时候，四层协议都采用TCP，很少采用UDP/UDT协议。而且由于TCP协议并不能完全保证数据传输到对面，比如我们再发送数据，只要数据写入本地缓冲区，操作系统就会返回应用层说发送成功，但是有可能根本没送到对面。所以我们一般还需要加上应用层的ACK，来保证网络层的行为是可预期的。

但是，即使加上应用层的ACK，当发送请求之后迟迟没收到ACK。这个时候作为发送方也并不知道到底对方是直接挂了没收到请求，还是收到请求之后才挂的。这个尤其是对于一些控制命令请求的发送尤为致命。

一般系统有两种方案：

1. 发送查询命令来判断到底是哪种情况
2. 将协议设计成"幂等性"(即可重复发送数据并不影响最终数据), 然后不停重试

3.其他异常

比如磁盘坏块，但是机器并没有宕机；机器还活着，就是各种操作特别慢；由于网络拥塞导致一会网络断掉，不发送数据之后又好了，一旦探活之后重新使用又挂了等恶心的情况；

这些异常都需要根据实际情况来分析，在长期工程实践中去调整解决。

并且令人非常沮丧的事实是：你在设计阶段考虑的异常一定会在实际运行情况中遇到，你没考虑到的异常也会在实际运行中遇到。所以分布式系统设计的一个原则是：不放过任何一个你看得到的异常。

3.读写过程一致性如何保证

一致性的概率很简单，就是我更新/删除请求返回之后，别人是否能读到我新写的这个值。对于单机系统，这个一致性要达到很简单，大不了是损失一点写的效率。但是对于分布式系统，这个就复杂了。为了容灾，一份数据肯定有多个副本，那么如何更新这多个副本以及控制读写协议就成了一个大问题。

而且有的写操作可能会跨越多个分片，这就更复杂了。再加上刚才提到的网络故障，可能在同步数据的时候还会出现各种网络故障，想想就头疼。

而且即使达到了一致性，有可能读写性能也会受到很大损失。我们设计系统的时候就像一个滑动条，左边是一致性，右边是性能，两者无法同时满足(CAP原理)。一般的系统会取折衷，设计得比较好的系统能够让用户通过配置来控制这个滑动条的位置，满足不同类型的需求。

一致性一般怎么折衷呢？我们来看看如下几种一致性的定义。注意除了强一致性以外，其他几种一致性并不冲突，一个系统可以同时满足一种或者几种一致性特点。

强一致性

不用多说，就是最严格的一致性要求。任何时候任何用户只要写了，写请求返回的一霎那，所有其他用户都能读到新的值了。

最终一致性

这个也是提得很多的一个概念，很多系统默认提供这种方式的一致性。即最终系统将将达到"强一致性"的状态，但在之前会有一段不确定的时间，系统处于不一致的状态。

会话一致性

这个也很容易理解，能满足很多场景下的需求。在同一个会话当中，用户感受到的是"强一致性"的服务。

单调一致性

这个比会话一致性还要弱一点。他之保证一个用户在读到某个数据之后，绝对不会读到比上一次读到的值更老的数据。

4.如何提高性能

分布式系统设计之初就是为了通过堆积机器来增加系统整体性能，所以系统性能也非常重要。性能部分一般会受一致性/容灾等设计的影响，会有一定的折衷。

衡量一个分布式系统的性能指标往往有：

1. 最大容量
2. 读qps
3. 写qps

5.如何保证横向扩展

横向扩展是指一个集群的服务能力是否可以通过加机器做到线性扩展。

附NAS、SAN、DAS的架构及比较

在网络存储中，有着各种网络存储解决方案，例如：SAN，NAS，DAS存储网络，它们各自有着各自的特点，其运用场景也有所不同。下面就说说各自的特点。

一、SAN

SAN（Storage Area Network）存储区域网络，是一种高速的、专门用于存储操作的网络，通常独立于计算机局域网（LAN）。SAN将主机（管理server，业务server等）和存储设备连接在一起，能够为其上的任意一台主机和任意一台存储设备提供专用的通信通道。SAN将存储设备从服务器中独立出来，实现了服务器层次上的存储资源共享。SAN将通道技术和网络技术引入存储环境中，提供了一种新型的网络存储解决方案，能够同时满足吞吐率、可用性、可靠性、可扩展性和可管理性等方面的要求。

通常SAN由磁盘阵列（RAID）连接光纤通道（Fibre Channel）组成（为了区别于IP SAN，通常SAN也称为FC-SAN）。SAN和服务器和客户机的数据通信通过SCSI命令而非TCP/IP，数据处理是“块级”（block level）。SAN也可以定义为是以数据存储为中心，它采用可伸缩的网络拓扑结构，通过具有高传输速率的光通道的直接连接方式，提供SAN内部任意节点之间的多路可选择的数据交换，并且将数据存储管理集中在相对独立的存储区域网内。SAN最终将实现在多种操作系统下，最大限度的数据共享和数据优化管理，以及系统的无缝扩充。

其中，SAN网络又被细分为FC-SAN网络和IP-SAN网络。

1、FC-SAN

FC-SAN顾名思义就是直接通过FC通道来连接磁盘阵列，数据通过发送SCSI命令来直接与硬件进行通信，从而提高了整体的速率。

FC-SAN的构成：

在FC-SAN中，有一些专用的硬件和软件。硬件包括FC卡、FC HUB、FC交换机、存储系统等，软件主要是FC控制卡针对各种操作系统的驱动程序和存储管理软件。

①FC卡：主要用于主机与FC设备之间的连接。

②FC HUB：内部运行仲裁环拓扑，连接到HUB的节点共享100MB/S带宽（或更高）。

③FC交换机：内部运行Fabric拓扑，每端口独占100MB/S带宽（或更高）。

④FC存储设备：采用FC连接方式，光纤接口可以有一到多个。FC存储设备通常采用光纤的硬盘，也有Fibre to SCSI（Fibre to ATA）的解决方案，使用SCSI（或ATA）的硬盘，在整个配置上较便宜。

⑤存储网络管理软件：存储管理软件主要的功能是自动发现网络拓扑及映射，当在存储网络中增加或减少时自动发现及组态。

⑥高性能的光纤通道交换机和光纤通道网络协议是FC-SAN的关键。把以光纤通道交换机为骨干的网络拓扑结构称为“SAN Fabric”。而光纤通道协议是FC-SAN的另一个本质特征。FC-SAN正是利用光纤通道协议上加载SCSI协议来达到可靠的块级数据传输。

FC-SAN的应用场景：

由于FC-SAN是为在服务器和存储设备之间传输大块数据而进行优化的，因此对于以下应用来说是理想的选择：

①关键任务数据库应用，其中可预计的响应时间、可用性和可扩展性是基本要素。

②集中的存储备份，其中性能、数据一致性和可靠性可以确保企业关键数据的安全。

③高可用性和故障切换环境可以确保更低的成本、更高的应用水平。

④可扩展的存储虚拟化，可使存储与直接主机连接相分离，并确保动态存储分区。

⑤改进的灾难容错特性，在主机服务器及其连接设备之间提供光纤通道高性能和扩展的距离。

FC-SAN的优点：

面对迅速增长的数据存储需求，企业和服务提供商渐渐开始选择FC-SAN作为网络基础设施，因为SAN具有出色的可扩展性。事实上，SAN比传统的存储架构具有更多显著的优势。例如，传统的服务器连接存储通常难于更新或集中管理。每台服务器必须关闭才能增加和配置新的存储。相比较而言，FC-SAN不必宕机和中断与服务器的连接即可增加存储。FC-SAN还可以集中管理数据，从而降低了总体拥有成本。

利用光纤通道技术，FC-SAN可以有效地传输数据块。通过支持在存储和服务器之间传输海量数据块，SAN提供了数据备份的有效方式。因此，传统上用于数据备份的网络带宽可以节约下来用于其他应用。

开放的、业界标准的光纤通道技术还使得FC-SAN非常灵活。FC-SAN克服了传统上与SCSI相连的线缆限制，极大地拓展了服务器和存储之间的距离，从而增加了更多连接的可能性。改进的扩展性还简化了服务器的部署和升级，保护了原有硬件设备的投资。

此外，FC-SAN可以更好地控制存储网络环境，适合那些基于交易的系统在性能和可用性方面的需求。SAN利用高可靠和高性能的光纤通道协议来满足这种需要。

FC-SAN的另一个长处是传送数据块到企业级数据密集型应用的能力。在数据传送过程中，FC-SAN在通信结点（尤其是服务器）上的处理费用开销更少，因为数据在传送时被分成更小的数据块。因此，光纤通道FC-SAN在传送大数据块时非常有效，这使得光纤通道协议非常适用于存储密集型环境。

2、IP-SAN

简单来讲，IP-SAN（IP存储）的通信通道是使用IP通道，而不是光纤通道，把服务器与存储设备连接起来的技术，除了标准已获通过的iSCSI，还有FCIP、iFCP等正在制定的标准。而iSCSI发展最快，已经成了IP存储一个有力的代表。

像光纤通道一样，IP存储是可交换的，但是与光纤通道不一样的是，IP网络是成熟的，不存在互操作性问题，而光纤通道SAN最令人头痛的就是这个问题。IP已经被IT业界广泛认可，有非常多的网络管理软件和服务产品可供使用。

二、NAS

NAS（Network Attached Storage）网络附加存储。在NAS存储结构中，存储系统不再通过I/O总线附属于某个服务器或客户机，而直接通过网络接口与网络直接相连，由用户通过网络访问。

NAS实际上是一个带有瘦服务器的存储设备，其作用类似于一个专用的文件服务器。这种专用存储服务器去掉了通用服务器原有的不适用的大多数计算功能，而仅仅提供文件系统功能。与传统以服务器为中心的存储系统相比，数据不再通过服务器内存转发，直接在客户机和存储设备间传送，服务器仅起控制管理的作用。

NAS的特点：

NAS使用了传统以太网协议，当进行文件共享时，则利用了NFS和CIFS以沟通NT和Unix系统。由于NFS和CIFS都是基于操作系统的文件共享协议，所以NAS的性能特点是进行小文件级的共享存取。

NAS设备是直接连接到以太网的存储器，并以标准网络文件系统如NFS、SMB/CIFS over TCP/IP接口向客户端提供文件服务。NAS设备向客户端提供文件级的服务。但内部依然是以数据块的层面与它的存储设备通讯。文件系统是在这个NAS 存储器里。

NAS的优点：

NAS适用于那些需要通过网络将文件数据传送到多台客户机上的用户。NAS设备在数据必须长距离传送的环境中可以很好地发挥作用。

NAS设备非常易于部署。可以使NAS主机、客户机和其他设备广泛分布在整个企业的网络环境中。NAS可以提供可靠的文件级数据整合，因为文件锁定是由设备自身来处理的。

NAS应用于高效的文件共享任务中，例如UNIX中的NFS和Windows NT中的CIFS，其中基于网络的文件级锁定提供了高级并发访问保护的功能。

三、DAS

DAS（Direct Attached Storage）直接附加存储，直接附加存储是指将存储设备通过总线（SCSI、PCI、IDE等）接口直接连接到一台服务器上使用。DAS购置成本低，配置简单，因此对于小型企业很有吸引力。

DAS存在问题：

①服务器本身容易成为系统瓶颈。

②服务器发生故障，数据不可访问。

③对于存在多个服务器的系统来说，设备分散，不便管理。同时多台服务器使用DAS时，存储空间不能在服务器之间动态分配，可能造成相当的资源浪费。

④数据备份操作复杂。

四、总结

,