Mailing-List: contact user-help@cassandra.apache.org; run by ezmlm
Precedence: bulk
Reply-To: user@cassandra.apache.org
Received-SPF: pass (athena.apache.org: local policy)
Message-ID: <4E9D2772.5060005@l3s.de>
Date: Tue, 18 Oct 2011 09:14:58 +0200
From: Matthias Pfau <pfau@l3s.de>
User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US;
 rv:1.9.2.23) Gecko/20110922 Thunderbird/3.1.15
MIME-Version: 1.0
To: user@cassandra.apache.org
Subject: Re: Storing pre-sorted data
References: <4E95C17C.5000008@l3s.de>
 <CAKc7CJQ89-7dpUumed2LC1SWb4iQz=sefJrfpEFJ5EWEOusTYA@mail.gmail.com>
 <4E95C6C6.2060304@l3s.de>
 <CA+nPnMx5wEYgg0nGCYFXhbVEnjWEJ_OKuWPmUcvKMW_oorzaOQ@mail.gmail.com>
 <4E969786.7040208@l3s.de>
 <CA+nPnMzAEtArcAMB-23G3mFCOk340w4gnDY2M10RaTYNSggayg@mail.gmail.com>
 <4E97186A.5010401@l3s.de>
 <CA+nPnMx8ZVBK7Qek_eeBuQcWy34Hm2sQ7uDkpPM0DnOmhfiz1A@mail.gmail.com>
 <4E974834.2030205@l3s.de>
 <CA+nPnMz8VLyJxdijiQsa_HgSB6ozsnjNtnEok8Wr5Wk4s3RnHA@mail.gmail.com>
 <CA+CP9O6nb0=U6LZQCQsceuvxrABugewgTfYfPcC_ONvR1U4eLg@mail.gmail.com>
 <4E9BF7C0.9090107@l3s.de>
 <BBA94646-9526-4386-AB0C-25559D506192@thelastpickle.com>
In-Reply-To: <BBA94646-9526-4386-AB0C-25559D506192@thelastpickle.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Aaron,
we want to sort completely on the client-side (where the data is 
encrypted). But that requires an "insert at offset X" operation. We 
would always use CL QUORUM and client side synchronisation.

However, it seems to be not be a good idea to add such a feature to 
cassandra as everyone using these features would have to use client 
synchronization and QUORUM.

Kind regards
Matthias

On 10/17/2011 10:38 PM, aaron morton wrote:
> Sort order is determined by the Comparator, which is  an implementation of the o.a.c.db.marshal.AbstractType<T>  class.
>
> If you wish to order column (names) in a row based on an opaque (to cassandra) byte value you can create your own implementation. You would then need to decrypt and compare column values. I've not idea how feasible that is in your situation with regard to security and performance.
>
> Also without understanding how you want to compare the values, composite types may be useful as you can make some parts of the opaque value visible to cassandra so sorting. If you can provide more info on how you want the sorting (i may have missed it) done that would be handy.
>
> Insert at offset X, even with client side synchronization, would be troublesome at CL ONE.
>
> Hope that helps.
>
> -----------------
> Aaron Morton
> Freelance Cassandra Developer
> @aaronmorton
> http://www.thelastpickle.com
>
> On 17/10/2011, at 10:39 PM, Matthias Pfau wrote:
>
>> David,
>> thanks for your nice summary on this topic.
>>
>> We would be very happy if cassandra would give us an option to maintain the sort order on our own (application logic). That is why it would be interesting to hear from any of the developers if it would be easily possible to add such a feature to cassandra.
>>
>> Otherwise, it seems like we have to implement sth. based on strategy (a) because (b) is not feasible for us and (c) is a rather young research topic which is slowly gaining more attention.
>>
>> Kind Regards
>> Matthias
>>
>> On 10/15/2011 10:55 PM, David Jeske wrote:
>>> Logically, whether you use cassandra or not, there is some "physics" of
>>> sorted order structures which you should understand and dictate what is
>>> possible.
>>>
>>> In order to keep data sorted, a database needs to be able to see the
>>> proper sort-order of the data "all the time" not just at insertion or
>>> query time. When inserting a new record, it is compared with existing
>>> records to put it in the "right place".
>>>
>>> As a result, whether you use cassandra or a different system, I believe
>>> you are limited to one of these strategies:
>>>
>>> (a) Encrypt the data outside the database with non-order-preserving
>>> encryption, and expose some "actual data" in unencrypted form for
>>> sorting. Since the encryption ruins the sort order, some "actual data"
>>> must be exposed to sort properly. Any data you expose, even if encoded,
>>> would be your actual data, because otherwise it wouldn't sort in the
>>> right order. You can limit the amount of data you expose, creating
>>> buckets instead of proper detailed sorting. Within buckets, only the
>>> agent capable of decrypting the data would be able to properly order the
>>> data within a bucket.
>>>
>>> (b) Encrypt the data inside the database. This would expose the "actual
>>> data" to the database, allowing it to keep it in proper order. The code
>>> to handle encryption would be handled after sort-order comparisons. The
>>> code (and keys) for decryption would also be known to the database. The
>>> data would need to be decryptable by the database at all times, because
>>> the database will need to compare new data to existing data in order to
>>> perform operations correctly.
>>>
>>> (c) Use an order-preserving encryption scheme. If the encryption output
>>> is in the same order as the source-data, then the database can sort on
>>> the encrypted data and get proper sort-results. I don't know anything
>>> about this field, but doing a google search returned the following paper...
>>>
>>> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.8664&rep=rep1&type=pdf
>>> <http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.8664&rep=rep1&type=pdf>
>>>
>>> I believe these three cases represent a totalogy of what is possible in
>>> any data-storage system. So the solution you compose would involve one
>>> or more of these schemes.
>>>
>>> One might be tempted to generate some type of "ordinal value"
>>> representing the sort-order of an item. However, in order for this
>>> ordinal to be mathematically unrelated to the original data, it would
>>> have to be generated by a system which stored a copy of the entire data,
>>> which would then have to use one of the above three methods. (i.e. this
>>> approach is a chicken and egg problem)
>>
>