Argot Versioning - Part 3 - Remote Type Negotiation

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.
  

Having two solutions only solves part of the problem. There are a few scenarios which should be catered for:

• 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(“u8”));
  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.

Argot Versioning - Part 2 - Meta Data Naming

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.

Argot Versioning - Part 1 - Meta Data Type Versioning

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.