This post originated from an RSS feed registered with Ruby Buzz by Eigen Class. Original Post: Backward and forward compatible protocol evolution with extprot: the case of Grafffer Feed Title: Eigenclass Feed URL: http://feeds.feedburner.com/eigenclass Feed Description: Ruby stuff --- trying to stay away from triviality. Latest Ruby Buzz Posts Latest Ruby Buzz Posts by Eigen Class Latest Posts From Eigenclass

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:

1. bright, colorful Grafffs

2. 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:

Read more...