RFR: 8259886 : Improve SSL session cache performance and scalability [v2]

[djelinski]

On Tue, 16 Feb 2021 19:38:50 GMT, djelinski <github.com+30433125+djelinski at openjdk.org> wrote:

>>> I may think it differently. It may be hard to know the future frequency of an cached item based on the past behaviors. For the above case, I'm not sure that K=3 is used less frequently than K=1. Maybe, next few seconds, K=1 could be more frequently.
>> 
>> I agree that such prediction might not be 100% accurate. But, quick google search reveals that there are [many](https://www.usenix.org/system/files/hotstorage20_paper_eytan.pdf) [articles](https://link.springer.com/article/10.1007/PL00009255) that claim that LRU caches offer better hit rates than FIFO, especially for in-memory caches.
>>> I would like a solution to following the timeout specification: keep the newer items if possible.
>> 
>> That's a trivial change; all we need to do is change `true` to `false` [here](https://github.com/openjdk/jdk/blob/abe0e238bd25adb1ddd2b655613899bfa063cd85/src/java.base/share/classes/sun/security/util/Cache.java#L268). But, as stated above, LRU is better than FIFO, so I wouldn't want to do that.
>> 
>> I could keep LRU and add another linked list that would store items in the order of their expiration dates; then we could quickly scan that list for expired items. Note: the order of expiration dates is not necessarily the order of insertion, because 1) `System.currentTimeMillis()` is not monotonic - it can move back when something changes the system time, 2) the expiration date is calculated at insertion time, so if someone changes the timeout on a non-empty cache, new items may have shorter expiration time than old ones. So, I'd either need to address that first (change `currentTimeMillis` to `nanoTime` and store creation time instead of expiration time), or use insertion sort for adding items (which would get very slow if either of the above mentioned situations happened).
>> Let me know your thoughts.
>
> Well, if removing all expired items before evicting live ones is a non-negotiable, implementing all operations in constant time is much easier with FIFO, where we only need to keep one item order.
> The new commits contain the following changes:
> - use `nanoTime` instead of `currentTimeMillis` to make sure that time never goes back
> - store insertion time instead of expiration time, so that older items always expire before newer ones, even when timeout is changed
> - change internal hash map to store (and evict) items in insertion (FIFO) order
> - always stop scanning entries after finding the first non-expired item, because subsequent items are now guaranteed to have later expiration dates, and collected soft references are handled by reference queue.
> 
> tier1 and jdk_security tests passed; benchmark results show only minimal changes. I verified that none of the classes using `Cache` mentions LRU, looks like this was an implementation detail.

Actually there's a much easier solution to reduce the number of slow `put()`s without making any behavioral changes.
The cache object could store the earliest expire time, and then exit `expungeExpiredEntries()` early when current time is earlier than the earliest expire time - when it is, we know that there are no expired items in the queue and we can skip the scan entirely.
@XueleiFan do you think the above is worth exploring?

-------------

PR: https://git.openjdk.java.net/jdk/pull/2255