You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@accumulo.apache.org by "cshannon (via GitHub)" <gi...@apache.org> on 2024/06/01 16:00:18 UTC
[PR] Implement estimateOverlappingEntries in fenced files [accumulo]
cshannon opened a new pull request, #4626:
URL: https://github.com/apache/accumulo/pull/4626
This adds support for estimating overlapping entries in fenced RFiles. This works by clipping the KeyExtent provided with the fenced file range to find the overlapping section to use for computing the estimated entries.
A new clip() method was added to KeyExtent to make this easier to generate the new KeyExtent. Also, the range required must be the same type that KeyExtent uses when calling toDataRange() (a more narrow row range) so that we can compute the overlapping section correctly. Fenced files allow other ranges but with our current use case fenced files will only be derived from KeyExtents so this should be fine. (Such as when doing merge operations)
I also added some tests, including missing RFile tests for estimating overlapping entries on non-fenced files.
This closes #4611
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@accumulo.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement estimateOverlappingEntries in fenced files [accumulo]
Posted by "keith-turner (via GitHub)" <gi...@apache.org>.
keith-turner commented on code in PR #4626:
URL: https://github.com/apache/accumulo/pull/4626#discussion_r1623246930
##########
core/src/main/java/org/apache/accumulo/core/dataImpl/KeyExtent.java:
##########
@@ -388,6 +393,70 @@ public Range toMetaRange() {
return new Range(metadataPrevRow, prevEndRow() == null, toMetaRow(), true);
}
+ /**
+ * Creates a KeyExtent which represents the intersection of this KeyExtent and the passed in
+ * range.
+ * <p>
+ * <b>Note:</b> The range provided must be a range that is derived from a KeyExtent. This means
+ * the range must be in the format of a row range and also requires an exclusive start key, which
+ * is the format that {@link #toDataRange()} uses
+ *
+ * @param range range to clip to
+ * @return the intersection of this KeyExtent and the given range
+ * @throws IllegalArgumentException if the KeyExtent and range do not overlap
+ */
+ public KeyExtent clip(Range range) {
+ return clip(range, false);
+ }
+
+ /**
+ * Creates a KeyExtent which represents the intersection of this KeyExtent and the passed in
+ * range. Unlike {@link #clip(Range)}, this method can optionally return null if the given range
+ * and this KeyExtent do not overlap, instead of throwing an exception. The returnNullIfDisjoint
+ * parameter controls this behavior.
+ * <p>
+ * <b>Note:</b> The range provided must be a range that is derived from a KeyExtent. This means
+ * the range must be in the format of a row range and also requires an exclusive start key, which
+ * is the format that {@link #toDataRange()} uses
+ *
+ * @param range range to clip to
+ * @param returnNullIfDisjoint true to return null if ranges are disjoint, false to throw an
+ * exception
+ * @return the intersection of this KeyExtent and the given range, or null if given range and this
+ * KeyExtent do not overlap and returnNullIfDisjoint is true
+ * @throws IllegalArgumentException if the KeyExtent and range does not overlap and
+ * returnNullIfDisjoint is false
+ *
+ * @see KeyExtent#clip(Range)
+ **/
+ public KeyExtent clip(Range range, boolean returnNullIfDisjoint) {
+ // A standard row range only requires an exclusive key but
+ // KeyExtent has a narrower definition of a row range and toDataRange()
+ // will always create exclusive start keys as well,
+ // so we need to restrict the range further
+ requireRowRange(range);
+ if (!range.isInfiniteStartKey()) {
+ Preconditions.checkArgument(isExclusiveKey(range.getStartKey()),
Review Comment:
If want requireRowRange to be really generic then should also move the isExclusiveKey check for the end key outside to this function. Looking at the range constructors for rows, it does not always append a 0x00 to the end row key for all row ranges.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@accumulo.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement estimateOverlappingEntries in fenced files [accumulo]
Posted by "keith-turner (via GitHub)" <gi...@apache.org>.
keith-turner commented on code in PR #4626:
URL: https://github.com/apache/accumulo/pull/4626#discussion_r1623246571
##########
core/src/main/java/org/apache/accumulo/core/util/RangeUtil.java:
##########
@@ -0,0 +1,59 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.accumulo.core.util;
+
+import org.apache.accumulo.core.data.ByteSequence;
+import org.apache.accumulo.core.data.Key;
+import org.apache.accumulo.core.data.Range;
+
+import com.google.common.base.Preconditions;
+
+public class RangeUtil {
Review Comment:
Could use the following name
```suggestion
public class RowRangeUtil {
```
##########
core/src/test/java/org/apache/accumulo/core/data/KeyExtentTest.java:
##########
@@ -181,4 +182,42 @@ private KeyExtent writeAndReadFields(KeyExtent in) throws IOException {
return KeyExtent.readFrom(new DataInputStream(bais));
}
+ @Test
+ public void testClip() {
+ // Test extent will null end/prevEnd and infinite range matches original
+ ke = new KeyExtent(TableId.of("1"), null, null);
+ Range range = new Range();
+ KeyExtent expected = ke;
+ KeyExtent clipped = ke.clip(range);
+ assertEquals(expected, clipped);
+
+ // Test extent with null end/prevEnd with a range, should match the range
+ expected = new KeyExtent(TableId.of("1"), new Text("r_0001"), new Text("r_0000"));
+ ke = new KeyExtent(TableId.of("1"), null, null);
+ range = new Range("r_0000", false, "r_0001", true);
+ clipped = ke.clip(range);
+ assertEquals(expected, clipped);
+
+ // Test resulting extent is narrowed, the overlapping rows are 4 - 7
+ expected = new KeyExtent(TableId.of("1"), new Text("r_0007"), new Text("r_0003"));
+ ke = new KeyExtent(TableId.of("1"), new Text("r_0007"), new Text("r_0000"));
+ range = new Range("r_0003", false, "r_0009", true);
+ clipped = ke.clip(range);
+ assertEquals(expected, clipped);
+
+ // Test disjoint
+ ke = new KeyExtent(TableId.of("1"), new Text("r_0007"), new Text("r_0005"));
+ range = new Range("r_0002", false, "r_0004", true);
+ clipped = ke.clip(range, true);
+ assertNull(clipped);
+ final Range r = range;
+ assertThrows(IllegalArgumentException.class, () -> ke.clip(r));
+
+ // Invalid row ranges
+ assertThrows(IllegalArgumentException.class,
+ () -> ke.clip(new Range("r_0002", true, "r_0004", true)));
+ assertThrows(IllegalArgumentException.class, () -> ke
+ .clip(new Range(new Key("r_0002", "cf_0002"), false, new Key("r_0003", "cf_0003"), true)));
Review Comment:
Could add an additional test where the start row is empty string, this would exercise the code in isExclusiveKey that checks the key length.
##########
core/src/main/java/org/apache/accumulo/core/dataImpl/KeyExtent.java:
##########
@@ -388,6 +393,70 @@ public Range toMetaRange() {
return new Range(metadataPrevRow, prevEndRow() == null, toMetaRow(), true);
}
+ /**
+ * Creates a KeyExtent which represents the intersection of this KeyExtent and the passed in
+ * range.
+ * <p>
+ * <b>Note:</b> The range provided must be a range that is derived from a KeyExtent. This means
+ * the range must be in the format of a row range and also requires an exclusive start key, which
+ * is the format that {@link #toDataRange()} uses
+ *
+ * @param range range to clip to
+ * @return the intersection of this KeyExtent and the given range
+ * @throws IllegalArgumentException if the KeyExtent and range do not overlap
+ */
+ public KeyExtent clip(Range range) {
+ return clip(range, false);
+ }
+
+ /**
+ * Creates a KeyExtent which represents the intersection of this KeyExtent and the passed in
+ * range. Unlike {@link #clip(Range)}, this method can optionally return null if the given range
+ * and this KeyExtent do not overlap, instead of throwing an exception. The returnNullIfDisjoint
+ * parameter controls this behavior.
+ * <p>
+ * <b>Note:</b> The range provided must be a range that is derived from a KeyExtent. This means
+ * the range must be in the format of a row range and also requires an exclusive start key, which
+ * is the format that {@link #toDataRange()} uses
+ *
+ * @param range range to clip to
+ * @param returnNullIfDisjoint true to return null if ranges are disjoint, false to throw an
+ * exception
+ * @return the intersection of this KeyExtent and the given range, or null if given range and this
+ * KeyExtent do not overlap and returnNullIfDisjoint is true
+ * @throws IllegalArgumentException if the KeyExtent and range does not overlap and
+ * returnNullIfDisjoint is false
+ *
+ * @see KeyExtent#clip(Range)
+ **/
+ public KeyExtent clip(Range range, boolean returnNullIfDisjoint) {
+ // A standard row range only requires an exclusive key but
+ // KeyExtent has a narrower definition of a row range and toDataRange()
+ // will always create exclusive start keys as well,
+ // so we need to restrict the range further
+ requireRowRange(range);
+ if (!range.isInfiniteStartKey()) {
+ Preconditions.checkArgument(isExclusiveKey(range.getStartKey()),
Review Comment:
If want requireRowRange to be really generic then should also move the isExclusiveKey check for the end key outside to this function. Looking at the range constructors for rows, it does not always append a 0x00 to the row key for all row ranges.
##########
core/src/test/java/org/apache/accumulo/core/file/rfile/RFileTest.java:
##########
@@ -1512,6 +1512,39 @@ public void testReseekUnconsumed() throws Exception {
trf.closeReader();
}
+ @Test
+ public void testEstimateOverlappingEntries() throws IOException {
+ TestRFile trf = new TestRFile(conf);
+ // lower block sizes so estimates are closer
+ trf.openWriter(true, 100, 100);
+
+ // generate 1024 entries
+ int count = 0;
+ for (int row = 0; row < 4; row++) {
Review Comment:
Could this code to write data be pushed up into AbstractRfileTest so it could be shared w/ FencedRfileTest?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@accumulo.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement estimateOverlappingEntries in fenced files [accumulo]
Posted by "cshannon (via GitHub)" <gi...@apache.org>.
cshannon commented on PR #4626:
URL: https://github.com/apache/accumulo/pull/4626#issuecomment-2143570603
The sunny ITs all passed for main and also when merging forward into elasticity. I will keep an eye on the full ITs and fix anything else that might have broken as there were some validation changed in this PR that could require some more test fixes.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@accumulo.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement estimateOverlappingEntries in fenced files [accumulo]
Posted by "cshannon (via GitHub)" <gi...@apache.org>.
cshannon commented on code in PR #4626:
URL: https://github.com/apache/accumulo/pull/4626#discussion_r1623249720
##########
core/src/main/java/org/apache/accumulo/core/dataImpl/KeyExtent.java:
##########
@@ -388,6 +393,70 @@ public Range toMetaRange() {
return new Range(metadataPrevRow, prevEndRow() == null, toMetaRow(), true);
}
+ /**
+ * Creates a KeyExtent which represents the intersection of this KeyExtent and the passed in
+ * range.
+ * <p>
+ * <b>Note:</b> The range provided must be a range that is derived from a KeyExtent. This means
+ * the range must be in the format of a row range and also requires an exclusive start key, which
+ * is the format that {@link #toDataRange()} uses
+ *
+ * @param range range to clip to
+ * @return the intersection of this KeyExtent and the given range
+ * @throws IllegalArgumentException if the KeyExtent and range do not overlap
+ */
+ public KeyExtent clip(Range range) {
+ return clip(range, false);
+ }
+
+ /**
+ * Creates a KeyExtent which represents the intersection of this KeyExtent and the passed in
+ * range. Unlike {@link #clip(Range)}, this method can optionally return null if the given range
+ * and this KeyExtent do not overlap, instead of throwing an exception. The returnNullIfDisjoint
+ * parameter controls this behavior.
+ * <p>
+ * <b>Note:</b> The range provided must be a range that is derived from a KeyExtent. This means
+ * the range must be in the format of a row range and also requires an exclusive start key, which
+ * is the format that {@link #toDataRange()} uses
+ *
+ * @param range range to clip to
+ * @param returnNullIfDisjoint true to return null if ranges are disjoint, false to throw an
+ * exception
+ * @return the intersection of this KeyExtent and the given range, or null if given range and this
+ * KeyExtent do not overlap and returnNullIfDisjoint is true
+ * @throws IllegalArgumentException if the KeyExtent and range does not overlap and
+ * returnNullIfDisjoint is false
+ *
+ * @see KeyExtent#clip(Range)
+ **/
+ public KeyExtent clip(Range range, boolean returnNullIfDisjoint) {
+ // A standard row range only requires an exclusive key but
+ // KeyExtent has a narrower definition of a row range and toDataRange()
+ // will always create exclusive start keys as well,
+ // so we need to restrict the range further
+ requireRowRange(range);
+ if (!range.isInfiniteStartKey()) {
+ Preconditions.checkArgument(isExclusiveKey(range.getStartKey()),
Review Comment:
Well, the original intent of requireRowRange was for no-chop merge as there were issues when not requiring that. I don't remember off the top of my head but it was added for a reason to require the end key to be exclusive when we store entries in metadata. So if we remove the exclusive key check then we'd need to add something to still enforce that for TabletFile and StoredTabletFile i think.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@accumulo.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement estimateOverlappingEntries in fenced files [accumulo]
Posted by "cshannon (via GitHub)" <gi...@apache.org>.
cshannon commented on code in PR #4626:
URL: https://github.com/apache/accumulo/pull/4626#discussion_r1623249852
##########
core/src/test/java/org/apache/accumulo/core/file/rfile/RFileTest.java:
##########
@@ -1512,6 +1512,39 @@ public void testReseekUnconsumed() throws Exception {
trf.closeReader();
}
+ @Test
+ public void testEstimateOverlappingEntries() throws IOException {
+ TestRFile trf = new TestRFile(conf);
+ // lower block sizes so estimates are closer
+ trf.openWriter(true, 100, 100);
+
+ // generate 1024 entries
+ int count = 0;
+ for (int row = 0; row < 4; row++) {
Review Comment:
We could, the only reason why I didn't was that the fencing test already has something to do a similar thing but I could likely refactor it to have it shared in the Abstract test (or at least try to)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@accumulo.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement estimateOverlappingEntries in fenced files [accumulo]
Posted by "cshannon (via GitHub)" <gi...@apache.org>.
cshannon commented on code in PR #4626:
URL: https://github.com/apache/accumulo/pull/4626#discussion_r1623264672
##########
core/src/test/java/org/apache/accumulo/core/file/rfile/RFileTest.java:
##########
@@ -1512,6 +1512,39 @@ public void testReseekUnconsumed() throws Exception {
trf.closeReader();
}
+ @Test
+ public void testEstimateOverlappingEntries() throws IOException {
+ TestRFile trf = new TestRFile(conf);
+ // lower block sizes so estimates are closer
+ trf.openWriter(true, 100, 100);
+
+ // generate 1024 entries
+ int count = 0;
+ for (int row = 0; row < 4; row++) {
Review Comment:
I think i'll leave things how they are for now since the fenced test uses another method already to write the test data
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@accumulo.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement estimateOverlappingEntries in fenced files [accumulo]
Posted by "cshannon (via GitHub)" <gi...@apache.org>.
cshannon commented on PR #4626:
URL: https://github.com/apache/accumulo/pull/4626#issuecomment-2143562038
requireRowRange has been renamed to `requireKeyExtentData` range and the checks have been more narrowed. Everywhere we are using fencing (currently) the ranges are derived from KeyExtent so it makes sense to validate. The actual RFiles can still use ranges that are not KeyExtent data ranges but `StoredTabletFile` will verify the correct format and we require that format when computing estimated overlapping entries
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@accumulo.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement estimateOverlappingEntries in fenced files [accumulo]
Posted by "cshannon (via GitHub)" <gi...@apache.org>.
cshannon merged PR #4626:
URL: https://github.com/apache/accumulo/pull/4626
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@accumulo.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement estimateOverlappingEntries in fenced files [accumulo]
Posted by "keith-turner (via GitHub)" <gi...@apache.org>.
keith-turner commented on code in PR #4626:
URL: https://github.com/apache/accumulo/pull/4626#discussion_r1623250653
##########
core/src/test/java/org/apache/accumulo/core/file/rfile/RFileTest.java:
##########
@@ -1512,6 +1512,39 @@ public void testReseekUnconsumed() throws Exception {
trf.closeReader();
}
+ @Test
+ public void testEstimateOverlappingEntries() throws IOException {
+ TestRFile trf = new TestRFile(conf);
+ // lower block sizes so estimates are closer
+ trf.openWriter(true, 100, 100);
+
+ // generate 1024 entries
+ int count = 0;
+ for (int row = 0; row < 4; row++) {
Review Comment:
Please ignore the comment if it does not make sense. I was not sure about the class hierarchy w/ the test and code sharing.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@accumulo.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement estimateOverlappingEntries in fenced files [accumulo]
Posted by "cshannon (via GitHub)" <gi...@apache.org>.
cshannon commented on PR #4626:
URL: https://github.com/apache/accumulo/pull/4626#issuecomment-2143897756
> The sunny ITs all passed for main and also when merging forward into elasticity. I will keep an eye on the full ITs and fix anything else that might have broken as there were some validation changed in this PR that could require some more test fixes.
The full IT build had 7 test failures but all are quick fixes. Fixed in 73125e9
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@accumulo.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org