ロックフリー性の証明について - くまメモ
http://www.slideshare.net/kumagi/lock-free-safe?next_slideshow=1 とか過去に自分で書いておきながら、その当時の自分の認識が甘かった事もあるのでここに一度書き出しておく。 Lock-Freeは「ロックを使わない事」ではない STMの事をもってしてLock-Freeと呼んでる文脈はいっぱいあるけれど、STMの実装にロックを使う事は一般的だし、それは正しい専門用語で言う所のLock-Freeとは呼ばない。 Lock-Freeとは「どんなスケジューリングが為されようともどれかの操作が進行する」という進行保証(Progress Guarantee)を表している。 スケジューリング？ マルチコアCPUでもシングルコアCPUでも、OSは実行中のプログラムを任意のタイミングで強制的に一時停止させて他のプログラムにCPUリソースを割り当てる事が
pixivでBloomFilterを使うためにやったこと - pixiv inside [archive]
こんにちは。最近はAndroidアプリ開発に入門しました、@edvakfです。 pixivではキャッシュ兼汎用KVSとしてKyotoTycoon (KT)を使用しており、頻繁にアクセスされるキーはアプリケーションサーバー内のAPC（PHPのshared memory cacheです）にもキャッシュすることで多段化しています。 このような構成の弱点として、「ほとんどの場合は値が無いけど毎回存在確認が必要なキー」の場合に前段にキャッシュが無くて毎回後段にまで問い合わせなければいけないという問題があります。ネガティブキャッシュ（値がないことをキャッシュする）を使うという手もありますが、問い合わせるキーの数が膨大になってくると現実的ではありません。 pixivでは、作品に付いている最大10個のタグについて、ピクシブ百科事典に記事があるかどうかを判定する必要がありました。これに加え、最近ではBOOT
![pixivでBloomFilterを使うためにやったこと - pixiv inside [archive]](https://cdn-ak-scissors.b.st-hatena.com/image/square/f9fafe007d2b6ff62ac1964b4f2415dd1e588183/height=288;version=1;width=512/http%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Fd%2Fdevpixiv%2F20140722%2F20140722045434.png)
PostgreSQL Internals
本コンテンツは、2014年1月30～31日に筑波大学で開講された「情報システム特別講義D」における講義「Inside PostgreSQL Kernel」の内容を再構成、加筆・修正したものです。 はじめに 本コンテンツについて 本コンテンツへのフィードバックについて アーキテクチャ概要 PostgreSQLの構成要素 PostgreSQLの基本的なアーキテクチャ SQL文の処理される流れ トランザクション管理 トランザクション処理におけるACID特性 各レコードの可視性の管理 Atomicity（原子性）の実装 Consistency（一貫性）の実装 Isolation（分離性）の実装 トランザクション分離レベルの定義 Durability（永続性）の実装 チェックポイント メタデータ管理 pg_controlファイル OID/XID/TID システムカタログ MVCCとストレージ構造 テ
Paxos
2. ⾃自⼰己紹介 l 久保⽥田展⾏行行(@nobu_k) l 製品開発部 l Sedue/Bazil l (Jubatus) l ブル l 最近勉強してるもの l 開発⼿手法：要件定義・管理理 l 本 l Transactional Information Systems(@ノーチラス) ‒ 約1年年で念念願のリカバリーまで到達・・・！ l 分散DB本 2 3. 今⽇日の話 l Paxos l Consensus algorithm(protocol)の1つ l ものすごく難しいことで有名(主に元論論⽂文が) l 流流れ l Consensus l 問題設定 l Paxos l (ちょびっとだけ)Multi-Paxos l 参考⽂文献紹介 l ⽇日本語の⽂文献が少なく、⽤用語が怪しいですすいません 3
文書解析のための簡潔データ構造 - Preferred Networks Research & Development
岡野原です。 12/1〜12/2に高松で開催されたALSIP2011で文書解析のための簡潔データ構造の最近の進展について話をしてきました。 ここの業界の進展は速く毎年様々な方法が出てきますが、要点だけを上げると – Wavelet Treeがアルファベットサイズが大きい場合のRank/Select操作だけではなく、2D矩形探索、最頻要素列挙など様々な問題を効率的に解けることが分かってきて非常に重要なデータ構造であることが分かってきた。2D探索も、もはや数億 x数億とかでも解けてしまうので2D探索を利用するような様々な手法が全部現実的になった。 – Top-K Queryが盛り上がっている。検索などデータ構造に問い合わせをする際に、該当する結果を全部を列挙することの高速化は理論的にも難しいが、スコアが高い順（例えばterm frequencyやPageRankなど）にk個だけ列挙するだけなら
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
TechCrunch | Startup and Technology News
あなたの知らないハッシュテーブルの世界