Subject: [mmox] My evaluation of LLSD+LLIDL

From: "Hurliman, John" <[email-masked]>
Date: Fri, 20 Feb 2009 19:20:34 -0700

I have a partial, very early implementation of a C# LLIDL lexer/parser and code generator in SVN at http://openmv.org/svn/misc/LLIDL/ (under the BSD license) in addition to the C# implementation of LLSD that has been under active development for about a year. This is my evaluation of the combined LLSD+LLIDL system in comparison to other similar offerings. Please add comments, corrections, and general feedback.

Linden Lab Structured Data by itself provides an abstract type system. This defines a fixed number of data types: null, boolean, signed 32-bit integer, 64-bit floating point, string, 128-bit UUID, timestamp, URI, binary data, array, and map. Arrays and maps are weakly typed allowing them to store any LLSD data type. Type-casting mechanics are defined, creating a complete, weakly typed system. Implementation involves a layer to handle the weak typing (straightforward in Python, usually a class for each type inheriting from a base class in OO languages) and a layer to handle the conversions to and from native language types.

LLSD by itself is not very interesting; each individual programming language already had its own way of handling data and has no need for a new abstract type system. The idea is that if all languages shared a common type system, one or more serializations can be defined that allows the types to travel language and network boundaries. The approach used in other systems (ASN.1, Google Protocol Buffers, Apache Thrift, etc.) is to clearly define the data types at the serialization level instead of at the LLSD<->native level. My opinion is that this is an implementation detail that does not affect the developer using library in any meaningful way.

Where LLSD gets interesting is the addition of LLIDL. The interface description language for LLSD defines a text format for defining messages, similar to what you find in ASN.1, Protobufs, Thrift, and every other IDL. The text is very easy to parse (here's my ANTLR grammar file to convert LLIDL files to an AST: http://openmv.org/svn/misc/LLIDL/LLIDL.g, compare this to the ANTLR grammar for ASN.1: http://www.antlr.org/grammar/1231433381400/ASN.g). What you do with the LLIDL is an open question. You can make a simple parser that validates LLSD against an LLIDL definition, but that doesn't add value beyond being a good debugging tool. You can make a converter for incoming LLSD to conform to an LLIDL definition, but this has questionable value. Section 2.1 of the LLSD draft already states that reading the values will either "just work", or default values will be filled in for missing parameters. The only thing LLIDL can offer in addition to this is a warning of whether or not there were missing or extra fields. Additionally, this forces you to work with weakly typed data where you want to have strict type enforcement. The code generated by ASN.1, Protobufs, Thrift, etc. doubles as a compiler-enforced contract. Consider the following example:

Thrift:

struct UserProfile {
  1: i32 uid,
  2: string name
}

This might generate psuedocode code like this:

public struct UserProfile {
  int uid;
  string name;
  public void Serialize(Stream outputStream) { ... }
}

LLSD/LLIDL:

&UserProfile = {
  uid : int,
  name : string
}

This generates:

LLSDMap UserProfile;

With keys "uid" and "name" that hold the types int and string, respectively. When writing code with the first example, you know exactly what data types the enclosing type is composed of, what the types of each format are, and any default/fixed values. Working with the LLSD/LLIDL system, your only reference is to open up the LLIDL text file and look at it. This is roughly equivalent to a well formatted README file.

The solution? Implement a strongly typed generator on top of LLSD/LLIDL. This is what my llidlgen program attempts to do. For very basic examples of LLIDL (such as the example above) this seems like a straightforward thing to do. However, because of the baked in assumption that no one would attempt to do this, there are several problems. The outputted code is full of generator-named types and variables, lots of special handling has to be added to prevent the output from turning into layer after layer of nested classes, there are situations such as nested maps ({ $ : { $ : int } }) that drastically increase the complexity of converting LLSD types to native types, and the fact that this happens to be using an abstract type system starts to feel like a trivial design decision that is eventually hidden away from the developer.

Summary:

* There is no clear benefit to standardizing on conversions at the abstract type level instead of the serialization level. Doing so removes the ability to enforce data contracts at compile time

* The only published code for LLIDL is a broken C# generator. ASN.1, Protobufs, and Thrift all have proven implementations across a wide variety of languages

* The binary serialization format for LLSD is objectively less efficient than the Protobuf serialization format. With real-world data, the gap likely widens (haven't compared with Thrift or ASN.1). LLSD and Thrift support JSON "out of the box", Protobufs is flexible enough to support it but does not ship with JSON support. I haven't seen anything that would suggest ASN.1 could be transported over JSON. Only LLSD and ASN.1 (XER) support XML

* LLSD+LLIDL gives you the choice between guessing and checking what parameters need to be serialized for a particular message (no compiler-enforced structure), or writing a strongly typed generator so complex it makes ASN.1 look easy. Generator-named types and variables (in a strongly typed output) move the system further away from comprehensible data contracts

This evaluation was based on the LLSD/LLIDL draft at http://www.ietf.org/internet-drafts/draft-hamrick-llsd-00.txt. If I overlooked something in the draft or misunderstood the intended use please provide corrections.

John

---

From: Jon Watte <[email-masked]>
Date: Sat, 21 Feb 2009 00:05:28 -0800

Hurliman, John wrote:
> Linden Lab Structured Data by itself provides an abstract type system. This defines a fixed 

As does XDR, by the way. XDR is well understood, very widespread, and 
has been in use (including some very common Internet protocols) for the 
last 20 years. XDR is also an accepted IETF RFC. Others have pointed out 
other existing data serialization/encoding standards that already exist 
and are standardized. However, I think all that is beside the point.

Honestly, I really do think we should start with the overall basics of 
agreeing on requirements, then agreeing on a model of interoperability, 
before we even start thinking about adopting, adapting, or introducing 
things like data format specifications. I think the discussion of LLSD 
on this list is, at best, premature, and at worst, adds noise at this 
juncture.

Sincerely,

jw

---

From: Morgaine <[email-masked]>
Date: Sat, 21 Feb 2009 09:24:18 +0000

On Sat, Feb 21, 2009 at 8:05 AM, Jon Watte <[email-masked]> wrote:

> things like data format specifications. I think the discussion of LLSD on
> this list is, at best, premature, and at worst, adds noise at this juncture.
>
> I don't see why this should be so.  The two activities are highly
independent, and so work on them can proceed concurrently.

In general, I would tend to take the opposite approach to yours, and define
my foundations before trying to build more complex structures.  It's the
usual bottom-up approach in engineering.

The only time when defining the datatypes first isn't sensible nor feasible
is when the datatypes are not yet known, but that is not the case here.  We
all have experience of one virtual world or several, and therefore we know
the datatypes needed for interop:  it is the superset of all the ones we use
or imagine we might use, which is a rather small set of primitive types plus
some composite construction material.  It's rather simple.

Admittedly LLSD is too narrow, but that's why we'll be extending it to suit
worlds beyond LL's.  (*Proviso: unless someone proposes an equally flexible
alternative.)*

Morgaine.

---

From: "Meadhbh Hamrick (Infinity)" <[email-masked]>
Date: Sat, 21 Feb 2009 02:07:51 -0800

xdr is a presentation layer construction, not an abstract type system.  
for instance, it provides no guidance for conversion between basic  
abstract types.

the role of LLSD in OGP is two fold:

1. to provide a mechanism for reasoning about the semantics of fields  
in protocol messages (which is why we have URI, UUID and Date type as  
distinct from type String)
2. to (un)marshall protocol messages into one of a number  
serialization formats.

the selection of XML and JSON as two of the serialization formats in  
the LLSD draft is not a mistake. there is a well developed ecosystem  
of tools for the manipulation of XML data and streams. we also see a  
future that integrates the virtual world with the web; JSON is far  
easier to consume in AJAXish applications than XDR.

that being said... an XDR serialization of LLSD is certainly possible,

On Feb 21, 2009, at 12:05 AM, Jon Watte wrote:

> As does XDR, by the way. XDR is well understood, very widespread,  
> and has been in use (including some very common Internet protocols)  
> for the last 20 years. XDR is also an accepted IETF RFC. Others have  
> pointed out other existing data serialization/encoding standards  
> that already exist and are standardized. However, I think all that  
> is beside the point.
>
> Honestly, I really do think we should start with the overall basics  
> of agreeing on requirements, then agreeing on a model of  
> interoperability, before we even start thinking about adopting,  
> adapting, or introducing things like data format specifications. I  
> think the discussion of LLSD on this list is, at best, premature,  
> and at worst, adds noise at this juncture.
>
> Sincerely,
>
> jw
>
> _______________________________________________
> mmox mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mmox

---

From: Morgaine <[email-masked]>
Date: Sat, 21 Feb 2009 13:48:50 +0000

On Sat, Feb 21, 2009 at 2:20 AM, Hurliman, John <[email-masked]>wrote:

>
> * There is no clear benefit to standardizing on conversions at the abstract
> type level instead of the serialization level. Doing so removes the ability
> to enforce data contracts at compile time
>

That's true of LLSD because of the ambiguities that result from its
unhelpfully small set of types which denies effective 1:1 mapping between
programs and on-the-wire representations (and possibly other reasons too).
I think you would find a lot of aggreement that LLSD as it stands is not
adequate, but we never expected it to be --- it's an SL standard, after
all.  The problem can be fixed by modifying LLSD to meet our broader
requirements, or replacing it if deemed appropriate.

On the question of the benefit of standardizing on conversions at the
abstract type level instead of the serialization level, there are three
absolutely key benefits:

   1. Independence of programs from the on-the-wire format;
   2. Ability to switch the wire format dynamically and to support multiple
   formats simultaneously on different channels from the same code base;  and
   3. Ability to use interface generation/validation tools and to write
   marshalling systems that are independent of the wire format.

These are highly tangible benefits that promote broad acceptance of a
protocol standard simply by being all-embracing at the on-the-wire level.
But it goes much further than that, because of the strong engineering
benefits that come from better toolset longevity and from allowing the wire
formats to evolve and improve without impacting the code base.

Multiple serializations is a benefit that should not be lost, and
consequently we need some way of programming to an abstract interface.

I am not wedded to LLSD though.  Given an alternative that provides these
same benefits and is also better in some area, I would happily support it.

Morgaine.

---

From: Jon Watte <[email-masked]>
Date: Sat, 21 Feb 2009 10:58:02 -0800

Morgaine wrote:
> In general, I would tend to take the opposite approach to yours, and 
> define my foundations before trying to build more complex structures.  
> It's the usual bottom-up approach in engineering.
>

In engineering, you usually have the requirements before you start 
building. After all, if you start building a house, the way you've 
always built houses, and half-way through, you realize that the house is 
for Giraffes, then don't you feel foolish?

> Admittedly LLSD is too narrow, but that's why we'll be extending it to 
> suit worlds beyond LL's.  (/Proviso: unless someone proposes an 
> equally flexible alternative.)/

Google Protocol Buffers have been suggested by multiple people. That 
uses a compiled schema, though.

Sincerely,

jw

---

From: Morgaine <[email-masked]>
Date: Sat, 21 Feb 2009 21:32:51 +0000

On Sat, Feb 21, 2009 at 6:58 PM, Jon Watte <[email-masked]> wrote:

> building. After all, if you start building a house, the way you've always
> built houses, and half-way through, you realize that the house is for
> Giraffes, then don't you feel foolish?
>

Nope, I don't feel foolish because they're both made of bricks. ;-)

And that's not a joke, because in the paragraph that you didn't quote, I had
written:

 "*We all have experience of one virtual world or several, and therefore we
know the datatypes needed for interop:  it is the superset of all the ones
we use or imagine we might use, which is a rather small set of primitive
types plus some composite construction material.*"

So we already know what bricks we need, although we might think ahead a bit
and add a few more likely candidates just for future proofing.

It's the higher level requirements that we won't know until we start
examining multiple virtual worlds in detail.  While we don't know now what
the payloads will be, we certainly know in what serializable form the
payloads will be represented from cumulative experience within the group.

Morgaine.

---

From: Jon Watte <[email-masked]>
Date: Sat, 21 Feb 2009 14:56:39 -0800

Charles Krinke wrote:
> Well, we already have interop with both OGP and HyperGrid between 
> multiple projects, companies and grids, so at this point the question 
> is how to seek consensus with other virtual worlds.
>
> As I have said before, the architecture exists, OGP exists, HyperGrid 
> exists. Folks are using them, folks are extending them. Folks are 
> moving forward.
>
> Our only hope is to add some personality into the mix as the train 
> gathers speed. It already appears to have left the station.

With that kind of thinking, the train left the station when IEEE 1278 
was ratified.

There are a number of problems with OGP, which I have enumerated, when 
it comes to the architecture of "generic" virtual worlds, in the broad. 
The fact that a few worlds that use the SL architecture can talk 
together using the current OGP (is there a newer document than version 
5?) does not mean that that protocol is, in itself, technology agnostic, 
or even suitable for a wider interoperability standard.

In the end, everyone will have to write code to implement whatever 
standard comes out, I don't think we can avoid that.

Sincerely,

jw