You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by "Peter Schuller (Created) (JIRA)" <ji...@apache.org> on 2012/03/07 19:40:57 UTC
[jira] [Created] (CASSANDRA-4011) range-based log(n) elimination of
sstables in read path
range-based log(n) elimination of sstables in read path
-------------------------------------------------------
Key: CASSANDRA-4011
URL: https://issues.apache.org/jira/browse/CASSANDRA-4011
Project: Cassandra
Issue Type: Improvement
Components: Core
Reporter: Peter Schuller
If the read path was able to eliminate sstables based on token ranges, we would avoid {{O(n)}} bloom filter checks ({{n}} being number of sstables).
Contributing motivation:
* For maximally efficient bulk-import, you tend to want a lot of small sstables to avoid having to build up huge ones during the bulk creation process.
* To avoid having to keep duplicate data when switching a data set (in a periodic bulk replace import process), keeping sstables partitioned on token range (similarly to leveled compaction) allows in-place replacement of sstables one sstable at a time.
Those two in combination would mean that you can run a bulk-import based total-dataset-replacement cluster with zero compaction and with zero disk space overhead stemming from having to have overhead for compaction.
In addition:
* For e.g. leveled compaction where we have range based partitioning anyway, {{log(n)}} is preferable to {{o(n)}}; especially if it would allow us to have more than 10 "partitions" per level. I'm not sure yet whether there are other reasons to have "only" 10, but if we can make them smaller by eliminating the {{o(n)}} behavior in the read path, individual compactions can be even smaller with leveled and you would scale even more easily with large data sets while avoiding build-up in L0.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (CASSANDRA-4011) range-based log(n) elimination
of sstables in read path
Posted by "Peter Schuller (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-4011?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13225030#comment-13225030 ]
Peter Schuller commented on CASSANDRA-4011:
-------------------------------------------
Agreed about STC. It should be relevant for leveled compaction and *no* compaction (the latter being reasonable for bulk imports).
Some background: The reason we looked into this to begin with was that we were doing 1.x style bulk import, and needed to limit the size of the sstables in the map/reduce job for heap size reasons. In combination, we have the desire to avoid doing any compaction at all. And in addition to that, the desire to replace one sstable at a time (possible with range partitioning). If we do that, we'll end up with lots of smallish sstables but with non-existent overlap, and the {{log(n)}} makes sense.
> range-based log(n) elimination of sstables in read path
> -------------------------------------------------------
>
> Key: CASSANDRA-4011
> URL: https://issues.apache.org/jira/browse/CASSANDRA-4011
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Peter Schuller
>
> If the read path was able to eliminate sstables based on token ranges, we would avoid {{O(n)}} bloom filter checks ({{n}} being number of sstables).
> Contributing motivation:
> * For maximally efficient bulk-import, you tend to want a lot of small sstables to avoid having to build up huge ones during the bulk creation process.
> * To avoid having to keep duplicate data when switching a data set (in a periodic bulk replace import process), keeping sstables partitioned on token range (similarly to leveled compaction) allows in-place replacement of sstables one sstable at a time.
> Those two in combination would mean that you can run a bulk-import based total-dataset-replacement cluster with zero compaction and with zero disk space overhead stemming from having to have overhead for compaction.
> In addition:
> * For e.g. leveled compaction where we have range based partitioning anyway, {{log(n)}} is preferable to {{o(n)}}; especially if it would allow us to have more than 10 "partitions" per level. I'm not sure yet whether there are other reasons to have "only" 10, but if we can make them smaller by eliminating the {{o(n)}} behavior in the read path, individual compactions can be even smaller with leveled and you would scale even more easily with large data sets while avoiding build-up in L0.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (CASSANDRA-4011) range-based log(n) elimination
of sstables in read path
Posted by "Jonathan Ellis (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-4011?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13224612#comment-13224612 ]
Jonathan Ellis commented on CASSANDRA-4011:
-------------------------------------------
For Leveled compaction, we do this with the IntervalTree code. For STC I doubt the range check is cheaper than the BF check, since unlike with leveled we expect significant overlapping.
> range-based log(n) elimination of sstables in read path
> -------------------------------------------------------
>
> Key: CASSANDRA-4011
> URL: https://issues.apache.org/jira/browse/CASSANDRA-4011
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Peter Schuller
>
> If the read path was able to eliminate sstables based on token ranges, we would avoid {{O(n)}} bloom filter checks ({{n}} being number of sstables).
> Contributing motivation:
> * For maximally efficient bulk-import, you tend to want a lot of small sstables to avoid having to build up huge ones during the bulk creation process.
> * To avoid having to keep duplicate data when switching a data set (in a periodic bulk replace import process), keeping sstables partitioned on token range (similarly to leveled compaction) allows in-place replacement of sstables one sstable at a time.
> Those two in combination would mean that you can run a bulk-import based total-dataset-replacement cluster with zero compaction and with zero disk space overhead stemming from having to have overhead for compaction.
> In addition:
> * For e.g. leveled compaction where we have range based partitioning anyway, {{log(n)}} is preferable to {{o(n)}}; especially if it would allow us to have more than 10 "partitions" per level. I'm not sure yet whether there are other reasons to have "only" 10, but if we can make them smaller by eliminating the {{o(n)}} behavior in the read path, individual compactions can be even smaller with leveled and you would scale even more easily with large data sets while avoiding build-up in L0.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira