You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@thrift.apache.org by Bryan Duxbury <br...@rapleaf.com> on 2008/09/09 19:21:01 UTC

Ordering in collections

We use Thrift structures within Hadoop Map/Reduce. Occasionally, a  
Thrift object will be our grouping or join key. Usually, this works  
great, but occasionally, there are some issues. In particular, we  
have trouble with maps and sets. The problem is that the ordering of  
the map/set internally is arbitrary, and we serialize in that  
arbitrary order. The result is that two 'equal' objects might not  
serialize into the same byte array, and therefore fail equality  
checks based only on the serialized data.

I was wondering if it would make sense to enforce some sort of  
ordering scheme for collections where order might be arbitrary, at  
least during serialization. This would necessitate implementing a  
decent compareTo on generated Thrift structs so we could sort before  
writing, and obviously, it would include sorting overhead.

Are other people interested in making this use case work acceptably?

-Bryan

Re: Ordering in collections

Posted by David Reiss <dr...@facebook.com>.
Forcing the other side to do something that is not defined in the
IDL requires changing the wire format, which is something we should
try to avoid unless it provides big benefits.  You also have to consider
the fact that the "other side" could be running a language that doesn't
support order-preserving maps.  However, I mentioned the possibility
of annotating a type to use an ordered map.  It would be as easy to
force it to use an order-preserving map, if available.

--David

Yonik Seeley wrote:
> On Tue, Sep 9, 2008 at 1:45 PM, David Reiss <dr...@facebook.com> wrote:
>> I'm fine with implementing compareTo.  With proper type annotations,
>> we could provide a way to define that a given map be instantiated as
>> a TreeMap instead of a HashMap when deserializing, which would enforce
>> an order.
> 
> How about retaining an order... if LinkedHashMap is used on one side
> when order is important, is it possible to force creation of an order
> preserving map (like LinkedHashMap) on the receiver?
> 
> -Yonik
> 

Re: Ordering in collections

Posted by Yonik Seeley <yo...@apache.org>.
On Tue, Sep 9, 2008 at 1:45 PM, David Reiss <dr...@facebook.com> wrote:
> I'm fine with implementing compareTo.  With proper type annotations,
> we could provide a way to define that a given map be instantiated as
> a TreeMap instead of a HashMap when deserializing, which would enforce
> an order.

How about retaining an order... if LinkedHashMap is used on one side
when order is important, is it possible to force creation of an order
preserving map (like LinkedHashMap) on the receiver?

-Yonik

Re: Ordering in collections

Posted by David Reiss <dr...@facebook.com>.
I'm fine with implementing compareTo.  With proper type annotations,
we could provide a way to define that a given map be instantiated as
a TreeMap instead of a HashMap when deserializing, which would enforce
an order.

--David

Bryan Duxbury wrote:
> We use Thrift structures within Hadoop Map/Reduce. Occasionally, a 
> Thrift object will be our grouping or join key. Usually, this works 
> great, but occasionally, there are some issues. In particular, we 
> have trouble with maps and sets. The problem is that the ordering of 
> the map/set internally is arbitrary, and we serialize in that 
> arbitrary order. The result is that two 'equal' objects might not 
> serialize into the same byte array, and therefore fail equality 
> checks based only on the serialized data.
> 
> I was wondering if it would make sense to enforce some sort of 
> ordering scheme for collections where order might be arbitrary, at 
> least during serialization. This would necessitate implementing a 
> decent compareTo on generated Thrift structs so we could sort before 
> writing, and obviously, it would include sorting overhead.
> 
> Are other people interested in making this use case work acceptably?
> 
> -Bryan
>