apache / apache/shenyu

[BUG] — `BaseDataCache.selectorAccept`/`ruleAccept`: O(n² log n) re-scan + re-sort on EVERY sync event

Open
#6,796 1 comment 0 reactions 0 assignees View on GitHub
priority: medium type: performance
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.