Newly added entries are evicted immediately in 3.8.2 when LRU or LFU strategy is used

[d123456temp]

Despite comments in #7634, this is definitely NOT fixed for the LRU and LFU eviction strategies in 3.8.2. Newly added items are still being evicted straight away (while really-really old entries are kept intact) when Map is working at almost-full size (so it reached max-size count).

I discovered this during load testing when several independent client are writing c.a. 3000 entries each, and then read exact these entries. With any of the eviction strategies enabled, I have a lot of null reads for these freshly added entries despite the fact that there are 1500000+ better candidates for eviction.

This is the first bad experience I had with Hazelcast. It would be a shame as this is pretty much very important, basic functionality that should work without any issues.

I could somehow understood it for LFU strategy in case of read-only-once data, but this should never-ever happen for LRU strategy.

Map configuration:

                <in-memory-format>BINARY</in-memory-format>
		
		<backup-count>1</backup-count>
		<async-backup-count>0</async-backup-count>
		<read-backup-data>false</read-backup-data>
			
		<time-to-live-seconds>43200</time-to-live-seconds>
		<max-idle-seconds>0</max-idle-seconds>
		<eviction-policy>LRU</eviction-policy>
		<max-size policy="PER_NODE">2000000</max-size>
		<eviction-percentage>25</eviction-percentage>

I'm observing this incorrect behavior when maps are populated with ~2000000, so close to the max-size above.

[jerrinot]

hi @d123456temp,

the fix for #7634 only makes sure the very element being added is not evicted immediately. However subsequent step can still evict an item stored in a previous step.

Let me check the LRU strategy impl. The eviction algorithm is probabilistic so some error is expected.

[jerrinot]

hello @d123456temp,

I think the issue you are observing is caused by the fact the out-of-the-box LRU policy does not consider entry creation as a usage. Only entry access (get) is considered as a usage. The good news is that you can implement your own eviction strategy and tweak this behaviour, it's fairly easy:

import com.hazelcast.config.Config;
import com.hazelcast.config.EvictionPolicy;
import com.hazelcast.config.MapConfig;
import com.hazelcast.config.MaxSizeConfig;
import com.hazelcast.core.EntryView;
import com.hazelcast.core.Hazelcast;
import com.hazelcast.core.HazelcastInstance;
import com.hazelcast.core.IMap;
import com.hazelcast.map.eviction.MapEvictionPolicy;


public class LruTest {
    public static void main(String[] args) {
        String mapName = "myMap";
        int maxSize = 100000;
        int insertCount = 200000;
        int tailToCheck = 10000;
        boolean useCustomEvictionPolicy = true;


        Config config = new Config();
        MapConfig mapConfig = config.getMapConfig(mapName);

        MaxSizeConfig maxSizeConfig = mapConfig.getMaxSizeConfig();
        maxSizeConfig.setMaxSizePolicy(MaxSizeConfig.MaxSizePolicy.PER_NODE).setSize(maxSize);
        if (useCustomEvictionPolicy) {
            MapEvictionPolicy mapEvictionPolicy = new MyMapEvictionPolicy();
            mapConfig.setMapEvictionPolicy(mapEvictionPolicy);
        } else {
            mapConfig.setEvictionPolicy(EvictionPolicy.LRU);
        }

        HazelcastInstance instance = Hazelcast.newHazelcastInstance(config);
        IMap<Integer, Integer> myMap = instance.getMap(mapName);

        for (int i = 0; i < insertCount; i++) {
            myMap.put(i, i);
        }
        System.out.println(insertCount + " Entries Inserted");

        int missCounter = 0;
        for (int i = insertCount - tailToCheck; i < insertCount; i++) {
            if (myMap.get(i) == null) {
                missCounter++;
            }
        }
        System.out.println("Miss counter: " + missCounter);

        instance.shutdown();
    }

    private static class MyMapEvictionPolicy extends MapEvictionPolicy {
        @Override
        public int compare(EntryView e1, EntryView e2) {
            long accessTime1 = e1.getLastAccessTime();
            long accessTime2 = e2.getLastAccessTime();
            if (accessTime2 < accessTime1) {
                return 1;
            } else if (accessTime1 < accessTime2) {
                return -1;
            } else {
                long creationTime1 = e1.getCreationTime();
                long creationTime2 = e2.getCreationTime();
                if (creationTime2 < creationTime1) {
                    return 1;
                } else if (creationTime2 > creationTime1) {
                    return -1;
                } else {
                    return 0;
                }
            }
        }
    }
}

When the useCustomEvictionPolicy flag is set to false then it reports about 891 missing entries. When I use the custom policy then no missing entry is reported. You can tweak the policy as you see fit.

Please bear in mind this is still probabilistic - you can play with the tailToCheck parameter to see the behaviour.

[mmedenjak]

This is an internal behaviour fix and may be done without breaking changes. Moving to 4.1.

[pratikgr]

@jerrinot and @mmedenjak
The issue still persist even after making the custom Eviction Policy as mentioned above. However, I see that issue is not happening if we have the partition count as only set to 1. By default the partition count are 271. So if I have data less than 271 none of the Eviction policy works correctly and I see that eviction happening very random.

For example if I fill 50 objects and apply eviction to remove the 1st created object in cache through custom policy it may still not evict the first one but it may evict the just entered object in cache.

Does the @Compare method of custom policy only compares within one partition?

[growlingchaos]

In my opinion the meaning of "usage" in LRU/LFU policy has to be described in the documentation in the section 7.2.4.

[SiddhantAgarwal17]

We observe a similar behavior with Hazelcast 4.0.1. Here is the configuration that we rely on:

      in-memory-format: NATIVE
      backup-count: 1
      time-to-live-seconds: 86400
      max-idle-seconds: 0
      eviction:
        eviction-policy: LRU
        max-size-policy: FREE_NATIVE_MEMORY_PERCENTAGE
        size: 20

This seems to be a very basic behavior which we expect to work. What we tried was a PUT followed by an immediate GET. Out of the 10,000 entries that we ran for, we experienced it for about 25 entries. However, in one or two instances this behavior wasn't observed.

[Holmistr]

Related: #18614

[ahmetmircik]

should be closed by closed by #18624