key-value storage勉強会メモ

KVS 090220

---
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クライアント
    - ここで電池切れ。。。。