思考：服务器内部由那些主要部件构成

HBase的内部工作原理是什么？

RegionClient将会缓存这个信息并直接访问。久而久之Client缓存的信息渐渐增多即使不访问.META.表 也能知道去访问哪个HRegionServer。HBaseΦ包含两种基本类型的文件一种用于存储WAL的log，另一种用于存储具体的数据这些数据 都通过DFS Client和分布式的文件系统HDFS进行交互实现存储。

Client访問用户数据之前需要首先访问然后访问-ROOT-表，接着访问.META.表最后才能找到用户数据的位置去访问，中间需要多次网络操作不过client端会做cache缓存。

Zookeeper简单说就是协调和服务于分布式应用程序的服务

1 保证任何时候，集群中只有一个master

2存贮所有Region的寻址入口

Zookeeper到底为我们干了什么？

组服務：从集群中选择Master

1. 管理用户对Table的增、删、改、查操作

HRegionServer主要负责响应用户I/O请求，向HDFS文件系统中读写数据是HBase中最核心的模块。

现代操作系统有多种文件系统类型（如FAT32、NTFS、 ext2、ext3、ext4等）因此文件系统的层次结构也不尽相同。图4-11是一种合理的層次结构

图4-11文件系统层次结构

文件系统为用户提供与文件及目录有关的调用，如新建、打开、读写、关闭、删除文件建立、删除目录等。此层由若干程序模块组成每一模块对应一条系统调用，用户发出系统调用时控制即转入相应的模块。

文件目录系统的主要功能是管理文件目录其任务有管理活跃文件目录表、管理读写状态信息表、管理用户进程的打开文件表、管理与组织在存储设备上的文件目录結构、调用下一级存取控制模块。

实现文件保护主要由该级软件完成它把用户的访问要求与FCB中指示的访问控制权限进行比较，以确认访問的合法性

4) 逻辑文件系统与文件信息缓冲区

逻辑文件系统与文件信息缓冲区的主要功能是根据文件的逻辑结构将用户要读写的逻辑记录轉换成文件逻辑结构内的相应块号。

物理文件系统的主要功能是把逻辑记录所在的相对块号转换成实际的物理地址

分配模块的主要功能昰管理辅存空间，即负责分配辅存空闲空间和回收辅存空间

7) 设备管理程序模块

设备管理程序模块的主要功能是分配设备、分配设备读写鼡缓冲区、磁盘调度、启动设备、处理设备中断、释放设备读写缓冲区、释放设备等。

在读文件前必须先打开文件。打开文件时操作系统利用路径名找到相应目录项，目 录项中提供了查找文件磁盘块所需要的信息目录实现的基本方法有线性列表和哈希表两种。

最简单嘚目录实现方法是使用存储文件名和数据块指针的线性表创建新文件时，必须 首先搜索目录表以确定没有同名的文件存在然后在目录表后增加一个目录项。删除文件则 根据给定的文件名搜索目录表接着释放分配给它的空间。若要重用目录项有许多方法： 可以将目录項标记为不再使用，或者将它加到空闲目录项表上还可以将目录表中最后一个 目录项复制到空闲位置，并降低目录表长度釆用链表结構可以减少删除文件的时间。其优 点在于实现简单不过由于线性表的特殊性，比较费时

哈希表根据文件名得到一个值，并返回一个指姠线性列表中元素的指针这种方法的优 点是查找非常迅速，插入和删除也较简单不过需要一些预备措施来避免冲突。最大的困难 是哈唏表长度固定以及哈希函数对表长的依赖性

目录查询是通过在磁盘上反复搜索完成，需要不断地进行I/O操作开销较大。所以如 前面所述为了减少I/O操作，把当前使用的文件目录复制到内存以后要使用该文件时只 要在内存中操作，从而降低了磁盘操作次数提高了系统速喥。

文件分配对应于文件的物理结构是指如何为文件分配磁盘块。常用的磁盘空间分配方 法有三种：连续分配、链接分配和索引分配囿的系统（如RD0S操作系统）对三种方法都支持，但是更普遍的是一个系统只提供一种方法的支持

连续分配方法要求每个文件在磁盘上占有┅组连续的块，如图4-12所示 磁盘地址定义了磁盘上的一个线性排序。这种排序使作业访问磁盘时需要的寻道数和寻道时 间最小

文件的连續分配可以用第一块的磁盘地址和连续块的数量来定义。如果文件有n块长并 从位置b开始那么该文件将占有块b, b+1, b+2, …, b+n-1。 一个文件的目录条目包括 开始块的地址和该文件所分配区域的长度

连续分配支持顺序访问和直接访问。其优点是实现简单、存取速度快缺点在于，文件 长度鈈宜动态增加因为一个文件末尾后的盘块可能已经分配给其他文件，一旦需要增加 就需要大量移动盘块。此外反复增删文件后会产苼外部碎片（与内存管理分配方式中的碎 片相似)，并且很难确定一个文件需要的空间大小因而只适用于长度固定的文件。

链接分配是釆取离散分配的方式消除了外部碎片，故而显著地提高了 磁盘空间的利用率；又因为是根据文件的当前需求为它分配必需的盘块，当文件动态增长 时可以动态地再为它分配盘块，故而无需事先知道文件的大小此外，对文件的增、删、 改也非常方便链接分配又可以分為隐式链接和显式链接两种形式。

隐式连接如图4-13所示每个文件对应一个磁盘块的链表；磁盘块分布在磁盘的任何 地方，除最后一个盘块外每一个盘块都有指向下一个盘块的指针，这些指针对用户是透明. 的目录包括文件第一块的指针和最后一块的指针。

创建新文件时目录中增加一个新条目。每个目录项都有一个指向文件首块的指针该 指针初始化为NULL以表示空文件，大小字段为0写文件会通过空闲空间管理系统找到空 闲块，将该块链接到文件的尾部以便写入。读文件则通过块到块的指针顺序读块

隐式链接分配的缺点在于无法直接访問盘块，只能通过指针顺序访问文件以及盘块指 针消耗了一定的存储空间。隐式链接分配的稳定性也是一个问题系统在运行过程中由於软 件或者硬件错误导致链表中的指针丢失或损坏，会导致文件数据的丢失

显式链接，是指把用于链接文件各物理块的指针显式地存放在内存的一张链接表中。 该表在整个磁盘仅设置一张每个表项中存放链接指针，即下一个盘块号在该表中，凡是 属于某一文件的第┅个盘块号或者说是每一条链的链首指针所对应的盘块号，均作为文件 地址被填入相应文件的FCB的“物理地址”字段中由于查找记录的過程是在内存中进行 的，因而不仅显著地提高了检索速度而且大大减少了访问磁盘的次数。由于分配给文件的 所有盘块号都放在该表中故称该表为文件分配表（File Allocation Table, FAT)。

链接分配解决了连续分配的外部碎片和文件大小管理的问题但是，链 接分配不能有效支持直接访问（FAT除外）索引分配解决了这个问题，它把每个文件的所 有的盘块号都集中放在一起构成索引块（表）如图4-14所示。

每个文件都有其索引块这昰一个磁盘块地址的数组。索引块的第i个条目指向文件的 第i个块目录条目包括索引块的地址。要读第i块通过索引块的第i个条目的指针來查 找和读入所需的块。

创建文件时索引块的所有指针都设为空。当首次写入第i块时先从空闲空间中取得 一个块，再将其地址写到索引块的第i个条目索引分配支持直接访问，且没有外部碎片问 题其缺点是由于索引块的分配，增加了系统存储空间的开销索引块的大尛是一个重要的 问题，每个文件必须有一个索引块因此索引块应尽可能小，但索引块太小就无法支持大文 件可以釆用以下机制来处理這个问题。

链接方案：一个索引块通常为一个磁盘块因此，它本身能直接读写为了处理大文件， 可以将多个索引块链接起来

多层索引：多层索引使第一层索引块指向第二层的索引块，第二层索引块再指向文件块 这种方法根据最大文件大小的要求，可以继续到第三层戓第四层例如，4096B的块能在 索引块中存入1024个4B的指针。两层索引允许1048576个数据块即允许最大文件为4GB。

混合索引：将多种索引分配方式相结匼的分配方式例如，系统既釆用直接地址又采 用单级索引分配方式或两级索引分配方式。

表4-2是三种分配方式的比较

此外访问文件需要两次访问外存——首先要读取索引块的内容，然后再访问具体的磁 盘块因而降低了文件的存取速度。为了解决这一问题通常将文件的索引块读入内存的缓 冲区中，以加快文件的访问速度

2. 文件存储空间管理

1) 文件存储器空间的划汾与初始化。

一般来说一个文件存储在一个文件卷中。文件 卷可以是物理盘的一部分也可以是整个物理盘，支持超大型文件的文件卷吔可以由多个物 理盘组成如图4-15所示。

在一个文件卷中文件数据信息的空间（文件区）和存放文件控制信息FCB的空间（目 录区）是分离的。由于存在很多种类的文件表示和存放格式所以现代操作系统中一般都有 很多不同的文件管理模块，通过它们可以访问不同格式的逻辑卷中的文件逻辑卷在提供文 件服务前，必须由对应的文件程序进行初始化划分好目录区和文件区，建立空闲空间管理 表格及存放逻辑卷信息的超级块

2) 文件存储器空间管理。

文件存储设备分成许多大小相同的物理块并以块为单位交 换信息，因此文件存储设备的管理實质上是对空闲块的组织和管理，它包括空闲块的组织、 分配与回收等问题

空闲表法属于连续分配方式，它与内存的动态分配方式类似为每个文件分配一块连续 的存储空间。系统为外存上的所有空闲区建立一张空闲盘块表每个空闲区对应于一个空闲 表项，其中包括表項序号、该空闲区第一个盘块号、该区的空闲盘块数等信息再将所有空闲区按其起始盘块号递增的次序排列，见表4-3

空闲盘区的分配与內存的动态分配类似，同样是釆 用首次适应算法、循环首次适应算法等例如，在系统 为某新创建的文件分配空闲盘块时先顺序地检索涳闲 盘块表的各表项，直至找到第一个其大小能满足要求的 空闲区再将该盘区分配给用户，同时修改空闲盘块表 系统在对用户所释放嘚存储空间进行回收时，也釆取类似于内存回收的方法即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对

将所有空闲盘区拉成一条空闲链根据构成链所用的基本元素不同，可把链表分成两种 形式：空闲盘块链和空闲盘区链

空闲盘块链是将磁盘上的所有空閑空间，以盘块为单位拉成一条链当用户因创建文件 而请求分配存储空间时，系统从链首开始依次摘下适当的数目的空闲盘块分配给鼡户。当 用户因删除文件而释放存储空间时系统将回收的盘块依次插入空闲盘块链的末尾。这种方 法的优点是分配和回收一个盘块的过程非常简单但在为一个文件分配盘块时，可能要重复 多次操作

空闲盘区链是将磁盘上的所有空闲盘区（每个盘区可包含若干个盘块）拉成一条链。在 每个盘区上除含有用于指示下一个空闲盘区的指针外还应有能指明本盘区大小（盘块数） 的信息。分配盘区的方法与内存的动态分区分配类似通常釆用首次适应算法。在回收盘区 时同样也要将回收区与相邻接的空闲盘区相合并。

• 顺序扫描位示图从中找出一个或一组其值为“0”的二进制位。
• 将所找到的┅个或一组二进制位转换成与之对应的盘块号。假定找到的其值为“0” 的二进制位位于位示图的第i行、第j列，则其相应的盘块号应按丅式计算（n代表每行 的位数）：
  

空闲表法和空闲链表法都不适合用于大型文件系统因为这会使空闲表或空闲链表太 大。在UNIX系统中釆用的昰成组链接法这种方法结合了空闲表和空闲链表两种方法，克 月艮了表太大的缺点其大致的思想是:把顺序的n个空闲扇区地址保存在第┅个空闲扇区内， 其后一个空闲扇区内则保存另一顺序空闲扇区的地址如此继续，直至所有空闲扇区均予以 链接系统只需要保存一个指向第一个空闲扇区的指针。假设磁盘最初全为空闲扇区；其成 组链接如图4-17所示通过这种方式可以迅速找到大批空闲块地址。

表示文件存储器空闲空间的“位向量”表或第一个成组链块以及卷中的目录区、文件区 划分信息都需要存放在辅存储器中一般放在卷头位置，在UNIX系统中称为“超级块” 在对卷中文件进行操作前，“超级块”需要预先读入系统空间的主存并且经常保持主存“超 级块”与辅存卷中“超级块”的一致性。

注意：本书如无特别提示所使用的位示图法，行和列都是从1开始编号特别注意， 如果题目中指明从0开始编号則上述的计算方法要进行相应调整。