fix: fix session budget penalty logic#13857
Conversation
There was a problem hiding this comment.
Code Review
This pull request updates 'SessionCreationBudget.java' to use 'Collections.min()' for retrieving the earliest timestamp from 'delayedCreationTokens', removing the assumption that the list is sorted and deleting the early-exit optimization in 'drainCreationFailures()'. The reviewer suggests using a 'PriorityQueue' instead of a 'List' to optimize finding the minimum element from O(N) to O(1) and improve overall performance.
| } | ||
|
|
||
| return delayedCreationTokens.get(0); | ||
| return Collections.min(delayedCreationTokens); |
There was a problem hiding this comment.
While Collections.min() correctly finds the earliest timestamp, it has a time complexity of O(N) for a List, where N can be up to maxConcurrentRequests (default 1000). This could become a performance bottleneck if getNextAvailableBudget() is called frequently.
Consider using a java.util.PriorityQueue for delayedCreationTokens. This would make getNextAvailableBudget() an O(1) operation (peek()), and addCreationFailure() an O(log N) operation. drainCreationFailures() could also be implemented more efficiently by repeatedly polling expired items from the head of the queue (O(k*logN) where k is the number of expired items).
Remove the early break when draining creation failures pool and update the logic when returning the next available budget. The list is not strictly increasing order of the timestamps. Updates to the penalty duration can change the orders of the timestamps in the list: