[BUG] — `BaseDataCache.selectorAccept`/`ruleAccept`: O(n² log n) re-scan + re-sort on EVERY sync event
- Dominant language
- Java
- Stars
- 8.8k
- Forks
- 3.1k
- Avg merge
- 7d 1h
- Merged PRs (30d)
- 85
Description
- severity: Medium-High
- files: `shenyu-plugin/shenyu-plugin-base/src/main/java/org/apache/shenyu/plugin/base/cache/BaseDataCache.java:268-301` (`selectorAccept` lines 288-301; `ruleAccept` lines 268-281); per-item dispatch `CommonPluginDataSubscriber.onSelectorSubscribe` → `cacheSelectData` → `selectorAccept`
- description: Each event does `existList.stream().filter(r -> !r.getId().equals(data.getId())).collect(toList())` (O(n)) → `.add` → `.stream().sorted(Comparator.combingBy(sort)).collect(toList())` (O(n log n)) → `put`. Combined with the per-event `removeIf` (O(n), lines 137/195), a batch refresh of N selectors under one plugin is O(N²) removals + O(N² log N) re-sorts on the sync thread, blocking all config propagation.
- impact: Gateway config lag under bulk admin writes / startup resync.
- suggested_fix: Keep the per-plugin list already sorted (insert via `Collections.binarySearch`+`set`, or `TreeSet`/`ConcurrentSkipListMap` keyed by sort); invalidate-by-id in O(log n); coalesce batch events so a refresh re-sorts once per plugin.
- confidence: High
---
_Identified during the 2026-08-02 deep re-scan; full list in [`docs/scan2-2026-08-02/06-medium-tiers.md`](docs/scan2-2026-08-02/06-medium-tiers.md)._
Contributor guide
No contributing guide indexed for this repository
Research direction
Start in shenyu-plugin/shenyu-plugin-base/src/main/java/org/apache/shenyu/plugin/base/cache/BaseDataCache.java:268-301, then trace CommonPluginDataSubscriber.onSelectorSubscribe through cacheSelectData to selectorAccept. Compare selectorAccept and ruleAccept with the per-item removeIf at lines 137/195. Done means bulk selector or rule refreshes no longer repeatedly rescan and resort the same per-plugin list while config propagation remains correct.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- backend, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100