Googleの構造を想像して、KVSとRDBを考える
Googleの内部を知っているわけではないのであくまで想像ですけれど、わたしが作るとしたらこんな風に作る。それって、RDBとそんなに構造が変わらないよね。って話です。Googleの構造はユーザーとして想像しているだけに過ぎないので、違っていたとしても、そこそこ効率的に動きますからその辺には突っ込まないようにね（笑）。
まずは、リクエスト処理サーバ群がリクエストを受けたところから考えてみましょう（番号は絵とリンクしていません）。
1.Googleは辞書を使う形態素解析という方式ですので、受け取った検索文字列を、辞書を使っていくつかに分割する。
2.分割したキーワードをキーワードライブラリサーバ群に投げます。このサーバ群には、キーワード毎のコンテンツ件数と、その内容が、どのキーワードスコア管理サーバにあるかが入っています。
3.リクエスト処理サーバは、分割したキーワードのそれぞれの件数からどのように処理すべきか検討します。
例えば、「生島 勘富」で検索したとします。このときコンテンツの件数が、
生島 100,000件
勘富 200件
であったとしたら、「勘富」の入っているサーバからスコアの高い順にアクセスし、返ってきたURLを「生島」の入っているサーバに存在するか確認します。「生島」でもヒットするコンテンツが、クライアントが必要な件数（10件）まで集まればアクセスをやめます。もちろん、10件は両方のスコアを合計してソート。
コンテンツの件数が、
生島 100,000件
勘富 90,000件
であったとしたら、両方のサーバから、スコアの高い順にクライアントの要求件数分づつアクセスしながらマッチングする（2回目以降は前回ヒットしなかったデータも対象にする）。クライアントの要求件数に達したらやめる。他にもヒット数とその差によって、何種類かアクセス方法を作る。
4．結果を返します。
ヒット数は、以下の式で出力します。
およそ、【少ない方の件数 × (10 ÷ やめるまでの件数）】件中10件表示
3．の部分がもう一段別サーバ群を噛ませているかどうかとか、実際見たわけじゃないので、わたしは知らない。上のやり方では、実際のスコアーと逆に出力される不具合も、小さな範囲で起きますので、もう少し大量に読み込んでマッチングしている可能性もありますが、いずれにしても、プログラムとしてはそんなに難しくない。テクニカルに難しい部分はむしろハード側（分散や死活監視の高速化など）にあるでしょう。
＃ 実際、おそらくスコアーが反転しているであろう
＃ 結果も起きています。SEOの仕事をしたことが
＃ あれば気づいている人も多いと思うけれど、
＃ わたしの勘違いかも知れません。
＃ 確認方法は下の方でこっそり。
RDBMSでいえば、3．の部分がオプティマイザがやっている処理と、DBエンジンがやっている処理になります。
＃ Googleがヒット数の差で、動的にアクセス方法を変えてない
＃ としたらびっくりですが、上のやり方では、キーワード・URL順に
＃ 並んでいるインデックスと、キーワード・スコアー順で並んで
＃ いるインデックスを切り替える必要があるわけで、もしかしたら
＃ やってないかな……。
RDBは基本的に1つのインスタンスですから分散には向かないし、検索を漏れなく返すということを1つの目的として作られているのですが、Googleなどの検索エンジンはスコアの低いコンテンツを無視することでパフォーマンスを出している。つまり、要件が違うので、まったく同じではないけれど、RDBMSも内部構造は、内部キーと実データをいろんな方法でループしてマッチングしていると考えると、内部構造は大して変わらないのです（人によって「大して」の感じ方は違うと思うが）。
漏れをなくすというのは、SQLはFROM句WHERE句から処理しますので、明示的に「無視しろ」とSQLで書かないと、例えば上の条件では200×100000件のマッチング処理をしてから、計算したスコアでソートするしかありません。厳格ですが遅くなります。
インデックスするときは、おそらくクロールしたときに中間データとしてキーワードとヒットしたHTMLのタグ毎に保存しているだろう。SEOの仕事をしていると分かるが、METAタグの評価がゼロに近くなったり、外部リンクの評価が上がったりすることがある。これをSEO業者の間では「ロジック変更」と呼んで大騒ぎしていたけれど、スコアを計算する際のウェートをホンの少し変えてスコア計算をやり直しただけに過ぎなかった。（中には、新たな評価軸が加わるという本当のロジック変更もあったかも知れないが）そのスコアの計算を高速化するには中間データを取っておく必要があるわけです。
それでも、Googleなどはあまりに大きく、ハードが弱かったであろう数年前は、スコアの計算のやり直しに1週間前後のディレイがあり、その間は計算処理が終わったサーバと終わってないサーバでまったく違う答えが返ることになっていました。SEO業者の間でいわれていた「Googleダンス」です。今となっては気になるほどダンスしないようですが、多少は起きていますよ。
「およそxx件」という表示の曖昧さも、概算はスコアーが高いもの同士でヒット率を計算せざるを得ないので、スコアーが低いコンテンツとではヒット率が多きく変わることも起こるのです。その結果、概算との乖離が大きくなるキーワードもある。検索結果を順次見ていくと途中でページ数が狂ったりすることで、皆さんも気づいていると思います。
つまり、漏れが起こることが当たり前であったり、サーバ毎に違う結果が返ったり、ヒット数は概算でよかったりという緩いシステムであるからGoogleなどの検索エンジンは維持できるのであって、確かにそういうシステムは存在するのですけれど、絶対数は多くない。システムの数としては、Googleのように巨大にならない代わりに「検索漏れ」が非常に大きな問題になることの方が圧倒的に多いでしょう。そのようなシステムではRDBMSでやる方が向いているわけです。RDBMSでやるならば、3.の部分を「検索漏れがない」という条件で、オプティマイザが適切なアクセスパスを作ってくれます。
＃ Oracleで上位のみの高速出力を擬似的にやろうとすると
＃ オプティマイズヒントを FIRST ROWS にして
＃ クライアントにパイプライン表で返す。要求された
＃ 行数を返したら読み込みを止めるという方法は
＃ ありますけどね。常にネスティッドループになる。
デメリットとしては、RDBMSで作るとするとどうしてもサーバを分散させるのは難しい。Oracle RACなどを使わないときは、分散をさせると3．の部分を自前で作る必要があって、その場合はRDBMSの大きなオーバーヘッドが余分に掛かるので無駄です。
ただ、RDBMSでは無駄だからといって単純なKVSでできるかというと、KVSでは機能不足です。つまり、ソート済みで保存できるような拡張版のKVS（KVSというよりNoSQLで、探せばあるのでしょうが、今のところわたしには必要がないので知らない）が必要になる。逆に、RDBMSの中でも比較的機能を削って高速化しているMySQLのようなものと、KVS（NoSQL）とどちらを使うべきかは、要件によって検討するしかない。
現在のハードウェア環境であれば、中規模まではRDBMSで十分可能で、RDBMSでやるメリットは、後から、全文検索以外の抽出条件や、ソート条件を自在に追加できることです。それらメリット・デメリットを考慮して十分検討した上で、RDBMSを使って3．の部分を外側で書くのもよいし、NoSQLを使うのもよいのですが、今まで「SQLを使うべき」と散々書いてきたのは、SQLができないから外側で3.部分を書いている。というのが多いからです。
それは、下のイラストのようにタイヤを浮かせてキャタピラーを外付けしている状態になっています。おかしいでしょう。
※ イラストはhttp://blog.livedoor.jp/nikumaru17/ からいただきました。ありがとうございました。
イラストのように、RDBMSとKVS（NoSQL）は、似ているけれど用途が違います。RDBMSを使うならば、SQLを使いこなすこと。外にキャタピラーを新たに開発するなんてことは馬鹿げているのです。ちなみに、O/Rマッパーってタイヤとキャタピラーをつなぐ治具みたいなモノです。そんなモノの開発意義って、わたしにはまったく感じられないのですけどね……。
Googleを魔法使いか何かのように思う人もいるでしょう。でも同じ技術者が作っているのです。間違っていてもいいから、どうやっているのかユーザー側から見える範囲で、想像しましょうよ。
Googleの構造については、調査したら公開されている情報もあるかも知れませんが、わたしは1円の得にもならないので調査していません。ただ、間違っていても考える方が重要と思っていて、考えるだけなら風呂でもトイレでも電車でもできる。
実際、Google（実はGoogleの前のInfoseek）について10年以上前に考えたことが、今でも活きているわけです。料理人が毎日の食事に何も感じないのは問題です。同じようにIT技術者ならば、システムに触れるたびに、ソフトに触れるたびに、何か感じ、何か考える人でありたいし、あって欲しいと思います。
ユーザーとして考えて、通販とか価格調査サイトなどの検索機能には、まったく納得できないことが多い、あれは漏れてはいけないソートなどを追加する必要がある、RDBMSが向く典型的なパターンです。技術者としては「×××▲▲▲×××■■■×××！」といいたいし、経営者としては「弊社に依頼してください！」って思ってますけれど、なかなかね～。
検索窓を使う人は購入意欲が高く、その検索窓がショボイと数％の機会損失はある、（某家電量販店で20％上がったらしい）1億円を超える売上がある通販サイトは見直した方がよいですよ～。「プリンタ」と「プリンター」で違う結果が返るなんてあってはならないでしょう、「Let’s Note」「Lets Note」では、どちらかは出てこないなんて……。
スコアの逆転が起きているか確認する方法ですが、Googleの検索オプションで表示する検索結果を変えて、複合キーワードで10件×10ページ、100件×1ページの100件分結果を取ってみる。そうするとGoogleダンスとは言い難い逆転が起きることがあります。その辺りが低いスコアを無視したために、スコアの逆転が起きる範囲と考えられます。まぁ、わたしの勘違いかも知れませんし、中を見たわけじゃないので外しているかもしれませんけどね。
これも現象からロジックを考えたのじゃなく、高速に返すロジックを考えて、「じゃあ、このパターンでひっくり返るかな？ やっぱり！」って感じだったので覚えているのですけれど、確認したのはかなり前なので、今は知らない。
コメント
クラウザー
いつもの過激なＳＱＬ至上論は半分楽しみながら読めたのだが、前々回と今回は読んでいて不快になった。それは氏がコラムの中で展開しているKVS論である。
本人が言っているように、氏はKVSのことを何もわかっていない。わかっていないことは別に罪ではないが、わかっていないくせに、やらないけどやればできるんだ的に適当に書き散らしたKVS論は的はずれもいいところである。
おそらくクラウド＋KVSが主流になるとＳＱＬ中心の自分の仕事が減ることを危惧したのか、業務では使えないと断言する。しかし、おおっぴらに否定して先が読めない奴だと思われるのが怖いのか、よく調べたわけではないから違っているかもしれない、などと逃げ口は用意しているところが姑息だ。
まさかまだ時期尚早で実例など出ないだろうと思ったのだろうが、実際にKVSを業務に使っている方のコメントを読んで、あわててGoogle を作るとしたらなどと適当に書いているのが片腹痛い。
そもそも氏は、コメントで否定的な意見が出ると、コメント代わりにと銘打って、全くコメント代わりになっていないコラムを作ることで話を逸らすか、そうでなければ読み手の読解力が足らないせいだ、などと、仮にも物を書いている人間とは思えないような暴言を書いて平然としている。
今回のコラムには、KVSと分散をある程度やったことがある人間ならすぐわかるような技術的な間違いが、少なくとも４つはある。正確には４つまで数えたところでばかばかしくなって数えるのをやめたのだが。所詮、氏はRDB的な思考から脱却できないのだろう。昔、COBOLばかりやっていた人がRDBに移行すると、１テーブル
のカラム数が異様に多いテーブルや、不要なワークテーブルをやたらに設計していたものだが、氏がやっているのはそれと同じことだ。
氏がGoogleの設計や保守に携わっていないのは幸いである。さもなければGoogleはどうしようもない検索システムになっていただろうから。
このように書くと、きっと氏は「だから想像しているだけだと書いている。読解力をつけてから出直せ」などとのたまうのだろうが、無責任な個人のブログではなく、技術サイトの技術コラムで「想像で書いている。技術的には違っているかもしれない。外しているかもしれない」と放言して開き直っているとは信じがたい無神経である。
氏がどんなシステムを作っているのか知らないが、そんな調子で作られたシステムを使わされるエンドユーザも迷惑である。
皮肉にも、氏のコラムを読むことで「こんなにわかっていない人がいるのか」と、逆にKVSを進んで使おうという人が出てくるかもしれない。やっている人が少ないことに手をつけるのは、ビジネスにもエンジニアとしての将来にも、大いに優位に働くだろうから。そういう点では、氏のコラムも反面教師としての役には立っているのかもしれない。
ついでにflatline氏に忠告。ludiaは今後バージョンアップされる見込みはなく8.4にも未対応なので、N-Gramの全文検索ならtextsearch-sennaに乗り換えることをお勧めする。
ついでにAC/DC氏にも忠告。あなたの言っていることは、ただの難癖以外のなにものでもない。もう少し建設的なコメントを期待したい。
クラウザーさん、こんばんは。
残念ながら私の読解力では、何が言いたいのかさっぱり分かりません。
私は理解力がある方だと思っていたのに残念です。
私が理解できれば、良い議論ができたかも知れないのに、申し訳ない限りです。
flatline
クラウザーさん、こんにちは。
ご忠告どうも。すでにその方向で再構築を始めています。
クラウザー
おそらく氏と議論したとしても良い議論には到底なりえないだろう。
氏の技術レベルがどうこうではなく、氏の思考がＲＤＢ的なそれから脱却し得ないだろうからだ。
余談だが、氏は以前のコラムで中学生に負けたら腹を切ると言った。氏の意図するところは、中学生に負けるようなことは恥なので切腹するという意味であろう。
しかし、切腹は武士にとって名誉の死だということをわかっていない。恥だから切腹するというのは間違っている。恥じて死を選ぶというのなら、首でもくくるのが正しいのだ。
つい最近、高校野球の監督が切腹と口にしたが、氏の言っていることはあの監督と同じレベルでしかない。
クライザーさん、こんばんは。
コメントはしようがないので余談ですが、確かに腹を切るというのは名誉ですね。
しかし、そんな昔話をするならば、例えば、江戸時代に道場破りで負けた者が腹を切るというのは普通にあることです。
死ぬ必要はないけれど、恥ずかしいから腹を切る。
腹を切った以上、負けたことはチャラにして名誉は守られるわけです。
そんな取り立てて言うことでもないと思いますけどね。