chooseTarget，在选则取dataNode方法后会调用getPipeline方法，进行dataNode排序，从writer所在节点开始,总是寻找相对路径最短的目标节点,最终形成pipeline,这其实也是经典的TSP旅行商问题.下面是具体的源码实现
/**
* 从writer所在节点开始,总是寻找相对路径最短的目标节点,最终形成pipeline
* Return a pipeline of nodes.
* The pipeline is formed finding a shortest path that
* starts from the writer and traverses all <i>nodes</i>
* This is basically a traveling salesman problem.
*/
private DatanodeStorageInfo[] getPipeline(Node writer,
DatanodeStorageInfo[] storages) {
LOG.info("-------getPipeline---------------");
LOG.info("-------Node writer---------------" + writer.getName() + "=" + writer.getNetworkLocation());
for (int i = 0; i < storages.length; i++) {
DatanodeStorageInfo storage = storages[i];
String hostName = storage.getDatanodeDescriptor().getHostName();
LOG.info("---getPipeline------" + hostName);
}
LOG.info("-------getPipeline---------------");
if (storages.length == 0) {
return storages;
}
synchronized (clusterMap) {
int index = 0;
// 首先如果writer请求方本身不在一个datanode上,则默认选取第一个datanode作为起始节点
if (writer == null || !clusterMap.contains(writer)) {
writer = storages[0].getDatanodeDescriptor();
}
for (; index < storages.length; index++) {
// 获取当前index下标所属的Storage为最近距离的目标storage
DatanodeStorageInfo shortestStorage = storages[index];
// 计算当前距离
int shortestDistance = clusterMap.getDistance(writer,
shortestStorage.getDatanodeDescriptor());
int shortestIndex = index;
for (int i = index + 1; i < storages.length; i++) {
// 遍历计算后面的距离
int currentDistance = clusterMap.getDistance(writer,
storages[i].getDatanodeDescriptor());
if (shortestDistance > currentDistance) {
shortestDistance = currentDistance;
shortestStorage = storages[i];
shortestIndex = i;
}
}
//switch position index & shortestIndex
// 找到新的最短距离的storage,并进行下标替换
if (index != shortestIndex) {
storages[shortestIndex] = storages[index];
storages[index] = shortestStorage;
}
// 找到当前这一轮的最近的storage,并作为下一轮迭代的源节点
writer = shortestStorage.getDatanodeDescriptor();
}
}
return storages;
}
概况就是选出一个源节点,根据这个节点,遍历当前可选的下一个目标节点,找出一个最短距离的节点,作为下一轮选举的源节点,这样每2个节点之间的距离总是最近的,于是整个pipeline节点间的距离和就保证是足够小的了.那么现在另外一个问题还没有解决,如何定义和计算2个节点直接的距离,就是下面这行代码：
clusterMap.getDistance(writer,shortestStorage.getDatanodeDescriptor());
要计算其中的距离,我们首先要了解HDFS中如何定义节点间的距离,其中涉及到了拓扑逻辑结构的概念,结构图如下:
20160420093756707.png
这里显示的是一个三层结构的树形效果图,Root可以看出是一个大的集群,下面划分出了许多个机架,每个机架下面又有很多属于此机架的节点.在每个连接点中,是通过交换机和路由器进行连接的.每个节点间的距离计算方式是通过寻找最近的公共祖先所需要的距离作为最终的结果.比如Node1到Node2的距离是2,就是Node1->Rack1, Rack1->Node2.同理,Rack1的Node1到Rack2的Node1的距离就是4.大家有兴趣的可以学习一下相关算法LCA最近公共祖先算法.
网友评论