一、Introduction
As we all know，网络是时时刻刻会出现故障的，HDFS集群庞大了之后出现节点故障也是常事。因此HDFS一个重要的设计需求就是保证持续地正确地写入操作。这时候lease recovery, block recovery, 和 pipeline recovery就开始发挥作用了。理解这些recovery过程什么时候被调用以及为什么被调用对我们理解hdfs原理有很大帮助，本文来学习租约恢复和块恢复的过程。
在摘录英文前给出自己的总结：
- lease recovery就是关闭文件并释放这个文件上客户端的租约，从而让其他客户端可以写这个文件。
- block recovery就是在lease recovery过程中，确保文件的最后一个数据块的所有副本有相同的长度。
- pipeline recovery就是在pipeline操作中，遇到pipeline中的datanodes失败时，底层的写操作不会失败，相反，HDFS会尝试从错误中recovery来让pipeline keep going，来让client继续写文件。
接下来，来点纯正的英文摘录：
Lease recovery, block recovery, and pipeline recovery come into play in this type of situation：
- Before a client can write an HDFS file, it must obtain a lease, which is essentially a lock. This ensures the single-writer semantics. The lease must be renewed within a predefined period of time if the client wishes to keep writing. If a lease is not explicitly renewed or the client holding it dies, then it will expire. When this happens, HDFS will close the file and release the lease on behalf of the client so that other clients can write to the file. This process is called lease recovery.
在HDFS中，客户端要想写文件，必须要获得该文件的租约（本质上类似于锁的概念）。如果client想继续写文件，那么必须要在提前定义好的时间周期里（soft limit and hard limit）进行renew 租约。如果没有显式地renew租约或者client 挂掉了，那么HDFS就会close the file并且释放掉代表这个client的租约，从而让其他的clients能够写文件。这个过程就叫做lease recovery。
If the last block of the file being written is not propagated to all DataNodes in the pipeline, then the amount of data written to different nodes may be different when lease recovery happens. Before lease recovery causes the file to be closed, it’s necessary to ensure that all replicas of the last block have the same length; this process is known as block recovery. Block recovery is only triggered during the lease recovery process, and lease recovery only triggers block recovery on the last block of a file if that block is not in COMPLETE state (defined in later section).
Block recovery只会在lease recovery过程中被触发；lease recovery只有在文件的最后一个block不是COMPLETE状态的时候对这个block进行block recovery。During write pipeline operations, some DataNodes in the pipeline may fail. When this happens, the underlying write operations can’t just fail. Instead, HDFS will try to recover from the error to allow the pipeline to keep going and the client to continue to write to the file. The mechanism to recover from the pipeline error is called pipeline recovery.
在写pipeline操作的过程中，一些Datenode可能会发生失败。当发生这种情况时，写操作不能只是失败而已。HDFS会尝试从error中恢复使得pipeline能够keep going，同时让client继续写文件。这就是pipeline recovery。
二、Blocks, Replicas, and Their States
在详述这三个recovery过程之前，我们先来介绍一下block和replicas的概念，以及他们的状态。
为了区分在Namenode和Datanode不同上下文中的blocks。我们用blocks表示在namenode中，用replicas表示在datanode中。
Datanode中的replicas有以下这些状态：（由enum ReplicaState类定义）
FINALIZED: when a replica is in this state, writing to the replica is finished and the data in the replica is “frozen” (the length is finalized), unless the replica is re-opened for append. All finalized replicas of a block with the same generation stamp (referred to as the GS and defined below) should have the same data. The GS of a finalized replica may be incremented as a result of recovery.
RBW (Replica Being Written): this is the state of any replica that is being written, whether the file was created for write or re-opened for append. An RBW replica is always the last block of an open file. The data is still being written to the replica and it is not yet finalized. The data (not necessarily all of it) of an RBW replica is visible to reader clients. If any failures occur, an attempt will be made to preserve the data in an RBW replica.
RWR (Replica Waiting to be Recovered): If a DataNode dies and restarts, all its RBW replicas will be changed to the RWR state. An RWR replica will either become outdated and therefore discarded, or will participate in lease recovery.
RUR (Replica Under Recovery): A non-TEMPORARY replica will be changed to the RUR state when it is participating in lease recovery.
TEMPORARY: a temporary replica is created for the purpose of block replication (either by replication monitor or cluster balancer). It’s similar to an RBW replica, except that its data is invisible to all reader clients. If the block replication fails, a TEMPORARY replica will be deleted.
Namenode中的blocks有以下状态：（由 enum BlockUCState类定义）
- UNDER_CONSTRUCTION: this is the state when it is being written to. An UNDER_CONSTRUCTION block is the last block of an open file; its length and generation stamp are still mutable, and its data (not necessarily all of it) is visible to readers. An UNDER_CONSTRUCTION block in the NameNode keeps track of the write pipeline (the locations of valid RBW replicas), and the locations of its RWR replicas.
- UNDER_RECOVERY: If the last block of a file is in UNDER_CONSTRUCTION state when the corresponding client’s lease expires, then it will be changed to UNDER_RECOVERY state when block recovery starts.
- COMMITTED: COMMITTED means that a block’s data and generation stamp are no longer mutable (unless it is reopened for append), and there are fewer than the minimal-replication number of DataNodes that have reported FINALIZED replicas of same GS/length. In order to service read requests, a COMMITTED block must keep track of the locations of RBW replicas, the GS and the length of its FINALIZED replicas. An UNDER_CONSTRUCTION block is changed to COMMITTED when the NameNode is asked by the client to add a new block to the file, or to close the file. If the last or the second-to-last blocks are in COMMITTED state, the file cannot be closed and the client has to retry.
- COMPLETE: A COMMITTED block changes to COMPLETE when the NameNode has seen the minimum replication number of FINALIZED replicas of matching GS/length. A file can be closed only when all its blocks become COMPLETE. A block may be forced to the COMPLETE state even if it doesn’t have the minimal replication number of replicas, for example, when a client asks for a new block, and the previous block is not yet COMPLETE.
notices：DataNodes persist a replica’s state to disk, but the NameNode doesn’t persist the block state to disk. When the NameNode restarts, it changes the state of the last block of any previously open file to the UNDER_CONSTRUCTION state, and the state of all the other blocks to COMPLETE.
Simplified Replica State Transition:
Simplified Block State Transition:
三、Generation Stamp （GS）
A GS is a monotonically increasing 8-byte number for each block that is maintained persistently by the NameNode。GS的引入有以下目的：
- Detecting stale replica(s) of a block: that is, when the replica GS is older than the block GS, which might happen when, for example, an append operation is somehow skipped at the replica.
- Detecting outdated replica(s) on DataNodes which have been dead for long time and rejoin the cluster.
A new GS is needed when any of the following occur:（生成新的GS的场景）：
- A new file is created
- A client opens an existing file for append or truncate
- A client encounters an error while writing data to the DataNode(s) and requests a new GS
- The NameNode initiates lease recovery for a file
四、Lease Recovery and Block Recovery
lease相关的管理操作由Namenode端的lease manager统一管理。client可能会持有很多文件的租约，client会定期发送一个请求来renew所有这些文件的租约。
org.apache.hadoop.hdfs.protocol.proto.ClientNamenodeProtocolProtos.RenewLeaseResponseProto
每个Namenode管理一个Namespace，同时持有这个namespace下的leasemanager。联邦HDFS cluster的情况下，每一个namespace有自己的leasemanager。
leasemanager保存了soft limit(1 min)和hard limit（1 hour）。当client的lease超过了soft limit时长并且client没有进行renew操作或者close file时，其他的client可以强制的获取这个文件的lease，从而对这个文件进行写操作。如果超过了hard limit时长并且client还没renew lease，那么HDFS就认为这个client已经退出了，于是自动地为client关闭这个文件，从而recovery lease。
HDFS client通过org.apache.hadoop.hdfs.LeaseRenewer.LeaseRenewer类来renew leases。这个类维护了一个users list并且在每个namenode上为一个用户跑一个线程。这些线程会周期性的向namenode登记，并且当lease period过半时 renew all of the client's leases
4.1 lease recovery process（租约恢复过程）
lease recovery在namenode中被触发，要么是由monitor thread检测超过hard limit，要么是超出soft limit后，一个client尝试接管从其他client那里接管lease。lease recovery检查client打开的每个file，如果file的最后一个block不是Complete状态则进行block recovery，然后close file。
notice：Block recovery of a file is only triggered when recovering the lease of a file
下面给定一个文件f来阐述租约恢复算法，当一个client挂掉的时候，下面的算法对每一个由这个client打开的文件都适用：
- Get the DataNodes which contain the last block of f.
- Assign one of the DataNodes as the primary DataNode p.
- p obtains a new generation stamp from the NameNode.
- p gets the block info from each DataNode.
- p computes the minimum block length.
- p updates the DataNodes, which have a valid generation stamp, with the new generation stamp and the minimum block length.
- p acknowledges the NameNode the update results.
- NameNode updates the BlockInfo.
- NameNode remove f’s lease (other writer can now obtain the lease for writing to f).
- NameNode commit changes to edit log.
算法的步骤3--7是block recovery阶段。如果一个file需要进行block recovery，那么namenode会挑选出一个primary datanode（这个datanode持有文件最后一个块的副本）。这个primary datanode 负责协调与其他datanodes的块恢复工作。当块恢复结束后，向namenode汇报。接着namenode会change这个block的。state，移除租约，commit changes to edit log。
