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

greeさんで開催されたKey Value Store勉強会に行ってきました。

時間にして4時間超え、内容も国内のKey-Value Storeなソフトウェアの最前線の話ばかりで相当なボリューム。以下、メモってたのを残しておきたいと思います。(誤字、脱字、内容に誤りを含むものなどありましたらお伝えください)また、発表者の方やプロダクトについて、ざっくり調べてURL見つけられたものについてはリンク張っています。

森さん / 末永さん  

  • groonga
    • Sennaの後継エンジン
      • 融通が効かないのがSennaのデメリット
    • スコア算出式のカスタマイズなど
    • Sennaの転置索引
    • 索引の構成部品を自由に組み合わせて使える
    • APIもいろいろ
      • QL
      • DB
      • Low Level
    • memcached互換のkey-value store
    • バイナリのみ対応
      • 計測
        • クライアント memstorm-0.6.8
        • memcachedと同じくらいの性能
        • valueサイズが小さいとほとんどかわらない
        • valueサイズが大きくなると少しパフォーマンス悪くなる
    • DB的な使い方もできる
      • Scheme以外の言語バインディングもできる(はず
    • 名前の由来
      • ブルース音楽の発祥地(?
    • Sennaともあんましかわらない(はず

山田浩之さん (LuxIO)

  • IBM, Yahoo, MetaCast
  • LuxIO (ラックスIO)
    • データベースマネージャ
      • C++
      • B+tree,
    • 分散はなし
  • ほかに不得意なことがすこし得意
  • 分散検索エンジンLuxの内部データベースとして開発
  • 普通のB+-tree
  • 特徴1
    • mapped index
    • index部を全部mmap
      • index部を実メモリより小さいシステムが対象
  • 特徴2
    • 長いvalue
    • 4Gまで
    • node size(page size)をこえたvalueも余計なオーバーヘッドなしで扱える
  • 特徴3
    • 効率的なappend
    • paddingなしでLinkedListのデータ構造
  • SSDに向いてる?
  • 使い道
    • key-valともに小さいデータで構想なアクセスが必要な場合
    • 実メモリ以下のデータベースという制約あり
    • 大きなvalueを扱いたい場合
    • 大きなvalueをどんどん追記したい
  • 向かない処理
    • 削除が多い処理
    • 小さいデータをたくさんリンク
      • seekのオーバーヘッドが大きすぎる
    • Read,Writeの激しいアプリ
  • 分散はたぶんしない
  • Hashはつくるかも
  • read lockはなくしたい
    • 読み込みを重きをおく
  • 単純に作ってみたかった
  • 名前の由来
    • リッチな検索エンジン
    • 某シャンプーからとった(←ウケた

平林さん (TokyoCabinet / TokyoTyrant)

  • 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は1台あたりのスループットを最大化する技術
      • 1台あたりでできることは増えてる

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

  • 興味分野
    • データ圧縮、自然言語処理、全文検索
  • 文字列のキーを利用していろんな値を格納したい
  • 方法1
    • 木による格納
    • キーに対してtrieなどの木構造を構築し、木の接点、葉に値を格納など
  • 方法2
    • ハッシュによる格納
  • 木によるキーの格納
    • 各枝に文字が付随、つなげるとキー
    • 値は接点の先
  • 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もわりあてていいの?
  • 11211はmemcachedのポートとして公式に決定された

安井さん(repcached のなかみ)

  • KLabの方
  • memcacpedにレプリケーション機能をつけたもの
  • 案1 マルチスレッド
    • スレッド作成
    • キューをつくってセットされたデータを入れる
    • メリット
      • 本体への影響がすくなそう
      • 比較的簡単
    • ただし、、
      • アクセス数が多いときに問題発生
      • 忙しいときにレプリケーション処理が追いつかない
      • キューがあふれる
      • memcachedのレスポンスが悪くなる
  • 案2 シングルスレッド
    • libeventを利用
    • ハンドラを登録しておくとコールバックしてくれる
    • 自分でselect(2), poll(2)とかしなくていいのでらくちん
    • set/addのついでにrepl
      • プロトコルの処理中にレプる必要
      • どうしても応答時間が長くなる
  • 案3 Pipeにキーを書き込むように変更
    • だいぶよくなった
    • やっぱりリクエストが多くなれば素のパフォーマンスよりもすこし悪くなる
  • 今のところ2台までの構成
    • 1台だけレプリケーション?
    • 3台使わないといけないシチュエーションがまだない
  • 利用用途
    • 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チューニング重要
          • パフォーマンスが4桁あがった
          • read/writeは計画的に
      • アルゴリズムの限界
        • 人気の集中
        • 非対称ノード
          • Virtual node増減させる?
          • LC-VSS by Godfrey et al.
          • 大量のノード前提
        • データ局所性
          • DHT => すべてをぶちこわす。。!
            • 似たようなコンテンツもバラバラ
          • 検索どうしよう?
        • 少数ノード系
          • 最近の論文だと大規模系を対象にしすぎ
          • 昔の論文のほうが数十ノードを対象にしていて実は役立ったりする
    • これらの問題を解決すべきアルゴリズムを改良中

古橋さん (kumofs, kumo fast strage)

  • えとらぼ株式会社のプロジェクト
    • 小さいkey-valueを大量に保存
    • 永続化させたい
  • 名前
    • 雲は落ちない!(会場でおおお!という声)
  • 特徴
    • replicationは3つ
    • サーバおちても動作
    • サーバを追加してスケールアウト
    • 低遅延
  • 機能
    • set, get, delete
  • 性能的にはmemcachedよりいい
  • 応答速度はmemcachedよりすこし遅い
    • set
      • 非同期にすることで速くなる
    • ハイブリッドP2P型
      • Gateway
        • ローカルホストに
        • memcachedのプロトコルで扱えるように
      • Manager
        • サーバ一覧を監視
        • GatewayやServerに通達
    • ハッシュ空間は2つもっている
      • 古いバージョン(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時に、ノードは左右のノードにレプリケーションされる
    • データは3つ存在することになる
    • クライアントはレプリケーション完了まで待つ
  • 障害がなくてもPUTレプリケーション失敗するときがある
    • ノードが忙しすぎるときとか
  • マスターがPUT成功したらクライアントにはPUT成功を返す
    • PUT失敗した隣接ノードはdirty flag
    • dirty flagは自然に解消される
  • ノードの参加、脱退が自由に可能
    • 各ノードはじわじわ情報を伝搬させていく

首藤さん

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

藤本さん

  • Flare
  • memcached互換
    • delete key expire_date(!)
      • 実装していない
    • 勝手拡張も
  • Diskに書き込み(メモリ上じゃない)
    • TCベース
    • Slaveの数だけenque
  • set → getですぐに取得できない場合にset syncコマンドがある
  • proxy機能も
  • 2000 qps
    • greeの足跡で使ってる
      • mixiの足跡でTTを使っていると信じていた(←某記事は少し間違ってたみたい)

まとめ

メモ読み返しただけでも相当濃い内容でした。同時にこの分野のトレンドはざっと見渡せた感じ。印象深いのはTokyo Cabinetを最下層のストレージに使って、その上でいろんな展開をしている、というトレンドはありそう。あと岡野原さんや首藤さんたちの学問的なアプローチからの視点によるKey-Value Storeの話も面白かったです。ハッシュ関数のトレンド(!)なんてあるんですねー。

ボリュームがあったからかもしれませんが、久々にインプットが相当多い勉強会でした。企画、司会をされた太田さん、場所を提供いただいたgreeのみなさん、どうもありがとうございました!

関連広告

Trackbacks:2

TrackBack URL for this entry
http://blog.katsuma.tv/mt-tb.cgi/194
Listed below are links to weblogs that reference
Key-Value Store勉強会に行ってきました from blog.katsuma.tv
日本全国鍵値保存機構勉強会に行ってきた from developer’s delight 2009-02-21 (土) 09:02
GREEで行われた勉強会に行ってきた。ビール飲みながらkey-valueな方々が語りあう会。groonga, lux IO, Kai, TokyoCab...
[kvs]Key-Value Store (Strage) 勉強会にお邪魔してきました from cooldaemonの備忘録 2009-02-22 (日) 22:25
id:Voluntas さんのコネで潜り込んできました。 当初の目当ては、id:teahut さんによる Kai の発表と、首藤さんによる Overla...

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

Search
Feeds

Return to page top