动机
本文的主要动机是让用户能同时访问或修改不相关的目录。比如同时修改或访问/a/b/f1和/a/c/f2的子目录 。
对于与文件相关的操作，比如getFileInfo，compete和rename，namenode在每个inode上持有一个锁。这些锁在调用InodesInPath解析路径时获取。我们定义这个锁叫IIPLock。
对于与块相关的操作，比如blockReport(BR)，blockReceivedAndDeleted(IBR)和RedundancyMonitor，namenode的线程安全由INodeFile对象锁保证。因为一个block一段时间内仅会被一个INodeFile拥有。我们定义这个锁叫INodeFileLock。
对于DN操作，比如registerDataNode和heartbeat，namenode的线程安全由DN lock保证。因为DN和IIPLock、INodeFileLock不相关，因此namenode不能用IIPLock和INodeFileLock执行这些操作。这样namenode引入了一个新的DN lock。
设计
锁类型
我们将namenode的所有操作抽象为四类：
- HA相关的操作
- 目录相关的操作
- Block相关的操作
- DN相关的操作
HA相关的操作
HDFS支持多个NameNode来保证高可用服务。在HA故障转移过程中，NameNode会对所有操作进行锁定，这样NameNode就可以安全地切换其状态。因此，对于所有HA相关操作，NameNode仍然可以使用全局文件系统锁来使其线程安全。这里不使用root iNode的写锁来锁定整个NameNode，因为它无法锁定与DN相关和与块相关的操作，这些操作将在后续部分中进行描述。另一个原因是所有操作都可以使用全局读锁来检查操作。
常用的HA相关操作包括:
- start/stopCommonServices
- start/stopActiveServices
- start/stopStandbyServices
- saveNamespace
提示:除了HA相关操作外，leaveSafeMode也需要此全局写锁，以便所有其他操作都可以持有全局读锁来检查NameNodeSafeMode。
目录相关的操作
HDFS为客户端提供了丰富的文件接口，这些接口在ClientProtocol.java中定义，比如:create，mkdir，complete，complete，setQuota等。所有这些操作都有一个或多个完整的输入路径或一个iNodeFileId，可以用于获取完整路径。这意味着NameNode可以使用IIPLock使这些操作线程安全。
从输入路径视角，我们可以将这些操作分为3类:
- 包含一个路径的操作
- 包含多个路径的操作
- 包含iNodeFile id的操作
包含一个路径的操作
对于这类只包含一个路径的操作，NameNode只需要获取IIPLock就可以安全地处理它们。不同的操作可能会修改路径中的不同iNode，所以NameNode应该用不同的方式获取IIPLock，我们称之为IIPLockMode。
大多数RPC请求属于这一类，例如:getFileInfo(获取文件信息)、getBlockLocation(获取块位置)、create(创建)、setErasureCodingPolicy(设置伪传错编码策略)、setXAttr(设置扩展属性)、setACL(设置访问控制列表)、getListing(获取目录列表)、mkdir(创建目录)等。
包含多个路径的操作
对于NameNode中包含多个路径的一些RPC操作，例如重命名(rename)、连接(concat)、建立软链接(createSymlink)等。为避免死锁，NameNode应按顺序获取这些路径的IIPLock，例如字典顺序。
包含iNodeFile id的操作
NameNode中还包含一些只有一个iNodeFile id输入的RPC操作，如:addBlock、abandonBlock、getAdditionalDatanode、updateBlockForPipeline、updatePipeline和complete等。所以，为了使IIPLock获取逻辑清晰，NameNode可以采取以下步骤获取IIPLock:
- 在持有全局FS读锁且不持有任何iNode锁的情况下，通过iNodeFileId获取该iNode文件的完整路径;
- 如果完整路径是相对路径，意味着iNodeFile被其他线程删除，直接抛出FileNotFoundException;
- 如果完整路径是绝对路径，根据操作需要的IIPLockMode获取该路径的IIPLock;
- 检查IIP中最后一个iNode的Id与输入iNodeId是否匹配;
- 如果匹配，则表示可以使用此IIPLock处理操作，直接返回IIPLock;
- 如果不匹配，表示iNode已被重命名到其他目录，重试获取iNodeFileId对应的IIPLock;
- 重试次数达到最大次数(如5-10次)后，把RetryException抛给客户端，要求重试。
以上过程可以明确IIPLock获取逻辑，保证只含iNodeFileId的操作的并发安全性。
Block相关的操作
NameNode通过BlockManager管理块的复制，例如处理副本块不足，或处理多余冗余块。Datanode通过BR和IBR报告块，NameNode检查不健康块并处理。NameNode成为Active后也会扫描所有块获取不健康块。NameNode使用RedundancyMonitor异步处理这些不足副本块。
对于这些操作，NameNode只需要持有iNodeFile锁就可以处理每个块，因为一个块在某个时间只属于一个iNodeFile，块与块也是互相独立的。
但是也有几个实现导致块与目录树和块之间存在依赖关系:
- HDFS-10843把quota更新逻辑从commitBlock移动到completeBlock，从而产生块与目录树的关系。
- HDFS-6584引入了块与目录树之间的关系。BR/IBR试图基于存储策略选择多余冗余副本，但存储策略可能设置在一个祖先iNode上。所以NameNode不仅需要持有iNodeFile锁，还需要持有IIP锁。
但不是每个块处理逻辑都涉及Quota更新和冗余复制，所以IIP锁不一定全都需要。与IIP锁相比，iNodeFile锁开销较小，所以为每个块持有IIP锁会导致性能下降。上述情况的解决方案后面会讨论。
DN相关的操作
NameNode管理所有数据节点，比如管理它们的状态和存储等。因为DN与目录树和块没有关系，NameNode无法使用IIPLock或INodeFileLock使这些与DN相关的操作并发安全。
使用全局写锁开销很大，而DN之间互相独立，所以NameNode可以为每个DN分配一个锁，利用这个锁使与DN相关的操作并发安全。
一些常用的与DN相关操作包括:注册数据节点(registerDatanode)、心跳(sendHeartbeat)、停服(decommission)、维护(maintenance)和缓存报告(cacheReport)等。所以NameNode可以在处理一个DN时使用DNLock来使这些操作并发安全。
锁顺序
如上所述，NameNode主要有四种锁，分别是:全局锁(globalLock)、DN锁(DNLock)、IIP锁(IIPLock)和iNode文件锁(INodeFileLock)。当然NameNode中还有些小范围锁，例如在LeaseManager中的锁。这里我们主要讨论这四种范围较大的锁。
为避免死锁，NameNode应按固定顺序获取这些锁。但顺序应该是什么呢?
首先获取的应该是全局锁。对于HA相关操作，获取全局写锁;对其他操作，获取全局读锁。
第二把锁应获取DN锁，因为BR/IBR/CacheReport都来源于一个DN，NameNode需要获取INodeFileLock处理每个块报告，所以DN锁应为第二把锁。
第三把锁是IIPLock或INodeFileLock。
最后获取NameNode中的小范围锁，例如LeaseManager中的锁。
所以锁顺序应为:全局锁 -> DN锁 -> IIP锁 -> INodeFileLock -> 小范围锁
通常IIP锁和INodeFile锁不会同时获取，但有一种特殊的递归删除RPC操作同时获取IIPLock和INodeFileLock，前者用于保护子目录树，后者用于保护最后一个iNodeFile中的块。
这样可能会出现下列锁的组合：
- Global Write Lock
- Global Read Lock -> DNLock
- Global Read Lock -> DNLock -> INodeFileLock
- Global Read Lock -> IIPLock
- Global Read Lock -> IIPLock -> INodeFileLock
- Global Read Lock -> DNLock -> IIPLock
LockPoolManager
内存是NameNode的一个非常重要的资源。FGL需要尽可能少地使用内存资源，同时也需要限制可以使用的最大资源量。
LockPoolManager用于管理所有iNode锁，比如分配锁和释放锁。如果分配的iNode锁不在池中缓存，LockPoolManager将创建一个新的锁实例绑定输入的iNode，并将锁实例缓存在池中。如果没有空间用于新的iNode锁，LockPoolManager将抛出IOException，NameNode将释放所有已获取的iNodeLock并返回RetryException给客户端以供重试。每个缓存的锁实例包含一个引用计数器，用于标识该实例是否被使用。如果一个锁实例没有被任何人使用，LockPoolManager将从池中移除它，，让JVM进行清理。
关于LockPool的容量，管理员可以根据模型进行计算，以确保分配不会失败。模型如:容量=【放大因子】*【处理器计数器】*【平均目录深度】。放大因子可以是1.5或2。平均目录深度可以从FSImage获取，处理器计数器可以从配置中获取。一个锁实例使用的内存可以计算出来，这样整个LockPool使用的内存也可以计算出来。
池中有一些“热”锁实例，比如根iNode的锁实例。对于这些“热”实例，LockManager可以进行缓存以提高获取和释放效率。
LookPoolManager只是一个抽象类，它有多个实现，如持久化所有锁实例、仅持久化“热”锁实例等。这样管理员可以选择合适的实现。
除了管理锁实例外，LockPoolManager还将与TrackLogManager结合使用，追踪和观测是否存在死锁。TraceLogManager类似于DataSetLockManager中的TrackLog。
IIPLock模式
HDFS为客户端提供了丰富的文件接口。这些接口的语义各不相同，不同操作可能会在输入路径不同层级的iNode上进行修改。例如：getBlockLocation RPC仅访问输入路径的最后一个iNode，delete RPC同时修改输入路径最后两个级别的iNode，setPermission只修改输入路径最后级别的iNode。所以，应当抽象IIPLock模式，使IIPLock获取逻辑简单明确。
可以用于获取输入路径IIPLock的抽象锁模式有5种:
- LOCK_READ
- 为路径中的所有iNode获取读锁
- getBlockLocation和getFileInfo可以使用此模式获取IIPLock
- LOCK_WRITE
- 仅为最后一个iNode获取写锁，其他iNode获取读锁
- setPermission、setOwner和setReplication可以使用此模式获取IIPLock
- LOCK_PARENT
- 为最后两个级别iNode获取写锁，其他iNode获取读锁
- rename和delete可以使用此模式获取IIPLock
- LOCK_ANCESTOR
- 为最后存在的iNode获取写锁，其他存在的iNode获取读锁
- mkdir和create可以使用此模式获取IIPLock
- NONE
- 不获取路径任何iNode锁
- 已持有全局写锁的操作可以使用此模式
通过抽象IIPLock模式，IIPLock获取逻辑变得简单明确，且与各操作语义匹配，更易于扩展和维护。
