Aggregation FWの特徴と地雷
MongoDBのAggregation FWはSQLの集約関数(COUNT,SUM,GROUP等)の様な組み込み機能の集合である。
非常に便利なのだが、色々と問題があって、手放しにはお勧めできない。
Aggregation FWの機能や利用する時のハマリ所をリストアップしてみた。
機能
MapReduceの様にロジックを投入できる訳ではなく、組み込みの機能を利用するだけなので、柔軟性は無いものの殆どの用途に十分なほどの機能が用意されている。
1. noscripting=trueで運用できる
なによりサーバサイドでスクリプトを走らせるリスクを回避できる事が最大のポイント
2. SECONDARYで動作
Primaryへの負荷を掛けることなく動作できる。
専用のhiddenノードで運用すすればオンライン系への負担も無いのでとても便利。
3. パイプライン
多段の集計が可能。ある意味SQLより強力。（サブクエリーでも一応できるが、、）
$match (WHERE) -> $group (GROUP BY) -> $match (HAVING) -> $group -> $sort
地雷リスト
1. メモリー制限
クエリーが10%以上のメモリーを使うと強制的に殺されるようだ。
（多分MongoDB全体の制限）
terminating request: request heap use exceeded 10% of physical RAM
これでは満足な集計が出来ない。
ソート系は特にヤバイ。
上記の様に折角hidden secondaryで動作できる仕様の割に中途半端な制限。
2. Sharding環境では、、
mongosにクエリーを投げる事で、各Shardへのリクエストはヨロシクやってくれるのだが
なんとPRIMARYノードに投げてしまう！
この制御方法もなさそうだ。。
これでは使えない・・・
結果的に大規模なデータでは使えないということ。
結論
そんな訳で、、
AggregationFWは便利なのだが、現状では中途半端な感が否めない。
まだお勧めできる状態にあるとは言えないな。
これらを解ってて使う分には良いが
AggregationFWに頼ったシステムを構築すると、後々痛い目を見るだろう。
やはり解析はMongoDBの外で行った方が良いと思う。
MongoHadoopか、、
チャレンジングな人はMonmoちゃん使ってあげて！！w
Aggregation FW機能、SQLとの比較
使い方や例など詳細は本家のドキュメントを参照してください。
基本機能
| オペレータ | SQL相当 | 説明 |
|---|---|---|
| $project | SELECT | 集計用のフィールドの削除・追加・定義など |
| $match | WHERE | 絞込み条件を指定 |
| $limit | LIMIT | 対象行数指定 |
| $skip | LIMIT | 読み飛ばし行数指定 |
| $unwind | - | 配列フィールドを複数ドキュメントに展開（使わない使えない使いたくない） |
| $group | GROUP BY | 集計 |
| $sort | ORDER BY | ソート |
| $geoNear | - | 座標フィールド近傍検索+ソート |
集計($group)機能
| 集計オペレータ | SQL相当 | 説明 |
|---|---|---|
| $first | - | SQLでもやりたい事は多いのでうれしい |
| $last | - | 同上 |
| $max | MAX | |
| $min | MIN | |
| $avg | AVG | |
| $sum | SUM | {$sum:1}でCOUNTを代用できる |
| $push | - | 全要素を配列として返す |
| $addToSet | - | $pushのユニーク版（どっちも便利） |
文字列操作
| オペレータ | SQL相当 | 説明 |
|---|---|---|
| $concat | CONCAT | 文字列結合 |
| $strcasecmp | - | 文字列比較（$cmpの文字列版） |
| $substr | SUBSTR | 部分文字列 |
| $toLower | LOWER | 小文字変換 |
| $toUpper | UPPER | 大文字変換 |
日付関連
| オペレータ | SQL相当 | 説明 |
|---|---|---|
| $dayOfYear | ... | 1-366 |
| $dayOfMonth | ... | 1-31 |
| $dayOfWeek | ... | 1-7 |
| $year | ... | |
| $month | ... | 1-12 |
| $week | ... | 0-53 |
| $hour | ... | 0-23 |
| $minute | ... | 0-59 |
| $second | ... | 0-59(,60) |
| $millisecond | ... | 0-999 |
mongodb in Sakura VPSのスローダウン仮説
サクラvps3Gのmongoで原因不明のスローダウンが発生。
どうも、急激にディスクリードが遅くなったようだ。
プロセス再起動も効果なし、メモリーも十分。
謎だったのだが、一つ仮定は作れた。
・どうやら50Gもあるコレクションで起きてるっぽい
・そこには古くて暫く触ってないデータが大量にある
ココからは想像だが、、
サクラの仮想環境はもちろんサーバのイメージは専用の巨大ストレージにあって、ポータブルな構成になっている筈だ。
巨大なストレージは巨大なキャッシュ層があるのが普通で
メモリーキャッシュやフラッシュなど多層構造のキャッシュがある。
フレッシュじゃないデータ（ブロック）はキャッシュ層の下層に追いやられていき、最後はディスクに落ちる
仮想サーバから見たとき、同じディスクリード（mongoはmmapなのでpagefault）に見えても、裏では軽くキャッシュから取るだけだったり、ドデカイfaultとディスク処理になってるのかもしれない。
と仮定すると、データは適度に触れと云うことになるな。。
キャッシュを独占的に使うようなやり方は気が引けるんだけども、、、
MongoDB丸の内勉強会でしゃべって来ました
MongoDBだけで自然言語処理
後半は僕が喋らせてもらいました。
前半はスライドを使って座学
http://www.slideshare.net/crumbjp/mongodb-26372826
後半は、一応ハンズオンでしたが、時間が押してて
僕も遠慮なくタイピングしたので、付いて来た人は居ないかもしれない（ＴＴ；
時間が無くて、形態素解析と熟語解析までで一旦終わりましたが、皆さん楽しんで貰えましたかね？
普通に考えたら到底『正しい』とは言えないMongoDBの使い方ですが
僕的には、これこそがベストなんじゃないかな？と思ったり。。
もう他のフレームワークでロジック書く気がしなくなった。
そんなこんなで楽しんで来ましたが、
話は途中までだったので次回以降、どこかで続きをやりたいなぁ
サーチ評価の話（和訳）
仕事で考えなきゃならないケースが出てきたので
『後でやる』シリーズを消化していく。
（赤字は私の所感）
Googleサーチエンジンの改善に関する記事の和訳
（想定される問題をピックアップする目的）
Search evaluation at Google
Posted: Monday, September 15, 2008This series of posts has described Google's search quality efforts in areas such as ranking and search UI. Now I'll describe search evaluation. Simply put, search evaluation is the process of measuring the quality of our search results and our users' experience with search.
この一連のポストはGoogleのサーチやランキングにおける品質向上努力についてである。
サーチ評価とは、我々のサーチ結果の品質を計測するプロセスと我々のユーザのuser-experienceのことだ。
Let me introduce myself. I'm Scott Huffman, an engineering director responsible for leading search evaluation, working with a talented team of statisticians and software engineers. I've been here since 2005, and have been working on search in one form or another for the past fourteen years or so.
［自己紹介］２００５年からサーチ評価をリードしてきた、統計分野のエンジニア
When I'm interviewing folks interested in joining the search evaluation team, I often use this scenario to describe what we do: Imagine a Google ranking engineer bursts into your office. "I have a great idea for improving our search results!" she exclaims. "It's simple: Whenever a page's title starts with the letter T, move it up in the results three slots." This engineer comes armed with several example search queries where, lo and behold, this idea actually improves the results significantly.
私はサーチ評価チームにjoinしたい人々との面接で、説明のため、たとえ話を使う。
ランキングエンジニアがきた事を想像してみて？
『サーチを向上させる為、いい事を思いついたの!!』
『簡単よ！いつでもタイトルがTから始まるページを上に持ってくればよい。』
このエンジニアはいくつかの例を示し、このアイディアは実際にすごく結果を向上させた。
※以降、Ｔハック
Now, you and I may think that this "letter T" hack is really a silly idea, but how can we know for sure? Search evaluation is charged with answering such questions. This hack hasn't really come up, but we are constantly evaluating everything, which can include:
- proposed improvements to segmentation of Chinese queries
- new approaches to fight spam
- techniques for improving how we handle compound Swedish words
- changes to how we handle links and anchortext
- and everything in between
ここで、、あなたや私はTハックを馬鹿げたアイディアだと考えるかもしれない。しかしどうだろうか？
サーチ評価はこのような疑問に答えるためのものだ。
このハックが実際に提案された事はないが、我々は色々なことを評価している。
- 漢字圏のサーチ結果向上の提案
- スパム対策の新しいアプローチ
- スウェーデン語に関する新技術
- リンクとアンカーの扱いの変更
- その他
As Udi mentioned in his initial post on search quality, in 2007 we launched over 450 improvements to Google search, and every one of them went through a comprehensive evaluation process.
Udi がサーチ品質について言及しているように
２００７年我々はGoogle searchに４５０もの改善を包括的な評価プロセスを通して行った。
Not surprisingly, we take search evaluation very seriously. Precise evaluation enables our teams to know "which way is up". One of our tenets in search quality is to be very data-driven in our decision-making. We try hard not to rely on anecdotal examples, which are often misleading in search (where decisions can affect hundreds of millions of queries a day). Meticulous, statistically-meaningful evaluation gives us the data we need to make real search improvements.
驚くべき事ではない。我々は真剣にサーチ評価を行っている。詳細な評価をする事で我々はどの方法がよいのか知ることができた。
サーチ評価について一つ言える事は、データドリブンな意思決定であれ。だ。
我々は逸話的な事例に頼ってはならなかった。それらはミスリードを引き起こす。（一日、何億ものクエリーに影響してしまう）
入念に、統計的に意味深い評価こそが、我々が本当に必要とする結果を導く。
Evaluating search is difficult for several reasons.
First, understanding what a user really wants when they type a query -- the query's "intent" -- can be very difficult. For highly navigational queries like [ebay] or [orbitz], we can guess that most users want to navigate to the respective sites. But how about [olympics]? Does the user want news, medal counts from the recent Beijing games, the IOC's homepage, historical information about the games, ... ? This same exact question, of course, is faced by our ranking and search UI teams. Evaluation is the other side of that coin.
Second, comparing the quality of search engines (whether Google versus our competitors, Google versus Google a month ago, or Google versus Google plus the "letter T" hack) is never black and white. It's essentially impossible to make a change that is 100% positive in all situations; with any algorithmic change you make to search, many searches will get better and some will get worse.
Third, there are several dimensions to "good" results. Traditional search evaluation has focused on the relevance of the results, and of course that is our highest priority as well. But today's search-engine users expect more than just relevance. Are the results fresh and timely? Are they from authoritative sources? Are they comprehensive? Are they free of spam? Are their titles and snippets descriptive enough? Do they include additional UI elements a user might find helpful for the query (maps, images, query suggestions, etc.)? Our evaluations attempt to cover each of these dimensions where appropriate.
Fourth, evaluating Google search quality requires covering an enormous breadth. We cover over a hundred locales (country/language pairs) with in-depth evaluation. Beyond locales, we support search quality teams working on many different kinds of queries and features. For example, we explicitly measure the quality of Google's spelling suggestions, universal search results, image and video searches, related query suggestions, stock oneboxes, and many, many more.
サーチ評価はいくつかの理由から難しい：
- ユーザがサーチによって本当は何を望んでいるのか（クエリーの意図）理解することが非常に難しい
高度に導きやすいクエリー（ebeyやorbitz）では、殆どのユーザが、それぞれのサイトに飛びたい事であろう。
しかしolympicsでは？ニュースが欲しい？メダルの数？IOCのサイト？歴代記録？
ランキング／サーチチームにとって正に問題だ。（取り違えれば）この評価は真逆になる。
答えが明確では無い問題の典型だ。サーチに限らず『どう評価して良いか明確ではない問題』におけるアプローチとして参考にできる
- サーチ品質を他のエンジンと比較することも難しい。本質的に１００％良くなる改善は不可能だ。
どんなアルゴリズム的改善であっても、改善した人が大勢いる一方で悪化する人もいる。
- 一口に『良い』といっても、色々な次元がある。
伝統的なサーチ評価では『結果の関連性（望む結果が得られたか？）』や『我々の設定する優先度』をもって良しとする。
しかし今日のユーザは『関連性』以上の事を期待している。タイムリーな情報か？信頼のおける情報か？包括的な情報か？スパムじゃない？興味を引くタイトル？
ユーザはUI要素をクエリーに含めるかも？（maps,images,query,suggestions,など）
我々の評価はこれらの側面もカバーしようとしている。
ユーザが主体となるサービス全てに言えることだ。具体的に参考になる切り口でもある
- Googleサーチの品質は、非常に大きな何百という地域（国／言語）をカバーすることを要求される。地域にまたがって、サーチ品質チームは幾つものクエリーや機能をサポートしている。
たとえば、spell-suggestion、サーチ結果、画像／動画サーチ、query-suggestion、stock oneboxes?,その他。
To get at these issues, we employ a variety of evaluation methods and data sources:
Human evaluators. Google makes use of evaluators in many countries and languages. These evaluators are carefully trained and are asked to evaluate the quality of search results in several different ways. We sometimes show evaluators whole result sets by themselves or "side by side" with alternatives; in other cases, we show evaluators a single result at a time for a query and ask them to rate its quality along various dimensions.
Live traffic experiments. We also make use of experiments, in which small fractions of queries are shown results from alternative search approaches. Ben Gomes talked about how we make use of these experiments for testing search UI elements in his previous post. With these experiments, we are able to see real users' reactions (clicks, etc.) to alternative results.
これらの問題のため、我々は多様な評価方法や情報源を採用している。
- 人間の評価者。Googleは多くの国や言語の評価者を活かしている。評価者は注意深くトレーニングされ幾つもの異なる方法でサーチ結果を評価することを求められている。
ときに、評価者の評価が割れる事があったり、評価者の評価が一つになり、多様な側面から評価してくれるよう頼むこともある。
- Live traffic実験。我々はまた少数のクエリーをに対し実験的に別アプローチのサーチ結果を表示している。Ben Gomesはexperiments for testing serach UI elemetsで
我々がどのようにこれらを行っているか言及した。これらの実験によってサーチ結果によるユーザのリアルなリアクションを見る事ができる。
Clearly, we can never measure anything close to all the queries Google will get in the future. Every day, in fact, Google gets many millions of queries that we have never seen before, and will never see again. Therefore, we measure statistically, over representative samples of the query-stream. The "letter T" hack probably does improve a few queries, but over a representative sample of queries it affects, I'm confident it would be a big loser.
明らかに、、我々は殆どすべてのクエリーを計測する事はできていない。
事実、Googleは数百万もの新たな（また今後二度と送られる事のない）クエリーを毎日受けている。
そのため、我々はサンプリングを行い、統計的に計測している。
Tハックはおそらく、少数のクエリー結果を向上するが、そのようにサンプリングしたクエリにも影響を及ぼし、間違いなく巧く行かない。
One of the key skills of our evaluation team is experimental design. For each proposed search improvement, we generate an experiment plan that will allow us to measure the key aspects of the change. Often, we use a combination of human and live traffic evaluation. For instance, consider a proposed improvement to Google's "related searches" feature to increase its coverage across several locales. Our experiment plan might include live traffic evaluation in which we show the updated related search suggestions to users and measure click-through rates in each locale and break these down by position of each related search suggestion. We might also include human evaluation, in which for a representative sample of queries in each locale, we ask evaluators to rate the appropriateness, usefulness, and relevance of each individual related search suggestion. Including both types of evaluation allows us to understand the overall behavioral impact on users (via the live traffic experiment), and measure the detailed quality of the suggestions in each locale along multiple dimensions (via the human evaluation experiment).
我々サーチ評価チームにおけるキースキルのうちの一つは、実験的設計だ。
我々はそれぞれのサーチ向上施策案に実験を計画する。これによりその変更の主要な側面を計測できる。時に、人手での評価と組み合わせることもある。
たとえば、広範囲の地域にまたがるGoogle関連性サーチ機能に関する施策を検討する際、
Live traffic実験を含めるだろう。そして、関連サーチ候補の変化、地域毎のクリックレート、関連サーチ候補の位置の上下などを見る。
また、人手による評価も含めるだろう。そして、地域毎に不適切さ、不便さ、関連サーチ候補の調整などを依頼する。
これら両方の結果をもって、我々はこの施策の全体におけるインパクトを理解し、多角的に地域毎の候補クエリーの詳細をつめる事ができる。
実証実験をせよと言うことか。A,Bテストなどもそれに含まれるだろう。手間もかかるし、スピードとトレードオフになる感は否めない。
多角的に評価したものを包括的に判断する部分も難しそうだ
Choosing an appropriate sample of queries to evaluate can be subtle. When evaluating a proposed search improvement, we consider not only whether a given query's results are changed by the proposal, but also how much impact the change is likely to have on users. For instance, a query whose first three results are changed is likely much higher impact than one for which results 9 and 10 are swapped. In Amit Singhal's previous post on ranking, he discussed synonyms. Recently, we evaluated a proposed update to make synonyms more aggressive in some cases. On a flat (non-impact-weighted) sample of affected queries, the change appeared to be quite positive. However, using an evaluation of an impact-weighted sample, we found that the change went much too far. For example, in Chinese, it synonymized "small" (小) and "big" (大)... not a good idea!
『適切なサンプリング』は微妙な問題をはらむ。
サーチ施策案を評価するとき、我々は、クエリー結果の変化だけでなく、ユーザにとってのインパクトの程も検討する。
たとえば、クエリの上位３つが変わったとき、９、１０が入れ替わった時より、大きなインパクトがある。
Amit Singhalのprevious post on rankingの中で、彼は同義語について話している。
最近、我々は同義語をもっとアグレッシブに扱う施策を評価した。
平坦なサンプリングにおいて、これはとても巧くいくようだった。
しかしながら、重みづけサンプル(impact-weighted sample)においては、到底、成功とは言えない結果だった。
例えば、漢字において、small(小)とbig(大)は巧く行かない。
サンプリング問題。平坦に取るだけでは駄目と・・・これは真逆の発想ですらある。。
We're serious about search evaluation because we are serious about giving you the highest quality search experience possible. Rather than guess at what will be useful, we use a careful data-driven approach to make sure our "great ideas" really are great for you. In this environment, the "letter T" hack never had a chance.
Posted by Scott Huffman, Engineering Director
我々は、サーチ評価に関して真剣だ。それはあなた方に可能な限り快適で高品質なサーチを届けたいからだ。
むしろ便利さよりも。。我々は『我々の良いと思う事』が本当に『あなた方にとって良い事』になるよう、データ駆動アプローチをしている。
このような環境ではTハックは絶対採用されない！
転職しました。。
退職エントリーが流行の様なので・・・
９月末付けで楽天を退社しました。
楽天は、６年間お世話になりました。
非常に働き易く良い会社だったと思います。
それまでは、長くても同じ職場には２年は居つかなかったのですが
特に大きな不満もなく、居心地が良すぎてツイツイ長居してしまった。
今までの職場ではやりたい事はスグやり終えてしまい、退屈でした。
楽天には沢山ありましたね。。やり切れないほどに・・・
楽天台湾進出プロジェクト、インフォシークの大改修など
数多くの得がたい機会と経験をさせて頂き感謝しております。
さて、、では何故退社したのか？
一言でというと
『私にとって楽天は大きく成り過ぎた』
大きな会社は必然的に動きが鈍くなります。
これは『誰が悪い』とか、『どうしたら良い』とかの問題ではありません。
組織が大きくなれば、それなりにガバナンスコストが上がり
そのコストが時間に跳ね返るというだけの話です。
いくら社長が突出して優秀で、適切な処置をしたとしてもです。。
４０才が見えてきた自分にとって、この時間が惜しく感じたのが理由です。
『もっとスピード感のある仕事をしたい。機敏に動きたい。』
という欲求が転職を決意させました。
１０月からはCookpadで働きます。
まだ組織的に小さく、それでいてビジネス的にも可能性が大きく
更にエンジニアに手厚い会社と感じました。
これからも、生涯現役エンジニアを目指して頑張っていくので
よろしくお願いします。
自然言語処理の落書き（canopy問題）
やはりcanopyが厄介だ。。
T2サンプリングの問題
自然言語処理では物凄くスパースなベクトルを扱ってるので
canopy(T2)の段階で、クラスタ数が必要以上に増える。
その後、canopy(T1)で重心算出すると、２０個以上の重心がT2内に入ってる状態になったりする。
後処理しても、、
後からそれらを纏めてしまう事もできるが、そもそも必要以上の重心を作ってしまったT2サンプリングに問題があるように思える。
只でさえ、並列化の難しいアルゴリズムなのに、
本来必要な比較回数の数十倍の比較回数を処理しなければならないのが無駄だ。
代替案
T2サンプリング時に、逐一、重心算出をしながら行えば、ベクトルのスパース問題が緩和されると思いきや、精々1/2程度。
ヒドイとクラスタ数が増えたりする。
（ベクトルのスパースが埋まってくる前にクラスタ数が爆発的に増えてしまう為）
あまり効果が無い上に、重心算出コストが比較コストよりも高く、やってられない。
結論としては並列化するしかない
なんとかMapperに食わせる形にするしかないな。
やりたいのは、Kmeansに食わせる初期クラスタ算出であって、純粋なcanopy実装ではない。
canopyベースで色々変形させてみようか。。
＜追記１＞
＜追記２＞
上の、無駄クラスタを減らす努力の話はどうもダメダメっぽいな。
canopyは並列化し難い代わりに、スパースなベクトルのcos距離（≒内積）という軽量な比較処理が魅力に感じてきた。
スパースなベクトル同士の内積は関与する項が少ない
V1 , V2 を比較しようとしてて、それぞれ1000次元だとしても
共通項が"foo"一つなら、V1["foo"] * V2["foo"] でおしまいということ。
よって、無駄クラスタが多少増えようと、並列化のアプローチが正しそう。
＜追記３＞
T2サンプリングの際に、クラスタ数が多くなり過ぎる無駄に対応するために
T2半径を大きく取る試みは大きな間違いだったのようだ。
canopy（T2サンプリング）ではスパースな重心とスパースなベクトルのcos距離（実用：1-cos距離）を取るので、基本的には距離が遠い。
- 1-cos距離
- cos距離は、最大距離が0で、最小距離が1。
ユークリッド距離の同様の計算処理に通したいので、値が大きいほど遠く扱える『1-cos距離』を用いている
しかしT1サンプリング後の重心算出では、ベクトルの平均を取るので、スパースではない重心が生成される。
この重心らは非常に距離が近くなる。
よってT2を大きく取ってしまうと、T1サンプリングの段階で、それぞれの重心に大半のベクトルが所属してしまう事になる。
こうなると元々近く、クラスタとして不適切な上に、スパースベクトルで無い分、データサイズも大きくなってしまう。
- 不適切
- 後続のk-meansの収束が遅くなるし、結果も悪くなる。
- サイズ
- 同数のクラスタを抽出する場合でも、下記の方法と比べて10〜100ものデータ量になる場合もある
よって、比較的小さい半径のT2を取り、T2 -> T1 -> T2 と処理するのが良い模様。
- 補足
- サイズ的にも配置的にもk-means中に出現するクラスタに近く、収束が早くなる傾向もある。
