Use faster fallback diff algorithm in case of timeouts
Current logic uses the default diff algorithm "Histogram Diff". In case
of timeouts, it throws an exception that is propagated to the caller.
In this change, we adjust the logic to follow what was implemented in
PatchListLoader (the old diff cache): If the diff execution times out,
we fallback to the faster histogram algorithm without myers diff and log
a warning message. Notice that in DiffOperations, the fallback is done
outside the cache, i.e. we are requesting the diff from the cache with
new keys that specify which algorithm should be used. In old diff cache,
this fallback was done inside the cache loader. This is one of the
advantages of the new diff cache that we can explicitly specify which
algorithm to use as part of the cache key.
This change implies that slow requests will always have to go through
the timeout before requesting the diffs using the faster algorithm. In a
follow up change, we can enhance the logic by caching negative results
for the histogram diff keys to quickly fallback without having to
hit the timeout.
Change-Id: I34fe29dc166534d835c97beab85661facafac31f
diff --git a/java/com/google/gerrit/server/patch/DiffOperationsImpl.java b/java/com/google/gerrit/server/patch/DiffOperationsImpl.java
index fd30868..5183f8c 100644
--- a/java/com/google/gerrit/server/patch/DiffOperationsImpl.java
+++ b/java/com/google/gerrit/server/patch/DiffOperationsImpl.java
@@ -66,7 +66,8 @@
private static final FluentLogger logger = FluentLogger.forEnclosingClass();
private static final int RENAME_SCORE = 60;
- private static final DiffAlgorithm DEFAULT_DIFF_ALGORITHM = DiffAlgorithm.HISTOGRAM;
+ private static final DiffAlgorithm DEFAULT_DIFF_ALGORITHM =
+ DiffAlgorithm.HISTOGRAM_WITH_FALLBACK_MYERS;
private static final Whitespace DEFAULT_WHITESPACE = Whitespace.IGNORE_NONE;
private final ModifiedFilesCache modifiedFilesCache;
@@ -132,6 +133,7 @@
.newCommit(newCommit)
.baseCommit(oldCommit)
.comparisonType(ComparisonType.againstOtherPatchSet())
+ .diffAlgorithm(DEFAULT_DIFF_ALGORITHM)
.build();
return listModifiedFilesWithTimeout(params);
}
@@ -147,7 +149,13 @@
try {
DiffParameters diffParams = computeDiffParameters(project, newCommit, parent);
FileDiffCacheKey key =
- createFileDiffCacheKey(project, diffParams.baseCommit(), newCommit, fileName, whitespace);
+ createFileDiffCacheKey(
+ project,
+ diffParams.baseCommit(),
+ newCommit,
+ fileName,
+ diffParams.diffAlgorithm(),
+ whitespace);
return getModifiedFileWithTimeout(key, diffParams);
} catch (IOException e) {
throw new DiffNotAvailableException(
@@ -169,12 +177,20 @@
.baseCommit(oldCommit)
.newCommit(newCommit)
.comparisonType(ComparisonType.againstOtherPatchSet())
+ .diffAlgorithm(DEFAULT_DIFF_ALGORITHM)
.build();
FileDiffCacheKey key =
- createFileDiffCacheKey(project, oldCommit, newCommit, fileName, whitespace);
+ createFileDiffCacheKey(
+ project, oldCommit, newCommit, fileName, params.diffAlgorithm(), whitespace);
return getModifiedFileWithTimeout(key, params);
}
+ /**
+ * Computes the list of modified files between two commits using the {@link
+ * DiffAlgorithm#HISTOGRAM_WITH_FALLBACK_MYERS} diff algorithm. The computation runs with the
+ * timeout specified by {@link #timeoutMillis} milliseconds. If the timeout is reached, this
+ * method falls back to the {@link DiffAlgorithm#HISTOGRAM_NO_FALLBACK}.
+ */
private Map<String, FileDiffOutput> listModifiedFilesWithTimeout(DiffParameters params)
throws DiffNotAvailableException {
Future<DiffResult> task =
@@ -183,42 +199,59 @@
ImmutableMap<String, FileDiffOutput> modifiedFiles = getModifiedFiles(params);
return DiffResult.create(null, modifiedFiles);
});
- DiffResult diffResult = execDiffWithTimeout(task, params);
- return diffResult.modifiedFiles();
- }
-
- private FileDiffOutput getModifiedFileWithTimeout(FileDiffCacheKey key, DiffParameters params)
- throws DiffNotAvailableException {
- Future<DiffResult> task =
- diffExecutor.submit(
- () -> {
- Map<String, FileDiffOutput> diffList = getModifiedFilesForKeys(ImmutableList.of(key));
- FileDiffOutput fileDiffOutput =
- diffList.containsKey(key.newFilePath())
- ? diffList.get(key.newFilePath())
- : FileDiffOutput.empty(key.newFilePath(), key.oldCommit(), key.newCommit());
- return DiffResult.create(fileDiffOutput, null);
- });
- DiffResult result = execDiffWithTimeout(task, params);
- return result.fileDiff();
- }
-
- /** Executes a diff task by employing a timeout. */
- private DiffResult execDiffWithTimeout(Future<DiffResult> task, DiffParameters params)
- throws DiffNotAvailableException {
try {
- return task.get(timeoutMillis, TimeUnit.MILLISECONDS);
+ return task.get(timeoutMillis, TimeUnit.MILLISECONDS).modifiedFiles();
} catch (InterruptedException | TimeoutException e) {
- throw new DiffNotAvailableException(
+ logger.atWarning().withCause(e).log(
String.format(
- "Timeout reached while computing diff for project %s, old commit %s, new commit %s",
- params.project(), params.baseCommit().name(), params.newCommit().name()),
- e);
+ "Timeout reached while computing diff for project %s, old commit %s, new commit %s."
+ + " Retrying using the fallback algorithm.",
+ params.project(), params.baseCommit().name(), params.newCommit().name()));
+ task.cancel(/* mayInterruptIfRunning= */ true);
+ DiffParameters newParams =
+ params.toBuilder().diffAlgorithm(DiffAlgorithm.HISTOGRAM_NO_FALLBACK).build();
+ ImmutableMap<String, FileDiffOutput> modifiedFiles = getModifiedFiles(newParams);
+ return DiffResult.create(null, modifiedFiles).modifiedFiles();
} catch (ExecutionException e) {
throw new DiffNotAvailableException(e);
}
}
+ /**
+ * Computes the file diff for a single file using the {@link
+ * DiffAlgorithm#HISTOGRAM_WITH_FALLBACK_MYERS} diff algorithm. The computation runs with the
+ * timeout specified by {@link #timeoutMillis} milliseconds. If the timeout is reached, this
+ * method falls back to the {@link DiffAlgorithm#HISTOGRAM_NO_FALLBACK}.
+ */
+ private FileDiffOutput getModifiedFileWithTimeout(FileDiffCacheKey key, DiffParameters params)
+ throws DiffNotAvailableException {
+ Future<DiffResult> task = diffExecutor.submit(() -> getModifiedFileForKey(key));
+ try {
+ return task.get(timeoutMillis, TimeUnit.MILLISECONDS).fileDiff();
+ } catch (InterruptedException | TimeoutException e) {
+ logger.atWarning().withCause(e).log(
+ String.format(
+ "Timeout reached while computing diff for project %s, old commit %s, new commit %s."
+ + " Recomputing using the fallback algorithm.",
+ params.project(), params.baseCommit().name(), params.newCommit().name()));
+ task.cancel(/* mayInterruptIfRunning= */ true);
+ FileDiffCacheKey newKey =
+ key.toBuilder().diffAlgorithm(DiffAlgorithm.HISTOGRAM_NO_FALLBACK).build();
+ return getModifiedFileForKey(newKey).fileDiff();
+ } catch (ExecutionException e) {
+ throw new DiffNotAvailableException(e);
+ }
+ }
+
+ private DiffResult getModifiedFileForKey(FileDiffCacheKey key) throws DiffNotAvailableException {
+ Map<String, FileDiffOutput> diffList = getModifiedFilesForKeys(ImmutableList.of(key));
+ FileDiffOutput fileDiffOutput =
+ diffList.containsKey(key.newFilePath())
+ ? diffList.get(key.newFilePath())
+ : FileDiffOutput.empty(key.newFilePath(), key.oldCommit(), key.newCommit());
+ return DiffResult.create(fileDiffOutput, null);
+ }
+
private ImmutableMap<String, FileDiffOutput> getModifiedFiles(DiffParameters diffParams)
throws DiffNotAvailableException {
try {
@@ -233,12 +266,22 @@
List<FileDiffCacheKey> fileCacheKeys = new ArrayList<>();
fileCacheKeys.add(
createFileDiffCacheKey(
- project, oldCommit, newCommit, COMMIT_MSG, /* whitespace= */ null));
+ project,
+ oldCommit,
+ newCommit,
+ COMMIT_MSG,
+ diffParams.diffAlgorithm(),
+ /* whitespace= */ null));
if (cmp.isAgainstAutoMerge() || isMergeAgainstParent(cmp, project, newCommit)) {
fileCacheKeys.add(
createFileDiffCacheKey(
- project, oldCommit, newCommit, MERGE_LIST, /*whitespace = */ null));
+ project,
+ oldCommit,
+ newCommit,
+ MERGE_LIST,
+ diffParams.diffAlgorithm(),
+ /*whitespace = */ null));
}
if (diffParams.skipFiles() == null) {
@@ -252,6 +295,7 @@
entity.newPath().isPresent()
? entity.newPath().get()
: entity.oldPath().get(),
+ diffParams.diffAlgorithm(),
/* whitespace= */ null))
.forEach(fileCacheKeys::add);
}
@@ -305,6 +349,7 @@
ObjectId aCommit,
ObjectId bCommit,
String newPath,
+ DiffAlgorithm diffAlgorithm,
@Nullable Whitespace whitespace) {
whitespace = whitespace == null ? DEFAULT_WHITESPACE : whitespace;
return FileDiffCacheKey.builder()
@@ -313,16 +358,12 @@
.newCommit(bCommit)
.newFilePath(newPath)
.renameScore(RENAME_SCORE)
- .diffAlgorithm(DEFAULT_DIFF_ALGORITHM)
+ .diffAlgorithm(diffAlgorithm)
.whitespace(whitespace)
.build();
}
- /**
- * All interface methods create their results using this class. This is used so that the timeout
- * method {@link #execDiffWithTimeout(Future, DiffParameters)} could be reused by all interface
- * methods.
- */
+ /** All interface methods create their results using this class. */
@AutoValue
abstract static class DiffResult {
static DiffResult create(
@@ -359,10 +400,14 @@
@Nullable
abstract Boolean skipFiles();
+ abstract DiffAlgorithm diffAlgorithm();
+
static Builder builder() {
return new AutoValue_DiffOperationsImpl_DiffParameters.Builder();
}
+ abstract Builder toBuilder();
+
@AutoValue.Builder
abstract static class Builder {
@@ -376,6 +421,8 @@
abstract Builder skipFiles(@Nullable Boolean skipFiles);
+ abstract Builder diffAlgorithm(DiffAlgorithm diffAlgorithm);
+
abstract Builder comparisonType(ComparisonType comparisonType);
public abstract DiffParameters build();
@@ -386,7 +433,11 @@
private DiffParameters computeDiffParameters(
Project.NameKey project, ObjectId newCommit, Integer parent) throws IOException {
DiffParameters.Builder result =
- DiffParameters.builder().project(project).newCommit(newCommit).parent(parent);
+ DiffParameters.builder()
+ .project(project)
+ .newCommit(newCommit)
+ .parent(parent)
+ .diffAlgorithm(DEFAULT_DIFF_ALGORITHM);
if (parent != null) {
result.baseCommit(baseCommitUtil.getBaseCommit(project, newCommit, parent));
result.comparisonType(ComparisonType.againstParent(parent));
diff --git a/java/com/google/gerrit/server/patch/filediff/FileDiffCacheKey.java b/java/com/google/gerrit/server/patch/filediff/FileDiffCacheKey.java
index 7ac9343..26aa2b0 100644
--- a/java/com/google/gerrit/server/patch/filediff/FileDiffCacheKey.java
+++ b/java/com/google/gerrit/server/patch/filediff/FileDiffCacheKey.java
@@ -73,6 +73,8 @@
return new AutoValue_FileDiffCacheKey.Builder();
}
+ public abstract Builder toBuilder();
+
@AutoValue.Builder
public abstract static class Builder {
diff --git a/java/com/google/gerrit/server/patch/gitfilediff/GitFileDiffCacheImpl.java b/java/com/google/gerrit/server/patch/gitfilediff/GitFileDiffCacheImpl.java
index 31afd17..33773f6 100644
--- a/java/com/google/gerrit/server/patch/gitfilediff/GitFileDiffCacheImpl.java
+++ b/java/com/google/gerrit/server/patch/gitfilediff/GitFileDiffCacheImpl.java
@@ -78,15 +78,15 @@
/** Enum for the supported diff algorithms for the file diff computation. */
public enum DiffAlgorithm {
- HISTOGRAM,
- HISTOGRAM_WITHOUT_MYERS_FALLBACK
+ HISTOGRAM_WITH_FALLBACK_MYERS,
+ HISTOGRAM_NO_FALLBACK
}
/** Creates a new JGit diff algorithm instance using the Gerrit's {@link DiffAlgorithm} enum. */
public static class DiffAlgorithmFactory {
public static org.eclipse.jgit.diff.DiffAlgorithm create(DiffAlgorithm diffAlgorithm) {
HistogramDiff result = new HistogramDiff();
- if (diffAlgorithm.equals(DiffAlgorithm.HISTOGRAM_WITHOUT_MYERS_FALLBACK)) {
+ if (diffAlgorithm.equals(DiffAlgorithm.HISTOGRAM_NO_FALLBACK)) {
result.setFallbackAlgorithm(null);
}
return result;
diff --git a/javatests/com/google/gerrit/server/cache/serialize/entities/FileDiffCacheKeySerializerTest.java b/javatests/com/google/gerrit/server/cache/serialize/entities/FileDiffCacheKeySerializerTest.java
index ecab07d..d738bf6 100644
--- a/javatests/com/google/gerrit/server/cache/serialize/entities/FileDiffCacheKeySerializerTest.java
+++ b/javatests/com/google/gerrit/server/cache/serialize/entities/FileDiffCacheKeySerializerTest.java
@@ -39,7 +39,7 @@
.newCommit(COMMIT_ID_2)
.newFilePath("some_file.txt")
.renameScore(65)
- .diffAlgorithm(DiffAlgorithm.HISTOGRAM)
+ .diffAlgorithm(DiffAlgorithm.HISTOGRAM_WITH_FALLBACK_MYERS)
.whitespace(Whitespace.IGNORE_ALL)
.build();
diff --git a/javatests/com/google/gerrit/server/cache/serialize/entities/GitFileDiffKeySerializerTest.java b/javatests/com/google/gerrit/server/cache/serialize/entities/GitFileDiffKeySerializerTest.java
index 12d8d00..d17bf8e 100644
--- a/javatests/com/google/gerrit/server/cache/serialize/entities/GitFileDiffKeySerializerTest.java
+++ b/javatests/com/google/gerrit/server/cache/serialize/entities/GitFileDiffKeySerializerTest.java
@@ -38,7 +38,7 @@
.newTree(TREE_ID_2)
.newFilePath("some_file.txt")
.renameScore(65)
- .diffAlgorithm(DiffAlgorithm.HISTOGRAM)
+ .diffAlgorithm(DiffAlgorithm.HISTOGRAM_WITH_FALLBACK_MYERS)
.whitespace(Whitespace.IGNORE_ALL)
.build();
