The Hadoop Distributed File System 论文_hdfs论文

一. Abstract

可靠存储大数据集，高带宽传输，服务器的分布式存储和计算。本论文描述了HDFS体系结构及25年的Yahoo企业大数据存储经验

二. Introduction and related works

1. Hadoop提供了一个分布式文件系统和一个框架，用于使用MapReduce范式分析和转换非常大的数据集。一个重要特征是跨数以千计的主机进行数据和计算的分区，并在其主机附近并行执行应用程序计算。 Hadoop集群只需添加商品服务器即可扩展计算能力，存储能力和IO带宽。

2. Hadoop是Apache组织的项目。有以下几个组件：

3. NameNode：dedicated server stores metadata
    DataNode：other servers store Application data
    NameNode就像是一本书的目录，可以快速找到数据所在的DataNode，DataNode是负责存储数据的，他们之间用TCP协议通。

4. 与Lustre和PVFS不同，HDFS中的DataNode不使用RAID这样的数据保护机制来使数据持久。 相反，像GFS一样，文件内容被复制到多个DataNode上以提高可靠性。 在确保数据持久性的同时，此策略还具有以下优势：数据传输带宽成倍增加，并且有更多机会将计算定位在所需数据附近。

5. 几个分布式文件系统已经或正在探索名称空间的真正分布式实现。

Ceph 有一个namespace servers（MDS）集群，并使用动态子树分区算法，以便将namespace tree均匀地映射到MDS。    

GFS也正在发展distributed namespace。 新的GFS将具有数百个 namespace servers (masters），每个master有上亿个文件。

Luster 在其2.2版本中has an implementation of clustered namespace。 目的是在多个metadata servers（MDS）上分割目录，每个MDS包含名称空间的不相交部分。 使用文件名上的哈希函数将文件分配给特定的MDS。

三. Architecture

A. NameNode

HDFS keeps the entire namespace in RAM

inode:索引节点，Files and directories are represented on the NameNode by inodes, which record attributes like permissions, modification and access times, namespace and disk space quotas.

https://www.cnblogs.com/wxplmm/p/7239342.html

image: The inode data and the list of blocks belonging to each file comprise the metadata of the name system called the image索引节点数据和属于每个文件的块列表构成了名称系统的元数据，称为图像。

checkpoint: The persistent record of the image stored in the local host’s native files system is called a checkpoint.存储在本地主机的本机文件系统中的图像的持久记录称为检查点。

B. DataNode

该节点上存储两种文件：1. 数据本身  2. block’s metadata including checksums for the block data and the block’s generation stamp.一个是元数据（数据块的长度，块数据的校验和，以及时间戳）

启动时：

1. DN will connect NN and perform a handshake.检查namespaceID和software version。如果有一个不相同就自动关闭

2.namespaceID，NN的ID，是DN第一次访问NN就获得的，每个NN底下所有的DN的namespaceID相同
StorageID，每个DN的ID，是唯一的，哪怕下次DN的IP变了也不会变，唯一识别。

3.DN给NN发送block report. A block report contains the block id, the generation stamp and the length for each block replica the server hosts. 

4.第一个block report在DN刚初始化就发送，之后每一小时发一次，这样NN的image会有所有它属下DN的block情况视图

5.在正常运行期间，DN每过3秒（默认）会发送heartbeats给NN确保自己在运行，如果NN 10分钟没接收到心跳，则会认为该DN挂了，在其他DN上计划创建新副本

6.heartbeats中包含information about total storage capacity, fraction of storage in use, and the number of data transfers currently in progress. （总存储容量，正在使用的存储部分以及当前正在进行的数据传输数量的信息。）这些统计信息用于NN的空间分配和负载平衡决策

7.NN不直接调用DN,而是对heartbeats做答复指令，包括：
• replicate blocks to other nodes;（复制块）
• remove local block replicas;（删除本地块副本）
• re-register or to shut down the node;（重启或关闭）
• send an immediate block report.（让DN立即发送块报告）

C. Client

用户通过HDFS Client调用
HDFS provides an API that exposes the locations of a file blocks.HDFS提供了一个公开文件块位置的API。
the replication factor：（复制因子，默认为3）

D. Image and Journal

Image: The namespace image is the file system metadata that describes the organization of application data as directories and files.（描述应用程序数据作为目录和文件的组织。）

Journal：日志，即https://www.cnblogs.com/wxplmm/p/7239342.html中提到的edits

checkpoint：A persistent record of the image written to disk is called a checkpoint

为了防止checkpoint或journal丢失，需存储在多个storage directories存储目录中：Recommended practice is to place the directories on different volumes, and for one storage directory to be on a remote NFS server.（这些存储目录在不同卷中，有一个作远程NFS备份）。如果写入其中一个存储目录失败，则不再选择这个目录。如果没有可用的存储目录，NN自动关闭

NameNode还支持多线程，同时处理多个客户端的请求

E. CheckpointNode

定期地创建命名空间的检查点。首先从NameNode下载image和journal，然后在本地合并它们，然后将合并后的新的image上传回NameNode，避免重新启动NameNode再合并image和journal的问题。CheckpointNode与NameNode通常运行在不同的机器上，内存与NameNode的内存一样大小。

F. BackupNode

可以将BackupNode视为只读的NameNode。
BackupNode不仅提供了与CheckpointNode相同的检查点功能，而且在内存中维护了文件系统命名空间的最新拷贝，该拷贝与NameNode中的状态总是同步的。除了从NameNode接收journal文件流外，BackupNode将这些journal文件在内存中创建副本，这样就创建了命名空间的备份。BackupNode不需要从NameNode下载image和journal文件以创建检查点（CheckpointNode和SecondaryNameNode需要从NameNode下载这些文件），因为BackupNode已经在内存中最新的命名空间状态。BackupNode的检查点更加高效，因为它只需要将命名空间保存到本地image文件中并重置journal文件。BackupNode的内存大小与NameNode的一样。NameNode一次只支持一个BackupNode，并且在启用BackupNode的同时不启用CheckpointNode。

G. Upgrades, File System Snapshots

快照用于回滚，相当于创建指针，而不是硬复制（存储容量不够）

四. FILE I/O OPERATIONS AND REPLICA MANGEMENT

A. File Read and Write

HDFS implements a single-writer, multiple-reader model.(单写入，多读取)
单写入的Client会有一个lease（租约），包括硬限制和软限制（soft limit and hard limit），如果软限制到期了还没结束，另一个Client可以抢占它。如果硬限制（一小时）到期，HDFS会假定用户已经完成，自动关闭。写入期间不妨碍其他Client读取文件。

An HDFS file consists of blocks.（HDFS由文件块组成） The DataNodes form a pipeline, the order of which minimizes the total network distance from the client to the last DataNode. （数据节点形成一条管道，其顺序使从客户端到最后一个数据节点的总网络距离最小。）

在将数据写入HDFS文件之后，HDFS不提供任何保证，直到关闭该文件后，新读取器才能看到该数据。如果用户应用程序需要可见性保证，则可以显式调用hflush操作。

checksums：HDFS generates and stores checksums for each data block of an HDFS file.https://blog.csdn.net/lb812913059/article/details/79718303

The design of HDFS I/O is particularly optimized for batch processing systems, like MapReduce, which require high throughput for sequential reads and writes.（HDFS I / O的设计特别针对批处理系统（例如MapReduce）进行了优化，该系统需要高吞吐量才能进行顺序读取和写入。）

B. Block Placement

Rack：机架    bandwidth：带宽     

在大多数情况下，同一机架中节点之间的网络带宽大于不同机架中节点之间的网络带宽。
HDFS通过两个节点之间的距离来估计它们之间的网络带宽。两个节点之间的距离可以通过将它们到最接近的共同祖先的距离相加得出。两个节点之间的距离越短，意味着它们可用于传输数据的带宽越大。
HDFS允许管理员配置脚本，该脚本在给定节点地址的情况下返回节点的机架标识。当DataNode向NameNode注册时，NameNode运行配置的脚本来确定该节点属于哪个机架。如果未配置此类脚本，则NameNode会假定所有节点都属于默认的单个机架。
replicas的放置对于HDFS数据可靠性和read/write performance至关重要。好的replicas放置策略应提高数据可靠性，可用性和网络带宽利用率。目前，HDFS提供了一个configurable block placement policy interface，以便用户和研究人员可以试验和测试最适合其应用程序的任何策略。
The default HDFS block placement policy provides a tradeoff between minimizing the write cost, and maximizing data reliability, availability and aggregate read bandwidth.（默认的HDFS块放置策略可在最小化写入成本与最大化数据可靠性，可用性和聚合读取带宽之间进行权衡。）创建新块时，HDFS将第一个副本放置在写入程序所在的节点上，将第二个和第三个副本放置在不同机架中的两个不同节点上，其余放置在随机节点上，且限制不超过当副本数少于机架数的两倍时，在一个节点上放置一个副本，在同一机架中放置不超过两个副本。将第二个和第三个副本放置在不同机架上的选择可以更好地在整个群集中分配单个文件的块副本。如果将前两个副本放置在同一机架上，则对于任何文件，其三分之二的块副本将位于同一机架上。
选择所有目标节点之后，按照它们与第一个replicas的接近程度的顺序将它们组织为pipeline管道。为了阅读，NameNode首先检查客户端的主机是否位于群集中。如果是，则将块位置按与读者的亲近顺序返回给客户端。按此优先级顺序从DataNodes中读取该块。该策略减少了机架间和节点间的写流量，并通常提高了写性能。

默认的HDFS副本放置策略可以总结如下：
1.No Datanode contains more than one replica of any block. 没有一个Datanode包含一个块的多个副本。
2.No rack contains more than two replicas of the same block, provided there are sufficient racks on the cluster. 如果集群上有足够的机架，则每个机架都不能包含两个以上同一块副本。

C. Replication management

NameNode努力确保每个块始终具有预期数量的副本。当来自DataNode的块报告到达时，NameNode检测到一个块已被复制不足或过度。当块被过度复制时，NameNode选择要删除的副本。 NameNode宁愿不减少承载副本的机架的数量，其次更喜欢从DataNode中删除可用磁盘空间最少的副本。目的是在不降低数据块可用性的情况下平衡各个DataNode的存储利用率。
块复制不足时，会将其放入复制优先级队列中。只有一个副本的块具有最高优先级，而副本数大于其复制因子三分之二的块具有最低优先级。后台线程定期扫描复制队列的头部，以确定将新副本放置在何处。块复制遵循与新块放置类似的策略。如果现有副本数为1，则HDFS会将下一个副本放置在其他机架上。如果该块具有两个现有副本，则如果两个现有副本位于同一机架上，则将第三个副本放置在另一个机架上；否则，第三个副本将与现有副本放置在同一机架中的不同节点上。此处的目标是降低创建新副本的成本。
NameNode还确保并非块的所有副本都位于一个机架上。如果NameNode检测到一个块的副本终止于一个机架，则NameNode将该块视为复制不足，并使用上述相同的块放置策略将其复制到其他机架。 NameNode收到创建副本的通知后，该块将被过度复制。然后，NameNode将决定删除旧副本，因为过度复制策略不希望不减少机架数量。

D. Balancer

HDFS块放置策略未考虑DataNode磁盘空间利用率。这是为了避免将新数据（更有可能被引用）放置在DataNode的一小部分中。因此，数据可能并不总是在DataNode上均匀地放置。将新节点添加到群集时，也会发生不平衡。
平衡器是一种用于平衡HDFS群集上磁盘空间使用情况的工具。它以阈值作为输入参数，该阈值是（0，1）范围内的分数。如果对于每个DataNode，节点的利用率与整个集群的利用率相差不超过阈值，则该集群是平衡的。
该工具被部署为可以由集群管理员运行的应用程序。它将副本从利用率较高的DataNode重复移动到利用率较低的DataNode。平衡器的一项关键要求是保持数据可用性。在选择要移动的副本并确定其目的地时，平衡器保证该决定不会减少副本的数量或机架的数量。
平衡器通过最小化机架间数据复制来优化平衡过程。如果平衡器确定需要将副本A移动到其他机架，并且目标机架恰好具有相同块的副本B，则将从副本B而不是副本A复制数据。
第二个配置参数限制了重新平衡操作消耗的带宽。允许的带宽越高，群集可以更快地达到平衡状态，但是与应用程序的竞争也就更大。

E. Block Scanner

每个DataNode运行一个块扫描器，该扫描器定期扫描其块副本并验证存储的校验和是否与块数据匹配。在每个扫描周期中，块扫描器都会调整读取带宽，以便在可配置的周期内完成验证。如果客户端读取一个完整的块并且校验和验证成功，它将通知DataNode。 DataNode将其视为副本的验证。
每个块的验证时间存储在人类可读的日志文件中。任何时候，顶级DataNode目录中最多有两个文件，即当前日志和上一个日志。新的验证时间将附加到当前文件中。相应地，每个DataNode都有一个内存中的扫描列表，该列表按副本的验证时间排序。
每当读取客户端或块扫描器检测到损坏的块时，它都会通知NameNode。 NameNode将副本标记为已损坏，但不会立即计划删除副本。相反，它开始复制该块的良好副本。仅当良好的副本数达到块的复制因子时，才计划删除损坏的副本。此政策旨在尽可能长时间地保留数据。因此，即使块的所有副本都已损坏，该策略也允许用户从损坏的副本中检索其数据。

F. Decommissioing退役

群集管理员通过列出允许注册的节点的主机地址和不允许注册的节点的主机地址，指定哪些节点可以加入群集。 管理员可以命令系统重新评估这些包含和排除列表。 已被排除在集群中的当前成员被标记为退役。 一旦将DataNode标记为停用，它将不会被选择作为副本放置的目标，但是它将继续为读取请求提供服务。 NameNode开始计划将其块复制到其他DataNode。 一旦NameNode检测到复制了退役DataNode上的所有块，该节点便进入退役状态。 然后可以安全地将其从群集中删除，而不会损害任何数据可用性。

G. Inter-Cluster Data Copy

当使用大型数据集时，将数据复制到HDFS群集中以及从中复制数据是艰巨的。 HDFS提供了一个称为DistCp的工具，用于大型集群间/集群内并行复制。 这是MapReduce的工作； 每个映射任务都会将部分源数据复制到目标文件系统中。 MapReduce框架自动处理并行任务调度，错误检测和恢复。

五. PRACTICE AT YAHOO!

Yahoo!上的大型HDFS群集 包括大约3500个节点。

70％的磁盘空间分配给HDFS。其余部分保留用于操作系统（Red Hat Linux），日志和用于溢出映射任务输出的空间。 （MapReduce中间数据未存储在HDFS中。）单个机架中的40个节点共享一个IP交换机。机架式交换机分别连接到八个核心交换机。核心交换机提供机架之间的连接以及集群外资源。对于每个群集，特别为NameNode和BackupNode主机配备了高达64GB的RAM。应用程序任务永远不会分配给那些主机。总计，一个3500个节点的群集具有9.8 PB的可用存储块，可以将其复制3次，从而为用户应用程序提供3.3 PB的净存储。为了方便起见，一千个节点代表应用程序存储的一个PB。在使用HDFS（以及将来）的多年中，被选为群集节点的主机受益于改进的技术。新的群集节点始终具有更快的处理器，更大的磁盘和更大的RAM。较慢，较小的节点将退役或降级为保留用于Hadoop开发和测试的群集。如何配置群集节点的选择在很大程度上是经济购买计算和存储的问题。 HDFS不会强制计算与存储的特定比率，也不会限制连接到群集节点的存储量。

在一个示例大型集群（3500个节点）上，大约有6000万个文件。这些文件有6300万块。由于每个块通常被复制3次，因此每个数据节点承载着54 000个块副本。用户应用程序每天将在群集上创建200万个新文件。 Yahoo!的Hadoop集群中的25000个节点提供25 PB的在线数据存储。在2010年初，这只是Yahoo!数据处理基础结构的适度但正在增长的一部分。雅虎！ 2004年开始研究使用分布式文件系统的MapReduce编程。Apache Hadoop项目成立于2006年。到年底，Yahoo！已采用Hadoop供内部使用，并有一个300节点的集群用于开发。从那时起，HDFS已成为Yahoo!后台的组成部分。 HDFS的旗舰应用程序是Web Map的生产，Web Map是万维网的索引，它是搜索的关键组成部分（耗时75小时，500 TB的MapReduce中间数据，总输出300 TB）。更多的应用程序正在迁移到Hadoop，尤其是那些分析和建模用户行为的应用程序。成为Yahoo!技术套件的关键组件意味着解决一些技术问题，这些问题既是研究项目，又是许多PB公司数据的保管人。最重要的是数据的健壮性和持久性问题。同样重要的是经济性能，用户社区成员之间资源共享的规定以及系统操作员的易于管理。

A. Durability of Data

三次复制数据是防止由于不相关的节点故障而导致的数据丢失的有力保障。雅虎不太可能！曾经以这种方式失去了一块；对于大型集群，一年内丢失一个块的概率小于.005。关键的理解是每月约有0.8％的节点发生故障。 （即使最终恢复了该节点，也没有采取任何措施来恢复它可能已经托管的数据。）因此，对于如上所述的示例大型集群，每天损失一两个节点。同一集群将在大约两分钟内重新创建故障节点上托管的54 000个块副本。 （复制是快速的，因为这是一个并行问题，会随着群集的大小而扩展。）在两分钟内几个节点发生故障，从而丢失了某个块的所有副本的概率确实很小。
节点的相关故障是另一种威胁。在这方面最常见的故障是机架或核心交换机的故障。 HDFS可以容忍丢失机架开关（每个块在其他机架上都有一个副本）。核心交换机的某些故障可以有效地将群集的一部分与多个机架断开连接，在这种情况下，某些块可能会变得不可用。在这两种情况下，修复交换机都会将不可用的副本还原到群集。另一种相关的故障是群集的电力意外或故意损失。如果功率损耗跨越机架，则有可能某些块将变得不可用。但是恢复电源可能不是一种补救方法，因为一半到百分之一的节点将无法在完全上电重启后继续运行。从统计上讲，实际上，大型群集在重新启动电源时会丢失一些块。
 （未经测试的策略是在几周内一次故意重新启动一个节点，以识别无法在重新启动后存活的节点）。
除了节点的全部故障之外，存储的数据可能会损坏或丢失。块扫描器每两周扫描一个大型群集中的所有块，并在此过程中找到约20个坏副本。

B. Caring for the Commons

随着对HDFS的使用的增长，文件系统本身不得不引入一种手段，以在庞大而多样的用户社区中共享资源。第一个这样的功能是一个权限框架permissions framework，该框架紧密地基于文件和目录的Unix权限方案。在此框架中，文件和目录对所有者，与文件或目录关联的用户组的其他成员以及对所有其他用户具有单独的访问权限。 Unix（POSIX）与HDFS之间的原理差异在于，HDFS中的普通文件既没有“执行”权限也没有“粘性”位。
在当前的权限框架中，用户身份很薄弱：您就是您的主人说的那样。当访问HDFS时，应用程序客户端只需查询本地操作系统以获取用户身份和组成员身份。正在开发更强大的身份模型。在新框架中，应用程序客户端必须向名称系统提供从受信任来源获得的凭据。可能有不同的凭证管理；最初的实现将使用Kerberos。用户应用程序可以使用相同的框架来确认名称系统也具有可信赖的身份。并且名称系统还可以要求参与集群的每个数据节点提供凭据。
可用于数据存储的总空间由数据节点的数量和为每个节点配置的存储设置。 HDFS的早期经验表明，需要一些手段来跨用户社区实施资源分配策略。不仅必须加强共享的公平性，而且当用户应用程序可能涉及成千上万个写入数据的主机时，防止应用程序无意中耗尽资源也很重要。对于HDFS，由于系统元数据始终位于RAM中，因此名称空间的大小（文件和目录的数量）也是有限的资源。为了管理存储和名称空间资源，可以为每个目录分配一个配额，该配额用于从该目录开始的名称空间子树中文件所占的总空间。也可以为子树中文件和目录的总数设置单独的配额。
尽管HDFS的体系结构假定大多数应用程序会将大数据集作为输入流，但是MapReduce编程框架可能会生成许多小输出文件（每个reduce任务一个），从而进一步加重了命名空间资源。为了方便起见，可以将目录子树折叠为单个Hadoop存档文件。 HAR文件类似于熟悉的tar，JAR或Zip文件，但是文件系统操作可以寻址归档文件的各个文件，并且HAR文件可以透明地用作MapReduce作业的输入。

C. Benchmarks