Key-Value Store勉強会に行ってきました

• Tokyo-Cabinet の歴史
• 全文検索システムSnatcher
• Namazu、スニペットつき
• GDBMをベースにした転置インデックス
• 計量データベースライブラリQDBM
• cat mode, B+木対応のGDBM
• 全文検索システム　Estraier
• 全文検索システム　HyperEstraier
• mixiの検索機能
• 外部システムからHEベースへ
• この成長ペースだと破綻するのは必須。。。
• Tokyo Cabinet
• モダンなQDBM
• C99, Pthread, mmap pread/pwrite...
• win32互換を破棄
• でも検索機能にはあんまり使ってない
• HEからTokyo Dystopiaにおきかえたもの
• 主にデータマイニングで利用
• HWのスペックあがってきててメモリ豊富なマシンでうごかせばHEのままでいい
• ハッシュデータベース
• static hashingによる単純化
• データフォーマットの効率化
• BER圧縮、アラインメントとビットシフト
• フリーブロックプール
• ベストフィットアロケーション
• メモリにのればmmap, それ以外はpread
• ページキャッシュとBTree索引
• LRU削除キャッシュ
• 多機能
• 順序を維持、カスタム比較関数
• 範囲検索、カーソル
• Trick
• 格納時にページ単位で圧縮可能
• 投機的探索
• 並列性はテーブル全体のrwrite
• そのほか
• レコードに複数のカラム
• スキーマ不要
• 250万qps
• Tokyo Tyrant
• TCのネットワーク対応
• ローカルのマルチプロセスでもDB共有に利用
• 並列化
• スレッドプール
• epoll. kqueue, evenports利用
• 各種プロトコル
• 独自バイナリ、memcached互換、HTTP互換
• 抽象データベース
• 60000qps
• これから
• 並列分散処理の時代？
• TC/TTは１台あたりのスループットを最大化する技術
• １台あたりでできることは増えてる

岡野原さん (Key-valueの効率的格納)

• 興味分野
• データ圧縮、自然言語処理、全文検索
• 文字列のキーを利用していろんな値を格納したい
• 方法１
• 木による格納
• キーに対してtrieなどの木構造を構築し、木の接点、葉に値を格納など
• 方法２
• ハッシュによる格納
• 木によるキーの格納
• 各枝に文字が付随、つなげるとキー
• 値は接点の先
• tx : 木の簡潔h町減による木の簡潔な表現によるtrieライブラリ(09/02/22 修正。thx myuiさん)
• キー集合をコンパクトに格納し操作可能
• 元のサイズの約1/2 で格納
• 10億くらいのキーでものる
• select, rankの組み合わせで定数時間で探索可能
• ハッシュ
• Cuckoo Hashing
• 1から作り直す確率は非常に低い
• 全体の平均計算量はキーの線形倍で

前坂さん

• mixi, R&D
• memcached
• LRU
• 最近はARCアルゴリズムがあつい？？
• Patentされてる
• Key/Value,
• Value=Object
• 1MB以内なら何でも扱える
• RDBMSもキャッシュできるよ！
• MySQL
• QueryCache
• 採用するには厳しい理由
• オブジェクトの粒度をコンとトールできない
• テーブル更新でデータがinvalidate
• マシンをこえたメモリ容量がつかえない
• フラグメントが発生しやすい
• キャッシュを共有できない
• ロードバランサは？
• 一貫性のないキャッシュ配布
• Facebook
• 28TB
• 独自の改良
• Shared Buffer Pool
• Stats Global Lock  の除去
• TCPからUDPへの移行（cacheだし）
• 通信パケットのバッチ
• 秒間20万クエリ(!!!!←すごい)
• 変更しすぎたのでとりこまれなかった
• 一部はとりこまれる予定
• 最近の話
• バイナリプロトコルでno-replyが加わった
• エラーはかえす
• CASに固定で8byteもわりあてていいの？
• http://tinyurl.com/more-space
• 11211はmemcachedのポートとして公式に決定された

安井さん(repcached のなかみ)

• KLabの方
• memcacpedにレプリケーション機能をつけたもの
• 案1 マルチスレッド
• スレッド作成
• キューをつくってセットされたデータを入れる
• メリット
• 本体への影響がすくなそう
• 比較的簡単
• ただし、、
• アクセス数が多いときに問題発生
• 忙しいときにレプリケーション処理が追いつかない
• キューがあふれる
• memcachedのレスポンスが悪くなる
• 案2　シングルスレッド
• libeventを利用
• ハンドラを登録しておくとコールバックしてくれる
• 自分でselect(2), poll(2)とかしなくていいのでらくちん
• set/addのついでにrepl
• プロトコルの処理中にレプる必要
• どうしても応答時間が長くなる
• 案3 Pipeにキーを書き込むように変更
• だいぶよくなった
• やっぱりリクエストが多くなれば素のパフォーマンスよりもすこし悪くなる
• 今のところ２台までの構成
• １台だけレプリケーション？
• ３台使わないといけないシチュエーションがまだない
• 利用用途
• PHPのセッション管理
• 某SNSのアバターの着せ替え機能のセッションなど
• OKおすまで

たけまるさん

• Kai = Dynamo + memcached API / Erlang
• Dynamoの特徴
• amazonの裏
• 分散したkey-val
• 高い分散透過性
• ショッピングカートでも使われてるらしい
• 高い可用性
• ロックなし、いつでもかきこめる
• Eventually Consistant
• 3レプリカ
• Consistent Hashingで選択
• ベクトルタイムスタンプを比較
• 古いデータを上書き
• 結果的に整合性がとれる
• 分散透過性
• 分散していることの隠蔽
• P2P
• 透過性が高いと管理コストが低下
• 場所、移動、障害
• memcachedのAPIだけだとすこし不十分、、、
• なんだけども、とりあえずサポート
• Erlangの使いどころ
• 分散システムの適している
• アクターモデルが便利
• 共有メモリがなく安全
• プロセスが軽い
• Copy on write的にメッセージングパッシングを効率化
• そこそこ速い
• Java未満、LL以上
• 弱点は正規表現がだめ
• Kai
• Dynamo + memcached API / Erlang実装
• 開発者の本籍地から命名
• 検索しにくい。。
• Kaiの性能
• 約10000 qps
• Erlangの備え付けのストレージがボトルネックっぽい
• TCとか使えばいい？
• 某ポータルサイトで試験中らしい

上野さん （分散メディアストレージ的ななにか）

• 株式会社Fillotの方
• 配信をメインターゲット
• ブロードバンドメディアの配信基盤
• Cagra
• 1000 speakers confで古橋さんとペアプロでつくった
• amazon dynamo like zero-hop DHT
• consistant hashing based
• zero conf
• single thread
•  商用版を作成中
• 独自アルゴリズム
• multi thread / FSM
• リセットした理由
• 商用化
• アーキテクチャの限界
• fiberアーキテクチャ
• TCPチューニング重要
• パフォーマンスが４桁あがった
• read/writeは計画的に
• アルゴリズムの限界
• 人気の集中
• 非対称ノード
• Virtual node増減させる？
• LC-VSS by Godfrey et al.
• 大量のノード前提
• データ局所性
• DHT => すべてをぶちこわす。。！
• 似たようなコンテンツもバラバラ
• 検索どうしよう？
• 少数ノード系
• 最近の論文だと大規模系を対象にしすぎ
• 昔の論文のほうが数十ノードを対象にしていて実は役立ったりする
• これらの問題を解決すべきアルゴリズムを改良中

古橋さん (kumofs, kumo fast strage)

• えとらぼ株式会社のプロジェクト
• 小さいkey-valueを大量に保存
• 永続化させたい
• 名前
• 雲は落ちない！（会場でおおお！という声）
• 特徴
• replicationは３つ
• サーバおちても動作
• サーバを追加してスケールアウト
• 低遅延
• 機能
• set, get, delete
• 性能的にはmemcachedよりいい
• 応答速度はmemcachedよりすこし遅い
• set
• 非同期にすることで速くなる
• ハイブリッドP2P型
• Gateway
• ローカルホストに
• memcachedのプロトコルで扱えるように
• Manager
• サーバ一覧を監視
• GatewayやServerに通達
• ハッシュ空間は２つもっている
• 古いバージョン(rhs)と新しいバージョン(whs)
• 困った
• 再配置で大量のトラフィック
• Managerの分断問題
• Gatewayを中継するのはオーバーヘッド？
• deleteが一貫性を保証しない
• バックエンドDBにTC

西澤さん(ROMA)

• ROMA
• 複数マシンから構成されるP2Pを利用した
• Ruby実装のkey-value store
• Key : 4~6KB
• 社内クラウド
• 高負荷な状況であっても十分高速なデータアクセス
• Pure P2Pで自律的にノード管理
• Consistent Hash(環状)
• 各ノードが環全体のノード情報を保持
• クライアントが環情報を保持することも可能
• ROMAに始めてアクセスしたときにクライアントは環序湯法を取得
• クライアントとRoma間は独自プロトコル
• Java, Rubyで実装
• 開発者に分散を意識させない
• データPUT時に、ノードは左右のノードにレプリケーションされる
• データは３つ存在することになる
• クライアントはレプリケーション完了まで待つ
• 障害がなくてもPUTレプリケーション失敗するときがある
• ノードが忙しすぎるときとか
• マスターがPUT成功したらクライアントにはPUT成功を返す
• PUT失敗した隣接ノードはdirty flag
• dirty flagは自然に解消される
• ノードの参加、脱退が自由に可能
• 各ノードはじわじわ情報を伝搬させていく

首藤さん

• Overlay Weaver のデモ
• オーバーレイ上でのDNS
• PC１台で15万くらいのノードをシミュレーション
• 性能重視
• no-hop
• 全ノードが全ノードを知る
• スケーラビリティ（P2P由来）
• multi-hop
• 小さな経路表O(log n)以下
• XML-RPC, memcachedプロトコル
• memcache対応のためにあえて1つだけしかvalueを返さない、とか
• クラウド上の技術コンテストがあるのでぜひ参加してください！

藤本さん