前言

上次讲了大数据启蒙的分治思想，这次根据几个场景需求，一起来讨论一下大数据单机处理大数据问题。

需求一

假设有一个需求：

有一个非常大的文本文件，里面有很多很多的行（上亿），只有两行一样，它们出现在未知的位置，需要查找到它们。单机处理这个问题，而且可用的内存很少，也就几十兆。

假设I/O读取速度是500MB每秒（固态硬盘更快，这边只是一个假设值），1T文件读取一遍需要约3分钟，循环遍历需要I/O读取N次数据，使用分治思想可以使实际为2次I/O读取时间。内存寻址速度比I/O寻址快10万倍。

方案一：循环对比每一行。第1行作为对比数据，和第2、3、4、n行数据对比，如果没有重复，就将第2行作为对比数据再循环对比一次。这样最坏的结果是最后两行是一样的，那么就要读取n - 1次数据（1T），需要耗时（n-1)*30分钟。

I/O读取速度是大多数场景性能的瓶颈。

一个程序员如果在I/O方面可以有很多优化方案，那他就已经进入高级开发的门槛了。那么我们也来试试迈出这一步。

我们通过readLine()方法读取文件数据，每次读取后，将读取的数据的hashCode 取模 2000，然后放到对于位置的一个小文件中，这样我们遍历了一次整个文件（30分钟），将这个文件分为2000个小文件。因为hashCode值的算法是固定的，那么相同行的hashCode值是一样的，然后取模的值也是一样的，那相同行就会在同一个小文件里面。然后我们再遍历2000个小文件，就可以找到里面的相同的行，这时候最大复杂度也是读取2000个小文件，一共1T，耗时30分钟。这样算起来，最大时间复杂度就是2*30分钟。

需求二

假设1T的文件全部是乱序数字，现在要将这些数字全排序。

这时候使用hashCode就不合适了，因为取数字的hashCode反而增加了一些时间消耗，那么可以换一种方式。

每次读取一个数x，如果x大于0且小于等于100，就将这个数放到第一个小文件中，以此类推，我们可以得到很多个小文件，这个过程消耗了30分钟。这些文件是有大小顺序的，但是文件内部的值是乱序的。然后依次读取每个小文件，排序后追加写入第一个小文件，这样消耗了30分钟，得到了全排序的文件，最大时间复杂度就是2*30分钟。

当然，我们还有其他方案，每次先读取50M数据进行排序，然后放到一个小文件里，重复操作后得到若干个小文件，这些文件是没有顺序的，但是文件内的数据是有顺序的。敲重点了，当遇到外部是无序的，内部是有序的数据结构，我们可以使用归并排序算法。 这里就细说了。

需求三

需求一如果想让时间变为分钟甚至秒要如何实现？

单机性能瓶颈是I/O速度，通过单机去实现想要达到几分钟，甚至几十秒的难度很大。那么我们就可以考虑多台机器实现了。假设有2000台机器，每台500M数据，并行读取数据大概要消耗1秒钟。然后使用需求一的方式，将500M数据分为2000个小文件，这时候每台机器中都有2000个小文件，因为数据是分开的，要判断是否重复就要吧所有机器中的相同位置的文件合并起来判断。那么我们可以让第1台机器，拉取其他所有机器的第1个文件到本机合并数据判断，以此类推每个机器判断一个位置的文件，这是可以并行操作的，假设拉取其他文件的耗时1分钟，判断文件500M文件消耗1秒钟，那么这个过程大概消耗了62秒。这只是举个例子说明解决方案思路，时间并不是很准确。这其实是以资源换取时间的方式。