メディアチーム【Java】MapReduceプログラミングモデルとMongoDBを用いて Facebookのような共通の友達（Mutual Friends)を見つける！
メディアチームIT技術
MapReduceプログラミングモデルとMongoDBで共通の友達を見つける！
前回の記事では、実現的な例を用いて MapReduce プログラミングモデルの概念を解説しました。
今回は、MapReduce プログラミングモデルを用いて、Facebook のようなソーシャルネットワークにおける、共通の友達を見つけてみたいと思います！
共通の友達を見つける機能とは？
Facebook では、他のユーザのプロフィルを見ると、自分とそのユーザとの共通の友達が表示されます。
Facebook を利用したことがあれば、見たことがある人も多いのではないでしょうか？
今回は、そのような共通の友達を求める方法を、MapReduce プログラミングモデルを適用した Steve Krenzel のアルゴリズムを Java で実装することで実現したいと思います！
【参考サイト】
http://stevekrenzel.com/articles/finding-friends
前回の記事はこちら
実装環境
今回の執筆者の環境は、以下の通りです。
- IDE : IntelliJ IDEA
- JDK : Oracle Java 8
- OS : MacOS Catalina
使用するデータベース
データベースは、「MongoDB Atlas」のフリーアカウントを使用します。
MongoDB Atlas は無料枠の範囲でも、512 MB の容量を自由に使うことが出来ます。
また、MongoDB の Java API を用いて、IDE からクラウドにある MongoDB のデータベースを操作することも出来ます。
【MonagoDB Atlas】
https://www.mongodb.com/cloud/atlas
ファイル構成
では早速、プロジェクトを作成し、実装を進めて行きます！
最終的にプロジェクトの構成は、このようになります。
Java で MongoDB Atlas に接続する！
Maven プロジェクトを作成する
IDE を起動して、新規の Maven プロジェクトを作成してください。
プロジェクト名は「mapreduce-mutualfriend」と名付けましょう。
MongoDB Java ドライバを用意する
MongoDB に接続するには、Maven リポジトリの「MongoDB Java ドライバ」が必要になります。
ですので、新しく作成した「mapreduce-mutualfriend」プロジェクトの pom.xml ファイルに「mongo-java-driver」へのディペンデンシーを追加してください。
pom.xml ファイル
pom.xml ファイルは、以下のようになります。
1<?xml version="1.0" encoding="UTF-8"?>
2<project xmlns="http://maven.apache.org/POM/4.0.0"
3 xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
4 xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
5 <modelVersion>4.0.0</modelVersion>
6
7 <groupId>org.example</groupId>
8 <artifactId>mapreduce-mutualfriend</artifactId>
9 <version>1.0-SNAPSHOT</version>
10
11 <dependencies>
12 <!-- https://mvnrepository.com/artifact/org.mongodb/mongo-java-driver -->
13 <dependency>
14 <groupId>org.mongodb</groupId>
15 <artifactId>mongo-java-driver</artifactId>
16 <version>3.12.1</version>
17 </dependency>
18 </dependencies>
19
20</project>「Connection String」を取得
次に、MongoDB Atlas への接続に必要となる「Connection String」を取得します！
MongoDB Atlas のフリーアカウントを、「登録・ログイン」すると、「Clusters」ページが表示されます。
「Clusters」ページの「Sandbox」の枠の中に、「connect」ボタンがあると思います。
この「connect」ボタンをクリックすると、ダイアログウィンドウが表示されます。
ダイアログウィンドウ
Connect your application メニュー
そして、「Connect your application」メニューをクリックすると、次の画面が表示されます。
ここで、「DRIVER」のドロップダウンメニューから「Java」を選んでください。
「VERSION」は、一番新しいバージョンを選択します。
Connection String が表示される
すると、「Connection String」が表示されるので、それをコピーしてください。
※ 上の画像の場合だとmongodb+srv://username:password@cluster0-s9bfc.mongodb.net/rightcode?retryWrites=true&w=majority の部分
プログラム中で、MongoDB Atlas への接続を確立する際に、ここでコピーした文字列を使用します。
友達情報をデータベースに追加する！
MongoDB Atlas に接続する準備ができたので、早速、使用する友達情報データをデータベースに追加していきます。
MongoCloudConnector クラスを追加
src/main/java/mongodb/ ディレクトリに、以下のような MongoCloudConnector クラスを追加してください。
1package mongodb;
2
3import com.mongodb.ConnectionString;
4import com.mongodb.MongoClientSettings;
5import com.mongodb.MongoClientURI;
6import com.mongodb.client.MongoClient;
7import com.mongodb.client.MongoClients;
8import com.mongodb.client.MongoCollection;
9import com.mongodb.client.MongoDatabase;
10import org.bson.codecs.configuration.CodecRegistry;
11import org.bson.codecs.pojo.PojoCodecProvider;
12
13import java.util.Arrays;
14import java.util.List;
15
16import static org.bson.codecs.configuration.CodecRegistries.fromProviders;
17import static org.bson.codecs.configuration.CodecRegistries.fromRegistries;
18
19public class MongoCloudConnector {
20 MongoClientURI atlasUri = new MongoClientURI("mongodb+srv://uichaya:accha1330@cluster0-s9bfc.mongodb.net/rightcode?retryWrites=true&w=majority");
21 public MongoDatabase db;
22 public MongoCollection<Person> person_coll;
23
24 public MongoCloudConnector() {
25 ConnectionString connectionString = new ConnectionString(atlasUri.toString());
26 CodecRegistry pojoCodecRegistry = fromProviders(PojoCodecProvider.builder().automatic(true).build());
27 CodecRegistry codecRegistry = fromRegistries(MongoClientSettings.getDefaultCodecRegistry(), pojoCodecRegistry);
28
29 MongoClientSettings clientSettings = MongoClientSettings.builder()
30 .applyConnectionString(connectionString)
31 .codecRegistry(codecRegistry)
32 .build();
33
34 MongoClient mongoClient = MongoClients.create(clientSettings);
35 db = mongoClient.getDatabase("rightcode");
36 person_coll = db.getCollection("person", Person.class);
37 System.out.println("Connected to : " + db.getName() + ":" + person_coll.getNamespace());
38 }
39
40 public static void main(String[] args) {
41 MongoCloudConnector atlasConnector = new MongoCloudConnector();
42
43 Person chieya = new Person("Chieya");
44 chieya.setFriend_list(Arrays.asList(new String[]{"Maya", "Sora", "Yukie", "Kenji"}));
45
46 Person yukie = new Person("Yukie");
47 yukie.setFriend_list(Arrays.asList(new String[]{"Chieya", "Sora", "Zara", "Rafa"}));
48
49 Person maya = new Person("Maya");
50 maya.setFriend_list(Arrays.asList(new String[]{"Chieya", "Zara", "Rafa"}));
51
52 Person sora = new Person("Sora");
53 sora.setFriend_list(Arrays.asList(new String[]{"Chieya", "Yukie", "Ichiro", "John"}));
54
55 List<Person> persons = Arrays.asList(new Person[]{chieya, yukie, maya, sora});
56
57 //atlasConnector.person_coll.insertOne(michie);
58 atlasConnector.person_coll.insertMany(persons);
59
60 for (Person p : atlasConnector.person_coll.find()) {
61 System.out.println(p);
62 }
63 }
64
65}MongoCloudConnector クラスのコンストラクタによって、MongoDB Atlas のクラスタ上に、「rightcode」という新規のデータベースと、「person」という新しいコレクションが作成されます。
ここで、「person」コレクションのデータ構造は、後述の「Person」クラスに反映されます。
「Person」クラス
src/main/java/mongodb/ ディレクトリに「Person.java」ファイルを作成し、Person クラスのデータ構造を次のコードのように定義します。
1package mongodb;
2
3import org.bson.types.ObjectId;
4import java.util.List;
5
6public final class Person {
7 private ObjectId id;
8 private String name;
9 private List<String> friend_list;
10
11 public Person() {
12 id = new ObjectId();
13 }
14
15 public Person(String name){
16 id = new ObjectId();
17 this.name = name;
18 }
19
20 public ObjectId getId() {
21 return id;
22 }
23
24 public void setId(final ObjectId id) {
25 this.id = id;
26 }
27
28 public String getName() {
29 return name;
30 }
31
32 public void setName(final String name) {
33 this.name = name;
34 }
35
36 public List<String> getFriend_list(){
37 return friend_list;
38 }
39
40 public void setFriend_list(List<String> friend_list){
41 this.friend_list = friend_list;
42 }
43
44 public String toString(){
45 return name + "|" + friend_list.toString();
46 }
47}ここで Person クラスは、ObjectId 、name 、friend_list と言う３つのメンバーから成り立っています。
ObjectId は、「person」コレクション内のドキュメントの識別子（ID）です。
name は、人（person）の名前で、friend_list は、その人の友達の名前を格納するリストです。
main 関数
次に、MongoCloudConnector クラスに戻って、main 関数を見てみましょう。
main 関数では、「chieya」、「yukie」、「maya」、「sora」と言う、4つの Person クラスのオブジェクトを作って、それぞれに、name と friend_list を設定しています。
続いて、atlasConnector.person_coll.insertMany(persons); の部分で、これらの Person オブジェクトを、MongoDB Atlas クラスタの「rightcode」データベースの、「person」コレクションのドキュメントとして保存しています。
友達情報を追加
では早速、MongoCloudConnector の main 関数を実行してみましょう！
エラーがなければ、以下のような結果がコンソールに出力されます。
| ...
Connected to : rightcode:rightcode.person ... Chieya|[Maya, Sora, Yukie, Kenji] Process finished with exit code 0 |
MongoDB Atlas で「rightcode」データベースを見る
MongoDB Atlas で「rightcode」データベースを見ると、以下のようなデータ（ドキュメント）が格納されているのが確認できます。
※クリックすると別ウィンドウで画像が開きます
MongoDB Atlas クラスタ上のデータベースへの接続とドキュメントの作成に成功しました！
以上で、「person」コレクションのデータの準備は完了です。
共通の友達を求める「MapReduce アルゴリズム」を実装
いよいよ、MapReduce プログラミングモデルを使って、「person」コレクションに登録されている人の、共通の友達を求めて行きましょう！
「MapReduce」の成り立ち
「MapReduce」は、基本的に「Map フェーズ」と「Reduce フェーズ」から成り立ちます。
各フェーズに対応する、Mapper クラスと Reducer クラスを実装していきます。
この2つのクラスを、src/main/java/mongodb/ で作成しましょう。
「Map フェーズ」の実装
Mapper クラス
Map フェーズの Mapper クラスは以下のようなコードになります。
1package mapreduce;
2
3/*
4Mapper.java
5 */
6
7import mongodb.Person;
8
9import java.util.*;
10
11public class Mapper {
12 public List<MapOut> mapOuts;
13
14 public Mapper (){
15 mapOuts = new ArrayList<>();
16 }
17
18 public void map (List<Person> persons){
19
20 for (Person person:persons){
21 String name = person.getName();
22 List<String>friends = person.getFriend_list();
23 System.out.println("=========================\nMapper.intermediateResult(key, value)\n=========================");
24 for (int i = 0; i < friends.size(); i++){
25 List<String> key = new ArrayList();
26 key.add(name);
27 key.add(friends.get(i));
28 Collections.sort(key);
29 emitIntermediate(key, friends);
30 }
31 }
32 }
33
34 private void emitIntermediate(List<String> key, List<String> friends){
35 System.out.println(key.toString() + ":" + friends.toString());
36 mapOuts.add(new MapOut(key, friends));
37 }
38}Mapper クラスの map 関数の引数は、Person オブジェクトのリストとなります。
つまり、Mapper への入力は、MongoDB Atlas クラスタにおける「rightcode」データベースの「person」コレクションです。
ここで、「person」コレクションには、先ほど保存した4つの「person」ドキュメントが格納されています。
各ドキュメントは、人（person）の名前と友達リストから成り立っています。
| Chieya:[Maya, Sora, Yukie, Kenji] Yukie : [Chieya, Sora, Zara, Rafa] Maya : [Chieya, Zara, Rafa] Sora : [Chieya, Yukie, Ichiro, John] |
これらのドキュメントを、map関数に入力して処理しています。
MapOut クラス
処理結果は、以下のような MapOut クラスのような構造になります。
1package mapreduce;
2
3/*
4MapOut.java
5 */
6import java.util.List;
7
8public class MapOut {
9 List<String> key;
10 List<String> value;
11
12 public MapOut (List<String> key, List<String> value){
13 this.key = key;
14 this.value = value;
15 }
16}具体的に示すと、Mapper の出力は以下のよう「key:value」のペアになります。
| ========================= Mapper.intermediateResult(key, value) ========================= [Chieya, Maya]:[Maya, Sora, Yukie, Kenji] [Chieya, Sora]:[Maya, Sora, Yukie, Kenji] [Chieya, Yukie]:[Maya, Sora, Yukie, Kenji] [Chieya, Kenji]:[Maya, Sora, Yukie, Kenji]========================= Mapper.intermediateResult(key, value) ========================= [Chieya, Yukie]:[Chieya, Sora, Zara, Rafa] [Sora, Yukie]:[Chieya, Sora, Zara, Rafa] [Yukie, Zara]:[Chieya, Sora, Zara, Rafa] [Rafa, Yukie]:[Chieya, Sora, Zara, Rafa]... |
「Reduce フェーズ」の実装
Map フェーズで出力されたデータは、「Reduce フェーズ」の Reducer クラスで処理されます。
Reducer クラスの reduce 関数の引数は、「key:values」となっているので、Mapper の出力（key:valueのペア）を「key:values」のペアにグルーピングする必要があります。
このグルーピングを ReduceIn クラスのgroup 関数で行い、「MapOut」のデータ構造を「ReduceIn」のデータ構造に変換します。
ReduceIn クラス
ReduceIn クラスは、以下のようなコードになります。
1package mapreduce;
2
3/*
4ReduceIn.java
5 */
6import java.util.ArrayList;
7import java.util.List;
8
9public class ReduceIn {
10 public List<String> key;
11 public List<List<String>> values;
12
13 public ReduceIn (){
14 key = new ArrayList<>();
15 values = new ArrayList<>();
16 }
17
18 public List<ReduceIn> group (List<MapOut> mapOuts){
19 List<ReduceIn> reduceIns = new ArrayList<>();
20
21 for (MapOut mapOut:mapOuts){
22 boolean newKey = true;
23 for (ReduceIn reduceIn:reduceIns){
24 if(reduceIn.key.equals(mapOut.key)){
25 newKey = false;
26 reduceIn.values.add(mapOut.value);
27 break;
28 }
29 }
30 if (newKey){
31 ReduceIn reduceIn = new ReduceIn();
32 reduceIn.key = mapOut.key;
33 reduceIn.values.add(mapOut.value);
34 reduceIns.add(reduceIn);
35 }
36 }
37 return reduceIns;
38 }
39}これを実行すると、次のような結果が得られます。
| ========================= Reduce Input: (key, values) ========================= [Chieya, Maya]:[[Maya, Sora, Yukie, Kenji], [Chieya, Zara, Rafa]] [Chieya, Sora]:[[Maya, Sora, Yukie, Kenji], [Chieya, Yukie, Ichiro, John]] [Chieya, Yukie]:[[Maya, Sora, Yukie, Kenji], [Chieya, Sora, Zara, Rafa]] [Chieya, Kenji]:[[Maya, Sora, Yukie, Kenji]] [Sora, Yukie]:[[Chieya, Sora, Zara, Rafa], [Chieya, Yukie, Ichiro, John]] [Yukie, Zara]:[[Chieya, Sora, Zara, Rafa]] [Rafa, Yukie]:[[Chieya, Sora, Zara, Rafa]] [Maya, Zara]:[[Chieya, Zara, Rafa]] [Maya, Rafa]:[[Chieya, Zara, Rafa]] [Ichiro, Sora]:[[Chieya, Yukie, Ichiro, John]] [John, Sora]:[[Chieya, Yukie, Ichiro, John]] |
このデータを使って、次に解説する Reducer クラスで共通の友達を取得します。
Reducer クラス
ここまでの処理で生成されたデータを使って、共通の友達を取得します。
以下のような、Reducer クラスを作成してください。
1package mapreduce;
2
3/*
4Reducer.java
5 */
6
7import java.util.*;
8import java.util.stream.Collectors;
9
10public class Reducer {
11 public List<Result> results;
12
13 public Reducer (){
14 results = new ArrayList<>();
15 }
16
17 public void reduce (List<ReduceIn> reduceIns){
18 for (ReduceIn reduceIn:reduceIns){
19 if (reduceIn.values.size() > 1){
20 Set<String> finalValue = new HashSet<>();
21 List<String> list1 = reduceIn.values.get(0);
22 for (int i = 1; i < reduceIn.values.size(); i++){
23 finalValue = intersect(list1, reduceIn.values.get(i));
24 }
25 if (!finalValue.isEmpty()){
26 results.add(new Result(reduceIn.key, finalValue));
27 }
28 }
29 }
30 }
31
32 private Set<String> intersect (List<String> list1, List<String> list2){
33 Set<String> commonItems = list1.stream()
34 .distinct()
35 .filter(list2::contains)
36 .collect(Collectors.toSet());
37 return commonItems;
38 }
39}ここで、Reducer クラスの reduce 関数の引数は、 ReduceIn オブジェクトのリストとなっています。
Result クラス
Reducer の出力データの構造は、以下の Result クラスのようになります。
1package mapreduce;
2
3/*
4Result.java
5 */
6import java.util.List;
7import java.util.Set;
8
9public class Result {
10 public List<String> key;
11 public Set<String> value;
12
13 public Result (List<String> key, Set<String> value){
14 this.key = key;
15 this.value = value;
16 }
17}共通の友達を取得する！
ここまでに作成したコードを使って、いよいよ、今回の目標である共通の友達を取得したいと思います。
MapReduce クラスを作成
以下のような MapReduce クラスを作成してください。
1package mapreduce;
2/*
3MapReduce.java
4 */
5
6import mongodb.MongoCloudConnector;
7import mongodb.Person;
8
9import java.util.ArrayList;
10import java.util.List;
11
12public class MapReduce {
13 private final MongoCloudConnector atlasConnector;
14 private final List<Person> persons;
15
16 public MapReduce(){
17 persons = new ArrayList<>();
18 atlasConnector = new MongoCloudConnector();
19 for (Person person:atlasConnector.person_coll.find()){
20 persons.add(person);
21 }
22 }
23
24 public static void main(String[] args) {
25 MapReduce mr = new MapReduce();
26
27 Mapper mapper = new Mapper();
28 mapper.map(mr.persons);
29
30 List<ReduceIn> reduceIns = new ReduceIn().group(mapper.mapOuts);
31 System.out.println("=========================\nReduce Input: (key, values)\n=========================");
32 reduceIns.forEach(reduceIn -> {
33 System.out.println(reduceIn.key.toString() + ":" + reduceIn.values.toString());
34 });
35
36 System.out.println("=========================\nReduce Result: (key, values)\n=========================");
37 Reducer reducer = new Reducer();
38 reducer.reduce(reduceIns);
39 for (Result result:reducer.results){
40 System.out.println(
41 "Mutual friends of " + result.key.get(0) +
42 " and " + result.key.get(1) +
43 " is " + result.value.toString()
44 );
45 }
46 }
47}結果
これを実行すると、以下のような結果が得られます。
| ========================= Reduce Result: (key, values) ========================= Mutual friends of Chieya and Sora is [Yukie] Mutual friends of Chieya and Yukie is [Sora] Mutual friends of Sora and Yukie is [Chieya] |
「Chieya」と「Sora」との共通の友達は「Yukie」で、「Chieya」と「Yukie」との共通の友達は「Sora」で、「Sora」と「Yukie」との共通の友達は「Chieya」というような結果が得られました。
さいごに
以上で、MapReduce プログラミングモデルを用いて共通の友達を求めるプログラムは完成です！
2回に渡り、MapReduceプログラミングモデルをご紹介してきました。
前回と今回の記事を参考に、是非試していただければと思います！
こちらの記事もオススメ！
ライトコードでは、エンジニアを積極採用中！
ライトコードでは、エンジニアを積極採用しています！社長と一杯しながらお話しする機会もご用意しております。そのほかカジュアル面談等もございますので、くわしくは採用情報をご確認ください。
採用情報へ
「好きを仕事にするエンジニア集団」の（株）ライトコードです！ ライトコードは、福岡、東京、大阪、名古屋の４拠点で事業展開するIT企業です。 現在は、国内を代表する大手IT企業を取引先にもち、ITシステムの受託事業が中心。 いずれも直取引で、月間PV数1億を超えるWebサービスのシステム開発・運営、インフラの構築・運用に携わっています。 システム開発依頼・お見積もり大歓迎！ また、現在「WEBエンジニア」「モバイルエンジニア」「営業」「WEBデザイナー」を積極採用中です！ インターンや新卒採用も行っております。 以下よりご応募をお待ちしております！ https://rightcode.co.jp/recruit
