Subject: [mmox] XML serialization

From: Catherine Pfeffer <[email-masked]>
Date: Mon, 23 Feb 2009 11:39:07 +0100

Jon Watte wrote:
> > Meadhbh Hamrick (Infinity) wrote:
> > <llsd>
> >   <map>
> >     <key>success</key>
> >     <boolean>true</boolean>
> >     <key>something_i_like_to_eat_on_sundays</key>
> >     <string>bananas</string>
> >   </map>
> > </llsd>
>
> IMO, that's a terrible serialization, because it depends on ordering.
> While XML is ordered, this particular serialization makes it hard to
> write XPath that selects "the string that comes after key success but
> before key something_i_like_to_eat_on_sundays".

Yes, I have already made this very same remark to Infinity in private.

The "classical way" to solve this is to add new wrapper tags:

<llsd>
   <map>
      <entry>
        <key>success</key>
        <boolean>true</boolean>
      </entry>
      <entry>
        <key>something_i_like_to_eat_on_sundays</key>
        <string>bananas</string>
       </entry>
   </map>
</llsd>

but that would make the "angle bracket tax" even more expensive to pay...

It's not *that* complicated in XPath (following-sibling axis is made for
that). But it's just... well... unusual practice in the XML world.

I have the strong feeling that depending on the order is calling for
trouble, although I have not found yet examples where it would lead to real
problems, other than ugly XPath constructions or unusual DTD fragments.

-- 
Cathy

---

From: Jon Watte <[email-masked]>
Date: Mon, 23 Feb 2009 12:56:26 -0800

>         <key>something_i_like_to_eat_on_sundays</key>

A better way is

<map>
  <value type="boolean" key="success>true</value>
  <value type="string" 
key="something_i_like_to_eat_on_sundays">bananas</value>
</map>

natural way to express it.This has less of the angle bracket tax, and it 
has a VERY straight-forward parsing style. In fact, in my opinion it's 
the most In XPath, it's now trivial: "value[@key=success]"

I'm working on a list of the things I think are wrong with the current 
proposal, of which this is one thing (there are about six). If we're 
open to change on those things (including this), then I could get behind 
the LLSD. Stay tuned :-)

Sincerely,

jw

---

From: "Hurliman, John" <[email-masked]>
Date: Mon, 23 Feb 2009 14:19:00 -0700

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On Behalf Of
>Jon Watte
>Sent: Monday, February 23, 2009 12:56 PM
>To: Catherine Pfeffer
>Cc: [email-masked]
>Subject: Re: [mmox] XML serialization
>
>Catherine Pfeffer wrote:
>> <llsd>
>>    <map>
>>       <entry>
>>         <key>success</key>
>>         <boolean>true</boolean>
>>       </entry>
>>       <entry>

Once you post your LLSD comments I can add them to the LLSD evaluation page at http://www.openmetaversetech.org/node/13 (this site is currently under heavy construction, but will become an open wiki soon).

John

---

From: "Meadhbh Hamrick (Infinity)" <[email-masked]>
Date: Mon, 23 Feb 2009 13:46:58 -0800

Catherine... Jon...

can you create a proposal for a next generation XML serialization?

the existing serialization is in current use by SL, OpenSim and PyOGP,  
so there's probably going to be a lot of resistance to changing  
something that currently works and is deployed.

keep in mind, however, that OGP does not use XML to represent it's  
PDUs, it uses LLSD. XML is one of three defined serializations of  
LLSD. it's a subtle difference, but important.

for instance... is there a benefit to explicitly adding support for  
namespaces to the XML serialization? there was a bit of discussion  
about this amongst some AWG members, and the consensus was... "why  
bother? the XML (presentation layer) is not the place where you want  
to extend the PDU... you want to extend it in the LLSD / LLIDL  
definition of the interaction."

but, i still think it's an interesting idea as it might allow systems  
that use XML serialization exclusively to extend display and  
distribution options of various PDUs.

-cheers
-m

On Feb 23, 2009, at 12:56 PM, Jon Watte wrote:

> natural way to express it.This has less of the angle bracket tax,  
> and it has a VERY straight-forward parsing style. In fact, in my  
> opinion it's the most In XPath, it's now trivial:  
> "value[@key=success]"
>
>
> I'm working on a list of the things I think are wrong with the  
> current proposal, of which this is one thing (there are about six).  
> If we're open to change on those things (including this), then I  
> could get behind the LLSD. Stay tuned :-)
>
> Sincerely,
>
> jw
>
> _______________________________________________
> mmox mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mmox

---

From: "Hurliman, John" <[email-masked]>
Date: Mon, 23 Feb 2009 15:18:22 -0700

Speaking as the maintainer of OpenSim's LLSD<->XML serialization library (OpenMetaverse.StructuredData) I can say there would be zero resistance from me in adopting a better serialization. In fact, I would greet the changes with open arms, as would most people in the open source virtual world sphere. Please do not put any of the OpenSim/OpenMetaverse efforts in the same sentence when claiming that improvements will be met with resistance. If there is going to be a significant amount of resistance to anything that improves on deployed and working Second Life technology, then I don't think this will get very far.

John

>Meadhbh Hamrick (Infinity)
>Sent: Monday, February 23, 2009 1:47 PM
>To: Jon Watte
>Cc: [email-masked]

---

From: Jon Watte <[email-masked]>
Date: Mon, 23 Feb 2009 14:35:49 -0800

> something that currently works and is deployed.

Honestly, for a vendor neutral standard, I don't think that argument 
holds much water.

I have put a write-up of the high-level points I want to see addressed 
for LLSD to work as a general purpose data description language for 
interoperable virtual worlds here:

http://www.interopworld.com/node/32

Note that it is not an in-detail specification edit, because it 
addresses a large number of concerns -- instead, it's a checklist of 
in-detail edits that would have to be done for LLSD to "fit the bill" in 
my opinion. However, I'm not sure that we should actually make all those 
edits just yet, because I think it's still too early to actually decide 
to standardize a data interchange description language.

Sincerely,

jw

---

From: Mark Lentczner <[email-masked]>
Date: Mon, 23 Feb 2009 14:54:51 -0800

> key="something_i_like_to_eat_on_sundays">bananas</value>

This format is notably more difficult for schemas (from XMLSchema to  
RelaxNG) to support, since value now has a key attribute that is only  
valid iff it is tested in a map element.  Second, you have left out  
the top element, which needs to be something fixed, rather than being  
map or array or value depending on the structure of the data.

Including a type attribute also makes things difficult for schemas, as  
the content of the value element now depends on the value of one of  
it's attributes.

Including the key value as an attribute value will make this somewhat  
harder to edit in some systems where "human readable" text is  
generally much easier to handle as element content.  Keeping the key  
value as element content also keeps the processing with key values  
consistent with the processing of string values with respect to string  
handling including normalization.

The issue of wrapping each key value pair of a map in an entry element  
or just using ordered alternation is one of those infinite XML debates.

The XPath argument doesn't hold:  XPath expressions for selecting the  
value of the success entry in a map are about the same, and not all  
that difficult:

Current draft LLSD:
	/llsd/map/key[.="success"]/following-sibling::*[1]

Catherine's LLSD:
	/llsd/map/entry/key[.="success"]/following-sibling::*[1]

Jon's LLSD:
	/llsd/map/value[@key="success"]

True, Jon's LLSD yields a slightly smaller and cleaner XPath  
expression, the others are nothing out of the ordinary.

	- Mark

Mark Lentczner
Sr. Systems Architect
Technology Integration
Linden Lab

[email-masked]

Zero Linden
[email-masked]

---

From: "Meadhbh Hamrick (Infinity)" <[email-masked]>
Date: Mon, 23 Feb 2009 14:58:33 -0800

i stand corrected...

okay... John, Catherine and Jon...

the existing serialization is in current use by SL, OpenSim and PyOGP,  
so there's probably going to be some resistance (from Linden) to  
changing something that currently works and is deployed and some  
people who have deployed OpenSim code (distinct from the people who  
created the code) MAY have some resistance.

which is to say... my co-workers will pummel with rotten vegetables if  
i commit them to supporting another serialization, despite it's  
obvious advantages. before making a change of this sort, we would be  
doing a fair amount of testing to ensure our system works fine with  
the new serialization. this would require a non-zero amount of  
resources be spent on deploying the change. ergo, we would need some  
justification for making the change.

that being said... "there are a number of deployed hosts with whom we  
want to interoperate who use this serialization" might be a suitable  
justification, or at least it would decrease the number of rotten  
vegetables i would be pelted with to an acceptably low level.

but may i ask? why do we need to change something that we know works,  
is already deployed, and seems to work without flaw?

my suspicion is that there's a belief that:
	1. there are too many angle brackets, leading to wasted bandwidth and  
wasted CPU use.
	2. it's hard to use with XSLT

so my response would be:
	1.a. can we look at the effect before making this change? my  
suspicion is that message sizes will be much more affected by turning  
on compressed content encoding than with the change from one DTD to  
another.
	1.b. do any of us have numbers about how much more efficient the  
"new" encoding is vs. the "legacy" encoding? sure.. there are fewer  
angle brackets, but really you're just trading parsing angle brackets  
for parsing attributes and enclosing quote.
	2.a. to a certain degree, the contents of the XML serialization are  
un-important compared to the contents of the object to which it  
deserializes.
	2.b. why is this more of an issue with XML map elements than it was  
when people were trying to use Apple plists with XSLT?

so... my recommendation might be...

* can someone write a "next generation" XML serialization proposal?
* can we do a bake off?
	* first with testing the space savings between the two serialization  
schemes after compressed content encoding is taken into account and
	* second with seeing how much of a decoding speed improvement you get  
from moving from keys in their own elements to keys as attributes.

-cheers,
-meadhbh

On Feb 23, 2009, at 2:18 PM, Hurliman, John wrote:

> Speaking as the maintainer of OpenSim's LLSD<->XML serialization  
> library (OpenMetaverse.StructuredData) I can say there would be zero  
> resistance from me in adopting a better serialization. In fact, I  
> would greet the changes with open arms, as would most people in the  
> open source virtual world sphere. Please do not put any of the  
> OpenSim/OpenMetaverse efforts in the same sentence when claiming  
> that improvements will be met with resistance. If there is going to  
> be a significant amount of resistance to anything that improves on  
> deployed and working Second Life technology, then I don't think this  
> will get very far.
>
> John
>

---

From: Jon Watte <[email-masked]>
Date: Mon, 23 Feb 2009 15:03:10 -0800

> map or array or value depending on the structure of the data.

Yes, my illustration was only an illustration of how to turn a tag-fest 
into something more useful.

> the content of the value element now depends on the value of one of 

I don't think you can verify the content of any element absent the 
actual executable code endpoint. Trying to do that in schema is pretty 
useless IMO. For example, if we have a "float64_3" type for global 
position, then perhaps a schema validator could verify that the content 
of that element would be three float64 values separated by commas 
(assuming that's the defined serialization), but there would be no way 
for the schema to validate that that position was actually semantically 
valid within the target context, because that's a simulation property.

> handling including normalization.

My experience is the opposite. Hence, my proposed change :-)

Also, my suggested serialization is invariant to child node re-ordering. 
Most of the time, that's not important, but for some cases, where a tree 
might be put into a hash map for fast access, it matters. 
Not-order-specific XML is generally faster to parse and more robust, 
when you can actually assume it's non-order-specific.

I'd be comfortable with backing off to say that the element tag name is 
the data type, while key is still an attribute, but from my experience, 
putting the type as an attribute as well actually works out better in 
practice.

Sincerely,

jw

---

From: Jon Watte <[email-masked]>
Date: Mon, 23 Feb 2009 15:58:40 -0800

Meadhbh Hamrick (Infinity) wrote:
> our system works fine with the new serialization. this would require a 
> non-zero amount of resources be spent on deploying the change. ergo, 
> we would need some justification for making the change.
>

Do you agree that any kind of generally suitable interoperability will 
require engineering effort, sometimes significant, on the part of all 
possible implementors, including Linden Lab or the Open Sim developers?

You do not have to update your internal serialization at all just 
because we, collectively, design a serialization scheme with 
differences. You don't need to do any work until and unless such time that
1) there is an actual standard, or at least a concrete proposal
2) you decide that supporting this standard is in the best interests of 
your company or group

> is already deployed, and seems to work without flaw?

Because it can work better. It can be more compact, it can better suit a 
variety of parser styles, it can be easier read and written by human 
beings, it can be easier expanded or adapted, it can more easily be 
processed using fast hashing-based (order independent) processing methods.

If your argument is that "while I understand that some other people feel 
that direction X is better, we are currently using direction Y in the 
Second Life implementation, so I think Second Life's way should prevail" 
then you're not actually signed on to the generally applicable, vendor 
neutral interoperability standard bandwagon.

> * can we do a bake off?

Once we're done with a serialization format that fulfills all the 
necessary requirements, I believe there won't be anything "else" to 
bake-off against.
See here for some requirements I would put on a standardized format:
http://www.interopworld.com/node/32

I will copy and paste for the convenience of those who don't like 
out-of-line references:

I have looked at the proposal, and see a number of issues that I think 
need to be addressed before the proposal can be used as a general 
interoperability standard.

! Proposal Name

The name probably should change to something like "VWSD" to avoid any 
accusation of vendor bias. I trust we can just get this done without too 
much argument about specific naming.

! Large and Small Integers

The "integer" data type needs to be more flexible. 64-bit integers are 
important, and you can even view UUIDs as 128-bit integers. I propose 
that integers can be specified as a specific bit width, and signed or 
unsigned. If you want to stay byte aligned, the set of allowable sizes 
may be limited to 8, 16, 32 or 64. I additionally propose that a 
Variable Length Integer Encoding be specified.

! Float32 and Float16

Reals should come in at least two forms: 64-bit and 32-bit. The reason 
is that localized position relative to some center usually is best 
described as a 32-bit float. Additionally, mesh data is generally 
described as 32-bit float vertices, rather than 64-bit. There may be 
some additional benefit in supporting 16-bit floats, for things like 
normals, color values or direction vectors.

! Compact Binary Serialization

There needs to be support for a binary serialization that does not 
contain embedded type or key references, but instead use explicit 
external schema. Thus, to describe a "quaternion" you would simply 
specify four fp16 (or fp32) values in sequence, with no specific type 
information. This can extend to describing general entity property 
values: the type information can be carried by the schema for the 
entity, and does not need to be encoded in the actual data. Allowing 
external schema leads to significant bandwidth savings during transmission.

! XPath Friendly XML

The XML encoding needs to be XPath friendly, and friendly to introducing 
or adapting new types in a negotiated higher-version schema. Generally, 
this means that it looks something like:
<map>
<value key="success" type="boolean">true</value>
<value key="cpu_temp" type="float32">67.0</value>
</map>
The currently proposed serialization is poor because it's not easy or 
efficient to find specific values you care about by key; it's also 
inefficient because it requires any new data types to update the XSD 
schema, because each type is a tag name.

! Machine Parsable Descriptions

It is likely that the language describing the serialization structures 
will actually be read by machines at runtime, rather than used to 
generate code. This is definitely true for things like proxy servers and 
systems that treat entities as "generic collections of data" but want to 
have some understanding of the underlying data for display, translation, 
or other processing. While it would be possible to write a parser for 
the current LLSD syntax, introducing a new language syntax into the 
world doesn't seem warranted. I propose that the data structure 
definition language be moved to some XML schema.

Sincerely,

jw

---

From: "Hurliman, John" <[email-masked]>
Date: Mon, 23 Feb 2009 17:48:50 -0700

>From: Jon Watte [mailto:[email-masked]]
>Sent: Monday, February 23, 2009 3:59 PM
>To: Meadhbh Hamrick (Infinity)
>Cc: Hurliman, John; [email-masked]

No opinion here, other than not tying it to virtual worlds. All we are doing is defining yet another IDL, because the group asserts that ASN.1, Apache Thrift, Google Protocol Buffers, and any other proposed solutions will not work as a virtual world interop base for technical or political reasons. However, that doesn't mean that we have to create an IDL that only works for virtual worlds.

>Variable Length Integer Encoding be specified.

Agreed on supporting multiple lengths of signed vs. unsigned. I would really like to see int32, int64, uint32, uint64 and could take or leave the rest personally. Doing variable length integer encoding (such as the base-128 varints used in Google Protocol Buffers: http://code.google.com/apis/protocolbuffers/docs/encoding.html) would be a nice fix for the binary encoding.

>normals, color values or direction vectors.

Just adding 32-bit float support is probably fine for most use cases. I don't understand the reasoning behind only supporting 64-bit floats in LLSD at all, especially considering the vast majority of floating point data in Second Life is 32-bit.

>external schema leads to significant bandwidth savings during

Maybe one of the existing binary serializations used by Apache Thrift or Google Protocol Buffers could be supported? Even if we don't want to tie the LLSD spec to third party references, something that draws on the techniques from those IDLs would be much more efficient than the current LLSD binary. I think the need to tightly couple the IDL and type system for this kind of serialization highlights the fact that LLSD/LLIDL is not doing anything new; the same dependencies are still present.

>definition language be moved to some XML schema.

-1 on this. The LLIDL syntax is very easy to parse, and I posted a simple grammar file to generate a lexer/parser. Introducing a new XML schema creates just as much implementation work. However, LLSD/LLIDL is still encouraging code that is difficult to read and easy to break. Data should enter and exit in the form of a struct, not a map of string/value pairs where anything can be inserted but only a fixed subset of possibilities will be valid.

John

---

From: Jon Watte <[email-masked]>
Date: Mon, 23 Feb 2009 17:21:30 -0800

Hurliman, John wrote:
> length integer encoding (such as the base-128 varints used in Google Protocol Buffers: http://code.google.com/apis/protocolbuffers/docs/encoding.html) would be a nice fix for the binary encoding.
>
>   

That needs a fix for signed-ness, though. My proposal is to encode the 
sign bit in the 6th bit of the first byte IF the value is less than 0 or 
greater than 127 (keeping the encoding of small positive integers to a 
single byte). For negative numbers, encode the one's complement and the 
sign bit, and negate when done. This nicely sidesteps problems you'd get 
when trying to encode two's complement in a variable-width container. 
But that might be a slightly premature technical detail ;-)

> -1 on this. The LLIDL syntax is very easy to parse, and I posted a simple grammar file to generate a lexer/parser. Introducing a new XML schema creates just as much implementation 

My point is that XML for a schema language is even easier to parse:

xd = new System.Xml.XmlDocument();
xd.LoadXml(...);

Done. And this allows various code bases to easily adopt various levels 
of knowledge of the serialized data using existing tools, instead of 
having to add yet another kind of language parser with yet another set 
of mutually ambiguous or buggy implementations.

Sincerely,

jw