1. HOME
  2. ブログ
  3. IT技術
  4. MapReduceプログラミングモデルとMongoDBを用いて Facebookのような共通の友達(Mutual Friends)を見つける!

MapReduceプログラミングモデルとMongoDBを用いて Facebookのような共通の友達(Mutual Friends)を見つける!

MapReduceプログラミングモデルとMongoDBで共通の友達を見つける!

前回の記事では、実現的な例を用いて MapReduce プログラミングモデルの概念を解説しました。

今回は、MapReduce プログラミングモデルを用いて、Facebook のようなソーシャルネットワークにおける、共通の友達を見つけてみたいと思います!

共通の友達を見つける機能とは?

Facebook では、他のユーザのプロフィルを見ると、自分とそのユーザとの共通の友達が表示されます。

Facebook を利用したことがあれば、見たことがある人も多いのではないでしょうか?

今回は、そのような共通の友達を求める方法を、MapReduce プログラミングモデルを適用した Steve Krenzel のアルゴリズムを Java で実装することで実現したいと思います!

【参考サイト】
http://stevekrenzel.com/articles/finding-friends

前回の記事はこちら

実装環境

今回の執筆者の環境は、以下の通りです。

  1. IDE : IntelliJ IDEA
  2. JDK : Oracle Java 8
  3. 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 ファイルは、以下のようになります。

「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 クラスを追加してください。

MongoCloudConnector クラスのコンストラクタによって、MongoDB Atlas のクラスタ上に、「rightcode」という新規のデータベースと、「person」という新しいコレクションが作成されます。

ここで、「person」コレクションのデータ構造は、後述の「Person」クラスに反映されます

「Person」クラス

src/main/java/mongodb/ ディレクトリに「Person.java」ファイルを作成し、 Person クラスのデータ構造を次のコードのように定義します。

ここで Person クラスは、 ObjectIdnamefriend_list と言う3つのメンバーから成り立っています。

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」コレクションのドキュメントとして保存しています。

友達情報を追加

では早速、 MongoCloudConnectormain 関数を実行してみましょう!

エラーがなければ、以下のような結果がコンソールに出力されます。

Connected to : rightcode:rightcode.person

Chieya|[Maya, Sora, Yukie, Kenji]
Yukie|[Chieya, Sora, Zara, Rafa]
Maya|[Chieya, Zara, Rafa]
Sora|[Chieya, Yukie, Ichiro, John]

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 クラスは以下のようなコードになります。

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 クラスのような構造になります。

具体的に示すと、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 クラスは、以下のようなコードになります。

これを実行すると、次のような結果が得られます。

=========================
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 クラスを作成してください。

ここで、 Reducer クラスの reduce 関数の引数は、  ReduceIn オブジェクトのリストとなっています。

Result クラス

Reducer の出力データの構造は、以下の Result クラスのようになります。

共通の友達を取得する!

ここまでに作成したコードを使って、いよいよ、今回の目標である共通の友達を取得したいと思います。

MapReduce クラスを作成

以下のような MapReduce クラスを作成してください。

結果

これを実行すると、以下のような結果が得られます。

=========================
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プログラミングモデルをご紹介してきました。

前回と今回の記事を参考に、是非試していただければと思います!

関連記事

ライトコードよりお知らせ

にゃんこ師匠にゃんこ師匠
システム開発のご相談やご依頼はこちら
ミツオカミツオカ
ライトコードの採用募集はこちら
にゃんこ師匠にゃんこ師匠
社長と一杯飲みながらお話してみたい方はこちら
ミツオカミツオカ
フリーランスエンジニア様の募集はこちら
にゃんこ師匠にゃんこ師匠
その他、お問い合わせはこちら
ミツオカミツオカ
   
お気軽にお問い合わせください!せっかくなので、別の記事もぜひ読んでいって下さいね!

一緒に働いてくれる仲間を募集しております!

ライトコードでは、仲間を募集しております!

当社のモットーは「好きなことを仕事にするエンジニア集団」「エンジニアによるエンジニアのための会社」。エンジニアであるあなたの「やってみたいこと」を全力で応援する会社です。

また、ライトコードは現在、急成長中!だからこそ、あなたにお任せしたいやりがいのあるお仕事は沢山あります。「コアメンバー」として活躍してくれる、あなたからのご応募をお待ちしております!

なお、ご応募の前に、「話しだけ聞いてみたい」「社内の雰囲気を知りたい」という方はこちらをご覧ください。

ライトコードでは一緒に働いていただける方を募集しております!

採用情報はこちら

関連記事