インフラエンジニアのためのkumofs情報リスト構造：So-net Developer Blog：So-netブログ

	ブログをはじめるログイン

インフラエンジニアのためのCassand..｜インフラエンジニアのためのCassand.. ブログトップ

インフラエンジニアのためのkumofs情報リスト構造　[kumofs] [編集]

kumofsはキーバリューストアの中でも、機能よりもスピード重視なので、それ自体では
キーとバリューペアだけのシンプルな構造しか扱えず、検索やレンジスキャン、キー一覧
の取得などは行えません。
そこで、前回紹介したCAS操作を応用して、kumofsにリスト構造を作ってみます。
プログラマにお馴染みのリスト構造は、「値」と「次の要素を示すポインタ」を持ち
「次の要素」を順番に辿っていくことで、順番を持った値集合を作ることができます。
kumofsを使ってこれを実現するためには、バリュー値に「値、次のキー値」を持たせることで
実現できそうです。
一つのバリュー内に、値と（次の）キーを入れるためには、カンマ区切りにするなどしてデータ
を登録しておきます。
また、操作と構造を簡単にするために循環リストとします。
循環リストは、最後の要素の「次のキー値」が先頭要素の「キー値」になっていて、次の要素を
辿っていくと、先頭に戻ります。ちょうどリングのようなイメージです。

しかしこのままではkumofsで実装するには、面倒なことがおきます。リストに新しい要素を
追加しようとするとき、最後の要素のバリュー内の「次のキー値」を新しい要素のキー値に
置き換える必要があります。ところがkumofsのようなデータストアは複数プロセスから追加
更新が発生することが前提になるので、追加時に「最後の要素」がどこにあるのかを、プロセス
間で共有する仕組みが必要になってきます。

そこで、矢印を逆にしてみます。つまり、「値、前のキー値」をバリューに持たせます。

こうすると、要素の追加の時に更新しなければいけないのは、先頭キーのバリューになり、要素
が増えても先頭キーは固定されているので、各プロセスは先頭キーだけ知っていれば要素の
追加ができます。

要素追加時の操作は、新しい要素に「値、前のキー値(先頭のキー値のバリュー内にある）」を
登録し、最初のキー値のバリューを「値、新しい要素のキー」に更新します。
複数プロセスから要素の追加が発生する場合を考慮すると、先頭のキー値のバリューを更新する
にはCAS操作が必要になります。そうしないと、他のプロセスで先頭のバリュー値を上書きされて
追加した要素がリングから外れてしまいます。

では、実際に実装してみましょう。
その前に、前回紹介したrubyでのCAS操作を見やすくするため、メソッドを置き換えておきます。

require 'memcache'

class MemCache2 < MemCache

  def atomic_set(key)
    begin
      ret = self.cas(key,0,true){|value| yield(value) }
    end until ret == "STORED\r\n"
  end
end

CAS操作は次のようになります。

mem = MemCache2.new 'localhost:11211'
mem.atomic_set('key') {|value|
  valueに関する操作
}

本題のリスト操作に戻って、要素の追加は

mem.atomic_set('first_key') {|value|
    prev_key = value.split(",")[1]
    mem.set(new_key, new_value + ',' + prev_key, 0, true) 
    value = value.split(",")[0] + ',' + new_key
  }

各要素を順に拾っていくには、先頭キーから後ろ向きに辿っていきます。

current_key = 'first_key'
while 1
  current_value = mem.get(current_key, true)
  print "key=#{current_key}, value=#{current_value.split(",")[0]}\n"
  current_key = current_value.split(",")[1]
  if current_key == 'first_key' then break end
end

このようにリスト操作を実装しておけば、先頭要素のキーを知るだけで、集合の要素を
順番に取得することができ、キーや値の一覧も得ることができます。

2010-12-02 10:19 nice!(0) コメント(13) トラックバック(0)