【操作系统】模块六 ：文件系统

Linux的文件目录

• 学习文件系统的意义在于文件系统有很多设计思路可以迁移到实 际的工作场景中，比如：MySQL 的 binlog 和 Redis AOF 都像极了日志文件系统的设计； B Tree 用于加速磁盘数据访问的设计，对于索引设计也有通用的意义。
• 比如 Linux 可以支持每个目录用不同的文件系统。这些文 件看上去是一个个目录和文件，实际上可能是磁盘、内存、网络文件系统、远程磁盘、网卡、随机数产 生器、输入输出设备等，这样虚拟文件系统就成了整合一切设备资源的平台。大量的操作都可以抽象成 对文件的操作，程序的书写就会完整而统一，且扩展性强。
• Linux 所有的文件都建立 在虚拟文件系统（Virtual File System ，VFS）
  
• 因此，Linux 上不同的目录可能是不同的磁盘，不同的文件可能是不同的设备。

分区结构

• /是对应一个磁盘还是多个磁盘呢？在/创建目录的时候，目录属于哪个磁盘呢？
  
  你可以用df -h查看上面两个问题的答案，在上图中我的/挂载到了/dev/sda5上。如果你想要看到更 多信息，可以使用df -T，如下图所示
  

• /dev/sda5究竟是一块磁盘还是别的什么？ -> fdisk -l查看
  

• 你可以看到我的 Linux 虚拟机上，有一块 30G 的硬盘（当然是虚拟的）。然后这块硬盘下有 3 个设备 （Device）：/dev/sda1, /dev/sda2 和 /dev/sda5。在 Linux 中，数字 1~4 结尾的是主分区，通常一块 磁盘最多只能有 4 个主分区用于系统启动。主分区之下，还可以再分成若干个逻辑分区，4 以上的数字 都是逻辑分区。因此/dev/sda2和/dev/sda5是主分区包含逻辑分区的关系

挂载

• 上面例子中/dev/sda5分区被挂载到了/下。 这样在/创建的文 件都属于这个/dev/sda5分区。 另外，/dev/sda5采用ext4文件系统。可见不同的目录可以采用不同 的文件系统
• 将一个文件系统映射到某个目录的过程叫作挂载（Mount）。当然这里的文件系统可以是某个分区、某 个 USB 设备，也可以是某个读卡器等。你可以用mount -l查看已经挂载的文件系统

• sysfs让用户通过文件访问和设置设备驱动信息。
• proc是一个虚拟文件系统，让用户可以通过文件访问内核中的进程信息。
• devtmpfs在内存中创造设备文件节点。
• tmpfs用内存模拟磁盘文件。
• ext4是一个通常意义上我们认为的文件系统，也是管理磁盘上文件用的系统。

mount /dev/sda6 /abc 
上面这个命令将/dev/sda6挂载到目录abc

目录结构

Linux 对文件系统中的目录进行了一定的归类

• 最顶层的目录称作根目录， 用/表示。/目录下用户可以再创建目录，但是有一些目录随着系统创建就 已经存在，接下来我会和你一起讨论下它们的用途。
• **/bin（二进制）**包含了许多所有用户都可以访问的可执行文件，如 ls, cp, cd 等。这里的大多数程序都是 二进制格式的，因此称作bin目录。bin是一个命名习惯，比如说nginx中的可执行文件会在 Nginx 安 装目录的 bin 文件夹下面。
• /dev（设备文件） 通常挂载在devtmpfs文件系统上，里面存放的是设备文件节点。通常直接和内存进 行映射，而不是存在物理磁盘上。值得一提的是其中有几个有趣的文件，它们是虚拟设备。
• /dev/null是可以用来销毁任何输出的虚拟设备。你可以用>重定向符号将任何输出流重定向 到/dev/null来忽略输出的结果。
• /dev/zero是一个产生数字 0 的虚拟设备。无论你对它进行多少次读取，都会读到 0。
• /dev/ramdom是一个产生随机数的虚拟设备。读取这个文件中数据，你会得到一个随机数。你不停地 读取这个文件，就会得到一个随机数的序列。
• /etc（配置文件），/etc名字的含义是and so on……，也就是“等等及其他”，Linux 用它来保管程序的 配置。比如说mysql通常会在/etc/mysql下创建配置。再比如说/etc/passwd是系统的用户配置，存 储了用户信息。
• /proc（进程和内核文件） 存储了执行中进程和内核的信息。比如你可以通过/proc/1122目录找到和 进程1122关联的全部信息。还可以在/proc/cpuinfo下找到和 CPU 相关的全部信息。
• /sbin（系统二进制） 和/bin类似，通常是系统启动必需的指令，也可以包括管理员才会使用的指令。
• /tmp（临时文件） 用于存放应用的临时文件，通常用的是tmpfs文件系统。因为tmpfs是一个内存文 件系统，系统重启的时候清除/tmp文件，所以这个目录不能放应用和重要的数据。
• /var （Variable data file,，可变数据文件） 用于存储运行时的数据，比如日志通常会存放 在/var/log目录下面。再比如应用的缓存文件、用户的登录行为等，都可以放到/var目录下，/var 下的文件会长期保存。
• /boot（启动） 目录下存放了 Linux 的内核文件和启动镜像，通常这个目录会写入磁盘最头部的分区， 启动的时候需要加载目录内的文件。
• /opt（Optional Software，可选软件） 通常会把第三方软件安装到这个目录。以后你安装软件的时 候，可以考虑在这个目录下创建。
• /root（root 用户家目录） 为了防止误操作，Linux 设计中 root 用户的家目录没有设计在/home/root 下，而是放到了/root目录。
• /home（家目录） 用于存放用户的个人数据，比如用户lagou的个人数据会存放到/home/lagou下 面。并且通常在用户登录，或者执行cd指令后，都会在家目录下工作。 用户通常会对自己的家目录拥 有管理权限，而无法访问其他用户的家目录。
• /media（媒体） 自动挂载的设备通常会出现在/media目录下。比如你插入 U 盘，通常较新版本的 Linux 都会帮你自动完成挂载，也就是在/media下创建一个目录代表 U 盘。
• /mnt（Mount，挂载） 我们习惯把手动挂载的设备放到这个目录。比如你插入 U 盘后，如果 Linux 没 有帮你完成自动挂载，可以用mount命令手动将 U 盘内容挂载到/mnt目录下。
• /svr（Service Data,，服务数据） 通常用来存放服务数据，比如说你开发的网站资源文件（脚本、网 页等）。不过现在很多团队的习惯发生了变化， 有的团队会把网站相关的资源放到/www目录下，也有的团队会放到/data下。总之，在存放资源的角度，还是比较灵活的。

/usr（Unix System Resource） 包含系统需要的资源文件，通常应用程序会把后来安装的可执行文件 也放到这个目录下，比如说

• vim编辑器的可执行文件通常会在/usr/bin目录下，区别于ls会在/bin目录下
• /usr/sbin中会包含有通常系统管理员才会使用的指令。
• /usr/lib目录中存放系统的库文件，比如一些重要的对象和动态链接库文件。
• /usr/lib目录下会有大量的.so文件，这些叫作Shared Object，类似windows下的dll文 件。
• /usr/share目录下主要是文档，比如说 man 的文档都在/usr/share/man下面。

文件系统底层设计 FAT、NTFS 和 Ext3 文件系统有什么区别？

硬盘分块

• 使用硬盘和使用内存有一个很大的区别，内存可以支持到字节级别的随机存取，而这种情况在硬盘中通 常是不支持的。
• **为了提高性能，通常会将物理存储（硬盘）划分成一个个小块，**比如每个 4KB。这样做也可以让 硬盘的使用看起来非常整齐，方便分配和回收空间。况且，数据从磁盘到内存，需要通过电子设备，比 如 DMA、总线等，如果一个字节一个字节读取，速度较慢的硬盘就太耗费时间了，因此一次读/写一个块（Block）才是可行的方案。
  
• 这样做还有一个好处就是如果你知道块的序 号，就可以准确地计算出块的物理位置。

文件的描述

如何利用上面的硬盘存储文件，就是文件系统（File System）要负责的事情了

• 3 种文件系统：
• 早期的 FAT 格式
• 基于 inode 的传统文件系统
• 日志文件系统（如 NTFS, EXT2、3、4）

这种文件索引节点（inode）的方式，完美地解决了 FAT 的缺陷，一直被沿用至今。FAT 要把所有的块 信息都存在内存中，索引节点只需要把用到的文件形成数据结构，而且可以使用虚拟内存分配空间，随 着页表置换，这就解决了 FAT 的容量限制问题

目录的实现

目录是特殊的文件，所以每个目录都有自己的 inode。目录是文件的集合，所以目录的内容中必须有所有其下文件的 inode 指针。

文件名也最好不要放到 inode 中，而是放到文件夹中。这样就可以灵活设置文件的别名，及实现一个文 件同时在多个目录下。

• 硬链接有一个非常显著的特点，硬链接的双方是平等的。上面的程序我们用ln指令为文件 a 创造了一 个硬链接b。如果我们创造完删除了 a，那么 b 也是可以正常工作的。如果要删除掉这个文件的 inode，必须 a,b 同时删除。这里你可以看出 a,b 是平等的。
  

软链接

软链接的原理如下图：

• 所有写操作先存入缓冲区，然后每过一定的秒数，才进行一次持久化。这种设计，是一个很好的 思路，但最大的问题在于容错。 比如上图的步骤 1 或者步骤 2 只执行了一半，如何恢复？如果步骤 2 只 写入了一半，那么数据就写坏了。如果步骤 1 只写入了一半，那么数据就丢失了。无论出现哪种问题， 都不太好处理。更何况写操作和写操作之间还有一致性问题，比如说一次删除 inode 的操作后又发生了 写入……
  
• 解决上述问题的一个非常好的方案就是利用日志。

• 上图这种设计可以让写入变得非常快速，多数时间都是写内存，最后写一次磁盘。而上图这样的设计成不成立，核心在能不能解决容灾问题。
  你可以思考一下这个问题——丢失一批日志和丢失一批数据的差别大不大。其实它们之间最大的差别在 于，如果丢失一批日志，只不过丢失了近期的变更；但如果丢失一批数据，那么就可能造成永久伤害。
• 为了进一步避免损失，一种可行的方案就是**创建还原点（Checkpoint），**比如说系统把最近 30s 的日志 都写入一个区域中。下一个 30s 的日志，写入下一个区域中。每个区域，我们称作一个还原点。创建还原点的时候，我们将还原点涂成红色，写入完成将还原点涂成绿色。
  

总结

• FAT 的设计简单高效，如果你要自己管理一定的空间，可以优先考虑这种设计。
• inode 的设计在内存中创造了一棵树状结构，对文件、目录进行管理，并且索引到磁盘中的数据。这是一种经典的数据结构，这种思路会被数据库设计、网络资源管理、缓存设计反复利用。
• 日志文件系统——日志结构简单、容易存储、按时间容易分块，这样的设计非常适合缓冲、批量写入和故障恢复。

多分布式系统的设计也是基于日志，比如 MySQL 同步数据用 binlog，Redis 的 AOF，著名的分布式一致性算法 Paxos ，因此 Zookeeper 内部也在通过实现日志的一致性来实现分布式一致性。

FAT、NTFS 和 Ext3 有什么区别？

【解析】FAT 通过内存中一个类似链表的结构，实现对文件的管理。NTFS 和 Ext3 是日志文件系统，它们和 FAT 最大的区别在于写入到磁盘中的是日志，而不是数据。日志文件系统会先把日志写入到内存中一个高速缓冲区，定期写入到磁盘。日志写入是追加式的，不用考虑数据的覆盖。一段时间内的日志内容，会形成还原点。这种设计大大提高了性能，当然也会有一定的数据冗余。

MySQL 的B树 和 B+树

B 树和 B+ 树是两种数据结构，构建了磁盘中的高速索引结构，因此不仅 MySQL 在用，MongoDB、Oracle 等也在用，基本属于数据库的标配常规操作。

行存储和列存储

行存储

行存储本质就是数据一个接着一个排列，一行数据后面 马上跟着另一行数据。如果订单表很大，一个磁盘块（Block）存不下，那么实际上就是每个块存储一定的行数。 类似下图这样的结构：

行存储更新一行的操作，往往可以在一个块（Block）中进行。而查询数据，聚合数据（比如求 4 月份的 订单数），往往需要跨块（Block）。因此， 行存储优点很明显，更新快、单条记录的数据集中，适合事务。但缺点也很明显，查询慢。

列存储（Column Storage）

列存储中数据是一列一列存的。还以订单表为 例，如下图所示：

• 每个列的数据都聚集在一起。
• 特别是更新某一条记录的时候，需要更新多 处，速度很慢。优势其实是在查询和聚合运算。
  总结一下，行存储、列存储，最终都需要把数据存到磁盘块。行存储记录一个接着一个，列存储一列接 着一列。

为什么行存储更适合事务？

实适合不适合是相对的，说行存储适合是因为列存储非常不适合事务。试想一下，你更新一个表的若 干个数据，如果要在不同块中更新，就可能产生多次更新操作。更新次数越多，保证一致性越麻烦。在 单机环境我们可以上锁，可以用阻塞队列，可以用屏障……但是分布式场景中保证一致性（特别是强一致 性）开销很大。因此我们说行存储适合事务，而列存储不适合。

索引

• 如果我们想查询一个id，一般都会想到二分，但是直接在原始数据上排序，我们可能会把数据弄乱，常规做法是设计冗余数据描述这种排序关系—— 这就是索引
• 订单（10001）是第 2 个订单。但是进行排序后，订单（10001）会到第 1 个位置。这样会弄乱订单 ID（10001）和 金额（100.00）对应的关系。
• 用空间换时间，额外将订单列拷贝一份排序：
  
• 以上这种专门用来进行数据查询的额外数据，就是索引。索引中的一个数据，也称作索引条目。上面的 索引条目一个接着一个，每个索引条目是 <订单 ID, 序号> 的二元组。
• 所以我们不能用一种线性结构将磁盘排序。那么树呢？ 比如二叉搜索树（Binary Serach Tree）行不行 呢？利用磁盘的空间形成一个二叉搜索树，例如将订单 ID 作为二叉搜索树的 Key。
• 复合索引，比如 <订单状态、日期、序号> 作为一个索引条目，其实就是先按照订单状态，再按照日期排序的索引。所以复合索引，无非就是多消耗一些空间，排序维度多一些。而且你可以看出复合索引和单列索引完全 是独立关系，所以我们可以认为每创造一组索引，就创造了一份冗余的数据。也创造了一种特别的查询 方式。
• 核心的问题：**上面的索引是一个连续的、从小到大的索引，**那么应不应该使用 这种从小到大排序的索引呢？？ 应该 ， 因为无论是单索引还是复合索引查询的时候都是继续二分查找.

二叉搜索树

• 二叉搜索树的特点是一个节点的左子树的所有节点都小于这个节点，右子树的所有节点都 大于这个节点。而且，因为索引条目较少，确实可以考虑在查询的时候，先将足够大的树导入内存，然 后再进行搜索。搜索的算法是递归的，与二分查找非常类似，每次计算可以将问题规模减半。当然，具 体有多少数据可以导入内存，受实际可以使用的内存数量的限制。
• 每个节点的数 据分成 Key 和 Value , Key 就是索引值.
• 二叉搜索树是一个天生的二分查找结构，每次查找都可以减少一半的问题规模。而且二叉搜索树解决了 插入新节点的问题，因为二叉搜索树是一个跳跃结构，不必在内存中连续排列。这样在插入的时候，新节点可以放在任何位置，不会像线性结构那样插入一个元素，所有元素都需要向后排列。
  
• 在使用磁盘的时候，二叉搜索树是不是一种合理的查询结构？
  当然还不算，因此还需要继续优化我们的算法。二叉搜索树，在内存中是一个高效的数据结构。这是因 为内存速度快，不仅可以随机存取，还可以高频操作。注意 CPU 缓存的穿透率只有 5% 左右，也就是 95% 的操作是在更快的 CPU 缓存中执行的。而且即便穿透，内存操作也是在纳秒级别可以完成。

B 树和 B+ 树

B树

• 二叉搜索树解决了连续结构插入新元素开销很大的问题，同时又保持着天然的二分结构。**但是，**当需要 索引的数据量很大，无法在一个磁盘 Block 中存下整棵二叉搜索树的时候。每一次递归向下的搜索，实际都是读取不同的磁盘块。这个时候二叉搜索树的开销很大。
• 一个更好的方案，就是继续沿用树状结构，利用好磁盘的分块让每个节点多一些数据，并且允许子节点 也多一些，树就会更矮。因为树的高度决定了搜索的次数。
• B 树（B-Tree）
  
• 上图中的 B 树是一个 3-4 B 树，3 指的是每个非叶子节点允许最大 3 个索引，4 指的是每个节点最多允 许 4 个子节点，4 也指每个叶子节点可以存 4 个索引。
• B-Tree 是一种递归的搜索结构，与二叉搜索树非常类似。不同的是，B 树中的父节点中的数据会对子树 进行区段分割。

继承 B 树：B+ 树

• **B+ 树只有叶子节点才映射数据，**下图中是对 B 树设计的一种改进，节点 1 为冗余节点，它不存储数据，只划定子树数据的范围。你可以看到节点 1 的索引 Key：12 和 30，在节点 3 和 4 中也有一份。
  

树的形成：插入

• 在 2-3 B+ 树中依次插入 3,6,9,12,19,15,26,8,30
• 插入 3,6,9 过程很简单，都写入一个节点即可，因为叶子节点最多允许每个 3 个索引。接下来我们插入 12，会发生一次过载，然后节点就需要拆分，这个时候按照 B+ 树的设计会产生冗余节点。
  
  
  
  
  
  
  
  再次解决过载，拆分红色部分，得到最后结果：

• B+ 树始终可以保持平衡状态，而且所有叶子节点都在同一层级。

插入和删除效率

• B+ 树有大量的冗余节点，比如删除一个节点的时候，可以直接从叶子节点中删除，甚至可以不动非叶子节点。这样删除非常快。B 树则不同，B 树没有冗余节点，删除节点的时候非常复杂。比如删除根节点 中的数据，可能涉及复杂的树的变形。
• B+ 树的插入也是一样，有冗余节点，插入可能存在节点的拆分（如果节点饱和），但是最多只涉及树的 一条路径。而且 B+ 树会自动平衡。
  因此，B+ 树的插入和删除效率更高。

搜索：链表的作用

• B 树和 B+ 树搜索原理基本一致。先从根节点查找，然后对比目标数据的范围，最后递归的进入子节点 查找。
  你可能会注意到，B+ 树所有叶子节点间还有一个链表进行连接。这种设计对范围查找非常有帮助，比如 说我们想知道 1 月 20 日和 1 月 22 日之间的订单，这个时候可以先查找到 1 月 20 日所在的叶子节点， 然后利用链表向右遍历，直到找到 1 月22 日的节点。这样我们就进一步节省搜索需要的时间。

总结

• 如果是存储海量数据的数据库，我们的思考点需要放在 I/O 的效率上。如果把今天的知识放到分布式数据库上，那除了需要节省磁盘读写还需要节省网络 I/O。

MySQL 中的 B 树和 B+ 树有什 么区别？

【解析】 B+ 树继承于 B 树，都限定了节点中数据数目和子节点的数目。B 树所有节点都可以映射数据， B+ 树只有叶子节点可以映射数据。
单独看这部分设计，看不出 B+ 树的优势。为了只有叶子节点可以映射数据，B+ 树创造了很多冗余的索 引（所有非叶子节点都是冗余索引），这些冗余索引让 B+ 树在插入、删除的效率都更高，而且可以自 动平衡，因此 B+ 树的所有叶子节点总是在一个层级上。所以 B+ 树可以用一条链表串联所有的叶子节点，也就是索引数据，这让 B+ 树的范围查找和聚合运算更快。

分布式文件系统和数据库

分布式文件系统通过计算机网络连接大量物理节点，将不同机器、不同磁 盘、不同逻辑分区的数据组织在一起，提供海量的数据存储（一般是 Petabytes 级别，1PB = 1024TB）。分布式数据库则在分布式文件系统基础上，提供应对具体场景的海量数据解决方案。

存储所有的网页

• 作为搜索引擎最核心的一个能力，就是要存储所有的网页。
• 搜索引擎不单单要存下这些页面，而且搜索引擎还需要存储这些网页的历史版本。

模型的选择

• 应该用何种模型存下这个巨大的网页表？
• 网页的历史版本，可以用 URL+ 时间戳进行描述。但是为了检索方便，网页不仅有内容，还有语言、外 链等。在存储端可以先不考虑提供复杂的索引，比如说提供全文搜索。但是我们至少应该提供合理的数 据读写方式等等等
• 先看看行存储，可不可以满足需求。比如每个网页（ URL） 的数据是一行。 看似这个方案可行， 可惜列不是固定。比如外链可能有很多个，如下表：

列不固定，不仅仅是行的大小不好确定，而是表格画不出来。何况每一列内容还可能有很多版本，不同 版本是搜索引擎的爬虫在不同时间收录的内容，再加上内容本身也很大，有可能一个磁盘 Block都存不下

• 因为列是不确定的，这种情况下只能考虑用 Key-Value 结构，也就是 Map 存储。Map 是一种抽象的数 据结构，本质是 Key-Value 数据的集合。 作为搜索引擎的支撑，Key 可以考虑设计为 <URL, Column， 时间戳> 的三元组，值就是对应版本的数据。
• 列名（Column）可以考虑分成两段，用:分隔开。列名包括列家族（Family) 、列标识（Qualifier）。 这样设计是因为有时候多个列描述的是相似的数据，比如说外链（Anchor），就是一个列家族。然后百度、搜狐是外链家族的具体的标识（Qualifier）。比如来自百度页面 a 外链的列名是 anchor:baidu.com/a。分成家族还有一个好处就是权限控制，比如不同部门的内部人员可以访问不同 列家族的数据。当然有的列家族可能只有一个列，比如网页语言；有的列家族可能有很多列，比如外 链。

这个巨大的 Map（Key-Value）的集合应该用什么数据结构呢？

• 设计想法一 ： 通过 B+ 树，这样即便真的有海量的数据，也可以在少数几次、几十次查询内完成找到 URL 对应的数据。况且，我们还可以设计缓存, B+ 树需要一种顺序，比较好的做法是 URL 以按照字典序排列。这是因为，相同域名的网页资源同时被 用到的概率更高，应该安排从物理上更近，尽量把相同域名的数据放到相邻的存储块中（节省磁盘操作）， 可以考虑分列存储。那么行内用什么数据结构呢？如果列非常多，也 可以考虑继续用 B+ 树。还有一种设计思路，是先把大表按照行拆分，比如若干行形成一个小片称作 Tablet，然后 Tablet 内部再使用列存储

查询和写入

当客户端查询的时候，请求参数中会包含 <URL, 列名>，这个时候我们可以通过 B+ 树定位到具体的行 （也就是URL对应的数据）所在的块，再根据列名找到具体的列。然后，将一列数据导入到内存中，最后在内存中找到对应版本的数据。客户端写入时，也是按照行→列的顺序，先找到列，再在这一列最后面追加数据。 对于修改、删除操作可以考虑不支持，因为所有的变更已经记录下来了。

分片（Tablet）的抽象

假设存储网页的表有几十个 PB，那么先水平分表，就是通过行（URL） 分表。URL 按照字典排序，相邻的 URL 数据从物理上也会相近。水平分表的结果，字典序相近的行（URL）数据会形成分片（Tablet）， Tablet 这个单词类似药片的含义。

分片（Tablet），可以作为数据分布的最小单位。分片内部可以考虑图上的行存储，也可以考虑内部是一个 B+ 树组织的列存储。为了实现分布式存储，每个分片可以对应一个分布式文件系统中的文件。假设这个分布式文件系统接入 了 Linux 的虚拟文件系统，使用和操作会同 Linux 本地文件并无二致。其实不一定会这样实现，这只是 一个可行的方案。
为了存储安全，一个分片最少应该有 2 个副本，也就是 3 份数据。

块（Chunk）的抽象

• 比分片更小的单位是块（Chunk），这个单词和磁盘的块（Block）区分开。Chunk 是一个比 Block 更 大的单位。eg.Google File System 把数据分成了一个个 Chunk，然后每个 Chunk 会对应具体的磁盘块 （Block）
• 如下图，Table 是最顶层的结构，它里面含有许多分片（Tablets）。从数据库层面来看，每个分片是一 个文件。数据库引擎维护到这个层面即可，至于这个文件如何在分布式系统中工作，就交给底层的文件 系统——比如 Google File System 或者 Hadoop Distributed File System。
  
• 分布式文件系统通常会在磁盘的 Block 上再抽象一层 Chunk。一个 Chunk 通常比 Block 大很多，比如 Google File System 是 64KB，而通常磁盘的 Block 大小是 4K；HDFS 则是 128MB。这样的设计是为了 减少I/O操作的频率，分块太小 I/O 频率就会上升，分块大 I/O 频率就减小。 比如一个 Google 的爬虫 积攒了足够多的数据再提交到 GFS 中，就比爬虫频繁提交节省网络资源。

分布式文件的管理（待补充）

和单机文件系统一样，一个文件必须知道自己的数据 （Chunk）存放在哪里。下图展示了一种最简单的设计，文件中包含了许多 Chunk 的 ID，然后每个 ChunkID 可以从 Chunk 的元数据中找到 Chunk 对应的位置

• 如果 Chunk 比较大，比如说 HDFS 中 Chunk 有 128MB，那么 1PB 的数据需要 8,388,608 个条目。如 果每个条目用 64bit 描述，也就是 8 个字节，只需要 64M 就可以描述清楚。考虑到一个 Chunk 必然会 有冗余存储，也就是多个位置，实际会比 64M 多几倍，但也不会非常大了。
• 因此像 HDFS 和 GFS 等，为了简化设计会把所有文件目录结构信息，加上 Chunk 的信息，保存在一个 单点上，通常称为 Master 节点。
  
  下图中，客户端想要读取/foo/bar中某个 Chunk 中某段内容（Byterange）的数据，会分成 4 个步 骤：

客户端向 Master 发送请求，将想访问的文B件名、Chunk 的序号（可以通过 Chunk 大小和内容位 置计算）；
2. Master 响应请求，返回 Chunk 的地址和 Chunk 的句柄（ID）； 3.
客户端向 Chunk 所在的地址（一台 ChunkServer）发送请求，并将句柄（ID）和内容范围 （Byterange）作为参数；
3. ChunkServer 将数据返回给客户端。在上面这个模型中，有 3 个实体。

1.客户端（Client）或者应用（Application），它们是数据的实际使用方，比如说 BigTable 数据库 是 GFS 的 Client。
2. Master 节点，它存储了所有的文件信息、Chunk 信息，权限信息等。
3. ChunkServer 节点，它存储了实际的 Chunk 数据。
Master 只有一台，ChunkServer 可以有很多台。上图中的 namespace 其实就是文件全名（含路径） 的集合。Chunk 的 namespace 存储的是含文件全名 + ChunkLocation + ChunkID 的组合。文件的命名 空间、Chunk 的命名空间，再加上文件和 Chunk 的对应关系，因为需要频繁使用，可以把它们全部都 放到 Master 节点的内存中，并且利用 B 树等在内存中创建索引结构。ChunkServer 会和 Master 保持 频繁的联系，将自己的变更告知 Master。这样就构成了一个完整的过程。

读和写 （待补充）

读取文件的过程需要两次往返（Round Trip），第一次是客户端和 Master 节点，第二次是客户端和某 个 ChunkServer。
写入某个 Chunk 的时候，因为所有存储了这个 Chunk 的服务器都需要更新，所以需要将数据推送给所 有的 ChunkServer。这里 GFS 设计中使用了一个非常巧妙的方案，先由客户端将数据推送给所有 ChunkServer 并缓存，而不马上更新。直到所有 ChunkServer 都收到数据后，再集中更新。这样的做 法减少了数据不一致的时间。
下图是具体的更新步骤： 1.
客户端要和服务器签订租约，得到一个租期（Lease）。其实就是 Chunk 和 Chunk 所有复制品的 修改权限。如果一个客户端拿到租期，在租期内，其他客户端能不能修改这个 Chunk。
2.
Master 告诉客户端该 Chunk 所有的节点位置。包括 1 台主节点（Primary）和普通节点 （Secondary）。当然主节点和普通节点，都是 ChunkServer。主 ChunkServer 的作用是协助更 新所有从 ChunkServer 的数据。3.
这一步是设计得最巧妙的地方。客户端接下来将要写入的数据同时推送给所有关联的 ChunkServer。这些 ChunkServer 不会更新数据，而是把数据先缓存起来。
4.
图中的所有 ChunkServer 都收到了数据，并且给客户端回复后，客户端向主 ChunkServer 请求写 入。
5. 主 ChunkServer 通知其他节点写入数据。因为数据已经推送过来了，所以这一步很快完成。 6. 写入完数据的节点，所有节点给主 ChunkServer 回复。 7. 主 ChunkServer 通知客户端成功。

以上，就是 GFS 的写入过程。这里有个规律，实现强一致性（所有时刻、所有客户端读取到的数据是一 致的）就需要停下所有节点的工作牺牲可用性；或者牺牲分区容错性，减少节点。GFS 和 HDFS 的设 计，牺牲的是一致性本身，允许数据在一定时间范围内是不一致的，从而提高吞吐量。

容灾

在 HDFS 设计中，Master 节点也被称为 NameNode，用于存储命名空间数据。ChunkServer 也被称为 DataNode，用来存储文件数据。在 HDFS 的设计中，还有一个特殊的节点叫作辅助节点（Secondary Node）。辅助节点本身更像一个客户端，它不断和 NameNode 交流，并把 NameNode 最近的变更写 成日志，存放到 DataNode 中。类似日志文件系统，每过一段时间，在 HDFS 中这些日志会形成一个还 原点文件，这个机制和上一讲我们提到的日志文件系统类似。如果 Master节点发生了故障，就可以通过这些还原点进行还原。

总结

现在，我们已经可以把所有的场景都串联起来。Google 需要的是一个分布式数据库，存储的数据是包括内容、外链、Logo、标题等在内的网页的全部版本和描述信息。为了描述这些信息，一台机器磁盘不够 大，吞吐量也不够大。因此 Google 需要将数据分布存储，将这个大表（BigTable）拆分成很多小片 （Tablet）。当然，这并不是直接面向用户的架构。给几十亿用户提供高效查询，还需要分布式计算， 计算出给用户使用的内容索引。
Google 团队发现将数据分布出去是一个通用需求。不仅仅是 BigTable 数据库需要，很多其他数据库也 可以在这个基础上构造。按照软件设计的原则，每个工具应该尽可能的专注和简单， Google 的架构师 意识到需要一个底层的文件系统，就是 Google File System。这样，BigTable 使用 Tablet 的时候，只 需要当成文件在使用，具体的分布式读写，就交给了GFS。后来，Hadoop 根据 GFS 设计了 Hadoop 分布式文件系统，用于处理大数据，仍然延续了整个 GFS 的 设计。

分布式文件系统是怎么回事？

【解析】分布式文件系统通过网络将不同的机器、磁盘、逻辑分区等存储资源利用起来，提供跨平台、 跨机器的文件管理。通过这种方式，我们可以把很多相对廉价的服务器组合起来形成巨大的存储力量。

面试题

【问题】socket 文件都存在哪里？ （待补充 socket 内容）

【解析】socket 没有实体文件，只有 inode，所以 socket 是没有名字的文件。你可以在 /proc/net/tcp 目录下找到所有的 TCP 连接，在 /proc/[pid]/fd 下也可以找到这些 socket 文件，都是数字代号，数字就是 socket 文件的 fd，如下图所示：

【问题】思考日志文件系统的数据冗余如何处理？

【解析】 日志系统产生冗余几乎是必然发生的。 只要发生了修改、删除，肯定就会有数据冗余。日志系统通常不会主动压缩，但是日志文件系统通常会对磁盘碎片进行整理，这种机制和内存的管理非常相似。
首先我们把这个磁盘切割成很多等大的小块，大文件可能需要分配多个小块，多个小文件共用一个小块。而当很多文件被删除之后，磁盘中的小块会产生碎片，文件系统会进行碎片整理，比如把多个有很多碎片的区域拷贝到一起，使存储空间更加紧凑。
回到正题，最终的答案就是不压缩、不处理冗余，空间换时间，提升写入速度。

【问题】按照应该尽量减少磁盘读写操作的原则，是不是哈希表的索引更有优势？

【解析】哈希表是一种稀疏的离散结构，通常使用键查找值。给定一个键，哈希表会通过数学计算的方 式找到值的内存地址。因此，从这个角度去分析，哈希表的查询速度非常快。单独查找某一个数据速度 超过了 B+ 树（比如根据姓名查找用户）。因此，包括 MySQL 在内的很多数据库，在支持 B+ 树索引的 同时，也支持哈希表索引。
**这两种索引最大的区别是：B+ 树是对范围的划分，其中的数据还保持着连续性；而哈希表是一种离散的 查询结构，数据已经分散到不同的空间中去了。**所以当数据要进行范围查找时，比如查找某个区间内的 订单，或者进行聚合运算，这个时候哈希表的性能就非常低了。
哈希表有一个设计约束，如果我们用了 m 个桶（Bucket，比如链表）去存储哈希表中的数据，再假设 总共需要存储 N 个数据。那么平均查询次数 k = N/m。为了让 k 不会太大，当数据增长到一定规模时， 哈希表需要增加桶的数目，这个时候就需要重新计算所有节点的哈希值（重新分配所有节点属于哪个桶）。
综上，对于大部分的操作 B+ 树都有较好的性能，比如说>,<, =,BETWEEN，LIKE等，哈希表只能用于等 于的情况。

【问题】Master 节点如果宕机了，影响有多大，如何恢复？

【解析】在早期的设计中，Master 是一个单点（Single Point），如果发生故障，系统就会停止运转， 这就是所谓的单点故障（Single Point of Failure）。由此带来的后果会非常严重。发生故障后，虽然我 们可以设置第二节点不断备份还原点，通过还原点加快系统恢复的速度，但是在数据的恢复期间，整个 系统是不可用的。
在一个高可用的设计当中，我们不希望发生任何的单点故障（SPoF），因此所有的节点都至少有两份。 于是在 Hadoop 后来的设计当中，增加了一种主从结构。

如上图所示，我们同时维护两个 Master 节点（在 Hadoop 中称为 NameNode，NN）——一个活动 （Active）的 NN 节点，一个待命（StandBy）的 NN 节点。
为了保证在系统出现故障的时候，可以迅速切换节点，我们需要一个故障控制单元。因为是分布式的设 计，控制单元在每个 NN 中都必须有一个，这个单元可以考虑 NN 节点进程中的一个线程。控制单元不 断地检测节点的状态，并且不断探测其他 NN 节点的状态。一旦检测到故障，控制单元随时准备切换节 点。一方面，因为我们不能信任任何的 NN 节点不出现故障，所以不能将节点的状态存在任何一个 NN 节点 中。并且节点的状态也不适合存在数据节点中，因为大数据集群的数据节点实时性不够，它是用来存储 大文件的。因此，可以考虑将节点的状态放入一个第三方的存储当中，通常就是 ZooKeeper。 另一方面，因为活动 NN 节点和待命 NN 节点数据需要完全一致，所以数据节点也会把自己的状态同时 发送给活动节点和待命节点（比如命名空间变动等）。最后客户端会把请求发送给活动节点，因此活动 节点会产生操作日志。不可以把活动节点的操作日志直接发送给待命节点，是因为我们不确定待命节点是否可用。
而且，为了保证日志数据不丢失，它们应该存储至少 3 份。即使其中一份数据发生损坏，也可以通过对 比半数以上的节点（2 个）恢复数据。因此，这里需要设计专门的日志节点（Journal Node）存储日 志。至少需要 3 个日志节点，而且必须是奇数。活动节点将自己的日志发送给日志节点，待命节点则从 日志节点中读取日志，同步自己的状态

• **数据节点同步给主节点的日志。**这类数据由数据节点同时同步给活动、待命节点。
• 活动节点同步给待命节点的操作记录。这类数据由活动节点同步给日志节点，再由日志节点同步给 待命节点。日志又至少有 3 态机器的集群保管，每个上放一个日志节点。
• 记录节点本身状态的数据（比如节点有没有心跳）。这类数据存储在分布式应用协作引擎上，比如 ZooKeeper。
  有了这样的设计，当活动节点发生故障的时候，只需要迅速切换节点即可修复故障

总结

• 理解虚拟文件系统的设计，理解在一个目录树结构当中，可以拥有不同的文件系统——一切皆文件的设计。基于这种结构，设备、磁盘、分布式文件系、网络请求都可以是文件。
• 将空间分块管理是一种高效的常规手段。方便分配、方便回收、方便整理——除了文件系统，内存 管理和分布式文件系统也会用到这种手段。
• 日志文件系统的设计是重中之重，日志文件系统通过空间换时间，牺牲少量的读取性能，提升整体 的写入效率。除了单机文件系统，这种设计在分布式文件系统和很多数据库当中也都存在。
• 分层架构：将数据库系统、分布式文件系搭建在单机文件管理之上——知识是死的、思路是活的。 希望你能将这部分知识运用到日常开发中，提升自己系统的性能