デバイスを直接読み書きする意味は、自前でキャッシュ機構を持っている場合に、ファイルシステムのキャッシュメモリを節約することにあるんだろうけど、その目的だったらopen(...,O_SYNC) でいいはずだよね。

posted at 20:30:43

ということで、いまのところ、ブロックデバイスを使う意味はほとんどないと思っている。扱い難さ1000%のわりに、スループットはほんのちょっとしか向上しないからだ。

posted at 20:20:40

ブロックデバイスにマップした領域を madvise(..., MADV_WILLNEED) しておくとファイルシステムよりほんのちょっと早くはなるっぽい。ただ、madvise自体にすげー時間がかかる。

posted at 20:18:55

ブロックデバイスをmmapして直接読み書きするようにしてみたが、かえって遅くなった。ext2上にDBファイルを置くと100万qpsで書き込みできるが、それをHDDのブロックデバイスでやると50万qpsになっちゃう。意味ねー。

posted at 19:57:58

トランザクションなしで100万qpsなので、自動トランザクションの性能限界は30万qpsくらいじゃないかな。レコード本体のwriteに加えて、WALのための古いレコードのreadとWAL自体のwriteが入るので。よって、現状でかなり最善に近いところまで来ていると思う。

posted at 17:36:08

KC-0.5.14リリース。自動トランザクションモードの性能がさらに倍化し、挿入で28万qpsくらい出るようになった。

posted at 17:31:51

予算シートを書くというなんだか面倒な業務なう

posted at 17:20:38

1億レコードでもキャッシュに載せると書き込み121万qps、読み込み400万qps。もちろんマシン1台でDBファイルも1個。書き込みが遅くなるのは、ある程度時間がかかるテストだと途中でpdflushが走ってしまうため。

posted at 15:07:50

ていうかこのXeon E5540のマシンがすげー早い。KCを4スレッドで動かすと書き込み280万qps、読み込み400万qpsくらい出る。

posted at 14:50:25

fusion-ioの早さが鬼神級。KCへの1億レコードの挿入がHDDで16084秒（6217qps）のところ、fusion-ioだと255秒（392156qps）。キャッシュに乗せない状態で40万qps近く出るってのはすごいぞ。大抵のサービスで分散コストを抑制できる。

posted at 10:55:03

朝青龍→朝赤龍→朝緑龍→朝銀龍→朝金龍→朝プラチナ龍→朝サファイア龍→朝ルビー龍→朝エメラルド龍→朝ダイアモンド龍（ボス）→真・朝青龍（裏ボス）→滅・朝青龍（外伝）

posted at 10:13:03

さて、存在しない領域の長さが0であるという期待は自然だろうか？ 非存在と長さ0の存在が同一視されるべきだという類の「ありがちな誤謬」に基づく期待とどう共存すべきだろうか。

posted at 09:50:48

一方で、良い仕様とは、利用者（ライブラリの場合はアプリ実装者）の自然な期待から乖離しないものだ。驚き最小の法則。だから仕様が決まる前に普通のアプリ実装者の思考を汲み取っておきたい。

posted at 09:41:24

良い実装とは、仕様に準拠して意図通りに動作する実装だ。だから仕様に書いてない論理的に未定義な実装に対しては、実装者に非があるとみなしてよい。

posted at 09:36:31

@kunzo 米国銘柄を買っている身としては辛い。円下がれ～。

posted at 09:19:16

./kcutiltest file -th 4 -rnd -msiz 1m casket 10000

posted at 08:53:11

TODO: トランザクション開始時の同期処理を削る

posted at 00:11:50

いまこそ商用ライセンスを作るかなぁ。1アプリあたり50000円くらいとれるかな？ それなら30ライセンス売れれば庭を1坪増やして向日葵とか植えられるぞ。

posted at 22:22:37

iPhoneでTCが使えるらしいのだが、iPhoneにダイナミックリンク機構がないから静的リンクでTCを配布せざるを得ず、そうするとクローズドソースなアプリを配布できなくなるとのこと。

posted at 22:18:00

いいと書いてないときはダメの法則からいくと、fsyncじゃないとダメって判断をするのが妥当か。

posted at 21:56:10

ftruncateの結果をディスクに書くにはfdatasyncでなくてfsyncじゃないとダメだとmanに書いてある。では、writeによってファイルサイズが変更された場合もfsyncじゃないとダメ？

posted at 21:47:51

その点では、constだからって並列呼び出しして大丈夫との期待に基づいてコードを書くのも危険。並列呼び出しして大丈夫って書いてないものを並列呼び出ししたらその挙動は未定義。といいつつ std::map::find const を呼んじゃってるとこがあって、寝る前にうなされる。

posted at 21:17:29

「エラー時にsizepの変数に0を代入する」って仕様に書いてあるならそうしていいけど、明示されていない性質に依存するのはよっぽどの理由がないかぎり止めといた方がいい。書いてないことは未定義。未定義なことはやっちゃだめ。たとえソースを読んでそうなっていたとしてもだ。

posted at 21:13:52

個人的に驚くのは、char* get(..., size_t* sizep); とかいうシグネチャで、成功時に値の領域へのポインタを返してその領域のサイズをsizepが示す変数に格納するっていう仕様に対して、sizepを評価して0じゃないかどうかでエラー判定をする奴がいること。

posted at 21:09:30

まあペアプロっていうよりも、こちらとしてはベータ段階でアプリの開発シーンを見たいだけなんだけど、それだけだと見られる側にメリットがないから、質問に答えたり要望を反映したりすることでバランスをとる感じ。

posted at 20:47:02

ペアプログラミングのドライバ役がアプリの主管プログラマが担ってナビゲータ役を依存ライブラリの作者が担うということなんだけど、ライブラリの開発初期段階からそれをやると結構いいかもな。

posted at 20:43:03

宮本茂のチームがゲームを作る時にはプロトタイプ版を素人のユーザにプレーさせてその姿を見ていろいろ直していくそうだが、ライブラリの作者もそういうことをした方がよいものを作れるかもな。TCのアプリのプログラマが関連するコードを書いていく様子を俺がジッと見つめるみたいな。

posted at 20:37:09

えー。「キーボード見ないでそんなに早く書けるなんて、まるでハッカーみたいですね」「あたし知ってますよ。このpってのは改行するって意味なんですよね」「ドルマークがいっぱいあってなんだかアメリカに来たみたい」とか言ってもらいたくないですか？

posted at 17:41:58

隣で励ましてくれるくらいならどうだろう。「すごーい！ ついにコンパイルできちゃいましたね」「コンピュータに強い男性ってなんだか頼もしいですよね」「括弧とか記号がいっぱいあって面白ーい」とかなんか適当なことを言ってくれる。

posted at 17:25:28

まあ俺ペアプロとか苦手なんだけどね。コーディングスタイルの違いがストレスになってダメ。モジュール切って協業するならいいけど、同じファイルを編集するのはできればやりたくない。もちろん仕事で人のソースを保守しなきゃならない時は割り切ってやるけども。

posted at 17:16:34

@tatsuma_mu 御社で経営に乗り出してみては？　会員制にして会費で回してもいいかも。

posted at 17:07:37

まあその前に、ペアプロができる女の子がどんだけいるのかという話と、いたとして時給1000円で働くかという話があり、実現には大変な困難が予想されるわけだ。

posted at 16:59:44

2500/hに値上げして、入店料500円と指名料2000円をとろうか。指名料も折半として、1日10回入るとすると、売上85000/日か。それでも多分やってけない気がするなぁ。

posted at 16:58:30

ペアプロカフェの考察。2000円/hだと、女の子には半分の1000円/hくらい渡すだろう。仮に10ブースが50%の稼働率で1日12時間営業だとすると、1日の売上は6万くらいか。これじゃやってけないな。

posted at 16:54:58

以上が、100万レコードの規模の更新性能の速報。今日は1億レコードとかのテストをかけて帰る。

posted at 16:39:24

ちなみに、KCのnon transactionモード（デフォルト）だと、HDDでもfusion-ioでもだいたい160万qpsくらい。4スレッドで動かすと両者とも285万qpsくらい。

posted at 16:37:42

KCのauto soft transactionモード（WALは書くけどsyncはしない）だと、HDDが21万qpsで、fusion-ioが23万qps。つまりキャッシュに乗ってればあんまし変わらない。そらそうだ。

posted at 16:35:36

KCのauto hard transactionモード（WALとDB本体を両方fsyncしながら書く）だと、HDDで1704qps、fusion-ioで3329qpsくらい。

posted at 16:27:30

fusion-ioだと、fsyncの速度がHDDに比べて2倍ちょい。「fusuion-ioならfsyncしまくっても大丈夫」ってほど早くはないけど、まあ結構早い。

posted at 16:25:35

某市某駅徒歩50分になると21万くらいだそうです。

posted at 15:27:16

さっき調べたら、銀座の三越前の交差点の地価（今年の固定資産税路線価）は26500000円/m2。つまり坪単価8700万円くらいだそうだ。http://www.chikamap.jp/map/map.asp?plc=1310200500400005

posted at 15:19:01

TODO: KCでraw device対応の検討。mmap経由で全部やっていいなら簡単そう。

posted at 14:19:14

さて、チャリで出社しちゃうぞ。あったかいし、快適だなー。

posted at 14:10:21

やっぱWALもmmapにすると断然早いな。さらに2倍速になった。でもこれでいいのか？

posted at 14:09:11

KCRNDSEED=2538522278 ./kchashtest wicked -th 1 -it 4 -oat -bnum 5000 -msiz 50000 -dfunit 4 casket 10000

posted at 13:49:07

ということで、せっかく善意を見せるなら、実効のあることをしよう。せっかくパッチを書くのなら、それが本当に必要かを誰かにレビューしてもらってからにしよう。善意は本当に貴重なリソースなのだから大切に使いたい。

posted at 12:49:04

実効のない善行は、その善意からくる本来の効用を損失しているので、相対的に悪である。それを偽善という。神や仏じゃないんだから、人間の善意は有限のリソースだ。「やらない偽善よりやる偽善」というけど、偽善で無駄に善意を消費することを推奨する風潮は嫌い。

posted at 12:46:57

というかリリースビルドが気に入らないんだったらデバッグビルドを使いつづければいいだろ。謎だなー。なんで本家と全てのユーザにそれを強制しようという思考になるのか。

posted at 12:28:18

「assertだとリリースビルドの時にチェックが働かないからassertと同じ条件文とabortをその直後に置いてみた」というパッチが来たが、それはassertという機構を完全否定してるだろ。なんでデバッグビルドとリリースビルドが分かれているのかを考えてほしい。

posted at 12:25:28

「技術職は自分の時間つかって技術をみがいて、それを提供して対価をいただく」（via @tokuhirom）に禿同。逆に言えば時間の対価をもらっているわけではないので、時間的に拘束されるのは最小限にしたいよね。技術者にフレックスタイムと美味しいコーヒーを！

posted at 12:07:26

やっぱり午前半休（＆妻子は外出なので一人）っていいなー。モンカフェとか飲んじゃったりしてね。@tmaesakaさんや@fujimizuさんはこんなに優雅な時間を過ごしていたのか。

posted at 11:32:12

指名した女の子とペアプログラミングできるカフェがあるといいんじゃまいか。2000yen/hくらいで。

posted at 01:43:16

KC-0.5.13リリース。自動トランザクションモードのスループットが2倍程度になり、15万qpsくらいで動作するようになった。読み込みが100万qpsを越えていることから考えるとずいぶん遅いので、もうちょい改善せねばならん。

posted at 01:31:21

WALをmmapで書くことの是非についてもう一度考えたい。今は普通にwriteでWALを書いているが、CPU時間の実に86%をWALのwriteが占めてしまっている。こいつは何とかしたい。

posted at 01:17:44

TODO: WALの上書きを実際より１バイト多めにやる。

posted at 23:40:03

やっべぇ。自転車屋に修理出したチャリとりにいくの忘れた。

posted at 21:54:47

「ファイルの更新はサイズの変更を伴うことが多いからmtimeだけでなくてsizeのメタデータも更新するのでmtimeだけ更新しないようにしても意味が薄い」とかいう回答をどっかで見たけど、DBとかだとサイズを変更しない変更も多いんだけどなぁ。

posted at 16:11:57

@kazuho 実際に更新するのは1秒に1回以下でしょうけれど、更新しようとすること自体が負荷になってるのかなと。まあそういうオプションがない時点で、ファイルシステムをハックしないと実験しようもないわけですが。

posted at 16:11:18

no"m"time オプションってないのかなー。

posted at 16:00:00

ホビープログラミングカフェすげー。回転率が悪すぎて利益出なさそうだけど、でも儲けが目的じゃないっぽいのでいいのかな。頑張ってほしい。

posted at 15:22:37

If you criticize the choice of other's software lisence, please read the body of the lisence at least.

posted at 11:58:08

コミット方法を変えたらトランザクション付きのinsertで19万qpsくらい出るようになった。

posted at 10:55:22

たんぽぽGのテーマソングは「じこはおきるさ」ということなので、研究開発Gのテーマソングは「てんぱいぽんちん体操」にしたいと思います。http://www.youtube.com/watch?v=OtfJIHWeo-A

posted at 10:38:41

eTaxってなにげに昔からあったのか、目には入ってたんだろうけど、認識してなかった。

posted at 10:09:56

@kunzo 「公的個人認証サービスに基づく電子証明書は、住民基本台帳カード（ICカード）に格納されていますので、別途、電子証明書に適合したICカードリーダライタが必要になります。」て、めんどくせー！！

posted at 10:08:46

確定申告てネットでできるようになったのか？！

posted at 09:43:04

Berkeley DBのグループコミットを参考にすりゃいいか。にしても、ディスクに書きさえすればdurableであるって発想には同調できないなぁ。ユースケースの違いと言えばそれまでだが。

posted at 09:12:08

やっぱ、もっと上のレイヤ（TCでいうところのTT。すなわちC/Sモデルでレイテンシが隠蔽されそうな層）でクエリをグループ化するなら現実的な気がするけど、プロセス組み込みのDBMとしてはアプリ側の知識を使ってアプリが自分でグループ化を行う方がマシっぽい。

posted at 08:57:03

KVS的にはレイテンシの最小化は重要課題だから、timedwait系のアルゴリズムは使いたくない。とすると、WAL同期専用のスレッドを立てるのが妥当っぽいけども、でもDBM的にはそれはあんまりやりたくない。

posted at 08:46:28

そもそもレイテンシを伴わずにトランザクションをグループ化するのって結構難しくないか？ あるスレッドがトランザクションのWALをfsyncしようとした時に、全く同時に他のスレッドのWALが書かれていれば、2つのfsyncを1回に統合できるわけが、「全く同時」をどう捉えるかが重要。

posted at 08:42:43

ていうかグループコミットについてあんまり理解できてない自分。ちゃんと調査せねば。

posted at 02:11:30

Oracleのマニュアル見てると、「定期的な永続コミット」っていうオプションがあるっぽいな。durabilityは落ちるけどグループ化に伴うレイテンシは無くせるオプション。

posted at 01:56:31

@kazuho C/S型じゃないので「同時接続」の概念もないので、どの単位でグループを構成すべきかが悩ましいですね。fsyncを毎回でなくて毎秒とかにする場合、当然duralibityを保証するためにはレイテンシも秒単位にしないといけなくなってしまうので、それも現実的ではない。

posted at 01:16:35

オペレーションの単位がもっと大きい場合はfsyncも有用かなと思います。でもKVSの個々のレコードの更新を単位としてfsyncを呼ぶのはさすがにないなと。

posted at 00:51:31

@kazuho それをDISるなんてとんでもない！

posted at 00:49:28

TODO: TTに自動トランザクションモードをつける。

posted at 00:48:04

WALファイルをmmapで読み書きすればもっと高速化しそうだけど、msyncするとかえって遅くなり、でもmsyncしないとWALファイルとしての機能を保証できないので、こまっちんぐ。

posted at 00:45:53

まあ、「実用になる」って言葉はユースケースに応じて決まるものなので、「俺や同僚や友人の多くのユースケースでは実用になることが多い」という意味なんだけど。

posted at 00:39:11

しつこいようだが、自動同期（fsync）モードを使うのは愚の骨頂である。一方、自動トランザクション（WAL）モードは5万qpsくらい出るので実用になる。

posted at 00:36:45

KC-0.5.12リリース。自動トランザクションモードと自動同期モードがついた。つまり、begin|end_transactionやsynchronizeを明示的に呼ばなくても、勝手にWALやfsyncでファイルを保護する。

posted at 00:28:40

あ、もちろん例え話ですよ。fsyncを呼んでも故障率は下がらないし、スループットの低下を補填するためにshardingとかすると故障率が飛躍的に増大するから、結局レプリケーションしなきゃだめでしょって話。

posted at 19:16:38

レプリケーションを1台追加して冗長化するコストを嫌ったfsync教信者は同じスループットを得るために500台のサーバを投入しましたとさ。金かかるのも馬鹿みたいだけど、故障率が500倍なのが悲しい。fsync教は滅びるべし。

posted at 18:46:28

毎回の更新で暗黙的にfsyncするAUTOSYNCモードを実装したものの、27qpsしか出ない。通常モードだと110万qpsだから、実にスループットが0.2%になるわけだ。使う奴いんのか？こんなの頭がどうかしている連中のための機能だ。

posted at 18:39:55

というのを言い訳にしてアセンブリ言語の理解やglibcのコード読みを後回しにする俺。

posted at 14:41:29

下層のカラクリが理解できないという劣等感は飼いならさないといけない。むしろ下層を知らなくても乗りこなせるように、機能を仕様書でしっかり確認するのと、性能等の非機能要件を実験で確かめるのが大事なんだと思う。

posted at 14:40:05

言語仕様とライブラリのAPIを理解していればよくって、下層のゴニョゴニョの知識は必須ではないと思う。周辺のレイヤを学ぶのは有用だけれども、工数は有限なんだから、程度を加減するのも大事。

posted at 14:37:32

@nobu_k あらら。CPPFLAGSに -I. って書いてあるので、<> か "" かによらずにカレントディレクトリを先に見るとは思うのですが、実はそうでもないのかな。

posted at 12:55:35

KC-0.5.11リリース。レコードの削除処理が著しく高速化した。第２ハッシュ関数をより散けるように改良した。

posted at 10:25:23

ソーシャルクラウド2.0 はじめました

posted at 10:14:30

「ソーシャル」って言葉も「クラウド」並にバズワードだな。「御社のソーシャル活用事例をお聞かせください」みたいな取材が来ちゃったりするのか。

posted at 09:54:03

ふと思うのだが、みんな、自分のソフトのテストかけて帰らないのは何でだろ。負荷テストの結果をコーヒー飲みながら待つなんて無駄。テスト専用マシンでずっとかけっぱなしにできるならいいけども。

posted at 09:46:51

出社。make check-foreverが生きてた。すなわち俺の勝ち！

posted at 09:38:38

TODO: autotranモード。autosyncモード。

posted at 08:45:41

TODO: Makefile内でldconfig

posted at 23:18:59

なんじゃこの雪は。なんか楽しくなってきた。

posted at 23:11:17

よっしゃ。(make check-forever & go home) && win

posted at 22:58:32

うはははははははあはははあははははh！！　直った！！　たった1行のミスで1日潰すとは…。

posted at 22:21:55

帰りたいのは山々だが、このバグをどげんかせんといかん。

posted at 20:42:42

SUSv3を見るかぎり、スレッドIDで指定したスレッドが実行中かどうかを調べるAPIはない。なので、アプリ側の努力でadaptive lockを実装することは不可能ぽい。

posted at 10:14:22

ロック用の変数にスレッドIDを入れておいて、CASに失敗したらその値を調べて、そいつが実行中かどうか確認するのがいいが、可能だろうか。

posted at 09:49:20

といいつつ、コア数あたりpauseループ何回が適当なのかはヒューリスティックになるから、ださいことに変わりはない。

posted at 09:45:21

てことは、pauseでループする回数をコア数の関数で決めて、それ以降はyieldでループするということにすれば、adaptive lockの簡便法として成立するかも。

posted at 09:28:30

adaptive lockの仕様にもあるように、ビジーウェイトに意味があるのは他のCPUコアがそのロックを獲得したスレッドを動かしているという場合だけだから、つまりシングルコア環境ではまったく意味がなく、2コア程度でも効果は薄く、4、8、16あたりからやっと得が出てくる感じか。

posted at 09:25:46

TODO: B+木APIのヘッダ書き

posted at 23:26:59

TODO: FBPのロックはspinlockにすべきかmutexにすべきかを再検討

posted at 23:25:11

TODO: CacheDBでだけ回転平衡化を実装。

posted at 23:24:33

いろいろ試した結果、ビジーウェイトをpauseで負荷低減するよりも、おとなしくyieldした方が大抵のユースケースでマシな性能になるっぽい。クリティカルセクション内で変数の値を調べるとかいうだけの小さいロックでも、ビジーウェイトはあんまりお得ではない。

posted at 19:55:08

またも洗足散策なう。

posted at 11:56:00

メモ：pentium4プロセッサにおけるスピンループ http://download.intel.com/jp/developer/jpdoc/w_spinlock_j.pdf

posted at 11:04:32

@xkazu よくなるかもです。何回かはrep nopやらpauseやらで待ってダメそうならyieldするっていうadjustiveな感じの挙動にしたらかっこいいかなとも思っています。ただ、それらを呼び出すGCC拡張がないので、__asm__ 書かねばならず、ちょっと躊躇。

posted at 09:53:42

洗足池公園なう。気分がいい。

posted at 14:16:42

やはり母親の威力は凄い。帰ってきて声が聞こえた瞬間に泣き止んだ。3歳くらいになるまでは父親って独自の存在感がないただの大人っつーか、母親の劣化スレーブに過ぎんのかも。

posted at 12:57:51

問題は、娘を抱きながら片手でコーディングするのがすごく辛いということだ。

posted at 09:52:12

うーむ。回転させないとバランスさせられないし、回転させると書き込みが発生しちゃうから、どっちが得かは一概に言えないなぁ。削除孤児の挿入先部分木をランダムに選択するという現状の実装がやはり最善ぽい気がする。あとは実装上の最適化を頑張るしかない。

posted at 09:51:44

レコードを削除した際の二分探索木の回復処理で、回転を伴わずにバランスを最大化するにはどうするべきか考える。

posted at 02:21:18

TODO: KCのremoveがなぜ遅いのか調査。TCのremoverecのバランス処理の検証。

posted at 19:32:59

つか、「年末年始の贈答」ってことにすれば贈与税がかからないっつーのはザルだな。

posted at 12:40:08

@shudo 「個人から受ける香典、花輪代、年末年始の贈答、祝物又は見舞などのための金品で、社会通念上相当と認められるもの」には贈与税がかからないそうです。

posted at 12:35:39

インターナショナルスクールも無料化するってマジか？　すげーな国。公立高校の学費が年10万ちょいでインターナショナルスクールは200万以上だから、つまり20倍も格差があるわけだが、納得できる説明が思い浮かばん。

posted at 10:28:31

負荷テストをやらないでストレージシステムを実運用しようとしている人はこの歌を100回くらい聞いた方がいい。

posted at 00:36:00

おもいつきでやると　きっと　しっぱいするよ

posted at 00:30:23

じこがほら　おきるよ　いいきになってると

posted at 00:27:44

この歌が家庭内で大ブレイク。歌詞がポジティブすぐる。 http://www.youtube.com/watch?v=6hBt0R2roCk

posted at 00:24:44

許可をいただいたので、Software Design誌の今月号に寄稿した記事を公開。http://1978th.net/tech/promenade.cgi?id=72

posted at 22:42:10

100均のドライバーってマカダミアナッツの殻にも負ける弱さだから嫌だなぁ。

posted at 20:40:50

家の近所の100均にあればいいが。

posted at 20:38:13

@993targa おお。どうもです。危なかった。

posted at 20:36:48

精密ドライバーを買って帰りたいが、渋谷だとハンズ行かなきゃだめかなぁ。ていうか何時までだろ。

posted at 20:27:04

ロック置き換えによる高速化についての過程をブログった。http://1978th.net/tech/promenade.cgi?id=71

posted at 20:05:17

KC-0.5.9リリース。標準のロックを自作のに置き換えて驚くほど高速化した。

posted at 20:00:20

PTHREAD_PROCESS_SHAREDとかサポートしてるから遅いとかそんな感じなのかなぁ。全然適当で言ってるけど。

posted at 15:41:24

自作spin_rwlockはGCC拡張のcasでクリティカルセクションを作っているのだが、それを標準のspinlockを使うようにしたら、標準のrwlockとほぼ同じ性能になった。つまり、遅いのは標準のspinlockなのではないかという仮説が立つ。

posted at 15:40:41

spin_rwlockを自作したら標準のrwlockに比べて5倍くらい早いことがわかった。これでKCもかなり実用性が強まってくる。

posted at 12:57:27

iWifeとiDaughterにiHugしてからiWalkとiTrainでiCommuteするなう。

posted at 09:21:18

おお！これは愛に満ちてる。 RT: @frsyuki これは…！！「GCC 4.5 の半分は C++03 へのやさしさでできています」：http://bit.ly/9G8UZB

posted at 20:28:09

先ほどの、ブルームフィルタ＋オンメモリキャッシュ＋DBMの話をまとめてみた。http://1978th.net/tech/promenade.cgi?id=70

posted at 19:57:44

まあ、DBMの典型的なユースケースは、Webサイトのセッション情報の管理とか、ニックネームやパスワードなどのプロフィール管理とか、足あとや最終ログイン時刻などの履歴管理とかだと思っていて、それらはほぼ確実に存在するレコードを見るものなんだけれども。

posted at 18:01:32

@takemaru_jp ありがとうございます。参考にさせていただきます。

posted at 17:54:26

class CacheDB : public DB { CacheDB(DB* storage){...} }; ということだから、無限に階層化できる。

posted at 17:53:32

いやいや。「ダーティなキャッシュが溢れたらファイルに書く」「キャッシュに無い場合にファイルから読む」「ファイル上のキーの一覧を得る」をコールバック関数にできればよいのだから、つまりDBMインターフェイスを外部から受けとればファイル層の実装は隠蔽できるか。これはいいな。

posted at 17:47:05

つまり、kc::CacheDBとkc::HashDBを再利用してキャッシュ付きDBMを作ることはできないということ。双方を融合させないといけない。

posted at 17:30:02

分割したキー空間に合わせた排他制御を行ってその中でキャッシュ層とファイル層を一貫して操作しなければならないので、モジュールとして双方を独立させることがかなり難しくなっちゃう。仕方ないんだけど、実装も保守も面倒になることうけあいで、なんかやる気が失せる。

posted at 17:28:37

さて、並列性を考えた最適化を行うとフィルタを「上層」に綺麗に分けられないのも悩みどころ。DBM全体のキー空間のフィルタを一度に再構築するのは簡単だが、できればキー空間をいくつかに分けておいて部分部分のフィルタを適宜再構築したい。

posted at 17:19:31

つまり、比較的少数の迷惑ユーザの迷惑行為をカウントしなくちゃならないんだけど、全てのユーザに大して迷惑度がしきい値を下回っているかどうかを調べなきゃならない場合。

posted at 17:16:33

@kzk_mover 迷惑ユーザのDBMとかが典型的です。

posted at 17:14:23

で、フィルタについてはとりあえずは上層に分けて、今はその下層である「キャッシュ付きDBM」についてのみ考える。上層がきっと頑張ってくれるとして、下層はキャッシュヒット率が高いとの仮定に基づいて設計する。

posted at 17:05:59

@kzk_mover それもありですね。ただいずれカウントは溢れるので延命措置にすぎず、結局再構築のロジックは入れることにはなりそうです。

posted at 17:02:08

でもその条件に当てはまるユースケースって、ないとは言えないけど、DBMのユースケースとしては稀だと思う。

posted at 16:55:18

つまり、存在しないレコードがよく探されて、かつレコードがあんまり削除されないようなデータベースでは、前段にフィルタを持っておくと、キャッシュが有効活用されてファイルIOも減らせるということ。

posted at 16:53:08

だが、ブルームフィルタは要素を削除できないので、削除されたレコードを多く行う場合には定期的にフィルタ自体を再構築しないと、偽陽性がじんわり増えてきて効率が悪化してしまう。

posted at 16:50:58

そこで、存在しないことが予め分かるフィルタを検討することになる。存在することを正とするブルームフィルタを持ち、陽性もしくは偽陽性の場合にのみ実際の検索を行う。そうすると非存在レコードの検索回数が激減するので、存在レコードのみをキャッシュするだけでよくなる。

posted at 16:47:46

とはいえ存在しないという事実（キーと非存在フラグ）を大量に持つとメモリ容量が圧迫されるわけで、存在するレコードを探すのが主な場合には非存在キーはキャッシュしたくない。

posted at 16:43:27

ただ、存在しないレコードを探す場合にどうするかは戦略が分かれる。無いという事実をキャッシュするかどうかだ。存在しない事実をキャッシュしないとすると、存在しないレコードを探すことが多い場合に毎回ファイルを見てしまうのでキャッシュの意味がなくなる。

posted at 16:41:43

参照されたレコードがキャッシュ上に無い場合に常にファイルを見てキャッシュに載せるというのは絶対だ。ヒット率が高い場合はファイルを見ないからIOは減る。

posted at 16:39:54

オンメモリのキャッシュDBであるkc::CacheDBで、容量制限を越えたレコードをファイルのDBMに書き出せるようにコールバック関数をつけたとして、じゃあそれをいつキャッシュに載せ直すかが問題となる。

posted at 16:36:45

macにはpthread_spinlock_tがないのか？ 代わりにlibkern/OSAtomic.hのOSSpinLockLockなどを使わないとダメ？

posted at 16:15:28

ハッカー時計。「出演させたい人名リストを作ったら、spyseeあたりから顔画像を集めて、OpenCVで顔の位置を特定して顔画像以外の場所に時計盤を挿入する」という手順で画像を60*24個以上作っておくと完全自動化できるか。

posted at 12:55:43

@Yappo おおおおおおお！

posted at 12:50:20

イメージ：http://1978th.net/misc/tmclock-1.jpg

posted at 11:27:45

TODO: tmaesaka時計

posted at 11:19:42

この男子に惚れた。http://www.elle.co.jp/love/ikemen/10_0127

posted at 10:24:14

イーサネットのケーブルで繋ぐ無線LANリピータでUSB端子から電源とれる小型の装置はないかな。そうすりゃOSの設定は楽だ。

posted at 09:40:16

無線LAN。デュアルブートのWindows側は5分未満で接続設定できたのに、なんでできないんだぁ～？

posted at 09:31:05

だめだ。つながらねぇ。あきらめた。

posted at 04:34:27

無線が全然認識されねぇ。insmodでドライバはインストールしたし、iwconfigによるとデバイスとしては認識されてはいるのだが、ランプが光らない。

posted at 03:57:55

ubuntuの最新版入れたなう。 例によって無線LANの設定にてこずる。それ以外はすこぶる快適。

posted at 01:23:39

異常終了した時は次回起動時に勝手にoptimizeするようにしちゃおかなぁ。でもそれをもって「壊れない」と言い張るのは誤魔化だよなぁ。トランザクションモードをデフォルトにするのもいいけど、「遅いけど堅牢なDBM」にどれほど意味があるか疑問。

posted at 20:18:36

TODO: kchashmgr importの実装

posted at 19:45:21

KC-0.5.8リリース。LRU削除機能付き連想配列をDBインターフェイスで操作できるようにした。ロックがレコード単位なので、JavaのConcurrentHashMapと同じように使える。それでいてメモリ効率がとてもよい。

posted at 19:37:08

TODO: 奥さんのMacにXcodeを入れさせてもらう。

posted at 19:15:11

TODO: キャッシュから消すレコードの後処理をコールバックで補足。

posted at 17:34:16

@ukyooo ネコイラズという薬があるので、それで毒殺するのも手かと。

posted at 10:04:28

なんかここ、タイムラインがバグってるぽくない？　俺の発言が別の人のになってたり、別の人のすげー古い発言が突然上がってきてたり。

posted at 10:03:09

TODO: ハッシュからの削除方法の再検討

posted at 09:44:05

@kazeburo なるほど。仮想マシンをいっぱい立てるような場合だとメモリ節約効果は多少はありそうですね。

posted at 09:09:42

なんか、仕事の進捗が遅れぎみ。もっと冷静かつ大胆に手を動かさねば。

posted at 00:33:54

いい加減、32ビットOSを使うのは止めようや。

posted at 00:08:30

TODO: LRUになってるかテスト

posted at 20:31:43

つか、まじで頭痛い。定時まであと30分もあるお。

posted at 18:27:49

youtubeのdiscoで「小泉今日子」を検索したら何故かjazztronikっていうバンドのプレイリストが出てくるわけだが、それはそれでなんかとてもいい曲が多い気がするのでそのまま流している。だがキョンキョンを所望している俺もいる。

posted at 16:36:35

Youtubeのdisco機能すげぇな。こりゃ生半可な音楽配信サービスじゃ勝負にならん。

posted at 16:03:18

人として真理に到達したところがすごい。

posted at 12:43:13

やっぱしオフィスに来るとクシャミが出る。ここはやばい。魔空空間にひきずりこまれてる。

posted at 11:33:24

novice（nα'vэs）は「ノバス」または「ナバス」って表記の方が適切だという説。

posted at 10:44:22

casを2段にすればrwlockを実装できることはわかっているのだが、それが最善かどうかが自信ないなぁ。

posted at 10:14:26

ほとんど競合しない（競合させる奴はロジックがおかしい）ということを仮定するなら、競合時のオーバーヘッドが多少大きくても構わないはずだ。

posted at 10:04:09

てことで、競合をスピンして解決するspin rwlockが欲しい。

posted at 10:02:28

ただ、KCの競争力を高めていくためには、ノービスでなくプロのユースケースに特化すべきで、したがってこのrwlockは廃止するか、より軽量化したい。

posted at 09:50:39

しかし、このrwlockは本来は不必要だ。通常操作とメタ操作を並行して行うなんてのは明らかにバグだからだ。しかし、そうするなと仕様書に書いてもやる奴がわんさかいるというのも事実なので、わざわざオーバーヘッドを伴って保護している。

posted at 09:44:29

TCやKCにおけるrwlockの使い方は、更新がライタで参照がリーダという典型的なものではない。通常のレコード操作はレコード単位のロックで排他制御する。通常操作とopen/close等のメタ操作を排他制御するためにrwlockを使うのだ。

posted at 09:38:05

いや、やっぱりロールバック用の差分リストをスロット毎に保存する。

posted at 02:01:09

TODO: CacheDBのトランザクション再検討。slotにレコードリストのコピーを持たせる

posted at 01:54:35

二子玉川の柿安でビュッフェなう。野菜中心に攻める。

posted at 17:58:08

多摩川沿いに散歩しまくったら二日酔いがやっと治ってきた。ワインは体に優しくない。

posted at 16:33:59

さっきの件、俺が足ひっぱってたかも。すまん。

posted at 20:23:35

結婚式なう。

posted at 17:08:52

ありゃ。家のPC（32ビットLinux）だとやっぱしrwlockのreader lockでちゃんと並列性が出る。64ビットだと遅いとか？ 2.6.18だと遅いとか？

posted at 01:26:37

TODO: iterateの実装。スピーチ検討。

posted at 00:05:39

100万レコード格納でkc::CacheDBは0.6秒かつ64MB。std::mapは4.5秒かつ150MB。std::tr1::unordered_mapは1.2秒かつ134MB。

posted at 23:36:35