キーバリューストア上に構築するFIFO

キーバリューストアはフラットな名前空間でキーとバリューの1:1ペアを保持するだけの簡単なデータ構造しか提供しませんが使う側の工夫で好きな構造を作って有効利用できるはずです。

そこで擬似コードを書いてみました。memcachedプロトコルの上でFIFOを実現します。
keyに「データ+ユニークな乱数」valueに「次の要素へのポインタ」を保持させる事により、memcachedプロトコル上のgets,cas,addなどの基本的な操作でキーバリューストアを構築できます。ユニークな乱数を使うのは、全く同一の内容でもキーバリューストアに別のキーとして保存させるためです。

// queue
class queue:

	string head,tail // これらのデータはFIFOを共有するクライアント同士で共有する
	Memcached& kvs

	__Init(Memcached _kvs):
		head = RandomString()
		tail = RandomString()
		kvs = _kvs
		
		string dummy = rand()
 		kvs.add(dummy, NULL)
		
		kvs.add(head, dummy)
		kvs.add(tail, dummy)
	
	enqueue(string data):
		string newdata = data + RandomString()
		kvs.add(newdata, NULL)
		while(1):
			string old_tail, int tail_uniq = kvs.gets(tail) // 現行のtail情報からtailのキーを探す
			string curr_tail, int new_uniq = kvs.gets(old_tail) 
			
			if(curr_tail == NULL): // ちゃんとtailに到達したなら
				bool result = kvs.cas(curr_tail, new_uniq, newdata) // enqueue操作の線形化ポイント
				if(result == false): // 他のクライアントがenqueueした
					continue // 初めからやり直し
				else: // 最後尾の更新に成功したなら
					kvs.cas(tail, new_key, tail_uniq) // tailを更新する。こちらの操作は投機的
					/* ↑の操作が成功する場合は、tailの指している先が変化しなかった場合
					この操作が失敗する場合は「他のスレッドが訂正してくれた場合」だけ */
					return;
			else: // tailが指してた物より続きがあったら
				kvs.cas(tail, tail_uniq, curr_tail) // ちゃんとtailが最後尾を指すよう訂正してやり直し
	
	string dequeue(void)
		while(1):
			string old_head, int head_uniq = kvs.gets(head) // 現行のhead情報を獲得
			string old_tail, int tail_uniq = kvs.gets(tail) // tailも確認
			string next, int next_uniq = kvs.gets(old_head) // headが指すキーのバリュー値nextが次にqueueされるデータ
			
			if(old_head == old_tail): // 何も無いように見えるなら
				if(next == NULL): // 本当に何も無いか確認
					return NULL　// 何も無かったらNULL
				else:
					kvs.cas(tail, tail_uniq, next) // ちゃんとtailが最後尾を指すよう更新
			else:
				bool result = kvs.cas(head, head_uniq, next) // dequeue操作の線形化ポイント
				if(result == true): // headの更新に成功したなら
					kvs.delete(old_head) // キーを削除
					return RemoveRandomString(old_head) // 削除したキーから乱数を剥がして返す

実際にこれをmemcached上で動かすとLRUに従ってキューの中間データが消えるのでFlareやkumofsなどの上でしか実用できません。
また、queue程度の処理であれば単一のサーバに集中させた方が、クエリをこのように何度も飛ばすことなく高い性能を得られると思います。
わざわざキュー全体をキーバリューストア上で行うのは対故障性をキーバリューストア側で担保できることと、莫大な量を保存できる事しか利点が無いと思います。