Итерация по значениям из Guava Cache приводит к потере данных

Question

Я начал тестировать способы поиска ключа по значению в кеше Guava и заметил странное поведение, связанное с уровнем параллелизма. Я не уверен, является ли это ошибкой или неопределенным поведением или, возможно, даже ожидаемым, но не указанным.

Мой бенчмарк должен находить ключ по значению в Guava Cache, а я знаю, что это не обычное дело.

Это мой полный тестовый класс:

@Fork(4)
@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Warmup(iterations = 1, time = 100, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 4, time = 100, timeUnit = TimeUnit.MILLISECONDS)
public class ValueByKey {

    private Long counter = 0L;

    private final int MAX = 2500;

    private final LoadingCache<String, Long> stringToLong = CacheBuilder.newBuilder()
        .concurrencyLevel(1)
        .maximumSize(MAX + 5)
        .build(new CacheLoader<String, Long>() {
            public Long load(String mString) {
                return generateIdByString(mString);
            }
        });

    private final Map<String, Long> mHashMap = new Hashtable<>(MAX);
    private final Map<String, Long> concurrentHashMap = new ConcurrentHashMap<>(MAX);

    @Setup(Level.Trial)
    public void setup() {
        // Populate guava cache
        for(int i = 0; i <= MAX; i++) {
            try {
                stringToLong.get(UUID.randomUUID().toString());
            } catch (ExecutionException e) {
                e.printStackTrace();
                System.exit(1);
            }
        }
    }

    @Benchmark
    public String stringToIdByIteration() {
        Long randomNum = ThreadLocalRandom.current().nextLong(1L, MAX);

        for(Map.Entry<String, Long> entry : stringToLong.asMap().entrySet()) {
            if(Objects.equals(randomNum, entry.getValue())) {
                return entry.getKey();
            }
        }
        System.out.println("Returning null as value not found " + randomNum);
        return null;
    }

    @Benchmark
    public String stringToIdByIterationHashTable() {
        Long randomNum = ThreadLocalRandom.current().nextLong(1L, MAX);

        for(Map.Entry<String, Long> entry : mHashMap.entrySet()) {
            if(Objects.equals(randomNum, entry.getValue())) {
                return entry.getKey();
            }
        }
        System.out.println("Returning null as value not found " + randomNum);
        return null;
    }

@Benchmark
    public String stringToIdByIterationConcurrentHashMap() {
        Long randomNum = ThreadLocalRandom.current().nextLong(1L, MAX);

        for(Map.Entry<String, Long> entry : concurrentHashMap.entrySet()) {
            if(Objects.equals(randomNum, entry.getValue())) {
                return entry.getKey();
            }
        }
        System.out.println("concurrentHashMap Returning null as value not found " + randomNum);
        return null;
    }

    private Long generateIdByString(final String mString) {
        mHashMap.put(mString, counter++);
        concurrentHashMap.put(mString, counter);
        return counter;
    }

}

Что я заметил, так это когда я меняюсь .concurrencyLevel(1) на число, отличное от 1, я начинаю терять данные. Следующий выход получен из уровня параллелизма 4:

Iteration   1: Returning null as value not found 107
Returning null as value not found 43
Returning null as value not found 20
Returning null as value not found 77
Returning null as value not found 127
Returning null as value not found 35
Returning null as value not found 83
Returning null as value not found 43
Returning null as value not found 127
Returning null as value not found 107
Returning null as value not found 83
Returning null as value not found 82
Returning null as value not found 40
Returning null as value not found 58
Returning null as value not found 127
Returning null as value not found 114
Returning null as value not found 119
Returning null as value not found 43
Returning null as value not found 114
Returning null as value not found 18
Returning null as value not found 58
66.778 us/op

Я заметил, что никогда не теряю никаких данных при использовании HashMap или же HashTable для использования того же кода он также работает намного лучше:

Benchmark Mode Cnt Score Error Units ValueByKey.stringToIdByIteration avgt 16 58.637 ± 15.094 us/op ValueByKey.stringToIdByIterationConcurrentHashMap avgt 16 16.148 ± 2.046 us/op ValueByKey.stringToIdByIterationHashTable avgt 16 11.705 ± 1.095 us/op

Мой код неверен или Guava не может правильно обрабатывать секционированный HashTable с уровнем параллелизма выше 1?

• Параметр уровня параллелизма используется для внутреннего разделения таблицы таким образом, чтобы обновления могли происходить без конфликтов.
• Идеальным параметром будет максимальное количество потоков, которые могут потенциально получить доступ к кэшу за один раз.

Answer 1

Нет кеша гарантирует постоянное попадание в кеш

Наличие / отсутствие данных в кеше определяется политикой вытеснения (и в первую очередь данными, загружаемыми в кеш).

Так как вы использовали CacheBuilder.maximumSize(MAX + 5) Ваш кэш будет использовать высвобождение на основе размера и начнет удалять элементы, прежде чем он достигнет заданного максимального размера.

При уровне параллелизма, равном 4, Guava Cache воспроизводит его безопасно и устанавливает чуть более низкий порог выселения, что имеет смысл, поскольку элементы могут продолжать поступать по мере их выселения.

Вот почему ваши элементы начинают "исчезать".

Чтобы проверить это, заставьте ваш класс реализовать RemovalListener интерфейс:

public class ValueByKey implements RemovalListener<String, Long> { 
    //...
    @Override
    public void onRemoval(RemovalNotification<String, Long> notification) {
        System.out.println("removed: " + notification.getKey() + " -> " + notification.getValue());
    }
    //...
}

... и во время выполнения тестов вы заметите выселения, которые соответствуют отсутствующим значениям:

# Warmup Iteration   1: 
removed: 110c0a73-1dc3-40ee-8909-969e6dee0ea0 -> 3
removed: 6417015a-f154-467f-b3bf-3b95831ac5b7 -> 6
removed: 5bc206f9-67ec-49a2-8471-b386ffc03988 -> 14
removed: 3c0a33e1-1fe1-4e42-b262-bf6a3e8c53f7 -> 21
Returning null as value not found 14
Returning null as value not found 14
Returning null as value not found 3
64.778 us/op
Iteration   1: 
Returning null as value not found 21
Returning null as value not found 21
Returning null as value not found 6
37.719 us/op
[...]

Я могу представить, что расчет порога для выселения может быть сложным, но на моей машине увеличение максимального размера на 5% (CacheBuilder.maximumSize(Math.round(MAX * 1.05))) предотвратил ВСЕ выселения при запуске тестов.