GAE + GWT 004 – Composite Sharding

So a ‘sharded counter’ is technique used where fast writes are required to a single entity. Google provides a thorough explaination as to why to use this technique so do check it out.

When playing with my Collaba-Doodle, I’m realising I need something similar for the doodle canvas which can possibly be update by lots of collaborators simultaneously and thus the need for a ‘sharded doodle canvas’ becomes more and more apparent.

I was already using the sharding approach to track how many visitors my showcase was retrieving, so adapting it for a doodle canvas wouldn’t be too difficult. The main problem was that if I wanted to shard even more objects, I’d have go through the process of creating lots of sharded’elements’ copying and pasting lots of code which more or less does the same thing bar a few changes. So I decided to try a more generic approach to sharding – ‘Composite Sharding’  for reasons which will become apparent shortly. (I’m also 90% sure this is not a novel approach but I couldn’t find anything useful on the topic from some searches, so I’m putting it out here)

Many developers are familiar with the composite design pattern, where a parent and its children share the same interface, allowing both objects (from the user’s perspective) to be treated as a single object but behind the scenes, the object handles the delegation to children (if any). I tried to do something similar with my parent shard (ShardedElement) and the children shards (Shard).

So, my ShardedDoodle and DoodleShard would implement some Doodle Interface (IDoodle – not related to ‘the fruit’ products) and have:

• addChanges(ChangesFromUser)
• getChanges(startTimeOfChanges)

We can see, that this composite sharding approach will work as adding changes can occur to a single Doodle shard independantly. When retrieving the changes, we traverse all doodle shards and get the changes from each shard to give us all the relevant changes.

To make my life easier, I templated and abstracted out all the base code for sharding into the three main components:

• ShardedElement<T extends Shard>: abstract class, handles storing and retriving of shards. Subclasses should extend and implement an ElementInterface.
• ShardCounter: class which handles book-keeping of shards matching the ShardElement name. This object is internal to a shardedElement and is never exposed.
• Shard: abstract class which handles storing and retriving of data from the datastore. Subclasses should extend and implement an ElementInterface.

In my Doodle Canvas example above:

• DoodleShard extends Shard implements IDoodle
• ShardedDoodle extends ShardedElement<DoodleShard> implements IDoodle

And that’s really all there is to it. Because most of the grunt work is handled by the ShardedElement we can simple get a random shard via getShard() and do PUT operations on it or we can get all the shards getShards() and do GET operations on them.

I’m looking forward to seeing how well this works in other scenarios besides counting and my doodle canvas… maybe I’ll try the guestbook =P

I’ll put the code up for this at one point in time…

Advertisement