面试题-关于大数据量的分布式处理

题目：生产系统每天会产生一个日志文件F，数据量在5000W行的级别。文件F保存了两列数据，一列是来源渠道，一列是来源渠道上的用户标识。文件F用来记录当日各渠道上的所有访问用户，每访问一次，记录一条。

请问如何快速计算出各渠道上新增的用户？

问题分析：首先本次面试的是有关于分布式数据处理以及数据分析的职位，所以相关的面试题目可能会偏向于使用分布式的思想去解决。但无奈本人当时反应太慢，实在没向分布式处理方向思考。

方案一：

本题最直观的一个处理方法就是，直接拿着当日新增的5000W条访问记录一条一条的去匹配历史访问用户。若存在历史访问记录，则忽略；若不存在访问记录，则保存为新增记录。很明显，假若历史访问用户有2亿条记录，则需要和2亿条数据比较5000W次。比较次数可想而知。

由于本人一直在做基于数据库的数据处理工作，很容易就想到将历史数据保存在数据库的一张表中，并对来源渠道和用户标识这两个字段建立索引，然后遍历日志文件F（5000W次）。根据日志文件F中的每一行去匹配数据库中的历史访问记录。由于历史数据表有索引，单次查询的速度也非常快。但是需要5000W次的数据库查询，很明显效率低下。

方案二：

既然多次单一查询无法满足要求，于是可以先通过一种数据导入技术将当日新增数据导入到数据库的另一张表中，并和历史数据做左外关联。若能关联成功，则表示此用户已存在；若关联失败，则表示此用户不存在。

此方案暂且不说5000W条记录的大表与2亿条记录的大表关联效率有多高以及使用到的数据库缓冲区的资源有多少，单就5000W条访问记录导入数据库表，都是一个不小的时间花费。

方案三：

很明显，面试时方案二的回答并未达到面试官的预期，最初被遗憾的PASS掉。一家很有潜力，自己很看好的公司，并计划做为自己未来发展方向的职位，就这样丢下我，扬长而去了。

这几天又看了下分布式相关的介绍，突然想到这道题。一下子醒悟过来，其实还是因为对题目要考察的点分析得不够透彻。当时以为只是仅仅考数据处理效率的一个题目，其实考的是一种将复杂问题拆分为简单问题的拆分思想。了解到这一层，一种新的方式立马在脑海中浮现出来。具体如下：

假如现在有N（N>=2）个存储块，并存在一个函数f（来源渠道，用户标识），对于给定的一组（来源渠道，用户标识），总能将其分发到一个固定的存储块内。那么可以使用此函数将5000W行访问记录尽量均匀的分发至N个存储块上，并同时使用此函数将历史访问记录也分发至这些存储块上。由于相同的一组记录，肯定会被分配至同一个存储块，所以比较时，只需要分别比较各个存储块上当日新增记录与历史访问用户，然后将N个存储块上比较的结果汇总，即可得到最终结果。

假设历史访问用户数据已通过函数f（来源渠道，用户标识）被分发至了N个历史文件H1、H2、…、HN。则详细处理步骤如下：

1、将F中的内容使用函数f（来源渠道，用户标识），分发至文件F1、F2、…、FN内。（可开M（M>=2）个并行，且若N-M越大，同时向同一文件写入数据的概率越小）

2、将文件F1、F2、…、FN内的访问记录去重。（可开N个并行分别处理对应的N个文件）。

3、将文件Fn（1=<n<=N）去重后的结果与对应的历史文件Hn比较得出新增用户结果Rn。（可开N个并行分别处理对应的N个文件且当N足够大时，实际要处理数据的量级就会相当小）。

4、合并第3步得到的结果R1、R2、…、RN即可得到当日新增用户。（可并行）

5、为使历史数据文件H1、H2、…、HN中的数据最全，将结果R1、R2、…、RN分别写入对应的历史文件中。（可并行）

本方案主要有以下优点：

1、数据的分发、处理、合并都可并行处理，明显提高了处理效率。

2、由于每个存储块上的新增数据，只需要与它对应存储块上的历史数据比较即可，大大减少了比较次数。（对于当日每一条记录来说，都只需要与大约历史的N分之一条数据去比较）

3、基本不需要考虑历史全量数据的保存及获取问题。

本方案缺点：

1、处理方案明显变的复杂许多，不仅需要处理数据的分发，处理，还需要一个并行的快速收集方法。

2、可能需要多台服务器并行处理。

本方案难点：

1、一个稳定（对于相同的一组来源渠道和用户标识，必定会被分发至同一存储块）、快速（根据一条来源渠道和用户标识数据，可以快速的计算出它将要被分发至的存储块）、均匀（当日新增数据及历史数据都能尽量均匀的被分发至N个存储块，最理想的情况是每个存储块上分发到的数据都是总数据的N分之一）的分发函数至关重要。

2、如何分发、并行处理及汇总数据。