数据结构算法及分布式文件实践
Author: Jessie
Date: 2020/7/28 V1.0
两条单向链表是否合并的查找算法
有两个单向链表(链表长度分别为m,n)。这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速判断这两个链表是否合并?如果合并,找到合并的原则,也就是图中的x元素。
请用(伪)代码描述算法,并给出时间复杂度。
方法一:
采用暴力的方法,遍历两个链表,判断第一个链表的每个结点是否在第二个链表中,时间复杂度为O(m*n),耗时很大。
方法二:
如果两个链表合并,那么最后的节点的地址一定相同。时间复杂度为O(m+n)。
伪代码实现:
DataNode服务节点宕机,HDFS处理时序图
请画出DataNode服务器节点宕机的时候,HDFS的处理过程时序图。
HDFS写文件具体流程如下:
1.客户端端首先通过DistributedFileSystem对象的create方法创建一个FSDataOutputStream(输出流)对象;
2.客户端通过DistributedFileSystem对象向NameNode发起一次RPC调用,在HDFS的Namespace中创建一个文件条目;
3.通过FSDataOutputStream对象,向DataNode写入数据,数据首先被写入FSDataOutputStream对象内部的Buffer中,然后数据被分割成一个个Packet数据包;
4.以Packet最小单位,基于Socket连接发送到按特定算法选择的HDFS集群中一组DataNode中的一个节点上,在这组DataNode组成的Pipeline(数据量管道)上依次传输Packet;
5.这组DataNode组成的Pipeline反方向上,发送ack,最终由Pipeline中第一个DataNode节点将Pipeline ack发送给客户端;
6.完成向文件写入数据,客户端在FSDataOutputStream对象上调用close方法,关闭流;
7.调用DistributedFileSystem对象的complete方法,通知NameNode文件写入成功。
判断失效:
发现DataNode宕机后,NameNode处理时序图,简化表示过程如下:
参考文献:
1 . 对于有环的链表查找是否有合并点,还可以参考如下链接:
https://www.cnblogs.com/testling/p/11581179.html
版权声明: 本文为 InfoQ 作者【架构5班杨娟Jessie】的原创文章。
原文链接:【http://xie.infoq.cn/article/e95b72ca3a097b8a89fb357c2】。文章转载请联系作者。
评论