You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by "Jonathan Ellis (JIRA)" <ji...@apache.org> on 2009/06/09 00:10:07 UTC
[jira] Created: (CASSANDRA-223) time-based slicing does not work
correctly w/ "historial" memtables
time-based slicing does not work correctly w/ "historial" memtables
-------------------------------------------------------------------
Key: CASSANDRA-223
URL: https://issues.apache.org/jira/browse/CASSANDRA-223
Project: Cassandra
Issue Type: Bug
Reporter: Jonathan Ellis
TimeFilter assumes that it is done as soon as it finds a column stamped earlier than what it is filtering on, but when you have a group of "historical" memtables whose columns were written in an arbitrary order this is not a safe assumption.
It is not even a safe assumption when dealing with a single memtable + sstable pair, as the attached new test shows.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-223) time-based slicing does not work
correctly w/ "historial" memtables
Posted by "Jun Rao (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-223?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12718094#action_12718094 ]
Jun Rao commented on CASSANDRA-223:
-----------------------------------
get_column is also designed to stop iterating SSTables as soon as the requested column is found. Therefore, it could suffer from the above problems too.
> time-based slicing does not work correctly w/ "historial" memtables
> -------------------------------------------------------------------
>
> Key: CASSANDRA-223
> URL: https://issues.apache.org/jira/browse/CASSANDRA-223
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Attachments: 223.patch
>
>
> TimeFilter assumes that it is done as soon as it finds a column stamped earlier than what it is filtering on, but when you have a group of "historical" memtables whose columns were written in an arbitrary order this is not a safe assumption.
> It is not even a safe assumption when dealing with a single memtable + sstable pair, as the attached new test shows.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-223) time-based slicing does not work
correctly w/ "historial" memtables
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-223?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jonathan Ellis updated CASSANDRA-223:
-------------------------------------
Attachment: 223-2-v2.patch
oops. already had to rebase.
> time-based slicing does not work correctly w/ "historial" memtables
> -------------------------------------------------------------------
>
> Key: CASSANDRA-223
> URL: https://issues.apache.org/jira/browse/CASSANDRA-223
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Attachments: 223-2-v2.patch, 223-2.patch, 223.patch
>
>
> TimeFilter assumes that it is done as soon as it finds a column stamped earlier than what it is filtering on, but when you have a group of "historical" memtables whose columns were written in an arbitrary order this is not a safe assumption.
> It is not even a safe assumption when dealing with a single memtable + sstable pair, as the attached new test shows.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-223) time-based slicing does not work
correctly w/ "historial" memtables
Posted by "Jun Rao (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-223?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12717749#action_12717749 ]
Jun Rao commented on CASSANDRA-223:
-----------------------------------
The assumption that columns in an SSTable with a larger file name always have more recent timestamp also breaks in the following cases:
1. after SSTables are compacted (since the compaction works on a group of SSTables at a time)
2. hinted data is delivered
3. columns fixed through read repairs
> time-based slicing does not work correctly w/ "historial" memtables
> -------------------------------------------------------------------
>
> Key: CASSANDRA-223
> URL: https://issues.apache.org/jira/browse/CASSANDRA-223
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Attachments: 223.patch
>
>
> TimeFilter assumes that it is done as soon as it finds a column stamped earlier than what it is filtering on, but when you have a group of "historical" memtables whose columns were written in an arbitrary order this is not a safe assumption.
> It is not even a safe assumption when dealing with a single memtable + sstable pair, as the attached new test shows.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-223) time-based slicing does not work
correctly w/ "historial" memtables
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-223?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jonathan Ellis updated CASSANDRA-223:
-------------------------------------
Attachment: 223.patch
> time-based slicing does not work correctly w/ "historial" memtables
> -------------------------------------------------------------------
>
> Key: CASSANDRA-223
> URL: https://issues.apache.org/jira/browse/CASSANDRA-223
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Attachments: 223.patch
>
>
> TimeFilter assumes that it is done as soon as it finds a column stamped earlier than what it is filtering on, but when you have a group of "historical" memtables whose columns were written in an arbitrary order this is not a safe assumption.
> It is not even a safe assumption when dealing with a single memtable + sstable pair, as the attached new test shows.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-223) time-based slicing does not work
correctly w/ "historial" memtables
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-223?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12722657#action_12722657 ]
Jonathan Ellis commented on CASSANDRA-223:
------------------------------------------
I came to the same conclusion.
One partial answer to the files-to-read is to change compaction to guarantee log(n) sstable files instead of the current ad-hoc behavior, where n is the maximum sstable "generation" number. (Where "generation" is the number of compactions done.)
For each CF, when you flush, you compact until there is nothing already at the same generation to compact with. For example,
flush 1: nothing to merge. memtable becomes sstable-gen0
flush 2: there is already a sstable-gen0 so you merge. now you have sstable-gen1
flush 3: no gen0, so you store there. now you have sstable-gen0, sstable-gen1
flush 4: 0 and 1 exist, so you compact (with the new one) to sstable-gen2
etc.
Generation tracking can be done in the sstable filename.
> time-based slicing does not work correctly w/ "historial" memtables
> -------------------------------------------------------------------
>
> Key: CASSANDRA-223
> URL: https://issues.apache.org/jira/browse/CASSANDRA-223
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Attachments: 223.patch
>
>
> TimeFilter assumes that it is done as soon as it finds a column stamped earlier than what it is filtering on, but when you have a group of "historical" memtables whose columns were written in an arbitrary order this is not a safe assumption.
> It is not even a safe assumption when dealing with a single memtable + sstable pair, as the attached new test shows.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-223) time-based slicing does not work
correctly w/ "historial" memtables
Posted by "Michael Greene (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-223?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Michael Greene updated CASSANDRA-223:
-------------------------------------
Component/s: Core
> time-based slicing does not work correctly w/ "historial" memtables
> -------------------------------------------------------------------
>
> Key: CASSANDRA-223
> URL: https://issues.apache.org/jira/browse/CASSANDRA-223
> Project: Cassandra
> Issue Type: Bug
> Components: Core
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Fix For: 0.4
>
> Attachments: 223-2-v2.patch, 223-2.patch, 223.patch
>
>
> TimeFilter assumes that it is done as soon as it finds a column stamped earlier than what it is filtering on, but when you have a group of "historical" memtables whose columns were written in an arbitrary order this is not a safe assumption.
> It is not even a safe assumption when dealing with a single memtable + sstable pair, as the attached new test shows.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-223) time-based slicing does not work
correctly w/ "historial" memtables
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-223?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12717676#action_12717676 ]
Jonathan Ellis commented on CASSANDRA-223:
------------------------------------------
Thinking about it more, the current behavior is sort of reasonable if you assume that timestamp values are strictly increasing. I prefer not to rely on this because it's impossible to sync clocks with perfect accuracy, but it's a reasonable optimization to make and consistent with the rest of Cassandra's design.
In this case though, clock sync problems can lead to permanently inconsistent behavior -- different queries will not agree on what data the node contains.
> time-based slicing does not work correctly w/ "historial" memtables
> -------------------------------------------------------------------
>
> Key: CASSANDRA-223
> URL: https://issues.apache.org/jira/browse/CASSANDRA-223
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Attachments: 223.patch
>
>
> TimeFilter assumes that it is done as soon as it finds a column stamped earlier than what it is filtering on, but when you have a group of "historical" memtables whose columns were written in an arbitrary order this is not a safe assumption.
> It is not even a safe assumption when dealing with a single memtable + sstable pair, as the attached new test shows.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-223) time-based slicing does not work
correctly w/ "historial" memtables
Posted by "Jun Rao (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-223?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12722753#action_12722753 ]
Jun Rao commented on CASSANDRA-223:
-----------------------------------
Well, as for SSTable compaction, we probably can learn from Lucene. Overall, Lucene tries to keep on the order of log(n) index segments, where n is the total number of segments generated. It does that by keeping merging index segments (up to a merging factor) of about the same size. The current compaction code in cassandra seems to try to do that too. It's worth revisiting it though.
> time-based slicing does not work correctly w/ "historial" memtables
> -------------------------------------------------------------------
>
> Key: CASSANDRA-223
> URL: https://issues.apache.org/jira/browse/CASSANDRA-223
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Attachments: 223.patch
>
>
> TimeFilter assumes that it is done as soon as it finds a column stamped earlier than what it is filtering on, but when you have a group of "historical" memtables whose columns were written in an arbitrary order this is not a safe assumption.
> It is not even a safe assumption when dealing with a single memtable + sstable pair, as the attached new test shows.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-223) time-based slicing does not work
correctly w/ "historial" memtables
Posted by "Jun Rao (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-223?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12722651#action_12722651 ]
Jun Rao commented on CASSANDRA-223:
-----------------------------------
Since it's hard to guarantee any timestamp ordering among memtable and sstables because of the reasons listed above, the only way that we can get the correct answer is do look at the memtable and ALL sstables (this is what HBase has been doing). This affects the following APIs.
get_column
get_slice_by_names
get_slice_by_name_range
get_slice_since
The implication is that those APIs will potentially run slower since there are more files to read. One can probably tune the performance by setting a proper compaction policy.
> time-based slicing does not work correctly w/ "historial" memtables
> -------------------------------------------------------------------
>
> Key: CASSANDRA-223
> URL: https://issues.apache.org/jira/browse/CASSANDRA-223
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Attachments: 223.patch
>
>
> TimeFilter assumes that it is done as soon as it finds a column stamped earlier than what it is filtering on, but when you have a group of "historical" memtables whose columns were written in an arbitrary order this is not a safe assumption.
> It is not even a safe assumption when dealing with a single memtable + sstable pair, as the attached new test shows.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-223) time-based slicing does not work
correctly w/ "historial" memtables
Posted by "Jun Rao (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-223?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12724612#action_12724612 ]
Jun Rao commented on CASSANDRA-223:
-----------------------------------
The patch looks good to me.
> time-based slicing does not work correctly w/ "historial" memtables
> -------------------------------------------------------------------
>
> Key: CASSANDRA-223
> URL: https://issues.apache.org/jira/browse/CASSANDRA-223
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Attachments: 223-2-v2.patch, 223-2.patch, 223.patch
>
>
> TimeFilter assumes that it is done as soon as it finds a column stamped earlier than what it is filtering on, but when you have a group of "historical" memtables whose columns were written in an arbitrary order this is not a safe assumption.
> It is not even a safe assumption when dealing with a single memtable + sstable pair, as the attached new test shows.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-223) time-based slicing does not work
correctly w/ "historial" memtables
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-223?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jonathan Ellis updated CASSANDRA-223:
-------------------------------------
Attachment: 223-2.patch
add brute-force fix for the bug: always merge in results from all memtables and sstables. (this is what bigtable does.)
> time-based slicing does not work correctly w/ "historial" memtables
> -------------------------------------------------------------------
>
> Key: CASSANDRA-223
> URL: https://issues.apache.org/jira/browse/CASSANDRA-223
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Attachments: 223-2.patch, 223.patch
>
>
> TimeFilter assumes that it is done as soon as it finds a column stamped earlier than what it is filtering on, but when you have a group of "historical" memtables whose columns were written in an arbitrary order this is not a safe assumption.
> It is not even a safe assumption when dealing with a single memtable + sstable pair, as the attached new test shows.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.