A naive implementation of log-structured sets in Ruby.

append_only_sets.rb

# # Append-only sets
#
# Dustin Sallings described [how to implement sets in memcached using only
# atomic commands](http://dustin.github.com/2011/02/17/memcached-set.html).
# This implements the necessary encoding/decoding for that
# scheme. You could then use this with a database that doesn't support sets.
#
# N.B. This is a naive implementation (see the pending specs), but it's fun.

# An append-only set is, after all, a set
require 'set'

class AppendOnlySet < Set

  # Create a new append-only set
  def initialize(*args)
    # We want the same behavior as a normal set
    super(*args)

    # Once the parent class is done initializing, we need to initialize the
    # append-only structure
    to_append_only
  end

  # We need a way to fetch the log for this object.
  def to_append_only
    # We've memozied the structure here. If it doesn't exist, we take each
    # element in the set and add it to the set.
    @structure ||= map { |v| "+#{v}" }.join(' ')
  end

  # We have to override how objects are added to the set.
  def <<(element)
    # First we grab the parent class's behavior.
    super(element)

    # Then we update the structure of the log.
    @structure << " +#{element}" 
  end

  # We also need to override how objects are removed from the set.
  def delete(element)
    # Again we borrow parent class functionality.
    super(element)

    # Then we add a removal to the log.
    @structure << " -#{element}"
  end

  # Finally, we need a way to load an append-only set from a log.
  def self.from(value)
    # We take the string that was loaded and split on spaces. Then we create
    # a new AppendOnlySet and iterate over each chunk.
    value.split.inject(self.new) do |set, chunk|
      # We first grab the op (`+` or `-` out of the log).
      op, key = [chunk.slice(0, 1), chunk.slice(1, 1)]

      # Now we're going to apply this op to the set.
      if op == '+'
        # Additions add.
        set << key
      else
        # Removals delete.
        set.delete(key)
      end

      # The first rule of Enumerable#inject is, don't forget to return the
      # object at the end of the block.
      set
    end
  end

end

describe AppendOnlySet do

  let(:set) { AppendOnlySet.new(%w{a b c}) }

  it "encodes a set as an append-only structure" do
    set.to_append_only.should == '+a +b +c'
  end

  it "encodes primitive values directly"
  it "encodes composites using length and body elements"

  it "adds an element to an existing structure" do
    set << 'd'
    set.to_append_only.should == '+a +b +c +d'
  end

  it "removes an element from an existing structure" do
    set.delete('c')
    set.to_append_only.should == '+a +b +c -c'
  end

  it "decodes a set" do
    value = set.to_append_only
    AppendOnlySet.from(value).should == set
  end

  it "tracks the dirtiness of the set"

end