IDL: Encodings, Mappings, and Backward Compatibility

posted February 15, 2016 by "No Bugs" Hare, translated by Sergey Ignatchenko

	Author:	“No Bugs” Hare Follow:
	Job Title:	Sarcastic Architect
	Hobbies:	Thinking Aloud, Arguing with Managers, Annoying HRs, Calling a Spade a Spade, Keeping Tongue in Cheek

[rabbit_ddmog vol=”1″ chap=”Chapter 3(d) from “beta” Volume I”]

As we’ve discussed those high-level protocols we need, I mentioned Interface Definition Language (IDL) quite a few times. Now it is time to take a closer look at it.

Motivation for having IDL is simple. While manual marshalling is possible, it is a damn error-prone (you need to keep it in sync at least at two different places – to marshal and to unmarshal), not to mention too inconvenient and too limiting for further optimizations. In fact, the benefits of IDL for communication were realized at least 30 years ago, which has lead to development of ASN.1 in 1984 (and in 1993 – to DCE RPC).

“However, for most game and game-like communications I still prefer to have my own IDL.These days in game engines, quite often a (kinda) IDL is a part of the language/engine itself; examples include [RPC]/[Command]/[SyncVar] tags in Unity 5, or UFUNCTION(Server)/UFUNCTION(Client) declarations in Unreal Engine 4. However, for most game and game-like communications I still prefer to have my own IDL. The reason for it is two-fold: first, standalone IDL is inherently better suited for cross-language use, and second, none of in-language IDLs I know are flexible enough to provide reasonably efficient compression for games; in particular, per-field Encodings specifications described below are not possible¹

¹ and even if Encodings (along the lines described below) are implemented as a part of your programming language, they would make it way too cumbersome to read and maintain

IDL Development Flow

With a standalone IDL (i.e. IDL which is not a part of your programming language), development flow (almost?) universally goes as follows:

you write your interface specification in your IDL
- IDL does NOT contain any implementation, just function/structure declarations
you compile this IDL (using IDL compiler) into stub functions/structures in your programming language (or languages)
for callee – you implement callee-side stub functions in your programming language
for caller – you call the caller-side stub functions (again in your programming language). Note that programming language for the caller may differ from the programming language for callee

One important rule to remember when using IDLs is that

Never Ever make manual modifications to the code generated by IDL compiler.

“Modifying generated code usually qualifies as a Really Bad IdeaModifying generated code will prevent you from modifying the IDL itself (ouch), and usually qualifies as a Really Bad Idea. If you feel such a need to modify your generated code, it means one of two things. Either your IDL declarations are not as you want them (then you should modify your IDL and re-compile it), or your IDL compiler doesn’t do what you want (then you need to modify your IDL compiler).

Developing your own IDL compiler

Usually I prefer to develop my own IDL compiler. From my experience, costs of such development (which are of the order of several man-weeks provided that you’re not trying to be overly generic) are more than covered with additional flexibility (and ability to change things when you need ) it brings to the project.

With your own IDL compiler:

whenever you feel the need to change marshalling to a more efficient one (without any changes to the caller/callee code) – no problem, you can do it
whenever you need to introduce an IDL attribute to say that this specific parameter (or struct member) should be compressed in a different manner² (again, without any changes to the code) – no problem, you can add it
whenever you want to add support for another programming language – no problem, you can do it
you can easily have ways to specify the technique to extend interfaces (so that extended interfaces stay 100% backwards-compatible with existing calls/callees), and to have you IDL compiler check whether your two versions of the IDL guarantee that the extended interface is 100% backwards-compatible. While techniques to keep backward compatibility are known for some of the IDLs out there (in particular, for ASN.1 and for Google Protocol Buffers), the feature of comparing two versions of IDL for compatibility, is missing from almost all the IDL compilers I know; one exception is Google flatc which seems to provide this functionality via recently added “-conform” flag. [[IF YOU KNOW ANOTHER IDL COMPILER WHICH HAS AN OPTION TO COMPARE TWO VERSIONS OF IDL FOR BACKWARD COMPATIBILITY – PLEASE LET ME KNOW]]

Now to the queston “how to write your own IDL compiler”. Very briefly, the most obvious and straightforward way is the following:

write down declarations you need (for example, as a BNF). To start with your IDL, you usually need only two things:
- declaring structures
- declaring RPCs
- in the future, you will probably want more than that (collections being the most obvious example); on the other hand, you’ll easily see it when it comes 🙂
then, you can re-write your BNF into YACC syntax
AST In computer science, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language.— Wikipedia —then, you should be able to write the code to generate Abstract Syntax Tree (AST) within YACC/Lex (see the discussion on YACC/Lex in Chapter VI).
As soon as you have your AST, you can easily generate whatever-stubs-you-want.

² see section “Publishable State: Delivery, Updates, Interest Management, and Compression” above for discussion of different compression types

IDL + Encoding + Mapping

Now, let’s take a look at the features which we want our IDL to have. First of all, we want our IDL to specify protocol that goes over the network. Second, we want to have our IDL compiler to generate code in our programming language, so we can use those generated functions and structures in our code, with marshalling for them already generated.

When looking at existing IDLs, we’ll see that there is usually one single IDL which defines both these things. However, for a complicated distributed system such as an MMO, I suggest to have it separated into three separate files to have a clean separation of concerns, which simplifies things in the long run.

The first file is the IDL itself. This is the only file which is strictly required. Other two files (Encoding and Mapping) should be optional on per-struct-or-function basis, with IDL compiler using reasonable defaults if they’re not specified. The idea here is to specify only IDL to start working, but to have an ability to specify better-than-default encodings and mappings when/if they become necessary. We’ll see an example of it a bit later.

ASN.1 Abstract Syntax Notation One (ASN.1) is a standard and notation that describes rules and structures for representing, encoding, transmitting, and decoding data in telecommunications and computer networking.— Wikipedia —The second file (“Encoding”) is a set of additional declarations for the IDL, which allows to define Encodings (and IDL+Encodings effectively define over-the-wire protocol). In some sense, IDL itself is similar to ASN.1 language as such, and IDL encodings are similar to ASN.1 “Encoding Rules”. IDL defines what we’re going to communicate, and Encodings define how we’re going to communicate this data. On the other hand, unlike ASN.1 “Encoding Rules”, our Encodings are more flexible and allow to specify per-field encoding if necessary.

Among other things, having Encoding separate from IDL allows to have different encodings for the same IDL; this may be handy when, for example, the same structure is sent both to the client and between the servers (as optimal encodings may differ for Server-to-Client and Server-to-Server communications; the former is usually all about bandwidth, but for the latter CPU costs may play more significant role, as intra-datacenter bandwidth usually comes for free until you’re overloading the Ethernet port, which is not that easy these days).

The third file (“Mapping”) is another set of additional declarations, which define what kind of code we want to generate to use for our programming language. The thing here is that the same IDL data can be “mapped” into different data types; moreover, there is no one single “best mapping”, so it all depends on your needs at the point where you’re going to use it (we’ll see examples of it below). Changing “Mapping” does NOT change the protocol, so it can be safely changed without affecting anybody else.

In the extreme case, “Mapping” file can be a file in your target programming language.

Example: IDL

While all that theoretical discussion about IDL, Encodings, and Mappings is interesting, let’s bring it a bit down to earth.

Let’s consider a rather simple IDL example. Note that this is just an example structure in the very example IDL; syntax of your IDL may vary very significantly (and in fact, as argued in “Developing your own IDL compiler” section above, you generally SHOULD develop your own IDL compiler – that is, at least until somebody makes an effort and does a good job in this regard for you):

PUBLISHABLE_STRUCT Character {
  UINT16 character_id;
  NUMERIC[-10000,10000] x;//for our example IDL compiler, notation [a,b] means
                          //  “from a to b inclusive”
                          //our Game World has size of 20000x20000m
  NUMERIC[-10000,10000] y;
  NUMERIC[-100.,100.] z;//Z coordinate is just +- 100m
  NUMERIC[-10.,10.] vx;
  NUMERIC[-10.,10.] vy;
  NUMERIC[-10.,10.] vz;
  NUMERIC[0,360) angle;//where our Character is facing
                       //notation [a,b) means “from a inclusive to b exclusive”
  enum Animation {Standing=0,Walking=1, Running=2} anim;
  INT[0,120) animation_frame;//120 is 2 seconds of animation at 60fps
  
  SEQUENCE<Item> inventory;//Item is another PUBLISHABLE_STRUCT
                           // defined elsewhere
};

This IDL declares what we’re going to communicate – a structure with current state of our Character.³

³ yes, I remember that I’ve advised to separate inventory from frequently-updated data in “Publishable State” section, but for the purposes of this example, let’s keep them together

Example: Mapping

Now let’s see how we want to map our IDL to our programming language. Let’s note that mappings of the same IDL MAY differ for different communication parties (such as Client and Server). For example, mapping for our data above MAY look as follows for the Client:

MAPPING(“CPP”,“Client”) PUBLISHABLE_STRUCT Character {
  UINT16 character_id;//can be omitted, as default mapping
                      //  for UINT16 is UINT16
  double x;//all 'double' declarations can be omitted too
  double y;
  double z;
  double vx;
  double vy;
  double vz;
  float angle;//this is the only Encoding specification in this fragment 
              //  which makes any difference compared to defaults
              // if we want angle to be double, we can omit it too
  enum Animation {Standing=0,Walking=1, Running=2} anim;
              //can be omitted too
  UINT8 animation_frame;//can be omitted, as 
                        //  UINT8 is a default mapping for INT[0,120)

  vector<Item> inventory;//can be also omitted, 
                         //  as default mapping for SEQUENCE<Item>
                         //  is vector<Item>
};

In this case, IDL-generated C++ struct may look as follows:

struct Character {
  UINT16 character_id;
  double x;
  double y;
  double z;
  double vx;
  double vy;
  double vz;
  float angle;
  enum Animation {Standing=0,Walking=1, Running=2} anim;
  UINT8 animation_frame;
  vector<Item> inventory;

  void idl_serialize(int serialization_type,OurOutStream& os);
    //implementation is generated separately
  void idl_deserialize(int serialization_type,OurInStream& is);
    //implementation is generated separately
};

On the other hand, for our Server, we might want to have inventory implemented as a special class Inventory, optimized for fast handling of specific server-side use cases. In this case, we MAY want to define our Server Mapping as follows:

MAPPING(“CPP”,“Server”) PUBLISHABLE_STRUCT Character {
  // here we're omitting all the default mappings
  float angle;
  class MyInventory inventory;
    //class MyInventory will be used as a type for generated 
    //  Character.inventory
    //To enable serialization/deserialization, 
    //  MyInventory MUST implement the following member functions:
    // size_t idl_serialize_collection_get_size(),
    // const Item& idl_serialize_collection_get_item(size_t idx),
    // void idl_deserialize_collection_reserve_size(size_t),
    // void idl_deserialize_collection_add_item(const Item&)
};

As we see, even when we’re using the same programming language for both Client-Side and Server-Side, we MAY need different Mappings for different sides; in case of different programming languages such situations will become more frequent. One classical (though rarely occurring in practice) example is that SEQUENCE<Item> can be mapped either to vector<Item> or to list<Item>, depending on the specifics of your code; as specifics can be different on the different sides of communication – you may need to specify Mapping.

Also, as we can see, there is another case for non-default Mappings, which is related to making IDL-generated code to use custom classes (in our example – MyInventory) for generated structs (which generally helps to make our generated struct Character more easily usable).

Mapping to Existing Classes

One thing which is commonly missing from existing IDL compilers is an ability to “map” an IDL into existing classes. This can be handled in the following way:

you do have your IDL and your IDL compiler
you make your IDL compiler parse your class definition in your target language (this is going to be the most difficult part)
you do specify a correspondence between IDL fields and class fields
your IDL generates serialization/deserialization functions for your class
- generally, such functions won’t be class members, but rather will be free-standing serialization functions (within their own class if necessary), taking class as a parameter
- in languages such as C++, you’ll need to specify these serialization/deserialization functions as friends of the class (or to provide equivalent macro)

“I want YOU to read page 2!

Continued on Page 2... Further topics include IDL Encodings (including Delta Compression, rounding, etc.) and IDL Backward Compatibility

Pages: 1 2

ITHare (11)
Reddit (13)

Comments

Wanderer says

February 18, 2016 at 1:42 pm

As always, very nice and informative text! Thanks and keep up the good work! Much appreciated.

I’d like to ask about one thing. In this chapter, you are discussing IDL in a bit “detached” manner from the rest of the code.

As Mark Seemann perfectly pointed out in his blog, “Applications are Not Object-Oriented at the Boundaries”. And transport layer is one of those boundaries (just like persistence layer). That is why all IDL-related code usually operates on what’s called “bags of properties” and that’s perfectly fine.

At the same time, since the rest of the code usually follows OOP principles (unless you are John Carmack in the pre-id4 age), i.e. your actual “game objects” are not a bunch of fields and POD public structs. Instead, these are nice encapsulated objects keeping their invariants and “all that jazz”.

Therefore, my understanding of IDL and mapping was also about this “leap” between actual classes used in game logic and transport objects. Because it’s not really fun to have all this auto-generated code for marshaling if you still have to write all mappings between your “model::Character” and “dto::PublicCharacterData”.

[C++ specific part]

Also, since most of the folks over Internet came to an agreement that having “persistence-ignorant” (and in MMO case, “marshaling-ignorant”) domain model is a “good thing”, the whole thing becomes a bit of a task by itself.

For example, the only viable way I found to do it in C++ is to do something very similar to what CodeSynthesis’ ODB does. I.e. you can’t make it completely “ignorant”, but you can get away with a single injection of friend definition and do the rest with some IDL/auto-generated code (ODB folks just use your source code itself as an IDL to generate all autogen stuff).

[/C++ specific part]

One more addition, out of pure personal taste. I prefer to have de-serialization as a member function, but serialization as a free function without any dependency to the DTO struct – i.e. accepting a bunch of fields and putting them into binary form. IMHO that helps to make this model-to-dto “leap” a bit smaller with the ability to throw fields of your “domain” class directly into serializer without the need to create temporary DTO object. If course, it doesn’t work in all cases (i.e. you do need to keep previous DTO for dead reckoning and other optimizations), but it’s helpful in some cases. Especially in all RPC-like code.

Reply
- "No Bugs" Hare says
  
  February 19, 2016 at 9:43 am
  
  Yes, ability to map IDL to existing classes is one necessary thing. Actually, we’re planning to include this feature into our own IDL compiler :-).
  
  However, I don’t see much problems on this way (that is, until you’re trying to serialize non-owning pointers, and if you can parse target language to get struct definitions). I’ve added a section on it titled “Mapping to Existing Classes”, THANK YOU!
  
  In short – it pretty much follows what you wrote, with free-standing friend functions (I didn’t know of ODB specifics, but we came to the same conclusion anyway). Dealing with custom collections is a bit more tricky, but that I’ve already described with class MyInventory.
  
  Reply
  - Wanderer says
    
    February 19, 2016 at 12:24 pm
    
    On “non-owning pointers”, as far as I see, it’s a common problem for everyone doing any kind of serialization. Cause moving objects to persistent DB can actually be considered as just a specific case of serialization. Whether it’s binary over TCP, JSON in NoSQL, or an Update SQL statement, doesn’t actually matter – it’s a transformation of in-memory “object” entity into some serialized “data” form.
    
    And, from what I see in the papers by Martin Fowler and other founders of DDD approach, concepts like “Aggregates”, “Aggregate Roots”, “Repositories” etc, their main purpose is exactly this – to define the boundary of what is considered “serializable non-dividable item”.
    
    Basically, my current approach is to define some kind of mapping between “references” (i.e. non-owning pointers) and IDs, of course, assuming that I can only hold “references” to an object with identity. And for objects without identity (i.e. http://martinfowler.com/bliki/ValueObject.html), the procedure is to serialize the object as a part of containing one.
    
    In other words, this mimic the approach of C++ itself in value-member/pointer-member mechanics, which is pretty much natural (but, of course, using IDs instead of raw memory pointers 🙂 ).
    
    As of ODB, I actually came to the same conclusion before seeing it there, because there is simply no other way to hide internal details, but deliberately expose them to some specific “marshaling mechanism”. The only other way is to put the implementation of serialization into objects, but this triggers my SRP alarm and all other SOLID/tiers/layers/whatever alarms I have in my head 🙂
    
    Reply
    - "No Bugs" Hare says
      
      February 20, 2016 at 7:58 am
      
      > On “non-owning pointers”, as far as I see, it’s a common problem for everyone doing any kind of serialization.
      
      Of course; I remember discussions on these going on at least 20 years ago. OTOH, I didn’t really see realistic cases where *marshalling* of such things is really necessary (serialization being a different matter though). So for the time being I am usually successful in ignoring this problem altogether :-).
      
      > Basically, my current approach is to define some kind of mapping between “references” (i.e. non-owning pointers) and IDs, of course, assuming that I can only hold “references” to an object with identity. And for objects without identity (i.e. http://martinfowler.com/bliki/ValueObject.html), the procedure is to serialize the object as a part of containing one.
      
      Yes, this is probably the best thing to do. To implement it, I would try to experiment with using some kind of identified_pointer{T} which would hold BOTH object id AND pointer, but pointer essentially being a cache of the id. This way, serialization becomes a breeze, PLUS you’ll be able to move your objects around the heap, removing fragmentation (!), just at the cost of dropping these cached pointers (thread sync will be a headache, but is doable at least as long as you’re fine with controlled “stop the world”). Did you think about doing it this way?
      
      > As of ODB, I actually came to the same conclusion before seeing it there, because there is simply no other way to hide internal details, but deliberately expose them to some specific “marshaling mechanism”.
      
      Exactly 🙂
      
      Reply
  - Wanderer says
    
    February 19, 2016 at 12:46 pm
    
    The only drawback of such “non-owning-pointer to ID” automated transformation is the fact that receiving side will have to perform “ID to non-owning-pointer-on-instance” deserialization. So, if receiving side already has that ID in specific “Identity Map”, we are cool. But when it doesn’t, it basically triggers another RPC.
    
    That works perfectly fine when there are just one or two references. But it might fail miserably when there is an array with N references inside. Think of MyInventory item which is { “item_type”:123, “quantity”:1 } “small object” (ValueObject) with non-owning reference inside. Of course, this case is pretty much trivial, since one can simply store the map of all item_types in-memory on startup, but there are cases when such approach is not possible.
    
    I’m currently mocking up some kind of meta-tag (as a part of IDL) that can designate strategy for the reference – eager/lazy loading. Not sure how far that can get me to, but preliminary results look promising.
    
    Reply
    - "No Bugs" Hare says
      
      February 20, 2016 at 8:10 am
      
      > The only drawback of such “non-owning-pointer to ID” automated transformation is the fact that receiving side will have to perform “ID to non-owning-pointer-on-instance” deserialization. So, if receiving side already has that ID in specific “Identity Map”, we are cool. But when it doesn’t, it basically triggers another RPC.
      
      It is not *that* bad actually. First of all, if you do know what the other side has, you can include the whole thing into original call. And second, even if you don’t know it, you can request all the stuff you’re missing, in one single RPC call, bringing the whole conversation down to not-more-than-two round-trips.
      
      Reply
Wanderer says

July 15, 2016 at 9:49 am

Had to implement a simple IDL on a Windows/MSVC platform just recently, and got a couple of notes that might be helpful for Windows developers:

1. It’s not easy to get original flex/bison source code distribution to work in a Windows environment, even with cygwin/gnuwin.

For those who’d like to save their time, “Win flex-bison” can be used – https://sourceforge.net/projects/winflexbison/ . Also comes with a “custom build step” rules to incorporate lex/yacc files compilation as a Build step. There are some limitations and peculiarities:

1.1. Need to add generated lexer/parser source code manually to the project. It is required only once and, with “custom build rules”, VS will rebuild them from .y and .l on each recompile and pull updated version during compilation;

1.2. I wasn’t able to compile generated scanner/parser without warnings for x64 (initially, it was producing a lot of errors, but those can be reduced to merely “warnings”). For “Win32” target the generated scanner/parser can be compiled without warnings at all (a few manual adjustments are required in m4 prototypes). Also, one will have to define C99 using /D __STDC_VERSION__ = 199901 to avoid int types macro redefinition. Yes, this is a cheat, but it does the trick;

1.3. Versions of “Win flex-bison” differ from actual GNU flex/bison. Latest win-version v2.5.5 is actually flex of v2.5.37 and bison v3.0;

2. When AST is ready, I found it handy to generate source code using CTemplate (former Google Template) – https://github.com/OlafvdSpek/ctemplate

Again, some efforts will be needed to build it within VS. Actually, repository maintainer provides ready-to-use archive for VS2015 users in the comments in Issues section of github. The archive is here – http://xwis.net/ctemplate/ctemplate-2.3.zip

Plain Github distribution of CTemplate uses some generated code during make/install which requires m4 and Python as far as I see (usually not available on a average MSVS workstation);

Just want to drop it here as a comment in case some VS developer would like to setup lex/yacc/CTemplate environment after reading your article 🙂

PS: To sum up, it might actually be easier to setup VM with ubuntu or something and do IDL-related stuff here (since one should already have some *nix VM to do cross-platform checks). Still, it’s perfectly possible to run flex-bison-ctemplate tool-chain within Windows environment.

Reply
- Wanderer says
  
  July 15, 2016 at 10:47 am
  
  Re-reading my own comment, it seems that I didn’t express my tool-chain well enough. The basic idea is to have this pipe:
  
  IDL definitions -> (lex/yacc) -> AST -> (walk the tree) -> in-memory structures with definitions -> (CTemplate) -> generated .h/.cpp
  
  1. Although, since simple IDL is rarely needing actual “walk through AST”, one can create in-memory definitions right from the yacc(bison) by simply defining necessary yacc actions every time a new struct or field is parsed.
  
  2. This flow can generate single .h and single .cpp, running ctemplate twice with the same dictionaries. And I was able to get away with a single huge piece of source code with all stubs in my case. However, I think if one would like to have “cleaner” code and break down generated source into separate files, the following trick can be applied (haven’t tried it myself, but it should work).
  
  Add “file markers” in the single ctemplate output stream, like “#newfile filename.h” (or filename.cpp). When ctemplate output is ready, run one more “parsing” step, find all #newfile “pragmas” and drop all code after #newfile into specified destination. In that case, however, one would really need to make sure that each separate file contains proper includes to other parts of generated code. It shouldn’t be hard, because all information about dependencies is already within in-memory definition structures.
  
  To sum up, my “ideal” processing pipe would look like that:
  
  * prerequisites – idl.l (lexer), idl.y (syntax), enum_h.tpl, struct_h.tpl, struct_cpp.tpl, struct_field.tpl … etc (ctemplates with stubs for each piece of generated code)
  
  IDL definitions -> (lex/yacc) -> metadata describing structures -> (CTemplate) -> amalgam of generated code (simple line-by-line parsing) -> bunch of .h and .cpp with CMakeLists.txt (or makefile, or even something like vcproj)
  
  Reply
- "No Bugs" Hare says
  
  July 15, 2016 at 11:40 am
  
  Strange, as I didn’t really had much problems with setting it up. IIRC, last time I was using GNUWin32’s http://gnuwin32.sourceforge.net/packages/bison.htm (and also flex from them) – and the only problem I was facing, was an extra *nix header in generated code (which can be easily commented out via GnuWin32 sed or something). That was pretty much it; then I’ve made good ol’ batch file to compile the whole thing from .y / .l into .c (avoiding any issues “how to integrate it into VS”). After running .bat and having those .c files – I simply compiled them in VS (no integration needed – they’re just .c files after all). That was pretty much it – and I don’t have any info that this (IMO very straightforward) way doesn’t work now…
  
  Reply
Matthew Horsley says

January 18, 2017 at 3:13 pm

Google’s flatc compiler has a -conform flag to check if a new schema is a valid evolution of an old one.

–conform FILE : Specify a schema the following schemas should be an evolution of. Gives errors if not. Useful to check if schema modifications don’t break schema evolution rules.

Reply
- "No Bugs" Hare says
  
  January 19, 2017 at 7:42 am
  
  THANKS, added a sentence about it.
  
  Reply