Binary Object REst Distributed (BORED) system - Part 4 - Constraints & Assumptions

At this point I've introduced the BORED idea, the blueprint and provided a rough 0.1 version of the protocol. The next step is to test the message structure against various constraints & assumptions of REST.

The first constraints and assumptions to be tested are based on the constraints defined by REST. They set the ground work for the protocol and provide the constraints required to define the request/response headers.

Lossless Communication Stream
The very first assumption is that the solution will operate on a lossless bi-directional communication channel that supports streams (i.e. TCP). This assumes the transport will take care of the connection set-up and tear down. The transport will ensure that the data is received in order and provides a byte stream interface. This is a rather obvious assumption to make, however, it is important to get the basics right.

For embedded devices we will assume that if it doesn't support TCP, then another transport protocol will be provided. If the messages are small enough the protocol should also operate on UDP style network protocol. The protocol may also operate on an asynchronous transport such as message queuing and email systems.

Client-Server
The second part of the requirements is that of client-server. This is REST's first requirement. Fielding describes client-server as:

"The client-server style is the most frequently encountered of the architectural styles for network-based applications. A server component, offering a set of services, listens for requests upon those services. A client component, desiring that a service be performed, sends a request to the server via a connector. The server either rejects or performs the request and sends a response back to the client."

The client-server style requires that request data is sent to the server and it responds with response data. The initial definition of the protocol's request and response data is the following. request:

preamble - BORED
version
...
;

The response structure is the same:

prefix - BORED
version
...
;

The request and response headers look the same. It contains a preamble that notifies the receiver that the message is using the BORED protocol. The preamble also provides a point where if the receiver is out of sync with the send, it provides a point where the start of the next message can be found. The client sets the version of the protocol. The server sets the version to the version it is currently using. The server must not respond with a version that is greater than the client.

Asynchronous Client-Server
One of the interesting parts of Fielding's dissertation is the REST mismatch with HTTP. Fielding states:

"HTTP/1.1, though defined to be independent of the transport protocol, still assumes that communication takes place on a synchronous transport. It could easily be extended to work on an asynchronous transport, such as e-mail, through the addition of a request identifier. Such an extension would be useful for agents in a broadcast or multicast situation, where responses might be received on a channel different from that of the request. Also, in a situation where many requests are pending, it would allow the server to choose the order in which responses are transferred, such that smaller or more significant responses are sent first."

To support asynchronous requests, a request identifier needs to be added to the request and response data structures. i.e. The request:

prefix - BORED
version
request identifier
...
;

and response:

prefix - BORED
version
request identifier
...
;

The request identifier is set by the client. The server must respond with the same request identifier in the response. This allows a client and server to use a single channel and interleave requests and responses. This improves the channel usage and reduces latency which leads to a better user experience. Using a single channel for multiple requests also aligns well with the direction of CPUs containing many cores. Many threads can be assigned to a single channel.

The response can come from either a cache, server proxy, or server containing the object. The important thing is that by introducing a request identifier the protocol no longer needs to conform strictly to synchronous request/response semantics.

Specifying a "request identifier" is a rather simplistic approach to allowing asynchronous request/response message processing. One problem with this approach is that the server has no way of letting the client know how many messages it is able to process at one time. A possible solution to this would be for the server to response with how many message slots it has available. ie response:

prefix - BORED
version
available request slots
request identifier

For a server with constrained resources the request slots value may always be 1. Using the response message to provide the number of request slots requires that the client receive at least one response before it can know how many requests it can send. A simple solution to this would be that the server notifies the client upon initial request. This will need to be explored further in the future.

The other feature suggested by Fielding is that an asynchronous request could use different channels for receipt of the request. To allow this, additional optional headers could be provided to specify a "return address" and "time to live". The "time to live" allows the client to specify how long it is willing to wait for a response. If the server is unable to provide a response before the given time it should drop the request and not deliver the response. This type of feature is added to the protocol via the optional headers because it likely to be used rarely.

Introducing the concept of asynchronous requests and responses introduces a number of new challenges that must be explored. The proof of how well each of these ideas will work in BORED will be explored when implementing the protocol.

Binary Object REst Distributed (BORED) system - Part 3 - Structure

In this post I present version 0.1 of the BORED request and response structures. This will be refined in future posts as trade-offs are made and the protocol matures. I won't go into much detail here as future posts will provide a lot more detailed analysis.

There are only two message types in the BORED protocol; the request type and response type. Operations such as GET or POST found in HTTP are encapsulated in the message data and do not form the surrounding message. The request message consists of:

request:

preamble - BORED
version

location - URI location or other location type.

optional headers
- headers meta data
- headers data

message
- message meta data.
- message - request data.
- - operation - GET,META,POST,METHOD,etc
- - message data

optional security
- identity/signature meta data
- - optional identity
- - optional signature

The request data elements are:

preamble - "BORED" The six ASCII characters define the headers of the BORED protocol. This signifies the start of the message.
version - This will consist of a major and minor version as two unsigned 8-bit characters.
location - This is the location where the message should be delivered.
optional headers - This provides an area for additional information to be added. It is analogous to HTTP headers.
message - The message to be delivered to the specified location. This should include any POST data or URI request parameters found in HTTP.
optional security - This provides the option to provide identify of the client and sign requests.

A simple request message might look logically like:

BORED 0.1 - BORED://www.livemedia.com.au/document.pdf (GET) - ;

Note: For now these requests are demonstrated as text for human readability. As the elements of the protocol are refined binary examples will be provided.

In the example above the following elements are present:

preamble - BORED
version - 0.1
location - BORED://www.livemedia.com.au/document.pdf
optional headers - not included
message - (GET)
optional security - not included

The response has much of the same information as the request data. The response includes a response code and caching information.

response:

preamble - BORED
version

response code
cache information

optional headers
- headers meta data
- headers data

message
- message meta data.
- message - response data.
- - message data

optional security
- optional identity/signature meta data
- optional identity
- optional signature (from response code)

The response fields include many of the same data as in the request.

preamble - "BORED" The six ASCII characters define the headers of the BORED protocol. This signifies the start of the message.
version - This will consist of a major and minor version as two unsigned 8-bit characters.
response code - The response code for the data.
cache information - Information on if the response should be cached and for how long.
optional headers - This provides an area for additional information to be added. It is analogous to HTTP headers.
message - The message to be returned to the client.
optional security - This provides the option to provide identify of the server and sign responses.

A corresponding response might logically be:

BORED 0.1 200(OK) "No Cache" - (mime document/pdf .....data....) - ;

In this case the elements are:

preamble - BORED
version - 0.1
response code - 200(OK)
cache information - "No Cache"
optional headers - not included
message - (mime document/pdf .....data....)
optional security - not included

Tim Bray mentioned in this blog that it would be likely that any development of a protocol will probably end up looking a lot like HTTP. I think his spot on! You will find many of the same elements in different protocols. However, some of the nuances between each protocol can have a big effect on a protocols design and flexibility. For example, by moving the GET verb from the request header and into the body, we've completely changed the character of the protocol. HTTP is purposely constrained to a reduced set of verbs such as GET, PUT and POST. However, BORED places the verb into the body of the message which allows any number of verbs to be implemented without disturbing the transfer portion of the protocol.

Refering back to the layers of the protocol, we can see that most of the protocol is concerned with the transfer layer. The message/presentation layer is the message structure and its structure can be defined without concern for the transfer layer. The object receiver is concerned with how to process the message content and is outside the scope of the actual protocol. It is only important that any type of data can be transferred to the Object Receiver in the message body.

The layered design should allow the message data to arrive at the Object Receiver using different methods (protocols or in other data structures). This becomes important when providing a layered system. A front-end server (e.g. apache) may receive the message and then use a different transfer protocol to pass the message to an internal system. Using this method, the Object Receiver may receive additional information regarding the request; this would be dependent on the features of the internal system. This design ensures that the message can be separated from the transfer protocol in a simple way without requiring processing the data contained inside the message.

The import elements in the request which are required for the transfer layer include:

Preamble and Version – This simply sets the receiver of the message to understand and sync with the right version of the protocol.
Location – The location provides the target for the message.
Optional Headers – This can include information for Proxy servers, or request that the request is not responded to by caches.
Optional Security – This can be used for signing the message request data.

The message structure is the payload of the transfer protocol. The message layer requires a separate investigation and will be developed further later in this series of posts.

This post provides the rough outline of the data to be included in requests. The message structure and meta data associated with request and response will be developed in future posts. The next steps will be to test the protocol design against REST constraints and see what other features may be useful.

Binary Object REst Distributed (BORED) system - Part 2 - Blueprint

The discussions on Steve vinoski's blog regarding REST, RPC, ORBs, etc highlighted that there's usually a very high level model that a distributed system is built upon. In the case of RPC it is the notion that a procedure call can be made to look local. In REST/Hypermedia it is a distributed document model with loose coupling through hyperlinks. Finally, in the case of ORBs it is an Object Request Broker; an object based remote procedure call. In all these cases the model helps define many of the constraints of the system. These restrains often permeate into every aspect of the system.

The BORED system has the rather interesting task of trying to combine the REST/Hypermedia constraints with that of an object orientated system. To do this, a high level model needs to be defined to use as the blueprint.

The BORED blueprint in this case is quite simple:

client --[request]--> Server --> Container --> Object Receiver | Object

client <--[response] -- Server <-- Container <-- Object Receiver | Object

The idea behind BORED is that a message is being delivered directly to an Object Receiver via a server and container. The message can be any data. It is up to the Object Receiver to decide how to process the message received. The Container and Server are there as conduits for the message to be delivered, however, they do not directly respond to the message. The conduits can add security constraints on who can interact with the target object and manage the life cycle of creating and destroying the target object. The container itself could also be the Object Receiver, however, to keep the model simple these types of adaptations won't be discussed.

The Object Receiver is able to respond directly to the message by returning the object data (as in a document or image). This should allow a hypermedia solution to be developed that has simple file based Object Receiver. Alternatively, the Object Receiver may process the message and call a method as is done in a traditional RPC or ORB. 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...

An important note here regarding RPC and BORED. BORED is designed to support a RPC mechanism, however, it is not locked into a single mechanism. Different types of skeletons could be built into the Object Receiver. The initial mechanism will likely use a Remote Message Call mechanism, however, it is up to the Object Receiver to define the meta data and interfaces associated with it.

I have used the name “Remote Message Call” to describe the BORED call method; this is to separate it from the traditional Remote Procedure Call (RPC). A Remote Procedure Call is the language centric view that maps a set of parameters of a method on a server to an equivalent local call on a client. This is a simplistic view of RPC. In BORED there is a message centric view of RPC. That is, the remote call is defined by the data contained in the request object and the data returned in the response. The message data in the request and response forms the contract between client and server. This message data in the request or response can be bound to a language based method call on the client and server, however, it is not a requirement. As BORED is based on describing the request/response data, not the remote method call this is not a traditional RPC mechanism. The distinction is important and ensures that some of the issues of RPC do not get embedded into BORED.

Interestingly, the BORED/RMC model reflects message queuing semantics more than it does RPC, REST or ORB semantics. The fundamental idea is that the data is contained in an envelope and delivered directly to an end point. The difference is that the BORED model is designed for synchronous request/reply semantics, where as message queuing is uni-directional.

As an example of how BORED semantics differ from HTTP, we can look at a HTTP GET request. The HTTP protocol uses the verb GET before specifying the location of the document to be retrieved. This creates a model where the server is performing the GET operation on the document requested. The BORED system will include a GET verb inside the message and deliver it to the Object Receiver. By moving the GET verb into the message it is the “Object Receiver” processing the verb instead of the server. The intention of this is to localise the requested data to the object to which it is being delivered.

One thing I should point out at this point; the model is already making trade-offs. The most obvious to the REST aware folk will be that by encapsulating the message in an envelope and by allowing language orientated mechanisms in the object receiver, BORED removes the Uniform Interface constraint of REST at the protocol level. The Uniform Interface constraint can be catered for, however, in BORED it is not a constraint of the protocol and must be defined in the message data structure. This is an area that still needs to be explored to work out how to combine the two seemingly opposed constraints. This will be expanded further in future posts when the message data structure is explored.

In the on-going REST debate, Tim Bray provided a good description of the trade-offs found in REST versus other systems. These are good things to keep in mind while designing BORED. It reminded me that I had'nt described the layered approach used in BORED.

In the BORED model there's at least three different layers. Defining layers in a protocol ensures that concepts of each layer does not infect other layers. The following compares the traditional OSI 7-layer model with HTTP and BORED.

OSI	HTTP	BORED
application	application (browser/client)	object receiver(client)
presentation	mime (presentation)	message (DATA)
session	transfer (HTTP)	transfer (BORED)
transport	transport (TCP/IP)	transport (TCP/IP)

I've had a few conversations where people viewed the OSI 7-layer model is seen as out dated and not very useful in today’s protocol developments. This may be true, however I still find it useful as a backdrop to understanding the layers of different protocols. By modelling a protocol stack using this type of layering provides another view of the protocol.

In the HTTP model the HTTP transfer protocol is easily recognisable as fitting the OSI session layer. It sets up the structure of the conversation between client and server. The data returned by a GET request specifies the mime-type which sets the presentation format for the response. The uniform interface specified by HTTP spreads across both the session and application layers. This unclear distinction of which layer the GET belongs is one example of how having a layered stack model can ensure each layers purpose is well understood.

In the BORED model, the transfer part of the protocol will define the request/response semantics and setup the basis for communications. The transfer layer will also provide the security and location of where the message will be delivered. The message data layer defines the presentation layer of the model. The message data should provide all the data required by the Object Receiver to perform its request.

A good analogy is a physical envelope. The transfer layer is the envelope which has the address, any routing information, the sender and any security information. The message layer is the paper that is put into envelope. The paper can contain any sort of information that the recipient can process. The Object Receiver layer is the actual data contained on the paper and directs the Object Receiver to perform an action. By ensuring the each layer is self contained, the whole system will be more flexible and easier to work with.

This post outlines the model for the BORED system. It has constrained BORED to request/response semantics directed to an Object Receiver. It has outlined the Remote Message Call (RMC) semantics used to create a solid distinction between it and Remote Procedure Calls (RPC). Finally, it outlined the layers in the protocol stack so that each layer can be analysed and its purpose described independently. In the next post I'll do a first cut of the logical elements of the protocol.

Binary Object REst Distributed (BORED) system - Part 1

I was recently involved in a long discussion over at Steve Vinoski's blog regarding RPC and REST. The discussion was been long and multi-faceted covering definitions of RPC, REST and various other aspects of distributed computing. Steve has recently closed the loop on the discussions referencing some comments from Stu Charlton which offer a higher level perspective. The whole thing is a good read if you're into learning about the innards of the web and views on distributed systems.

One of the benefits of having these types of discussions is learning new perspectives and technology. There's nothing like getting into the nitty gritty and working out where opinions and ideas intersect. One of the things I learnt along the way is that I had misunderstood the meaning of REST. I was told to go and read Roy Fielding's (the person who coined REST) PHD dissertation. Unless you've read Fielding's dissertation it's most likely that you don't actually know the true meaning of REST. To quote myself in Steve's blog after I had read Fielding's dissertation:

"REST is fundamentally not RPC. REST is an 'architectural style' that is designed to ensure that the web's hypermedia solution to distributed computing will not be ruined by future changes. REST is not a design pattern or an implementation. You could look at the actions of REST and loosely suggest as I've done in the past, and Michi has, that they have some similarities to RPC. I don't think it is an argument worth pursuing. This does not mean that the REST architecture doesn't look like RPC on the client, but I'll get to that later. REST is as different from RPC as it is from Message Queueing or Publish Subscribe systems."

Of course Wikipedia has a better description of the situation:

“REST strictly refers to a collection of network architecture principles which outline how resources are defined and addressed. The term is often used in a looser sense to describe any simple interface which transmits domain-specific data over HTTP without an additional messaging layer such as SOAP or session tracking via HTTP cookies. These two meanings can conflict as well as overlap”

I've been asking myself, how can I apply REST constraints to a binary protocol? I've spent the last week or two developing a thought experiment for a protocol design for a Binary Object REst Distributed (BORED) system. This may not go any further than a thought experiment, however, it should highlight some of the trade-offs you make when developing a protocol. With some luck I'll attract some other smart people to throw in their thoughts and may end up with something useful; or at least some useful material for future work.

Future posts will go into the detail of the BORED protocol; however, for now I'll highlight the guiding principles:

• REST - REST has a strong architectural style that has many benefits for internet scale distributed systems. This has obviously been proven by the World Wide Web. The BORED protocol must live up to the architectural requirements specified by REST.
  
• Binary - The data encoding will be binary. I have a long history with binary encoding with Argot. The protocol will leverage the learning and methods used in Argot. The protocol may still be applicable to other binary encodings.
  
• Object - Integrating the REST model with an Object model is to a certain extent a direct contradiction. However, there's a huge disconnect currently between REST and programming languages; I'll see if I can find a way to align the two.
  
• Scalable - The solution must be able to scale from tiny embedded devices to enterprise systems. Embedded devices require a protocol that can be scaled to respond to requests in only a few KB of code.
  

The above should provide the flavour of the protocol to be designed. Obviously, there will be trade-offs.

Also, I should mention, the name BORED was probably not the best acronym I could come up with. I think it's somewhat fitting though, as I'm bored with all the arguments about which distributed system is better. I'd rather work on how to combine great technology to make even better systems.