Consider you are building a financial back-office trade processing application. Trades are flowing in from the front-office system. To cope with the velocity and volume of the trades you want to use in-memory processing.

The trades are usually settled no later than 24 hours from trade execution. These trades objects can get very active during the current business day, but once they execute, you rarely need to access them again. So there is no need to keep settled trades in-memory. This means that when the number of entries keeps growing, you will want to evict older, unneeded trades from main memory, either by replicating them to a database or deleting them altogether.

 

Replicating to databases using XAP is easily done by deploying a mirror processing unit into your cluster. This is further explained here.

 

Why Go Beyond LRU?

If you want to use the Least Recently Used (LRU) strategy to manage what gets evicted from your in-memory data grid, you can use the GigaSpaces XAP built-in LRU eviction policy as explained here.

But configuring an LRU cache means you have to have a good estimation of certain characteristics of the trade stream and the in-memory data grid, such as the maximum throughput of the stream a trade maximum size, and the amount of RAM available. And all these inputs, which might change over time, go into defining the number of trades to be stored in-memory. This means LRU becomes a heuristic algorithm that requires you to change the different values and settings as the business grows.

This calls for better control over what gets evicted: what if the trade object has a Boolean settled field, and you can only evict trades that are set to ‘true’? What if trades by certain customers are known to be more prone to repeated processing than others?

Introducing XAP SpaceEvictionStrategy

SpaceEvictionStrategy is a new simple abstract class that XAP 9.1 users can extend. This class consists of an initialize method, onInsert, onRemove, etc., that are called whenever an action is performed on one of the entries in the in-memory data grid, and an evict method that is called by the cache manager (users don’t need to call to evict themselves) when there are more entries than the maximum cache size, or when memory is running low.

Initialize should mainly be used to initialize the user’s strategy supporting data structures, like so:

The action indicator methods are used to specify what your strategy should do in the event a specific entry is inserted or read from the in-memory data grid. For example, if you want to implement LRU, you should update the entry’s index in your supporting data structure when the object is being accessed. When implementing your strategy, keep in mind that these methods should provide a high level of concurrency. You can rest assure that the cache manager will not call two methods with the same entry concurrently (except for onRead() and onUpdate()), so using java’s concurrent package should suffice for most implementations. But onRead/Update should be guarded.

The most important method you should implement is: abstract int evict(int numOfEntries). This method gets the number of entries needed for eviction from the cache manager. According to your defined logic, you should call getEvictionManager().tryEvict(entry) and increase a counter each time you succeed. The return value is the number of successful removals.

In the PrioritizedEvictionStrategy example, we give a class a priority by using the SpaceEvictionPriority annotation. In this project we have three distinctive custom eviction strategies:

§ The single order package approach includes two strategies:

o ClassBasedEvictionFIFOStrategy evicts entries first by priority. This means it goes through all the priority numbers in the space in descending order (priorities must be positive integers, which means priority 0 is the most valuable and should get evicted last). After selecting the least valuable priority available, it tries to evict objects that belong to this priority by FIFO (First In, First Out). Here, you can see the way entries are inserted into the strategy class’s data structures with an index value which helps later with the order of eviction:

o ClassBasedEvictionLRUStrategy. This strategy acts exactly the same as the previous one except it updates the entry’s index when it is being accessed either by being read or by being modified. This fact transforms this strategy to an LRU strategy. Notice the fact that we try and remove the entry from the data structure and only perform actions if we are successful. This is because onRead() and onUpdate() can be called concurrently with the same entry.

 

§ Specific order package: So far, we have seen two single ordering strategies that follow the priority based classification. Now we will see where the custom eviction strategy really gives freedom to users. In this package we have the ClassSpecificEvictionStrategy strategy which is used as a delegator to class specific eviction strategies.

In the onInsert method we get for each entry its priority we go to the relevant map of classes for the priority level and get the entry’s class specific eviction strategy.

We do the same in all of the other action indicator methods.

When the call to evict arrives we go by priority and get the class-specific strategy from the map. We then delegate the evict command to this specific strategy, as shown here:

In the concrete FIFO class specific implementation all the entries belong to the specific class and get evicted by FIFO:

In our example, Michael Phelps has a medal showcase of only 1000 medals (which is our in-memory data grid), but he keeps winning medals, which means he keeps adding medals to the showcase. So Phelps decides that he would never want to evict his gold medals even if it means they burst out of his showcase and break it (filling a space with “None” evict-able objects will eventually result in OutOfMemoryException). The “None” strategy is simply an empty implementation with the evict method set to return 0. As for silver medals, he decides they should get evicted by LRU, and bronze should be evicted by FIFO. The eviction is still based on the class’ priority first, which guarantees bronze will get evicted before silver and silver before gold, but each type of object now has its own strategy for eviction. The class-specific strategies can be found in the specific order package.

Class-Based Eviction Strategy: Going Beyond LRU
Sagi Bernstein
Tagged on: