You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@skywalking.apache.org by wu...@apache.org on 2023/06/13 12:15:47 UTC
[skywalking] branch master updated: Improve match performance of URI matching in 40% (#10923)
This is an automated email from the ASF dual-hosted git repository.
wusheng pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/skywalking.git
The following commit(s) were added to refs/heads/master by this push:
new 848583cde5 Improve match performance of URI matching in 40% (#10923)
848583cde5 is described below
commit 848583cde52252eb8634e8f2f8b1fe5b42a4f0e0
Author: 吴晟 Wu Sheng <wu...@foxmail.com>
AuthorDate: Tue Jun 13 20:15:40 2023 +0800
Improve match performance of URI matching in 40% (#10923)
## Conclusion
1. In matching the first rule scenario, the new implementation(mostly due to split performance), it is 40% fast than the previous implementation.
2. Quick match has a huge advantage in GC(time and cost) and memory cost(alloc, G1 Eden and G1 Old) in every case. In my 64G M1 Max env, the regex matching even causes full GC just in the benchmark, which is only running in 2:11 mins. The regex would be a disaster for product env memory.
3. The quick match only has lower performance when the number of pattern rules is less than 4, which is nearly impossible. Even for that, Regex matching costs most GC and memory alloc in a one-time match, and 3-time cost in 4 times match.
## Other Changes
1. I made the URI cache only works in AI pipeline works, as it should. This was a bug in the previous commit.
2. `/` is not required in this case, as generally, the pattern recognition should work well for the demo name as well.
---
.../group/uri/RegexVSQuickMatchBenchmark.java | 102 +++++++++++++--------
.../core/config/group/EndpointNameGrouping.java | 40 ++++----
.../config/group/uri/quickmatch/PatternTree.java | 21 ++++-
3 files changed, 107 insertions(+), 56 deletions(-)
diff --git a/oap-server/microbench/src/main/java/org/apache/skywalking/oap/server/microbench/core/config/group/uri/RegexVSQuickMatchBenchmark.java b/oap-server/microbench/src/main/java/org/apache/skywalking/oap/server/microbench/core/config/group/uri/RegexVSQuickMatchBenchmark.java
index ce0165abeb..bc3761a175 100644
--- a/oap-server/microbench/src/main/java/org/apache/skywalking/oap/server/microbench/core/config/group/uri/RegexVSQuickMatchBenchmark.java
+++ b/oap-server/microbench/src/main/java/org/apache/skywalking/oap/server/microbench/core/config/group/uri/RegexVSQuickMatchBenchmark.java
@@ -103,6 +103,16 @@ public class RegexVSQuickMatchBenchmark extends AbstractMicrobenchmark {
bh.consume(formatClass.match("service1", "/products/123"));
}
+ @Benchmark
+ public void matchFourthRegex(Blackhole bh, RegexVSQuickMatchBenchmark.RegexMatch formatClass) {
+ bh.consume(formatClass.match("service1", "/sales/123/2"));
+ }
+
+ @Benchmark
+ public void matchFourthQuickUriGrouping(Blackhole bh, RegexVSQuickMatchBenchmark.QuickMatch formatClass) {
+ bh.consume(formatClass.match("service1", "/sales/123/2"));
+ }
+
@Benchmark
public void notMatchRegex(Blackhole bh, RegexVSQuickMatchBenchmark.RegexMatch formatClass) {
bh.consume(formatClass.match("service1", "/employees/123"));
@@ -126,41 +136,59 @@ public class RegexVSQuickMatchBenchmark extends AbstractMicrobenchmark {
* # Benchmark mode: Throughput, ops/time
* # Benchmark: org.apache.skywalking.oap.server.microbench.core.config.group.uri.RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping
*
- Benchmark Mode Cnt Score Error Units
- RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping thrpt 21824009.131 ops/s
- RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping:·gc.alloc.rate thrpt 5388.565 MB/sec
- RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping:·gc.alloc.rate.norm thrpt 272.000 B/op
- RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping:·gc.churn.G1_Eden_Space thrpt 5414.783 MB/sec
- RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping:·gc.churn.G1_Eden_Space.norm thrpt 273.323 B/op
- RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping:·gc.churn.G1_Old_Gen thrpt 0.019 MB/sec
- RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping:·gc.churn.G1_Old_Gen.norm thrpt 0.001 B/op
- RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping:·gc.count thrpt 186.000 counts
- RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping:·gc.time thrpt 112.000 ms
- RegexVSQuickMatchBenchmark.matchFirstRegex thrpt 52815735.190 ops/s
- RegexVSQuickMatchBenchmark.matchFirstRegex:·gc.alloc.rate thrpt 7286.910 MB/sec
- RegexVSQuickMatchBenchmark.matchFirstRegex:·gc.alloc.rate.norm thrpt 152.000 B/op
- RegexVSQuickMatchBenchmark.matchFirstRegex:·gc.churn.G1_Eden_Space thrpt 7306.492 MB/sec
- RegexVSQuickMatchBenchmark.matchFirstRegex:·gc.churn.G1_Eden_Space.norm thrpt 152.408 B/op
- RegexVSQuickMatchBenchmark.matchFirstRegex:·gc.churn.G1_Old_Gen thrpt 0.026 MB/sec
- RegexVSQuickMatchBenchmark.matchFirstRegex:·gc.churn.G1_Old_Gen.norm thrpt 0.001 B/op
- RegexVSQuickMatchBenchmark.matchFirstRegex:·gc.count thrpt 251.000 counts
- RegexVSQuickMatchBenchmark.matchFirstRegex:·gc.time thrpt 143.000 ms
- RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping thrpt 23265119.660 ops/s
- RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping:·gc.alloc.rate thrpt 5914.434 MB/sec
- RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping:·gc.alloc.rate.norm thrpt 280.000 B/op
- RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping:·gc.churn.G1_Eden_Space thrpt 5939.872 MB/sec
- RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping:·gc.churn.G1_Eden_Space.norm thrpt 281.204 B/op
- RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping:·gc.churn.G1_Old_Gen thrpt 0.025 MB/sec
- RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping:·gc.churn.G1_Old_Gen.norm thrpt 0.001 B/op
- RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping:·gc.count thrpt 204.000 counts
- RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping:·gc.time thrpt 108.000 ms
- RegexVSQuickMatchBenchmark.notMatchRegex thrpt 10462244.647 ops/s
- RegexVSQuickMatchBenchmark.notMatchRegex:·gc.alloc.rate thrpt 26817.565 MB/sec
- RegexVSQuickMatchBenchmark.notMatchRegex:·gc.alloc.rate.norm thrpt 2824.000 B/op
- RegexVSQuickMatchBenchmark.notMatchRegex:·gc.churn.G1_Eden_Space thrpt 26925.722 MB/sec
- RegexVSQuickMatchBenchmark.notMatchRegex:·gc.churn.G1_Eden_Space.norm thrpt 2835.389 B/op
- RegexVSQuickMatchBenchmark.notMatchRegex:·gc.churn.G1_Old_Gen thrpt 0.128 MB/sec
- RegexVSQuickMatchBenchmark.notMatchRegex:·gc.churn.G1_Old_Gen.norm thrpt 0.013 B/op
- RegexVSQuickMatchBenchmark.notMatchRegex:·gc.count thrpt 925.000 counts
- RegexVSQuickMatchBenchmark.notMatchRegex:·gc.time thrpt 507.000 ms
+ Benchmark Mode Cnt Score Error Units
+ RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping thrpt 28464926.797 ops/s
+ RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping:·gc.alloc.rate thrpt 6194.492 MB/sec
+ RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping:·gc.alloc.rate.norm thrpt 240.000 B/op
+ RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping:·gc.churn.G1_Eden_Space thrpt 6222.267 MB/sec
+ RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping:·gc.churn.G1_Eden_Space.norm thrpt 241.076 B/op
+ RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping:·gc.churn.G1_Old_Gen thrpt 0.023 MB/sec
+ RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping:·gc.churn.G1_Old_Gen.norm thrpt 0.001 B/op
+ RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping:·gc.count thrpt 214.000 counts
+ RegexVSQuickMatchBenchmark.matchFirstQuickUriGrouping:·gc.time thrpt 194.000 ms
+ RegexVSQuickMatchBenchmark.matchFirstRegex thrpt 51679120.204 ops/s
+ RegexVSQuickMatchBenchmark.matchFirstRegex:·gc.alloc.rate thrpt 7130.116 MB/sec
+ RegexVSQuickMatchBenchmark.matchFirstRegex:·gc.alloc.rate.norm thrpt 152.000 B/op
+ RegexVSQuickMatchBenchmark.matchFirstRegex:·gc.churn.G1_Eden_Space thrpt 7162.842 MB/sec
+ RegexVSQuickMatchBenchmark.matchFirstRegex:·gc.churn.G1_Eden_Space.norm thrpt 152.698 B/op
+ RegexVSQuickMatchBenchmark.matchFirstRegex:·gc.churn.G1_Old_Gen thrpt 0.020 MB/sec
+ RegexVSQuickMatchBenchmark.matchFirstRegex:·gc.churn.G1_Old_Gen.norm thrpt ≈ 10⁻³ B/op
+ RegexVSQuickMatchBenchmark.matchFirstRegex:·gc.count thrpt 246.000 counts
+ RegexVSQuickMatchBenchmark.matchFirstRegex:·gc.time thrpt 224.000 ms
+ RegexVSQuickMatchBenchmark.matchFourthQuickUriGrouping thrpt 23359343.934 ops/s
+ RegexVSQuickMatchBenchmark.matchFourthQuickUriGrouping:·gc.alloc.rate thrpt 6106.164 MB/sec
+ RegexVSQuickMatchBenchmark.matchFourthQuickUriGrouping:·gc.alloc.rate.norm thrpt 288.000 B/op
+ RegexVSQuickMatchBenchmark.matchFourthQuickUriGrouping:·gc.churn.G1_Eden_Space thrpt 6143.526 MB/sec
+ RegexVSQuickMatchBenchmark.matchFourthQuickUriGrouping:·gc.churn.G1_Eden_Space.norm thrpt 289.762 B/op
+ RegexVSQuickMatchBenchmark.matchFourthQuickUriGrouping:·gc.churn.G1_Old_Gen thrpt 0.023 MB/sec
+ RegexVSQuickMatchBenchmark.matchFourthQuickUriGrouping:·gc.churn.G1_Old_Gen.norm thrpt 0.001 B/op
+ RegexVSQuickMatchBenchmark.matchFourthQuickUriGrouping:·gc.count thrpt 211.000 counts
+ RegexVSQuickMatchBenchmark.matchFourthQuickUriGrouping:·gc.time thrpt 143.000 ms
+ RegexVSQuickMatchBenchmark.matchFourthRegex thrpt 24074353.094 ops/s
+ RegexVSQuickMatchBenchmark.matchFourthRegex:·gc.alloc.rate thrpt 17999.991 MB/sec
+ RegexVSQuickMatchBenchmark.matchFourthRegex:·gc.alloc.rate.norm thrpt 824.000 B/op
+ RegexVSQuickMatchBenchmark.matchFourthRegex:·gc.churn.G1_Eden_Space thrpt 18070.905 MB/sec
+ RegexVSQuickMatchBenchmark.matchFourthRegex:·gc.churn.G1_Eden_Space.norm thrpt 827.246 B/op
+ RegexVSQuickMatchBenchmark.matchFourthRegex:·gc.churn.G1_Old_Gen thrpt 0.095 MB/sec
+ RegexVSQuickMatchBenchmark.matchFourthRegex:·gc.churn.G1_Old_Gen.norm thrpt 0.004 B/op
+ RegexVSQuickMatchBenchmark.matchFourthRegex:·gc.count thrpt 621.000 counts
+ RegexVSQuickMatchBenchmark.matchFourthRegex:·gc.time thrpt 934.000 ms
+ RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping thrpt 27031477.704 ops/s
+ RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping:·gc.alloc.rate thrpt 6081.482 MB/sec
+ RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping:·gc.alloc.rate.norm thrpt 248.000 B/op
+ RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping:·gc.churn.G1_Eden_Space thrpt 6109.321 MB/sec
+ RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping:·gc.churn.G1_Eden_Space.norm thrpt 249.135 B/op
+ RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping:·gc.churn.G1_Old_Gen thrpt 0.022 MB/sec
+ RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping:·gc.churn.G1_Old_Gen.norm thrpt 0.001 B/op
+ RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping:·gc.count thrpt 210.000 counts
+ RegexVSQuickMatchBenchmark.notMatchQuickUriGrouping:·gc.time thrpt 171.000 ms
+ RegexVSQuickMatchBenchmark.notMatchRegex thrpt 9368757.119 ops/s
+ RegexVSQuickMatchBenchmark.notMatchRegex:·gc.alloc.rate thrpt 23999.619 MB/sec
+ RegexVSQuickMatchBenchmark.notMatchRegex:·gc.alloc.rate.norm thrpt 2824.000 B/op
+ RegexVSQuickMatchBenchmark.notMatchRegex:·gc.churn.G1_Eden_Space thrpt 24087.019 MB/sec
+ RegexVSQuickMatchBenchmark.notMatchRegex:·gc.churn.G1_Eden_Space.norm thrpt 2834.284 B/op
+ RegexVSQuickMatchBenchmark.notMatchRegex:·gc.churn.G1_Old_Gen thrpt 0.114 MB/sec
+ RegexVSQuickMatchBenchmark.notMatchRegex:·gc.churn.G1_Old_Gen.norm thrpt 0.013 B/op
+ RegexVSQuickMatchBenchmark.notMatchRegex:·gc.count thrpt 828.000 counts
+ RegexVSQuickMatchBenchmark.notMatchRegex:·gc.time thrpt 896.000 ms
*/
\ No newline at end of file
diff --git a/oap-server/server-core/src/main/java/org/apache/skywalking/oap/server/core/config/group/EndpointNameGrouping.java b/oap-server/server-core/src/main/java/org/apache/skywalking/oap/server/core/config/group/EndpointNameGrouping.java
index 85ea7b0dde..abbb51d8e2 100644
--- a/oap-server/server-core/src/main/java/org/apache/skywalking/oap/server/core/config/group/EndpointNameGrouping.java
+++ b/oap-server/server-core/src/main/java/org/apache/skywalking/oap/server/core/config/group/EndpointNameGrouping.java
@@ -39,10 +39,19 @@ import org.apache.skywalking.oap.server.library.util.StringFormatGroup;
@Slf4j
public class EndpointNameGrouping {
+ /**
+ * Endpoint grouping according to local endpoint-name-grouping.yml or associated dynamic configuration.
+ */
@Setter
private volatile QuickUriGroupingRule endpointGroupingRule;
+ /**
+ * Endpoint grouping according to OpenAPI specification. The OpenAPI spec file is expected to provide.
+ */
@Setter
private volatile EndpointGroupingRule4Openapi endpointGroupingRule4Openapi;
+ /**
+ * AI pipeline based HTTP URI pattern recognition. The rules are automatically generated by remote AI/ML service.
+ */
@Setter
private volatile QuickUriGroupingRule quickUriGroupingRule;
/**
@@ -64,8 +73,9 @@ public class EndpointNameGrouping {
*
* @param serviceName service name
* @param endpointName endpoint name to be formatted.
- * @return Tuple2 where the first element is the formatted name and the second element is a boolean
- * represented the endpoint name is formatted or not.
+ * @return Tuple2 The result of endpoint name formatting.
+ * The first element is the formatted name or original name when not formatted.
+ * The second element is a boolean represented the endpoint name is formatted or not.
*/
public Tuple2<String, Boolean> format(String serviceName, String endpointName) {
Tuple2<String, Boolean> formattedName = new Tuple2<>(endpointName, Boolean.FALSE);
@@ -79,23 +89,17 @@ public class EndpointNameGrouping {
if (!formattedName._2() && quickUriGroupingRule != null) {
formattedName = formatByQuickUriPattern(serviceName, endpointName);
- }
- if (!formattedName._2()) {
- // Only URI includes '/' will be cached and formatted later.
- // Otherwise it could be anything, and has no need to be formatted.
- if (endpointName.indexOf("/") > -1) {
- ConcurrentHashMap<String, AtomicInteger> svrHttpUris = cachedHttpUris.get(serviceName);
- if (svrHttpUris == null) {
- cachedHttpUris.putIfAbsent(serviceName, new ConcurrentHashMap<>());
- svrHttpUris = cachedHttpUris.get(serviceName);
- }
- // Only cache first 2000 URIs per 30 mins.
- if (svrHttpUris.size() < maxHttpUrisNumberPerService) {
- final AtomicInteger cachedCount = svrHttpUris.putIfAbsent(endpointName, new AtomicInteger(1));
- if (null != cachedCount) {
- cachedCount.incrementAndGet();
- }
+ ConcurrentHashMap<String, AtomicInteger> svrHttpUris = cachedHttpUris.get(serviceName);
+ if (svrHttpUris == null) {
+ cachedHttpUris.putIfAbsent(serviceName, new ConcurrentHashMap<>());
+ svrHttpUris = cachedHttpUris.get(serviceName);
+ }
+ // Only cache first N(determined by maxHttpUrisNumberPerService) URIs per 30 mins.
+ if (svrHttpUris.size() < maxHttpUrisNumberPerService) {
+ final AtomicInteger cachedCount = svrHttpUris.putIfAbsent(formattedName._1(), new AtomicInteger(1));
+ if (null != cachedCount) {
+ cachedCount.incrementAndGet();
}
}
}
diff --git a/oap-server/server-core/src/main/java/org/apache/skywalking/oap/server/core/config/group/uri/quickmatch/PatternTree.java b/oap-server/server-core/src/main/java/org/apache/skywalking/oap/server/core/config/group/uri/quickmatch/PatternTree.java
index a930ed11d3..129e703166 100644
--- a/oap-server/server-core/src/main/java/org/apache/skywalking/oap/server/core/config/group/uri/quickmatch/PatternTree.java
+++ b/oap-server/server-core/src/main/java/org/apache/skywalking/oap/server/core/config/group/uri/quickmatch/PatternTree.java
@@ -78,8 +78,27 @@ public class PatternTree {
current.setExpression(pattern);
}
+ List<String> splitByCharacter(String input, char delimiter) {
+ List<String> parts = new ArrayList<>();
+ int start = 0;
+
+ for (int i = 0; i < input.length(); i++) {
+ if (input.charAt(i) == delimiter) {
+ parts.add(input.substring(start, i));
+ start = i + 1;
+ }
+ }
+
+ // Add the last part if necessary
+ if (start < input.length()) {
+ parts.add(input.substring(start));
+ }
+
+ return parts;
+ }
+
public StringFormatGroup.FormatResult match(String uri) {
- final String[] slices = uri.split("/");
+ final List<String> slices = splitByCharacter(uri, '/');
List<PatternToken> current = roots;
PatternToken matchedToken = null;
for (final String slice : slices) {