You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@cassandra.apache.org by Michael Theroux <mt...@yahoo.com> on 2012/07/14 02:00:55 UTC

SSTable format

Hello,

I've been trying to understand in greater detail how SStables are stored, and how information is transferred between Cassandra nodes, especially when a new node is joining a cluster.

Specifically, Is information stored to SStables ordered by rowkeys?  Some of the articles I've read suggests this is the case (although it's a little vague if they actually mean that the columns are stored in order, not the rowkeys).  However, if data is stored in rowkey order, how is this achieved, as sstables are immutable?

Thanks for any insights,
-Mike 

Re: SSTable format

Posted by Dave Brosius <db...@baybroadband.net>.
While in memory cassandra calls it a MemTable, but yes sstables are 
write-once, and later combined with others into new ones thru compaction.



On 07/13/2012 09:54 PM, Michael Theroux wrote:
> Thanks for the information,
>
> So is the SStable essentially kept in memory, then sorted and written to disk on flush?  After that point, an SStable is not modified, but can be written to another SStable through compaction?
>
> -Mike
>
> On Jul 13, 2012, at 8:22 PM, Rob Coli wrote:
>
>> On Fri, Jul 13, 2012 at 5:18 PM, Dave Brosius<db...@baybroadband.net>  wrote:
>>> It depends on what partitioner you use. You should be using the
>>> RandomPartitioner, and if so, the rows are sorted by the hash of the row
>>> key. there are partitioners that sort based on the raw key value but these
>>> partitioners shouldn't be used as they have problems due to uneven
>>> partitioning of data.
>> The formal way this works in the code is that SSTables are ordered by
>> "decorated" row key, where "decoration" is only a transformation when
>> you are not using OrderedPartitioner. FWIW, in case you see that
>> "DecoratedKey" syntax while reading code..
>>
>> =Rob
>>
>> -- 
>> =Robert Coli
>> AIM&GTALK - rcoli@palominodb.com
>> YAHOO - rcoli.palominob
>> SKYPE - rcoli_palominodb
>


Re: SSTable format

Posted by Michael Theroux <mt...@yahoo.com>.
Thanks for the information,

So is the SStable essentially kept in memory, then sorted and written to disk on flush?  After that point, an SStable is not modified, but can be written to another SStable through compaction?

-Mike

On Jul 13, 2012, at 8:22 PM, Rob Coli wrote:

> On Fri, Jul 13, 2012 at 5:18 PM, Dave Brosius <db...@baybroadband.net> wrote:
>> It depends on what partitioner you use. You should be using the
>> RandomPartitioner, and if so, the rows are sorted by the hash of the row
>> key. there are partitioners that sort based on the raw key value but these
>> partitioners shouldn't be used as they have problems due to uneven
>> partitioning of data.
> 
> The formal way this works in the code is that SSTables are ordered by
> "decorated" row key, where "decoration" is only a transformation when
> you are not using OrderedPartitioner. FWIW, in case you see that
> "DecoratedKey" syntax while reading code..
> 
> =Rob
> 
> -- 
> =Robert Coli
> AIM&GTALK - rcoli@palominodb.com
> YAHOO - rcoli.palominob
> SKYPE - rcoli_palominodb


Re: SSTable format

Posted by Rob Coli <rc...@palominodb.com>.
On Fri, Jul 13, 2012 at 5:18 PM, Dave Brosius <db...@baybroadband.net> wrote:
> It depends on what partitioner you use. You should be using the
> RandomPartitioner, and if so, the rows are sorted by the hash of the row
> key. there are partitioners that sort based on the raw key value but these
> partitioners shouldn't be used as they have problems due to uneven
> partitioning of data.

The formal way this works in the code is that SSTables are ordered by
"decorated" row key, where "decoration" is only a transformation when
you are not using OrderedPartitioner. FWIW, in case you see that
"DecoratedKey" syntax while reading code..

=Rob

-- 
=Robert Coli
AIM&GTALK - rcoli@palominodb.com
YAHOO - rcoli.palominob
SKYPE - rcoli_palominodb

Re: SSTable format

Posted by prasenjit mukherjee <pr...@gmail.com>.
Appreciate the insightful replies. Understood Sylvain's argument that
having different partitioning locally and globally could create
problem in data movement.

Edward, for a given sstable in a node, why having lexicographically
closer  rows clumped together should matter ? Anyways the lookups for
a key in a sstable is based on sequential reads ( after first random
I/O ) ?

-Thanks,
Prasenjit

On Sat, Jul 14, 2012 at 6:58 PM, Edward Capriolo <ed...@gmail.com> wrote:
> There is a more subtle and profound aspect here as well. The md5
> transformation is a hash that is good at spraying data around the hash
> space evenly. For a given sstable their should be good entropy where
> if the data was not transformed it could be "clumpy" and the sorted
> string structure and indexes would not be as effective.
>
> On Sat, Jul 14, 2012 at 5:50 AM, Sylvain Lebresne <sy...@datastax.com> wrote:
>>> Any reason  rowkeys are not stored by their raws keys on a given node
>>> for RP ? I understand the partitioning across nodes should be
>>> randomized, but on a given node why they are sorted by hash of their
>>> keys and not just by the raw keys ?
>>
>> All the operation that change the topology of the cluster
>> (adding/removing/moving a node, but repair too) requires that we are able to
>> transfer data corresponding to token ranges. If rows were ordered locally by
>> their raw key rather than their token, those operation would require a node to
>> read all it's data even to transfer a small amount of it. This would be highly
>> inefficient.
>>
>> --
>> Sylvain

Re: SSTable format

Posted by Edward Capriolo <ed...@gmail.com>.
There is a more subtle and profound aspect here as well. The md5
transformation is a hash that is good at spraying data around the hash
space evenly. For a given sstable their should be good entropy where
if the data was not transformed it could be "clumpy" and the sorted
string structure and indexes would not be as effective.

On Sat, Jul 14, 2012 at 5:50 AM, Sylvain Lebresne <sy...@datastax.com> wrote:
>> Any reason  rowkeys are not stored by their raws keys on a given node
>> for RP ? I understand the partitioning across nodes should be
>> randomized, but on a given node why they are sorted by hash of their
>> keys and not just by the raw keys ?
>
> All the operation that change the topology of the cluster
> (adding/removing/moving a node, but repair too) requires that we are able to
> transfer data corresponding to token ranges. If rows were ordered locally by
> their raw key rather than their token, those operation would require a node to
> read all it's data even to transfer a small amount of it. This would be highly
> inefficient.
>
> --
> Sylvain

Re: SSTable format

Posted by Sylvain Lebresne <sy...@datastax.com>.
> Any reason  rowkeys are not stored by their raws keys on a given node
> for RP ? I understand the partitioning across nodes should be
> randomized, but on a given node why they are sorted by hash of their
> keys and not just by the raw keys ?

All the operation that change the topology of the cluster
(adding/removing/moving a node, but repair too) requires that we are able to
transfer data corresponding to token ranges. If rows were ordered locally by
their raw key rather than their token, those operation would require a node to
read all it's data even to transfer a small amount of it. This would be highly
inefficient.

--
Sylvain

Re: SSTable format

Posted by prasenjit mukherjee <pr...@gmail.com>.
>
> It depends on what partitioner you use. You should be using the
> RandomPartitioner, and if so, the rows are sorted by the hash of the row
> key. there are partitioners that sort based on the raw key value but these
> partitioners shouldn't be used as they have problems due to uneven
> partitioning of data.
>

Any reason  rowkeys are not stored by their raws keys on a given node
for RP ? I understand the partitioning across nodes should be
randomized, but on a given node why they are sorted by hash of their
keys and not just by the raw keys ?

What are we gaining by 'decorating' the keys with a random number ?  (
ref section 3 in http://wiki.apache.org/cassandra/ArchitectureSSTable
)

-Thanks,
Prasenjit

Re: SSTable format

Posted by Dave Brosius <db...@baybroadband.net>.
On 07/13/2012 08:00 PM, Michael Theroux wrote:
> Hello,
>
> I've been trying to understand in greater detail how SStables are stored, and how information is transferred between Cassandra nodes, especially when a new node is joining a cluster.
>
> Specifically, Is information stored to SStables ordered by rowkeys?  Some of the articles I've read suggests this is the case (although it's a little vague if they actually mean that the columns are stored in order, not the rowkeys).  However, if data is stored in rowkey order, how is this achieved, as sstables are immutable?
>
> Thanks for any insights,
> -Mike

It depends on what partitioner you use. You should be using the 
RandomPartitioner, and if so, the rows are sorted by the hash of the row 
key. there are partitioners that sort based on the raw key value but 
these partitioners shouldn't be used as they have problems due to uneven 
partitioning of data.

As for how this is done, remember an sstable doesn't hold all the data 
for a column family. Not only does the data for a column family exist on 
multiple servers, there are usually multiple sstable files on disk that 
represent data from one column family on one machine. So at the time the 
sstable is written, the rows that are to be put in the sstable are 
sorted, and written in sorted order. In fact the same rowkey may be 
written in multiple sstables, one sstable having one set of columns for 
the key, the other sstable having other columns for the same key.

On query for some row based on a key, cassandra is responsible for 
finding where the columns are found in which sstables (potentially 
several) and merging the results.