Building a Space to Grow

time to read 5 min | 938 words

Udi has been talking lately about using spaces. Spaces are a distributed hash table that has the following operations: Write/Read/Take/Notify. The idea is that you can put entities or messages in the space, and something will handle them for you.

I find the idea interesting, since I had the chance to build such a system (~20 - 50 workers, each doing their own little part, independant from others) on a single machine. It turn out that this is a very nice approach to separating responsabilities and getting things done.

Scaling it out to a distibuted approach is interesting. I am going to ignore Udi's suggestion to get a ready-made solution and think about the way I would implement it. Just to make it interesting, I will throw in as many technologies as possible. Remember, this is a thought experiment.

Distributed hash table... hm, where did I heard that before? Memcached is exacatly what this is talking about and using it makes Read / Write / Take operations very easy, and notify nearly impossible. Obviously notify is a critical piece here, so I would rule Memcached out for now, it may be used as our backend, but it can't be the primary technology.

WCF has a peer to peer capabilities, and it may be interesting to try that. Read / Write / Take now becomes interesting, not in the implementation, but rather in deciding where to put the data? Ideally, I want to be ignorant of where the data is physically at, while maintaining the hash table aspect of it.

This means that for a read operation with a known key, I should be able to go to the exact node that contains the data that I want. This probably means that P2P is out, since I don't want to query the mesh in order to get a response, I would like to communicate directly with nodes. This bring me to a design decision, do I assume that we are using a mostly reliable and static set of nodes, or do I want to go for unreliable, dynamic nodes. The first means that I can do a simple hash of the key, mod by the number of known nodes, and go directly to the node by index.

This is how Memcached works, basically a two way hashtable. The problem with that is handling failures and additions. Because failures and additions both distrub the key distributions and require re-shuffling of the data. This is not so important in a cache, which is (by definition) allowed to lose data, but it is much more important if I am going to put business data there.

I think that I will decide on the second approach, unreilable and dynamic it is. This means that the operations for the infrastructure are now: Read / Write / Take / Notify - which is what the user is familiar with, but on the wire, we have:

  • FindFor(key) - search the P2P mesh for the node that has this key
  • FindPlaceFor(key, size, attributes) - search the P2P mesh for a node that is willing to accept the data
  • [Read | Write | Take]Direct - talk directly to the node - doesn't use the P2P mesh, rather talks directly to the node
  • Notify - sends a notify request on the mesh, where all the nodes will pick it up.

Now, let us think about notify, which is actually the reason that I started all this. We basically want to pass some sort of a query that will return results for us. When I am thinking about a query, there are several options, we can use something like this as the client side API:

var query = from msg in Space.OrderMessages
   where msg.Status == OrderMessageStatus.ReadyToShip;
Space.Notification += OnMessageNotified;

But how is this implemented? I can think of two ways, either NHibernate criteria or Lucene queries. I am probably going to lean toward Lucene here, it is much faster for mostly search scenarios, and very easy to work with.

A client for the mesh would expose an end point for getting notified about the messages, here I'll probably pass either the node id and the data, or just the node id and the key. Probably the second, so I can get reliable results in the case of more than a single client for the same type of message.

Transactions are a problem, though. We would usually want to do several operations, and I would really like them to run in a transaction. This is more complicated because I may need to interact with several nodes in a single transaction. I am not familiar enough with WCF to know how to make this work, although I do believe that this is possible.