この記事はの CakePHP3 Advent Calendar 2016 の13日目として投稿したものです。

CakePHP3 には以前の CakePHP には存在しなかった MapReduce という仕組みがあります。本記事を読む前に、まずは下のリンクから公式ドキュメントの当該の節を読んでみてください。

~~http://book.cakephp.org/3.0/ja/orm/retrieving-data-and-resultsets.html#map-reduce~~
https://github.com/cakephp/docs/blob/a528eeb6a80c038db05f434466475756b2bb311c/ja/orm/retrieving-data-and-resultsets.rst#結果を-mapreduce-で変更する ¹

簡単にまとめると以下のような仕組みのようです。

Mapper は、データを仕分けして Reducer に渡すデータを作る
Reducer は Mapper が仕分けしたデータから最終的なデータを作る
MapReduce はこれらの橋渡しをして最終的なデータを返す

ところで、 Cookbook にあった三つの例の中の最後の一つ、嘘の友人を検索する例がいったい何をやっているのか、皆さん理解できましたか？

おそらく、あまりよく理解できなかった、という方が大半なのではないでしょうか。私自身、初めて読んだ時にはずいぶんと頭を捻ったものです。

どうして、これでフォローを返していない相手を検出できるのかよくわからないけれど、でも、これはエキスパート向けだから今はわからなくてもいいか。

そんなふうに考えていた時期が私にもありました。しかし、今にして思えば理解できなくて当然だったのです。なぜなら、誠に遺憾ながら、この嘘の友人の例は思いっきり間違っているのですから――。

この記事では、 Cookbook の例の誤りについて検証しながら、ついでに MapReduce のふるまいについて理解を深めてしまおう、というのが目当てです。

friends テーブルの構造

では、まずは嘘の友人の例にある friends テーブルの構造について考えてみましょう。

これは、どのユーザーがどのユーザーをフォローしているかを表現するテーブルで、余計なカラムをすべて取り除けば、おそらく次のようなテーブル構造になるでしょう。

source_user_id ―― フォローする側のユーザーID
target_user_id ―― フォローされる側のユーザーID

これで belongsToMany としてユーザー同士を関連付けることができるはずです。友人関係のモデルは belongsToMany ですね。例えば、私の友人になったからといって、もう他の誰かの友人になれなくなってしまうわけではありません。

対照的に、婚姻関係は互いに hasOne/belongsTo ですね。誰かの夫や妻になった場合、その関係が解消されない限り、他の誰かの夫や妻になることはできなくなります。

ところで、私の人生のモデルには hasOne/belongsTo Wife のアソシエーションが張られていないみたいなんですがバグでしょうか。

まァ、それはさておき、 friends の例を見ると、しかし、どういうわけかテーブルにはもう一つカラムがあるようです。例の中にある $mapper を見てください。

$mapper = function ($rel, $key, $mr) {
    $mr->emitIntermediate($rel['source_user_id'], $rel['target_user_id']);
    $mr->emitIntermediate($rel['target_user_id'], $rel['source_target_id']);
};

source_target_id というカラムが使われているのがわかると思います。このカラムは何でしょうね。

実は、これが私が誤りではないかと思っている部分なのです。本当はこうなのではないかと思うわけです。

$mapper = function ($rel, $key, $mr) {
    $mr->emitIntermediate($rel['source_user_id'], $rel['target_user_id']);
    $mr->emitIntermediate($rel['target_user_id'], $rel['source_user_id']); // source_user_id の誤り
};

source_user_id の誤りで、ここでは単にフォローする側とされる側を入れ替えているのではないでしょうか。つまり、 source_target_id などというカラムは friends テーブルには存在しないのです。

その後に続く文も見てください。日本語訳は

互いにフォローしあっているユーザリストを得るためにデータをコピーしていきました。

となっており、原文は

We just duplicated our data to have a list of users each other user follows.

となっていますが、この部分を訳すのは難しかったのではないかと思います。もしも、私の考えの通りであれば、直前の例が間違っているのですから正しく訳せるはずがありません。

私は原文はこういうことを言いたかったのではないかと思っています。

互いにフォローしあっているユーザーリストを得るためにデータをただ重複させました。

要するに直前の例の説明です。フォローする側とされる側を入れ替えただけの、重複したデータを emitIntermediate() に渡しました、と言っているのでしょう。

emitIntermediate() のふるまい

ちょっと待ってほしい、という声が聞こえてきそうです（幻聴）。本当にそんなことをするだけで嘘の友人――相互フォローしていないユーザーを得ることができるのでしょうか。

にわかには信じられませんね。これはいったいどういったアルゴリズムなのでしょうか？

順番に処理を追っていきましょう。まずはカラム名の誤りを修正した後の $mapper の例です。

$mapper = function ($rel, $key, $mr) {
    $mr->emitIntermediate($rel['source_user_id'], $rel['target_user_id']);
    $mr->emitIntermediate($rel['target_user_id'], $rel['source_user_id']);
};

ここで、仮に 1 が 2 をフォローしているとすれば、 source_user_id は 1 になり、 target_user_id は 2 になります。 emitIntermediate() はデータを仕分けするために、第二引数をキーにして入れ子の配列を内部的に作りますので、 2 をキーにした配列に 1 が入るはずです。

[
    2 => [ 1 ],
]

でも、 $mapper の処理はこれだけではありませんね。その次の行の、フォローする側とされる側を入れ替えてデータを重複させる処理を行う必要があります。そうすると今度は 1 をキーにした配列に 2 が入ることになります。

[
    2 => [ 1 ],
    1 => [ 2 ],
]

おさらいのために、 1 が 3 もフォローしている場合についても考えてみましょう。同様に 3 のキーにした配列 1 が入ります。

[
    2 => [ 1 ],
    1 => [ 2 ],
    3 => [ 1 ],
]

そして、データを入れ替えて重複させます。 1 をキーにした配列に 3 が入りました。

[
    2 => [ 1 ],
    1 => [ 2, 3 ],
    3 => [ 1 ],
]

もう一度おさらいです。 1 が 4 もフォローしていれば、次のようになりますね。

[
    2 => [ 1 ],
    1 => [ 2, 3 ],
    3 => [ 1 ],
    4 => [ 1 ],
]

そして、データを入れ替えて重複させます。

[
    2 => [ 1 ],
    1 => [ 2, 3, 4 ],
    3 => [ 1 ],
    4 => [ 1 ],
]

こうなりました。

さて、 Cookbook の中では最終的には 2 と 4 が 1 にフォローを返してくれていない結果になっています。この結果に矛盾しないように 3 についてはフォローを返してくれたことにしましょう。 1 のキーに 3 を入れ、 3 のキーに 1 を入れます。

[
    2 => [ 1 ],
    1 => [ 2, 3, 4, 3 ],
    3 => [ 1, 1 ],
    4 => [ 1 ],
]

この時点で初めて相互フォローが成立したことになります。 emitIntermediate() が作った配列中のデータに何か変化はあったのでしょうか。

注目すべきは、相互フォローが成立した 1 や 3 に、まだ成立していない 2 や 4 と比べて何かしらの特徴が生まれているか、ということです。

勘のよい方はお気付きかもしれませんね。実は Cookbook の例のコメント中にその答えが書いてあります。

繰り返し登場する数字は双方向で関係が繋がっていることを意味しています

つまり、そういうことです。 1 のキーから横に見た場合、 3 が繰り返し登場しているので、 1 と 3 とは相互フォローになっているということですね。

続いて $reducer の例も見直してみましょう。

$reducer = function ($friendsList, $user, $mr) {
    $friends = array_count_values($friendsList);
    foreach ($friends as $friend => $count) {
        if ($count < 2) {
            $mr->emit($friend, $user);
        }
    }
}

実装では array_count_values() を用いて、この $mapper が作った配列の各値について登場回数を得ています。例えば $reducer が $user 1 の $friendsList [ 2, 3, 4, 3 ] を受け取った時、 array_count_values() によって次のような配列 $friends が作られます。

[
    2 => 1,
    3 => 2,
    4 => 1,
]

これを $count < 2 にかけて emit() すれば、 Cookbook にあるような 1 のキーに [ 2, 4 ] の入った配列ができる、という寸法です。

[
    2 => 1,
    1 => 4,
    4 => 1,
]

いや、そんな配列はできませんでした。なぜでしょうか？

emit() のふるまい

実は、誠に遺憾ながら、 Cookbook の例にはカラム名の他にもまだ誤りがあって、 emit() の使い方を間違えているのです。

emit() は emitIntermediate() とは異なり、同じキーで二度呼んだからといって、配列に値をプッシュしていくわけではありません。前の値を上書きます。つまり、 1 のキーで 2 と 4 をそれぞれ emit() した都合、後に呼ばれた 4 だけがスカラーとして残ったわけですね。

正しい emit() の使い方は次のようになるでしょう。

$reducer = function ($friendsList, $user, $mr) {
    $fakeFriends = []; // 配列を用意する

    $friends = array_count_values($friendsList);
    foreach ($friends as $friend => $count) {
        if ($count < 2) {
            // $mr->emit($friend, $user); // これは間違い
            $fakeFriends[] = $friend; // 配列に ID をプッシュする
        }
    }

    if ($fakeFriends) {
        $mr->emit($fakeFriends, $user); // 最後にその配列を emit() する
    }
}

これでよさそうですね。結果は次のようになります。

[
    2 => [ 1 ],
    1 => [ 2, 4 ],
    4 => [ 1 ],
]

この配列の意味するところは Cookbook の例の最後に書いてある通りです。

結果の配列は、たとえば、 id 1 のユーザは 2 と 4 をフォローしていますが、彼らは 1 をフォローし返していないということを意味します。

なるほど、こういうアルゴリズムがあるんですね。これは総当たり表を思い浮かべてみるとイメージを摑みやすいかもしれません。

＼	1	2	3	4
1	＼	1	2	1
2	1	＼
3	2		＼
4	1			＼

フォローする側とされる側の枠にそれぞれ 1 を加算していくと、互いにフォローをしている場合には枠内に 2 が入ることになります。こう考えれば $count < 2 をしている理由もすんなりと頭に入ってくるでしょう。

勉強になりますね。

嘘の友人検索アルゴリズムの嘘

いや、ちょっと待ってください。何かが変です。

確かに 1 から見た場合には結果はそうなっているようですが、では 2 や 4 から見た場合にはどうなんでしょう。先ほどの結果配列をもう一度見てみます。

[
    2 => [ 1 ],
    1 => [ 2, 4 ],
    4 => [ 1 ],
]

例えば 2 のキーの配列には繰り返し登場しなかった 1 が入っています。これは、同じように 2 は 1 をフォローしているものの、 1 は 2 をフォローし返していないということを意味するのでしょうか？

明らかに違いますね。 1 は 2 をちゃんとフォローしています。むしろ、フォローを返していないのは 2 の方なのです。被害妄想もいいところです。

つまり、この結果が意味するところは、もっとずっと曖昧で、例えば 1 は 2 や 4 とは一方がフォローする関係ではあるものの相互フォローは成立していない、ということに過ぎません。

そうすると、誠に遺憾ながら、嘘の友人の例はプログラムだけではなく、アルゴリズムまでもが間違っているのでした。最初から、にわかには信じられなかったアルゴリズムでしたが、最後まで信じなかった方、正解です。

こうなってしまった原因は $mapper の中でフォローする側とされる側を単純に入れ替えて emitIntermediate() した都合、どちらがフォローしている側でどちらがフォローされている側だったのか、わからなくなってしまったことにありそうです。

せっかくですから、問題の箇所を修正してみましょう。

$mapper = function ($rel, $key, $mr) {
    $mr->emitIntermediate(-$rel['source_user_id'], $rel['target_user_id']);
    $mr->emitIntermediate($rel['target_user_id'], $rel['source_user_id']);
};

フォローされる側を明確にするために、片方のIDにマイナスをつけてみました。 1 が 2 をフォローしていれば、最初の $mapper の呼び出しでこうなるはずです。

[
    2 => [ -1 ],
    1 => [ 2 ],
]

これで 2 が 1 によってフォローされており、 1 が 2 をフォローしていることが明確になりました。

この調子で $reducer の処理も修正してしまいましょう。片方が負の数になった都合、 $reducer が受け取る配列中に同じ数字が繰り返し登場することはもはやありませんね。

array_count_values() の呼び出しや $count < 2 の部分を変更して、正の値（フォローしている）に対応する負の値（フォローされている）を探すようにします。負の値が見つかれば、相互フォローが成立しているわけです。

$reducer = function ($data, $user, $mr) {
    $fakeFriends = [];

    foreach ($data as $friend) {
        // 正の値に対応する負の値がない場合 $user は $friend からフォローされていない
        if ($friend > 0 && !in_array(-$friend, $data)) {
            $fakeFriends[] = $friend;
        }
    }

    if ($fakeFriends) {
        $mr->emit($fakeFriends, $user);
    }
};

これでよいはずです。実行結果はこうなりました。

[
    1 => [ 2, 4 ],
]

どうやら、ちゃんと動いてくれたようですね。

MapReduce の使いどころ

さて、これまで嘘の友人の例を検証してきましたが、誠に遺憾ながら、実は二番目の英単語を数える例も結構間違っています。皆さん、お気付きでしたでしょうか？

まず $mapper の中で stripos() に渡す引数の順番が間違っています。

$mapper = function ($article, $key, $mapReduce) {
    if (stripos('cakephp', $article['body']) === false) { // 引数の順番が間違っている
        return;
    }

    $words = array_map('strtolower', explode(' ', $article['body']));
    foreach ($words as $word) {
        $mapReduce->emitIntermediate($article['id'], $word);
    }
};

これでは cakephp という文字列の中に記事本文が含まれているかを探す処理になってしまいます。見つかるはずがありません。

結果を受け取る変数も $articlesByStatus になっていますが、これは $wordCount のような変数名が適切でしょう。また、配列を返すためには最後に toArray() を呼ぶ必要があります。

$articlesByStatus = $articles->find()  // 受け取る変数名は $wordCount などが適切
    ->where(['published' => true])
    ->andWhere(['published_date >=' => new DateTime('2014-01-01')])
    ->hydrate(false)
    ->mapReduce($mapper, $reducer); // 配列を返すには最後に toArray() を呼ぶ必要がある

これだけ誤りが散見されながら、今まで誰からも指摘を受けていないことを考えると、この MapReduce は実はあまり使われていない機能なのかもしれません。

formatResults() を使えば同じことができてしまうからでしょうか。例えば、嘘の友人の例を formatResutls() を使って書き直すとこうなります。

$query->formatResults(function($friends) {
    $tmp = [];
    foreach ($friends as $rel) {
        $tmp[ $rel['target_user_id'] ][] = -$rel['source_user_id'];
        $tmp[ $rel['source_user_id'] ][] = $rel['target_user_id'];
    }

    $fakeFriends = [];
    foreach ($tmp as $user => $data) {
        foreach ($data as $friend) {
            if ($friend > 0 && !in_array(-$friend, $data)) {
                $fakeFriends[$user][] = $friend;
            }
        }
    }

    return $fakeFriends;
})

二重のループがちょっと複雑かもしれませんが、 MapReduce を使ったからといって取り立てて単純になるわけでもありません。クロージャを変数で受けないように書き直しましたので、比較してみてください。

$query->mapReduce(
    function ($rel, $key, $mr) {
        $mr->emitIntermediate(-$rel['source_user_id'], $rel['target_user_id']);
        $mr->emitIntermediate($rel['target_user_id'], $rel['source_user_id']);
    },
    function ($data, $user, $mr) {
        $fakeFriends = [];

        foreach ($data as $friend) {
            if ($friend > 0 && !in_array(-$friend, $data)) {
                $fakeFriends[] = $friend;
            }
        }

        if ($fakeFriends) {
            $mr->emit($fakeFriends, $user);
        }
    }
)

また emitIntermediate() や emit() の呼び出しによるオーバーヘッドの分だけ、パフォーマンスは劣ります。処理対象のレコードが増えるほど、このパフォーマンスの低下は顕著になるはずです。

あまりメリットがあるようには思えませんね。

それもそのはず、そもそも MapReduce というのは並列処理のためのモデルだからです。

英単語を数える例を思い出してください。 Mapper が記事本文を単語に分解する作業をしている横で、 Reducer はもう単語を数え始めていても問題はないはずです。このようにすれば処理全体にかかる時間もぐっと短くなるでしょう。

これが本来あるべき MapReduce の姿です。

しかし CakePHP3 の実装は並列処理ではなく完全な逐次処理になっています。 Mapper が全てのデータを emitIntermediate() し終えた後で、ようやく Reducer が動き始めて emit() を行う作業に取りかかります。

もっとも PHP では並列処理を行うのが難しいため、この実装はやむをえないところではありますが、これでは MapReduce というモデル自体が持つメリットは完全に失われていることになります。

では、いったい CakePHP3 において MapReduce の使いどころはどこにあるのでしょうか――。

その答えを探し求めた私は、ついに MapReduce が formatResults() よりも明らかに先行する特徴を発見しました。これです。

フォーマッタ関数はすべての Map/Reduce が実行し終わった後、適用されます。

実行順が先でした――。

きっと、設計思想としては formatResults() はあくまでもデータの整形を行うためのものであって、その整形対象となるデータのふるい分けについては MapReduce で行うべき、ということなのかもしれませんね。

以上、 Cookbook の例の誤りを検証しながら、 MapReduce のふるまいを見てきました。ずいぶんと長文になってしまいましたが、最後までお読みいただいた方、心よりお礼を申し上げます。

なお、例の誤りについては後日チームに報告しようと思っています ²。

Cookbook の修正を行ったため、この記事で指摘している問題はすでに解消されています。当時の内容を確認できるようにリンク先を Github の方に差し替えました (2017年12月3日) 。 ↩
この問題は #4545 として報告し、プルリクエスト #5138 で英語版、 #5156 で日本語版の修正をそれぞれ行っています。 ↩