HDFS多副本放置策略及云中的优化（LDBAS）

在HDFS集群中，一般设置多副本提高可靠性（冗余），也能提高数据读取的总体性能。但这多个副本应该选择哪些节点进行放置呢？即本文要讨论的数据放置策略，或称多副本放置策略 replica placement policy。
mark: 本文中，默认副本因子为3。

最原始的放置策略即把三个副本尽量分配到不同的三个节点上。否则，假设两副本放置到了一个节点，则会因为该节点的故障而直接损失两个副本，且在该数据被大量客户端同时读取时，两个副本也不能分担负载（该节点的处理能力即上限）。

三副本放置

机架感知策略 Rack Awareness

既然考虑了节点故障，不妨再考虑下机架故障：由于断电/物理线路断路/交换机故障等问题造成一整个机架的机子同时崩溃时……若某个重要机密放置时正好全放在了这一个机架的三台机子上……就问你怕不怕！
若我们在数据放置时，尽量将一个数据的不同副本尽量均匀地放置到不同机架的机子中，就能有效避免机架崩溃即数据丢失的情况，提高可靠度。若你非要问我：几个机架都崩溃了呢？机房都没了呢？我也无言以对，抱拳向“杠精”致敬。

网络拓扑

实现“均匀放置到不同机架”的策略之前，我们需要先识别不同的机架。在Hadoop中，通过网络拓扑对节点进行相对位置定义。树形的网络位置拓扑如下，一个严格的层级结构。

网络位置拓扑

/datacenter/rack/node，类似文件系统中的文件路径名，Hadoop据此来识别不同的节点。

但是集群无法自己感知到各节点的相对位置（其实可以通过探测网络延迟来推断），需要进行机架感知的配置。配置前，所有的节点的相对位置都默认为是一样的“/default-rack”，只会通过IP去区分。
Hadoop中，可通过调用Java类或配置文件指定的外部脚本来获取各节点的网络位置标志符。但两种方式都需要遵守继承org.apache.hadoop.net.DNSToSwitchMapping接口，以保证节点与ID的一一对应关系，拓扑信息格式/rack/host。

使用Java类：实现一个类，该类将由net.topology.node.switch.mapping.impl参数指定
使用外部脚本：由net.topology.script.file.name参数指定，以下是官网给的一个python脚本示例，输入节点IP可输出对应的位置ID。

#!/usr/bin/python
# this script makes assumptions about the physical environment.
#  1) each rack is its own layer 3 network with a /24 subnet, which
# could be typical where each rack has its own
#     switch with uplinks to a central core router.
# 2) topology script gets list of IP's as input, calculates network address, and prints '/network_address/ip'.

import netaddr
import sys
sys.argv.pop(0)                                                  # discard name of topology script from argv list as we just want IP addresses

netmask = '255.255.255.0'                                        # set netmask to what's being used in your environment.  The example uses a /24

for ip in sys.argv:                                              # loop over list of datanode IP's
    address = '{0}/{1}'.format(ip, netmask)                      # format address string so it looks like 'ip/netmask' to make netaddr work
    try:
        network_address = netaddr.IPNetwork(address).network     # calculate and print network address
        print "/{0}".format(network_address)
    except:
        print "/rack-unknown"

机架感知策略

启用机架感知后的副本放置策略具体如下：

如果writer在集群节点中，将副本一放置到它所属的节点上，无法满足则放置到与它同机架的随机一个节点，再不行就随机一个节点。
副本二放置到不同机架的节点上。
副本三放置到与副本二同机架的节点中。

由此避免机架故障带来的数据丢失，并能有效减少机架间的写数据带来的流量开销，可提高写入性能，但是限定在了两个机架中从而降低了数据读取的总网络带宽。算是一个总体性能的综合衡量考虑吧。
若副本因子大于3，后续的副本会随机放置，但总体上会保证每个机架的副本数量小于 $(replicas-1) / racks +2$ 。

LDBAS(可靠性部分)

在云环境中又不一样了。在云平台中，两个虚拟机可能会存在于一台物理宿主机中，称之为虚拟机共存。若两个副本被分配到这两个同宿主机的虚拟节点中，一样地存在可靠性下降（当物理机宕掉时）和性能瓶颈（该节点的处理能力限制了该副本的并发读取上限）。

LDBAS即解决了云环境中，虚拟共存带来的可靠性下降，主要思想即重构Hadoop网络拓扑，将虚拟节点的物理宿主机信息考量其中，副本分配时尽量分布到不同物理宿主机的虚拟机节点，避免或减少副本在硬件设备（物理机/机架）的冗余放置，从而提高可靠性。即网络拓扑更新为：/机架/物理宿主机/虚拟节点。

LDBAS网络位置拓扑

由图，可定义两个节点的距离为树中最短路径的边的条数。由此节点间距离越小，即节点的共存信息越少，在其中放置副本的可靠性越高。故将节点间距离作为副本放置时选择节点的依据。
如何求解副本放置的多个节点呢？暴力求解固然能得到最优解，但遍历搜索多节点集合选择相对距离最小的一个，求解的时间复杂度达到O(n^k)，k是副本因子数。HDFS原始放置策略，是针对每个副本都遍历节点进行选择，复杂度在(可·n)，LDBAS也采用了贪心算法求解：

优先客户端所在节点或与其同机架节点或随机
与副本一放置节点，距离最远的节点
与副本一、二放置节点总距离最远的节点
实质策略中，还考虑了本地性的影响因素，此处仅针对可靠性，不做展开（可见后续文章）。