NumberedPartitionChunk and NumberedOverwritingPartitionChunk are not compatible
- Dominant language
- Java
- Stars
- 14.1k
- Forks
- 3.8k
- Avg merge
- 2d 58m
- Merged PRs (30d)
- 233
Description
### Affected Version
All versions since 0.16
### Description
`VersionedIntervalTimeline` consists of `PartitionHolders` each of which represents a time chunk in the timeline. Each `PartitionHolder` consists of `PartitionChunk`s which are segments in a time chunk. `PartitionHolder` has a method called `isComplete()` which is used to check whether or not the core partition set in the time chunk is fully available. This method is essential to guarantee the atomic replacement of segments which directly relates to the correctness of query results.
The logic of `isComplete()` is simple; while it iterates all partitionChunks, it checks if there are start end end chunks and each chunk abut the next chunk. Once it finds all chunks existing, `OvershadowableManager` finally checks all visible atomic update groups are fully available. This is because the completeness of the atomic update group doesn't matter until the core partition set is fully available. However, the implementation is not correct since `NumberedPartitionChunk` is not compatible to `NumberedOverwritingPartitionChunk` in `abuts()` method. As a result, all segments never become queryable in the below case.
```java
// This unit test is written based on `VersionedIntervalTimelineTest`.
@Test
public void testWhenHigherPartOfCorePartitionSetIsPartiallyOvershadowed()
{
final String intervalString = "2019-01-01/2019-01-02";
// The core partition set is [0, 3).
// Add the first segment in the core partition set.
add(intervalString, "0", makeNumbered("0", 0, 3, 0));
// Add a segment partially overshadowing the core partition set of [1, 3).
add("2019-01-01/2019-01-02", "0", makeNumberedOverwriting("0", 0, 1, 1, 3, 1, 1));
// The partitionHolder is not complete because NumberedPartitionChunk doesn't abut NumberedOverwritingPartitionChunk.
// As a result, this assert fails.
Assert.assertEquals(
ImmutableSet.of(
makeNumbered("0", 0, 3, 0).getObject(),
makeNumberedOverwriting("0", 0, 1, 1, 3, 1, 1).getObject()
),
timeline.findNonOvershadowedObjectsInInterval(Intervals.of(intervalString), Partitions.ONLY_COMPLETE)
);
}
```
To fix this bug, I think `PartitionHolder.isComplete()` should still check in two steps, first checking the availability of the core partition set, and then the availability of the atomic update group, but the first check should be fixed to include checking if atomic update groups are fully available when they overshadow any portions of the core partition set.
After this bug is fixed, the segment availability check in a partitionHolder will be done as below:
1. A partitionHolder will not be queryable until the whole core partition set is available no matter whether or not it includes partially overshadowed segments created with segment locking.
2. The availability check for the core partition set will be done by checking that all atomicUpdateGroups are fully available in the root partition range. Note that the first-generation segment also has an atomicUpdateGroup consisting of itself. If an atomicUpdateGroup overshadows the segments across the boundary of the core partition set, the core partition set will become queryable only when the whole atomicUpdateGroup is available including the non-core partition set part.
3. When an atomicUpdateGroup overshadows only non-core partition segments, it will become queryable when both the core partition set in the same time chunk and the atomicUpdateGroup itself are fully available.
Contributor guide
Research direction
Start with PartitionHolder.isComplete() and the abuts() implementations for NumberedPartitionChunk and NumberedOverwritingPartitionChunk. Reproduce the scenario in VersionedIntervalTimelineTest using testWhenHigherPartOfCorePartitionSetIsPartiallyOvershadowed, then verify that the expected segments become queryable only when the stated core and atomic update group availability conditions are met.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- databases
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100