開発メモ: IndexDB: 転置インデックスのためのDB
大震災の時分に何だが、Kyoto Cabinetベースで検索エンジンの核となる転置インデックスを作るのに適したDBを実装したという話。 転置インデックスとappend操作 多くの検索エンジンの核となる転置インデックスとは、検索語に一致する表現がどこに出てきたかという位置情報のリストを保持するものであり、検索語をキーとして位置情報リストを値とする連想配列である（転置インデックスを使わない検索エンジンもあるが）。この位置情報リストをposting listとか呼んだりするらしい。転置インデックスにもいくつか流儀があり、検索語をどのように切り分けるかで単語（分かち書き）方式とか文字N-gram方式とか呼ばれるものがあったりするが、いずれにせよ、小さいキーと、非常にでかい値を保持する連想配列を作ることには変わりない。 で、素朴に転置インデックスを作ろうとすると、検索対象の文書を解析しながら、得られ
開発メモ: Kyoto Cabinetのロック機構の改善
Kyoto CabinetはIO負荷が高い場合にCPU負荷も高くなりがちだという指摘を受けて、それを解決すべくロック機構を見直したという話。 スロットロック ハッシュテーブルの操作はハッシュバケット毎に完全に独立して実行できるのが強みだ。ハッシュテーブルは計算量が有利なだけでなく、並列性にも優れるということ。実際には下層のファイルIOで実装依存の排他制御が行われることになるが、ハッシュ層だけ見れば理想的な並列性を備えている。ただし、同じバケットに連なるレコード群の操作は互いに依存関係があるので、それらは一括して排他制御してやる必要がある。となると、バケット毎にロックを用意するのが理想だが、実際にはメモリを節約するために、予め決めた数のロックを用意して、ここのロックに複数のバケットを割り当てる構成をとる。リソース空間をスロットに分けるというイメージから、これをスロットロックと呼ぼう。 スロッ
開発メモ: もし自営業の男子プログラマがKVSで「ブログサービス」を書いたら
Webサービスの典型例でありCMSの典型例であるブログサービス。それを実装するための指針が示せれば、その他のサービスを開発する際にも大いに参考になることだろう。 データ構造 単純なブログサービスのデータノードとしてKyoto Tycoonのサーバ群を用いることを想定する。ブログの個々の記事は以下の属性を持つものとする。 著者のユーザID（uint32） 投稿日時（uint32） 題名（text） 本文（text） コメントリスト（シーケンス） 各コメントは、コメントした人のユーザIDと本文からなる データノードに対する問い合わせは、「あるユーザの最新記事を降順で5件くれ」というのが典型である。「降順で」という順序に対する要求があるのでB+木を選択し、連想配列のキーは、ユーザIDと投稿日時を連結したものとする。単純化のために、各々を10桁の10進数文字列をコロンで区切って並べて、全体で21バ
Kernel/VM Advent Calendar ４日目: Linuxのネットワークスタックのスケーラビリティについて - syuu1228's blog
【お願い】私はLinuxカーネルもネットワーク周りも素人です。ここに書いてある事は間違えている可能性もあるのでおかしいなと思ったらすかさず突っ込んでください。宜しくお願い致します。 今回は、この記事の内容を全面的に見直して、再度Linuxのネットワークスタックのスケーラビリティについてまとめようと思います。 従来のLinuxネットワークスタック＋従来のシングルキューNIC 以下の図は従来のLinuxネットワークスタック＋従来のシングルキューNICで、あるプロセス宛のパケットを受信している時の処理の流れを表している。フォワーディングの場合やプロトコルスタック内の処理は割愛した。 プロセスがシステムコールを発行してからスリープするまで プロセスは、システムコールを通してカーネルにパケットを取りに行く。 パケットはソケット毎のバッファに貯まるようになっているが、バッファが空だったらプロセスはパケ
開発メモ: memcachedプロトコルをKTにプラグインする
高効率キャッシュサーバ兼データベースサーバであるKyoto Tycoonのネットワーク通信機構をプラグインで切り替えられるようにして、memcachedプロトコルにも対応したというお話。 プラガブルサーバ Apacheは、様々なモジュールを後付けのプラグインで組み込むことで、非常に柔軟に機能追加を行えるようになっている。MySQLもストレージエンジンをプラグインで切り替えられるようになっていて、非常に柔軟なソリューションが提供できるようになっている。そのようなプラグインできるモジュールをプラガブルモジュールと呼ぶことにしよう。 同じように、KTでもストレージエンジン（DBM層）をプラガブルモジュールにする予定ではあるが、今回はストレージエンジンの話ではない。逆に、ネットワーク層をプラガブルモジュールにしてしまうのだ。そうすると、任意のプロトコルでデータベースを操作できるようになる。 DBM
Transport Layer Security (TLS) False Start
Transport Layer Security (TLS) False Start draft-bmoeller-tls-falsestart-00 Abstract This document specifies an optional behavior of TLS implementations, dubbed False Start. It affects only protocol timing, not on-the-wire protocol data, and can be implemented unilaterally. The TLS False Start feature leads to a latency reduction of one round trip for certain handshakes. Status of this Memo This I
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： 見るバイトに関
ソーシャルゲームのためのMySQL入門 | BLOG - DeNA Engineering
こんにちはこんにちは。最近お腹痛いばっかり言ってることで有名なiwanagaです。 DeNAは外部的にはプラットフォーム的な部分の方がフィーチャーされることが多いですが、実はソーシャルゲームの提供も行っています。怪盗ロワイヤルとか、どこかで聞いたことがあるのではないでしょうか。 僕はDeNAでソーシャルゲームが誕生した辺りからずっとサーバサイドを見てきましたが、そんな運用の中で自分が貯めてきた知見とかTIPSをご紹介したいと思います。 かれこれ10タイトル近くはレビューしたり運用したりしてるため結構言いたいことはいっぱいあるので、小出しにしつつ評判よければ次も書きます。 ソーシャルゲームのためのMySQL入門一覧 ソーシャルゲームのためのMySQL入門 - Technology of DeNA ソーシャルゲームのためのMySQL入門2 - Technology of DeNA 「MySQL
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
NVIDIA Networking Solutions
One-third of the 30 million data center servers shipped every year are consumed by the software-defined data center stack. To support heavy data center workloads, enterprises need to modernize their network infrastructure and evolve to keep up with the exponential demand for data processing. NVIDIA offers InfiniBand- and Ethernet-accelerated networking solutions, providing enterprises with the inf
Technical Memo: Memory Saving Associative Array by Kyoto Cabinet and MessagePack
Kyoto Cabinet features on-memory database which can be used as associative array of strings. MessagePack is a binary-based efficient object serialization library. Combination of the two provides you associative array to contain generic objects. Space Efficiency of Kyoto Cabinet Let's suppose that we should manage 1 million simple records whose key and value are 10 bytes strings. The following is a
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
Fusion-ioのCOO・スミス氏、SSD「Fusion-io」の技術的特徴を解説 | エンタープライズ | マイコミジャーナル
フュージョンアイオーは10月15日、米Fusion-io COOのランス・スミス氏、ワールドワイド・セールス シニア・バイスプレジデントのジム・ドーソン氏の来日に合わせて、記者説明会を開催した。説明会では、両氏が同社の製品の特徴について解説したほか、デルよりFusion-io製品を搭載した同社サーバの検証結果が発表された。 米Fusion-io COO ランス・スミス氏 同社は、PCI Expressカード型SSD「ioDrive」と「ioDrive Duo」を開発・提供を行っている。両製品の特徴はNANDフラッシュメモリを搭載することで、ストレージにおけるI/O処理のボトルネックを解消している点だ。 スミス氏は、同社の製品はNANDフラッシュメモリが抱える「データの書き込み回数に限界がある」、「データロスのおそれがある」、「データが誤って書き換えられるおそれがある」といった課題を解決して
SolarisのネットワークスタックってSMPに強いのん？ - syuu1228's blog
「SolarisのネットワークスタックはSMPに強い」という噂を聞いていたので、取り敢えずどんな感じなのか資料を斜め読みしてみた。 Solarisとか全ッ然知らないので、間違ってたらツッコミ下さい。 資料： Oracle and Sun Microsystems | Strategic Acquisitions | Oracle OpenSolaris 最新動向とプロジェクト Crossbow の威力 1990年代後半以降、サーバーは、多数の CPU を実行する SMP ベースになった ミッドエンドマシンからハイエンドマシンが NUMA 主体となったため、CPU の切り替え処理のコストが高くなった 従来のSolarisのTCP/IPスタックの問題点 設計上 CPU と密接に関係していないため、特定の接続のパケットがさまざまな CPU の間を移動してしまう マルチスレッドには対応している
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
The DNSSEC Diaries, Ch. 6: Just How Much Should We Put In DNS?
PVFS.org
如何在TILEPro64多核心板卡上编译和运行Erlang | 系统技术非业余研究
https://www.inf.puc-rio.br/~roberto/talks/lua-ll3.pdf