给定 a、b 两个文件，各存放 50 亿个 url，每个 url 各占 64 字节，内存限 制是 4G，让你找出 a、b 文件共同的 url？

在内存限制为 4GB 的情况下，直接将 50 亿个 URL 读入内存是不可行的。每个 URL 占 64 字节，50 亿个 URL 总共需要约 3.2TB 的内存。因此，我们需要使用外部排序和 MapReduce 等技术来解决这个问题。以下是使用 Hadoop 的解决方案：

解决方案 数据预处理：将文件 a 和 b 分成多个小文件，每个小文件的大小适合内存处理。 MapReduce 任务：使用 MapReduce 来找出两个文件中的共同 URL。 步骤

1. 数据预处理 将文件 a 和 b 分成多个小文件，每个小文件的大小适合内存处理。假设每个小文件的大小为 1GB，那么每个文件可以分成 32 个小文件（因为 4GB 内存可以处理 1GB 的数据）。

▼
bash
复制代码
split -b 1G a a_
split -b 1G b b_

2. 编写 MapReduce 程序 编写一个 MapReduce 程序来找出两个文件中的共同 URL。

Mapper Mapper 读取输入文件中的 URL，并输出 (URL, 文件标识) 对。

▼
java
复制代码
import java.io.IOException;
import java.util.StringTokenizer;

import org.apache.hadoop.io.LongWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Mapper;

public class CommonURLMapper extends Mapper<LongWritable, Text, Text, Text> {
    private final static Text fileMarker = new Text();

    @Override
    protected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {
        String line = value.toString();
        StringTokenizer tokenizer = new StringTokenizer(line);
        while (tokenizer.hasMoreTokens()) {
            String url = tokenizer.nextToken();
            if (context.getInputSplit().toString().contains("a_")) {
                fileMarker.set("a");
            } else {
                fileMarker.set("b");
            }
            context.write(new Text(url), fileMarker);
        }
    }
}

Reducer Reducer 收集来自 Mapper 的 (URL, 文件标识) 对，并找出同时出现在文件 a 和 b 中的 URL。

▼
java
复制代码
import java.io.IOException;
import java.util.HashSet;

import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Reducer;

public class CommonURLReducer extends Reducer<Text, Text, Text, Text> {
    private HashSet<String> seenFiles = new HashSet<>();

    @Override
    protected void reduce(Text key, Iterable<Text> values, Context context) throws IOException, InterruptedException {
        for (Text val : values) {
            seenFiles.add(val.toString());
        }

        if (seenFiles.contains("a") && seenFiles.contains("b")) {
            context.write(key, new Text("common"));
        }

        seenFiles.clear();
    }
}

3. 配置和运行 MapReduce 作业 编写一个主类来配置和运行 MapReduce 作业。

▼
java
复制代码
import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;

public class CommonURLJob {
    public static void main(String[] args) throws Exception {
        Configuration conf = new Configuration();
        Job job = Job.getInstance(conf, "Common URL Finder");

        job.setJarByClass(CommonURLJob.class);
        job.setMapperClass(CommonURLMapper.class);
        job.setReducerClass(CommonURLReducer.class);

        job.setOutputKeyClass(Text.class);
        job.setOutputValueClass(Text.class);

        FileInputFormat.addInputPath(job, new Path(args[0]));
        FileOutputFormat.setOutputPath(job, new Path(args[1]));

        System.exit(job.waitForCompletion(true) ? 0 : 1);
    }
}

4. 运行作业 将上述代码编译并打包成 JAR 文件，然后在 Hadoop 集群上运行。

▼
bash
复制代码
hadoop jar common-url-finder.jar CommonURLJob /input /output