Live Media
Live Media is the parent company of Einet. A spin off company to commercialise Argot and Colony, which provide new methods to allow information communications to work more easily between computer systems.
You can learn more about other projects Live Media are involved, by reviewing the Projects page. You can learn more about David, by reading his Blog which is hosted on this site.
If you would like to keep up to date with changes to the site, or David's blog, you can point your favourite RSS client to the sites RSS feed.
A key concept of Argot is that it allows a client and server to perform type agreement dynamically. Introducing meta data versioning creates a number of issues when performing type agreement. The following goes into the details of Argot remote type negotiation and investigates the issues and some possible solutions.
To understand the problems of dynamic type negotiation, the fundamental concept of Argot data encoding must be understood. Argot meta data definitions are a reflection of how the data is encoded in communications. This is the opposite of Abstract Syntax Notation(ASN1) which defines the abstract meta data of a structure and then applies one of various encodings when the data is being written.
For instance, I'll use the Address data type as an example:
(library.entry
(library.definition u8ascii:"address" u8ascii:"1.0")
(sequence [
(tag u8ascii:"street" (reference #u8ascii))
(tag u8ascii:"suburb" (reference #u8ascii))
(tag u8ascii:"state" (reference #u8ascii))
]))
In the above data definition, the address structure has three fields; street, suburb and state which are all defined as ASCII strings with a maximum length of 256 characters (u8ascii). Defining an instance of this in Argot would be:
(address street:"PO Box 4591" suburb:"Melbourne" state:"Victoria")
If this instance was to be serialised for communications it would look as follows:
0x0B "PO Box 4591" 0x09 "Melbourne" 0x08 "Victoria" (note strings have not been changed to hex to ease readability)
Referring back to the address meta data you can see that this encoding shows a sequence of three strings. The u8ascii type uses a unsigned 8-bit byte to specify the length of each string before the data. Other than the length of each string before the string data there is no other meta data embedded into to encoding. This format has a number of consequences for how Argot must read data from the stream. The most important requirement is that Argot must know exactly how many fields each structure contains and what data is coming next. The advantage is that Argot is able to use a very compact data format with little to no meta data being utilised in the data stream. The disadvantage is that the exact structure of the data must be known before it can be read. This requires a client/server to both agree on the data types being used for communication.
Remote Dynamic Data Type Agreement
When communicating between client and server using Argot, information such as the Address instance above are identified using a 16bit identifier. This identifier is assigned dynamically to allow the communication channel to dynamically discover the data types it can communicate between client and server (as was discussed in the Versioning Part 1). In Argot's current form this negotiation is quite simple. It involves the following transactions.
- Meta dictionary check - There is an initial call to the server which checks if the core meta dictionary data types are the same. These data types are assigned a common set of identifiers that both client and server must adhere. This operates as a bootstrap mechanism for other types to be defined. This boot strap mechanism allows the meta data to be expanded and include new concepts for how to describe the data being transferred that were not previously developed in the core of Argot's meta data.
- Resolve Identifier - When a client needs to send a data type for the first time (that is not in the meta dictionary list of types) it sends a "resolve" message to the server. This message has the type's name and structure. The server receives the message, finds the data type and decides if the data structures match. If they match, an identifier is assigned for the channel for that type; if they don't match, an error is returned to the client. If an agreement can not be found, then the client will receive an error and the message being sent must be aborted.
- Reserve - In some circumstances a data type will have a cyclic reference to itself. Before the data type structure can be resolved using the above call the client must assign an identifier so that its data structure meta data can be written. The reserve call sends a message with a type name to the server. If the server has a data type with the same name it assigns an identifier to the client. If the server does not have the specific data type name then an error is returned to the client.
- Resolve Reverse - When a server is responding to a request it may wish to send a client a data structure that has not been resolved by the client. Argot uses asynchronous request/response semantics for all calls. This means that the server is unable to initiate a request to the client to resolve the data structure. In this situation the server assigns an identifier and sends the data to the client. When the client reads an identifier it doesn't recognise, it makes a "resolve reverse" call to the server with the identifier. The server responds with the name and the data type meta data assigned to the identifier. If the client finds it has the same data structure it is able to continue reading the data. If the client does not find a match it must abort reading the data as it does not understand the data received.
These four calls work well in Argot without versioning. The client and server are able to check for each and every type if the structure's match. This includes the data type meta data.
Adding versioning into Argot requires a location to be used instead of a name for all of the above calls. To a large extent, this is all that is required. However, there is a problem at the protocol level centred around the concept of "resolve reverse". As stated above, currently the server has one version of each data type. When responding with a previously unused data type it is able to respond with the single version of the data structure. The client either reads the data or doesn't. In a situation where the server has multiple versions of the data structure it needs to know which version to send to the client. In a protocol that uses asynchronous request/reply semantics, the server is unable to initiate request to the client to ask which version to use.
Here's some ideas that were explored to solve this issue:
- Place holder - The server could return a place holder for the data instead of the actual data. This would require that the client must find this place holder in the data stream and send a message to the server.
This is not suitable as it puts a burden on the application to keep the instance data around to be encoded as required by the client. It also makes the Argot streaming interfaces very complex.
- Second Channel - Require that the client hold open a second channel to the server. This allows the server to initiate requests such as this to the client. The client could close both channels when communications has completed.
This is not suitable as TCP sessions are a scarce resource. Keeping open a communications channel for the chance of communications is not appropriate.
- Pause Stream - Stop the current response and return a message in the stream asking the client to resolve the version required. The client would resolve the version and then return a message to the server asking it to continue with the selected version.
This is not suitable as the client may be in the middle of reading any other data type. It may not be in a position to find the message in the stream.
A few possible workable solutions are:
- Chunked Stream - Require that a response stream is broken up into chunks. The server fills up a chunk before sending the response to the client. If the server finds a data type that needs a version selected, the server can initiate a request to the client asking which version to use. As the stream is chunked the client is able to receive requests from the server interleaved with the response stream.
The interesting part of this solution is it changes the underlying request/response semantics and opens up the stream to be a bidirectional group of channels. This aligns well with the asynchronous request/reply concept already stated in BORED (Binary Object REst Distributed system). Using a chunked stream is bringing the concepts of TCP up a layer to allow multiple communications to occur on the same channel. Allowing the server to initiate requests also creates a new set of opportunities and challenges. The chunked stream also has some similarities to SCTP, the protocol used in VOIP systems.
- Pre-fetch - Require that the client know the type of data structures that will be returned by a request. The client must send a request to the server with all the data types that it could receive in the response.
Ideally the client would send a group of data types to the server for data type and version negotiation. An issue with this is that some data types may need to be resolved before the group can be sent. To resolve this, the client can use a set group of reserved identifiers for the purpose of performing type resolution.
- Negotiated Versioning - The discussion above revolves around the concept that the client and server require to negotiate the version of data they should use. This scenario would be most effective where a client and server have a communication which persists over a series of calls. This is especially true in environments that have multiple servers and clients with data that is evolving over time.
In negotiated versioning the server has a set of versions for each data type. The client is able to select which version it would like to communicate with for each type.
- Shared Versioning - Another possible scenario is that both the client and server agree to adhere to a version dictated by separate server. In this scenario the server is able to send any data to the client as long as it adheres to the shared version. This may be appropriate for organisations wishing to centralise the data dictionary for better management purposes. It is also likely that the server will contain multiple versions of data types. The client would select a version of the dictionary which would select the correct version of each data type; much like a version in traditional version control systems. This is required as clients and servers programmed for a particular version of a data type can not have the structure of that type changed unexpectedly.
This scenario requires that the client or server select the server that will be used to select the data type version.
- Server Dictated - In some cases the server may only have a single version of each data type. In this scenario there is no point attempting to negotiate the data types. The client must have the specific versions of data required by the client. This is scenario that Argot currently uses for communications. In scenarios where deploying new servers are more expensive and clients talk to many servers this is most appropriate. The client must contain all data type versions required to communicate with each server.
This case is also true for any form of message queueing or file base messages. The server will have no idea which version the client requires. If the server has multiple versions available then it will need to select the most appropriate version of each type for a given file. It is also true for embedded systems where the server will not have the resources or processing power to perform full negotiation of data types.
- Client Pre-Selected - In some cases its most appropriate for the client to pre-select the data type versions it expects to receive from the server. In this scenario the client sends a group of data types and versions that the server should use for communications. In this scenario the client is more expensive to deploy or a server needs to communicate with multiple versions of a client.
This method fits into the pre-fetch method above.
- Version Controlled - In this scenario the stream includes a version selector for a group of data types. This is more in-line with how many systems currently operate. The disadvantage of this mechanism is that every data type must be pre-selected to be part of the group of a selected version.
If you can think of other methods of performing version agreement between servers please let me know so that I can add it to the list.
Catering for the various types of version management in a single protocol is not a simple task. The protocol redesign should also align with the BORED protocol discussed in previous posts. In addition to these requirements the final requirement is to build security into the protocol. These issues will be explored in a later post.
Argot Programming Model
Another piece in the versioning puzzle is how the programmer's API has changed for the most common functions of Argot. In the current system, Argot uses the concept of a TypeMap for mapping specific data types to a stream. Currently this does not include any type of version information. Some example code looks like:
TypeMap map = new TypeMap( typeLibrary );
map.map( 1, typeLibrary.getId("uint8"));
map.map( 2, typeLibrary.getId("u8ascii"));
In this scenario, the user is mapping a local identifiers to data types in the type library. To support versioning, the developer would need to specify which version of u8 and u8ascii they wanted from the TypeLibrary.
TypeMap map = new TypeMap( typeLibrary );
map.map( 1, typeLibrary.getId("u8", "1.0.0"));
map.map( 2, typeLibrary.getId("u8ascii", "1.0.0"));
The problem with this is it re-introduces a specific version too early in the communications. The solution is the introduction of a TypeMapper interface which is passed into the TypeMap. The TypeMapper has the task of selecting which version of a data type is required at the time it is being used. The user simply creates the TypeMap with the required TypeMapper. The TypeMap initialises the TypeMapper which gives it a chance to map any required types. When a developer writes a data type that is not in the map, the TypeMapper is called which resolves which version of a type to use. Creating a type map now looks like:
TypeMap map = new TypeMap( typeLibrary, new TypeMapperDynamic());
In this case a dynamic type map is being used to resolve the data types. It dynamically assigns any types required by the type map. A stream is created and written using:
typeStream = new TypeOutputStream( stream, map ); typeStream.writeObject( "address", addressObject );
If we were to write a specific version, the API would change to:
typeStream.writeObject( "address", "1.2", addressObject );
Once again this re-introduces a specific version too early. If the line above was on a server, any client or receiver of the data would be locked in to version 1.2 of the address. For this reason the first example is how objects should be written to the stream. This requires that the TypeMapper select the correct version of the address type.
Different type mappers can be created to deal with the various styles of type negotiation listed above. After an id has been mapped, any use of that name will tie directly to the specified version.
Meta Dictionary Update
Near the end of the last post I suggested a change to the meta dictionary which had the effect of only allowing a single version of any data type to be used on a stream. The requirement at the API to only use the name and not the version validates that this change would match the API. The meta dictionary has been updated to reflect this change. This changes very little in actual meta dictionary.
A consequence of this change is that an additional request/response pair is required for the traditional method of performing type agreement. The first time a client wishes to use a type it must send to the server the name of the type without specifying the version. The server maps a specific version to the type and returns the mapped identifier, the location of the definition and the definition structure. The client is able to check this against its local version. This method continues to use server dictated versioning and is a temporary solution until a more advanced protocol can be devised.
Another small update to the meta dictionary is naming. Currently types in Argot are defined using a short ascii string (e.g. "meta.abstract.map" ). In the meta dictionary this is defined as:
(library.entry
(library.definition u8ascii:"meta.name" meta.version:"1.3")
(meta.reference #u8ascii))
While the string implies that the name has groupings, each name is simply a unique string. As the number of objects in the TypeLibrary increases it will become more difficult to find specific groups of types. The string also goes against a central concept of Argot; there's no need to define string based expressions for encodings. The solution is to change the meta.name to:
(library.entry
(library.definition
meta.name:"meta.name_part" meta.version:"1.3")
(meta.reference #u8utf8))
(library.entry
(library.definition
meta.name:"meta.name" meta.version:"1.3")
(meta.array
(meta.reference #uint8)
(meta.reference #meta.name_part)))
This creates an array of name parts which is a more true representation of the name. This allows the TypeLibrary to build a hierarchy in the type library. For programmer simplicity a parser is still used for the text representation. However it would still be possible to write one of the entries above as:
(library.entry
(library.definition
(meta.name [ u8utf8:"meta" u8utf8:"name_part" ] )
(meta.version major:1 minor:3))
(meta.reference #u8utf8))
Another small change is from u8ascii to u8utf8. This allows a wider variety of languages to be used for names. In the future I'll introduce a meta.alias type as an extension to the meta dictionary. This will allow different languages (I.e. Spanish, Japanese, etc.) to define their own names for data types while still keeping compatibility.
Object Relationships
Another issue to add to the list. How to you deal with the relationship between data types and data objects across multiple versions. The whole point of Argot is to create a simple API for making it easy to read/write data to/from data streams. In essence to communicate knowledge between systems.
When binding a Java class to the TypeLibrary, is the Name or the data type definition version used? If the same class can be used for all Definitions then binding to the name is appropriate. If different classes are required between versions then binding to the definition is required. All definitions should define a common interface or super class. If this is not the case then the developer must be very careful not to create data streams that intermix objects as class cast exceptions will be likely. This is another area which is not fully developed and will need to be explored. However, relative to the versioning base meta data changes, this is a small task.
Conclusion
The Argot library now supports versioning, however, there's still some loose ends to tidy up. Future posts will explore the some of these loose ends. Version 1.3.0 which includes versioning is currently being cleaned up and will be released in the next week or two.
In this post I'll introduce the solution implemented for meta data versioning in Argot. It builds on the last post which introduced some of the versioning issues. Some light reading for getting the brain in gear after easter.
During the development of the versioning feature, a very important aspect of the system has been modified and updated. I found that every type definition needs more than a simple ascii string to define its name. Instead of a name, a location in the the type library is defined. To explain further, it's best to understand some background information and what this means for Argot.
To recap on the last post, performing type negotiation between peers (client and server) or application and file in the past requires each data type definition have a unique name. This has caused an issue with various aspects of meta data requiring a name where it has not been essential. This is because the basis of Argot is a single table which contains an identifier, name and definition.
Adding versioning into the meta data causes the single table to be broken up into multiple levels. Each name in the table may have multiple definitions. The small table example given in the last post now expands to a much larger table as shown in the table below.
Another example in Argot without versioning is that of abstract data types. These required multiple named definitions. A short example is:
meta.definition: meta.abstract(); meta.definition#basic: meta.map( #meta.definition, #meta.basic ); meta.definition#map: meta.map( #meta.definition, #meta.map );
The three definitions is actually trying to represent the following:
This diagram represents three levels to the data type structure. The first entry defines the name (meta.definition). The second entry defines version 1.0 as being an abstract type. The third and fourth entries are a relation to the version 1.0 definition and map the abstract type to other types.
Using the same naming mechanism to flatten this into a single table useful for Argot creates a group of ugly name strings:
id:10, name:"meta.definition" - meta.name; id:11, name: meta.definition#v1.0 - meta.abstract; id 12, name: meta.definition#meta.basic#v1.0 - meta.abstract.map #meta.basic; id 13, name: meta.definition#meta.map#v1.0 - meta.abstract.map #meta.map;
The solution to this is to replace each name with a location. The location is an abstract type that initially has three concrete location types. The first location includes the name, the second is a version definition and includes the id of the name location and the version information. The third location is a relation type and includes the id of a versioned definition( eg 11 in the above list) and a tag. The tag is a unique string used to uniquely identify the location. As in the flat table version of Argot where every name must be unique, a location must also be unique. It must be possible to find any definition using just its location data.
The separation of location from the definition is the key concept in Argot with versioning. The location being an abstract type also means that it can be extended to include any type of location specifier. The location specifier replaces the name and provides a flexible method to specify where to place a definition in the meta data library.
An interesting aspect of the above is that there is often more information being used to specify where the data belongs than the actual data. The abstract type "meta.definition" and mapping data definitions now look like:
// 1. define the name. (library.entry (dictionary.name:"meta.definition") (meta.identity) ) // 2. define version 1.0 as abstract. (library.entry (dictionary.definition name:"meta.definition" version:"1.0") (meta.abstract []) // 3. map meta.basic to the abstract type. (library.entry (dictionary.definition name:"meta.definition" version:"1.0") (meta.abstract.map #meta.basic)) // 4. map meta.abstract.map to the abstract type. (library.entry (definition name:"meta.definition" version:"1.0") (meta.abstract.map #meta.abstract.map)
Each entry in the above is in two parts, the location and the definition. This separation has also had other beneficial flow on effects. In the previous versions of Argot, information in the name string had to be replicated in the definition. In effect the definition was previously being used to specify both location and definition information. By using a data structure in the location, this is no longer required. An example of this is the "meta.abstract.map" definition which previously included both the abstract target and the mapping type. This now only includes the mapping.
The location information provides a mechanism that allows very flexible data structures to be defined in the data type library. This can be extended to define methods signatures or other methods of defining protocol semenatics. In effect it allows the type library to define a complex directed graph while still providing a flat one dimensional table structure so that each individual definition can be found.
Dictionary Text Format
An obvious change in the example above is that the syntax used to define a data type has also changed. The syntax is loosely based on LISP and provides a more flexible way of encoding the meta data in a text format.
Each parenthesis starts with the name of the data type. All subsequence elements is the data for that type. eg.
(library.definition name:"empty" version:"1.3")
This is an instance of the "library.definition"(v1.3) data type. The library.definition is defined as follows:
(library.entry (library.definition name:"library.definition" version:"1.3") (meta.sequence [ (meta.tag name:"name" (meta.reference #meta.name)) (meta.tag name:"version" (meta.reference #meta.version)) ]))
This shows that each list shown in parenthesis is actually a strict data structure.
Also in the example is how to include simple type data. "name" and "version" are the names of the fields in the library.definition structure. Field names can be specified for both simple types and data structure. The values for each follow the colon. i.e. "field name":"value" // not currently implemented or "field type":"value" or "field name":("data structure" ... ) // not currently implemented
For all value types the "field type" must provide a parser capable of parsing the value into an object used internally. In some cases a parser may be provided to parse a string into a complex internal structure. This is currently used for the meta.version type which uses MAJOR.MINOR string type.
The only other form are arrays. Arrays are specified using square brackets. e.g. [ element1 element2 element3 ] or "field name":[ element1 element2 element3 ] // not currently implemented
Meta Dictionary
The following is the full meta dictionary in its pre-compiled form. Each and every data type and structure used is defined in the meta dictionary. This provides the self referencing base from which all elements are defined. It does not attempt to define all basic data types. It only attempts to define those data types required as part of the meta dictionary. The data structures in the meta dictionary are used later to define all other common data types in the common dictionary.
You might want to skip the meta dictionary definition unless you really want to give the brain a work out.
// 0. empty
(library.entry
(library.definition u8ascii:"empty" meta.version:"1.3")
(meta.fixed_width uint16:0
[ (meta.fixed_width.attribute.size uint16:0) ]))
// 1. uint8
(library.entry
(library.definition u8ascii:"uint8" meta.version:"1.3")
(meta.fixed_width uint16:8
[ (meta.fixed_width.attribute.size uint16:8)
(meta.fixed_width.attribute.integer)
(meta.fixed_width.attribute.unsigned)
(meta.fixed_width.attribute.bigendian) ] ))
// 2. uint16
(library.entry
(library.definition u8ascii:"uint16" meta.version:"1.3")
(meta.fixed_width uint16:16
[ (meta.fixed_width.attribute.size uint16:16)
(meta.fixed_width.attribute.integer)
(meta.fixed_width.attribute.unsigned)
(meta.fixed_width.attribute.bigendian) ] ))
// 3. meta.id
(library.entry
(library.definition u8ascii:"meta.id" meta.version:"1.3")
(meta.reference #uint16))
// 4. meta.abstract.map
(library.entry
(library.definition u8ascii:"meta.abstract.map" meta.version:"1.3")
(meta.sequence [
(meta.tag u8ascii:"id" (meta.reference #meta.id))
]))
// 5. meta.abstract
(library.entry
(library.definition u8ascii:"meta.abstract" meta.version:"1.3")
(meta.sequence [
(meta.array
(meta.reference #uint8)
(meta.reference #meta.abstract.map))]))
// 6. u8ascii
(library.entry
(library.definition u8ascii:"u8ascii" meta.version:"1.3")
(meta.encoding
(meta.array
(meta.reference #uint8)
(meta.reference #uint8))
u8ascii:"ISO646-US"))
// 7. meta.name
(library.entry
(library.definition u8ascii:"meta.name" meta.version:"1.3")
(meta.reference #u8ascii))
// 8. meta.version
(library.entry
(library.definition u8ascii:"meta.version" meta.version:"1.3")
(meta.sequence [
(meta.tag u8ascii:"major" (meta.reference #uint8))
(meta.tag u8ascii:"minor" (meta.reference #uint8))
]))
// 9. meta.definition
(library.entry
(library.definition u8ascii:"meta.definition" meta.version:"1.3")
(meta.abstract [
(meta.abstract.map #meta.fixed_width)
(meta.abstract.map #meta.abstract)
(meta.abstract.map #meta.abstract.map)
(meta.abstract.map #meta.expression)
(meta.abstract.map #meta.identity)
]))
// 10. meta.identity
(library.entry
(library.definition u8ascii:"meta.identity" meta.version:"1.3")
(meta.sequence [
]))
// 11. meta.expression
(library.entry
(library.definition u8ascii:"meta.expression" meta.version:"1.3")
(meta.abstract [
(meta.abstract.map #meta.reference)
(meta.abstract.map #meta.tag)
(meta.abstract.map #meta.sequence)
(meta.abstract.map #meta.array)
(meta.abstract.map #meta.envelop)
(meta.abstract.map #meta.encoding)
]))
// 12. meta.reference
(library.entry
(library.definition u8ascii:"meta.reference" meta.version:"1.3")
(meta.sequence [(meta.reference #meta.id)]))
// 13. meta.tag
(library.entry
(library.definition u8ascii:"meta.tag" meta.version:"1.3")
(meta.sequence [
(meta.tag u8ascii:"name"
(meta.reference #u8ascii))
(meta.tag u8ascii:"data"
(meta.reference #meta.expression))]))
// 14. meta.sequence
(library.entry
(library.definition u8ascii:"meta.sequence" meta.version:"1.3")
(meta.array
(meta.reference #uint8)
(meta.reference #meta.expression)))
// 15. meta.array
(library.entry
(library.definition u8ascii:"meta.array" meta.version:"1.3")
(meta.sequence [
(meta.tag u8ascii:"size" (meta.reference #meta.expression))
(meta.tag u8ascii:"data" (meta.reference #meta.expression))]))
// 16. meta.envelop
(library.entry
(library.definition u8ascii:"meta.envelop" meta.version:"1.3")
(meta.sequence [
(meta.tag u8ascii:"size"
(meta.reference #meta.expression))
(meta.tag u8ascii:"type"
(meta.reference #meta.expression)) ]))
// 17. meta.encoding
(library.entry
(library.definition u8ascii:"meta.encoding" meta.version:"1.3")
(meta.sequence [
(meta.tag u8ascii:"data" (meta.reference #meta.expression))
(meta.tag u8ascii:"encoding" (meta.reference #u8ascii))]))
// 18. meta.fixed_width
(library.entry
(library.definition u8ascii:"meta.fixed_width" meta.version:"1.3")
(meta.sequence [
(meta.tag u8ascii:"size" (meta.reference #uint16))
(meta.tag u8ascii:"flags"
(meta.array
(meta.reference #uint8)
(meta.reference #meta.fixed_width.attribute)))]))
// 19. meta.fixed_width.attribute
(library.entry
(library.definition
u8ascii:"meta.fixed_width.attribute" meta.version:"1.3")
(meta.abstract [
(meta.abstract.map #meta.fixed_width.attribute.size)
(meta.abstract.map #meta.fixed_width.attribute.integer)
(meta.abstract.map #meta.fixed_width.attribute.unsigned)
(meta.abstract.map #meta.fixed_width.attribute.bigendian)
]))
// 20. meta.fixed_width.attribute.size
(library.entry
(library.definition
u8ascii:"meta.fixed_width.attribute.size" meta.version:"1.3")
(meta.sequence [
(meta.tag u8ascii:"size" (meta.reference #uint16))
]))
// 21. meta.fixed_width.attribute.integer
(library.entry
(library.definition
u8ascii:"meta.fixed_width.attribute.integer"
meta.version:"1.3")
(meta.sequence []))
// 22. meta.fixed_width.attribute.unsigned
(library.entry
(library.definition
u8ascii:"meta.fixed_width.attribute.unsigned"
meta.version:"1.3")
(meta.sequence []))
// 23. meta.fixed_width.attribute.bigendian
(library.entry
(library.definition
u8ascii:"meta.fixed_width.attribute.bigendian"
meta.version:"1.3")
(meta.sequence[]))
// 24. dictionary.name
(library.entry
(library.definition u8ascii:"dictionary.name" meta.version:"1.3")
(meta.sequence [
(meta.tag u8ascii:"name" (meta.reference #meta.name))
]))
// 25. dictionary.definition
(library.entry
(library.definition u8ascii:"dictionary.definition" meta.version:"1.3")
(meta.sequence [
(meta.tag u8ascii:"id" (meta.reference #meta.id))
(meta.tag u8ascii:"version" (meta.reference #meta.version))
]))
// 26. dictionary.relation
(library.entry
(library.definition u8ascii:"dictionary.relation"
meta.version:"1.3")
(meta.sequence [
(meta.tag u8ascii:"id" (meta.reference #meta.id))
]))
// 27. dictionary.location
(library.entry
(library.definition u8ascii:"dictionary.location"
meta.version:"1.3")
(meta.abstract [
(meta.abstract.map #dictionary.name)
(meta.abstract.map #dictionary.definition)
(meta.abstract.map #dictionary.relation)
]))
// 28. dictionary.definition.envelop
(library.entry
(library.definition
u8ascii:"meta.definition.envelop"
meta.version:"1.3")
(meta.envelop
(meta.reference #uint16)
(meta.reference #meta.definition)))
// 29. dictionary.entry
(library.entry
(library.definition u8ascii:"dictionary.entry" meta.version:"1.3")
(meta.sequence [
(meta.tag u8ascii:"id"
(meta.reference #meta.id))
(meta.tag u8ascii:"location"
(meta.reference #dictionary.location))
(meta.tag u8ascii:"definition"
(meta.reference #meta.definition.envelop))]))
// 30. dictionary.entry.list
(library.entry
(library.definition u8ascii:"dictionary.entry.list"
meta.version:"1.3")
(meta.array
(meta.reference #uint16)
(meta.reference #dictionary.entry )))
Library types
These types are only used for the pre-compiled definitions and are used by the compiler. They are kept separate from the meta dictionary. These are required so that a user does not need to define identifiers for each type and keep track of which entry is defined by which identifier.
// library.entry (library.entry (library.definition name:"library.entry" meta.version:"1.3") (meta.sequence [ (meta.tag "location" (meta.reference #library.location) (meta.tag "definition" (meta.reference #meta.definition) ])) // library.location (library.entry (library.definition name:"library.location" meta.version:"1.3") (meta.abstract [ (meta.abstract.map #library.definition) ])) // library.definition (library.entry (library.definition name:"library.definition" meta.version:"1.3") (meta.sequence [ (meta.tag "name" (meta.reference #meta.name)) (meta.tag "version" (meta.reference #meta.version)) ]))
Multiple Versions Per Stream
Each of the entries in the meta dictionary is compiled into two dictionary entries. For example the "empty" data type is defined by the following two dictionary entries:
(dictionary.entry meta.id:1 (dictionary.name name:"empty") (meta.identity)) (dictionary.entry meta.id:2 (dictionary.definition #empty meta.version:"1.3") (meta.fixed_width size:0 [ (meta.fixed_width.attribute.size size:0) ]))
This fits the versioning model of Argot. The first entry simply defines the name (empty), while the second entry defines the definition of version 1.3 of the "empty" type. This mimics the internal representation of the type library. A question I am yet to resolve; should this be the external representation? Another solution for the external representation combines the two entries:
(dictionary.entry meta.id:2 (dictionary.definition u8ascii:"empty" meta.version:"1.3") (meta.fixed_width size:0 [ (meta.fixed_width.attribute.size size:0) ]))
The advantage of this is that it reduces the data size for the dictionary. A consequence of this is that the meta identifier (meta.id) is the same for both the name and the specific meta data version (in this case 1.3). Therefore only the one version of a data type can be used in any individual communication or stream. This is possibly an advantage, as the constraint will create an easier to debug and program communications environment. It also allows a simpler API to be developed which only needs to map each named type to a single version. The disadvantage is that it reduces the flexibility of the communications environment; there may be situations where multiple versions of the same type need to be communicated in the one stream.
Nearly Full Circle
Another adaption to the above is to remove the version from the definition. e.g.
(dictionary.entry meta.id:2 (dictionary.name u8ascii:"empty") (meta.fixed_width size:0 [ (meta.fixed_width.attribute.size size:0) ]))
The removal of the version information requires that each definition is used to create a unique signature. The signature becomes the version data used to match particular versions. This method is very close to the original method of defining data, however, the location instead of name is still required. The location type allows the relation location type to be used for abstract types and other types that are defined using multiple entries. This disadvantage of removing the version data is that it requires a more complex library and doesn't provide any form of ordering to be performed between versions. For this reason it won't be used.
Conclusion
The solution implemented for versioning meta data in Argot provides a new and innovative approach to this difficult problem. The concept of using a location in a directed graph allows any graph to be built and partially compared. In the next post I'll explore the area of remote data type negotiation and show how versioning adds new complexities.
Data type meta data versioning in communication is one of the more (if not most) complex areas of distributed computing. It's also an area that I've managed to avoid for quite some time. That is until someone sent me an email asking about versioning in Argot. This has kicked off a thought process which has resulted in around six months of investigation, a couple failed attempts, and introducing a long overdue feature in Argot. The final result solves the problem of versioning in a new and unique way.
In the next series of posts I'm going to discuss some of the issues of versioning and how versioning has been implemented in Argot. Be warned that the posts are probably going to be long and complex. Along the way, I'll demonstrate the new Argot meta dictionary which will become the basis for versioning meta (type) data in Argot.
Background
In Argot, before now, I've taken the view that a client and server have a single version of each data type. Each data type has a name, a structure definition and a unique identifier. When an Argot connection is established the client and server compare the names and data structures for each type. If the data structure of any type is different between client and server then the system is unable to communicate that data type.
The image above demonstrates how a client and server create a shared table which defines the set of data types that they can use to communicate. The name and definition of each data type must be the same on both client and server for an entry to be added to the shared table. The client and server assign a unique internal identifier which may differ for their own data type tables; each data type in the shared table has a unique identifier that is agreed between client and server.
For my purposes this method of having a single data type has worked fine. In my small environments I can update the client and server at the same time. However, versioning is a necessary requirement for many systems. You can't always upgrade all clients after a server has been updated. This means a single server must be able to support multiple versions on the client. In a similar way, you can't always upgrade all servers, requiring a client to support multiple versions of data structures. In situations where both clients and servers can not be upgraded then both must have multiple versions of data types. Therefore Argot needs to be modified to allow a data type name to have multiple definitions or versions.
The Issue of Names
The development of Argot to some extent has always been based on a language dictionary. The idea is that each and every data type definition can be taken individually (much like a single word can be found in a dictionary) and used in any data dictionary (schema). The language dictionary is once again the premise for how versioning should be handled by Argot. A standard language dictionary defines various aspects of a word's definition. Each word will have its pronunciation, phonetic spelling, various ways the word is used and possibly its etymology.
Compare this to an example using Argot's (version 1.2) definition:
address:
meta.sequence([
meta.reference( #u8ascii, "street"),
meta.reference( #u8ascii, "suburb"),
meta.reference( #u8ascii, "state" )
]);
Argot provides a very basic format to create definitions. It has two parts: the name ("address" in the example above) and the definition. Internally this is also assigned a unique identifier. This simplicity is a double edged sword. The consequence is that every definition must have a name. However, there are many cases where a name is not required for Argot definitions.
The other important aspect of Argot is that each statement or definition must stand alone. This is required so that a client and server can compare each part of a types definition. This means that a single concept may be defined using multiple statements. This is the case for abstract data types. For example:
meta.definition: meta.abstract(); meta.definition#basic: meta.map( #meta.definition, #meta.basic ); meta.definition#map: meta.map( #meta.definition, #meta.map );
In this case meta.definition is defined as an abstract data type. The meta.basic and meta.map are then mapped to the abstract type using separate definitions. This requires that Argot define fake names like "meta.definition#basic" so that each definition can be found in the data type tables.
Introducing versioning offers an opportunity to modify the way data types are defined to create a model which is closer to a language dictionary.
An interesting aspect of basing versioning on a language dictionary is that each version of a data type may be completely different. A single dictionary might define an address as:
address version:"1.0" : sequence( [ reference( #u8ascii, "street" ) reference( #u8ascii, "suburb state" ) ] ); version"2.0" : sequence( [ sequence( [ reference( #u8utf8, "street number" ) reference( #u8utf8, "street name" ) reference( #u8utf8, "street type" ) ]) reference( #street, "street" ) reference( #u8utf8, "suburb" ) reference( #u8utf8, "city" ) reference( #u8utf8, "state" ) ] );
This is considerably different to how many other object serialization systems work. For instance, in ProtocolBuffers a label is assigned to each field in a definition. New versions consist of adding new optional elements to the definition. In effect this means a definition can not change radically between versions. It also means that new versions must become a hybrid data structure of both old and new, moving the strict rules about the data structure into the program. The advantage of the language based model is that versions can be completely different and encode strict definitions at the protocol or file format level.
Versions in Structure Definitions
One of the first problems to be solved in introducing versioning is how to reference a data type with multiple versions in another definition. For example, in the following example the structure test refers to "foo" and "bar" version 1.0.
test: version:"1.0": sequence( [ reference(#foo, version:1.0) reference(#bar, version:1.0) ]))
However, there's a problem, when a data structure is defined and contains references to other data types it creates a brittle type system that is difficult to maintain. In the "test" definition there's a strict relationship of versioning between each sequence sub element. If foo was to be updated to "foo_1.1" the "test" type would also need to be updated. This causes a versioning ripple through every element that uses foo. Every element that was changed will also cause changes.
In the following example we try defining "test" using major and minor versions. Each reference can then specify the minimum version that is supported. The problem with this is that every definition requires too much data. The developer and schema designer will get lost in meta data versioning information.
"test" vMajor:1 vMinor:0: (reference #foo (minVersion major:1 minor:0) (maxVersion major:1 minor:99) );
Looking back at the dictionary model (ie real world dictionary book) that Argot was built upon, it is clear that every word definition does not refer directly to a specific version of each word used to define another. Returning back to the original concept of a data structure definition without version information:
"test" version:"1.0":
sequence([
reference( #foo)
reference( #bar)
]));
In many cases the actual version of a referenced field is probably not important when defining the data type. As long as the server and client both agree on what version of a particular type they agree on then the data can be any format.
This model has the advantage that any change to "foo" does not cause a ripple through other data types. It also removes any barriers to what version of "foo" a client and server should use to communicate. This places additional burden on the programmer to ensure that all versions of "foo" that can be understood by the software are interchangeable through all parts of the application. Overall the advantages of not specifying a version is preferred over the other options, so it will be adopted for Argot versioning.
Using this model requires the ability to identify both the Name and definition as two separate references in the Argot Type system. When data structure's are being defined, any reference uses the Name identifier. When a data structure is being used in communication it uses a specific definition. This means that the name must have its own identifier and form part of the TypeLibrary.
Version Information Data
There are a few options as to how to encode the version information for a specified data structure. As far as Argot is concerned each version of a data type is a completely different type. From this point of view having a single integer value to represent the version is easiest. However, from a user point of view the version often consists of major, minor and patch levels.
Version options:
- Single Integer - Has the advantage that it aligns with the design of Argot. Each version is completely independent of the other. Ordering of versions can be easily maintained.
- Major, Minor, Patch Integers - Allows each data type to have multiple levels. Ordering of later versions can be easily maintained. The other advantage of this is it allows a mechanism for designers to make "compatible" changes to the protocol as part of minor revisions. A major revision will often signal a departure from previous logical designs and the previous system Object will no longer be a viable representation. A minor revision will signal the addition of a field or other minor change in which case the same system Object can be used. This method also allows a developer to keep track of the version of software that a definition was introduced.
- String - A generic string has the advantage that any versioning system that the developer produces can be handled. No ordering can be guaranteed unless an additional ordering function is supplied by the developer and bound to each data type.
- Abstract Type - An abstract type offers the most flexibility as the user is able to define the version using any method and mapping to the abstract type. This expands the meta dictionary and makes versions more difficult to compare.
To reduce complexity in the initial development a simple string was used. However, as the release version is developed this will migrate to a MAJOR and MINOR mechanism. The major and minor values are small unsigned integers. The use of major and minor releases becomes important to differentiate between new and older type versions. Later releases may eventually allow multiple tags to be assigned to specific versions providing a method of performing a version control across a group of data types.
This sets a couple of the core concepts of versioning in Argot. In the next post I'll introduce the key concept that makes versioning in Argot a possibility and demonstrate the Argot meta dictionary.
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:
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:
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.
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.
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:
- 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.
- Build and read Meta dictionary. The rest of the meta dictionary is read and mapped between the application and file.
- 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.
- 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.
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.
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.
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.
Got any comments, you can leave them on the shadow blog here.
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.
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.
This week Google released Protocol Buffers to much acclaim, receiving coverage on slashdot, osnews and other places. I must admit that I haven't looked too closely at Protocol Buffers implementation. This is because I read as far into the documentation to discover that there's a set number of primitive types that can be encoded onto the wire. This basically equates to yet another adaption of the Sun XDR data encoding method used in the original RPC.
I must admit that I did do a little astroturfing on the Protocol Buffers google group which did actually result in a few hits to the einet web site. It didn't equate to any downloads or any actual interest in Argot which is quite disappointing. Obviously astroturfing is not the right way to advertise a new technology.
There's also been a few responses in the blogosphere regarding this release from Ted Neward, Steve Vinoski and Stefan Tilkov. The latter two have simply deferred to Ted's entry which comprises a good analysis of Protocol Buffers. As I read this analysis, I started to think how Argot solved many of the issues pointed out in Protocol Buffers. I was going to respond to Ted's blog, but its probably easier to do this here on my own Blog.
Before getting into responding to Ted's analysis, I should say what Argot is all about. At its most basic Argot is about defining meta data for describing binary data formats and a library for encoding and decoding that data. What makes Argot interesting is that the meta data itself is encoded in binary. This creates the ground work for dynamic data agreement and various other things. There's a full description of Argot here, so I won't bother with the technical implementation details right now.
The first issue Ted found with Protocol Buffers is their claim of language and/or platform-neutrality. I must admit I do claim the same with Argot. I also still regard this as a reasonable claim, and believe Protocol Buffers claim is also reasonable. In my mind, this is not a claim that the solution has complete coverage of all languages. It's simply a claim that no special language tricks or platform specifics have leaked into the data format. Compare this against RMI or other language specific solution. To implement RMI on another language would be difficult as its core data encoding requires Java specific information. I do understand Ted's issue with this and agree that XML's coverage is huge. Currently I have implementations of Argot in Java, C and C#, although I'm currently only working on updating and improving Java. So yes Argot is designed to be language and platform neutral but is currently best supported by Java.
Next Ted reminisces to when binary formats were big. Actually, I don't remember them being big at all. I remember CORBA being the big thing. Other than ASN.1 there has been very few attempts to build structured binary data formats that are independent of RPC or other system. There's some big problems with binary formats being inflexible, tightly-coupled, etc because there has been no real interest in actually solving these problems at a binary level. I will come back to many of these issues soon, as these are the exact problems I built Argot to solve.
Ted moves on to talk about all the advantages of XML. I agree with most of his comments on XML. For what XML was designed to be, it has done very well. And it has stayed true to its initial principles. This is great, but XML is not solving many of the things it was not designed to solve. Yes this makes little sense intentionally. There are many situations where binary data formats are required for speed, size constraints, etc. XML is not the data presentation layer silver bullet. The problem Argot, Protocol Buffers and others are trying to solve is how to move binary data around in a fast, efficient way. Ideally many of the advantages and lessons learned with XML and XML Schema can be applied to binary data formats.
As a side note, one area that I've just started working in the last few months is investigating the issues of interoperability for home area network (HAN) devices in the Energy industry. There's some really interesting work being done to build interoperable systems. They are defining the data formats to ensure all the smart appliances will work together in the home. These are really hard problems which require binary data format agreements so even the smallest of devices can work together. This is not an area where XML will be accepted. Its a market where manufacturing items are costed in cents and the CPU processing power required for XML is not acceptable. However, these industries need to face all the problems that binary solutions provide without the tools and solutions that XML provides. Surely there's a better way than just accepting the old issues in binary data solutions.
To bring it back to Ted's analysis of Protocol Buffers. I'm sure he understands that there's a need for binary data. I think he takes issue that Protocol Buffers is claiming to provide similar benefits of XML in a binary format. I agree completely that Protocol Buffers does not provide most of the benefits of XML. The problem is that in this increasingly connected world where convergence will mean that every appliance in the house might soon be conversing, we really do need a solution. We actually need more people working on this and not just saying how wonderful XML is. I accept that XML is great in all that it achieves, but I don't accept that we can't have most of the benefits of XML in a binary format for where it is required.
Ted also refers to the XML binary InfoSet specification in his analysis. I think I need to be clear here that when I talk about requiring many of the benefits of XML in a binary format, I don't believe that XML binary Infoset or similar is the answer. These solutions still require complex decoding mechanism which once again do not work in many situations. We need the benefits of XML at a really basic binary level.
I'll now move onto the guts of Ted's analysis of Protocol Buffers. I'll now examine some of the biggest short comings of Protocol Buffers identified by Ted. I'll discuss: if Argot solves it, if its required by binary communications and if it can be done effectively.
- Binary is hard to work with. Agreed. However, as already discussed its a requirement in many situations. Lets make it as easy as possible to work with. Argot solves the problem by creating and incredibly flexible meta data structure that can be extended. In fact I'm willing to claim that the Argot meta data format (which has similarities to S-Expressions) is more flexible than XML Schema and anything else out there. I agree that binary data will never be as easy as text for humans to read, however, in the situations where it is needed it is not humans reading it. In these situations we should build tools to make it easier for humans to read. The way to achieve this is through good meta data.
- Binary is tightly-coupled. This is probably the biggest issue with binary. In fact for most situations binary solutions actually need to be tightly-coupled for each individual message. This is where Argot shines the brightest. It is the only solution I know that can allow two peers to dynamically discover each element's meta data. What this means is that a server and client can support multiple versions of the same data structure and pick the format that both will use. I believe this is a very important capability which is needed in binary solutions. It gives clients and servers the ability to change over time and still support sets of data formats. For more details read about the TypeMap in the Argot documentation. I call this allowing tight-binding and loose-coupling. An important note is that I have proved this with a server implementation of around 7kb. It does not take a huge amount of data as the meta data format is itself binary.
- XPath. This is something I believe can be achieved using Argot, however, it is not something I've worked on. At the moment, I don't believe its an area that developers need solutions for when binary is required. Its a nice to have that could be added to Argot tools.
- XSLT. I agree this is a great example of what can be built over the top of XML. I have a long term plan to build something like this, however, it requires a language around Argot which is not yet developed. Once again, this is not a core requirement for working with binary solutions that is required today.
- Structureless parsing. This is an area that I've just started working on. I believe that with enough meta data you can parse anything. In the next release of Argot I've built a parser that is able to read binary data into a form of DOM tree without knowing the meaning of the data. This is an important step to building XPath, XSLT and generic binary data editor tools. This also makes it possible to connect to a server and dynamically discover its interfaces and message formats and then dynamically build requests and read responses. Solving this ability at a binary level should lead to some interesting results when all appliances in the home can publish their message formats and capabilities.
There's probably a lot more that I could add here about Argot. However, I'm trying not to make this a sales pitch. The point I'm trying to make is that XML is a great tool for many situations. However, there are plenty of situations where binary data is required. We need more people understanding what is needed to build binary systems that support many of the features already supported by XML. We also need to recognise that the situations binary data is used is different from XML. The set of tools and use cases are different. I know that it is possible to build tightly-bound and loosely-coupled servers that communicate in binary as I've done it with Argot. Maybe someone can prove me wrong with Argot; I'd enjoy the discussion.
Here's an example of the changes that's been made in Argot in the latest version. In Argot 1.2 an unsigned 8-bit integer:
u8: meta.basic( 8, 0 );
In the latest version, the text format is now using a form of S-Expressions. The unsigned 8-bit integer now looks like:
(meta.structure meta.name:"uint8"
(meta.fixed_width uint8:8
[ (meta.fixed_width.attribute.size uint8:8)
(meta.fixed_width.attribute.integer)
(meta.fixed_width.attribute.unsigned)
(meta.fixed_width.attribute.bigendian) ] ))
There's obviously some big changes here. The name has changed from u8 to uint8 to be more in line with the C language definition. The other big change is that instead of defined using meta.basic, it is defined with meta.fixed_width. This new type includes the size and an array of attributes. The attribute type is abstract and can be extended define any number of attribute types.
The same definition can be shown in a very quick and dirty visual editor.
There's plenty to improve with the editor, but it shows the concept.
After studying the idea of a language for Argot I realised that I needed to go back and make some changes to Argot to support it. Over the last few weeks I updated the Argot dictionary compiler and built an Argot 1.3 alpha. This latest version has required some major changes to the guts of Argot. Today I just finished some end to end testing which shows that all the changes are working.
The first was to move the Argot dictionary text format to a S-Expression format. This is the first step to allowing an Argot language which uses the same S-Expression format. The Argot compiler can now over time be updated to read any type of data.
The next was to update the Meta Dictionary. The meta dictionary is the set of self describing data elements which forms the heart of Argot. This is normally a scary process as each small change ripples through other parts of the meta dictionary. While the changes were quite major they didn't change the more difficult aspects of the meta dictionary.
The changes included changing the meta.basic type to meta.fixed_width. This now has attributes which can be expanded to describe any fixed width data type. The other was to split the meta.reference type into a meta.reference and meta.tag type. Originally all references required a description. This wasn't required in many situations. Now the reference is a simple type reference and the tag provides a description. The other was to allow abstract data types to map to other abstract data types. This creates a more flexible type system.
The final change which has been the most challenging has been to create a Document Object Model(DOM) style interface to Argot. The ability to read in Argot data directly into business objects or into an abstract DOM structure. The current version has some code duplication, but works like a charm.
There's still some clean up to do on the code, but it should be released soon. I may even build a small example Argot editor to show off the new DOM style data.
PS If none of that made any sense whats so ever.. don't worry, it will all become clearer when an Argot editor is built!
After a year and a half of not doing providing news, I've decided that in 2008 I'll actually start again. My aim is to document the design and implementation of a new browser. I still need to work out what to call it. More soon...
It's been a week of my new job in the Wireless and Location group at Sensis. The first week is usually a bit slow and painful as you try and get your head around a new set of tools and code. So far, it has been pretty good, and I've gotten up to speed quickly. The less brain strain in the first week the better.
On my first day I found a new tool to add to my collection of favourites. Emma is a coverage tool which tells you what percentage of your code has been utilized during tests. It's a great way to ensure that you've debugged enough of your application, or written enough unit tests. In other jobs I've used commercial versions of this type of tool, however, Emma is the first one that I've found that is completely free.
The other thing I need to get used to, is not having much time to work on my projects. Thankfully Argot and Colony are nearly at a stage I'm happy with. The biggest task left is to prepare Colony to be put on the public Subversion with the same license as Argot. After that I can move on to projects that use Argot and Colony, rather than continue developing it.
Speaking of other projects, after three months of hitting my head against a wall, I was able to add loadable modules to LuaPlayer. One of the smaller projects will be to add Argot and/or Colony client to LuaPlayer as a loadable module.
It's already June and there's been a lot going on that I haven't been talking about here. The biggest news is that I'm now back at University, studying a postgraduate certificate in innovation management at the Melbourne Business School. What that all means is that I'm studying business at the top business school of Australia. The course has a focus on Innovation which should provide some great help for evaluating and commercialising my various software related ideas.
The course so far has been very interesting. The first subject, "World of Management" provided a nice overview of all the course. It also had a strong focus on the theory behind learning and skills required to make the most of the course. I must admit that the subject was geared towards students doing a full MBA. This meant that quite a bit of content was geared towards the skills needed to survive a three year part time masters course. Not an easy task! Overall I'm glad I did the subject. Last Saturday was the exam which was a bit of a shock to the system after 10+ years of not having to do an exam. It's nice to have the first one out of the way though.
My second subject I'm taking is "Organising for Innovation". As you can guess, this is all about how to structure business so that it can excel at creating and evaluating new and innovative concepts and then more importantly get them built. There's been some fantastic information in this course already and I'm only into the third week.
In other news I have finally taken the plunge and will be getting a car. This is the first car that I've ever owned after owning motorbikes most of my driving life. After looking around at many cars and deliberating way too much I ordered a new Honda CRV Sport. Of course it is black and comes with some fancy extras like sunroof, etc. To finish off the look of the car I also did something rather fun and silly. I purchased personalised number plates with...... ROXOR. It would have been better if they allowed r0x0r, but they don't allow lower case or the number zero. ROXOR will have to do! I pick up the car this friday which should be fun!
From all the above going on I have had little time to concentrate on other projects. Thankfully ps2dev.org has been moving along nicely the last few months. The forums have a good size community and the moderators have been doing a good job. It also look as though there will be a reasonable number of entries to the Fourth Creation Game competition.
I can't say the same for Argot and Colony. These projects need to mature a little more and find a niche. Without that communication happenning to drive development things are going to continue to move slowly.
After a lot of deliberation last week, I now have a job! I'll be working in the Wireless and Location group at Sensis. Sensis are the company behind Australia's Yellow and White pages directories. They are also very serious about the internet and creating a lasting presense there. I think working in the Wireless and Location group will be a great fit for my skills and background with Argot and Colony. The job starts on the 20th of March, which gives me this next two weeks to get a few things done.
One of those things has been to fix Colony to work with the latest version of Argot. While I prepared Argot for release and created the C# and C versions, Colony became out of sync with the Argot interfaces. Bringing it back into line also added the features of strongly bound interfaces between client and server. Now every method is checked to ensure the request/response/exception parameters are the same. This tight contract between client and server has really proven its worth while upgrading ps2dev.org's web site software. Not a single byte change in an interface gets past Colony.
Speaking of ps2dev.org, I upgrade the site software today. The last upgrade was the start of August last year. I'd love to spend more time on the software, however, there's always so much I'd like to do. Today's software upgrade includes News items, locking and unlocking topic items, file handling changes, ability to delete topics and a few other things. Of course there's always plenty more to do, but it might be time to move onto other things.
Hi Ho Hi Ho.. it's off to work I go.. again.
After about eight months of working on Argot, Colony and generally attempting to move Einet forward; it is time to admit defeat for now. I've accomplished the main goals of the last eight months, which was to release Argot under a shared source license. As always, it didn't go quite to plan. The Open Vendor license didn't get approved by the OSI, which was a disapointment. Argot didn't get released before Christmas which was also a disapointment. However, Argot did get written in Java, C# and C, and was released. A manual was written which describes the details of Argot's dictionary. Overall, the time taken was well worth it.
In the past month a lot of time has been taken up with looking for work. However, that task should be finalised this week.. after I've received two offers late last week. Now it's time to make the difficult decision of which one to take. Both are contracts, and both are interesting work. In the next day the final choice will be made.
In the past month I've also been working on Colony and resyncing it with Argot. It has required a few changes to the network type agreement interfaces, but it is turning out for the best. The Argot changes have been put in Subversion for anyone to check out online.
I've also started reading Ralf's blog which I found while Blog jumping last week. He has some smart theories on RPC and how to develop client interfaces for them. Have a read of Form should follow function and Coordination structures beat RPC. They offer some well thought out arguments on RPC methodologies.
I've also finished reading The Innovator's Dilema by Clayton M. Christensen. It focuses on distruptive technology and why large companies fail to adapt to new technologies. The author uses the Hard Drive industry as a case study, which is a lot more facinating than you'd expect. Do you know how many companies who made the big 14" hard drives for the original main frame market survived to make 8" hard drives for the mini computer market? Zero.. Read the book to understand why!
Finally, I've met up with the people up at NICTA/Melbourne Uni doing P2P research. They're doing some interesting research into data storage and retrieval using Distributed Hash Tables. They've even wrapped it all up and made a gaming platform to test out their theories. Hopefully after work has started I'll still have a chance to keep in contact with what they are doing. I also found out that they will be hosting Middleware 2006 in Melbourne later this year! Maybe it's time to try putting pen to paper and turn my Argot knowledge into a paper worth publishing.
After some work with Makefiles, Nant and Ant the Argot packages are finally released. Each package includes the argot dictionary compiler; which for now requires Java. The files are availabe from the einet web site. If you have just happened to stumble across Argot, have a look. Argot provides the abililty to describe binary data so that it can be used more effectively in file formats, communications or anywhere data is written or read. Being available in C, Java and .Net(C#), it can be used for heterogenous systems. Being binary, it is effecient and can be used in small devices to internet services.
In the next few weeks there's still plenty to do. Thankfully the tedious job of getting subversion set up and packages released is done. Maybe I can get back to some code. In particular, it would be nice to make some changes to the client/server data type agreement protocol; maybe even come up with a short name.
Another year has come to a close, and the festive season has wound down. The week before christmas I had planned to package up Argot ready for release and advertise, however, it wasn't to be. There's always Way too much to do, and way too little time. The break after Christmas has been fantastic with great presents, and visiting family and holidays. Now the break is over it's time to get back to grind stone.
As usual, I'm looking ahead to a new year and wondering how much of all the things I'd like to get done will get done. Most of the items on my todo list this year so far are small and with a bit of concentration shouldn't take too long. The major items are: to finally get Argot out the door and start telling the world about it, finish the PSP version of Send0r, and add improvements to ps2dev web site. There's plenty to do on all those fronts, so time to get to them.
In my current job I've been doing development at the front end of a web application. This has involved getting a lot more involved with technologies like CSS, HTML, Javascript, AJAX and plugins. This is on top of the requirement of developing in Java using Struts, Hibernate and database technologies. This tower of babel we have built for ourselves in computer science is one of the most bizare things to come out of the new milinium. To make matters worse, it is not just the large number of different technologies that is difficult to learn and put together. The technologies themselves change from browser to browser; css, javascript and ajax all have their idiocincrocies. There are complete books devoted to helping understand how to make web sites work on multiple browsers. This is not where I thought software development would end up.
The question I ponder is when is this pain going to end? A developers job is supposed to be to solve commercial problems and create competitive advantage for companies. I think we spend more time just trying to keep up with the latest methods and languages and in particular understand how they can come together and actually work.
I believe Argot holds a key in reducing this tower of babel. At the core of all programming and mark up languages is a text description of what is trying to be achieved. Argot is designed to record complex data structures to disk in a form that is quick and easy for programmers to read and write. The result is that the structures we describe in CSS, HTML, Javascript, Java, etc all become part of the one structure. This has some huge implications for how we develop systems and languages.
The most important aspect of applying argot to development is that it reduces each concept in all our languages to indivdual structures (words) in a dictionary. We have the ability with Argot to add or remove words when ever we like which allows the whole system to evolve. So where's this most awesome solution you might ask? It requires a lot more work than I have time to accomplish right now. If you're interested in throwing in a few lines of code, please let me know. Maybe together we could reduce this tower of babel to rubble.
The plan is reasonably straight forward. The most important aspect to be solved initially is creating an Argot editor. To accomplish this Argot requires an Abstract model which can read any argot data and allow it to be manipulated. The initial editor is likely to be written in Java and use a basic tree view to get started. From their the tree view can be replaced with a text representation and editor. This provides the language with a structure that more developers understand and are happy to work with.
After an editor is built it comes back to building the language. The most important aspect of an Argot based language is the words in the dictionary. It must be created so that it can be flexible and be open to change. Developing the initial set of words and a basic engine to execute them is likely to be achieved incrementally. It is likely that the language will have some basis in scripting or object oriented languages such as small talk. However it must also combine this with concepts from HTML and CSS to allow easy methods of defining look and feel for user interfaces.
If this language can be created the final part of the puzzle is to add communications. Argot was designed for communications and it is likely to be where the new language will find its biggest advantages over current systems. Using Argot objects and data structures can be transfered between peers with ease. Communications will be in effect written into the core of the language.
I suspect this would take me a couple of years to develop alone. There are many issues that will arise along the way. However, I think the goal is a realistic and smart one. The tower of computer babel we have created needs to be replaced with something new and well thought out. Argot offers a underlying key concept in achieving this.
Nearly another week, and another step closer to having Argot out in the wild. It turns out that converting the network resolution code to C was a little more painful that I would have liked. Finally, I'm pleased to say that the first cut is done. Argot is ready to be sent out the door.. well.. nearly!
The last step in getting Argot out the door is to find an appropriate license. A full OSI approved license is not going to provide the right mix of freedom and protection which is ashame. Now that the OVPL is not considered open source its time to rethink the best way to allow open source to take advantage of Argot, yet still allow the business to grow and develop the software.
Surprisingly there really isn't much out there the provides a precedence for this type of license. The GhostScript AFPL and Java Research License touch on some of the required aspects.
Much like Java where controlling compatibility is important, Argot needs to develop but ensure commercial applications stay compatible. The Java Research License provides these elements. But to be compatible with open source we would like to allow Argot to be embedded in any open source software. It is this element that is difficult to find in a license.
Some more research to do. It will be absolutely fantastic to finally have Argot out the door. Very nearly there...
It has taken the Open Source Initiative(OSI) eight months to come to the conclusion that the OVPL and OVLPL do not comply with the Open Source Definition(OSD), and therefor will not be approved for use by the OSI. This has been a long and frustrating battle, however, I'm glad there is now some resolution. My response to the OSI had a touch of annoyance about it. I also posed a few questions to the OSI regarding their stance on future licenses to ensure everyone understands their new 'line in the sand'(the request and response is not yet archived online). If nothing else I can say that I helped shape the future of how the OSI interpret and enforce the OSD.
The result of this is that it is time to rethink what license is required for Argot. My initial feeling is that it is unlikely to be an OSI approved license. This gives more freedom in taloring the license to best fit Argot and users needs. The downside is that Argot doesn't get the OSI logo on it; c'est la vie.
The final nail in the coffin of OVPL is not quite finalised. We may look at using a BSD license back for contributions. However it will need some discussion to decide how this will effect the license.
In Argot news, the Argot Network Resolution code has been added to the Java and C# versions of Argot. It has been added in a way that abstracts the functionality away from any transport. It requires that the developer provide the transport mechanism as part of their peer to peer or client server protocol. That finishes up the functionality for those versions.
Only a few more things to do before release. Sort out this license issue and port the Argot Network Resolution code to C. Easy!
Phew! After a day of turning my brain into mush I have the C version of Argot finished to the same level as Java and C#. The missing functionality was providing Argot Message Format readers and writers. This also happens to be one of the more complex and brain twisting elements of Argot. It's always nice to press the commit button and know that it is done.
The other thing I've added to the C version is CPPUNIT testing. Argot now has unit testing libraries for each version; JUnit for Java, NUnit for C# and CPPUNIT for C/C++. These testing frameworks are a real life saver when it comes to making sure functionality is the same for each version. I hope my XP friends are happy that their methods are rubbing off.
The documentation is done. The functionality or C, Java and C# is done. There's only a couple of things missing required before release. The first one is the approval from the OSI for the Open Vendor License. The second thing missing is adding the Argot Network Resolution(ANR) protocol into the Argot library.
The Open Vendor License is still up before the OSI board. They will be meeting next week to finally decide its fate. It still isn't clear which way they will go. If they decide in the negative it's going to be fun to work out the best way to release Argot. It might be back to the license drawing board.
The Argot Network Resolution protocol provides the data type matching facilities when Argot is used in client/server or peer to peer communications. Currently it forms the low level aspect of Colonly. However, its functionality is probably more closely aligned with Argot than Colony. Thankfully there isn't too much code to it as Argot already does most of the work. It might even be ready for when the OSI make their decision.
In the last two weeks I've been concentrating on slowly bringing together a programmer's guide for Argot. It's now 34 pages and should provide a reasonable introduction to getting started with Argot. I'm sure it will grow over time.
I've also prepared the Java version of Argot to be inline with the C and .Net verisons. I use Java for testing out new changes so it had ended up with a few loose ends. It was nice to go back and tidy it up.
The next thing on the agenda is to find out what's happenning with the OVPL and OVLPL. These licenses will have been infront of the OSI board for five months on friday. The most frustrating thing is that the OSI board have made no clear indications of if they will approve or reject the licenses. Rejecting them will have to spur changes to the Open Source Definition as they clearly comply.
Another week and another language. I had hoped Argot wouldn't take too long to port to C#. Well, with a little help from the Microsoft's Java to C# conversion utility it's all done in three working days. Actually it took three days of massaging the code from the output of the conversion utility. It didn't do a bad job, however, I wouldn't want to use it for any larger project.
I was expecting it would take a little longer to fix the code. Thankfully C# is close enough to Java that it didn't take long to fix up the changes. A few things surprised me about C#. The biggest one was the lack of a byte[] compare method. It's always the small things that bite when changinge languages. Searches on google showed it was a rather common query. It didn't take long to handle that one. Most of my time was spent either changing signed to unsigned data types. I never did like Java's ban on unsigned types. The other painful task was capitalising all the first letters of method names. It's something the Java conversion assistant probably should do! I was also a bit disapointed by the result of GetHashCode() on basic integer types. The result is the same as the value. It isn't hashed at all. This didn't take long to work around either. Overall I think the C# version will not look too much like converted java to the C# officianados.
I now have Argot in Java, C and C#! The only bit missing is documentation. This next task won't be my favourite, but documentation can make or break a project. So time to document!
I've managed to shrink my RPC server to 7kb! My last test case used a Java client to Java server using the full Argot/Colony software library. This test case uses the exact same Java client connected to a hand coded C server over TCP/IP. The server uses a static type map which defines the full set of data types, interfaces and objects on the server.
The original aim of this exercise was to target a ATMEL ATMEGA8 microprocessor with 8kb of memory. Compiling the same C code targeted to the ATMEL AVR produced a 3kb binary! This provides a single function on a single interface. I suspect with a normal set of functionality this would creep up to 5kb. However, even this still leaves plenty of room for actual functionality to be included in the processor.
This now shows that Argot/Colony combination can create a strongly bound data contract between client and server on even the smallest of devices. This includes both data and interfaces. This is the exact same protocol and software used in full size service oriented architecture(SOA) solutions using Argot/Colony.
All the C skeleton code was hand coded in this test. In time I will create an IDL to Dictionary converter and then a Dictionary to C skeleton code generator which will speed development time. The only part not hand coded was the static type map; this was generated with the interface dictionaries.
It looks like this excersize of seeing how small Argot can go is a great success. I will have to wait and see if I can get some interest to actually create a light switch and light hardware to show Argot/Colony being used to turn on a light!
For now it's time to jump languages and move back to C#. Having done Argot in Java and C, I figure it would be nice to also include a C# version. This will provide good coverage of the most popular languages for Argot. The C# version was started last year. Hopefully it won't take too long to complete.
In other news, the Open Vendor Public License continues to be slow progress. If you ever have the thought that it would be really useful to have another open source license in the world. Be prepared! The OVPL has taken nearly ten months so far. We shall see how much longer it will take!
About three weeks since I started investigating Objects and Interfaces. I've just managed to call a remote method. object.doSomething(22); returns the value 66. Remote procedure call(RPC) techniques like this remind me of a conversation I had last week with a friend. We were discussing the fact that I'm currently putting a lot of effort into developing a light switch which if I'm lucky could possibly turn on a light. Fifteen years of computer science training and experience culminating in the ability to flick a switch and turn on a light! Thankfully, the underlying techniques have a much broader application than a single switch.
This is the second iteration of the underlying RPC mechanism. The previous version relied on matching data types dynamically with methods on the server. This version creates an IDL style description of the methods which are then bound to the implementation interfaces. This allows the client and server to check the signature before making a call. If the client signature differs from the servers, the client can fail safely. I'm continually impressed with how the strong data contract between client and server allows me to quickly debug the communication aspects of the system.
Now the Java implementation is working I can move back to C and see how small I can build a service.
I've been meaning to put up a photo of the offices latest painting for a couple of weeks now. It's called "4bit Argot" and is my version of a self describing painting. It has turned out to be a nice way to give a visual view of what Argot is all about. The painting is a binary view of all the information required to describe the information on the painting. Still confused? Maybe the meta description will help.
Each definition following has been encoded onto the painting using only descriptions included:
- definition( 0 "u4" , basic( 4, 0 ) );
- definition( 1 "basic" , sequence([ reference( #u4 ), reference( #u4 )]));
- definition( 2 "abstract", sequence([]));
- definition( 3 "expression", abstract() );
- definition( 4 "sequence", array( reference( #u4 ), reference( #expression ) ) );
- definition( 5 "reference", sequence( [ reference( #u4 ) ] );
- definition( 6 "array", sequence( [ reference( #expression ), reference( #expression ) ] ) );
- definition( 7 "expr#ref", map( #expression, #reference ) );
- definition( 8 "expr#seq", map( #expression, #sequence ) );
- definition( 9 "expr#ary", map( #expression, #array ) ) );
- definition( 10 "map", sequence([ reference( #u4 ), reference( #u4 )]));
- definiiton( 11 "expr#map", map( #expression, #map ) );
- definition( 12 "expr#abstract", map( #expression, #abstract ) );
- definition( 13 "definition", sequence([reference( #u4 ), reference( #expression )]));
- definition( 14 "expr#basic", map( #expression, #basic ) );
- definition( 15 "dictionary", array( reference( #u4 ), reference( #definition )));
The painting contains a dictionary definition. white is 1, black is 0. Can you decode the painting using the definitions above? There could be a bit or two wrong, let me know if you can find any errors. :)
The painting has some similar attributes and problems to what I've been working on the last week. The challenge has been to see how small Argot can go. The aim is to embed Argot in devices like light switches. As I mentioned last week, the target is 8kb AVR microprocessors. I was a little surprised at how easy it was. The data marshalling code finished up at 1kb and the Argot description at around 3kb. This was much smaller than I expected and leaves 4kb in an 8kb processor for functionality.
The aim of the light switch exercise was to allow a new device to be entered into a home network and have the device contain a description of all of its functionality. The home network controller is then able to configure itself appropriately to communicate with that device. Doing the excerise reminded me that I wanted/needed to put Interfaces and Object descriptions into Argot.
The focus this week is now Interfaces and Objects. After that is done I can have another go at creating a working prototype for the light switch.
After two weeks of intense development the first cut of Argot for C is done. I've ended up with a head cold and feel terrible, but atleast Argot is basically done. The first cut is complete when Argot can read in a dictionary file of definitions of other elements. This is not only an essential feature, it also tests about 90% of the Argot software in one hit. This is all thanks to the self referencing nature of Argot and Dictionary files. My original aim for Argot was for the library to be less than 50Kb. I'm incredibly chuffed that my final test executable ended up at 32Kb!
One of the interesting things about writing Argot in C is seeing all the improvements I can make to the Java version. It's difficult not to jump straight back into the Java version and making it better, however, for now there's better things to do. I also promised myself to setup a build machine that will ensure all the different language versions of Argot continue to work together.
There are two other versions of Argot I'd like to have complete. The C# and Micro edition. Working with the C version I've had some great ideas for the Micro edition. Today I'll be loaning a development kit for some 8kb and 16kb processors. It's going to be a tight squeeze making them Argot enabled, but I think it's doable!
The C# version is going to involve re-porting the java version again with the assitance of the Microsoft Java to C# porting tool. With that done I'll have my four core languages complete: java, c, c# and micro.
Aside from the development I've been talking to people about Argot and getting feedback. Having to explain in details of the meta dictionary to other people has given me a better understanding. It has also helped me see some small things to tweak and improve in the meta dictionary.
So much to do! Argot Micro, Argot C#, Build Machine, Meta Dictionary improvements across all versions. That should keep me busy for the next month.
Now that I have a blog, I suppose I should keep it up to date. After finishing the web sites last week, I put two papers online the Einet web site. The Argot White Paper provides some high level information on Argot as well as some low level technical aspects of Argot. The other new paper is the "Creating Evolvable Programming Languages", which demonstrates how Argot can be used to encode languages. This is opposed to the traditional method of encoding languages using text and syntax. Both are available in the Articles section of Einet.
With the web sites up to date, I've moved back to working on the C/C++ version of Argot. The C++ version of Argot was written early last year. However I discovered that C++ exceptions, RTTI, STL templates and virtual functions caused a lot of bloat. This time around I've decided to turn as much as I can into C.
After working with Java for a while, it's actually a refreshing change to write code in C. I've got all the fun of playing with function pointers, structures, unions and memory management. This refactoring will probably lead to changes that can be put back into the Java version. It's very interesting to see the same program in the light of a different programming language.
One of the disadvantages of working in C over Java is that you need to build your own abstract functions, like stacks and queues. This it turns out to be an advantage because unlike Java, these can be tailored specifically for the application. A simple case of this was developing a small integer to integer hash map(intmap). I was able to create a fast integer hash map in 1.5KB. This intmap will be heavily used in Argot, so making it small and fast will pay of well.
In other news the Open Vendor Public License (OVPL) continues to be discussed on the OSI license-discuss mailing list. There's plenty more that could be said on this; maybe a topic for the next post!
Finally, the new web site is now online. This completes the process of getting my various projects up to the same level of software. www.livemedia.com.au, ps2dev.org, www.einet.com.au and openvendor.org are all using lime site(name subject to change) software. From now it should be easier to manage upgrades as I add features and fix bugs.
This web site is also the first to be fully designed with CSS. Overtime I'll redo the other sites using CSS. I'm especially looking forward to updating ps2dev.org with CSS. It's in desperate need of a facelift. Maybe with it CSS enabled, I can encourage one of the members with some graphic abilities to have a go (hint hint).
There is still plenty to add to the software. Over the next few entries I'll hopefully explore some of the items that need to be completed.
Here's my first entry. The site isn't even live yet, however after nearly two years of having a very basic web site online it is time to refresh the site. Live Media will continue to be my home base as I continue work on my various projects. Hopefully this blog will both let other people know what changes I'm making and planning to various sites and software I manage through Live Media.