Argot, Colony and stuff about internet protocol stacks.

Tuesday, September 23, 2008

Part 7 - Uniform Interface Constraint

Its been a couple of weeks since the last BORED post. Something has gone wrong with my very old Thinkpad. It now only boots in safemode with 640x480 resolution; not the nicest environment to work. I'm holding out for another few weeks before hopefully getting hold of a new Mac. I'm still not sure if it will be an air, book, pro. The posts here will probably slow down until they're out.

For now, back to BORED. Today's post is probably the most interesting of the posts and highlights the real issue that BORED, Argot and every other protocol is really trying to solve. That is the movement of information and knowledge between client and server. This is very different to the simple task of moving data (ie bits and bytes). The problem of moving knowledge between applications is the central aspects of what draws me to this otherwise dull area of computer science.

I look at the current browsers, programming languages and enterprise systems and see a single underlying problem; we have very little understanding of how to move knowledge between systems. Solving this problem can lead to more fluidity of data with less work by programmers. This should also lead to better useability for the applications we build. There's a lot of work to do and probably a few books to be written in this area before it will be solved. BORED is an excersize in breaking out of the mold and seeing if a better approach can be found. Without further ado, lets get back to BORED!

The BORED protocol has now been tested against some of the challenging REST constraints. The next and probably the most difficult constraint to be tested is the Uniform Interface Constraint. This is the point where the request message data structures hit the target object and the mismatch between a hypermedia system and other types of interactions with servers is most obvious. As the aim of the BORED protocol is to bring find some alignment between REST and Object orientated systems, this is where things should get interesting.

Uniform Interface

The Uniform Interface constraint is one of the more interesting constraints of REST. It reduces all operations to a small set of file like operations, e.g. GET, POST, PUT, DELETE, HEAD, etc. In the case of BORED, however, I'm trying to bring together the concept of an Object Orientated system with that of a Hypermedia system in a sensible way. At this point it is a good time to review the BORED architectural model:

client --[request]-->Server-->Container-->Object ReceiverObject

client<--[response]--Server<--Container<--Object ReceiverObject

The BORED Remote Message Call(RMC) model encompasses all interface request data into the message data portion of the request. This is delivered to the Object Receiver, which uses this information to interact with the target Object. These interactions could involve any one of the following:

Object Receiver -------> Document/File
Object Receiver -------> Object Instance with public methods
Object Receiver -------> Data Collection
Object Receiver -------> Proxy Interface
Object Receiver -------> Etc...

It is also worth reviewing what Fielding has to say about the Uniform Interface Constraint:

"The central feature that distinguishes the REST architectural style from other network based styles is its emphasis on a uniform interface between components (Figure 5-6). By applying the software engineering principle of generality to the component interface, the overall system architecture is simplified and the visibility of interactions is improved. Implementations are decoupled from the services they provide, which encourages independent evolvability. The trade-off, though, is that a uniform interface degrades efficiency, since information is transferred in a standardized form rather than one which is specific to an application’s needs. The REST interface is designed to be efficient for large grain hypermedia data transfer, optimizing for the common case of the Web, but resulting in an interface that is not optimal for other forms of architectural interaction."


As stated, it is the Uniform Interface constraint that really sets the REST approach apart from many other systems. It is the simplicity of the uniform interface that makes the interactions between browser and web server so powerful.

Fielding continues with:

"In order to obtain a uniform interface, multiple architectural constraints are needed to guide the behaviour of components. REST is defined by four interface constraints: identification of resources; manipulation of resources through representations; self descriptive messages; and, hypermedia as the engine of application state. These constraints will be discussed in Section 5.2."


The Uniform Interface constraint therefore has multiple sub-constraints. Any diversion from these constraints will cause BORED to diverge from the REST approach. However, Fielding also states that the Uniform Interface constraint is a trade-off between degrading efficiency and providing an:

"efficient interface for large grain hypermedia data transfer, optimizing for the common case of the Web, but resulting in an interface that is not optimal for other forms of architectural interaction."


This trade-off is clearly shown in AJAX based applications. Application designers are forced to use the REST approach for all aspects of the client-server interactions. An AJAX based application downloads Javascript which often makes remote calls back to the web server. These AJAX calls are better suited to a solution which allows a program centric interaction with the server (note I'm being careful not to use the term RPC). The client may be attempting to return document fragments or even simple single string responses. In these situations the uniform interface constraint creates additional work for the developer and designer. These AJAX/Web 2.0 interactions would benefit from a stronger binding between client and server.

The AJAX/Web 2.0 example shows the trade-off that Fielding discusses in regards to REST. However, the trade-off has obviously served the Web Hypermedia system well to this point. Take for example the simplicity of:

http://www.livemedia.com.au/my_image.jpg

By entering a URL into a browser we imply the GET request, and the image is retrieved. The web's power is driven through this simplicity.

At this point it is worth doing a small detour into the realm of data contracts. Understanding the different types of data contracts that client/server systems use will provide a better set of tests to base the BORED protocol.

Data Contracts

The topic of data contracts is probably the most interesting aspect of distributed computing. This is where there is some agreement between client and server that after sending a specific set of data to a location will result in an agreed set of other data being returned. The contract can range from being implied, to being rigidly defined using procedure call semantics (as is the case in CORBA IDL). This philosophy around the area of data contracts changes with each new technology and fad.

The reason for this constant flux is that what is required changes for different purposes. If a user is involved then human cognition is the most important part of the contract. If the communication is purely between code on both client and server then as long as the client matches the server the contract can be implied. If the clients are many and varied and are using a 3rd party service then consistancy and an Interface Definition Language is desierable. If the client wishes to discover new interfaces then discoverability and associated IDL is a requirement. Finally, in some cases an IDL does not go far enough and a full and independent textual specification (eg RFC) is required.

Each of the methods of creating data contracts implies different requirements for the BORED protocol. The following is a simple breakdown of different contracts and some implications for the BORED protocol. There has probably been better and more thorough analysis of data contracts been done before; if you're aware of any, please let me know via comments.

Human Cognition Data Contract

The URL is probably the best example of providing human cognition to a data contract. By reading a URL a user is able to have a fairly good idea of what information will be returned. There is obviously skill in defining a good URL structure for any web site. However, the current URL also include request parameters which can modify the result of a particular page.

Take for example the following hyperthetical request:

http://www.livemedia.com.au/store_search.x?s=books&author=ryan&page=2

To an experienced web user the parameters of this request are obvious:

s=books (search the term “books”)
author=ryan (find books by the
author “ryan”)
page=2 (return the second page of results)

The contract between client and server regarding these parameters are loose and do not provide a formal contract between client and server. However, the need for this contract is reduced for most web pages as Javascript is usually used to construct the required URL. This reduces the usability of the server application for purposes outside the scope of the web page that uses it. To fix this issue many web sites that wish to offer services to external sites use additional web services based around SOAP technologies.

As part of the BORED protocol we've already stated a location requirement. At the sametime this ability for a user to modify a request URL parameters provides flexibility and gives the user a greater control over the information requested. To solve this in BORED a mechanism for the data contract for a URL to be made available to the browser. The user can then be presented with an interface to allow them to modify request parameters in a formal way.

Hypermedia Data Contract

The hypermedia data contract is associated with the REST design philosophy. The idea that each object in a system is identified using a simple URL. Links and references between objects are provided through hyperlinks. For instance instead of saying that a customer order contains product id A1234, a hyperlink is provided which gives a direct link to the component.

The final solution in a hypermedia system consists of many URLs with the interaction of each object in the system reduced to the REST uniform interface constraints. The client may request to be provided with different formats in responses depending on its requirements. Examples include HTML for user interaction, XML for programming language interaction and PDF for printing purposes. The REST approach requires that a client can specify the type of data it wishes to receive through its request parameters.

The actual data contract is deferred to the data representation returned by the specific request. In the case of XML, the contract can be specified using XML Schema or DTD. In a way, REST splits the data contract into two halves; The data representation using mime and the location of information through the publishing of URLs. REST does not currently have a method of bringing this information together in a way to make the data discoverable.

This type of solution puts minimal requirements on the BORED protocol. Infact, the hypermedia/REST method does its best to avoid the data contract issue by reducing all calls to a uniform interface and mime-types. The BORED protocol must allow the client to request the type of data it wishes to have returned in the GET verb. The response must support the ability to provide at least a mime type associated with the data returned.

Implied Data Contract

This form of contract is when a client is built specifically for a server. This is the case with most Web 2.0/AJAX based applications today. The data contract is not specified in any formal way and the specific data sent and received is at the full discretion of the developer. The developer must be aware of any changes with the data sent or received between client and server and ensure each section of the software is updated.

A large Web 2.0/AJAX based application is likely to have associated documentation that is put together by the team developing the product. This documentation is unlikely to provide a formal description of the data. Any changes to the product would require a separate task to update the associated documentation.

An important aspect of this type of communication is that the data format sent to/from the server is at the total discretion of the developer. A developer may return a simple string, some preformated HTML, some JSON data, or a new script.

This type of communication puts a requirement that the protocol should be open to any data type the developer wishes to sent between the client and server. To support this, the message data should allow at the very least a mime-type to be specified with the data. It may also be beneficial that additional meta data be provided separate to the data being supplied.

Strongly Typed Data Contract

This form of contract is defined using an Interface Definition Language(IDL) or Web Services Definition Language(WSDL). This is the most formal method of defining a contract between client and server. Associated with this type of formal contract is a complete communications stack (I.e. stubs and skeletons) which provides the middleware for the formal agreement.

In examples such as CORBA and Web Services there is a complete framework which surrounds strongly typed data contracts. As has already been shown numerous times over, a single framework is unlikely to provide all the facilities required by developers. Multiple Data Contract Languages (DCL's) may be required with more specific purposes to meet a developers requirements.

To support strongly typed data contracts the BORED protocol should support allow an interface to be associated with a specific location. In these cases the default GET uniform interface may provide an objects current state, however more specific interfaces can also be provided. The Data Contract Language associated with the object can be made available via a META call to the location.

Uniform Interface Constraint Reviewed

After reviewing the various types of contracts it is clear that the Uniform Interface constraint is just one of the many ways of building a data contract between client and server. However, the Uniform Interface constraint is an important element of the REST design; this is because as already suggested, its power is in its simplicity. eg

http://whereis.com

This URL links to a Web 2.0 application that uses heavy JavaScript and has many dynamic elements. In these cases the Uniform Interface constraint is defining a common naming mechanism that defines a link to a web application. The URL in effect is a bootstrap for the application.

The calls to the server after the application is loaded are hidden away from the user. If the user went hunting through the code for these AJAX calls they would be of little use alone. They are likely to require very specific parameters and return information that only the client application can interpret.

This concept of identifying the URL as a bootstrap has helped frame a few conclusions about the Uniform Interface constraint. In particular the requirement for the uniform interface constraint is only important for those locations that require direct user interaction or return a simple data representation. However, any data that needs to be transferred between the client application and server can use any other means that is suitable to the application. A developer may choose a mixture of implied and strongly typed interface contracts. It depends on the needs of the interactions that will occur between client and server.

Uniform Meta Interface

The discussion above points to the need for a uniform meta interface layer to be created. The purpose of this layer is to provide a mechanism to discover the meta data associated with the object being interacted. This meta data can describe the type of interactions that the object receiver will resposne. This layer should be flexible enough to cater for any type of data be sent and received. It should allow the interactions with the object to be described using meta data that is most appropriate for the service being delivered.

The danger of providing a single meta interface layer which could describe any number of interfaces and protocols is that the REST uniform interface is lost. I've already stated numerous times that the power of the REST architectural style is in the uniform interface. For this reason, a reduced number of verbs needs to be defined which allow the object to publish a basic set of known operations. This supports the main aim of the REST architectural style, but still allows flexibility in catering for other application protocols.

To support this concept of a uniform meta presentation layer, the object receiver must at a minimum respond to a request with a META verb. The response to this verb must be a description of the interfaces supported by the object. The meta data returned may include a set of REST style verbs such as GET, HEAD and DELETE.

This implies that for many interactions the client must make a call to the server to retrieve the meta data and then a second call to perform an operation. Additional calls may also be required to retrieve and bind interfaces depending on the method described in the meta data. However, it will be assumed that most locations will support atleast the GET verb with no parameters. This support will allow published URLs to be accessed without making multiple calls to the service.

Sunday, September 07, 2008

Part 6 - Cache Constraint

The BORED protocol already meets the first two constraints of REST; client-server and stateless. We've also extended the client-server constraint to allow asynchronous client-server. The next REST constraint to meet is the Cache constraint.

Cache
Returning to Fielding's REST dissertation, we find:
"Cache constraints require that the data within a response to a request be implicitly or explicitly labelled as cacheable or non-cacheable. If a response is cacheable, then a client cache is given the right to reuse that response data for later, equivalent requests."
In the BORED protocol there's an additional requirement to this, which relates to the stateless requirement. To label a response as cacheable or non-cacheable requires that the request is uniquely identifiable. In BORED, the stateless request data is broken into two parts; the location and the message data. To satisfy this constraint a proxy server or client must identify the location and the request data as a single object and match this against the response data. As the request message data is binary the simplest solution is for a client or proxy server to keep a hash on the message data and location. To improve performance this hash value could be added to the request data to provide a key to a cache that will lower its overhead to calculate the key. It's important to add that the hash should only be based on the message data. This allows proxies to perform operations such as rerouteing of messages to new locations without needing to update the hash value.

To support the response aspect of the cache requirement, BORED includes cache information in the response header:


preamble - BORED
version
dictionary parts
available request slots
request identifier

response code
cache information


In the REST mismatches with HTTP Fielding writes:

"Differentiating Non-authoritative Responses
One weakness that still exists in HTTP is that there is no consistent mechanism for differentiating between authoritative responses, which are generated by the origin server in response to the current request, and non-authoritative responses that are obtained from an intermediary or cache without accessing the origin server. The distinction can be important for applications that require authoritative responses, such as the safety-critical information appliances used within the health industry, and for those times when an error response is returned and the client is left wondering whether the error was due to the origin or to some intermediary. Attempts to solve this using additional status codes did not succeed, since the authoritative nature is usually orthogonal to the response status.

HTTP/1.1 did add a mechanism to control cache behaviour such that the desire for an authoritative response can be indicated. The ’no-cache’ directive on a request message requires any cache to forward the request toward the origin server even if it has a cached copy of what is being requested. This allows a client to refresh a cached copy, which is known to be corrupted or stale. However, using this field on a regular basis interferes with the performance benefits of caching. A more general solution would be to require that responses be marked as non-authoritative whenever an action does not result in contacting the origin server. A Warning response header field was defined in HTTP/1.1 for this purpose (and others), but it has not been widely implemented in practice."
When the request message headers are developed in detail it will be important to include the ability to define a 'no-cache' directive. The cache information returned in the response should also indicate if the response is non-authoritative.

Location only constraint
At this point we add another new constraint to the system; the location only constraint. The location in each request should only include the location specific information. Request parameters must only be supplied in the message data. This constraint is designed to ensure the separation of the message data from the location data. This allows fast and easier routing of message data.

This constraint is a direct opposite of a common practise of encoding request parameters on to URI's in HTTP. For example:
http://www.livemedia.com.au/bookstore?author=ryan&page=1&list=10

In the BORED protocol the location must be separate from the message data.

(location bored://www.livemedia.com.au/bookstore)
(message author=ryan@page=1&list=10)

This constraint is designed to combine with the cache constraint to ensure message parameters are not confused with location data in cache systems. It also ensures that the required meta data to decode the message is included in the message meta data.

It is interesting to note that the cache constraint requires the stateless constraint to function. A cache must be able to deal with a whole message uniquely to operate correctly.

Tuesday, September 02, 2008

Part 5 - Stateless constraint

The initial constraints of REST were easy to provide a solution in BORED. In this post we tackle the stateless constraint. As BORED uses binary message data this constraint creates some unique challenges.

Stateless

The Stateless requirement is REST's second constraint. Fielding writes:

"We next add a constraint to the client-server interaction: communication must be stateless in nature, as in the client-stateless-server (CSS) style of Section 3.4.3 (Figure 5-3), such that each request from client to server must contain all of the information necessary to understand the request, and cannot take advantage of any stored context on the server. Session state is therefore kept entirely on the client."


To see the stateless requirement more clearly I'll review HTTP. Here's an example of a HTTP 1.1 request and response.

GET http://www.eienet.com.au/ HTTP 1.1
...

200 OK
...


The request encodes the full description of what the client is requesting in the URI and HTTP GET verb. To align with REST, BORED requires a similar location specifier. Let's assume a URI for now, however, to support embedded devices this will need to be more flexible.

To satisfy the stateless constraint, the following parts of BORED are required in the request:

prefix - BORED
version
request identifier
location - URI location or
other location type.
....
message
-- message meta data.
-- message - request data.
---- operation - GET,META,POST,METHOD,etc
---- message data



To meet the stateless requirement the BORED protocol includes the location and full request data.

In the case of a binary protocol an interesting addition is the inclusion of "message meta data". This is Argot specific however can be extended to any binary system that has a meta data definition. In the Argot case the meta data specifies the data structures of the data in the message.

The “message meta data” describes the message data, however, at this point there's no meta data to describe the actual request structure. To understand how BORED will solve this it is worth introducing the concept of an Argot Message Format. The Argot Message Format is designed to be completely self defining. Here's a short description from the Argot Programmer's guide.



Argot Message Files & Dictionaries

Argot message files are binary encoded files that provide the specification of their data with the data. An Argot file contains three parts; a meta dictionary, a data dictionary and the data.

The Argot Message Format allows the full specification of the data to be transferred with the data. This requires no external definition of the data. For an application to be able to read the file its type library must contain all the data types used in the file. A Type Map is generated from the data dictionary portion of the file to read the data. The general format of the file is:



The receiver of an Argot enabled file is able to read the dictionary and compare the data types of its own dictionary with that of the files. Once the types of the file dictionary have been matched with that of the application reading the file, the data can be read. This completely removes the need for a static common domain schema. Each application and file in effect contains its own schema.



This can be re-illustrated using the following venn diagram:



The process of reading a file involves:

  1. Binary compare of meta dictionary map. The very first dictionary map of the meta dictionary is the core met dictionary. The only way to read this entry is by performing a binary compare. These are the base dictionary items used to describe new items. Please refer to the meta dictionary reference section for details of the core meta dictionary.
  2. Build and read Meta dictionary. The rest of the meta dictionary is read and mapped between the application and file.
  3. Read the Data dictionary. Using the Type Map produced from entries in the Meta Dictionary the Data dictionary is read. A Data dictionary type map is created based on the types identified.
  4. Read the Data. Using the Data dictionary type map the actual data of the file is read.


The argot message format can be used anywhere that a data buffer can be transferred. In files, message oriented middleware, email, etc.



It would be easy to simply use the Argot Message Format as the full request structure to be delivered to the server. However, carrying the 'meta dictionary' with each and every request adds a lot of overhead. This would also hide the contents of the request data requiring a cache/proxy to read the meta dictionary, data dictionary and data before it can understand the request.

The solution used in BORED is to use the version information of the protocol as a monica for a data dictionary. When a server receives a request it uses the BORED protocol version to choose the corresponding data dictionary. This is like having the meta dictionary and data dictionary of the request at the start of every request. The request and response BORED message are themselves specified in this data dictionary.

The BORED request message however also requires a meta data section for times when the meta data for the request does not include data required by the object receiver. The message data dictionary expands on the request data dictionary to include elements required by the message.

Logically this looks as follows:

[ meta dictionary ] [ request data dictionary ]
---- [ request ... [ message [ message data dictionary] [data ]] ... ]


This allows the Request to logically contain the full meta dictionary, data dictionary, and data for the full BORED request in every message without the overhead of the full meta dictionary and data dictionary.

Using the above method has a drawback that the "request data dictionary" must define every aspect of the request message structure. This includes, security, cache information formats, header formats, and others. This creates an issue for very small devices that only support a subset of the request headers. A solution to this is to break the "request data dictionary" into parts. The client and server can then identify in their request and response the parts of the request data dictionary it supports. For simplicity the parts supported can be indicated via a bit-flag in the version part of the header. For instance, the version header could use three 8-bit flags. The first two would be the major and minor version with the third being the bit-flag for the parts of the request data dictionary supported.

Building on the last post, the request structure header now looks like for the request:

prefix – BORED
version
dictionary parts
request identifier
...

and response:

prefix - BORED
version
dictionary parts
available request slots
request identifier
...



Delivering the stateless constraint using a binary protocol has required developing a few tricks. In particular using the request version number as a key to meta dictionary and request data dictionary has allowed the solution to deliver a technically correct construct and still delivered the ability to reduce the amount of network traffic for each request/response. Using the bit-flag for specifying the parts request data dictionary supported has also allows the solution to scale from small devices to large full features systems.