**

大数据小题

一、简述向HDFS写文件的流程；
答：1.调用客户端对象DistributedFileSystem的create方法
2.DistributedFileSystem会发起对namenode的一个RPC连接，请求穿件一个文件，不包括block块的请求。namenode会执行各种各样 的检查，确保要创建的文件不存在，并且客户端有创建文件的权限。如果检查通过，namenode会创建一个文件在edits中，同时更新内存状态，否则创建失败，客户端抛出异常IOException。
3.NN在文件创建后，返回给HDFSClient文件创建成功的信息和文件块列表信息。
4.DistributedFileSystem返回一个FSDataOutStream对象给客户端用于写数据。FSDataOutputSystem封装了一个DFSOutstream对象负责客户端跟datanode以及namenode的通信
5.5.FSDataOutputStream对象将数据切分为小的数据包（64kb，core-default.xml：file.client-write-packet-size默认值65536），并写入到一个内部队列（“数据队列”）。DataStreamer会读取其中内容，并请求namenode返回一个datanode列表来存储当前block副本。列表中的datanode会形成管线，DataStreamer将数据包发送给管线中的第一个datanode，第一个datanode将接收到的数据发送给第二个datanode，第二个发送给第三个。。。
6.DFSOoutputStream维护着一个数据包的队列，这的数据包是需要写入到datanode中的，该队列称为确认队列。当一个数据包在管线中所有datanode中写入完成，就从ack队列中移除该数据包。如果在数据写入期间datanode发生故障，则执行以下操作
a)关闭管线，把确认队列中的所有包都添加回数据队列的最前端，以保证故障节点下游的datanode不会漏掉任何一个数据包。
b)为存储在另一正常datanode的当前数据块指定一个新的标志，并将该标志传送给namenode，以便故障datanode在恢复后可以删除存储的部分数据块。
c)从管线中删除故障数据节点并且把余下的数据块写入管线中另外两个正常的datanode。namenode在检测到副本数量不足时，会在另一个节点上创建新的副本。
d)后续的数据块继续正常接受处理。
e)在一个块被写入期间可能会有多个datanode同时发生故障，但非常少见。只要设置了dfs.replication.min的副本数（默认为1），写操作就会成功，并且这个块可以在集群中异步复制，直到达到其目标副本数（dfs.replication默认值为3）。
7.如果有多个block，则会反复从步骤4开始执行。
8.当客户端完成了数据的传输，调用数据流的close方法。该方法将数据队列中的剩余数据包写到datanode的管线并等待管线的确认
9.客户端收到管线中所有正常datanode的确认消息后，通知namenode文件写完了。
10.namenode已经知道文件由哪些块组成，所以它在返回成功前只需要等待数据块进行最小量的复制。

二、Hadoop集群启动的主要进程有哪几个？分别起到什么作用？
1. Namenode它是hadoop中的主服务器，管理文件系统名称空间和对集群中存储的文件的访问，保存有metadate元数据
2. SecondaryNameNode它不是namenode的冗余守护进程，而是提供周期检查点和清理任务。帮助NN合并editslog，减少NN启动时间
3. DataNode他负责管理连接到节点的数据（一个集群中可以有多个节点）。每个存储数据的节点运行一个datanode守护进程。
4. ResourceManager(Job Tracker) JobTracker负责调度DataNode上的工作。每个DataNode上有一个TaskTracker，他们执行实际任务
5.NodeManager（TaskTracker）执行任务
6.DFSZKFailoverController高可用时它负责监控NN的状态，并及时的把状态信息写入ZK。它通过一个独立线程周期性的调用NN上的一 个特定接口来获取NN的健康状态。FC也有选择谁作为Active NN的权利，因为最多只有两个节点，目前选择策略还比较简单（先到先得，轮换）。
7.JournalNode 高可用情况下存放namenode的editlog文件

三、Zookeeer的选举机制，以及搭建集群时的注意点？
1.zookeeper选举机制是过半机制：集群中只要过半节点存活，集群就可用
2.zookeeper搭建的时候并不需要指定的leader和follower，而是通过其内部的选举机制临时产生的
3.选举说明选举机制：
假设有五台服务器组成了zookeeper集群，他们的ID依次是1~5
（1）假设先启动服务器1，此时只有它启动了，它发出去的报文没有任何回应，此时他的选举状态为looking
（2）服务器2启动，他会和服务器1通信，互相交换自己的选举结果，（它们首先会投自己一票，但发现自己的票数不过半）由于 两者没有历史数据，所以ID值比较大的服务器2胜出，但没有达到超过半数以上的服务器统一选它，所以服务器1和服务器2，继续保持looking状态
（3）服务器3启动，由以上可知，服务器3获得了服务器1和2的选票，此时他有三票，超过半数，服务器3成为leader
（4）服务器4启动，由于已经有超过半数以上的服务器选举了服务三，所以服务器4只能是follower
（5）服务器5同4一样是follower
4.搭建集群注意点
在各个zkData目录下创建一个myid的文件，并依次递增给myid赋值。比如第一台myid上写入1，第二台写2，以此类推。
四、找出共同的url，给定a，b两个文件，各存放50亿个url，每个url各占64个字节，内存限制是4G，找出a,b文件共同的url。
答：1. 遍历文件a，对每个url求取hash(url)%1000，然后根据所得值将url分别存储到1000个小文件（设为a0,a1,…a999）当中；遍历文件b，对每个url求取hash(url)%1000，然后根据所得值将url分别存储到1000个小文件（设为b0,b1,…b999）当中；这样处理后，所有可能相同的url都在对应的小文件(a0-b0, a1-b1…a999-b999)当中，不对应的小文件（比如a0-b99）不可能有相同的url。
2.统计1000对文件中相同的url，采用hash_set.比如对a0-b0，遍历a0，将其中的url存储到hash_set当中；然后遍历b0，如果url在hash_map中，则说明此url在a和b中同时存在，保存到文件中即可。

五、对大文件进行排序。现在有一个10G的大文件，文件内容是一行一行字符串，但是机器内存只有1个G，如果对文件内容进行排序，需要怎么做，写出算法思路即可。
答：10G的大文件、不可能采用传统排序法。但是可以将文件分成许多块，每块xMB,针对每个快各自进行排序，存回文件系统。然后将这些块逐一合并，最终得到全部排好序的文件。
外排序的一个例子是外归并排序（External merge sort），它读入一些能放在内存内的数据量，在内存中排序后输出为一个顺串（即是内部数据有序的临时文件），处理完所有的数据后再进行归并。比如，要对900MB的数据进行排序，但机器上只有100 MB的可用内存时，外归并排序按如下方法操作
读入100 MB的数据至内存中，用某种常规方式（如快速排序、堆排序、归并排序等方法）在内存中完成排序。
将排序完成的数据写入磁盘。
重复步骤1和2直到所有的数据都存入了不同的100 MB的块（临时文件）中。在这个例子中，有900 MB数据，单个临时文件大小为100 MB，所以会产生9个临时文件。
读入每个临时文件（顺串）的前10 MB（ = 100 MB / (9块 + 1)）的数据放入内存中的输入缓冲区，最后的10 MB作为输出缓冲区。（实践中，将输入缓冲适当调小，而适当增大输出缓冲区能获得更好的效果。）
执行九路归并算法，将结果输出到输出缓冲区。一旦输出缓冲区满，将缓冲区中的数据写出至目标文件，清空缓冲区。一旦9个输入缓冲区中的一个变空，就从这个缓冲区关联的文件，读入下一个10M数据，除非这个文件已读完。这是“外归并排序”能在主存外完成排序的关键步骤 – 因为“归并算法”(merge algorithm)对每一个大块只是顺序地做一轮访问(进行归并)，每个大块不用完全载入主存

六、请介绍下java常用的集合，特性，使用场景等
答：List，Set，Map都是接口，前两个继承的是Collection接口，Map为独立接口
1.Set下：
（1）HashSet，（特性：底层数据结构是哈希表 无序 唯一 使用hashcode（）和equals（）保证元素唯一性）
（2）LinkedHashSet，（底层数据结构是链表和 哈希表。FIFO插入有序，唯一 由链表保持元素有序，由哈希表保证元素唯一）
（3）TreeSet，（底层数据结构是红黑树 唯一，有序 使用自然排序，比较器排序保证元素排序 根据比较的返回值是否为0来决定元素 的唯一性）
2.List下：
（1）ArrayList，（特性：数据结构是数组，查询快，增删慢 线程不安全，效率高）
（2）Vector，（特性：数据结构跟ArrayList一样是数组，查询快，增删慢 线程安全，效率低）
（3）LinkedList （特性：底层数据结构是链表，查询慢，增删快， 线程不安全，效率高）
使用场景：唯一吗?
唯一：Set
排序吗?
是：TreeSet或LinkedHashSet
否：HashSet
如果你知道是Set，但是不知道是哪个Set，就用HashSet。
不唯一：List
要安全吗?
是：Vector
否：ArrayList或者LinkedList
查询多：ArrayList
增删多：LinkedList
如果你知道是List，但是不知道是哪个List，就用ArrayList
3.Map下：
（1）Hashtable，（特性：无序 方法同步 线程安全 效率较低 不允许有null值）
（2）HashMap，（特性：无序 方法不同步 线程不安全 效率较高 允许有null值）
（3）TreeMap （特性：有序）
三者在数据存储层面的机制原理基本一致
HashMap不是线程安全的，多线程环境下除了不能保证数据一致性之外，还有可能在rehash阶段引发Entry链表成环，导致死循环
Hashtable是线程安全的，能保证绝对的数据一致性，但性能是问题，并发线程越多，性能越差
ConcurrentHashMap 也是线程安全的，使用分离锁和volatile等方法极大地提升了读写性能，同时也能保证在绝大部分情况下的数据一致性。但其不能保证绝对的数据一致性， 在一个线程向Map中加入Entry的操作没有完全完成之前，其他线程有可能读不到新加入的Entry

		。