FastFindCache.java
/*
** Module : FastFindCache.java
** Abstract : Caches and serves record information based on the find properties in order to avoid the database
** trip, making the simple queries much faster.
**
** Copyright (c) 2020-2024, Golden Code Development Corporation.
**
** -#- -I- --Date-- ---------------------------------------Description---------------------------------------
** 001 OM 20200708 First revision.
** 002 ECF 20201201 Minor optimization.
** OM 20210927 The cache must take into account changes of all field, not only from unique indexes.
** ECF 20211005 Reworked invalidation of cached results referencing non-indexed properties to be more
** performant. As a trade-off, queries referencing non-indexed properties, which produce a
** negative result (i.e., no record is found) do not have the negative result cached.
** CA 20220104 Node.l3Cache must be a weak reference, otherwise once the direct cache invalidates a key,
** the reverse lookup has no chance of being cleaned up, as this is not done explicitly.
** 003 AL2 20220608 Implemented synchronizeWithReturn to avoid creating separate results array.
** 004 DDF 20230608 Made the size of the L2 and L3 caches configurable.
** DDF 20230613 Removed the static block that reads the configuration sizes of the cache.
** CacheManager will handle the finding of the configuration size and the
** cache creation.
** DDF 20230627 Made the cache final.
** 005 CA 20240323 Resolve the FieldReference value when the cache key is built, to allow cachine on this
** value.
** 006 AI 20240418 Updated constructor of Key to take the non indexed props as difference of all props and
** only indexed props used in query instead of all indexed props.
** 007 RAA 20240613 Added tenantInstances map for storing instances of FastFindCache per tenant + database id.
** BS 20230511 Shared cache instance per persistent database.
** RAA 20240627 Added removeCache method.
** 008 SP 20240731 Replaced calls to synchronizeWithReturn and synchronize with specific function calls,
** to reduce capturing lambda usage.
** 009 OM 20240909 Tenant caches use tenant databases as keys and are stored as normal values.
** 010 CA 20240924 Allow a L2/L3 cache to be cleared instead of discarding the instace, to help the garbage
** collector.
*/
/*
** This program is free software: you can redistribute it and/or modify
** it under the terms of the GNU Affero General Public License as
** published by the Free Software Foundation, either version 3 of the
** License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU Affero General Public License for more details.
**
** You may find a copy of the GNU Affero GPL version 3 at the following
** location: https://www.gnu.org/licenses/agpl-3.0.en.html
**
** Additional terms under GNU Affero GPL version 3 section 7:
**
** Under Section 7 of the GNU Affero GPL version 3, the following additional
** terms apply to the works covered under the License. These additional terms
** are non-permissive additional terms allowed under Section 7 of the GNU
** Affero GPL version 3 and may not be removed by you.
**
** 0. Attribution Requirement.
**
** You must preserve all legal notices or author attributions in the covered
** work or Appropriate Legal Notices displayed by works containing the covered
** work. You may not remove from the covered work any author or developer
** credit already included within the covered work.
**
** 1. No License To Use Trademarks.
**
** This license does not grant any license or rights to use the trademarks
** Golden Code, FWD, any Golden Code or FWD logo, or any other trademarks
** of Golden Code Development Corporation. You are not authorized to use the
** name Golden Code, FWD, or the names of any author or contributor, for
** publicity purposes without written authorization.
**
** 2. No Misrepresentation of Affiliation.
**
** You may not represent yourself as Golden Code Development Corporation or FWD.
**
** You may not represent yourself for publicity purposes as associated with
** Golden Code Development Corporation, FWD, or any author or contributor to
** the covered work, without written authorization.
**
** 3. No Misrepresentation of Source or Origin.
**
** You may not represent the covered work as solely your work. All modified
** versions of the covered work must be marked in a reasonable way to make it
** clear that the modified work is not originating from Golden Code Development
** Corporation or FWD. All modified versions must contain the notices of
** attribution required in this license.
*/
package com.goldencode.p2j.persist;
import com.goldencode.cache.*;
import com.goldencode.p2j.persist.orm.*;
import com.goldencode.p2j.security.*;
import com.goldencode.p2j.util.*;
import java.lang.ref.*;
import java.util.*;
import java.util.BitSet;
import java.util.concurrent.ConcurrentHashMap;
/**
* Implementation of FastFind caching algorithm. The internal structures use a triple-cache to store the
* id-s of the records that should be present in session cache. The first level is keyed by the table unique
* identifier. The second level is the index id, also guaranteed to be unique (positive for unique indexes and
* negative for the rest). The last level is keyed by the FQL of the query, the navigation type, and
* substitution parameters. We need to store the identifier (private key) as the cache value, rather than the
* DMO instance itself, because:
* <ul>
* <li>DMO instances cannot be shared across contexts;</li>
* <li>we don't want two sources of cached DMO instances.</li>
* </ul>
* <p>
* Temporary tables are handled as context-local. Permanent tables are shared, but only within one database to
* avoid mix-ups when separate databases use same names for tables. Thus, pointer to a database is required to
* lookup tables - it is used as a key leading to appropriate cache instance.
* <p>
* The first two levels of cache size are not limited. They are the table and indexes unique ids and are
* stable, governed by database structure. Only the very last level is an actual {@code LRUCache} object
* whose size will need to be configured based on how many records should be cached for each index of a
* table. However, since the invalidation of the cache will occur quite often, the value can be kept small.
* <p>
* Cache Invalidation: the cache is individually invalidated for each affected index when a record is updated.
* On insert and delete operations all indices are invalidated for respective table. On a rollback event all
* affected tables are invalidated.
* <p>
* Concurrency: The cache access is thread-safe for temporary because the instances are context local. When
* accessing the permanent table shared instances, all accesses are synchronized since the LRU cache
* implementation also alter the internal structure.
*
* TODO: implement support for {@code Resolvable} substitution parameters.
*/
public class FastFindCache
{
/** Constant for representing a negative result (i.e., the lack of result) for a query. */
public static final RecordIdentifier<String> NO_RECORD = new RecordIdentifier<>("", -1L);
/** The instances for permanent database(s). */
private static final Map<Database, FastFindCache> permanentInstances = new ConcurrentHashMap<>();
/** The context-local instance for the current session for temp-tables. */
private static final ContextLocal<FastFindCache> tempTableInstances = new ContextLocal<FastFindCache>()
{
@Override
protected FastFindCache initialValue()
{
return new FastFindCache(false);
}
};
/** The internal data, as a triple-level cache: table-uid x index x other-information. */
private final Map<Long, Map<Integer, Cache<L2Key, RecordIdentifier<String>>>> cache = new HashMap<>();
/** Reverse cache of record identifiers to invalidation info, for queries with non-indexed properties */
private final ReverseLookup reverseLookup = new ReverseLookup();
/** Differentiate between permanent and temporary tables and caches. */
private final boolean isPermanent;
/**
* Constructor for internal use.
*
* @param isPermanent
* Differentiate between permanent and temporary tables and caches.
*/
private FastFindCache(boolean isPermanent)
{
this.isPermanent = isPermanent;
}
/**
* Obtain the singleton instance, if FastFind mode enabled.
* Return {@code null} to disable FastFind mode.
*
* @param temporary
* Use {@code true} to get the instance object for a temp-table database. They are context-local
* objects. When {@code false} the global instance for permanent databases is returned.
* @param database
* The instance of the database to work with.
*
* @return the static instance of {@code FastFindCache}, or {@code null} if FastFind mode is disabled.
*/
public static FastFindCache getInstance(boolean temporary, Database database)
{
if (temporary)
{
return tempTableInstances.get();
}
if (database == null)
{
throw new IllegalArgumentException("Database can not be null when instantiating FastFindCache");
}
return permanentInstances.computeIfAbsent(database, db -> new FastFindCache(true));
}
/**
* Remove a cache based on a (tenant id, database id) key.
*
* @param db
* The database to be deleted.
*/
public static void removeTenantCache(Database db)
{
if (!db.isTenant())
{
System.err.println("This API can be used only for tenant databases.");
return;
}
permanentInstances.remove(db);
}
/**
* Combines the DMO uid and the optional temp-table multiplex value into a single {@code long} value.
*
* @param uid
* The DMO uid.
* @param multiplex
* The {@code multiplex} value of a temp-table. Must be positive. Use 0 or {@code null} for
* permanent tables.
*
* @return a single {@code long} value used as level 1 key in cache.
*/
public static long combine(int uid, Integer multiplex)
{
if (multiplex == null || multiplex == 0)
{
return uid; // permanent tables
}
return (((long) multiplex) << 32) | uid;
}
/**
* Creates a cache key.
* <p>
* If provided, all substitution parameters ({@code values}) are checked if they are instances of
* {@code Resolvable}. These are not yet supported so no key is generated if they are encountered.
*
* @param buffer
* The buffer that holds the record. Used for obtaining the DMO uid and multiplex (for
* temp-tables).
* @param indexId
* The id of the index used when executing the query.
* @param fql
* The fql of the query which selected the keyed record.
* @param properties
* The set of properties used in {@code fql}.
* @param type
* The type of navigation. Must be one of {@code FIRST}, {@code LAST} or {@code UNIQUE} values
* of the {@code QueryConstants}.
* @param values
* The substitution values. May be {@code null}.
*
* @return a new {@code Key} for the provided parameters or {@code null} if not supported.
*/
static Key createKey(RecordBuffer buffer,
int indexId,
String fql,
BitSet properties,
int type,
Object[] values)
{
if (values != null)
{
Object[] resolved = null;
for (int i = 0; i < values.length; i++)
{
Object subst = values[i];
if (subst instanceof FieldReference)
{
if (resolved == null)
{
resolved = new Object[values.length];
System.arraycopy(values, 0, resolved, 0, values.length);
values = resolved;
}
resolved[i] = ((Resolvable) subst).resolve();
}
else if (subst instanceof Resolvable)
{
return null;
}
}
}
// all substitution parameters were checked and none is a Resolvable.
return new Key(buffer, indexId, fql, properties, type, values);
}
/**
* Query the cache for a value.
*
* @param k
* The key for cache.
*
* @return a {@code RecordIdentifier} structure. In the case of a cache-hit, this is the key for
* a {@code Session} cache, and {@code null} otherwise.
*/
public RecordIdentifier<String> get(Key k)
{
if (k == null)
{
// an invalid key caused by the presence of Resolvable substitution parameters in values
return null;
}
if (!isPermanent)
{
// no synchronization needed here
return getImpl(k);
}
synchronized (this)
{
return getImpl(k);
}
}
/**
* Saves a result in cache. Supports both real records and also "NOT-FOUND" results, when the second
* parameter is {@code null}.
*
* @param k
* The key for cache.
* @param value
* The value to be stored in cache. Only the primary key is important. If {@code null}, -1 will
* be used to mark the result as not present in database.
*/
public void put(Key k, Record value)
{
// if no key or record represents a housekeeping (e.g., dirty database) copy or an incomplete record
// (partial fields are populated due to EXCEPT/FIELDS options), don't store it
if (k == null ||
(value != null && (value.checkState(DmoState.COPY) || value.checkState(DmoState.INCOMPLETE))))
{
return; // throw some error?
}
if (!isPermanent)
{
// no synchronization needed here
putImpl(k, value);
return;
}
synchronized (this)
{
putImpl(k, value);
}
}
/**
* Invalidates the index for a table. Called when an operation on the table affected an index.
*
* @param dmoUid
* The unique id of the table.
* @param multiplex
* The multiplex of the records to be invalidated, if any.
* @param unique
* The set of dirty unique indices which need to be invalidated.
* @param nonUnique
* The set of dirty unique indices which need to be invalidated.
*/
public void invalidate(int dmoUid, Integer multiplex, BitSet unique, BitSet nonUnique)
{
if ((unique == null || unique.isEmpty()) && (nonUnique == null || nonUnique.isEmpty()))
{
return;
}
if (!isPermanent)
{
// no synchronization needed here
invalidateImpl(dmoUid, multiplex, unique, nonUnique);
return;
}
synchronized (this)
{
invalidateImpl(dmoUid, multiplex, unique, nonUnique);
}
}
/**
* Invalidate any cached result which matches the given DMO name and primary key, iff {@code dirtyProps}
* intersects with the set of non-indexed properties used in the associated FQL query.
*
* @param dmoName
* DMO implementation class name of the record that was touched.
* @param id
* Primary key of the DMO that was touched.
* @param dirtyProps
* The set of properties touched by an update to the DMO.
*/
public void invalidate(String dmoName, long id, BitSet dirtyProps)
{
// quick out if nothing to do
if (dirtyProps.isEmpty() || cache.isEmpty())
{
return; // this should not happen, anyway
}
if (!isPermanent)
{
// no synchronization needed here
reverseLookup.invalidate(new RecordIdentifier<>(dmoName, id), dirtyProps);
return;
}
synchronized (this)
{
reverseLookup.invalidate(new RecordIdentifier<>(dmoName, id), dirtyProps);
}
}
/**
* Invalidates all indexes of a table.
*
* @param dmoUid
* The table uid whose indexes are invalidated.
* @param multiplex
* The multiplex of the records to be invalidated if any.
*/
public void invalidate(int dmoUid, Integer multiplex)
{
invalidate(dmoUid, multiplex, false);
}
/**
* Invalidates all indexes of a table.
*
* @param dmoUid
* The table uid whose indexes are invalidated.
* @param multiplex
* The multiplex of the records to be invalidated if any.
* @param remove
* Flag indicating if the cache can be actual cleared, as the DMO is out of scope.
*/
public void invalidate(int dmoUid, Integer multiplex, boolean remove)
{
long dmoId = combine(dmoUid, multiplex);
if (!isPermanent)
{
if (remove)
{
cache.remove(dmoId);
return;
}
// no synchronization needed here
Map<Integer, Cache<L2Key, RecordIdentifier<String>>> map = cache.get(dmoId);
if (map != null)
{
map.forEach((idxId, cache) -> cache.clear());
}
return;
}
synchronized (this)
{
if (remove)
{
cache.remove(dmoId);
return;
}
Map<Integer, Cache<L2Key, RecordIdentifier<String>>> map = cache.get(dmoId);
if (map != null)
{
map.forEach((idxId, cache) -> cache.clear());
}
return;
}
}
/**
* Invalidate a single index of a table.
*
* @param dmoUid
* The table uid whose indexes are invalidated.
* @param multiplex
* Multiplex ID for a temp-table ({@code null} for a persistent table).
* @param idxUid
* Index identifier, unique to its table.
*/
public void invalidate(int dmoUid, Integer multiplex, int idxUid)
{
if (!isPermanent)
{
// no synchronization needed here
invalidateImpl(dmoUid, multiplex, idxUid);
return;
}
synchronized (this)
{
invalidateImpl(dmoUid, multiplex, idxUid);
}
}
/**
* Invalidates records from a list of DMOs.
*
* @param dmoList
* The collection of unique identifiers of the DMOs to be invalidated.
*/
public void invalidate(Collection<Long> dmoList)
{
if (!isPermanent)
{
// no synchronization needed here
invalidateImpl(dmoList);
return;
}
synchronized (this)
{
invalidateImpl(dmoList);
}
}
/**
* Saves a result in cache. Supports both real records and also "NOT-FOUND" results, when the second
* parameter is {@code null}.
*
* @param k
* The key for cache.
* @param value
* The value to be stored in cache. Only the primary key is important. If {@code null}, -1 will
* be used to mark the result as not present in database.
*/
private void putImpl(Key k, Record value)
{
// There are multiple configured sizes for the caches, the discriminator for the
// L2 and L3 caches should not be changes since it is must be the same one
// used in the directory configuration.
Map<Integer, Cache<L2Key, RecordIdentifier<String>>> l2Cache =
cache.computeIfAbsent(k.tableId, x -> CacheManager.createLinkedMapCache(FastFindCache.class,
"L2",
10));
Cache<L2Key, RecordIdentifier<String>> l3Cache =
l2Cache.computeIfAbsent(k.indexId, x -> CacheManager.createLRUCache(FastFindCache.class,
"L3",
100));
// for a positive result (i.e., a record was found), ensure we use the canonical instance of the
// record identifier, so that if it is stored in the reverse lookup cache, the weak keys can be
// garbage collected
RecordIdentifier<String> cacheVal =
value == null
? NO_RECORD
: reverseLookup.getCanonicalRecordIdentifier(new RecordIdentifier<>(value.getClass().getName(),
value.primaryKey()));
boolean hasNonIndexedProps = k.k2.nonIndexedProps != null && !k.k2.nonIndexedProps.isEmpty();
// cache all positive results (i.e., a record was found); only cache negative results (i.e., no
// record was found) when the query references NO non-indexed properties
if (cacheVal != NO_RECORD || !hasNonIndexedProps)
{
l3Cache.put(k.k2, cacheVal);
}
// if the query has a positive result AND uses non-indexed properties, create a reverse lookup entry
// for it, to permit fast invalidation
if (cacheVal != NO_RECORD && hasNonIndexedProps)
{
reverseLookup.put(cacheVal, l3Cache, k.k2);
}
}
/**
* Query the cache for a value.
*
* @param k
* The key for cache.
*
* @return a {@code RecordIdentifier} structure. In the case of a cache-hit, this is the key for
* a {@code Session} cache, and {@code null} otherwise.
*/
private RecordIdentifier<String> getImpl(Key k)
{
Map<Integer, Cache<L2Key, RecordIdentifier<String>>> l2Cache = cache.get(k.tableId);
if (l2Cache == null || l2Cache.isEmpty())
{
return null;
}
Cache<L2Key, RecordIdentifier<String>> l3Cache = l2Cache.get(k.indexId);
if (l3Cache == null || l3Cache.size() == 0)
{
return null;
}
return l3Cache.get(k.k2);
}
/**
* Invalidates the index for a table. Called when an operation on the table affected an index.
*
* @param dmoUid
* The unique id of the table.
* @param multiplex
* The multiplex of the records to be invalidated, if any.
* @param unique
* The set of dirty unique indices which need to be invalidated.
* @param nonUnique
* The set of dirty unique indices which need to be invalidated.
*/
private void invalidateImpl(int dmoUid, Integer multiplex, BitSet unique, BitSet nonUnique)
{
Map<Integer, Cache<L2Key, RecordIdentifier<String>>> table = cache.get(combine(dmoUid, multiplex));
if (table == null)
{
return;
}
if (unique != null)
{
for (int u = unique.nextSetBit(0); u >= 0; u = unique.nextSetBit(u + 1))
{
// unique indexes have non-null, positive ids
Cache<L2Key, RecordIdentifier<String>> l3 = table.get(u + 1);
if (l3 != null)
{
l3.clear();
}
}
}
if (nonUnique != null)
{
for (int i = nonUnique.nextSetBit(0); i >= 0; i = nonUnique.nextSetBit(i + 1))
{
// nonunique indexes have non-null, negative ids
Cache<L2Key, RecordIdentifier<String>> l3 = table.get(-i - 1);
if (l3 != null)
{
l3.clear();
}
}
}
}
/**
* Invalidate a single index of a table.
*
* @param dmoUid
* The table uid whose indexes are invalidated.
* @param multiplex
* Multiplex ID for a temp-table ({@code null} for a persistent table).
* @param idxUid
* Index identifier, unique to its table.
*/
private void invalidateImpl(int dmoUid, Integer multiplex, int idxUid)
{
Map<Integer, Cache<L2Key, RecordIdentifier<String>>> table = cache.get(combine(dmoUid, multiplex));
if (table != null)
{
Cache<L2Key, RecordIdentifier<String>> l3 = table.get(idxUid);
if (l3 != null)
{
l3.clear();
}
}
}
/**
* Invalidates records from a list of DMOs.
*
* @param dmoList
* The collection of unique identifiers of the DMOs to be invalidated.
*/
private void invalidateImpl(Collection<Long> dmoList)
{
for (Long dmoId : dmoList)
{
Map<Integer, Cache<L2Key, RecordIdentifier<String>>> map = cache.get(dmoId);
if (map != null)
{
map.forEach((idxId, cache) -> cache.clear());
}
}
}
/**
* The second level key for Fast Find algorithm. It uses this class as cache key for quickly checking
* whether a particular record was found recently.
*/
private static class L2Key
{
/** The fql of the query which selected the keyed record. */
private final String fql;
/** The set of <em>non-indexed</em> properties used in {@code fql}. */
private final BitSet nonIndexedProps;
/** The type of navigation. Must be one of FIRST, LAST or UNIQUE values of the {@code QueryConstants} */
private final int type;
/** The substitution values. May be {@code null}. */
private final Object[] values;
/** The precomputed hash code. */
private final int hash;
/**
* The unique constructor builds the immutable key.
*
* @param fql
* The fql of the query which selected the keyed record.
* @param nonIndexedProps
* The set of <em>non-indexed</em> properties used in {@code fql}. May be {@code null} if
* {@code fql} is {@code null} or references no non-indexed properties.
* @param type
* The type of navigation. Must be one of {@code FIRST}, {@code LAST} or {@code UNIQUE} values
* of the {@code QueryConstants}.
* @param values
* The substitution values. May be {@code null}.
*/
private L2Key(String fql, BitSet nonIndexedProps, int type, Object[] values)
{
this.fql = fql;
this.nonIndexedProps = nonIndexedProps;
this.type = type;
this.values = values;
// precompute hash key
// The [nonIndexedProps] do not need to be part of key because they are deterministically
// derived/extracted from [fql]. They are used only to invalidate objects in the cache later.
this.hash = 31 * (31 * type + Arrays.hashCode(values)) + (fql != null ? fql.hashCode() : 0);
}
/**
* Test for equality with another object.
*
* @param o
* The other object.
*
* @return {@code true} if and only if the objects are equals.
*/
@Override
public boolean equals(Object o)
{
if (this == o)
{
return true;
}
if (o == null || getClass() != o.getClass())
{
return false;
}
L2Key l2Key = (L2Key) o;
if (hash != l2Key.hash)
{
return false;
}
if (type != l2Key.type)
{
return false;
}
if (!Objects.equals(fql, l2Key.fql))
{
return false;
}
return Arrays.equals(values, l2Key.values);
}
/**
* Obtain the precomputed hash code.
*
* @return the precomputed hash code.
*/
@Override
public int hashCode()
{
return hash;
}
}
/**
* A special key used for accessing values in cache. Internally, it is compound from two private keys, one
* for each cache level. They are grouped together to simplify the external interface to a single entity
* instead of two.
*/
static class Key
{
/**
* An computed value that uniquely identifies the DMO table and, in case temp-table the multiplex.
* It is composed from: the unique id of the DMO interface of the keyed record in lower 4 bytes and
* the optional multiplex number in the higher bits.
*/
private final long tableId;
/** The id of the index used when executing the query. */
private final int indexId;
/**
* The key for the second level cache, composed of type of query (one of {@code FIRST}, {@code LAST} or
* {@code UNIQUE} constants of the {@link QueryConstants}, the optional FQL predicate used in query and
* the optional substitution values.
*/
private final L2Key k2;
/**
* Creates the immutable key object for accessing values in cache.
*
* @param buffer
* The buffer that holds the record. Used for obtaining the DMO uid and multiplex (for
* temp-tables).
* @param indexId
* The id of the index used when executing the query.
* @param fql
* The fql of the query which selected the keyed record.
* @param properties
* The set of properties used in {@code fql}.
* @param type
* The type of navigation. Must be one of {@code FIRST}, {@code LAST} or {@code UNIQUE} values
* of the {@code QueryConstants}.
* @param values
* The substitution values. May be {@code null}.
*/
private Key(RecordBuffer buffer,
int indexId,
String fql,
BitSet properties,
int type,
Object[] values)
{
int tableId = 0;
int multiplex = 0;
if (buffer != null)
{
tableId = buffer.getDmoInfo().getId();
if (buffer.isTemporary())
{
multiplex = buffer.getMultiplexID();
}
}
this.tableId = combine(tableId, multiplex);
this.indexId = indexId;
BitSet nonIndexedProps = null;
if (properties != null)
{
RecordMeta recMeta = buffer.getDmoInfo().getRecordMeta();
// determine all properties used by the query which do NOT represent indexed fields for the table
BitSet allIndexedProps = indexId > 0 ?
recMeta.getUniqueIndices()[indexId - 1] :
recMeta.getNonuniqueIndices()[-indexId - 1];
nonIndexedProps = (BitSet) properties.clone();
nonIndexedProps.andNot(allIndexedProps);
if (nonIndexedProps.isEmpty())
{
nonIndexedProps = null;
}
}
this.k2 = new L2Key(fql, nonIndexedProps, type, values);
}
}
/**
* A reverse cache of record identifiers to values which contain information to enable the quick
* invalidation of individual, cached results from the primary cache. Only results of queries which
* use non-indexed properties exist in this reverse cache. It is not necessary to store other mappings,
* because these are already "bulk" invalidated by record inserts/deletes (all results for a table) or
* by updates to indexed properties (all results for a set of indices).
* <p>
* <strong>Important implementation note:</strong> it is imperative that only a "canonical" {@link
* RecordIdentifier} is used as a key in this reverse cache. The same canonical instance of the record
* identifier must be used as the cached result in the primary cache (i.e., at the L3 level). Not doing
* so can cause a memory leak, because we use a weak map for this reverse cache. This is necessary
* because bulk invalidation (i.e., for an entire table or set of indices) can "orphan" entries in this
* reverse cache. However, if only canonical {@code RecordIdentifier} instances are used as keys for
* this cache (and as values in the primary, L3 caches), any orphaned entries in this reverse cache will
* be cleaned up eventually during garbage collection.
* <p>
* The {@link ReverseLookup#getCanonicalRecordIdentifier(RecordIdentifier)} method is used to retrieve
* a canonical {@code RecordIdentifier}.
*/
private static class ReverseLookup
{
/** Weak map of canonical record identifiers to information needed to invalidate cache entries */
private final Map<RecordIdentifier<String>, Value> cache = new WeakHashMap<>();
/**
* Add an entry to the reverse cache.
*
* @param recID
* Unique record identifier, which may represent one or more primary cache entries.
* @param l3Cache
* The third level of the primary cache, in which a cache result for the given record
* identifier is stored.
* @param l2Key
* The key used to identify a cached result in the {@code l3Cache}.
*/
void put(RecordIdentifier<String> recID, Cache<L2Key, RecordIdentifier<String>> l3Cache, L2Key l2Key)
{
Value value = cache.get(recID);
if (value == null)
{
value = new Value(recID);
cache.put(recID, value);
}
value.addNode(l3Cache, l2Key);
}
/**
* Get the canonical instance of the given {@code RecordIdentifier}.
*
* @param recID
* A record identifier.
*
* @return The canonical {@code RecordIdentifier} instance for {@code recID}. If there is not yet a
* reverse lookup entry for {@code recID}, it is returned as the canonical instance.
*/
RecordIdentifier<String> getCanonicalRecordIdentifier(RecordIdentifier<String> recID)
{
Value value = cache.get(recID);
if (value != null)
{
RecordIdentifier<String> referent = value.ref.get();
if (referent != null)
{
recID = referent;
}
}
return recID;
}
/**
* If any cached results with non-indexed properties are associated with the given record identifier,
* invalidate each result whose FQL's non-indexed properties intersect with the given set of dirty
* properties.
*
* @param recID
* Record identifier of any cached result which might require invalidation.
* @param dirtyProps
* The set of properties touched by an update. For performance reasons, we do not compare
* the old and new values of each property, only check whether the property was touched.
*/
void invalidate(RecordIdentifier<String> recID, BitSet dirtyProps)
{
if (cache.isEmpty())
{
return;
}
Value value = cache.get(recID);
if (value != null)
{
value.invalidate(dirtyProps);
if (value.head == null)
{
cache.remove(recID);
}
}
}
/**
* The value object in the reverse cache, which contains the information needed to invalidate all
* cached results associated with the {@link RecordIdentifier} keys in the reverse cache. This
* includes a weak reference to the canonical {@code RecordIdentifier} instance, and a linked list
* of nodes containing invalidation information. Each node represents a single, L3 result in the
* primary cache.
*/
private static class Value
{
/** A weak reference to the canonical record identifier instance */
private final WeakReference<RecordIdentifier<String>> ref;
/** Head of the list; always the newest node added */
private Node head;
/**
* Constructor.
*
* @param recID
* Record identifier. This must be the canonical instance.
*/
Value(RecordIdentifier<String> recID)
{
this.ref = new WeakReference<>(recID);
}
/**
* Add a node to the linked list of invalidation nodes.
*
* @param l3Cache
* The L3 cache containing a cached result for the record associated with the record
* identifier.
* @param l2Key
* The key used to remove a single cached result from the {@code l3Cache} upon
* invalidation.
*/
void addNode(Cache<L2Key, RecordIdentifier<String>> l3Cache, L2Key l2Key)
{
Node node = new Node(l3Cache, l2Key);
// make the new node the head of the list and have it point to the previous head, if any
node.next = head;
head = node;
}
/**
* Walk the linked list of nodes and invalidate any L3 cached result whose non-indexed properties
* intersects with the given set of dirty properties. If a result is invalidated, drop the
* associated node from the linked list.
*
* @param dirtyProps
* The set of properties touched by an update.
*/
private void invalidate(BitSet dirtyProps)
{
for (Node node = head, prev = null; node != null; prev = node, node = node.next)
{
if (!node.l2Key.nonIndexedProps.intersects(dirtyProps))
{
continue;
}
// remove the entry from the L3 cache
Cache<L2Key, RecordIdentifier<String>> l3 = node.l3Cache.get();
if (l3 != null)
{
l3.remove(node.l2Key);
}
// remove the node from the list
if (head == node)
{
head = node.next;
}
else if (prev != null)
{
prev.next = node.next;
}
}
}
}
/**
* A node containing information required to invalidate a single, L3 cached result. The node is an
* element of the linked list in a {@code Value} object.
*/
private static class Node
{
/** L3 cache containing the cached result which may require invalidation */
private final WeakReference<Cache<L2Key, RecordIdentifier<String>>> l3Cache;
/** Key associated with an L3 cached result */
private final L2Key l2Key;
/** The next node in a linked list, if any */
private Node next = null;
/**
* Constructor.
*
* @param l3Cache
* L3 cache containing the cached result which may require invalidation.
* @param l2Key
* Key associated with an L3 cached result.
*/
Node(Cache<L2Key, RecordIdentifier<String>> l3Cache, L2Key l2Key)
{
this.l3Cache = new WeakReference<>(l3Cache);
this.l2Key = l2Key;
}
}
}
}