You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@accumulo.apache.org by "Adam J. Shook" <ad...@gmail.com> on 2015/12/28 17:47:53 UTC
Map Lexicoder
Hello all,
Any suggestions for using a Map Lexicoder (or implementing one)? I am
currently using a new ListLexicoder(new PairLexicoder(some lexicoder, some
lexicoder), which is working for single maps. However, when one of the
lexicoders in the Pair is itself a Map (and therefore another
ListLexicoder(PairLexicoder)), an exception is being thrown because
ArrayList is not Comparable.
Regards,
--Adam
Re: Map Lexicoder
Posted by Josh Elser <jo...@gmail.com>.
Gotcha, thanks for the background.
I think as long as you can preserve the same level of compatibility with
the other lexicoders, this would be a nice addition. If it's an itch you
want to scratch, others probably will want to do the same too :)
Keith probably knows the most about what current works off the top of
his head (since he wrote the Lexicoders, IIRC), but I imagine he's
taking some time off work and isn't watch the list mailing list closely.
If you get stuck with how to implement this, let me know and I can try
to poke around at the implementation too.
Adam J. Shook wrote:
> Hi Josh,
>
> Thanks for the advice. I'm with you on using the CQ and Value instead
> of putting the whole map into a Value, but what I am working on is using
> the relational model of mapping data to Accumulo and expects the value
> of the cell to be in the Value. Certainly some optimization
> opportunities by using the 'better' ways for storing data in Accumulo,
> but I'd like to get this working before diving into that rabbit hole.
>
> A brief look at the ListLexicoder encodes each element of the list using
> a sub-lexicoder and escapes each element (0x00 -> 0x01 0x01 and 0x01 ->
> 0x01 0x02). The voodoo here escapes me a little (pun!), but it seems to
> be enough to enable multi-dimensional arrays encoded by nesting
> ListLexicoders (up to 4D, haven't tried a fifth dimension). I would
> expect something similar could be done using a Map. Would a
> MapLexicoder be something worth contributing to the project? I'd be
> happy to give it a stab.
>
> --Adam
>
> On Mon, Dec 28, 2015 at 12:21 PM, Josh Elser <josh.elser@gmail.com
> <ma...@gmail.com>> wrote:
>
> Looks like you would have to implement some kind of ComparableMap to
> be able to use the PairLexicoder (see that the parameterization
> requires both types in the Pair to implement Comparable). The Pair
> lexicoder requires these Comparable types to align itself with the
> original goal of the Lexicoders: provide byte-array serialization
> for types whose sort order matches the original object's ordering.
>
> Typically, when we have key to value style data we want to put in
> Accumulo, it makes sense to leverage the Column Qualifier and the
> Value, instead of serializing everything into one Accumulo Value.
> Iterators make it easy to do server-side predicates and
> transformations. My hunch is that this is another reason why you
> don't already see a MapLexicoder provided.
>
> One technical difficulty you might run into implementing a
> generalized MapLexicoder is how you delimit the key and value in one
> pair and how you delimit many pairs from each other. Commonly, the
> "null" byte (\x00) is used as a separator since it doesn't often
> appear in user-data. I'm not sure if some of the other Lexicoders
> already use this in their serialization (e.g. the ListLexicoder
> might, I haven't looked at the code). Nesting Lexicoders generically
> might be tricky (although not impossible) -- thought it was worth
> mentioning to make sure you thought about it.
>
>
> Adam J. Shook wrote:
>
> Hello all,
>
> Any suggestions for using a Map Lexicoder (or implementing
> one)? I am
> currently using a new ListLexicoder(new PairLexicoder(some
> lexicoder,
> some lexicoder), which is working for single maps. However,
> when one of
> the lexicoders in the Pair is itself a Map (and therefore another
> ListLexicoder(PairLexicoder)), an exception is being thrown because
> ArrayList is not Comparable.
>
> Regards,
> --Adam
>
>
Re: Map Lexicoder
Posted by "Adam J. Shook" <ad...@gmail.com>.
Hi Josh,
Thanks for the advice. I'm with you on using the CQ and Value instead of
putting the whole map into a Value, but what I am working on is using the
relational model of mapping data to Accumulo and expects the value of the
cell to be in the Value. Certainly some optimization opportunities by
using the 'better' ways for storing data in Accumulo, but I'd like to get
this working before diving into that rabbit hole.
A brief look at the ListLexicoder encodes each element of the list using a
sub-lexicoder and escapes each element (0x00 -> 0x01 0x01 and 0x01 -> 0x01
0x02). The voodoo here escapes me a little (pun!), but it seems to be
enough to enable multi-dimensional arrays encoded by nesting ListLexicoders
(up to 4D, haven't tried a fifth dimension). I would expect something
similar could be done using a Map. Would a MapLexicoder be something worth
contributing to the project? I'd be happy to give it a stab.
--Adam
On Mon, Dec 28, 2015 at 12:21 PM, Josh Elser <jo...@gmail.com> wrote:
> Looks like you would have to implement some kind of ComparableMap to be
> able to use the PairLexicoder (see that the parameterization requires both
> types in the Pair to implement Comparable). The Pair lexicoder requires
> these Comparable types to align itself with the original goal of the
> Lexicoders: provide byte-array serialization for types whose sort order
> matches the original object's ordering.
>
> Typically, when we have key to value style data we want to put in
> Accumulo, it makes sense to leverage the Column Qualifier and the Value,
> instead of serializing everything into one Accumulo Value. Iterators make
> it easy to do server-side predicates and transformations. My hunch is that
> this is another reason why you don't already see a MapLexicoder provided.
>
> One technical difficulty you might run into implementing a generalized
> MapLexicoder is how you delimit the key and value in one pair and how you
> delimit many pairs from each other. Commonly, the "null" byte (\x00) is
> used as a separator since it doesn't often appear in user-data. I'm not
> sure if some of the other Lexicoders already use this in their
> serialization (e.g. the ListLexicoder might, I haven't looked at the code).
> Nesting Lexicoders generically might be tricky (although not impossible) --
> thought it was worth mentioning to make sure you thought about it.
>
>
> Adam J. Shook wrote:
>
>> Hello all,
>>
>> Any suggestions for using a Map Lexicoder (or implementing one)? I am
>> currently using a new ListLexicoder(new PairLexicoder(some lexicoder,
>> some lexicoder), which is working for single maps. However, when one of
>> the lexicoders in the Pair is itself a Map (and therefore another
>> ListLexicoder(PairLexicoder)), an exception is being thrown because
>> ArrayList is not Comparable.
>>
>> Regards,
>> --Adam
>>
>
Re: Map Lexicoder
Posted by Josh Elser <jo...@gmail.com>.
Looks like you would have to implement some kind of ComparableMap to be
able to use the PairLexicoder (see that the parameterization requires
both types in the Pair to implement Comparable). The Pair lexicoder
requires these Comparable types to align itself with the original goal
of the Lexicoders: provide byte-array serialization for types whose sort
order matches the original object's ordering.
Typically, when we have key to value style data we want to put in
Accumulo, it makes sense to leverage the Column Qualifier and the Value,
instead of serializing everything into one Accumulo Value. Iterators
make it easy to do server-side predicates and transformations. My hunch
is that this is another reason why you don't already see a MapLexicoder
provided.
One technical difficulty you might run into implementing a generalized
MapLexicoder is how you delimit the key and value in one pair and how
you delimit many pairs from each other. Commonly, the "null" byte (\x00)
is used as a separator since it doesn't often appear in user-data. I'm
not sure if some of the other Lexicoders already use this in their
serialization (e.g. the ListLexicoder might, I haven't looked at the
code). Nesting Lexicoders generically might be tricky (although not
impossible) -- thought it was worth mentioning to make sure you thought
about it.
Adam J. Shook wrote:
> Hello all,
>
> Any suggestions for using a Map Lexicoder (or implementing one)? I am
> currently using a new ListLexicoder(new PairLexicoder(some lexicoder,
> some lexicoder), which is working for single maps. However, when one of
> the lexicoders in the Pair is itself a Map (and therefore another
> ListLexicoder(PairLexicoder)), an exception is being thrown because
> ArrayList is not Comparable.
>
> Regards,
> --Adam
Re: Map Lexicoder
Posted by Josh Elser <jo...@gmail.com>.
Yeah, I could see Key ordering or Entry ordering both make sense
depending on the context :)
Adam J. Shook wrote:
> I personally think all maps with the same keys should be sorted
> together, but I think it'd be best to support and document both ways and
> leave that up to the user. I'm sure either way could be argued, and
> this is certainly an edge case for lexicoders.
>
> On Tue, Dec 29, 2015 at 7:16 PM, Keith Turner <keith@deenlo.com
> <ma...@deenlo.com>> wrote:
>
> Do you want all maps with the same keys to sort together? If so
> doing abc123 would make that happen.
>
> The map data below
>
> { a : 1 , b : 2, c : 3 }
> { a : 1 , x : 8, y : 9 }
> { a : 4 , b : 5, c : 6 }
>
> Would sort like the following if encoding key values pairs
>
> a1b2c3
> a1x8y9
> a4b5c6
>
> If encoding all key and then all values, it would sort as follows
>
> abc123
> abc456
> axy189
>
>
>
> On Tue, Dec 29, 2015 at 4:53 PM, Adam J. Shook <adamjshook@gmail.com
> <ma...@gmail.com>> wrote:
>
> Agreed, I came to the same conclusion while implementing. The
> final result that I have is a SortedMapLexicoder to avoid any
> comparisons going haywire. Additionally, would it be best to
> encode the map as an array of keys followed by an array of
> values, or encode all key value pairs back-to-back:
>
> { a : 1 , b : 2, c : 3 } encoded as
>
> a1b2c3
> -or-
> abc123
>
> Feels like I should be encoding a list of keys, then the list of
> values, and then concatenating these two encoded byte arrays. I
> think the end solution will be to support both? I'm having a
> hard time reconciling which method is better, if any. Hard to
> find some good examples of people who are sorting a list of maps.
>
> On Tue, Dec 29, 2015 at 2:47 PM, Keith Turner <keith@deenlo.com
> <ma...@deenlo.com>> wrote:
>
>
>
> On Mon, Dec 28, 2015 at 11:47 AM, Adam J. Shook
> <adamjshook@gmail.com <ma...@gmail.com>> wrote:
>
> Hello all,
>
> Any suggestions for using a Map Lexicoder (or
> implementing one)? I am currently using a new
> ListLexicoder(new PairLexicoder(some lexicoder, some
> lexicoder), which is working for single maps. However,
> when one of the lexicoders in the Pair is itself a Map
> (and therefore another ListLexicoder(PairLexicoder)), an
> exception is being thrown because ArrayList is not
> Comparable.
>
>
>
> Since maps do not have a well defined order of keys and
> values, comparison is tricky. The purpose of Lexicoders is
> encode things in such a way that the lexicographical
> comparison of the serialized data is possible. With a
> hashmap if I add the same data in the same order to two
> different hash map instances, its possible that when
> iterating over those maps I could see the data in different
> orders. This could lead to two maps constructed in the
> same way at different times (like different JVMs with
> different implementations of HashMap) generating different
> data that compare as different. Ideally comparison of the
> two would yield equality.
>
> Something like LinkedHashMap does not have this problem for
> the same insertion order. If you want things to be
> comparable regardless of insertion order (which I think is
> more intuitive), then SortedMap seems like it would be a
> good candidate. So maybe a SortedMapLexicoder would be a
> better thing to offer?
>
>
> Regards,
> --Adam
>
>
>
>
>
Re: Map Lexicoder
Posted by "Adam J. Shook" <ad...@gmail.com>.
I personally think all maps with the same keys should be sorted together,
but I think it'd be best to support and document both ways and leave that
up to the user. I'm sure either way could be argued, and this is certainly
an edge case for lexicoders.
On Tue, Dec 29, 2015 at 7:16 PM, Keith Turner <ke...@deenlo.com> wrote:
> Do you want all maps with the same keys to sort together? If so doing
> abc123 would make that happen.
>
> The map data below
>
> { a : 1 , b : 2, c : 3 }
> { a : 1 , x : 8, y : 9 }
> { a : 4 , b : 5, c : 6 }
>
> Would sort like the following if encoding key values pairs
>
> a1b2c3
> a1x8y9
> a4b5c6
>
> If encoding all key and then all values, it would sort as follows
>
> abc123
> abc456
> axy189
>
>
>
> On Tue, Dec 29, 2015 at 4:53 PM, Adam J. Shook <ad...@gmail.com>
> wrote:
>
>> Agreed, I came to the same conclusion while implementing. The final
>> result that I have is a SortedMapLexicoder to avoid any comparisons going
>> haywire. Additionally, would it be best to encode the map as an array of
>> keys followed by an array of values, or encode all key value pairs
>> back-to-back:
>>
>> { a : 1 , b : 2, c : 3 } encoded as
>>
>> a1b2c3
>> -or-
>> abc123
>>
>> Feels like I should be encoding a list of keys, then the list of values,
>> and then concatenating these two encoded byte arrays. I think the end
>> solution will be to support both? I'm having a hard time reconciling which
>> method is better, if any. Hard to find some good examples of people who
>> are sorting a list of maps.
>>
>> On Tue, Dec 29, 2015 at 2:47 PM, Keith Turner <ke...@deenlo.com> wrote:
>>
>>>
>>>
>>> On Mon, Dec 28, 2015 at 11:47 AM, Adam J. Shook <ad...@gmail.com>
>>> wrote:
>>>
>>>> Hello all,
>>>>
>>>> Any suggestions for using a Map Lexicoder (or implementing one)? I am
>>>> currently using a new ListLexicoder(new PairLexicoder(some lexicoder, some
>>>> lexicoder), which is working for single maps. However, when one of the
>>>> lexicoders in the Pair is itself a Map (and therefore another
>>>> ListLexicoder(PairLexicoder)), an exception is being thrown because
>>>> ArrayList is not Comparable.
>>>>
>>>
>>>
>>> Since maps do not have a well defined order of keys and values,
>>> comparison is tricky. The purpose of Lexicoders is encode things in such
>>> a way that the lexicographical comparison of the serialized data is
>>> possible. With a hashmap if I add the same data in the same order to two
>>> different hash map instances, its possible that when iterating over those
>>> maps I could see the data in different orders. This could lead to two
>>> maps constructed in the same way at different times (like different JVMs
>>> with different implementations of HashMap) generating different data that
>>> compare as different. Ideally comparison of the two would yield equality.
>>>
>>> Something like LinkedHashMap does not have this problem for the same
>>> insertion order. If you want things to be comparable regardless of
>>> insertion order (which I think is more intuitive), then SortedMap seems
>>> like it would be a good candidate. So maybe a SortedMapLexicoder would be
>>> a better thing to offer?
>>>
>>>
>>>> Regards,
>>>> --Adam
>>>>
>>>
>>>
>>
>
Re: Map Lexicoder
Posted by Keith Turner <ke...@deenlo.com>.
Do you want all maps with the same keys to sort together? If so doing
abc123 would make that happen.
The map data below
{ a : 1 , b : 2, c : 3 }
{ a : 1 , x : 8, y : 9 }
{ a : 4 , b : 5, c : 6 }
Would sort like the following if encoding key values pairs
a1b2c3
a1x8y9
a4b5c6
If encoding all key and then all values, it would sort as follows
abc123
abc456
axy189
On Tue, Dec 29, 2015 at 4:53 PM, Adam J. Shook <ad...@gmail.com> wrote:
> Agreed, I came to the same conclusion while implementing. The final
> result that I have is a SortedMapLexicoder to avoid any comparisons going
> haywire. Additionally, would it be best to encode the map as an array of
> keys followed by an array of values, or encode all key value pairs
> back-to-back:
>
> { a : 1 , b : 2, c : 3 } encoded as
>
> a1b2c3
> -or-
> abc123
>
> Feels like I should be encoding a list of keys, then the list of values,
> and then concatenating these two encoded byte arrays. I think the end
> solution will be to support both? I'm having a hard time reconciling which
> method is better, if any. Hard to find some good examples of people who
> are sorting a list of maps.
>
> On Tue, Dec 29, 2015 at 2:47 PM, Keith Turner <ke...@deenlo.com> wrote:
>
>>
>>
>> On Mon, Dec 28, 2015 at 11:47 AM, Adam J. Shook <ad...@gmail.com>
>> wrote:
>>
>>> Hello all,
>>>
>>> Any suggestions for using a Map Lexicoder (or implementing one)? I am
>>> currently using a new ListLexicoder(new PairLexicoder(some lexicoder, some
>>> lexicoder), which is working for single maps. However, when one of the
>>> lexicoders in the Pair is itself a Map (and therefore another
>>> ListLexicoder(PairLexicoder)), an exception is being thrown because
>>> ArrayList is not Comparable.
>>>
>>
>>
>> Since maps do not have a well defined order of keys and values,
>> comparison is tricky. The purpose of Lexicoders is encode things in such
>> a way that the lexicographical comparison of the serialized data is
>> possible. With a hashmap if I add the same data in the same order to two
>> different hash map instances, its possible that when iterating over those
>> maps I could see the data in different orders. This could lead to two
>> maps constructed in the same way at different times (like different JVMs
>> with different implementations of HashMap) generating different data that
>> compare as different. Ideally comparison of the two would yield equality.
>>
>> Something like LinkedHashMap does not have this problem for the same
>> insertion order. If you want things to be comparable regardless of
>> insertion order (which I think is more intuitive), then SortedMap seems
>> like it would be a good candidate. So maybe a SortedMapLexicoder would be
>> a better thing to offer?
>>
>>
>>> Regards,
>>> --Adam
>>>
>>
>>
>
Re: Map Lexicoder
Posted by Matthew Hall <mh...@mhcomputing.net>.
On Tue, Dec 29, 2015 at 04:53:47PM -0500, Adam J. Shook wrote:
> a1b2c3
Most map serializations use this approach to maximize locality of reference in
the CPU cache when serializing and deserializing.
Matthew.
Re: Map Lexicoder
Posted by "Adam J. Shook" <ad...@gmail.com>.
Agreed, I came to the same conclusion while implementing. The final result
that I have is a SortedMapLexicoder to avoid any comparisons going
haywire. Additionally, would it be best to encode the map as an array of
keys followed by an array of values, or encode all key value pairs
back-to-back:
{ a : 1 , b : 2, c : 3 } encoded as
a1b2c3
-or-
abc123
Feels like I should be encoding a list of keys, then the list of values,
and then concatenating these two encoded byte arrays. I think the end
solution will be to support both? I'm having a hard time reconciling which
method is better, if any. Hard to find some good examples of people who
are sorting a list of maps.
On Tue, Dec 29, 2015 at 2:47 PM, Keith Turner <ke...@deenlo.com> wrote:
>
>
> On Mon, Dec 28, 2015 at 11:47 AM, Adam J. Shook <ad...@gmail.com>
> wrote:
>
>> Hello all,
>>
>> Any suggestions for using a Map Lexicoder (or implementing one)? I am
>> currently using a new ListLexicoder(new PairLexicoder(some lexicoder, some
>> lexicoder), which is working for single maps. However, when one of the
>> lexicoders in the Pair is itself a Map (and therefore another
>> ListLexicoder(PairLexicoder)), an exception is being thrown because
>> ArrayList is not Comparable.
>>
>
>
> Since maps do not have a well defined order of keys and values, comparison
> is tricky. The purpose of Lexicoders is encode things in such a way that
> the lexicographical comparison of the serialized data is possible. With a
> hashmap if I add the same data in the same order to two different hash map
> instances, its possible that when iterating over those maps I could see the
> data in different orders. This could lead to two maps constructed in the
> same way at different times (like different JVMs with different
> implementations of HashMap) generating different data that compare as
> different. Ideally comparison of the two would yield equality.
>
> Something like LinkedHashMap does not have this problem for the same
> insertion order. If you want things to be comparable regardless of
> insertion order (which I think is more intuitive), then SortedMap seems
> like it would be a good candidate. So maybe a SortedMapLexicoder would be
> a better thing to offer?
>
>
>> Regards,
>> --Adam
>>
>
>
Re: Map Lexicoder
Posted by Keith Turner <ke...@deenlo.com>.
On Mon, Dec 28, 2015 at 11:47 AM, Adam J. Shook <ad...@gmail.com>
wrote:
> Hello all,
>
> Any suggestions for using a Map Lexicoder (or implementing one)? I am
> currently using a new ListLexicoder(new PairLexicoder(some lexicoder, some
> lexicoder), which is working for single maps. However, when one of the
> lexicoders in the Pair is itself a Map (and therefore another
> ListLexicoder(PairLexicoder)), an exception is being thrown because
> ArrayList is not Comparable.
>
Since maps do not have a well defined order of keys and values, comparison
is tricky. The purpose of Lexicoders is encode things in such a way that
the lexicographical comparison of the serialized data is possible. With a
hashmap if I add the same data in the same order to two different hash map
instances, its possible that when iterating over those maps I could see the
data in different orders. This could lead to two maps constructed in the
same way at different times (like different JVMs with different
implementations of HashMap) generating different data that compare as
different. Ideally comparison of the two would yield equality.
Something like LinkedHashMap does not have this problem for the same
insertion order. If you want things to be comparable regardless of
insertion order (which I think is more intuitive), then SortedMap seems
like it would be a good candidate. So maybe a SortedMapLexicoder would be
a better thing to offer?
> Regards,
> --Adam
>