FWD » Core Development » Database

FastFindCache currently reacts to writes by invalidating cached results very aggressively. In a workload where the same index entries are repeatedly invalidated and then immediately queried again, this creates a thrashing pattern:
- the cache entry is cleared,
- the next lookup repopulates it,
- another update clears it again,
- and the cycle repeats.
This means the cache is spending effort on entries that may not stay valid long enough to pay for the cost of caching them. The result is extra invalidation traffic, extra repopulation work, and limited real benefit for very hot keys.

A practical fix is a 2-hit admission policy:
- do not cache an entry the first time it is requested,
- only admit it into FastFindCache if the same key is requested again soon after.

The challenge here is to efficiently remember when a key was already requested for caching, if this can be achieved, the benefit would be an overall more efficient ffc.

The initial implementation shows promise, these are the results of comparing memory retention of FFC, trunk vs 11638a:
multi tenant app harness + 1 user creation: 2.2mb -> 0.6mb, 3.6x less retained memory
large gui app unit tests: 9.9mb -> 1.3mb, 7.5x less retained memory

The performance is not reduced since we are no longer caching results that were not hit anyway.

The main parts of the implementation are:
- The first time a key is seen, it is stored in a small probation structure keyed by the same cache key components already used by FastFind, so we can recognize the exact same lookup later.
- On the second sighting within the probation window, the entry is admitted into the main cache and stored normally.
- The probation state has a bounded lifetime and size, it uses a short TTL window, currently 1 minute, and a small LRU cache so it does not grow without limit.
- Invalidation paths now also clear the probation state for the affected table or index, so stale "seen once" keys do not linger after writes.
- The policy applies before the main cache write, so it helps both positive hits and negative results avoid immediate cache tharshing.

I am tidying up the code and will request a review. Any suggestions are welcomed.

Danut, will you be able to do the performance testing?

Artur Școlnic wrote:

Danut, will you be able to do the performance testing?

Yes, will do.

This is based on trunk/16684 that was converted with 11650a.

Thank you, Danut.
On my part the multi tenant app performance is unchanged. Proceeding with a wider test plan.

Multi tenant app regression testing is ok, also tested large gui application unit tests.
Alex, please take a quick look at the branch, if you also approve of the changes, we can merge.

Alex, please take a quick look at the branch, if you also approve of the changes, we can merge.

With these changes, isn't #9802 changes to FFCache nullified? The changes in #9802 were meant to allow a single table to hold more than N (the per-table limit) records at once by having one single big cache with 100.000 slots that can be shared across tables. With probation, you add back the former limitation of having at most N probes (previously it was 1024, now it is 2048). In #9802, if you bring in 6k records of a table using a nested FIND, then FFCache won't be used at all anymore as there are at most 2k probes available for one table? Increasing the number of probes (e.g. 10k) is not a solution, just because, this way, you end up having 10k * number of tables records (i.e. 10M slots) that may break memory.

Even if we overcome this, I can't understand fully why probation is avoiding trashing.

In a workload where the same index entries are repeatedly invalidated and then immediately queried again

This will trash the probation map instead of the cache. As you put and invalidate the probes, why is it working faster comparing to putting and invalidation in cache directly? In other words, you mention that we put, invalidate and put again - and thus the cache is being trashed. But this happens now for probes collection instead (qut, invalidate and put again). In fact, there is also an overhead of "moving" the records from probes to cache. I can't tell how #11638-11 is justified.

I added #10776 and #11037 as related:

• #10776 is a performance regression that occurred on POC after changing FFCache on #9802. I am inclined to say that #11638 fix you propose now is indirectly reverting the changes in #9802 and removes the performance regression caused on POC. However it also reverts the performance improvement meant for #9802 in the first place. Interestingly enough, there is a fix for #10776 that keeps the #9802 functionality in place and it also mitigated the performance regression. I am curious if the changes here (#11638) on top of #10776 are going to still show an improvement on POC.
• #11037 is a functional regression that occurred on the same customer as of POC after #9802. It doesn't relate completely to #11638 from performance POV, but it may spoil the execution as they imply a broken behavior.

All changes are in 11037a. Please make an effort to review them, test them (including performance) and check if the thrashing in 11037a is still a problem. If it is still a problem, please check how 11638a is going to mitigate it:

• if invalidation are slow in cache, why are they not slow in probes
• if put is slow in cache, why is it not slow in probes
• first-time queries should be fast in cache as fast as in probes. I don't see a reason why probes would be faster.
• second-time queries should be slower considering the probes (as they won't find the record in cache)
• third-time queries should be slower considering that probes shall be promoted so and extra remove + put is being done instead of a direct put.
• 4th+ time queries should work at the same rate.

Alex, the thrashing aspect was more of a speculation on my part, while working on this I observed that a lot of cached records are never read, the changes in 11638a do a single thing, they ensure that FFC caches only the record identifiers that are read at least twice. The improvement comes from storing up to 7 times less data in the FFC.

The improvement comes from storing up to 7 times less data in the FFC.

But maybe stored in the probes collection instead. As the probes is set to 2k limit per table, then the memory limit is, of course, mitigated. Highly used tables will be limited to 2k entries in the FFcache in one burst. Of course, if you go through 2k records of a table twice and then another 2k records of a table a second time and so on, you can end up with more than 2k records of a table in the ffcache. But on long running queries fetching 6k records, none will end up in the ffcache.

However, I can sense the problem you are stating here as well. If a nested find goes through 100.000 records, than all of these 100.000 records will fill the ffcache, so other highly queried rows will simply be removed due to a long running query of a session. As this cache is shared across sessions, a session that is idle may "lose" all of its cached work and it may need to start again. These 100.000 records may never be used, so it behaves like a "clear cache".

A report engine session may spoil the ffcache with the rows from one single table it reports from.

I would think that a cache policy might be more important in this context. Entries that a queried more often to stay more in the cache than the ones that are not when it comes to eviction. If an entry was queried 10 times, then allow it to survive the least-recently-used eviction 10 times (or log_2 10 = 3 times). This will make records that are added once and removed afterward (thrashing) work exactly like probes. The policy will evict them just like it evicts them now from probes collection. On the other hand, the more used entries will survive more. A solution is to change Node to store a hit statistic. Node.remove would eventually touch instead of remove if its statistic bypasses an exponentially growing threshold. This is a very early idea; it may be worth doing some technical research on this subject first.

Anyway, please tackle #10776 and #11037 first. They are both functional and performance-wise. This will give us a better baseline to work on future performance improvements.

• LRU force skips (-lruskips): The number of times to access a buffer in the Primary Buffer Pool before moving it to the end of the LRU chain.
  It lets a buffer be touched n times before its LRU position is actually updated. Set -lruskips 100 and a buffer gets a counter; on a hit, the counter increments and the process moves on without taking the latch. Only on the 100th touch does it pay the cost of repositioning. The FWD equivalent would be the touch method in FFC, since we know it is a point of contention, we could implement a similar algorithm that moves the record to the front of the queue only if it is really hot.

• Blocks in Alternate Buffer Pool (-B2): Specify tables for which the records in the cache will not be evicted. The tables must be specified by the user. In OE it is a separate structure, maybe we could also add a second level FFC, or simply a list of tables and on invalidation we could consult that list, if the table is there, do not evict.