https://bz.apache.org/bugzilla/show_bug.cgi?id=66564
Bug ID: 66564
Summary: Improvements to WebResource Cache eviction
Product: Tomcat 11
Version: 11.0.0-M3
Hardware: PC
Status: NEW
Severity: enhancement
Priority: P2
Component: Catalina
Assignee: dev@tomcat.apache.org
Reporter: steven.kea...@servicenow.com
Target Milestone: -------
Created attachment 38540
--> https://bz.apache.org/bugzilla/attachment.cgi?id=38540&action=edit
patch for enhancement to WebResource Cache eviction
Summary:
The current Cache implementation for WebResource objects can be improved.
Every 10s it sorts all of the items in the cache in order to pre-evict
10% of the space in LRU order, to enable application threads to cache objects
without
having to evict any items. If the cache space grows so that an application
thread DOES have to evict some items, it evicts items in a worse than random
order.
By persisting the results of sorting the cache items across calls to background
processing, the expensive time spent sorting becomes much reduced.
Further benefits are that when an application thread DOES have to evict some
items,
it can usually evict items in LRU order rather than the random order.
Details:
Here is a description of the current implementation, which
is needed to understand the issues being addressed.
The Cache object is a cache for WebResource objects.
1) Every 10s a background process runs which evicts enough
entries from the cache to reduce the cache space (amount of memory,
not number of entries) to 90% of the maximum. It does this
by sorting the cache entries from oldest validation time to
youngest validation time and by evicting entries in that order
until the goal is met. However, it will NOT evict an entry which
has been validated within its its ttl, which defaults to 5s.
2) The advantage of "pre-eviction" objects from the Cache is that
in many cases it enables items to be added to the cache without
having to evict any items to keep the cache space within limits.
Since the background process
reduces the cache space to 90% of the maximum every 10s, the Cache would have
to add new items adding up to more than 10% of the cache space in 10s in order
to have the cache space exceed its limit.
3) The advantage of "pre-evicting" objects in a background process is that
this (hopefully) moves most of the eviction work to a background thread
which allows the application threads to do Cache inserts without
doing any evictions.
4) When a new item is added to the cache, Cache checks the cache space
to ensure it is still within the desired limit. As discussed above,
in many cases the insert will NOT cause the cache space to exceed its limit
because of the pre-eviction of objects by a background process. Unfortunately,
it is still possible for the cache space to exceed its limit.
5) When the addition of a new item grows the Cache to exceed the cache space
limit, it will
evict a "random" subset of the cache until it reduces the cache space to
95% of its max. It evicts a "random" subset to avoid the lengthy computation
needed
to find the LRU (least recently used) items. It finds the "random" subset by
evicting items in the resourceCache in iteration order. Since the
resourceCache is a map
from WebAppPath to CachedResource, this means it preferentially
evicts items whose WebAppPath hashes to values that map to cache buckets at
small indices in the resourceCache.
This is random in the sense that hash values are random, but is non random in
the sense that
certain WebAppPaths will always have a much higher probability of being evicted
than others.
6) However, it will NOT evict an entry which has been validated within its its
ttl, which defaults to 5s.
Because of this fact, it is possible that the insert of the new item in the
cache would result in the
cache space limit being exceeded and Cache would NOT be able to evict enough
entries to reduce the
space. In this case the new item is NOT inserted, or more specifically
it is inserted and then removed.
Here are the issues with this implementation that we fix:
7) In section (5), why does the Cache reduce the cache space to 95% in of max
instead of reducing it to just below the max?
Wouldn't it make more sense for each cache insert to evict a small number of
items than for one
cache insert to evict a large number of items and others evict no items?
My guess is that this was done because if each cache insert evicted a small
number of items
then each insert would require the creation of an iterator over resourceCache.
Perhaps the
overhead of this iterator creation was a concern? (ConcurrentHashSet iterators
work by iterating over
all of the hash buckets from first to last; since Cache evicts items in this
order then the index
of the first hash bucket with an item gets progressively larger as more items
are evicted in this way,
which increases the inititalization time of an iterator).
8) The time spent in (1) is wasteful. Even if just a few items are evicted the
background
process does alot of work. Every time the background process runs
it sorts all of the items in resourceCache, by making a TreeMap with an
appropriate
Comparator and inserting all items in resourceCache. This takes time
O(n*log(n))
where n is the number of items in resourceCache. As n gets large this time can
become
significant. It discards this TreeMap at the
conclusion of the background process, and the garbage generation that results
is also unwelcome.
9) The practice (see sections (1) and (6)) of avoiding the eviction of cache
entries which have been validated in
the last ttl seconds makes no sense. The ttl is the MAXIMUM time that a cache
entry can be assumed valid
and is not the MINIMUM time that it should live in the cache. The harm of this
practice is the
needless complexity of having to handle the possibility that Cache may not be
able to admit a new entry because
it is unable to evict enough older entries. Also and more importantly, this
practice favors the presence in the cache
of older validated items in the cache over newer validated items in the cache,
which is opposite the
practice of keeping the most recently used items in the cache.
10) The current implementation does something dangerous: it creates a TreeMap
of the items in resourceCache,
sorting on the CachedResource.nextCheck field. This is dangerous because the
nextCheck field might be
updated concurrently during the TreeMap initialization. This violates the
precondition of the TreeMap that
the key field should not be altered while an item is in the map.
Here is how we propose to fix these issues:
11) we add a lastUsed field to the CachedResource object for tracking the last
time a resource was accessed,
and a lastUsedForSorting field which is a snapshot of the lastUsed field at a
time T.
12) the background process will create an array resourceCacheLru[] containing
the items in resourceCache at time T
ordered by ascending lastUsedForSorting time. And it will maintain a variable
resourceCacheLruEvictNext which is
the index of the next item in resourceCacheLru[] to check for eviction.
This array will persist even after the background process
returns. Then each time the background process runs it can evict items in LRU
order by using these persisted
variables, instead of recreating this sorted list every time. Specifically, it
evicts the next item by
code like this:
int indexToEvict = resourceCacheLruEvictNext++;
if (indexToEvict < resourceCacheLru.size()) {
CachedResource cr = resourceCacheLru[indexToEvict];
if (evictable(cr)) {
reourceCache.remove(cr.getWebAppPath());
resourceCacheLru[indexToEvict] = null;
}
}
13) Of course as the useful items in resourceCacheLru[] are reduced, the
background process must eventually
rebuild resoureCacheLru[]. When the space used by remaining evictable items in
resourceCacheLru[] is less than 10% of the max,
and the current space usage of resourceCache is >= 50% of the max,
then the background process will rebuild resourceCacheLru[] and reset
resourceCacheLruEvictNext. This ensures
that upon background process completing, new items whose cumulative space is
atleast 20% of max can
be inserted into the cache before resourceCacheLru[]
becomes useless for finding the next item to evict. The 20% figure results from
the fact that background process
pre-evicts 10% of max space, and ensures that the remaining evictable items are
>= 10% of max.
14) One might point out that upon return to the background process
the items in resourceCacheLru[] do not accurately order the items in
resourceCache, since there will probably
have been inserts, evictions, and retrievals of resourceCache items in the
interim. This is true, however
resourceCacheLru[] does have useful information. First note that newly
inserted items, and items accessed
since resourceCacheLru[] was created, will have a lastUsed value > any
resourceCacheLru[i].lastUsedForSorting
value. If we ignore these items then the remaining items in resourceCacheLru[]
are indeed the least recently
used items in resourceCache, ordered by ascending lastUsed. It is just that
resourceCacheLru[] does not
order ALL of the items in resourceCache. This leads to this definition for
evictable() as used in (12):
boolean evictable(CachedResource cr) {
// cr.lastUsed is set to -1 when cr is deleted from the resourceCache
// cr.lastUsed is given a larger value when cr is retrieved from the
cache.
return cr.lastUsed != -1 && cr.lastUsed == cr.lastUsedForSorting;
}
15) we no longer avoid evicting CachedResource which have been validated in the
last ttl.
As discussed in (9) this makes little sense, and in return we can always
guarantee that we
can reduce cache space below the limit.
16) To calculate "space used by remaining evictable items in
resourceCacheLru[]" efficiently,
which is required in (12), we maintain a variable resourceCacheLruEvictableSize
which is equal
to the cumulative size of the items in resourceCacheLru[] at creation time, and
is reduced when
an item is accessed the first time since creation, or deleted from the cache
since creation.
17) We modify (5), which describes what happens when we insert an item into the
cache and it expands the
cache space above the maximum, as follows.
Instead of evicting a "random" element of resourceCache, we first try evicting
using resourceCacheLru[] as described in (12). This is a big improvement
because
it means we are evicting based on the LRU policy
rather than the random policy. Only if the useful info in resourceCacheLru[]
is exhausted do
we then evict "random" elements of resourceCache by using a persisted iterator
over resourceCache.
Also, in this case we evict just enough items to reduce the cache space below
the max which means that each
application thread pays a relatively equal cost.
If you like the enhancement then I would develop comprehensive test cases for
the new behavior.
--
You are receiving this mail because:
You are the assignee for the bug.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@tomcat.apache.org
For additional commands, e-mail: dev-h...@tomcat.apache.org
