FWD » Core Development » Database

PS: this is not caused directly by #9802, but rather a latent bug that is exposed by more "intensive" caching.

• The fix is almost complete. You are missing the cases where resolved[i] = ((Resolvable) subst).resolve();.
  • In other words, the field reference that is resolved might be a handle/raw/etc.

I extended the check to resolvable also, the code is in rev 16070.

+               if (isContextLocalBDT(subst))
+               {
+                  return null;
+               }

This check is not correct. subst is known to be a FieldReference. You need a check for resolved[i].

I changed it.

Harness and webui navigation passed.

10337a was merged to trunk as rev 16069.

Reverted the changes from trunk rev 16051. I will create 10337b and use it to bring those back with a more robust memory management.
I do agree with Alexandru and am also positive that the new branch will not regress the performance gains 9802f brought.

Artur, please archive branches after you merge them - 10337a is still 'active'.

Review of 10337b:

void put(RecordIdentifier<String> recID, Map<L2Key, RecordIdentifier<String>> l3Cache, L2Key l2Key)

+         ReverseCacheEntry val = reverseCache.get(recID);
+         if (val == null)
+         {
+            List<L2Key> l2Keys = new LinkedList<>();
+            l2Keys.add(l2Key);
+            val = new ReverseCacheEntry(l3Cache, l2Keys, recID);
+            reverseCache.put(recID, val);
+         }
+         else
+         {
+            val.l2Keys.add(l2Key);
+         }

This code from ReverseLookup.put is not correct. Mind that the l3Cache parameter you get is not honored when the reverseCache is hit. So you end up registering all FFcache entries of a specific DMO to the same l3Cache. This is wrong as the same DMO can be registered for same table, but different indexes (aka different L3 caches). First key is a combination of table id and multiplex, the second key is the index id and the third key is the complex one holding the FQL and parameters.

• beside the LRU cache, create a map Map<RecordIdentifier<String>, Value> just like before. The keys can be weakly referenced just like in trunk. In fact, all "weak referencing" work can be reintroduced.
• The LRU cache will only gather L2Keys. They can be weakly referenced.
  • On expiry, just invalidate the entries from the reverse look-up map, which ultimately will invalidate records from ffCache.
• To invalidate entries from reverse look-up, you should:
  • transform the forward linked list to a doubly linked list (instead of next, store prev and next)
  • call Node.delete. This will delete the Node of the linked list. This should be straight-forward.

You can start from scratch with trunk (but maybe add the emptyRecordsReverseCache logic). Next to the existing reverse look-up caches, create a separate LRU cache as described with their respective listeners. The only difference is that the lists will have a different implementation to allow expiry to call Node.delete.

In fact, I think there is a small caveat. We still need a touch mechanism so that the LRU cache will mark the Node as "recently" used.
I think this can be added in FastFindCache.getImpl. When you find something with l3Cache.get(k.k2), you shall also touch that in reverse look-up.
This functionality was not present in #9802 implementation either.

I think that the memory leak in 9802f was caused mainly by the absence of a designated ExpiryListener for the emptyRecordsCache.
Adding the listener, the weak references in Value and Node, and touching the reverse lookup entries on L3 hit should be enough to solve the memory leak and get back the performance improvement.

Alexandru, what if we introduce a new type of LRU that has weak references as keys? This will take care of the situations when the L2 or L3 cachs are cleared entirely and reverse lookup entries become orphaned.
The explicit invalidation was already handled correctly.
I would like to avoid having multiple heavy structures, if possible.

Alternatively, we can disregard the ReveresLookup class in favor of a more light weight solution:

Map<RecordIdentifier<String>, List<L2Key>> reverseLookup = new WeakHashMap<>();

Artur Școlnic wrote:

Alternatively, we can disregard the ReveresLookup class in favor of a more light weight solution:
A structure that maps weak references of the record identifiers to the associated L2 keys.

I implemented an early version, it looks promising, the only downside is that the L3 is bound again. I think that if we make the reverseLookup a LRU cache with weak referenced keys, we can unbound the L3 cache.

I think that if we make the reverseLookup a LRU cache with weak referenced keys, we can unbound the L3 cache.

Technically, a LRU cache with weak keys might ameliorate this problem.

But I want to express my concern of the fact that we are still allowing the reverse-look-up to grow indefinitely on the second axis (linked list). We have no guarantee that the linked list is bound. A weak LRU will only ensure that the list will be evicted from memory more eagerly. But I think there is still a blind spot. In pseudo-code:

repeat i = 1 to 1000000000:
   find first tt where tt.f1 = i.
end.

There is no invalidation in this code, but I think the FFCache will really cache 1 billion finds (especially for NO_RECORD case).

Alexandru Lungu wrote:

But I want to express my concern of the fact that we are still allowing the reverse-look-up to grow indefinitely on the second axis (linked list).

You are right. The obvious solution to this problem is the use of a custom LRU Linked List instead of a linked list. On main cache hit, we also touch the entry from that list, so the relevant entries are kept at the head of the list. This way we eliminate the need for ReverseLookup as a designated class, we only use something like:

Map<WeakReference<RecordIdentifier<String>>, LRUList<L2Key>> reverseLookup; 

Well, I guess a map with weak references as keys is a WeakHashMap :)

Map<RecordIdentifier<String>, LRUList<L2Key>> reverseLookup = new WeakHashMap<>();

Considering the L3 cache for FFCache is unbound, we are now missing a bound on the first axis. The record identifier has the same order of magnitude as the number of records in the database. They will always be retained by the Fast Find Cache in an unbound fashion.

How about

LRUCache<WeakReference<RecordIdentifier<String>>, LRUList<L2Key>> reverseLookup;

Although, invalidation of the L3 caches on revereseLookup/LRUList expiry would be a nightmare. We would need to keep the reference to the Key, not just the L2Key, in order to identify exactly which L3 cache needs invalidation.

LRUCache<WeakReference<RecordIdentifier<String>>, LRUList<L2Key>> reverseLookup;

This is something that might work, of course. But this will provide two levels or orthogonal caching. In other words, there will be at most X DMOs cached. Each DMOs will have at most Y entries cached. The total amount of memory required is X * Y. Having it 1000 and 1000 will mean having at most 1000 queries cached per DMO and at most 1000 DMOs with some caching.

Such technique brings us back (more or less) to the OG problem where only 1000 queries were cached per (table, index) pair. We chose to have a consistent caching against all entries in the FFCache by moving the LRU logic in ReverseLookup. In fact, the initial requirement from #9802 was to define in directory.xml that I want X entries and the FastFindCache will have at most X entries at any time (not to starve more intensively used tables or DMOs). Right now we are unsatisfying that requirement by having unreasonable bounds set per number of DMOs or per number of L2Keys for a DMO.

Although, invalidation of the L3 caches on revereseLookup/LRUList expiry would be a nightmare. We would need to keep the reference to the Key, not just the L2Key, in order to identify exactly which L3 cache needs invalidation.

Artur, please follow the idea of #10337-19. I do not understand why are we holding back from having two structures implemented. If you favor code clarity, mind embedding them in a ReverseLookupCache class to abstract away the fact that there are two structures being used.

Review of 10337b/16074:

• rewrite reverseLookup.lruCache.get(new ReverseLookup.Node(l3Cache, k.k2)); to reverseLookup.touch(l3Cache, k.k2). This will avoid exposing Node and lruCache outside ReverseLookup
• open/close curly braces for ReverseLookup constructor
• the expiry listener should invalidate only the expired node, not the whole list (Value)
  • this means that something like node.remove() should be called.
• avoid putting a node in value and lruCache if already exists. In other words, if lruCache contains the node, simply skip the whole put process. In the current implementation, nodes are eagely added to Value, but only putIfAbsent in lruCache.
• add javadoc to equals and hashcode.
• return l2Key.hash == node.l2Key.hash; for equals check is not correct. Please use l2Key.equals(node.l2Key).
• The invalidate should abstract the doubly linked list delete as node.remove() to avoid duplicate code with expiry of LRU cache.
• Important: the Node should now store Key instead of L2Key. The LRUCache will not be able to distinguish between queries on different tables / multiplexes / indexes without more context. So an equals and hashcode should be implemented for key as well.

I addressed the review in rev 16075.

• add braces to the lambda inside ReverseLookup c'tor
• Indent lruCache javadoc (/** shouldn't be followed by doc; next two lines should be * ..., last line should be only one */)
• please move node = nextNode as the third clause of the for loop to avoid duplicating it in the conditional and at the end of the loop.
• please pre-cache the hash of Key to avoid computing it on each hashCode call.
• Node.remove shouldn't have any parameter.
  • If you remove an expired node from the list, you should no longer try to remove it again. The remove operation is redundant.
  • If you forcefully remove a node, then you should also treat the cache eviction there.
• reverseCache is unbound - which is completely fine. But mind that this means removing keys manually from it when the list becomes empty.
  • If a node expires and it was the last node of the list, then the reverseCache should evict the corresponding record identifier. This can be done in the expiry listener as the values of the LRU cache are the actual Value lists.
  • If you do computeIfAbsent in reverseCache, you risk adding a new empty list that may not be updated due to !lruCache.containsKey(node). reverseCache update should be conditioned.

• are the operations thread-safe considering that some FFCaches are cross-session? Is the expiry, touching, etc. operations thread-safe?
• I still want to understand if getCanonicalRecordIdentifier still fits in the current implementation and how.

Alexandru Lungu wrote:

• If a node expires and it was the last node of the list, then the reverseCache should evict the corresponding record identifier. This can be done in the expiry listener as the values of the LRU cache are the actual Value lists.

On expiry or removal of a node, the corresponding L3 cache entries are removed, which means that the weak references in reverseCache will be garbage collected.

• are the operations thread-safe considering that some FFCaches are cross-session? Is the expiry, touching, etc. operations thread-safe?

All the explicit put/get operations on the caches are synchronized in the persistent tables case. The only questionable thing is entry expiry, which is not synchronized in the LRUCache implementation, nor externally. Just to be sure I enclosed the expiry listener code in a synchronized block.

• I still want to understand if getCanonicalRecordIdentifier still fits in the current implementation and how.

It is used to get the true reference to a RecordIdentifier since we are working with weak references, so it is still useful.

I addressed the other issues in rev 16076.

• Please make Node class static again.
• short-circuit equals so that this == o returns true directly.
• Important: I think value.head is inconsistent after removal. If you remove a node, then value.head will still reference it, right? So when you add a new node, it will bring it back to life as it will be linked as node.next = head.
  • This also means that value.head == null won't ever be hit after invalidation?
• The synchronization in ReverseLookup c'tor is done on ReverseLookup, while other synchronization is done on FastFindCache instance. These locks are unrelated. I incline to say that the expiry is done eagerly and synchronous on ensureCapacity (so on put). That means that if put is synchronized, the expiry listener is also called in a thread-safe manner. I think the synchronize can be removed.
• hash class member is not read.

If a node expires and it was the last node of the list, then the reverseCache should evict the corresponding record identifier. This can be done in the expiry listener as the values of the LRU cache are the actual Value lists.

• This is reasonable, but requires testing to confirm.

Alexandru, I think we have an issue with the Key objects retention.
I did a memory profiling and Keys are accumulating at a steady rate, this causes Nodes to also stay in memory. Not sure what is causing this, maybe the fact that we use references to a Key to put objects in the ff cache, but primitive values to remove from it?.. Anyway, it is not entirely clear to me when a Key should be removed or GC`ed.

Alexandru Lungu wrote:

• Important: I think value.head is inconsistent after removal. If you remove a node, then value.head will still reference it, right? So when you add a new node, it will bring it back to life as it will be linked as node.next = head.

You are right, this also caused the issue from note 43. After fixing this problem, the Nodes are kept at a reasonable number, still more than the lruCache limit, but this is due to using weak references everywhere, AFAIK weak references do not guarantee a speedy garbage collection, the objects can linger in memory until the GC is forced to clear some memory.
I addressed the other issues, please review.

You are right, this also caused the issue from note 43. After fixing this problem, the Nodes are kept at a reasonable number, still more than the lruCache limit, but this is due to using weak references everywhere, AFAIK weak references do not guarantee a speedy garbage collection, the objects can linger in memory until the GC is forced to clear some memory.

I would rather be more eager with this then. This will put less pressure on the GC, especially in tight loops that use FIND. Please add eager removes of empty lists from the reverse look-up cache.

This actually is implemented for the explicit invalidation, but it needed to be added for the expiry event also.
I committed the changes.

I think we are still leaking memory, after one hour or running Harness on loop, there are 500k 'live' Node objects, after a force GC, 300k remained, which is way above the limit of 100k. They are consuming an insignificant amount of memory, but that usage has a linear growth. I think clearing L1/2 caches does not clean up the associated Nodes as well. Will investigate further.

I think we are still leaking memory, after one hour or running Harness on loop, there are 500k 'live' Node objects, after a force GC, 300k remained, which is way above the limit of 100k. They are consuming an insignificant amount of memory, but that usage has a linear growth. I think clearing L1/2 caches does not clean up the associated Nodes as well. Will investigate further.

You can decrease the cache size to something like 10 for more straight-forward testing. Or maybe even to 1 or 2 :)

The same thing happens in trunk, the number of leaked Node instances grows slowly, but surely. After 20 mins of harness, the number of live Nodes went from 400 to 7000.
I am assuming that the 'live objects' in VisualVm means objects that are still stored in memory and can't be GC'ed.

Alexandru Lungu wrote:

You can decrease the cache size to something like 10 for more straight-forward testing. Or maybe even to 1 or 2 :)

The limit of the lruCache does not matter, it is honored anyway, the problem is that we end up having Nodes that are not referenced in the lruCache, but are somewhere else.

I think the issue is that bulk invalidation where entire caches are cleared or removed do not clean up the associated Value/Nodes, in order to properly clean those, we would need to go through all L3 entries and invalidate one by one.

Artur Școlnic wrote:

I think the issue is that bulk invalidation where entire caches are cleared or removed do not clean up the associated Value/Nodes, in order to properly clean those, we would need to go through all L3 entries and invalidate one by one.

No. The LRU cache policy should have taken care of this, without the need to manually seek and destroy.

I may have misunderstood things a bit :) Apparently, there are multiple instances of ReverseLookup, which means multiple instances of lruCaches. For the application I am testing with, there are 7 instances, i set the limit to 100 records, the number of nodes does climb above 700, but after a GC, the total number never exceeds 700, so I guess this was a false alarm.
There is one change I made:

=== modified file 'src/com/goldencode/p2j/persist/FastFindCache.java'
--- old/src/com/goldencode/p2j/persist/FastFindCache.java    2025-08-06 11:51:43 +0000
+++ new/src/com/goldencode/p2j/persist/FastFindCache.java    2025-08-07 10:35:02 +0000
@@ -1027,7 +1027,7 @@
             }
             value.addNode(node);
             reverseCache.put(recID, value);
-            lruCache.put(node, value);
+            lruCache.put(node, null);
          }
          else
          {

I just realized that we don't actually need the values in the lruCache, it acts more like a queue, so only the nodes are needed.

I just realized that we don't actually need the values in the lruCache, it acts more like a queue, so only the nodes are needed.

The value is used in the expiry listener.

Forgot about that, I'll uncommit.

Testing status:
Harness and webui navigation - passed
Large customer application FWDTests and unit tests - passed
Large gui application unit tests - passed

I also monitored memory allocation over time, it seems ok. There are still an excessive amount of nodes created and alive in memory, but on GC they are erased.

Please merge 10337b to trunk after 10004a.

10337b was merged as rev 16106.