This is an automated email from the ASF dual-hosted git repository.
Aias00 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/shenyu.git
The following commit(s) were added to refs/heads/master by this push:
new cb2a610d4e [type:fix] Index metadata cold lookups by path prefix
(#7251)
cb2a610d4e is described below
commit cb2a610d4e352979140e20353b48fa9c901213ce
Author: Liming Deng <[email protected]>
AuthorDate: Thu Oct 1 12:18:49 2026 +0800
[type:fix] Index metadata cold lookups by path prefix (#7251)
---
.../shenyu/plugin/base/cache/MetaDataCache.java | 108 +++++++++++---
.../plugin/base/cache/MetaDataPrefixIndexTest.java | 159 +++++++++++++++++++++
2 files changed, 249 insertions(+), 18 deletions(-)
diff --git
a/shenyu-plugin/shenyu-plugin-base/src/main/java/org/apache/shenyu/plugin/base/cache/MetaDataCache.java
b/shenyu-plugin/shenyu-plugin-base/src/main/java/org/apache/shenyu/plugin/base/cache/MetaDataCache.java
index 0ef7a49f9c..f15df36785 100644
---
a/shenyu-plugin/shenyu-plugin-base/src/main/java/org/apache/shenyu/plugin/base/cache/MetaDataCache.java
+++
b/shenyu-plugin/shenyu-plugin-base/src/main/java/org/apache/shenyu/plugin/base/cache/MetaDataCache.java
@@ -22,7 +22,12 @@ import org.apache.shenyu.common.constant.Constants;
import org.apache.shenyu.common.cache.WindowTinyLFUMap;
import org.apache.shenyu.common.dto.MetaData;
import org.apache.shenyu.plugin.base.utils.PathMatchUtils;
+import org.springframework.util.StringUtils;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Optional;
@@ -47,6 +52,13 @@ public final class MetaDataCache {
private static final WindowTinyLFUMap<String, MetaData> CACHE =
new WindowTinyLFUMap<>(Constants.CACHE_MAX_COUNT,
Constants.CACHE_MAX_COUNT, Boolean.FALSE);
+ private volatile Map<String, List<MetaData>> pathIndex =
Collections.emptyMap();
+
+ // Index state is read and written only while holding this cache's monitor.
+ private boolean indexDirty;
+
+ private volatile boolean negativeCacheDirty;
+
private MetaDataCache() {
}
@@ -64,7 +76,7 @@ public final class MetaDataCache {
*
* @param data the data
*/
- public void cache(final MetaData data) {
+ public synchronized void cache(final MetaData data) {
// clean old path data
Optional.ofNullable(META_DATA_MAP.get(data.getId())).ifPresent(oldMetaData -> {
// the update is also need to clean, but there is
@@ -73,6 +85,8 @@ public final class MetaDataCache {
clean(oldMetaData.getPath());
});
META_DATA_MAP.put(data.getId(), data);
+ indexDirty = true;
+ negativeCacheDirty = true;
final String path = data.getPath();
clean(path);
if (!path.contains("*")) {
@@ -86,11 +100,56 @@ public final class MetaDataCache {
*
* @param data the data
*/
- public void remove(final MetaData data) {
+ public synchronized void remove(final MetaData data) {
META_DATA_MAP.remove(data.getId());
+ indexDirty = true;
+ negativeCacheDirty = true;
clean(data.getPath());
}
+ private void rebuildPathIndex() {
+ Map<String, List<MetaData>> index = new HashMap<>();
+ META_DATA_MAP.values().forEach(data ->
index.computeIfAbsent(firstSegment(data.getPath()), key -> new
ArrayList<>()).add(data));
+ index.replaceAll((key, value) -> List.copyOf(value));
+ pathIndex = Map.copyOf(index);
+ }
+
+ private String firstSegment(final String path) {
+ // AntPathMatcher ignores repeated separators, so use the same
tokenization.
+ String[] segments = StringUtils.tokenizeToStringArray(path, "/",
false, true);
+ if (segments.length == 0) {
+ return "";
+ }
+ String segment = segments[0];
+ if (segment.indexOf('*') >= 0 || segment.indexOf('?') >= 0 ||
segment.indexOf('{') >= 0) {
+ return "";
+ }
+ return (path.startsWith("/") ? "/" : "") + segment;
+ }
+
+ private MetaData matchIndexedPath(final String path) {
+ // Called under the same monitor as mutations and cold-cache
publication.
+ if (indexDirty) {
+ rebuildPathIndex();
+ indexDirty = false;
+ }
+ Map<String, List<MetaData>> index = pathIndex;
+ String segment = firstSegment(path);
+ MetaData match = matchCandidates(index.getOrDefault(segment,
Collections.emptyList()), path);
+ MetaData fallback = segment.isEmpty() ? null :
matchCandidates(index.getOrDefault("", Collections.emptyList()), path);
+ if (Objects.isNull(match)) {
+ return fallback;
+ }
+ return Objects.isNull(fallback) ||
PathMatchUtils.compare(match.getPath(), fallback.getPath(), path) <= 0 ? match
: fallback;
+ }
+
+ private MetaData matchCandidates(final List<MetaData> candidates, final
String path) {
+ return candidates.stream()
+ .filter(data -> data.getEnabled() &&
PathMatchUtils.match(data.getPath(), path))
+ .min((left, right) -> PathMatchUtils.compare(left.getPath(),
right.getPath(), path))
+ .orElse(null);
+ }
+
private void clean(final String key) {
if (key.contains("*")) {
CACHE.clear();
@@ -103,8 +162,19 @@ public final class MetaDataCache {
/**
* clean cache for divide plugin.
*/
- public void clean() {
+ public synchronized void clean() {
clean(DIVIDE_CACHE_KEY);
+ negativeCacheDirty = true;
+ cleanNegativeCache();
+ }
+
+ private synchronized void cleanNegativeCache() {
+ if (negativeCacheDirty) {
+ // URI variables (/{tenant}/new) and normalized separators can
turn earlier misses into hits.
+ // Sweep the bounded result cache once per mutation burst, never
an unbounded reverse index.
+ CACHE.entrySet().removeIf(entry -> NULL.equals(entry.getValue()));
+ negativeCacheDirty = false;
+ }
}
/**
@@ -114,23 +184,25 @@ public final class MetaDataCache {
* @return the meta data
*/
public MetaData obtain(final String path) {
- final MetaData metaData = Optional.ofNullable(CACHE.get(path))
- .orElseGet(() -> {
- final MetaData value = META_DATA_MAP.values()
- .stream()
- .filter(data -> data.getEnabled() &&
PathMatchUtils.match(data.getPath(), path))
- .min((left, right) ->
PathMatchUtils.compare(left.getPath(), right.getPath(), path))
- .orElse(null);
- final String metaPath = Optional.ofNullable(value)
- .map(MetaData::getPath)
- .orElse(DIVIDE_CACHE_KEY);
- // init cache
- initCache(path, value, metaPath);
- return value;
- });
+ if (negativeCacheDirty) {
+ cleanNegativeCache();
+ }
+ MetaData cached = CACHE.get(path);
+ final MetaData metaData = Objects.nonNull(cached) ? cached :
loadPath(path);
return NULL.equals(metaData) ? null : metaData;
}
+ private synchronized MetaData loadPath(final String path) {
+ MetaData cached = CACHE.get(path);
+ if (Objects.nonNull(cached)) {
+ return cached;
+ }
+ MetaData value = matchIndexedPath(path);
+ String metaPath = Objects.isNull(value) ? DIVIDE_CACHE_KEY :
value.getPath();
+ initCache(path, value, metaPath);
+ return value;
+ }
+
/**
* cacheMap.
*
@@ -138,7 +210,7 @@ public final class MetaDataCache {
* @param value the MetaData
* @param metaPath the metaPath
*/
- public void initCache(final String path, final MetaData value, final
String metaPath) {
+ public synchronized void initCache(final String path, final MetaData
value, final String metaPath) {
// The extreme case will lead to OOM, that's why use LRU
CACHE.put(path, Optional.ofNullable(value).orElse(NULL));
}
diff --git
a/shenyu-plugin/shenyu-plugin-base/src/test/java/org/apache/shenyu/plugin/base/cache/MetaDataPrefixIndexTest.java
b/shenyu-plugin/shenyu-plugin-base/src/test/java/org/apache/shenyu/plugin/base/cache/MetaDataPrefixIndexTest.java
new file mode 100644
index 0000000000..2a7b1706c4
--- /dev/null
+++
b/shenyu-plugin/shenyu-plugin-base/src/test/java/org/apache/shenyu/plugin/base/cache/MetaDataPrefixIndexTest.java
@@ -0,0 +1,159 @@
+/*
+ * 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
+ *
+ * http://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.shenyu.plugin.base.cache;
+
+import org.apache.shenyu.common.dto.MetaData;
+import org.apache.shenyu.plugin.base.utils.PathMatchUtils;
+import org.junit.jupiter.api.AfterEach;
+import org.junit.jupiter.api.Test;
+import org.mockito.MockedStatic;
+import org.mockito.Mockito;
+import org.springframework.test.util.ReflectionTestUtils;
+
+import java.util.ArrayList;
+import java.util.List;
+import static org.junit.jupiter.api.Assertions.assertFalse;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNull;
+import static org.junit.jupiter.api.Assertions.assertSame;
+import static org.junit.jupiter.api.Assertions.assertNotSame;
+import static org.mockito.Mockito.times;
+
+/**
+ * Regression tests for metadata prefix indexing.
+ */
+public class MetaDataPrefixIndexTest {
+
+ private final MetaDataCache cache = MetaDataCache.getInstance();
+
+ private final List<MetaData> registered = new ArrayList<>();
+
+ @AfterEach
+ public void cleanup() {
+ registered.forEach(cache::remove);
+ cache.clean();
+ }
+
+ @Test
+ public void testMutationBurstsRebuildOnlyOnColdLookup() {
+ Object initialIndex = ReflectionTestUtils.getField(cache, "pathIndex");
+ for (int i = 0; i < 10000; i++) {
+ register("burst-" + i, "/burst-" + i + "/**");
+ }
+ assertSame(initialIndex, ReflectionTestUtils.getField(cache,
"pathIndex"));
+ assertEquals("burst-42", cache.obtain("/burst-42/first").getId());
+ Object rebuilt = ReflectionTestUtils.getField(cache, "pathIndex");
+ assertNotSame(initialIndex, rebuilt);
+ assertEquals("burst-43", cache.obtain("/burst-43/second").getId());
+ assertSame(rebuilt, ReflectionTestUtils.getField(cache, "pathIndex"));
+ registered.forEach(cache::remove);
+ assertSame(rebuilt, ReflectionTestUtils.getField(cache, "pathIndex"));
+ assertNull(cache.obtain("/burst-42/after-delete"));
+ assertNotSame(rebuilt, ReflectionTestUtils.getField(cache,
"pathIndex"));
+ }
+
+ @Test
+ public void testNewVariablePatternInvalidatesEarlierNegativeLookup() {
+ assertNull(cache.obtain("/tenant/new"));
+ register("new-variable", "/{tenant}/new");
+ assertEquals("new-variable", cache.obtain("/tenant/new").getId());
+ }
+
+ @Test
+ public void testMutationBurstDefersBoundedNegativeCacheSweep() {
+ assertNull(cache.obtain("/negative/before"));
+ final Object miss = cache.getMetaDataCache().get("/negative/before");
+ for (int i = 0; i < 1000; i++) {
+ register("literal-burst-" + i, "/literal/" + i);
+ assertSame(miss, cache.getMetaDataCache().get("/negative/before"));
+ }
+ register("variable-after-miss", "/{tenant}/before");
+ assertSame(miss, cache.getMetaDataCache().get("/negative/before"));
+ assertEquals("variable-after-miss",
cache.obtain("/negative/before").getId());
+ assertFalse((Boolean) ReflectionTestUtils.getField(cache,
"negativeCacheDirty"));
+ assertNull(cache.obtain("/unmatched/one"));
+ assertNull(cache.obtain("/unmatched/two"));
+ cache.clean();
+ assertNull(cache.getMetaDataCache().get("/unmatched/one"));
+ }
+
+ @Test
+ public void testLiteralPathInvalidatesNormalizedNegativeLookup() {
+ assertNull(cache.obtain("/normalized//path"));
+ register("normalized", "/normalized/path");
+ assertEquals("normalized", cache.obtain("/normalized//path").getId());
+ }
+
+ @Test
+ public void testSpecificityIsComparedAcrossPrefixAndFallbackBuckets() {
+ register("broad", "/api/**");
+ register("specific-fallback", "/{tenant}/users");
+ assertEquals("specific-fallback", cache.obtain("/api/users").getId());
+ }
+
+ @Test
+ public void testColdLookupOnlyMatchesRelevantPrefix() {
+ for (int i = 0; i < 100; i++) {
+ register("route-" + i, "/service-" + i + "/**");
+ }
+ try (MockedStatic<PathMatchUtils> matcher =
Mockito.mockStatic(PathMatchUtils.class, Mockito.CALLS_REAL_METHODS)) {
+ assertEquals("route-42", cache.obtain("/service-42/cold").getId());
+ matcher.verify(() -> PathMatchUtils.match("/service-42/**",
"/service-42/cold"), times(1));
+ matcher.verifyNoMoreInteractions();
+ }
+ }
+
+ @Test
+ public void testFallbackPatternsAndRepeatedSeparators() {
+ register("literal", "/prefix//items/**");
+ register("variable", "/{tenant}/records/**");
+ register("question", "/tenant?/items/**");
+ assertEquals("literal", cache.obtain("//prefix/items/one").getId());
+ assertEquals("variable", cache.obtain("/acme/records/one").getId());
+ assertEquals("question", cache.obtain("/tenant1/items/one").getId());
+ }
+
+ @Test
+ public void testChangedPrefixAndRemovalUpdateIndex() {
+ final MetaData old = register("changing", "/old-prefix/**");
+ assertEquals("changing", cache.obtain("/old-prefix/one").getId());
+ MetaData updated = register("changing", "/new-prefix/**");
+ assertNull(cache.obtain("/old-prefix/two"));
+ assertEquals("changing", cache.obtain("/new-prefix/one").getId());
+ cache.remove(updated);
+ assertNull(cache.obtain("/new-prefix/two"));
+ registered.remove(old);
+ }
+
+ @Test
+ public void testDisabledWildcardDoesNotMatch() {
+ MetaData metadata =
MetaData.builder().id("disabled").path("/disabled-prefix/**").enabled(false).build();
+ registered.add(metadata);
+ cache.cache(metadata);
+ assertNull(cache.obtain("/disabled-prefix/one"));
+ }
+
+ private MetaData register(final String id, final String path) {
+ MetaData metadata =
MetaData.builder().id(id).path(path).enabled(true).build();
+ registered.add(metadata);
+ cache.cache(metadata);
+ return metadata;
+ }
+}
