【Java】MapReduceプログラミングモデルとMongoDBを用いて Facebookのような共通の友達（Mutual Friends)を見つける！
2021.12.20
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | <?xml version="1.0" encoding="UTF-8"?> <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"> <modelVersion>4.0.0</modelVersion> <groupId>org.example</groupId> <artifactId>mapreduce-mutualfriend</artifactId> <version>1.0-SNAPSHOT</version> <dependencies> <!-- https://mvnrepository.com/artifact/org.mongodb/mongo-java-driver --> <dependency> <groupId>org.mongodb</groupId> <artifactId>mongo-java-driver</artifactId> <version>3.12.1</version> </dependency> </dependencies> </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 クラスを追加してください。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | package mongodb; import com.mongodb.ConnectionString; import com.mongodb.MongoClientSettings; import com.mongodb.MongoClientURI; import com.mongodb.client.MongoClient; import com.mongodb.client.MongoClients; import com.mongodb.client.MongoCollection; import com.mongodb.client.MongoDatabase; import org.bson.codecs.configuration.CodecRegistry; import org.bson.codecs.pojo.PojoCodecProvider; import java.util.Arrays; import java.util.List; import static org.bson.codecs.configuration.CodecRegistries.fromProviders; import static org.bson.codecs.configuration.CodecRegistries.fromRegistries; public class MongoCloudConnector { MongoClientURI atlasUri = new MongoClientURI("mongodb+srv://uichaya:accha1330@cluster0-s9bfc.mongodb.net/rightcode?retryWrites=true&w=majority"); public MongoDatabase db; public MongoCollection<Person> person_coll; public MongoCloudConnector() { ConnectionString connectionString = new ConnectionString(atlasUri.toString()); CodecRegistry pojoCodecRegistry = fromProviders(PojoCodecProvider.builder().automatic(true).build()); CodecRegistry codecRegistry = fromRegistries(MongoClientSettings.getDefaultCodecRegistry(), pojoCodecRegistry); MongoClientSettings clientSettings = MongoClientSettings.builder() .applyConnectionString(connectionString) .codecRegistry(codecRegistry) .build(); MongoClient mongoClient = MongoClients.create(clientSettings); db = mongoClient.getDatabase("rightcode"); person_coll = db.getCollection("person", Person.class); System.out.println("Connected to : " + db.getName() + ":" + person_coll.getNamespace()); } public static void main(String[] args) { MongoCloudConnector atlasConnector = new MongoCloudConnector(); Person chieya = new Person("Chieya"); chieya.setFriend_list(Arrays.asList(new String[]{"Maya", "Sora", "Yukie", "Kenji"})); Person yukie = new Person("Yukie"); yukie.setFriend_list(Arrays.asList(new String[]{"Chieya", "Sora", "Zara", "Rafa"})); Person maya = new Person("Maya"); maya.setFriend_list(Arrays.asList(new String[]{"Chieya", "Zara", "Rafa"})); Person sora = new Person("Sora"); sora.setFriend_list(Arrays.asList(new String[]{"Chieya", "Yukie", "Ichiro", "John"})); List<Person> persons = Arrays.asList(new Person[]{chieya, yukie, maya, sora}); //atlasConnector.person_coll.insertOne(michie); atlasConnector.person_coll.insertMany(persons); for (Person p : atlasConnector.person_coll.find()) { System.out.println(p); } } } |
MongoCloudConnector クラスのコンストラクタによって、MongoDB Atlas のクラスタ上に、「rightcode」という新規のデータベースと、「person」という新しいコレクションが作成されます。
ここで、「person」コレクションのデータ構造は、後述の「Person」クラスに反映されます。
「Person」クラス
src/main/java/mongodb/ ディレクトリに「Person.java」ファイルを作成し、 Person クラスのデータ構造を次のコードのように定義します。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | package mongodb; import org.bson.types.ObjectId; import java.util.List; public final class Person { private ObjectId id; private String name; private List<String> friend_list; public Person() { id = new ObjectId(); } public Person(String name){ id = new ObjectId(); this.name = name; } public ObjectId getId() { return id; } public void setId(final ObjectId id) { this.id = id; } public String getName() { return name; } public void setName(final String name) { this.name = name; } public List<String> getFriend_list(){ return friend_list; } public void setFriend_list(List<String> friend_list){ this.friend_list = friend_list; } public String toString(){ return name + "|" + friend_list.toString(); } } |
ここで 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 クラスは以下のようなコードになります。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | package mapreduce; /* Mapper.java */ import mongodb.Person; import java.util.*; public class Mapper { public List<MapOut> mapOuts; public Mapper (){ mapOuts = new ArrayList<>(); } public void map (List<Person> persons){ for (Person person:persons){ String name = person.getName(); List<String>friends = person.getFriend_list(); System.out.println("=========================\nMapper.intermediateResult(key, value)\n========================="); for (int i = 0; i < friends.size(); i++){ List<String> key = new ArrayList(); key.add(name); key.add(friends.get(i)); Collections.sort(key); emitIntermediate(key, friends); } } } private void emitIntermediate(List<String> key, List<String> friends){ System.out.println(key.toString() + ":" + friends.toString()); mapOuts.add(new MapOut(key, friends)); } } |
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 クラスのような構造になります。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | package mapreduce; /* MapOut.java */ import java.util.List; public class MapOut { List<String> key; List<String> value; public MapOut (List<String> key, List<String> value){ this.key = key; this.value = value; } } |
具体的に示すと、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 クラスは、以下のようなコードになります。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | package mapreduce; /* ReduceIn.java */ import java.util.ArrayList; import java.util.List; public class ReduceIn { public List<String> key; public List<List<String>> values; public ReduceIn (){ key = new ArrayList<>(); values = new ArrayList<>(); } public List<ReduceIn> group (List<MapOut> mapOuts){ List<ReduceIn> reduceIns = new ArrayList<>(); for (MapOut mapOut:mapOuts){ boolean newKey = true; for (ReduceIn reduceIn:reduceIns){ if(reduceIn.key.equals(mapOut.key)){ newKey = false; reduceIn.values.add(mapOut.value); break; } } if (newKey){ ReduceIn reduceIn = new ReduceIn(); reduceIn.key = mapOut.key; reduceIn.values.add(mapOut.value); reduceIns.add(reduceIn); } } return reduceIns; } } |
これを実行すると、次のような結果が得られます。
| ========================= 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 クラスを作成してください。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | package mapreduce; /* Reducer.java */ import java.util.*; import java.util.stream.Collectors; public class Reducer { public List<Result> results; public Reducer (){ results = new ArrayList<>(); } public void reduce (List<ReduceIn> reduceIns){ for (ReduceIn reduceIn:reduceIns){ if (reduceIn.values.size() > 1){ Set<String> finalValue = new HashSet<>(); List<String> list1 = reduceIn.values.get(0); for (int i = 1; i < reduceIn.values.size(); i++){ finalValue = intersect(list1, reduceIn.values.get(i)); } if (!finalValue.isEmpty()){ results.add(new Result(reduceIn.key, finalValue)); } } } } private Set<String> intersect (List<String> list1, List<String> list2){ Set<String> commonItems = list1.stream() .distinct() .filter(list2::contains) .collect(Collectors.toSet()); return commonItems; } } |
ここで、 Reducer クラスの reduce 関数の引数は、 ReduceIn オブジェクトのリストとなっています。
Result クラス
Reducer の出力データの構造は、以下の Result クラスのようになります。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | package mapreduce; /* Result.java */ import java.util.List; import java.util.Set; public class Result { public List<String> key; public Set<String> value; public Result (List<String> key, Set<String> value){ this.key = key; this.value = value; } } |
共通の友達を取得する！
ここまでに作成したコードを使って、いよいよ、今回の目標である共通の友達を取得したいと思います。
MapReduce クラスを作成
以下のような MapReduce クラスを作成してください。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | package mapreduce; /* MapReduce.java */ import mongodb.MongoCloudConnector; import mongodb.Person; import java.util.ArrayList; import java.util.List; public class MapReduce { private final MongoCloudConnector atlasConnector; private final List<Person> persons; public MapReduce(){ persons = new ArrayList<>(); atlasConnector = new MongoCloudConnector(); for (Person person:atlasConnector.person_coll.find()){ persons.add(person); } } public static void main(String[] args) { MapReduce mr = new MapReduce(); Mapper mapper = new Mapper(); mapper.map(mr.persons); List<ReduceIn> reduceIns = new ReduceIn().group(mapper.mapOuts); System.out.println("=========================\nReduce Input: (key, values)\n========================="); reduceIns.forEach(reduceIn -> { System.out.println(reduceIn.key.toString() + ":" + reduceIn.values.toString()); }); System.out.println("=========================\nReduce Result: (key, values)\n========================="); Reducer reducer = new Reducer(); reducer.reduce(reduceIns); for (Result result:reducer.results){ System.out.println( "Mutual friends of " + result.key.get(0) + " and " + result.key.get(1) + " is " + result.value.toString() ); } } } |
結果
これを実行すると、以下のような結果が得られます。
| ========================= 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プログラミングモデルをご紹介してきました。
前回と今回の記事を参考に、是非試していただければと思います！
こちらの記事もオススメ！
書いた人はこんな人
- 「好きを仕事にするエンジニア集団」の（株）ライトコードです！
ライトコードは、福岡、東京、大阪の3拠点で事業展開するIT企業です。
現在は、国内を代表する大手IT企業を取引先にもち、ITシステムの受託事業が中心。
いずれも直取引で、月間PV数1億を超えるWebサービスのシステム開発・運営、インフラの構築・運用に携わっています。
システム開発依頼・お見積もり大歓迎！
また、現在「WEBエンジニア」「モバイルエンジニア」「営業」「WEBデザイナー」「WEBディレクター」を積極採用中です！
インターンや新卒採用も行っております。
以下よりご応募をお待ちしております！
https://rightcode.co.jp/recruit
ITエンタメ10月 13, 2023Netflixの成功はレコメンドエンジン？- ライトコードの日常8月 30, 2023退職者の最終出社日に密着してみた！
- ITエンタメ8月 3, 2023世界初の量産型ポータブルコンピュータを開発したのに倒産!?アダム・オズボーン
- ITエンタメ7月 14, 2023【クリス・ワンストラス】GitHubが出来るまでとソフトウェアの未来
関連記事
採用情報
\ あの有名サービスに参画!? /
バックエンドエンジニア
\ クリエイティブの最前線 /
フロントエンドエンジニア
\ 世界を変える…！ /
Androidエンジニア
\ みんなが使うアプリを創る /
iOSエンジニア
