GridGain Developers Hub
GitHub logo GridGain iso GridGain.com
GridGain Software Documentation

Eviction Policies

When Native Persistence is off, GridGain holds all cache entries in the off-heap memory and allocates pages as new data comes in. When a memory limit is reached and GridGain cannot allocate a page, some of the data must be purged from memory to avoid OutOfMemory errors. This process is called eviction. Eviction prevents the system from running out of memory but at the cost of losing data and having to reload it when you need it again.

Eviction is used in following cases:

When Native Persistence is on, a similar process — called page replacement — is used to free up off-heap memory when Ignite cannot allocate a new page. The difference is that data is not lost (because it is stored in the persistent storage) and therefore you are less concerned about losing data than about efficiency. Page replacement is automatically handled by GridGain and is not user-configurable.

Off-Heap Memory Eviction

Off-heap memory eviction is implemented as follows.

When memory usage exceeds the preset limit, GridGain applies one of the preconfigured algorithms to select a memory page that is most suitable for eviction. Then, each cache entry contained in the page is removed from the page. However, if an entry is locked by a transaction, it is retained. Thus, either the entire page or a large chunk of it is emptied and is ready to be reused.

Off-Heap Memory Eviction Mechanism

By default, off-heap memory eviction is disabled, which means that the used memory constantly grows until it reaches its limit. To enable eviction, specify the page eviction mode in the data region configuration. Note that off-heap memory eviction is configured per data region. If you don’t use data regions, you will have to explicitly add default data region parameters in your configuration to be able to configure eviction.

By default, eviction starts when the overall RAM consumption by a region gets to 90%. Use the DataRegionConfiguration.setEvictionThreshold(…​) parameter if you need to initiate eviction earlier or later.

GridGain supports two page selection algorithms:

  • Random-LRU

  • Random-2-LRU

The differences between the two are explained below.

Random-LRU

To enable the Random-LRU eviction algorithm, configure the data region as shown below:

<bean class="org.apache.ignite.configuration.IgniteConfiguration">
  <!-- Memory configuration. -->
  <property name="dataStorageConfiguration">
    <bean class="org.apache.ignite.configuration.DataStorageConfiguration">
      <property name="dataRegionConfigurations">
        <list>
          <!--
              Defining a data region that will consume up to 20 GB of RAM.
          -->
          <bean class="org.apache.ignite.configuration.DataRegionConfiguration">
            <!-- Custom region name. -->
            <property name="name" value="20GB_Region"/>

            <!-- 500 MB initial size (RAM). -->
            <property name="initialSize" value="#{500L * 1024 * 1024}"/>

            <!-- 20 GB maximum size (RAM). -->
            <property name="maxSize" value="#{20L * 1024 * 1024 * 1024}"/>

            <!-- Enabling RANDOM_LRU eviction for this region.  -->
            <property name="pageEvictionMode" value="RANDOM_LRU"/>
          </bean>
        </list>
      </property>
    </bean>
  </property>

  <!-- The rest of the configuration. -->
</bean>
// Node configuration.
IgniteConfiguration cfg = new IgniteConfiguration();

// Memory configuration.
DataStorageConfiguration storageCfg = new DataStorageConfiguration();

// Creating a new data region.
DataRegionConfiguration regionCfg = new DataRegionConfiguration();

// Region name.
regionCfg.setName("20GB_Region");

// 500 MB initial size (RAM).
regionCfg.setInitialSize(500L * 1024 * 1024);

// 20 GB max size (RAM).
regionCfg.setMaxSize(20L * 1024 * 1024 * 1024);

// Enabling RANDOM_LRU eviction for this region.
regionCfg.setPageEvictionMode(DataPageEvictionMode.RANDOM_LRU);

// Setting the data region configuration.
storageCfg.setDataRegionConfigurations(regionCfg);

// Applying the new configuration.
cfg.setDataStorageConfiguration(storageCfg);
var cfg = new IgniteConfiguration
{
    DataStorageConfiguration = new DataStorageConfiguration
    {
        DataRegionConfigurations = new[]
        {
            new DataRegionConfiguration
            {
                Name = "20GB_Region",
                InitialSize = 500L * 1024 * 1024,
                MaxSize = 20L * 1024 * 1024 * 1024,
                PageEvictionMode = DataPageEvictionMode.RandomLru
            }
        }
    }
};

Random-LRU algorithm works as follows:

  • Once a memory region defined by a memory policy is configured, an off-heap array is allocated to track the 'last usage' timestamp for every individual data page.

  • When a data page is accessed, its timestamp gets updated in the tracking array.

  • When it is time to evict a page, the algorithm randomly chooses 5 indexes from the tracking array and evicts the page with the oldest timestamp. If some of the indexes point to non-data pages (index or system pages), then the algorithm picks another page.

Random-2-LRU

To enable Random-2-LRU eviction algorithm, which is a scan-resistant version of Random-LRU, configure the data region, as shown in the example below:

<bean class="org.apache.ignite.configuration.IgniteConfiguration">
  <!-- Memory configuration. -->
  <property name="dataStorageConfiguration">
    <bean class="org.apache.ignite.configuration.DataStorageConfiguration">
      <property name="dataRegionConfigurations">
        <list>
          <!--
              Defining a data region that will consume up to 20 GB of RAM.
          -->
          <bean class="org.apache.ignite.configuration.DataRegionConfiguration">
            <!-- Custom region name. -->
            <property name="name" value="20GB_Region"/>

            <!-- 500 MB initial size (RAM). -->
            <property name="initialSize" value="#{500L * 1024 * 1024}"/>

            <!-- 20 GB maximum size (RAM). -->
            <property name="maxSize" value="#{20L * 1024 * 1024 * 1024}"/>

            <!-- Enabling RANDOM_2_LRU eviction for this region.  -->
            <property name="pageEvictionMode" value="RANDOM_2_LRU"/>
          </bean>
        </list>
      </property>
    </bean>
  </property>

  <!-- The rest of the configuration. -->
</bean>
// Ignite configuration.
IgniteConfiguration cfg = new IgniteConfiguration();

// Memory configuration.
DataStorageConfiguration storageCfg = new DataStorageConfiguration();

// Creating a new data region.
DataRegionConfiguration regionCfg = new DataRegionConfiguration();

// Region name.
regionCfg.setName("20GB_Region");

// 500 MB initial size (RAM).
regionCfg.setInitialSize(500L * 1024 * 1024);

// 20 GB max size (RAM).
regionCfg.setMaxSize(20L * 1024 * 1024 * 1024);

// Enabling RANDOM_2_LRU eviction for this region.
regionCfg.setPageEvictionMode(DataPageEvictionMode.RANDOM_2_LRU);

// Setting the data region configuration.
storageCfg.setDataRegionConfigurations(regionCfg);

// Applying the new configuration.
cfg.setDataStorageConfiguration(storageCfg);
var cfg = new IgniteConfiguration
{
    DataStorageConfiguration = new DataStorageConfiguration
    {
        DataRegionConfigurations = new[]
        {
            new DataRegionConfiguration
            {
                Name = "20GB_Region",
                InitialSize = 500L * 1024 * 1024,
                MaxSize = 20L * 1024 * 1024 * 1024,
                PageEvictionMode = DataPageEvictionMode.Random2Lru
            }
        }
    }
};

In Random-2-LRU, the two most recent access timestamps are stored for every data page. At the time of eviction, the algorithm randomly chooses 5 indexes from the tracking array and the minimum between two latest timestamps is taken for further comparison with corresponding minimums of four other pages that are chosen as eviction candidates.

Random-LRU-2 outperforms LRU by resolving the "one-hit wonder" problem: if a data page is accessed rarely but accidentally accessed once, it’s protected from eviction for a long time.

On-Heap Cache Eviction

When on-heap caching is enabled, you can use one of the on-heap eviction policies to manage the growing on-heap cache.

Eviction policies control the maximum number of elements that can be stored in a cache’s on-heap memory. Whenever the maximum on-heap cache size is reached, entries are evicted from Java heap.

Some eviction policies support batch eviction and eviction by memory size limit. If batch eviction is enabled, then eviction starts when cache size becomes batchSize elements greater than the maximum cache size. In this case, batchSize entries will be evicted. If eviction by memory size limit is enabled, then eviction starts when the size of cache entries in bytes becomes greater than the maximum memory size.

Eviction policies are pluggable and are controlled via the EvictionPolicy interface. The implementation of eviction policy is notified of every cache change and defines the algorithm of choosing the entries to evict from the on-heap cache.

Least Recently Used (LRU)

LRU eviction policy, based on the Least Recently Used (LRU) algorithm, ensures that the least recently used entry (i.e. the entry that has not been touched for the longest time) gets evicted first.

This eviction policy can be enabled in the cache configuration as shown in the example below. It supports batch eviction and eviction by memory size limit.

<bean class="org.apache.ignite.cache.CacheConfiguration">
  <property name="name" value="myCache"/>

  <!-- Enabling on-heap caching for this distributed cache. -->
  <property name="onheapCacheEnabled" value="true"/>

  <property name="evictionPolicy">
  	<!-- LRU eviction policy. -->
    <bean class="org.apache.ignite.cache.eviction.lru.LruEvictionPolicy">
    	<!-- Set the maximum cache size to 1 million (default is 100,000). -->
      <property name="maxSize" value="1000000"/>
    </bean>
  </property>

</bean>
CacheConfiguration cacheCfg = new CacheConfiguration();

cacheCfg.setName("cacheName");

// Enabling on-heap caching for this distributed cache.
cacheCfg.setOnheapCacheEnabled(true);

// Set the maximum cache size to 1 million (default is 100,000).
cacheCfg.setEvictionPolicyFactory(() -> new LruEvictionPolicy(1000000));

IgniteConfiguration cfg = new IgniteConfiguration();

cfg.setCacheConfiguration(cacheCfg);
var cfg = new IgniteConfiguration
{
    CacheConfiguration = new[]
    {
        new CacheConfiguration
        {
            Name = "cacheName",
            OnheapCacheEnabled = true,
            EvictionPolicy = new LruEvictionPolicy
            {
                MaxSize = 100000
            }
        }
    }
};

First In First Out (FIFO)

FIFO eviction policy, based on the First-In-First-Out (FIFO) algorithm, ensures that the entry that has been in the on-heap cache for the longest time will be evicted first. It is different from LruEvictionPolicy because it ignores the access order of entries.

This eviction policy can be enabled in the cache configuration as shown in the example below. It supports batch eviction and eviction by memory size limit.

<bean class="org.apache.ignite.cache.CacheConfiguration">
  <property name="name" value="myCache"/>

  <!-- Enabling on-heap caching for this distributed cache. -->
  <property name="onheapCacheEnabled" value="true"/>

  <property name="evictionPolicy">
  	<!-- FIFO eviction policy. -->
    <bean class="org.apache.ignite.cache.eviction.fifo.FifoEvictionPolicy">
    	<!-- Set the maximum cache size to 1 million (default is 100,000). -->
      <property name="maxSize" value="1000000"/>
    </bean>
  </property>

</bean>
CacheConfiguration cacheCfg = new CacheConfiguration();

cacheCfg.setName("cacheName");

// Enabling on-heap caching for this distributed cache.
cacheCfg.setOnheapCacheEnabled(true);

// Set the maximum cache size to 1 million (default is 100,000).
cacheCfg.setEvictionPolicyFactory(() -> new FifoEvictionPolicy(1000000));

IgniteConfiguration cfg = new IgniteConfiguration();

cfg.setCacheConfiguration(cacheCfg);
var cfg = new IgniteConfiguration
{
    CacheConfiguration = new[]
    {
        new CacheConfiguration
        {
            Name = "cacheName",
            OnheapCacheEnabled = true,
            EvictionPolicy = new FifoEvictionPolicy
            {
                MaxSize = 100000
            }
        }
    }
};

Sorted

Sorted eviction policy is similar to FIFO eviction policy with the difference that entries' order is defined by default or by a user defined comparator and ensures that the minimal entry (i.e. the entry that has an integer key with the smallest value) gets evicted first.

The default comparator uses cache entries' keys for comparison that imposes a requirement for keys to implement the Comparable interface. You can provide your own comparator implementation which can use keys, values, or both for entries comparison.

Enable sorted eviction policy in the cache configuration as shown below. It supports batch eviction and eviction by memory size limit.

<bean class="org.apache.ignite.cache.CacheConfiguration">
  <property name="name" value="myCache"/>

  <!-- Enabling on-heap caching for this distributed cache. -->
  <property name="onheapCacheEnabled" value="true"/>

  <property name="evictionPolicy">
  	<!-- Sorted eviction policy. -->
    <bean class="org.apache.ignite.cache.eviction.sorted.SortedEvictionPolicy">
      <!--
      Set the maximum cache size to 1 million (default is 100,000)
      and use default comparator.
      -->
      <property name="maxSize" value="1000000"/>
    </bean>
  </property>

</bean>
CacheConfiguration cacheCfg = new CacheConfiguration();

cacheCfg.setName("cacheName");

// Enabling on-heap caching for this distributed cache.
cacheCfg.setOnheapCacheEnabled(true);

// Set the maximum cache size to 1 million (default is 100,000).
cacheCfg.setEvictionPolicyFactory(() -> new SortedEvictionPolicy(1000000));

IgniteConfiguration cfg = new IgniteConfiguration();

cfg.setCacheConfiguration(cacheCfg);