This is an automated email from the ASF dual-hosted git repository.
dlmarion pushed a commit to branch 2.1
in repository https://gitbox.apache.org/repos/asf/accumulo.git
The following commit(s) were added to refs/heads/2.1 by this push:
new 56c186df99 GC algorithm changes to reduce complexity and object
allocation (#6636)
56c186df99 is described below
commit 56c186df99650d5bb930bfb1214df85b369e861e
Author: Dave Marion <[email protected]>
AuthorDate: Tue Nov 10 11:42:50 2026 -0500
GC algorithm changes to reduce complexity and object allocation (#6636)
Assisted-By: OpenAI GPT-6 Luna
---
.../accumulo/gc/GarbageCollectionAlgorithm.java | 170 ++++++++++++++++-----
.../apache/accumulo/gc/GarbageCollectionTest.java | 14 +-
2 files changed, 136 insertions(+), 48 deletions(-)
diff --git
a/server/gc/src/main/java/org/apache/accumulo/gc/GarbageCollectionAlgorithm.java
b/server/gc/src/main/java/org/apache/accumulo/gc/GarbageCollectionAlgorithm.java
index 1d5863ca9e..a484b4aafd 100644
---
a/server/gc/src/main/java/org/apache/accumulo/gc/GarbageCollectionAlgorithm.java
+++
b/server/gc/src/main/java/org/apache/accumulo/gc/GarbageCollectionAlgorithm.java
@@ -18,9 +18,6 @@
*/
package org.apache.accumulo.gc;
-import static java.util.Arrays.stream;
-import static java.util.function.Predicate.not;
-
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
@@ -28,7 +25,6 @@ import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
-import java.util.Locale;
import java.util.Map.Entry;
import java.util.Set;
import java.util.SortedMap;
@@ -71,54 +67,130 @@ public class GarbageCollectionAlgorithm {
* the original path. This method will also remove prefixed relative paths
like ../4/t0/F000.rf
* and return 4/t0/F000.rf. It also strips out empty tokens from paths like
* hdfs://foo.com:6000/accumulo/tables/4//t0//F001.rf returning 4/t0/F001.rf.
+ *
+ * @return the normalized table-relative path: {@code
tableId/tabletDir/fileName} for a file or
+ * {@code tableId/tabletDir} for a directory
*/
private String makeRelative(String path, int expectedLen) {
- String relPath = path;
-
// remove prefixed old relative path
- if (relPath.startsWith("../")) {
- relPath = relPath.substring(3);
- }
-
- // remove trailing slash
- while (relPath.endsWith("/")) {
- relPath = relPath.substring(0, relPath.length() - 1);
- }
+ int position = path.startsWith("../") ? 3 : 0;
+ int componentCount = 0;
+ int start0 = 0;
+ int end0 = 0;
+ int start1 = 0;
+ int end1 = 0;
+ int start2 = 0;
+ int end2 = 0;
+ int start3 = 0;
+ int end3 = 0;
+ boolean hasColon = false;
+
+ // Scan once, ignoring empty components and retaining only the last four
ranges.
+ while (position < path.length()) {
+ while (position < path.length() && path.charAt(position) == '/') {
+ position++;
+ }
+ if (position == path.length()) {
+ break;
+ }
- // remove beginning slash
- while (relPath.startsWith("/")) {
- relPath = relPath.substring(1);
+ int componentStart = position;
+ while (position < path.length() && path.charAt(position) != '/') {
+ if (path.charAt(position) == ':') {
+ hasColon = true;
+ }
+ position++;
+ }
+ int componentEnd = position;
+
+ start0 = start1;
+ end0 = end1;
+ start1 = start2;
+ end1 = end2;
+ start2 = start3;
+ end2 = end3;
+ start3 = componentStart;
+ end3 = componentEnd;
+ componentCount++;
}
- // Handle paths like a//b///c by dropping the empty tokens.
- String[] tokens =
stream(relPath.split("/")).filter(not(""::equals)).toArray(String[]::new);
+ int outputStart1;
+ int outputEnd1;
+ int outputStart2;
+ int outputEnd2;
+ int outputStart3 = 0;
+ int outputEnd3 = 0;
+ int outputComponents;
- if (tokens.length > 3 && path.contains(":")) {
+ if (componentCount > 3 && hasColon) {
// full file path like hdfs://foo:6000/accumulo/tables/4/t0/F000.rf
- if (tokens[tokens.length - 4].equals(Constants.TABLE_DIR)
+ int tablesLength = end0 - start0;
+ if (tablesLength == Constants.TABLE_DIR.length()
+ && path.regionMatches(start0, Constants.TABLE_DIR, 0, tablesLength)
&& (expectedLen == 0 || expectedLen == 3)) {
- // return the last 3 tokens after tables, like 4/t0/F000.rf
- relPath = tokens[tokens.length - 3] + "/" + tokens[tokens.length - 2]
+ "/"
- + tokens[tokens.length - 1];
- } else if (tokens[tokens.length - 3].equals(Constants.TABLE_DIR)
- && (expectedLen == 0 || expectedLen == 2)) {
- // return the last 2 tokens after tables, like 4/t0
- relPath = tokens[tokens.length - 2] + "/" + tokens[tokens.length - 1];
+ // return the last 3 components after tables, like 4/t0/F000.rf
+ outputStart1 = start1;
+ outputEnd1 = end1;
+ outputStart2 = start2;
+ outputEnd2 = end2;
+ outputStart3 = start3;
+ outputEnd3 = end3;
+ outputComponents = 3;
} else {
- throw new IllegalArgumentException("Failed to make path relative. Bad
reference: " + path);
+ int directoryTablesLength = end1 - start1;
+ if (directoryTablesLength == Constants.TABLE_DIR.length()
+ && path.regionMatches(start1, Constants.TABLE_DIR, 0,
directoryTablesLength)
+ && (expectedLen == 0 || expectedLen == 2)) {
+ // return the last 2 components after tables, like 4/t0
+ outputStart1 = start2;
+ outputEnd1 = end2;
+ outputStart2 = start3;
+ outputEnd2 = end3;
+ outputComponents = 2;
+ } else {
+ throw new IllegalArgumentException(
+ "Failed to make path relative. Bad reference: " + path);
+ }
}
- } else if (tokens.length == 3 && (expectedLen == 0 || expectedLen == 3)
- && !path.contains(":")) {
+ } else if (componentCount == 3 && (expectedLen == 0 || expectedLen == 3)
&& !hasColon) {
// we already have a relative path so return it, like 4/t0/F000.rf
- relPath = tokens[0] + "/" + tokens[1] + "/" + tokens[2];
- } else if (tokens.length == 2 && (expectedLen == 0 || expectedLen == 2)
- && !path.contains(":")) {
- // return the last 2 tokens of the relative path, like 4/t0
- relPath = tokens[0] + "/" + tokens[1];
+ outputStart1 = start1;
+ outputEnd1 = end1;
+ outputStart2 = start2;
+ outputEnd2 = end2;
+ outputStart3 = start3;
+ outputEnd3 = end3;
+ outputComponents = 3;
+ } else if (componentCount == 2 && (expectedLen == 0 || expectedLen == 2)
&& !hasColon) {
+ // return the last 2 components of the relative path, like 4/t0
+ outputStart1 = start2;
+ outputEnd1 = end2;
+ outputStart2 = start3;
+ outputEnd2 = end3;
+ outputComponents = 2;
} else {
throw new IllegalArgumentException("Failed to make path relative. Bad
reference: " + path);
}
+ String relPath;
+ boolean contiguous = outputEnd1 + 1 == outputStart2 &&
path.charAt(outputEnd1) == '/';
+ if (outputComponents == 2) {
+ if (contiguous) {
+ relPath = path.substring(outputStart1, outputEnd2);
+ } else {
+ relPath = new StringBuilder(outputEnd1 - outputStart1 + outputEnd2 -
outputStart2 + 1)
+ .append(path, outputStart1, outputEnd1).append('/')
+ .append(path, outputStart2, outputEnd2).toString();
+ }
+ } else if (contiguous && outputEnd2 + 1 == outputStart3 &&
path.charAt(outputEnd2) == '/') {
+ relPath = path.substring(outputStart1, outputEnd3);
+ } else {
+ relPath = new StringBuilder(
+ outputEnd1 - outputStart1 + outputEnd2 - outputStart2 + outputEnd3 -
outputStart3 + 2)
+ .append(path, outputStart1, outputEnd1).append('/').append(path,
outputStart2, outputEnd2)
+ .append('/').append(path, outputStart3, outputEnd3).toString();
+ }
+
log.trace("{} -> {} expectedLen = {}", path, relPath, expectedLen);
return relPath;
}
@@ -204,8 +276,13 @@ public class GarbageCollectionAlgorithm {
private long removeBlipCandidates(GarbageCollectionEnvironment gce,
SortedMap<String,GcCandidate> candidateMap) throws
TableNotFoundException {
long blipCount = 0;
- boolean checkForBulkProcessingFiles =
candidateMap.keySet().stream().anyMatch(
- relativePath ->
relativePath.toLowerCase(Locale.ENGLISH).contains(Constants.BULK_PREFIX));
+ boolean checkForBulkProcessingFiles = false;
+ for (String relativePath : candidateMap.keySet()) {
+ if (containsBulkPrefix(relativePath)) {
+ checkForBulkProcessingFiles = true;
+ break;
+ }
+ }
if (checkForBulkProcessingFiles) {
try (Stream<String> blipStream = gce.getBlipPaths()) {
@@ -243,6 +320,16 @@ public class GarbageCollectionAlgorithm {
return blipCount;
}
+ private boolean containsBulkPrefix(String path) {
+ int prefixLength = Constants.BULK_PREFIX.length();
+ for (int i = 0; i <= path.length() - prefixLength; i++) {
+ if (path.regionMatches(true, i, Constants.BULK_PREFIX, 0, prefixLength))
{
+ return true;
+ }
+ }
+ return false;
+ }
+
/**
* Double check no tables were missed during GC
*/
@@ -327,10 +414,11 @@ public class GarbageCollectionAlgorithm {
// find the table ids that had dirs deleted
for (String delete : candidateMap.keySet()) {
- String[] tokens = delete.split("/");
- if (tokens.length == 2) {
+ int firstSlash = delete.indexOf('/');
+ if (firstSlash > 0 && firstSlash < delete.length() - 1
+ && delete.indexOf('/', firstSlash + 1) == -1) {
// its a directory
- TableId tableId = TableId.of(delete.split("/")[0]);
+ TableId tableId = TableId.of(delete.substring(0, firstSlash));
tableIdsWithDeletes.add(tableId);
}
}
diff --git
a/server/gc/src/test/java/org/apache/accumulo/gc/GarbageCollectionTest.java
b/server/gc/src/test/java/org/apache/accumulo/gc/GarbageCollectionTest.java
index a251215223..3548437af1 100644
--- a/server/gc/src/test/java/org/apache/accumulo/gc/GarbageCollectionTest.java
+++ b/server/gc/src/test/java/org/apache/accumulo/gc/GarbageCollectionTest.java
@@ -487,14 +487,14 @@ public class GarbageCollectionTest {
public void testBlip() throws Exception {
TestGCE gce = new TestGCE();
- gce.addCandidate("/4/b-0");
- gce.addCandidate("/4/b-0/F002.rf");
- gce.addCandidate("hdfs://foo.com:6000/accumulo/tables/4/b-0/F001.rf");
+ gce.addCandidate("/4/B-0");
+ gce.addCandidate("/4/B-0/F002.rf");
+ gce.addCandidate("hdfs://foo.com:6000/accumulo/tables/4/B-0/F001.rf");
gce.addCandidate("/5/b-0");
gce.addCandidate("/5/b-0/F002.rf");
gce.addCandidate("hdfs://foo.com:6000/accumulo/tables/5/b-0/F001.rf");
- gce.blips.add("/4/b-0");
+ gce.blips.add("/4/B-0");
gce.blips.add("hdfs://foo.com:6000/accumulo/tables/5/b-0");
GarbageCollectionAlgorithm gca = new GarbageCollectionAlgorithm();
@@ -504,13 +504,13 @@ public class GarbageCollectionTest {
assertFileDeleted(gce);
// Remove the first blip
- gce.blips.remove("/4/b-0");
+ gce.blips.remove("/4/B-0");
// And we should lose all files in that blip and the blip directory itself
-- relative and
// absolute
gca.collect(gce);
- assertFileDeleted(gce, new GcCandidate("/4/b-0", 0L), new
GcCandidate("/4/b-0/F002.rf", 1L),
- new GcCandidate("hdfs://foo.com:6000/accumulo/tables/4/b-0/F001.rf",
2L));
+ assertFileDeleted(gce, new GcCandidate("/4/B-0", 0L), new
GcCandidate("/4/B-0/F002.rf", 1L),
+ new GcCandidate("hdfs://foo.com:6000/accumulo/tables/4/B-0/F001.rf",
2L));
gce.blips.remove("hdfs://foo.com:6000/accumulo/tables/5/b-0");
