a group powered by ototoy blog

ブラジル！

デバッグ状況とか書こうと思って。。

とりあえずタフなバグと格闘中。
特定のシーケンスでインデックスが破壊される。
mysql.logから再現するためのシーケンスを抽出中

真面目にデバッグするはずが、ついqwikで遊んでしまった。。
http://qwik.jp/senna/

真面目にデバッグするはずが辛酸なめ子先生の女・一人日記を発見し、バックナンバーに読み耽ってしまった。
いかん、、またべこに叱られる。

こらー！

バグ取れました。0いっこ付け忘れてただけだった。。(T_T)
しかもsvnの更新方法が分からないと言う罠

某見込みユーザのためにutf8対応を突貫工事で進めている。
コアはだいたい出来たけど、encodingの指定方法がめんどくさい。
設定ファイルのパースにstrcmp多用するのは避けたい。
(satoru氏に嘲笑されるー)
strcmp ２コまでなら許容範囲かな？
３コ以上になったらhashテーブルにしよう。

utf8対応完成！と、思ってたら、検索時にerror 127
また未知の事象。。。
早くなんとかしたいけど、高熱で頭がまともに動かん。

通常のdeleteと全件deleteとで通るルーチンが違ったのだった＜mysql
そこにsennaパッチ当ててなかったのでインデックスと表の内容に不整合が生じていた。
とりあえず治った。でもvacuum(optimize)するとお手上げなんだけど。

うひょひょ。

英文字列と数字文字列はひとまとまりとして扱うオプションをつけてみた。ngram切り出しの関数にエンバグしてまた2日ほどハマった。

インデックスサイズの縮小に挑戦中。
インデックスが大きいからと言って処理速度が遅いとは限らないが、小さいに越したことはない。
検索精度とのトレードオフを調整しつつサイズを縮小するアプローチで25%ほどサイズが小さくなった。
次に文字列の出現頻度を利用して縮小する方法を試行中。
手元のメールアーカイブをサンプルにして統計量を測定したところ、
「ろゆき」「ちゃんねる」等の文字列が抽出されてしまう。もうちょっと偏りがないサンプルを使わんと。。

人間が偏っているのかもしれません。

alpha, digit, symbolはbigram化しないようにした。
N社開発環境にも反映して、再import完了した。
SQLでlimit指定すれば多分高速に動くと思います。

1.再現率と適合率、2.更新性能と検索性能という
二つの非常に本質的なトレードオフについてずっと悩み続け中。

http://chasen.org/~taku/blog/archives/2005/01/post_784.html
こういう考え方を高効率に実装する方法がないものか。

やっぱ適合率重視するなら形態素解析は避けて通れない気が。。
sennaにmecabを組み込んでみた。なかなかいい感じ！
速い！精度も悪くない！ これでアメリ問題も解決か？

相変わらずmecab萌え中。
mt-safe化が当面の課題。
mecabのドキュメントには、thread毎にinstanceを作るか、
parse実行全体をmutexでlockしろ、とある。どっちもやだなぁ。。
parserはstatelessに実装できそうなものなのに、、と思ってソースをほげってみると、
parserの内部に辞書のcacheを持っているのだった。
cacheの更新操作がthread unsafeなのだろう。。
困った。。

「1インスタンス = 1スレッドの場合、
辞書は mmap (MapViewOfFile) を用いて, OS の仮想メモリ上に割りあてられるため, 複数のインスタンスを作成しても, 多くのメモリを使用することは ありません.」とあるが、
物理メモリは確かに共有されるだろうが、論理メモリ空間はinstance数分消費するので、やはり問題なのだ。
(論理空間が2GBを越えるとMySQLごとあぼーんする)
うーんうーん、、

mecabのソース読んでてバグ発見したのでパッチとレポートを作者に送ったのですが、反応なくて激しく鬱。。

mecabにpatchが取り入れられた。些細なbugでversion upさせてしまってなんかかえって申し訳ない。。
問題は、
http://chasen.org/~taku/blog/archives/2005/03/post_801.html
この技術がfreeなmecabに反映されるかどうか。。
これと組み合わせたsennaは最強のエンジンになるかも。

やっぱり。。
http://tahoo.org/~taku/ml/mecab/msg00154.html
「いろいろ事情があって、公開はまだ先になりそうです。すいません。」だって。

N社で権利確保中なのかな〜

分かち書きが独立可能な形で
独自に進化してくれたほうがよさげですなぁ。

>>18
shm使うのはダメ？

>>22
多言語化のこともあるし、分かち書きエンジンは容易に切替えられるよう考慮しますです。

>>23
バッポン的に直せばアリですが、なるべく元バージョンを尊重したいなーと思っていたり。。

雑誌に載るかもってんで、sennaのページをがんばって作成
http://dev.razil.jp/project/senna/
最初は面倒だったんだけど、こういう作業ってつい時間を忘れて没頭してしまいますね！

しかし、どうも色合いが変らしい.. orz

API手直しした版をcommitしました。defaultでmecabになってる。

いやーようやく承認されたよー。。
http://sourceforge.net/projects/senna/
べこさんのおかげです！！

adminページにもリンク置きました。

おぉ。。さんくすです！

mecabのmt-safe化に関して方式のメドが立ったのでガリガリ実装中。
本家に取り入れられるかどうか分かんないけど、これがないとMySQLに組み込めないのでお構いなしに書く。
これが済んでようやくN社向け作業が進展するかな。。

http://naoya.dyndns.org/~naoya/mt/archives/001639.html
褒め上手な人だ。。

こうやって徐々に知られていくのかー。

なんか、オープンソースでやるからには「TODO」セクションと、コード書きヘルプ募集中、みたいなのをプロジェクトページに出してみては？

あとnaoyaさんに知られてしまったからにはSenna-Perl急がないと先に書かれる・・・

それもそうだー

他社の特許を侵害しているのではないかと急に心配になり、調査した。
http://www2.ipdl.ncipi.go.jp/begin/BE_DETAIL_MAIN.cgi?sType=0&sMenu=1&;sBpos=1&sPos=27&sFile=TimeDir_2/mainstr1112118077850.mst&sTime=0
これが非常に近い。しかも特許成立している。でも微妙に違う。
請求項の「極大となる索引要素全てを格納」というあたりが。
セーフ。。かな。

mecab悪戦苦闘中。妙に大きなパッチに。。
もっとスッキリかけないのかなぁ。
C++の言語仕様に翻弄される日々。

mecabのmt安全化ようやく出来た!! 一週間ぐらいかかった。。
.hファイルに関数実体を書くスタイルとかどーもキモくてたまらん。。＜C++
なるべくパッチのサイズを小さくするように心がけたんだけど、
500行ぐらいになってしまった。これは本家には取り込んで貰えないかもだなー。。

うわああああ。。
なんかすごい勢いでほげってる人がぁぁ。。
http://blog.yappo.jp/yappo/archives/cat_searchdev.html

MLとか整備して、ちょっとOSSっぽくなってきたカモ。

wikiで書いたドキュメントをhtml化しつつdev.razil.jpに取り込むようなことしたいなー。
ついでにRSSも生成できると良い。htmlレンダリングエンジンだけ取り出せると良いのだが、、qwik。

またmecabのバグを拾った。
freeのタイミングでsegfaultになるので、バッファオーバーフローかなあとアタリをつけて解析。
この手の障害は、原因となる箇所と症状が起こる箇所が一致しないのでなかなか厄介なのです。
特定のデータで症状が再現するので、データの中身をいろいろいじくってみたら、
どうやらデータ長がちょうど16384の倍数の時に発生することが分かった。
それらしい箇所をしらべてバッファ拡張時の境界条件判定が甘いことをつきとめた。
パッチを作者に送付。苦労のわりには変更箇所は1byteのみ。
うーん。細かいパッチがんがん送って来てウザい奴だと思われてるかも。。

わーい。mecab作者から反応あったよ。本家に採用されるかも。
http://tahoo.org/~taku/ml/mecab/msg00157.html

なんか大人気ですね。ML

パッチ送って貰えるのはホントありがたいっすね。
M川さんとNやさんに紹介してもらったのが相当効いてるっぽい。

またスゲー優秀な人がG社に引き抜かれる。
知合いばっかり、もう3人目。激しく鬱。

mysql+sennaで更新が遅い遅いと思っていたら、元々のmysqlのfulltext indexの更新がネックだった。
これを外すと1.5時間かかっていた更新処理が、20分に短縮できた。一安心。

わー渋谷に引き抜かれるのは誰ですか誰ですか？

め、めっそうもない。。
かれのなまえをここで明かすなんて、
ぶれいなことは僕にはできないっす！！

つまり、上戸ソマ子か！
# 斜めのイレレ！

stackに大きめの領域(4KB程度)を取る関数に入った時点でmysqldがsegfaultで落ちる。
setrlimitでRLIMIT_STACKを拡張しても効き目なし。
なんだこれは。。うーんうーん。。

mecabパッチ、gcc3.4.2だとダメらしい。静的オブジェクトのコンストラクタ問題っぽい。
http://www.mozilla-japan.org/hacking/portable-cpp.html#dont_use_static_constructors
こんなの全部守れないよー。。やっぱc++キライだ。

いつのまにかmysql+sennaでレプリケーションできてるような。。
しかしよくよく考えるとそんなに使い道なさげ。

ええ、できたほうがいいっですって＞レプリケーション。
俺だったら絶対使う・・・。

t社環境で同時に複数の更新処理を走らせてたらsegfaultで落ちた。
d社の打合せ最中にそれに気づき、人知れず打ちひしがれてしまった。

救えないor救うのが非常に困難な検索洩れパタンに気づき、
またまた打ちひしがれてしまった。
lexiconからcommon prefix searchしてlatticeを作って
全パタンを照合すれば理論的には救えるが、コスト高すぎかも。(実装も大変)

全文検索完了後、結果をmysqlに引き渡した後に発生するfull table scan を抜本的に回避できない。
もっと密にmysqlと結合しないと無理なのかも。。

mysqlとsennaとのメモリの使用モデルの差に悩む。
mysqlは非常に禁欲的で、sennaは富豪的。
論理空間をたやすく枯渇させるsennaの実装をmysqlの作者が見たら、気を悪くするに違いない。
それなりのbufferを持たないと広大なinverted indexへのランダムな更新をまともな時間でさばけないんすよぉ。。
やっぱprocessを分けてメモリ空間を独立にするべきなのか。。

更新処理中のsegfaultはなんとかつぶしたい。
とりあえず再現はできるようになった。
thread_stackを拡張しても転置ファイル更新バッファを減らしても再現する。
さーてどうやって解析するか。。

>>58
もしかして根本的なアーキテクチャの変更っすか？

SQLあきらめちゃえ。

segfaultのバグつぶしたーーー！！
またmecabのバグでした。。
一旦unmapした領域が、destructorから再度unmapされるため、

スレッド1がunmap
↓
スレッド2がmmap(たまたまさっき解放したアドレスにmapされる)
↓
スレッド1がそのアドレスを再度unmap
↓
スレッド2がその領域にアクセス
↓
あぼーん

となっていた。c++のdestructorって、ホント余計なお世話だよな。キライだー。

マルチスレッドのデバッグって結構大変。今回も丸一日かかった。。
しかしまたパッチはまた１行だけだ。。

>>60
いやいや。プログラムへの変更はそんなに大きくないですよ。
インタフェースの切り方を変えてプロセス構成をいじるだけ。

>>61

SQL以外の選択もできるようにしたいす。
何か適当なストレージエンジンとクエリーエンジンないかなー

>>56 の問題に
現状の実装である程度対処するためにインデックスをいろいろ操作中

>>57 について
実践ハイパフォーマンスSQLを読んでいたらこんな一文が。。
「MySQLでは、1つのクエリを実行する時、1つのテーブルにつき1つのインデックスしか使用できない」
なん、だっ、てぇーーー
つまり、フルテキストインデックスを使用するクエリでは、
ソート処理にその他のインデックスを一切使用できないってことだ。
んー。。なんか抜け道がないかな。。

apr(http://apr.apache.org/)を採用すべきかどうかについて迷っています。
動的リンク前提になると多少性能劣化があるかなぁとか。。
ループの内側からライブラリ跨りで関数を呼び出さないように注意すれば問題ないかなー。

mysqlでマルチカラムのフルテキストインデックスを張った場合、
カラム値が空白なしに連結されて格納されていたためにただしくマッチングできなくなっていた。
('ymo','ymo','ymo'が'ymoymoymo'と連結されるので)
とりあえずカラム値間に空白を入れて対処。。
でも、「ペリンレッド」で「レッドツェッペリン」がマッチするなどまだ改善の余地があるのは秘密だ。

2ch検索用というわけではないのだが、1文書が複数の短いパラグラフの集合から成り立っているような構造をうまく扱うために、文書番号とセクション番号の両方を管理できるように設計している。その分の転置ファイルサイズの増大を抑えるために、tf情報とscore情報を併せて1byteにパッキングしてしまうのはどうだろうかと思い付いた。tf<=scoreが常になりたち、tf==scoreである場合が非常に多いので、
n = score * (score + 1) / 2 + score - tf
によって算出される数値nを更にber圧縮する。
すると、score=tf=16 までは1byteに格納できる。これぐらいの範囲に収まるケースが大半だから、圧縮効果はそれなりにありそう。
問題は復号化時に平方根を算出しないといけないこと。平方根算出とδ圧縮符号の復号化とどっちがCPUコストが低いだろうか。

セクション情報をコンパクトに詰め込むためのインデックス構造の改造作業中。bit単位でデータをやりくりする地道なこの作業ってドット絵描くのと近いノリなのかも。(描いたことないけど)

sennaのインデックスファイルは基本的に圧縮をかけてあるのですが、更新処理を高速化するために非圧縮のバッファ領域を持っています。バッファの中身は検索時に毎回ソートしているのですが、これがイマイチな気がして来ました。線形リストだったのをスキップリストに変えようかと検討中。

値域が予測しにくいデータ集合でもうまく動作し、メモリ効率も良さげなスキップリストのアルゴリズム思い付いた。ただし実装が複雑そう。またエンバグしたら鬱だしなー。。でもやるなら今のタイミングしかないかー。。やろう！

アラインメントの関係でまたしても空間効率が低下することに気づいて鬱。bit単位のやりくりモードにまた逆戻り。

わー、森さんの顔だらけだ。

新しいアルゴリズムを転置ファイルのモジュールに組み込み中。
大きな一つのモジュールなので単体試験がやりにくく、長い暗いトンネルの中を通っているような苦しい状況。

まるで人生。＞長い暗いトンネルの中を通っているような

今後こっちに書くです。
http://d.recommuni.jp/senna/

あれ？？ ブログ、メール経由でかけなくなっちゃたよ。。
しょうがないのでこっちに書くです。。

------------------------------------------
けっこう大規模な改造だったのだが、単体試験が概ねすんなりと通過。すげー意外。
スキップリストも想定した通りに動作している。
昇順/降順/ランダム順のいずれで登録しても
ほぼO(logN)程度のステップで探索可能なバランスの良い構造ができている。

しかし、転置インデックスのサイズは残念ながら若干増大してしまった。
新たな情報(段落情報)を追加しているのだから仕方がないと言えばそれまでなのだが‥

次はいよいよ検索モジュールとの結合。

結合済んだ。検索がすごく速くなった！！ かなり嬉しい！

くわしくはこっち
http://d.recommuni.jp/senna/AC_20098

わーパチパチパチ(拍手)。T社のやつに入れたら効果ありますくわ？

あると思います！ でもまだMySQLと結合しての安定化試験してないです。

いまAPIの見直し中。sectionを導入したことによって思ったよりいろんなことができそう。
xpathエンジンと組み合わせれば、本格的なXML検索エンジンとかできそうな気もするのでそこら辺も見据えて設計してます。

森サン、さっきメッセ返事できなくてスマソ。
xpath、結構やったですよ。なんか出来る事あったら声かけてくださーい

ぼ、ぼくはゆげっすよ

グループ化した結果を取得する関数の仕様だけが
どうしてもスッキリ決まらない。うーんあと一歩なのに。
これが済んだらフタ開けよう。。

API決めました。要件を欲張りに設定したので、かなり悩んだけど、使いやすさと機能性と性能となんとか折り合えるものになったのではないかと思ってます。
あとは実装するのみ。。(未実装関数があと23個)

18個実装した。あと5つ。。

あと3つ。1個の関数でもうひと山越えないといけないのを思い出した。。またbinary heapでしのごう。

ゆげげ。

あと2つ。。

あと一つ。。最後の関数は、
sen_rc
sen_index_select(sen_index *i, const char *string, sen_records *r, sen_sel_operator op, sen_select_optarg *optarg)
こんなの。

最後の関数が一応形ができたので、SVNコミットした。
コンパイルは通したけど試験してないから不安。
まだ、類似文書検索、近傍検索、段落単位検索といった検索オプションを実装してない。

基本APIに関しては簡単にインデクシング／検索の試験をしてみた。
とりあえず問題なく動いている。
次は高度APIの試験。こっちは全く無問題とはいかないだろうな。。

と思ったらやっぱエンバグしてたよ。
検索結果数を出すまでは良かったんだけど、
各検索結果を取り出す関数がバグってた。

ま、こんなのは序の口だな。。(←開きなおってどーする)

見っけ
http://pc8.2ch.net/test/read.cgi/php/1118762053/
ちょうどLGPLの話が出ててタイミングいい感じ

http://blog.yappo.jp/yappo/archives/000258.html
MLでそれとなくフォローしてみました。
こういうtipsも文書化しないとなぁ。。

おひょ

todo

- sen_select_optargの未実装オプション対応(mapper, near, similar)

- utf8, sjisサポート強化

- bit数え上げ, 冪乗切り上げ算出アルゴリズム修正

- 高度APIの仕様書更新

- 高度APIの網羅的なテスト/性能計測

- MySQL組み込み(高度API対応版)

検索系の拡張機能も全部実装した。類似検索とか近傍検索とか。テストしてないけど。

「ハッカーの楽しみ」に載ってたbit数え上げアルゴリズムを組み込んでみた。それ自体は速いんだけど、hotspotじゃないから全体の高速化にはあまり寄与しない模様。残念。

100ｹﾞﾄｫｫｫｫｫ

スキップリストのところでバグ入れてまして、更新中に無限ループに陥る事象に苦しみました。大体治ったと思うんだけど。。

"空閑"で検索すると"空"で検索したのと同じ結果になってしまう。苦しんで切り分けた結果、mecabの辞書によって"閑"を空文字に解析してしまうことが判明。ipadicでは問題ないが、juman-dicだと発生する。
とりあえずipadicに入れ替えて再インデックスかなぁ。。
T社環境はたまたまipadicだったので助かった。

スキップリストがループしそうになるバグを一個とった。

log rotateする処理がthread unsafeだったバグを取った。でも、mysqlをstallさせるバグがまだ残っている。。

最後のバグに苦しみ中。再現条件が不確定で非常に厳しい。不確定な振舞から推して、ヒープの管理あたりに原因があるのかもしれない。地道にassertionを組み込んでみる。

sennaに関して設定したマイルストーンをクリアしたら次こそはフタを開けようと心に決めていたのですが、クリアすればしたですぐに次の課題が持ち上がる。どうやら永遠にフタを開ける日は来ないということに気づくのに半年以上かかりました。。orz

xango環境ではかれこれ10日ほど無問題で動作しているsennaですが、別のところで実施している高負荷試験で新たなバグが出ました。再現手順確立中。

memory leakが2箇所ほどあったのを取りました。

unicode正規化を実装した。けっこー苦しんだ。。
ICUと比べてサイズは1/10以下、実行速度は7倍近い。

utf8対応版をリリースした。
次はbooleanモード。
新しいAPIの安定性を見極めてからじゃないとリリースするのが恐いけど。

Thank you! http://bmnxyhbb.com/zarm/tvwb.html | http://iqmxgclx.com/lnuz/fhkj.html