LruCache appears to actually be implemented/used as least recently inserted

[bokken]

I see 2 places where LruCache instances are created:

1. QueryExecutorBase for statementCache.
2. PgConnection for fieldMetadataCache.

Both usages are passing false for accessOrder, which is simply passed along to the LinkedHashMap constructor where the description is:

accessOrder - the ordering mode - true for access-order, false for insertion-order

So that seems to mean that these are not least recently /used/ caches but least recently /created/.
Is that what is actually intended?

[davecramer]

Excellent question. I am trying to find the commit that added it without much luck. Seems we would want it to evict the least used first.

[jorsol]

I wonder if we could replace the LruCache with ConcurrentLinkedHashMap (https://github.com/ben-manes/concurrentlinkedhashmap/) WDYT?

I think it should be possible to embed a slightly modified version of this inside the project, it's Apache-2.0 but should be ok to embed the code (or we can also ask permission to Ben Manes).

[bokken]

@jorsol, that project does not appear to be actively maintained, as the last commit was from 2015.
This does bring up the question of what the policy should be towards dependencies on other projects.

[jorsol]

It should not be a direct dependency, that's why I mention embedding the code, the project is not actively maintained because the successor is a more complex caching library called Caffeine, but the use of ConcurrentLinkedHashMap as an LRU Cache should be simpler and stable.

[davecramer]

In general I don't like to be dependent on other projects. SCRAM was a special case as it was ostensibly written for us.

As far as embedding code goes you don't have to ask, but you do have to include the fact that you used it and add their license.

I see no reason to just not use the LruCache correctly. I don't think it's in a critical path ?

[jorsol]

While the LruCache should work fine, ConcurrentLinkedHashMap could offer a little more performance in highly concurrent environments (although I have not tested that) and possibly other features, a cache should always be performant, if not, it defeats its purpose.

This might be used in a critical path since can be used as a shared cache in some places.

[davecramer]

If I'm not mistaken the cache here is being used to avoid parsing the query if possible. I would expect the difference in the time to lookup the query in the cache vs parse the query to be significant. I could be wrong but I doubt the speed of the actual cache implementation is significant. However not being implemented as an LRU cache would be significant.

[bokken]

Both places an lru cache is used is on a per connection basis. So while thread safety is important, there should be little or no actual contention.

[bokken]

#2007 fixes our use of LruCache and deprecates the constructors which allow it to be based on insertion order.
@jorsol I do think we could move to an implementation based on ConcurrentLinkedHashMap and maintain all current functionality. My guess, however, is that the overall memory footprint is larger while performance differences are negligible in absence of contended usage.

[ben-manes]

You are welcome to use and embed ConcurrentLinkedHashMap if it is helpful. Of course if it not then don’t.

It’s commonly embedded. mssql-jdbc, Groovy, micronaut, etc do so. It’s small and easily hackable. Prefer it to excessive hacking around LHM or writing a custom implementation if a fully synchronized LRU is not good enough.

[vlsi]

@bokken , the original use case for the cache was "borow-return". For instance, CachedQuery borrowQueryByKey(Object key) borrows a value from the cache, so concurrent execution of the same-looking SQL do not overlap (they do not share statement id).

For example, the client code might use multiple prepared statements with the same SQL text at the same time (e.g. fetch from the corresponding resultsets.
I am not sure if it is valid to share the parsing result, so the implementation was to borrow a value from the cache, and return it as the query execution is finished.

That is why "least recently inserted" was the same as "least recently used".

---

The caches are not shared across connections, so there's no need in CLHM.

---

CLHM and friends requires Java 8, so that was not an option earlier.
Caffeine brings 1MiB+ of classes :-(

[bokken]

@vlsi, as commented my recent comment on the PR, the 2 uses of LruCache are split in the pattern of usage. The statement cache does use the borrow (remove/put) pattern you describe, while the field metadata uses the more traditional put/get pattern.

I agree that, since these instances are not shared across connections, there is not value in CLHM. It is important that the cache is thread safe because it will likely be read and mutated across multiple threads through the life of the (pooled) connection, but there should be no (or very little) contention on those actions.

[jorsol]

The caches are not shared across connections, so there's no need in CLHM.

Well, that might be an area of improvement, allow to share the cache across connection improving hit ratio and reduce duplicate objects.

CLHM and friends requires Java 8, so that was not an option earlier.

But now it could be an option.

Caffeine brings 1MiB+ of classes :-(

Caffeine and/or other external dependency is out of the scope here.

Anyway I won't longer hijack this discussion, the use of CLHM belongs to an entirely different discussion. ;-)

[vlsi]

It is important that the cache is thread safe because it will likely be read and mutated across multiple threads through the life of the (pooled) connection

A proper connection pool should ensure thread safety even in the case when a connection implementation is not thread-safe.

But now it could be an option.

That is true.

[bokken]

A proper connection pool should ensure thread safety even in the case when a connection implementation is not thread-safe.

We do not appear to be consistent in assuming/relying on that. The handful of examples where we appear to not assume that are per connection specific items like Encoding, TypeInfoCache, and the LruCache being discussed here. All are developed to be thread safe. It would be good to have a consistent definition of what is expected to support thread safety/concurrent usage.

Well, that might be an area of improvement, allow to share the cache across connection improving hit ratio and reduce duplicate objects.

The Query objects in statementCache do not appear to lend themselves to reuse across connections. While the NativeQuery being wrapped is immutable, the SimpleQuery seems to keep track of connection specific things like statementName, what fields have been prepared, whether the portal has been described, etc. There could be a benefit to reusing NativeQuery instances across connections, but it seems the query objects themselves are tied to connections.
The fieldMetadataCache, on the other hand, does appear to lend itself to re-use across connections to the same logical database (maybe identified by user and url?). The key is basically the tableOid and column position and the value is immutable.

[MarkMielke]

Even without StampedLock, I still see:

1. A lot of introduced complexity, much of which has nothing to do with the insertion order. And, no data to show why they are improvements. In particular, the unwrapping of put() into an "innertPut()" to avoid "overhead" of putAll() calling put(), seems like the same type of pre-optimization as the use of StampedLock. Completely unnecessary, and no evidence on the table that the resulting code is faster. It may well be slower.
2. One updated test case. There are many code paths being introduced, but no new test cases to ensure they are working properly. For example, I saw removal of a null check, but it isn't immediately clear to me that null is an impossibility. The null check improves robustness - possibly it is unnecessary robustness, but given all the extra code added for abstract performance gains, it seems strange to also remove a null check that might provide safety.

I'd like to see the change that just implements "LruCache to order by access, instead of by update". If more than this is necessary, there should be some explanation as to why it is necessary, and it should be a separate review that can be evaluated on its own merits, without tying it to this review.

[bokken]

@MarkMielke, I agree the innerPut should not have remained when removing usage of stamped lock. I was too focused on replacing the StampedLock and missed that (rather obvious) change to unwind.

Can you provide an example of new code paths added? The 2 actions are now null checked in the constructor and populated with default behaviors if caller provided null. The statementCache will construct with custom actions. The fieldCache will use the default actions. The Nullable annotation was removed from the variables, so the checker framework is also validating that they are not null.
For some reason it appears we have lost our code coverage, but my best guess is that the only new uncovered code would be the now deprecated constructor public LruCache(int maxSizeEntries, long maxSizeBytes, boolean accessOrder). If there is something I am missing, I will definitely add tests.

[MarkMielke]

Ok, thanks.

For new code paths - as some of the more complex code is removed, there might only be a few left. It was ones like this that had me curious:

    this.createAction = createAction != null ? createAction : k -> {
    this.onEvict = onEvict;	      throw new UnsupportedOperationException("createAction == null, so can't create object");
    };
    this.onEvict = onEvict != null ? onEvict : v -> { };

Each ?: represents a code path. The question going through my head when seeing the earlier version is that I'm not sure whether value can be null or not, and whether the check for null could be safely dropped or not. The same applies to the handlers above. But, it may be that all of these are covered by existing test cases and the collection of all the changes made it seem worse than it really was in my first review. :-)

I do appreciate the care to review the comments and try to understand and address them. Thanks.

[bokken]

Those null checks are not (net) new, simply moved to the constructor rather than at each use. Null is possible for both, coming from the constructor(s) which only accept size restrictions. Specifically this is used by the fieldMetadataCache in 'PgConnection`[1].

I assume that the use case of a null createAction resulting in the UnsupportedOperationException is likely never tested. That would only occur if borrow is called on an instance without a createAction (and without an entry for the given key). This flow does not exist in the "real" code and is not covered in the LruCacheTest either.

The evictAction being null could get exercised as part of using the fieldMetadataCache, but I am not certain if any tests generate enough usage to lead to evictions.

[1] - https://github.com/pgjdbc/pgjdbc/blob/master/pgjdbc/src/main/java/org/postgresql/jdbc/PgConnection.java#L323