This is the year 2011, and the latest fad successful Web 2.0 platform is Grafffer, a free social networking and messaging service that allows its users to send and view each other's short pictorial messages (known as grafffs). The story of Grafffer is one of exponential growth and rapid technological evolution, with the extprot-based Grafff protocol at its core.
The Grafffer service is based on the exchange of grafffs, short pictorial messages whose length was limited to 140 bytes at service launch (this limit was raised posteriorly, but remains low to this day). Grafffs can be sent and received via the Grafffer website, RSS, email, SMS, using one of the many 3rd party Grafffer applications, or through specific devices like the iGrafff.
Mirroring the evolution in the applications and devices used to create and represent Grafffs, the Grafff protocol underwent a number of changes. The ability to extend the protocol cleanly while retaining compatibility with existing data proved to be a key technological enabler that made Grafffer's growth possible.
Original protocol
The Grafffer developers realized early on that Grafff messages were to remain as short as possible if the service was to scale, so they engineered a binary Grafff protocol using extprot. Grafff messages were originally defined as follows:
(* Grafff protocol 0.0.1 *)
type point = (int * int) (* a pair of pixel coordinates *)
message shape =
Polygon { vertices : [ point ] } (* list of points *)
| Circle { center : point; radius : int }
message grafff = { objects : [ (shape * byte) ] }
(* list of tuples with shape and grayscale value *)
A Grafff is essentially a list of objects, each one being either a polygon or a circle.
Given this protocol definition, a Grafff like
{ objects =
[
(Polygon { vertices = [ (0, 0); (0, 1); (1, 0) ] }, 100);
(Circle { center = (2, 2); radius = 1 }, 0)
]
}
is serialized as this compact 55-byte message:
00000000 01 35 01 05 32 02 01 1e 02 01 19 01 05 16 03 01 |.5..2...........| 00000010 05 02 00 00 00 00 01 05 02 00 00 00 02 01 05 02 |................| 00000020 00 02 00 00 02 64 01 0f 02 11 0a 02 01 05 02 00 |.....d..........| 00000030 04 00 04 00 02 02 00 |.......| 00000037
The extprot compiler (extprotc) uses the above definition to create the functions to serialize, deserialize and pretty-print messages, but a human-readable dump of a binary message can be generated even in the absence of the original protocol definition because messages are self-describing. This is the output of a generic extprot decoder written in Ruby when given the above binary message:
{
[
{ { [ { 0; 0 }; { 0; 1 }; { 1; 0 } ] }; 0x64 };
{ T1 { { 2; 2 }; 1 }; 0x0 }
]
}
Here, T1 is tag 1 and corresponds to a Circle. The first shape has got tag T0 (Polygon), which isn't printed by inspect_msg.rb, for the sake of concision.
Early extensions
The Grafff protocol underwent its first extensions when it was launched in Japan in association with NTT (Grafff was first made available through NTT DoCoMo's i-mode). This launch triggered changes in the Grafff protocol to cater to the needs of the Japanese consumer.
Being exposed to calligraphy from an early age, Japanese subscribers soon expressed the need to support different brushes. Moreover, arbitrary polygons were required.
It was critical that existent Grafffs keep working with the newer devices. Fortunately, extprot allowed to extend the protocol trivially by changing this definition:
(* Grafff 1.0 *)
(* other types identical to Grafff v0.0.1 *)
type brush =
Default
| Calligraphic int (* size in pixels *)
| Hello_Kitty int (* size of head in pixels *)
message grafff = { objects : [ (shape * byte * brush) ] }
A Grafff is no longer a list of shapes, but a list of shapes along with associated brushes. Existent Grafff messages lack the brush element, so the Default brush is used by default by the systems supporting the new protocol. Older clients simply ignore the brush element. This allows clients using both protocol versions to coexist and interoperate safely.
The extension that has been applied here is the addition of an element to a tuple. Since the new element has got a default value (Default), this extension is both backward and forward compatible.
PokéGrafff! and the arrival of colors
The Grafff service became immensely popular among Japanese youngsters with the arrival of the PokéGrafff! media merchandise, which included trading cards (Grafffs grafffed by celebrities and original material), video games, a manga series and an anime adaptation. (The PokéGrafff! anime follows the adventures of young PokéGrafff! Masters in their quest to obtain 150 mythical Grafffs.) Shortly after the launch of PokéGrafff!, the iGrafff was marketed to the adults that had been exposed indirectly to the Grafff service via their children. (It is rumoured that the adult industry played a large role in the success of Grafffer over its competitors, because adult contents in extended Grafffer formats soon became popular.)
The needs of the public PokéGrafff! was addressed to required two major modifications to the Grafff service:
bright, colorful Grafffs
polygon filling
Again, it was essential that the existent catalog of Grafffs keep working with the new devices. Moreover, new Grafffs were to work in older clients, with graceful degradation.
The Grafff protocol was modified this way:
(* Grafff 2.0 *)
(* other types identical to Grafff v1.0 *)
type opt_byte = Unset | Set byte
message color = { value : byte; hue : opt_byte; saturation : opt_byte }
type filling = No_filling | Alpha_filling byte
message grafff = { objects : [ (shape * color * brush * filling) ] }
There are two extensions at play here:
a new element has been added to a tuple (same as the "brush" extension)
a primitive type (
byte) has been promoted to a complex type (color)
color, which used to be a mere byte representing a grayscale value, is now a structure holding hue, saturation and value. This extension requires that the value be placed first in the structure (this doesn't change anything in the client code, since it will be accessed by name, with something like c.value). Moreover, the hue and saturation information is encoded carefully to provide default values (Unset = arbitrary hue, saturation 0).
Thanks to these protocol changes, older clients can reproduce new Grafffs with graceful degradation, and newer devices have access to an extensive back-catalog of grayscale Grafffs as well as new ones with extended functionality like colors and polygon filling.
Conclusion
The extensibility of the extprot-based Grafff protocol played a key role in Grafffer's growth, by allowing to introduce new functionality in the protocol while retaining forward and backward compatibility with existent data and clients. This enabled the quick introduction of improved terminals and the steady evolution of the Grafffer service, leading to its exponential growth.
extprot's rich abstract syntax allows to serialize complex data structures easily, and the compact, yet simple low-level encoding supports a number of protocol extensions that retain backward and forward compatibility.
Comments
This is an amazing example. I really didn't get it in the last blog about extprotc but seeing the binary dump and the recovered object in Ruby really clarified the example.
I know that this is going to be aimed at developers because it is a complex topic but I hope that some genius will come along and document it in their blog in a way that will make it obvious to everyone. This is such a powerful syntax that I hope everyone can get on board instead of just core developers of languages (and _why of course).
Excellent work. I hope very much to see more news of extprot's adoption in major projects. I know I'm considering rewriting my Ruby-Erlang bridge to see if this could solve some of the data problems I was having. Perhaps just the concepts of default actions will be enough to bridge my intellectual gaps :)
Regards!
Chuck, the basic ideas behind extprot are obvious when you have been exposed to algebraic types (sum and product (aka tuples) types) as found in OCaml. I have to confess it took me a while to simplify the original design, though. It's one of those things that look trivial after you come up with them.
Your comment helped me realize that the "universal message pretty-printer" in Ruby could be simplified considerably: I have rewritten it as a universal decoder that uses Ruby's built-in pretty-printing (
#inspect), and it now takes ~100 lines to decode any message encoded with extprot. I'll be writing about this soon. Thank you!PS: Erlang would be an interesting target. Once I'm done with Ruby, I'll know enough about how to handle extprot messages in a dynamically typed environment to at least document the process (a sort of "HOWTO implement extprot (de)serializers"). A universal decoder (with no provisions for primitive type promotion, so comparable to a binary JSON with extra types) takes around 100 lines in Ruby, so it should be quite simple in Erlang, too.
Nice work!
This is very like (probably isomorphic) to my UBF system (see http://www.sics.se/~joe/ubf) - two ideas in UBF that you could steal are the caching convention (if you send the same term twice, don't, send it once with a cache index, then second and subsequent times send the cache index (which in UBF is a single byte)). Also use contracts to define the legal sequences of messages.
Pity more people aren't interested in protocols.
/Cheers
Thanks for the pointer to UBF, it's very interesting. extprot is indeed similar. The main difference (besides the encoding, of course) I can see is that semantic tags are defined in the UBF(A) layer and not in UBF(B). In fact, even though the latter supports alternation types with
T1 | T2, there's no way to require a specific semantic tag, is there? For example, how does one specify something likewhich corresponds to
in my notation? It looks to me like you'd only get a
inttype and the semantic type would have to be handled "dynamically" by the client code. This divergence probably comes from the different way to encode discriminated unions in Erlang and ML. Whereas in the latter the tag (constructor) belongs to the type, so to speak, in the former what you do is pattern match over a tuple whose first element is a constant (the constructor), right? If so, a discriminated union would be done in UBF withunit() = cm | inch; length() = {unit(), int}UBF's caching convention is similar to what you'd have to do to handle references (for recursive structures), with the key difference that the there's no recursion here. It seems quite easy to implement (fortunately, I have several unused "wire types" left in extprot's encoding), but how much space does it save in practice? Repeated values (of significant length) are rather exceptional in the data I have in mind, maybe because UBF(A)'s constants map in extprot to a constant constructor encoded with only one byte, generally.
I'll have to think about contracts. To be honest, I never thought that much beyond allowing disjoint message unions, mainly because my main use for extprot is serialization and minimalistic protocols more than complex ones (in the sense of well-defined request/response sequences). It should be possible to define contracts as an additional layer on top of the existing abstract syntax, but I don't see how to enforce them statically. Nevertheless, they'd be useful even if they remained at the "formal specification" level.