Skip to content

Instantly share code, notes, and snippets.

@hryk
Created February 20, 2009 17:27
Show Gist options
  • Save hryk/67578 to your computer and use it in GitHub Desktop.
Save hryk/67578 to your computer and use it in GitHub Desktop.
key-value storage勉強会メモ
---
senna:
- Groonga
- sennaの後継
- memcached binary protocol互換のストレージ
- 柔軟かつ高速
- DB的な感じにもできる
- DB APIでテーブル定義とかできる。言語バインドは今schemeだけど書けるらしい。
- http://groonga.org/
luxIO:
- DBマネージャー
- C++, B+Tree , Array
- 分散しない
- Luxの内部DBとして開発
- 長いvalueを入れられる(4Gまで)
- 削除が多い処理には向かない。
- 大きいデータ入れるときはいいかも
- 小さいデータと大きいデータがとくい
- http://luxio.sorceforge.net/
TokyoCabinet_Tyrant:
TokyoCabinet:
- ハッシュDB
- static hashing
- pthreadで並列化
- メモリに載るとこはmmap それ以外はpwrite/pread
- B+Tree DB
- 2.5G q/s
- http://tokyocabinet.sourceforge.net/
Database:
- オンメモリDB
- スプレー木 -> 転置インデクスのキャッシュ 順序木
- 固定長配列データベース
- テーブルデータベース
- レコードごとにカラム名を持ってる -> 最初にスキーマを作らなくてもいい。
- 複数のプロセスで開きたい要望があった
- Hash構造体的な事ができる?
Tokyo_Tyrant:
- TCのネットワーク対応
- 並列化 -> スレッドプールモデル kqueue/epoll
- 各種プロトコル対応
- 60M q/s
- http://tokyocabinet.sourceforge.net/tyrantdoc/
TCの改善:
- フリーブロックプールが遅い
- B+木をページ単位ロックに
- 検索サーバ作る
- キャッシュ用時限ストレージ
- テキストマイニングとグラフマイニングのミドルウェア化
- TC/TTは1台あたりのスループットを最大化する
- 実際は1台で処理できる事も多い
- key/valあきた
アカデミックなkey_val:
- 簡潔木 txのtrie表現
- 方法1 木による格納
- 方法2 ハッシュに依る格納
- そんなにメモリに載せられるの?ってデータ載せちゃう
- 赤黒木、hash
- tx, bep, bep(キー無し)
- trie キー集合を機構増で管理
- 各枝に文字が付随し、つなげるとキーになる
- 値は節点の先に格納
- 1nodeあたり2bit、低数時間
- tx:
- 木の簡潔表現によるtrieライブラリ
- 複雑な操作でも、キーが増えても高速処理
- http://www-tsujii.is.s.u-tokyo.ac.jp/~hillbig/tx-j.htm
- LOUDS
- Hash:
- cuckoo hashing
- 2種類のハッシュ関数を用意
- 定数回のLookupでok
- http://d.hatena.ne.jp/KZR/20080531/p2
memcached:
- 早い、軽い、かんたん、しぶとい
- LRU -> least recentry used
- ARCアルゴリズム Adaptive Replacement Cache
- ARCの場合はqueueと頻度
- http://en.wikipedia.org/wiki/Adaptive_Replacement_Cache
- Postgresとかzfsとかで使われている
- ARCはPatentされてるよ!
- 1MB以内ならなんでも扱える
- RDBMSにもキャッシュがある!
- MySQL QueryCache:
- オブジェクトの粒度をコントロールできない。
- 生存率が長く無い
- マシンを超えたメモリ容量が使えない
- フラグメンテーションが激しい
- デフラグを手動でやらなきゃ
- キャッシュを共有できない
- ロードバランサどうする?
- 一貫性の無いキャッシュ配布
- FaceBookとか:
- Shared Buffer Pool
- Stats Global Lock除去
- TCPからUDPに移行
- 通信パケットのバッチ(en|de)キュー
- 本家への取り込みを要請するが却下
- 原型があまり残っていない...
- 使える所はとりこむ
- memcached最近:
- 更新系no-replyない
- 実装した!
- エラーはかえすべきじゃね?
- Asciiでは完全に無視
- IANAにport番号の公式申請を出してうけつけられた
repcached:
- multithread化 -> だめ
- queueがあふれる
- memcachedのレスポンスが悪くなる
- memcachedの実装:
- libevent
- selectとかpollとかしないでいいかららく
- set/addのついでにreprication
- 応答時間が長くなる
Kai:
- kaiとは 'Dynamo + memcached / erlang'
- erlangで書いてある
- Dynamo:
- 消えたら困るデータを於いておく
- 分散透過性
- High Availability ロック無し,いつでも書き込める
- 結果整合性をちょっとあれしても
- eventually consistent:
- 3レプリカを同時に書き込み
- ベクトルタイムスタンプを刻印
- バージョン不整合はタイムスタンプで対応
- 結果的に生合成がとれればいい
- 書き込みのパフォーマンスを上げたい
- kaiの分散透過性:
- 分散している事をどれだけ隠せるか
memo:
- memstorm? memcacheクライアント
- ここで電池切れ。。。。
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment