Details
-
Bug
-
Status: Resolved
-
Major
-
Resolution: Duplicate
-
None
-
None
-
None
Description
Fluo's internal schema uses the first 4 bits of the timestamp to store different types of information per column. These first 4 bits divide the timestamp space up into 16 ranges. Fluo has server side iterators that consider information in one of these 16 ranges and then seek forward to another of the 16 ranges.
Unfortunately, Accumulo's built in iterator that processes delete marker makes seeking within the timestamps of a column an O(N^2) operation. This is because of the way deletes work in Accumulo. A delete marker for timestamp X in Accumulo deletes anything with a timestamp <= X.
When seeking to timestamp Y, the Accumulo iterator that handles deletes will scan from MAX_LONG to Y looking for any deletes that may keep you from seeing data at timestamp Y. The following example shows what the delete iterator will do when a user iterator does some seeks.
- User iterator seeks to stamp 1,000,000. This causes the delete iter to scan from MAX_LONG to 1,000,000 looking for delete markers.
- User iterator seeks to stamp 900,000. This causes the delete iter to scan from MAX_LONG to 900,000 looking for delete markers.
- User iterator seeks to stamp 500,000. This causes the delete iter to scan from MAX_LONG to 500,000 looking for delete markers.
So Fluo can seek efficiently, it has done some serious shenanigans using reflection to remove the DeleteIterator. The great work being done on ACCUMULO-3079 will likely break this crazy reflection code. So I would like to make a change to upstream Accumulo that allows efficient seeking in the timestamp range. I have thought of the following two possible solutions.
- Make the DeleteIterator stateful so that it remember what ranges it has scanned for deletes. I don't really like this solution because it will add expense to every seek in Accumulo for an edge case.
- Make it possible to create tables with an exact delete behavior. Meaning a delete for timestamp X will only delete an existing row column with that exact timestamp. This option could only be chosen at table creation time and could not be changed. For this delete behavior, the delete iterator doesnot need to scan for every seek.
Are there other possible solutions?
