Hi Zach,
thanks for your additional input. You are absolutely right: The long
namespace should be big enough. We are going to insert up to 2^32 values
into the list.
We only need support for get(index), insert(index) and remove(index)
while get and insert will be used very often. Remove is also needed but
used very rare.
Kind regards
Matthias
On 10/13/2011 04:49 PM, Zach Richardson wrote:
Matthias,
Answers below.
On Thu, Oct 13, 2011 at 9:03 AM, Matthias Pfau<p...@l3s.de> wrote:
Hi Zach,
thanks for that good idea. Unfortunately, our list needs to be rewritten
often because our data is far away from being evenly distributed.
This shouldn't be a problem if you use long's. If you were to space
them at original write (with N objects) at a distance of
Long.MAX_VALUE / N, and N was 10,000,000 you could still fit another
1844674407370 entries in between.
However, we could get this under control but there is a more severe problem:
Random access is very hard to implement on a structure with undefined
distances between two following index numbers. We absolutely need random
access because the lists are too big to do this on the application side :-(
I'm guessing you need to be able to implement all of the traditional
get(index), set(index), insert(index) type operations on the "list."
Once you start trying to do that, you start to hit all of the same
problems you get with different in memory list implementations based
on which operation is most important.
Could you provide some more information on what operations will be
performed the most, and how important they are. I think that would
help anyone recommend a path to take.
Zach
Kind regards
Matthias
On 10/13/2011 02:30 PM, Zach Richardson wrote:
Matthias,
This is an interesting problem.
I would consider using long's as the column type, where your column
names are evenly distributed longs in sort order when you first write
your list out. So if you have items A and C with the long column
names 1000 and 2000, and then you have to insert B, it gets inserted
at 1500. Once you run out of room between any two column name
entries, i.e 1000, 1001, 1002 entries are all taken at any spot in the
list, go ahead and re-write the list.
If your unencrypted data is uniformly distributed, you will have very
few collisions on your column names and should not have to re-write
the list to often.
If your lists are small enough, then you could use ints to save space,
but will then have to re-write the list more often.
Thanks,
Zach
On Thu, Oct 13, 2011 at 2:47 AM, Matthias Pfau<p...@l3s.de> wrote:
Hi Stephen,
this is a great idea but unfortunately doesn't work for us either as we
can
not store the data in an unencrypted form.
Kind regards
Matthias
On 10/12/2011 07:42 PM, Stephen Connolly wrote:
could you prefix the data with 3-4 bytes of a linear hash of the
unencypted data? it wouldn't be a perfect sort, but you'd have less of a
range to query to get the sorted values?
- Stephen
---
Sent from my Android phone, so random spelling mistakes, random nonsense
words and other nonsense are a direct result of using swype to type on
the screen
On 12 Oct 2011 17:57, "Matthias Pfau"<p...@l3s.de<mailto:p...@l3s.de>>
wrote:
Unfortunately, that is not an option as we have to store the data in
an compressed and encrypted and therefore binary and non-sortable
form.
On 10/12/2011 06:39 PM, David McNelis wrote:
Is it an option to not convert the data to binary prior to
inserting
into Cassandra? Also, how large are the strings you're sorting?
If its
viable to not convert to binary before writing to Cassandra, and
you use
one of the string based column ordering techniques (utf8, ascii,
for
example), then the data would be sorted without you needing to
specifically worry about that. Of course, if the strings are
lengthy
you could run into additional issues.
On Wed, Oct 12, 2011 at 11:34 AM, Matthias Pfau<p...@l3s.de
<mailto:p...@l3s.de>
<mailto:p...@l3s.de<mailto:p...@l3s.de>>> wrote:
Hi there,
we are currently building a prototype based on cassandra and
came
into problems on implementing sorted lists containing
millions of items.
The special thing about the items of our lists is, that
cassandra is
not able to sort them as the data is stored in a binary
format which
is not sortable. However, we are able to sort the data
before the
plain data gets encoded (our application is responsible for
the order).
First Approach: Storing Lists in ColumnFamilies
***
We first tried to map the list to a single row of a
ColumnFamily in
a way that the index of the list is mapped to the column
names and
the items of the list to the column values. The column names
are
increasing numbers which define the sort order.
This has the major drawback that big parts of the list have
to be
rewritten on inserts (because the column names are numbered
by their
index), which are quite common.
Second Approach: Storing the whole List as Binary Data:
***
We tried to store the compressed list in a single column.
However,
this is only feasible for smaller lists. Our lists are far
to big
leading to multi megabyte reads and writes. As we need to
read and
update the lists quite often, this would put our Cassandra
cluster
under a lot of pressure.
Ideal Solution: Native support for storing lists
***
We would be very happy with a way to store a list of sorted
values
without making improper use of column names for the list
index. This
implies that we would need a possibility to insert values at
defined
positions. We know that this could lead to problems with
concurrent
inserts in a distributed environment, but this is handled by
our
application logic.
What are your ideas on that?
Thanks
Matthias
--
*David McNelis*
Lead Software Engineer
Agentis Energy
www.agentisenergy.com<http://www.agentisenergy.com>
<http://www.agentisenergy.com>
c: 219.384.5143<tel:219.384.5143>
/A Smart Grid technology company focused on helping consumers of
energy
control an often under-managed resource./
