ThinkIT 「徹底比較！検索エンジン」についてツッコミ

Sennaの場合には、文書数を166,512より多くしようとすると、メモリ確保の失敗が原因のsen_memory_exhaustedというエラーが発生し、インデックスに文書を追加できなくなりました。
http://thinkit.jp/article/744/1/

しっかりと反応しておきます。

対象文書サイズが4000000KB(≒4GB)を超えた場合インデックスが作成できないのは、
32bit OSを使っているからだと思われます。
64bit OSを使えば問題なくインデックスが作成できると思います。

あと、LuceneのN-gramの実験をやるんだったら、
SennaのN-gramの実験もやって欲しいなぁ…と思います。

次世代Senna（名称未決定…、名前変えることにしました）では
さらに転置インデックスのサイズが圧縮できるように努力してまーす。
名前が思いつかないのが困り者…

こういうパフォーマンス比較モノ記事は、書くのが非常に難しいです。
各比較対象についての知識と、それぞれでのチューニングのキモを知る必要があるからです。
各種パラメータなどをカリカリにチューニングしないと、そのライブラリに失礼ですから。
また、各検索エンジンが対象としている用途が異なるため、
納得感のある比較が難しいとも思います。
例えばSennaの場合、インデックスの更新と検索が平行して走っているときに
高スループットが出せることを目標としています。
「２ちゃんねる検索」なんかは更新走りっぱなしだし。

単純に言えば、↓こういう話なんですが…

• http://d.hatena.ne.jp/tokuhirom/20081202/1228232190

というわけで、「徹底比較！検索エンジン」記事の今後に期待です！

SennaでWAVE DASH(〜)とFULLWIDTH TILDE(〜)を同一視する

Sennaでは、UTF-8の文字列を正規化しています。
たとえば、「?」は「ミリバール」に、「AbRACADAbra」は「abracadabra」に、「ﾊﾗﾍｯﾀＺＯ」は「ハラヘッタZO」に変換されます。
これで、文字のゆれに対応した検索ができるわけです。

さて、某サービスでWAVE DASH(〜)とFULLWIDTH TILDE(〜)を同一視してほしい、
という要望が届きました。
そういうときはlib/nfkc.cをいじるとよいです。

lib/nfkc.cのいじり方について説明します。このソースコードは自動生成されていますので、直にいじるのはちょっと大変です。
lib/nfkc.c自動生成のためのプログラムは、util/unicode/以下に入っています。
util/unicode/icudump.cに以下のようなパッチを当てれば、FULLWIDTH TILDEを全てWAVE DASHに変換するようになります。
あくまで全角チルダのみ変換されて、チルダそのものは変換されないので地球に大変やさしい(?)ですね。

--- /home/tasuku/senna-svn/util/unicode/icudump.c       2008-10-15 20:09:54.000000000 +0900
+++ icudump.c   2008-11-02 14:49:50.000000000 +0900
@@ -75,6 +75,10 @@
   if (rc != U_ZERO_ERROR /*&& rc != U_STRING_NOT_TERMINATED_WARNING*/) {
     return -1;
   }
+  /* normalize full width tilda to wave dash */
+  if (ubuf[0] == 0xff5e) {
+    ubuf[0] = 0x301c;
+  }
   rc = U_ZERO_ERROR;
   nlen = unorm_normalize(ubuf, ulen, mode, 0, nbuf, BUF_SIZE, &rc);
   if (rc != U_ZERO_ERROR /*&& rc != U_STRING_NOT_TERMINATED_WARNING*/) {

lib/nkf.cの自動生成を行うには、util/unicode/nfkc.rbを実行します。
nfkc.rb動作のためには、ICU(開発用のヘッダファイル含む)とRubyが必要です。
Debianですと、libicu-devパッケージをインストールしてください。
nfkc.rbを動作すると以下のような操作を行います。

1. icudump.cからicudumpを作る
2. icudumpを使ってマッピング表を作り、nfkc.cを生成する

生成されたnfkc.cをlibに移動してビルドすればOKです。

今回は１文字だけでしたので直にnfkc.cをいじってもよかったのですが、
ひらがなとカタカナを同一視したい、などの要件がある場合には
icudump.cで置換することをオススメしておきます。

今月あたりに、仮想空間が枯渇したりメモリが枯渇したときの安定度を増した
Senna 1.1.4を出せたらいいなぁ、と考えています。
最後のSenna 1.1系となる予定です。

libxml-rubyでメモリリークしている気がする

libxml-rubyでメモリ使用量がじわじわと増えていく。
以下のようなコード。使い方の間違いとかについてツッコミ求む。

require 'xml/libxml'

doc = XML::Document.new()
doc.root = XML::Node.new('root')
root = doc.root
root << child = XML::Node.new('child')
(1..100000).each {|i|
  a = XML::Node.new('dummy')
  child.prev = a
  a.remove!
  GC.start
}

Hpricotはメモリリークするのでlibxml-rubyに乗り換えたんだけど、
世の中そうそう楽できるようには出来てないのね…

• Hpricotのメモリリークについて

明日ちゃんと追おう。

[追記]修正されました。

修正してもらいました(rev. 647) 。再現コードと、不完全でもいいからパッチがあるとやはり動きが早い。

memcachedを時刻巻き戻りに強くしてみる

昨日のダサい失敗エントリが注目を集めているようで恥ずかしいお…
今後ダサい失敗で困らないために、memcachedのパッチを書いてみようと思った。
時間が巻き戻った瞬間に障害が出るのはしょうがないけど、
巻き戻ったあとにその影響が残り続けるのは嬉しくない。

昨日起きた現象を考えるに、
「memcached内部での時間は、絶対時間で保持しているのではなく起動時間からの相対時間で保持されている」のだろう、と予想していた。実際そうみたい。

current_timeという変数に、現在の起動時間からの相対秒が記録されている（set_curent_time()）。
realtime()では、各種コマンドで与えられるexptimeを起動時間からの相対秒に変換している。

#define REALTIME_MAXDELTA 60*60*24*30
typedef unsigned int rel_time_t;

/* time-sensitive callers can call it by hand with this, outside the normal ever-1-second timer */
static void set_current_time(void) {
    struct timeval timer;

    gettimeofday(&timer, NULL);
    current_time = (rel_time_t) (timer.tv_sec - stats.started);
}

static rel_time_t realtime(const time_t exptime) {
    /* no. of seconds in 30 days - largest possible delta exptime */

    if (exptime == 0) return 0; /* 0 means never expire */

    if (exptime > REALTIME_MAXDELTA) {
        /* if item expiration is at/before the server started, give it an
           expiration time of 1 second after the server started.
           (because 0 means don't expire).  without this, we'd
           underflow and wrap around to some large value way in the
           future, effectively making items expiring in the past
           really expiring never */
        if (exptime <= stats.started)
            return (rel_time_t)1;
        return (rel_time_t)(exptime - stats.started);
    } else {
        return (rel_time_t)(exptime + current_time);
    }
}

まず思いつく手法は、rel_time_t型の変数について、全部絶対秒に変える手法。
time_tの型である__TIME_T_TYPEはlong intか。
絶対時間を採用するとLP64ではサイズが2倍になる。これは使えねー。
そもそも、絶対秒にすると修正点が多すぎる。

というわけで、set_current_timeを以下のように変えてみた。
時間の巻き戻りを検出したら、検出時の時間を起動時間に設定する、という超泥縄。
分岐予測も効くから実行速度への影響も少なげ。
2秒ずらしているのは、相対時間0が特別な意味を持つためっす。

/* time-sensitive callers can call it by hand with this, outside the normal ever-1-second timer */
static void set_current_time(void) {
    struct timeval timer;

    gettimeofday(&timer, NULL);
    if (timer.tv_sec < stats.started) {
      stats.started = timer.tv_sec - 2;
    }
    current_time = (rel_time_t) (timer.tv_sec - stats.started);
}

時間さえきっちり設定していれば、

• 揮発するとそれなりにマズい
• 永続化するほどでもない
• 高スループットが要求される
• ネットワーク越しで参照したい

情報について保持するために、repcachedは適していますよ！！
(これが主に言いたい)

memcachedを愚弄する１つの方法

某サービスでセッション情報を保持するために利用している
memcached(repcached)に障害が起こった。
ちゃんと追えていないけど、おそらく以下のような原因。他の人がハマらないように。

障害発生まで

• memcached(repcached)の中には揮発したらそれなりにマズい情報が入っている。
• repcachedサーバ２台のOS入れ替えをしていて、１台は再起動が成功した。
• １台目のサーバへ２台目のサーバからのレプリケーションが完了したのをstatsのcurr_itemsにて確認した。
• よって２台目を再起動するものの、起動しなくなった。

この時点では、１台は生きているから後でデータセンターいこうっと、という気軽な気持ちだった…

現象

生きている１台目のサーバで、以下のような現象が起こった…

• 値をsetする際に、ある閾値以上のexptimeを指定すると即expireされる。
• その閾値はなぜか刻々と減っていく
• memcachedでstatsコマンドを発行した結果のuptimeが4294954584とかのありえない値に
• でもdate +"%s"とかでサーバのUNIX timeチェックしてもまったく問題なし
• 俺大パニック

再起動に成功して、レプリケーションもすんだはずのサーバが謎の挙動を！
ウワーン…

tcpdumpやtelnetでプロトコルをチェックしたところ、
exptime周りの挙動がおかしいことが判明。
パニくってmemcachedの再起動とかをしてみたが状況変わらず。
exptimeを0にして仮対応した。
２台目死んだ状態で再起動したので、情報は揮発。しゅん。

死んだサーバの復旧のため、データセンターに向かう。とぼとぼと。

予想した発生メカニズム

データセンターで死んだサーバを再起動。普通に起動した…が、時間が9時間ズレている！
ということは、こんな感じで問題が起こったのかな。

• サーバのBIOS画面での時刻は、localtime(JST)になっている。
• Debianのtimezone設定はAsia/Tokyo。
• /etc/default/rcSでUTC=yesとなっていたが、NTPで時刻合わせする設定をしていたので稼働中は時刻がちゃんと設定されているように見えていた。
• /etc/init.d/memcachedでmemcached(repcached)が自動起動するようになっていた。

• 時刻が本来よりも9時間進んだ状態でサーバ起動
• memcached自動起動
• 「しばらくしてから」NTPサーバの時刻あわせが動き、時刻が9時間戻る。
• memcached大パニック

解決方法

• /etc/default/rcSでUTC=noとする
• もしくは、BIOSで設定する時間をUTCにする。

結論

• memcachedは起動後にサーバの時間が戻ると、ものっそ怪しい挙動になる。
• セッション情報は結構大事。永続化を検討すべき。特にお絵かき掲示板系はローカル保存ができない場合にはセッションが失われたらかなりマズい。
• repcachedで障害が！とTwitterでつぶやいたら即効開発者の方たちにチェックされていた。たぶん上記のような原因でした、騒いでごめんなさい…（これが主に言いたい）

Subversionクライアントだけをソースからインストールする(清貧な感じで)

複数台へのデプロイをするときに、
各マシンでsvn updateをして、
最新版のファイルをSubversionのリポジトリから入手する手法があります。
でも、これって各マシンにSubversionを入れないといけないんだよね。
portsも入れていない（わざとだけど）FreeBSDにいろいろと入れるのは大変めんどーい！

というわけで、http経由でSubversionのサーバからsvn checkout/updateできればいいや、
という目的のためのインストール方法のメモ。

neonはインストールする必要はなく、subversionのディレクトリ下に入れておくだけでよいようです。

fetch http://www.webdav.org/neon/neon-0.28.3.tar.gz
fetch http://subversion.tigris.org/downloads/subversion-1.5.2.tar.bz2
tar xvfz neon-0.28.3.tar.gz
tar xvfj subversion-1.5.2.tar.bz2
mv neon-0.28.3 subversion-1.5.2/neon
cd subversion-1.5.2
./configure --includedir=/usr/local \
 --without-berkeley-db \
 --without-apache \
 --without-apxs \
 --without-swig \
 --with-ssl \
 --disable-nls
make
make install

includedirはたぶんいらないと思います。必要に応じてつけてください。
さらに何もない環境であれば、--with-sslを--without-sslにしたほうがいいかもしれません。
たぶんhttpsは使えなくなると思うけど…

neonがない場合、httpのURLでリポジトリを指定すると「Unrecognized URL scheme」と怒られてしまいます。
neonは入れましょう。

グッドデザイン賞を受賞しました。

未来検索ブラジルが検索エンジン開発において(!)グッドデザイン賞を受賞したようです。

• http://www.g-mark.org/search/Detail?id=34960&sheet=outline&lang=ja

みんなも、オープンソース開発をしてグッドデザイン賞をもらおう！

あ、あとブラジルはIT技術者募集中です。

• デザイナ HTML/CSS
• ウェブアプリ開発 PHP/JavaScript/Ruby/Cのうち2つ以上
• フラッシュ開発 ゲーム/ツール
• Senna開発 C/Scheme/Rubyのうち2つ以上

詳しくはこのページへ、とリンクをつけたときに気づいたけど、
このページ恥ずかしいんだよな…

• 未来検索ブラジル:スタッフ募集