kumofs-0.4.0リリース - CAS操作をサポート

新たにCAS（Compare-And-Swap）をサポートした、kumofs-0.4.0をリリースしました。
memcachedのテキストプロトコルで、getsコマンドとcasコマンドを新たに使うことができます。
後方互換性は保たれています*1。新機能を利用するには、kumo-gatewayとkumo-serverを更新してください。

CASとは？

CAS（Wikipedia）は Compare-And-Swap の略で、ある値を取得したあと、その値が別のプロセスから更新されていなければ（Compare）変更を適用する（Swap）という操作を、アトミックに実行することができます。
CASを利用することで、kumofs上にキューやカウンタ、連想配列、ロックなどを実装することが可能になります。

例えば kumofs でキューを実現する擬似コードは、次のようになります：

KEY = "myqueue"

# 初期値を設定しておく
$db.set(KEY, [].to_msgpack)  # シリアライズした配列を保存

def pop
  while true
    value, unique = $db.gets(KEY)  # 現在の値と、何か一意な値が得られる
    array = MessagePack.unpack(value)  # 値をデシリアライズ

    element = array.pop                # 値を変更

    success = $db.cas(KEY, array.to_msgpack, unique)  # この間に値が変更されていなければ、変更した値を保存

    # 保存が成功したら、取り出した値を返す
    if success
      return element
    end
    # 値が変更されていたら、リトライする
  end
end

def push(element)
  while true
    value, unique = $db.gets(KEY)
    array = MessagePack.unpack(value)

    # ここだけがpopと異なる
    array.push(element)

    success = $db.cas(KEY, array.to_msgpack, unique)

    if success
      return
    end
  end
end

このコードでは while true と無限ループしていますが、実際には堅牢性を確保するために（十分に長い）タイムアウト時間を設定した方が良いでしょう。
この pop と push の実装を見ると、値を変更する部分のコードだけが異なることが分かります。そこで共通部分をまとめると、次のようになります：

def atomic(&block)
  while true
    value, unique = $db.gets(KEY)
    object = MessagePack.unpack(value)

    # ここだけが異なる
    object = block.call(object)

    success = $db.cas(KEY, object.to_msgpack, unique)

    if success
      return object
    end
  end
end

# atomicを利用してpopを実装
def pop
  element = nil

  atomic do |array|      # 現在の値を受け取って
    element = array.pop  # 値を変更して
    array                # 変更した値を返す
  end   # この間に値が変更されていたら、リトライされる

  return element
end

# atomicを利用してpushを実装
def push(element)
  atomic do |array|
    array.push(element)
    array
  end
end

カウンタも実装してみたくなりますが、ここで実装した atomic を使えば、話は簡単です：

# atomicを利用してaddを実装
def add(num)
  atomic do |value|      # 現在の値を受け取って
    value = value + num  # 値を変更して
    value                # 変更した値を返す
  end   # この間に値が変更されていたら、リトライされる
end

def sub(num) add(-num) end
def incr()   add(1)    end
def decr()   sub(-1)   end

このようにCASを使うことで、単純なkey-valueストアに上に様々なデータ構造を実装することが可能になります。

kumofsのCAS

kumofsが実装しているCAS操作の意味論は、比較が失敗すれば、値の更新は失敗するというものです。言い換えれば、比較が成功したときに、値の更新が成功するとは限りません。
現象として値の更新が失敗した場合は、何度かリトライする必要があります。上記のatomicのように、アプリケーションでリトライすることを期待しています。

kumofsでは、ノードの数が増減したときに、double-hash-spaceアルゴリズムに基づいて、データの移動を行います。
kumofsはこの移動中でもSet操作やGet操作を処理することができますが、CAS操作については古いデータ（=比較対象のデータ）を必要とするため、移動が完了した後にしか（単純には）受け付けられません。
このためノードの数が増減したあとは、しばらくCAS操作が失敗する期間が発生します。しばらくリトライしていると、その内に成功するようになります。

Have fun with kumofs! The Kumofs Project

*1:gatewayやserverの一部だけをアップデートしても問題が起きません。