The system proposed consists of a smaller buffer layer in memory and an incarnation table on flash memory that is augmented by bloom filters maintained in memory as well.

Performance evaluation on the system confirms it is capable of a few orders of magnitude more operations per second per dollar than the studied existing alternatives.

The key-value store built is a pretty common log-based solution, with some mostly insignificant optimizations for using SSDs as storage. The authors sort of cheat by implementing a hash-based toy solution that only supports very basic operations. They then unfairly compare it with a full-fledged key-value store (BerkleyDB). The latter provides operations such as iterators and compare-and-swap. Iterators require an ordered structure (e.g. B-Tree, SkipList, etc.) which significantly slows down insertion and deletion operations as well as tremendously increasing program complexity. Atomic compare-and-swap operations may be used as building blocks for supporting transactions; but they need to block several other operations on the same key which may slow down the system further.

The key to the system is partitioning, and the authors argue that probably all useful applications can easily manage to naturally find a way to partition their data. Several very different in-house applications are given as examples, with the partitioning scheme provided. Full ACID guarantees are provided within a partition while still maintaining high availability. Cross partition queries need to sacrifice either consistency, or availability, but the decision is left to the application which can choose either option on a transaction by transaction basis: Full ACID guarantees may be achieved cross-partitions at the cost of availability by using two-phase commit; or higher availability may be opted for by using asynchronous message delivery queues.

A lot of complexity is dealt with at the application, however a Megastore Library is provided to ease application programming, but the exact contents of this library are a mystery. Applications need to provide a schema for their data and define partitions. Here is an example:

CREATE SCHEMA PhotoApp;

CREATE TABLE User
required int64 user_id;
required string name;
PRIMARY KEY(user_id), ENTITY GROUP ROOT;

CREATE TABLE Photo
required int64 user_id;
required int32 photo_id;
required int64 time;
required string full_url;
optional string thumbnail_url;
repeated string tag;
PRIMARY KEY(user_id, photo_id),
IN TABLE User,
ENTITY GROUP KEY(user_id) REFERENCES User;

CREATE LOCAL INDEX PhotosByTime
ON Photo(user_id, time);

CREATE GLOBAL INDEX PhotosByTag
ON Photo(tag) STORING (thumbnail_url);

The PAXOS protocol is used throughout the solution to provide consensus on the ordering of operations. In fact there is even a special replica type that doesn’t store data (only logs) which can still be used in the PAXOS voting process, without having large storage needs. The architecture is very flexible: the opposite kind of replica is also available – read-only replicas distribute the load, but participate in the global ordering process – thus not slowing it down (writes are impossible on such replicas).

Another interesting, simple and fast hash-function for actual use is the SuperFastHash: http://www.azillionmonkeys.com/qed/hash.html

This storage service is optimized for a specific workload such as that of cacheing the entire internet. Other usage patterns, such as random writes will perform poorly. Even random reads are less optimized than sequential ones, as the block size used in the system is 64 MB (because of the underlying GFS infrastructure). Data may only be accessed at a row level and although atomicity is guaranteed on a per-row basis, multi-row transactions are impossible without a client orchestrated algorithm that includes separate locking. Also deleting data may not be done instantly; it may take a very long time before data may be deleted. All the files written to disk are immutable, meaning that they will simply be garbage collected once they contain no more useful data. This approach also wastes a lot of disk space. I would however like to point out that these drawbacks, are all a result of trade-offs being made to support the expected workload; they are not results of poor design decisions.

Writes need to be propagated to all regions and this is done with a guaranteed delivery publisher/subscriber service called the Yahoo! Message Broker (YMB). This service guarantees delivery even if parts of it fail. Records are grouped together in so called ‘tablets’ which are the objects servers work with. The paper calls these servers “Storage units” and basically allows for any hardware storage device to be used. Tablet controllers are responsible for assigning tablets to storage units and performing load control by moving tablets around.

The service is live and being used in several Yahoo! Products.

GFS/Colossus running on top of the hardware along with MapReduce/Bigtable etc. All of them have small improvements.

Spanner – storage and computation system that runs across many datacenters.

Single master pattern is prevalent and can scale very well.

Canary requests (test out a request on one machine to see if it crashes it).

Backup requests to minimize latency.

Store ranges rather than hash values.

The system only supports very few operations – essentially only get and put, with some extra versioning constraints. In the face of failures, the system state may branch and in some cases merging back these branches is pushed to the client applications which thus become more complex. Probably one of the most annoying things about this paper is the writing style – the authors just rant about loosely related things for most of the paper – it is very ambiguous most of the time whether they are talking about their own system or about general things such as P2P networks, SLAs, or distributed databases.

The authors briefly study the security implications of allowing multiple applications that run side by side to execute customized code. The report is however hardly thorough and the implemented solution lies in severely restricting the capabilities of the language the scripts must be written in as well as imposing communication caps between the nodes and restricting access to only applications stored under the same key.

All in all the system proves very versatile despite the heavy restrictions and I find the idea of allowing active tweaks to the storage structure on an application by application basis very interesting. Such an approach far extends the usability of a system beyond its intended purpose without modifying an established well documented and implemented framework.

“Scatter implements a simple DHT model in which a circular key-space is partitioned among groups. Each group maintains up-to-date knowledge of the two neighboring groups that immediately precede and follow it in the key-space. These consistent lookup links form a global ring topology, on top of which Scatter layers a best-effort routing policy based on cached hints. If this soft routing state is stale or incomplete, then Scatter relies on the underlying consistent ring topology as ground truth.”

Additional small optimizations to the algorithm are presented, but don’t make a large impact.

Again, this is a simple software product employing known techniques that simply chooses tradeoffs that optimize for the common use case. In this case the storage system is used within Facebook and has been designed for their particular workloads. I have pointed out some of the downsides of the tradeoffs in the previous paragraph; however this doesn’t seem to be a weak point in the design.

The background story and mathematical proofs are given in the form of a fable describing an ancient civilization that had developed the algorithm for use in their parliament. The parallel to distributed systems is given later in the paper and one interesting aspect is that the parliament was described as having a much higher rate of people coming and going. The distributed system equivalent would only have someone (a machine) leave upon its failure, and it is reasonable to assume this happens less often. This aspect proves the system to be sturdy under much worse circumstances.

The data pairs enter the structure in through the LogStore and make their way up to the SortedStore once the previous data structures fill up. There is an impressive amount of parameters that can be tuned with this approach, such as the sizes of the three data structures and the frequency of the movement of data through them. Unfortunately the large number of tuning knobs is the greatest weakness of this solution – finding the proper balance for a given workload is nearly impossible and there are no good general purpose values available either.

The system may be used as a building block for a larger scale distributed version of the algorithm by assigning master copies to deal with the “In-memory” aspect of the solution, while multiple replicas can handle the “On-flash” part.

The proposed solution lets database designers use these simple building blocks along with other carefully designed aggregator blocks to quickly define a customized key-value storage solution that is optimized for a certain workload. For example one can have an aggregator on top of a log and a hash table in order to batch hash table modifications for increased speed and longer storage (SSD) life. Thus all inserts are done in the log and all lookups are done on the log first and on the hash-table second in case an entry isn’t found. In order to preserve fast read speeds the size of the log is kept small – whenever a certain threshold defined in the aggregator piece is reached the log gets compacted into the hashtable. It’s important however to remember the benefit of this system isn’t in the resulting key-value storage system, but in the ease with which a designer can build this system in a few minutes by specifying a few parameters to three available building blocks.

It might also be important to note that customized building blocks are fully allowed and that there is no bound to their complexity, but the strength of the system, again, lies in fast prototyping and testing out different data storage options. An interesting note would be the fact that a system like Google’s “Bigtable” can be quite easily built within Anvil.

As the authors point out, the overall application structure for Piccolo is very similar to that of the CUDA platform (NVIDIA GPU computing). Both these technologies utilize control functions that launch kernels to execute the same piece of code over multiple processors/computers. Within the kernel, different execution paths may occur based on the position of the kernel (the thread number). Kernel synchronization in both platforms is only possible on global barriers where the initial control function waits for the completion of all previously launched kernels. There isn’t any way of pairwise synchronization among concurrent kernel instances; however the piccolo system allows for communication via the key-value table proposed.

The solution proposed isn’t however impressive by any standards – a simple versioning scheme is used to make transactions atomic. Thus the state of the memory is always consistent. In case of corruption upon writing, the memory can simply return to the most recent consistent state.