開発メモ: IndexDB: 転置インデックスのためのDB
大震災の時分に何だが、Kyoto Cabinetベースで検索エンジンの核となる転置インデックスを作るのに適したDBを実装したという話。 転置インデックスとappend操作 多くの検索エンジンの核となる転置インデックスとは、検索語に一致する表現がどこに出てきたかという位置情報のリストを保持するものであり、検索語をキーとして位置情報リストを値とする連想配列である（転置インデックスを使わない検索エンジンもあるが）。この位置情報リストをposting listとか呼んだりするらしい。転置インデックスにもいくつか流儀があり、検索語をどのように切り分けるかで単語（分かち書き）方式とか文字N-gram方式とか呼ばれるものがあったりするが、いずれにせよ、小さいキーと、非常にでかい値を保持する連想配列を作ることには変わりない。 で、素朴に転置インデックスを作ろうとすると、検索対象の文書を解析しながら、得られ
Kernel/VM Advent Calendar ４日目: Linuxのネットワークスタックのスケーラビリティについて - syuu1228's blog
【お願い】私はLinuxカーネルもネットワーク周りも素人です。ここに書いてある事は間違えている可能性もあるのでおかしいなと思ったらすかさず突っ込んでください。宜しくお願い致します。 今回は、この記事の内容を全面的に見直して、再度Linuxのネットワークスタックのスケーラビリティについてまとめようと思います。 従来のLinuxネットワークスタック＋従来のシングルキューNIC 以下の図は従来のLinuxネットワークスタック＋従来のシングルキューNICで、あるプロセス宛のパケットを受信している時の処理の流れを表している。フォワーディングの場合やプロトコルスタック内の処理は割愛した。 プロセスがシステムコールを発行してからスリープするまで プロセスは、システムコールを通してカーネルにパケットを取りに行く。 パケットはソケット毎のバッファに貯まるようになっているが、バッファが空だったらプロセスはパケ
epollのなかみ - moriyoshiの日記
よく C10K 問題とかいって epoll(7) の話が出てきて select(2) 遅いね poll(2) 遅いねってなるんだけど、正直なところ、これらのシステムコールを実際に使ってコードを書いてみたひとはどのくらいいるのだろう。ましてや eventpoll が何やってるか知っている人はそんなに多くないんじゃないだろうか。もう O(n) だの O(1) だのって煙に巻かれるのもうんざりだ。 というわけで、2.6.26 の fs/eventpoll.c のコードを読んでみた。正直 Linux カーネルにすごく詳しいわけでもないので、誤りがあったら適宜突っ込んでもらえると幸いです。 前提知識として VFS モジュールがどうなってるかとかは LinuxのFSモジュールを書いてみる LinuxのFSモジュールを書いてみる (その2) のソース中のコメントを追ってもらえればと。 登場する構造体 e
インテル・AMDのCPUアーキテクトが明かす： GNU grep が速い理由 - karasuyamatenguの日記
GNU grepの元祖作者がFreeBSDハッカーをschoolしている。 http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html FreeBSD対GNU grepのパフォーマンスを議論していると思われるとことに「俺はgrepの初代作者だ」と名乗って現われた男がいる。 履歴書(http://duckytech.com/resume.pdf)を見ると、GNU coreutilsに貢献した後、インテルやAMDでCPUアーキテクトを勤めている男だ。これは話を聞いた方がよさそうだ。 FreeBSDユーザでもある彼はリストを観閲していたらたまたまGNU対BSDのgrep論争に当ってしまったようだ。BSDのリストにGNU grepの秘密を解く。 技1： 全ての入力バイトを見ないから速い 技2： 見るバイトに関
AppEngine/Jのspin-upを劇的に改善する方法 - ひがやすを技術ブログ
AppEngineは、アクセスがあったときにアプリケーションを起動し、しばらくアクセスが無ければアプリケーションを終了させ、また次のリクエストで再起動するという仕組みを導入しています。 そのため、アプリケーションを起動(spin-up)する時間がとても重要になってきます。このspin-upの時間はpython(webapp)で60cpu_ms以下。(cpu_msはcpuが使う仮想的な時間ですがmsと同じ感じで捉えてもらってもとりあえずは大丈夫です)JavaのServletだと600cpu_msくらいです。PythonでもDjangoような大きなフレームワークだと1000cpu_msくらい(アプリによる)かかりますが、許容範囲内。JavaだとSlim3で1300cpu_ms、Springだと早くて7000cpu_msという感じで、Slim3がギリギリ許容範囲内でしょうか。ほんとうは、1000
The LuaJIT Project
This is the common project page for: LuaJIT — a Just-In-Time Compiler for Lua. Coco — a Lua extension for True C Coroutines. DynASM — a Dynamic Assembler for code generation engines. Lua Bitop — a Lua extension for bitwise operations on numbers. Privacy Policy This website does not request, store or process any private data. This website is fully static and does not allow entry of personal informa
Using MySQL as a NoSQL - A story for exceeding 750,000 qps on a commodity server
UPDATE: Oracle officially released memcached daemon plugin that talks with InnoDB. I'm glad to see that NoSQL+MySQL has become an official solution. It's still preview release but will be very promising. Let's try it to make it better! Most of high scale web applications use MySQL + memcached. Many of them use also NoSQL like TokyoCabinet/Tyrant. In some cases people have dropped MySQL and have sh
NoSQLの成功は1:10問題にかかっている:Kenn's Clairvoyance
ここ2-3年ほど、いわゆる非SQL系データベースがホットな話題になってきています。このムーブメントを総称して「NoSQL (Not-only SQL)」と呼ばれることが多いようです。まるでSQLを否定しているかのような誤解を招きやすい用語ですが、かといってキー・バリュー型データストアや列指向DBを総称できる他の呼び方もないので、このエントリではNoSQLという用語を使うことにします。 OracleやMySQLなどのSQLデータベースが成熟していく一方で、SQLデータベースを特徴づける弱点である柔軟性のなさ、堅牢さと引き換えに犠牲になった更新性能の低さ、スケールアウトの難しさなどから、「何でもかんでもRDB」から「目的に応じた永続化」が模索される流れになってきました。 時を同じくして、キャッシュサーバの世界でも、MemcachedのもつシンプルなAPIの使いやすさが評価される一方、LRUによ
今のJVMに欠けている物
原文: チャールズ＝オリバー＝ナター 今日ツイッターで、「JVM及びJDKが、あらゆるプログラミングにおいて真にイケてるプラットフォームになる為には未だ幾つかの欠陥が有る」と呟きました。沢山の人から「もっと詳しく」とせっつかれたので、ここに短く書き起こしておきます。勿論、これで全部という訳ではないのでしょうが、今日思いついたのはこれだけです。 ゼロから起動する際のパフォーマンス現存するJVMの起動はかなり速いですが、Java 7でのHotSpot（訳注：Sun及びオラクルのJVM）にはこれをより良くする為の改良が盛り込まれています。普通、こういった改良は、バイトコードを予め検証したり（或いは検証の為のヒントを与えたり）、クラスデータを幾つかのプロセスで共有したり、在り来たりではありますがプログラムのロード時間やリンク時間を短縮する工夫を凝らす事で成し遂げられます。ところが、多くのアプリケー
漢(オトコ)のコンピュータ道: InnoDBでCOUNT()を扱う際の注意事項あれこれ。
InnoDBを使うとき、MyISAMと比較して度々やり玉に挙げられるポイントとして「COUNT()が遅い」というものがある。確かにInnoDBにおいて行数を弾き出すのにはテーブルスキャンが必要なのだが、そもそもMyISAMのCOUNT()が速い（テーブルの行数を保持してる）のが特殊なのであって、InnoDBが遅いわけではないのである。とはいえ、高速なCOUNT()については需要が多く、この問題には多くの人取り組んでおられるようだ。しかしながら、COUNT()のチューニングについては未だ語られていない点があるように見受けられるので、今日はCOUNT()のチューニングについて解説しようと思う。 COUNT(*)、COUNT(col)、COUNT(1)の違い基本的なことではあるが、COUNT(*)とCOUNT(col)では意味が異なるため、異なる結果が返される場合がある。COUNT(*)はフェッ
140行で作る分散リアルタイム検索エンジン（Twitter Streaming API対応） - 古橋貞之の日記
マトモに使えるRPCライブラリ MessagePack-RPC for Ruby のバージョン 0.2.0 をリリースしました！ 新たにコネクションプーリングの機能を追加しました。一度接続したコネクションを共有して使い回すことができます。コネクションを何度も張り直す負荷と遅延を削減でき、リソースの消費も抑えられます。 また、不意に切断されたコネクションを自動的に再接続する機能を導入し、信頼性を向上させています。 これを使って何か作ってみようと言うことで、twitterのリアルタイム検索エンジンを作ってみました。日本語を検索できないなど機能は貧弱ですが、プログラム全体がわずか140行に収まっています（クローラ27行、インデクサ48行、クラスタ管理ノード37行、検索クライアント28行）。 新しいつぶやきを受信するたびに、リアルタイムで転置インデックスを作成していきます。インデックスを作成するノ
Schemeで信号処理 - .mjtの日記復帰計画
先日、1日でCODECを書けるか(Schemeで)というネタをやって、VorbisとSBC*1を実装してみた。細かい報告は後で(修論に)書くけど、結局実時間の50倍とか掛かるのでリアルタイムデコードは出来なかった。 パフォーマンス劣化の基本的な要因はバッファを共有できずにメモリを大量に確保することにあるように観測された。つまり、プロファイラを使うと殆どBoehm GCの中で時間を使っているように見える。 SBCのデコーダのうち、"波形の合成"はこんな感じになる。 http://gist.github.com/247737 たった130行！ 実は、音声CODECのデコーダを実装するにあたっては、面倒な仕事の殆どはエントロピ圧縮のデコードとパケットのパースに有って、音声圧縮のコアであるところの周波数変換とか音声符号化はそれほど面倒でも無い。 このコードは非常に大量のメモリを"使い捨て"にしてい
Google App Engine入門：実行効率を犠牲にせずに開発効率だけを上げるテクニック
一つ前の富豪プログラミングのエントリーともつながる話だが、Google App Engineは「ちゃんとスケーラビリティを考慮してアプリケーションを作るには何に気をつけなければならないか」を勉強するには絶好の環境だ。そこで今回は、その「ケチな大富豪的なプログラミング」の実践編。 Google App Engine上のアプリをいくつか書いているうちに、必要に迫られて自然発生的にできてきたのが、gdispatchという数十行のコードからなる小さなモジュール（ソースコードはgithubに置いてある）。これをGoogle App Engineに標準で付いて来るwebappと組み合わせてフレームワークとして使っている。 gdispatchを設計する上で重視したのは、 （１）Google App Engine上でのアプリの開発を効率化する上で「明らかにこれがあると開発効率が格段に向上する」というもの以
L'eclat des jours(2009-11-10)
_ でっかなバッファを避ける? Aleviating Memory Fragmentation in Mono コンパクティングしなければ、いやでもフラグメントがどかどかできる。 するとでっかなバッファを取ろうとすると新しいページの割り当てが必要となりプロセスが肥大する。 だからでっかなバッファを要求すんな。細切れ継ぎ合わせメモリーストリームを使え。 と読んだ。 細切れ継ぎ合わせ方式だと実際のバッファへのポインタ分だけ余分なメモリを食うわけだし、次の細切れへの移動にオーバーヘッドがかかるわけだが、それを補ってあまりある恩恵が得られればOK。 （ここで、「さっそく試してみる」といかないところがだめなところだ）
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
MySQL Clusterが苦手とするJOINを如何にして克服するべきか。
シェアードナッシング型の負荷分散機能を持ち、なおかつ同期レプリケーションによるHA機能まで備えたMySQL Cluster最大の弱点といえば、JOINの遅さであろう。MySQL ClusterのJOINは偽りなく遅い。JOINを多用するアプリケーションでMySQL Clusterを利用するのはある意味マゾヒスティックな行為であると言えよう。何故MySQL ClusterはJOINが遅いのか？それはMySQL Clusterが分散データベースだからである。 ご存じの通り、MySQLにおけるJOINのアルゴリズムにはNested Loopしかない。他のストレージエンジンを利用していればそれでも十分実用に耐えうるぐらい高速なのだが、MySQL Clusterの場合はそうはいかない。JOINでは自ずとストレージエンジンからデータをフェッチする回数が増えるが、MySQL Clusterの場合レコード
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
如何在TILEPro64多核心板卡上编译和运行Erlang | 系统技术非业余研究
The MySQL “swap insanity” problem and the effects of the NUMA architecture
Node crashing handling and VM statistics | ioremap.net | Page 454
f-zipper-with-pipe-forward