一种基于LRFU缓存替换策略的HDFS客户端本地缓存设计与实现

谢 磊 吴建华 廖卓凡 罗 可

(长沙理工大学计算机与通信工程学院 湖南 长沙 410004)

0 引 言

Hadoop[1-2]是一种对分析大数据的MapReduce模型的实现框架，凭借其开源、高效、高扩展性、低成本、高可靠的特性在互联网领域得到了广泛的利用。受Google文件系统启发而形成的Hadoop分布式文件系统HDFS[3]是Hadoop 底层基础框架的存储部分，由一个管理文件系统命名空间的命名节点(NameNode)和若干个数据节点(DataNode)组成。在这种主从结构分布式文件系统中，命名节点作为主节点负责管理整个文件系统的目录树，并在集群中提供集中式服务，而数据节点作为从节点负责数据的存储，配合名字节点工作。

HDFS从启动到正常运行期间，命名节点需要处理客户端、数据节点、第二命名节点的大量请求，创建并维护文件系统目录树。现阶段的HDFS只有单一的命名节点，而随着HDFS数据量不断增长，HDFS中数据节点不断增多，命名节点的性能将是整个HDFS的瓶颈。因此，需要降低NameNode的负载。

1 相关工作

解决HDFS命名节点性能问题的主要方法分为两种，一种是增加命名节点的数量，另一种是在数据节点建立缓存，减少数据节点与命名节点交互次数和访问磁盘次数。

饶磊等[7]利用一个superNameNode节点和多个NameNode节点组成一个小型的分布式NameNode系统作为HDFS的主节点，superNamenode节点负责管理所有 NameNode节点，监控所有Namenode状态并作出处理。李宽[8]利用多个NameNode并在这多个Namenode中选取一个Leader节点和一个SecondaryLeader节点组成一个NameNode集群作为整个HDFS的主节点。其中Leader节点根据选举制、终生制、世袭制原则从NameNode中选举出来。集群中的所有NameNode节点都是对等的，它们一起为HDFS提供服务。Leader节点负责监控NameNode集群的工作状态、处理集群中的节点故障。HDFS的HDFS Federation[9]使用多个相互独立的NameNode节点使得命名服务水平拓展。在HDFS Federation中的NameNode之间是联盟关系，它们之间相互独立且不需要相互协调。赵婧等[10]等提出了一种在HDFS数据节点上增加本地缓存的解决方案，实现了HDFS数据节点的本地缓存。

增加命名节点的数量需要通过某种选举机制选举一个主命名节点，并建立命名节点群，这将使整个HDFS系统复杂化，并影响系统的稳定性。而在数据节点建立缓存不能从根本上降低NameNode负载。

本文针对该现象提出一种利用LRFU[4-5]缓存替换算法在 HDFS 客户端建立本地缓存[6]的解决方案。当用户请求文件时，如果HDFS客户端已缓存该文件的元数据，则不必请求NameNode，直接从缓存中读取。由于客户端实现了NameNode部分功能，所以从功能上讲，每个HDFS客户端也是一个NameNode。

2 HDFS客户端本地缓存解决方案架构

HDFS客户端本地缓存解决方案主要由缓存模块、离线日志分析模块、定时器三部分组成。如图1所示。

图1 HDFS客户端缓存架构

缓存模块是本方案的主要模块，离线日志分析模块和定时器服务于缓存模块。缓存模块负责缓存的建立、缓存更新、缓存命中等。离线日志分析使用Hadoop中的MapReduce通过分析历史文件，更新缓存模块中部分参数，达到优化缓存模块的目的。定时器记录缓存文件缓存时间，当缓存时间达到临界值时，将其从缓存数据结构中删除，以保证缓存文件的有效性。

3 文件读取与缓存

3.1 HDFS文件读取部分源码分析

文件在数据节点中是以块(Block)的形式存储的，一方面简化了HDFS存储子系统，使HDFS可以存储比存储节点单一磁盘大的文件。另一方面，使HDFS方便容错，有利于数据复制[11]。命名节点中维护着HDFS中两层重要的关系：每个文件对应的数据块及这些数据块对用的数据节点。命名节点启动后，读取命名空间镜像(FSImage)并加载编辑日志(FSEdit)到内存获得HDFS某时刻的第一层关系。启动数据节点时，数据节点需要和命名节点握手、注册、上报管理的数据块信息以建立HDFS中的第二层关系。启动之后，数据节点不断地向命名节点发送心跳(Heartbeat)，维护这层关系，向命名节点上报块信息并获取指令。

HDFS向用户应用提供如Java API、类Shell命令等多种接口，这样用户就可以像操作本地文件系统一样操作HDFS。当用户需要读取HDFS文件时，会在HDFS客户端(DFSClient)调用open()方法打开要读取的文件，该方法返回一个DFSInputStream对象，然后就可以通过这个对象的read()方法读取HDFS文件。DFSInputStream类的构造方法最终会调用NameNode的远程方法getBlockLocations()向命名节点请求文件的数据块信息，命名节点返回文件从指定位置起配置项{dfs.read.prefecth.size}个数据块信息，客户端将此信息保存在变量locatedBlocks中。在DFSInputStream类中，用pos成员变量保存“下一个”要数据字节在文件中的位置以支持HDFS文件随机读。当用DFSInputStream对象的read()方法读取文件的时候，首先会调用blockSeekTo()方法查找pos所指文件位置所在的数据块，如果pos所指的数据块的信息在变量locatedBlocks中，则在本地读取。反之，则需要再次调用NameNode远程方法getBlockLocations()向命名节点请求数据块信息，并将此数据块信息插入到locatedBlocks变量中。当客户端获取到数据块信息后，读取此信息，请求数据节点，读取数据块。每次从数据节点读取输入缓冲区大小数据，并更新pos的值，根据pos的值判断是否需要请求其他数据节点和调用远程NameNode方法getBlockLocations()获得其他数据块信息。输入缓冲区大小的值由配置项由{io.file.buffer.size}决定。这样，当HDFS文件读取完毕后，pos指向文件的末尾，locatedBlocks变量中保存了文件所有数据块的信息。

本文利用此特点，在HDFS读取文件后，如果locatedBlocks变量中保存了文件完整的数据块信息，则将此信息缓存在HDFS客户端。当客户端下次需要访问此文件时，不必从命名节点那里请求数据块信息，而直接从本地读取。不仅降低了命名节点的负载，而且提高了文件的访问效率。

3.2 HDFS客户端建立本地缓存后文件读取步骤

HDFS客户端建立缓存后，文件读取步骤如下：

步骤1HDFS客户端通过java API 、C、类Shell等接口接收到用户读取文件请求。并查看所请求的文件是否已缓存，若已缓存，则向命名节点取得文件的访问权。得到文件访问权后，向命名节点查询文件块信息有无变更。若无变更，则直接将缓存的文件对应的数据节点信息赋值给locatedBlocks变量，进行步骤3。若文件块信息变更或文件没有缓存进行步骤2。

步骤2HDFS客户端向命名节点获取文件的访问权并调用getBlockLocations()获得部分文件对应的数据节点信息，更新locatedBlocks变量。

步骤3读取变量pos当前的值，若pos的值不位于变量locatedBlocks中所有的数据块中时，转向步骤2。否则，从变量locatedBlocks中选择合适的数据节点，建立连接，并转向步骤4。

步骤4从连接的数据节点不断读取配置项{io.file.buffer.size}个字节数据到内存，并更新pos变量。当变量pos的值超出该节点所存储的数据块时，若其值不小于文件的长度时，转向步骤5，否则转向步骤3。

步骤5根据LRUF缓存替换策略，更新缓存模块。如图2所示。

图2 文件读取流程

3.3 LRUF缓存替换策略

LFU(Least Frequently Used)[12]和LRU(Least Recently Used)[13-14]是两种最常用的缓存替换策略[15]。LFU是基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路，而LRU的核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。在这两种看起来毫无关联的策略之间却存在着LFU和LRU分别是极端值的缓存替换策略，这就是LRFU(Least Recently/Frequently Used)缓存替换策略。LRFU通过用一个控制参数 灵活地权衡LFU和LRU在替换策略中的比重。 的变化范围是0到1。一方面，如果 越接近0，LRFU 缓存替换策略就越靠近LFU缓存替换策略。最终当 等于0时，LRFU 缓存替换策略就是简单的LFU缓存替换策略。另一方面，如果 越接近1，LRFU 缓存替换策略就越靠近LRU缓存替换策略。最终当 等于1时，LRFU 缓存替换策略就退化到LRU缓存替换策略。文献[6] 证明了该缓存替换策略的可行性。

在HDFS中，用户可以根据分析HDFS历史文件访问日志、HDFS特殊应用场景等来确定 的取值。

3.4 HDFS客户端本地缓存模块设计

在客户端缓存模块中用LocatedBlocksWithCRF类代表HDFS文件。该类的UML类图如图3所示。

图3 LocatedBlocksWithCRF UML类图

该类主要有三个私有属性：该文件绝对路径src,此属性唯一区分一个HDFS文件、该文件的数据块信息blks和一个缓存模块分配给每个文件的值CRF(Combined Recency and Frequency), 缓存模块用这个值来度量该文件将来被访问的可能性。另外，属性last记录此文件上次被访问时经历过了多少个单位时间(一个单位时间对应一次访问)。

由文献[6]，文件的CRF值可由式(1)算得:

CRFlast(b)=f(0)+f(tc-LAST(b))×CRFlast(b)

(1)

式中：

(2)

LAST(b),CRFlast(b)分别表示上次访问文件b时的单位时间次数和文件b的CRF值。tc表示当前单位时间次数。结合式 (1) 和式 (2) 可知，f(0)即为当前被访问，且在此次访问之前从未被访问过的文件的CRF值。

图4 文件缓存替换流程

在每次文件读取完毕更新缓存系统时，都新建一个LocatedBlocksWithCRF对象，用来缓存被访问过文件的数据块信息。该对象的src属性赋值为被访问文件在HDFS中的绝对路径，CRF属性为f(0)，blks为文件被访问完后DFSInputStream对象的locatedBlocks属性，last为当前单位时间次数。用LocatedBlocksWithCRF类的src属性的比较器查看该文件的数据块信息是否已被缓存。若该文件的数据块信息未被缓存(既不在链表中，也不再堆中)，则进行如下步骤：

步骤1替换掉链表尾部的一个元素。

步骤2堆顶元素降级到链表的首部。

步骤3新块插入到堆顶部。

步骤4调整堆，使其满足小根堆性质。

若该文件的数据块信息位于缓存堆中，则根据式(1)用缓存LocatedBlocksWithCRF对象的CRF、last和当前时间算出新的CRF值，并用其更新新建的LocatedBlocksWithCRF对象。然后用新建的LocatedBlocksWithCRF对象替换缓存的LocatedBlocksWithCRF对象，并调整以其作为根的子树的堆，使其满足小根堆性质。若该文件的数据块信息位于缓存单链表中，则进行如下步骤：

堆顶元素降级到单链表首部。删除单链表中的该文件的LocatedBlocksWithCRF对象。根据式(1)用缓存LocatedBlocksWithCRF对象的CRF、last和当前时间算出新的CRF值，并用其更新新建的LocatedBlocksWithCRF对象。将新建LocatedBlocksWithCRF对象插入到堆顶。调整堆，使其满足小根堆性质。

4 日志分析模块

HDFS客户端缓存模块性能取决于由参数所决定的LFU和LRU在替换策略中的比重是否符合实际文件访问情况。HDFS运用的场景不同，HDFS客户端缓存模块最佳性能对应的值不同。在HDFS运行前，通过参数{io.file.cache.Lambda}来设定的值，不设定则使用系统默认值。在HDFS运行时，通过分析Web日志文件来确定合适的值。

在HDFS客户端缓存模块中用Pf(A)表示在LFU缓存替换策略中用户访问文件A后再次访问文件A的概率。计算如公式所示:

(3)

式中：N表示访问日志中所有文件出现的次数，Na表示访问文件A前t时间单位内文件A被访问的次数，在HDFS客户端缓存模块中t为单链表的长度与堆大小之和。LFU缓存替换策略用Pf(A)值表示文件A在将来被访问概率，Pf(A)值越大表示文件A在将来越有可能再次被访问，文件A越不可能被替换出缓存。

用Pr(A)表示在LRU缓存替换策略中用户访问文件A后再次访问文件A的概率。计算如公式所示：

(4)

式中：T表示访问日志总单位时间，在数值上等于所有文件出现的次数，Ta表示此次访问文件A距上次访问文件A的单位时间次数，t为单链表的长度与堆大小之和，当t-Ta小于0，则t-Ta取0。LRU缓存替换策略用Pr(A)值表示文件A在将来被访问概率，Pr(A)值越大表示文件A在将来越有可能再次被访问，文件A越不可能被替换出缓存。

在HDFS客户端缓存模块更新缓存并根据LRFU缓存替换算法替换出缓存中文件时，比较被替换出文件的Pf值和Pr值大小，若其Pf值较大说明LRU缓存替换策略更适合此场景，LFU缓存替换策略在此场景下的比重应当比LRU缓存替换策略小些。在Pf值大于Pr值1 000此时，将λ值加0.001。反之，在Pf值小于Pr值1 000此时，将λ值减0.001。这样通过将分析日志得出的结构反馈到值上，提高HDFS客户端缓存模块的命中率，使HDFS客户端缓存模块具有实时性。

5 实验与分析

5.1 实验环境

本实验环境基于4个节点的Hadoop集群，其中NameNode配置为4 GB内存，AMD Athlon(tm) X4 740 Quad 3.20 GHz， 1 TB硬盘。3个dataNode是2 GB内存，Intel Core i5-6200U CPU 2.30 GHz，2 TB硬盘。

每个节点的操作系统都是Centos 7，Hadoop版本2.7.3，Java版本1.8.0，HDFS副本数为3，HDFS块大小是32 MB。

实验中实现了客户端本地缓存的HDFS的值均取系统默认值，缓存大小均取400个LocatedBlocksWithCRF对象。

5.2 NameNode负载测试

本实验使用的指标：客户端调用远程方法getBlockLocations()请求NameNode的次数。在本实验中，NameNode负载只考虑由访问文件而请求NameNode的请求量，由于HDFS客户端和实现了客户端本地缓存的HDFS均需维护原数据，连接数据节点等工作，所以这部分负载不作考虑。

在访问日志中随机选取一个时间点作为访问的起始点，使用HDFS以及实现了客户端本地缓存的HDFS分别根据访问日志分别访问2 000、4 000、6 000、8 000和10 000个文件，并记录客户端调用远程方法getBlockLocations()的次数，结果如图5所示。

图5 HDFS与实现了客户端本地缓存HDFS请求NameNode次数对比

从图5中可以看到，HDFS随着访问文件的次数增加，调用远程方法getBlockLocations()的次数呈线性增加。而实现了客户端本地缓存的HDFS随着访问文件次数的增加，调用远程方法getBlockLocations()的次数开始也会增加，而之后的变化趋势较为平缓。实验结果说明了本地缓存的客户端能明显减少对NameNode的请求量，从而降低了NameNode的负载。

5.3 缓存命中率测试

为模仿不同的场景，首先使用LRFU缓存替换策略，在访问日志中选取8个相距较远的访问时间作为访问点，并分别从这些访问点开始根据访问日志访问2 000个文件，同时记录从缓存中读取文件块信息的文件数，算出访问命中率。然后使用LRU和LFU缓存替换策略以相同的方法，分别再次实验。实验结果如图6所示。

图6 LRFU与LRU、LFU缓存替换策略命中率对比

从图6中可以看出，LRU和LFU缓存替换策略从不同的访问点访问文件的命中率折线具有波动，命中率不如LRFU缓存替换策略高。而LRFU缓存替换策略命中率折现较为平缓。说明LRFU缓存替换策略对不同的场景具有自适应性。

5.4 文件访问时间测试

在访问日志中随机选取一个时间点作为访问的起始点，使用HDFS以及实现了客户端本地缓存的HDFS分别根据访问日志分别访问2 000、4 000、6 000、8 000和10 000个文件，记录每次实验的访问时间。实验结果如图7所示。

图7 HDFS与实现了客户端本地缓存HDFS文件访问时间对比

从图7可以看出，客户端本地缓存的HDFS速度比HDFS快，证明了实现了客户端本地缓存的HDFS能提高访问效率。

6 结 语

本文基于Master/Slave主从构架设计的HDFS中单个NameNode造成的性能瓶颈问题，提出了一种由每个HDFS客户端在某些功能上充当NameNode，分担NameNode部分任务的思想。并基于该思想设计实现了在HDFS客户端中根据LRFU缓存替换策略建立文件元数据缓存，得到如下结论：

1) 该方案减少HDFS客户端对NameNode请求量，一方面减少分布式系统中网络流量，另一方面减轻单个NameNode的负载，从而达到优化HDFS性能的目的。

2) 该方案对场景具有自适应性。在不同的场景中，HDFS客户端通过分析文件访问日志来权衡LFU和LRU在替换策略中的比重，使其更符合当时的场景，保持较高的缓存命中率。

参考文献

[1] White T. Hadoop:The Definitive Guide[M]． California:O’Reilly Media，inc．，2015:1-4.

[2] Melorose J，Perroy R，Careas S．Hadoop definitive guide[M]．Chicago:Yahoo！Press，2015:1-4.

[3] Honnutagi P S．The Hadoop distributed file system[J]．International Journal of Computer Science & Information Technology，2014，5 (5):6238-6243.

[4] Lee D，Choi J，Kim J H，et al．LRFU:A Spectrum of Policies that Subsumes the Least Recently Used and Least Frequently Used Policies[J]．Computers IEEE Transactions on，2013，50(12):1352-1361.

[5] Bai S，Bai X，Che X，Window‐LRFU:a cache replacement policy subsumes the LRU and window‐LFU policies[J]．Concurrency & Computation Practice & Experience，2016，28(9):2670-2684.

[6] Wang C Y，Huang T E，Huang Y T，et al．An Inter-framework Cache for Diverse Data-Intensive Computing Environments[C]//IEEE International Conference on Smart City/socialcom/sustaincom．IEEE，2016:944-949.

[7] 饶磊，杨凡德，刘东．基于分布式NameNode节点的HDFS优化研究[C]//全国信号和智能信息处理与应用学术会议，2014:450-453.

[8] 李宽．基于HDFS的分布式NameNode节点模型研究[D]．广州:华南理工大学，2011.

[9] Aishwarya K，Arvind R A，Sreevatson M C，et al．Efficient prefetching technique for storage of heterogeneous small files in Hadoop Distributed File System Federation[C]//Fifth International Conference on Advanced Computing．IEEE，2014:523-530.

[10] 赵婧，王洪波，程时端．HDFS 数据节点本地缓存的设计与实现[EB/OL].http://www.paper.edu.cn/releasepaper/content/201112-98.

[11] 蔡斌，陈湘萍．Hadoop:技术内幕深入解析Hadoop Common和HDFS架构设计与实现原理[M]．北京:机械工业出版社，2013:218-219.

[12] Einziger G,Friedman R.TinyLFU:A Highly Efficient Cache Admission Policy[C]//Euromicro International Conference on Parallel, Distributed and Network-Based Processing. IEEE, 2014:146-153.

[13] Dan A，Towsley D．An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes[J]．ACM Sigmetrics Performance Evaluation Review，1990，18(1):143-152.

[14] Hai J，Kai H. Efficient LRU Algorithm for Cache Scheduling in a Disk Array System[J]．International Journal of Computers & Applications，2015，22(3):134-139.

[15] Rexha G，Elmazi E，Tafa I．A Comparison of Three Page Replacement Algorithms:FIFO，LRU and Optimal[J]．Epl， 2015，28(7):465-469.