MySQLでの高速な重み付きランダム表示

東京都で賢い借金返済方法を教えます！では、MySQLに格納したWikipedia記事をランダムに表示している。速度を気にしないなら、

SELECT * FROM docs ORDER BY RAND() LIMIT 10;

で良いのだけど、レコード数が多いと遅くて使いものにならない。そこで、記事IDを1から始まる連番になるようにDBに格納している。このようにすると、アプリケーション側でDBに格納されている文書IDが全て分かるので、ランダムに文書IDを10個選択して、その文書IDのレコードを表示することで、ランダム表示を実現している。

例えば、IDは10個選択するRubyコードは、

ids = Array.new(10){ rand(num_docs) + 1 }

で、DBに発行するSQLはこんな感じになる。

SELECT * FROM docs where ID in (id1,id2,..,id10)  LIMIT 10;

最初はこの方式で満足していたのだが、不満も出てきた。Wikipediaの記事をランダム表示させてしばらく眺めていると、やけにイタリアのコムーネ（市町村）の記事が多い。調べて見たところ、イタリアのコムーネの記事は8102件もあって、結構なボリュームを占めていた。*1
他にも、イタリアのコムーネなどのマイナー記事が頻繁に表示されるのはつまらないので、記事の重要性に応じて表示頻度を変えたくなった。つまり、重要な記事ほど、頻繁に表示されるように変更したくなった。

重要度に応じて出現割合を変えるのは RAND() 関数を使えば簡単だが、前述のように処理速度が遅いため実用的でない。そこで、アプリケーション側でなんとかする方法を考えた。

まず、重要度順に記事をソートして、各記事のソート順位を求める。そして、Wikipedia記事テーブルにRANKカラムを追加し、RANKカラムに求めたソート順位を格納する。つまり、RANKカラムは1からレコード数までの範囲の値をとり、そのカラム値が小さい記事ほど重要度が高いことになる。

後は、アプリケーション側でRANKを10件ランダムに選択して、その値をカラム値とする記事を取得すれば良い。この時、小さいRANKを優先して選択する。このような選択方法は色々とある。

例えば、次のRubyコードの場合、ランク1位の記事は最下位の記事の2.7(=e)倍の確率で選択し、また、記事の選択確率はランクに応じて指数的に減少する。

ranks = Array.new(10) {
  p = exp(1 - rand()) - exp(0)
  q = exp(1) - exp(0)
  (p / q * num_docs).to_i
}

選択したrank値を用いてレコードを表示する際はIDの場合と同じで、次のようになる。

SELECT * FROM docs where RANK in (rank1,rank2,..,rank10)  LIMIT 10;

まとめる。

  • MySQLに格納したデータを高速にランダム表示するには、アプリケーション側でレコードIDなどを指定する。
  • 重要度に応じたランク値をDBに格納することで、重み付きランダム表示が可能となる。

*1:Category:イタリアのコムーネ - Wikipedia

XPathGraphを使ってAmazonでの売り上げランキングの変化をグラフにする方法

http://xpath.kayac.com/を使って、Amazonでの売り上げランキングの変化をグラフにしてみました。グラフにすることで、売り上げランキングの変化を簡単に見ることができます。

まず、XPathGraphにユーザ登録します。ユーザ登録した後、「新しくグラフを作成する」のボタンをクリックします。すると、グラフ作成画面になるので、次のパラメータを入力します。

タイトル、説明：適当なタイトル、説明をいれます。
URL：詳細ページのURLです。次のURLの_asin_のところに、ASINを入れたURLにしてもらえると、私がちょっとうれしいです。

http://www.amazon.co.jp/exec/obidos/ASIN/_asin_/diaryofllamer-22/

XPath：次のXPathを入力します。

//li[@id="SalesRank"]/text()

タグ：適当なタグをいれます。

「テスト」ボタンでランキング値がとれていることを確認したら、「グラフ作成」コマンドでグラフを作成します。グラフのURLが表示されますので、これで完成です。

作成例：http://xpath.kayac.com/graph/embmqbwH3RGOfg

XPathGraphのAPIが公開されたら、上記の作業を自動化するアプリケーションを作ってみたいと思っています。

Google App Engineから感じるGoogleのメッセージ

Google App Engine]のチュートリアルを試したみた。
pythonは殆んど知らないが、Railsに似たフレームワーク構成になっているので、だいたいなんとかなった。

Google App. Engineの特長をまとめるとこんな感じだろうか。第一印象なので、間違っているところはあると思うが、大筋ははずしていないと思う。

インストールが楽

一瞬で開発環境が整う。インストール後、コンソールでコマンドを叩けば、すぐに開発にかかれる。必要なのはエディタとWebブラウザとアイデアだけ。

デブロイが楽

ローカル環境とサーバ環境の差を意識する必要がない。コマンド一発で、ローカルの開発環境がサーバ環境にアップされる。アプリケーションにバージョン番号があって、古いバージョンに戻せるなど、周辺ツールも整っているみたい。

サービス公開が楽

信頼性（リライアビリティ）や拡張性（スケーラビリティ）を（基本的には）全く考慮しなくてよい。全部Googleが面倒をみてくれる。ApacheのチューニングやMySQLのバックアップに頭を悩ませる必要はない。

安い

500MBまでストレージは無料。それ以上は有料化されるらしいが、GMailのストレージを提供できる会社だけに、料金は相当安いはず。


開発言語がPythonだけなど制限も多いが、これらの制限も徐々になくなるはず。ただ、蓄積したデータを外部に取り出す手段がないのは嫌かも。

Google Application EngineはWebサービスを公開する上での障壁の多くを取り払っており、多くの開発者にとって非常に魅力的なサービスだと思う。

個人的にGoogle Application Engineから感じるGoogleのメッセージは次のようなものである。

「もっとWebを便利で面白い場所にしよう。その為の協力は惜しまない。簡単にWebサービスを作るための環境は我々が整えるから、君たちはどんどんWebサービスを作ってくれ。そうすれば、Webにもっと人が集まり、我々もAdsenseやAdWordsでもっと儲かるようになるから。」

あるWikipedia記事に似ている記事を表示する「Wikipediaめくり」

Wikipedia記事をランダムに表示したり、ある記事に似ている別の記事を表示する東京都で賢い借金返済方法を教えます！というサービスを作りました。

Wikipediaの記事は面白くてついつい読んでしまいますが、自分の興味の範囲内の記事ばかり読んでしまいがちです。そこで、記事をランダムに表示させてみると意外な発見があってなかなか楽しいです。

とはいえ、完全にランダムだと全く興味のない記事ばかり表示されるので、ある記事に似ている記事を優先して表示するようにしました。例えば、ダックスフントの場合、犬種（ゴールデン・レトリバーなど）や動物の名前（ナマケグマなど）が表示されます。

また、記事のタイトルでYahoo画像検索・YouTube検索・Amazon検索した結果もAjaxで表示できるようにしています。珍しい動物の名前で画像検索したり、ミュージシャンの名前でYouTube検索するのがお気に入りです。

アニメーションにはJSDeferredを使っています。具体的には、各記事を順番にゆっくりと入れ替えて、全ての記事を入れ替え終わったらAjaxでサーバに新しい記事を取りにいくところです。連続する非同期処理を処理の順番そのままに素直に書けるのが楽しかったです。

Wikipediaのデータは色々といじりがいがあるので、これからもちょこちょこと手を入れていきます。

「はてなダイアリー」は「はてな」の収益に貢献しているか?

twitterでのid:fromdusktildawnとid:malaのやり取り*1をみて考えてみたが、「はてなダイアリー」は、「はてな」の収益に凄い貢献していると思う。多分、ブログサービスの中では例外的に儲かっている気がする。特に、無料ユーザをお金に結びつける点ではピカイチかも。

もちろん、「はてなダイアリー」では（他のブログサービスと違って）無料ユーザのダイアリーでも広告は表示されない。なので、一見、無料ユーザは収益に全然貢献しないように思える。

ヒントは有料オプションにある。有料ユーザはキーワード自動リンクをオフにすることができる。つまり、逆にいえば、無料ユーザにはダイアリー内のキーワードを「はてなキーワード」にリンクしてもらう必要があるのだ。

無料ユーザが記事をアップする毎に「はてなキーワード」へのリンクが増える。検索エンジン対策で最も有効なのは、優良な被リンクを増やすことである。つまり、無料ユーザが記事を書けば書くほど、「はてなキーワード」の検索ランキングが上位になる確率が高くなる。

そのため、「はてなキーワード」は検索エンジン、特にGoogleで上位に表示されている。そして、検索エンジンで上位に表示されることをお金に結びつけるのは簡単である。実際、「はてなキーワード」のページは広告やアフィリエイトだらけである。比較は難しいが、個々の無料ブログに広告を表示するよりもずっと効率が良い気がする。

まとめると、「はてなダイアリー」は、「はてなキーワード」の検索ランキングを押し上げ「はてなキーワード」の収入を増すことによって、「はてな」の収益に貢献していると思う。

*1:id:fromdusktildawnのtwitterはpublicでないのでリンクははっていないです。

TinySegmenterをRubyに移植

Javascriptだけで書かれたコンパクトな分かち書きソフトウェアであるTinySegmenterをRubyに移植しました。移植してから別実装があるのに気がつきましたが、気にせず公開することにします。

Codereposにアップしてありますので、下記のURLよりダウンロードできます。

http://svn.coderepos.org/share/lang/ruby/ruby_tiny_segmenter/

MeCabに対するTinySegmenterの利点は、Ruby だけで書かれているので、どんな環境でも簡単に動作する点です。インストールも簡単です。Windows環境でMeCabをRubyから扱うのは少し面倒ですが、TinySegmenterならば殆んど問題ありません。

実行例はこんな感じです。

require "tiny_segmenter"

words = TinySegmenter.segment("私の名前は中野です")
puts words.join("|") # => 私|の|名前|は|中野です

TinySegmenterのページには、TODOに「キラーアプリを考える」がありますが、TinySegmenterはコンパクトなのが最大の特長なので、色々な言語に移植すれば、様々な場面で活躍するような気がします。

GoogleのBigTableの特長の1つはエンジンとストレージが疎結合であること

GoogleのBigTableの特長の1つはエンジンとストレージが疎結合であることである。
MySQLやPostgreSQLではSQLクエリを受け付けるマシン(エンジン)と、実際にデータを格納するマシン(ストレージ)は同じである。つまり、エンジンとストレージが密結合である。
エンジンとストレージが密結合である利点は、ストレージへのアクセスが、ネットワーク越しの場合に比べて高速なことである。
しかし、この利点は薄れつつある。ディスクへのアクセスはメモリへのアクセスに比べれば遥かに低速である。そのため、ストレージをメモリにキャッシュして運用することが多い。そして、常にストレージをメモリにキャッシュするならば、ストレージがローカルディスクにあるが、ネットワーク越しの別マシンにあろうが大差ない。必要に応じてメモリに読み込むだけである。
GoogleのBigTableではストレージはGFS上に格納される。従って、ストレージはエンジンと別の複数のサーバにレプリケーションされて保存される。つまり、エンジンとストレージは疎結合である。エンジンとストレージが疎結合であることの利点は多い。例えば次のような利点がある。

  • 柔軟性が高い。エンジンとストレージが独立のソフトウェアとなる。そのため、性能強化・機能追加・バグ改修が容易となる。また、別のアプリケーションに転用しやすい。実際、GFSはBigTable以外でも活用されている。
  • 耐障害性が高い。密結合の場合、マシンが落ちるとストレージとエンジンが必ず同時に落ちる。一方、疎結合ならば両者は独立に落ちるので、障害復旧は比較的容易である。例えば、あるストレージを担当するエンジンが落ちたら、別のエンジンを立ち上げて、そのストレージを新たに担当されれば良い。バックアップデータからの復旧は不要である。
  • スケーラビリティが高い。密結合ではマシンの追加はエンジンとストレージの追加を意味し、無駄が発生しやすりが、疎結合では両者を別々に追加できる。そのため、システムに必要なマシン台数を抑えられる。

まとめ