内容


HDFS 副本放置策略的研究和优化

Comments

云计算

云计算(cloud computing)是基于互联网的相关服务的增加、使用和交付模式,通常涉及通过互联网来提供动态易扩展且经常是虚拟化的资源。云是网络、互联网的一种比喻说法。过去在图中往往用云来表示电信网,后来也用来表示互联网和底层基础设施的抽象。因此,云计算甚至可以让你体验每秒 10 万亿次的运算能力,拥有这么强大的计算能力可以模拟核爆炸、预测气候变化和市场发展趋势。用户通过电脑、笔记本、手机等方式接入数据中心,按自己的需求进行运算。

按照美国国家标准与技术研究院(NIST)定义:云计算是一种按使用量付费的模式,这种模式提供可用的、便捷的、按需的网络访问,进入可配置的计算资源共享池(资源包括网络、服务器、存储、应用软件、服务),这些资源能够被快速提供,只需投入很少的管理工作,或与服务供应商进行很少的交互。

云计算是分布式计算(Distributed Computing)、并行计算(Parallel Computing)、效用计算(Utility Computing)、网络存储(Network Storage Technologies)、虚拟化(Virtualization)、负载均衡(Load Balance)、热备份冗余(High Available)等传统计算机和网络技术发展融合的产物。

云计算可以认为包括以下几个层次的服务:基础设施即服务(IaaS),平台即服务(PaaS)和软件即服务(SaaS)。

IBM 在这一领域占有相当的优势,提供了一系列的云计算产品和服务。近期与苹果合作,将苹果设备与 IBM 的软件解决方案成功绑定,从软硬件领域为企业提供移动化的解决方案。

云存储

云存储是在云计算概念上延伸和发展出来的一个新的概念,是指通过集群应用、网格技术或分布式文件系统等功能,将网络中大量各种不同类型的存储设备通过应用软件集合起来协同工作,共同对外提供数据存储和业务访问功能的一个系统。当云计算系统运算和处理的核心是大量数据的存储和管理时,云计算系统中就需要配置大量的存储设备,那么云计算系统就转变成为一个云存储系统,所以云存储是一个以数据存储和管理为核心的云计算系统。简单来说,云存储就是将储存资源放到云上供人存取的一种新兴方案。使用者可以在任何时间、任何地方,通过任何可连网的装置连接到云上方便地存取数据。

云存储系统的结构模型由 4 层组成。

存储层

存储层是云存储最基础的部分。存储设备可以是 FC 光纤通道存储设备,可以是 NAS 和 iSCSI 等 IP 存储设备,也可以是 SCSI 或 SAS 等 DAS 存储设备。云存储中的存储设备往往数量庞大且分布在多种不同地域,彼此之间通过广域网、互联网或者 FC 光纤通道网络连接在一起。

存储设备之上是一个统一存储设备管理系统,可以实现存储设备的逻辑虚拟化管理、多链路冗余管理,以及硬件设备的状态监控和故障维护。

基础管理

基础管理层是云存储最核心的部分,也是云存储中最难以实现的部分。基础管理层通过集群、分布式文件系统和网格计算等技术,实现云存储中多个存储设备之间的协同工作,使多个的存储设备可以对外提供同一种服务,并提供更大更强更好的数据访问性能。

应用接口

应用接口层是云存储最灵活多变的部分。不同的云存储运营单位可以根据实际业务类型,开发不同的应用服务接口,提供不同的应用服务。比如视频监控应用平台、IPTV 和视频点播应用平台、网络硬盘引用平台,远程数据备份应用平台等。

访问层

任何一个授权用户都可以通过标准的公用应用接口来登录云存储系统,享受云存储服务。云存储运营单位不同,云存储提供的访问类型和访问手段也不同。

HDFS

Hadoop 分布式文件系统 (HDFS) 被设计成适合运行在通用硬件 (commodity hardware) 上的分布式文件系统。它和现有的分布式文件系统有很多共同点。但同时,它和其他的分布式文件系统的区别也是很明显的。HDFS 是一个高度容错性的系统,适合部署在廉价的机器上。HDFS 能提供高吞吐量的数据访问,非常适合大规模数据集上的应用。HDFS 放宽了一部分可移植操作系统接口 (POSIX) 约束,来实现流式读取文件系统数据的目的。HDFS 在最开始是作为 Apache Nutch 搜索引擎项目的基础架构而开发的。HDFS 是 Apache Hadoop Core 项目的一部分。

以下是本文对 HDFS 及其副本放置策略的具体介绍说明。

副本技术

副本技术即分布式数据复制技术,是分布式计算的一个重要组成部分。该技术允许数据在多个服务器端共享,一个本地服务器可以存取不同物理地点的远程服务器上的数据,也可以使所有的服务器均持有数据的拷贝。

通过副本技术可以有以下优点:

  1. 提高系统可靠性:系统不可避免的会产生故障和错误,拥有多个副本的文件系统不会导致无法访问的情况,从而提高了系统的可用性。另外,系统可以通过其他完好的副本对发生错误的副本进行修复,从而提高了系统的容错性。
  2. 负载均衡:副本可以对系统的负载量进行扩展。多个副本存放在不同的服务器上,可有效的分担工作量,从而将较大的工作量有效的分布在不同的站点上。
  3. 提高访问效率:将副本创建在访问频度较大的区域,即副本在访问节点的附近,相应减小了其通信开销,从而提高了整体的访问效率。

HDFS 架构

图 1. HDFS 架构图
图 1. HDFS 架构图
图 1. HDFS 架构图

HDFS 是一个主从结构,一个 HDFS 集群有一个名字节点,它是一个管理文件命名空间和调节客户端访问文件的主服务器,当然还有一些数据节点,通常是一个节点一个机器,它来管理对应节点的存储。HDFS 对外开放文件命名空间并允许用户数据以文件形式存储。

内部机制是将一个文件分割成一个或多个块,这些块被存储在一组数据节点中。名字节点用来操作文件命名空间的文件或目录操作,如打开、关闭、重命名等等。它同时确定块与数据节点的映射。数据节点来负责来自文件系统客户的读写请求。数据节点同时还要执行块的创建、删除、和来自名字节点的块复制指令。

集群中只有一个名字节点极大地简单化了系统的体系结构。名字节点是仲裁者和所有 HDFS 元数据的仓库,用户的实际数据不经过名字节点。

数据复制

HDFS 设计成能可靠地在集群中大量机器之间存储大量的文件,它以块序列的形式存储文件。文件中除了最后一个块,其他块都有相同的大小。属于文件的块为了故障容错而被复制。块的大小和复制数是以文件为单位进行配置的,应用可以在文件创建时或者之后修改复制因子。HDFS 中的文件是一次写的,并且任何时候都只有一个写操作。

名字节点负责处理与所有的块复制相关的决策。它周期性地接受集群中数据节点的心跳和块报告。一个心跳的到达表示这个数据节点是正常的。一个块报告包括该数据节点上所有块的列表。

副本放置策略

块副本存放位置的选择严重影响 HDFS 的可靠性和性能。HDFS 采用机架敏感(rack awareness)的副本存放策略来提高数据的可靠性、可用性和网络带宽的利用率。

图 2. 副本放置策略图
图 2. 副本放置策略图
图 2. 副本放置策略图

HDFS 运行在跨越大量机架的集群之上。两个不同机架上的节点是通过交换机实现通信的,在大多数情况下,相同机架上机器间的网络带宽优于在不同机架上的机器。

在开始的时候,每一个数据节点自检它所属的机架 id,然后在向名字节点注册的时候告知它的机架 id。HDFS 提供接口以便很容易地挂载检测机架标示的模块。一个简单但不是最优的方式就是将副本放置在不同的机架上,这就防止了机架故障时数据的丢失,并且在读数据的时候可以充分利用不同机架的带宽。这个方式均匀地将复制分散在集群中,这就简单地实现了组建故障时的负载均衡。然而这种方式增加了写的成本,因为写的时候需要跨越多个机架传输文件块。

一般情况下复制因子(文件的副本数)为 3,HDFS 的副本放置策略是:将第一个副本放在本地节点,将第二个副本放到本地机架上的另外一个节点,而将第三个副本放到不同机架上的节点。这种方式减少了机架间的写流量,从而提高了写的性能。机架故障的几率远小于节点故障。这种方式并不影响数据可靠性和可用性的限制,并且它确实减少了读操作的网络聚合带宽,因为文件块仅存在两个不同的机架,而不是三个。文件的副本不是均匀地分布在机架当中,1/3 副本在同一个节点上,1/3 副本在同一个机架上,另外 1/3 副本均匀地分布在其他机架上。这种方式提高了写的性能,并且不影响数据的可靠性和读性能

图 3. 副本放置策略源码分析图
图 3. 副本放置策略源码分析图
图 3. 副本放置策略源码分析图

HDFS 副本放置策略缺陷

HDFS 的默认副本放置策略是一个随机选择策略,副本放置的最终状态很难被控制。其具体表现如下:

  1. 其是利用将副本放置在不同的机架上来达到高可靠性和数据块的均匀分布存储的,但如果数据中心只有一个机架,那么该副本放置策略就退化为一个随机选择策略,数据块的均匀分布和可靠性就很难被保证。
  2. 其并没有考虑到节点负载的情况,即使有一个节点的负载远高于其他节点,按照默认的副本放置策略,这个节点还是有可能被持续的写入数据。
  3. 其主要是对前三个副本的放置位置做出了考虑,如果需要放置更多的副本,则后面的副本放置会采用随机选择的策略。

当然在 HDFS 系统中也有个叫均衡器(Balancer)的守护进程。它会将数据块从负载较高的节点移动到负载较低的节点上,从而达到数据块重新分配的目的,最终使得整个集群分布均衡。虽然均衡器能在一定程度上解决问题,但是它也是存在缺陷的:

  1. 它对于集群数据块均衡的调节具有滞后性。
  2. 均衡器的调节和数据块的移动都需要一定资源的消耗。

因此,解决问题的关键是应该放在最初副本的放置上而不是事后去补救。这也就需要对 HDFS 的副本放置策略做出适当的优化。

HDFS 副本放置策略优化

根据上述所说的缺陷,本文提出了基于用户信息和负载的副本放置策略 UILBPS(Placement Strategy based on User Information and Load Balance)。

基于 HDFS 的特性,在副本创建副本后的操作主要以读取为主,即将负载均衡副本可用性和访问速率作为副本放置策略的优化目标。其中,副本访问速率性能受到副本节点负载的影响,尤其是 I/O 负载会成为访问的瓶颈;副本所在节点的状态也会对副本访问产生一定的影响,并影响到之后的负载均衡上。另外,同一用户所创建的副本,其副本访问在地域上有一定的相似性。因此,UILBPS 将通过副本访问特征的提取和节点负载的计算,解决副本初始创建阶段的副本数量和副本放置位置的确定问题。

副本访问特征提取

对用户副本放置特征的提取主要借助用户的历史信息。对于一个有历史信息的用户来说,其创建的副本已有一定的访问记录。

我们定义副本访问位置向量 cn_P 和访问位置范围 cn_cov 来提取副本访问的特征。其中 cn_P 表示该副本被访问的具体位置,cn_cov 表示访问同一副本的客户端(Client)的主要分布范围。

对于有 k 条副本访问位置记录的数据块 i,其 cn_cov 为其大于 q 条记录所对应的最小位置范围(q=0.8k),若没有这样的范围则 cn_cov 为全集。

提取过程如下:

  1. Client 随机抽取用户已创建的 n 个数据块组成抽样样本集合。
  2. Client 向名字节点发送获取集合 N 的副本个数信息和 cn_P 请求,获得样本副本个数集合和 cn_P 集合。
  3. Client 计算样本集合中 n 个数据块的副本平均值下界作为该次副本创建数量 rep_num。默认副本下界为 2,即至少有 2 个副本。
  4. Client 根据样本的 cn_P 计算 cn_cov,并组成包含了 n 个副本位置范围的集合 F={f1,f2,f3,……,fn}。
  5. Client 根据集合 F 来确定副本位置选择集合 F'(F 子元素的并集)。
  6. Client 将 rep_num 和 F'发送给名字节点。

如下表所示,根据访问节点的记录,可以得出其访问位置范围为向量(0,86,0574)。

表 1. 访问节点抽样的样本集合
节点 国际 地区 访问次数
a 0 81 080 15
b 0 86 021 21
c 0 86 0574 109
d 0 86 0574 81
e 0 86 0574 90
f 0 86 0580 17
g 1 18 37 1
h 3 55 089 9
i 4 37 21 3
j 5 145 03 2

节点负载

名字节点在获得副本创建个数和副本位置选择集合后,对处于副本位置选择集合中的节点根据其负载情况,选择 req_num 个负载低的节点进行副本放置。

其中节点负载越大表示磁盘越繁忙,已使用空间越多;越小表示磁盘空闲,已使用的空间越小。因此,通过考虑节点的负载情况,一方面可以避免因磁盘繁忙而导致数据块写操作的阻塞,从而导致系统性能的下降;一方面可以尽可能的使副本分布均衡,降低后续副本调整操作的压力,节约系统资源。

因此以磁盘 I/O 负载和磁盘空间负载作为整个节点负载的主要影响因素。公式如下:

清单 1. 节点负载计算公式
LOAD=W1*IO + W2*SPACE

其中 W1 和 W2 是磁盘 I/O 负载和磁盘空间负载的权重值。

放置算法

图 4. 副本创建流程图
图 4. 副本创建流程图
图 4. 副本创建流程图

副本放置策略比较分析和思考

本节通过模拟数据,进行 HDFS 默认算法与 UILBPS 算法进行比较分析。初始化模拟系统中有 3 个大洲,5 个国家,10 个地区,10 个数据中心,20 个机架,200 个节点,20 个 Client,250 个数据及其 2~5 个副本。其中节点和 Client 随机分布在各个不同的机架上,每个数据对象的副本也随机分布在不同的节点上,且被 Client 访问 10~20 次。不过同一 Client 的访问节点有一定的相似性,保证访问节点分布在一定的范围。系统默认磁盘负载的权重值为 0.5。

下图都是该模拟系统在重新创建 M 个数据对象后的比较:

图 5. 负载分析图
图 5. 负载分析图
图 5. 负载分析图

由上图可见,在创建的数据对象 M 相同的情况下,UILBPS 的负载是明显低于 HDFS 默认算法下的负载的,这正是因为考虑到了负载均衡的原因,尽可能的选择那些负载较低的节点进行副本的放置的结果。

图 6. 访问速率分析图
图 6. 访问速率分析图
图 6. 访问速率分析图

由上图可见,在创建的数据对象 M 相同的情况下,UILBPS 的平均访问距离是略小于 HDFS 默认算法下的负载的,这正是因为考虑到了用户访问特性的原因,使其 Client 能尽可能的访问与其较近的节点,从而节约了网络带宽,减少了因网络故障带来的风险,加快了节点访问的速率。

HDFS 的机架敏感放置策略对其副本放置的位置是随机的,而 UILBPS 则是基于用户历史信息和负载的,充分考虑了节点负载情况和用户历史访问的地域特征,从某种程度来说对机架敏感放置策略进行了优化,提高了系统的性能并均衡了系统负载,降低了用户的访问延迟,提高了数据的可用性。

因为 HDFS 系统将由数百或数千个存储着文件数据片断的服务器组成。实际上它里面有非常巨大的组成部分,每一个组成部分都很可能出现故障,这就意味着 HDFS 里的总是有一些部件是失效的,即硬件故障是常态,而不是异常。那么如何自动快速的恢复是 HDFS 一个很重要的目标。而对副本放置策略的优化则减少了系统负载,加快了副本的访问速率,从而能将失效的部件尽快的恢复过来或者起到与原失效部件一样的作用。

HDFS 有着高容错性的特点,并且设计了用来部署在低廉的硬件上的特性。同时,用户历史信息和负载状况都是通过名字节点来进行管理和计算。因此,优化中附加的信息并不会很大程度上占用 HDFS 所需要的磁盘空间,也不会产生因磁盘空间的减少而带来的系统性能下降问题。

对于因数据节点失效,副本损坏,数据节点磁盘损坏或者文件的复制因子增大等原因而导致的后续副本的调整来说,较好的副本位置更有利于副本的创建、删除和迁移,即更有利于后续的副本调整,保证了分布式系统的一致性、可用性、分区容错性。

结束语

本文主要对 HDFS 中副本放置策略进行了研究分析,并根据其算法上的实现提出了疑问,然后提出了基于用户历史信息和负载的放置策略对其原本的策略做出了一定的优化。事实上,本文提出的优化算法也并不是说一定是最优算法。哥伦比亚大学提出了一种自稳定的、全分布的、异步可升级的副本放置算法。加州大学伯克利分校开发设计了一个动态、高效及可升级的内容分发网络 SCAN(sealableContentAccessNetwork),使用了沿路缓存的算法进行副本放置。德克萨斯大学提出了一种协作的缓存放置算法等等。每种算法都有其优劣性,至于哪种算法最优,则需要通过生产环境来验证了。同时,整个 HDFS 系统乃至说 Hadoop 还是有很多值得研究、思考、优化和完善的地方。


相关主题


评论

添加或订阅评论,请先登录注册

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Information Management
ArticleID=1005420
ArticleTitle=HDFS 副本放置策略的研究和优化
publish-date=05112015